4736387687

i>u=i;U=u*-.«)

w, - Uj + nXjj < n —1; (i,j = 2,3,...,n;i * y) jc, _;. e C⁺

gdzie:

w - liczbmiast.

Ci j - odległość pomiędzy dwoma sąsiednimi miastami,

X_u - zmienna incydencji, określająca występowanie danego zabiegu, m, - dodatkowa zmienna ciągłości cyklu Hamiltona.

Zadanie komiwojażera można rozwiązać stosując algorytm simpleks. Dyskretyzację zmiennych do liczb całkowitych można przeprowadzić metodą Land Doiga.

Zadanie 4

Komiwojażer ma odwiedzić klientów w czterech punktach miasta i wrócić do domu. Mieszka w pobliżu klienta k2. Dana jest macierz odległości między tymi punktami:

KI

K2

jO_

K4

KI

14

10

K2

15

3

K3

II

6

11

K4

20

10

9

A)    Ustalić, o ile minimalna droga przynajmniej się wydłuży, jeżeli zamknięty zostanie odcinek

<k3,k2>.

B)    Podać kolejność odwiedzania klientów.

Zadanie 5

Mechanik ma naprawić uszkodzony sprzęt w kilku miejscach, a następnie wrócić do domu. Mieszka w pobliżu jednego z tych punktów. Dana jest macierz odległości między tymi punktami:

pi

P2

P3

P4

PI

14

9

P2

15

P3

20

6

11

P4

11

10

9

A)    Mechanik mieszka w pobliżu punktu Pr Jaka powinna być kolejność ich odwiedzania?

B)    Ile wynosiłaby długość drogi, gdyby mechanik poruszał się w kierunku przeciwnym do wyznaczonej trasy optymalnej? Kiedy długości obu tras (wyznaczonej i przeciwnej do wyznaczonej) byłyby takie same?

C)    Ustalić, o ile wydłuży się przynajmniej najkrótsza droga, jeżeli z powodu remontu ulicy zamknięty zostanie odcinek <pl,p4>.

D)    Ustalić długość najkrótszej drogi, gdy zablokowany zostanie odcinek <p2,p3>

>20<