Файл: Сирл, С. Матричная алгебра в экономике.pdf

б) Теперь предположите, что у производителя имеется план другой реклам­ ной кампании, проведение которой стоит столько же, столько и проведение предыдущей, и единственным результатом которой будет увеличение вероят­ ности удержания своих покупателей с 0,8 до 0,9. Следует ли выбрать эту кампа­ нию?

10.Рассмотрите пример с машиной в параграфе 5 данной главы. Предполо­ жите, что ремонт машины в случае, если она требует регулировки, стоит не 0,90 доллара, а 1,40 доллара. Если осталось всего три периода до того момента, как машину должны разобрать и перестроить, то какова оптимальная стратегия ре­ монта для каждого из трех периодов?

11.Предположите, что машина переходит из состояния 1 (работает хорошо)

всостояние 2 (требуется регулировка) и обратно с такими вероятностями пе­ рехода:

Предположите, что в случае, если машина в течение дня находится в состоянии 1, то она приносит 100 долларов прибыли, а в случае, если она в течение дня на­ ходится в состоянии 2, то приносит убытков на 50 долларов.

а) Подсчитайте ожидаемую дневную прибыль.

б) Теперь предположите, что машину можно починить за 120 долларов, причем ремонт может быть проведен столь быстро, что машина получает возмож­ ность работать в состоянии 1 в течение полного рабочего дня. Предполагая, что переходы из состояния в состояние происходят в конце рабочего дня, вычислите стационарное ожидаемое вознаграждение за период при условии, что выполняет­ ся решающее правило «всегда ремонтировать машину, если она этого требует». Какое из решающих правил (не ремонтировать, либо ремонтировать) дает большее стационарное вознаграждение?

в) Если бы оставалось всего несколько дней до момента, когда машину за­ менят другой моделью, то следовало ли бы тогда придерживаться оптимальной стратегии, найденной в ответе на вопрос б? Объясните свой ответ.

Предположите, что текущие расходы на хранение одной единицы в течение недели равны 1 доллару, и что одна продажа приносит 5 долларов прибыли. Всякий запрос, который не может быть удовлетворен из запасов на складе, теряется. Какому из решений нужно следовать, чтобы максимизировать стацио­

с машиной в параграфе 5 равно 1,33 доллара за период, если машину ремонти­ руют, когда это требуется.

14. Для произвольной матрицы переходных вероятностей Р и произволь­ ного целого п покажите:

(Указание. Используйте вектор 1, каждый элемент которого равен единице.) 15. Проверьте, что для любой матрицы переходных вероятностей Р матри­

ца (I—Р) вырожденная.

2 2 2

IX ЛИНЕЙНОЕ

ГЛАВА П РОГРАММИ РОВАНИЕ

Линейное программирование — аналитический аппарат (создан­ ный Данцигом, см. [5])*, привлекший к себе большое внимание в эко­ номике в последние двадцать лет. Это метод максимизации (или ми­ нимизации) линейной функции, учитывающий множество линейных ограничений. Наиболее распространенное его применение заключает­ ся в распределении дефицитных ресурсов Между несколькими вида­ ми деятельности для максимизации или минимизации некой «цели», например такой, как прибыли или издержки. Метод линейного про­ граммирования обеспечивает решения широкого класса такого рода задач, возникающих в хозяйстве.

1. ПРОБЛЕМА МАКСИМИЗАЦИИ

а) ГРАФИЧЕСКОЕ РЕШЕНИЕ

Пример. Небольшая механическая мастерская выпускает два типа изделий, причем изделия каждого типа изготовляются двумя разными машинами. А именно, каждая единица продукта 1 (первый тип изделий) требует трех часов работы на машине I и двух часов работы на машине II; каждая единица продукта 2 (второй тип изделий) тре­ бует двух часов на машине I и трех часов на машине II. Машину I можно использовать только восемь часов, а машину II — только семь часов в день. Предположим, что прибыль, получаемая от продажи единицы каждого продукта, равна 20 и количество любого продукта, которое может быть продано, не имеет ограничения. Задача состоит

При этом надо учитывать ограничения, определяемые фондом машин­ ного времени.

Прежде всего представим задачу в алгебраической форме: пусть хх обозначает число единиц продукта 1 , х2 — число единиц продукта 2, a z — общую прибыль; надо найти максимум функции

[;г = 20ЛУ+ 20х2,

*Первая работа, положившая начало линейному программированию, как известно, принадлежит советскому ученому академику Л. В. Канторовичу

(1939 г.) — Прим. ред.

224

равенствами в любую сторону; 3) решения должны быть не­

отрицательными.

Свойства 2 и 3 обычно предполагают, что существует довольно большое число решений, удовлетворяющих поставленным условиям. Например, если задачу (1) решить графически (рис. 1), заштрихо­ ванная площадь будет удовлетворять всем четырем условиям, т. е.

площадь называется областью допустимых решений. Задача сводится

кнахождениию такой точки (лу, х2) в области допустимых решений,

вкоторой значение целевой функции максимально.

положим карандаш на любую из них и будем удалять его от начала координат, сохраняя его параллельность двум пунктирным линиям.

Карандаш изображает линию 20хх + 20х2 = г, где z увеличивается по мере того, как он удаляется от начала координат. Так как целью является получение возможно большего значения г, то карандаш надо двигать вверх до тех пор, пока он не коснется области допусти­ мых решений только в одной точке; эта точка есть оптимальное ре­ шение задачи линейного программирования. Оптимальной является точка (2; 1), в ней z — 20хх + 20х3 = 60. В любой другой точке об­ ласти допустимых решений целевая функция не равна 60, так как каж­ дая из этих точек лежит на линии 20хх + 20х3 = z, где г < 60. Пунк­ тирные линии иногда называют линиями равной прибыли. Таким обра­ зом, в любой точке на л и н и и 20х\ + 20х2 = 60 можно получить при­ быль 60; однако только одна точка на этой линии допустима данными условиями задачи.

б) СВОЙСТВО УГЛОВЫХ ТОЧЕК

Графический метод решения задач линейного программирования удобен в случае, когда область допустимых решений имеет два измере­ ния; но его трудно применять, когда она описывается тремя или более измерениями. В этом случае оптимальные решения следует искать другими способами. Здесь рассматривается специальный метод реше­ ния, так называемый модифицированный симплекс-метод, основан­ ный на свойстве, по которому оптимальное решение является угловой точкой области допустимых решений.

системы уравнений, полученной выбором я ограничений, которые рас­ сматриваются как равенства, из ограничений, определяющих область допустимых решений. Если угловая точка удовлетворяет оставшимся ограничениям, то ее называют допустимой угловой точкой (или угло­ вой точкой области допустимых решений)1.

Например, в рассмотренной задаче (1) четыре допустимые угловые

точки: (0; 0), (J; 0j, (О; ^), (2; 1). Они являются решениями следую­

щих систем уравнений (составлены из условий):

1 Исключения имеют место в следующих случаях: а) если область допустимых решений не ограничена, то оптимальное решение может быть не определено; б) когда условия таковы, что не существует области допустимых решений. Та­ кие случаи в данной главе не рассматриваются.

226