TEORIA I METODY
OPTYMALIZACJI
Zadanie programowania liniowego część II
Wydział Elektroniki
Kier. Automatyka i Robotyka
Studia II st.
dr in\
. Ewa Szlachcic
Zakład Sterowania i Optymalizacji
Instytut Informatyki, Automatyki i Robotyki
Politechnika Wrocławska
Extremum zadania programowania liniowego PL
Definicja 4.5
X ‚" Rn
Punkt x nale\
ący do wypukłego zbioru jest punktem wierzchołkowym zbioru
X, jeśli nie mo\
e być wyra\
ony jako kombinacja liniowa innych punktów zbioru X.
Twierdzenie 4.1
Zbiór wszystkich rozwiązań dopuszczalnych zadania programowania liniowego PL jest
zbiorem wypukłym.
Twierdzenie 4.2
RozwiÄ…zanie dopuszczalne x zadania programowania liniowego PL jest punktem
wierzchołkowym zbioru rozwiązań dopuszczalnych X wtedy i tylko wtedy gdy
odpowiada mu bazowe rozwiÄ…zanie dopuszczalne tzn.:
x = [xB,0]T
Dowód: 1. Zakłada się, \
e wektor x jest bazowym rozwiązaniem dopuszczalnym. Pokazać, \
e x
jest punktem wierzchołkowym zbioru X
2. Zakłada się, \
e wektor x jest punktem wierzchołkowym zbioru rozwiązań
dopuszczalnych zadania programowania liniowego. Pokazać, \
e wektor x jest bazowym
rozwiÄ…zaniem dopuszczalnym.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Extremum zadania programowania liniowego PL cd.
Twierdzenie 4.3
f : X R1
Je\
eli funkcja , określona na domkniętym i ograniczonym wypukłym
zbiorze , jest ciągła i wklęsła, to globalne minimum funkcji f(x) występuje w
X ‚" Rn
punkcie ekstremalnym (bÄ…dz
punktach) zbioru X.
'"
Dowód: Zaprzeczamy tezie:
f (x) < f (v)
'"
x - dowolne globalne minimum
v  dowolny punkt ekstremalny zbioru X.
'"
x
Zbiór X jest zbiorem zwartym, funkcja f(x) jest ciągła  więc istnieje punkt
- punkty ekstremalne zbioru X .
vi , i = 1,..., k
x " X
Ka\
dy punkt , który nie jest punktem ekstremalnym, mo\
e być wyra\
ony jako
kombinacja wypukła punktów vi
k k
'"
x = vi , µi e" 0, i = 1,..., k;
i i
"µ "µ = 1
i=1 i=1
'"
x " X
Funkcja f(x) jest wypukła więc zachodzi dla dowolnego punktu zachodzi:
k k
'"
i i i
f (x) = f ( v ) e" f (v ) e" max f (v )
"µ "µ
i i
i
i=1 i=1
ckd.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Extremum zadania programowania liniowego PL cd.
Twierdzenie 4.4
1. Funkcja celu zadania PL przyjmuje wartość maksymalną w punkcie
wierzchołkowym zbioru rozwiązań dopuszczalnych zadania PL.
2. Jeśli funkcja celu zadania PL przyjmuje wartość maksymalną w więcej ni\
jednym
punkcie wierzchołkowym, to ma tą samą wartość dla ka\
dej kombinacji wypukłej
tych punktów.
'" '" '"
Dla p dopuszczalnych bazowych rozwiązań optymalnych, tzn.
p
x1, x2 .....x
Zbiór rozwiązań optymalnych przyjmuje postać:
p p
'"
'"
X = xi , i e" 0,i =1,..., p
i i
" " =1
i=1 i=1
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Wprowadzone oznaczenia:
y0 j
îÅ‚ Å‚Å‚
y00
îÅ‚ Å‚Å‚
ïÅ‚
îÅ‚ Å‚Å‚ y1 j śł
cB B-1aj - cj ïÅ‚ śł
îÅ‚ Å‚Å‚ y10 śł
cB B-1b
ïÅ‚
y a" a"
ïÅ‚ śł
ïÅ‚
j
y0 a" a"
oraz
ïÅ‚ śł
M
B-1aj śł ïÅ‚ śł
ïÅ‚ śł
ïÅ‚ śł
M
ðÅ‚ ûÅ‚
B-1b
ðÅ‚ ûÅ‚
ïÅ‚ śł
ïÅ‚ śł
ymj
ïÅ‚ śł
ðÅ‚ ûÅ‚
ðÅ‚ym0 ûÅ‚
gdzie oznaczajÄ… kolumny macierzy N.
aj , j " RN
Funkcja celu x0
x0 = y00 -
"y xj
0 j
j"R
M funkcji ograniczeń
xBi = yi0 -
ij j
"y x , dla i = 1,..., m
j"RN
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Postać początkowej tablicy simpleksowej
- xN
- xN
x0 0 - cN
x0 cBB-1b cBB-1N - cN
cB = 0
xB b N
xB B-1b B-1N
dla przypadku gdy cB=0 tzn. pierwsze rozwiÄ…zanie bazowe dopuszczalne odpowiada za
punkt wierzchołkowy x
x = [0,...,0].
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Polepszanie rozwiÄ…zania bazowego dopuszczalnego
x0 = y00 -
0 j j
"y x
j"RN
zawsze xj e" 0,
zatem gdy xk ę! to równie\
x0 Ä™! gdy y0k d" 0
xBi = yi0 -
ij j
"y x , dla i = 1,...,m
j"RN
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Polepszanie bazowego rozwiÄ…zania dopuszczalnego  metoda eliminacji
Gauss a.
¸rk = min(yi0 / yik, yik > 0).
i=1,...,m
y
y 1
rj
r 0
x = - x - x
k j Br
"
y y y
rk rk rk
j " R - {k }
N
yik y
ëÅ‚ öÅ‚ ëÅ‚ öÅ‚
yik y yik
rj
r 0
ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
x = yi 0 - - yij - x + x
Bi j Br
"
ìÅ‚ ìÅ‚ ÷Å‚
yrk ÷Å‚ y y
rk rk
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚
j" R -{k }
N
Gdy mamy nie-zdegenerowane rozwiÄ…zanie bazowe dopuszczalne takie, \
e
y0 j < 0 dla pewnego j = k, k " RN oraz yik > 0
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.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Polepszona tablica simpleks odpowiada za następne rozwiązanie bazowe
dopuszczalne o większej wartości funkcji celu.
... -xj ... -xBr ...
x0 y00-(y0kyr0/yrk) ... y0j-(y0kyrj/yrk) ... -y0k/yrk
... ... ...
xBi yi0-(yikyr0/yrk) ... yij-(yikyrj/yrk) -yik/yrk
... ... ...
xk yr0/yrk ... yrj/yrk ... 1/yrk ...
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Optymalne rozwiÄ…zanie zadania programowania liniowego PL metodÄ…
simpleks
Twierdzenie 4.5
Twierdzenie 4.5
Rozwiązanie bazowe dopuszczalne układu równań Ax=b
jest rozwiązaniem optymalnym zadania PL, jeśli są spełnione dwa warunki:
(i) Warunek prymalnej dopuszczalności:
yio e" 0 dla i "{1,..., m}
(ii) Warunek optymalności
y0 j e" 0 dla "j " RN
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Algorytm simpleks dla ograniczeń mniejszościowych
Krok 1. (start). Rozpoczynamy algorytm od znalezienia pierwszego rozwiÄ…zania
bazowego dopuszczalnego. Nale\
y sprawdzić dopuszczalność
yi0 e" 0 dla i = 1,..., m
rozwiÄ…zania: czy Tak - idz
do kroku 2, Nie  STOP.
Krok 2. (test optymalności). Czy dla ka\
dego j " RN ?
y0 j e" 0
" Tak - to aktualne rozwiÄ…zanie jest optymalne.
" Nie - idz
do kroku 3.
Krok 3. (Wybór zmiennej wchodzącej do bazy). Wybierz jako zmienną wchodzącą do
x , k " R y < 0 .
bazy taką zmienną dla której
k N
0 k
xk
Typową regułą jest wybór zmiennej jest reguła dla której:
y = {y , y d" 0}
0 k 0 j 0 j
min
j" R
N
Id\
do kroku 4.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Algorytm simpleks (prymalny) c.d.
Krok 4. (wybór zmiennej usuwanej z bazy). Wybierz jako zmienną usuwaną z bazy
taką zmienną dla której
x ,
Br
¸rk = min(yi0 / yik, yik > 0).
i=1,...,m
Jeśli wiele zmiennych spełnia ten warunek, wybierz arbitralnie jedną z nich.
Id\
do kroku 5.
x , i `" R ,
Krok 5. (eliminacja Gauss a). Wyznacz oraz względem zmiennych
xk
Bi N
x , j " RN - {k}
xB
oraz zmiennej zgodnie z wyprowadzonym wzorem.
j
r
Podstaw
x = 0, j " RN -{k} i xBr = 0
j
aby otrzymać nowe rozwiązanie bazowe dopuszczalne.
Idz
do kroku 2.
Krok ten czasami nazywa siÄ™ wymianÄ… zmiennej bazowej ( piwotyzacjÄ…).
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Schemat reguły przeliczenia współczynników w tablicy simpleks
wg metody eliminacji Gauss a
p - element centralny (główny)
q  dowolny element w wierszu centralnym (głównym)
r  dowolny element w kolumnie centralnej (głównej)
s  dowolny pozostały element
1 q
îÅ‚ Å‚Å‚
ïÅ‚ śł
p q
îÅ‚ Å‚Å‚
p p
śł
ïÅ‚r sśł Ò! ïÅ‚ r
ïÅ‚- s - rq śł
ðÅ‚ ûÅ‚
ïÅ‚ śł
p p
ðÅ‚ ûÅ‚
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Zadanie programowania liniowego PL dla ograniczeń mniejszościowych
Zało\
enia:
X `" 0
1. Zbiór X rozwiązań dopuszczalnych
2. algorytm simpleks startuje z bazowego dopuszczalnego rozwiÄ…zania oraz w
trakcie jego realizacji nie występuje degeneracja
I. Zadanie programowania liniowego PL posiada jedno rozwiÄ…zanie
x1 + x2 d" 5
Å„Å‚ üÅ‚
max x0 = 2x1 +1x2 X = ôÅ‚x : - x1 + x2 d" 0 , x e" 0ôÅ‚
òÅ‚ żł
x"X
ôÅ‚ ôÅ‚
6x1 + 2x2 d" 21
ół þÅ‚
Przykład:
x5 x2
x5 x3
x1 x2
x0 7 1/3 -1/3 x0 31/4 1/4 1/2
x0 0 -2 -1
x2 9/4 -1/4 3/2
x3 3/2 -1/6 2/3
x3 5 1 1
x4 1/2 1/2 -2
x4 7/2 1/6 4/3
x4 0 -1 1
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
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka