«Во всех частях земного шара имеются свои, даже иногда очень любопытные другие части» Сочинения Козьмы Пруткова ТРАНСПОРТНА ЗАДАЧА Транспортна задача є типовою задачею лінійного програмування, отже, її розв’язок можна отримати звичайним симплексним методом. Однак, у деяких випадках застосування універсальних алгоритмів є нераціональним. Специфічна структура транспортної задачі дає змогу отримати альтернативний метод відшукання оптимального плану у вигляді простішої у порівнянні з симплексним методом обчислювальної процедури. Транспортна задача належить до типу розподільчих задач лінійного програмування. Економічний зміст таких задач може стосуватися різноманітних проблем, що переважно зовсім не пов’язано із перевезенням вантажів, як, наприклад, задачі оптимального розміщення виробництва, складів, оптимального призначення тощо. Деякі з таких задач розглянемо в цьому розділі. 5.1. Економічна і математична постановка транспортної задачі Класична транспортна задача лінійного програмування формулюється так: деякий однорідний продукт, що знаходиться у m постачальників Аі в обсягах одиниць відповідно необхідно перевезти n споживачам в обсягах одиниць. При цьому виконується умова, що загальний наявний обсяг продукції у постачальників дорівнює загальному попиту всіх споживачів. Відомі вартості перевезень одиниці продукції від кожного Аі-го постачальника до кожного Вj-го споживача, що подані як елементи матриці виду:
Необхідно визначити план перевезень, за якого вся продукція була б вивезена від постачальників, повністю задоволені потреби споживачів і загальна вартість всіх перевезень була б мінімальною. У такій постановці задачі ефективність плану перевезень визначається його вартістю і така задача має назву транспортної задачі за критерієм вартості перевезень. Запишемо її математичну модель. Позначимо через обсяг продукції, що перевозиться від постачальника до споживача . Тоді умови задачі зручно подати у вигляді такої таблиці: Таблиця 5.1 Споживачі В1 В2 ... Вn
Постачальники b1 b2 ... bn
A1 а1 с11 x11 с12 x12 ... с1n x1n
A2 а2 с21 x21 с22 x22 … с2n x2n
… … … … … …
Am аm сm1 xm1 сm2 xm2 … сmn xmn
Мають виконуватися такі умови: сумарний обсяг продукції, що вивозиться з кожного і-го пункту, має дорівнювати запасу продукції в даному пункті:
сумарний обсяг продукції, що ввезений кожному j-му споживачеві, має дорівнювати його потребам:
сумарна вартість всіх перевезень повинна бути мінімальною:
Очевидно, що . У скороченій формі запису математична модель транспортної задачі за критерієм вартості перевезень має такий вигляд: (5.1) за обмежень: ; (5.2) ; (5.3) . (5.4) У розглянутій задачі має виконуватися умова: . (5.5) Транспортну задачу називають збалансованою, або закритою, якщо виконується умова (5.5). Якщо ж така умова не виконується, то транспортну задачу називають незбалансованою, або відкритою. Домовимося планом транспортної задачі називати будь-який невід’ємний розв’язок системи обмежень (5.2)—(5.4), який позначають матрицею . Значення невідомих величин — обсяги продукції, що мають бути перевезені від i-х постачальників до j-х споживачів, називатимемо перевезеннями. Оптимальним планом транспортної задачі називають матрицю , яка задовольняє умови задачі, і для якої цільова функція (5.1) набирає найменшого значення. Теорема (умова існування розв’язку транспортної задачі): необхідною і достатньою умовою існування розв’язку транспортної задачі (5.1)—(5.4) є її збалансованість: . Доведення. Необхідність. Нехай задача (5.1)—(5.4) має розв’язок , тоді для нього виконуються рівняння-обмеження (5.2) і (5.3). Підсумуємо відповідно ліві та праві частини систем рівнянь (5.2) і (5.3). Матимемо: , (5.6) (5.7) Оскільки ліві частини рівнянь (5.6) та (5.7) збігаються, то праві також рівні одна одній, отже, виконується умова: . (5.8) Достатність. Потрібно показати, що за заданої умови (5.8) існує хоча б один план задачі, і цільова функція на множині планів обмежена. Нехай = W > 0. Розглянемо величини (). Підставивши значення в систему обмежень задачі (5.1)—(5.4), матимемо: ; . Оскільки умови (5.2) та (5.3) виконуються, то є планом наведеної транспортної задачі. Виберемо з елементів найбільше значення і позначимо його через . Якщо замінити в цільовій функції (5.1) всі коефіцієнти на , то, враховуючи (5.2), матимемо: . Виберемо з елементів найменше значення і позначимо його через . Якщо замінити в цільовій функції (5.1) всі коефіцієнти на , то, враховуючи (5.2), матимемо: . Тобто цільова функція на множині допустимих планів транспортної задачі є обмеженою: . Теорему доведено. Якщо при перевірці збалансованості (5.5) виявилося, що транспортна задача є відкритою, то її необхідно звести до закритого типу. Це здійснюється введенням фіктивного (умовного) постачальника у разі перевищення загального попиту над запасами із ресурсом обсягом . Якщо ж загальні запаси постачальників перевищують попит споживачів , то до закритого типу задача зводиться введенням фіктивного (умовного) споживача з потребою . Вартість перевезення одиниці продукції від фіктивного постачальника (або фіктивного споживача ) до кожного зі споживачів (виробників) має дорівнювати нулю або бути набагато більшою за реальні витрати . Як правило, у такому разі використовують нульові значення вартостей перевезень, що дає змогу спростити обчислення. Як згадувалося вище, транспортна задача (5.1)—(5.4) є звичайною задачею лінійного програмування і може бути розв’язана симплексним методом, однак особливості побудови математичної моделі транспортної задачі дають змогу розв’язати її простіше. Легко помітити, що всі коефіцієнти при змінних у рівняннях (5.2), (5.3) дорівнюють одиниці, а сама система обмежень (5.2), (5.3) задана в канонічній формі. Крім того, система обмежень (5.2), (5.3) складається з mn невідомих та m + n рівнянь, які пов’язані між собою співвідношенням (5.8). Якщо додати відповідно праві та ліві частини систем рівнянь (5.2) та (5.3), то отримаємо два однакових рівняння: ; . Наявність у системі обмежень двох однакових рівнянь свідчить про її лінійну залежність. Якщо одне з цих рівнянь відкинути, то в загальному випадку система обмежень буде містити m + n – 1 лінійно незалежне рівняння, отже, їх можна розв’язати відносно m + n – 1 базисних змінних. Назвемо опорним планом транспортної задачі такий допустимий її план, що містить не більш ніж m + n – 1 додатних компонент, а всі інші його компоненти дорівнюють нулю. Такий план є невиродженим. Якщо ж кількість базисних змінних менша ніж m + n – 1, то маємо вироджений опорний план. 5.2. Властивості опорних планів транспортної задачі Якщо умови транспортної задачі і її опорний план записані у вигляді табл. 5.1, то клітини, в яких (ненульові значення поставок), називаються заповненими, всі інші — пустими. Заповнені клітини відповідають базисним змінним і для невиродженого плану їх кількість дорівнює m + n – 1. Назвемо циклом таку послідовність заповнених клітин таблиці 5.1, яка задовольняє умову, що лише дві сусідні клітини містяться або в одному рядку, або в одному стовпці таблиці, причому перша клітина циклу є і його останньою клітиною. Якщо для певного набору заповнених клітин неможливо побудувати цикл, то така послідовність клітин є ациклічною. Лема. Кількість клітин, які утворюють будь-який цикл транспортної задачі, завжди парна. Доведення. Якщо позначити кожну клітину циклу двома індексами , то довільний цикл, що складається з n клітин, можна записати одним із двох способів: , (5.9) або . (5.10) Оскільки перша та остання клітини циклу є однією клітиною, то виключимо з розгляду останній елемент (i1, j1) наведених послідовностей. Кількість клітин, що залишилась, парна, бо кожній клітині виду в (5.9) та (5.10) відповідає наступна або . Саме такими клітинами закінчуються наведені послідовності. Передостанньою клітиною є клітина виду , де . Отже, цикл утворюється клітинами, які містяться в l рядках та l стовпцях, тобто загальна їх кількість n = 2l. Лему доведено. Теорема 5.1. Щоб деякий план транспортної задачі був опорним, необхідно і достатньо його ациклічності. Доведення. Необхідність. Нехай у таблиці 5.1 міститься опорний план транспортної задачі, тобто не більше ніж m + n – 1 клітин будуть заповненими. Якщо заповнених клітин менше, ніж m + n – 1, то решта базисних клітин знаходиться серед незаповнених. Довести необхідність умови теореми означає довести ациклічність опорного плану. Вектори, що відповідають базисним клітинам, тобто базисним змінним, є лінійно незалежними, і потрібно довести ациклічність набору клітин, що відповідає будь-якій системі лінійно незалежних векторів. Допустимо протилежне. Нехай деяка підсистема з даної системи базисних векторів утворює цикл, а саме: . (5.11) Складемо лінійну комбінацію таких векторів, що дорівнює нулю. Оскільки кожна змінна входить у систему обмежень лише двічі, то базисні вектори матимуть вид:
Лінійною комбінацією базисних векторів буде:
Або . (5.12) Проте рівність (5.12) суперечить умові лінійної незалежності базисних векторів, отже, послідовність (5.11) є ациклічною. Достатність. Нехай деякий план транспортної задачі є ациклічним. Потрібно показати, що він є опорним планом, тобто довести лінійну незалежність векторів, що відповідають ненульовим компонентам плану. Всякий план не може містити від’ємних компонент, а кількість лінійно незалежних між собою векторів у обмеженнях транспортної задачі завжди дорівнює m + n – 1, так що кількість відмінних від нуля компонент плану, якщо він опорний, не перевищує цієї величини. Позначимо множину всіх заповнених клітин через Н, а відповідні вектори — . Доведемо достатність, міркуючи від супротивного. Нехай вектори лінійно залежні. Розглянемо нульову лінійну комбінацію цих векторів: . (5.13) Деякі з коефіцієнтів можуть відрізнятися від нуля. Нехай один з таких коефіцієнтів відповідає індексам , тобто . Тоді відповідний доданок у рівності (5.13) можна перенести в ліву частину рівняння: , (5.14) де . Оскільки і1-ша компонента в лівій частині (5.14) відмінна від нуля, то в правій частині також має бути хоча б один доданок з і-ою компонентою, що відмінна від нуля. Припустимо, що . Відповідний доданок також можна перенести в ліву частину (5.14): , (5.15) де . Оскільки (інакше клітина входила б у суму (5.13) двічі) і компонента лівої частини (5.15) відмінна від нуля, то серед доданків правої частини знайдеться хоча б один, для якого . Перенесемо його також в ліву частину рівняння. Отримаємо: , (5.16) де . Оскільки кількість заповнених клітин, що входять у множину Н, а отже, і кількість векторів скінченна і не перевищує числа , то через N кроків описаний процес перенесень обов’язково закінчиться. Після деякої непарної кількості кроків дістанемо рівність: , (5.17) де . Якщо кількість кроків була парною, матимемо: , (5.18) де . Розглянемо співвідношення (5.17). При деякому значенні серед доданків другої суми лівої частини знайдеться такий, що має індекс . Тоді всі клітини, що були перенесені в ліву частину після -го кроку, утворюють цикл. Аналогічні міркування стосуються також (5.18). Покажемо, що до закінчення процесу, виходячи з рівності (5.17), обов’язково матимемо цикл. Для цього припустимо, що . Тоді, згідно з попередніми міркуваннями, в правій частині (5.17) обов’язково знайдеться доданок з індексами , для якого , бо інакше б рівність (5.17) не справджувалась. Отже, процес перенесення у разі, якщо , буде продовжуватись. Проте, внаслідок згаданої скінченності процесу перенесень (N ? m · n) умова виконання рівностей (5.17) та (5.18) рівносильна тому, що випадок обов’язково матиме місце, що означатиме побудову циклу. Отже, припущення лінійної залежності векторів , що описується рівнянням (5.13), означає, що серед відповідних клітин існує цикл, але це суперечить умові теореми. Значить, достатність згаданої умови, а разом з тим і всю теорему доведено. Отже, базисні клітини опорного плану завжди утворюють ациклічну послідовність клітин. Теорема 5.2. (Наслідок теореми 5.1.) Будь-яка сукупність з клітин матриці транспортної задачі утворює цикл. Доведення. Як зазначалось, сукупність лінійно незалежних векторів задачі не перевищує . Отже, всяка сукупність з векторів буде лінійно залежною. Як випливає з доведення попередньої теореми, відповідні клітини завжди утворюють цикл. Отже, сукупність усіх базисних клітин та однієї вільної клітини таблиці транспортної задачі завжди утворює цикл. Теорема 5.3. Якщо всі запаси і всі потреби є невід’ємними цілими числами, то будь-який опорний план складається із значень, що є цілими числами. Доведення. Компоненти кожної системи із лінійно незалежних (базисних) векторів можуть бути подані у вигляді трикутної матриці. Нехай розглядається задача (5.1)—(5.4). Матриця з перших компонент базисних векторів системи (5.2), (5.3) матиме вигляд: (5.19) m n – 1 Розв’язування системи, що визначається (5.19), включатиме лише дії додавання та віднімання, і, оскільки та у постановці транспортної задачі є цілими числами, то значення змінних також будуть цілими числами. 5.3. Методи побудови опорного плану транспортної задачі Як і в звичайному симплексному методі, розв’язування транспортної задачі полягає в цілеспрямованому переборі та перевірці на оптимальність опорних планів. Початком такого ітераційного процесу є побудова першого опорного плану. Перший опорний план транспортної задачі, як і будь-якої задачі лінійного програмування можна побудувати методом, який було розглянуто в розділі 2, що призведе до необхідності надто складних розрахунків. Завдяки вищезгаданим особливостям будови математичної моделі транспортної задачі існують кілька простих методів побудови опорного плану. Розглянемо методи північно-західного кута, мінімальної вартості, подвійної переваги та метод апроксимації Фогеля. Побудову опорного плану зручно подавати у вигляді таблиці, в якій постачальники продукції відповідають рядкам, а споживачі — стовпчикам. Нехай умови конкретної транспортної задачі подані в табл. 5.2. Ідея методу північно-західного кута полягає в тому, що заповнення таблиці починають, не враховуючи вартостей перевезень, з лівого верхнього (північно-західного) кута. У клітину записують менше з двох чисел а1 та b1. Далі переходять до наступної клітини в цьому ж рядку або у стовпчику і заповнюють її, і т. д. Закінчують заповнення таблиці у правій нижній клітинці. У такий спосіб значення поставок будуть розташовані по діагоналі таблиці. Розглянемо цей процес детальніше на прикладі. Спочатку, не враховуючи вартості перевезень, завжди задовольняють потреби першого споживача В1, використовуючи запаси першого постачальника А1. У нашому прикладі (табл. 5.2) потреби споживача В1 становлять = 110, а запаси постачальника — = 150 одиниць (тобто із запасів першого постачальника можна повністю задовольнити потреби першого споживача), тому в клітинку А1В1 записуємо менше із значень , , тобто 110. Тепер потреби першого споживача повністю задоволені, і переходимо до задоволення потреб наступного (другого) споживача В2. Обсяг його потреб = 50. Після задоволення потреб першого споживача залишок запасів першого постачальника становить 150 –– 110 = 40. Отже, від першого виробника другому споживачеві можна перевезти лише 40 одиниць продукції, тому в клітину А1В2 записуємо число 40. Після цього, оскільки запаси першого постачальника повністю вичерпані, переходимо до використання запасів наступного постачальника А2. Його запаси = 60, а незадоволені потреби другого споживача 50 – 40 = 10, тому в клітинку А2В2 записуємо число 10, і другий споживач у такий спосіб також повністю отримав необхідну кількість продукції. Переходимо до задоволення потреб наступного споживача В3. У результаті часткового використання запасів другого постачальника його залишок продукції становить 60 – 10 = 50. Отже, від другого виробника до третього споживача можна перевезти 50 одиниць продукції. Клітинка А2В3 міститиме зазначене число 50, і цим запаси постачальника А2 будуть повністю вичерпані. Переходимо до розподілу запасів останнього (третього) постачальника А3. Залишились незадоволеними потреби третього споживача в обсязі 60 –50 = 10. Для їх задоволення скористаємося запасами постачальника А3. У клітинку А3В3 записуємо число 10, і потреби споживача В3 також повністю задоволені. Переходимо до останнього споживача В4 з потребами b4 = 80, які повністю задовольняються за рахунок залишку запасів третього постачальника: 90 – 10 = 80. Таблиця 5.2 Постачальники Запаси Споживачі
B1 B2 B3 B4
Потреби
b1 = 110 b2 = 50 b3 = 60 b4 = 80
А1 а1 = 150 4 110 4 40 2 5
А2 а2 = 60 5 3 10 1 50 2
А3 а3 = 90 2 1 4 10 2 80
Отже, в таблиці 5.2 у заповнених клітинках знаходяться числа, що означають можливий план перевезень продукції. Сума чисел (перевезень) по рядках дорівнює обсягам запасів постачальників, а сума чисел по стовпцях — обсягам потреб відповідних споживачів. Аналогічний результат можна отримати, якщо почати з правого нижнього кута таблиці, рухаючись до лівого верхнього. Процедуру методу можна застосовувати також, починаючи розподіл поставок з лівого нижнього кута і рухаючись до правого верхнього по діагоналі. В такому разі спосіб розподілу перевезень можна було б назвати методом південно-західного кута, тому цей метод ще називають діагональним. Метод північно-західного кута є найпростішим, однак і найменш ефективним. Процес відшукання оптимального плану після початкового опорного, визначеного методом північно-західного кута, пов’язаний зі значним обсягом обчислювальних робіт, тому його реалізують на ЕОМ. Визначимо загальну вартість перевезень згідно з початковим опорним планом. Від першого постачальника до першого споживача необхідно перевезти 110 одиниць продукції за ціною 4 ум. од. (ціна записана в правому верхньому куті кожної клітини), отже, це коштуватиме ум. од. Крім того, необхідно перевезти від першого постачальника 40 одиниць продукції до другого споживача за ціною 4 ум. од. і т. д. У такий спосіб визначимо загальну вартість усіх перевезень: (ум. од.). Теорема 5.4. Опорний план транспортної задачі, знайдений методом північно-західного кута, завжди ациклічний. Доведення. Скористаємося методом індукції числа . Для теорема очевидна: план ациклічний, оскільки складається з елемента. Так само ациклічним є план для , оскільки він складається лише з двох клітин. Нехай теорема справедлива для деякого довільного . Доведемо її справедливість для числа . Допустимо для визначеності, що в транспортній задачі (5.1)—(5.4) , тобто після першого кроку за методом північно-західного кута отримаємо , всі інші . Дальші кроки методу пов’язані із його застосуванням до таблиці розмірністю , де , а , причому всі запаси і потреби нової таблиці збігаються з запасами і потребами попередньої, крім . За припущенням індукції план, знайдений методом північно-західного кута для , тобто в новій таблиці, ациклічний. Очевидно, що приєднання до цього плану першого рядка з єдиним ненульовим елементом не утворить циклу, але відшуканий у такий спосіб план буде планом початкової задачі для , чим і доводиться теорема. Наведені властивості опорних планів стосуються і тих планів, що отримані розглянутими нижче іншими способами, які певною мірою є модифікаціями методу північно-західного кута. Очевидно, якщо за побудови опорного плану враховувати вартості перевезень, то сумарна вартість всіх постачань може бути зменшена, і отриманий опорний план буде ближчим до оптимального. Ідея методу мінімальної вартості полягає в тому, що на кожному кроці заповнюють клітинку таблиці, яка має найменшу вартість перевезення одиниці продукції. Такі дії повторюють доти, доки не буде розподілено всю продукцію між постачальниками та споживачами. Складемо за допомогою цього методу план розглянутої задачі (табл. 5.3). Найменшу вартість мають перевезення, які здійснюються від А2 до В3 та від А3 до В2 (ціна перевезення одиниці продукції — 1 ум. од.). Заповнимо будь-яку з них, наприклад, А2В3. Оскільки постачальник має 60 одиниць продукції, а споживач потребує саме такої її кількості, то в клітину А2В3 ставимо значення 60. У такий спосіб запаси другого постачальника повністю вичерпані, а потреби третього споживача повністю задоволені. Також мінімальною є вартість перевезень від третього постачальника до другого споживача, тому заповнимо також клітину А3В2. З клітинок таблиці, що залишились незаповненими, вибираємо наступне мінімальне значення вартості перевезень, яке дорівнює 2 ум. од. — для клітин А1В3, А2В4, А3В1 та А3В4. Заповнення клітин А2В4 та А1В3 неможливе, оскільки постачальник А2 вже повністю вичерпав власний обсяг запасів, задовольняючи потреби споживача В3, а споживач В3 повністю задовольнив свої потреби. Отже, можна заповнити тільки клітину А3В1 чи А3В4. Заповнимо А3В1. Обсяг запасів а3 = 90, причому 50 одиниць продукції вже надано другому споживачеві. Отже, маємо залишок 90 – 50 = 40, а потреби b1 = 110, тому від третього постачальника до першого споживача плануємо перевезти 40 одиниць продукції. Тепер у клітину А3В4 не можна записати будь-який обсяг постачання, оскільки запаси третього постачальника вже повністю вичерпані. Знову вибираємо найменшу вартість для клітин таблиці, що залишилися пустими, і продовжуємо процес доти, поки всі запаси не будуть розподілені, а потреби — задоволені. Таблиця 5.3 bj ai b1 = 110 b2 = 50 b3 = 60 b4 = 80
а1 = 150 4 70 4 2 5 80
а2 = 60 5 3 1 60 2
а3 = 90 2 40 1 50 4 2
В результаті таких міркувань отримали початковий опорний план, загальна вартість перевезень для якого становить: (ум. од.). Значення цільової функції менше за попередній варіант, значить цей план ближчий до оптимального. Метод подвійної переваги. Якщо розмірність задачі досить велика, то перебір за методом мінімальної вартості ускладнюється. В такому разі спростити пошук клітин з найменшими вартостями можна, застосовуючи метод подвійної переваги. Згідно з процедурою цього методу перед початком заповнення таблиці необхідно позначити будь-якими символами клітинки, які містять найменшу вартість у рядках, а потім — у стовпчиках. Таблицю починають заповнювати з клітинок, позначених двічі (які містять вартості, що є мінімальними і в рядку, і в стовпчику). Далі заповнюють клітинки, позначені один раз (що містять мінімальні вартості або в рядку, або в стовпчику), а вже потім — за методом мінімальної вартості. Таблиця 5.4 bj ai b1 = 110 b2 = 50 b3 = 60 b4 = 80
а1 = 150 4 110 4 V 2 5 40
а2 = 60 5 3 VV 1 60 V 2
а3 = 90 V 2 VV 1 50 4 V 2 40
(ум. од.). Застосування для побудови опорного плану даного методу уможливлює отримання найменшого у зіставленні з розглянутими вище значення цільової функції. Отже, такий план є найближчим до оптимального. Метод апроксимації Фогеля. За цим методом на кожному кроці визначають різницю між двома найменшими вартостями в кожному рядку і стовпчику транспортної таблиці. Ці різниці записують у спеціально відведених місцях таблиці — знизу та справа у кілька рядків та стовпчиків, що відповідають крокам заповнення таблиці. З-поміж усіх різниць вибирають найбільшу і у відповідному рядку чи стовпчику заповнюють клітинку з найменшою вартістю. Якщо ж однакових найбільших різниць кілька, то вибирають будь-який відповідний рядок або стовпчик. Коли залишається незаповненим лише один рядок або стовпчик, то обчислення різниць припиняють, а таблицю продовжують заповнювати за методом мінімальної вартості. Даний метод побудови опорного плану враховує не лише маршрути з мінімальними витратами перевезень продукції, але й співвідношення витрат у рядку чи стовпчику, тобто розраховується наскільки, може збільшитися вартість постачання на наступних кроках процедури, якщо не здійснити на поточному кроці постачання в клітину з мінімальною вартістю. Метод апроксимації Фогеля дає змогу особливо для задач великих розмірностей скласти найкращий опорний план. Таблиця 5.5 bj ai b1 = 110 b2 = 50 b3 = 60 b4 = 80 Різниці по рядках
а1 = 150 4 110 4 40 2 5 2 2 0
а2 = 60 5 3 1 60 2 1 2
а3 = 90 2 1 10 4 2 80 1 1 1
Різниці по стовпцях 2 2 1 3
2 2 1
2 3
У таблиці 5.5. навпроти кожного рядка і стовпчика записані величини, які знайдені як різниці між мінімальним значенням вартості та наступним за ним по рівню. Максимальне значення такої різниці на першому кроці відповідає четвертому стовпчику і означає, що у разі, коли не буде задоволена потреба четвертого споживача перевезенням продукції від третього постачальника за ціною 2 ум. од. за одиницю, то на наступних кроках вартість перевезення може бути на 3 ум. од. більшою. Тобто інакше може статися, що потребу четвертого споживача необхідно буде задовольняти перевезенням продукції від першого постачальника, що призведе до збільшення вартості цього перевезення в 2,5 рази. Водночас для всіх інших споживачів та постачальників такі різниці є меншими. Отже, найдоцільніше на першому кроці заповнити клітину А3В4. Після цього потреби В4 повністю задоволені, і всі клітини четвертого стовпчика виключаються з наступного розрахунку різниць по рядках і стовпцях. На другому кроці максимальна різниця дорівнює 2 і відповідає першому і другому рядкам та першому і другому стовпчикам, тому можна заповнювати будь-яку їх клітину з мінімальною вартістю, наприклад, А2В3. Після цього з розгляду виключаються одразу всі клітини другого рядка та третього стовпця, оскільки потреби третього споживача повністю задоволені, а запаси другого постачальника вичерпані. Останній розрахунок різниць (найбільше значення 3 відповідає другому стовпчику) свідчить про доцільність введення поставки від третього постачальника до другого споживача. Решту клітин заповнимо методом мінімальної вартості та визначимо загальну вартість перевезень: (ум. од.). Результат збігся із значенням цільової функції для опорного плану, що складений за попереднім методом. Ефективність методу апроксимації Фогеля, як вже згадувалось, є очевидною для задач більшої розмірності. Зазначимо, що ефективність наведених методів можна оцінювати лише в середньому, оскільки можлива ситуація, що методом мінімальної вартості отримано опорний план транспортної задачі кращий, ніж методом подвійної переваги. 5.4. Випадок виродження опорного плану транспортної задачі Опорний план транспортної задачі, як зазначалося раніше, має містити не більше ніж (m + n – 1) відмінних від нуля компонент. Якщо їх кількість дорівнює (m + n – 1), то такий опорний план називають невиродженим. Якщо ж кількість додатних компонент менша ніж (m + n – 1), то опорний план є виродженим. Вироджений план може виникати не лише за побудови опорного плану, але і при його перетвореннях у процесі знаходження оптимального плану. Найчастіше, щоб позбутися виродженості опорного плану, в деякі клітини таблиці транспортної задачі в необхідній кількості вводять нульові постачання. Обсяги запасів постачальників і потреби споживачів після цього не змінюються, однак клітини зі значенням «нуль» вважаються заповненими. Головною умовою при введенні нульової поставки є збереження необхідної і достатньої умови опорності плану транспортної задачі — його ациклічності. Клітина має вибиратись у такий спосіб, щоб неможливо було побудувати замкнений цикл. Нехай маємо такі умови транспортної задачі та початковий опорний план, що подані в табл. 5.6. Таблиця 5.6 bj ai b1 = 7 b2 = 10 b3 = 6
а1 = 8 0 7 5 1 2
а2 = 7 2 3 7 4
а3 = 6 1 2 0 6
а4 = 2 0 0 2 0
Перевіримо, чи є отриманий опорний план виродженим. Кількість постачальників , а кількість споживачів . Для невиродженого опорного плану кількість заповнених клітин таблиці 5.6 має дорівнювати . У наведеному опорному плані кількість заповнених клітин на одну менше (п’ять), отже, він вироджений. Позбудемося виродженості опорного плану введенням нульової поставки в одну з пустих клітин. Враховуючи необхідність збереження ациклічності опорного плану, не можна заповнювати клітини А2В1 та А4В1, оскільки це призведе до утворення циклів, які зображені в табл. 5.7. та 5.8. Таблиця 5.7 bj ai b1 = 7 b2 = 10 b3 = 6
а1 = 8 0 7 5 1 2
а2 = 7 2 0 3 7 4
а3 = 6 1 2 0 6
а4 = 2 0 0 2 0
Таблиця 5.8 bj ai b1 = 7 b2 = 10 b3 = 6
а1 = 8 0 7 5 1 2
а2 = 7 2 3 7 4
а3 = 6 1 2 0 6
а4 = 2 0 0 0 2 0
Очевидно введення нульової поставки в будь-яку іншу пусту клітинку не дає змоги утворити цикл. Отже, можна заповнити нулем одну з клітин А1В3, А2В3, А3В1, А3В2, А4В3. Наприклад, виберемо клітину А3В2. Таблиця 5.9 bj ai b1 = 7 b2 = 10 b3 = 6
а1 = 8 0 7 5 1 2
а2 = 7 2 3 7 4
а3 = 6 1 2 0 0 6
а4 = 2 0 0 2 0
Зазначимо, що необхідність введення нульової поставки є очевиднішою на наступних етапах розв’язування транспортної задачі. 5.5. Методи розв’язування транспортної задачі 5.5.1. Задача, двоїста до транспортної Один із способів розв’язування транспортної задачі ґрунтується на розгляді двоїстої задачі. Розглянемо транспортну задачу (5.1)—(5.4).
