Постановка задачи ЛП

Любое множество значений Х, удовлетворяющих условиям (2) и (3) называется допустимым множеством решений - допустимый план или опорный план или базисное решение.

Решение Х из допустимого множества решений называется оптимальным, если оно удовлетворяет условию (1), т.е. приносит целевой функции оптимум

- оптимальный план.

Если дана задача на отыскание min то переменой знака целевой функции на противоположный ее сводят к задаче на max.

Опорный план может указывать на:

- неразрешимость задачи

- возможность улучшить план

Оптимальный план может быть:

- единственным

- бесконечное множество

Если опорный план можно улучшить (сделать более близким к оптимальному), то переходят к поиску другого опорного плана.

Т.о. решение задачи ЛП – это переход от одного опорного плана к другому более оптимальному.

Симплекс - метод – это ряд шагов, заключающихся в том, что от одного опорного плана (базиса) переходи к другому опорному плану (базису) так, чтобы значение целевой функции увеличилось или, по крайней мере, не уменьшилось.

	n – количество неизвестных (X- ов) - столбцов матрицы m – количество уравнений - строк матрицы

В матричной форме задача ЛП записывается так:

Дата добавления: 2015-07-14