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

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

Основные положения симплекс-метода - №1 - открытая онлайн библиотека (4.1)

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

Основные положения симплекс-метода - №2 - открытая онлайн библиотека

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

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

x1 + x4=2,

x2 + 2x4=7,

x3 – x4=2.

Так как х1= 2 – х4 и Основные положения симплекс-метода - №3 - открытая онлайн библиотека , то х4 < 2; аналогично х2=7 – 2х4и Основные положения симплекс-метода - №4 - открытая онлайн библиотека , следовательно Основные положения симплекс-метода - №5 - открытая онлайн библиотека . Так как х3 = 2 + х4, то здесь х4 может возрастать неограниченно. Далее выберем максимально возможное значение х4 равное 2; при этом х1 = 0, х2 = 3, х3 = 4, х4 = 2, х5 = 0.

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

Основные положения симплекс-метода - №6 - открытая онлайн библиотека x2 – 2x1 + x5 = 3,

Основные положения симплекс-метода - №7 - открытая онлайн библиотека x3 + x1 + 2x5 = 4, (4.2)

x4 + x1 + x5 = 2;

Основные положения симплекс-метода - №8 - открытая онлайн библиотека

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

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

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

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

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

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

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

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

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

Основные положения симплекс-метода - №9 - открытая онлайн библиотека а11х1 + a12x2 + х3= b1,

Основные положения симплекс-метода - №7 - открытая онлайн библиотека а21х1 + a22x2 + х4= b2,

а31х1 +a32x2 + х5= b3,

f(X) = с0 – (с1х12х2)→min.

В задаче Хопор1 = (0,0, b1, b2, b3), f1= f (Х) = с0. Внесем коэффициенты этой модели в симплекс-таблицу (см. табл. 4.1).

Таблица 4.1

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

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

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

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

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

Пусть для определенности у нас а11 > 0, а21 > 0, a3l ≤ 0. Если все аi1 отрицательны или равны нулю, то задача решений не имеет, т.к. целевая функция не ограничена. Пусть, кроме того, Основные положения симплекс-метода - №11 - открытая онлайн библиотека .

6. У нас a11 >0, a21 >0, тогда выберем Основные положения симплекс-метода - №12 - открытая онлайн библиотека . Это означает, что х1 будет базисной переменной, а х3 - свободной. Переходим к следующей таблице:

Таблица 4.2

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

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

Основные положения симплекс-метода - №13 - открытая онлайн библиотека , Основные положения симплекс-метода - №14 - открытая онлайн библиотека , Основные положения симплекс-метода - №15 - открытая онлайн библиотека .

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

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

Основные положения симплекс-метода - №16 - открытая онлайн библиотека ; Основные положения симплекс-метода - №17 - открытая онлайн библиотека ; Основные положения симплекс-метода - №18 - открытая онлайн библиотека ;

Основные положения симплекс-метода - №19 - открытая онлайн библиотека ; Основные положения симплекс-метода - №20 - открытая онлайн библиотека ; Основные положения симплекс-метода - №21 - открытая онлайн библиотека ;

Основные положения симплекс-метода - №22 - открытая онлайн библиотека ; Основные положения симплекс-метода - №23 - открытая онлайн библиотека ; Основные положения симплекс-метода - №24 - открытая онлайн библиотека .

9. Мы получили новую таблицу, а следовательно, новый опорный план: Хопор2 = (β1, 0, 0, β2, β3), f1= f (Хопор2) = d0.

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

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

 
  Основные положения симплекс-метода - №25 - открытая онлайн библиотека

12х1 + 4х2 ≤300,

1 + 4х2 ≤120,

1 + 12х2 ≤252, х1 ≥0, х2 Основные положения симплекс-метода - №26 - открытая онлайн библиотека 0;

f(х) = 30х1 +40х2 ® mах.

Основные положения симплекс-метода - №27 - открытая онлайн библиотека 1) Перейдем к канонической модели. Для этого подберем х3, х4, х5, уравнивающие левые и правые части системы ограничений. Затем перейдем к задаче минимизации: f(x) ® max, тогда f1(х) = – f(х) ® min. Запишем каноническую модель:

12х1 +4х2 + х3 =300,

1 +4х24 =120,

1 +12х25 =252, хj ≥0, j = 1,…5;

f1(х) = – (30х1 +40х2) ® min.

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

Таблица 4.3

Базис В х1 х2 х3 х4 х5
х3
х4
Основные положения симплекс-метода - №28 - открытая онлайн библиотека х5
f1(х)

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

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

Основные положения симплекс-метода - №29 - открытая онлайн библиотека

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

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

Таблица 4.4.

Базис В х1 х2 х3 х4 х5
х3 -1/3
Основные положения симплекс-метода - №30 - открытая онлайн библиотека х4 -1/3
x2 1/4 1/12
f1(х) -840 -10/3

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

Основные положения симплекс-метода - №31 - открытая онлайн библиотека .

Будем работать с таблицей 4.4. так же, как и с таблицей 4.3. Делим вторую строку на 3. Затем получаем в столбце для переменной х1 нули в остальных строках, умножая элементы разрешающей строки последовательно на (-11), Основные положения симплекс-метода - №32 - открытая онлайн библиотека , (–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
f1(х) -1080 -20/3 -10/9

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

Ответ: Хmin = (12, 18, 84, 0, 0); f1min) = -1080.

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