III. Решение задачи линейного программирования Симплекс-методом

 

Задача линейного программирования (ЗЛП) (1) - (3) (см. задание 2) назы­вается канонической, если все ограничения вида (2) являются уравнениями (равенствами), т.е. задачей линейного программирования в канонической форме называется задача:

Z = c₁ x₁ + c₂ x₂ +...+ c_n x_n ® min (max) (1)

при ограничениях:

a₁₁ x₁ + a₁₂ x₂ +...+ a_1n x_n = b₁

a₂₁ x₁ + a₂₂ x₂ +...+ a_2n x_n = b₂ (2)

...........................

a_m1 x₁ + a_m2 x₂ +...+ a_mn x_n = b_m,

x_j ³ 0, j = 1,..., n (3)

 

Симплекс-метод является вычислительной процедурой, которая позво­ляет решить любую каноническую ЗЛП алгебраическим методом. Теоретичес­кой основой метода являются следующие два утверждения:

Теорема 1. Если ЗЛП имеет допустимые решения, то существует хотя бы одно базисное допустимое решение задачи.

Теорема 2. Если ЗЛП имеет конечное оптимальное решение, то хотя бы одно из оптимальных решений является базисным.

Напомним, что решение системы (2) называется допустимым, если оно удовлетворяет ограничениям (3). Таким образом, из теоремы 1 следует, что если не существует ни одного базисного допустимого решения системы (2), то эта система вообще не имеет допустимых решений, т.е. ограничения (2) – (3) являются несовместными. В случае если имеются допустимые решения сис­темы 2, то теорема 2 утверждает, что оптимальное решение ЗЛП можно найти среди базисных допустимых решений этой системы, которых, как мы знаем, конечное число. Суть симплекс-метода и состоит в последовательном переборе базисных допустимых решений системы (2), начиная с некоторого начального, которое еще называют первоначальным опорным планом. Перебор осущест­вляется таким образом, чтобы каждое новое решение было лучше предыдущего (в смысле приближения к максимуму или минимуму целевой функции Z).

Итак, для применения метода необходимо, чтобы задача была в канони­ческой форме, и чтобы существовало начальное базисное допустимое решение (опорный план), наличие которого гарантирует непротиворечивость ограниче­ний задачи.

Чтобы преобразовать ЗЛП к каноническому виду к правой части каждого ограничения-неравенства прибавляют или вычитают неотрицательную допол­нительную переменную, например, ограничение 3х₁ + 5х₂ – 2х₃ £ 7 преоб­разуется в уравнение 3х₁ + 5х₂ – 2х₃ + х₄ = 7 прибавлением дополнительной переменной х₄ ³ 0, а неравенство вида х₁ – 2х₂ + х₃ ³ 5 заменяется на уравнение х₁ – 2х₂ + х₃ - х₅ = 5, где х₅ ³ 0.

Заметим, что знак неравенства ³ можно заменить на £ умножением всего неравенства на -1, например, неравенство х ₁ – 3 х₂ ³ -6 эквивалентно неравенст­ву -х₁ + 3х₂ £ 6. Отметим также, что максимизацию целевой функции Z можно заменить на минимизацию функции – Z и наоборот, так как максимум функции

Z = c₁ x₁ + c₂ x₂ +...+ c_n x_n достигается в тех же точках, что и минимум функции -Z = - c₁ x₁ - c₂ x₂ -...- c_n x_n.

Мы приведем алгоритм симплекс-метода для минимизации целевой функции (1) Z = c₁ x₁ + c₂ x₂ +...+ c_n x_n. Поясним суть метода на следующем примере:

Пусть требуется решить следующую ЗЛП: Найти максимум функции

Z = 3x₁ +4 x₂ ® max

при ограничениях:

3x₁ + x₂ £ 9

x₁ + 2x₂ £ 8

x₁, x₂ ³ 0.

Приведем задачу к каноническому виду и заменим максимизацию целе­вой функции Z на минимизацию функции Z¢ = -Z. Получим следующую задачу:

 

Z¢ = -3x₁ - 4x₂ + 0х₃ + 0х₄ ® min (4)

3x₁ + x₂ + x₃ = 9

x₁ + 2x₂ + x₄ = 8 (5)

x₁, x₂, x₃, x₄ ³ 0. (6)

 

Ясно, что переменные x₃ и x₄ являются базисными в системе (5) и соот­ветствующее базисное решение Х₀ = (0, 0, 9, 8) является допустимым, т.к. все

