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.
Wyszukiwarka
Podobne podstrony:
badania operacyjne, w5 Metoda Simpleks
badania operacyjne, w5 Metoda Simpleks
badania operacyjne wykład 4 (metoda simpleks)
badania operacyjne w4-Metoda Selekcji
badania operacyjne, w2 Metoda Geometryczna
badania operacyjne metoda simplex[1]
badania operacyjne metoda simplex+zagadnienie transportowe+excel 28 11 2010
badania operacyjne metoda simplex(1)
metoda simplex badania operacyjne Projekt!!
Metoda liniowa - szablon, Nauka, Studia, Notatki, Badania operacyjne
metoda graf pl, Zarządzanie Tutystyką Notatki Różne, badania operacyjne
Metoda graficzna, ZIP, Badania operacyjne
PUSTE TABELKI DO ALGORYTMU SIMPLEKS, Studia, badania operacyjne
badania operacyjne, Kamil Wietrzyński, Laboratorium polegało na rowiązaniu 2 zadań dwoma poznanymi m
badania operacyjne, Metoda iteracji prostej Gaussa, Metoda iteracji prostej Gaussa-Jordana
Badania operacyjne wyklad 2 id Nieznany
badania operacyjne 3 id 76767 Nieznany (2)
więcej podobnych podstron