min
ALGORYTM SYMPLEKS PRYMALNY
min |
|
|
|
|
Wyznaczyć wyjściowy (początkowy) program bazowy (najlepiej macierz jednostkową), 
.
Niech 
będzie zbiorem wskaźników kolumn macierzy 
należących do macierzy bazowej bazy 
. 
, 
, 
.
Wyznaczyć macierz 
, oraz wielkości 
, 
.
Zbadać liczby 
(jak wyglądają różnice 
) dla 
:
jeżeli 
to znaleźliśmy rozwiązanie optymalne (minimalne);
- jeżeli 
to jest to jedyne rozwiązanie,
- jeżeli 
to programów optymalnych jest nieskończenie wiele,
jeżeli 
to przechodzimy do punktu 4 algorytmu; oznaczmy przez 
, 
, zbiór tych wskaźników 
, dla których zachodzi warunek 
. ( 
, 
)
Zbadać kolumny 
, 
:
jeżeli 
(w kolumnie 
nie ma elementu dodatniego),
wtedy są dwie możliwości:
- nie ma skończonego programu minimalnego 
,
- układ jest sprzeczny.
jeżeli
(w kolumnie
jest co najmniej jeden element 
),
to wyznaczamy wskaźnik 
i 
spełniające warunki:
- kryterium wejścia,
. 
- kryterium wejścia .
Element 
nazywamy elementem centralnym.
W macierzy bazowej 
wymienia się kolumnę 
z kolumną 
. Dostaje się nową macierz bazową 
, dla której funkcja celu osiąga wartość nie większą od wyliczonej wartości dla poprzedniej bazy (widać tutaj, która baza jest najlepsza). Należy obliczyć nowy program bazowy 
odpowiadający bazie 
oraz nowe wartości 
i 
macierzy 
.Wrócić do punktu 3 algorytmu.
|
|
|
|
|
… |
|
… |
|
… |
|
|
|
|
|
|
… |
|
… |
|
… |
|
|
|
|
|
|
… |
0 |
… |
0 |
… |
|
|
|
|
|
|
… |
1 |
… |
0 |
… |
|
|
|
|
|
|
… |
0 |
… |
0 |
… |
|
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
|
|
|
|
|
… |
0 |
… |
1 |
… |
|
Wyliczyliśmy 
i 
- wchodzi do bazy; 
- wychodzi z bazy
dla 
dla 
ZMIANA BAZY - reguła prostokąta
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
Element 
- element centralny.
1
Badania operacyjne - algorytm Sympleks Prymalny - treść
programowanie liniowe
A.Andruch-Sobiło
