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

Пример.

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

Рассмотрим однородную задачу ЛП:

(1)

Добавив к левым частям системы неравенств соответствующие балансовые переменные преобразуем задачу (1) в каноническую форму:

(2)

Для удобства и единообразия запишем определение целевой функции в виде уравнения:

(3)

Запишем (2) и (3) в виде первой симплекс таблицы:

0	1	1	1	0	0	8
0	- 2	3	0	1	0	9	(4)
0	2	- 1	0	0	1	10
1	- 4	- 3	0	0	0	- 1

Первые три строки таблицы (4) содержат, по сути, расширенную матрицу системы линейных уравнений (2), к которой слева приписан столбец переменной . Последняя строка, называемая индексной, содержит уравнение (3). Буквой , как обычно, обозначен столбец свободных членов. Отметим, что таким образом составленная таблица (4) называется симплексной, поскольку задача (2) имеет симплексную форму. Напомним, что это означает, что, во-первых, матрица системы (и таблица (4)) содержат т базисных столбцов (столбцы ), где т - число уравнений (в данном случае ); во-вторых, все элементы столбца свободных членов неотрицательны (это числа 8, 9 и 10), кроме, возможно, элемента индексной строки; в- третьих, целевая функция зависит только от свободных переменных ( и ). Последнее верно, поскольку в базисных столбцах ( ) в индексной строке находятся только нули. Первая симплекс-таблица (4) определяет первое опорное решение. Напомним, что опорное решение является допустимым базисным решением, и, следовательно, свободные переменные и равны нулю: и .

Далее, переменная определяется первой строкой таблицы (4), которая является сокращённой записью первого уравнения системы (2). При оно принимает вид:

Вторая строка таблицы определяет переменную

Третья строка определяет :

Значение целевой функции определяем по индексной строке:

В дальнейшем мы покажем, что оптимальное решение канонической задачи ЛП является опорным, и, следовательно, его следует искать среди опорных решений. Симплекс-таблица (4) и дает одно из таких решений. Как проверить, является ли оно оптимальным? Оказывается, просто. Как мы увидим далее, если коэффициенты целевой функции канонической задачи ЛП неположительные: ,- и функция зависит только от свободных переменных, то соответствующее опорное решение является оптимальным.

Но условие означает, что коэффициенты индексной строки, стоящие в столбцах свободных переменных, должны быть неотрицательны: поскольку индексная строка соответствует уравнению: , - и содержит коэффициенты с противоположным знаком.

Мы видим, что в таблице (4) условие неотрицательности всех элементов индексной строки (разумеется, кроме правой части , стоящей в столбце свободных членов) не выполнено. Более того, оба столбца свободных переменных и содержат в индексной строке отрицательные элементы: - 4 и -3, - соответственно.

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

,

где - номер ведущего столбца.

В нашем случае и допустимые отношения соответственно равны:

Добавим к симплекс-таблице (4) столбец :

0	1	1	1	0	0	8	8
0	- 2	3	0	1	0	9		(5)
0	2	- 1	0	0	1	10	5
1	- 4	- 3	0	0	0	- 1

В таблице (5) отрицательный элемент – 4 ведущего столбца взят в рамочку, для того чтобы выделить ведущий столбец. Можно, разумеется, выделить этот столбец и любым другим разумным образом: цветом, шрифтом и т.п.

Среди всех допустимых отношений найдем наименьшее: .

Наименьшее допустимое отношение соответствует третьей строке таблицы, которую мы теперь объявляем ведущей строкой. На пересечении ведущей строки и ведущего столбца стоит ключевой элемент таблицы. В нашем случае это Выделим в таблице (5) минимальное допустимое отношение и ключевой элемент, рамочкой:

0	1	1	1	0	0	8	8
0	- 2	3	0	1	0	9		(6)
0	2	- 1	0	0	1	10	5 =
1	- 4	- 3	0	0	0	- 1

Дальнейшая наша цель состоит в том, чтобы преобразовать методом Гаусса таблицу (6) в новую симплекс-таблицу, первый столбец который стал бы базисным, содержащим число 1 в ведущей (третьей) строке.

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

0	1	1		1	0	0	8
0	- 2	3		0	1	0	9		(7)
0	1			0	0		5
1	- 4	- 3		0	0	0	- 1

