- •Симплекс-метод.
- •2.1. Основные операции и теоремы линейного программирования
- •Понятие о симплекс-методе
- •Алгоритм симплекс-метода
- •2.4. Вырожденность в задачах линейного программирования. Проблема зацикливания
- •2.4.1.Симплекс метод (метод последовательного улучшения плана)
- •2.4.2.Алгоритм симплекс метода
- •2.4.3.Построение оптимального плана.
- •2.4.4.Построение опорного плана.
- •2.4.5Правила выбора разрешающего элемента при поиске опорного плана.
- •2.4.6.Вырожденность в задачах линейного программирования
- •2.5. Анализ линейных моделей на чувствительность. Двойственный симплекс-метод.
- •2.6. Использование искусственной переменной в программировании симплекс-методом.
- •2.7. Модифицированный симплекс - метод
- •2.7.1. Теоретические сведения
- •2.7.2. Мультипликативное представление обратной матрицы
- •2.7.3.Алгоритм модифицированного симплекс-метода.
- •2.7.4.Выводы
- •2.8. Целочисленное линейное программирование (зцлп)
- •Методы решения зцлп
- •Метод ветвей и границ
2.4. Вырожденность в задачах линейного программирования. Проблема зацикливания
2.4.1.Симплекс метод (метод последовательного улучшения плана)
Метод предназначен для решения общей задачи линейного программирования.
Пусть имеем следующую задачу:
, (2.5)
с системой ограничений следующего вида:
. (2.6)
Разрешим эту систему относительно переменных x1, ...,xm:
. (2.7)
Векторы условий, соответствующие x1, ...,xm, образуют базис. Переменныеx1, ...,xmназовембазисными переменными. Остальные переменные задачи – небазисные.
Целевую функцию можно выразить через небазисные переменные:
. (2.8)
Если приравнять небазисные переменные нулю: xm+1= 0,xm+2= 0, ...,xn= 0,
то соответствующие базисные переменные примут значения:
Пусть коэффициенты a-aобразуют матрицаA.
Вектор такими компонентами представляет собой угловую точку многогранника решений (допустимую) при условии, что(опорный план).
Теперь необходимо перейти к другой угловой точке с меньшим значением целевой функции. Для этого следует выбрать некоторую небазисную переменную и некоторую базисную так, чтобы после того, как мы “поменяем их местами”, значение целевой функции уменьшилось. Такой направленный перебор в конце концов приведет нас к решению задачи.
Пример 2.6:
Пусть
Выберем в качестве базисных следующие переменные {x1,x2,x3} и разрешим систему относительно этих переменных. Система ограничений примет следующий вид:
Переменные {x4,x5}являются небазисными. Если взятьx4= 0 иx5= 0, то получим угловую точку (опорный план):, которому соответствует.
Значение целевой функции можно уменьшить за счет увеличения x5. При увеличенииx5величинаx1также увеличивается, аx2иx3– уменьшаются. Причем величинаx2раньше может стать отрицательной. Поэтому, вводя в базис переменнуюx5, одновременноx2исключаем из базиса. В результате после очевидных преобразований получим следующие выражения для новой системы базисных переменных и целевой функции:
Соответствующий опорный план: и.
Целевую функцию можно уменьшить за счет увеличения x4. Увеличениеx4приводит к уменьшению толькоx3. Поэтому вводим в базис переменнуюx4, аx3исключаем из базиса. В результате получим следующие выражения для новой системы базисных переменных и целевой функции:
Соответствующий опорный план: и значение целевой функции:. Так как все коэффициенты при небазисных переменных в целевой функции неотрицательны, то нельзя уменьшить целевую функцию за счет увеличенияx2илиx3, следовательно, полученный планявляется оптимальным.
Пример 2.7:
Пусть имеем задачу
Переменные {x3,x4}- базисные, а {x1,x2}- небазисные переменные. Опорный план,.
Теперь вводим в базис переменную x1, ax4исключаем из базиса. В результате получим следующие выражения для базисных переменных и целевой функции:
Опорный план: , значение целевой функции:.
Теперь можно заметить, что при увеличении x2значения переменныхx1иx3также возрастают, то есть прив допустимой области(задача не имеет решения).
Замечание
В процессе поиска допустимого плана может быть выявлена противоречивость системы ограничений.