3.1ГрафическийметодрешениязадачЛп

Вначалерассмотримнаиболеепростойметодрешения,применимыйдляслучая,когдаколичествопеременныхнепревосходитдвух.Рассмотримследующийпример.

Компанияпроизводитпогрузчикиитележки.Отодногопогрузчикакомпанияполучаетдоходвразмере$80иотоднойтележкивразмере$40.Имеетсятриобрабатывающихцен-тра,накоторыхвыполняютсяоперацииметаллообработки,сваркиисборки,необходимыедляпроизводствалюбогоизпродуктов.Дляинтервалапланирования,равногомесяцу,за-данапредельнаяпроизводственнаямощностькаждогообрабатывающегоцентравчасах,атакжеколичествочасов,необходимоенаэтомцентредляпроизводстваодногопогрузчика

иоднойтележки.Этаинформациязаданавтаблице.

Центр\Изделие	Погрузчик Тележка (часынаед.) (часынаед.)	Общаямощность (часы)
Мет.обработка Сварка Сборка	6 4 2 3 9 3	2400 1500 2700

Требуетсясоставитьдопустимыйпланработнамесяцсмаксимальнымдоходом.Матема-тическаямодельзадачиможетбытьзаписанаследующимобразом.

80x₁₊40x_2→max,

^_6x1

^

+4x₂

^≤2400

^{2x1+3x2≤1500}

^{ 1 2}

^

^9x+3x≤2700

^{x1≥0,x2≥0}

^гдеx₁^иx₂^{–количествапроизводимыхпогрузчиковитележексоответственно.}

Представимограниченияввидеследующегографика,гдепоосям(0x₁)и(0x₂)отклады-ваетсяколичествопроизведенныхпогрузчиковитележексоответственно,алиниипред-ставляютограничениянапроизводственныемощности.Допустимаяобластьзадачипред-ставленаввидемногоугольника.

Представимцелевуюфункцию80x₁₊40x₂₌zспеременнымзначениемzпрерывистойлинией.Любаяточка(x₁,x₂)налинии80x₁₊40x₂₌zсоответствуетдоходувразмереz.Перемещаяеепараллельносебесамой,получаемразныезначениядохода.

Приx₁₌0значениеz=40x₂.Следовательно,значениеzувеличиваетсяприувеличенииx₂,т.е.приперемещениицелевойфункциивверх.Приэтомлиния80x₁₊40x₂₌zнедолжнапокинутьдопустимуюобласть.

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

_{соответствующихограничениямнаметаллообработкуисборку,x∗=200,x∗=300.}

1 2

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

3.2 ВозможныевариантырешениязадачЛп

1)ЗЛПимеетединственноерешение

_x2

✻

900

_❇

_❇

_❇

_❇

_❇

600 ❇

_{❏ ❇}

_500❏❇

_❏

_❇

_◗

_◗❇

_❏◗

^❏◗❇_◗

❇

❏◗

^•_❏❇ ^◗

_{❇ ◗}

_❆

❆

_❆✟✟✯

_{❏ ◗}

_◗

_❇❏ ^◗

_{❇❏ ◗}

_{❇❏ ◗}

_✲

_◗

_❆

_{❆ ❇ ❏} ^◗

300400 750 ^x1

2)НесуществуетдопустимогорешенияЗЛП

^{3)ЗЛПимеет∞многооптимальныхрешений,которыеназываютсяальтернативными}

4)ЦелеваяфункцияЗЛПнеограничена(вдопустимойобласти).

3.3 ЭквивалентныепостановкизадачЛп

_{Общаяпостановка:}

n

j=1

_{ n}

c_jxj→max(min),

_j=1^a_ij^x_j^≤b_i^,i∈I₁

n

n

^

^

 _j=1^aij^xj^=bi^,i∈I2

^ _j=1^{aijxj≥bi,i∈I3}

^{j 1}

^x≥0,j∈N,

^

^

^{xj∈R,j∈N2,}

^{xj≤0,j∈N3,}

гдеc_j,a_ij,b_i–заданныечисловыепараметры,множестваI₁,I_2иI_{3попарно}непересе-каются,I_1∪I_2∪I₃₌{1,...,m},R–множестводействительныхчисел,множестваN₁,N_2иN_{3попарно}непересекаются,иN_1∪N_2∪N₃₌{1,...,n}.Cуществуетнесколько

эквивалентныхпостановокзадачЛП:

–Задачимаксимизациииминимизации.Дляпереходаотоднойзадачикдругойкоэффи-циентыцелевойфункцииможноумножитьна-1.

^{–Задачисограничениямитипа”=”,”≤”и”≥”.Дляпереходаотограничения”≤”кограни-}

^{чению”≥”инаоборотдостаточнодомножатьсоответствующееограничениена-1.Огра-}

^{ничениетипа”=”можетбытьпредставленоввидедвухограничений”≤”и”≥”стойже}

^{левойиправойчастью.Дляпереходаотограниченийтипа”=”кограничениямтипа≤}

можноприменитьметодГаусса.Например,рассмотримзадачу

−x₁₋x₂₊x_5→min

^_x1+x2=1

^

^^x2^−2x3⁼⁻³

⁻

x₃ x₄₊x₅₌1

^

^

^xj≥0

ПрипомощиметодаГауссавыделяемединичнуюподматрицувматрицеограничений.

