Звіт2логіс (1)

Міністерство освіти і науки України

Федеральна державна бюджетна освітня установа вищої професійної освіти

"САМАРСЬКИЙ ДЕРЖАВНИЙ АЕРОКОСМІЧНИЙ

УНІВЕРСИТЕТ імені академіка С.П. КОРОЛЬОВА

національний дослідницький університет" (СДАУ)

Факультет економіки та управління

Звіт з лабораторної роботи №2

"Застосування математичної моделі транспортної задачі для складання оптимального плану перевезень"

за курсом: Логістика

Виконала: Василенкова О.С., гр. 742

Перевірив: Просвіркін Н.Ю

Вихідні дані завдання є обсяги передбачуваних перевезень ресурсів від постачальників до споживачів вартість їх доставки.

Існуєmпостачальників (i=1,m), які мають запас якогось продукту в кількостіaiодиниць відповідно, іnспоживачів ( j=1,n), у яких існує потреба в продукті в обсягахbjодиниць вантажу відповідно. Відомі транспортні витрати на перевезення одиниці товару з пунктів поставки до пунктів призначенняcij- транспортні витрати на перевезення одиниці вантажу від i-го постачальника до j-го споживача. Черезxijпозначатиметься кількість одиниць продукції, що перевозиться за маршрутом (i,j). На закінчення визначатиметься значення цільової функції F, що характеризує величину сумарних транспортних витрат.

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

За вихідними даними, використовуючи відомі методи («північно-західного» кута, мінімальної вартості, метод Фогеля), знайти вихідний допустимий план перевезень, перевірити його оптимальність методом потенціалів і, у разі потреби,провести один крок оптимізації.

Знайти оптимальне рішення за допомогою надбудови Ms Excel «Пошук рішення» для транспортного завдання з додатковими умовами:

- Фіксована поставка від i-го постачальника до j-го споживача;

- Постачання з обмеженнями за обсягом вантажів, що перевозяться.

Додаткові обмеження визначаються за результатами пошуку оптимального рішення базового варіанта завдання.

1.3 Алгоритм розв'язання транспортного завдання:

1. перевірка закритості транспортного завдання

2. перебування опорного плану (рішення, базису)

- методом північно-західного кута

- методом "мінімальної вартості"

3. перевірка опорного плану оптимальність

4. перехід від одного опорного плану до іншого до пошуку оптимального рішення

2.1 Розв'язання транспортного завдання методом північно-західного кута

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

На роль першої базисної змінної у спільній постановці вибирають будь-яку xij і вважають, що xij – min(bj ai)/

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

У ході вирішення поставленого завдання було отримано такі значення:

2.2 Розв'язання транспортного завдання методом "мінімальної вартості"

Методмінімальної вартості передбачає виконання наступної послідовності дій. У таблиці тарифів із усіх значень вартості вибирається найменше й у клітину (i,j). з найменшою вартістю записується min(ai bj), тобто найменше чисел ai і bj. З подальшого розгляду виключається рядок i, якщо запас ai вивезений повністю або стовпець j, якщо попит bj задоволений повністю, або рядок і стовпець, якщо ai=bj. Серед клітин, що залишилися, знову заповнюється клітина з найменшим значенням вартості і так далі, до тих пір, поки не будуть виконані всі обмеження завдання і знайдено опорне рішення.

Рішення транспортної задачі методом Фогеля

Метод Фогеля полягає у поетапному заповненні клітин таблиці. На першому етапі знаходиться різниця між найменшими цінами перевезення в кожному рядку та кожному стовпці таблиці. Ці різниці заносяться у відповідний додатковий рядок та стовпець таблиці. Далі вибирається рядок (стовпець) з найбільшим значенням різниці та в клітину з найменшою вартістю записується значення min(ai bj), викреслюється відповідний рядок або стовпець, як у методі мінімальної вартості. На наступному етапі для клітин, що залишилися, знову знаходиться рядок або стовпець з найбільшими значеннями різниць мінімальних значень цін і так далі, поки не знайдено опорне рішення. Цей метод дозволяє знайти опорний план, близький до оптимального.

3. Метод потенціалів (для опорного плану, отриманого методом "мінімальної вартості")

Алгоритм розв'язання задачі на основі методу потенціалів:

Знаходяться потенціали постачальників ui(i=1,m) та vj(j=1,n) за значеннями cij у заповнених (xij>0) клітинах таблиці. Так як в опорному плані заповнено m+n-1 клітин таблиці,то визначення потенціалів потрібно скласти систему m+n-1 лінійно незалежних рівнянь, де v=u-c. Така система є невизначеною, тому одній невідомій надають нульового значення (u1=0).

Знаходяться значення характеристик вільних (xij=0) клітин таблиці Якщо всім вільних клітин >0, то опорний план оптимальний. Якщо є значення Сусідні файли в папці маркетинг, відповіді на тести

#

---