В таблице (7) мы не заполняем столбец , поскольку он нужен, только для того, чтобы определить ведущую строку, что мы уже сделали. Мы выделили только ключевой элемент, так как он определяет одновременно и ведущую строку (третью) и ведущий столбец (первый).

Проделаем теперь следующие преобразования Гаусса:

1. вычтем из первой строки ведущую (третью) строку;

2. прибавим ко второй строке ведущую, умноженную на 2;

3. прибавим к индексной строке ведущую, умноженную на 4.

В итоге получим новую таблицу:

0	0			1	0		3
0	0	2		0	1	1	19		(8)
0	1			0	0		5
1	0	- 5		0	0	2	19

Нетрудно видеть, что мы получили симплекс-таблицу. Действительно, в таблице (8) после перестановки столбца со столбцом в последних трех столбцах получается единичная матрица; столбец свободных членов неотрицателен; целевая функция зависит только от свободных переменных и

Отметим, что столбец , став базисным, вытеснил «из базиса» столбец . В силу этого обстоятельства проделанный процесс называют операцией однократного замещения. В данном случае эта операция состояла из последовательности элементарных преобразований Гаусса 1), 2) и 3).

Таким образом, получена вторая симплекс-таблица (8), которой соответствует второе опорное решение. Переменные и - свободные и, следовательно, и . Поскольку первое уравнение имеет вид.

то значение базисной переменной равно 3: . Базисная переменная определяется вторым уравнением:

а базисная переменная определяется третьим уравнением (так как в столбце единица стоит в третьей строке):

Итак, , - второе опорное решение. Новое значение целевой функции определяется индексной строкой:

Это опорное решение также не является оптимальным, что следует из того, что в индексной строке таблицы (8) имеется отрицательный элемент (-5) во втором столбце, который мы выберем теперь в качестве ведущего столбца. Затем найдем ведущую строку с минимальным допустимым отношением и ключевой элемент:

0	0		1	0		3	2
0	0	2	0	1	1	19	9,5	(9)
0	1		0	0		5
1	0	- 5	0	0	2	19

Разделим ведущую строку (первую) на ключевой элемент :

0	0	1			0		2
0	0	2		0	1	1	19	(10)
0	1			0	0		5
1	0	- 5		0	0	2	19

Выполним теперь следующие преобразования Гаусса:

1. вычтем из второй строки первую, умноженную на 2;

2. прибавим к третьей строке первую, умноженную на ;

3. прибавим к индексной строке первую, умноженную на 5. В результате получим третью симплекс-таблицу:

0	0	1			0		2
0	0	0			1		15	(11)
0	1	0			0		6
1	0	0			0		29

Ей соответствует третье опорное решение:

- и значение целевой функции .

Поскольку индексная строка таблицы (11) не содержит отрицательных элементов, полученное опорное решение будет оптимальным: и (12) При этом Здесь мы звездочками помечаем оптимальные значения переменных.

Таким образом, задача (2), а с ней и задача (1) решены.

Решение транспортной задачи методом потенциалов

Пример.

bj ai	150	130	150	140
200	7	8	1	2
180	4	5	9	8
190	9	2	3	6

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

Подсчитаем суммарные запасы груза и суммарные потребности заказчиков ,

.

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

2. Построим первый опорный план транспортной задачи методом северо-западного угла.

Начинаем заполнение распределительной таблицы с верхней левой клетки, то есть построение исходного опорного плана начинаем с удовлетворения потребностей первого потребителя b₁ за счет запасов первого поставщика a₁. Для этого сравниваем запас a₁ = 200 с потребностями b₁ = 150. Так как a₁ > b₁, то потребности b₁ полностью удовлетворяем за счет a₁, и в первую клетку помещаем min (200, 150)=150. У первого поставщика осталось 50 единиц груза. Так как потребности первого получателя груза полностью удовлетворены, исключим из рассмотрения первый столбец, заполнив в нем оставшиеся клетки точками. Далее заполняем таблицу по строкам слева направо и сверху вниз. Следующая самая верхняя левая незаполненная клетка – (1,2). Потребителю b₂ поставляем 50 единиц груза, оставшихся у первого поставщика. Поскольку от первого поставщика весь груз вывезен, заполняем оставшиеся клетки первой строки точками. Второму получателю, пока что, недопоставлено 80 единиц груза. Следующая незаполненная клетка – (2,2). Потребителю b₂ отправляем недостающие 80 единиц груза, при этом его потребности полностью удовлетворены, поэтому оставшиеся клетки во втором столбце заполняем точками. У второго поставщика a₂ осталось еще 100 единиц груза. Аналогичным образом заполняем оставшиеся клетки, пока не удовлетворим всех потребителей и не вывезем все запасы груза у поставщиков.

