Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Programowanie liniowe - podsumowanie
KaŜde bazowe rozwiązanie dopuszczalne jest punktem
wierzchołkowym zbioru X.
Istnieje punkt wierzchołkowy zbioru X w którym funkcja
celu zadania PL przyjmuje maksimum
KaŜdemu punktowi wierzchołkowemu zbioru X odpowiada
m wektorów liniowo niezaleŜnych z danego zbioru n
wektorów związanych z tym punktem.
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Twierdzenie 6.1
Niech będzie dany układ równań liniowych
Ax=B
gdzie jest macierzą mxn, dim x=m, (A)=m, n>m. Jeśli istnieje
rozwiązanie dopuszczalne układu równań tzn. takie, Ŝe x>=0 to
istnieje równieŜ bazowe rozwiązanie dopuszczalne tzn. x=[x
B
,0]
Twierdzenie 6.2
Rozwiązanie dopuszczalne x zadania programowania liniowego
jest punktem wierzchołkowym zbioru rozwiązań dopuszczalnych
X
OL
wtedy i tylko wtedy gdy odpowiada mu bazowe rozwiązanie
dopuszczalne tzn. x=[x
B
,0]
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Rozwiązania optymalne
Twierdzenie 6.3
Twierdzenie 6.3
Je
Je
ś
ś
li zadanie programowania liniowego PL posiada rozwi
li zadanie programowania liniowego PL posiada rozwi
ą
ą
zanie optymalne i
zanie optymalne i
wszystkie rozwi
wszystkie rozwi
ą
ą
zania bazowe s
zania bazowe s
ą
ą
niezdegenerowane to za pomoc
niezdegenerowane to za pomoc
ą
ą
algorytmu
algorytmu
simpleks uzyskuje si
simpleks uzyskuje si
ę
ę
rozwi
rozwi
ą
ą
zanie optymalne po co najwy
zanie optymalne po co najwy
Ŝ
Ŝ
ej
ej
m
n
iteracjach.
iteracjach.
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Przypadki szczególne cd.
Twierdzenie 6.4
Jeśli zadanie PL jest nieograniczone, to istnieją rozwiązania
bazowe dopuszczalne
oraz wektor
taki, Ŝe:
Wówczas zbiór rozwiązań jest pusty.
B
x
K
y
,
min
2
1
0
x
x
x
−
−
=
0
,
1
2
2
1
2
1
2
1
≥
≤
+
−
≤
−
−
x
x
x
x
x
x
m
i
dla
y
i
y
ik
k
,...,
1
0
0
0
=
≤
<
Przykład:
II. Zadanie programowania liniowego – zadanie nieograniczone
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Przypadki szczególne cd.
III. Zadanie programowania liniowego – posiadające nieskończoną ilość
rozwiązań optymalnych na zbiorze ograniczonym
Ten przypadek wystąpi wtedy, gdy moŜna znaleźć tablicę simpleksową, której
odpowiada optymalne rozwiązanie bazowe, takie Ŝe:
i istnieje para
dla której:
Dla przestrzeni o wymiarze n rozwiązanie optymalne jest kombinacją wypukłą
wierzchołków naleŜących do zbioru optymalnego.
i
x
[ ]
p
i
gdy
x
x
i
p
i
i
p
i
i
i
,...,
1
,
1
,
0
,
1
1
1
=
∈
=
=
∑
∑
=
∧
=
∧
∧
λ
λ
λ
n
j
dla
y
oraz
m
i
dla
y
j
i
,...,
1
0
,...,
1
0
0
0
=
≥
=
≥
(
)
{
}
{
}
n
j
m
i
j
i
,...,
1
,
,...,
1
,
,
0
0
0
0
∈
∈
0
0
,
0
0
0
0
0
0
0
>
>
=
j
i
i
j
y
i
y
y
!!
Dla rozwiązania zdegenerowanego, przypadek ten moŜe zaistnieć równieŜ
pod innymi warunkami.
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Przypadki szczególne cd.
III. Przykład gdy jest wiele rozwiązań optymalnych na zbiorze ograniczonym
x
1
x
2
x
0
0
-4
-2
x
3
4
-1
1
x
4
6
2
1
x
4
x
2
x
0
12
2
0
x
3
7
0.5
1.5
x
1
3
0.5
0.5
x
4
x
3
x
0
12
2
0
x
2
4.66 0.33 0.66
x
1
0.66 0.33
0.5
•1 rozwiązanie bazowe optymalne w:
•2 rozwiązanie bazowe optymalne w:
T
T
x
x
]
3
14
,
3
2
[
]
0
,
3
[
2
1
=
=
∧
∧
Zadanie posiada dwa dopuszczalne bazowe rozwiązania optymalne. Odpowiadają one dwóm
wierzchołkom w zbiorze rozwiązań optymalnych.
Zbiór rozwiązań optymalnych
[ ]
{
}
[ ]
.
)
3
14
3
14
(
),
3
7
3
2
(
:
1
,
0
)),
1
(
3
14
0
(
)),
1
(
3
2
3
(
:
1
,
0
,
)
1
(
:
2
1
−
+
=
=
∈
−
+
−
+
=
=
∈
−
+
=
=
∧
λ
λ
λ
λ
λ
λ
λ
λ
λ
x
x
x
x
x
x
x
x
X
2
1
0
2
4
max
x
x
X
x
+
=
∈
x
≥
≤
+
≤
+
−
=
0
,
6
2
4
:
2
1
2
1
x
x
x
x
x
x
X
2
R
2
R
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Przypadki szczególne cd.
IV. Zadanie programowania liniowego – posiadające nieskończoną ilość
rozwiązań optymalnych na zbiorze nieograniczonym
Ten przypadek wystąpi wtedy, gdy moŜna znaleźć tablicę simpleksową, której
odpowiada optymalne rozwiązanie bazowe, takie Ŝe:
dla której, Ŝe istnieje j
0
takie, Ŝe i dla wszystkich „i” zachodzi
y
i0
=0 (degeneracja) bądź
0
0
0
=
j
y
n
j
dla
y
oraz
m
dlai
y
j
i
,...,
1
0
,...,
1
0
0
0
=
≥
=
≥
0
0
0
≤
j
y
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Rozwiązanie optymalne zadania PL przyjmuje postać parametryczną:
Dla n=2 równanie parametryczne prostej,
Dla n=3 równanie parametryczne płaszczyzny itd.
T
x
]
3
7
,
3
2
[
=
∧
Przykład:
Bazowe rozwiązanie optymalne:
Zbiór rozwiązań optymalnych jest półprostą:
≥
+
=
∈
=
∧
∧
0
,
]
3
1
,
3
2
[
:
2
t
t
x
x
R
x
X
T
2
1
0
4
2
max
x
x
X
x
+
−
=
∈
x
≥
≤
+
−
≤
+
−
=
0
,
4
2
1
1
2
:
2
1
2
1
x
x
x
x
x
x
X
x
1
x
2
x
0
0
2
-4
x
3
1
-2
1
x
4
4
-1
2
x
4
x
3
x
0
4
-6
4
x
2
1
-2
1
x
4
2
3
-2
x
4
x
3
x
0
8
2
0
x
2
2.33 0.66 -0,33
x
1
0.66 0.33 -0,66
IV. Zadanie programowania liniowego – posiadające nieskończoną ilość
rozwiązań optymalnych na zbiorze nieograniczonym
cd
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
V. Zadanie programowania liniowego – zbiór rozwiązań dopuszczalnych
jest zbiorem pustym - brak rozwiązania
φ
=
X
2
1
0
4
max
x
x
X
x
+
=
∈
x
≥
−
≤
−
≤
+
=
0
,
2
4
:
2
1
2
1
x
x
x
x
x
x
X
W tej wersji metody prymalnej simpleks algorytm nie potrafi stworzyć pierwszego
rozwiązania bazowego dopuszczalnego z powodu wektora b, który posiada składowe
ujemne.
Przykład:
x
1
x
2
x
0
0
-1
-4
x
3
4
1
1
x
4
-2
1
-1
−
+
=
=
2
4
2
1
b
b
b
m
i
dla
y
i
,...,
1
0
0
=
≥
Nie jest spełniony warunek dopuszczalności pierwszej tablicy simpleks
Krok 1.
(start). Rozpoczynamy algorytm od znalezienia pierwszego rozwiązania bazowego
dopuszczalnego. NaleŜy sprawdzić dopuszczalność
rozwiązania: