Тому отримуємо

F(y) ³ 0 Þ F(x^’ + y) ³ F(x^’ ) Þ x^’- оптимальний розв’язок.

Нехай x^r – опорний план, задовольняючий умові

F(x^r) £ F(x^j ), j = 1, k.

Тоді F(x^’) = F(l_j x^j) = F(l_j x^j) = l_jF(x^j) ³ l_jF (x^r) = F(x^r) l_j = F(x^r).

Отже F(x^’) ³ F(x^r). Це означає, що x^r – оптимальний розв’язок (план), і цим завершується доведення.

Отримані результати означають, що при пошуку розв’язку задачі лінійного програмування можна обмежитися розгляданням тільки опорних планів, тобто шукати розв’язок тільки серед опорних планів. Симплекс-метод – аналітичний метод розв’язування задачі лінійного програмування, що розглядається далі, являє собою саме таку процедуру.

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

симплекс-методом

Дата добавления: 2014-01-13