Пример 4.3.
Решить следующую задачу ЛП в неканонической форме симплекс-методом:
f(x) = x1 - x2 - 3x3 → min
при ограничениях
2x1 – x2 + x3 ≤ 1
-4x1 + 2x2 – x3 ≤ 2
3x1 +x3 ≤ 5
Умножая обе части
на -1 и прибавляя в левые части системы
дополнительные (или слабые) переменные
,
получим каноническую форму (слабые
переменные на целевую функцию не влияют):
f(x) = x1 - x2 - 3x3 → min
при ограничениях
2x1 – x2 + x3 + x4 = 1
-4x1 + 2x2 – x3 + x5 = 2
3x1 +x3 x6 = 5
x1,…, x6 ≥ 0
Так как все слабые переменные входят со знаком "+", то их можно взять в качестве базисных и составить н.д.б.р. x0=(0,0,0,1,2,5) . В данном случае исключать базисные переменные из целевой функции нет надобности (так как они в ней отсутствуют), поэтому целевую функцию записываем сразу в виде
(требование симплекс-метода). С помощью н.д.б.р. x0 и ограничений составим начальную симплекс-таблицу 4.4 (здесь f(x0)=0 ).
Таблица 4.4
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
f |
0 |
-1 |
1 |
3 |
0 |
0 |
0 |
x4 |
1 |
2 |
-1 |
1 |
1 |
0 |
0 |
x.5 |
2 |
-4 |
2 |
-1 |
0 |
1 |
0 |
X6 |
5 |
3 |
0 |
1 |
0 |
0 |
1 |
Так как x0 неоптимален (в нулевой строке есть положительные числа 1 и 3), то с обозначенным ведущим элементом строим новое д.б.р. И так далее. На четвертой итерации (шаге) получаем таблицу 4.5:
Таблица 4.5
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
f |
-43/3 |
0 |
0 |
0 |
-19/3 |
-11/3 |
-1/3 |
x3 |
4 |
0 |
0 |
1 |
2 |
1 |
0 |
x.2 |
11/3 |
0 |
1 |
0 |
-1/3 |
1/3 |
2/3 |
x1 |
1/3 |
1 |
0 |
0 |
-1/2 |
-1/3 |
1/3 |
На рис. 4.11 показана таблица коэффициентов для исходной системы в базисном виде для вершины (x1 = 0, x2 = 0, x3 = 0).
)Коэффициенты при нулевых переменных x2 и x3 - положительны. Значит целевая функция – не минимальна. Выбираем перемещение по ребру x3 до следующей вкршины симплекса, в которой
x3 = 1.
Рис. 4.11 Значение целевой функции в вершине (x1 = 0, x2 = 0, x3 = 0).
На рис. 4.12 показана таблица коэффициентов для следующей системы в базисном виде для вершины (x1 = 0, x2 =0, x4 =0).
Рис. 4.12 Значение целевой функции в вершине (x1 = 0, x2 = 0, x4 =0).
На рис. 4.13 показана таблица коэффициентов для следующей системы в базисном виде для вершины (x1 = 0, x4 =0, x5 =0).
Рис. 4.13 Значение целевой функции в вершине (x1 = 0, x4 = 0, x5 =0).
На рис. 4.14 показана таблица коэффициентов для последней системы в базисном виде для вершины (x4 = 0, x5 =0, x6 =0).
Рис. 4.14 Значение целевой функции в вершине (X4 = 0, X5 =0, X6 =0).
Как видно из последней таблицы, оптимальным решением задачи является x0000=(1/3, 11/3, 4) и f(x0000)=-46/3 .
Варианты заданий для этого примера приведены в приложении 4.3
Алгоритм симплекс-метода:
1. привести задачу к канонической форме:
2. привести систему ограничений к диагональной форме и определить базисные переменные;
3. исключить базисные переменные из целевой функции;
4. построить симплекс-таблицу;
5. проверить найденное д.б.р. на оптимальность: если оно оптимально, то решение закончить; если нет, то идти к пункту 6;
6. вычислить ведущий элемент таблицы;
7. провести симплексное преобразование;
8. построить новое д.б.р. и идти к пункту 5.
Если в ведущем столбике нет ни одного строго положительного элемента, то задача не имеет оптимального решения, а целевая функция не ограничена снизу (в задаче на минимум) или не ограничена сверху (в задаче на максимум).
Несовместимость системы ограничений (в канонической форме) обнаруживается при построении начального д.б.р. (оно не существует).
Симплекс-метод за конечное число итераций либо приводит к оптимальному решению, либо устанавливает неразрешимость задачи (см. пп. 1,2,3).
На каждой итерации симплекс-метод сохраняет допустимость базисного решения, т.е. неотрицательность элементов нулевого столбика - следствие правила выбора ведущей строки.
На каждой итерации целевая функция убывает (в задаче на минимум) или возрастаем (в задаче на максимум); это свойство нарушается только в случае зацикливания (см. примечания 11,12).
В качестве ведущего столбика можно выбирать любой столбик с положительной оценкой (в задаче на минимум), однако максимальность оценки ведущего столбика ведет к сокращению числа итераций (целевая функция быстро убывает).
Приложение 4.1