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

МІНІСТЕРСТВО ОСВІТИ РОСІЙСЬКОЇ ФЕДЕРАЦИИ.

МАДИ (ТУ).

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

СИСТЕМ.

Виконав: Белоногов М.В.

Група 4ВЭДС3.

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

Москва 1999;2000.

Розділ 1.

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

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

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

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

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

А 1 Б.

4 У 2.

Д 3 Г.

Знайдемо найкоротші відстані до пункту А.

|пункт |А |Б |У |Д |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.

Теперь розглядаємо пункт і котрій 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.

при наступних ограничениях:

. з кожного і потрібно поїхати лише одне раз.

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 — тоді як шуканий маршрут входить переїзд із і до пункту 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 |98 912,5 | |2 |90 |60 |0 |75 |99 037,5 | |3 |90 |40 |5 |90 |100 067,5 | |4 |90 |45 |0 |90 |100 072,5 | |-найкращий| | | | | |.