Создан заказ №1857082
22 марта 2017
открытая Вводим фиктивного потребителя с потребностью 200-100 = 100 ед груза и с тарифами на доставку равными 0
Как заказчик описал требования к работе:
Необходимо решить 4 задачи с подробными пояснениями. 1 вариант
Фрагмент выполненной работы:
открытая. Вводим фиктивного потребителя с потребностью 200-100 = 100 ед. груза и с тарифами на доставку равными 0.
Для решения задачи полагаем, что стоимости перевозки единицы груза по запрещенным маршрутам равны достаточно большому числу М > 0. Далее эта М-задача решается обычным методом потенциалов, но потенциалы будут зависеть от коэффициента М. Если оптимальный план М-задачи содержит положительные перевозки по запрещенным маршрутам, то исходная ТЗ неразрешима (множество ее планов пусто). (работа была выполнена специалистами Автор 24) В противном случае получаем решение исходной ТЗ.
Предварительный этап. Составляем методом «минимального элемента» исходный опорный план (табл. 1).
Итерация 1. Вычисляем потенциалы и проверяем план на оптимальность (см. табл. 1).
Таблица 1
Vj
-31750-14732000Ui
Запас
М
5
4
2
0 30
- - 20 10 -
2
5
М
3
0 50
20 30 - - -
3
2
М
5
0 120
20 - - - 100
Потребность 40
30 20
10
100
Число занятых клеток равно 6 и совпадает с рангом матрицы ограничений ТЗ:
r = m + n – 1 = 3 + 5 – 1 = 7.
Вводим нулевую поставку через ячейку (1,5):
Таблица 2
Vj
-31750-14732000Ui
Запас
М
5
4
2
0 30
- - 20 10 0
2
5
М
3
0 50
20 30 - - -
3
2
М
5
0 120
20 - - - 100
Потребность 40
30 20
10
100
Итерация 1. Для проверки полученного опорного плана на оптимальность находим систему потенциалов для занятых клеток (xij > 0).
Для этого, например, полагаем U1 = 0 (записываем U1 = 0 слева в табл. 2).
Таблица 2
Vj
-31750-14732000Ui 3 6 4 2 0 Запас
0 3
М 6 5
4
2
0 30
- - 20 10 0
-1
2
5 3
М 1
3 -1 0 50
20+ 30- - - -
0
3 6 2 4 М 5
5
0 120
20- +- - - 100
Потребность 40
30 20
10
100
Далее вычисляем сумму потенциалов для каждой из свободных клеток и записываем их в верхнем левом углу. Так как для клеток (1,2) и (3,2) критерий оптимальности не выполняется:
U1 + V2 = 6 >5,
U3 + V2 = 6 > 2,
то полученный опорный план не оптимальный. Так как
32 = U3 + V2 – C32 = 4
то в клетку (3,1), проставляем некоторое число .
Для того чтобы не нарушился баланс в 3-й строке, вычитаем из величины перевозки, стоящей в клетке (3,1), прибавляем к X21 = 20, вычитаем от X23 ADVANCE \d 4 ADVANCE \u 4 , т.е. составляем цикл:
(3,2) → (3,1) → (2,1) → (2,2)
Знаки «+» и «–» в клетках чередуются.
Заметим, что движение от одной клетки к другой происходит только по занятым, кроме первой, в которую проставляется. Максимальное значение равно наименьшему уменьшаемому: = 20. Если взять больше, то получаем отрицательную величину в плане перевозок, а если меньше, то нарушается опорность плана.
Новый опорный план приведен в табл. 3
Таблица 3
Vj
-31750-14732000Ui -1 2 4 2 0 Запас
0 -1
М 2 5
4
2
0 30
- - 20 10 0
3
2
5 7
М 5
3 3 0 50
40 10- - - +
0 -1
3
2 4 М 2
5
0 120
20+ - - 100-
Потребность 40
30 20
10
100
В клетке (2,5) имеем
,
т.е. план не является оптимальным. Проставляем в эту клетку и составляем замкнутый маршрут. Получаем . Опорный план приведен в табл. 4.
Таблица 3
Vj
-31750-14732000Ui 2 2 4 2 0 Запас
0 2
М 2 5
4
2
0 30
- - 20 10 0
0
2 2 5 4
М 2
3
0 50
40
- - 10
0 2
3
2 4 М 2
5
0 120
30 - - 90
Потребность 40
30 20
10
100
Проверяем план на оптимальность. Так как для всех свободных клеток
,
то план – оптимальный и не содержит положительных перевозок по запрещенным маршрутам.
Минимальные транспортные расходы составляют
4*20+2*10+0*0+2*40+0*10+2*30+0*90 = 240
Задание №4
Решите методом ветвей и границ следующую задачу коммивояжера:
1.
Решение:
42545015684500
di =min(dij )
M 31 15 19 8 55 8
19 M 22 31 7 35 7
25 43 M 53 57 16 16
5 50 49 M 39 9 5
24 24 33 5 M 14 5
34 26 6 3 36 M 3
Затем вычитаем di из элементов рассматриваемой строки.
9340854572000 M 23 7 11 0 47
12 M 15 24 0 28
9 27 M 37 41 0
0 45 44 M 34 4
19 19 28 0 M 9
31 23 3 0 33 M
dj= min(dij) 0 19 3 0 0 0
После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины di и dj называются константами приведения.
42989512763500
M 23 7 11 0 47
12 M 15 24 0 28
9 27 M 37 41 0
0 45 44 M 34 4
19 19 28 0 M 9
31 23 3 0 33 M
Сумма констант приведения определяет нижнюю границу H:
H = ∑di + ∑dj = 8+7+16+5+5+3+0+19+3+0+0+0 = 66
Шаг №1.
Считаем для нулей сумму новых констант приведения:
39370016764000
di
M 4 4 11 0(4) 47 4
12 M 12 24 0(12) 28 12
9 8 M 37 41 0(12) 8
0(13) 26 41 M 34 4 4
19 0(4) 25 0(0) M 9 0
31 4 0(4) 0(0) 33 M 0
dj 9 4 4 0 0 4 0
ʘ(1,5) = 4 + 0 = 4;
ʘ(2,5) = 12 + 0 = 12;
ʘ(3,6) = 8 + 4 = 12;
ʘ (4,1) = 4 + 9 = 13;
ʘ (5,2) = 0 + 4 = 4;
ʘ (5,4) = 0 + 0 = 0;
ʘ (6,3) = 0 + 4 = 4;
ʘ (6,4) = 0 + 0 = 0
Наибольшая сумма констант приведения для ребра (4,1) равна 13.
Множество разбивается на два подмножества (4,1) и (4,1).
Исключение ребра (4,1) проводим путем замены элемента d41= 0 на «М».
63515240000
di
M 4 4 11 0 47 0
12 M 12 24 0 28 0
9 8 M 37 41 0 0
M 26 41 M 34 4 4
19 0 25 0 M 9 0
31 4 0 0 33 M 0
dj 9 0 0 0 0 0 13
Нижняя граница гамильтоновых циклов этого подмножества:
H(4,1) = 66 + 13 = 79
Включение ребра (4,1) проводится путем исключения всех элементов 4-ой строки и 1-го столбца, а элемент d14 заменяем на «М».
i j 2 3 4 5 6 di
1 3302023495004 4 M 0 47 0
2 M 12 24 0 28 0
3 8 M 37 41 0 0
5 0 25 0 M 9 0
6 4 0 0 33 M 0
dj 0 0 0 0 0 0
Нижняя граница подмножества (4,1) равна:
H(4,1) = 66 + 0 = 66 ≤ 79
Поскольку нижняя граница этого подмножества (4,1) меньше, чем подмножества (4,1), то ребро (4,1) включаем в маршрут с границей H = 66.
Шаг №2.
i j 2 3 4 5 6 di
42164023495001 4 4 M 0(4) 47 4
2 M 12 24 0(12) 28 12
3 8 M 37 41 0(17) 8
5 0(4) 25 0(0) M 9 0
6 4 0(4) 0(0) 33 M 0
dj 4 4 0 0 9 0
Наибольшая сумма констант приведения равна 17 для ребра (3,6).
Разбивается на два подмножества (3,6) и (3,6).
Исключение ребра (3,6) проводим путем замены элемента d36 = 0 на «М».
i j 2 3 4 5 6 di
42164023495001 4 4 M 0 47 0
2 M 12 24 0 28 0
3 8 M 37 41 M 8
5 0 25 0 M 9 0
6 4 0 0 33 M 0
dj 0 0 0 0 9 17
Нижняя граница гамильтоновых циклов этого подмножества:
H(3,6) = 66 + 17 = 83
Включение ребра (3,6)
i j 2 3 4 5 di
1 1905046990004 4 M 0 0
2 M 12 24 0 0
5 0 25 0 M 0
6 4 M 0 33 0
dj 0 4 0 0 4
Нижняя граница подмножества (3,6) равна:
H(3,6) = 66 + 4 = 70 ≤ 83
Поскольку нижняя граница этого подмножества (3,6) меньше, чем подмножества (3,6), то ребро (3,6) включаем в маршрут с границей H = 70.
Шаг №3...Посмотреть предложения по расчету стоимости
Заказчик
заплатил
заплатил
20 ₽
Заказчик не использовал рассрочку
Гарантия сервиса
Автор24
Автор24
20 дней
Заказчик принял работу без использования гарантии
23 марта 2017
Заказ завершен, заказчик получил финальный файл с работой
5
открытая Вводим фиктивного потребителя с потребностью 200-100 = 100 ед груза и с тарифами на доставку равными 0.jpg
2020-08-30 13:00
Последний отзыв студента о бирже Автор24
Общая оценка
4.1
Положительно
Отличный автор! Очень хорошо разбирается в информатике, выш. мате. Спасибо за помощь
Хочешь такую же работу?
300 ₽
