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

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

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

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

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

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

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

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

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