Создан заказ №1044792
21 марта 2016
открытая Для решения задачи полагаем что стоимости перевозки единицы груза по запрещенным маршрутам равны достаточно большому числу М >
Как заказчик описал требования к работе:
Необходимо решить 4 задачи. Подробности во вложении.
Фрагмент выполненной работы:
открытая.
Для решения задачи полагаем, что стоимости перевозки единицы груза по запрещенным маршрутам равны достаточно большому числу М > 0. Далее эта М-задача решается обычным методом потенциалов, но потенциалы будут зависеть от коэффициента М. Если оптимальный план М-задачи содержит положительные перевозки по запрещенным маршрутам, то исходная ТЗ неразрешима (множество ее планов пусто). В противном случае получаем решение исходной ТЗ. (работа была выполнена специалистами author24.ru)
Предварительный этап. Составляем методом «минимального элемента» исходный опорный план (табл. 1).
Итерация 1. Вычисляем потенциалы и проверяем план на оптимальность (см. табл. 1).
Таблица 1
Vj
-31750-14732000Ui
15 33-М 32-М 10 15-М
0
15 33-М 13 32-М М
10 15-М 0
0+
100-
М-15
М
18
17 М-5
14
0
100- 50 50 310
-2 13
11 31-М М 30-М 13
8 13-М 0
300
В клетке (2,4) имеем
,
т.е. планне является оптимальным. Проставляем в эту клеткуи составляем замкнутый маршрут. Получаем . Опорный план приведен в табл. 2.
Итерация 2.
Таблица 2
Vj
-31750-14732000Ui
15 14 13 10 -4
0
15 14 13 32-М М
10 -4 0
100
0+
4 19
М
18
17
14
0
50 50 100 310
-2 13
11 12 М 11 13
8 -6 0
300-
В клетке (3,1) имеем
,
т.е. планне является оптимальным. Проставляем в эту клеткуи составляем замкнутый маршрут. Получаем . Опорный план приведен в табл. 3.
Таблица 3
Vj
-31750-14732000Ui
13 14 13 10 -4
0 13
15 14 13 13 М
10 -4 0
100-
4 17
М
18
17
14
0
50- 50 100+ 310
-2 13
11 12 М 11 13
8 -6 0
100
200
Итерация 3.
В клетке (1,2) имеем
,
т.е. план не является оптимальным. Проставляем в эту клеткуи составляем замкнутый маршрут. Получаем . Опорный план приведен в табл. 3.
Таблица 3
Vj
-31750-14732000Ui
13 13 13 10 -4
0 13
15
13 13 М
10 -4 0
50
50
4 17
М 17 18
17
14
0
50 150 310
-2 13
11 11 М 11 13
8 -6 0
100
200
Проверяем план на оптимальность. Так как для всех свободных клеток
,
то план – оптимальный и не содержит положительных перевозок по запрещенным маршрутам.
Минимальные транспортные расходы составляют
13*50 + 10*50 + 17*50 + 14*150 + 0*310 + 11*100 + 8*200 = 6800
Задание №4
Решите методом ветвей и границ следующую задачу коммивояжера:
23.
Решение:
42545156845
di =min(dij )
M 36 33 35 41 32 32
19 M 29 31 26 18 18
57 51 M 44 51 7 7
25 20 22 M 24 26 20
33 41 28 23 M 53 23
19 54 24 10 41 M 10
Затем вычитаем di из элементов рассматриваемой строки.
933983457200 M 4 1 3 9 0
1 M 11 13 8 0
50 44 M 37 44 0
5 0 2 M 4 6
10 18 5 0 M 30
9 44 14 0 31 M
dj= min(dij) 1 0 1 0 4 0
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
43007512741900
M 4 0 3 5 0
0 M 10 13 4 0
49 44 M 37 40 0
4 0 1 M 0 6
9 18 4 0 M 30
8 44 13 0 27 M
Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj = 32+18+7+20+23+10+1+0+1+0+4+0 = 116
Шаг №1.
Считаем для нулей сумму новых констант приведения:
87055167676
di
M 4 0(1) 3 5 0(0) 0
0(4) M 10 13 4 0(0) 0
49 44 M 37 40 0(37) 37
4 0(4) 1 M 0(4) 6 0
9 18 4 0(4) M 30 4
8 44 13 0(8) 27 M 8
dj
4 4 1 0 4 0 0
Наибольшая сумма констант приведения для ребра (3,6) равна 37.
Множество разбивается на два подмножества (3,6) и (3,6).
Исключение ребра (3,6) проводим путем замены элемента d36 = 0 на «–».
84455152400
di
M 4 0 3 5 0 0
0 M 10 13 4 0 0
49 44 M 37 40 M 37
4 0 1 M 0 6 0
9 18 4 0 M 30 0
8 44 13 0 27 M 0
dj
0 0 0 0 0 0 37
Нижняя граница гамильтоновых циклов этого подмножества:
H(3,6) = 116 + 37 = 153
Включение ребра (3,6) проводится путем исключения всех элементов 3-ой строки и 6-го столбца, а элемент d36 заменяем на «М».
i j 1 2 3 4 5 di
1 1333511430M 4 0 3 5 0
2 0 M 10 13 4 0
4 4 0 1 M 0 0
5 9 18 4 0 M 0
6 8 44 M 0 27 0
dj
0 0 0 0 0 0
Нижняя граница подмножества (3,6) равна:
H(3,6) = 116 + 0 = 116 ≤ 153
Поскольку нижняя граница этого подмножества (3,6) меньше, чем подмножества (3,6), то ребро (3,6) включаем в маршрут с новой границей H = 116.
Шаг №2.
i j 419101657351 2 3 4 5 di
1 M 4 0(4) 3 5 3
2 0(8) M 10 13 4 4
4 4 0(4) 1 M 0(4) 0
5 9 18 4 0(4) M 4
6 8 44 M 0(8) 27 8
dj
4 4 1 0 4 0
Наибольшая сумма констант приведения равна 8 для ребра (2,1).
Разбивается на два подмножества (2,1) и (2,1).
Исключение ребра (2,1) проводим путем замены элемента d21 = 0 на «–».
i j 1 2 3 4 5 di
1 34925311150M 4 0 3 5 0
2 M M 10 13 4 4
4 4 0 1 M 0 0
5 9 18 4 0 M 0
6 8 44 M 0 27 0
dj
4 0 0 0 0 8
Нижняя граница гамильтоновых циклов этого подмножества:
H(2,1) = 116 + 8 = 124
Включение ребра (2,1)
i j 01727202 3 4 5 di
1 M 0 3 5 0
4 0 1 M 0 0
5 18 4 0 M 0
6 44 M 0 27 0
dj
0 0 0 0 0
Нижняя граница подмножества (2,1) равна:
H(2,1) = 116 + 0 = 116 ≤ 124
Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2,1), то ребро (2,1) включаем в маршрут с новой границей H = 116.
Шаг №3...Посмотреть предложения по расчету стоимости
Заказчик
заплатил
заплатил
200 ₽
Заказчик не использовал рассрочку
Гарантия сервиса
Автор24
Автор24
20 дней
Заказчик принял работу без использования гарантии
22 марта 2016
Заказ завершен, заказчик получил финальный файл с работой
5
открытая
Для решения задачи полагаем что стоимости перевозки единицы груза по запрещенным маршрутам равны достаточно большому числу М >.docx
2016-03-23 19:57
Последний отзыв студента о бирже Автор24
Общая оценка
5
Положительно
Спасибо большое за выполненную работу! Работа выполнена быстро, качественно и в срок, Рекомендую данного автора.
Хочешь такую же работу?
300 ₽
