0000004

122

122

C =

110

10

Na tej podstawie zanalizujemy zbiór możliwych rozwiązań z dwoma bazami Możemy o nich z góry powiedzieć, że koszt rozwiązania wy niesie na pewno (28)

Jeżeli odrzucimy lokalizację 1 to koszt wzrośnie przynajmniej o (122). Zbiór wszystkich rozwiązań dzielimy względem jednej cechy. Tą cechą jest : czy w rozwiązaniu jest baza 1, czy jej nie ma

Rozwiązania, które wykluczają stację 1 to rozwiązania:

{2,3} {2,4} {3,4}

Pozostałą część 6-cio elementowego zbioru tworzą tc rozwiązania, w których jest baza 1. Odrzucając stację 1 mówimy, żc wartość ograniczenia dolnego funkcji ograniczanej wzrośnie o (122), a więc wyniesie (122 +28 = 150). Następnie przyjmujemy kolejną cechę podziału będzie to baza której odrzucenie będzie kosztowało najwięcej. W naszym przypadku będzie to baza 3, bo jej odrzucenie daje przyrost kilometrażu (110) - z macierzy y. co w sumie daje nam kilometraż przy odrzuceniu bazy 3 równy (148) Jeżeli natomiast dostajemy podzbiór (1,3), to jest pojedyncze rozwiązanie i wobec tego nie szacujemy ograniczenia dolnego na podzbiorze, ale liczymy koszt tego rozwiązania.

Powyższe rozwiązanie przedstawimy za pomocą grafu:

Zbiór możliwych rozwiązań

28

150

Wybraliśmy najbardziej ekonomiczne rozwiązanie t.j. bazy {1,3} więc policzymy ile kilometrów trzeba przebyć korzystając z tych dwóch baz.

4