Algorytm simpleks
Uniwersalna,metoda,rozwiazywania programś liniowych jest algorytm sim-
ow
,
pleks. Metoda ta polega na badaniu kolejnych rozwiazaś bazowych programu
n
,
liniowego o postaci kanonicznej w taki sposś ze
ob, _
�znajdujemy dowolne rozwiazanie bazowe programu;
,
�sprawdzamy, czy jest ono optymalne;
�jezeli dane rozwiazanie nie jest optymalne, znajdujemy nastepne rozwiazanie
_
, , ,
bazowe lepsze lub przynajmniej nie gorsze niz poprzednie.
_
ZdeŻniujmy program liniowy:
c1x1 +c2x2 +:::+xncn!max;
a11x1 +a12x2 +:::+a1nxn�b1;
a21x1 +a22x2 +:::+a2nxn�b2;
:::::::::::::::::::::::::::
am1x1 +am2x2 +:::+amnxn�bm;
x1;x2;:::;xn�0
Mozna zapisaś go w postaci macierzowej:
_ c
cx!max;
Ax�b
x�0;
gdzie
0 1 0 1 0 1
a11 a12 ::: a1n x1 b1
B C B C B C
C; C; C;
A =B a21 a22 ::: a2n x =B x2 b =B b2
@ A @ A @ A
::: ::: ::: ::: ::: :::
am1 am2 ::: amn xn bn
Ą ó
c = c1 c2 ::: cn :
Algorytm simpleks polega na badaniu rozwiazaś bazowych programu o postaci
n
,
kanonicznej.
DeŻnicja 1 Model o postaci kanonicznej jest to taki model, w ktś wszystkie
orym
warunki ograniczajace maja, postaś rś sci.
c ownoś
,
Zatem zamieniamy wszystkie nierś sci na rś sci:
ownoś ownoś
�w przypadku nierś sci typu�do lewych stron warunkś ograniczajacych
ownoś ow
,
dodajemy tzw. zmienne swobodne, ktś wchodza,do poczatkowego rozwiazania
ore
, ,
bazowego ( w pierwszej tablizy sympleksowej);
1
�w przypadku nierś sci typu�od lewych stron odejmujemy zmienne
ownoś
swobodne i dodajemy tzw. zmienne sztuczne. W tym przypadku zmienne
sztuczne wchodza, do pierwszej bazy.
Do funkcji celu zmienne swobodne wchodza, ze wspślczynnikami rś zeru,
o� ownymi
a zmienne sztuczne z tzw. wspślczynnikami M, gdzieM jest liczba, bardzo duza.
o� _
,
Zmienne swobodne moga,znaleśś sie, w koś rozwiazaniu PL, a zmienne
zc ncowym
,
sztuczne nie moga, dlatego w funkcji celu, ktś jest maksymalizowana, zmienne
ora
,
sztuczne wystepuja, ze wszpślczynnikamiĄM, natomiast w funkcji celu, ktś
o� ora
,
jest minimalizowana zmienne sztuczne wystepuja, ze wspślczynnikami +M.
o�
,
Macierzowa postaś tablicy simpleksowej dla l-tej operacji:
c
Zmienne bazowe c Rozwiazanie
,
Ą1 Ą1
cbl xbl Bl A BlĄ1 Bl b
Ą1 Ą1 Ą1
zj cTBl A cTBl cTBl b
b b b
Ą1
cjĄzj cĄcTBlĄ1A ĄcTBl
b b
Przyk� 1 Firma produkuje dwa wyrobyW1 iW2. Ograniczeniem w produkcji
lad
sa, zapasy trzech surowcś S1, S2 i S3.
ow
Surowce Zu_ surowca w jedn. Zapas surowca (kg)
zycie
na 1 szt. wyrobu
W1 W2
S1 2 1 1000
S2 3 3 2400
S3 1,5 - 600
Cena (w z� 30 20
l)
Ustaliś rozmiar produkcji wyrobś W1 i W2, ktś zpewniaja, maksymalny
c ow ore
zysk i ich sprzedazy przy istniejacych zapasach surowcś
_ ow.
,
Tablica sympleksowa
cb cj 30 20 0 0 0 Rozwiazanie (bj)
,
Zmienne bazowe x1 x2 x3 x4 x5
0 x3 2 1 1 0 0 1000
0 x4 3 3 0 1 0 2400
0 x5 1,5 0 0 0 1 600
zj 0 0 0 0 0 0
cjĄzj 30 20 0 0 0
0 1 0 1 0 1
2 3 1 0 0 1000
A,I A, A,
Zauwazmy, zeA=@ 3 3 =@ 0 1 0 b=@ 2400
_ _
1;5 0 0 0 1 300
2
0 1 0 1
x3 0
Ą ó
A.
c= 30 20 0 0 0 ,xb =@ x4 A, cb =@ 0
x5 0
0 1 0 1
1 0 2 1 0 Ą4
3
Ą1
@ A. @ A
Macierz B2 ma postaś 0 1 3 Wtedy B2 = 0 1 Ą2
c
2
0 0 1;5 0 0
3
0 1 0 1
0 1 200
Ą1
@ A, Ą1 @ A, b Ą1 Ą ó
oraz B2 óA = 0 3 B2 ób = 1200 cTB2 A = 30 0 ,
1 400
Ą ó0
Ą1 Ą1
cTB2 = 0 0 20 oraz cTB2 b = 12000. Wś II tablica simplek-
owczas
b b
sowa wyglada nastepujaco:
, , ,
cb cj 30 20 0 0 0 Rozwiazanie (bj)
,
Zmienne bazowe x1 x2 x3 x4 x5
4
0 x3 0 1 1 0 - 200
3
0 x4 0 3 0 1 -2 1200
2
30 x1 1 0 0 0 400
3
zj 30 0 0 0 20 12000
cjĄzj 0 20 0 0 -20
0 1 0 1
1 0 2 1 0 Ą4
3
Ą1
A. A
Macierz B3 ma postaś 3 1 3 Wtedy B3 =@Ą3 1 2
c@
2
0 0 1;5 0 0
3
0 1 0 1
0 1 200
ó
Ą1
@ A, Ą1 @ A, b Ą1 Ą
oraz B3 óA = 0 0 B3 ób = 600 cTB3 A = 30 20 ,
1 0 400
Ą ó
Ą1 Ą1
cTB3 = 20 0 Ą20 oraz cTB3 b = 16000. Wś III tablica sim-
owczas
b 3 b
pleksowa wyglada nastepujaco:
, , ,
cb cj 30 20 0 0 0 Rozwiazanie (bj)
,
Zmienne bazowe x1 x2 x3 x4 x5
4
20 x2 0 1 1 0 - 200
3
0 x4 0 0 -3 1 2 600
2
30 x1 1 0 0 0 400
3
20
zj 30 20 20 0 - 16000
3
20
cjĄzj 0 0 -20 0
3
0 1 0 1
2
1 0 2 1 0
3
Ą1
A. A
MacierzB4 ma postaś 3 0 3 WtedyB4 =@Ą1;5 0;5 1
c@
1 Ą1 0
3
0 10 1 1;5 0 1
0 1 600
ó
Ą1
@ A, Ą1 @ A, b Ą1 Ą
oraz B4 óA = 0 0 B4 ób = 300 cTB4 A = 30 20 ,
1 0 200
3
Ą ó
Ą1 10 Ą1
cTB4 = 10 0 oraz cTB4 b = 18000. Wś IV tablica simplek-
owczas
b 3 b
sowa wyglada nastepujaco:
, , ,
cb cj 30 20 0 0 0 Rozwiazanie (bj)
,
Zmienne bazowe x1 x2 x3 x4 x5
2
20 x2 0 1 -1 0 600
3
0 x5 0 0 -1,5 0,5 1 300
30 x1 1 0 1 Ą1 0 200
3
10
zj 30 20 10 0 18000
3
cjĄzj 0 0 -10 Ą10 0
3
4