IV. Двойственность в линейном программировании.

ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД

 

Рассмотрим задачу линейного программирования в общей форме:

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

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

y ₁³0 a₁₁ x₁ + a₁₂ x₂ +...+ a_1n x_n £ b₁

y ₂³0 a₂₁ x₁ + a₂₂ x₂ +...+ a_2n x_n £ b₂

....................................... (2)

y _k³0 a_k1 x₁ + a_k2 x₂ +...+ a_kn x_n £ b_k

y _k+1 a_{k+1 1} x₁ + a_{k+1 2} x₂ +...+ a_{k+1 n} x_n = b_k+1

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

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

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

Каждому i -му ограничению из (2) соответствует переменная y _i так назы­ваемой двойственной задачи к задаче (1) – (3) (показана слева от соответст­вующего ограничения).

Двойственная задача имеет вид:

W = b₁ y₁ + b₂ y₂ +...+ b_m x_m ® min (4)

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

x₁ ³ 0 a₁₁ y₁ + a₂₁ y₂ +...+ a_m1 y_m ³ c₁

x₂ ³ 0 a₁₂ y₁ + a₂₂ y₂ +...+ a_m2 y_m ³ c₂

....................................... (5 )

x_l ³ 0 a_1l y₁ + a_2l y₂ +...+ a_ml y_m ³ c_l

x_l+1 a_{1 l+1} y₁ + a_{2 l+1} y₂ +...+ a _{m l+1} y_m = c_l+1

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

x_n a_1n y₁ + a_2n y₂ +...+ a_mn y_m = c_n,

y_i ³ 0, i = 1,..., k; k £ n (6)

Задачи (1) – (3) и (4) – (6) образуют пару задач, называемую в линейном программировании двойственнойпарой.

Сравнивая две задачи, видим, что двойственная задача по отношению к исходной (прямой) содержит те же самые коэффициенты a_ij, b_i, c_j и состав­ляется согласно следующим правилам:

1. Целевая функция (1) исходной задачи задается на максимум, а целевая функция (4) двойственной задачи – на минимум.

2. Матрица А^Т, составленная из коэффициентов при неизвестных в системе ограничений (5) двойственной задачи получается из матрицы А прямой задачи транспонированием (т.е. заменой строк столбцами):

а₁₁ а₁₂... а_1n a₁₁ a₂₁... a_m1

A = а₂₁ а₂₂... а_2n A^T = a₁₂ a₂₂... a_m2

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

а_m1 а_m2... а_mn a_1n a_2n... a_mn

 

3. Число переменных в двойственной задаче (4)–(6) равно числу ограниче­ний в системе (2) прямой задачи, а число ограничений в системе (5) двойствен­ной задачи равно числу переменных в прямой задаче.

4. Коэффициентами при неизвестных в целевой функции (4) двойственной задачи являются свободные члены в системе (2) прямой задачи и наоборот.

5. Если переменная x_j ³ 0, то j- ое ограничение в системе (5) двойственной задачи является неравенством “ ³ ”. Если же переменная x_j может иметь любой знак, то j -ое ограничение в системе (5) представляет собой уравнение.

Каждая из задач двойственной пары (1) – (3) и (4) – (6) фактически яв­ляется самостоятельной задачей линейного программирования и может быть решена независимо одна от другой. Однако при определении симплексным методом оптимального плана одной из задач, тем самым находится решение и другой задачи. Существующие зависимости между решениями прямой и двойственной задач характеризуются сформулированными ниже теоремами двойственности.

Теорема 1. (Основная теорема двойственности). Если одна из пары двойственных задач имеет оптимальный план, то и другая имеет оптимальный план причем значения целевых функций задач при их оптимальных планах сов­падают, т.е. Z_max = W_min.

Если же целевая функция одной из задач не ограничена (для исходной (1) – (3) – сверху, для двойственной (4) – (6) – снизу), то другая задача вообще не имеет допустимых решений.

Теорема 2. (Вторая теорема двойственности). Для того, чтобы два до­пустимых решения и пары двойствен­ных задач были их оптимальными решениями, необходимо и достаточно, чтобы они удовлетворяли системам уравнений:

(7)

