Математическое моделирование экономических систем
17,64
Б
16,64
---
15
21
---
В
13
15,32
---
15
12,32
Г
---
21,64
15,32
---
16
Д
17
---
12
16,32
---
Математическая модель задачи коммивояжера:
Найти минимальное значение целевой функции z

при следующих ограничениях:
из каждого города i нужно уехать только один раз

в каждый город j нужно приехать только один раз:

переменные xij могуть принимать одно из двух значений: 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т аб АБЗ, располож-м в пункте, руб, 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 |
|
Математическая модель транспортной задачи:

Ограничения:

весь продукт ai имеющийся у i-го поставщика должен быть вывезен потребителю.

спрос j-го потребителя должен быть полностью удовлетворен
xij і 0 i=1, ...., m; j=1, ...., nxij – объем перевозок от 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 |
||||||