Все шпаргалки / Теория вероятностей и матстатистика / 

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

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