Определение рационального варианта размещения производственно-хозяйственных предприятий (на примере АБЗ) и выбор оптимального маршрута поездки коммивояжера
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
МАДИ (ТУ)
КУРСОВАЯ РАБОТА ПО
ДИСЦИПЛИНЕ: МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ СИСТЕМ
Выполнил: Белоногов М.В.
Группа 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 =
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
|
Затраты на
транспортировку 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 = S S Cij * xij
i=1 j=1
Ограничения:
n
n S xij = ai i=1,
......, m
j=1
весь продукт ai имеющийся у i-го
поставщика должен быть вывезен потребителю.
m
n S xij = bj j=1,
......, n
i=1
спрос j-го потребителя должен быть полностью удовлетворен
n xij ³ 0 i=1, ...., m; j=1, ...., n
xij – объем перевозок от i-го поставщика j-му
потребителю
Транспортная
таблица:
|
Мощность АБЗ
|
Спрос зон-потребителей,
тыс.т/год
|
|
тыс.т/год
|
B1=50
|
B2=60
|
B3=45
|
B4=70
|
Bф=135
|
Ui
|
Ki
|
|
433,3
|
440,3 < 465,3
|
449,3 < 450,3
|
437,3 < 495,3
|
0
|
|
|
|
X1=90
|
50
|
|
|
|
40
|
0
|
5/9
|
|
433,3 < 471,3
|
440,3
|
449,3 < 503,3
|
437,3 < 458,3
|
0
|
|
|
|
X2=90
|
|
60
|
|
|
30
|
0
|
6/9
|
|
433,3 < 466,3
|
440,3 < 511,3
|
449,3
|
437,3 < 478,3
|
0
|
|
|
|
X3=90
|
|
|
45
|
|
45
|
0
|
½
|
|
433,3 < 500,3
|
440,3 < 455,3
|
449,3 < 466,3
|
437,3
|
0
|
|
|
|
X4=90
|
|
|
|
70
|
20
|
0
|
7/9
|
|
Vj
|
433,3
|
440,3
|
449,3
|
437,3
|
0
|
|
|
Так
как задача не сбалансирована, то определяем спрос фиктивного потребителя:
Вф=S аi
- S bj = 360 – 225 = 135 тыс.т/год
В
верхний правый угол клеток вносится суммарная величина приведенных затрат на
приготовление и транспортировку 1т аб, Сpi
+ E*Kpi + Cij
С
помощью правила минимального элемента вносим в таблицу перевозки xij.
Проверяем
план на вырожденность:
m + n - 1 = 8 = 8 (занятых клеток), следовательно план является невырожденным.
Строим
систему потенциалов поставщиков и потребителей. Для этого потенциал столбца или
строки с наибольшим кол-вом занятых клеток приравниваем нулю, в данном случае
это потенциал столбца Bф,
остальные потенциалы определяем исходя из условия оптимальности для занятых
клеток (Ui + Vj
= Сpi + E*Kpi
+ Cij).
Проверяем
план на оптимальность:
·
число занятых клеток не должно
превышать величину m + n – 1
·
для каждой занятой клетки сумма
потенциалов должна равняться суммарной величине затрат на приготовление и
транспортировку 1т аб.
·
для каждой свободной клетки должно
выполняться неравенство :
Ui + Vj < Сpi
+ E*Kpi + Cij
Все три условия выполняются, следовательно план
является оптимальным с точки зрения транспортной задачи.
Определяем значения коэффициентов интенсивности.
Ki = S xij / xi
S xij – cуммарный объем
поставок i-го АБЗ реальным потребителям
xi – мощность
i-го АБЗ
Так
как ни один Ki не равен нулю или единице, то рассматриваемый вариант
размещения АБЗ соответствующей мощности не есть наилучший, поэтому необходимо
его улучшить.
Отыскиваем
смешанную строку с минимальной величиной Ki и
в этой строке мощность АБЗ уменьшаем до следующей возможной величины, в нашем
случае это третья строка.
Строим
новую транспортную таблицу не забывая, что суммарная мощность АБЗ должна
равняться суммарному спросу потребителей. Также необходимо пересчитать величину
Сpi + E*Kpi
+ Cij для клеток
третьей строки.
|
Мощность АБЗ
|
Спрос зон-потребителей,
тыс.т/год
|
|
тыс.т/год
|
B1=50
|
B2=60
|
B4=70
|
Bф=90
|
Ui
|
Ki
|
|
433,3
|
424,3 < 465,3
|
450,3
|
421,3 < 495,3
|
-16< 0
|
|
|
|
X1=90
|
50
|
|
40
|
|
|
-16
|
1
|
|
449,3 < 471,3
|
440,3
|
466,3 < 503,3
|
437,3 < 458,3
|
0
|
|
|
|
X2=90
|
|
60
|
|
|
30
|
0
|
6/9
|
|
449,3 < 485,3
|
440,3 < 530,3
|
466,3 < 468,3
|
437,3 < 497,3
|
0
|
|
|
|
X3=45
|
|
|
|
|
45
|
0
|
0
|
|
449,3 < 500,3
|
440,3 < 455,3
|
466,3
|
437,3
|
0
|
|
|
|
X4=90
|
|
|
5
|
70
|
15
|
0
|
15/18
|
|
Vj
|
449,3
|
440,3
|
466,3
|
437,3
|
0
|
|
|
Новый
вариант также не является наилучшим, поэтому уменьшаем мощность АБЗ во втором
пункте.
|
Мощность АБЗ
|
Спрос зон-потребителей,
тыс.т/год
|
|
тыс.т/год
|
B1=50
|
B2=60
|
B3=45
|
B4=70
|
Bф=45
|
Ui
|
Ki
|
|
433,3
|
439,3 < 465,3
|
450,3
|
421,3 < 495,3
|
-18< 0
|
|
|
|
X1=90
|
50
|
|
40
|
|
|
-16
|
|
|
452,3 < 489,3
|
458,3
|
469,3< 521,3
|
440,3 < 476,3
|
1 > 0
|
|
|
|
   X2=45
