МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

МАДИ (ТУ)

КУРСОВАЯ РАБОТА ПО ДИСЦИПЛИНЕ: МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ СИСТЕМ

Выполнил: Белоногов М.В.

Группа 4ВЭДС₃

Проверил: Беляков Г.С.

Москва 1999-2000

Раздел 1.

Выбор оптимального маршрута поездки.

Постановка задачи:

Машина с инкассатором ежедневно забирает выручку 4-х торговых точек (пункты Б, В, Г, Д), расположенных на разных улицах города и отвозит ее в банк (пункт А). Определено время на проезд по различным улицам с учетом интенсивности движения по ним транспортного потока. Требуется найти маршрут движения инкассаторской машины, который начинался и заканчивался бы в пункте А, позволял посетить каждую торговую точку и проехать по соответствующей улице только один раз и характеризовался минимальными затратами времени на поездку. Маршрут должен включать переезд из пункта Б в пункт Г.

Порядок решения задачи:

1. Определить кратчайшие расстояния между различными парами пунктов используя алгоритм поиска кратчайших путей на циклической сети.

А 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₄=  y₄=9

y_A + l_BA=0+13=13  y_B=  y_B=13

y_A + l_1A=0+8,32=8,32  y₁=  y₁=8,32

Теперь рассматриваем пункт i для которого y_i перестала быть равной бесконечности и дуги, которые в него входят.

y₄ + l_B4=9+7=16  y_B=13

y₄ + 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  у₁=8,32

y₁ + l_В1=8,32+10=18,32  y_В=13

y₁ + l_Б1=8,32+8,32=16,64  у_Б=28  y_Б=16,64

y_Д + l_4Д=8,32+17=25,32  y₄=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₁=8,32

Теперь проверим условие l_ij  y_i - y_j для всех дуг сети.

l_4A = у₄ - у_А 9=9-0

l_4Д  у₄ – у_Д 8,329-17

l_Д4 = у_Д – у₄ 8=17-9

l_ДВ  у_Д – у_В 1217-13

l_BA = y_B - y_A 13=13-0

l_BД  y_B – y_Д 12,3213-17

l_BБ  y_B – y_Б 15,3213-16,64

l_B4  y_B – y₄ 713-9

l_B1  y_B – y₁ 1013-8,32

l_БВ  у_Б - у_В 1516,64-13

l_Б1 = у_Б – у₁ 8,32=16,64-8,32

l_1А = у₁ – у_А 8,32=8,32-0

l_1В  у₁ – у_В 98,32-13

l_1Б  у₁ – у_Б 88,32-16,64

Чтобы найти кратчайшие пути, найдем дуги для которых выполняется условие:

l_ij = y_i - y_j

Таковыми являются:

l_4A = у₄ - у_А 9=9-0

l_Д4 = у_Д – у₄ 8=17-9

l_BA = y_B - y_A 13=13-0

l_Б1 = у_Б – у₁ 8,32=16,64-8,32

l_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 =   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 - в противном случае

