Материал: 5462
81
8.Проведите аналогию решения методом потенциалов транспортной задачи в матричной форме и сетевой постановке.
Задачи для самостоятельного решения
Найти оптимальное решение транспортной задачи на сети
1.
|
|
|
|
(-100) |
|
|
(-100) |
|
|
|
|
2 |
125 |
3 |
|
|
120 |
|
115 |
|
|
|
110 |
|
|
|
|
(-25) |
(-50) |
|
|
|
|
4 |
(+200) |
1 |
120 |
7 |
165 |
|
|
160 |
120 |
105 |
|
|
6 |
130 |
5 |
|
|
|
|
(+100) |
|
|
|
(-25) |
|
2.
|
|
|
|
(+100) |
|
|
(-50) |
|
|
|
|
2 |
80 |
3 |
|
|
70 |
|
20 |
|
|
|
40 |
|
|
|
|
(-100) |
(-50) |
|
|
|
|
4 |
(+200) |
1 |
100 |
7 |
80 |
|
|
50 |
50 |
100 |
|
|
6 |
40 |
5 |
|
|
|
|
(-50) |
|
|
|
(-50) |
|
3.
|
(-120) |
|
(-90) |
|
|
|
|
|
2 |
80 |
3 |
100 |
(-160) |
|
50 |
|
|
|
||
|
|
|
100 |
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
130 |
60 |
(+400) |
1 |
75 |
|
10 |
|
160 |
|
|
|
|
(+100) |
|
5 (-70) |
|
|
|
|
|
|
|
|
175 |
80 |
|
|
|
75 |
|
|
|
110 |
|
||
|
|
|
|
|
|
|
|
9 |
110 |
18 |
|
40 |
|
|
|
8 |
7 |
6 |
||
|
(-100) |
|
|
|
|
(+200) |
|
|
(-125) |
(-35) |
|
|
|
82
4.
(-70) (-30)
|
2 |
100 |
|
3 |
|
|
|
|
|
|
135 |
(-50) |
|
|
75 |
|
70 |
|
|
|
|
|
|
|
4 |
|
|
(+200) |
1 |
(-20) |
|
|
|
|
|
95 |
|
|
|
|
|
|
|
9 |
|
105 |
55 |
|
|
|
|
|
|
|
|
|
75 |
|
|
|
|
|
|
|
60 |
|
|
5 |
(-30) |
|
|
|
|
|
|
|
|
8 |
100 |
|
|
60 |
|
|
|
|
|
|
|
|
|
(-65) |
7 |
125 |
6 |
|
|
|
|
(-35) |
|
(+100) |
|
|
5.
|
(-180) |
|
|
(-120) |
|
|
|
2 |
70 |
|
3 |
|
|
|
|
|
|
30 |
(-150) |
|
|
80 |
|
|
|
|
|
|
|
|
|
|
4 |
|
(+300) |
1 |
(+200) |
|
50 |
|
|
|
75 |
|
|
|
|
|
|
|
9 |
|
60 |
50 |
|
|
|
|
|
|
|
|
|
110 |
|
|
|
|
|
|
|
100 |
|
120 |
5 |
(-60) |
|
|
|
|
|
||
|
8 |
|
|
|
40 |
|
|
70 |
|
|
|
|
|
|
(-200) |
7 |
80 |
6 |
|
|
|
|
(-190) |
|
(+300) |
|
|
6.
|
|
|
|
|
(-45) |
|
|
|
|
(-120) |
|
|
|
|
|
|
|
|
2 |
110 |
3 |
|
|
|
|
200 |
|
|
|
130 |
|
|
|
|
|
50 |
(+300) |
|
|
|
|
|
|
|
|
|
(-130) |
|
|
|
|
|
8 |
100 |
4 |
(+500) |
1 |
180 |
7 |
90 |
|
|
|
|
|
|
(-200) |
|
85 |
|
|
|
|
150 |
|
50 |
|
80 |
|
|
|
|
6 |
120 |
5 |
|
|
|
|
|
|
|
(-125) |
|
|
|
|
|
(-180) |
|
|
|
|
83
7.
|
(-130) |
|
(-150) |
|
|
|
|
2 |
300 |
3 |
75 |
(+150) |
|
|
|
|
|
|||
|
120 |
|
|
|
|
|
|
|
|
|
|
4 |
|
(+250) |
1 |
(-115) |
|
150 |
|
|
|
80 |
|
|
|
|
|
|
|
9 |
|
210 |
150 |
|
|
|
|
|
|
|
|
|
75 |
|
|
|
|
|
|
|
|
180 |
|
5 |
(-155) |
|
|
|
|
|
|
|
|
8 |
|
|
|
200 |
|
|
70 |
|
|
|
|
|
|
(-150) |
7 |
180 |
6 |
|
|
|
|
(-100) |
|
(+400) |
|
|
8.
|
(-90) |
|
(-150) |
|
|
|
2 |
140 |
3 |
|
|
|
|
|
120 |
(+220) |
|
|
250 |
120 |
|
|
|
|
|
|
4 |
|
|
(+280) |
1 |
(-120) |
130 |
|
|
|
|
8 |
210 |
135 |
|
|
|
|
|
|
|
|
90 |
|
|
|
|
|
|
135 |
|
5 |
(-125) |
|
7 |
70 |
|
180 |
|
|
(-115) |
6 |
|
|
|
|
|
|
|
|
|
|
|
|
(+100) |
|
|
9.
|
(-90) |
|
(-80) |
|
|
|
|
2 |
65 |
3 |
|
|
|
|
|
|
|
35 |
(+130) |
|
|
140 |
|
|
|
|
|
|
|
|
|
|
4 |
|
(+400) |
1 |
(-90) |
|
210 |
|
|
|
120 |
|
|
|
|
|
|
|
9 |
|
|
90 |
|
|
|
|
|
85 |
|
|
|
200 |
|
|
|
|
|
|
|
145 |
|
|
5 |
(-30) |
|
8 |
|
|
|
120 |
|
|
|
150 |
|
|
|
|
|
(-120) |
7 |
300 |
6 |
|
|
|
|
(-80) |
|
(-40) |
|
|
84
10.
|
(-90) |
|
|
(-60) |
|
|
|
2 |
120 |
|
3 |
|
|
|
|
|
|
90 |
(-150) |
|
|
140 |
|
|
|
|
|
|
|
|
|
|
4 |
|
(+200) |
1 |
(+400) |
|
|
|
|
|
170 |
|
|
|
|
|
|
|
9 |
|
40 |
210 |
|
|
|
|
|
|
|
|
|
180 |
|
|
|
|
|
|
|
|
|
60 |
5 |
(-75) |
|
|
|
|
|
|
|
|
8 |
80 |
|
|
130 |
|
|
|
|
|
|
|
|
|
(-80) |
7 |
90 |
6 |
|
|
|
|
(-70) |
|
(-75) |
|
|
Глава 11. Задача коммивояжера
Постановка задачи. Имеется n городов, расстояние между которыми задаются матрицей Сij i, j 1,n . Коммивояжер должен побывать в
каждом городе один раз и вернуться в исходный пункт маршрута, совершив путь минимальной длины. Для некоторых пар i, j
непосредственный переход от i к j может быть запрещен. В этом случае элемент матрицы Сij полагается равным . В других случаях требуют,
чтобы определенная дуга обязательно входила в маршрут.
На каждом шаге описываемого алгоритма задача включает n городов, причем из n шагов маршрута k могут быть уже установлены и нужно выбрать оптимальным образом оставшиеся n k .
Математическая модель задачи
Введем неизвестные величины
xij |
1, если коммивояжер из города i переезжаетв город j ; |
|
0, в противном случае. |
||
|
Пусть С (Сij ) матрица расстояний между городами. Тогда
z |
|
Cij |
xij |
|
|
|
min ; |
(11.1) |
||
|
i |
j |
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
xij |
1, |
j |
1, n ; |
(11.2) |
||||||
i |
1 |
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
||
xij |
1, |
i |
|
1, n ; |
(11.3) |
|||||
j |
1 |
|
|
|
|
|
|
|
|
|
xij – целые. |
(11.4) |
85
Данная задача относится к числу задач целочисленного программирования. Целевая функция z в (11.1) означает длину маршрута для данного плана переездов. Система ограничений (11.2) обеспечивает построение маршрута, при котором коммивояжер въезжает в каждый город только раз, а система ограничений (11.3) – маршрута, когда он выезжает из каждого города раз. Этих ограничений еще недостаточно для постановки задачи, так как они не исключают решения, в котором вместо простого цикла, проходящего через n вершин, отыскиваются два или более отдельных цикла (подцикла), проходящих через меньшее число вершин. На рис. 7 и 8 приведены связанные и несвязанные маршруты
1
|
|
1 |
2 |
4 |
2 |
|
|
4 |
3 |
5 |
3 |
|
|
5 |
|
6 |
|
|
|
6 |
Рис. 7. Вариант замкнутого |
Рис. 8. Пример двух замкнутых |
|
|
маршрута коммивояжера |
несвязанных маршрутов, |
|
|
не являющихся решением |
|
|
задачи коммивояжера |
Поэтому для исключения подобных несвязанных маршрутов задача (11.1 – 11.4) должна быть дополнена ограничениями, обеспечивающими связность цикла:
|
|
|
|
ui u j n xij n 1, i, j 1,n, i j |
(11.5) |
||
Условия (11.5) выражают требование цикличности. Переменные ui и u j
могут принимать произвольные действительные значения.
Введение ограничений (11.5) резко увеличивает размеры модели. Так при n = 50 получается порядка 2500 ограничений. Решение целочисленных задач таких размеров представляет серьезную вычислительную проблему. Между тем во многих практических ситуациях задача коммивояжера является стандартной подзадачей, решение которой должно выполняться многократно. При решении задачи используются различные, хорошо зарекомендовавшие себя эвристические методы и точные методы, в основе