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

мы приведем два примера такого рода приложений и сошлемся на ряд других.

Пример. Проблема выбора способов рекламы. Проблема размеще­

щать свои рекламные объявления на местной радиостанции или в еже­ месячном журнале. Далее предположим, что мы заинтересованы лишь в двух группах потребителей: домохозяйки из семей с годовым дохо­ дом свыше 10 000 долларов и домохозяйки из семей с доходом ниже 10 000 долларов. Мы принимаем допущение, что лица первой группы покупают в два раза больше, чем лица второй группы, и желаем мак­ симизировать склонность к покупкам, основываясь на этом допущении. Одна единица рекламы на радио стоит 90 долларов и доходит (в сред­ нем) до двух человек из первой группы и семи из второй. Одна едини­ ца рекламы в журнале стоит 120 долларов; она достигает шести чело­ век из первой группы и трех из второй1. Управляющий требует, чтобы было использовано не менее шести единиц радиорекламы и не более двенадцати единиц журнальной рекламы (т. е. не более одной единицы в месяц). В целом затраты на рекламу равны 1740 долларам в год.

Мы формулируем эту задачу как задачу линейного программиро­ вания! Положим, что

хх= количеству единиц радиорекламы и

х2 = количеству единиц журнальной рекламы.

Введя избыточную переменную, две дополнительные и одну искусст­ венную переменную, получаем:

максимизировать г = Илу + 15х2 — Ю 000xd

при условии, что хг — Xsi + xd — 6,

х2 + Xs2 = 12,

XB данном примере предполагается, что круг читателей журнала не пере­ секается с аудиторией радио.

240

90xx -f- 120х3 “Ь xs3 = 1 740,

Х-! > 0,

х2 > 0.

После записи в такой форме можно применять симплекс-метод для решения задачи.

Пример. Транспортные задачи. Особым типом задач линейного программирования являются так называемые транспортные задачи (иногда их называют задачами Хичкока—Купманса, по фамилиям тех, кто впервые их решил). Созданный Данцигом симплекс-метод был на самом деле сформулирован для решения именно этого типа задач, хотя он с неменьшим успехом может применяться и для решения более общих задач линейного программирования. Любая задача, в которой речь идет о т пунктах отправления, п пунктах назначения, о постоян­ ных затратах на производство единицы продукта в каждом из пунктов отправления и на ее перевозку из любого пункта отправления в любой пункт назначения, может решаться как транспортная задача линей­ ного программирования. Существуют специальные методы решения таких задач, но мы приведем лишь пример задачи, относящейся к это­ му классу.

Предположим, что некоторый производитель изготовляет некоторый продукт на трех заводах, при этом затраты на производство единицы продукта на этих заводах составляют 0,50; 0,60 и 0,45 доллара соот­ ветственно. Он владеет также четырьмя крупными магазинами, через которые он должен удовлетворить спрос на 50, 55, 40 и 60 единиц продукта соответственно. Затраты на транспортировку единицы про­

сформулирована как транспортная задача линейного программиро­ вания.

Пусть ха 1 — число единиц продукта, произведенных на заводе А и отправленных в магазин 1 ; затраты на единицу типа ха i будут складываться из затрат на производство в Л и затрат на транспорти­ ровку из А в 1, т. е. 0,50 + 0,05 = 0,55. Пусть хв 2 равно числу еди­ ниц, произведенных в В и отправленных в 2; соответствующие затра-

241

гы равны 0,60 + 0,06 = 0,66 и т. д. Всего мы имеем 12 таких пере-- менных. Целью является минимизация затрат. Формулировка данной задачи на языке линейного программирования выглядит так:

минимизировать г = 0,55хл1 + Q J7xB\ Ц 0,5 lxci +

-f 0,67х.42 -г 0,66хв2 Ч~ 0,71хс2 +

0,62л:лз + 0,73хвз + 0,57хСз +

; 0,51хд4 Ч- 0,64хд4 Ч- 0,56 хс4

при условии, что Ха i Ч- хв 1 Ч- Хс 1 = 50 (т. е. общее количество продукта, отправленного в магазин 1, равно 50),

Х д2 Ч~ %В2 Ч~ Х С2 = 5 5 ,

Хаз Ч~ Хвз Ч' хсз = 40,

и при этом не могут быть превышены производственные возможности заводов. Обратите внимание на то, какую форму имеет матрица А, когда эта задача записывается в матричной форме:

