5.3.Видызаписизадачлинейногопрограммирования

Чтобывмножествеограниченийбылоединообразиеприрешениираз-личныхзадачлинейногопрограммирования,ихцелесообразнопривестикодномуиздвухвидов–стандартному,когдавсеограничениязаписанывви-денеравенствсоднимзнаком,скажем,сознаком«≤»;каноническому,когдавсеограниченияестьравенства.Приведениекканоническомувидуисполь-зуется,вчастности,прирешенииЗЛПсимплекс-методом.

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

1.Стандартныйкканоническому-путемвведениядополнительныхпере-менных:например,есливЗЛПснеравенствамитипаa_j1x₁₊a_j2x₂+a_j3x_3≤b_{jдобавить}переменнуюx_4скоэффициентомa_j4=1(или«–1»вслучае«≥»),томожнозаписатьa_j1x₁₊a_j2x₂+a_j3x₃₊a_j4x₄₌b_j.

2.Каноническийкстандартному–путемвведениявместоодногоравен-

ствадвухнеравенств:вместоa_j1x₁₊a_j2x₂+a_j3x₃₊a_j4x₄₌b_jможнозаписать

a_j1x₁₊a_j2x₂+a_j3x₃₊a_j4x_4b_j,

a_j1x₁₊a_j2x₂+a_j3x₃₊a_j4x_4b_j.

Кромеупомянутыхвидовзаписииихвзаимныхпреобразованийможнопреобразоватьзадачупоискаминимумавзадачупоискамаксимума(илинаоборот)путемизменениязнаковприкоэффициентес_i,ввыражениицеле-войфункции.

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

Особенностизадачлинейногопрограммирования,накоторыхоснованыметодырешенияЗЛП,можнопроиллюстрироватьспомощьюграфическойинтерпретации.Этоможносделать,когдавекторXсодержитдвеперемен-ные.РассмотримграфическуюинтерпретациюЗЛПнаследующемпримере(сравнитеспримером1).

Пример2.Данаследующаязадачалинейногопрограммирования:

3x₁₊2x_2→max,

2x₂₊4x_2≤16,

x_1≤6,

x_2≤8,

x₁,x_2≥0.

Шаг1.Дляграфическойинтерпретациизадачипостроимсистемукоор-динатx₁Ox₂₍рис.7).Любаяточкавэтойсистемезадаетсясвоимикоордина-таминаосяхOx_1иОх_2–(x₁,x₂),т.е.также,какивекторX.Такимобразом,решениемзадачибудетнекотораяточкавпространствеx₁Ox₂.

Еслиучитыватьтребованиенеотрицательностипеременныхинеучиты-

ватьдругиеограниченияЗЛП,торешениемзадачиможетбытьлюбаяточкаизтойчастиплоскости,котораярасположенавышеилевееосейOx_1иОх₂.Определимвэтойчастиплоскостиобластьдопустимыхрешенийнашейза-дачи(говоряттакжеобластьдопустимыхзначенийпеременныхвектораX).Дляэтогонарисуемпрямые,заданныеуравнениями2x₁₊4х₂₌16,x₁₌6,x₂₌8.

Относительноограниченияx_1≤6допустимымибудуттерешения(точки),которыележатлевеепрямойx₁₌6илинаней.Относительноограниченияx_2≤8–терешения,которыележатнижепрямойх₂₌8илинаней.Относи-тельноограничения.2x₁₊4х_2≤16допустимымибудуттерешения,которыележатлевееилинапрямой2x₁₊4х₂₌16.Областьдопустимыхрешенийзада-

^{чиестьтаобластьвx}₁^Ox₂^{,точкикоторойудовлетворяютвсемэтимограни-}

x₂

x₂₌8

x₁₌6

A

₁ ^{C B}

^x₁

^O 1 ^D

2x₁₊4x₂₌16

