4.2. Правило преобразования симплекс-таблиц

Мы в пункте (4.1) увидели, что переход от одного опорного решения к другому начинается с исследования коэффициентов целевой функции и затем вычисляются коэффициенты новой модели задачи ЛП. Запишем требования к исходной модели задачи.

1. Задача линейного программирования должна быть представлена в виде канонической модели.

2. Целевая функция должна минимизироваться.

3. При занесении в таблицу у целевой функции меняются на противоположные знаки коэффициентов при свободных переменных.

Запишем полученную каноническую задачу:

а ₁₁х₁ + a₁₂x₂ + х₃ = b₁,

а ₂₁х₁ + a₂₂x₂ + х₄ = b₂,

а₃₁х₁ +a₃₂x₂ + х₅ = b₃,

f(X) = с₀ – (с₁х₁ +с₂х₂) → min.

В задаче Х_опор1 = (0, 0, b₁, b₂, b₃), f₁ = f (Х) = с₀. Внесем коэффициенты этой модели в симплекс-таблицу (см. табл. 4.1).

Таблица 4.1

Базис	В	х1	х2	х3	х4	х5
х3	b1	а11	al2	1	0	0
х4	b2	а21	a22	0	1	0
х5	b3	а31	a32	0	0	1
f(х)	с0	с1	с2	0	0	0

4. Рассмотрим последнюю строку таблицы 4.1 (коэффициенты целевой функции). Нас интересуют знаки с₁ и с₂.

а) если хотя бы один из коэффициентов положителен, например с₁ > 0, то отмечаем стрелкой столбец таблицы, где находится с₁. Этот столбец назовем ключевым. Если положительны оба коэффициента, то выберем наибольший из них;

б) если с₁ ≤ 0 и с₂ ≤ 0, то таблицу не надо преобразовывать. Из таблицы находится оптимальное решение.

5. Выберем ту базисную переменную, которая будет свободной вместо х₁, для этого выберем положительные из коэффициентов а_i1, i = 1, 2, 3.

Пусть для определенности у нас а₁₁ > 0, а₂₁ > 0, a_3l ≤ 0. Если все а_i1 отрицательны или равны нулю, то задача решений не имеет, т.к. целевая функция не ограничена. Пусть, кроме того, .

6. У нас a₁₁ >0, a₂₁ >0, тогда выберем . Это означает, что х₁ будет базисной переменной, а х₃  свободной. Переходим к следующей таблице:

Таблица 4.2

Базис	В	х1	х2	х3	х4	х5
х1	β1	1	al2*	al3*	0	0
х4	β2	0	a22*	a23*	1	0
х5	β3	0	a32*	a33*	0	1
f(х)	d0	0	d2	d3	0	0

7. Сначала заполняем первую строку таблицы 4.2, эта строка соответствует базисной переменной х₃ в таблице 4.1. Все коэффициенты 1-ой строки таблицы 4.1. делим на разрешающий элемент а₁₁, результат запишем в первую строку таблицы 4.2. Эта строка называется разрешающей.

, , .

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

8. Умножим разрешающую строку последовательно на (а₂₁), (а₃₁), (–с₁). Полученные строки чисел прибавим ко второй, потом к третьей, затем к последней строке таблицы 4.1, а результаты вычислений поставим во вторую, третью и последнюю строку таблицы 4.2, где:

; ; ;

; ; ;

; ; .

9. Мы получили новую таблицу, а следовательно, новый опорный план: Х_опор2 = (β₁, 0, 0, β₂, β₃), f₁ = f (Х_опор2) = d₀.

10. Если d₁ ≤0, d₂ ≤0, то решение оптимально. Если среди них есть положительные, то процесс преобразования таблиц надо продолжать.

Пример. Решим симплекс-методом пример из п.2. Модель задачи ЛП в этом примере стандартная:

12х₁ + 4х₂ ≤300,

4х₁ + 4х₂ ≤120,

3х₁ + 12х₂ ≤252, х₁ ≥0, х₂ 0;

f(х) = 30х₁ +40х₂  mах.

1 ) Перейдем к канонической модели. Для этого подберем х₃, х₄, х₅, уравнивающие левые и правые части системы ограничений. Затем перейдем к задаче минимизации: f(x)  max, тогда f₁(х) = – f(х)  min. Запишем каноническую модель:

12х₁ +4х₂ + х₃ =300,

4х₁ +4х₂+х₄ =120,

3х₁ +12х₂+х₅ =252, х_j ≥0, j = 1,…5;

f₁(х) = – (30х₁ +40х₂)  min.

2) Внесем коэффициенты в таблицу:

Таблица 4.3

Базис	В	х1	х2	х3	х4	х5
х3	300	12	4	1	0	0
х4	120	4	4	0	1	0
х 5	252	3	12	0	0	1
f1(х)	0	30	40	0	0	0

В таблице 4.3 с₁ = 30; с₂ = 40; 40 = max{30;40}, неизвестная х₂ – перейдет в базисную. Столбец ее коэффициентов будет ключевым. Все элементы ключевого столбца положительны.

2) Найдем разрешающую строку и разрешающий элемент в таблице:

Третья строка в таблице является разрешающей. Эта строка базисной переменной х₅, поэтому х₅ будет свободной переменной. Элемент, находящийся в таблице 4.3 на пересечении выделенных строки и столбца будет разрешающим элементом, равным 12. Замена базисной переменной х₅ на свободную х₂ в таблице 4.3 показаны стрелками.

3) Разделим все элементы третьей (разрешающей) строки таблицы 4.3 на 12. Далее все полученные элементы строки умножим последовательно на (– 4), (– 4), (– 40) и сложим с первой, второй и последней строкой таблицы 4.3. Составим новую симплекс-таблицу:

Таблица 4.4.

Базис	В	х1	х2	х3	х4	х5
х3	216	11	0	1	0	-1/3
х 4	36	3	0	0	1	-1/3
x2	21	1/4	1	0	0	1/12
f1(х)	-840	20	0	0	0	-10/3

4) Снова изучим последнюю строку таблицы 4.4. Там есть положительный коэффициент 20. Отметим ключевой столбец, выберем в нем элемент а₂₁. Тогда:

.

Будем работать с таблицей 4.4. так же, как и с таблицей 4.3. Делим вторую строку на 3. Затем получаем в столбце для переменной х₁ нули в остальных строках, умножая элементы разрешающей строки последовательно на (11), , (–20). Результаты поместим в таблицу 4.5:

Таблица 4.5.

Базис	В	х1	х2	х3	х4	х5
х3	84	0	0	1	-11/3	8/9
х1	12	1	0	0	4/3	-1/9
х2	18	0	1	0	-1/12	1/9
f1(х)	-1080	0	0	0	-20/3	-10/9

В последней строке таблицы 4.5 нет положительных чисел, решение оптимально.

Ответ: Х_min = (12, 18, 84, 0, 0); f₁ (Х_min) = 1080.

Ответ исходной задачи: Х_mах = (12, 18, 84, 0, 0); f (Х_mах) = 1080.