img328 (4)

Tablica 105

\ J i		Przewóz z miasta (			do miasta j
	1	2	3	4	5	6	7
i	0	5	8	11	4	6	16
2	10	0	8	7	6	5	12
3	9	4	0	5	5	10	7
4	4	3	3	0	6	9	17
5	20	15	4	9	0	8	6
6	10	9	7	8	11	0	11
7	8	7	6	5	7	9	0

Tablica 106

d,j	1	2	3	4	5	6	7
1	0	18	34	55	10	21	50
2		0	53	29	64	19	10
3			0	18	33	22	14
4				0	54	9	36
5					0	13	15
6						0	19
7							0

Znaleźć taki plan przewozu pustych ciężarówek, przy którym samochodo-kilometraż pustych przebiegów będzie minimalny.

2.2. Problemy przydziału

Można wyodrębnić kilka grup problemów, których zadaniem jest alokacja szeroko pojętych zasobów. Najogólniej problem można sformułować następująco: N wyrobów (czynności) można wykonywać w P miejscach produkcji (w zakładach, na stanowiskach pracy, maszynach). Znane są ograniczone moce produkcyjne poszczególnych miejsc pracy (np. dopuszczalny czas pracy) B_{ (i = 1, 2a często także zadania planowe w zakresie produkcji wyrobów Cj(j = 1,2Ponadto dana jest macierz A = [a_tj], której elementy oznaczają koszt (czas pracy lub wydajność) i-tego miejsca przy wykonywaniu jednostki /-ego wyrobu.

Należy zaproponować przydział zadań produkcyjnych do poszczególnych miejsc pracy, optymalny z punktu widzenia jednego z poniższych kryteriów:

a)    minimalizacja kosztów lub czasu wykonywania zadań planowych,

b)    maksymalizacja efektów (ilości wyprodukowanych wyrobów).

Konkretna postać modelu zależy od charakteru podanych parametrów

a_i}. Modele te można znaleźć np. w pracy Kalichmana [35]. Dwie typowe sytuacje decyzyjne ilustrują przykłady 20 i 21. Inne, spotykane w praktyce, uwzględnione zostały w zadaniach. Zagadnienia te można rozwiązać stosując algorytm simpleks, przy czym liczba zmiennych decyzyjnych jest równa N x P.

Szczególnym przypadkiem zadań ulokucyjnych są tzw. zagadnienia o optymalnym przydziale z dodatkowymi warunkami. Istnieje N rodzajów robót (czynności) i P sposobów (miejsc, osób) ich wykonania. Dana jest macierz A = [fl_y], której elementy a_tj oznaczają nakład (czas, koszt) związany z wykonywaniem j-ej czynności (j = 1,2,...,N) w i-tym miejscu (i = 1,2Należy przydzielić wykonywanie czynności do poszczególnych miejsc (osób) tak, aby zminimalizować łączny nakład, czas, koszt pracy, przy dodatkowych warunkach, że każda czynność może być wykonywana tylko w jednym miejscu pracy i równocześnie w każdym miejscu pracy można wykonywać tylko jedną czynność. Modele tego typu zagadnień można znaleźć np. w pracy R.L. Childressa [13], gdzie podany jest także prosty algorytm ich rozwiązywania, który zostanie zaprezentowany w przykładach 22 i 23.

Przykład 20. Na trzech typach krosien można produkować pięć rodzajów tkanin. Wydajność krosien (w m/godz.) przy produkcji poszczególnych tkanin oraz dopuszczalne czasy pracy krosien podano w tabl. 107.

Tablica 107

Krosna typu	Wydajność (w m/godz.) przy produkcji tkaniny					Dopuszczalny czas pracy (krosnogodz.)
	1	2	3	4	5
A	5	10	8	12	6	600
B	7	7	12	10	8	840
C	8	9	10	11	9	720

Rozdzielić produkcję tkanin pomiędzy poszczególne typy krosien tak, aby wyprodukować co najmniej 1120 m tkaniny 1, 1260 m tkaniny 2, 1800 m tkaniny 3, 1200 m tkaniny 4 i 720 m tkaniny 5, minimalizując łączny czas pracy krosien.

Rozwiązanie. W zadaniu podano wydajności krosien przy produkcji poszczególnych rodzajów tkanin (w m/godz.). Wobec tego, aby rozdzielić produkcję tkanin pomiędzy krosna, należy określić czas pracy i-tego typu krosien (i = 1,2,3) przy produkcji j-e go rodzaju tkaniny (j = 1,2,...,5) - i to będą zmienne decyzyjne x_tJ.

Zmienne decyzyjne powinny spełniać dwie grupy warunków. Po pierwsze, ograniczony jest dopuszczalny czas pracy krosien. I tak, krosna typu A przy produkcji wszystkich tkanin mogą pracować nie dłużej niż 600 godz., zatem

*n -t-x₁₂ + x₁3-l-x₁₄-l-jc₁₅    600,

i analogicznie dla krosien typu B i C:

*21 +*22+ *23 +*24+ *2 5 ^ 840 , *31 + *32 + *3 3 + *34 + *35 ^ 720.

113