Транспортна задача

ЗМІСТ

ВСТУП ................................................................................. 3

1. МАТЕМАТИЧНА ПОСТАНОВКА ЗАДАЧІ ПРО ОПТИМАЛЬНИХ ПЕРЕВЕЗЕННЯ .......................................................................... 5

2. АНАЛІТИЧНИЙ МЕТОД ВИРІШЕННЯ ПАРАМЕТРИЧНОЇ ТРАНСПОРТНОЇ ЗАВДАННЯ

2.1. Методика знаходження вихідного опорного рішення задачі про оптимальні перевезеннях методом Фогеля .................................... 6

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

2.3. Методика рішення параметричної транспортної задачі ......... 7

3. МЕТОД ВИРІШЕННЯ ЗАДАЧІ ПРО ОПТИМАЛЬНИХ ПЕРЕВЕЗЕННЯ ЗАСОБАМИ MS EXCEL ......................................................... 8

4. РІШЕННЯ ПАРАМЕТРИЧНОЇ ТРАНСПОРТНОЇ ЗАВДАННЯ

4.1. Постановка параметричної транспортної завдання ................... 10

4.2. Математична модель задачі ............................................. 10

4.3. Рішення задачі аналітичним методом ................................. 11

4.4. Рішення завдання засобами Ms Excel ..................................... 14

ВИСНОВОК ........................................................................... 19

Список використаної літератури ......................................... 20

                                                              Вступ

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

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

Існує кілька основних алгоритмів оптимізації: методом перебору, симплекс-методом, (рішенням екстремальних рівнянь або нерівностей).

Найбільший інтерес представляє симплекс-метод, при відносно нескладному алгоритмі дозволяє прораховувати і знаходити рішення для сотень і тисяч рівнянь (нерівностей).

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

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

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

1. Математична постановка задачі про оптимальні перевезеннях

В загальному вигляді задачу можна представити таким чином: в m пунктах виробництва A1, A2, ..., Am є однорідний вантаж у кількості відповідно a1, a2, ..., am. Цей вантаж необхідно доставити в n пунктів призначення B1, B2, ..., Bn у кількості відповідно b1, b2, ..., bn. Вартість перевезення одиниці вантажу (тариф) з пункту Ai в пункт Bj дорівнює cij.

Потрібно скласти план перевезень, що дозволяє вивести всі вантажі і має мінімальну вартість.

Позначимо через xij кількість вантажу, що перевозиться з пункту Ai, в пункт Bj. Запишемо умови задачі в розподільну таблицю, яку будемо використовувати для знаходження рішення (табл. 1.1).

Таблиця 1.1. Модель розподільної таблиці.

Математична модель транспортної задачі має вигляд

при обмеженнях:

Оптимальним рішенням завдання є матриця

задовольняє системі обмежень і доставляє мінімум цільової функції [1].

2. Аналітичний метод вирішення параметричної транспортної задачі

2.1 Методика знаходження вихідного опорного рішення задачі про оптимальні перевезеннях методом Фогеля

Алгоритм виконання методу.

1. В кожному рядку і кожному стовпці розподільної таблиці обчислити різниці між усіма парами елементів (Cij) і вибрати мінімальну.

2. Серед усіх обраних мінімальних різниць Cij вибрати максимальне значення і виділити відповідний стовпець (рядок).

3. У вибраному стовпці (рядку) знайти мінімальне значення Cij і призначити необхідну перевезення, орієнтуючись на наявність запасів (ai) даного постачальника (Aij) і потреб (bj) даного споживача (Bij).

4. Викресливши відповідний рядок (стовпець), тобто видаливши з подальших розрахунків постачальника (споживача), запаси якого (потреби) вичерпані, повторити заново алгоритм (1-4) до повного складання плану перевезень.

Процес розподілу продовжують до тих пір, поки всі вантажі від постачальників не будуть вивезені, а споживачі не будуть задоволені. При розподілі вантажів може виявитися, що кількість зайнятих клітин менше, ніж m + n-1. В цьому випадку завдання вважається виродженої. В цьому випадку відсутнє число зайнятих клітин заповнюється нульовими поставками, які називаються умовно зайнятими.

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

Знайдене вихідне опорне рішення перевіряється на оптимальність методом потенціалів за наступним критерієм: якщо опорне рішення транспортної задачі є оптимальним, то йому відповідає система m + n дійсних чисел ui і vj, що задовольняють умовам ui + vj = cij для зайнятих клітин і ui + vj-cij ≤ 0 для вільних клітин.

Числа ui і vj називають потенціалами. В розподільну таблицю додають рядок vj і стовпець ui.

Потенціали ui і vj знаходять з рівності ui + vj = cij, справедливого для зайнятих клітин. Одному з потенціалів дається довільне значення, наприклад u1 = 0, тоді інші потенціали визначаються однозначно. Так, якщо відомий потенціал ui, то vj = cij-ui; якщо відомий потенціал vj, то ui = cij-vj.

Позначимо Δij = ui + vj-cij. Цю оцінку називають оцінкою вільних клітин. Якщо Δij ≤ 0, то опорне рішення є оптимальним. Якщо хоча б одна з оцінок Δij> 0, то опорне рішення не є оптимальним і його можна поліпшити, перейшовши від одного опорного рішення до іншого [1].

2.3. Методика рішення параметричної транспортної задачі

              Завдання формулюється так: для всіх значень параметра δ≤k≤φ где δ и φ – довільні дійсні числа, знайти такі значення які звертають в мінімум функцію

де Xij - обсяг поставок вантажу,

при обмеженнях:

Xij≥0,

              Користуючись методом потенціалів, (Фогеля) вирішуємо завдання при k = δ до отримання оптимального рішення. Ознакою оптимальності є умова:

для незайнятих клітин

и для зайнятих клітин,

де – потенціали рядків, стовпців розподільної таблиці.

Умова сумісності транспортної завдання запишеться у вигляді

Значення aij і Bij визначаються з умови

где визначаються з систем рівнянь

Значення k знаходяться в межах k1≤k≤k2:

якщо існує хоча б одне Bij>0;

якщо все Bij≥0

якщо існує хоча б одне Bij>0;

якщо все Bij≤0.

Алгоритм рішення.

1) Задачу вирішуємо при конкретному значенні параметра k = δ до отримання оптимального рішення.

2) Визначаємо aij і Bij.

3) Обчислюємо значення параметра k.

4) Якщо k> δ, виробляємо перерозподіл поставок і отримуємо нове оптимальне рішення. Якщо k = δ, то процес вирішення закінчено [1].

3 Метод рішення задачі обоптімальних перевезеннях засобами Ms Excel

Знаходження оптимального плану перевезень із застосуванням комп'ютерної програми Ms Excel здійснюється за допомогою функції "Пошук рішення".

Схема виконання:

1. Для зручності розрахунків необхідно окремо створити матрицю, що відображає вартість перевезень (Cij) (рис 3.1.), А також матрицю, яка повинна буде відображати шуканий план перевезень (рис. 3.2.).

Рис. 3.1. Фрагмент вікна програми Ms Excel: Модель таблиці «Вартість перевезень».

2. У таблиці «Вартість перевезень» в осередках запасів постачальників і потреб споживачів записати кількість запасів постачальників і потреб споживачів відповідно, вказане в умові завдання.

3. Таблицю "План перевезень" створити з порожніми полями (заповненими одиницями), заздалегідь заданого числового формату. В осередках запасів (потреб) кожного постачальника (споживача) ввести формулу, що виконує підсумовування всіх можливих поставок цього постачальника (споживача).