Основні властивості розв’язків задачі лінійного програмування

Властивості розв’язків задачі лінійного програмування формулюються у вигляді чотирьох теорем.

Властивість 1. (Теорема 1.) Множина всіх планів задачі лінійного програмування опукла.

Властивість 2. (Теорема 2.) Якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин многогранника розв’язків. Якщо цільова функція набуває екстремального значення більш як в одній вершині цього многогранника, то вона досягає його і в будь-який точці, що є лінійною комбінацією таких вершин.

Властивість 3. (Теорема 3.) Якщо відомо, що система векторів (k n) у розкладі , , лінійно незалежна і така, що

,

де всі то точка є кутовою точкою багатогранника розв’язків.

Властивість 4. (Теорема 4.) Якщо – кутова точка багатогранника розв’язків, то вектори в розкладі , , що відповідають додатнім є лінійно незалежними.

З наведених властивостей маємо:

якщо функціонал задачі лінійного програмування обмежений на багатограннику розв’язків, то:

1) існує така кутова точка багатогранника розв’язків, в якій лінійний функціонал досягає свого оптимального значення;

2) кожний опорний план відповідає кутовій точці багатогранника розв’язків. Тому, для розв’язання задачі лінійного програмування необхідно досліджувати лише кутові точки багатогранника (опорні плани), не включаючи до розгляду внутрішні точки множини допустимих планів.

Дата добавления: 2017-02-01