§ 9.3. применение двойственности в однопродуктовой задаче

§ 9.3. применение двойственности в однопродуктовой задаче

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

Предположим, что некоторое предприятие, производящее однородную продукцию, может в процессе производства использовать п различных технологий. Пусть т — число расходуемых ресурсов; Ь, — доступное на период планирования количество ресурса i(i =1,2, ...,m)Xj — интенсивность применения технологии j (j 1,2, и). В конкретных задачах мерой интенсивности может служить: количество произведенной по данной технологии продукции, длительность применения технологии, число занятых рабочих и т. п.

Предположим также, что затраты z,y ресурса / при работе по технологии /линейно зависят от интенсивности ее применения:

zij = aiixr

где atj — количество единиц ресурса /, расходуемых при использовании технологии /с единичной интенсивностью.

Система ограничений по ресурсам имеет вид

aux[+al2x2+... + ainxn<bl, . а2хх+а22х2+...+а2пхп<Ьъ

ат х + ат2 *2 + + атп хп 5 bnf

Кроме того, выполняются условия неотрицательности

х,>0, х2>0,.... хп>0. (9.15)

Выпуск продукции/составит

f=qlxl+q2x2+ ...+q„xn,

где qj — количество продукции, производимой при единичной интенсивности применения технологии у.

Таким образом, мы приходим к следующей задаче линейного программирования:

/-> max при условиях (9.14), (9.15). (916)

Решение задачи (9.16) должно дать ответ на вопрос: с какой интенсивностью следует использовать каждую из технологий, чтобы Добиться максимального выпуска продукции?

Заметим, что в случае, когда интенсивность применения технологии измеряется количеством произведенной по данной технологии продукции, имеем:qx = q2 = ... = qn = I. Далее мы предполагаем, что все коэффициенты atj неотрицательны и для каждой технологии j= 1,2, п хотя бы один коэффициент aij*§. Последнее условие означает, что мы не рассматриваем технологии, производящие продукцию из ничего. Этих естественных предположений достаточно для разрешимости задачи (9.16). Действительно, во-первых, допустимое множество не пусто, так как имеется нулевое решение

x (О, 0,0), во-вторых, из ограничений (9.14) и (9.15) следует, что

xi < —, поэтому целевая функция ограничена. Разрешимость теперь

следует из теоремы 1 § 7.2.

Запишем ограничения двойственной задачи:

а\У+а2У2+ +amXym>qx,

, anyx+a22y2 + ...+am2ym>q2, (9 17)

апУ +а1пУг + -+атПУт^Ят,

^, >0, ^2>0,.... ут>0. (9.18)

Пусть ф = Ьху + Ь2у2 + ... + ЬпУт. Тогда двойственная задача имеет вид

ф-утш при условиях (9.17), (9.18). (9.19)

Если задача (9.19) допускает более простое решение, чем непосредственное решение задачи (9.16), то для решения задачи (9.16) имеет смысл воспользоваться теоремой равновесия. Проиллюстрируем эту идею на следующем примере.

Пример. Предприятие, выпускающее однородную продукцию, использует четыре технологии, применение которых связано с расходом двух ресурсов. Затраты ресурсов на единицу продукции

указаны в следующей таблице.

Пусть Xj — количество продукции, произведенной по технологии/ Найдем вектор X* = (х, х, х3, х), для которого выпуск продукции /=*| + х2 + хъ + х4 максимален при условии, что число доступных единиц ресурса і (і = 1, 2) равно b-.

Для данного примера общая задача (9.16) приобретает вид

(9.20)

I 1 1 1 ,и 3*1 + 4*2 + 6*3 + 8*4 ^°1>

II 1 1

6*1 +4*2+3*3+2*4 ^2>

xj>0 (/=1,2,3,4), /=*! +х2 + *з + *4 ~* max,

а общая задача (9.19)

1 l^i ^, + ^2>1,

(9.21)

1 1 -> і 4^1 +4^2 ^ 1>

1 1 і

-ух + у2>,

1 1 ^ t ^ух+^у2>,

mm,

у{ >0, у2>0, У = ЬУ+Ь1у2

Прямое решение задачи (9.20) затруднено тем, что допустимое множество зависит от параметров bl и Ь2. В то же время в задаче (9.21) допустимое множество не зависит от параметров bx,b2, а сама задача допускает решение графическим методом.

Пусть хих2, хъ, х4,у{,уг — участвующие в теореме равновесия невязки задач (9.20) и (9.21):

Построим на координатной плоскости У,у2 следующие четыре прямые:

х{ = 0, х2 = 0, jc3 = 0, *4 = 0.

Именно эти прямые (вместе с прямыми у у 0 и у2 = 0) ограничивают допустимое множество задачи (9.21).

Определив для каждой прямой, с какой стороны от нее расположено допустимое множество, находим это множество и его угловые точки:/1(0; 6), Л(2; 2), С(4; 1), D(8; 0) (рис. 9.1).

0;

w Ьг Случаи І: т— Є

Решая задачу (9.21) графическим методом, находим оптимальное решение Y* = А, если^*^ И]Г7*0 Е°ЛИ ЖЄЇ^=0' Т° множество оптимальных решений Y* — луч с началом в точке А, направленный по оси у2 вверх. Если жеуу= . то Y* =ЛВ — отрезок.

Итак, в случае I среди оптимальных решений всегда имеется точка Л. На рис. 9.1 видно, что точка А не принадлежит прямым х2 = 0, *з = 0, х4 = 0 и у2 = 0.

Следовательно, для Y* =А имеем:

х2 * 0, хъ * 0, jc4 * 0, у* 0.

По теореме равновесия получаем условие оптимальности для допустимого решения задачи (9.20):

х2 = 0, хъ = 0, х4 = 0, у2 = 0,

которое можно записать в виде следующей системы линейных уравнений:

{х = ь\>

х2 = *з = х4 = 0.

Откуда х* = (66,, 0,0,0).

Случай II: ^є(д'. 2

Находим оптимальное решение Y* = В. Так как В не принадлежит прямым,х4 = 0,ух =0,_у2 = 0,тодля Г* = В,имеем:

£4*0,j^*0,j£*0.

Из теоремы равновесия получаем условие оптимальности для X*:

111, 3*1 + 4*2 + 5*3 = °\>

1 1 1 6*1 + 4*2+ з^З = *2хА = 0.

Выражая xt и дс3 через х2, получим:

х, =46, -26, jx2> х3 = 462 26, -^х2.

Учитывая неотрицательность ^ х2 и х3> находим границы изменения х2:

х2 > 0;

б) х, s 0 => лг2 < 8*, -462;

x3so => х2£862-46,.

(9.22)

Пусть М = min { 86, 462, 862 46, }. Тогда всякое оптимальное решение задачи (9.20) в случае II представляется в виде

X * = 46, 2й2 ±х2, х2, 462 26, ^с2, 0

гдех2Є[0,Л/].

Таким образом, множество всех оптимальных решений { X*} — это отрезок концы которого получаются путем подстановки х2 = 0 и х2 = М в равенство (9.22).

Итак, в случае II имеем { X*} = PQ, где

^ = (46, 2*2,0,462-26,, о) и

(0,86,-462,662-66„0), 6, <62,

Q =

1(б6,-662,862-46,, о, о), 6, > 62.

Случай III: т^є[2; 4).

Среди оптимальных решений есть Y* = С (единственное,

еслиур* 2). Для Y* = С имеем

х, *0,х2*0,>>**0,><2*0.

Условие оптимальности X*, следующее из теоремы равновесия, таково:

' 1 1 _.

6*3+ g*4~°l>

1 1 .

3*3 + 2*4 °2>

1*1 = *2 = 0Решал систему, находим:^* = (0,0, 126, 362, 462 86,).

Случай IV: ^^4.

Среди оптимальных решений есть решение Y* = D (единственное,

если ^Д* 4). Для Y * = D имеем о 1

•с, *0,х2*0,хг*0,у] *0. Из теоремы равновесия получаем условие оптимальности для X*:

8*4-*|. [*| = *2 = *з = 0Откуда Аг*= (0,0,0, 86,).

Случай II оказался самым сложным, так как в оптимальной точке Y* = В одновременно пересекаются три прямые, ограничивающие допустимое множество задачи (9.21). К счастью, пересечение трех прямых в одной точке без особых на то причин встречается крайне редко.

В нашем примере возможным объяснением тройного пересечения могло бы быть то, что технология 2 является в действительности смесью технологий 1 и 3. Это проявляется в том, что производство двух частей продукции по технологии 2 осуществляется путем производства одной части продукции по технологии 1, а другой — по технологии 3. Ясно, что включение смешанных технологий в список технологий задачи линейного программирования (9.16) только усложняет решение примера, однако не позволяет получить новых (после пересчета на «чистые» технологии) решений. Отметим также без доказательства, что технология j, для которой линия ху = 0 касается допустимого множества двойственной задачи (в случае двух ресурсов) по отрезку, не может быть представлена как смесь других технологий. Поэтому технологии 1, 3 и 4 задачи (9.20) являются «чистыми».

Вернемся к общей задаче (9.16) и изучим зависимость max / от Ь,Ьг, ...,ftm

Теорема 1. Пусть {у,, у2,.., уа] — множество всех угловых точек допустимого множества задачи (9.19). Тогда максимальное значение целевой функции f задачи (9.16) совпадает с минимальным значением целевой функции ф задачи (9.19) на множестве | у,, у2,...,

тах/=тіп{ф(у1),ф(у2) ф(у,)}.

Доказательство. Как было отмечено выше, задача (9.16) разрешима и, по основной теореме двойственности, max/ = min ф. С другой стороны, по теореме 2' из § 7.2 имеем

min ф = min | ф (у,), ф (у^,ф (уу) }.

Теорема доказана.

С целью упрощения обозначений будем изучать зависимость max/только от одного из свободных членов, скажем, от ft,. Для

угловой точки уа. (yk y2k ■••> y„^j имеем

Таким образом, ф(уа-) = аА. + рА. ft, — линейная функция от ft|, где a,^2,f + Vf + ... + ^>,

Определим функции/;.. ( ft, ) (к = 1,2,s )uF(b{ ) тождествами: Л(*і>яф(у*> = а* + Мі» (9.23) F( ft, ) = min 1/, ( ft, ),/2 ( ft, ), ..,/, (ft,)}. (9.24)

На координатной плоскости ft,Q построим графики функций Q=/k(bl) (к = 1, 2,s) и Q = F ( ft, ). Достаточно ясно, что график Q = F ( ft, ) является ломаной, состоящей из отрезков (лучей), расположенных на прямых Q -fk ( ft|). Докажем, что наклоны этих отрезков уменьшаются при увеличении ft,.

Отсюда, в частности, следует, что прямые Й=/А. (ft,) и б=//(*і) не совпадают. В точках 6, > ft*, расположенных достаточно близко к ft*, точка У/ является точкой минимума функции ф. Поэтому

ф( Уа.)>ф( У,), при ft, >ft*. (9.25) Так как fk ( ft* ) =// ( ft*), то

fk{ ft, )-//( b, )=/*( ft, )-/A. (&')-[//(*«) -/;(** ) ] =

= pA.(ft,-ft*)-P/(6,-ft*) = (6A.-p/)(ft,-ft*). (9 26)

207

Поскольку ф (У*) =/*(*,) и ф (У/) =//(*]), то из формул (9.25), (9.26) получим

(Pt-B/H*,-**)^, прибей*.

Следовательно, (3Л. > р,. Более того, Рд.*Р/, так как прямые Q ~А (° ) и Q ~fi (*i)не совпадают. Поэтому рА. > р,. Итак, мы доказали, что с увеличением Ъ наклон графика

G = max/( =

уменьшается.

Этот факт подтверждает широко применяемый в экономической теории тезис:

Отдача от дополнительных единиц ресурса уменьшается при увеличении количества доступных единиц данного ресурса.

Заметим, что в процессе увеличения Ь наклон графика Q = F(b{)

уменьшается, но не может стать отрицательным. Действительно, наклон (т. е. угловой коэффициент pfc) — это первая координата

соответствующего неотрицательного вектора Yk.

Пусть [0; *'|] — отрезок, на котором наклон графика Q = F( bx) положителен. Тогда всякое увеличение *| (в пределах [0; Ь'х]) приводит к увеличению выпуска Q = F ( Ь ), что свидетельствует о том, что ресурс полностью потребляется. Следовательно, F(b,) — это не только величина выпуска Q при ограничении Ь, но и (на отрезке [0; А'(])

величина выпуска q в зависимости от фактического расхода ресурса.

В качестве последнего примера найдем зависимость max / от Ь2 в задаче (9.20), считая, что 6, = 10 = const. Угловым точкам А, В, С к D допустимого множества задачи (9.21) соответствуют следующие функции:

/,(*2) = ф(Л) = 6*2; /2(Ь2) = Ф(5) = 20 + 2*2; /3(Ь2) = Ф(С) = 40 + 62; /4(&2> = фф) = 80.

как линия, огибающая снизу прямые q =fk (b2 ) (к , z, і, у