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

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

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

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

2. 4. Опорні плани ЗЛП

Розглянемо канонічну форму запису ЗЛП

(20)

(21)

(22)

Щоб мало сенс говорити про оптимальний план задачі (20)-(22), необхідно й достатньо, щоб система обмежень (21) була сумісна в області невід’ємних значень змінних.

Тому що в системі лінійних рівнянь (21) m рівнянь і n змінних, то ранг r системи повинен бути менше числа змінних (r<n). У такому випадку серед змінних r змінних – базисні, і (n-r) змінних – вільні

Визначення. Опорним планом ЗЛП називається такий план, у якому базисні змінні невід’ємні, а вільні дорівнюють нулю.

З визначення виходить, що кількість невід’ємних компонентів в опорних планах не повинне перевищувати ранг системи обмежень.

2.5. Геометрична інтерпретація опорних планів

Відомо, що плани ЗЛП із геометричної точки зору можна трактувати, як геометричне місце точок опуклого багатогранного тіла, що є ОДР задачі. Тоді опорні плани ЗЛП є вершинами цього багатогранного тіла.

Теорема. Кожному опорному плану ЗЛП відповідає вершина багатогранника Ω і навпаки, кожній вершині багатогранника Ω відповідає опорний план. Таким чином, оптимальні плани варто шукати серед опорних.