Теоремы двойственности
Теоремы двойственности
Первая теорема (теорема о существовании решений)
А) Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение:
Х*, у* f0(Х*)=g0(у*)
Б) Если одна из двойственных задач не имеет смысла, то другая не имеет решения:
1) Пусть f0(Х*) ® ¥, тогда Q =Æ
2) Пусть g0(у*)® ¥, тогда R =Æ
В) Если одна из задач не имеет решения, то двойственная к ней либо не имеет смысла, либо не имеет решения.
Пункт А) следует из теоремы о критерии оптимальности прямой и двойственной задач.
Рекомендуемые материалы
Б), В) - смотри геометрическую интерпретацию практических задач.
Вторая теорема (о свойствах оптимальных решений)
Пусть имеется решение:
Х*, у*, если Х*к >0, то к - ограничение. В двойственной ЗЛП при подстановке оптимального решения У* обратится в равенство:
=ck
Если какой-либо Х*L =0, то соответствующие ограничения двойственной задачи будут строго больше СL :
>CL
Если Ys*>0, то 
=bs
Если Yr*=0, то 
< br
X*j(
)=0 (1)
Y*i(
)=0 (2)
Тогда теорема 2 переформулируется:
- Для того, чтобы Х* и Y* были оптимальными решениями, необходимо и достаточно, чтобы выполнялись условия (1) и (2).
Доказательство:
1) Необходимость
Х*, Y* - оптимальное решение
Доказательсть: выполняются соотношения (1) и (2)
Из критерия оптимальности следует:
f0(Х*)= g0(у*)
f0(Х*)=
=
=
Сгруппируем члены:
=
=0 (2)
£ bi
=0 (3)
(3) - сумма неотрицательных чисел (она равна нулю, когда каждое из чисел равно нулю)
yi*
=0 ½*(-1)
Получим:
yi*
=0 ® это (2)
2)Достаточность
Для того, чтобы доказать (1) и (2) необходимо доказать, что x* и y* - оптимальные решения, т.е.
f0(Х*)= g0(у*)
Соотношение (1) суммируем по i, а (2) по j
, yi*=0
=0 
f0(Х*)= g0(у*)
Анализ двойственных оценок
Исследуем переменные:
Yi*, i=1,2,...,m для задачи распределения ресурсов, которая формулируется следующим образом:
П1, П2,..., Пn - продукция; изготавливается из ресурсов R1, R2, ..., Rm
Процесс задаётся технологической матрицей:
x1 x2 xj xn
- матрица прямых затрат, в которой элемент aij показывает количество i-го ресурса, необходимого для изготовления j-той продукции.
j-тый столбец показывает технологию изготовления ед. j-той продукции.
Экономический смысл i-ой строки: показывает использование i-го ресурса при изготовлении единичной номенклатуры продукции.
Тогда, 
- использование i-го ресурса для выпуска единичной номенклатуры продукции.
- затраты ресурсов на выпуск ед. j-той продукции.
xj £ bi (1), i=1,2,...,m,...
c=c1,c2,...,cn cj - цена, доход от ед. j-той продукции.
Тогда можно сформулировать задачу:
max f0(x)=
(2) x ³0 (3)
Сформулируем двойственную задачу:
min g0(y)=
(4)
³ cj (5) y ³0 (6)
Третья теорема двойственности
Если задача распределения ресурсов имеет оптимальное решение x* и y* - единственное решение двойственной задачи. То f0(x) в точке x= x* дифференцируема по переменной b и
(7)
Доказательство:
Т. к. x* и y* - оптимальные решения, т.е. f0(Х*)= g0(у*)=
Возьмем производную от обеих частей и получим:
Замечание
Экономический смысл этой теоремы состоит в следующем:
или Df0(x*)=Dbiyi* (8)
Соотношение (8) справедливо для малых приращений.
Пусть в (8) Dbi=1, тогда Df0(x*)= yi* (9), тогда экономический смысл теоремы 3:
yi* - называется двойственной оценкой, показывает как изменится суммарный доход от производства продукции при увеличении i-го ресурса на единицу, поэтому:
yi* - теневая(скрытая, маржинальная) цена i-го ресурса, она показывает эффективность использования единицы i-го ресурса.
Экономический смысл дополнительной двойственной переменной:
³сs ; 
- 
= сs , >0
xs ¹0
- показывает, что продукция соответствующая ей не вошла в оптимальный план и убыток от производства единицы этой продукции xs будет равен величине уi+s* (это из Т.2)
Если xs=0, то уi+s* показывает значение убытка при производстве единицы этой s продукции.
Если xs ¹0, то уi+s* =0
Метод потенциалов решения транспортных задач.
Постановка транспортной задачи.
Пусть имеется m поставщиков однородной продукции и n потребителей этой продукции.
Каждый 
-ый поставщик располагает продукцией в количестве 
, i=1,2,3,...,m. Потребность каждого потребителя 
-ого составляет 
, j=1,2,3,...,n. 
- стоимость перевозки единицы продукции от поставщика к потребителю.
Требуется составить такой план перевозок , который минимизировал бы суммарную стоимость перевозок.
Обозначим через 
количество продукции , перевозимое от поставщика к потребителю .
, тогда целевая функция
(1)
Таким образом мы сформулировали транспортную задачу. Условия разрешимости транспортной задачи (1) и (4) , когда
(5)
Теорема о разрешимости транспортной задачи.
Для того , чтобы задача (1) и (4) имела решение , необходимо и достаточно, чтобы выполнялось условие (5).
Необходимость:
Дано : существует решение задачи (1) , (4) - 
Доказать: для него выполняется условие (5)
(2 /) i=1,2,3,..,m
просуммируем (2 ) по i
(6)
, j=1,2,3,...,n (3/ )
(7)
приравниваем (6) и (7)
=
Достаточность
Дано: выполняется условие (5)
Доказать: существует решение задачи (1), (4)
Пусть 
подставим значение 
в систему ограничений (2)
подставим значение в систему ограничений (3)
- удовлетворяет ограничениям (3)
Из построения следует 
, следовательно выполнилось условие (4)
- дополнительное решение задачи (1), (4)
Замечание 1 : есть дополнительное решение задачи (1), (4), то для поиска оптимального решения используются специальные методы.
Замечание 2: если 
, оно выполняется при условиях:
а. Если 
, тогда вводится фиктивный 
потребитель с потребностью 
- (8)
Стоимость перевозки
, i=1,2,3,...,m (9)
б. Если 
, тогда вводится фиктивный поставщик 
с поставкой
- (10)
Стоимость перевозки
, о=1,2,3,...,n (11)
Для случая «а» условие (5) запишется:
=
(5а)
Для случая «б» условие (5) запишется:
= (5б)
Построим двойственную задачу к задаче (1), (4)
Каждому i –ому ограничению поставим в соответствие 
, каждому j -ому ограничению - 
, тогда двойственная задача формулируется:
(12)
Метод потенциалов основан на второй теореме двойственности :
если
, то соответствующее ограничение двойственной задачи обращается в строгое равенство
(16)
если 
,то
(17)
переменные u и v называются потенциалами и соответственно метод называется методом потенциалов.
В этом методе предполагается, что начальное решение уже найдено. Наиболее распространенными методами нахождения начального решения являются метод северо-западного угла и метод минимальной стоимости. Рассмотрим их.
Метод северо-западного угла
| А |
| П1 | П2 | П3 | П4
|
|
В | в а | 50 | 80 | 20 | 40 |
| а1 | 90 | 2 50 | 3 40 | 4 | 3 |
| а2 | 30 | 5 | 3 30 | 1 | 2 |
| а3 | 40 | 2 | 1 10 | 4 20 | 2 10 |
| а4 | 30 | 0 | 0 | 0 | 0 30 |
Суть:
Заполнение начинается с элемента Х11 и если 
, то элемент Х11=b1 , а разность 
распространяется между вторым потребителем и следующим. Если 
, то Х11= а1 ,а разность 
берется у второго и последующих поставщиков.
Метод минимальной стоимости.
Суть:
Первая поставка выделяется для поставщика у которого стоимость перевозки является минимальной по i и j из Сij
а. 
, то
и столбец вычеркивается, у 
размер поставки 
б. 
, то 
, потребность потребителя 
неудовлетворенна на 
и вычеркивается строка 
.
Решим приведенную выше задачу методом минимальной стоимости
| А |
| П1 | П2 | П3 | П4
|
|
В | в а | 50 | 80 | 20 | 40 |
| а1 | 90 | 2 50 | 3 30 | 4 ----- | 3 10 |
| а2 | 30 | 5 ---- | 3 ----- | 1 ----- | 2 30 |
| а3 | 40 | 2 ---- | 1 10 | 4 20 | 2 10 |
| а4 | 30 | 0 ----- | 0 ----- | 0 ----- | 0 30 |
Rg A
(7) , наше решение х0 и х1 – невырожденное 
Если
,то 
Метод потенциалов.
Теоретическим обоснованием этого метода является вторая теорема двойственности для задачи в канонической форме записи
Для этой формы записи справедлива только теорема:
если 
,то соответствующее ограничение двойственной задачи обращается в равенство;
если 
, то соответствующее к-ое ограничение двойственной задачи обращается в строгое неравенство.
Построим двойственную задачу:
Находим начальное решение 
, получаем систему ограничений исходной задачи
, при условие ,что 
>0
, при условие ,что =0
Для оптимального решения:
, невыполнение этого условия называется невязкой (18)
, 
должно быть больше нуля (19)
Метод потенциалов состоит в итерационном процессе получения неотрицательных оценок 
Пусть 
- оптимальное решение (матрица), тогда если компоненты
>0 , то (20)
, то 
(21)
Рассмотрим пример:
| А |
| в1 | в2 | в3 | в4 | в5
|
|
В | в а | 18 | 13 | 14 | 31 | 9 |
| а1 | 24 | 5 12 | 3 ----- | 24 5 | 10 7 | 25 ----- |
| а2 | 15 | 30 ----- | 2 13 | 22 ----- | 16 ------ | 7 ------ |
| а3 | 16 | 30 ----- | 24 ------ | 27 9 | 29 ------ | 10 7 |
| а4 | 24 | 15 ------ | 17 ----- | 21 ----- | 2 24 | 3 ----- |
| а5 | 6 | 0 6 | 0 ----- | 0 ----- | 0 ----- | 0 ----- |
0. Нахождение начального решения.
0.1. 
0.2. Построим начальное решение методом минимальной стоимости
m+n-1=5+5-1=9 не вырожденная
1. Первая итерация
1.1. Построение матрицы 
, для этого решим систему уравнений , при условие , что 
.
Выбираем минимальный из отрицательных элементов и вычеркиваем соответствующую строку, помеченные нули должны быть перечеркнуты два раза. Затем к перечеркнутым столбцам прибавляем разрешающий элемент, а из каждого элемента перечеркнутых строк вычитаем разрешающий элемент.
1.2. Построение плана 
1.3. Построим цикл перемещения групп: вершины цикла должны находиться в значимых элементах матрицы. Чтобы не нарушить не отрицательность будем перемещать максимальный из помеченных минусами в начальном решение элементов.
2.1.Вторая итерация
Строим 
, используя при этом данные 
.
=
2.2. Построение плана 
3.1. Третья итерация
3.2. План 
4.1. Четвертая итерация
Рекомендуем посмотреть лекцию "12 Патока".
Проверка осуществляется по формуле
, где
- максимальный элемент из помеченных минусами в плане 
- разрешающий элемент 
