- •Симплекс-метод.
- •2.1. Основные операции и теоремы линейного программирования
- •2.2. Понятие о симплекс-методе
- •2.3. Алгоритм симплекс-метода
- •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, a x4 исключаем из базиса. В результате получим следующие выражения для базисных переменных и целевой функции:
.
Опорный план:
,
значение целевой функции:
.
Теперь можно заметить, что при увеличении
x2 значения переменных x1
и x3 также возрастают, то есть
при
в
допустимой области
(задача
не имеет решения).
