4736387686

wagony od tych stacji, w których wystąpiła nadwyżka pustych wagonów. Tabela podaje odległości między stacjami oraz przywóz i wywóz pełnych wagonów.

Stacje	SI | S2 | S3 | S4 | S5 | S6						Przywóz pełnych wagonów
	odległości (w km)
SI	0	20	60	30	40	22	70
S2		0	30	50	90	75	40
S3			0	25	23	48	10
S4				0	39	45	20
S5					0	84	10
S6						0	30
Wywóz pełnych wagonów	30	40	50	30	25	5	180

Należy ustalić taki plan przemieszczeń pustych wagonów pomiędzy stacjami. Aby łączny przebieg pustych wagonów był możliwie najmniejszy.

>    określić popyt na puste wagony i podaż pustych wagonów,

>    zapisać problem w postaci makiety zamkniętego zadania transportowego.

Problem komiwojażera

Problem komiwojażera (TSP - ang. traveling salesman problem) jest zagadnieniem z teorii grafów, polegającym na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym. Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość pomiędzy każdą parą miast. Można rozróżnić symetryczny problem komiwojażera (STSP), polegający na tym, że odległość pomiędzy miastami A i B jest zawsze taka sama, oraz asymetryczny problem (ATSP), gdzie odległość od miasta A do miasta B może być inna, niż odległość od miasta B do miasta A.

Znane są metody optymalizacyjne - przybliżone rozwiązujące problem komiwojażera bazujące, np. na algorytmie mrówkowym. Współcześnie wobec możliwości komputerowego wspomagania rozwiązywania problemów optymalizacji, efektywnym sposobem generowania rozwiązań problemu komiwojażera, nawet dla złożonych problemów, może być zastosowanie także metod dokładnych, takich jak programowanie liniowe.

Model programowania liniowego problemu komiwojażera zakłada minimalizcję funkcji celu, wyrażającej sumę wszystkich cykli Hamiltona w grafie:

ŚŹ^cu'^xu ^^min

Przy ograniczeniach

Y₄x_{i j} =1; (i = 1,2,3,...,n)

>19<