036 037 2

I

I

36

Programowanie liniowe ?

Kryterium optymalności dla zadania maksymalizacji

Jeżeli wartości wszystkich wskaźników optymalności są niedodatnie, to rozpat- l rywane rozwiązanie jest optymalne. Jeżeli choć jeden ze wskaźników optymalności |

jest dodatni, to istnieje możliwość poprawy tego rozwiązania.

'

1.3.3. Wybór zmiennej

wprowadzanej do bazy

Wprowadzenie do początkowego rozwiązania bazowego zmiennej *, = 1 powoduje wzrost funkcji celu o 2 jednostki, natomiast wprowadzenie zmiennej x₂=\ zwiększa wartość funkcji celu o 3 jednostki. Ponieważ dążymy do jak najszybszego osiągnięcia rozwiązania optymalnego, posłużymy się opisanym poniżej sposobem wyboru zmiennej wprowadzanej do bazy.

Kryterium wejścia

Wybieramy największą wartość wskaźnika optymalności. Odpowiadającą mu zmienną wprowadzamy do nowej bazy. Jeżeli największej wartości wskaźnika optymalności odpowiada więcej niż jedna zmienna, to do nowej bazy wprowadzamy zmienną o najniższym numerze.

W rozpatrywanym przez nas przypadku wprowadzimy do nowej bazy zmienną x₂.

1.3.4. Wybór zmiennej

opuszczającej bazę

Zastanówmy się teraz, jaka jest największa dopuszczalna wartość zmiennej x₂, którą zdecydowaliśmy się wprowadzić do nowej bazy. Musi ona być dobrana w laki sposób, aby były spełnione wszystkie warunki ograniczające. Rozpatrzymy je po kolei.

Pierwszy warunek ograniczający:

2x, + 2x₂+x_t = 14.

Ponieważ zmienna x, jako niebazowa jest równa zeru, więc:

2x₂ + x₃= 14.

Zwiększając wartość x₂, możemy doprowadzić do tego, że dotychczasowa zmienna bazowa jc₃ przyjmie wartość zero. Będzie tak wówczas, gdy:

2.r₂= 14,

czyli *2= 7. Dalsze zwiększenie wartości zmiennej x₂ doprowadziłoby do tego, że Xj byłoby ujemne, co jest niedopuszczalne. Największa dopuszczalna wartość zmiennej x₂ dla pierwszego warunku ograniczającego jest więc równa 7.

Drugi warunek ograniczający:

X\ + 2x₂ + x₄ = 8.

W związku z tym, że mamy jc, = 0, otrzymujemy:

2x₂ + *4 =

Zwiększając wartość x₂, możemy doprowadzić do tego, że dotychczasowa zmienna bazowa *₄ przyjmie wartość zero. Będzie lak wówczas, gdy 2jc₂ = 8, czyli x₂ = 4. Największa dopuszczalna wartość ze względu na drugi warunek ograniczający jest więc równa 4.

Trzeci warunek ograniczający:

4*1 +0x₂+.*5= 16.

Ponieważ współczynnik przy jc₂ jest równy 0, zwiększenie wartości zmiennej x₂ nie ma żadnego wpływu na zmienną jc₅, tak więc zmiennej x₅ nie można wyprowadzić z bazy przez wprowadzenie do bazy zmiennej x₂. W taki sam sposób interpretujemy sytuację, gdy współczynnik przy rozpatrywanej zmiennej jest ujemny.

Największa dopuszczalna wartość zmiennej x₂ musi być tak dobrana, aby spełnione były wszystkie warunki ograniczające. Ponieważ drugi z warunków ogranicza ją w największym stopniu, wynosi ona 4. Odpowiadająca drugiemu warunkowi zmienna bazowa x₄ przyjmie wówczas wartość 0, stając się zmienną niebazową.

Otrzymujemy następujące kryterium wyboru zmiennej opuszczającej bazę: Kryterium wyjścia

Obliczamy ilorazy kolejnych wyrazów wolnych przez odpowiadające im elementy kolumny wchodzącej do bazy dla tych elementów kolumny wprowadzanej do bazy, które są dodatnie. Bazą opuszcza ta zmienna, dla której odpowiadający jej iloraz jest najmniejszy. Jeżeli minimum jest przyjmowane więcej niż jeden raz, to jako zmienną opuszczającą bazą wybieramy zmienną o najniższym numerze.

1.3.5. Przejście do rozwiązania bazowego sąsiedniego

Ponieważ doszliśmy do wniosku, że z dotychczasowej bazy, w której były zmienne x_y, x₄ i x_s, należy usunąć zmienną x₄ oraz wprowadzić na jej miejsce zmienną x₂, naszym celem jest obecnie otrzymanie odpowiadającego nowej bazie rozwiązania bazowego sąsiedniego. Uzyskamy je za pomocą operacji elementarnych, wykonywanych na wierszach tablicy simpleksowej.

Ze względu na to, że zmienna ,r₂ staje się zmienną bazową, wykonamy te operacje w taki sposób, aby druga kolumna w przekształconej macierzy warunków