Rozproszenie i koszty transportu

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 = { a₁, a₂, a₃, a₄, a₅ }, rozmieszczonych jak na rysunku. Pokazano tam również usytuowanie projektowanej centrali p.
W tym projekcie

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 p₀, by   R( A, p₀ ) R( A, p )  dla wszystkich p.

Taki punkt p₀ nazwiemy centrum A i oznaczmy C( A ).
Gdy p₀ jest centrum A, to liczbę R₀( A) = R( A, p₀ ) 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ź!).

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:

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

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 = { a₁, a₂, a₃, a₄ } do oddziałów zakładów B = { b₁, b₂, b₃, b₄ }. 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:

 
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 ( a_i ) = b_i.
Ten sam transport opisuje poniższa tabelka.

T ' : A B

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

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 n³, gdzie n oznacza liczność zbiorów A i B. Oznacza to, że mniej więcej po wykonaniu 100³ = 1 000 0000 operacji algorytm daje optymalne rozwiązanie dla 100 elementowych zbiorów A, B.