TEORIA I METODY
OPTYMALIZACJI
Zadanie programowania liniowego część I
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
Zadanie programowania liniowego PL dla ograniczeń mniejszościowych
max f (x)= cT x
x"X
przy ograniczeniach:
Ax d" b
x e" 0
dim x=n, dim c=n, dim A =[m x n], dim b1=m1,
Postać kanoniczna zadania PL
max x0 = cT x
x"X
X = {x : Ax = b, x e" 0}
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Równowa\
ność zadań programowania matematycznego
I Ograniczenie równościowe mo\
na
gi (x) d" 0
Å„Å‚
zastąpić dwoma ograniczeniami nierów-
gi (x) = 0 Ò!
òÅ‚g (x) e" 0Ò! -gi (x)
ściowymi
i
ół
II Ograniczenie nierównościowe mo\
na
zastąpić ograniczeniem równościowym ,
gi(x) Ä… xn+ j = 0
wprowadzając zmienną uzupełniającą
xn+ j e" 0
III ZmiennÄ… wolnÄ… mo\
na przedstawić
xi " R
jako ró\
nicę dwóch zmiennych nieujemnych
xi = xi+ - xi-
xi+ e" 0, xi- e" 0
gdzie:
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Przykład zadania programowania liniowego
x1 + x2 d" 5
Å„Å‚ üÅ‚
ôÅ‚x
X = : - x1 + x2 d" 0 , x e" 0ôÅ‚
max x0 = 2x1 +1x2
òÅ‚ żł
x"X
ôÅ‚ ôÅ‚
6x1 + 2x2 d" 21
ół þÅ‚
" Liczba zmiennych n=2,
" Liczba ograniczeń m=3.
Postać kanoniczna zadania PL  wprowadzenie zmiennych uzupełniających dla układu m równań
liniowych.
max x0 = 2x1 +1x2 + 0x3 + 0x4 + 0x5
x"X
x1 + x2 + x3 + 0 + 0 = 5
Å„Å‚ üÅ‚
ôÅ‚x ôÅ‚
X = : - x1 + x2 + 0 + x4 + 0 = 0
òÅ‚ żł
ôÅ‚
6x1 + 2x2 + 0 + 0 + x5 = 21ôÅ‚
ół þÅ‚
Kolumny odpowiadajÄ…ce jednostkowej macierzy bazowej B
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Postać kanoniczna macierzowa zadania PL
x1 + x2 d" 5
Å„Å‚ üÅ‚
ôÅ‚x
X = : - x1 + x2 d" 0 , x e" 0ôÅ‚
max x0 = 2x1 +1x2
òÅ‚ żł
x"X
ôÅ‚ ôÅ‚
6x1 + 2x2 d" 21
ół þÅ‚
" Liczba zmiennych n=5,
" Liczba ograniczeń m=3.
xT =[x1,x2,x3,x4,x5]T
cT =[c1,c2,c3,c4,c5]T =[2,1, 0, 0, 0]
max x0 = cT x
x"X
X = {x : Ax = b, x e" 0}
x1
îÅ‚ Å‚Å‚
ïÅ‚x śł
5
îÅ‚ Å‚Å‚
1 1 1 0 0
îÅ‚ Å‚Å‚ 2
ïÅ‚ śł
ïÅ‚ śł
ïÅ‚-1 1 0 1 0śł
ïÅ‚ śł
b = 0 x = x3 e" 0
A =
ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
ïÅ‚
4
ïÅ‚x śł
ïÅ‚ śł
ûÅ‚
6 2 0 0 1ûÅ‚ ðÅ‚21śł
ðÅ‚
ïÅ‚x5 śł
ðÅ‚ ûÅ‚
x1 x2 x3 x4 x5
Kolumny odpowiadajÄ…ce jednostkowej macierzy bazowej B  x3, x4, x5
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Podstawowe definicje
Jeśli dla układu równań liniowych Ax=b spełniony jest warunek rz[Ar]=rz[A]
to mogą zaistnieć trzy następujące przypadki:
1. rz[A] = m = n istnieje jedno rozwiązanie układu Ax=b.
2. rz[A] = n < m istnieje jedno rozwiązanie układu równań, lecz przy tym
(m - n) równań jest zbędnych.
3. rz[A] = m < n istnieje nieskończenie wiele rozwiązań układu Ax=b , jest to
układ nieoznaczony.
Definicja 4.1 macierzy bazowej B
Macierzą bazową B układu równań Ax = b rz[A] = m, n>m nazywamy nieosobliwą
macierz kwadratowÄ… o wymiarach (m*m) utworzonÄ… z liniowo-niezale\
nych kolumn aj
macierzy A.
Definicja 4.2 rozwiÄ…zania bazowego
Rozwiązaniem bazowym układu równań Ax=b rz[A]=m, n>m nazywamy wektor
xb=B-1b utworzony ze zmiennych odpowiadajÄ…cych kolumnom aj macierzy bazowej B.
Składowe wektora bazowego xb są to zmienne bazowe.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
RozwiÄ…zania bazowe
B- macierz bazowa nieosobliwa
A = [B, N]
det B `" 0, dim B = m
N- macierz niebazowa
xB - wektor zmiennych bazowych odpowiadajÄ…cych kolumnom macierz B
x = [xB , xN ]
xN - wektor zmiennych niebazowych odpowiadajÄ…cych kolumnom macierz N
Definicja 4.3
RozwiÄ…zanie bazowe jest rozwiÄ…zaniem bazowym dopuszczalnym zadania programowania
liniowego PL
xB e" 0
jeśli wektor xB jest nieujemny tzn.
Wówczas rozwiązanie bazowe dopuszczalne posiada nie więcej ni\
m dodatnich xi.
x = [xB ,0] xB = B-1b xN = 0
Definicja 4.4
Niezdegenerowanym rozwiÄ…zaniem bazowym dopuszczalnym zadania PL nazywamy
rozwiązanie dopuszczalne , w którym nie wszystkie składowe xi
są większe od zera.
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Pierwsze rozwiÄ…zanie bazowe
xB = B-1b - B-1N xN
x0 =cB B-1b - (cB B-1N - cN ) xN
x0 îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
îÅ‚ Å‚Å‚ cB B-1b cBB-1N - cN
= - xN
ïÅ‚ śł ïÅ‚ śł
ïÅ‚x śł
B-1b B-1N
ðÅ‚ B ûÅ‚
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka
Poszukiwanie rozwiązań bazowych
dopuszczalnych
Pierwsze rozwiÄ…zanie bazowe dopuszczalne
xB = B-1b - B-1N xN
x0 =cB B-1b - (cB B-1N - cN ) xN
x0 îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
îÅ‚ Å‚Å‚ cB B-1b cBB-1N - cN
= - xN
ïÅ‚ śł ïÅ‚ śł
ïÅ‚x śł
B-1b B-1N
ðÅ‚ B ûÅ‚
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
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 w postaci:
x = [0,...,0].
N
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
ół þÅ‚
PoczÄ…tkowa tablica simpleksowa
x1 x2
x0 0 -2 -1
x3 5 1 1
x4 0 -1 1
x5 21 6 2
'"
x = [x , x ]
RozwiÄ…zanie bazowe poczÄ…tkowe:
B N
'"
T T
Wartość początkowa funkcji celu:
x = [x , x , x , x .x ] = [5, 0, 21, 0, 0]
3 4 5 1 2
x = 2* x + x tzn. x = 0.
0 1 2 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
Pierwsza tablica simpleks-I rozwiÄ…zanie bazowe dopuszczalne
... - x ... - xk ...
... --xj ... --xx ...
j
x0 y00 ...... y0 j xj ...... y0k k k ......
xx yy ... yyj ... yyk ...
0 00
0 00 ...... 0 0 j ...... 0 0k ......
... ... ...
xBi y ...... yij ...... yik ......
iO
xx yy ... yy ... yy ...
Bi ij
iO
Bi ...... ij ...... ikik ......
iO
... ... ...
xBr yr0 ...... yrj ...... yrk ......
xx yy0 ... yy ... yy ...
Br r rj
Br r0 ...... rj ...... rkrk ......
... ... ...
xBm ym0 ...... ymj ...... ymk ......
xx yy0 ... yy ... yy ...
Bm m mj mk
... ... ...
Bm m0 mj mk
Teoria i metody optymalizacji Wydział Elektroniki studia II st.
Dr in\
. Ewa Szlachcic kier. Automatyka i Robotyka