Замечание. Соотношения (7) верны только для ограничений в виде неравенств и для неотрицательных переменных.

 

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

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

 

(8)

(9)

(10)

 

Пусть матрица ограничений А содержит единичную подматрицу порядка m и первые m переменных являются базисными. Среди чисел есть отрицательные. Вектор есть решение системы (9). Однако, это решение не является планом задачи (8) – (10), поскольку среди его компонент есть отрицательные числе (т.е. не выполняются ограничения (10)). Исключим базисные переменные из целевой функции z:

.

Предположим, что

Шаг 1. Составить исходную симплексную таблицу.

 

№ строки	Базис	x1	…	xm	xm+1	…	xk	…	xn	b
1 l m	x1 xl xm	1 0 0	… … …	0 0 1	a1m+1 alm+1 amm+1	… … …	ak a^*lk amk	… … …	a1n aln amn	b1 bl bm
m+1	-z	0	…	0	dm+1	…	dk	…	dn	-do

 

Шаг 2. Выяснить, имеется ли хотя бы одно отрицательное число среди элементов столбца b. Если нет, то перейти к шагу 8. Иначе – к шагу 3.

Шаг 3. Если отрицательных чисел в столбце b несколько, то выбрать наименьшее. Пусть, для определенности, это число . Строка с номером l – ведущая.

Шаг 4. Среди элементов ведущей строки l находят отрицатель­ные. Если таковых нет, то исходная задача не имеет решения. В противном случае перейти к шагу 5.

Шаг 5. Вычислить . Столбец с номером k – ведущий, - ведущий элемент.

Шаг 6. С помощью ведущего элемента провести одну итерацию метода Жордана-Гаусса.

Шаг 7. Построить новую симплексную таблицу и перейти к шагу 2.

Шаг 8. Задача линейного программирования (8) – (10) решена. По последней симплексной таблице выписать оптимальный план и минимальное значение целевой функции задачи (8) – (10).

Замечание. Если среди чисел есть отрицательные, то следует в системе ограничений (9) преобразовать свободные члены b_j в неотрица­тельные, умножив на (-1) строки, содержащие отрицательные свободные члены и решать задачу (8) – (10) методом искусствен­ного базиса.

 

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

Z = 6x₁ + 9x₂ + 3x₃ ® min

-x₁ + 2x₂ + x₃ ³ 2

3x₁ + x₂ – x₃ ³ 1 (11)

x_j ³ 0, j = 1, 2, 3.

 

Решение. Составим для задачи (11) двойственную:

W = 2y₁ + y₂ ® max

-y₁ + 3y₂ £ 6

2y₁ + y₂ £ 9 (12)

y₁ - y₂ £ 3

y₁, y₂ ³ 0

Для решения задачи (11) двойственным симплекс-методом приведем ее к каноническому виду. Для этого умножим первое и второе ограничения на (-1) и добавим соответствен­но неотрицательные дополнительные переменные x ₄ ³ 0, x₅ ³ 0:

Z = 6x₁ + 9x₂ + 3x₃ ® min

x₁ - 2x₂ - x₃ + x₄ = -2

-3x₁ - x₂ + x₃ + x₅ = -1 (13)

x_j ³ 0, j = 1, 2,..., 5.

Базисными переменными здесь являются переменные х ₄ и х ₅. Поскольку все коэффициенты с _j ³ 0, то критерий оптимальности для этого базисного ре­шения выполнен, однако само решение Х = (0, 0, 0, -2, -1) содержит отрица­тельные переменные, то есть не является допустимым. Естественно попытаться вывести отрицательные (не являющиеся допустимыми) переменные из базиса, сохранив при этом неотрицательность коэффициентов последней строки, так как в этом случае полученное допустимое решение будет являться и оптималь­ным. Такой подход является содержанием двойственного симплекс-метода. Проиллюстрируем его на примере решения задачи (13).

Составим исходную симплекс-таблицу.

 

Базис	х1 х2 х3 х4 х5	Значение (bi)
x 4 x 5	1 -2 -1^*1 0 -3 -1 1 0 1	-2 -1
- Z	6 9 3 0 0

 

