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

п р и у с л о в и и , ч т о x 1 J r x 2 — х + + х ~ - j - x s i = 6,

2ху + х+ —х - - xS2 + xdl = 1 ,

*2+ х+ —.X - + xd2■= 4,

2%! - j -л'2— xsз + xd3 —3,

В первоначальный базис входят переменные (xsx, xdl, xd2, xd3), связанные с единичной матрицей 4-го порядка. М —достаточно большое число, чтобы обеспечить последовательное удаление переменных xdi, xd2, xd3 из. базиса.

е) ДВОЙСТВЕННАЯ ЗАДАЧА

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

ме:

максимизировать z = с'х

Первая из.этих задач называется основной, а вторая — двойственной. Если исходная задача (12), то двойственной к ней будет (13), если ис­ ходная задача (13), то двойственной к ней будет (12). Задача, двойст­ венная к двойственной задаче, идентична основной (см. упражнение 6). Двойственная задача играет важную роль в теории и приложениях линейного программирования; она полностью проанализирована у Хедли [9] и Данцига [6]. Легко видеть, что в случае, когда матрица А имеет размеры т X п, оптимальное решение двойственной задачи у0 будет /n-мерным вектором-столбцом. Двойственная задача важна именно потому, что элементы этого вектора представляют собой гра­ ничные значения каждого из ограничивающих пределов 6;. В большин­ стве хозяйственных задач величины 6г — это некоторые дефицитные ресурсы, находящиеся в распоряжении лица, принимающего решение. Для него важны сведения о том, насколько увеличится прибыль или уменьшатся затраты при увеличении на единицу объема того или иного из дефицитных ресурсов.

Пример. Задача (1) из примера на стр. 224 формулировалась так:

максимизировать z = 20хг + 20х2

236

при условии, что Зхг + 2х2 s£t 8,

Двойственная к данной задача имеет вид1: минимизировать г = 8ух + 7г/2

2г/г + 3f/2 > 20,

l/i > 0,

t/2 ^ 0.

Пример. Задача (8) из примера на стр. 231 формулировалась так: минимизировать г = 0,2хх + 0,03х2

при условии, что 0,5хх + 0,02х2 > 70,

0,2хх + 0,6х2 > 150,

хх > 0,

х2 > 0.

Двойственная к данной задача имеет вид: максимизировать z = 70уг + 150г/2

Уг > 0.

Двойственные переменные называют также теневыми ценами, или

симплексными мультипликаторами.

Пример. Двойственная задача (14) графически изображена и ре­ шена на рис. 3; оптимальным решением является точка (4; 4).

Как уже говорилось, элементы оптимального решения двойствен­ ной задачи представляют крайние значения (теневые цены) ограни­ чивающих пределов bt. Например, поскольку уг = 4, дополнительная единица рабочего времени машины I принесет четыре дополнительных единицы прибыли (первое ограничение основной задачи представляло производственные возможности машины I). В самом деле, если маши­ на I может работать не 8, а 9 часов, то оптимальным решением основной*

*В данном случае матрица технологических коэффициентов А равна А'. Это не является общим случаем.

237

задачи будет точка которой соответствует общая прибыль*

равная 64, т. е. на 4 единицы больше, чем прибыль, равная 60, в первом случае. (Читатель может проверить эти результаты графически, пере­

при цене 3 доллара в час? Теневые цены, полученные при решении двойственной задачи, оказываются полезными лишь

в некотором определенном диапазоне производственных возможностей. Как только мы арендовали дополнительные возможности машины II* мы изменили точку, соответствующую базису, что приводит к измене­ нию теневых цен. Определение области, внутри которой теневые цены остаются постоянными, называется анализом чувствительности, а из­ учение поведения теневых цен при непрерывном изменении производ­ ственных возможностей называется параметрическим программиро­ ванием. Для дальнейшего ознакомления с этими вопросами см. Хедли

[9]или Бирман, Бонини и Госман [3].

Фундаментальным соотношением между основной и двойственной

задачами является следующее утверждение: если х% и у%— соответ­ ственные оптимальные решения этих двух задач, то1

т. е. в соответствующих каждой из задач оптимальных точках целевые функции принимают одно и то же значение. Давайте перегруппируем элементы векторов с*, Ь*, х* и у* таким образом, чтобы x f = lxв х], с*' = [св 0] и уо' = [у0 ys], где хв — базисные переменные; х —■

!С м . Х е д л и [9 ].

2 3 8

небазисные переменные (т. е. равные нулю);'г/0— обычные переменные двойственной задачи; ys — избыточные переменные, соответствующие (13) в модифицированной симплексной форме, ас* и Ь* изменены соот­

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

Как отмечалось, обычные двойственные переменные у 0’ = с вВ’ ~г можно интерпретировать как крайние значения (теневые цены) до­ полнительных единиц для каждого из ресурсов, обозначенных через ft*. Если оптимальное решение задачи (12) содержит некоторые допол­ нительные переменные, то таким ресурсам соответствуют нулевые предельные значения. Предположим, что t'-e ограничение не является связывающим, т. е. соответствующая ему дополнительная переменная положительна в точке оптимума. Предположим далее, что с этой до­ полнительной переменной связан t-й столбец1 В. Этот столбец со­ стоит из нулей, за исключением t-ro элемента, который равен 1 , и можно показать, что г'-й столбец матрицы В -1выглядит точно также (см. упражнение 15). Следовательно, i-й элемент СвВ-1 равен cbi- Однако в силу того, что переменная является дополнительной, соот­ ветствующий ей коэффициент затрат равен нулю, так что yt в векторе у'о = с'вВ~1 равен нулю. Следовательно, двойственная переменная г/j, соответствующая несвязывающему ограничению (ограничению i), равна нулю.

переменных при управлении операциями децентрализованной фирмы, для которой проблема максимизации прибыли может быть сформули­ рована в виде задачи линейного программирования. Гэйл [9] и Лан­ кастер [1 1 ] предпочли аналогичный подход для анализа ценовых ус­ ловий конкурентного равновесия. Более подробное изложение теории двойственности и ее интерпретации может быть найдено у Хедли [9], Данцига [6], Дорфмана, Самуэльсона и Солоу [7],. в то время как в книге Бирмана, Бонини и Госмана [3] показано применение двойст­ венных переменных в многочисленных ситуациях, связанных с приня­ тием решений.

4. ПРИЛОЖЕНИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Линейное программирование — общий метод решения важного класса задач в области хозяйства и экономики. В данном параграфе

’-Рассматриваемый столбец может стоять в В на любом месте, это никак не влияет на результаты (см. упражнение 15).

2 3 9