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

Оптимальные значения переменных двойственной задачи

а) Коэффициенты при свободных переменных в строке 0 на последней симплекс-итерации при решении задачи максимизации совпадают с оптималь-ными значениями переменных двойственной задачи.

б) Коэффициент при xj в строке 0 на последней симплекс-итерации представляет собой разностть между левой и правой частями j-го ограничения двойственной задачи, соответствующую оптимальному решению последней.

Рассмотрим в качестве иллюстрации задачу распределения ресурсов.

максимизировать 4x1 +5x2 + 9x3 + 11x4

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

1x1 + 1x2 +1x3 + 1x4 <=15,

7x1 + 5x2 + 3x3 + 2x4 <=120,

3x1 + 5x2 + 10x3 + 15 x4 <=100,

x1>=0, x2>=0, x3>=0, x4>=0.

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

минимизировать 15y1 + 120y2 + 100y3 ( I)

при наличии ограничений:

1y1 + 7y2 + 3y3>=4,

1y1 + 5y2 + 5y3>=5,

1y1 + 3y2 + 10y3>=9, (II)

1y1 + 2y2 + 15y3>=11,

y1>=0, y2>=0, y3>=0.

Рассмотрим коэффициенты при трех свободных переменных в строке 0 на заключительной симплекс- итерации.

1x0 +3/7x2 +11/ 7x4+ 13/7x5 +5/7 x7 =695/7, (0)

1x1 + 5/7x2 - 5/7x4 + 10/7x5 -1/7 x7 = 50/7, (1)

-6/7x2 - 13/7x4 - 61/7x5+ 1x6 + 4/7x7 =325/7, (2)

2/7x2 + 1x3 + 12/7x4 - 3/7x5 + 1/7x7 =55/7. (3)

Согласно утверждению приведенному в пункте а), оптимальными значениями двойственной задачи являются следующие значения:

y1* =13/7, y2*=0, y3*=5/7. (III)

Убедимся, что выполняются ограничения (II):

1*13/7+3*5/7=28/7>=4,

1*13/7+5*5/7=38/7>=5,

1*13/7+10*5/7=63/7>=9, (V)

1*13/7+15*5/7=88/7>=11.

Покажем, что значение целевой функции двойственной задачи совпадает со значением целевой функции исходной задачи.

15*13/7+120*0+100*5/7=625/7.

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

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

Возьмем, например, второе и третье ограничения, для которых находим

38/7-5=3/7,

63/7-9=0 (VI)

т.е. получаем коэффициенты при x1 и x2 в строке 0 заключительной симплекс-итерации, что согласуется с утверждением, сформулированным в пункте б).

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

Продолжение анализа на чувствительность

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

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

Оптимальное значение x0 = (Константы в правых частях ограничений)*(оптимальные значения переменных двойственной задачи)

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

Коэффициенты в соотношениях, задающих ограничения.

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

Рассмотрим в качестве примера задачу распределения ресурсов. Предположим, что вводится дополнительная переменная, причем дополнения к строкам имеют следующий вид:

+1x8 (строка 1),

+2/7 x8 (cтрока 2),

+17x8 (строка 3).

Пусть при переменной x8 в выражении для целевой функции стоит c8. При каком значении c8 целесообразно ввести в базис x8? Cоотношение двойственной задачи имеет вид

1y1+ 2/7y2 + 17y3 >= c8.

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

1*13/7+ 2/7*0 + 17*5/7 >= c8,

или 14>= c8.

Следовательно, при с8>14 переменную c8 нужно включить в базис.

Предположим, что c8 =20. Тогда коэффициент при x8 в строке 0 системы уравнений

1x0 +3/7x2 +11/ 7x4+ 13/7x5 +5/7 x7 =695/7, (0)

1x1 + 5/7x2 - 5/7x4 + 10/7x5 -1/7 x7 = 50/7, (1)

-6/7x2 - 13/7x4 - 61/7x5+ 1x6 + 4/7x7 =325/7, (2)

2/7x2 + 1x3 + 12/7x4 - 3/7x5 + 1/7x7 =55/7. (3)

будет равен 14-20=-6.

Получим клоэффициенты при x8 в других строкахэтой системы уравнений.