Вычисляем Из базиса будем выводить пе­ременную x₄. Следовательно, первая строка таблицы является разрешающей. Среди элементов разрешающей строки находим отрицательные а ₁₂ = -2; a ₁₃ = -1.

Определяем Столбец, в кото­ром достигается этот минимум, соответствует переменной х ₃. Этот столбец является разрешающим и разрешающим элементом является элемент а ₁₃ = -1. Это делается для того, чтобы элементы последней строки остались неотрицательными. Проводим одну итерацию метода Жордана-Гаусса относи­тельно этого элемента, т.е. из базиса исключаем переменную х ₄ и включаем в базис переменную х ₃. Новая симплекс-таблица имеет вид:

 

Базис	х1 х2 х3 х4 х5	Значение (bi)
х 3 x 5	-1 2 1 -10 -2 -3^* 0 1 1	-3
- Z	9 3 0 3 0	-6

 

Элемент b ₂ = -3 < 0. Следовательно, разрешающей является вторая строка таблицы. Как и ранее, находим

Следовательно второй столбец – разрешающий, переменную х ₂ включаем в базис, переменную х ₅ исключаем из базиса. Пересчитывая таблицу относи­тельно элемента а ₂₂ = -3, получаем новую таблицу:

 

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

 

Среди элементов столбца “Значение” нет отрицательных чисел. В Z – строке также нет отрицательных чисел. Следовательно, найден оптимальный план: Х ^* = (0; 1; 0), при этом Z^* = Z_min = 9. По последней симплекс-таблице находим решение двойственной задачи (9). Для этого выясняем, какие перемен­ные задачи (10) входили в исходный базис. В первоначальной таблице это – х ₄, х ₅. В последней симплекс-таблице находим элементы Z – строки, соответст­вующие этим базисным переменным (с ₄ = 4, с ₅ = 1) и прибавляем к ним соот­ветствующие коэффициенты исходной целевой функции (с ₄ = с ₅ = 0). В ре­зультате получаем Y ^* = (4; 1), W ^* = W _max = 9.

 

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

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

Варианты

 

1. 2.

3.	4.
5.	6.
7.	8.
9.	10.

 

V. ТРАНСПОРТНАЯ ЗАДАЧА

 

Общая постановка транспортной задачи состоит в определении оптималь­ного плана перевозок некоторого однородного груза из m пунктов отправления А ₁, А ₂,..., А _m в n пунктов назначения B₁, B ₂,..., B _n. При этом в качестве критерия оптимальности берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки.

Математическая модель транспортной задачи имеет вид: , (14)

(15)

(16)

(17)

 

Здесь c _ij - тарифы перевозки единицы груза из i – го пункта отправления А _i в j – ый пункт назначения B _j, b_j - потребность в грузе в j – ом пункте на­значения, a_i – запасы груза в i – ом пункте отправления.

Наличие линейных уравнений (15) и (16) обеспечивает доставку необхо­димого количества груза в каждый из пунктов назначения и вывоз всего имею­щегося груза из всех пунктов отправления. При этом, ввиду (17), исключаются обратные перевозки. Задача (14) – (17) является частным случаем задачи линей­ного программирования, однако, в силу своей специфики решается специаль­ным методом.

Если выполняется так называемое условие баланса

, (18)

то такая транспортная задача называется закрытой. Если условие баланса (18) не выполняется, то задача называется открытой.

Теорема 1. Для разрешимости транспортной задачи необходимо и доста­точно, чтобы выполнялось условие баланса (5).

Если то вводится фиктивный (n + 1) - ый пункт назначения с потребностью и соответствующие тарифы полагают рав­ными нулю, т.е. c _{i n+1} = 0 (i = 1,2,..., m). Аналогично, при вводится фиктивный, (m+1) – ый пункт отправления с запасами груза , при этом тарифы на перевозку из этого пункта также полагают равными нулю, c _{m+1 j} = 0.

Для решения задачи (14) – (17) применяется метод потенциалов, который по существу, является другой формой симплекс-метода.

Опишем алгоритм метода. Исходные данные транспортной задачи запишем в таблице

bj ai	b 1	b 2	...	b n
a 1	c 11	c 12	...	c 1n
a 2	c 21	c 22	...	c 2n
	...	...	...	...
