Проверка опорного решения на оптимальность
Теорема. Опорное решение является оптимальным, если коэффициенты при свободных переменных в целевой функции отрицательны или равны нулю.
Если полученное опорное решение не оптимально, то нужно перейти к другому опорному решению.
Пример (продолжение).
Проверим, является ли полученное опорное решение оптимальным.
Т.к. коэффициенты при свободных переменных и положительны, то это решение не является оптимальным.
Переход к следующему опорному решению
При переходе от одного опорного решения к другому между множествами базисных и свободных переменных происходит взаимообмен переменными: одна из базисных переменных переходит в разряд свободных, а одна из свободных переменных переходит в разряд базисных.
Точка |
Свободные переменные (нулевые) |
Базисные переменные (ненулевые) |
A |
x 1 x2 |
x3 x4 x5 |
B |
x1 x5 |
x3 x4 x2 |
C |
x4 x5 |
x3 x1 x2 |
Например, для рассматриваемой задачи:
Для перехода к лучшему опорному решению следует увеличивать от исходного нулевого значения ту свободную переменную, которая в целевой функции имеет положительный коэффициент.
Однако увеличивать эту переменную следует так, чтобы значения базисных переменных оставались неотрицательными (так, чтобы не выйти за пределы допустимых решений).
Если в целевой функции несколько переменных имеют положительный коэффициент, то для обмена следует выбирать ту свободную переменную, которой соответствует . Это в большинстве случаев позволяет быстрее получить оптимальное решение.
Пример (продолжение).
Переходим к другому опорному решению.
И меющееся решение можно улучшить, если увеличить переменную , но только до 4, иначе станет меньше 0.
Выбранную свободную переменную обменивают с такой базисной, которая при увеличении этой свободной переменной первой обращается в ноль.
Т о есть меняем местами переменные и (переменную введём в базис, а сделаем свободной).
, .
,
.
,
.
,
.
Получим следующую систему уравнений:
.
Полагаем , тогда , , , (на графике - точка ).
Проверяем опорное решение на оптимальность.
Т.к. в целевой функции имеется положительный коэффициент при свободной переменной , то решение не является оптимальным.
Переходим к следующему опорному решению.
Переменную переведём в разряд базисных, а переменную - в разряд свободных.
,
.
,
.
,
.
,
.
Базисные переменные , , выражаются через , следующим образом:
.
Полагаем , тогда , , , (на графике – точка ).
Это решение является оптимальным, т.к. увеличение свободных переменных не приведёт к уменьшению (коэффициенты при свободных переменных в целевой функции отрицательны).
Максимум исходной целевой функции равен: .
Ответ: при , .