Rozproszenie i koszty transportu

Data ostatniej modyfikacji:
2009-12-25
Autor: 
Krzysztof Omiljanowski
pracownik IM UWr
Poziom edukacyjny: 
szkoła podstawowa
gimnazjum
szkoła średnia z maturą
szkoła profilowana zawodowa
szkoła wyższa
Dział matematyki: 
kombinatoryka

Zamiast mówić o punktach i figurach, będziemy mówili o oddziałach pewnej fabryki.

Fabryka A składa się z 5 oddziałów: A = { a1, a2, a3, a4, a5 }, rozmieszczonych jak na rysunku. Pokazano tam również usytuowanie projektowanej centrali p.
W tym projekcie

rozproszenie A względem p jest równe R(A, p) =  [km]
(jest to suma odległości p od poszczególnych oddziałów z A).
R(A, p) zmieni się, gdy zmienimy projekt i umieścimy centralę p gdzie indziej (spróbuj!).

UWAGA. Ten rysunek jest dynamiczny. Można przesuwać punkty zaznaczone pełnymi kwadracikami, chwytając je lewym przyciskiem myszy. Po chwili rysunek się zaktualizuje.

Natychmiast nasuwa się szereg pytań.

Problem 1.   Gdzie umieścić centralę p, by zminimalizować koszty połączeń?
To znaczy, że mamy   znaleźć taki punkt p0, by   R( A, p0 ) R( A, p )  dla wszystkich p.

Taki punkt p0 nazwiemy centrum A i oznaczmy C( A ).
Gdy p0 jest centrum A, to liczbę R0( A) = R( A, p0 ) nazwiemy rozproszeniem A.

Bywają sytuacje, w których jest wiele takich punktów. Wtedy każdy z nich nazwiemy centrum A, a C( A) będzie oznaczało zbiór wszystkich centrów A). Tak jest np. gdy A jest położony wzdłuż linii prostej, jak poniżej (sprawdź!).

UWAGA. Ten rysunek jest dynamiczny. Można przesuwać punkty zaznaczone pełnymi kwadracikami, chwytając je lewym przyciskiem myszy. Po chwili rysunek się zaktualizuje.

Poszukiwanie centrum A prowadzi do bardzo ciekawych zagadnień geometrycznych, jednak tu nie będziemy ich rozważać.

Powyższe pojęcia mają sens również wtedy, gdy inaczej będziemy mierzyć odległości, na przykład tak, jak na szachownicy, gdzie odległość pól mierzymy najkrótszą łączącą je drogą 'pionowo-poziomą' wyrażoną liczbą kratek.

Na przykład: na rysunku obok punkt (kwadrat) p ma współrzędne (2,3), a punkt (kwadrat) q ma współrzędne (4,7). Odległość tych punktów jest równa najkrótszej drodze „poziomo-pionowej” łączącej te punkty, czyli d(p, q) = 6.

Pomiędzy p i q jest wiele najkrótszych dróg. Punkt s leży w połowie drogi od p do q, ale nie tylko on, również punkt t.

Analogicznie można mierzyć odległości sześcianików w przestrzeni; np. d( (1,2,5), (2,4,1) ) = (2-1) + (4-2) + (5-1) = 7.

Na szachownicy zbiór A = { (8,6),(8,7),(8,8),(9,8) } oznacza zbiór ‘pełnych’ kwadratów. Mamy:

R ( A, (9,5) ) = 2+3+3+4 = 12,    R ( A, u ) = 8,
centrami A są punkty: (8,7) i (8,8)
czyli C( A ) = {(8,7), (8,8)}  i  R( A ) = 4 .

Dla zaznaczonego zbioru B znalezienie centrów i rozproszenia jest dość żmudne (trzeba sprawdzać, czy właściwie odgadliśmy prawidłowe punkty).

Dla zbioru D = { (4,2),(4,9),(9,9),(9,2) } można nie tylko zgadywać: niech p = (x,y) leży w obrębie prostokąta wyznaczonego przez D. Wtedy K(D, p) obliczymy sumując

