Властивості рішень ЗЛП
Особливості розв’язування ЗЛП графічним методом
1.
( - область припустимих планів.
F*max=F(Р1)
F*min=F(Р4)
Мал. 6
2.
Мал. 7
F*max=F(Р3), а мінімальне значення цільової функції досягається в кожній точці ребра Р1Р5 багатокутника W.
Записуємо рівняння відрізка Р1Р5:
3.
Мал. 8
F*min=F(Р2)
Лінійна форма необмежена зверху, отже, F*max ® ¥.
4.
Мал. 9
Система обмежень даної ЗЛП несумісна, задача не має рішень.
Властивості рішень ЗЛП сформулюємо у вигляді теорем.
Теорема 1. Для існування оптимальних рішень ЗЛП необхідно й достатньо, щоб багатогранник розв’язків містив хоча б одну точку і щоб лінійна форма F на ньому була обмежена знизу при визначенні opt типу min і зверху при визначенні opt типу max.
Теорема 2. Якщо ЗЛП має оптимальний план, то він досягається у вершинах опуклого багатогранного тіла, що є ОДР (областю припустимих розв’язків або планів). Якщо ж оптимальний план досягається більш ніж в одній вершині, то він досягається в будь-якій точці опуклої лінійної комбінації відповідних вершин багатогранника.