x_j ³ 0. При этом Z₀ = 0.

Начнем с того, что проверим опорный план Х₀ на оптимальность. По­скольку целевая функция Z¢ = -3x₁ - 4 x₂ + 0х₃ + 0х₄ выражена через свобод­ные переменные x₁ и x₂, коэффициенты при которых отрицательны, то, оче­видно, увеличение этих переменных приведет к уменьшению значения целевой функции на 3 ед. при увеличении x₁ на одну единицу и на 4 ед. при увеличении на одну единицу x₂ (сейчас x₁ и x₂ равны 0). Поэтому делаем вывод, что опор­ный план Х₀ не является оптимальным (т.к. введение в базис переменных x₁ и x₂ приведёт к уменьшению значения целевой функции).

Итак, для того, чтобы получить лучшее базисное решение, мы должны включить в базис переменные x₁ и x₂. Будем вводить их в базис по очереди. Поскольку увеличение переменной x₂ быстрее уменьшает Z, то выбираем переменную x₂ для включения ее в базис (это разумно, но не обязательно). Те­перь надо выяснить в какой строке системы (5) переменная x₂ будет базисной, чтобы полученное новое базисное решение было допустимым.

Анализируя первое уравнение системы 3x₁ + x₂ + x₃ = 9, замечаем, что поскольку x₁ = 0, то увеличение x₂ влечет уменьшение x₃. Так как x₃ ³ 0 ввиду (6), то увеличение x₂ возможно лишь до тех пор, пока x₃ не уменьшится до нуля, т.е. до значения 9/1 = 9. Поскольку переменная x₂ есть также и во втором уравнении, то рассуждая аналогично, заключаем, что в этом случае перемен­ную x₂ можно увеличивать максимум до значения 8/2 = 4 при котором пере­менная x₄ уменьшится до нуля.

Новое базисное решение будет допустимым, если мы будем увеличивать переменную х₂ до значения, равного min{9/1, 8/2} = 4, которое достигается во второй строке системы. Поэтому переменная x₂ должна быть базисной во втором уравнении, элемент а₂₂ = 4 системы будет разрешающим и, проводя преобразования Жордана-Гаусса, получаем новое (улучшенное) базисное допустимое решение:

 

X₁ = (0, 4, 5, 0), Z₁ = -3×0 - 4× 4 + 0×5 + 0×0 = -16 < Z₀ .

Теперь повторим эту процедуру для нового опорного плана Х₁. Для того, чтобы проверить его на оптимальность, нужно выразить целевую функцию че­рез свободные переменные x₁ и x₄ этого плана, поскольку их нужно будет изме­нять, чтобы получить другое (лучшее) базисное решение. Для этого из второго уравнения последней системы выражаем базисную переменную х₂ = 4 – ½ x₁ - ½ x₄ и подставляем ее в целевую функцию Z = -3x₁ - 4 x₂ + 0х₃ + 0х₄ = -3x₁ - 4 (4 – ½ x₁ - ½ x₄) + 0х₃ + 0х₄ = -16 – x₁ + 0х₂ + 0х₃ + 2 x₄.

Проводимые вычисления удобно оформлять в виде так называемых симплекс-таблиц, которые являются, фактически, расширенными матрицами системы ограничений (5) с добавленной Z – строкой.

Исходная симплекс-таблица.

Базис	х1 х2 х3 х4	Значение (bi)
х3 х4	3 1 1 0 1 2 0 1
- Z	-3 -4 0 0

Опорный план Х₀ = (0, 0, 9, 8), значение Z равно Z₀ = 0.

Таблица 1.

Базис	х1 х2 х3 х4	Значение (bi)
х3 х2	5/2 0 1 -½ ½ 1 0 ½
- Z	-1 0 0 2

 

План Х₁ = (0, 4, 5, 0), значение Z равно Z₁ = -16.

Последняя строка симплекс-таблицы называется Z – строкой поскольку в ней расположены коэффициенты целевой функции Z. Заметим, что для того, чтобы выразить коэффициенты целевой функции через свободные переменные, достаточно преобразованиями Жордана - Гаусса сделать нули в базисных столбцах Z – строки. При этом новое значение Z автоматически появится в столбце “Значение” с противоположным знаком.

