Симплекс метод решения задач линейного программирования


Универсальный метод решения задач ЛП называется симплекс-методом. Применение этого метода и его наиболее часто встречающейся модификации - двухфазного симплекс-метода мы поясним на примерах.
Пример. Решить следующую задачу ЛП в канонической форме симплекс-методом.
                                 (5.5)
                                              (5.6)
xi ≥ 0, i = 1,…,6                                                 (5.7)
Говорят, что задача ЛП имеет каноническую форму, если все ограничения (кроме условий неотрицательности переменных) имеют вид равенств, а все свободные члены неотрицательны. Так что мы имеем задачу в канонической форме.
Идея симплекс-метода заключается в следующем. Сначала нужно найти некоторую (начальную) вершину многогранника допустимых решений (начальное допустимое базисное решение). Затем нужно проверить это решение на оптимальность. Если оно оптимально, то решение найдено; если нет, то перейти к другой вершине многогранника и вновь проверить на оптимальность. Ввиду конечности вершин многогранника (следствие конечности ограничений задачи ЛП) за конечное число "шагов" мы найдем искомую точку минимума или максимума. Надо заметить, что при переходе от одной вершины к другой значение целевой функции убывает (в задаче на минимум) или возрастает (в задаче на максимум).
Таким образом, идея симплекс-метода основывается на трех свойствах задачи ЛП.
Решение. Чтобы найти начальное допустимое базисное решение, т.е. чтобы определить базисные переменные, систему (5.6) нужно привести к "диагональному" виду. Применяя метод Гаусса (метод последовательного исключения неизвестных), получаем из (5.6):
                                    (5.8)
Следовательно, базисными являются переменные x2, x4, x5, x6, им придаем значения, равные свободным членам соответствующих строк: x2=40, x4=20, x5=10, x6=30,. Переменные x1 и x3 являются небазисными: x1=0, x3=0 .
Построим начальное допустимое базисное решение
x0 = (0,40,0,20,10,30)                                        (5.9)
Для проверки на оптимальность найденного решения x0 нужно из целевой функции исключить базисные переменные (с помощью системы (5.8) ) и построить специальную симплекс таблицу.
После исключения переменных целевую функцию удобно записать в виде:
f(x) = -7x1 – 14x3  +880                                    (5.10)
Теперь при помощи (5.8) –(5.10) составляем начальную симплекс-таблицу:

В нулевую строчку записаны коэффициенты с обратным знаком соответствующих переменных при целевой функции. Критерий оптимальности (для задачи на поиск минимума): допустимое базисное решение(x0) оптимально, если в нулевой строчке нет ни одного строго положительного числа (не считая значения целевой функции (880)). Это правило распространяется и на следующие итерации (таблицы). Элементы нулевой строки будем называть оценками столбцов.
Так что начальное допустимое базисное решение (5.9) неоптимально: 7>0, 14>0.
В нулевом столбике записаны значения базисных переменных. Они обязательно должны быть неотрицательными (см. уравнение (5.7) ). От первой по четвертую строки написаны коэффициенты переменных из системы (5.8).
Так как x0 неоптимально, то надо перейти к другой вершине многогранника допустимых решений (построить новое д.б.р.). Для этого нужно найти ведущий элемент и провести определенное преобразование (симплексное преобразование).
Сначала находим ведущий элемент таблицы, который стоит в пересечении ведущего столбика (столбец с наибольшей положительной оценкой) и ведущей строки (строки, соответствующей минимальному соотношению элементов нулевого столбика к соответствующим элементам (строго положительным) ведущего столбика).
В таблице 1 ведущий столбик - третий столбик, и ведущая строка - четвертая строка (min{40/1,30/1}=30/1) обозначены стрелками, а ведущий элемент - кружочком. Ведущий элемент показывает, что базисную переменную x6 нужно заменить на небазисную x3. Тогда новыми базисными переменными будут x2, x3, x4, x5, , а небазисными -x1, x6, . Это и означает переход к новой вершине многогранника допустимых решений. Чтобы найти значения координат нового допустимого базисного решения x00 нужно строить новую симплекс-таблицу и провести в ней элементарные преобразования:
а) все элементы ведущей строки поделить на ведущий элемент, превратив этим самым ведущий элемент в 1 (для простоты выкладок);
б) с помощью ведущего элемента (равного 1) все элементы ведущего столбика превратить в нули (аналогично методу исключения неизвестных);
В результате в нулевом столбце получены значения новых базисных переменных x2, x3, x4, x5, (см. таблицу 2) - базисные компоненты новой вершины x00 (небазисные компоненты x1=0, x6=0, ).

Как показывает таблица 2, новое базисное решение x00=(0,10,30,20,40,0) неоптимально (в нулевой строке есть неотрицательная оценка 7). Поэтому с ведущим элементом 1 (см. таблицу 2 ) строим новую симплекс-таблицу, т.е. строим новое допустимое базисное решение

Таблице 3 соответствует допустимое базисное решение x000=(10,0,30,10,50,0) и оно оптимально, т.к. в нулевой строчке нет положительных оценок. Поэтому f(x000)=390 есть минимальное значение целевой функции.

Ответ: x000=(10, 0, 30, 10, 50, 0) - точка минимума, f(x000)=390.
загрузка...