wyk-OLB-PLC-ciecie, Studia, Stopień 2 Semestr I, Optymalizacja w logistyce i biznesie
[ Pobierz całość w formacie PDF ]
Programowanieliniowewliczbachca“kowitych-metoda
ciĢ
De
nicja1.NiechdanabƒdzieA=[a
ij
]macierzkszta“tumna
ij
2R,wektory
b=[b
1
;:::;b
m
]
T
,b
i
2R,c=[c
1
;:::;c
n
],c
j
2Rorazzbi
ó
r; 6=J
c
f1;:::;ng.
Zadaniemprogramowanialiniowegowliczbachca“kowitychPLCnazywamy
problempostaci:
8
>
>
>
>
>
>
<
cx!max
przyograniczeniach
Ax=b;
x0;
x
j
2Zdlaj2J
c
;
>
>
>
>
>
>
:
(PLC)
gdziex=(x
1
;:::;x
n
).Zadanietonazywamype“nym(czystym)zagadnieniem
PLC,je–liJ
c
=f1;:::;ng.Je»eliJ
c
6=f1;:::;ng,tozadanietonazywamymieszanym
zagadnieniemPLC.
Dok“adnemetodyrozwi¡zywaniaPLCmo»napodzieli¢natrzygrupy:
1)metodyciĢ;
2)metodypodzia“uiogranicze«;
3)metodyopartenateoriigrup.
Najstarszymzkierunk
ó
wjestzpierwszychwymienionych.Zapocz¡tkowa“agow
1958metodaGomoryiby“atopierwszapoprawnametodaprogramowaniawliczbach
ca“kowitych.Efektywno–¢metodGomoryniejestzadowalaj¡ca.Jesttoefektniewyko-
rzystywaniaprzezalgorytminformacjipomocniczychzawartychwfunkcjikryterialnej.
Du»olepsz¡(podwzglƒdemefektywno–ci)jestmetodapodzia“uiogranicze«.Metody
opartenateoriigrupwykorzystuj¡algebrƒBoole’aisprowadzaj¡problemPLCdo
r
ó
wnowa»negozadaniazezmiennymiboolowskimi.Nawyk“adzieom
ó
wimydwiepier-
wszemetody.
Przypomnijmy,»ewdowolnymPLpolegajacymnamaksymalizacjifunkcjicelu
mamytrzymo»liwo–ci:zagadnieniejestsprzecznealbofunkcjacelujestnieogranic-
zonazg
ó
ryalboproblemposiadarozwi¡zanieoptymalne.Zw“asno–cirozwi¡za«PL
mo»emywnioskowa¢orozwi¡zalno–ciproblemuPLCwpewnychprzypadkach.Itak,
je»elizagadnieniePLpowsta“ezPLCpoprzezopuszczeniewarunk
ó
woca“kowito–cijest
sprzeczne,toPLCjestr
ó
wnie»sprzeczne.Je»elifunkcjaceluwodpowiadaj¡cymPL
jestnieograniczonazg
ó
ry(poniewa»rozwa»amyzagadnieniemaksymalizacjiwPLC),
tojestonate»takanazbiorzerozwi¡za«dopuszczlanychdlaPLC.Zatempozosta“o
rozwa»y¢przypadek,kiedyzagadnieniePLodpowiadajacePLCmarozwi¡zanieopty-
malne.
Algorytmmetodyciƒ¢Gomorydlaczystego(pe“nego)problemuPLC
1
1.Metod¡symplekswyznaczamybazowerozwi¡zanieoptymalnex
B
problemuPL
otrzymanegozproblemuPLCpoprzezpominiƒciewarunkuoca“kowito–cizmi-
ennych.Nale»ypamiƒta¢otym,abystosowa¢prymaln¡metodƒsympleksnale»y
funkcjƒceluminimalizowa¢PL.
2.Badamy,czyx
B
jestwektoremowsp
ó
“rzƒdnychca“kowitych.Je»elitak,to
jestonor
ó
wnie»rozwi¡zaniemoptymalnymPLC.Wprzeciwnymwypadkuprze-
chodzimydopunktu3.
3.Znajdujemyelementh
i0
wektorah
0
=A
1
B
bniebƒd¡cyliczb¡ca“kowit¡.Do“¡czamy
doogranicze«problemuPLwarunek
X
([h
ij
]h
ij
)x
j
+x
n+1
=[h
i0
]h
i0
;x
n+1
0:
j62B
4.Metod¡symplekswyznaczamybazowerozwi¡zanieoptymalnex
B
otrzymanego
problemuPL.Wracamydopunktu2.
Przyk“ad1.Rozwi¡za¢zagadanienie
8
>
>
>
>
>
>
<
x
1
+x
2
!max
przyograniczeniach
x
1
+2x
2
32
18x
1
+3x
2
224
x
1
;x
2
0;x
1
;x
2
2Z
>
>
>
>
>
>
:
(P
1
)
2
[ Pobierz całość w formacie PDF ]