sympleks, Automatyka i Robotyka, Semestr III, Metody Obliczeniowe Optymalizacji, Gotowce, labki i inne, wyklad MOO
[ Pobierz całość w formacie PDF ]
Programowanieliniowe–metodasympleks
MirosławSobolewski
WydziałMatematyki,InformatykiiMechanikiUW
wykładzalgebryliniowej
Warszawa,stycze´n2009
MirosławSobolewski (UW)
Warszawa,2009 1/13
Metodasympleks
Twórca–GeorgeDantzig,USA1947rok
Cel:rozwi˛azywaniezadaniaprogramowanialiniowego
okre´slonegowpostacistandardowej
f(x
1
,...,x
n
)=c
1
x
1
+···+c
n
x
n
!min(f–
funkcjacelu
)
przywarunkach
8
>
<
>
:
a
11
x
1
+···+a
1n
x
n
=b
1
.
.
.
.
.
.
.
.
.
.
.
.
a
m1
x
m1
+···+a
mn
x
n
=b
m
U:
,x
1
0,...,x
n
0,gdzieb
i
0
dlai=1,...,m.Wskrócie:
2
3
a
11
···a
1n
.
.
.
.
.
.
.
.
.
a
m1
···a
mn
6
4
7
5
,
Min{c
>
·x:Ax=b,x0},gdzieA=
2
6
4
3
7
5
,x=
2
6
4
3
7
5
,c=
2
6
4
3
7
5
.Zakładamy,˙zer(A)=m.
b
1
.
.
.
b
m
x
1
.
.
.
x
n
c
1
.
.
.
c
n
b=
MirosławSobolewski (UW)
Warszawa,2009 2/13
Schematprzeszukiwania:
Zaczynaj˛acodpewnegorozwi˛azania
bazowegodopuszczalnego,przechodzimykolejnodoinnych
rozwi˛aza´nrozwi˛aza´nbazowychdopuszczalnych,wka˙zdymkroku
zast˛epuj˛acjedenelementzbiorubazowegoinnym,dopókidasi˛e
pomniejsza´cwarto´s´cfunkcjiceluf.
Interpretacjageometryczna:
Rozwi˛azaniabazowedopuszczalne=
wierzchołkizbiorudopuszczalnegoX.
Wymianajednegoelementuwzbiorzebazowym=przej´sciedo
s˛asiedniego(tzn.poł˛aczonegokraw˛edzi˛a)wierzchołkaX.W˛edrówk˛e
powierzchołkachko´nczymywwierzchołku”najni˙zszym”wsensie
funkcjiceluf.
MirosławSobolewski (UW)
Warszawa,2009 3/13
Przykład(
Szczegółymetodysympleks)
Szukamynajwi˛ekszejwarto´scifunkcjig(x
1
,x
2
)=15x
1
+10x
2
,przy
ograniczeniach(*)x
1
0,x
2
0,x
1
2,x
2
3,x
1
+x
2
4.
Sprowadzamyzagadnieniedopostacistandardowej,wprowadzaj˛ac
dodatkowezmiennex
3
,x
4
,x
5
,zast˛epuj˛acnierówno´sci(*)nast˛epuj˛acym
układemrówno´sciinierówno´scielementarnych:
x
1
+x
3
=2
x
2
+x
4
=3
x
1
+x
2
+x
5
=4
x
1
0,...,x
5
0
za´smaksymalizacj˛efunkcjigminimalizacj˛afunkcji
f(x
1
,x
2
,x
3
,x
4
,x
5
)=−15x
1
−10x
2
.Inaczejmo˙znatozadaniezapisa
´
c
wpostacif(x
1
,x
2
,x
3
,x
4
,x
5
)=−15x
1
−10x
2
!minprzy
2
6
6
6
6
4
3
7
7
7
7
5
x
1
x
2
x
3
x
4
x
5
2
4
3
5
,x=
2
4
3
5
10100
01010
11001
2
3
4
Ax=b,x
0
,gdzieA=
,B=
MirosławSobolewski (UW)
Warszawa,2009 4/13
Przykład(cd)
Utworzymytzw.tablic˛esympleksow˛a,składaj˛ac˛azmacierzy
bazowegoukładurówna´nzadaniaprogramowanialiniowego,
rozszerzonejowiersznazwany
wierszemfunkcjicelu
reprezentuj˛acy
równaniez=f(x
1
,x
2
,x
3
,x
4
,x
5
),z−f(x
1
,x
2
,x
3
,x
4
,x
5
)=0gdziez
jestpewn˛adodatkow˛azmienn˛aipewnepomocniczekolumnytzw.
kolumn˛eilorazów,którapozwolinampodj˛a´cdecyzj˛eusuni˛ecia
zmiennejzukładubazowegoikolumn˛ereprezentuj˛ac˛awybór
zmiennychukładubazowego.Pocz˛atkowymwektorembazowym
dopuszczalnymjest(x
1
,x
2
,x
3
,x
4
,x
5
)=(0,0,2,3,4)
ZmiennabazowaZx
1
x
2
x
3
x
4
x
5
bIloraz
x
3
01 01002 *
x
4
00 10103 *
x
5
01 10014 *
wierszf 1
15
100000 nic
MirosławSobolewski (UW)
Warszawa,2009 5/13
[ Pobierz całość w formacie PDF ]