Навігація
Головна
Транспортна задачаПриклад рішення канонічної транспортної задачіТранспортно-виробнича задачаМодель транспортної задачі лінійного програмуванняАлгоритми розв'язання задачСліди транспортних засобівПравове регулювання транспортно експедиційної діяльностіРозрахунок показників роботи окремого транспортного засобу або групи...Національне законодавство як джерело міжнародного транспортного права
 
Головна arrow Економіка arrow Економіко-математичні методи і прикладні моделі
< Попередня   ЗМІСТ   Наступна >

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

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

У т пунктах відправлення, які надалі будемо називати постачальниками, зосереджено певну кількість одиниць деякого однорідного продукту, яку позначимо: Даний продукт споживається в п пунктах, які будемо називати споживачами; обсяг споживання позначимо. Відомі витрати на перевезення одиниці продукту з пункту А i в пункт, які дорівнюють і наведені в матриці транспортних витрат

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

Позначимо кількість продукту, що перевозиться з пункту в пункт, через. Сукупність усіх змінних для стислості позначимо, тоді цільова функція задачі матиме вигляд

(3.15)

а обмеження виглядають наступним чином:

(3.16)

(3.17)

Умови (3.16) означають повне задоволення попиту у всіх пунктах споживання; умови (3.17) визначають повний вивіз продукції від всіх постачальників.

Необхідною і достатньою умовою розв'язання задачі (3.15) - (3.17) є умова балансу:

(3.18)

Транспортна задача, в якій має місце рівність (3.18), називається закритою і може бути вирішена як задача лінійного програмування за допомогою симплексного методу. Однак завдяки особливостям змінних задачі і системи обмежень розроблені спеціальні, менш громіздкі методи її вирішення. Найбільш застосовуваним методом є метод потенціалів, при якому кожній i- му рядку (i -му постачальнику) встановлюється потенціал, який можна інтерпретувати як ціну продукту в пункті постачальника, а кожному стовпцю j (j -му споживачеві) встановлюється потенціал, який можна прийняти умовно за ціну продукту в пункті споживача.

У найпростішому випадку ціна продукту в пункті споживача дорівнює його ціні в пункті постачальника плюс транспортні витрати на його доставку, тобто

(3.19)

Алгоритм методу потенціалів для закритої транспортної задачі детально описаний у ряді навчальних посібників (див., Наприклад, [6]). Першим етапом цього алгоритму є складання початкового розподілу (початкового плану перевезень); для реалізації цього початкового етапу є у свою чергу ряд методів: північно-західного кута, найменших вартостей, апроксимацій Фогеля та ін. Другим етапом служать побудова системи потенціалів на основі рівності (3.19) і перевірка початкового плану на оптимальність; у разі його неоптимальності переходять до третього етапу, зміст якого полягає в реалізації так званих циклів перерозподілу (коригування плану прикріплення споживачів до постачальників), після чого переходять знову до другого етапу. Сукупність процедур третього і другого етапів утворює одну ітерацію; ці ітерації повторюються, поки план перевезень не виявиться оптимальним за критерієм (3.15).

Якщо баланс (3.18) не виконується, то обмеження (3.16) або (3.17) мають вигляд нерівностей типу "менше або дорівнює"; транспортна задача в такому випадку називається відкритою. Для вирішення відкритій транспортній задачі методом потенціалів її зводять до закритої завданню шляхом введення або фіктивного споживача, якщо в нерівності перетворюються умови (3.17), або фіктивного постачальника - у разі перетворення в нерівності обмежень (3.16) (див . нижче приклад 3.5).

data-override-format="true" data-page-url = "http://stud.com.ua">

Розглянемо етапи реалізації методу потенціалів для закритої транспортної задачі більш докладно. Насамперед слід зазначити, що за умови балансу (3.18) ранг системи лінійних рівнянь (3.16), (3.17) дорівнює т + n - 1; таким чином із загального числа т 'п невідомих базисних невідомих буде т + п - 1. Внаслідок цього при будь-якому допустимому базисному розподілі в матриці перевезень (таблиці поставок), представленої в загальному вигляді в табл. 3.5, буде зайнято рівно т + п - 1 клітин, які будемо називати базисними на відміну від інших, вільних, клітин; зайняті клітини будемо відзначати діагональної рисою.

Таблиця 3.5

Потужності постачальників

Потужності споживачів

Етап 1. Первісне закріплення споживачів за постачальниками. Розглянемо два методи отримання початкового розподілу (початкового опорного плану): метод північно-західного кута і метод найменших вартостей. При кожному з цих методів при заповненні деякої клітини, крім останньої, викреслюється або тільки рядок матриці перевезень, або тільки стовпець; лише при заповненні останньої клітини викреслюються і рядок, і стовпець. Такий підхід буде гарантувати, що базисних клітин буде рівно т + п - 1. Якщо при заповненні деякої (не останньою) клітини одночасно задовольняються потужності і постачальника, і споживача, то викреслюється, наприклад, тільки рядок, а у відповідному стовпці заповнюється незайнята клітина так званої нульової поставкою, після чого викреслюється і стовпець. Для ідентифікації клітини зазвичай в дужках вказуються номери її рядка і стовпця.

У методі північно-західного кута завжди в першу чергу заповнюється клітка (з числа невикреслених), що стоїть у верхньому лівому (північно-західному) куту матриці перевезень. Приклад складання початкового розподілу даним методом показаний в табл. 3.6: заповнюється клітка (1; 1) і викреслюється перший стовпець, заповнюється клітка (1; 2) і викреслюється перший рядок; заповнюється клітка (2; 2) і викреслюється другий стовпець; заповнюється клітка (2; 3) і викреслюється другий рядок; заповнюється клітка (3; 3) і викреслюється третій стовпець; нарешті, заповнюється клітка (3; 4) і викреслюються останні рядок і стовпець. Число запитах клітин одно т + п - 1 = 3 + 4 - 1 = 6. Сумарні витрати па реалізацію даного плану перевезень складуть

Таблиця 3.6

Потужності

постачальників

Потужності споживачів

30

100

40

110

60

2

3

100

1

2

120

6

2

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

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

Порядок заповнення клітин: (2; 1), (3; 2), (1; 3), (2; 4), (1; 4), (3; 4). Сумарні витрати на перевезення, представлені в табл. 3.7, складають

Таблиця 3.7

Потужності

постачальників

Потужності споживачів

30

100

40

110

60

100

120

Отже, даний план перевезень значно ближче до оптимального, ніж план, складений за методом північно-західного кута.

Етап 2. Перевірка оптимальності отриманого плану перевезень. Введемо спеціальні показники для кожного рядка матриці перевезень (кожного постачальника), де, і показники для кожного стовпця (кожного споживача), де. Ці показники називаються потенціалами постачальників і споживачів, їх зручно інтерпретувати як ціни продукту у відповідних пунктах постачальників і споживачів. Потенціали підбираються таким чином, щоб для заповненої клітини (i; j) виконувалося рівність (3.19). Сукупність рівнянь виду (3.19), складених для всіх заповнених клітин (всіх базисних невідомих), утворює систему т + п - 1 лінійних рівнянь з т + п невідомими і. Ця система завжди сумісна, причому значення одного з невідомих можна задавати довільно (наприклад, і i = 0), тоді значення інших невідомих знаходяться з системи однозначно.

Розглянемо процес знаходження потенціалів для базисного початкового розподілу за методом північно-західного кута, представленого в табл. 3.6. Задавши і використовуючи формулу (3.19) для заповнених клітин (1; 1) і (1; 2), знаходимо і. Знаючи, по заповненої клітці (2; 2) знаходимо, а знаючи, по заповненої клітці (2; 3) знаходимо. Знаючи, по заповненої клітці (3; 3) знаходимо, а потім по заповненої клітці (3; 4) знаходимо. Результати представлені в табл. 3.8, де потенціали постачальників наведені в останньому стовпці, а потенціали споживачів - в останньому рядку.

Сенс прямокутного контуру, проведеного пунктиром в табл. 3.8, і знаків при його вершинах пояснений далі при описі етапу 3 методу потенціалів.

Таблиця 3.8

Потужності

постачальників

Потужності споживачів

u i

30

100

40

110

60

0

100

2

120

1

v j

4

5

8

5

Аналогічні результати для початкового розподілу за методом найменших вартостей, наведеного в табл. 3.7, представлені в табл. 3.9.

Таблиця 3.9

Потужності

постачальників

Потужності споживачів

u i

30

100

40

110

60

0

100

1

120

-1

v j

2

1

2

3

Щоб оцінити оптимальність розподілу, для всіх клітин (i, j) матриці перевезень визначаються їх оцінки, які позначимо через;, за формулою

(3.20)

Використовуючи раніше прийняту інтерпретацію, вираз () можна трактувати як суму ціни продукту у постачальника і вартості перевезення; ця сума шляхом вирахування порівнюється з ціною продукту у відповідного споживача v j. Очевидно, оцінки заповнених клітин дорівнюють нулю (ціна споживача покриває ціну постачальника і вартість перевезень). Таким чином, про оптимальність розподілу можна судити за величинами оцінок вільних клітин. Якщо оцінка деякої вільної клітини негативна, це можна інтерпретувати так: ціна, пропонована відповідним споживачем, більше суми ціни постачальника і вартості перевезення, тобто якби ця клітина була зайнята, то можна було б отримати додатковий економічний ефект. Отже, умовою оптимальності розподілу служить умова невід'ємності оцінок вільних клітин матриці перевезень.

Оцінки клітин за формулою (3.20) зручно представити у вигляді матриці оцінок. Для раніше розглянутого розподілу, отриманого методом північно-західного кута (див. Табл. 3.8), матриця оцінок клітин має вигляд

(3.21)

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

Для розподілу, отриманого методом найменших вартостей (див. Табл. 3.9), матриця оцінок клітин має вигляд

Так як всі оцінки невід'ємні, то не є можливості поліпшити даний план перевезень, тобто він оптимальний (сумарні витрати на перевезення за цим планом рівні 590). Крім того, слід зазначити, що в даному випадку оцінки всіх вільних клітин строго більше нуля, тобто будь-який інший план, що передбачає заняття хоча б однієї з цих клітин, буде менш оптимальний. Це говорить про те, що знайдений оптимальний план є єдиним. Наявність нульових оцінок вільних клітин в оптимальному плані перевезень, навпаки, свідчить про неєдиним оптимального плану.

