Pierwsze rozwiÄ…zanie bazowe dopuszczalne
xB = B-1b - B-1N xN
x0 =cB B-1b - (cB B-1N - cN ) xN
Poszukiwanie rozwiązań bazowych
x0 îÅ‚ Å‚Å‚ îÅ‚
îÅ‚ Å‚Å‚ cB B-1b cBB-1N - cN Å‚Å‚
= - xN
dopuszczalnych
ïÅ‚x śł ïÅ‚ śł ïÅ‚ śł
B-1b B-1N
ðÅ‚ B ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
Wprowadzone oznaczenia: Postać początkowej tablicy simpleksowej
y0 j
îÅ‚ Å‚Å‚
y00
îÅ‚ Å‚Å‚
ïÅ‚
îÅ‚ - cj ïÅ‚ śł
cB B-1a łł y1 j śł
îÅ‚ Å‚Å‚ y10 śł j
cB B-1b ïÅ‚
ïÅ‚ śł y a" a"
j ïÅ‚ śł - xN
y0 a" a" oraz
ïÅ‚ śł ïÅ‚ śł
B-1a M - xN
ïÅ‚ śł ïÅ‚ j śł
B-1b M ðÅ‚ ûÅ‚
ðÅ‚ ûÅ‚
ïÅ‚ śł
ïÅ‚ śł
ymj
ïÅ‚ śł
ðÅ‚ ûÅ‚
x0 0 - cN
ðÅ‚ym0 ûÅ‚
x0 cBB-1b cBB-1N - cN cB = 0
gdzie oznaczajÄ… kolumny macierzy N.
aj , j " RN
xB b N
xB B-1b B-1N
Funkcja celu x0
dla przypadku gdy cB=0 tzn. pierwsze rozwiÄ…zanie bazowe dopuszczalne odpowiada za
x0 = y00 - xj punkt wierzchołkowy x
"y0 j
x = [0,...,0].
j"R
m funkcji ograniczeń
xBi = yi0 - yij x , dla i = 1,...,m
" j
j"RN
Wydział Elektroniki Wydział Elektroniki
Wydział Elektroniki Wydział Elektroniki
Technika optymalizacji Technika optymalizacji
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic Dr in\
. Ewa Szlachcic
Postać początkowej tablicy simpleksowej dla omawianego
przykładu
Polepszanie rozwiÄ…zania bazowego dopuszczalnego
Å„Å‚ x1 + x2 d" 5 üÅ‚
max x0 = 2x1 +1x2
ôÅ‚ ôÅ‚
x"X X = : - x1 + x2 d" 0 , x e" 0żł
òÅ‚x
ôÅ‚ ôÅ‚ x0 = y00 - y0 j x
j
6x1 + 2x2 d" 21 "
ół þÅ‚
j"RN
max x0 = 2x1 +1x2 + 0x3 + 0x4 + 0x5
x"X
zawsze xj e" 0,
Å„Å‚ x1 + x2 + x3 + 0 + 0 = 5 üÅ‚
xN
ôÅ‚x ôÅ‚
X = : - x1 + x2 + 0 + x4 + 0 = 0
òÅ‚ żł
zatem gdy xk ę! to równie\
x0 Ä™! gdy y0k d" 0
ôÅ‚
6x1 + 2x2 + 0 + 0 + x5 = 21ôÅ‚
ół þÅ‚
x3 x3
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
x1 x2
ïÅ‚x śł
xBi = yi0 - yij x , dla i = 1,..., m
j
xB =ïÅ‚x4śł "
x0 0 -2 -1
xB ïÅ‚ 4 śł ïÅ‚ śł
îÅ‚ Å‚Å‚ j"RN
ïÅ‚ śł
ïÅ‚ śł
x = = x5 e" 0
ðÅ‚x5ûÅ‚
ïÅ‚x śł
x3 5 1 1
ïÅ‚ śł
ðÅ‚ N ûÅ‚
x1 x1 xB
x4 0 -1 1
ïÅ‚ śł îÅ‚ Å‚Å‚
xN =
ïÅ‚x2 śł ïÅ‚x śł
x5 21 6 2
ðÅ‚ ûÅ‚
ðÅ‚ 2ûÅ‚
Wydział Elektroniki Wydział Elektroniki
Wydział Elektroniki Wydział Elektroniki
Technika optymalizacji Technika optymalizacji
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic Dr in\
. Ewa Szlachcic
1
Polepszanie bazowego rozwiÄ…zania dopuszczalnego Optymalne rozwiÄ…zanie zadania programowania liniowego PL metodÄ…
simpleks
¸rk = min(yi0 / yik, yik > 0).
i=1,...,m
Twierdzenie 4.5
Twierdzenie 4.5
Gdy mamy nie-zdegenerowane rozwiÄ…zanie bazowe dopuszczalne takie, \
e
Rozwiązanie bazowe dopuszczalne układu równań Ax=b
y0 j < 0 dla pewnego j = k, k " RN oraz yik > 0
jest rozwiązaniem optymalnym zadania PL, jeśli są spełnione dwa warunki:
dla przynajmniej jednego i wówczas mo\
na z niego otrzymać lepsze bazowe
rozwiÄ…zanie dopuszczalne przez wymianÄ™ jednej z kolumn macierzy B na kolumnÄ™
macierzy N.
(i) Warunek prymalnej dopuszczalności:
y
y 1
rj
r 0
x = - x - x
k " j Br
yio e"0 dla i "{1,..., m}
y y y
rk - {k } rk rk
j " R
N
(ii) Warunek optymalności
ëÅ‚ yik y öÅ‚ ëÅ‚ yik yrj yik
öÅ‚
r 0
ìÅ‚ yij ÷Å‚ x + x
x = yi 0 - ÷Å‚ - ìÅ‚ - ÷Å‚
Bi " j y0 j e" 0 dla "j " RN
ìÅ‚ ÷Å‚ ìÅ‚
y y yrk Br
íÅ‚ rk Å‚Å‚ j" R -{k }íÅ‚ rk Å‚Å‚
N
Wydział Elektroniki Wydział Elektroniki
Wydział Elektroniki Wydział Elektroniki
Technika optymalizacji Technika optymalizacji
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic Dr in\
. Ewa Szlachcic
Pierwsza tablica simpleks-I rozwiÄ…zanie bazowe dopuszczalne
Polepszona tablica simpleks odpowiada za następne rozwiązanie bazowe
dopuszczalne o większej wartości funkcji celu.
Kryterium
y0 j e"0 dla "j " RN
optymalności
...xx- x... ...xx- xk... ... ... -xj ... -xBr ...
j
...
... -- ... -- ...
j k
j k
x0 y00-(y0kyr0/yrk) ... y0j-(y0kyrj/yrk) ... -y0k/yrk
x0 00 00... ... ...
x0 x0yy00 y... ...yj j y0... ...y y0... ...
y0 0 j y0k0k k
Kryterium
... ... ...
... ... ...
... ... ...
... ... ...
dopuszczalności
x y iO... ...
xBiBi xBi y... ...yij y... ...y yik... ... xBi yi0-(yikyr0/yrk) ... yij-(yikyrj/yrk) -yik/yrk
y yij ij yikik ...
iO iO
yioe"0
... ... ...
... ... ...
... ... ...
... ... ...
dla i"{1,...,m}
x y ... ...
xBrBr xBr y... ...yrj y... ...y yrk... ...
yr0r0 r0 yrj rj yrkrk ...
xk yr0/yrk ... yrj/yrk ... 1/yrk ...
... ... ...
... ... ...
... ... ...
xBmxBmm0 ... ... ymk ...
ym0ym0 ...y
xBm y ... ymjmj ymj... ...ymkymk... ...
Wydział Elektroniki Wydział Elektroniki
Wydział Elektroniki Wydział Elektroniki
Technika optymalizacji Technika optymalizacji
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic Dr in\
. Ewa Szlachcic
Algorytm simpleks dla ograniczeń mniejszościowych
Algorytm simpleks (prymalny) c.d.
Krok 1. (start). Rozpoczynamy algorytm od znalezienia pierwszego rozwiÄ…zania
bazowego dopuszczalnego. Nale\
y sprawdzić dopuszczalność Krok 4. (wybór zmiennej usuwanej z bazy). Wybierz jako zmienną usuwaną z bazy
taką zmienną dla której
x ,
yi 0 e" 0 dla i = 1,..., m
rozwiÄ…zania: czy Tak - idz
do kroku 2, Nie  STOP. Br
¸rk = min(yi0 / yik, yik > 0).
Krok 2. (test optymalności). Czy dla ka\
dego j " RN ? i=1,...,m
y0 j e" 0
" Tak - to aktualne rozwiązanie jest optymalne. Jeśli wiele zmiennych spełnia ten warunek, wybierz arbitralnie jedną z nich.
Id\
do kroku 5.
" Nie - idz
do kroku 3.
Krok 5. (eliminacja Gauss a). Wyznacz oraz względem zmiennych
xk x , i `" R ,
Bi N
Krok 3. (Wybór zmiennej wchodzącej do bazy). Wybierz jako zmienną wchodzącą do
x , j " RN - {k}
x , k " R oraz zmiennej xB zgodnie z wyprowadzonym wzorem.
bazy taką zmienną dla której y < 0 . j
k N 0 k r
Podstaw
Typową regułą jest wybór zmiennej xk x = 0, j " RN -{k} i xBr = 0
jest reguła dla której:
j
aby otrzymać nowe rozwiązanie bazowe dopuszczalne.
y = {y , y d" 0}
0 k 0 j 0 j
min
j" R Idz
do kroku 2.
N
Id\
do kroku 4.
Krok ten czasami nazywa siÄ™ wymianÄ… zmiennej bazowej ( piwotyzacjÄ…).
Wydział Elektroniki Wydział Elektroniki
Wydział Elektroniki Wydział Elektroniki
Technika optymalizacji Technika optymalizacji
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic Dr in\
. Ewa Szlachcic
2
Zadanie programowania liniowego PL dla ograniczeń mniejszościowych
Zało\
enia:
X `" 0
Schemat reguły przeliczenia współczynników w tablicy simpleks 1. Zbiór X rozwiązań dopuszczalnych
wg metody eliminacji Gauss a
2. algorytm simpleks startuje z bazowego dopuszczalnego rozwiÄ…zania oraz w
trakcie jego realizacji nie występuje degeneracja
p - element centralny (główny)
q  dowolny element w wierszu centralnym (głównym)
I. Zadanie programowania liniowego PL posiada jedno rozwiÄ…zanie
r  dowolny element w kolumnie centralnej (głównej) Å„Å‚ x1 + x2 d" 5 üÅ‚
ôÅ‚
max x0 = 2x1 +1x2 X = ôÅ‚ : - x1 + x2 d" 0 , x e" 0żł
s  dowolny pozostały element
òÅ‚x
x"X
ôÅ‚ ôÅ‚
6x1 + 2x2 d" 21
ół þÅ‚
Przykład:
1 q
îÅ‚ Å‚Å‚
ïÅ‚ śł
x5 x2
îÅ‚p qÅ‚Å‚ x1 x2 x5 x3
p p
ïÅ‚r sśł Ò! ïÅ‚ r rq śł x0 7 1/3 -1/3 x0 31/4 1/4 1/2
x0 0 -2 -1
ïÅ‚- s - śł
ðÅ‚ ûÅ‚
x2 9/4 -1/4 3/2
x3 5 1 1 x3 3/2 -1/6 2/3
ïÅ‚ śł
p p
x4 1/2 1/2 -2
ðÅ‚ ûÅ‚
x4 0 -1 1 x4 7/2 1/6 4/3
x1 11/4 1/4 -1/2
x5 21 6 2
x1 7/2 1/6 1/3
'"
11 9 1
x = [x1, x2, x3, x4.x5]T = [ , , 0, , 0]T
RozwiÄ…zanie bazowe optymalne:
4 4 4
31
Wartość optymalna funkcji celu:
x0 =
4
Wydział Elektroniki Wydział Elektroniki
Wydział Elektroniki Wydział Elektroniki
Technika optymalizacji Technika optymalizacji
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic Dr in\
. Ewa Szlachcic
Przykład zadania programowania liniowego  metoda prymalna simpleks Przykład zadania programowania liniowego  metoda prymalna simpleks cd.
- I rozw. bazowe dopuszczalne. - II rozw. bazowe dopuszczalne.
Krok 1. (start). Rozpoczynamy algorytm od znalezienia pierwszego rozwiÄ…zania bazowego
Krok 5. (eliminacja Gauss a). Wyznacz nowa tablicę simpleksów. Idz
do kroku 2.
dopuszczalnego. Nale\
y sprawdzić dopuszczalność rozwiązania.
Krok 2. (test optymalności). Tak - to aktualne rozwiązanie jest optymalne.
Tak - idz
do kroku 2, Nie  STOP.
Nie - idz
do Kroku 3.
Krok 2. (test optymalności).
Tak - to aktualne rozwiÄ…zanie jest optymalne. Nie - idz
do Kroku 3.
x5 x2
Krok 3. (Wybór zmiennej wchodzącej do bazy) - zmienna x1 .
x0 7 1/3 -1/3
Krok 4. (wybór zmiennej usuwanej z bazy) - - zmienna x5 . Id\
do kroku 5.
RozwiÄ…zanie bazowe dopuszczalne:
x3 3/2 -1/6 2/3
Wartość optymalna funkcji celu:
x1 x2
x4 7/2 1/6 4/3
x0 0 -2 -1
'" x1 7/2 1/6 1/3
x = [x3, x4, x5, x1.x2 ]T = [5, 0, 21, 0, 0]T
x3 5 1 1
'"
3 7 7
x = [x3, x4, x1, x5.x2 ]T = [ , , , 0, 0]T
x0 = 0 RozwiÄ…zanie bazowe dopuszczalne:
x4 0 -1 1 2 2 2
Wartość optymalna funkcji celu: x0 = 7
x5 21 6 2
Wydział Elektroniki Wydział Elektroniki
Wydział Elektroniki Wydział Elektroniki
Technika optymalizacji Technika optymalizacji
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika. Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic Dr in\
. Ewa Szlachcic
Przykład zadania programowania liniowego  metoda prymalna simpleks cd.
- III rozw. bazowe dopuszczalne = rozwiÄ…zanie optymalne.
Krok 2. (test optymalności). Tak - to aktualne rozwiązanie jest optymalne.
x5 x3
x0 31/4 1/4 1/2
x2 9/4 -1/4 3/2
x4 1/2 1/2 -2
x1 11/4 1/4 -1/2
'"
9 1 11
RozwiÄ…zanie bazowe optymalne:
x = [x2, x4, x1, x5.x3]T = [ , , , 0, 0]T
4 2 4
Wartość optymalna funkcji celu:
'"
31
x =
0
4
Wydział Elektroniki
Wydział Elektroniki
Technika optymalizacji
Kierunek EiT III r Potok: Elektronika.
Kierunek EiT III r Potok: Elektronika.
Dr in\
. Ewa Szlachcic
3