Поскольку в Z – строке есть отрицательный коэффициент в первом столб­це, то план Х₁ не оптимален, так как введение в базис свободной переменной х₁ уменьшает Z (введение в базис свободной переменной х₄ увеличивает Z). Поэтому вводим в базис х₁, и первый столбец таблицы будет разрешающим. Чтобы выбрать разрешающую строку, как и раньше делим элементы столбца “Значение” на положительные элементы разрешающего столбца и находим минимальное частное: которое достигается в первой строке, которая и будет разрешающей. Значит разрешающим элементом таблицы 1 будет элемент а₁₁ = 5/2 (выделим его прямоугольником). Теперь проведем обычные преобразования Жордана – Гаусса относительно этого элемента, т.е. сначала делим разрешающую строку на разрешающий элемент,

 

Базис	х1 х2 х3 х4	Значение (bi)
x3 x2	1 0 2/5 -1/5 ½ 1 0 ½
- Z	-1 0 0 2

 

а затем делаем нули на месте всех остальных элементов разрешающего столбца, для чего: ко второй строке прибавляем первую, умноженную на -½, к Z – строке прибавляем первую. В результате получим новую таблицу Таблица 2.

Базис	х1 х2 х3 х4	Значение (bi)
x1 х2	1 0 2/5 -1/5 0 1 -1/5 3/5
- Z	0 0 2/5 9/5

Новое базисное решение (план) Х₂ = (2, 3, 0, 0), значение Z равно Z₂ = -18.

Просматривая Z – строку, замечаем, что в ней нет отрицательных эле­ментов. Это означает, что при попытке ввести в базис свободные переменные х₃ или х₄ целевая функция будет увеличиваться (на 2/5 и 9/5 единиц при увеличе­нии на 1 единицу переменных х₃ и х₄ соответственно). Таким образом, других базисных решений, лучших чем Х₂, (т.е. с меньшим, чем –18 значением Z) не существует.

Решение Х₂ = (2, 3, 0, 0) является оптимальным и Z_min = Z(X₂) = -18.

Решение исходной задачи: Z_max = 18 при х₁ = 2, х₂ = 3, х₃, х₄ = 0.

Обобщая приведенные выше рассуждения, сформулируем

 

Алгоритм Симплекс-метода

Исходные данные: задача в канонической форме; целевая функция мини­мизируется; найдено начальное базисное допустимое решение (опорный план),

то есть система уравнений (2) имеет базис и все правые части уравнений b_i ³ 0 - неотрицательны; целевая функция выражена через свободные переменные.

При выполнении этих условий каждая итерация метода состоит из трех шагов:

Шаг 1. Имеющийся план проверяется на оптимальность. Если в Z – стро­ке нет отрицательных элементов, то имеющийся план оптимален и задача реше­на. Если отрицательные элементы есть, то план не оптимален. Выбираем любой отрицательный элемент Z – строки (как правило, максимальный по модулю) и считаем столбец, в котором он находится в качестве разрешающего. Пусть для определенности это столбец переменной х_s.

Шаг 2. Выбор разрешающей строки. Пусть разрешающий столбец, вы­бранный на предыдущем шаге, это столбец переменной х_s. Для каждой i -ой строки (i = 1,...,m) делим элементы столбца свободных членов “Значение” (напомним, что все они неотрицательные) на положительные элементы разрешающего столбца, стоящие в этой строке, и находим минимальное из полученных частных, т.е. находим

Пусть этот минимум достигается в строке r. Тогда r -ая строка является разрешающей, элемент a_rs - разрешающий элемент таблицы.

Шаг 3. Пересчет таблицы. Преобразованиями Жордана-Гаусса пересчи­тываем таблицу относительно разрешающего элемента a_rs, найденного на предыдущем шаге, для чего:

3.1. Делим разрешающую строку на разрешающий элемент. В результате, на месте элемента a_rs будет стоять а¢_rs = 1.

3.2. Ко всем остальным строкам таблицы (включая Z - строку) прибав­ляем полученную разрешающую, умноженную на элемент (-a_is), где i – номер изменяемой строки i =1,2,...,r-1,r+1,...,m. К Z – строке прибавляем разрешаю­щую строку, умноженную на (- c_s). Иначе говоря, элементы новой таблицы (со штрихом) вычисляются по формулам:

а¢_rj = a_rj / a_rs; - новые элементы разрешающей строки (j = 1, 2,..., n);

b¢_r = b_r / a_rs

а¢_ij = a_ij - a¢_rj× a_is; - новые элементы i-й строки (i =1, 2,...,m; j = 1, 2,..., n);

b¢_i = b_i - b¢_r × a_is

c¢_j = c_j - a¢_rj× c_s; - новые элементы Z - строки (j = 1, 2,..., n);

Z¢ = Z - b¢_r × c_s

В результате этих преобразований в столбце х_s везде будут стоять нули кроме r -строки, где будет 1, т.е. х_s будет новой базисной переменной, целевая функция будет выражена через новые свободные переменные, новый план Х¢ находится в столбце “Значение” и лучше предыдущего, так как значение целевой функции для нового плана равно -Z¢ < Z. Переходим к шагу 1 и повторяем всю процедуру для нового плана Х¢.

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

 

Решение задачи линейного программирования в общем случае. Рас­смотрим следующую задачу ЛП:

Z = - 3x₁ + х₂ ® min

2x₁ – х₂ ³ 2,

-x₁ + 2х₂ ³ 5,

x₁ + х₂ £ 10,

x_1, х₂ ³ 0.

Приведем ее к каноническому виду введением трех неотрицательных пе­ременных х₃, х₄, х₅. Получим задачу:

 

Z = - 3x₁ + х₂ ® min

2x₁ – х₂ - х₃ = 2,

-x₁ + 2х₂ - х₄ = 5, (7)

x₁ + х₂ + х₅ = 10,

x_1, х₂, х₃, х₄, х₅ ³ 0.

При попытке решить эту задачу симплекс-методом возникает опреде­ленная трудность, связанная с тем, что нет очевидного начального базисного допустимого решения (опорного плана), так как переменные х₃ и х₄ не являют­ся базисными. Умножение первых двух уравнений на -1 также ничего не дает, поскольку соответствующее базисное решение (0, 0, -2, -5, 10) не будет до­пустимым. Пытаться просто перебирать базисные решения в попытке отыскать допустимое, нецелесообразно, так как неясно, имеет ли эта задача вообще допустимые решения.

Для решения проблемы применим метод искусственного базиса. Введем в первые два уравнения (третье не создает проблем) искусственные перемен­ные х₆ ³ 0 и х₇ ³ 0. В результате получим базис из переменных х₆, х₇, х₅.

2x₁ – х₂ - х₃ + х₆ = 2,

-x₁ + 2х₂ - х₄ + х₇ = 5, (8)

x₁ + х₂ + х₅ = 10,

 

Соответствующее базисное решение Х₀ = (0, 0, 0, 0, 10, 2, 5) является до­пустимым для ограничений (8). Однако ограничения (7) и (8) не являются экви­валентными в том смысле, что любому допустимому решению системы ограни­чений (8), в котором хотя бы одна искусственная переменная отлична от нуля, нельзя поставить в соответствие допустимое решение системы ограничений (7). С целью исключения искусственных переменных из базисного решения систе­мы ограничений (8), т.е. для получения допустимого базисного решения систе­мы ограничений (7), используем алгоритм симплекс-метода. Для того, чтобы искусственные переменные стали свободными, необходимо, чтобы они были равны нулю (сейчас х₆ = 2, х₇ = 5). Поэтому введем искусственную целевую функцию

W = х₆ + х₇.

и будем ее минимизировать при ограничениях (8). Если удастся найти базисное допустимое решение при котором W = 0 (сейчас W = 7), то тогда х₆ и х₇ будут равны нулю, поскольку они неотрицательны, и мы получим базис из основных и дополнительных переменных.

Таким образом, задача разбивается на два этапа. На первом этапе мини­мизируется искусственная целевая функция W. Этот этап закончится либо нахождением опорного плана исходной задачи (7), либо тем, что минимизи­ровать функцию W до нуля не удастся, т.е. допустимых планов нет, а значит (ввиду теоремы 1) и нет вообще допустимых решений задачи.

Если опорный план найдется, то на втором этапе решаем задачу симп­лекс-методом. Проиллюстрируем описанный выше метод искусственного бази­са, применив его к решению задачи (7).

Этап 1. Составим исходную симплекс-таблицу для задачи (8). Все вычис­ления будем проводить также и для целевой функции Z. Тогда после заверше­ния первого этапа получим целевую функцию Z, выраженную через свободные переменные.

 

Базис	х1 х2 х3 х4 х5 х6 х7	Значение
x6 х7 x5	2 -1 -1 0 0 1 0 -1 2 0 -1 0 0 1 1 1 0 0 1 0 0
- Z	-3 1 0 0 0 0 0
- W	0 0 0 0 0 1 1

 

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

