2.3 Симплекс-метод с искусственным базисом
Если математическая модель задачи линейного программирования содержит неравенства со знаком «≥» или (и) «=», для ее решения следует использовать симплекс-метод с искусственным базисом. Рассмотрим решение следующей задачи.
Задача 2.2.Определить оптимальный план задачи линейного программирования:
max Z = 25 x1 + 50 x2 + 40 x3
25 x1+ 50 x2 21000
40 x3 12000
x1
+
x2
+
x3
1000
10
x1
+
x2
+25
x3
15760
x1, x2, x3 0
Вначале запишем задачу в каноническом виде, путем введения дополнительных и искусственных переменных. С помощью этих переменных система неравенств принимает вид уравнений.
Если
в неравенстве стоит знак
,
то к левой части этого неравенства
прибавляется некоторая неизвестная
неотрицательная величина – дополнительная
переменная. Ее обозначают буквой x
с соответствующим
номером.
Если в неравенстве стоит знак , то от левой его части вычитается дополнительная неотрицательная переменная. Кроме того, в такие ограничения вводятся искусственные переменные, которые служат для создания опорного решения.
Искусственные переменные вводятся также в целевую функцию с коэффициентом «–М» при решении задачи максимизации и с коэффициентом «+М» при минимизации целевой функции, где М – положительная константа, превосходящая модуль любого из коэффициентов целевой функции.
В результате получаем задачу в каноническойформе:
z
= 25
x1
+
50x2
+
40
x3
+ 0·(
)-
M
x8
- M
x9
max
25x1+50x2 – x4 + x8 = 21000
40 x3 - x5 +x9 = 12000
x1 + x2 + x3 + x6 100
10x1 + x2 + 25x3+ x7 =15760
xJ 0,j=1,2,…,9
В симплекс-методе с искусственным базисом первоначальная таблица имеет две последние строки «М+1» и «М+2». Строку «М+1» формируют аналогично симметричному симплекс-методу, а в строку «М+2» записывают суммы соответствующих коэффициентов ограничений с искусственными переменными. В нашей задаче – это коэффициенты первого и второго ограничений. Сегмент последних двух строк, принадлежащий столбцам искусственных переменных x8 и x9, заполняют нулями.
Выпишем первую симплексную таблицу.
Таблица 1 – Первоначальная симплексная таблица.
|
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X |
21000 |
25 |
50 |
0 |
-1 |
0 |
0 |
0 |
1 |
0 |
|
X9 |
12000 |
0 |
0 |
40 |
0 |
-1 |
0 |
0 |
0 |
1 |
|
X6 |
1000 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
X7 |
15760 |
10 |
1 |
25 |
0 |
0 |
0 |
1 |
0 |
0 |
|
М+1 |
0 |
-25 |
-50 |
-40 |
0 |
0 |
0 |
0 |
0 |
0 |
|
M |
33000 |
25 |
50 |
40 |
1 |
1 |
0 |
0 |
0 |
0 |
8
+2
Разрешающий столбец определяют по наибольшему положительному элементу строки «М+2». Разрешающую строку выбирают по тому же правилу, что и в симплекс-методе без искусственных переменных. В ходе итераций искусственные переменные вытесняются из базиса, а соответствующие им столбцы исключают. Процесс продолжается до тех пор, пока все коэффициенты строки «М+2» не станут равными нулю. На этом первый этап решения задачи завершается. Его результатом является опорный план исходной задачи. Далее используются алгоритм симплекс-метода с выбором разрешающего столбца по строке «М+1».
В таблице 1 разрешающий элемент находится в строке 1 столбца х2. В результате пересчета получим таблицу 2.
Таблица 2 – Вторая симплексная таблица
|
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X9 |
|
X2 |
420 |
0.5 |
1 |
0 |
0.020 |
0 |
0 |
0 |
0 |
|
X |
12000 |
0 |
0 |
40 |
0 |
-1 |
0 |
0 |
1 |
|
X6 |
580 |
0.50 |
0 |
1 |
0.02 |
0 |
1 |
0 |
0 |
|
X7 |
15340 |
9.5 |
0 |
25 |
0.02 |
0 |
0 |
1 |
0 |
|
М+1 |
-21000 |
0 |
0 |
-40 |
-1 |
0 |
0 |
0 |
0 |
|
M |
12000 |
0 |
0 |
40 |
0 |
1 |
0 |
0 |
0
|
9
+2Разрешающий элемент находится в строке 2 столбца х3. Следующая таблица будет иметь вид:
Таблица 3 – Третья симплексная таблица
|
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
|
X2 |
420 |
0.5 |
1 |
0 |
-0.02 |
0 |
0 |
0 |
|
X3 |
300 |
0 |
0 |
1 |
0 |
-0.03 |
0 |
0 |
|
X |
280 |
0.5 |
0 |
0 |
0.02 |
0.03 |
1 |
0 |
|
X7 |
7840 |
9.5 |
0 |
0 |
0.02 |
0.63 |
0 |
1 |
|
М+1 |
33000 |
0 |
0 |
0 |
-1 |
-1 |
0 |
0 |
|
М |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6
+2В таблице 3 нет столбцов x8 и x9, так как эти искусственные переменные исключены из базиса. Строку «M+2» следует отбросить. Завершен первый этап решения задачи.
Разрешающий элемент находится в строке 3 столбца х4.
Таблица 4 – Четвертая симплексная таблица
|
Базис |
B |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
|
X2 |
700 |
1 |
1 |
0 |
0 |
0.02 |
1 |
0 |
|
X3 |
300 |
0 |
0 |
1 |
0 |
-0.03 |
0 |
0 |
|
X4 |
14000 |
25 |
0 |
0 |
1 |
1.25 |
50 |
0 |
|
X7 |
7560 |
9 |
0 |
0 |
0 |
0.60 |
-1 |
1 |
|
M+1 |
47000 |
25 |
0 |
0 |
0 |
0.25 |
50 |
0 |
Последняя строка таблицы 4 не содержит отрицательных элементов, следовательно, выполнился критерий оптимальности. Завершен второй этап решения.
Оптимальный план:
, 
,
,
,
, 
,
.