Симплекс-метод: случай, когда оптимальное решение — не единственное

В примере, рассмотренном в статье «Симплекс-метод
решения задач линейного программирования: типичный пример и алгоритм», система
ограничений была совместной и имелся конечный оптимум, причём единственный. В этой статье
проиллюстрирован случай, когда одно из условий нарушается: оптимальное решение — не единственое.

Пример. Найти максимум функции
при ограничениях

Решение.

Введением добавочных неотрицательных переменных сведём систему
неравенств к системе уравнений:

Приняв в качестве основных добавочные переменные, получим базисное решение
(0; 0; 9; 2; 8), которое является
допустимым, поэтому его можно принять за исходное на I шаге решения.

Шаг I. Основные переменные: ,
, ;
неосновные переменные ,
. Выразим
основные переменные и линейную форму через неосновные:

Переводим
в основные переменные. Находим .
При имеем
и
переходит в
неосновные переменные.

Шаг II. Основные переменные , , ; неосновные
переменные ,
.
Имеем

В выражении линейной формы F
отсутствует одна из неосновных переменных (),
а критерий оптимальности выполнен (можно считать, что
входит в выражение F с нулевым коэффициентом). Поэтому
эта переменная не является ни выгодной, ни невыгодной.

Попробуем всё же перевести
в основные переменные. Полагая ,
заключаем, что
переходит в неосновные переменные.

Шаг III. Основные переменные , , ,
неосновные переменные ,
. Имеем

Таким образом, и на этом шаге получается то же самое выражение линейной
формы, а критерий оптимальности снова выполнен.

На II шаге оптимальное решение имело компоненты (2; 0; 13; 0; 6),
на на III шаге — (5; 3; 10; 0; 0). Однако
оба оптимальных решения дают одно и то же максимальное значение: .

Отсюда следует, что единственность оптимального решения может
нарушаться. Это происходит в том случае, когда на каком-то шаге решения критерий оптимальности
выполняется, а в выражении линейной формы отсутствует одна из неосновных переменных.

Поделиться с друзьями

Ссылка на основную публикацию