Властивості рішень ЗЛП

Особливості розв’язування ЗЛП графічним методом

1.

(- область припустимих планів.

F^*_max=F(Р₁)

F^*_min=F(Р₄)

Мал. 6

2.

Мал. 7

F^*_max=F(Р₃), а мінімальне значення цільової функції досягається в кожній точці ребра Р₁Р₅ багатокутника W.

Записуємо рівняння відрізка Р₁Р_5:

3.

Мал. 8

F^*_min=F(Р₂)

Лінійна форма необмежена зверху, отже, F^*_max ® ¥.

4.

Мал. 9

Система обмежень даної ЗЛП несумісна, задача не має рішень.

Властивості рішень ЗЛП сформулюємо у вигляді теорем.

Теорема 1. Для існування оптимальних рішень ЗЛП необхідно й достатньо, щоб багатогранник розв’язків містив хоча б одну точку і щоб лінійна форма F на ньому була обмежена знизу при визначенні opt типу min і зверху при визначенні opt типу max.

Теорема 2. Якщо ЗЛП має оптимальний план, то він досягається у вершинах опуклого багатогранного тіла, що є ОДР (областю припустимих розв’язків або планів). Якщо ж оптимальний план досягається більш ніж в одній вершині, то він досягається в будь-якій точці опуклої лінійної комбінації відповідних вершин багатогранника.

Дата добавления: 2014-12-07