3582319524

1

Badania operacyjne ZilP rok 2 ćwiczenia - zajęcia 1 Programowanie liniowe - metoda simpleks

maxx_e = 2x\ +- x₂ i"! + x₂ < 5

—Xi + #2 < 0

6xi + 2*2 — 21 X₃, X"2 — 0

Sprowadzenie problemu do postaci standardowej:

maxx₀ = Zti + x₂ + 0x₃ 4- 0.r₄ + 0x₅

*i + x₂ + x₂ = 5 — i^-! + X₂ + X₄ = 0 6x₁ + 2x_z + x_& = 21 Pierwsza tabela simpleksowa:

		~*i	“*2
Xa	0	-2	-1
*3	5	1	1	5/1=5
XA	0	-1	1
Xę	21	6	2	21/6=3 ,5

Oznaczenia:

p — wartość elementu centralnego n — wartość j — tego elementu w kolumnie centralnej q_: — wartość i — tego elementu w wierszu centralnym

5_SJ — wartość elementu w komórce przecięcia i — tej kolumny z j — tym wierszem

Aby wybrać zmienną wchodzącą do bazy wybieramy najmniejszą liczbę ujemną spośród wartości w komórkach przecięcia wiersza *^c z kolumnami ~^%i (tutaj: -2 w kolumnie ^_Al).

Wybrana kolumna nazywa się kolumną centralną danej iteracji (tutaj: kolumna ^Al).

Rozwiązanie jest optymalne jeżeli w kcmorkach prze.Je la wiersza ^t[ z kolumnami ^ł

występują wyłącznie liczny nieujemne

Aby wybrać zmienna wychodzącą z bazy, dla dodatnich elementów kolumny centralnej (tutaj: dla *³ oraz ^X;) oblicza się ilorazy: element z pierwszej kolumny/element z kolumny centralnej

(tutaj: dla *³ jest to ^5yi oraz dla ^Xsjest to ~^1/6). Spośród wyliczonych ilorazów wybiera się

najmniejszy (tutaj 3,5 w wierszu ^A’³). Zmienna, dla której iloraz jest najmniejszy wychodzi z bazy; wiersz odpowiadający tej zmiennej nazywa się wierszem centralnym danej iteracji (tutaj

Element wspólny dla wiersza centralnego i kolumny centralnej nazywa się elementem centralnym danej iteracji (tutaj element o wartości 6, pochodzący z komórki przecięcia wiersza ³ i kolumny ~^Xl).