Таблица 1.

Базис	х1 х2 х3 х4 х5 х6 х7	Значение
x6 х7 x5	2 -1 -1 0 0 1 0 -1 2 0 -1 0 0 1 1 1 0 0 1 0 0
- Z	-3 1 0 0 0 0 0
- W	-1 -1 1 1 0 0 0	-7

 

Так как в W – строке есть отрицательные элементы, то выбираем в качест­ве разрешающего любой из первых двух столбцов, например первый. Посколь­ку min{2/2, 10/1} = 1 достигается в первой строке, то разрешающая строка – первая и разрешающий элемент а₁₁ = 2. Пересчитывая таблицу относительно этого элемента, получим новую таблицу:

Таблица 2.

Базис	х1 х2 х3 х4 х5 х7	Значение
x1 х7 x5	1 -½ -½ 0 0 0 0 3/2 -½ -1 0 1 0 3/2 ½ 0 1 0
- Z	0 -½ -3/2 0 0 0
- W	0 -3/2 ½ 1 0 0	-6

 

Так как переменная х₆ вышла из базиса, то в дальнейшем ее не исполь­зуем (вычеркиваем столбец х₆). Теперь разрешающим столбцом будет второй, разрешающей строкой – вторая и после пересчета получим (поскольку искусственная переменная х₇ выйдет из базиса, столбец х₇ также вычеркиваем):

Таблица 3.

Базис	х1 х2 х3 х4 х5	Значение
x1 х2 x5	1 0 -2/3 -1/3 0 0 1 1/3 -2/3 0 0 0 1 1 1
- Z	0 0 -5/3 -1/3 0

 

Этап 1 успешно завершен, так как искусственные переменные выведены из базиса и мы получили опорный план Х₀ = (3, 4, 0, 0, 3) исходной задачи (7), к которому можно применить алгоритм симплекс-метода. На втором этапе W - строка уже не нужна и мы ее вычеркиваем.

 

 

Этап 2. Таблица 3.

Базис	х1 х2 х3 х4 х5	Значение
x1 х2 x5	1 0 -2/3 -1/3 0 0 1 -1/3 -2/3 0 0 0 1 1 1
- Z	0 0 -5/3 -1/3 0

 

Целевую функцию Z можно уменьшить (сейчас Z = -5) если ввести в базис х₃ или х₄.

Выбираем третий столбец в качестве разрешающего, т.к. –5/3 < -1/3. Разрешающей строкой будет третья, т.к. только в ней есть положительный эле­мент разрешающего столбца. Разрешающий элемент а₃₃ = 1. Пересчитывая таблицу, получим:

Таблица 4.

Базис	х1 х2 х3 х4 х5	Значение
x1 х2 x3	1 0 0 1/3 2/3 0 1 0 -1/3 1/3 0 0 1 1 1
- Z	0 0 0 4/3 5/3

 

Поскольку в Z – строке таблицы 4 нет отрицательных элементов, то новый план Х₁ = (5, 5, 3, 0, 0) является оптимальным и Z_min = Z(5,5) = -10.

Задача решена полностью.

 

КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задание 3. Решить задачу линейного программирования симплекс-методом (x, y ³ 0).

 

Варианты:

 

1. Z = x - 2y ® min 2. Z = -x + y ® min

3x + y ³ 8 3x - 2y ³ 7

4x + 5y £ 29 x + 2y £ 13

x + 4y ³ 10 x - 2y £ 1

 

3. Z = 2x + y ® max 4. Z = x - y ® max

-x + 2y ³ 3 -2x + 3y £ 5

-x + y £ 1 x + 2y ³ 8

3x - 2y £ 3 3x - y £ 10

 

 

5. Z = 2x + y ® max 6. Z = x + y ® max

x - y £ 0 x - y ³ 0

3x - 2y £ 3 -x + 2y £ 4

5x - 4y ³ 1 -3x + 4y ³ 2

 

7. Z = 5x + 2y ® max 8. Z = 2x + 4y ® max

3x + y ³ 9 3x + y ³ 8

2x + y ³ 7 -x + 3y ³ 4

5x + 2y £ 17 x + 2y £ 11

 

9. Z = 2x + y ® max 10. Z = x - y ® min

-x + 5y £ 4 x + 3y £ 7

x - y £ 4 2x - y £ 7

x + y ³ 2 5x + y ³ 7