8107620629

sporządzenia mieszanki, otrzymujemy problem

240xi + 300x2 + 200x3 —» min

Xi + 2X2 + X3 > 2

4x_x + x₂ + x₃ > 4 3xi + 5x2 + X3 > 3

Xl,X2,X3 > 0.

Odejmując od lewych stron nierówności nieujemne zmienne dodatkowe x_4l x₅ i x₆, otrzymamy problem PL w postaci standardowej

240xi + 300x₂ + 200x₃ -> min

Xi	+2X2	+x3 x4	= 2
4xi	+x2	+£3	—x5 = 4
3xi	+5x2	+£3	-x6 = 3
	Xj	>0, j = 1	,...,6.

Zwróćmy uwagę na interpretację zmiennych dodatkowych. Mamy np. x₄ = x\ +2x2 + X3 — 2, gdzie Xi + 2x2 + X3 oznacza ilość składnika A w mieszance, zaś 2 jest minimalną ilością tego składnika. Zatem x₄ oznacza nadwyżkę (ponad minimalną ilość) zawartości składnika A w mieszance.

Otrzymana postać standardowa nie jest postacią bazową, gdyż macierz współczynników w układzie równań nie zawiera macierzy jednostkowej. Możemy stworzyć macierz jednostkową w macierzy współczynników układu równań, dodając do lewych stron tych równań odpowiednie zmienne nieujemne X7, X8 i Xg. Jednak pisząc np. pierwsze równanie w postaci xi + 2x2 + x₃ — x₄ + x₇ = 2 naruszamy równanie x₄ + 2x2 + X3 — x₄ = 2 o ile x₇ > 0. Musimy więc zagwarantować, aby w rozwiązaniu optymalnym zmienne x_7l x₈ i Xg przyjęły wartości 0. Możemy to zrobić, przyporządkowując im bardzo wysokie koszty jednostkowe. Oznaczmy te koszty przez M, gdzie M oznacza wystarczająco dużą liczbę. Otrzymamy problem PL w postaci bazowej względem zbioru B = {7,8,9}, Ab = (a₇ a₈ ag) — I

240xi + 300x2 + 200x3 + Mx₇ -I- Mxg + Mxg —» min

x4	+2X2	+x3 x4	+x7 — 2
4xi	+x2	+x3 -x5	+x8 = 4
3xi	+5x2	+x3	—X6 +Xg = 3
		Xj > 0 ,	3 € N1|9.

Teraz zadanie to możemy rozwiązać za pomocą algorytmu sympleks.

Mamy B = {7,8,9}, więc c_B =    Wartości Zj obliczymy ze wzoru Zj = c_Bhj,

j £ Ni,g. Tablica sympleksowa dla początkowego rozwiązania bazowego ma zatem postać tabeli 12. Macierz c — z nie jest nieujemna.

Kryterium wejścia: wyznaczamy indeks k € B', dla którego c_k — z_k jest najmniejszym wyrazem macierzy c — z. Jest nim C\ — Z\ = —8M+240. Tak więc k = 1, czyli w drugiej iteracji wprowadzimy zmienną bazową X\.

Aby ustalić, w miejsce której z dotychczasowych zmiennych bazowych ją wprowadzić, należy podzielić wyrazy macierzy ho przez dodatnie wyrazy macierzy hi i wybrać indeks l € B, dla którego ten iloraz jest najmniejszy (kryterium wyjścia). Ponieważ min{^, ^} = min{f, |, §} = 1 =    = j^,

więc kryterium wyjścia nie rozstrzyga jednoznacznie, która zmienna opuszcza bazę. Wybierzmy jedną z nich, np. x_g. Otrzymaliśmy zdegenerowane bazowe rozwiązanie dopuszczalne, gdyż x₈ = 0. Mamy

18