, що запаси постачальників вивозяться повністю.
Суми перевезень, стоять в кожному стовпці матриці Ч, повинні бути рівні запитам відповідних споживачів:
В
Це означає, що запити споживачів задовольняються повністю.
Необхідно також враховувати, що перевезення не можуть бути негативними:
i = 1,2, ..., m; j = 1,1, ..., n.
Відповідь: математична модель задачі формулюється так: знайти змінні задачі, що забезпечують мінімум функції
В
і задовольняють системі обмежень
В
та умовам неотрицательности
i = 1,2, ..., m j = 1,2, ..., n.
1.2 АЛГОРИТМ РІШЕННЯ ТРАНСПОРТНОЇ ЗАВДАННЯ
1.2.1 ЗБАЛАНСОВАНІСТЬ ТРАНСПОРТНОЇ ЗАВДАННЯ
Транспортна задача є збалансованою, якщо сумарні запаси постачальників рівні сумарним запитам споживачів, тобто
.
Якщо транспортна завдання не збалансована, то виникають особливості у її вирішенні.
Особливості вирішення транспортних завдань з неправильним балансом:
1.Якщо сумарні запаси постачальників перевершують сумарні запити споживачів, тобто
В
то необхідно ввести фіктивного (n +1)-го споживача з запитами рівними різниці сумарних запасів постачальників і запитів споживачів, і нульовими вартостями перевезень одиниць вантажу
2. Якщо сумарні запити споживачів перевершують сумарні запаси постачальників, тобто
В
то необхідно ввести фіктивного (m +1)-го постачальника із запасами рівні різниці сумарних запитів споживачів і запасів постачальників, і нульовими вартостями перевезень одиниць вантажу
3. При складанні початкового опорного рішення в останню чергу слід розподіляти запаси фіктивного постачальника і задовольняти запити фіктивного споживача, незважаючи на те, що їм відповідає найменша вартість перевезень, рівна нулю.
1.2.2 Опорна РІШЕННЯ ТРАНСПОРТНОЇ ЗАВДАННЯ
Опорним рішенням транспортної задачі називається будь допустиме рішення, для якого вектори умов, відповідні позитивним координатами, лінійно незалежні.
З огляду на те, що ранг системи векторів умов транспортної задачі дорівнює N = m + n-1, опорне рішення не може мати відмінних від нуля координат більше, ніж N.
Для перевірки лінійної незалежності векторів умов, відповідних координатах допустимого рішення, використовують цикли.
Циклом називається така послідовність клітин таблиці транспортної задачі в якій дві і тільки сусідні клітини розташовані в одному рядку або стовпці, причому перша і остання також знаходяться в одному рядку або стовпці.
Система векторів умов транспортної задачі лінійно незалежна тоді і тільки тоді, коли з відповідних їм клітин таблиці не можна утворити жодного циклу. Отже, допустиме рішення транспортної задачі, i = 1,2, ..., m; j = 1,2, ..., n є опорним тільки в тому випадку, коли з зайнятих ним клітин таблиці не можна утворити жодного циклу.
Метод викреслювання. Для перевірки можливості утворення циклу використову...
