Презентация - Семенкин Е.С. Методы оптимизации
Подождите немного. Документ загружается.
Стоимостьперевозкиединицыпродукциидофиктивногопотребителяиот
фиктивногопоставщикаполагаетсяравнойнулю, таккакгрузвобоихслучаяхне
перевозится. Фиктивномупотребителюбудетнаправленгрузотнаименеевыгодного
поставщикагруз, апродукцияфиктивногопоставщикабудетнаправленакнаименее
выгодномупотребителю.
Еслипослерешениязадачиоказывается, чтонекоторыйпотребительдолжен
получитьгрузотфиктивногопоставщика, тоэтоозначает, чтопотребительданного
объемапродукциинеполучитиегоспросбудетудовлетвореннеполностью,
аналогично - дляфиктивногопотребителя.
Матрица планирования:
b a b
n i
i
m
j
j
n
+
= =
= −
∑ ∑
1
1 1
Потреб-
ности
Поставщики
b
1
b
2
- b
n
а
1
c
11
c
12
- c
1n
а
2
…
а
m
c
m1
c
m2
- c
mn
Решениесостоитиздвухэтапов: первый - построениепервоначальногоопорного
плана - обычновыполняетсяметодомминимальнойстоимости, второй - проверка
плана на оптимальность и переход к новому опорному плану (наиболее
распространенныйметод - методпотенциалов).
Задача о назначениях
Имеется n работ (заданий)T
1
,T
2
,…,T
n
иnчеловек M
1
,M
2
,…,M
n
,
каждыйизкоторыхспособенвыполнитьлюбуюработу. Всилуразличной
квалификациинавыполнениеэтихзаданийимтребуетсяразличноевремя.
Если c
ij
- время, затрачиваемое i-мчеловекомна j-езадание, токакследует
распределитьлюдейпозаданиям, чтобыминимизироватьвремявыполнения?
Пусть x
ij
- времяучастия i-гочеловекаввыполнении j-гозадания. Все
x
ij
≥ 0.
Таккаккаждыйчеловекдолженбытьзадействован,aкаждоезадание
полностьювыполнено, то x
ij
,i=1,...,n, j=1,...,m, должны
удовлетворятьследующимограничениям:
x
11
+x
12
+...+x
1n
=1
x
21
+x
22
+...+x
2n
=1
. . . . . . . . .
x
n1
+x
n2
+...+x
nn
=1
x
11
+x
21
... +x
n1
=1
x
12
+x
22
... +x
n2
=1
. . . . . . . .
Двойственность в линейном программировании
ДлялюбойзадачиЛПможносформулироватьдвойственнуюзадачу, являющуюся
"зеркальнымотражением" исходнойзадачи, т.к. онаиспользуеттежепараметры, аее
решениеможетбытьполученоодновременносрешениемисходнойзадачи.
Прямаязадача:
Сколькоизделийикакойконструкции x
j
(j =1,…,n) необходимопроизвести,
чтобыпризаданныхстоимостях c
j
(j =1,…,n) единицыпродукциииразмерах
имеющихсяресурсов b
i
(i =1,…,m) максимизироватьвыпускпродукциив
стоимостномвыражении?
z=c
1
x
1
+c
2
x
2
+…+c
n
x
n
→max
x
j
≥ 0,j=1,…,n
Двойственнаязадача:
Какиецены y
i
наединицукаждогоизресурсовнужноназначитьпризаданных
количествахресурсов b
i
ивеличинахстоимостипродукции c
j
, чтобыпродатьресурсы
былобынеменеевыгодно, чемпроизводитьпродукцию?
f=b
1
y
1
+b
2
y
2
+…+b
m
y
m
→min
≥
≤+++
≤+++
mnmnmm
nn
bxaxaxa
bxaxaxa
...
...........................................
...
2211
11212111
≥+++
≥+++
nmmnnn
mm
cyayaya
cyayaya
...
.............................................
...
2211
11221111
Пары двойственных задач
А. Несимметричные
Прямаязадача: Двойственнаязадача:
Б. Симметричные
Прямаязадача: Двойственнаязадача:
0X
BAX
minXCZ 1)
T
≥
=
→=
max )1
CYA
YBf
T
T
≤
→=
0X
BAX
maxXCZ 2)
T
≥
=
→=
minYB=f )2
T
CYA
T
≥
→
0X
BAX
minXCZ 3)
T
≥
≥
→=
0
max )3
≥
≤
→=
Y
CYA
YBf
T
T
0X
BAX
maxXCZ 4)
T
≥
≤
→=
0
min )4
≥
≥
→=
Y
CYA
YBf
T
T
Основные теоремы двойственности
Теорема 1(основноенеравенстводвойственности).
Длялюбыхдопустимыхпланов X прямойиYдвойственнойзадачих
целевыефункции z(X) и f(Y) связанымеждусобойнеравенствами:
приминимизации z(X) z(X) ≥ f(Y),
примаксимизации z(X) z(X) ≤ f(Y),
инесущественно, какаязадачапрямая, акакая - двойственная.
Доказательство.
Примаксимизации z(X):
).(
)(
)()(
1
1 11 11 1
1 11
Yfyb
yxayxaxya
xyaxcXz
m
i
ii
m
i
n
j
ijij
m
i
n
j
ijij
n
j
m
i
jiij
n
j
m
i
jiij
n
j
jj
=≤
≤===
=≤=
∑
∑∑∑∑∑∑
∑∑∑
=
= == == =
= ==
Теорема 2(критерийоптимальностиКанторовича).
ЕслинадопустимыхпланахпрямойидвойственнойзадачЛПзначенияцелевых
функцийсовпадают, тоэтипланыявляютсяоптимальнымиинаоборот, еслипланы
прямойидвойственнойзадачоптимальны, тозначенияцелевыхфункцийнаних
совпадают.
Доказательство.(Докажемпрямоеутверждение)
Пусть X–допустимыйпланпрямойзадачи, а Y–допустимыйпландвойственной
задачииz(X)=f(Y).
Пусть X'–произвольныйдопустимыйпланпрямойзадачи. Тогдапоосновному
неравенствудвойственности
z(X') ≤ f(Y), т.е. z(X') ≤ f(Y)=z(X),
т.е. значениецелевойфункциипрямойзадачивточке X являетсямаксимальным
(т.к. этонеравенствовыполняетсядлялюбогодопустимогоплана).
Пусть Y'–произвольныйдопустимыйпландвойственнойзадачи. Тогдапо
основномунеравенствудвойственности
f(Y') ≥ z(X)=f(Y),
т.е. значение целевой функции двойственной задачи в точке Y является
минимальным.
Теорема 3. Длясуществования оптимального решениякакпрямой, таки
двойственной
задачи
ЛП
необходимо
и
достаточно
существования
какого
-
либо
Достаточность. Если Y–допустимыйпландвойственнойзадачи, топо
основномунеравенствудвойственностидлялюбогодопустимогоплана X'
прямойзадачивыполняется z(X') ≤ f(Y).
Т.о., последовательностьзначенийцелевойфункциипрямойзадачи z(X
1
),
z(X
2
),…наразличныхеедопустимыхпланах X
1
,X
2
,…, полученныхсимплекс-
методом, являетсянеубывающейиограниченнойсверху. Поэтомунадопустимых
планах X
1
,X
2
,…можновыбратьтакойплан X, длякоторого z(X') ≤ z(X) при
любом X', чтодоказываетусловиедостаточностидлямаксимума.
Теорема 4. Еслипрямая (двойственная) задачаимеетоптимальноерешение,
тоидвойственная (прямая) задачаимеетоптимальноерешение.
Теорема 5. Еслипрямая (двойственная) задачанеимеетрешенияиз-за
неограниченностицелевойфункциинамножестведопустимыхрешений, то
системаограниченийдвойственной (прямой) задачипротиворечива.
Теорема 6(одополняющейнежесткости)
Необходимымидостаточнымусловиямиоптимальностидопустимыхпланов
прямой X идвойственной Y задачявляетсявыполнениеусловийдополняющей
нежесткости
nicyax
mjbxay
i
m
j
jjii
n
i
jiijj
,...,2,1,0)(
,...,2,1,0)(
1
1
==−
==−
∑
∑
=
+
Использование двойственности при решении задач ЛП
Теориядвойственностипозволилаусовершенствоватьсимплекс-методи
создатьулучшенный (илиисправленный) симплекс-метод, которыйпозволяет
получатьсразурешениеиисходнойидвойственнойзадач. Поэтомуможно
выбирать, решатьлизадачувтомвиде, вкоторомонапоставлена, илирешать
двойственнуюзадачу. ТаккакобъемвычисленийвзадачеЛПсвязанскореес
количеством ограничений, чем с количеством переменных, то можно
порекомендовать переходить к двойственной задаче в случае, когда
ограниченийбольше, чемпеременных.
Теориядвойственностипозволяеттакжепроводитьанализустойчивости
решенияприизменениикоэффициентов c
j
и b
j
, тоестьопределятьграницы
изменения этих коэффициентов при изменении условий (например,
стоимости, запасовресурсовит.п.), тоестьзаранеезнать, изменитсяилинет
оптимальноерешение, нуженлидополнительныйанализ, понадобитсялиеще
разприниматьрешение.
Теория двойственности создана Дж. Фон Нейманом и Л.В. Канторовичем.
Классические методы безусловной оптимизации
Классическийподходкзадачеопределениялокальныхиглобальныхминимумов
состоитвиспользованииметодовматематическогоанализадляпоискауравнений, которым
должныудовлетворятьэтиточки, идлярешенияэтихуравнений.
Определение 1. Функция f(x) однойпеременнойимеетлокальныйминимумвточке x,
еслисуществует , такая, что длявсех , тоестьеслисуществует
некотораяокрестностьточки x
0
, вкоторойзначениефункциивлюбойееточкебольше, чем
f(x
0
).
Определение 2. Функция f(x) имеет глобальный минимум в точке x
*
, если f(x
*
)<f(x) для
всех x из области определения f(x).
0
>
δ
(
)
(
)
0
xfxf
≥
δ<−
0
xx
Рис. 1. Стационарные точки непрерывной функции
Изрисунка 1 видно, чтовточках x
0
и x
*
касательнаякграфикуфункциибудет
параллельнаоси OX, аэтоозначает, чтопроизводнаяфункции f(x) вэтихточкахбудет
равнанулю. Следовательно, x
0
и x
*
будутрешениямиуравнения .
Однакоэтожесправедливоидляточкимаксимума x
m
, идляточкиперегиба x
c
.
Такимобразом, найденноеуравнениеявляетсянеобходимымусловиемминимума, ноне
являетсядостаточным.
Вточках x
0
и x
*
производная меняетзнаксотрицательногонаположительный,
в x
m
- сположительногонаотрицательный, вточке x
c
производнаязнакнеменяет.
Следовательно, вточкеминимумапроизводнаяявляетсявозрастающейфункцией.
Степеньжевозрастанияизмеряетсявторойпроизводной, тоестьвнашемслучае
, , . Однакоесли , тоситуацияостается
неопределенной.
Надежноеоснованиедляполученныхрезультатовдаетразложениефункциивряд
Тейлоравокрестноститочки x
0
(x
m
, x
*
).
Если x
0
- точкаминимума, то f(x
0
+h)-f(x
0
)>0 длялюбогодостаточномалого h
(|h|<δ).
Если , тоотрицательное h сделаетотрицательнойразность ,
что
невозможно
в
точке
минимума
.
Если
,
то
произойдет
то
же
самое,
если
(
)
′
=f x 0
(
)
′
f x
(
)
0
0
>
′
′
xf
(
)
0
*
>
′′
xf
(
)
0<
′
′
m
xf
(
)
0
=
′
′
xf
( ) ( ) ( ) ( ) ( )
...
!
3
!
2
0
3
0
2
000
+
′′′
+
′′
+
′
=−+ xf
h
xf
h
xfhxfhxf
(
)
0
0
>
′
xf
(
)
(
)
00
xfhxf −+
′
(
)
0
0
<
′
xf
(
)
′
=f x
0
0