METODA KARY (metoda zmiennych sztucznych)

ZADANIE WYJŚCIOWE

!!!

- dowolne

Algorytm ten wymaga zmiennych sztucznych

Algorytm ten - stanowi sposób rozpoczęcia obliczeń metodą sympleksów, gdy zagadnienie PL nie zawiera macierzy jednostkowej - pozwala stwierdzić, czy zagadnienie ma rozwiązanie dopuszczalne

Zadanie wyjściowe zastępujemy następującym zadaniem rozszerzonym.

przy ograniczeniach
,
.

- pewna stała dodatnia dowolnie duża (tzn. większa od każdej skończonej liczby, z którą
porównujemy). Wielkość
interpretujemy jako karę.

Należy pamiętać, że żadna zmienna sztuczna, która zostanie usunięta z bazy nie jest rozpatrywana później jako kandydat wejścia do bazy.

Sposób rozwiązania zadania (schemat postępowania) :

Do zadania rozszerzonego stosujemy alg. SP aż do momentu, gdy:

a) w bazie nie ma zmiennych sztucznych, mamy wówczas program bazowy zadania wyjściowego i stosujemy dalej algorytm SP, aż do uzyskania minimum;

b) baza zawiera zmienne sztuczne wszystkie z wartościami równymi 0, a współczynnik przy
w każdym z wyrażeń
są
, uzyskany program jest programem zdegenerowanym zadania wyjściowego. Może wystąpić wtedy, gdy
. Jeżeli żadna z różnic
nie jest dodatnia, to jest to program optymalny, w przeciwnym razie stosujemy algorytm PS bez rozpatrywania tych kolumn, dla których
jest zależne od
, aż do uzyskania minimum (końcowe rozwiązanie może zawierać zmienne sztuczne z wartością 0 lub też nie zawierać w ogóle zmiennych sztucznych);

c) baza zawiera co najmniej jedną zmienną sztuczna o wartości dodatniej i współczynnik przy
w każdym z wyrażeń
są
. W tym przypadku zadanie wyjściowe nie ma rozwiązania.

1

Badania operacyjne - programowanie liniowe - metoda kary - algorytm

A.Andruch-Sobiło

---