Пусть исходная задача линейного программирования представлена в канонической форме
f = c1x1 + c2x2 + … + cnxn > min;
a11x1 + a12x2 + … + a1nxn + xn+1 = b1;
a21x1 + a22x2 + … + a2nxn + xn+2 = b2;
……………………………………………;
am1x1 + am2x2 + … + amnxn + xn+m = bm;
∀xj ≥ 0 и ∀bi > 0.
Шаг 1. Построим начальную симплекс-таблицу (табл. 2.1).
Таблица 2.1
x1 ... |
x2 ... |
x3 |
xn |
... |
xn+m |
–f |
||
xn+1 |
a11 |
a1s |
a1n |
1 |
b1 |
|||
xn+r |
ar1 |
ars |
arn |
... |
bm |
|||
xn+m |
am1 |
ams |
amn |
1 |
br |
|||
–f |
c1 |
cs |
cn |
1 |
0 |
Шаг 2. Если все сj ≥ 0, то конец – оптимальным решением является базисное решение (2.6); если некоторое значение сj < 0, то выбрать переменную xs, которая будет введена в базисное множество на следующей итерации вместо r-й базисной переменной, так чтобы
cs = min cj < 0.
Шаг 3.
а) Если все ais ≤ 0, то конец, множество решений есть:
– xs ≥ 0 произвольно, базисные переменные равны
xj = bi – aisxs;
– небазисные переменные xj = 0 (j ≠ s) удовлетворяют исходной системе и обладает свойством
f = f0 + csxs → –∞ при xs → +∞.
б) Если какое-то ais > 0, то выбираем r-ю базисную переменную, чтобы вывести ее в следующей итерации, следующим образом
при ais > 0.
Шаг 4. Чтобы получить из предшествующей таблицы начальные данные таблицы, описывающей следующую итерацию, умножим каждый элемент выбранной строки r на число, обратное ведущему элементу ars и поместим эти произведения в r-ю строку таблицы для следующей итерации (табл. 2.2). Вводим переменную xs на место переменной xn+r в предыдущей итерации. Чтобы получить элемент, стоящий в i-й строке и j-м столбце в новой таблице, вычтем из соответствующего элемента предыдущей таблицы произведение числа, стоящего в i-й строке и s-м столбце предыдущей таблицы на число, стоящее в r-й строке и j-м столбце новой таблицы.
Таблица 2.2
x1 ... xn+1 |
x2 ... .... |
x3 xn+m |
xn |
… |
xn+m |
–f |
bi |
|
xn+1 |
|
|
1 |
|
||||
xn+r |
|
1 |
|
... |
|
|||
xn+m |
|
|
1 |
|
||||
1 |
||||||||
... |
||||||||
1 |
||||||||
–f |
c1 |
cs |
cn |
1 |
|
где в соответствии с правилами шага 4:
Пример 2.1.
f = –9x1 – 10x2 – 16x3 > min;
18x1 + 15x2 + 12x3 + x4 = 360;
6x1 + 4x2 + 8x3 + x5 = 192;
5x1 + 3x2 + 3x3 + x6 = 180;
∀xj ≥ 0.
Шаг 1. Начальная симплекс-таблица имеет вид (табл. 2.3)
Таблица 2.3
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
–f |
bi |
|
x4 |
18 |
15 |
12 |
1 |
360 |
|||
x5 |
6 |
4 |
8 |
1 |
192 |
|||
x6 |
5 |
3 |
3 |
1 |
180 |
|||
–f |
–9 |
–10 |
–16 |
1 |
0 |
Шаг 2. cs = min {–9; –10; –16} = –16. Следовательно, s = 3.
Шаг 3.
Следовательно r = 2 и ведущий элемент ars = a23 = 8.
Шаг 4. Переход к следующей симплекс-таблице (табл. 2.4)
Таблица 2.4
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
–f |
|
|
x4 |
9 |
9 |
1 |
|
72 |
|||
x3 |
|
|
1 |
|
24 |
|||
x6 |
–1 |
|
|
1 |
108 |
|||
–f |
3 |
–2 |
2 |
1 |
384 |
Так как условие теоремы 2.3 не выполнено снова переходим к шагу 2.
Шаг 2. cs = –2.Следовательно s = 2.
Шаг 3.
Следовательно r = 1 и ведущий элемент ars = a12 = 9.
Шаг 4. Переход к следующей симплекс-таблице (табл. 2.5)
Таблица 2.5
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
–f |
bi |
|
x2 |
9 |
1 |
|
|
8 |
|||
x3 |
|
1 |
|
|
20 |
|||
x6 |
|
|
|
1 |
96 |
|||
–f |
6 |
|
|
f |
400 |
Все относительные оценки в последней симплекс-таблице не отрицательны, следовательно, в соответствии с теоремой 2.3 имеем оптимальное решение:
x1 = 0; x2 = 8; x3 = 20; x4 = 0; x5 = 0; x6 = 96; f = –400.