Учебное пособие: Практикум по решению линейных задач математического программирования

Пример. Для данной задачи линейного программирования найти начальный опорный план (базисное решение).

max

Решение. Изменим знаки второго и третьего неравенств на противоположные, умножив каждое из них на –1. Система ограничений теперь будет такой:

В каждом ограничении слева добавим положительную переменную , соответственно запишем канонический вид задачи:

max

.

Переменные базисные. Приравниваем их к правым частям ограничений: Все остальные переменные – свободные, приравниваем их к нулю:

Запишем теперь начальный опорный план

(0; 0; 0; 0; 16; 4; 0).

2) Составление симплексных таблиц. Критерий оптимальности.

Симплексный метод удобно применять, используя построение симплексных таблиц. Первая симплексная таблица, соответствующая начальному плану, имеет вид:

Базис		В			…
					…
					…
					…
…	…	…	…	…	…	…
					…
					…

Здесь приняты следующие обозначения.

Столбец «Базис» – это базисные переменные.

Столбец «» – это коэффициенты при базисных переменных в целевой функции.

Столбец «В» – правые части ограничений;

– коэффициенты при переменных в ограничениях;

– коэффициенты при переменных в целевой функции.

Последняя строка в таблице () – это проверочная или оценочная строка.

– значение целевой функции, соответствующее построенному начальному плану. Его находят так: каждый элемент столбца умножают на соответствующий элемент столбца В и произведения складывают, т.е.

.

– называют оценками или симплексными разностями и находят так: элементы столбца умножают на соответствующие элементы столбца , складывают результаты и вычитают .

Например,

.

Оценки () базисных переменных всегда равны нулю.

Признак оптимальности опорного плана состоит в следующем:

Опорный план будет оптимальным тогда и только тогда, когда все оценки

для задачи на max и