Zadanie programowania liniowego PL dla ograniczeń
mniejszościowych
max f (x)= cT x
x"X
Ax d" b
przy ograniczeniach:
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}
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
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 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 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.
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
Rozwiązania bazowe
det B `" 0, dim B = m
B- macierz bazowa nieosobliwa
A = [B, N]
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:
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:
Niezdegenerowanym rozwiązaniem bazowym dopuszczalnym zadania PL nazywamy
rozwiązanie dopuszczalne , w którym nie wszystkie składowe xi
są większe od zera.
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
Extremum zadania programowania liniowego PL
Definicja:
Punkt x nale\
ący do wypukłego zbioru jest punktem wierzchołkowym zbioru
X �" Rn
X, jeśli nie mo\
e być wyra\
ony jako kombinacja liniowa innych punktów zbioru X.
Twierdzenie 5.1
Zbiór wszystkich rozwiązań dopuszczalnych zadania programowania liniowego PL jest
zbiorem wypukłym.
Twierdzenie 5.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.
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
Extremum zadania programowania liniowego PL cd.
Twierdzenie 5.3
f : X R1
Je\
eli funkcja określona na domkniętym i ograniczonym wypukłym
X �" Rn
zbiorze jest ciągła i wypukła, to globalne maksimum funkcji f(x) występuje
w punkcie ekstremalnym (bądz
punktach) zbioru X.
Dowód: Zaprzeczamy tezie:
'" '"
x - dowolne globalne minimum f (x) > f (v)
v  dowolny punkt ekstremalny zbioru X.
'"
x
Zbiór X jest zbiorem zwartym, funkcja f(x) jest ciągła  więc istnieje punkt
vi , i = 1,..., k
- punkty ekstremalne zbioru X .
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
'"
f (x) = f ( vi ) d"
i i
"� "� f (vi ) d" max f (vi )
i
ckd.
i=1 i=1
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
Extremum zadania programowania liniowego PL cd.
Twierdzenie 5.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.
'" '" '"
p
x1, x2 ..... x
Dla p dopuszczalnych bazowych rozwiązań optymalnych, tzn.
Zbiór rozwiązań optymalnych przyjmuje postać:
p p
'"
'"
X = xi , i e" 0,i = 1,..., p
i i
" " = 1
i=1 i=1
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
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 �ł
�ł �ł �ł �ł
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
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 �ł
�ł �ł �ł �ł
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
Wprowadzone oznaczenia:
y0 j
y00 �ł łł
�ł łł
�ł
�ł łł y1 j śł
cB B-1aj - cj �ł śł
�ł łł y10 śł
cB B-1b
�ł
�ł śł oraz
y a" a"
y0 a" a" �ł
j
�ł śł
M
B-1aj śł �ł śł
�ł śł
M
�ł śł
B-1b
�ł �ł
�ł �ł
�ł śł
�ł śł
ymj
�ł śł
�ł �ł
�łym0 �ł
a , j " RN
gdzie oznaczają kolumny macierzy N.
j
x0 = y00 - y0 j xj
"
j"R
xBi = yi0 -
ij j
"y x , dla i = 1,..., m
j"RN
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
Postać początkowej tablicy simpleksowej
- xN
- xN
x0 0 - cN
x0 cBB-1b cBB-1N - cN
xB B-1b B-1N
xB b N
dla przypadku gdy cB=0 tzn. pierwsze rozwiązanie bazowe dopuszczalne odpowiada za
punkt wierzchołkowy x=0.
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
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
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
Polepszanie bazowego rozwiązania dopuszczalnego
�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.
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
Optymalne rozwiązanie zadania programowania liniowego PL metodą
simpleks
Twierdzenie 5.5
Twierdzenie 5.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
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
Pierwsza tablica simpleks-I rozwiązanie bazowe dopuszczalne
... --xx ... --xx ...
... -j xj ... ...
... -k xk ...
...
j k
xx yy ... yyj ... yyk 0k ...
x0 00y00 ... 0y0 j ... 0yk ...
... ... ...
0
0 00 0 j 0
... ... ...
... ... ...
... ... ...
xx yy ... yy ... yy ...
xBi y ... yij ... ikyik ...
... ...
Bi ij
iO
...
iO
Bi ij ik
iO
... ... ...
... ... ...
... ... ...
xx yy0 r0 ... yy ... yy ...
xBr r y0 ... ... ...
... yrj ... rkyrk ...
Br rj
Br r rj rk
... ... ...
... ... ...
... ... ...
xx yy0 ... yy ... yy ...
xBm mym0 ... mj ... ymk ...
... ymj ... mk ...
Bm
Bm m0 mj mk
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
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 ...
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
Algorytm simpleks (prymalny)
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.
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
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ą).
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic
Schemat reguły przeliczenia współczynników zmiennych 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
�ł �ł
Wydział Elektroniki PWr
Technika optymalizacji Wykład 4
EiT III r. subkier. EKA
Dr in\
. Ewa Szlachcic