bj ai	150	130	150	140
200	7 150	8 50	1 *	2 *
180	4 *	5 80	9 100	8 *
190	9 *	2 *	3 50	6 140

В результате распределения груза получим первый опорный план, в котором x₁₁ = 150, x₁₂ = 50, x₂₂ = 80, x₂₃ = 100, x₃₃ = 50, x₃₄ = 140. Эти переменные соответствуют заполненным клеткам и являются базисными, остальные переменные, соответствующие клеткам с точками, являются свободными (значения свободных переменных равны нулю). Первый опорный план можно представить в матричном виде

Число заполненных клеток k = 6. Это число должно равняться рангу системы ограничений r = m + n – 1 = 3 + 4 – 1 = 6. Так как k = r = 6, то построенный план является невырожденным. Подсчитаем затраты на перевозку по этому плану

.

3. Построим первое опорное решение транспортной задачи методом минимальной стоимости (минимального тарифа).

bj ai	150	130	150	140
200	7 *	8 *	1 150	2 50
180	4 150	5 *	9 *	8 30
190	9 *	2 130	3 *	6 60

Найдем клетку с минимальным тарифом. Это клетка (1,3) с тарифом

c₁₃ =1. Построение исходного опорного плана начинаем с занесения поставки груза в клетку с наименьшей стоимостью c₁₃. Заполняем клетку x₁₃ = 150. Оставшиеся клетки третьего столбца заполняем точками, так как потребности третьего получателя полностью удовлетворены. У первого поставщика осталось 50 единиц груза. Ищем следующую клетку с минимальным тарифом. Таких клеток две: c₁₄ =2, c₃₂ =2. Заполним сначала клетку (3,2). Поставим в нее x₃₂=min (190, 130)=130. Второй столбец заполняем точками. У третьего поставщика осталось 60 единиц груза. Ищем следующую клетку с наименьшим тарифом – это клетка (1,4). В нее помещаем 50 единиц груза, min(50,140)=50. Первую строку заполняем точками, так как от первого поставщика вывезен весь груз. Четвертому получателю недопоставлено 90 единиц. Аналогичным образом распределяем весь имеющийся груз и получаем первый опорный план перевозок.

Подсчитаем затраты на перевозку по этому плану.

.

Итак, в каждой строке и в каждом столбце таблицы заполнена хотя бы одна клетка, циклов по заполненным клеткам нет, число заполненных клеток m+n-1=6, следовательно, план опорный и невырожденный.

4. Проверка первого опорного плана (решения) на оптимальность. Метод потенциалов

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

В таблице в дополнительном столбце справа помещаем потенциалы отправителей , а в строке снизу – потенциалы получателей. Составим систему уравнений для определения потенциалов:

Из этой системы находим

bj ai	150	130	150	140
200	7 *	8 *	1 150	2 50	=2
180	4 150	5 *	9 *	8 30	=8
190	9 *	2 130	3 *	6 60	=6

Считаем оценки для свободных клеток:

Запишем получившиеся оценки в левом верхнем углу свободных клеток.

bj ai	150	130	150	140
200	9>0 7 *	10>0 8 *	1 150	2 50	=2
180	4 150	1>0 5 *	2>0 9 *	8 30	=8
190	7>0 9 *	2 130	-2<0 3 *	6 60	=6

Так как среди оценок имеются отрицательные , то данный план не является оптимальным. Его можно улучшить перераспределением поставок. Для этого выбираем свободную клетку с наименьшим отрицательным значением (наибольшим по абсолютной величине). В данном случае это клетка (3,3).

bj ai	150	130	150	140
200	7 *	8 *	1 150--	2 50+	=2
180	4 150	5 *	9 *	8 30	=8
190	9 *	2 130	3 * +	6 60--	=6

