img317 (3)

a)    x₁+x₂-+ max,

b)    x_i— 4x₂ ->min,

. x,+x₂

c)    -— -> max,

x₂ — 4x₂

x₁-4x₂

d)    —---»min.

x₁ +x₂

Przedyskutować poszczególne rozwiązania. 64. Dane jest następujące zadanie PI:

(1)	xl—x2^2,
(2)	— x1+x2<2,
(3)	x1+x2^4,
(4)	xl + x2^8,
(5)	x1,x2^0,
(6)

max.

1.    Podać wartość parametru a, dla której punktem obrotu prostej rozwiązującej jest punkt P₀(3; —4).

2.    Znaleźć rozwiązanie optymalne zadania przy spełnieniu warunku z pkt. 1.

3.    Podać wartość a, dla której punktem obrotu prostej rozwiązującej jest punkt P₀(-4; 3).

4.    Wskazać rozwiązanie optymalne przy spełnieniu warunku z pkt. 3.

2. Problemy transportowe i przydziału

Modele zagadnień omawianych w tym rozdziale są szczególnym przypadkiem modeli liniowych, można je zatem rozwiązywać za pomocą algorytmu simpleks. Jednak specyficzna struktura warunków ograniczających w tych modelach sprawiają, że mogą one być rozwiązywane również za pomocą metod bardziej efektywnych. Niektóre z tych metod będą omówione w niniejszym rozdziale.

2.1. Zagadnienia transportowe

Zagadnienie transportowe zostało sformułowane po raz pierwszy (w 1941 r. przez F.L. Hitchocka) jako problem opracowania planu przewozu pewnego jednorodnego produktu z kilku różnych źródeł zaopatrzenia do kilku punktów zgłaszających zapotrzebowanie na ten produkt. Kryterium optymalizacji planu przewozów jest najczęściej minimalizacja łącznych kosztów transportu (rzadziej - minimalizacja odległości lub czasu transportu).

Do tak sformułowanego zagadnienia można sprowadzić wiele różnych zagadnień (w tym również pewne zagadnienia nie dotyczące transportu), które mają tę samą strukturę matematyczną. Kolejne przykłady niniejszego podrozdziału dotyczą następujących zagadnień:

a)    zagadnienia transportowego zamkniętego i otwartego,

b)    zagadnienia transportowo-produkcyjnego,

c)    zagadnienia lokalizacji produkcji,

d)    zagadnienia minimalizacji pustych przebiegów.

Uniwersalną metodą rozwiązywania modeli transportowych jest algorytm transportowy, który podobnie jak algorytm simpleks jest procedurą iteracyjną. W pierwszym etapie (kroku), stosując jedną ze znanych metod, wyznacza się początkowe rozwiązanie dopuszczalne, które następnie poprawia się w kolejnych iteracjach. Poniżej przedstawiono jedynie dwie wybrane metody wyznaczania początkowego rozwiązania dopuszczalnego: metodę kąta północno-zachodniego i metodę minimalnego elementu macierzy. Zrezygnowano z peł-

91