Итерация 1

Базисные переменные	Рассматриваемое пробное решение	Коэффициент при Х4	Значения отношений	Минимальное значение	Следующее пробное решение
Х0	0	- 11	-	-	-
Х5	15	1	15	-	-
Х6	120	2	60	-	-
Х7	100	15	100/15	6,67	Х4 = 6,67; Х7=0

Шаг 4. Перепишем соотношения (7.55) таким образом, чтобы в строке 3 коэффициент при Х₄ был равен единице, а в строках 0, 1 и 2 -нулю. Процедуру, с помощью которой это достигается, называют опе­рацией замены базиса. Сначала разделим обе части уравнения в стро­ке 3 на коэффициент при Х₄, т. е. на 15

(7.56)

Обратим в нули коэффициенты при Х₄ в строках 0,1,2, действуя по следующей схеме:

1. умножить строку 3 на 11 и результат прибавить к строке 0;

2. умножить строку 3 на — 1 и результат прибавить к строке 1;

3. умножить строку 3 на — 2 и результат прибавить к строке 2.

В результате получим

Полученное уравнение (7.57) эквивалентно уравнению (7.55). Его удобство заключается в том, что, полагая Х₁ = Х₂= ... = Х₆ = Х₇ = 0, сразу можно определить значения переменных для нового пробного базисного решения. Х₀ = 220/3, Х₅ = 25/3, Х₆ = 320/3, Х₄ = 20/3. Прибыль для нового пробного решения равняется прибыли при пре­дыдущем пробном базисе плюс значение новой базисной перемен-

ной, умноженной на удельный вклад новой базисной переменной, в приращении прибыли:

220 / 3 = 0 + 20/3*11 .

Смысл правила 2 становится теперь более ясным. Если бы вместо Х₇ из первоначального базиса исключить X₅ (или Х₆), то Х₄, Х₇, Х₆ (или X₅) приняли бы отрицательное значение, что противоречит пред­положению о том, что ни одна из переменных не может быть отрица­тельной.

Итерация 2. Завершив первую итерацию, следует вернуться к шагу 2, с тем чтобы определить, является ли полученное решение оптимальным. Если оптимум еще не достигнут, необходимо в соот­ветствии с симплексным алгоритмом приступить к следующей итера­ции. Согласно правилу 1, возможность улучшить решение существует.

Таблица 37

Итерация 2

Базисные переменные	Рассматриваемое пробное решение	Коэффициент при Х1	Значения отношений	Минимальное значение	Следующее пробное решение
Х0	220/3	- 9/5	-	-	-
Х5	25/3	4/5	125/12	125/12	Х1 = 125/12; Х5=0
Х6	320/3	33/5	1600/99	-	-
Х4	20/3	1/5	100/3	-	-

При этом в очередной базис можно включить либо Х₁ либо Х₂ либо Х_3. На основании правила 1 выбор падает на Х₁ так как эта переменная обеспечивает наибольшее удельное приращение для зна­чения целевой функции.

(7.57)

В соответствии с табл. 37 в очередном пробном решении Х₅ следует заменить на Х₁. С учетом произведенной замены необходимо преобра­зовать систему уравнений (7.57). Вначале выполним нормировку ко­эффициента при Х₁ в строке 1:

(7.58)

Затем исключим X, из уравнений в строках 0, 2, 3, действуя по сле­дующей схеме:

262

263

1. умножить строку 1 на 9/5 и результаты сложить со строкой 0;

2. умножить строку 1 на - 33/5 и результаты сложить со строкой 2;

3. умножить строку I на - 1/5 и результаты сложить со строкой 3.

В результате получим:

Третье пробное базисное решение дало следующие результаты:

Х₀= 1105/12, Х₁= 125/12, Х₆= 455/12, Х₄= 55/12.

Итерация 3. Завершив вторую симплекс-итерацию, видим (строка 0), что решение может быть улучшено за счет X_3. Определим, какая переменная должна быть исключена из базиса.

Пронормируем коэффициент X₃ в строке 3 путем деления обеих частей соответствующего уравнения на 7/12 и исключим X₃ из урав­нений в строках 0,1 и 2 следующим образом:

1. умножить строку 3 на 11/12 и результат сложить со строкой 0;

2. умножить строку 3 на - 5/12 и результат сложить со строкой 1;

3. умножить строку 3 на 13/12 и результат сложить со строкой 2.

4. В результате получим:

В строке 0 все коэффициенты положительны, следовательно, со­гласно правилу 1, полученное решение является оптимальным (табл. 38).

Таблица 38

Итерация 3

(7.59)

Базисные переменные	Рассматриваемое пробное решение	Коэффициент при Х3	Значения отношений	Минимальное значение	Следующее пробное решение
Х0	1105/12	- 11/12	-	-	-
Х1	125/12	5/12	25	-	-
Х6	455/12	-13/12	-	-	Х3 = 55/7,
Х4	55/12	7/12	55/7	55/7	Х4=0

Коэффициенты при переменных в окончательном варианте строки 0 иногда называют скрытыми издержками. Каждый коэффициент определяет отклонение значения целевой функции от оптимального при увеличении значения соответствующей небазисной переменной на единицу. Таким образом, предприятие будет иметь прибыль 695/7 при выпуске продукции по технологическому процессу 1 и 3.

В кратком изложении симплексный метод состоит в следующем:

Шаг 1 . Выбирается исходный базис.

Шаг 2. Используется правило 1. Если рассматриваемое пробное решение не является оптимальным, осуществляется переход к шагу 3. В противном случае вычисления прекращаются.

Шаг 3. Выполняется процедура, предписанная правилом 2.

Шаг 4. Сменяется базис, после чего возвращаются к шагу 2.