Чтобы получить коэффициенты при x8, в каждой строке берутся коэффициенты при x5, x6, x7, затем первый из них умножается на единицу, второй - на 2/3, третий - на 17 и результаты перемножения складывают(система уравнений I).

(1*1+2/7*0+17*0) x8 =1 x8 (строка 1),

(1*0+2/7*1+17*0) x8 =2/7 x8 (строка 2),

(1*0+2/7*0+17*1) x8 =17 x8 (строка 3).

Коэффициенты при x8 в (F) определяются аналогично.

Метод решения транспортной задачи

Пример: Имеются 4 поставщика А1, А2, А3, А4 с запасами 40, 50, 30,70 соответственно и 3 потребителя В1,В2,В3 с потребностями 40, 70 ,80 соответственно. Матрица тарифов перевозок равна:

2 1 1

С= 3 2 1

1 2 3

2 4 5

требуется решить транспортную задачу.

Решение примера:

Проверка замкнутости задачи:

4 3

 ai= 40+50+30+70 = 190 +40+70+80+  bj,

i=1 j=1

следовательно условие замкнутости выполнено.

Составление таблицы для решения транспортной задачи

Заполняем таблицу методом наименьшего тарифа

табл. 1

	B1	В2	В3	ЗАПАСЫ
А1	2 0	1 40	1 0	40
А2	3 0	2 0	1 50	50
А3	1 30	2 0	3 0	30
А4	2 10	4 30	5 30	70
	40	70	80	ПОТРЕБНОСТИ
	10	30	30
	0	0	0

В верхнем углу каждой клетки стоит тариф на перевозку по данному маршруту Правее основной части записаны запасы поставщиков, а ниже - потребности потребителей. Кроме того, в каждой клетке записан объем перевозки по каждому маршруту, полученный методом наименьшего тарифа. Запись объемов перевозок начинается с любой клетки, где стоит наименьший тариф. В данном случае тариф равен 1. Такой тариф имеют четыре клетки, поэтому можно выбрать любую из них (выбираем (А1,В2). Заполняем ее: потребность В2 равна 70, а запас А1 равен 40. Значит по данному маршрут можно перевести 40 единиц товара (меньшее из чисел 70 и 40 ). Записываем 40 в клетку (А2В2). После этого запас А1 стал равен 0, а потребность В2 равна 30 (эти числа записывают соответственно правее и ниже прежних запасов и потребности). В строке А1 , где запас оказался равным 0, записывает 0 во всех оставшихся клетках. Дальнейшая последовательность заполнения клеток (А1В1), (А2В3), (А3В1), (А4В1), (А4В2), (А4В3). Получим исходный план перевозок

0 40 0

X= 0 0 50

30 0 0

10 30 30

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

Проверка оптимальности маршрута( методом потенциалов)

Каждой строке Аi сопоставим переменную ui , называемую потенциалом поставщика, каждому столбцу Bj - переменную vj, называемую потенциалом потребителя. Оценкой клетки (AiBj) назовем число

ij = ui+vj - cij,

где cij -тариф данной клетки.

Пусть оценки клеток равны 0; это дает нам -1 ( в данном примере 6) уравнений для переменных ui, vj вида: ui+vj= cij. Так как количество этих переменных равно m+n ( на 1 ед. больше чем количество уравнений), то значение одного потенциала берут равным 0, как правило это u1=0. Остальные потенциалы находим решая систему уравнений.

Затем находим оценки ij для всех свободных клеток ( объемы перевозок равны 0). Если для всех свободных клеток ij<=0, то текущий план оптимален;

если хотя бы одна из оценок положительна, то план можно улучшить.

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

u1+v2= 1;

u2+v3= 1;

u3+v1= 1;

u4+v1= 2;

u4+v2= 4;

u4+v3= 5;

Приравнивая u1 к 0 и решая систему, находим потенциалы: u1 = 0; v2= 1; u4=3;

v3= 2; u3=2; v1=-1; u2 =-1. Находим оценки для свободных клеток:

11= 0-1-2=-3; 13 = 0+2-1; 21 = -1-1-3-5;

22=-1+1-2=-2 32 = 2+1-2 33= 2+2-3=1;

Среди оценок есть положительные 13,32,33>0. План не оптимален.

В этом случае нужно найти свободную летку таблицы с максимальной положительной ценой ij*. ( в данном случае любую из трех) и сделать эту клетку занятой, перераспределив объемы перевозок так,чтобы

а) не нарушались балансы по строкам и столбцам;