Эта форма типична для транспортных задач. Можно пополнить спи* сок переменных дополнительными и избыточными переменными и обра­ зовать матрицу А *, если необходимо, можно с помощью искусственных переменных получить первоначальное решение.

242

Интересное свойство приведенной матрицы А состоит в том, что

в параграфе 5, при применении симплекс-метода последовательно прибегают к обращению текущего базиса для получения решения. Единственное различие, которое следует. принимать во внимание, связано со значением определителя, но если он всегда равен + 1 или

—1 (0 не используется в расчетах, так как для соответствующих под­ матриц не существует обратных), то мы начинаем расчет с целочислен­ ной матрицы и далее будем иметь дело лишь с целочисленными матри­ цами. Это важный аспект транспортных задач линейного программиро­ вания: они гарантируют целочисленность решения, хотя в общем, случае для задач линейного программирования такая гарантия невоз­ можна. Существуют алгоритмы получения наилучшего целочисленно­ го решения для произвольной задачи линейного программирования,, но до сих пор не выяснены их вычислительные возможности для боль­ шинства задач (см. Хедли [10]). Таким образом, этот аспект транспорт­ ных задач представляет известный интерес.

Некоторые задачи планирования производства, расстановки персо­ нала и планирования работы машин имеют форму транспортных задач линейного программирования, а это общая форма широкого круга задач, решение которых обычно требует малого объема вычислений.

Приведенные примеры иллюстрируют лишь две области возможных, приложений линейного программирования. Упомянем некоторые дру­ гие: оно было применено в проблемах финансирования капиталовло­ жений (см. Вейнгёртнер [13], Чарнес, Купер и Миллер [4]); широкий класс проблем планирования производства был сформулирован в виде задач линейного программирования; проблема составления авиарасписанпя с учетом случайных вызовов была решена с помощью мето­ дов линейного программирования; экономическая теория равновесия анализировалась по схеме линейного программирования; это же от­ носится и к играм двух лиц с постоянной суммой (см. упражнения главы II). Этот список ни в коей мере не является исчерпывающим,, но он дает некоторое представление о возможных областях приложе­ ния и типах задач, решаемых с применением методов линейного про­ граммирования. Для дальнейшего изучения роли линейного програм­ мирования в экономической теории мы отсылаем читателя к работе Дорфмана, Самуэльсона и Солоу [7]; что касается приложения к про­ блемам хозяйства, то мы сошлемся на Бирмана, Бонини и Госмана [3], Хедли [9] или на Данцига [6].

5. МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД

Хотя существуют машинные программы, пригодные для решения задач линейного программирования в самой общей постановке, было бы весьма полезно рассмотреть в данной работе процесс их решения с применением симплекс-метода. Модифицированный симплекс-ме­ тод отличается в отношении некоторых деталей расчетного характера

243»

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

соответствует угловой точке х = О (нулевому вектору, представляю­ щему начало координат), которая является допустимой в силу предпо­

ствующая ему переменная в х* из числа небазисных переменных (т. е. на предшествующем шаге приравненных нулю) обеспечила возраста­ ние значения целевой функции. Затем выбирают столбец (переменную), который должен быть изъят из существующего базиса; при этом необходимо, чтобы для получаемого нового Хв = В^1Ь сохранилось свойство допустимости; хв представляет базисные переменные, а все прочие переменные равны нулю. Это завершает процесс замены, мы получили новый базис Внов и соответствующее ему решение Х в , новНовому базису соответствует новая угловая точка, и, как мы увидим впоследствии, значение z в новой угловой точке не меньше, чем значе­ ние г в предыдущей угловой точке (а на самом деле обычно больше). Процесс повторяют (итерируют) до тех пор, пока можно найти новую замену (допустимую угловую точку), при которой возрастает (или по крайней мере не убывает) значение целевой функции; когда подоб­ ные замены уже невозможны, найденная угловая точка представляет собой оптимальное решение. Каждая допустимая угловая точка участвует в процессе не более чем один раз, и, поскольку множество всех допустимых угловых точек конечно, данный процесс выйдет на оптимальное решение за конечное число итераций1.

Для того чтобы применить модифицированный симплекс-метод, необходимо записать вместе целевую функцию и ограничения А*х* =

1Хотя можно построить примеры, когда этот процесс «зацикливается» (т. е. такие примеры, в которых некоторое заданное множество угловых точек пери­ одически участвует в процессе и при этом не происходит возрастания значений целевой функции), авторы выражают сомнение в том, что подобный случай ког­ да-либо встретится при решении практических задач.

244