|
|
45 _
|
|
|
+
|
3
|
|
|
451,3 < 485,3
|
457,3 < 530,3
|
468,3
|
439,3 < 497,3
|
0
|
|
|
|
  X3=45
|
|
|
0 +
|
|
_ 45
|
2
|
|
|
449,3 < 500,3
|
455,3
|
466,3
|
437,3
|
-2 < 0
|
|
|
|
 X4=90
|
|
15 +
|
5 _
|
70
|
|
0
|
|
|
Vj
|
449,3
|
455,3
|
466,3
|
437,3
|
-2
|
|
|
Для
одной свободной клетки не выполняется
условие Ui + Vj < Сpi
+ E*Kpi + Cij поэтому план необходимо улучшить.
Строим цикл для этой клетки. Вершине свободной клетки
присваиваем знак “-”, для остальных вершин этот знак чередуется. Перевозка хп = 5. Перемещаем эту перевозку по циклу, прибавляя ее в клетках со
знаком “+” и отнимая в клетках со знаком “-”. После строим новую транспортную
таблицу с учетом изменений.
|
Мощность АБЗ
|
Спрос зон-потребителей,
тыс.т/год
|
|
тыс.т/год
|
B1=50
|
B2=60
|
B3=45
|
B4=70
|
Bф=45
|
Ui
|
Ki
|
|
433,3
|
440,3 < 465,3
|
450,3
|
422,3 < 495,3
|
-18 < 0
|
|
|
|
X1=90
|
50
|
|
40
|
|
|
-18
|
1
|
|
451,3 < 489,3
|
458,3
|
468,3 < 521,3
|
440,3 < 476,3
|
0
|
|
|
|
X2=45
|
|
40
|
|
|
5
|
0
|
8/9
|
|
451,3 < 485,3
|
458,3 < 530,3
|
468,3
|
440,3 < 497,3
|
0
|
|
|
|
X3=45
|
|
|
5
|
|
40
|
0
|
1/9
|
|
448,3 < 500,3
|
455,3
|
465,3 < 466,3
|
437,3
|
-3 < 0
|
|
|
|
X4=90
|
|
20
|
|
70
|
|
-3
|
1
|
|
Vj
|
451,3
|
458,3
|
468,3
|
440,3
|
0
|
|
|
План является оптимальным, теперь подсчитываем
коэффициенты интенсивности. Так как не все коэффициенты равны нулю или единице,
то уменьшаем мощность завода в 3-м пункте.
|
Мощность АБЗ
|
Спрос зон-потребителей,
тыс.т/год
|
|
тыс.т/год
|
B1=50
|
B2=60
|
B3=45
|
B4=70
|
Bф=18
|
Ui
|
Ki
|
|
433,3
|
439,3 < 465,3
|
450,3
|
421,3 < 495,3
|
-78 < 0
|
|
|
|
X1=90
|
50
|
|
40
|
|
|
-16
|
1
|
|
452,3 < 489,3
|
458,3
|
469,3 < 521,3
|
440,3 < 476,3
|
-59 < 0
|
|
|
|
X2=45
|
|
45
|
|
|
|
3
|
1
|
|
511,3 < 545,3
|
517,3 < 590,3
|
528,3
|
499,3 < 557,3
|
0
|
|
|
|
X3=18
|
|
|
0
|
|
18
|
62
|
0
|
|
449,3 < 500,3
|
455,3
|
466,3
|
437,3
|
-62 < 0
|
|
|
|
X4=90
|
|
15
|
5
|
70
|
|
0
|
1
|
|
Vj
|
449,3
|
455,3
|
466,3
|
437,3
|
-62
|
|
|
План
является оптимальным, подсчитываем значения коэффициентов интенсивности. Так
как все коэффициенты равны либо 1, либо 0, то данный план является наилучшим.
Рассчитать
значение целевой функции для каждого из промежуточных вариантов и построить
таблицу.
|
Вариант размещения
|
Мощность АБЗ,
расположенного в пункте, тыс.т/год
|
Значение целевой функции,
zi, тыс.руб.
|
|
М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
|