Зміст
Введення
В§ 1. Постановка Транспортної задачі (ТЗ) для n змінних
В§ 2. Приклад рішення Транспортної задачі
В§ 3. Транспортні задачі за різними критеріями
В§ 4. Рішення транспортної задачі в Excel
Список літератури
Введення
Під назвою "транспортна задача" об'єднується широке коло завдань з єдиною математичною моделлю. Класична транспортна задача - задача про найбільш економному плані перевезень однорідного продукту або взаємозамінних продуктів з пунктів виробництва в пункти споживання, зустрічається найчастіше в практичних додатках лінійного програмування. Лінійне програмування є одним з розділів математичного програмування - галузі математики, розробляє теорію і чисельні методи рішення багатовимірних екстремальних задач з обмеженнями.
Величезне кількість можливих варіантів перевезень ускладнює отримання достатньо економного плану емпіричним або експертним шляхом. Застосування математичних методів і обчислювальних в плануванні перевезень дає великий економічний ефект. Транспортні задачі можуть бути вирішені симплексним методом проте матриця системи обмежень транспортної задачі настільки своєрідна, що для її рішення розроблені спеціальні методи. Ці методи, як і симплексний метод, дозволяють знайти початкове опорне рішення, а потім, поліпшуючи його отримати оптимальне рішення.
В Залежно від способу подання умов транспортної задачі вона може бути представлена ​​в мережевий (схематичною) або матричної (табличній) формі. Транспортна задача може також вирішуватися з обмеженнями і без обмежень.
В§ 1. Постановка Транспортної задачі (ТЗ) для n змінних
Нехай є кілька постачальників однорідної продукції (кожен з певним запасом) і кілька споживачів цієї продукції (з відомими потребами у кожного). Задана також мережа комунікацій (доріг, річок, повітряних ліній і т.д.) зв'язує кожного постачальника з кожним споживачем. На кожній комунікації задана ціна перевезення - вартість перевезення одиниці продукції. Якщо яка - або комунікація відсутня, то вважаємо, що вона є, але ціну перевезення на ній встановлюємо рівною безкінечності (+ в€ћ). Ця угода зробить невигідним перевезення по ній і автоматично виключить дану комунікацію з плану перевезень.
Таким чином, потрібно скласти план перевезень продукції від постачальників до споживачів так, щоб потреби споживачів були б задоволені за рахунок вивезення запасу від постачальників. Мета - мінімізація сумарної вартості всіх перевезень.
Транспортні задачі бувають:
1) відкриті m в‰ n (Сумарний запас продукції, наявної у постачальників, не збігається з сумарною потребою в продукції у споживачів.)
2) закриті m = n (сумарний запас продукції, наявної у постачальників, збігається з сумарною потребою в продукції у споживачів.)
Метод потенціалів В«працюєВ» тільки для закритих ТЗ, причому, закрита ТЗ завжди можна залагодити.
Відкриту ТЗ зводять до закритої ТЗ шляхом додавання до сумарного запасу продукції або сумарної потреби продукції відсутніх одиниць до рівності сумарного запасу продукції та сумарної потреби продукції.
Закрита транспортна задача формулюється як задача лінійного програмування (ЗЛП) наступного виду:
, де
- запас i - го постачальника
- потреба j - го споживача
- ціна перевезення одиниці продукції по комунікацій (i, j)
(від i - го постачальника до j - му споживачеві)
- обсяг перевезення продукції (Невідомий) з комунікацій (i, j).
Для виведення критерії оптимальності транспортної задачі побудуємо двоїсту задачу.
Структура матриці обмежень транспортної задачі така, що стовпець, відповідної змінної містить рівно два ненульових елемента: одиницю у рядку з номером i і одиницю у рядку m + i.
Вектор двоїстих змінних Y = (, ...,,, ...,) має m + n компонент (по числі обмежень ТЗ), які називаються потенціалами: змінні,, ..., - потенціали постачальників; змінні, ..., - потенціали споживачів.
Використовуючи схему для побудови двоїстої задачі до ЗЛП в стандартній формі, маємо:
В отриманій двоїстої задачі n В· m обмежень, відповідних кожної змінної ТЗ. Згадуючи, що нев'язка між лівою і правою частиною в обмежень двоїстої задачі є оцінка для відповідної змінної вихідної задачі, запишемо умови оптимальності поточного плану перевезень в ТЗ:
.
Невідомі потенціали і (їх загальна кількість дорівнює m + n) можуть бути знайдені (і саме так відшукуються) з умови рівності нулю оцінок для базисних змінних (заповнених клітин таблиці) ТЗ (таких рівностей (m + n - 1), що випливає з зауваження нижче).
для заповнених клітин (i, j) таблиці ТЗ.
Рішення отриманої системи (містить невідомих на одиницю більше, ніж число рівнянь) шукається, коли одне з невідомих (взагалі кажучи, будь-яке) покладається рівним деякому числу (теж, взагалі кажучи, будь). Після цього залишилася система має єдине рішення.
В§ 2. Приклад рішення Транспортної задачі
Метод потенціалів представляє з себе модифікацію симплекс-методу, що враховує специфіку транспортної задачі, тому його алгоритм не відрізняється від алгоритму симплекс-методу, за винятком кроку перевірки цільової функції на необмеженість на безлічі рішень. Відсутність зазначеного кроку в методі потенціалів обумовлено теоремою про те, що закрита ТЗ завжди можна залагодити . Отже, алгоритм методу потенціалів для вирішення ТЗ складається з наступних кроків:
КРОК 1. Побудова початкового плану перевезень.
КРОК 2. Перевірка поточного плану на оптимальність.
Якщо план оптимальний, то алгоритм завершено.
КРОК 3. Поліпшення плану перевезень. Перехід до кроку 1.
Опишемо алгоритм по кроках, ілюструючи кожний крок
КРОК 1. Побудова початкового плану перевезень.
Побудова початкового рішення (Як і подальші розрахунки) проводять в таблиці, що має наступний вигляд:
Клітка (i, j) таблиці відповідає комунікації, що зв'язує i-го постачальника сj-м споживачем.
Побудувати початковий план перевезень означає - призначити обсяги перевезень у клітини таблиці таким чином, щоб:
а) число заповнених клітин було (m + n-1). (Тоді план перевезень буде відповідати базисним рішенням ЗЛП);
б) сума перевезень в будь рядку повинна дорівнювати запасу відповідного постачальника, а сума перевезень в кожному стовпці дорівнює потреби споживача. (Умова виконання обмежень ТЗ). Існує кілька способів знаходження початкового рішення, які відрізняються тільки вибором клітини, в яку призначається чергова перевезення. Так, в способі північно-західного кута (СЗУ) для чергового призначення перевезення вибирається ліва верхня клітина таблиці (при цьому ніяк не враховуються ціни перевезень). Навпаки, в способі мінімальної вартості (МС) для заповнення вибирається клітина поточної таблиці з мінімальною ціною перевезення, що в більшості випадків (але не завжди) призводить до більш дешевого (а значить і ближчого до оптимального) початкового плану перевезень.
Ми будемо користуватися способом мінімальної вартості (МС).
Викладемо тепер алгоритм знаходження початкового рішення .
КРОК 1 . Певним способом вибираємо клітку в поточній таблиці. Нехай вона має індекси (i, j) (i-номер постачальника, j - номер споживача).
КРОК 2. В якості перевезень в цю клітку призначаємо найменшу з a i і потреби bj.
x ij = min { a i , bj }
КРОК З. Зменшимо запас a i і ...
