4. Двойственные задачи линейного программирования.

ПРЯМАЯ	ДВОЙСТВЕННАЯ
Система ограничений: Ах=B xi ≥0 Целевая функция: L=Cx → max	Система ограничений: ATu=CT ui ≥0 Целевая функция: L=BTu → min

5. Транспортная задача.

Существуют частные типы задач линейного программирования, которые в силу особой своей структуры, допускают решение более простыми методами. Например, транспортная задача. Она ставится следующим образом: имеются n пунктов отправления (ПО) A₁, A₂,… A_n-1, A_n, в которых сосредоточены запасы каких-то однородных грузов в количестве a₁, a₂,… a_n-1, a_n единиц. Имеются m пунктов назначения (ПН) B₁, B₂,… B_n-1, B_n, подавших заявки соответственно на b₁, b₂,… b_n-1, b_n единиц груза. Сумма всех заявок равна сумме всех запасов.

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

Считается, что стоимость перевозки нескольких единиц груза пропорциональна их числу.

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

Обозначим x_ij -количество единиц груза, отправляемого из A_i в B_j Совокупность (x_ij ) будем называть «планом перевозок» или решением, а сами величины «перевозками».

Составим ОЗЛП.

1. Суммарное количество груза, направляемого из каждого ПО во все ПН, должно быть равно запасу груза в данном пункте:

2. Суммарное количество груза, доставляемого в каждый ПН из всех ПО, должно быть равно заявке, поданной данным пунктом:

3. Суммарная стоимость всех перевозок должна быть минимальной:

То, что все коэффициенты в условиях-равенствах равны 1, позволяет решать задачу очень простыми способами.

Число линейно-независимых уравнений = m+n-1, общее число переменных = mn, число базисных переменных = m+n-1, а число свободных k=mn-(m+n-1)=(m-1)(n-1)

Так как оптимальное решение достигается в одной из вершин ОДР, то по крайней мере k перевозок должны быть равны нулю. Допустимый план будем называть опорным, если в нем отличны от нуля не более m+n-1 базисных перевозок.

Представим транспортную задачу в виде некоторой таблицы, называемой транспортной.

	B1	B2	…	Bn
A1	c11	c12	…	c1n	a1
A2	c21	c22	…	c2n	a2
…	…	…	…	…	…
Am	cm1	cm2	…	cmn	am
	b1	b2	…	bn

МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА

Построение начального плана согласно этому методу начинается с верхнего угла транспортной таблицы. Распределение груза первого поставщика происходит таким образом, что сначала максимально удовлетворяются заявки первого потребителя, затем второго и т.д. до полного распределения груза, имеющегося в A₁ Затем подобным же образом распределяется груз второго поставщика и т.д.

ПРИМЕР 2.6.

	B1	B2	B3	B4	ai	остаток
A1	1 3	3 5	7 2	1	10	7 2 0
A2	2	4	2 8	3 7	15	7 0
A3	6	5	4	1 7	7	0
bj	3	5	10	14	32
	0	0	8 0	7 0

Действуя описанным способом, мы получаем ступенчатую фигуру. В процессе решения получили 6 базисных клеток. Так как m+n-1= 3+4-1=6, то план невырожденный. Его можно принять за опорный.

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

МЕТОД МИНИМАЛЬНОГО ЭЛЕМЕНТА.

Распределение груза в этом методе начинается с одной из вершин минимальной стоимости. Также при каждом распределении необходимо максимально удовлетворить заявки выбранного потребителя. Очередное распределение выбирается из условия минимальной стоимости перевозок.

ПРИМЕР 2.7.

	B1	B2	B3	B4	ai	остаток
A1	1	3	7	1 10	10	0
A2	2 3	4 5	2 7	3	15	8 5 0
A3	6	5	4 3	1 4	7	3 0
bj	3	5	10	14	32
остаток	0	0	7 0	4 0

Чтобы улучшить решение, следует перейти к другому плану. Самый простой способ – метод Жордана-Гаусса. Он заключается в целенаправленном переборе планов. Какую клетку выбрать, чтобы переход к новому решению привел к уменьшению значения целевой функции?

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

ПРИМЕР 2.6.

Выберем в рассмотренном выше примере свободную клетку (3,2). Определим замкнутый цикл, последовательно расставляя знаки «+» и «-».

	B1	B2	B3	B4	ai
A1	1 3	3 - 5	7 + 2	1	10
A2	2	4	2 - 8	3 + 7	15
A3	6	5 +	4	1 - 7	7
bj	3	5	10	14	32

Минимумом в отрицательных вершинах является число 5. Его и занесем в клетку (3,2). Далее пройдем по всему циклу, меняя значения перевозок. Получим новый базисный план:

	B1	B2	B3	B4	ai
A1	1 3	3	7 7	1	10
A2	2	4	2 3	3 12	15
A3	6	5 5	4	1 2	7
bj	3	5	10	14	32

Ценой цикла будем считать разность между суммой стоимостей перевозок в положительных вершинах цикла и суммой перевозок в отрицательных вершинах. Если цена цикла < 0, то выгодно перебросить перевозки по этому циклу. Суммарные перевозки при этом не изменятся. Цена цикла говорит, на сколько изменится суммарная стоимость перевозок при переброске по циклу 1 единицы груза. Например, в рассмотренном примере цена цикла d₃₂=7+3+5-(1+2+3)=9>0. Следовательно, переброска 1 единицы груза по этому циклу приводит к увеличению суммарной стоимости перевозок на 9. В примере по циклу было переброшено 5 единиц, следовательно, затраты на перевозки увеличились на 45.

МЕТОД ЖОРДАНА-ГАУССА.

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

	B1	B2	B3	B4