1	1	0	0	0	1		1	0	2	0	0	4		1	0	0	2	-2	2
0	1	-2	0	0	-3	⇒	0	1	-2	0	0	-3	⇒	0	1	0	-2	2	-1
0	0	1	-1	1	1		0	0	1	-1	1	1		0	0	1	-1	1	1

Эквивалентнаязадача

^_^x₁^=2−(2x₄^−2x₅^)≥0

^

^x2^{=−1−(−2x}4^+2x5^)≥0

^{x3=1−(−x4+x5)≥0}

^−2+2x4^−2x5^−1+2x4^−2x5^+x5^=−3+4x4^−3x5^→min

^_2x4

^

^−2x₅^≤2

^{−2x4+2x5≤−1}

_^{−x4+x5≤1}

^x4,x5≥0

Дляпереходаотограниченийтипа≤кограничениямтипа=достаточноввестидополни-тельныенеотрицательныепеременные,пооднойдлякаждогоограничения≤.Этипере-

менныевойдутвцелевуюфункциюснулевымикоэффициентами.

^{Переменнаяx}_j^{∈Rможетбытьпредставленаввидедвухновыхнеотрицательныхпере-}

_{менных:xj=x}+_−x−_,x+_≥0,x−_≥0.

j j j j

ДлякаждойзадачиЛПможносформулироватьдвойственнуюей задачу.Рассмотримзадачумаксимизациисограничениями”≤”.Представимэтузадачувматричнойформе:

cx→max,Ax≤b,

гдеc=(c₁,...,c_n)–вектор-строка,x=(x₁,...,x_n)^T–вектор-столбец,A=||a_ij||–матрицаразмерностиm×n,b=(b₁,...,b_m)^T–вектор-столбец.Отметим,чтоограниченияx≥0отсутствуют.ОнимогутбытьвойтивограниченияAx≤bпутемвведенияэквивалентныхограничений−x≤0.Введемврассмотрениедвойственнуюейзадачу:

yb→min,

yA=c,y≥0,

гдеy=(y₁,...,y_m)–вектор-строкадвойственныхпеременныхилипотенциалов.ПустьA_iобозначаетстрокуiматрицыA,аA^j–столбецjэтойжематрицы.Соответствиемеждукомпонентамипрямойидвойственнойзадачпредставленовследую-щейтаблице.

Прямаязадача	Двойственнаязадача
max{cx} Aix≤bi,i∈I1 Aix=bi,i∈I2 xj≥0,j∈N1 xj∈R,j∈N2 xj≤0,j∈N3	min{yb} yi≥0,i∈I1 yi∈R,i∈I2 yAj≥cj,j∈N1 yAj=cj,j∈N2 yAj≤cj,j∈N3

Теорема1(Теоремадвойственности)Справедливоодноизследующихутверждений:

а)обезадачи,прямаяидвойственнаяей,имеютдопустимыерешенияи

max{cx}=min{yb},

б)еслиоднаиззадач,прямаяидвойственнаяей,неимеетдопустимогорешенияадругаяимеет,тоцелеваяфункциядругойзадачинеограничена.

в)обезадачинеимеютдопустимыхрешений.

Теорема2(Одополняющейнежесткости)Пустьxиy–допустимыерешенияпрямойидвойственнойзадачсоответственно.Тогдаследующиеусловияа),б)ив)эквивалент-ны:

а)xиyоптимальныерешенияпрямойидвойственнойзадач,б)cx=yb,

^{в)(условиедополняющейнежесткости)y}i^(Ai^x−bi^{)=0i=1,...,m,и(yAj−c}j^)xj^=0,

j=1,...,n.

Изэтойтеоремы,например,следует,чтоеслирешенияпрямойидвойственнойзадачдопу-стимыивыполняетсяусловиев)дополняющейнежесткости,тоэтирешенияоптимальны.Оптимальноерешениепрямойзадачиможетбытьполученоизоптимальногорешениядвойственнойзадачи.Например,рассмотримзадачу

^4x₁^−3x₂^−6x₃^−x₄^→max,

^

^{−2x1−x2+5x3+2x4≥2}

^−3x1^+x2^−x3^−x4^≥1

^x_i^{≥0,i=1,2,3,4}

^{Построимдвойственнуюейзадачу}

^2y₁^+y₂^→min,

^{−2y1−3y2≥4}

^{−y1+y2≥−3}

^

^

^

^{5y1−y2≥−6}

^

^{2y1−y2≥−1}

^yj^≥0,j=1,2

^{Решимдвойственнуюзадачуграфически:y∗=(−9/4,−21/4),z∗=−39/4.Оптимальное}

решениеопределяетсяпересечениемлиний,соответствующихограничению2и3двой-

1

ственнойзадачи.Этиограничениявыполняютсякакстрогиеравенства,аостальные-какнестрогие.Тогдапоусловиюдополняющейнежесткостидолжновыполнятьсяx^∗=0,

4_=0,x2_иx3_{могутбытьнайденыизравенств−x}2_+5x3_=2иx2_−x3_{=1(рассмат-}

^{x∗ ∗ ∗}

^{∗ ∗ ∗ ∗}

риваемподматрицуматрицыпрямойзадачи,состоящуюизстолбцов2и3).Получаем

_x^∗_{=(0,7/4,3/4,0).}