Transport10

Tablica 105

./ /		Przewóz z miastu i			do minuta /
	1	2	3	4	5	6	7
1	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

dij	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 samochodu 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 produ kej i (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(y = l,2,...,iV). Ponadto dana jest macierz A = [a_y], której ele menty oznaczają koszt (czas pracy lub wydajność) i-tego miejsca przy wykony waniu jednostki j-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_u. 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ć slosu jąc algorytm simpleks, przy czym liczba zmiennych decyzyjnych jest rów na N x /’.

II,'

Szczególnym przypadkiem zttdnń nlokacyjnych są tzw. zagadnienia o <>/> tymalnym 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 = [fly], której elementy a_tJ oznaczają nakład (czas, koszt) związany z wykonywaniem y-ej czynności (/' = 1,2,..., A^) w /-tym miejscu (/ = 1,2,..., P). Należ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ęć rodzą jó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 lak, 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 /'-tego typu krosien (/ = 1,2,3) przy produkcji j-ego rodzaju tkaniny (j = 1,2,...,5) i to będą zmienne decyzyjne x_ij.

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., żulem

Jen +x₁₂+x₁₃+x₁₄.-|-a:₁₅ ^ 600, i analogicznie dla krosien typu B i C:

I + X₂₂ + X₂3 + X₂4 + X₂5 ^ 840 ,

' tl +    +    + *34+ *35 < 720.

I