Основные положения симплекс-метода

 

Пусть задана задача линейного программирования в виде канонической модели.

(4.1)

Рассмотрим идею симплекс-метода на этом примере. Нетрудно убедиться, что система (4.1) совместна. Ее ранг r = 3, значит базисных переменных 3, а свободных переменных k = 5 – 3 = 2. Полагая свободные переменные x ₄, x ₅ равными нулю, получим первое опорное решение:

В начальном плане свободными, а значит равными нулю являются переменные х ₄, х ₅. Посмотрим, нельзя ли за счет увеличения х ₄ и х ₅ уменьшить значение целевой функции. У нас f(X) =3- х ₄ + х ₅, неизвестная х ₅ входит в выражение целевой функции со знаком плюс, поэтому ее увеличение приводит к увеличению функции. И это нам невыгодно. В то же время неизвестная х ₄ входит в выражениях со знаком минус. Поэтому ее увеличение сопровождается уменьшением значения функции f(Х). Увеличение свободной неизвестной х ₄ вызывает соответствующие изменения базисных переменных х ₁, х ₂, х ₃. Эти изменения могут оказаться такими, что базисные переменные станут отрицательными. Мы должны позаботиться о том, чтобы этого не произошло.

Оставим у переменной х ₅ - значение равное нулю и рассмотрим уравнения, которые в этом случае получаются из системы (4.1):

x ₁ + x ₄=2,

x ₂ + 2x ₄=7,

x ₃ – x ₄=2.

 

Так как х ₁= 2 – х ₄ и , то х ₄ < 2; аналогично х ₂=7 – 2 х ₄и , следовательно . Так как х ₃ = 2 + х ₄, то здесь х ₄ может возрастать неограниченно. Далее выберем максимально возможное значение х ₄ равное 2; при этом х ₁ = 0, х ₂ = 3, х ₃ = 4, х ₄ = 2, х ₅ = 0.

Мы перешли к новому опорному решению: X _опор2 = (0, 3, 4, 2, 0). Сравнивая X _опор1и X _опор2, видим, что х ₁ стала свободной, а х ₄ - базисной. Модель надо преобразовать так, чтобы х ₄ присутствовало только в первом уравнении системы (4.1), функция f(X) должна быть выражена через свободные переменные х ₁ и х ₅. Из первого уравнения х ₄ = 2 – х ₁ – х ₅, и задача ЛП будет такой:

x ₂ – 2 x ₁ + x₅ = 3,

x ₃ + x ₁ + 2 x ₅ = 4, (4.2)

x ₄ + x ₁ + x ₅ = 2;

 

Теперь видно, что f(X) не может быть уменьшена за счет увеличения х ₁ и х ₅. Значит, мы получили оптимальное решение. Запишем его.

 

Х _min = (0, 3, 4, 2, 0); f _min= f(Х _min ) = 1.

 

Идею, рассмотренную в примере, используем для того, чтобы сформулировать правило преобразования симплекс-таблиц для решения задач симплексным методом.

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	b 1	а 11	a l2
х 4	b 2	а 21	a 22
х 5	b 3	а 31	a 32
f(х)	с 0	с 1	с 2

 

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

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

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

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

Пусть для определенности у нас а ₁₁ > 0, а ₂₁ > 0, a _3l ≤ 0. Если все а_{i 1} отрицательны или равны нулю, то задача решений не имеет, т.к. целевая функция не ограничена. Пусть, кроме того, .

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

Таблица 4.2

Базис	В	х 1	х 2	х 3	х 4	х 5
х 1	β 1		a l2*	a l3*
х 4	β 2		a 22*	a 23*
х 5	β 3		a 32*	a 33*
f(х)	d 0		d 2	d 3

 

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
х 4
х 5
f 1 (х)

 

В таблице 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						-1/3
х 4						-1/3
x 2		1/4				1/12
f 1 (х)	-840					-10/3

 

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

.

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

Таблица 4.5.

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

 

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

 

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

 

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