Етап 3. Поліпшення неоптимального плану перевезень (цикли перерозподілу). Щоб поліпшити неоптимальний план перевезень, вибирається клітина матриці перевезень з негативною оцінкою; якщо таких клітин кілька, то зазвичай (але необов'язково) вибирається клітина з найбільшою за абсолютною величиною негативною оцінкою. Наприклад, для розподілу, представленого в табл. 3.8, такою клітиною може служити клітина (1; 3) (див. Матрицю оцінок (3.21)).

Для обраної клітини будується замкнута лінія (контур), початкова вершина якої лежить в обраній клітці, а всі інші вершини знаходяться в зайнятих клітинах; при цьому спрямування окремих відрізків контуру можуть бути тільки горизонтальними і вертикальними. Вершиною контуру, крім першої, є зайнята клітина, де відрізки контуру утворюють один прямий кут (не можна розглядати як вершини клітки, де горизонтальні і вертикальні відрізки контуру перетинаються). Очевидно, число відрізків контуру, як і його вершин, буде парним. У вершинах контуру розставляються черзі знаки "+" і "-", починаючи зі знака "+" в обраній вільній клітці. Приклад простого контуру показаний пунктиром в табл. 3.8, хоча вигляд контуру може бути найрізноманітнішим (див., Наприклад, контур в табл. 3.11).

Величина перерозподіляється поставки визначається як найменша з величин поставок у вершинах контуру зі знаком "-", і на цю величину збільшуються поставки в вершинах зі знаком "+" і зменшуються поставки в вершинах зі знаком "-". Це правило гарантує, що у вершинах контуру нс з'явиться негативних поставок, початкова обрана клітка виявиться зайнятою, в той час як одна із зайнятих клітин при цьому обов'язково звільниться. Якщо величина перерозподіляється поставки дорівнює поставкам не в одній, а в декількох вершинах контуру зі знаком "-" (це якраз має місце в контурі перерозподілу в табл. 3.8), то звільняється тільки одна клітина, зазвичай з найбільшою вартістю перевезення, а всі інші такі клітини залишаються зайнятими з нульовою поставкою.

Результат зазначених операцій для представленого в табл. 3.8 розподілу поставок показаний в табл. 3.10. Сумарні витрати на перевезення за цим планом складають:

що значно менше попередньої суми витрат 1170, хоча план перевезень в табл. 3.10 ще не є оптимальним. Про це свідчить наявність негативних значень у матриці оцінок клітин цього плану (відповідні потенціали u i і v j знайдені способом, викладеним при описі етапу 2):

Таблиця 3.10

Потужності

постачальників

Потужності споживачів

u i

30

100

40

110

60

0

100

2

120

-5

v i

4

5

2

-1

Транспортні завдання, у базисному плані перевезень яких мають місце зайняті клітини з нульовою поставкою (або в первісному розподілі, або в процесі ітерацій), називаються виродженими; приклад такої задачі представлений в табл. 3.10. У разі виродженої транспортної задачі існує небезпека зациклення, тобто нескінченного повторення ітерацій (нескінченного перебору одних і тих же базисних комбінацій зайнятих клітин). Як правило, в практичних завданнях транспортного типу зациклення не зустрічається, проте слід знати, що існують спеціальні правила, що дозволяють вийти з циклу, якщо зациклення все ж відбудеться. При відсутності виродження метод потенціалів кінцевий і призводить до оптимального плану перевезень за кінцеве число кроків.

Приклад 3.4. Вирішимо методом потенціалів закриту транспортну задачу, задану в табл. 3.11, в яку вже внесено деякий допустимий базисне розподіл. Сумарні транспортні витрати складають при цьому плані перевезень Потенціали за формулою (3.19) знаходимо наступним чином: задаючи u 1 = 0, знаходимо по клітці (1; 1) v i = 3, по клітці (1; 2) v 4 = 2, а по клітці (1; 4) v 4 = 1; потім по клітці (2; 1) знаходимо і 2 = 1 і по клітці (2; 3) v 3 = 2; нарешті, по клітці (3; 3) знаходимо u 3 = -2.

Таблиця 3.11

Потужності

постачальників

Потужності споживачів

u i

30

25

35

20

50

0

40

1

20

-2

v i

3

2

2

1

Матриця оцінок клітин для цього плану розраховується за формулою (3.21):

Наявність негативних оцінок свідчить про те, що план неоптимальний. Побудуємо контур перерозподілу, наприклад, для клітини (3; 2) в табл. 3.11 він показаний пунктиром і його вершин присвоєні відповідні знаки.

Найменша поставка в вершині контуру зі знаком "-" дорівнює 20, тому проведемо перерозподіл поставок, зменшивши поставки в клітинах зі знаком "-" на 20 і збільшивши поставки в клітинах зі знаком "+" також на 20; при цьому клітина (3; 2) заповнюється, а клітина (3; 3) звільняється. Новий план представлений в табл. 3.12, відповідні значення потенціалів показані в останніх стовпці і рядку.

Таблиця 3.12

Потужності

постачальників

Потужності споживачів

u i

30

25

35

20

50

0

40

1

20

0

v i

3

2

2

1

Матриця оцінок клітин цього розподілу не містить від'ємних значень, отже, даний план перевезень є оптимальним, вартість перевезень за цим планом дорівнює

Наявність нульовий оцінки незайнятої клітини (3; 1) говорить про те, що оптимальний план не є єдиним. Можна відзначити також, що, застосовуючи для початкового розподілу в цій транспортній задачі модифікацію подвійного переваги методу найменших вартостей, ми відразу ж отримали б оптимальний розподіл, представлене в табл. 3.12.

Приклад 3.5. Розглянемо приклад вирішення відкритої транспортної задачі, вихідні дані якої представлені в табл. 3.13.

Таблиця 3.13

Потужності

постачальників

Потужності споживачів

30

100

40

100

60

4

5

2

3

100

1

3

6

2

120

6

2

7

4

Перевіримо виконання умови балансу (3.18):

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

Нехай - обсяги перевезень від i -го постачальника j -му споживачеві. Цільова функція задачі матиме вигляд

а обмеження виглядають наступним чином:

по постачальниках:

по споживачах:

прямі обмеження:

Зведемо цю задачу до закритої, ввівши фіктивного споживача з потужністю 280 - 270 = 10; вартості перевезень одиниці вантажу у відповідних (фіктивних) клітинах приймаються рівними нулю, і ці клітини при складанні початкового розподілу перевезень заповнюються в найостаннішу чергу. Початковий план перевезень за методом найменших вартостей представлений в табл. 3.14.

Матриця оцінок клітин цього плану відповідно до методом потенціалів має вигляд

Таблиця 3.14

Потужності

постачальників

Потужності споживачів

u i

30

100

40

100

10

60

0

100

1

120

-1

v i

2

1

2

3

-1

Аналіз елементів матриці оцінок клітин свідчить про те, що план перевезень в табл. 3.14 є оптимальним і єдиним. Вартість перевезень за цим планом складе 550, при цьому потужності споживачів будуть задоволені повністю, а у третього постачальника залишаться невивезеним 10 одиниць вантажу.

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >
data-override-format="true" data-page-url = "http://stud.com.ua">

Cхожі теми

Транспортна задача
Приклад рішення канонічної транспортної задачі
Транспортно-виробнича задача
Модель транспортної задачі лінійного програмування
Алгоритми розв'язання задач
Сліди транспортних засобів
Правове регулювання транспортно експедиційної діяльності
Розрахунок показників роботи окремого транспортного засобу або групи однотипних транспортних засобів
Національне законодавство як джерело міжнародного транспортного права
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук