Математика

Определение рационального варианта размещения производственно-хозяйственных предприятий (на примере АБЗ) и выбор оптимального маршрута поездки коммивояжера


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



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



                                                    Выполнил: Белоногов М.В.
                                                               Группа 4ВЭДС3
                                                      Проверил: Беляков Г.С.



                              Москва 1999-2000
                                  Раздел 1.
                    Выбор оптимального маршрута поездки.


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

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

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

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



         А                       1                      Б



         4                       В                      2



         Д                       3                      Г


Найдем кратчайшие расстояния до пункта  А.

|пункт |А      |Б      |В      |Д      |1       |4       |
|i     |       |       |       |       |        |        |
|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.  (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 = (  ( Cij * xij
                 i=1   j=1

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

       n
 . ( xij = ai        i=1, ......, m
   j=1

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

         m
 . ( xij = bj        j=1, ......, n
   i=1

   спрос j-го потребителя должен быть полностью удовлетворен

 . 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 ( |449,3 ( |437,3 ( |0       |     |     |
|        |        |465,3   |450,3   |495,3   |        |     |     |
|X1=90   |50      |        |        |        |40      |0    |5/9  |
|        |433,3 ( |440,3   |449,3 ( |437,3 ( |0       |     |     |
|        |471,3   |        |503,3   |458,3   |        |     |     |
|X2=90   |        |60      |        |        |30      |0    |6/9  |
|        |433,3 ( |440,3 ( |449,3   |437,3 ( |0       |     |     |
|        |466,3   |511,3   |        |478,3   |        |     |     |
|X3=90   |        |        |45      |        |45      |0    |Ѕ    |
|        |433,3 ( |440,3 ( |449,3 ( |437,3   |0       |     |     |
|        |500,3   |455,3   |466,3   |        |        |     |     |
|X4=90   |        |        |        |70      |20      |0    |7/9  |
|Vj      |433,3   |440,3   |449,3   |437,3   |0       |     |     |


Так  как  задача  не  сбалансирована,   то   определяем   спрос   фиктивного
потребителя:
Вф=( аi  - ( 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 = ( xij / xi

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

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

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

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

|Мощность|Спрос зон-потребителей, тыс.т/год                             |
|АБЗ     |                                                              |
|тыс.т/го|B1=50   |B2=60   |B3=45   |B4=70   |Bф=90   |Ui   |Ki   |
|д       |        |        |        |        |        |     |     |
|        |433,3   |424,3 ( |450,3   |421,3 ( |-16(  0 |     |     |
|        |        |465,3   |        |495,3   |        |     |     |
|X1=90   |50      |        |40      |        |        |-16  |1    |
|        |449,3 ( |440,3   |466,3 ( |437,3 ( |0       |     |     |
|        |471,3   |        |503,3   |458,3   |        |     |     |
|X2=90   |        |60      |        |        |30      |0    |6/9  |
|        |449,3 ( |440,3 ( |466,3 ( |437,3 ( |0       |     |     |
|        |485,3   |530,3   |468,3   |497,3   |        |     |     |
|X3=45   |        |        |        |        |45      |0    |0    |
|        |449,3 ( |440,3 ( | 466,3  |437,3   |0       |     |     |
|        |500,3   |455,3   |        |        |        |     |     |
|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   |        |450,3   |421,3 ( |-18(  0 |     |     |
|        |        |439,3 ( |        |495,3   |        |     |     |
|        |        |465,3   |        |        |        |     |     |
|X1=90   |50      |        |40      |        |        |-16  |     |
|        |452,3 ( | 458,3  | 469,3( |440,3 ( |1 ( 0   |     |     |
|        |489,3   |        |521,3   |476,3   |        |     |     |
|X2=45   |        |   45  _|        |        |   +    |3    |     |
|        |451,3 ( | 457,3 (|  468,3 |439,3 ( |0       |     |     |
|        |485,3   |530,3   |        |497,3   |        |     |     |
|X3=45   |        |        |      0 |        |   _    |2    |     |
|        |        |        |+       |        |45      |     |     |
|        |449,3 ( |  455,3 | 466,3  |437,3   | -2 ( 0 |     |     |
|        |500,3   |        |        |        |        |     |     |
|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   |        |450,3   |422,3 ( |-18 (  0|     |     |
|        |        |440,3 ( |        |495,3   |        |     |     |
|        |        |465,3   |        |        |        |     |     |
|X1=90   |50      |        |40      |        |        |-18  |1    |
|        | 451,3 (| 458,3  |  468,3 |440,3 ( |  0     |     |     |
|        |489,3   |        |( 521,3 |476,3   |        |     |     |
|X2=45   |        |40      |        |        |5       |0    |8/9  |
|        |  451,3 | 458,3 (|  468,3 | 440,3 (|0       |     |     |
|        |( 485,3 |530,3   |        |497,3   |        |     |     |
|X3=45   |        |        |5       |        |40      |0    |1/9  |
|        | 448,3 (|  455,3 |465,3 ( |437,3   |-3 ( 0  |     |     |
|        |500,3   |        |466,3   |        |        |     |     |
|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   |        |450,3   |421,3 ( |-78 ( 0 |     |     |
|        |        |439,3 ( |        |495,3   |        |     |     |
|        |        |465,3   |        |        |        |     |     |
|X1=90   |50      |        |40      |        |        |-16  |1    |
|        | 452,3 (| 458,3  | 469,3 (|440,3 ( |-59 ( 0 |     |     |
|        |489,3   |        |521,3   |476,3   |        |     |     |
|X2=45   |        |45      |        |        |        |3    |1    |
|        |  511,3 | 517,3 (| 528,3  |  499,3 |0       |     |     |
|        |( 545,3 |590,3   |        |( 557,3 |        |     |     |
|X3=18   |        |        |0       |        |18      |62   |0    |
|        | 449,3 (|  455,3 | 466,3  |437,3   | -62 ( 0|     |     |
|        |500,3   |        |        |        |        |     |     |
|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        |
|-наилучший|        |          |          |          |                |





смотреть на рефераты похожие на "Определение рационального варианта размещения производственно-хозяйственных предприятий (на примере АБЗ) и выбор оптимального маршрута поездки коммивояжера"