II Zadanie programowania liniowego PL
min x0 = cT x
przy ograniczeniach:
A x e" b
x e" 0
dim x=[n*1], dim c=[n*1]
Macierz A odpowiada za współczynniki w m ograniczeniach
dim A=[m x n]
Wektor wyrazów wolnych b odpowiada za prawą stronę ograniczeń
dim b =[m*1]
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
Postać kanoniczna II zadania PL
T
min x0 = c x,
A x e" b,
x e" 0,
T
max - x0 = -c x,
- A x + I xs = -b,
s
x , xs e" 0,
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
Optymalne rozwiÄ…zanie II zadania PL metodÄ… dualnÄ… simpleks
Twierdzenie:
Twierdzenie:
Rozwiązanie bazowe dopuszczalne układu równań Ax=b
jest rozwiązaniem optymalnym II zadania PL, jeśli są spełnione
warunki:
(i) Warunek dualnej dopuszczalności:
yoj e"0 dla j " RN
(ii) Warunek dualnej optymalności
yi0 e" 0 dla i "{1,..., m}
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
Algorytm dualny simpleks
Krok 1. (start). Rozpoczynamy algorytm od znalezienia pierwszej tablicy
dualnie dopuszczalnej. Nale\
y sprawdzić dualną dopuszczalność
yoj e" 0 dla j "RN
rozwiÄ…zania: czy Tak - idz
do Kroku 2, Nie  koniec.
yi0 e" 0
Krok 2. (test optymalności). Czy dla ka\
dego ?
i = 1,..., m
" Tak - to aktualne rozwiÄ…zanie jest optymalne.
" Nie - idz
do Kroku 3.
Krok 3. (Wybór zmiennej usuwanej z bazy). Wybierz jako zmienną usuwaną z
y < 0 .
bazy taką zmienną x dla której
r 0
B
r
xB
Typową regułą jest wybór zmiennej dla której:
r
y = {y , y < 0, i = 1,..., m}
r 0 io i 0
min
j" R
N
Id\
do Kroku 4.
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
Algorytm dualny simpleks c.d.
Krok 4. (wybór zmiennej wprowadzanej do bazy). Wybierz jako zmienną
wchodzącą do bazy taką zmienną dla której
x
k
y0 j
y0k
= max( , yrj < 0).
yrk yrj
Jeśli wiele zmiennych spełnia ten warunek, wybierz arbitralnie jedną z nich.
Id\
do Kroku 5.
Krok 5. (eliminacja). Dokonaj dualnÄ… iteracjÄ™ simpleksowÄ… metodÄ… eliminacji
xB
Gauss a poprzez wprowadzenie do bazy oraz usunięcie
x r
k
Idz
do Kroku 2.
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
Przykład II zadania programowania liniowego  dualna metoda simpleks
min x0 =1x1 +1x2
x"X
+1x1 + 2x2 e" 8
Å„Å‚ üÅ‚
ôÅ‚x
X = :
òÅ‚ 2x1 + 1x2 e" 6, x e" 0ôÅ‚
żł
ôÅ‚ ôÅ‚
+1x1 + 1x2 e" 5
ół þÅ‚
tablica początkowa tablica pośrednia tablica optymalna
-x1 -x3
-x1 -x2
-x4 -x3
-x0 0 1 1
-x0 -4 ½ ½
-X0 -14/3 1/3 1/3
X3 -8 -1 -2
X2 4 ½ -1/2
X2 10/3 1/3 -2/3
X4 -6 -2 -1
x4 -2 -3/2 -1/2
X1 4/3 -2/3 1/3
X5 -5 -1 -1
X5 -1 -1/2 -1/2
X5 -1/3 -1/3 -1/3
tablica dualnie dopuszczalna tablica jeszcze nie optymalna
y20 < 0
yi0 e" 0 dla "i = 1,..., m
yoj e" 0 dla j "RN
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
Przykład II zadania programowania liniowego
cd. dualna metoda simpleks
tablica optymalna I tablica optymalna II
-x5 -x4 -x5 -x3
-X0 -5 1 0
-x0 -5 1 0
X2 3 1 -1
X2 4 -2 1
X1 2 -2 1
x1 1 1 -1
X4 1 -3 1
X3 1 -3 1
T
'" '" '" '" '" '"
îÅ‚ Å‚Å‚
'"
T
1 1 1
RozwiÄ…zanie optymalne I
x1 = x1 x3 x1 x5 śł = [1 4 1 0 0]
ïÅ‚x1 2 4
x0 = 5
ðÅ‚ ûÅ‚
wierzchołek:
'"
1 2 2
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ - 
Å‚Å‚
T
RozwiÄ…zanie optymalne II
'" '" '" '" '" '"
x = ïÅ‚ śł + (1- )ïÅ‚ śł =
îÅ‚ Å‚Å‚
ïÅ‚3 + śł
T
2 2 2 2 2
x2 = x2 x3 x4 x5 śł = [2 3 0 1 0]
ðÅ‚4ûÅ‚ ðÅ‚3ûÅ‚ ðÅ‚ ûÅ‚
ïÅ‚x1
wierzchołek:
ðÅ‚ ûÅ‚
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic Wykład 7 EiT III r. sub-kier. EKA
Przykład III  przykład praktyczny
Minimalizacja strat w procesie cięcia dłu\
yc
Dane procesu cięcia: Zamówienie na 300 kompletów belek
1 zestaw belek składa się z: 4 belek po 2,5 m i 7 belek po 0,7 m
Minimalizacja strat w wyniku cięcia dłu\
yc
Wektor zmiennych decyzyjnych:
2x1 +1x2 + 0x3 e" 1200
Å„Å‚ üÅ‚
min x0 = 0.2x1 + 0.6x2 + 0.3x3
X = :
òÅ‚x 0x1 + 3x2 + 7x3 e" 2400, x e" 0żł
x"X
ół þÅ‚
'" '" '" '"
'"
x = [x , x , x ]T = [600,0,300]T
1 2 3 x = 210
o
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
III Zadanie programowania liniowego PL
max f (x)= cT x
przy ograniczeniach:
A1x d" b1
A2 x e" b2
x e"0
dim x=[n*1], dim c=[n*1]
Macierze A1, A2 odpowiadają za współczynniki w m1 i m2 ograniczeniach
dim A1 =[m 1 * n], dim A2 =[m 2 * n]
Wektory b1, b2 odpowiadają za prawe strony ograniczeń
dim b1=[m1*1], dim b2=[m2*1]
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
Zadanie programowania liniowego dla ograniczeń mniejszościowych i
większościowych
Metoda dwóch faz
I faza - nale\
y znalez
ć pierwsze rozwiązanie bazowe dopuszczalne
poprzez rozwiÄ…zanie zadania pomocniczego
II faza - maksymalizacja funkcji celu x0 dla następnego rozwiązania
bazowego dopuszczalnego wg algorytmu simpleks.
Algorytm simpleks (prymalny)  I faza Krok 1  nie ma mo\
liwości stworzenia
pierwszego rozwiÄ…zania bazowego dopuszczalnego
Krok 1. (start). Rozpoczynamy algorytm od znalezienia pierwszego rozwiÄ…zania
bazowego dopuszczalnego. Nale\
y sprawdzić dopuszczalność
rozwiÄ…zania: czy Tak - idz
do Kroku 2, Nie  STOP.
yi0 e" 0 dla i = 1,..., m
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
I faza metody PL  Nieznane pierwsze rozwiÄ…zanie bazowe dopuszczalne
I.1 - technika zadania pomocniczego
I.2 - technika pomocniczej funkcji celu
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
Ad. I.1 RozwiÄ…zanie zadania pomocniczego PL z funkcjÄ… celu w postaci funkcji
liniowej z0
îÅ‚ Å‚Å‚
A1 It
A =
ïÅ‚ śł
0
ðÅ‚A2 ûÅ‚
Gdzie It jest macierzą jednostkową rzędu t.
A1xN + Itxt = b1
A2xN = b2
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
I faza metody PL cd.
Wprowadzamy wektor zmiennych pomocniczych dim
xÄ… xÄ… = m- t
A1xN + Itxt = b1
A2xN + Im-txÄ… = b2
Rozwiązanie bazowe dopuszczalne układu równań:
xt = b1, xÄ… = b2, xN = 0
Nale\
y znalez
ć inne rozwiązanie bazowe dopuszczalne, w którym
xÄ… =0
lub stwierdzić, \
e takie rozwiÄ…zanie nie istnieje.
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
I faza metody  zadanie pomocnicze PL
- 1x ,
max z0 =
Ä…
x - c x - c x = 0,
0 N N t t
xN , xt , xÄ… e" 0
A1xN + It xt
= b1,
I x = b ,
A2xN +
m - t Ä… 2
Zmienna x0 zawsze pozostaje zmiennÄ… bazowÄ…. RozwiÄ…zaniem poczÄ…tkowym zadania
PL I fazy jest
xt = b1 - A1xN , xÄ… = b2 - A2xN ,
z0 = 1(b2 - A2xN ),
x0 = ctb1 + (cN - ctA1)xN
Oraz
xN = 0
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
Ad.I.2 Pomocnicza funkcja celu
Uproszczona wersja I fazy metoda dwufazowej simpleks  uzyskanie
bazowego rozwiÄ…zania dopuszczalnego
" Jeśli wektor b w początkowej tablicy simpleksowej ma przynajmniej jedną ujemną współrzędną, to tablica
przedstawia niedopuszczalne rozwiÄ…zanie bazowe.
" PoczÄ…tkowÄ… niedopuszczalnÄ… tablicÄ™ simpleksowÄ… mo\
na przekształcić wykorzystując algorytm simpleks.
" Cel  uzyskanie nieujemnych wartości zmiennych pomocniczych.
r Ò! min{yi0, yi0 < 0 dla i = 1,2,..., m }
i
" Nale\
y znalez
ć najmniejszą wartość
" Wybrany wiersz s będzie stanowił pomocniczą funkcję celu , którą nale\
y zmaksymalizować.
" Kolejne kroki metody simpleks powinny być prowadzone do uzyskania dopuszczalnej tablicy simpleks, tzn.
takiej dla której spełniony jest warunek prymalnej dopuszczalności:
yi0 e" 0 dla i = 1,2,..., m
" Koniec I fazy
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
Ad.I.2 Pomocnicza funkcja celu
Uproszczona wersja I fazy metoda dwufazowej simpleks cd.
Krok 1. (start- wybór pomocniczej funkcji celu). Rozpoczynamy algorytm od
s = min{yi0 : yi0 < 0, i = 1,2,..., m}
ys0 < 0
znalezienia wiersza s , dla którego oraz
i
Jeśli brak takiego s ( ) to tablica odpowiada dopuszczalnemu
yi0 e" 0 dla i = 1,2,..., m
rozwiÄ…zaniu bazowemu  nale\
y przejść do II fazy.
Krok 2. (Wybór zmiennej wchodzącej do bazy). Wybierz jako zmienną wchodzącą
xk " RN
ysk < 0
do bazy taką zmienną dla której
Typową regułą jest wybór zmiennej , dla której:
x , k " R
k N
y = {y : y < 0}
0 k sk sk
min
j " R
N
xk
Jeśli jest brak takiej zmiennej ( ) to jest brak
ysk e" 0 dla k " RN
rozwiÄ…zania dopuszczalnego. Jest to problem sprzeczny.
Id\
do Kroku 3.
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
Krok 3. (wybór zmiennej usuwanej z bazy). Wybierz jako zmienną usuwaną z bazy
x ,
taką zmienną dla której
Br
Å„Å‚ üÅ‚
yr0 yio yi0
= minòÅ‚ : i = 1,..., m, > 0żł
yrk i ół yik yik þÅ‚
Jeśli wiele zmiennych spełnia ten warunek, wybierz arbitralnie jedną z nich.
ys0 < 0 i ysk < 0
Taki przypadek zawsze istnieje, poniewa\

