Симплекс-метод решения канонической задачи линейного программирования. Альтернативный оптимум. Признак альтернативного оптимума.

Опр. Основную ЗЛП будем называть канонической, если система уравнений этой задачи является канони-ческой, а целевая функция выражена только через свободные неизвестные.

Чтобы поставленную задачу привести к каноническо-му виду, надо преобразовать целевую функцию так, чтобы она зависела только от свободных переменных.

Где, - оценки соответствующих свободных переменных.
Решение канонической задачи симплексным методом облегчается с использованием симплексных таблиц. Запишем в виде симплекс-таблицы
Б … ….
…. …
1 0 … 0 …
0 1 … 0 …
… … … … … … … … …
0 0 … 1 …
Z
Последняя строка – оценочная, находится по формуле:
Оценка под столбцом равна сумме произведений элементов этого столбца на соответствующие элементы столбца минус число, стоящее в шапке.
Альтернативный оптимум. Известно, что можно иметь несколько опорных решений, в которых целевая функция достигает оптимального значения (альт.оптимум). Оптимальным будет при этом любое решение , являющейся выпуклой комбинацией оптимальных опорных решений. где
При решении задачи с альтернативным оптимумом необходимо выяснить вопросы: 1. Установить признаки существования в задаче альт.оптимума. 2. Найти все оптимальные опорные решения. Признаком существования альтернативного оптимума при расчёте по симплекс-таблице является наличие хотя бы одной нулевой оценки свободной переменной при неотрица-тельности всех остальных оценок. Введением в базис всех соответсвующих свободных переменных можно найти оптимальные опорные решения.