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
Wyszukiwarka