Technika optymalizacji
1
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
II 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
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
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:
{
}
m
i
dla
y
io
,...,
1
0
∈
≥
(ii) Warunek optymalności
N
j
R
j
dla
y
∈
∀
≥ 0
0
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
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
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
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.
•NaleŜy znaleźć 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
{
}
m
i
dla
y
y
r
i
i
i
,...,
2
,
1
0
,
min
0
0
=
<
⇒
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
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.
Pomocnicza funkcja celu
Uproszczona wersja I fazy metoda dwufazowej simpleks
cd.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
>
=
=
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
2
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Przykład II 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
1
1
6
x
5
1
-1
3
x
4
-1
-2
-2
x
3
-6
-1
0
x
0
-x
2
-x
1
1
1
6
x
1
2
1
9
x
4
1
2
10
x
3
-5
1
6
x
0
-x
2
-x
5
2
1
0
X
x
x
6
x
1
x
max
+
=
∈
-0,5
0,5
1,5
X
1
0,5
0,5
4,5
X
2
-0,5
1,5
5,5
X
3
2,5
3,5
28,5
x
0
-x
4
-x
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
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
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.
-1
1
0
2
x
6
1
-2
1/2
-3
x
5
1
2
-1/2
2
x
4
1
1
-1/2
0
x
0
-x
3
-x
2
-x
1
x
x
x
x
x
6
2
1
0
-1
x
5
x
x
x
x
x
2
x
x
x
x
x
0
-x
3
-x
4
-x
1
0
,
,
,
,
,
2
1
6
5
4
3
2
1
3
4
5
≥
−
−
−
=
x
x
x
x
x
x
x
x
x
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
III 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
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Postać kanoniczna II zadania PL
0,
,
A
T
≥
≥
=
x
b
x
x
c
x
,
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
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
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
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Teoria dualności dla zadania programowania liniowego PL
x
c
T
x =
0
max
0
≥
≤
x
b
x
A
0
≥
≥
v
c
v
A
T
b
v
v
T
=
0
min
Twierdzenie 7.1 :
Jeśli wektor x jest rozwiązaniem dopuszczalnym dla zadania prymalnego i
wektor v jest rozwiązaniem dopuszczalnym dla zadania dualnego, to wartość
funkcji celu w zadaniu dualnym nie moŜe być mniejsza od wartości funkcji
celu w zadaniu prymalnym.
x
c
b
v
T
T
≥
Technika optymalizacji
3
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Teoria dualności dla zadania PL cd.
∧
∧
v
i
x
∧
∧
=
v
b
x
c
T
T
0
=
v
x
T
Twierdzenie 7.2
Dla pary rozwiązań optymalnych zadania prymalnego i dualnego PL
zachodzi warunek:
Twierdzenie 7.3
Niech (x
r
,x
s
) i ( v
r
, v
s
) będą odpowiednio rozwiązaniami dopuszczalnymi zadania
prymalnego i dualnego, przy czym x
s
i v
s
są wektorami zmiennych dopełniających
do postaci kanonicznej zadania w wektorach rozwiązań.
Wtedy (x
r
,x
s
) i ( v
r
, v
s
) będą odpowiednio rozwiązaniami optymalnymi pary zadań
prymalnego i dualnego, jeśli zachodzi warunek komplementarności zmiennych:
tzn.
0
=
+
r
T
s
s
T
r
v
x
v
x
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Twierdzenie 7.4
Jeśli jedno z pary wzajemnie dualnych zadań programowania liniowego ma
rozwiązanie optymalne, to ma je równieŜ zadanie dualne i obydwa zadania mają
identyczne wartości funkcji celu.
Twierdzenie 7.5
Jeśli zadanie dualne jest nieograniczone, to zadanie prymalne jest sprzeczne.
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Przykład I zadanie prymalne
2
1
0
1
2
max
x
x
X
x
+
=
∈
x
≥
≤
+
≤
+
−
≤
+
=
0
,
21
2
6
0
5
:
2
1
2
1
2
1
x
x
x
x
x
x
x
x
X
≥
≥
+
+
≥
+
−
=
0
,
,
1
2
2
6
:
3
2
1
3
2
1
3
2
1
v
v
v
v
v
v
v
v
v
x
V
3
2
1
0
21
0
5
min
v
v
v
v
V
v
+
+
=
∈
Przykład II System cięcia dłuŜyc
3
2
1
0
2
.
0
6
.
0
3
.
0
min
v
v
v
v
+
+
=
0
,
,
1200
2
1
0
2100
0
3
7
3
2
1
3
2
1
3
2
1
≥
≥
+
+
≥
+
+
v
v
v
v
v
v
v
v
v
2
1
0
1200
2100
max
x
x
X
x
+
=
∈
x
≥
≤
+
≤
+
≤
+
=
0
,
2
.
0
2
0
6
.
0
1
3
3
.
0
0
7
:
2
1
2
1
2
1
x
x
x
x
x
x
x
x
X
Postać wektora rozwiązań:
[
] [
]
5
4
3
2
1
,
,
,
,
v
v
v
v
v
v
v
v
s
r
=
=
[
] [
]
5
4
3
2
1
,
,
,
,
x
x
x
x
x
x
x
x
s
r
=
=
[
] [
]
0
,
,
0
=
⇒
=
r
s
T
s
r
T
v
v
x
x
v
x
zadanie dualne
Technika optymalizacji
Dr inŜ. Ewa Szlachcic
Wydzia
Wydzia
ł
ł
Elektroniki
Elektroniki
Kierunek
Kierunek
EiT
EiT
III r Potok: Elektronika
III r Potok: Elektronika
.
.
Teoria dualności dla zadania PL
cd.
2
1
0
1
2
max
x
x
X
x
+
=
∈
x
≥
≤
+
≤
+
−
≤
+
=
0
,
21
2
6
0
5
1
1
:
2
1
2
1
2
1
x
x
x
x
x
x
x
x
X
2
6
21
x
5
1
-1
0
x
4
1
1
5
x
3
-1
-2
0
x
0
x
2
x
1
Zadanie dualne:
I. Rozwiązanie zadania dualnego metodą simpleks
Rozwiązanie optymalne:
a)
Zadanie dualne
b)
Zadanie prymalne
Wartość optymalna funkcji celu:
1/3
1/6
7/2
x
1
4/3
1/6
7/2
x
4
2/3
-1/6
3/2
x
3
-1/3
1/3
7
x
0
x
2
x
5
-1/2
1/4
11/4
x
1
-2
1/2
1/2
x
4
3/2
-1/4
9/4
x
2
1/2
1/4
31/4
x
0
x
3
x
5
[
]
[
]
3
2
1
5
4
5
4
3
2
1
,
,
,
,
,
,
,
,
v
v
v
v
v
v
x
x
x
x
x
x
↑
=
↑
=
∧
∧
↑
=
↑
=
∧
∧
4
1
,
0
,
2
1
,
0
,
0
0
,
2
1
,
0
,
4
9
,
4
11
v
x
4
31
0
0
=
=
∧
∧
v
x