img292

Zoptymalizować przewóz drobnicy przy maksymalnym wykorzystaniu ładowności barek, jeśli wiadomo, że maksymalna liczba użytych barek o ładowności 8 t nie może przekroczyć 30.

35. Punkt usługowy dostał zamówienie na wycięcie szyb do 300 jednakowych okien, z tym że na 1 okno wchodzą 2 szyby typu e₂ oraz 3 szyby typu e₂. Szyby wycina się z jednakowych płyt szklanych i można je wycinać trzema sposobami. Liczby szyb i odpad powstały w procesie wycinania przedstawiono w tabl. 34.

Tablica 34

Szyby	Sposoby cięcia płyty
typu	I	II	III
^ei	6	4	3
e2	0	4	6
Odpad (w kg)	0,6	1,6	1,2

1.    Zbudować model matematyczny zagadnienia.

2.    Sformułować program dualny.

3.    Rozwiązać go metodą geometryczną, podając wartość funkcji celu oraz przejść do rozwiązania programu pierwotnego.

36. Zakład otrzymał 1500 arkuszy tektury, z których wycinane są trzy rodzaje elementów: E_l5 E₂ i E₃. Stosowane pięć sposobów rozkroju jednego arkusza oraz jednostkowe zyski ze sprzedaży poszczególnych elementów podano w tabl. 35.

Tablica 35

Elementy	Sposoby rozkroju 1 arkusza					Zyski jednost-kowe (w zł)
	I	II	III	IV	V
Ei	1	1	0	0	0	8
e2	1	0	2	1	0	12
e3	0	1	1	2	4	5

Ile razy należy zastosować możliwe sposoby cięcia, aby zmaksymalizować zysk ze sprzedaży elementów, biorąc pod uwagę, że elementów E₃ powinno być dwa razy więcej niż elementów Ej?

1.4. Algorytm simpleks

Jak wspomniano na początku rozdziału, uniwersalną metodą rozwiązywania programów liniowych jest algorytm simpleks. Istota algorytmu simpleks polega na badaniu kolejnych rozwiązań bazowych (rozwiązań dopuszczalnych) programu liniowego w postaci kanonicznej w taki sposób, że:

a)    znajdujemy (dowolne) rozwiązunic bazowe programu;

b)    sprawdzamy, czy jest ono optymalne;

c)    jeżeli dane rozwiązanie nie jest optymalne, konstruujemy następne rozwiązanie bazowe lepsze (lub przynajmniej nie gorsze od poprzedniego).

Postępowanie kończy się w momencie stwierdzenia, że aktualne rozwiązanie bazowe jest optymalne, tzn. nie można już go poprawić. Algorytm simpleks icst więc procedurą iteracyjną (etapową), a wyniki poszczególnych etapów (iteracji) zestawia się w kolejnych tablicach simpleks.

Ze względu na dużą pracochłonność algorytmu simpleks nie będziemy go szczegółowo omawiać (jak wspomniano, problemy rozwiązywane są za pomocą pakietów komputerowych), ograniczymy się jedynie do podania zależności pomiędzy pierwszą tablicą a kolejnymi tablicami simpleks (znajomość tej zależności jest niezbędna w analizie wrażliwości omawianej w następnym podrozdziale). Wykorzystamy w tym celu zapis macierzowy programu liniowego.

Każdy program liniowy, na przykład:

c1x1 + c2x2 + ..	. + cnxn-* max.
^aVl^xl "b@12^X2 +	•+«iA
^aml^Xl + <*m2^X2 + -	.. + amnx„^bm,

x_l,x₂,...,x„^0,

można zapisać w postaci macierzowej:

cx—* max, Ax^b, x*tO,

gdzie:

^an	^ai2 '	3 J		*1 *2		V
			, x =		, b =
Au	^am2 '	^mn-		'X . 3 1_		kl

, c=[c₁...c„].

Jak zaznaczono na wstępie, algorytm simpleks polega na badaniu rozwiązań bazowych programu o postaci kanonicznej¹, a zatem przed przystąpieniem do budowy pierwszej tablicy simpleks należy zamienić wszystkie nierówności na równania przez wprowadzenie pewnych nowych zmiennych. W przypadku nierówności typu do ich lewych stron dodajemy tzw.

41

1

Model o postaci kanonicznej to taki, w którym wszystkie warunki ograniczające mają postać równości.