Определение рационального варианта размещения производственно-хозяйственных предприятий (на примере АБЗ) и выбор оптимального маршрута поездки коммивояжераРефераты >> Математика >> Определение рационального варианта размещения производственно-хозяйственных предприятий (на примере АБЗ) и выбор оптимального маршрута поездки коммивояжера
Чтобы найти кратчайшие пути, найдем дуги для которых выполняется условие:
lij = yi - yj
Таковыми являются:
l4A = у4 - уА 9=9-0
lД4 = уД – у4 8=17-9
lBA = yB - yA 13=13-0
lБ1 = уБ – у1 8,32=16,64-8,32
l1А = у1 – уА 8,32=8,32-0
Кратчайшие расстояния до пункта А равны:
пункт |
4 |
Д |
Б |
1 |
В |
расстояние до А |
9 |
17 |
16,64 |
8,32 |
13 |
Аналогичным образом находятся кратчайшие расстояния до других пунктов.
2. Построить матрицу кратчайших расстояний между пунктами А, Б, В, Г, Д.
А |
Б |
В |
Г |
Д | |
А |
--- |
16 |
13,32 |
--- |
17,64 |
Б |
16,64 |
--- |
15 |
21 |
--- |
В |
13 |
15,32 |
--- |
15 |
12,32 |
Г |
--- |
21,64 |
15,32 |
--- |
16 |
Д |
17 |
--- |
12 |
16,32 |
--- |
3. Математическая модель задачи коммивояжера:
Найти минимальное значение целевой функции z
n+1 n+1
min z = S S lij * xij
i=1 j=1
при следующих ограничениях:
n из каждого города i нужно уехать только один раз
n+1
S xij = 1 i=1, , n+1
j=1
n в каждый город j нужно приехать только один раз:
n+1
S xij = 1 j=1, , n+1
i=1
n переменные xij могуть принимать одно из двух значений: 0 или 1,
1 - если в искомый маршрут входит переезд из пункта i в пункт j
0 - в противном случае
n решение есть простой цикл
4. Решение задачи:
А |
Б |
В |
Г |
Д | |
А |
--- |
16 |
13,32 |
--- |
17,64 |
Б |
16,64 |
--- |
15 |
21 |
--- |
В |
13 |
15,32 |
--- |
15 |
12,32 |
Г |
--- |
21,64 |
15,32 |
--- |
16 |
Д |
17 |
--- |
12 |
16,32 |
--- |
Б – Г, Д – В, В – А, А – Б, Г – Д
Так как маршрут должен включать переезд из пункта Б в пункт Г, то первым разрешающим элементом будет элемент 21. (1) Обводим его в кружок. (2)Зачеркиваем все оставшиеся элементы в строке и столбце содержащем элемент 21. (3)Зачеркиваем также элемент 21,64 , чтобы исключить повторное посещение пунктов. (4)Находим наибольшие элементы и зачеркиваем их до тех пор пока в какой-нибудь строке или столбце не появится один незачеркнутый элемент, теперь он будет разрешающим. Повторяем действия (1), (2), (3), (4) до тех пор пока не останется последний разрешающий элемент.
В итоге искомый маршрут будет проходить через пункты:
А – Б – Г – Д – В – А
min z = 16+21+16+12+13 = 78
Раздел 2.
Определение рационального варианта размещения производственных предприятий (на примере АБЗ).
Постановка задачи:
В 2000г планируется осуществить ремонт и реконструкцию дорожной сети некоторого района. Территория района разбита на 4 части, потребности которых в асфальтобетоне в 2000г будут составлять:
B1 = 50.000 т
B2 = 60.000 т
B3 = 45.000 т
B4 = 70.000 т
Для удовлетворения потребностей в асфальтобетоне планируется разместить сеть полустационарных асфальтобетонных заводов. На территории района выбрано 4 возможных пункта размещения заводов, для каждого пункта рассматривается 3 варианта мощности заводов – 10, 25, 50 т аб./час.
Известны затраты на приготовление аб в каждом пункте и доставку его потребителям. Требуется найти в каких пунктах и какой мощности следует разместить аб заводы, чтобы суммарные затраты на его приготовление и доставку потребителям были минимальными.
Затраты на приготовление аб, руб
мощность АБЗ |
Приведенные затраты на приготов-е 1т аб АБЗ, располож-м в пункте, руб, Cpi + E*Kpi уд | ||||
т/час |
тыс. т/год |
1 |
2 |
3 |
4 |
10 |
18 |
484 |
489 |
495 |
481 |
25 |
45 |
423 |
428 |
435 |
420 |
50 |
90 |
405 |
410 |
416 |
401 |