Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
МІНІСТЕРСТВО АГРАРНОЇ ПОЛІТИКИ ТА ПРОДОВОЛЬСТВА УКРАЇНИ
ВІННИЦЬКИЙ НАЦІОНАЛЬНИЙ АГРАРНИЙ УНІВЕРСИТЕТ
Фінансово-економічний факультет Кафедра Економічної кібернетики
Звіт
з дисципліни
Оптимізаційні методи і моделі
Лабораторна робота №4
Тема:
«Постановка та розв’язок транспортної задачі»
Виконав:
студент групи 31-ФК
Візнюк В.Ю.
Перевірила:
Петровська А. В.
Вінниця 2013
Лабораторна робота №4
Тема: закріплення теоретичного і практичного матеріалу, придбання навичок розв’язання і аналізу транспортних задач в середовищі Microsoft Excel. Мета: сформувати математичну постановку транспортної задачі лінійного програмування, знайти рішення транспортної задачі за допомогою надбудови пакету Microsoft Excel "Поиск решения", проаналізувати обсяги перевезень і тіньові ціни за звітом по стійкості розв’язку задачі.
Хід роботи
Теоретична частина:
Транспортна задача – це розподільна задача, в якій роботи і ресурси вимірюються в одних і тих же одиницях. У таких задачах ресурси можуть бути розподілені між роботами, і окремі роботи можуть бути виконані за допомогою різних комбінацій ресурсів. Прикладом транспортної задачі є розподіл продукції підприємств-виробників між складами підприємств-споживачів.
Стандартна транспортна задача визначається як задача розробки найбільш економічного плану перевезення продукції одного виду з декількох пунктів відправлення в пункти призначення. При цьому величина транспортних витрат прямо пропорційна об'єму продукції, що перевозиться, і задається за допомогою тарифів на перевезення одиниці продукції.
Класична транспортна задача лінійного програмування є збалансованою або закритою, тобто формулюється у формі, коли має місце рівність загального обсягу виробництва аналізованого продукту – загальному обсягу його споживання. В іншому випадку, якщо рівність не має місця, то транспортна задача називається незбалансованою або відкритою. На практиці зустрічаються різні модифікації транспортної задачі.
Найбільш відомі з них використовують додаткову структуру типу графа для побудови структури транспортної мережі, що з'єднує пункти виробництва і споживання. Відповідна транспортна задача може бути сформульована в мережевій постановці стосовно до конкретного графу і тому відноситься до класу задач оптимізації на графах.
Отже, транспортні задачі класифікують наступним чином: 1. Задачі в яких виконується умова балансу (пропозиція дорівнює попиту):
Σаі = Σbj
Називають закритими, замкненими або збалансованими;
2. Якщо запаси менші ніж закази:
Σаі < Σbj
то такі задачі називають задачі відкриті з дефіцитом. Їх можна привести до стандартної збалансованої задачі, за допомогою введення додаткового фіктивного постачальника (складу) з запасом, що рівний дефіциту, та нульовими вартостями перевезень.
3. Якщо запаси перевищують заявки:
Σаі > Σbj
то такі задачі називають незбалансованими з надлишком. Вони приводяться до стандартної збалансованої задачі шляхом введення фіктивного споживача з заявкою, що рівна надлишку, і нульовими вартостями перевезень.
Практична частина
Задача №1
Знайдіть рішення транспортної задачі, вихідні дані якої визначаються таблицею і матрицею.
Матриця пропускних можливостей:
Числа в матриці D визначають граничну кількість вантажу, яку можна перевезти з даного пункту відправлення у відповідний пункт призначення. Символ ∞ означає, що на перевезення з даного пункту відправлення у відповідний пункт призначення немає обмежень. 1. Побудова моделі транспортної задачі
Постановка транспортної задачі полягає у визначенні оптимального плану перевезень деякого однорідного вантажу з m пунктів відправлення А1,
А2,.... Аm у n пунктів призначення B1, B2,..., Вn. При цьому в якості критерію оптимальності звичайно береться або мінімальна вартість перевезень усього вантажу, або мінімальний час його доставки. Розглянула транспортну задачу, як критерій оптимальності якої взята мінімальна вартість перевезень усього вантажу.
Позначила через сij тарифи перевезення одиниці вантажу з i-го пункту відправлення в j-й пункт призначення, через aі – запаси вантажу в i-му пункті відправлення, через bj – потреби у вантажі в j-му пункті призначення, через dij – пропускну спроможність вантажу з i-го пункту відправлення в j-й пункт призначення, а через хij – кількість одиниць вантажу, перевезеного з i-го пункту відправлення в j-й пункт призначення. Тоді математична постановка задачі набуває вигляду:
Оскільки змінні xij задовольняють систему лінійних рівнянь і умову додатності, то забезпечуються доставка необхідної кількості вантажу в кожний з пунктів призначення, при вивозі наявного вантажу із всіх пунктів відправлення, враховуються граничні кількості вантажу, а також виключаються зворотні перевезення. Достатньою і необхідною умовою для вирішення транспортної задачі є рівність сумарних запасів пунктів відправлення і сумарних потреб пунктів призначення. У такому разі така транспортна задача називається закритою.
Отже, ми маємо наступну економіко-математичну модель транспортної задачі:
2. Пошук оптимального плану перевезень.
Ввела в комірки робочого листа вихідну інформацію, розбиту на три таблиці: тарифи, план перевезень і пропускні спроможності . Символ ∞ в таблиці пропускних можливостей зручно замінювати сумарним запасом, тобто сумою запасів пунктів відправлення – 520 одиниць вантажу. В комірках стовпця "Вивезено" використано формули, що обчислюють кількість вантажу, яку вивезено з кожного пункту відправлення. Для цього можна, наприклад, скористатися наступною формулою =СУММ(B8:F8) для комірки G8. Для розрахунку рядка "Доставлено" також обчислюється сума вантажу, але по кожному пункту призначення. Для цільової функції, що мінімізує загальні витрати на перевезення вантажу, використовуємо наступну формулу =СУММПРОИЗВ(B8:F10;B3:F5). Аргументами цієї функції є
масиви тарифів і плану перевезень.
Виділила комірку, у якій обчислюється цільова функція, і вибрала в меню Сервис / Поиск решения. У діалоговому вікні в полі введення "Установить целевую ячейку" вже міститься адреса комірки з цільовою функцією $J$7. Установила перемикач: "Равной минимальному значению". Перейшла до поля введення "Изменяя ячейки:" потрібно занести адрес блоку з планом перевезень – $B$8:$F$10.
Систему обмежень задачі формують наступні умови (рис. 3): обсяги перевезень на кожному маршруті не перевищують пропускних спроможностей – $B$8:$F$10<= $I$3:$M$5, запаси з усіх пунктів відправлення повинні бути вивезені – $G$8:$G$10= $H$8:$H$10, потреби усіх пунктів призначення повинні бути задоволені – $B$11:$F$11= $B$12:$F$12, обсяги перевезень не можуть бути менше нуля – $B$8:$F$10>=0. Для належного формування звіту по стійкості в параметрах потрібно встановити прапорець "Линейная модель".
Задача оптимізації повністю підготовлена. Натискаємо кнопку "Выполнить". Після отримання оптимального плану перевезень потрібно також вивести звіт по стійкості.
Таким чином, оптимальний план перевезення вантажу з трьох пунктів відправлення до п’яти пунктів призначення, при якому мінімізується функція загальних витрат на перевезення (F=1480), має наступний вигляд:
3. Аналіз звіту по стійкості.
У першій таблиці звіту , що має назву "Изменяемые ячейки", у стовпці "Нормированная стоимость" наведені значення, на які збільшиться цільова функція (вартість перевезень) при збільшенні обсягу перевезень на даному маршруті. Таким чином, увагу потрібно звернути на негативні значення цього стовпця, тому що вони показують маршрути, збільшення об'ємів перевезень на яких може привести до зменшення загальної вартості перевезень.
Стовпці "Допустимое увеличение" і "Допустимое уменьшение" мають відношення до тарифів маршрутів перевезень і задають їхні допустимі границі зміни, в межах яких зміна тарифів не приводить до зміни оптимального плану перевезень.
У другій таблиці ("Ограничения") у стовпці "Теневая цена" для пунктів відправлення і призначення наведена величина, на яку зміниться значення цільової функції при зміні запасу пункту відправлення або потреби пункту призначення відповідно на одиницю. Така зміна може бути тільки синхронною – збільшення запасу одного пункту відправлення спричиняє зменшення запасу у іншого. За допомогою значення тіньової ціни можна намітити перерозподіл запасів пунктів відправлення, і, якщо це можливо, знайти нове оптимальне рішення задачі.
Задача №2
Припустимо, що фірма має 4 фабрики і 5 центрів розподілу її товарів. Фабрики фірми розташовуються в містах Дніпропетровськ, Донецьк, Харків і Київ з виробничими можливостями відповідно 200, 150, 225 і 175 одиниць продукції щоденно. Центри розподілу товарів фірми розташовуються у Львові, Києві, Луганську, Сімферополі і Одесі з потребами відповідно в 100, 200, 50, 250 і 150 одиниць продукції щоденно. Вартості перевезення одиниці продукції з фабрик в пункти розподілу наведені в таблиці. Необхідно так спланувати перевезення, щоб мінімізувати сумарні транспортні витрати.
Скласти модель транспортної задачі, та розв’язати її за допомогою Excel. Виконати аналіз оптимального рішення задачі. Розв’язання:
1. Склала модель транспортної задачі:
+
2. Пошук оптимального плану перевезень:
Таким чином, оптимальний план перевезення вантажу з чотирьох пунктів відправлення до п’яти пунктів призначення, при якому мінімізується функція загальних витрат на перевезення (F= 975).
Задача № 3
Підприємство, що займається збором та переробкою металолому має три промислові площадки. Вони можуть переробляти та поставляти металургійним підприємствам відповідно 240, 40 і 110 тон товарного металолому на місяць. В даний час у компанії є заявки на наступний місяць від 4-х металургійних підприємств на поставку 90, 190, 40 та 130 тон відповідно. Вартість доставки 1-єї тони металолому (в у. о.) від промислових площадок до металургійних заводів відома і наведена в таблиці.
Потрібно:
1. Скласти оптимальний план перевезення металолому споживачам – такий при якому сумарна вартість транспортних витрат буде мінімальною;
2. Встановити, яка кількість металолому і на який із заводів буде недопоставлена при оптимальному плані перевезення;
3. Встановити розмір мінімальних транспортних витрат. Розв’язання:
1. Склала модель транспортної задачі:
+
Пошук оптимального плану :
2. Я встановила, що 40 тон металолому буде недопоставлена на 3 – ій завод при оптимальному плані перевезення.
3. Встановила розмір мінімальних транспортних витрат.
Добавивши ще одну площадку, ми мінімізували транспортні витрати. Тепер цільова функція із F = 4040 змінилася на F*= 3120, тобто нам вигідно добавити ще одну промислову площадку.
Задача №4
Розглянемо задачу оптимального планування перевезень бензину деякої марки між нафтопереробними заводами (НПЗ) та автозаправними станціями (АЗС). У цьому випадку в якості продукту, що транспортується розглядається бензин, в якості пунктів виробництва-3 нафтопереробних заводи (n = 3), а в якості пунктів споживання - 4 автозаправні станції (m = 4). Обсяги виробництва бензину наступні: НПЗ № 1 - 10 т, НПЗ № 2 - 14 т, НПЗ № 3 - 17 т. Обсяги споживання бензину наступні: АЗС № 1-15 т, АЗС № 2 - 12 т, АЗС № 3-8,5 т, АЗС № 4-5,5 т. Тарифи транспортування однієї тонни бензину між НПЗ і АЗС задані у формі таблиці.
Необхідно побудувати математичну модель даної транспортної задачі, знайти оптимальний план перевезень при мінімальних витратах, проаналізувати стійкість отриманих результатів.
Розв’язання:
1. Склала модель транспортної задачі:
+
Пошук оптимального плану перевезень при мінімальних витратах:
Таким чином, цільова функція F = 208,5.
3. Аналіз звіту по стійкості.
У першій таблиці звіту , що має назву "Изменяемые ячейки", у стовпці "Нормированная стоимость" наведені значення, на які збільшиться цільова функція (вартість перевезень) при збільшенні обсягу перевезень на даному маршруті.
Стовпці "Допустимое увеличение" і "Допустимое уменьшение" мають відношення до тарифів маршрутів перевезень і задають їхні допустимі границі зміни, в межах яких зміна тарифів не приводить до зміни оптимального плану перевезень.
У другій таблиці ("Ограничения") у стовпці "Теневая цена" для пунктів відправлення і призначення наведена величина, на яку зміниться значення цільової функції при зміні запасу пункту відправлення або потреби пункту призначення відповідно на одиницю. Така зміна може бути тільки синхронною – збільшення запасу одного пункту відправлення спричиняє зменшення запасу у іншого. За допомогою значення тіньової ціни можна намітити перерозподіл запасів пунктів відправлення, і, якщо це можливо, знайти нове оптимальне рішення задачі.