Zadanie programowania liniowego część II
Wydział Elektroniki
Kier. Automatyka i Robotyka
Studia II st.
dr inŜ. Ewa Szlachcic
Zakład Sterowania i Optymalizacji
Instytut Informatyki, Automatyki i Robotyki
Politechnika Wrocławska
TEORIA I METODY
OPTYMALIZACJI
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Extremum zadania programowania liniowego PL
Twierdzenie 4.1
Zbiór wszystkich rozwiązań dopuszczalnych zadania programowania liniowego PL jest
zbiorem wypukłym.
Definicja 4.5
Punkt x naleŜący do wypukłego zbioru jest punktem wierzchołkowym zbioru
X, jeśli nie moŜe być wyraŜony jako kombinacja liniowa innych punktów zbioru X.
n
R
X ⊂
Dowód:
1. Zakłada się, Ŝe wektor x jest bazowym rozwiązaniem dopuszczalnym. Pokazać, Ŝe x
jest punktem wierzchołkowym zbioru X
2. Zakłada się, Ŝe wektor x jest punktem wierzchołkowym zbioru rozwiązań
dopuszczalnych zadania programowania liniowego. Pokazać, Ŝe wektor x jest bazowym
rozwiązaniem dopuszczalnym.
Twierdzenie 4.2
Rozwiązanie dopuszczalne x zadania programowania liniowego PL jest punktem
wierzchołkowym zbioru rozwiązań dopuszczalnych X wtedy i tylko wtedy gdy
odpowiada mu bazowe rozwiązanie dopuszczalne tzn.:
T
B
x
x
]
0
,
[
=
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Extremum zadania programowania liniowego PL cd.
1
:
R
X
f
→
Twierdzenie 4.3
JeŜeli funkcja , określona na domkniętym i ograniczonym wypukłym
zbiorze , jest ciągła i wklęsła, to globalne minimum funkcji f(x) występuje w
punkcie ekstremalnym (bądź punktach) zbioru X.
Dowód: Zaprzeczamy tezie:
- dowolne globalne minimum
v – dowolny punkt ekstremalny zbioru X.
Zbiór X jest zbiorem zwartym, funkcja f(x) jest ciągła – więc istnieje punkt
∧
x
- punkty ekstremalne zbioru X .
k
i
v
i
,...,
1
, =
KaŜdy punkt , który nie jest punktem ekstremalnym, moŜe być wyraŜony jako
kombinacja wypukła punktów v
i
X
x ∈
1
;
,...,
1
,
0
,
1
1
=
=
≥
=
∑
∑
=
=
∧
k
i
k
i
i
i
i
i
k
i
v
x
µ
µ
µ
Funkcja f(x) jest wypukła więc zachodzi dla dowolnego punktu zachodzi:
X
x ∈
∧
)
(
max
)
(
)
(
)
(
1
1
i
i
k
i
k
i
i
i
i
i
v
f
v
f
v
f
x
f
≥
≥
=
∑
∑
=
=
∧
µ
µ
ckd.
n
R
X ⊂
)
(
)
(
v
f
x
f
<
∧
∧
x
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Extremum zadania programowania liniowego PL
cd.
∧
∧
∧
p
x
x
x
.....
,
2
1
Twierdzenie 4.4
1.
Funkcja celu zadania PL przyjmuje wartość maksymalną w punkcie
wierzchołkowym zbioru rozwiązań dopuszczalnych zadania PL.
2. Jeśli funkcja celu zadania PL przyjmuje wartość maksymalną w więcej niŜ jednym
punkcie wierzchołkowym, to ma tą samą wartość dla kaŜdej kombinacji wypukłej
tych punktów.
Dla p dopuszczalnych bazowych rozwiązań optymalnych, tzn.
Zbiór rozwiązań optymalnych przyjmuje postać:
1
,...,
1
,
0
,
1
1
=
=
≥
=
∑
∑
=
=
∧
∧
p
i
i
i
p
i
i
i
p
i
x
X
λ
λ
λ
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Wprowadzone oznaczenia:
≡
≡
−
−
0
10
00
1
1
0
m
B
y
y
y
b
B
b
B
c
y
M
≡
−
≡
−
−
mj
j
j
j
j
j
B
j
y
y
y
a
B
c
a
B
c
y
M
1
0
1
1
N
j
R
j
a
∈
,
oraz
gdzie oznaczają kolumny macierzy N.
∑
∈
−
=
R
j
j
j
x
y
y
x
0
00
0
∑
∈
=
−
=
N
R
j
j
ij
i
Bi
m
i
dla
x
y
y
x
,...,
1
,
0
Funkcja celu x
0
M funkcji ograniczeń
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Postać początkowej tablicy simpleksowej
N
B
b
B
x
c
N
B
c
b
B
c
x
x
B
N
B
B
N
1
1
1
1
0
−
−
−
−
−
−
].
0
,...,
0
[
=
x
N
b
x
c
x
x
B
N
N
−
−
0
0
dla przypadku gdy c
B
=0 tzn. pierwsze rozwiązanie bazowe dopuszczalne odpowiada za
punkt wierzchołkowy x
0
=
B
c
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Polepszanie rozwiązania bazowego dopuszczalnego
∑
∈
=
−
=
N
R
j
j
ij
i
Bi
m
i
dla
x
y
y
x
,...,
1
,
0
∑
∈
−
=
N
R
j
j
j
x
y
y
x
0
00
0
0
,
0
0
0
≤
↑
↑
≥
k
k
j
y
gdy
x
równieŜ
to
x
gdy
zatem
x
zawsze
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Polepszanie bazowego rozwiązania dopuszczalnego – metoda eliminacji
Gauss’a.
0
,
0
0
>
∈
=
<
ik
N
j
y
oraz
R
k
k
j
pewnego
dla
y
).
0
,
/
(
min
0
,...,
1
>
=
=
ik
ik
i
m
i
rk
y
y
y
θ
{ }
Br
rk
j
k
R
j
rk
rj
rk
r
k
x
y
x
y
y
y
y
x
N
1
0
−
−
=
∑
−
∈
{ }
Br
rk
ik
j
k
R
j
rk
rj
ik
ij
rk
r
ik
i
B
x
y
y
x
y
y
y
y
y
y
y
y
x
N
i
+
−
−
−
=
∑
−
∈
0
0
Gdy mamy nie-zdegenerowane rozwiązanie bazowe dopuszczalne takie, Ŝe
dla przynajmniej jednego i wówczas moŜna z niego otrzymać lepsze bazowe
rozwiązanie dopuszczalne przez wymianę jednej z kolumn macierzy B na
kolumnę macierzy N.
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Polepszona tablica simpleks odpowiada za następne rozwiązanie bazowe
dopuszczalne o większej wartości funkcji celu.
...
/
1
...
/
...
/
...
...
...
/
)
/
(
...
)
/
(
...
...
...
/
...
)
/
(
...
)
/
(
...
...
...
0
0
0
0
0
0
0
0
00
0
rk
rk
rj
rk
r
k
rk
ik
rk
rj
ik
ij
rk
r
ik
i
Bi
rk
k
rk
rj
k
j
rk
r
k
Br
j
y
y
y
y
y
x
y
y
y
y
y
y
y
y
y
y
x
y
y
y
y
y
y
y
y
y
y
x
x
x
−
−
−
−
−
−
−
−
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
Algorytm simpleks dla ograniczeń mniejszościowych
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.
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 wchodzącej do bazy). Wybierz jako zmienną wchodzącą do
bazy taką zmienną
dla której
Typową regułą jest wybór zmiennej jest reguła dla której:
0
0
≥
j
y
N
R
j ∈
N
k
R
k
x
∈
,
.
0
0
<
k
y
{
}
0
,
0
0
0
min
≤
=
∈
j
j
R
j
k
y
y
y
N
k
x
IdŜ do kroku 4.
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 simpleks (prymalny) c.d.
Krok 5. (eliminacja Gauss’a). Wyznacz oraz
względem zmiennych
oraz zmiennej
zgodnie z wyprowadzonym wzorem.
Podstaw
aby otrzymać nowe rozwiązanie bazowe dopuszczalne.
Idź do kroku 2.
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 4. (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.
IdŜ do kroku 5.
,
Br
x
).
0
,
/
(
min
0
,...,
1
>
=
=
ik
ik
i
m
i
rk
y
y
y
θ
r
B
x
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Schemat reguły przeliczenia współczynników w tablicy simpleks
wg metody eliminacji Gauss’a
p - element centralny (główny)
q – dowolny element w wierszu centralnym (głównym)
r – dowolny element w kolumnie centralnej (głównej)
s – dowolny pozostały element
−
−
⇒
p
p
r
p
p
p
rq
s
q
s
r
q
1
Teoria i metody optymalizacji
Dr inŜ. Ewa Szlachcic
Wydział Elektroniki studia II st.
kier. Automatyka i Robotyka
Zadanie programowania liniowego PL dla ograniczeń mniejszościowych
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
2
6
21
x
5
1
-1
0
x
4
1
1
5
x
3
-1
-2
0
x
0
x
2
x
1
Przykład:
ZałoŜenia:
1. Zbiór X rozwiązań dopuszczalnych
2. algorytm simpleks startuje z bazowego dopuszczalnego rozwiązania oraz w
trakcie jego realizacji nie występuje degeneracja
I. Zadanie programowania liniowego PL posiada jedno rozwiązanie
Rozwiązanie bazowe optymalne:
Wartość optymalna funkcji celu:
4
31
]
0
,
4
1
,
0
,
4
9
,
4
11
[
]
.
,
,
,
[
0
5
4
3
2
1
=
=
=
∧
x
x
x
x
x
x
x
T
T
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
0
≠
X