Симплекс-метод: случай, когда оптимальное решение - не единственное
В примере, рассмотренном в статье "Симплекс-метод решения задач линейного программирования: типичный пример и алгоритм", система ограничений была совместной и имелся конечный оптимум, причём единственный. В этой статье проиллюстрирован случай, когда одно из условий нарушается: оптимальное решение - не единственое.
Пример. Найти максимум функции
при ограничениях
Решение.
Введением добавочных неотрицательных переменных сведём систему неравенств к системе уравнений:
Приняв в качестве основных добавочные переменные, получим базисное решение (0; 0; 9; 2; 8), которое является допустимым, поэтому его можно принять за исходное на I шаге решения.
Шаг I. Основные переменные: ,
,
;
неосновные переменные
,
. Выразим
основные переменные и линейную форму через неосновные:
Переводим
в основные переменные. Находим
.
При
имеем
и
переходит в
неосновные переменные.
Шаг II. Основные переменные ,
,
; неосновные
переменные
,
.
Имеем
В выражении линейной формы F
отсутствует одна из неосновных переменных (),
а критерий оптимальности выполнен (можно считать, что
входит в выражение F с нулевым коэффициентом). Поэтому
эта переменная не является ни выгодной, ни невыгодной.
Попробуем всё же перевести
в основные переменные. Полагая
,
заключаем, что
переходит в неосновные переменные.
Шаг III. Основные переменные ,
,
,
неосновные переменные
,
. Имеем
Таким образом, и на этом шаге получается то же самое выражение линейной формы, а критерий оптимальности снова выполнен.
На II шаге оптимальное решение имело компоненты (2; 0; 13; 0; 6),
на на III шаге - (5; 3; 10; 0; 0). Однако
оба оптимальных решения дают одно и то же максимальное значение: .
Отсюда следует, что единственность оптимального решения может нарушаться. Это происходит в том случае, когда на каком-то шаге решения критерий оптимальности выполняется, а в выражении линейной формы отсутствует одна из неосновных переменных.
Назад<<< | Листать | Вперёд>>> |
Поделиться с друзьями