чениям,включаятребованиянеотрицательности.Такойобластьюнарис.7являетсяобластьOABD,котораяестьпересечениеперечисленныхобластей,ирешениемзаданнойЗЛПявляетсяточкаэтойобласти.Решимэтузадачуграфическимметодом,т.е.порисунку.

Рис.7.Графическаяинтерпретациязадачлинейногопрограммирования

Дляэтогопослеопределенияобластидопустимыхрешений(первыйшагалгоритмарешенияЗЛПграфическимметодом)задачинеобходимовыпол-нитьследующиешаги.

Шаг2.ПостроитьвекторОСскоординатами(c₁,c₂).Здесьc₁,c_2–коэф-фициентыприпеременныхввыражениицелевойфункции.ВнашемпримереэтовекторОС=(3,2),которыйизображеннарис.7.

Шаг3.Провестилинию,перпендикулярнуювекторуОС.Этоестьлинияуровняцелевойфункции(нарис.7онапоказанаштрих-пунктиром).

Шаг4.ДляпоискаоптимальногорешенияперемещатьлиниюуровняпонаправлениювектораОСприпоискемаксимумаилипротивнаправлениявектораОС–припоискеминимума.Линиюперемещаемдотехпор,покаонанедостигнетпоследнейточкиобластидопустимыхрешений.Этаточкаибудетоптимальнымрешениемзадачи(нарис.7оптимальноерешение–точкаВ).

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

Шаг5.Определитькоординатыоптимальногорешения.Этоделаетсяилипорисунку,илирешаясистемууравненийтехпрямых,напересечениикото-рыхлежитточкаоптимальногорешения.Внашемпримереэтобылабыси-

_{стемауравнений}

2х₁₊4х₂₌16,

x₁₌6.

ДлязаданнойзадачирешениембудетточкаВскоординатами(6;1).Ина-чеговоря,решениемзадачиявляютсязначенияпеременныхx₁₌6,x₂₌1.Подставляяэтизначенияввыражениедляцелевойфункции,можемопреде-литьоптимальноезначениекритерия,внашемслучаеI–f(X^opt)=27.Еслибывпримере2необходимобылонайтиминимумцелевойфункции,торешени-ембылаточка(0;0).Анализируярезультатырешений,предлагаетсясравнитьзадачусзадачейвпримере1.

Наосновеанализапримера2можносформулироватьследующиеособен-

ностиЗЛП:

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

–решениеЗЛП,еслионоединственно,лежитводнойизвершинмного-гранника(точкаВвпримере2).Еслирешениймножество,тоонилежатнагранимногогранника(этомоглобыполучиться,еслибывпримере2векторОСоказалсяперпендикулярнымпрямой2х₁₊4х₂₌16,тогдабылобыбеско-нечноемножестворешений–точекнаотрезкеАВ);

–вЗЛПможетинесуществоватьрешений,еслиобластьдопустимыхрешенийнезамкнута.Так,есливпримере2убратьограничения2х₁₊4х_2≤16их_2≤8,иубратьсоответствующиепрямыенарис.7,тодвигатьлиниюуров-няможнобылобыдобесконечности,т.е.решениебыотсутствовало.

НаэтихособенностяхоснованнаиболееизвестныйметодрешенияЗЛП–симплекс-метод.Сущностьегосводитсякследующему:поопределеннымпра-виламприрешениизадачиищутсятакназываемыебазисныерешения(сим-плексы).Этибазисныерешениясовпадаютсвершинамимногогранникаобла-стидопустимыхрешений(нарис.7этоточкиО,А,В,D).Впроцессепоискабазисныхрешенийоцениваетсяихоптимальностьпоправилам,позволяющимопределить,можнолиулучшитьзначениецелевойфункции,есливыбратька-кое-тодругоебазисноерешение.Еслиможно–выбираетсяновоебазисноере-шение(новаявершинамногогранника)ипроверкаповторяется.Такделаетсядотехпор,поканайденноебазисноерешениенеокажетсяоптимальным.