Математическое моделирование экономических систем - (реферат)

Дата добавления: март 2006г.

    Математическое моделирование экономических систем
    Раздел 1. Выбор оптимального маршрута поездки.
    Постановка задачи:

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

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

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

    А 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

Аналогичным образом находятся кратчайшие расстояния до других пунктов.

Построить матрицу кратчайших расстояний между пунктами А, Б, В, Г, Д.

    А
    Б
    В
    Г
    Д
    А
    --
    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 = S S lij * xij
    i=1 j=1
    при следующих ограничениях:
    из каждого города i нужно уехать только один раз
    n+1
    S xij = 1 i=1, ........., n+1
    j=1
    в каждый город j нужно приехать только один раз:
    n+1
    S xij = 1 j=1, ........., n+1
    i=1

переменные 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
    Математическая модель транспортной задачи:
    m n
    min z = S S Cij * xij
    i=1 j=1
    Ограничения:
    n
    S xij = ai i=1, ........., m
    j=1

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

    m
    S 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 < 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
    B3=45
    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