Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kier. EiT ESA III r
.
.
II Zadanie programowania liniowego PL
przy ograniczeniach
:
x
c
T
x
0
min
0
x
b
x
A
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
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kier. EiT ESA III r
.
.
Postać kanoniczna II zadania PL
0,
,
A
T
x
b
x
I
x
x
c
x
s
s
,
min
0
0,
,
A
s
s
T
x
x
b
x
I
x
x
c
x
s
,
-
,
-
max
0
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kier. EiT ESA III r
.
.
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:
N
oj
R
j
dla
y
0
(ii) Warunek dualnej optymalności
m
i
dla
y
i
,...,
1
0
0
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kier. EiT ESA III r
.
.
Algorytm dualny simpleks
Krok 1
. (start). Rozpoczynamy algorytm od znalezienia
pierwszej tablicy dualnie dopuszczalnej. Należy sprawdzić
dualną dopuszczalność
rozwiązania: czy Tak - idź do Kroku 2,
Nie – koniec.
Krok 2.
(test optymalności). Czy
dla każdego
?
• Tak - to aktualne rozwiązanie
jest optymalne.
•
Nie - idź do Kroku 3.
Krok 3.
(Wybór zmiennej usuwanej z bazy). Wybierz jako
zmienną usuwaną z bazy taką zmienną
dla której
Typową regułą jest wybór zmiennej dla której:
0
0
i
y
m
i
,...,
1
r
B
x
.
0
0
r
y
m
i
y
y
y
i
io
R
j
r
N
,...,
1
,
0
,
0
0
min
r
B
x
Idż do Kroku 4.
N
oj
R
j
dla
y
0
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kier. EiT ESA III r
.
.
Algorytm dualny simpleks c.d.
Krok 5. (eliminacja). Dokonaj dualną iterację simpleksową metodą
eliminacji
Gauss’a poprzez wprowadzenie do bazy oraz usunięcie
Idź do Kroku 2.
k
x
Krok 4. (wybór zmiennej wprowadzanej do bazy). Wybierz jako
zmienną wchodzącą do bazy taką zmienną
dla której
Jeśli wiele zmiennych spełnia ten warunek, wybierz arbitralnie
jedną z nich.
Idż do Kroku 5.
k
x
).
0
,
(
max
0
0
rj
rj
j
rk
k
y
y
y
y
y
r
B
x
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kier. EiT ESA III r
.
.
Przykład II zadania programowania liniowego – dualna metoda
simpleks
0
,
3
1
1
6
6
1
2
2
1
:
2
1
2
2
1
1
x
x
x
x
x
x
x
x
X
-x
1
-x
2
-x
0
0
1
1
X
3
-6
-1
-2
X
4
-6
-2
-1
X
5
-3
-1
-1
-x
1
-x
3
-x
0
-3
½
½
X
2
3
½
-1/2
x
4
-3
-3/2
-1/2
X
5
0
-1/2
-1/2
2
1
0
1
1
min
x
x
X
x
x
-x
4
-x
3
-X
0
-4
1/3
1/3
X
2
2
1/3
-2/3
X
1
2
-2/3
1/3
X
5
1
-1/3
-1/3
tablica
początkowa
tablica
pośrednia
tablica
optymalna
tablica dualnie
dopuszczalna
tablica jeszcze nie
optymalna
tablica z rozwiązaniem
optymalnym
N
oj
R
j
dla
y
0
0
20
y
m
i
dla
y
i
,...,
1
0
0
Rozwiązanie
optymalne:
T
T
x
x
x
x
x
x
1
0
0
2
2
5
4
3
2
1
4
0
x
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kier. EiT ESA III r
.
.
III Zadanie programowania liniowego PL
przy ograniczeniach
:
x
c
x
T
f
max
0
2
2
1
1
x
b
x
A
b
x
A
dim x=[n*1], dim c=[n*1]
Macierze A
1
, A
2
odpowiadają za współczynniki w m
1
i m
2
ograniczeniach
dim A
1
=[m
1
* n], dim A
2
=[m
2
* n]
Wektory b
1
, b
2
odpowiadają za prawe strony ograniczeń
dim b
1
=[m
1
*1], dim b
2
=[m
2
*1]
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kier. EiT ESA III r
.
.
Zadanie programowania liniowego dla ograniczeń
mniejszościowych i większościowych
I faza - należy znaleźć pierwsze rozwiązanie bazowe
dopuszczalne poprzez rozwiązanie zadania pomocniczego
II faza - maksymalizacja funkcji celu x
0
dla następnego
rozwiązania bazowego dopuszczalnego wg algorytmu simpleks.
Metoda dwóch faz
Krok 1
. (start). Rozpoczynamy algorytm od znalezienia
pierwszego rozwiązania bazowego dopuszczalnego. Należy
sprawdzić dopuszczalność
rozwiązania: czy Tak - idź do Kroku 2,
Nie – STOP.
m
i
dla
y
i
,...,
1
0
0
Algorytm simpleks (prymalny) – I faza Krok 1 – nie ma możliwości
stworzenia pierwszego rozwiązania bazowego dopuszczalnego
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kier. EiT ESA III r
.
.
I faza metody PL – Nieznane pierwsze rozwiązanie bazowe
dopuszczalne
I.1 - technika zadania pomocniczego
I.2 - technika pomocniczej funkcji celu
Ad. I.1 Rozwiązanie zadania pomocniczego PL z funkcją celu w
postaci funkcji liniowej z
0
0
A
I
A
A
2
t
1
Gdzie I
t
jest macierzą jednostkową
rzędu t.
2
N
2
1
t
t
N
1
b
x
A
b
x
I
x
A
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kier. EiT ESA III r
.
.
I faza metody PL cd.
Wprowadzamy wektor zmiennych pomocniczych dim
= m- t
x
α
x
2
b
x
I
x
A
b
x
I
x
A
α
t
m
N
2
1
t
t
N
1
Rozwiązanie bazowe dopuszczalne układu równań:
0
,
,
2
1
N
t
x
b
x
b
x
Należy znaleźć inne rozwiązanie bazowe dopuszczalne,
w którym
lub stwierdzić, że takie rozwiązanie nie istnieje.
0
x
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kier. EiT ESA III r
.
.
I faza metody – zadanie pomocnicze PL
0
maxz
,
1x
α
t
t
N
N
0
x
c
x
c
x
,
0
t
t
N
1
x
I
x
A
,
b
1
N
2
x
A
,
2
α
t
m
b
x
I
0
,
,
x
x
x
t
N
Zmienna x
0
zawsze pozostaje zmienną bazową. Rozwiązaniem początkowym
zadania PL I fazy jest
Oraz
N
1
t
N
1
t
0
N
2
2
0
N
2
2
α
N
1
1
t
)x
A
c
(c
b
c
x
),
x
A
1(b
z
,
x
A
b
x
,
x
A
b
x
0
x
N
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kier. EiT ESA III r
.
.
Ad.I.2 Pomocnicza funkcja celu
Uproszczona wersja I fazy metody dwufazowej
simpleks – uzyskanie bazowego rozwiązania
dopuszczalnego
m
i
dla
y
y
y
i
i
i
so
,...,
2
,
1
0
,
min
0
0
•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 bazowych
•Należy znaleźć wiersz s, dla którego współczynnik y
io
przyjmuje 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:
m
i
dla
y
i
,...,
2
,
1
0
0
•Koniec I fazy
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kier. EiT ESA III r
.
.
Krok 1. (start- wybór pomocniczej funkcji celu). Rozpoczynamy
algorytm od znalezienia wiersza s , dla którego oraz
Krok 2. (Wybór zmiennej wchodzącej do bazy). Wybierz jako zmienną
wchodzącą do bazy taką zmienną
dla której
Typową regułą jest wybór zmiennej , dla której:
0
sk
y
N
k
R
x
N
k
R
k
x
,
0
:
min
0
sk
sk
R
j
k
y
y
y
N
k
x
Idż do Kroku 3.
N
sk
R
k
dla
y
0
0
0
s
y
m
i
y
y
s
i
i
i
,...,
2
,
1
,
0
:
min
0
0
Jeśli brak takiego s ( ) to tablica odpowiada
dopuszczalnemu rozwiązaniu bazowemu – należy przejść do II fazy.
m
i
dla
y
i
,...,
2
,
1
0
0
Jeśli jest brak takiej zmiennej ( ) to jest brak
rozwiązania dopuszczalnego. Jest to problem sprzeczny.
Ad.I.2 Pomocnicza funkcja celu
Uproszczona wersja I fazy metody dwufazowej
simpleks
cd.
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kier. EiT ESA III r
.
.
0
,
,...,
1
:
min
0
0
ik
i
ik
io
i
rk
r
y
y
m
i
y
y
y
y
Krok 4. (eliminacja Gauss’a). Wyznacz oraz
względem zmiennych
oraz zmiennej
zgodnie z wyprowadzonymi wzorami.
Podstaw
aby otrzymać pierwsze rozwiązanie bazowe dopuszczalne.
Idź do Kroku 1.
Krok ten czasami nazywa się wymianą zmiennej bazowej ( piwotyzacją).
k
x
,
,
N
Bi
R
i
x
}
{
,
k
R
j
x
N
j
0
i
}
{
,
0
Br
N
j
x
k
R
j
x
Krok 3. (wybór zmiennej usuwanej z bazy). Wybierz jako zmienną
usuwaną z bazy taką zmienną
dla której
Jeśli wiele zmiennych spełnia ten warunek, wybierz arbitralnie jedną z
nich.
Taki przypadek zawsze istnieje, ponieważ
Idż do Kroku 5.
,
Br
x
r
B
x
0
0
0
sk
s
y
i
y
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kier. EiT ESA III r
.
.
Przykład III zadania programowania liniowego
metoda dwufazowa simpleks
0
x
,
6
x
1
x
1
3
2
x
1
x
1
x
1
x
2
:
x
X
2
1
2
2
1
1
-x
1
-x
2
x
0
0
-1
-6
x
3
-2
-2
-1
x
4
3
-1
1
x
5
6
1
1
-x
5
-x
2
x
0
6
1
-5
x
3
10
2
1
x
4
9
1
2
x
1
6
1
1
2
1
0
X
x
x
6
x
1
x
max
-x
5
-x
4
x
0
28,
5
3,5
2,5
X
3
5,5
1,5
-0,5
X
2
4,5
0,5
0,5
X
1
1,5
0,5
-0,5
I faza
II faza cz.1
II faza cz.2
Brak rozwiązania
dopuszczalnego
I rozwiązanie bazowe
dopuszczalne
II rozwiązanie bazowe
dopuszczalne-
rozwiązanie optymalne
6
x
,
0
6
x
1
1
B
0
B
Rozwiązanie
optymalne:
T
T
x
x
x
x
x
x
0
0
5
,
5
5
,
4
5
,
1
5
4
3
2
1
5
,
28
0
x
5
,
28
,
5
,
4
5
,
1
2
1
0
B
B
x
x
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
Kier. EiT ESA III r
.
.
Przypadki szczególne – zbiór rozwiązań
dopuszczalnych jest zbiorem pustym - brak rozwiązania
X
3
2
1
0
2
1
max
x
x
x
X
x
x
0
,
2
3
2
2
1
2
2
2
1
:
3
2
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
x
X
W metodzie dwufazowej simpleks algorytm w I fazie obliczeń nie potrafi
stworzyć pierwszego rozwiązania bazowego dopuszczalnego z powodu braku
rozwiązań dopuszczalnych.
Przykład:
Nie jest spełniony warunek dopuszczalności drugiej tablicy simpleks i jednocześnie druga
tablica wskazuje, że jest brak rozwiązań dopuszczalnych.
-x
1
-x
2
-x
3
x
0
0
-1/2
1
1
x
4
2
-1/2
2
1
x
5
-3
1/2
-2
1
x
6
2
0
1
-1
-x
1
-x
4
-x
3
x
0
x
x
x
x
x
2
x
x
x
x
x
5
-1
0
1
2
x
6
x
x
x
x
0
,
,
,
,
,
1
2
6
5
4
3
2
1
3
4
5
x
x
x
x
x
x
x
x
x