DSC00095 (7)

WYZNACZANIE POCZĄTKOWEGO ROZWIĄZANIA BAZOWEGO DOPUSZCZALNEGO

I. Postać warunków ograniczających:

A x £ h b2 0, x 20

Postać standardową uzyskuje się poprzez wprowadzenie zmiennych osłabiających (wektora zmiennych bilansujących)

Ax+xf = b b2 0

x 2 0, x? 2 0

Wtedy pierwszym rozwiązaniem bazowym dopuszczalnym jest: x = 0, x* = b

2. Postać warunków ograniczających:

A x = b b20 x 20

Jeżeli w macierzy A można wyodrębnić podmacierz jednostkową stopnia m. tzn.

A = [AVI

wtedy

A*xi + Ixi = b    b2 0

xk,xb 2 0 X# e xg Pierwszym rozwijaniem bazowym dopuszczalnym jest: x« = 0, x_t=b

3. Postać warunków ograniczających:

Ax | b    b2 0

x 20

Jeżeli w macierzy A nie można wyodrębnić podmacierzy jednostkowej stopnia m. to wprowadzamy wektory sztucznej bazy x, (zmienne sztuczne).

Otrzymujemy tzw. zadanie rozszerzone:

max z a e^rx - J#[lj^Tx,

Ax + x, = b b 20 x 20. x,2 0

gdzie: wektor [1] jest wektorem, którego wszystkie składowe są równe jedności, natomiast Af jest bardzo dużą liczbą dodatnią.

Pierwszym rozwiązaniem bazowym dopuszczalnym zadania rozszerzonego jest

x = 0,x, = b

Twierdzenie

Jeżeli w rozwiązania optymalnym x 11 jr,, x, } zadania rozszerzonego mamy x, = 0, to x, jest rozwiązaniem optymalnym zadania początkowego, jeżeli zaś w rozwiązaniu tym x, > 0. to zadanie początkowe jest sprzeczne.

Algorytm postępowania

A.    Dla standardowej postaci zadania programowania firnowego zbudować zadanie rozszerzone.

B.    Znaleźć rozwiązanie optymalne zadania rozszerzonego za pomocą algorytmu simpleks.

Zadanie rozszerzone nigdy nie jest sprzeczne - albo otrzymujemy rozwiązanie optymalne, albo stwierdzamy nieograntczoność rozwiązania optymalnego.

Gdy zadanie rozszerzone ma skończone rozwiązanie optymalne, to mogą zaistnieć trzy przypadki:

!. Wśród zmiennych bazowych rozwiązania optymalnego nie ma zmiennych sztucznych - rozwiązanie to. po odrzuceniu zmiennych sztucznych, wyznacza rozwiązanie optymalne zadania początkowego.

2.    Wśród zmiennych bazowych rozwiązania optymalnego występują zmienne sztuczne z wartościami zerowymi - rozwiązanie to, po odrzucano zmiennych sztucznych . wyznacza rozwiązanie optymalne zadania początkowego.

3.    Wśród zmiennych bazowych rozwiązania optymalnego występują niezerowe zmienne sztuczne - zadanie wyjściowe jest sprzeczne.

Przykład

Zadanie początkowe

nun z = - */ * x₂ - Xj

x, + 2xj+ x_} < 16 2xj + x₂+ x, i 4 x,+ x₂ + 2x, = 5

Zadanie rozszerzone

mor z — X\ + xj + Xj - Mr« • Mx₇

= 16 = 4

+ x, = 5

xi + 2xt+ x₃

2x,+ xi+Xj -x,+ X4 */+ xj + 2x,