Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
II Zadanie programowania liniowego PL – dla ograniczeń większościowych
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]
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
∈
≥
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Przykład II zadania programowania liniowego – dualna metoda simpleks
≥
≥
+
+
≥
≥
+
+
+
=
0
,
5
1
1
6
8
1
2
2
1
:
2
1
2
2
1
1
x
x
x
x
x
x
x
x
X
-1
-1
-5
X
5
-1
-2
-6
X
4
-2
-1
-8
X
3
1
1
0
-x
0
-x
2
-x
1
-1/2
-1/2
-1
X
5
-1/2
-3/2
-2
x
4
-1/2
½
4
X
2
½
½
-4
-x
0
-x
3
-x
1
2
1
0
1
1
min
x
x
X
x
+
=
∈
x
-1/3
-1/3
-1/3
X
5
1/3
-2/3
4/3
X
1
-2/3
1/3
10/3
X
2
1/3
1/3
-14/3
-X
0
-x
3
-x
4
tablica początkowa
tablica pośrednia
tablica optymalna
tablica dualnie dopuszczalna
tablica jeszcze nie optymalna
N
oj
R
j
dla
y
∈
≥ 0
0
20
<
y
m
i
dla
y
i
,...,
1
0
0
=
∀
≥
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Przykład II zadania programowania liniowego–dualna metoda simpleks
cd.
]
0
,
1
,
0
,
3
,
2
[
]
,
,
,
,
[
1
5
1
4
1
3
1
2
1
1
1
=
=
∧
x
x
x
x
x
x
1
-3
1
X
4
1
-2
2
X
1
-1
1
3
X
2
0
1
-5
-X
0
-x
3
-x
5
1
-3
1
X
3
-1
1
1
x
1
1
-2
4
X
2
0
1
-5
-x
0
-x
4
-x
5
tablica optymalna I
tablica optymalna II
Rozwiązanie optymalne I
wierzchołek:
Rozwiązanie optymalne II
wierzchołek:
5
0
=
∧
x
]
0
,
0
,
1
,
1
,
1
[
]
,
,
,
,
[
2
5
2
4
2
3
2
2
2
1
2
=
=
∧
x
x
x
x
x
x
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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]
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
=
=
+
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
I faza metody – zadanie pomocnicze PL
=
0
max z
,
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
=
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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.
•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
=
<
⇒
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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 metoda dwufazowej simpleks
cd.
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
>
=
=
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
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
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
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
,
,
,
1
2
4
3
2
1
3
4
2
≥
−
−
−
=
x
x
x
x
x
x
x
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
≥
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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.
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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
1
2
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
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
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