Algorytm simpleks1

[ Pobierz całość w formacie PDF ]
Algorytm simpleks
Uniwersaln a metod a rozwi azywania programow liniowych jest algorytm sim-
pleks. Metoda ta polega na badaniu kolejnych rozwi azan bazowych programu
liniowego o postaci kanonicznej w taki sposob, ze
² znajdujemy dowolne rozwi azanie bazowe programu;
² sprawdzamy, czy jest ono optymalne;
² jezeli dane rozwi azanie nie jest optymalne, znajdujemy nastepne rozwi azanie
bazowe lepsze lub przynajmniej nie gorsze niz poprzednie.
Zde¯niujmy program liniowy:
c
1
x
1
+ c
2
x
2
+ ::: + x
n
c
n
! max;
a
11
x
1
+ a
12
x
2
+ ::: + a
1n
x
n
·b
1
;
a
21
x
1
+ a
22
x
2
+ ::: + a
2n
x
n
·b
2
;
:::::::::::::::::::::::::::
a
m1
x
1
+ a
m2
x
2
+ ::: + a
mn
x
n
·b
m
;
x
1
;x
2
;:::;x
n
¸ 0
Mozna zapisac go w postaci macierzowej:
cx
! max;
Ax
·
b
x
¸
0
;
gdzie
A
=
0
@
a
11
a
12
::: a
1n
1
A
;
x
=
0
@
x
1
x
2
:::
x
n
1
A
;
b
=
0
@
b
1
1
A
;
:
Algorytm simpleks polega na badaniu rozwi azan bazowych programu o postaci
kanonicznej.
c
=
¡
c
1
c
2
::: c
n
¢
De¯nicja 1
Model o postaci kanonicznej jest to taki model, w ktorym wszystkie
warunki ograniczaj ace maj a postac rownosci.
Zatem zamieniamy wszystkie nierownosci na rownosci:
² w przypadku nierownosci typu ·do lewych stron warunkow ograniczaj acych
dodajemy tzw. zmienne swobodne, ktore wchodz a do pocz atkowego rozwi azania
bazowego ( w pierwszej tablizy sympleksowej);
1
a
21
a
22
::: a
2n
::: ::: ::: :::
a
m1
a
m2
::: a
mn
b
2
:::
b
n
² w przypadku nierownosci typu ¸ od lewych stron odejmujemy zmienne
swobodne i dodajemy tzw. zmienne sztuczne. W tym przypadku zmienne
sztuczne wchodz a do pierwszej bazy.
Do funkcji celu zmienne swobodne wchodz a ze wspolczynnikami rownymi zeru,
a zmienne sztuczne z tzw. wspolczynnikami M, gdzie M jest liczb a bardzo duz a.
Zmienne swobodne mog a znalezc sie w koncowym rozwi azaniu PL, a zmienne
sztuczne nie mog a, dlatego w funkcji celu, ktora jest maksymalizowana, zmienne
sztuczne wyst epuj a ze wszpolczynnikami ¡M, natomiast w funkcji celu, ktora
jest minimalizowana zmienne sztuczne wyst epuj a ze wspolczynnikami +M.
Macierzowa postac tablicy simpleksowej dla l-tej operacji:
Zmienne bazowe
c
Rozwi azanie
c
bl
x
bl
B
¡
l
A B
¡1
l
B
¡
l
b
z
j
c
b
B
¡
l
A c
b
B
¡1
c
b
B
¡
l
b
l
c
j
¡z
j
c¡c
b
B
¡
l
A
¡c
b
B
¡1
l
Przyklad 1
Firma produkuje dwa wyroby W
1
i W
2
. Ograniczeniem w produkcji
s a zapasy trzech surowcow S
1
, S
2
i S
3
.
Surowce
Zuzycie surowca w jedn.
Zapas surowca (kg)
na 1 szt. wyrobu
W
1
W
2
S
1
2
1
1000
S
2
3
3
2400
S
3
1,5
-
600
Cena (w zl)
30
20
Ustalic rozmiar produkcji wyrobow W
1
i W
2
, ktore zpewniaj a maksymalny
zysk i ich sprzedazy przy istniej acych zapasach surowcow.
Tablica sympleksowa
c
b
c
j
30 20 0 0 0 Rozwi azanie (b
j
)
Zmienne bazowe x
1
x
2
x
3
x
4
x
5
0
x
3
2
1
1
0
0
1000
0
x
4
3
3
0
1
0
2400
0
x
5
1,5 0
0
0
1
600
z
j
0
0
0
0
0
0
c
j
¡z
j
30 20 0
0
0
Zauwazmy, ze A =
0
@
2 3
3 3
1; 5 0
1
A
, I =
0
@
1 0 0
0 1 0
0 0 1
1
A
, b =
0
@
1000
2400
300
1
A
,
2
c =
¡
30 20 0 0 0
¢
, x
b
=
0
@
x
3
x
4
x
5
1
A
, c
b
=
0
@
0
0
0
1
A
.
0
@
1 0 2
1
A
0
@
1 0 ¡
3
1
A
Macierz B
2
ma postac
0 1 3
0 0 1;5
. Wtedy B
¡1
2
=
0 1 ¡2
0 0
2
3
0
@
0 1
1
A
0
@
200
1
A
oraz B
¡
2
¢ A =
0 3
1 0
, B
¡
2
¢ b =
1200
400
, c
b
B
¡
2
A =
¡
30 0
¢
,
¡
¢
oraz c
b
B
¡
2
b = 12000. Wowczas II tablica simplek-
sowa wygl ada nastepuj aco:
c
b
0 0 20
c
j
30 20 0 0 0 Rozwi azanie (b
j
)
Zmienne bazowe x
1
x
2
x
3
x
4
x
5
0
x
3
0
1
1
0 -
4
3
200
0
x
4
0
3
0
1 -2
1200
30
x
1
1
0
0
0
2
3
400
z
j
30 0
0
0 20
12000
c
j
¡z
j
0 20 0
0 -20
Macierz B
3
ma postac
0
@
1 0 2
3 1 3
0 0 1;5
1
A
. Wtedy B
¡
3
=
0
@
1 0 ¡
4
3
¡3 1 2
0 0
1
A
2
3
0
@
0 1
1
A
0
@
200
1
A
oraz B
¡
3
¢ A =
0 0
1 0
, B
¡
3
¢ b =
600
400
, c
b
B
¡
3
A =
¡
30 20
¢
,
¡
¢
oraz c
b
B
¡
3
b = 16000. Wowczas III tablica sim-
pleksowa wygl ada nastepuj aco:
c
b
20 0 ¡
20
3
c
j
30 20 0
0
0
Rozwi azanie (b
j
)
Zmienne bazowe x
1
x
2
x
3
x
4
x
5
20
x
2
0
1
1
0 -
4
3
200
0
x
4
0
0
-3
1
2
600
30
x
1
1
0
0
0
2
3
400
z
j
30 20 20 0 -
20
3
16000
c
j
¡z
j
0
0 -20 0
20
3
0
@
1 0 2
1
A
0
@
1
A
3
0
¡1;5 0; 5 1
1
2
Macierz B
4
ma postac
3 0 3
0 1 1; 5
. Wtedy B
¡
4
=
1
¡
3
0
0
@
0 1
1
A
0
@
600
1
A
oraz B
¡
4
¢ A =
0 0
1 0
, B
¡
4
¢ b =
300
200
, c
b
B
¡
4
A =
¡
30 20
¢
,
3
c
b
B
¡1
2
=
c
b
B
¡1
3
=
1
oraz c
b
B
¡
4
b = 18000. Wowczas IV tablica simplek-
sowa wygl ada nastepuj aco:
c
b
¡
10
3
0
¢
c
j
30 20 0 0 0 Rozwi azanie (b
j
)
Zmienne bazowe x
1
x
2
x
3
x
4
x
5
20
x
2
0
1
-1
2
3
0
600
0
x
5
0
0 -1,5 0,5
1
300
30
x
1
1
0
1
¡
1
3
0
200
z
j
30 20 10
10
3
0
18000
c
j
¡z
j
0
0 -10
¡
1
3
0
4
c
b
B
¡
4
=
10
[ Pobierz całość w formacie PDF ]