(x-4)+(y-2) + (x-4)+(9-y) + (9-x)+(9-y) + (9-x)+(y-2).
Zaskakujące? Tak, każdy punkt tego prostokąta jest centrum D.

Można zatem nie tylko zgadywać. Zrobienie kilku ćwiczeń pozwoli zapewne na odkrycie prostego sposobu obliczania rozproszenia zbioru na szachownicy, nawet bardzo skomplikowanego.

Zachęcamy do samodzielnej pracy na przykład z zadaniami zebranymi w artykule 'Rozproszenie i koszty transportu (zadania)'.
 


 
Poniższy rysunek i tabelka opisują pewien transport T : A B , czterech produktów z oddziałów fabryki A = { a1, a2, a3, a4 } do oddziałów zakładów B = { b1, b2, b3, b4 }. Są też inne sposoby przetransportowania A na B, ważne, by do każdego oddziału z B przewieźć jakiś towar z A.

Koszt K( T ) transportu T mierzymy w kilometrach sumując odległości:

K( T ) = d( a1, T (a1) ) + d( a2, T (a2) ) + d( a3, T (a3) ) + d( a4, T (a4) ) .

UWAGA. Ten rysunek jest dynamiczny. Można przesuwać punkty zaznaczone pełnymi kwadracikami (chwytając je lewym przyciskiem myszy). Po chwili rysunek się zaktualizuje.
T a1 a2 a3a4

 
  

 
Natychmiast nasuwa się pytanie:

Problem 2.   Jak najtaniej przetransportować A na B ?
Innymi słowy:   znaleźć takie T ' : A B , by   K( T ' ) K( T )  dla wszystkich T.

Geometria podpowiada, że w takim najtańszym transporcie drogi nie powinny się krzyżować (wynika to z nierówności trójkąta).
Czy to już wystarcza? Czy brak przecięć dróg transportu zapewnia już optymalność?
Łatwo można narysować A, B i transport T z A na B, bez skrzyżowań, który na pewno nie jest najtańszy.

Można próbować przeanalizować wszystkie możliwe transporty z A na B i z nich wybrać najtańszy. Jednak taki sposób postępowania jest możliwy tylko dla zbiorów A, B o małej liczbie elementów.
Liczba wszystkich możliwych transportów rośnie bardzo szybko, ze wzrostem liczby elementów; np. gdy A, B mają po 10 elementów, to jest 10! = 3 628 800 możliwych transportów. Przy 100 elementowych zbiorach żaden komputer nie da rady!

Zobaczmy problem transportu na szachownicy.
 
Obok liczby kodują pewien transport T : A B ,   T ( ai ) = bi.
Ten sam transport opisuje poniższa tabelka.

  a1a2a3 a4a5
b1b2b3 b4b5
 

   K( T ) = 7+4+5+4+5 = 25.
 
Czy można znaleźć tańszy transport T ' : A B ?
Tak, np.:
  a1a2a3 a4a5
b1b2b3 b5b4
 

   K( T ' ) = 7+4+5+3+4 = 23.
 

Znaleźć najtańszy transport T : C D .
 

  (2,4)(2,5)(2,6)(3,4) (3,5)(3,6)(4,4)(4,5)(4,6)
............... ............


 
Dzięki niemu łatwo wskazać tani transport T' : C E .
 

Dalsze przykłady ćwiczeń można znaleźć w artykule Rozproszenie i koszty transportu (zadania).

Uwaga.   Problem najtańszego transportu ma informatyczne rozwiązanie.
Tak zwany algorytm węgierski (inaczej zwany algorytmem Kuhna-Munkresa) daje optymalne rozwiązanie w czasie rzędu n3, gdzie n oznacza liczność zbiorów A i B. Oznacza to, że mniej więcej po wykonaniu 1003 = 1 000 0000 operacji algorytm daje optymalne rozwiązanie dla 100 elementowych zbiorów A, B.

 

Powrót na górę strony