3.7.1. Класична транспортна задача


Повернутися на початок книги
1 2 3 4 5 6 7 8 9 10 11 12 13 14 
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 
60 61 62 63 64 65 66 67 

Загрузка...

Постановка задачі. Деякий однорідний продукт (вантаж), який зосереджено в т постачальників, no а, одиниць у кожного

(г = 1, т), потрібний п споживачам у кількості не менш як Ь- оди-ниць (/ = \,nj. Відома вартість перевезення одиниці вантажу від і-го постачальника до   у'-го споживача  ctj (і = \,m;j = \,nj. Потрібно

знайти такий план перевезень продукції від постачальників до споживачів, при якому загальні витрати z на транспортування ва-нтажів були б мінімальними [6], [12], [19].

Позначимо через xtJ обсяг перевезень продукції від /-го поста-

чальника до/-го споживача [i = l,m; j = \,nj і запишемо економі-ко-математичну модель сформульованої задачі. Знайти

х- > 0 ,    і = \,т,    j = \,п ,      (3.39)

що належать області G, визначеної умовами:

п                    

Yjxtj ^ аі, І = hт;         (3.40)

т                     

Yjxtj-bj   j' = 1,и         (3-41)

7=1

і мінімізують сумарні витрати на перевезення продукції

т    п

z = X X cijxtj ■            (3 -42)

7=1 j=\

Умови (3.39) означають, що загальний обсяг продукції, що ви-возиться від /'-го постачальника, не перевищує наявність у нього продукції; умови (3.41) означають, що обсяг постачання продук-

Щ1 ™еГУ(™"42Т3мНааєЧа™ ZZuuZf трантіітної задачі.

План перевезень х° = х°        називають допустимим, якщо він

 ^   (т-п)

задовольняє всі обмеження (3.39)—(3.41). Допустимий розв'язок є оптимальним, якщо він мінімізує функцію (3.42).

Транспортну задачу називають замкнутою, якщо виконується умова

т          п

Yjat = Yjbj ■   (3.43)

У такому випадку всі споживачі повністю отримують необ-хідну кількість продукції, а всі постачальники реалізують всю наявну в них продукцію.

т          п

Якщо Yjai)Yjbj , тобто постачальники мають більше продукції

7 = 1    } = \

ніж сумарна потреба в ній, тоді необхідно ввести п + 1 фіктивно-

т          п

го споживача, якому нібито необхідно bn+l = ^ а. - £ Ь- продукції,

але витрати на перевезення до нього від всіх постачальників до-

рівнюють нулеві (с.и+1 =0 ,і = 1,т), після чого умова (3.43) вико-

нується, проте частка продукції у деяких постачальників залиша-ється після виконання заявок на перевезення.

т          п

Якщо YJ ai(Yjbj > тобто постачальники мають менше продук-

7=1      }=\

ції, ніж замовлення на неї, необхідно ввести фіктивного т + 1 по-

стачальника, який нібито має ат+1 = £ Ь- - X я, продукції, витрати

>1        7=1

на  перевезення  якої  до   всіх   споживачів   дорівнюють   нулеві

Але потреби деяких споживачів в цьому випадку не будуть повністю задоволені. Отже, класична транспортна задача завжди маєрозв'язок.

Розв'язування транспортної задачі здійснюється, наприклад, за методом потенціалів; якщо розрахунок виконується на ПК, то можна використати пакет «Пошук рішення» Excel.

Приклад 3.6. Виробниче об'єднання «АвтоГаз» має у своєму складі три підприємства, виробнича потужність яких щодо випу-ску автомобілів дорівнює відповідно 4000, 3000 і 5000 одиниць. На цю продукцію є заявки з двох областей. Потреби становлять, відповідно, 4700 і 6500 автомобілів.

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

Таблиця 3.8

 

Підприємство            Обласний центр

 

            0\         02

Пі        700      400

П2       200      300

П3       100      200

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

Знайдемо спочатку загальну виробничу потужність об'єднан-ня: 4000 + 3000 + 5000 = 12 000 (автомобілів). Заявлена потреба областей щодо цієї продукції становить: 4700 + 6500 = 11 200 (автомобілів). Отже, заявки можуть бути виконані повністю, до того ж ще 800 автомобілів виробниче об'єднання зможе вигото-вити для реалізації в інших областях, для експорту або створення запасу продукції, яку можна буде згодом реалізувати.

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

Розглянемо далі ситуацію, коли поряд з існуючими двома за-мовленнями на поставку автомобілів надійде й третє замовлен-ня — на поставку 3500 автомобілів до третьої області. Витрати на транспортування одного автомобіля в цьому напрямі такі: від першого підприємства — 500 грошових одиниць, від другого — 400 і від третього — 100 грошових одиниць.

У новій ситуації виробничих потужностей об’єднання вже не вистачає, щоб у поточному періоді виконати всі замовлення по-вністю. Тому, якщо вимога про 100-процентне задоволення замо-влення кожної області в поточному періоді буде обов’язковою, TO задача буде нерозв’язувана.

Для розв’язування задачі слід ввести фіктивного постачальника, виробнича потужність якого дорівнює 2700 автомобілів і відповідає величині недопоставок продукції через її дефіцит, вважаючи вар-тість транспортування до усіх областей від фіктивного постачаль-ника рівною нулю, прийдемо до заьфитої транспортної задачі.