Определение рационального варианта размещения производственно-хозяйственных предприятий (на примере АБЗ) и выбор оптимального маршрута поездки коммивояжера
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
МАДИ (ТУ)
КУРСОВАЯ РАБОТА ПО ДИСЦИПЛИНЕ: МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ СИСТЕМ
Выполнил: Белоногов М.В.
Группа 4ВЭДС>3>
Проверил: Беляков Г.С.
Москва 1999-2000
Раздел 1.
Выбор оптимального маршрута поездки.
Постановка задачи:
Машина с инкассатором ежедневно забирает выручку 4-х торговых точек (пункты Б, В, Г, Д), расположенных на разных улицах города и отвозит ее в банк (пункт А). Определено время на проезд по различным улицам с учетом интенсивности движения по ним транспортного потока. Требуется найти маршрут движения инкассаторской машины, который начинался и заканчивался бы в пункте А, позволял посетить каждую торговую точку и проехать по соответствующей улице только один раз и характеризовался минимальными затратами времени на поездку. Маршрут должен включать переезд из пункта Б в пункт Г.
Порядок решения задачи:
Определить кратчайшие расстояния между различными парами пунктов используя алгоритм поиска кратчайших путей на циклической сети.
А
1 Б
4
В 2
Д
3 Г
Найдем кратчайшие расстояния до пункта А.
|
пункт i |
А |
Б |
В |
Д |
1 |
4 |
|
y>i> |
0 |
|
|
|
|
|
|
28 |
13 |
17 |
8,32 |
9 |
||
|
16,64 |
Первоначально принимаем расстояния до пункта А равными бесконечности, а расстояние от А до самого себя равным нулю.
Затем пересчитываем величины y>i> используя правило:
Если y>j> + l>ij> y>i> , то величина y>i> = y>j> + l>ij> , в противном случае y>i> оставляем без изменений. Расчет начинаем с пункта А и дуг, которые в него входят.
y>A> + l>4A>=0+9=9 y>4>= y>4>=9
y>A> + l>BA>=0+13=13 y>B>= y>B>=13
y>A> + l>1A>=0+8,32=8,32 y>1>= y>1>=8,32
Теперь рассматриваем пункт i для которого y>i> перестала быть равной бесконечности и дуги, которые в него входят.
y>4> + l>B4>=9+7=16 y>B>=13
y>4> + l>Д>>4>=9+8=17 у>Д>= y>Д>=17
y>В> + l>ДВ>=13+12=25 y>Д>=17
y>В> + l>БВ>=13+15=28 у>Б>= y>Б>=28
y>В> + l>1В>=13+9=22 у>1>=8,32
y>1> + l>В1>=8,32+10=18,32 y>В>=13
y>1> + l>Б1>=8,32+8,32=16,64 у>Б>=28 y>Б>=16,64
y>Д> + l>4Д>=8,32+17=25,32 y>4>=9
y>Д> + l>ВД>=17+12,32=29,32 y>В>=13
y>Б> + l>ВБ>=16,64+15,32=31 y>В>=13
y>Б> + l>1Б>=16,64+8=24,64 y>1>=8,32
Теперь проверим условие l>ij> y>i> - y>j> для всех дуг сети.
l>4A> = у>4> - у>А> 9=9-0
l>4Д> у>4> – у>Д> 8,329-17
l>Д4> = у>Д> – у>4 > 8=17-9
l>ДВ> у>Д> – у>В> 1217-13
l>BA >= y>B> - y>A> 13=13-0
l>BД > y>B> – y>Д> 12,3213-17
l>BБ > y>B> – y>Б> 15,3213-16,64
l>B4 > y>B> – y>4> 713-9
l>B1 > y>B> – y>1> 1013-8,32
l>БВ> у>Б> - у>В > 1516,64-13
l>Б1> = у>Б> – у>1 > 8,32=16,64-8,32
l>1А> = у>1> – у>А > 8,32=8,32-0
l>1В> у>1> – у>В > 98,32-13
l>1Б> у>1> – у>Б > 88,32-16,64
Чтобы найти кратчайшие пути, найдем дуги для которых выполняется условие:
l>ij> = y>i> - y>j>
Таковыми являются:
l>4A> = у>4> - у>А> 9=9-0
l>Д4> = у>Д> – у>4 > 8=17-9
l>BA >= y>B> - y>A> 13=13-0
l>Б1> = у>Б> – у>1 > 8,32=16,64-8,32
l>1А> = у>1> – у>А > 8,32=8,32-0
Кратчайшие расстояния до пункта А равны:
|
пункт |
4 |
Д |
Б |
1 |
В |
|
расстояние до А |
9 |
17 |
16,64 |
8,32 |
13 |
Аналогичным образом находятся кратчайшие расстояния до других пунктов.
Построить матрицу кратчайших расстояний между пунктами А, Б, В, Г, Д.
|
А |
Б |
В |
Г |
Д |
|
|
А |
--- |
16 |
13,32 |
--- |
17,64 |
|
Б |
16,64 |
--- |
15 |
21 |
--- |
|
В |
13 |
15,32 |
--- |
15 |
12,32 |
|
Г |
--- |
21,64 |
15,32 |
--- |
16 |
|
Д |
17 |
--- |
12 |
16,32 |
--- |
Математическая модель задачи коммивояжера:
Найти минимальное значение целевой функции z
n+1 n+1
min z = l>ij> * x>ij>
i=1 j=1
при следующих ограничениях:
из каждого города i нужно уехать только один раз
n+1
x>ij> = 1 i=1, ......, n+1
j=1
в каждый город j нужно приехать только один раз:
n+1
x>ij> = 1 j=1, ......, n+1
i=1
переменные x>ij> могуть принимать одно из двух значений: 0 или 1,
1 - если в искомый маршрут входит переезд из пункта i в пункт j
0 - в противном случае
решение есть простой цикл
Решение задачи:
|
А |
Б |
В |
Г |
Д |
|
|
А |
--- |
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т аб АБЗ, располож-м в пункте, руб, Cp>i> + E*Kp>i >>уд> |
||||
|
т/час |
тыс. т/год |
1 |
2 |
3 |
4 |
|
10 |
18 |
484 |
489 |
495 |
481 |
|
25 |
45 |
423 |
428 |
435 |
420 |
|
50 |
90 |
405 |
410 |
416 |
401 |
Затраты на транспортировку 1т аб потребителям, С>ij>, руб
|
Пункт размещения |
Зона-потребитель |
|||
|
1 |
28,3 |
60,3 |
45,3 |
90,3 |
|
2 |
61,3 |
30,3 |
93,3 |
48,3 |
|
3 |
50,3 |
95,3 |
33,3 |
62,3 |
|
4 |
99,3 |
54,3 |
65,3 |
36,3 |
Математическая модель транспортной задачи:
m n
min z = C>ij> * x>ij>
i=1 j=1
Ограничения:
n
x>ij> = a>i> i=1, ......, m
j=1
весь продукт a>i> имеющийся у i-го поставщика должен быть вывезен потребителю.
m
x>ij> = b>j> j=1, ......, n
i=1
спрос j-го потребителя должен быть полностью удовлетворен
x>ij> 0 i=1, ...., m; j=1, ...., n
x>ij> – объем перевозок от i-го поставщика j-му потребителю
Транспортная таблица:
|
Мощность АБЗ |
Спрос зон-потребителей, тыс.т/год |
||||||
|
тыс.т/год |
B>1>=50 |
B>2>=60 |
B>3>=45 |
B>4>=70 |
B>ф>=135 |
U>i> |
K>i> |
|
433,3 |
440,3 465,3 |
449,3 450,3 |
437,3 495,3 |
0 |
|||
|
X>1>=90 |
50 |
40 |
0 |
5/9 |
|||
|
433,3 471,3 |
440,3 |
449,3 503,3 |
437,3 458,3 |
0 |
|||
|
X>2>=90 |
60 |
30 |
0 |
6/9 |
|||
|
433,3 466,3 |
440,3 511,3 |
449,3 |
437,3 478,3 |
0 |
|||
|
X>3>=90 |
45 |
45 |
0 |
½ |
|||
|
433,3 500,3 |
440,3 455,3 |
449,3 466,3 |
437,3 |
0 |
|||
|
X>4>=90 |
70 |
20 |
0 |
7/9 |
|||
|
V>j> |
433,3 |
440,3 |
449,3 |
437,3 |
0 |
Так как задача не сбалансирована, то определяем спрос фиктивного потребителя:
В>ф>= а>i> - b>j> = 360 – 225 = 135 тыс.т/год
В верхний правый угол клеток вносится суммарная величина приведенных затрат на приготовление и транспортировку 1т аб, Сp>i> + E*Kp>i> + C>ij>
С помощью правила минимального элемента вносим в таблицу перевозки x>ij>.
Проверяем план на вырожденность:
m + n - 1 = 8 = 8 (занятых клеток), следовательно план является невырожденным.
Строим систему потенциалов поставщиков и потребителей. Для этого потенциал столбца или строки с наибольшим кол-вом занятых клеток приравниваем нулю, в данном случае это потенциал столбца B>ф>, остальные потенциалы определяем исходя из условия оптимальности для занятых клеток (U>i> + V>j> = Сp>i> + E*Kp>i> + C>ij>).
Проверяем план на оптимальность:
число занятых клеток не должно превышать величину m + n – 1
для каждой занятой клетки сумма потенциалов должна равняться суммарной величине затрат на приготовление и транспортировку 1т аб.
для каждой свободной клетки должно выполняться неравенство :
U>i> + V>j> Сp>i> + E*Kp>i> + C>ij>
Все три условия выполняются, следовательно план является оптимальным с точки зрения транспортной задачи.
Определяем значения коэффициентов интенсивности.
K>i> = x>ij> / x>i>
x>ij> – cуммарный объем поставок i-го АБЗ реальным потребителям
x>i> – мощность i-го АБЗ
Так как ни один K>i> не равен нулю или единице, то рассматриваемый вариант размещения АБЗ соответствующей мощности не есть наилучший, поэтому необходимо его улучшить.
Отыскиваем смешанную строку с минимальной величиной K>i> и в этой строке мощность АБЗ уменьшаем до следующей возможной величины, в нашем случае это третья строка.
Строим новую транспортную таблицу не забывая, что суммарная мощность АБЗ должна равняться суммарному спросу потребителей. Также необходимо пересчитать величину Сp>i> + E*Kp>i> + C>ij> для клеток третьей строки.
|
Мощность АБЗ |
Спрос зон-потребителей, тыс.т/год |
||||||
|
тыс.т/год |
B>1>=50 |
B>2>=60 |
B>3>=45 |
B>4>=70 |
B>ф>=90 |
U>i> |
K>i> |
|
433,3 |
424,3 465,3 |
450,3 |
421,3 495,3 |
-16 0 |
|||
|
X>1>=90 |
50 |
40 |
-16 |
1 |
|||
|
449,3 471,3 |
440,3 |
466,3 503,3 |
437,3 458,3 |
0 |
|||
|
X>2>=90 |
60 |
30 |
0 |
6/9 |
|||
|
449,3 485,3 |
440,3 530,3 |
466,3 468,3 |
437,3 497,3 |
0 |
|||
|
X>3>=45 |
45 |
0 |
0 |
||||
|
449,3 500,3 |
440,3 455,3 |
466,3 |
437,3 |
0 |
|||
|
X>4>=90 |
5 |
70 |
15 |
0 |
15/18 |
||
|
V>j> |
449,3 |
440,3 |
466,3 |
437,3 |
0 |
Новый вариант также не является наилучшим, поэтому уменьшаем мощность АБЗ во втором пункте.
|
Мощность АБЗ |
Спрос зон-потребителей, тыс.т/год |
||||||
|
тыс.т/год |
B>1>=50 |
B>2>=60 |
B>3>=45 |
B>4>=70 |
B>ф>=45 |
U>i> |
K>i> |
|
433,3 |
439,3 465,3 |
450,3 |
421,3 495,3 |
-18 0 |
|||
|
X>1>=90 |
50 |
40 |
-16 |
||||
|
452,3 489,3 |
458,3 |
469,3 521,3 |
440,3 476,3 |
1 0 |
|||
|
|
45 _ |
+ |
3 |
||||
|
451,3 485,3 |
457,3 530,3 |
468,3 |
439,3 497,3 |
0 |
|||
|
|
0 + |
_ 45 |
2 |
||||
|
449,3 500,3 |
455,3 |
466,3 |
437,3 |
-2 0 |
|||
|
|
15 + |
5 _ |
70 |
0 |
|||
|
V>j> |
449,3 |
455,3 |
466,3 |
437,3 |
-2 |
X>2>=45
X>4>=90Для одной свободной клетки не выполняется условие U>i> + V>j> Сp>i> + E*Kp>i> + C>ij> поэтому план необходимо улучшить.
Строим цикл для этой клетки. Вершине свободной клетки присваиваем знак “-”, для остальных вершин этот знак чередуется. Перевозка х>п> = 5. Перемещаем эту перевозку по циклу, прибавляя ее в клетках со знаком “+” и отнимая в клетках со знаком “-”. После строим новую транспортную таблицу с учетом изменений.
|
Мощность АБЗ |
Спрос зон-потребителей, тыс.т/год |
||||||
|
тыс.т/год |
B>1>=50 |
B>2>=60 |
B>3>=45 |
B>4>=70 |
B>ф>=45 |
U>i> |
K>i> |
|
433,3 |
440,3 465,3 |
450,3 |
422,3 495,3 |
-18 0 |
|||
|
X>1>=90 |
50 |
40 |
-18 |
1 |
|||
|
451,3 489,3 |
458,3 |
468,3 521,3 |
440,3 476,3 |
0 |
|||
|
X>2>=45 |
40 |
5 |
0 |
8/9 |
|||
|
451,3 485,3 |
458,3 530,3 |
468,3 |
440,3 497,3 |
0 |
|||
|
X>3>=45 |
5 |
40 |
0 |
1/9 |
|||
|
448,3 500,3 |
455,3 |
465,3 466,3 |
437,3 |
-3 0 |
|||
|
X>4>=90 |
20 |
70 |
-3 |
1 |
|||
|
V>j> |
451,3 |
458,3 |
468,3 |
440,3 |
0 |
План является оптимальным, теперь подсчитываем коэффициенты интенсивности. Так как не все коэффициенты равны нулю или единице, то уменьшаем мощность завода в 3-м пункте.
|
Мощность АБЗ |
Спрос зон-потребителей, тыс.т/год |
||||||
|
тыс.т/год |
B>1>=50 |
B>2>=60 |
B>3>=45 |
B>4>=70 |
B>ф>=18 |
U>i> |
K>i> |
|
433,3 |
439,3 465,3 |
450,3 |
421,3 495,3 |
-78 0 |
|||
|
X>1>=90 |
50 |
40 |
-16 |
1 |
|||
|
452,3 489,3 |
458,3 |
469,3 521,3 |
440,3 476,3 |
-59 0 |
|||
|
X>2>=45 |
45 |
3 |
1 |
||||
|
511,3 545,3 |
517,3 590,3 |
528,3 |
499,3 557,3 |
0 |
|||
|
X>3>=18 |
0 |
18 |
62 |
0 |
|||
|
449,3 500,3 |
455,3 |
466,3 |
437,3 |
-62 0 |
|||
|
X>4>=90 |
15 |
5 |
70 |
0 |
1 |
||
|
V>j> |
449,3 |
455,3 |
466,3 |
437,3 |
-62 |
План является оптимальным, подсчитываем значения коэффициентов интенсивности. Так как все коэффициенты равны либо 1, либо 0, то данный план является наилучшим.
Рассчитать значение целевой функции для каждого из промежуточных вариантов и построить таблицу.
|
Вариант размещения |
Мощность АБЗ, расположенного в пункте, тыс.т/год |
Значение целевой функции, z>i>, тыс.руб. |
|||
|
М>1> |
М>2> |
М>3> |
М>4> |
||
|
1 |
50 |
60 |
45 |
70 |
98912,5 |
|
2 |
90 |
60 |
0 |
75 |
99037,5 |
|
3 |
90 |
40 |
5 |
90 |
100067,5 |
|
4 -наилучший |
90 |
45 |
0 |
90 |
100072,5 |