1
Wykład 6
Metoda simpleks_cd.
Tablica simpleks
max
c x
T
→
1
c
2
c
...
k
c
1
k
c
+
2
k
c
+
...
k m
c
+
x
B
B
c
1
x
2
x
…
k
x
1
k
x
+
2
k
x
+
…
k m
x
+
b
1
k
x
+
1
k
c
+
11
a
12
a
...
1k
a
1
0
...
0
1
b
2
k
x
+
2
k
c
+
21
a
22
a
...
2k
a
0
1
...
0
2
b
…
...
...
...
...
...
...
...
...
...
...
k m
x
+
k m
c
+
1
m
c
2
m
a
...
mk
a
0
0
...
1
1
b
j
z
1
z
2
z
...
k
z
1
k
z
+
2
k
z
+
...
k m
z
+
j
j
c
z
−
1
e
2
e
...
k
e
1
k
e
+
2
k
e
+
...
k m
e
+
(
)
x
B
Z
C
=
Przykład 1
Dla danego problemu programowania liniowego zbudować tablicę simpleks.
1
2
3
4
1
2
3
4
1
2
3
4
1
2
3
4
1
2
3
4
( ,
,
,
)
8
9
6
10
3
600
4
5
1200
0,
0,
0,
0
FC:
MAX
O:
WB:
Z x x
x x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
=
+
+
+
→
+
+
+
≤
+
+
+
≤
≥
≥
≥
≥
najpierw sprowadzamy do postaci bazowej:
1
2
3
4
1
2
3
4
5
6
1
2
3
4
5
1
2
3
4
6
1
2
3
4
5
6
( ,
,
,
)
8
9
6
10
0
0
3
600
4
5
1200
0,
0,
0,
0,
0,
0
FC:
MAX
O:
WB:
Z x x
x x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
=
+
+
+
+
+
→
+
+
+
+
=
+
+
+
+
=
≥
≥
≥
≥
≥
≥
2
max
c x
T
→
6
9
6
10
0
0
b
x
B
B
c
1
x
2
x
3
x
4
x
5
x
6
x
5
x
0
1
3
1
1
1
0
600
6
x
0
4
1
1
5
0
1
1200
j
z
0
0
0
0
0
0
j
j
c
z
−
6
9
6
10
0
0
0
Rozwiązaniem bazowym w tej bazie jest
[
]
0 0 0 0 600 1200
x
T
=
i jest to
rozwiązanie bazowe dopuszczalne. Funkcja celu dla tego rozwiązania wynosi 0.
Po zbudowaniu tablicy simpleksowej naleŜy stwierdzić, czy otrzymane rozwiązanie bazowe jest
rozwiązaniem optymalnym. PoniewaŜ wskaźniki optymalności wszystkie są dodatnie lub równe
zero więc to rozwiązanie nie jest rozwiązaniem optymalnym.
Jeśli stwierdzimy, Ŝe rozwiązanie bazowe nie jest optymalne, to w metodzie simpleks
przechodzimy do sąsiedniej bazy, czyli takiej która będzie się róŜniła tylko jedną zmienną ( a
dokładniej: jednym wektorem kolumnowym) w stosunku do bazy wyjściowej. Innymi słowy,
naleŜy określić, która zmienna ma opuścić dotychczasową bazę, a która ma do niej wejść. O tym
decyduje tzw. kryterium wejścia:
•
ze wskaźników optymalności wybieramy największy. Odpowiadającą mu zmienną
wprowadzamy do bazy. JeŜeli największa wartość wskaźnika optymalności odpowiada
więcej niŜ jednej zmiennej, zazwyczaj do nowej bazy wprowadzamy zmienną o
najniŜszym indeksie.
Twierdzenie to jest intuicyjnie zrozumiałe, bo największy wskaźnik optymalności w funkcji celu
najbardziej zwiększa nam wartość tej funkcji, a chcemy jak najszybciej znaleźć maksimum.
3
ZałóŜmy, Ŝe
1
x
jest zmienną wprowadzaną do nowej bazy. Skoro ma to być zmienna bazowa, to
musi przyjąć wartość większą od zera (niebazowe zmienne są równe zero).
Tak więc, zakładamy:
1
0
x
= ∆ >
i chcemy wyznaczyć wartość
∆
. W ograniczeniach
11 1
12 2
1
1
1
21 1
22 2
2
2
2
1 1
2 2
...
...
...
k k
k
k k
k
m
m
mk k
k m
m
a x
a x
a x
x
b
a x
a x
a x
x
b
a x
a
x
a
x
x
b
+
+
+
+
+ +
+
=
+
+ +
+
=
+
+ +
+
=
⋮
zerujemy zmienne niebazowe (z wyjątkiem
1
x
= ∆
):
11
1
1
21
2
2
1
k
k
m
k m
m
a
x
b
a
x
b
a
x
b
+
+
+
∆ +
=
∆
+
=
∆
+
=
⋮
i ze względu na nieujemność zmiennych decyzyjnych moŜemy napisać:
1
1
1
11
2
2
21
1
0
0
0
0
k
k
k m
m
m
x
x
b
a
x
b
a
x
b
a
+
+
+
= ∆ >
= − ∆ ≥
= −
∆ ≥
=
−
∆ ≥
⋮
mamy więc rozwiązać następujący układ nierówności:
1
11
2
21
1
0
0
0
0
m
m
b
a
b
a
b
a
∆ >
− ∆ ≥
−
∆ ≥
−
∆ ≥
⋮
czyli:
11
1
21
2
1
0
m
m
a
b
a
b
a
b
∆ >
∆ ≤
∆ ≤
∆ ≤
⋮
załóŜmy, Ŝe
1
0
i
a
>
, z wyjątkiem
11
0
a
<
; wówczas:
4
1
11
2
21
1
0
m
m
b
a
b
a
b
a
∆ >
∆ ≥
∆ ≤
∆ ≤
⋮
jeŜeli któryś ze współczynników
1
i
a
jest równy zero np.
51
0
a
=
, to w układzie mamy
5
0 b
≤
,
a taka nierówność jest spełniona bezwarunkowo, co oznacza, Ŝe moŜemy ją pominąć przy
rozwiązywaniu układu.
Rozwiązaniem tego układu nierówności jest
1
1
0
min
i
i
i
b
a
≠
< ∆ <
poniewaŜ chodzi nam o jak największą wartość zmiennej wchodzącej do bazy, więc
przyjmujemy maksymalną dopuszczalną wartość
∆
, czyli:
1
1
min
i
i
i
b
a
≠
∆ =
Uogólniając powyŜsze rozwaŜania naleŜy stwierdzić, Ŝe jeŜeli zmienną wprowadzoną do nowej
bazy jest zmienna
j
x
, to obliczamy ilorazy prawych stron ograniczeń przez nieujemne elementy
kolumny odpowiadającej tej zmiennej i spośród nich wybieramy najmniejszy. Jeśli w kolumnie
odpowiadającej zmiennej
j
x
występuje zero lub wartość ujemna, to oczywiście takiego ilorazu
nie liczymy (odpowiednie nierówności nie mają wpływu na rozwiązanie układu).
Niech
2
21
b
a
∆ =
, wartość tę wstawiamy do zaleŜności
5
1
1
1
11
2
2
21
1
0
0
0
0
k
k
k m
m
m
x
x
b
a
x
b
a
x
b
a
+
+
+
= ∆ >
= − ∆ ≥
= −
∆ ≥
=
−
∆ ≥
⋮
i mamy:
2
1
21
2
1
1
11
21
2
2
2
21
21
2
1
21
0
k
k
k m
m
m
b
x
a
b
x
b
a
a
b
x
b
a
a
b
x
b
a
a
+
+
+
=
= −
= −
=
=
−
⋮
jak widać,
2
0
k
x
+
=
, czyli zmienna ta nie będzie zmienna bazową (bo jest równa zero).
Na podstawie przeprowadzonych rozwaŜań moŜna sformułować kryterium wyjścia:
•
Obliczamy ilorazy wyrazów wolnych
i
b
przez elementy (tylko dodatnie) kolumny
zmiennej wchodzącej do bazy. Bazę opuszcza ta zmienna, dla której odpowiadający jej
iloraz jest najmniejszy. JeŜeli minimum jest przyjmowane dla więcej niŜ jednej zmiennej,
to jako zmienną opuszczającą bazę moŜna wybrać dowolną z nich.
W tym miejscu naleŜy podkreślić, Ŝe wyznaczeniu minimum funkcji celu kryterium
optymalności i kryterium wejścia są inne, nie zmienia się natomiast kryterium wyjścia.
Kryterium optymalności jest następujące:
JeŜeli
[
]
1
2
0 0
0
x
T
B
m
g
g
g
=
…
…
jest dopuszczalnym rozwiązaniem bazowym
(
0
i
g
≥
dla i=1,2,...,m) problemu optymalizacji liniowej oraz funkcja celu dla danego
przedstawienia bazowego ma postać:
1 1
2
2
...
k
k
Z
C e x
e x
e x
= +
+
+ +
przy czym
0
j
e
≥
,
j=1,2,...,k ; to rozwiązanie
x
B
jest rozwiązaniem minimalizującym funkcję celu.
O tym, którą zmienną wprowadzamy do nowej bazy w przypadku wyznaczania minimum funkcji
celu decyduje następujące kryterium wejścia:
•
ze wskaźników optymalności wybieramy najmniejszy. Odpowiadającą mu zmienną
wprowadzamy do nowej bazy. JeŜeli najmniejszej wartość wskaźnika optymalności
6
odpowiada więcej niŜ jedna zmienna, zazwyczaj do nowej bazy wprowadzamy zmienną o
najniŜszym indeksie.
Kryterium
optymalności
Kryterium wejścia
Kryterium wyjścia
Maksimum
Wszystkie wskaźniki
optymalności
mniejsze lub równe
zero
Zmienna
odpowiadająca
największemu
wskaźnikowi
optymalności
Zmienna
odpowiadająca
najmniejszemu
ilorazowi
wyrazów
wolnych
przez
dodatnie
elementy
kolumny
wchodzącej do bazy
Minimum
Wszystkie wskaźniki
optymalności większe
lub równe zero
Zmienna
odpowiadająca
najmniejszemu
wskaźnikowi
optymalności
Jak dla maksimum
Przykład 1 cd:
Zmienna
4
x
ma największy wskaźnik optymalności: 10, wprowadzamy ją do bazy (najlepiej
poprawi funkcję celu).
Obliczamy ilorazy wyrazów wolnych przez elementy dodatnie kolumny czwartej:
zm. bazowa
5
x
:
600
600
1
=
, zm. Bazowa
6
x
:
1200
240
5
=
na podstawie kryterium wyjścia bazę opuszcza zmienna
6
x
.
Nowa baza
[
]
1
4
5
B
a
a
=
Budujemy nową tablicę simpleks.
Musimy przebudować ograniczenia:
1
2
3
4
5
1
2
3
4
6
3
600
4
5
1200
x
x
x
x
x
x
x
x
x
x
+
+
+
+
=
+
+
+
+
=
macierz jednostkowa powinna być przy zmiennych
4
x
i
5
x
. Drugie równanie dzielimy przez 5
i wstawiamy
4
x
do pierwszego (drugie piszemy jako pierwsze)
1
2
3
4
6
1
2
3
1
2
3
6
5
4
1
1
1
240
5
5
5
5
4
1
1
1
3
240
600
5
5
5
5
x
x
x
x
x
x
x
x
x
x
x
x
x
+
+
+
+
=
+
+
+
−
−
−
−
+
=
7
skąd
1
2
3
4
6
1
2
3
5
6
4
1
1
1
240
5
5
5
5
1
14
4
1
360
5
5
5
5
x
x
x
x
x
x
x
x
x
x
+
+
+
+
=
+
+
+
−
=
i nowa tablica simpleks ma postać:
max
c x
T
→
6
9
6
10
0
0
b
x
B
B
c
1
x
2
x
3
x
4
x
5
x
6
x
4
x
10
4
5
1
5
1
5
1
0
1
5
240
5
x
0
1
5
14
5
4
5
0
1
1
5
−
360
j
z
8
2
2
10
0
2
j
j
c
z
−
-2
7
4
0
0
-2
2400
Rozwiązaniem bazowym w tej bazie jest
[
]
0 0 0 240 360 0
x
T
=
i jest to rozwiązanie
bazowe dopuszczalne. Funkcja celu dla tego rozwiązania wynosi 2400, jest większa od
poprzedniej.
Powtarzamy procedurę:
Warunek optymalności – nie jest optymalne.
Kryterium wejścia – największy wskaźnik optymalności 7 – odpowiada zmiennej
2
x
-
wprowadzamy ją do nowej bazy.
Kryterium wyjścia - obliczamy ilorazy wyrazów wolnych przez elementy dodatnie kolumny
drugiej:
zm. bazowa
4
x
:
240
1200
1
5
=
, zm. bazowa
5
x
:
360
128.5
14
5
=
najmniejszy iloraz dla zmiennej
5
x
- wyprowadzamy ją z bazy.
Przechodzimy do nowej bazy
[
]
2
2
4
B
a
a
=
8
Budujemy nową tablicę simpleks. Musimy przebudować ograniczenia:
1
2
3
4
5
1
2
3
4
6
3
600
4
5
1200
x
x
x
x
x
x
x
x
x
x
+
+
+
+
=
+
+
+
+
=
macierz jednostkowa powinna być przy zmiennych
2
x
i
4
x
. Drugie równanie dzielimy przez
14
5
i wstawiamy
2
x
do pierwszego (drugie piszemy jako pierwsze)
1
2
3
5
6
1
1
3
5
6
3
4
6
1
4
5
1
1800
14
14
14
14
14
4
1 1800
1
4
5
1
1
1
240
5
5
14
14
14
14
14
5
5
x
x
x
x
x
x
x
x
x
x
x
x
x
+
+
+
−
=
+
−
−
−
−
+
+
+
=
skąd
1
2
3
5
6
1
3
4
5
6
1
4
5
1
1800
14
14
14
14
14
11
1
1
13
1500
14
7
14
70
7
x
x
x
x
x
x
x
x
x
x
+
+
+
−
=
+
+
−
+
=
i nowa tablica simpleks ma postać:
max
c x
T
→
6
9
6
10
0
0
b
x
B
B
c
1
x
2
x
3
x
4
x
5
x
6
x
2
x
9
1
14
1
2
7
0
5
14
1
14
−
900
7
4
x
10
11
14
0
1
7
1
1
14
−
13
70
1500
7
j
z
119
14
9
4
10
5
2
15
14
j
j
c
z
−
5
2
−
0
2
0
5
2
−
15
14
−
3300
9
Rozwiązaniem bazowym w tej bazie jest
900
1500
0
0
0 0
7
7
x
T
=
i jest to rozwiązanie
bazowe dopuszczalne. Funkcja celu dla tego rozwiązania wynosi 3300, jest większa od
poprzedniej.
Powtarzamy procedurę:
Warunek optymalności – nie jest optymalne.
Kryterium wejścia – największy wskaźnik optymalności 2 – odpowiada zmiennej
3
x
-
wprowadzamy ją do nowej bazy.
Kryterium wyjścia - wyrazy wolne dzielimy przez elementy dodatnie kolumny trzeciej:
zm. bazowa
2
x
:
900 7
450
7
2
⋅ =
, zm. bazowa
4
x
:
1500 7
1500
7
1
⋅ =
najmniejszy iloraz dla zmiennej
2
x
- wyprowadzamy ją z bazy.
Przechodzimy do nowej bazy
[
]
3
3
4
B
a a
=
Budujemy nową tablicę simpleks. Musimy przebudować ograniczenia:
macierz jednostkowa powinna być przy zmiennych
3
x
i
4
x
. Pierwsze równanie dzielimy przez
4
14
i wstawiamy
3
x
do drugiego
1
2
3
5
6
1
1
2
5
6
4
5
6
1
14
5
1
450
4
4
4
4
11
1
1
14
5
1
1
13
1500
450
14
7
4
4
4
4
14
70
7
x
x
x
x
x
x
x
x
x
x
x
x
x
+
+
+
−
=
+
−
−
−
−
+
−
+
=
skąd
1
2
3
5
6
1
2
4
5
6
1
14
5
1
450
4
4
4
4
3
1
1
1
150
4
2
4
20
x
x
x
x
x
x
x
x
x
x
+
+
+
−
=
−
+
−
+
=
nowa tablica simpleks ma postać:
10
max
c x
T
→
6
9
6
10
0
0
b
x
B
B
c
1
x
2
x
3
x
4
x
5
x
6
x
3
x
6
1
4
7
2
1
0
4
5
1
4
−
450
4
x
10
3
4
1
2
−
0
1
1
4
−
1
20
150
j
z
9
16
6
10
5
1
j
j
c
z
−
-3
-7
0
0
-5
-1
4200
Rozwiązaniem bazowym w tej bazie jest
[
]
0 0 450 150 0 0
x
T
=
i jest to rozwiązanie
bazowe dopuszczalne. Funkcja celu dla tego rozwiązania wynosi 4200, jest większa od
poprzedniej. Jest to juŜ rozwiązanie optymalne ( wszystkie wskaźniki optymalności są mniejsze
lub równe zero).
Uwaga: przejrzeliśmy 4 bazy, w metodzie selekcji byłoby
6!
15
2! 4!
=
⋅
ewentualnych baz.