A1	1 3	3 5	- 7 2	+ 1
A2	2	4	2 8 +	3 7 -
A3	6	5	4	1 7

d₂₁=2-1+7-2=6>0

d₃₁=6-1+7-2+3-1=12>0

d₂₂=4-3+7-2=4>0

d₃₂=9>0

d₃₃=4-2+3-1=4>0

d₁₄=1-3+2-7=- 4<0

Следовательно, выгодным является только цикл клетки (1,4). По нему можно перебросить min(2,7) =2 единицы груза. Получим следующий план.

	B1	B2	B3	B4
A1	1 3 -	3 5	7	1 2 +
A2	+ 2	4	2 10	3 5 -
A3	6	5	4	1 7

d₂₁=2-1+1-3=-1<0

d₂₂=4-3+1-3=-1<0

Для всех остальных циклов цена >0

Выберем клетку (2,1)

min(3,5) =3

	B1	B2	B3	B4
A1	1	3 5	7	1 5
A2	2 3	4	2 10	3 2
A3	6	5	4	1 7

d₂₂=4-3+1-3=-1<0

Для всех остальных циклов цена >0

min(2,5) =2

	B1	B2	B3	B4
A1	1	3 3	7	1 7
A2	2 3	4 2	2 10	3
A3	6	5	4	1 7

Для всех циклов цена >0, следовательно план оптимальный

Ответ: x₁₂=3; x₁₄=7; x₂₁=3; x₂₃=10; x₂₂=2; x₃₄=7; L=3∙3+7∙1+3∙2+10∙2+2∙4+7∙1=57

МЕТОД ПОТЕНЦИАЛОВ.

Обозначим переменные задачи, двойственной к транспортной через -u_i и v_j Их называют потенциалами пунктов отправления и пунктов назначения соответственно.

Двойственная задача заключается в нахождении потенциалов u_i и v_j, удовлетворяющих ограничениям v_j - u_i ≤ с _ij и максимизирующих функцию цели

КРИТЕРИЙ ОПТИМАЛЬНОСТИ. Для того чтобы план перевозок в транспортной задаче был оптимален, необходимо и достаточно, чтобы нашлись потенциалы u_i (пункта отправления) и v_j (пункта назначения) такие, что:

v_j - u_i = с _ij , если х_ij>0

v_j - u_i ≤ с _ij , если х_ij=0

ЭКОНОМИЧЕСКИЙ СМЫСЛ: v_j можно рассматривать как цену груза в ПН, u_i – цену груза в ПО. Тогда оптимальным будет план, в котором перевозки осуществляются по путям, где разность цен равна цене перевозки единицы груза.

Алгоритм.

1. Выберем любой базисный план.

2. Составим систему уравнений v_j - u_i = с _ij для базисных переменных

3. Так как система содержит m+n-1 уравнение и m+n неизвестных, то одну из них можно задать произвольно (например, =0). После этого определим остальные потенциалы.

4. Для каждой из свободных клеток вычислим величины a_ij=v_j-u_i

5. Если все a_ij≤ с_ij то план оптимален. Задача решена.

6. В противном случае рассмотрим все клетки, для которых a_ij> с_ij. Выберем свободную клетку, для которой реализуется max(a_ij-c_ij), введем ее в базис, образуем цикл и построим новое базисное решение. Переходим к п.2

ПРИМЕР 2.7.

	B1	B2	B3	B4
A1	1 3	3 5	7 2	1
A2	2	4	2 8	3 7
A3	6	5	4	1 7

Составим разность потенциалов для базисных клеток:

v₁-u₁=1

v₂-u₁=3

v₃-u₁=7

v₃-u₂=2

v₄-u₂=3

v₄-u₃=1

Положим u₁=0 и найдем остальные потенциалы

	B1	B2	B3	B4	ui
A1	1 3	3 5	7 2	8) 1	0
A2	-4) 2	-2) 4	2 8	3 7	5
A3	-6) 6	-4) 5	0 4	1 7	7
vj	1	3	7	8

a₁₄> с₁₄, следовательно построим цикл для клетки (1,4) и перебросим по нему максимально возможные перевозки.

	B1	B2	B3	B4	ui
A1	1 3 -	3 5	0) 7	1 2 +	0
A2	3) + 2	5) 4	2 10	3 5 -	-2
A3	1) 6	3) 5	0) 4	1 7	0
vj	1	3	0	1

a₂₁> с₂₁

a₂₂> с₂₂

Выберем клетку (2,1)

min(3,5) =3

	B1	B2	B3	B4	ui
A1	0) 1	3 5	0) 7	1 5	0
A2	2 3	5) 4	2 10	3 2	-2
A3	0) 6	3) 5	0) 4	1 7	0
vj	0	3	0	1

a₂₂> с₂₂

min(2,5) =2

	B1	B2	B3	B4	ui
A1	1) 1	3 3	1) 7	1 7	0
A2	2 3	4 2	2 10	2) 3	-1
A3	1) 6	3) 5	1) 4	1 7	0
vj	1	3	1	1

Для всех клеток a_ij≤ с_ij , следовательно план оптимальный

Ответ: x₁₂=3; x₁₄=7; x₂₁=3; x₂₃=10; x₂₂=2; x₃₄=7; L=3∙3+7∙1+3∙2+10∙2+2∙4+7∙1=57

ПРИМЕЧАНИЕ. Если условие равенства запасов груза в ПО и суммарной потребности в грузе ПН нарушено, то

1. если всех заявок удовлетворить нельзя, то вводится фиктивный ПО А_m+1, стоимости перевозок из которого равны 0;

2. если существует избыток груза, то вводится фиктивный ПН B_n+1, стоимости перевозок в который равны 0.