a m	c m1	c m2	...	c mn

 

1. Построение начального опорного плана. Система ограничений (16)-(17) содержит m×n неизвестных и m+ n уравнений, связанных отношением (18). Невырожденный опорный план задачи содержит m + n – 1 положительных пе­ревозок или компонент. Таким образом, если каким-либо способом получен не­вырожденный опорный план задачи, то в матрице (x_ij) значений его компонент положительными являются только m + n – 1, а остальные равны нулю.

Клетки, в которых находятся отличные от нуля перевозки, называются за­нятыми, остальные – незанятыми. Занятые клетки соответствуют базисным не­известным, и для невырожденного опорного плана их количество равно m + n-1.

Для построения начального опорного плана применим метод минималь­ной стоимости.

Выбираем клетку с минимальной стоимостью (если их несколько, возь­мем любую из них). Пусть, например, . Тогда в клетку (l, k) записы­вают число . При этом, если , то значение b_k уменьшают на a_l и «закрывают» строку с номером l, так как ресурсы l -го поставщика исчерпаны. Если , то значение a_l уменьшают на b_k и «закрывают» столбец с номером k, что означает удовлетворение спроса k- го потребителя. Если же a_l = b_k, то «закрывают» строку или столбец по выбору.

Вышеописанную процедуру повторяют для оставшейся транспортной таблицы до тех пор, пока не будут закрыты все строки и столбцы.

2. Построение системы потенциалов. Система потенциалов строится для невырожденного опорного плана и имеет вид:

где - стоимость перевозки единицы груза занятой (базисной) клетки в i – ой строке и j -ом столбце.

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

3. Проверка опорного плана на оптимальность. Для каждой свободной клетки вычисляют оценки

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

4. Построение цикла и нахождение нового опорного плана. Среди отрица­тельных оценок выбираем наименьшую. Пусть

В клетке (l, k) нарушено условие оптимальности. Для улучшения опорно­го плана необходимо в клетку (l, k) отправить некоторое количество груза, превратив ее тем самым в базисную. Эта операция эквивалентна действию по замене базиса в симплекс-методе.

Клетку (l, k) отмечают знаком «+» и затем строят цикл, расставляя пооче­редно знаки «-» и «+» в базисных клетках так, чтобы в строках и столбцах стоя­ло по одному знаку «+» иди «-». Цикл строится единственным образом.

Обозначим , где - перевозки, стоящие в вершинах цикла, от­меченных знаком «-». Величина l определяет количество груза, которое можно перераспределить по найденному циклу. Значение l записывают в незанятую клетку (l, k). Двигаясь по циклу, вычитают или прибавляют l к объемам перевозок, расположенных в клетках, помеченными знаками «-» или «+» соответственно. Перевозки в остальных базисных клетках остаются без изменения. Переходим к построению системы потенциалов.

Замечание. Если условие баланса нарушено, т.е. , то вводят фиктивного поставщика или потребителя с поставкой или потребностями соответственно. Стоимости соответствую­щих перевозок полагаются равными нулю. При построении начального опорного плана в этом случае фиктивные клетки заполняются в последнюю очередь.

Пример. Компания контролирует 3 фабрики, производительность кото­рых в неделю (в тыс. изделий) задается вектором . Компания за­ключила договоры с четырьмя заказчиками, еженедельные потребности кото­рых (в тыс.изделий) задаются вектором Стоимость транс­портировки 1 тыс. изделий с i -ой фабрики j- му заказчику задается матрицей тарифов .

Требуется определить оптимальный план перевозок с целью минимиза­ции суммарных затрат на транспортировку.

Так как , то введем в рассмотрение фиктивного 5-го заказчика с потребностью в b ₅ = 100 – 90 = 10 (тыс. ед.) груза. При этом положим c _i5 = 0, i = 1, 2, 3. Исходные данные запишем в виде таблицы.

 

Таблица 1.

bj ai	20	15	25	30	10
30	+		-
25
45	-		+

 

