 |
Симплексные преобразования
|
|
|
|
Для того, чтобы перейти к новому базису необходимо выразить новую базисную переменную через свободные переменные.
Рассмотрим систему ограничений ЗЛП:
(i= 
)
Рис. 12. Алгоритм выбора разрешающего элемента для задач линейного программирования на максимум (минимум)
Преобразуем ее следующим образом:
(i= )
Выразим из системы базисную переменную 
:
.
Распишем подробнее:
Отсюда:
Тогда
Подставим данное равенство в другие ограничения системы:
Для целевой функции формула представима в виде:
Вычисление по данным формулам получило название симплексных преобразований. Для того чтобы перейти с помощью симплексных преобразований к новому опорному плану можно действовать двумя способами.
Способ 1.
1. Найти разрешающий элемент.
2. С помощью представленных формул преобразовать все уравнения системы ограничений.
3. Посчитать значение целевой функции.
Способ 2.
Алгоритм действий представлен на Рис. 13.
Определение: Шаг симплексного метода, позволяющего перейти от одного опорного плана к другому, называется итерацией.
Пример: Решить симплексным методом ЗЛП:
при 
Рис. 13. Алгоритм решения задач линейного программирования на максимум (минимум), используя симплексные преобразования
Решение.
Система ограничений имеет предпочтительный вид. Можно составлять симплексную таблицу:
| БП | СБ | А | 
| 
| 
| 
| 
| № итерации |
| -5 | -1 | |||||||
|
| -5 | 1 \ 
| -1 | |||||
|
| 5 \ 
| |||||||
|
| -1 | -5 | ||||||
| -4 | -1 | |||||||
|
| -1 | |||||||
|
| -5 | 8 \ 
| ||||||
|
| -1 | -1 | ||||||
| -5 | ||||||||
|
| 
| 
| ||||||
|
| 
| 
| ||||||
|
| -1 | 
|
| |||||
| 
|
В индексной строке последней симплексной таблицы все оценки свободных переменных положительны. Следовательно, план оптимален.
|
|
|
Ответ: Z=72 в (7, 0, 0, 42, 2).
2.9. Альтернативный оптимум (признак бесконечности множества опорных планов)
Из геометрической иллюстрации ЗЛП следует, что она имеет бесконечно много решений, если линия уравнения проходит через сторону прямоугольника (Рис. 14).
Для решения задачи симплексным методом ответ на вопрос: имеет ли задача бесконечно много решений, дает теорема:
Теорема: Если в индексной строке последней симплексной таблицы, содержащей оптимальный план, имеется хотя бы одна нулевая оценка, соответствующая свободной переменной, то ЗЛП имеет бесконечно много решений.
Следствие: Если в индексной строке симплексной таблицы, содержащей оптимальный план, все оценки соответствующие свободным переменным положительны, то найденное решение - единственное.
|
|
|