• решение есть простой цикл

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т аб АБЗ, располож-м в пункте, руб, C^p_i + E*K^p_{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₁=50

B₂=60

B₃=45

B₄=70

B_ф=135

U_i

K_i

433,3

440,3  465,3

449,3  450,3

437,3  495,3

0

X₁=90

50

40

0

5/9

433,3  471,3

440,3

449,3  503,3

437,3  458,3

0

X₂=90

60

30

0

6/9

433,3  466,3

440,3  511,3

449,3

437,3  478,3

0

X₃=90

45

45

0

½

433,3  500,3

440,3  455,3

449,3  466,3

437,3

0

X₄=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*K^p_i + C_ij

С помощью правила минимального элемента вносим в таблицу перевозки x_ij.

Проверяем план на вырожденность:

m + n - 1 = 8 = 8 (занятых клеток), следовательно план является невырожденным.

Строим систему потенциалов поставщиков и потребителей. Для этого потенциал столбца или строки с наибольшим кол-вом занятых клеток приравниваем нулю, в данном случае это потенциал столбца B_ф, остальные потенциалы определяем исходя из условия оптимальности для занятых клеток (U_i + V_j = С^p_i + E*K^p_i + C_ij).

Проверяем план на оптимальность:

• число занятых клеток не должно превышать величину m + n – 1

• для каждой занятой клетки сумма потенциалов должна равняться суммарной величине затрат на приготовление и транспортировку 1т аб.

• для каждой свободной клетки должно выполняться неравенство :

U_i + V_j  С^p_i + E*K^p_i + C_ij

Все три условия выполняются, следовательно план является оптимальным с точки зрения транспортной задачи.

Определяем значения коэффициентов интенсивности.

K_i =  x_ij / x_i

 x_ij – cуммарный объем поставок i-го АБЗ реальным потребителям

x_i – мощность i-го АБЗ

Так как ни один K_i не равен нулю или единице, то рассматриваемый вариант размещения АБЗ соответствующей мощности не есть наилучший, поэтому необходимо его улучшить.

Отыскиваем смешанную строку с минимальной величиной K_i и в этой строке мощность АБЗ уменьшаем до следующей возможной величины, в нашем случае это третья строка.

Строим новую транспортную таблицу не забывая, что суммарная мощность АБЗ должна равняться суммарному спросу потребителей. Также необходимо пересчитать величину С^p_i + E*K^p_i + C_ij для клеток третьей строки.

Мощность АБЗ

Спрос зон-потребителей, тыс.т/год

тыс.т/год

B₁=50

B₂=60

B₃=45

B₄=70

B_ф=90

U_i

K_i

433,3

424,3  465,3

450,3

421,3  495,3

-16 0

X₁=90

50

40

-16

1

449,3  471,3

440,3

466,3  503,3

437,3  458,3

0

X₂=90

60

30

0

6/9

449,3  485,3

440,3  530,3

466,3  468,3

437,3  497,3

0

X₃=45

45

0

0

449,3  500,3

440,3  455,3

466,3

437,3

0

X₄=90

5

70

15

0

15/18

V_j

449,3

440,3

466,3

437,3

0

Новый вариант также не является наилучшим, поэтому уменьшаем мощность АБЗ во втором пункте.

Мощность АБЗ

Спрос зон-потребителей, тыс.т/год

тыс.т/год

B₁=50

B₂=60

B₃=45

B₄=70

B_ф=45

U_i

K_i

433,3

439,3  465,3

450,3

421,3  495,3

-18 0

X₁=90

50

40

-16

452,3  489,3

458,3

469,3 521,3

440,3  476,3

1  0

X₂=45

45 _

+

3

451,3  485,3

457,3  530,3

468,3

439,3  497,3

0

X₃=45

0 +

_ 45

2

449,3  500,3

455,3

466,3

437,3

-2  0

X₄=90

15 +

5 _

70

0

V_j

449,3

455,3

466,3

437,3

-2

Для одной свободной клетки не выполняется условие U_i + V_j  С^p_i + E*K^p_i + C_ij поэтому план необходимо улучшить.

Строим цикл для этой клетки. Вершине свободной клетки присваиваем знак “-”, для остальных вершин этот знак чередуется. Перевозка х_п = 5. Перемещаем эту перевозку по циклу, прибавляя ее в клетках со знаком “+” и отнимая в клетках со знаком “-”. После строим новую транспортную таблицу с учетом изменений.

Мощность АБЗ

Спрос зон-потребителей, тыс.т/год

тыс.т/год

B₁=50

B₂=60

B₃=45

B₄=70

B_ф=45

U_i

K_i

433,3

440,3  465,3

450,3

422,3  495,3

-18  0

X₁=90

50

40

-18

1

451,3  489,3

458,3

468,3  521,3

440,3  476,3

0

X₂=45

40

5

0

8/9

451,3  485,3

458,3  530,3

468,3

440,3  497,3

0

X₃=45

5

40

0

1/9

448,3  500,3

455,3

465,3  466,3

437,3

-3  0

X₄=90

20

70

-3

1

V_j

451,3

458,3

468,3

440,3

0

План является оптимальным, теперь подсчитываем коэффициенты интенсивности. Так как не все коэффициенты равны нулю или единице, то уменьшаем мощность завода в 3-м пункте.

Мощность АБЗ

Спрос зон-потребителей, тыс.т/год

тыс.т/год

B₁=50

B₂=60

B₃=45

B₄=70

B_ф=18

U_i

K_i

433,3

439,3  465,3

450,3

421,3  495,3

-78  0

X₁=90

50

40

-16

1

452,3  489,3

458,3

469,3  521,3

440,3  476,3

-59  0

X₂=45

45

3

1

511,3  545,3

517,3  590,3

528,3

499,3  557,3

0

X₃=18

0

18

62

0

449,3  500,3

455,3

466,3

437,3

-62  0

X₄=90

15

5

70

0

1

V_j

449,3

455,3

466,3

437,3

-62

План является оптимальным, подсчитываем значения коэффициентов интенсивности. Так как все коэффициенты равны либо 1, либо 0, то данный план является наилучшим.

Рассчитать значение целевой функции для каждого из промежуточных вариантов и построить таблицу.

Вариант размещения

Мощность АБЗ, расположенного в пункте, тыс.т/год

Значение целевой функции, z_i, тыс.руб.

М₁

М₂

М₃

М₄

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