б) число незанятых клеток не изменилось.

Для этого применяется процедура: пометим клетку(AiBj*) знаком +. Найдем в таблице замкнутый путь с началом и концом в данной клетке, вершинами которого являются только занятые клетки. Вдоль этого цикла расставим чередующиея знаки + и- в его вершинах, начиная с того знака+, что уже стоит в отмеченной клетке. Из вершин отмеченных знаком - выберем клетку с наименьшим объемом перевозок xij=w. Пусть оно расположено в (Аi1Вj1). Это максимальное количество товара, которое можно перераспределить добавляя w к объему перевозки в клетках отмеченных знаком +, и вычитая, в клетках отмеченных знаком-. Клетка (Аi1Вj1) станет после преобразования свободной. Полученный план снова проверяем на оптимальность.

Сделаем занятой в нашем прмере клетку (А1В3). Отмечая ее знаком+ и ищем цикл, начинающийся и заканчивающийся в этой клетке. Таков цикл:

(А1В3) (А1В2)(А4В2)(А4В3)(А1В3).

Отметим его в таблице 2 и расставим в его вершинах поочередно знаки + и-, начиная со знака + в исходной клетке (А1В3): помечаем (А1В2) - минус, (А4В2)-плюс, (А4В3)-минус. Из объемов перевозок в тех клетках, где стоит знак - выбираем меньший объем w=30. Вычитаем30 в тех клетках, которые помечены знаком минус, прибавляем тридцать в клетках со знаком +. Получаем новы план.

(таблица 3):

	В1	В2	В3
А1	2 0	1 0 -	1 + 0
А2	3 0	2 0	1 50
А3	1 30	2 0+	3 - 0
А4	2 10	4 30	5 30

	В1	В2	В3
А1	2 0	1 10	1 30
А2	3 0	2 0	1 50
А3	1 30 -	2 + 0	3 0
А4	2 10 +	4 - 60	5 0

Клетка (А1В3) стала занятой, клетка (А4В3) - свободной. Определим оценки свободных клеток, исходя из системы потенциалов.

u1+v2= 1;

u1+v3= 1;

u2+v3= 1;

u3+v1= 1;

u4+v1= 2;

u4+v2= 4;

Берем u1=0. Тогда v2=1, v3=1, u2=0, u4=3,v1=-1,u3=2. Значит,

11= 0-1-2=-3; 33 = 2+1-3=0; 21 = 0-1-3=-4;

22=0+1-2=-1 32 = 2+1-2=1; 43= 3+1-5=-1;

Единственная положительная оценка - это 32=1. Поэтому делаем занятой клетку (А3В2), отмечая ее знаком +. Находим в таблицце 1 цикл:

(А3В2) (А3В1)(А4В1)(А4В2) (А3В2).

Расставляем знаки , начиная с уже пославленного знака +. В клетках (А3В1) и(А4В2), отмеченных знаком -, минимальный объем перевозок равен w=30. Это число прибавляем лил вычитаем в соответствии со знаком. Полчаем новый план(таблица 4).

	В1	В2	В3
А1	2 0	1 10	1 30
А2	3 0	2 0	1 50
А3	1 0	2 30	3 0
А4	2 40	4 30	5 0

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

u1+v2= 1;

u1+v3= 1;

u2+v3= 1;

u3+v2= 2;

u4+v1= 2;

u4+v2= 4;

Полагаем u1=0. Остальные потенциалы последовательно находим из системы:

v2=1; v3=1; u2=1; u4=3; v1=-1. Находим оценки свободных клеток:

11= 0-1-2=-3;

21 = 0-1-3=-4;

22=0+1-2=-1;

31 = 1+-1-1=-1;

33 = 1+1-3=-1;

43= 3+1-5=-1.

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

0 10 30

X*= 0 0 50

0 30 0

40 30 0

Стоимость перевозок для него равна

L(x*)= 10*1+30*1 +50*1+ 30*2 +40*2 +30*4=350

Следовательно, минимально возможное значение функции L(x) есть L=350.