Построим начальный опорный план методом минимального элемента. Первой заполним клетку (1, 3) т. к. тариф этой клетки с ₁₃ = 2 меньше других та­рифов (фиктивный столбец заполняется в последнюю очередь). Поставка для клетки (1, 3) будет равна х ₁₃ = min( 30, 25) = 25. Записываем это число в верх­ний левый угол клетки. Это означает, что с первой фабрики третьему заказчику планируется поставить 25 тыс. ед. груза. При этом требования 3-го заказчика будут полностью удовлетворены и мы закрываем 3-й столбец. Затем в остав­шейся части таблицы (без 3-го столбца) ищем клетку с минимальным тарифом. Таких клеток две (1, 1) и (2, 4). Заполняем любую из них, например, клетку (1, 1). Остаток продукции 1-ой фабрики равен 30 – 25 = 5. Поэтому записать в клетку (1, 1) можно x ₁₁ = min(5, 20) = 5. Поскольку с первой фабрики вывезен весь груз (30 тыс. ед.), то закрываем первую строку. Далее поступаем аналогич­но, заполняя свободные клетки в порядке возрастания тарифов, закрывая каждый раз нужные строку или столбец. В результате начальный план имеет вид (см. табл.1):

Проверим этот план на оптимальность. Для этого найдем потенциалы u _i и v _j поставщиков и потребителей. Для этого по занятым клеткам составим систе­му уравнений вида u _i + v _j = c _ij:

u 1 + v 1 = 3 u 1 + v 3 = 2

u 2 + v 4 = 3

u 3 + v 1 = 8 u 3 + v 2 = 6 u 3 + v 4 = 9 u 3 + v 5 = 0.

Поскольку уравнений в системе столько же, сколько занятых клеток, то есть 7, а неизвестных - 8, то система имеет бесконечное множество решений. Положим, например, u ₃ = 0. Тогда остальные потенциалы находятся однознач­но: v ₅ = 0; v ₄ = 9; v ₂ = 6; v ₁ = 8; u ₂ = -6; u ₁ = -5; v ₃ = 7.

Теперь вычисляем оценки s _ij свободных клеток по формуле s _ij = c _ij – (u _i + v _j):

s 12 = 5 – (6-5) = 4 > 0; s 14 = 6 – (-5+9) = 2 > 0; s 15 = 0 – (-5+0) = 5 > 0;

s 21 = 6 – (-6 + 8) = 4 > 0; s 22 = 7 – (-6+6) = 7 > 0; s 23 = 5 – (-6+7) = 4 > 0; s 25 = 0 – (6+0) = 6 > 0;

s 33 = 4 – (0+7) = -3 < 0.

 

Среди оценок есть отрицательная (s ₃₃ = -3 < 0), следовательно план не является оптимальным. Необходимо улучшить план, загружая клетку с отрица­тельной оценкой.

Для этого построим для клетки (3, 3) цикл с вершинами в загруженных клетках (см. табл. 1), расставляя поочередно в вершинах, начиная с клетки (3, 3), знаки «+» и «-». Из поставок в клетках, помеченных знаком «минус», выбираем наименьшую: l = min(15, 25) = 15.

Для получения нового опорного плана изменим поставки в вершинах цикла: к поставкам в клетках, помеченных знаком «+», прибавляем величину l=15, в клетках, помеченных знаком «-», вычитаем эту величину 15. Новый опорный план поместим в таблицу 2.

Таблица 2.

b j ai	20	15	25	30	10	-2     -6
30		1 5		1 8	2 0
25	7 6	7 7	7 5		6 0
45	3 8

5 6 4 9 0

 

Исследование этого плана на оптимальность аналогично предыдущему. Вычисленные значения потенциалов записаны справа и снизу таблицы, а оцен­ки s _ij свободных клеток поместим в левых нижних углах этих клеток. Посколь­ку среди оценок нет отрицательных, то найденный план является оптимальным.

Выписываем матрицу Х^* (без последнего столбца):

Минимальные суммарные затраты по оптимальному плану составляют:

Z_min = 20×3+10×2+25×3+15×6+15×4+15×9 = 430 ден. ед. Из таблицы 2 видно, что избыточная продукция в количестве 10 тыс. изд. остается на третьей фабрике.

 

 

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

Задание 5. Определить оптимальный план перевозок с целью минимизации общих затрат на транспортировку с заданными векторами и и матрицей стоимостей С.

 

Варианты			С