Побудова моделі транспортної задачі

Звіт

з дисципліни

Оптимізаційні методи і моделі

Лабораторна робота №4

Тема:

«Постановка та розв’язок транспортної задачі»

Виконав:

студент групи 31-ФК

Візнюк В.Ю.

Перевірила:

Петровська А. В.

Вінниця 2013

Лабораторна робота №4

Тема: закріплення теоретичного і практичного матеріалу, придбання навичок розв’язання і аналізу транспортних задач в середовищі Microsoft Excel.

Мета: сформувати математичну постановку транспортної задачі лінійного програмування, знайти рішення транспортної задачі за допомогою надбудови пакету Microsoft Excel "Поиск решения", проаналізувати обсяги перевезень і тіньові ціни за звітом по стійкості розв’язку задачі.

Хід роботи

Теоретична частина:

Транспортна задача – це розподільна задача, в якій роботи і ресурси вимірюються в одних і тих же одиницях. У таких задачах ресурси можуть бути розподілені між роботами, і окремі роботи можуть бути виконані за допомогою різних комбінацій ресурсів. Прикладом транспортної задачі є розподіл продукції підприємств-виробників між складами підприємств-споживачів.

Стандартна транспортна задача визначається як задача розробки найбільш економічного плану перевезення продукції одного виду з декількох пунктів відправлення в пункти призначення. При цьому величина транспортних витрат прямо пропорційна об'єму продукції, що перевозиться, і задається за допомогою тарифів на перевезення одиниці продукції.

Класична транспортна задача лінійного програмування є збалансованою або закритою, тобто формулюється у формі, коли має місце рівність загального обсягу виробництва аналізованого продукту – загальному обсягу його споживання. В іншому випадку, якщо рівність не має місця, то транспортна задача називається незбалансованою або відкритою. На практиці зустрічаються різні модифікації транспортної задачі.

Найбільш відомі з них використовують додаткову структуру типу графа для побудови структури транспортної мережі, що з'єднує пункти виробництва і споживання. Відповідна транспортна задача може бути сформульована в мережевій постановці стосовно до конкретного графу і тому відноситься до класу задач оптимізації на графах.

Отже, транспортні задачі класифікують наступним чином:

1. Задачі в яких виконується умова балансу (пропозиція дорівнює попиту):

Σаі = Σbj

Називають закритими, замкненими або збалансованими;

2. Якщо запаси менші ніж закази:

Σаі < Σbj

то такі задачі називають задачі відкриті з дефіцитом. Їх можна привести до стандартної збалансованої задачі, за допомогою введення додаткового фіктивного постачальника (складу) з запасом, що рівний дефіциту, та нульовими вартостями перевезень.

3. Якщо запаси перевищують заявки:

Σаі > Σbj

то такі задачі називають незбалансованими з надлишком. Вони приводяться до стандартної збалансованої задачі шляхом введення фіктивного споживача з заявкою, що рівна надлишку, і нульовими вартостями перевезень.

Практична частина

Задача №1

Знайдіть рішення транспортної задачі, вихідні дані якої визначаються таблицею і матрицею.

Матриця пропускних можливостей:

Числа в матриці D визначають граничну кількість вантажу, яку можна перевезти з даного пункту відправлення у відповідний пункт призначення. Символ ∞ означає, що на перевезення з даного пункту відправлення у відповідний пункт призначення немає обмежень.

Побудова моделі транспортної задачі

Постановка транспортної задачі полягає у визначенні оптимального плану перевезень деякого однорідного вантажу з 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), має наступний вигляд: