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