6570141612

Hamiltona w G o minimalnym koszcie. W wielu praktycznych sytuacjach, biorąc pod uwagę wierzchołki i oraz j należące do E, najtaniej jest iść bezpośrednio z i do j, bez odwiedzania żadnego pośredniego wierzchołka. Jeśli taka reguła jest zawsze spełniona, funkcja kosztu w(e) spełnia zasadę nierówności trójkąta, tj. dla wszystkich i,j,k E ^zachodzi zależność:

< W (e(i,k)) + W (<*(/. kj)

Rozważając długość drogi jako funkcję kosztu, nierówność trójkąta jest zazwyczaj spełniona w sieciach komunikacyjnych, ponieważ drogi stanowią odcinki łączące punkty na przestrzeni euklidesowej.

3.2.    Problem plecakowy

Problem plecakowy można zdefiniować w następujący sposób: złodziej, rabując sklep, znalazł n przedmiotów, i-ty przedmiot jest wart Cj i waży w_it gdzie q oraz Wi są nieujemnymi liczbami. Złodziej chce zabrać ze sobą jak najwięcej przedmiotów, przy czym sumaryczna waga zabieranych przedmiotów nie może przekroczyć B (ograniczona pojemność plecaka). Rozwiązanie problemu polega na takim doborze przedmiotów, aby ich sumaryczna wartość była jak największa, przy jednoczesnym spełnieniu ograniczenia maksymalnej ich wagi. Na potrzeby niniejszej pracy rozważany jest dyskretny problem plecakowy, tj. taki, w którym nie ma możliwości zabrania części danego przedmiotu. Rozwiązanie problemu opiera się na decyzji czy zabrać dany przedmiot czy nie. Formalnie problem można zdefiniować następująco:

•    Plecak o maksymalnej pojemności B

•    N jest zbiorem elementów

•    Ci jest wartością j-tego elementu ze zbioru N

•    Wj jest wagą j-tego elementu ze zbioru N

•    Xj jest decyzją dla j-tego elementu ze zbioru N (0: nie zostaje zabrany, 1: zostaje zabrany)

Dla Y!j=t WjXj < B

zmaksymalizuj ^cj^xj

Problem ten występuje przy podejmowaniu decyzji o załadunku pojazdów w HUB-ie i towarzyszy procesowi planowania dostaw.

3.3.    Pojemnościowy problem marszrutyzacji

Zakłada się, że zbiór klientów jest z góry znany, stały i zdefiniowany, tj. dla każdego klienta znana jest jego pozycja oraz zapotrzebowanie (ilość dóbr, która ma zostać dostarczona). Pojazdy są identyczne, przypisane do jednego HUB-a, jedyną ich cechą jest maksymalna

14