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

Рис. 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).