Учебная работа № 1431. Определение рационального варианта размещения производственнохозяйственных предприятий (на примере АБЗ) и выбор оптимального маршрута поездки коммивояжера
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
МАДИ (ТУ)
КУРСОВАЯ РАБОТА ПО ДИСЦИПЛИНЕ: МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ СИСТЕМ
Выполнил: Белоногов М.В.
Группа 4ВЭДС3
Проверил: Беляков Г.С.
Москва 19992000
Раздел 1.
Выбор оптимального маршрута поездки.
Постановка задачи:
Машина с инкассатором ежедневно забирает выручку 4х торговых точек (пункты Б, В, Г, Д), расположенных на разных улицах города и отвозит ее в банк (пункт А). Определено время на проезд по различным улицам с учетом интенсивности движения по ним транспортного потока. Требуется найти маршрут движения инкассаторской машины, который начинался и заканчивался бы в пункте А, позволял посетить каждую торговую точку и проехать по соответствующей улице только один раз и характеризовался минимальными затратами времени на поездку. Маршрут должен включать переезд из пункта Б в пункт Г.
Порядок решения задачи:
1. Определить кратчайшие расстояния между различными парами пунктов используя алгоритм поиска кратчайших путей на циклической сети.
Найдем кратчайшие расстояния до пункта А.
пункт i | А | Б | В | Д | 1 | 4 |
yi | 0 | ¥ | ¥ | ¥ | ¥ | ¥ |
28 | 13 | 17 | 8,32 | 9 | ||
16,64 |
Первоначально принимаем расстояния до пункта А равными бесконечности, а расстояние от А до самого себя равным нулю.
Затем пересчитываем величины yi используя правило:
Если yj + lij < yi , то величина yi = yj + lij , в противном случае yi оставляем без изменений.Расчет начинаем с пункта А и дуг, которые в него входят.
yA + l4A =0+9=9 < y4 =¥Þ y4 =9
yA + lBA =0+13=13 < yB =¥Þ yB =13
yA + l1A =0+8,32=8,32 < y1 =¥Þ y1 =8,32
Теперь рассматриваем пункт i для которого yi перестала быть равной бесконечности и дуги, которые в него входят.
y4 + lB4 =9+7=16 > yB =13
y4 + lД 4 =9+8=17 < уД =¥Þ yД =17
yВ + lДВ =13+12=25 > yД =17
yВ + lБВ =13+15=28 < уБ =¥Þ yБ =28
yВ + l1В =13+9=22 > у1 =8,32
y1 + lВ1 =8,32+10=18,32 > yВ =13
y1 + lБ1 =8,32+8,32=16,64 < уБ =28 Þ yБ =16,64
yД + l4Д =8,32+17=25,32 > y4 =9
yД + lВД =17+12,32=29,32 > yВ =13
yБ + lВБ =16,64+15,32=31 > yВ =13
yБ + l1Б =16,64+8=24,64 > y1 =8,32
Теперь проверим условие lij ³ yi yj для всех дуг сети.
l4A = у4 уА 9=90
l4Д >у4 – уД 8,32>917
lД4 = уД – у4 8=179
lДВ >уД – уВ 12>1713
lBA = yB yA 13=130
lBД > yB – yД 12,32>1317
lBБ > yB – yБ 15,32>1316,64
lB4 > yB – y4 7>139
lB1 > yB – y1 10>138,32
lБВ >уБ уВ 15>16,6413
lБ1 = уБ – у1 8,32=16,648,32
l1А = у1 – уА 8,32=8,320
l1В >у1 – уВ 9>8,3213
l1Б >у1 – уБ 8>8,3216,64
Чтобы найти кратчайшие пути, найдем дуги для которых выполняется условие:
lij = yi yj
Таковыми являются:
l4A = у4 уА 9=90
lД4 = уД – у4 8=179
lBA = yB yA 13=130
lБ1 = уБ – у1 8,32=16,648,32
l1А = у1 – уА 8,32=8,320
Кратчайшие расстояния до пункта А равны:
пункт | 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 = SSlij * xij
i=1 j=1
при следующих ограничениях:
из каждого города i нужно уехать только один раз
n+1
Sxij = 1 i=1, ……, n+1
j=1
в каждый город j нужно приехать только один раз:
n+1
Sxij = 1 j=1, ……, n+1
i=1
переменные xij могуть принимать одно из двух значений: 0 или 1,
1 если в искомый маршрут входит переезд из пункта i в пункт j
0 в противном случае
решение есть простой цикл
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) до тех пор пока не останется последний разрешающий элемент.
В итоге искомый маршрут будет проходить через пункты:
А – Б – Г – Д – В – А
minz = 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т аб АБЗ, расположм в пункте, руб, Cp i + E*Kp i уд | ||||
т/час | тыс. т/год | 1 | 2 | 3 | 4 |
10 | 18 | 484 | 489 | 495 | 481 |
25 | 45 |