Id\
do Kroku 5.
x , i `" R ,
Krok 4. (eliminacja Gauss a). Wyznacz oraz względem zmiennych
x
Bi N
k
x , j " RN - {k}
xB
oraz zmiennej zgodnie z wyprowadzonymi wzorami.
j
r
x = 0, j " RN -{k} i xBr = 0
Podstaw
j
aby otrzymać pierwsze rozwiązanie bazowe dopuszczalne.
Idz
do Kroku 1.
Krok ten czasami nazywa siÄ™ wymianÄ… zmiennej bazowej ( piwotyzacjÄ…).
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
Przykład III zadania programowania liniowego
metoda dwufazowa simpleks
max x0 = 1x1 +6x2
x"X
+ 2x1 + 1x2 e" 2
Å„Å‚ üÅ‚
ôÅ‚x
X = : ,x e" 0ôÅ‚
òÅ‚ - 1x1 + 1x2 d" 3 żł
ôÅ‚ ôÅ‚
+ 1x1 + 1x2 d" 6
ół þÅ‚
I faza II faza cz.1 II faza cz.2
-x1 -x2
-x5 -x2 -x5 -x4
x0 0 -1 -6
x0 6 1 -5 x0 28,5 3,5 2,5
x3 -2 -2 -1
x3 10 2 1 X3 5,5 1,5 -0,5
x4 3 -1 1
x4 9 1 2 X2 4,5 0,5 0,5
x5 6 1 1
X1 1,5 0,5 -0,5
x1 6 1 1
Brak rozwiÄ…zania
I rozwiÄ…zanie bazowe II rozwiÄ…zanie bazowe
dopuszczalnego
dopuszczalne dopuszczalne- rozwiÄ…zanie
optymalne
6
îÅ‚ Å‚Å‚
xB = x0 B1 = 6
1,5
ïÅ‚0śł, îÅ‚ Å‚Å‚
1
xB = x0 B2 = 28,5
ðÅ‚ ûÅ‚
ïÅ‚4,5śł,
1
ðÅ‚ ûÅ‚
T '"
'" '" '" '" '"
'"
îÅ‚ Å‚Å‚
T
1
RozwiÄ…zanie optymalne: x0 = 28,5
x = x2 x3 x4 x5 śł == [1,5 4,5 5,5 0 0]
ïÅ‚x
ðÅ‚ ûÅ‚
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
Przypadki szczególne dla zadania programowania
liniowego
1. Zadanie programowania liniowego PL posiada jedno rozwiÄ…zanie
2. Zadanie programowania liniowego  nieograniczone
3. Zadanie programowania liniowego  posiadające nieskończoną liczbę
rozwiązań optymalnych na zbiorze ograniczonym
4. Zadanie programowania liniowego  posiadające nieskończoną liczbę
rozwiązań optymalnych na zbiorze nieograniczonym
5. Zadanie programowania liniowego  zbiór rozwiązań dopuszczalnych
jest zbiorem pustym - brak rozwiÄ…zania.
Zadania 2,3 i 4  rozwiÄ…zanie II fazy algorytmu PL analogicznie jak w
prymalnej metodzie simpleks.
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA
Przypadki szczególne  zbiór rozwiązań dopuszczalnych jest zbiorem
pustym - brak rozwiÄ…zania
X = Ć
W metodzie dwufazowej simpleks algorytm w I fazie obliczeń nie potrafi stworzyć
pierwszego rozwiązania bazowego dopuszczalnego z powodu braku rozwiązań
dopuszczalnych.
1
Przykład:
max x0 = x1 - x2 - x3
x"X
2
-x1 -x2 -x3
-x1 -x4 -x3
1
Å„Å‚ üÅ‚
x0 0 -1/2 1 1
- x1 + 2x2 + x3 d" 2
x0 x x x x
ôÅ‚ ôÅ‚
2
ôÅ‚ ôÅ‚
x4 2 -1/2 2 1
1
ôÅ‚x
x2 x x x x
X = : - x1 + 2x2 - x3 e" 3, x e" 0ôÅ‚
òÅ‚ żł
2
x5 -3 1/2 -2 1
ôÅ‚ ôÅ‚ x5 -1 0 1 2
x2 - x3 d" 2
ôÅ‚ ôÅ‚
x6 2 0 1 -1 x6 x x x x
ôÅ‚ ôÅ‚
ół þÅ‚
Nie jest spełniony warunek dopuszczalności drugiej tablicy simpleks i jednocześnie druga tablica
wskazuje, \
e jest brak rozwiązań dopuszczalnych.
x2 = -x4 - 2x3 -1
x1, x2, x3, x4 e" 0
Technika optymalizacji Wydział Elektroniki
Dr in\
. Ewa Szlachcic EiT III r. sub-kier. EKA