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

ЗМІСТ

ВСТУП ................................................................................. 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. Таблицю "План перевезень" створити з порожніми полями (заповненими одиницями), заздалегідь заданого числового формату. В осередках запасів (потреб) кожного постачальника (споживача) ввести формулу, що виконує підсумовування всіх можливих поставок цього постачальника (споживача).

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

4. В осередку цільової функції ввести формулу, вираховують суму добутків елементів матриці "Вартість перевезень" та відповідних елементів матриці "План перевезень".

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

6. У діалоговому вікні "Параметри пошуку рішення" встановити параметр "Лінійна модель" і число ітерацій, рівне 100.

7. Виконати функцію "Пошук рішення" натисканням на кнопку "Виконати". В якості звіту за результатами вибрати необхідний пункт у списку "Тип звіту" діалогового вікна «Результати пошуку рішення».

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

4. Рішення параметричної транспортної задачі

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

Є чотири постачальника однорідного вантажу з обсягами поставок 100, 70, 70, 20 т. і три споживачі з обсягами споживання 120, 80, 60 т. Вартість транспортних витрат задана матрицею

причому вартість перевезення вантажу від четвертого постачальника до третього споживача змінюється в діапазоні 0 ≤ k ≤ 9.

Визначити оптимальний план перевезень, що забезпечує мінімальні транспортні витрати.

Зобразимо матричну запис задачі (табл. 4.1.1)

Табл. 4.1.1. Матрична запис завдання

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

цільова функція

.

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

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

Xij≥0,

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

Табл. 4.2.1. Ограничения по потребностям и запасам

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

Вважаючи k = 0, за відомим алгоритмом складемо опорне рішення методом Фогеля. Отриманий опорний план перевезень і алгоритм виконання з перебуванням мінімальних різниць вартостей перевезень (Cij) в кожному стовпці і рядку зображений на малюнку 4.3.1.

Рис. 4.3.1. Складання першого опорного рішення задачі по методу Фогеля

Процес виконання отримання опорного рішення з послідовним призначенням перевезень в осередки: А4В3 - А3В3 - А3В1 - А1В1 - А1В2 - A2B2.

Перевірка плану на виродженість: m + n-1 = 6. План невироджений.

Перевіримо опорне рішення на оптимальність за методом потенціалів. Розрахунок потенціалів рядків і стовпців для зайнятих з умови vi + uj = cij для зайнятих клітин і перевірка умови vi + uj ≤ cij для незайнятих наведені в таблиці 4.3.1.

Рішення, отримане при k = 0, є оптимальним для всіх значень параметра k, що задовольняють умові.

З умови для вільних клітин знайдемо:             

∆13 = v3 + u1 - c'13 = -1 + 2 - 2 = -1

∆21 = v1 + u2 - c'21 = 0 + 3 - 5 = -2

∆23 = v3 + u2 - c'23 = -1 + 3 - 6 = -4

∆32 = v2 + u3 - c'32 = 2 + 4 - 7 = -1             

∆41 = v1 + u4 - c'41 = 0 + 2+k - 6 = -4 + k

∆42 = v2 + u4 - c'42 = 2 + 2+k - 8 = -4 + k

Табл. 4.3.1. Перевірка першого опорного рішення на оптимальність методом потенціалів

визначення значень k1 и k2:

k1 = max(-aij/Bij) =    т.к.  все              Bij ≥ 0

k2 = min(-aij/Bij) = (-a41/B41; -a42/B42) = min(4;4) = 4. Все Bij > 0.

Так як за умовою завдання k ≥ 0, то оптимальне рішення зберігається при 0 ≥ k ≥ 4.

При цьому мінімальна вартість транспортних витрат становить:F(X1)min = 20*(1+k) + 40*3 + 30*4 + 90*2 + 10*4 + 70*5 = 830 + 20k

Таким чином, при , F(X1)min = 830 + 20k и

.

Щоб отримати оптимальне рішення при k ≥ 4 перерозподілимо поставки товарів в клітину (4,1), де k2 = 4. Знову отримане розподіл з урахуванням зміни вартості перевезення в комірці A4B3 (k = 4) представлено на малюнку 4.3.2.

Рис. 4.3.2. Складання другого опорного рішення задачі по методу Фогеля.

Процес виконання отримання опорного рішення з послідовним призначенням перевезень в осередки: А4В1 - А3В3 - А3В1 - А1В1 - А1В2 - A2B2.

Перевірка плану на виродженість: m + n-1 = 6. План невироджений.

Перевіримо опорне рішення на оптимальність за методом потенціалів. Розрахунок потенціалів рядків і стовпців для зайнятих з умови vi + uj = cij для зайнятих клітин і перевірка умови vi + uj ≤ cij для незайнятих наведені в таблиці 4.3.2

Табл. 4.3.2 Перевірка другого опорного рішення на оптимальність методом потенціалів

Рішення, отримане при k = 4, є оптимальним для всіх значень параметра k, що задовольняють умові.

З умови для вільних клітин знайдемо:

∆13 = a3 + b1 - C'13  = -1 + 2 - 2 = -1

∆21 = a1 + b2 - C'21  = 0 + 3 - 5 = -2             

∆23 = a3 + b2 - C'23  = -1 + 3 - 6 = -4

∆32 = a2 + b3 - C'32  = 2 + 4 - 7 = -1             

∆42 = a2 + b4 - C'42  = 2 + 6 - 8 = 0

∆43 = a3 + b4 - (C'43 + С''43) = -1 + 6 - (1+k) = 4-k

визначення значень k1 и k2

k1 = max(-aij/Bij) = -a43/B43 = 4. Все Bij < 0

k2 = min(-aij/Bij)  = т.к. все Bij ≤ 0

Так як за умовою завдання k ≤ 9, то оптимальне рішення зберігається при 4≥k≥9.

При цьому мінімальна вартість транспортних витрат складе:

F(X2)min = 20*6 + 60*3 + 10*4 + 90*2 + 10*4 + 70*5 = 910

Таким чином, при F(X2)min = 910 и

.

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

Створимо у вікні програми Ms Excel дві матриці «План перевезень» та «Вартість перевезень», згідно вищевикладеним правилам (рис 4.4.1). Також потрібно вказати клітинку містить змінний параметр k. При цьому в клітці A4B3 матриці «Вартість перевезень» встановлюємо формулу, що відображає залежність даного тарифу від параметра k: L7 = 1 + L9.

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

В осередку, які повинні відображати запаси постачальників і потреби споживачів в матриці «План перевезень» вводимо формули підсумовують значення всіх можливих поставок даних постачальників і споживачів, наприклад: B4 = СУММ (C4: E4), C3 = СУММ (С4: С7).

У осередок цільової функції (N7) введемо = СУММПРОИЗВ (C4: E7; J4: L7).

Метод рішення параметричної транспортної задачі засобами Ms Excel полягає в знаходженні оптимального рішення при кожному значенні параметра k, зі збереженням сценарію для кожної процедури «Пошук рішення». Після цього необхідно з усього діапазону зміни параметра k виділити окремі проміжки, на яких зберігається оптимальне рішення задачі і мінімальна вартість затрат.

У діалоговому вікні «Пошук рішення», згідно вищевказаних правил встановимо всі необхідні обмеження і посилання на необхідні комірки (рис. 4.4.2). Також необхідно в обмеженнях вказати межі зміни параметра k, тобто 0 ≤ k ≤ 9.

Рис. 4.4.2. Діалогове вікно «Пошук рішення»

У діалоговому вікні «Параметри пошуку рішення» встановити необхідні параметри (рис. 4.4.3).