Сроим цикл пересчета, начиная с клетки (3,3), в которую нужно поместить поставку груза (её отмечают знаком «+»), и двигаясь по занятым клеткам (в данном случае это клетки (3,4), (1,4), (1,3)), поочередно отмечая их знаками «-», «+». Если в клетку (3,3) добавили + , то в смежных по циклу клетках необходимо вычесть для сохранения баланса перевозок по третьей строке и третьему столбцу. Звенья цикла должны быть параллельны строкам или столбцам таблицы, причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, а другое – в столбце. Количество вершин в цикле должно быть четно. В результате построения цикла в соответствующих строках и столбцах должно быть парное количество знаков «-», «+».

Определяем величину поставки в клетку (3,3), как минимальную величину из поставок, стоящих в отрицательных клетках, то есть . Перераспределяем по циклу поставки на величину . Значение записываем в незанятую клетку (3,3), отмеченную знаком «+», двигаясь по циклу, прибавляем эту величину к поставкам в клетках со знаком «+», вычитаем в клетках со знаком «-».

В результате получаем новое опорное решение или новый опорный план, в котором клетки с грузом, равным величине , становятся свободными.

bj ai	150	130	150	140
200	7 *	8 *	1 90	2 110
180	4 150	5 *	9 *	8 30
190	9 *	2 130	3 60	6 *

Если освобождается больше одной клетки, то есть число заполненных клеток меньше числа m + n - 1, то такой план называется вырожденными, и для определения потенциалов необходимо ввести недостающее количество нулевых элементов в число основных базисных переменных. Свободные клетки заполняют нулевыми поставками так, чтобы они не образовывали цикл по заполненным клеткам, и чтобы в каждой строке и в каждом столбце находилась хотя бы одна заполненная клетка. Проверим новый опорный план на оптимальность. Пусть =0. Тогда найдем все остальные потенциалы, рассматривая только заполненные клетки и помня, что для них , то есть что сумма потенциалов должна быть равна тарифу, стоящему на пересечении соответствующих потенциалам строки и столбца.

bj ai	150	130	150	140
200	7 *	8 *	1 90	2 110	=0
180	4 150	5 *	9 *	8 30	=6
190	9 *	2 130	3 60	6 *	=2

Число заполненных клеток k=m+n-1, следовательно, план невырожденный. Найдем оценки для всех клеток с точками, где стоят свободные переменные. Данный опорный план не является оптимальным, так как не все оценки для свободных клеток , а именно, .

bj ai	150	130	150	140
200	9>0 7 *	8>0 8 *	1 90	2 110	=0
180	4 150	-1<0 5 *	2>0 9 *	8 30	=6
190	9>0 9 *	2 130	3 60	2>0 6 *	=2

Возьмем клетку (2,2) за начало цикла пересчета. Цикл будет проходить по клеткам (2,2), (3,2), (3,3), (1,3), (1,4), (2,4) и опять вернется в (2,2).

bj ai	150	130	150	140
200	9>0 7 *	8>0 8 *	1 90-	2 110++	=0
180	4 150	-1<0 5 * +	2>0 9 *	8 30-	=6
190	9>0 9 *	2 1 30-	3 60+	2>0 6 *	=2

Ищем количество единиц груза , перераспределяемых по циклу пересчета, как минимум по клеткам, помеченных знаком минус. Получаем новый опорный план

bj ai	150	130	150	140
200	7 *	8 *	1 60	2 140
180	4 150	5 30	9 *	8 *
190	9 *	2 100	3 90	6 *

Проверяем данный опорный план на оптимальность

bj ai	150	130	150	140
200	8>0 7 *	8>0 8 *	1 60	2 140	=0
180	4 150	5 30	3>0 9 *	1>0 8 *	=5
190	8>0 9 *	2 100	3 90	2>0 6 *	=2

Полученный опорный план является оптимальным, так как все оценки для свободных клеток . Выписываем оптимальный план: x₁₁ = 0; x₁₂ = 0; x₁₃ = 60; x₁₄ =140; x₂₁ = 150; x₂₂ = 30; x₂₃ = 0; x₂₄ = 0; x₃₁ = 0; x₃₂ = 100; x₃₃ = 90; x₃₄ = 0. Или в матричной форме

Высчитываем минимальные затраты на транспортировку продукции: