Відмінності між версіями «Двохетапна транспортна задача.»
| Рядок 1: | Рядок 1: | ||
На практиці досить часто зустрічається випадок, коли певна частина продукції спочатку перевозиться до посередницьких фірм (сховищ), а потім споживачам. У такому разі розв’язання задачі поділяють на два етапи: спочатку знаходять оптимальний план перевезень від постачальників до посередників, а потім — від посередників до споживачів. Така задача має назву двохетапної транспортної задачі. | На практиці досить часто зустрічається випадок, коли певна частина продукції спочатку перевозиться до посередницьких фірм (сховищ), а потім споживачам. У такому разі розв’язання задачі поділяють на два етапи: спочатку знаходять оптимальний план перевезень від постачальників до посередників, а потім — від посередників до споживачів. Така задача має назву двохетапної транспортної задачі. | ||
| − | Нехай в m пунктах постачання <math>А_1, А_2, …, А_m</math> є відповідно <math>a_1, a_2, ... a_m</math> одиниць продукції, яку необхідно перевезти до l посередницьких фірм <math>D_1, D_2, …, D_l</math>, місткості сховищ яких становлять <math>D_1, D_2, …, D_l</math> , а потім доставити її споживачам <math>B_1, B_2, …, B_m</math> , потреби яких становлять <math>b_1, b_2, …, b_n</math> . Відомі також витрати на перевезення одиниці продукції від кожного постачальника до посередницьких фірм — <math>c_ik</math> та від посередників до споживачів — <math>c_kj</math> . Потрібно визначити оптимальну схему перевезень продукції з мінімальни-ми сумарними витратами. Якщо обсяг продукції, що перевозить-ся від i-го постачальника до k-ої фірми, позначити через <math>x_ik</math> , а об-сяг вантажу, що перевозиться від k-ої фірми j-му споживачеві — через <math>x_kj</math> , то математична модель задачі матиме вигляд: < | + | Нехай в m пунктах постачання <math>А_1, А_2, …, А_m</math> є відповідно <math>a_1, a_2, ... a_m</math> одиниць продукції, яку необхідно перевезти до l посередницьких фірм <math>D_1, D_2, …, D_l</math>, місткості сховищ яких становлять <math>D_1, D_2, …, D_l</math> , а потім доставити її споживачам <math>B_1, B_2, …, B_m</math> , потреби яких становлять <math>b_1, b_2, …, b_n</math> . Відомі також витрати на перевезення одиниці продукції від кожного постачальника до посередницьких фірм — <math>c_ik</math> та від посередників до споживачів — <math>c_kj</math> . Потрібно визначити оптимальну схему перевезень продукції з мінімальни-ми сумарними витратами. Якщо обсяг продукції, що перевозить-ся від i-го постачальника до k-ої фірми, позначити через <math>x_ik</math> , а об-сяг вантажу, що перевозиться від k-ої фірми j-му споживачеві — через <math>x_kj</math> , то математична модель задачі матиме вигляд: </ br> |
за умов: | за умов: | ||
| − | < | + | </ br> |
<math>\sum_{k=1}^l x_ik = a </math> ; <\ br> | <math>\sum_{k=1}^l x_ik = a </math> ; <\ br> | ||
| − | <math>\sum_{j=1}^n c_jx_j \to \max </math> ; < | + | <math>\sum_{j=1}^n c_jx_j \to \max </math> ; </ br> |
| − | <math>\sum_{j=1}^n c_jx_j \to \max </math> ; < | + | <math>\sum_{j=1}^n c_jx_j \to \max </math> ; </ br> |
| − | <math>\sum_{j=1}^n c_jx_j \to \max </math> ;. < | + | <math>\sum_{j=1}^n c_jx_j \to \max </math> ;. </ br> |
Зазначимо, що коли загальний обсяг вантажу дорівнює місткості всіх складів і баз , а також сумарній потребі всіх споживачів , тобто = = , то така двохетапна транспортна задача може бути розв’язана як дві одноетапні. В іншому разі окремі оптимальні плани двох задач не збігати-муться з оптимальним планом загальної задачі. | Зазначимо, що коли загальний обсяг вантажу дорівнює місткості всіх складів і баз , а також сумарній потребі всіх споживачів , тобто = = , то така двохетапна транспортна задача може бути розв’язана як дві одноетапні. В іншому разі окремі оптимальні плани двох задач не збігати-муться з оптимальним планом загальної задачі. | ||
Метод розв’язування двохетапної транспортної задачі, ро-зроб¬лений Орденом-Маршем, полягає у врахуванні місткос-тей посередників двічі — як постачальників і як споживачів. | Метод розв’язування двохетапної транспортної задачі, ро-зроб¬лений Орденом-Маршем, полягає у врахуванні місткос-тей посередників двічі — як постачальників і як споживачів. | ||
Умови задачі подаються у вигляді таблиці, в рядках якої запи-сують дані про постачальників, а також про посередницькі фір-ми, а в стовпцях — знову дані про посередників та споживачів. У клітинах, які розміщені на перетині рядків-постачальників та стовпців-споживачів, фіксують реальні затрати на перевезення одиниці продукції. В діагональних клітинах на перетині рядків і стовпців, які відповідають посередницьким фірмам, ставлять ну-льові величини затрат. Решту клітин таблиці блокують, тобто ва-ртості перевезень прирівнюють до деякого досить великого чис-ла М. У процесі розв’язування задачі в цих клітинах не будуть передбачатися перевезення продукції, що відповідає умовам дво-хетапної транспортної задачі. | Умови задачі подаються у вигляді таблиці, в рядках якої запи-сують дані про постачальників, а також про посередницькі фір-ми, а в стовпцях — знову дані про посередників та споживачів. У клітинах, які розміщені на перетині рядків-постачальників та стовпців-споживачів, фіксують реальні затрати на перевезення одиниці продукції. В діагональних клітинах на перетині рядків і стовпців, які відповідають посередницьким фірмам, ставлять ну-льові величини затрат. Решту клітин таблиці блокують, тобто ва-ртості перевезень прирівнюють до деякого досить великого чис-ла М. У процесі розв’язування задачі в цих клітинах не будуть передбачатися перевезення продукції, що відповідає умовам дво-хетапної транспортної задачі. | ||
Версія за 06:19, 14 травня 2012
На практиці досить часто зустрічається випадок, коли певна частина продукції спочатку перевозиться до посередницьких фірм (сховищ), а потім споживачам. У такому разі розв’язання задачі поділяють на два етапи: спочатку знаходять оптимальний план перевезень від постачальників до посередників, а потім — від посередників до споживачів. Така задача має назву двохетапної транспортної задачі. Нехай в m пунктах постачання Неможливо розібрати вираз (невідома помилка): А_1, А_2, …, А_m
є відповідно Неможливо розібрати вираз (невідома помилка): a_1, a_2, ... a_m одиниць продукції, яку необхідно перевезти до l посередницьких фірм Неможливо розібрати вираз (невідома помилка): D_1, D_2, …, D_l
, місткості сховищ яких становлять Неможливо розібрати вираз (невідома помилка): D_1, D_2, …, D_l
, а потім доставити її споживачам Неможливо розібрати вираз (невідома помилка): B_1, B_2, …, B_m , потреби яких становлять Неможливо розібрати вираз (невідома помилка): b_1, b_2, …, b_n . Відомі також витрати на перевезення одиниці продукції від кожного постачальника до посередницьких фірм — Неможливо розібрати вираз (невідома помилка): c_ik та від посередників до споживачів — Неможливо розібрати вираз (невідома помилка): c_kj . Потрібно визначити оптимальну схему перевезень продукції з мінімальни-ми сумарними витратами. Якщо обсяг продукції, що перевозить-ся від i-го постачальника до k-ої фірми, позначити через Неможливо розібрати вираз (невідома помилка): x_ik , а об-сяг вантажу, що перевозиться від k-ої фірми j-му споживачеві — через Неможливо розібрати вираз (невідома помилка): x_kj , то математична модель задачі матиме вигляд: </ br>
за умов: </ br> Неможливо розібрати вираз (невідома помилка): \sum_{k=1}^l x_ik = a
; <\ br>
Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n c_jx_j \to \max
; </ br>
Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n c_jx_j \to \max
; </ br>
Неможливо розібрати вираз (невідома помилка): \sum_{j=1}^n c_jx_j \to \max
;. </ br>
Зазначимо, що коли загальний обсяг вантажу дорівнює місткості всіх складів і баз , а також сумарній потребі всіх споживачів , тобто = = , то така двохетапна транспортна задача може бути розв’язана як дві одноетапні. В іншому разі окремі оптимальні плани двох задач не збігати-муться з оптимальним планом загальної задачі.
Метод розв’язування двохетапної транспортної задачі, ро-зроб¬лений Орденом-Маршем, полягає у врахуванні місткос-тей посередників двічі — як постачальників і як споживачів. Умови задачі подаються у вигляді таблиці, в рядках якої запи-сують дані про постачальників, а також про посередницькі фір-ми, а в стовпцях — знову дані про посередників та споживачів. У клітинах, які розміщені на перетині рядків-постачальників та стовпців-споживачів, фіксують реальні затрати на перевезення одиниці продукції. В діагональних клітинах на перетині рядків і стовпців, які відповідають посередницьким фірмам, ставлять ну-льові величини затрат. Решту клітин таблиці блокують, тобто ва-ртості перевезень прирівнюють до деякого досить великого чис-ла М. У процесі розв’язування задачі в цих клітинах не будуть передбачатися перевезення продукції, що відповідає умовам дво-хетапної транспортної задачі.
