МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ МАДИ (ТУ) КУРСОВАЯ РАБОТА ПО ДИСЦИПЛИНЕ: МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ СИСТЕМ Выполнил: Белоногов М.В. Группа 4ВЭДС3 Проверил: Беляков Г.С. Москва 1999-2000 Раздел 1. Выбор оптимального маршрута поездки. Постановка задачи: Машина с инкассатором ежедневно забирает выручку 4-х торговых точек (пункты Б, В, Г, Д), расположенных на разных улицах города и отвозит ее в банк (пункт А). Определено время на проезд по различным улицам с учетом интенсивности движения по ним транспортного потока. Требуется найти маршрут движения инкассаторской машины, который начинался и заканчивался бы в пункте А, позволял посетить каждую торговую точку и проехать по соответствующей улице только один раз и характеризовался минимальными затратами времени на поездку. Маршрут должен включать переезд из пункта Б в пункт Г. Порядок решения задачи: 1. Определить кратчайшие расстояния между различными парами пунктов используя алгоритм поиска кратчайших путей на циклической сети.
    А 1 Б
    4 В 2
    Д 3 Г Найдем кратчайшие расстояния до пункта А. пункт 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=9-0 l4Д ? у4 - уД 8,32?9-17 lД4 = уД - у4 8=17-9 lДВ ? уД - уВ 12?17-13 lBA = yB - yA 13=13-0 lBД ? yB - yД 12,32?13-17 lBБ ? yB - yБ 15,32?13-16,64 lB4 ? yB - y4 7?13-9 lB1 ? yB - y1 10?13-8,32 lБВ ? уБ - уВ 15?16,64-13 lБ1 = уБ - у1 8,32=16,64-8,32 l1А = у1 - уА 8,32=8,32-0 l1В ? у1 - уВ 9?8,32-13 l1Б ? у1 - уБ 8?8,32-16,64 Чтобы найти кратчайшие пути, найдем дуги для которых выполняется условие: 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 = ? ? lij * xij
    i=1 j=1 при следующих ограничениях: * из каждого города i нужно уехать только один раз n+1 ? xij = 1 i=1, ......, n+1 j=1 * в каждый город j нужно приехать только один раз:
    n+1
    ? xij = 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. ............