"Чистая"
и прикладная математика

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

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

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

Решение.

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

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

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

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

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

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

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

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

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

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

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

Назад<<<ЛистатьВперёд>>>
Начало темы "Линейное программирование"

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