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