Metoda Simpleks
Metoda Simpleks
Pierwszym
algorytmem
programowania
liniowego
był
algorytm
simplex,
opublikowany przez George’a Dantziga w
1947 roku.
Algorytm Simpleks realizuje tzw. podejście
local search: zaczyna od dowolnego
wierzchołka wielościanu (zbioru rozwiązań
dopuszczalnych) i w kaŜdej kolejnej iteracji
przemieszcza się do takiego sąsiedniego
wierzchołka, Ŝe wartość funkcji celu
poprawia się (lub przynajmniej nie
pogarsza).
Postać bazowa:
w macierzy A
występuje podmacierz
jednostkowa (oczywiście kwadratowa).
T
FC:
c x
MAX (MIN)
O: Ax
b
b
0
WB: x
0
Z
=
→
=
≥
≥
JeŜeli nie są spełnione warunki brzegowe
na
przykład
jedna
ze
zmiennych
decyzyjnych moŜe przyjmować dowolną
wartość
, to tę zmienną zastępujemy
róŜnicą dwóch dodatkowych zmiennych
nieujemnych:
x
0
≥
R
k
x
∈
*
**
k
k
k
x
x
x
=
−
*
0
k
x
≥
**
0
k
x
≥
Sprowadzenie dowolnego problemu
optymalizacji liniowej do postaci
bazowej:
• jeŜeli po prawej stronie ograniczenia
występuje liczba ujemna, to naleŜy je
pomnoŜyć
obustronnie przez –1 (dla
nierówności oczywiście trzeba zmienić
znak na przeciwny),
• do
lewej
strony
ograniczenia
nierównościowego „
” naleŜy dodać
nieujemną zmienną bilansującą,
• od
lewej
strony
ograniczenia
nierównościowego „
” naleŜy odjąć
nieujemną zmienną bilansującą, a następnie
do lewej strony tego ograniczenia dodać
nieujemną zmienną sztuczną,
≤
≥
• do
lewej
strony
ograniczenia
równościowego
„
”
naleŜy dodać
nieujemną zmienną sztuczną
• zmienne bilansujące wprowadza się do
funkcji celu z zerowymi współczynnikami
=
• zmienne sztuczne wprowadza się
ze
współczynnikami znacznie pogarszającymi
wartość funkcji celu – nie mogą one
wpływać
na
rozwiązanie
problemu
wyjściowego,
czyli
w
rozwiązaniu
optymalnym
muszą
przyjąć
wartości
zerowe
(w
przypadku
maksimum
współczynniki te to „duŜe”
wartości
ujemne, a w przypadku minimum – „duŜe”
wartości dodatnie).
Algorytm metody simpleks
ZałóŜmy,
Ŝ
e
podmacierz
jednostkową
macierzy A tworzy m ostatnich wektorów
kolumnowych:
11
12
1
22
22
2
1
2
1
0
0
0
1
0
0
0
1
A
k
k
m
m
mk
a
a
a
a
a
a
a
a
a
=
…
…
…
…
⋮
⋮
⋱
⋮
⋮
⋮
⋱
⋮
…
…
oczywiście, baza składa się z wektorów:
gdzie:
[
]
1
2
B
a
a
a
k
k
k m
+
+
+
=
…
1
1
0
,
0
a
k
+
=
⋮
2
0
1
,
0
a
k
+
=
⋮
0
0
1
..., a
k m
+
=
⋮
Funkcję celu moŜemy wtedy zapisać jako:
Jak
widać,
wyodrębniliśmy
zmienne
niebazowe
oraz zmienne bazowe
1 1
1
1
...
...
MAX
k k
k
k
k m k m
Z
c x
c x
c
x
c
x
+
+
+
+
=
+ +
+
+ +
→
1
2
,
,...,
k
x x
x
1
2
,
,...,
k
k
k m
x
x
x
+
+
+
Ograniczenia są następujące:
11 1
1
1
1
21 1
2
2
2
1 1
...
...
...
k k
k
k k
k
m
mk k
k m
m
a x
a x
x
b
a x
a
x
x
b
a
x
a
x
x
b
+
+
+
+ +
+
=
+ +
+
=
+ +
+
=
⋮
uzupełnimy je warunkami brzegowymi:
, j=1,2,...,k+m
oraz warunkami nieujemności prawych
stron ograniczeń:
,
i=1,2,...,m
jest
to
tzw.
przedstawienie
bazowe
problemu optymalizacji liniowej
0
j
x
≥
0
i
b
≥
Korzystając teraz z ograniczeń kaŜdą
zmienną bazową wyrazimy tylko przez
zmienne niebazowe:
1
1
11 1
1
2
2
21 1
2
1 1
...
...
...
k
k k
k
k k
k m
m
m
mk k
x
b
a x
a x
x
b
a x
a
x
x
b
a
x
a
x
+
+
+
= −
− −
=
−
− −
=
−
− −
⋮
ZaleŜności te wprowadzamy do funkcji
celu:
1 1
2 2
1 1
11 1
12 2
1
2
2
21 1
22 2
2
1 1
2 2
...
(
...
)
(
...
)
(
...
)
k k
k
k k
k
k k
k m
m
m
m
mk k
Z
c x
c x
c x
c
b
a x
a x
a x
c
b
a x
a
x
a
x
c
b
a
x
a
x
a
x
+
+
+
=
+
+ +
+
−
−
− −
+
−
−
− −
+
−
−
− −
⋮
i po przekształceniach mamy:
1 1
2 2
1
1 11
2 22
1
1
2
1 12
2 22
2
2
1 1
2 2
...
(
...
)
(
...
)
(
...
)
k
k
k m m
k
k
k m m
k
k
k m m
k
k
k
k
k
k m mk
k
Z
c
b
c
b
c
b
c
c
a
c
a
c
a
x
c
c
a
c
a
c
a
x
c
c
a
c
a
c
a
x
+
+
+
+
+
+
+
+
+
+
+
+
=
+
+ +
+
−
−
− −
+
−
−
− −
+
−
−
− −
⋮
definiujemy
wektor
zawierający
współczynniki funkcji celu, znajdujące się
przy zmiennych bazowych
1
2
c
k
k
B
k m
c
c
c
+
+
+
=
⋮
Funkcję celu moŜemy teraz zapisać w
następujący sposób:
1 1
2 2
1
1
1
...
(
)
... (
)
c a
c a
k
k
k m m
T
T
B
k
B
k
k
Z
c b
c
b
c
b
c
x
c
x
+
+
+
=
+
+ +
+
−
+ +
−
11
21
1
1
,
a
m
a
a
a
=
⋮
12
22
2
2
,
a
m
a
a
a
=
⋮
1
2
..., a
k
k
k
mk
a
a
a
=
⋮
oraz
jest macierzą transponowaną do
Iloczyn wektora
i wektora kolumnowego
oznaczymy przez
, czyli:
j=1,2,...,k
co po wstawieniu do wyraŜenia na funkcję
celu daje:
c
T
B
c
B
c
T
B
a
j
j
z
c a
T
j
B
j
z
=
1 1
2 2
1
1
1
2
2
2
...
(
)
(
)
... (
)
k
k
k m m
k
k
k
Z
c b
c
b
c
b
c
z x
c
z x
c
z x
+
+
+
=
+
+ +
+
−
+
−
+ +
−
wprowadzamy jeszcze jedno oznaczenie:
lub macierzowo:
oraz: , j=1,2,...,k
i ostatecznie funkcję celu zapisujemy
następująco:
1 1
2 2
...
k
k
k m m
C
c b
c
b
c
b
+
+
+
=
+
+ +
c b
T
B
C
=
j
j
j
e
c
z
= −
1 1
2
2
...
k
k
Z
C
e x
e x
e x
= +
+
+ +
Rozwiązanie
bazowe
otrzymujemy
przyjmując dla zmiennych niebazowych
wartości zerowe, czyli:
[
]
1
2
0
0
0
x
T
B
m
b
b
b
=
…
…
Biorąc pod uwagę załoŜenia o nieujemności
prawych
stron
ograniczeń,
jest
to
rozwiązanie bazowe dopuszczalne. Wartość
funkcji celu dla tego rozwiązania jest
równa:
( )
x
c b
T
B
B
Z
C
= =
Kryterium optymalności:
JeŜeli
[
]
1
2
0
0
0
x
T
B
m
g
g
g
=
…
…
jest dopuszczalnym rozwiązaniem bazowym
(
dla i=1,2,...,m) problemu
optymalizacji liniowej oraz funkcja celu dla
danego
przedstawienia
bazowego
ma
postać:
przy czym
, j=1,2,...,k
to rozwiązanie jest rozwiązaniem
maksymalizującym funkcję celu.
0
i
g
≥
1 1
2
2
...
k
k
Z
C
e x
e x
e x
= +
+
+ +
0
j
e
≤
x
B
Na podstawie kryterium optymalności
wiadomo, Ŝe znaki współczynników
decydują o tym, czy otrzymane rozwiązanie
bazowe jest optymalne, czy tez nie.
Współczynniki te nazywa się wskaźnikami
optymalności. Dla zmiennych bazowych
wskaźniki optymalności są równe zero.
j
e