mgr inż. Magdalena Mytkowska ćwiczenia Badania operacyjne Minimalizacja pustych przebiegów

Minimalizacja pustych przebiegów

Dotychczasowe zagadnienia dotyczyły optymalnych przewozów masy towarowej. Zagadnienie minimalizacji pustych przebiegów dotyczy optymalnego krążenia środków transportu rozwożących towar.

Rozwiązanie:

Należy podzielić np. miejscowości na dostawców i odbiorców pustych samochodów obliczając różnice pomiędzy przywozem i wywozem. p_i - w_i

Dostawcami będą miasta dla których p_i - w_i > 0

Odbiorcami będą miasta dla których p_i - w_i < 0

Zmienne decyzyjne x_ij oznaczać będą liczbę pustych samochodów, jaką powinien przesłać
i - ty dostawca j - emu odbiorcy.

Zadanie 1.

W skład pewnego przedsiębiorstwa wchodzi sześć zakładów produkcyjnych. Rozprowadzenie surowców oraz wywóz wyrobów gotowych odbywa się przy wykorzystaniu taboru samochodowego. Wielkości przewozu i wywozu (wyrażone liczbą pełnych samochodów) oraz odległości pomiędzy zakładami (w km) przedstawiono w tabeli.

Punkty wytwórcze	1	2	3	4	5	6	Wywóz
1 2 3 4 5 6	0	8 0	12 20 0	21 8 18 0	30 10 11 7 0	14 7 10 12 19 0	9 11 10 18 14 18
Przewóz	15	18	17	9	14	7	80

Zbudować model matematyczny, który pozwoli ustalić plan przebiegu pustych ciężarówek pomiędzy punktami wytwórczymi. Podać minimalny samochodokilometraż pustych przebiegów.

Zadanie 2.

Do siedmiu stacji kolejowych nadchodzą i są odprawiane przesyłki całowagonowe. Wielkości przewozu p_i i wywozu w_i oraz odległości miedzy stacjami podano w tabeli. Opracować plan przewozu pustych wagonów, tak aby łączny wagonokilometraż pustych przebiegów był możliwie najmniejszy.

Stacja kolejowa	1	2	3	4	5	6	7	pi
1	0	56	38	132	21	55	24	18
2		0	27	46	31	10	99	9
3			0	22	44	33	77	16
4				0	18	9	66	15
5					0	90	11	19
6						0	44	8
7							0	5
wi	5	13	22	22	7	12	9

Zadanie 3.

Zminimalizować puste przebiegi samochodów o ładowności 50 t, przewożących worki z piachem pomiędzy siedmioma miastami stanowiącymi układ zamknięty. Dzienne przewozy i wywozy worków z piachem (w tonach) do poszczególnych miast oraz odległości pomiędzy tymi miejscowościami podano w tabeli.

Miasta	L	M	N	O	P	R	S	Wywóz
L M N O P R S	0	20 0	50 40 0	100 20 100 0	150 30 150 40 0	200 50 200 30 80 0	100 20 100 150 70 60 0	1000 2000 1000 100 200 1000 500
Przywóz	500	1000	2000	1000	1000	300	0	5800

Rozwiązanie

Zadanie 1.

Na wstępie punkty wytwórcze 1, 2, 3, 4, 5, 6 należy podzielić na dostawców i odbiorców pustych ciężarówek, obliczając różnice pomiędzy przywozem i wywozem.

1: 15-9 = 6

2: 18-11= 7

3: 17-10 = 7

4: 9-18 = -9

5: 14-14 = 0

6: 7-18 = -11

Dostawcy (1, 2,3) = 3

Odbiorcy (4, 6) = 2

	4	6	wi
1	21	17	6
2	8	7	7
3	18	10	7
pi	9	11

Warunki dla dostawców

Warunki dla odbiorców

Funkcja celu

K(x_ij) = 21x₁₁+14 x₁₂+ 8 x₂₁ + 7 x₂₂ +18 x₃₁ +10 x₃₂→ min

Stosując metodę minimalnego elementu macierzy, otrzymujemy rozwiązanie optymalne dane macierzą.

21	14	Warunki zadania
8	7
18	10
7	0	W1=14
1	0	W2=7
8	0	W3=10
6	0	K1=1
0	0	K2=0
7	0
2	4	6
7		7
	7	7
9	11

K(x) = 2*21+7*8+14*4+7*10=224

Zadanie 2.

Na wstępie stacje kolejowe 1, 2, 3, 4, 5, 6, 7 należy podzielić na dostawców i odbiorców pustych wagonów, obliczając różnice pomiędzy przywozem i wywozem.

1: 18-5 = 13

2: 9-13 = - 4

3: 16-22 = - 6

4: 15-22 = - 7

5: 19-7 = 12

6: 8-12 = - 4

7: 5-9 = - 4

Dostawcy (1, 5) = 2

Odbiorcy (2, 3, 4, 6, 7) = 5

	2	3	4	6	7	wi
1	56	38	132	55	24	13
5	31	44	18	90	11	12
pi	4	6	7	4	4

Warunki dla dostawców

Warunki dla odbiorców

Funkcja celu

K(x_ij) = 56x₁₁+38 x₁₂+132 x₁₃+55 x₁₄+24x₁₅+31x₂₁+ 44 x₂₂+ 18 x₂₃+90 x₂₄+11 x₂₅→ min

Stosując metodę minimalnego elementu macierzy, otrzymujemy rozwiązanie optymalne dane macierzą.

	2	3	4	6	7	warunki zadania
1	56	38	132	55	24
5	31	44	18	90	11
	32	14	108	31	0	W1=24
	20	33	7	79	0	W2=11
	12	0	101	0	0	K1= 20
	0	19	0	48	0	K2=14
						K3=7
						K4=31
						K5=0
		6		4	3	13
	4		7		1	12
	4	6	7	4	4

K(x) = 4*31+6*38+7*18+4*55+3*24+11=781

---