Якщо при визна-поділ оптимального плану транспортної задачі методом по-потенціалів спочатку знаходився який-небудь її опорний план, а потім він послідовно поліпшувався, то при знаходженні реше-ня транспортної задачі методом диференціальних рент спочатку найкращим чином розподіляють між пунктами призначають-чення частина вантажу (так зване умовно оптимальне рас-пределеніе) і на наступних ітераціях поступово зменшують загальну величину нерозподілених поставок. Початковий варіант розподілу вантажу визначають наступним чином. У кожному зі стовпців таблиці даних транспортної задачі знаходять мінімальний тариф. Знайдені числа укладають в гуртки, а клітини, в яких стоять зазначені числа, заповнююч-ють. У них записують максимально можливі числа. У резуль-таті отримують деякий розподіл поставок вантажу в пункти призначення. Цей розподіл в загальному випадку не задовольнив ряется обмеженням вихідної транспортної задачі. Тому в ре-док наступних кроків слід поступово скорочувати нерозподілені поставки вантажу так, щоб при цьому загальна вартість перевезень залишалася мінімальною. Для цього спочатку визначають надлишкові і недостатні рядки.
Рядки, відповідні постачальникам, запаси яких повністю розподілені, а потреби пунктів призначення, пов'язаних з даними споживачами запланованими постав-ками, не задоволені, вважаються недостатніми. Ці рядки іноді називають також негативними. Рядки, запаси кото-яких вичерпані не повністю, вважаються надмірними. Іноді їх називають також позитивними.
Після того як визначені надлишкові і недостатні рядки, для кожного з стовпців знаходять різниці між числом в гуртку і найближчим до нього тарифом, записаним в надмірний-ної рядку. Якщо число в гуртку знаходиться в позитивній рядку, то різниця не визначають. Серед отриманих чисел знаходять найменше. Це число називається проміжною рен-тій. Після визначення проміжної ренти переходять до нової таблиці. Ця таблиця виходить з попередньої таблиці при-додану до відповідних тарифів, що стоять в отрицатель-них рядках, проміжної ренти. Інші елементи залишаються-ся колишніми. При цьому всі клітини нової таблиці вважають вільними. Після побудови нової таблиці починають запол-ня її клітин. Тепер вже число заповнюваних клітин на одну більше, ніж на попередньому етапі. Ця додаткова клітина знаходиться в стовпці, в якому була записана проміжна рента. Всі інші клітини знаходяться по одній в кожному зі стовпців і в них записані найменші для даного стовпця числа, укладені в гуртки. Укладено в гуртки і два одина-кових числа, що стоять в стовпці, в якому в попередній таб-особі була записана проміжна рента.
Оскільки в новій таблиці число заповнюваних клітин біль-ше, ніж число стовпців, то при заповненні клітин слід поль-тися спеціальним правилом, яке полягає в наступному. Вибирають деякий стовпець (рядок), в якому є одна клітина з поміщеним в ній кружком. Цю клітку заповнюють і виключають з розгляду даний стовпець (рядок). Після цього беруть деяку рядок (стовпець), в якій є одна клітина з поміщеним в ній кружком. Цю клітку заповнюють і виключають з розгляду цього рядка (стовпець). Продол-жая так, після кінцевого числа кроків заповнюють всі клітини, в яких поміщені гуртки з ув'язненими в них числами. Якщо до того ж вдається розподілити весь вантаж, наявний в пунктах відправлення, між пунктами призначення, то отримують оптимальний план транспортної задачі. Якщо ж оптимальний план не отримано, то переходять до нової таблиці. Для цього знахо-дять надлишкові і недостатні рядки, проміжну ренту і на основі цього будують нову таблицю. При цьому можуть виник-нути деякі труднощі при визначенні знака рядки, коли її нерозподілений залишок дорівнює нулю. В цьому випадку рядок вважають позитивною за умови, що друга заповнена клітина, що стоїть в стовпці, пов'язаному з даною рядком ще однієї заповненої кліткою, розташована в позитивній рядку.
Після кінцевого числа описаних вище ітерацій нераспред-ний залишок стає рівним нулю. В результаті получа-ють оптимальний план даної транспортної задачі.
Описаний вище метод вирішення транспортної задачі має більш просту логічну схему розрахунків, ніж розглянутий вище метод потенціалів. Тому в більшості випадків для знаходження вирішення конкретних транспортних задач з викорис-танням ЕОМ застосовується метод диференціальних рент.
5.6 Визначення оптимального плану транспортних задач, що мають деякі усложеніе в їх постановці.
При знаходженні вирішення низки конкретних транспортних задач часто буває не-обходимо враховувати додаткові обмеження, які не зустрічалися вище при розгляді простих варіантів даних завдань. Зупинимося докладніше на деяких можливих усклад-неніях в постановках транспортних завдань.
1. При деяких реальних умовах перевезення вантажу з визна-діленого пункту відправлення, в пункт призначення, не можуть бути здійснені. Для визначення оптимальних планів таких задач припускають, що тариф перевезення одиниці вантажу з пункту в пункт, є як завгодно великий вели-чиною М, і при цьому умови відомими методами знаходять реше-ня нової транспортної задачі. При такому припущенні виключається можливість при оптимальному плані транспортної задачі перевозити вантаж з пункту в пункт. Такий підхід до знаходження рішення транспортної задачі називають заборонено-ням перевезень або блокуванням відповідної клітини таб-лиці даних завдання.
2. В окремих транспортних задачах додатковим усло-Вієм є забезпечення перевезення по відповідним мар-шруті певної кількості вантажу. Нехай, наприклад, з пункту відправлення. в пункт призначення потрібно орга-тельно перевести одиниць вантажу. Тоді в клітку таблиці дан-них транспортної задачі, що знаходиться на перетині рядка і стовпця записують вказане число і надалі цю клітку вважають вільної зі як завгодно великим тарифом перевезень М. Для отриманої таким чином нової транспортної задачі знаходять оптимальний план, який визначає опти -мальний план вихідної задачі.
3. Іноді потрібно знайти рішення транспортної задачі, при якому з пункту відправлення в пункт призначення повинно бути завезено не менше заданої кількості вантажу. Для визна-ділення оптимального плану такого завдання вважають, що запаси пункту і потреби пункту менше фактичних на одиниць. Після цього знаходять оптимальний план нової транспорт-ної задачі, на підставі якого і визначають рішення результат-ної задачі.
4. У деяких транспортних задачах потрібно знайти опти-мальний план перевезень за умови, що з пункту отправле-ня в пункт призначення перевозиться не більше ніж одиниць вантажу, т. Е.
Сформульовану задачу можна вирішити так. У таблиці результат-них даних завдання для кожного -го обмеження (1) перед-глядають додатковий стовпець, т. Е. Вводять додатковий пункт призначення. Цей стовпчик записують ті ж тари-фи, що і в стовпці. за винятком тарифу, що знаходиться в -му рядку. У додатковому стовпці в цьому рядку тариф вва-ють рівним деякому як завгодно великому числу. При цьому потреби пункту вважають рівними "а потреби знову введеного пункту призначення вважають рівними. Рішення отриманої транспортної задачі може бути знайдено методом потенціалів, і тим самим буде визначено оптимальний план або встановлена нерозв'язність вихідної задачі. Заме-тім, що вихідна транспортна завдання можна вирішити лише в тому випадку, коли для неї існує хоча б один опорний план.
Наведену вище завдання можна вирішити і таким способом. З урахуванням обмеження (1) за правилом мінімального елемента будують опорний план. При цьому якщо величина записується на даному етапі в відповідну клітку числа визначається тільки обмеженням (1), то в подальшому з розгляду виключають тільки заповнену клітину. В інших случаяхіз розгляду виключають або рядок, або стовпець (що-небудь одне).
Якщо в результаті складання плану поставок всі наявні запаси пунктів відправлення розподілені і потреби в пунк-тах призначення задоволені, то отриманий опорний план транс-кравець завдання.
Якщо в якийсь рядку (а отже, і в стовпці) остал-ся нерозподілений залишок, що дорівнює, то вводять додатковий пункт призначення і додатковий пункт відправлення до потреб і запасами, рівними. У клітці, що знаходиться на перетині стовпця додаткового пункту призначення і рядки додаткового пункту відправлення, тариф вважають рівним нулю. У всіх інших клітинах даної будів-ки і шпальти тарифи вважають рівними деякому як завгодно великому числу М. Отриману в результаті цього транс-кравець завдання вирішують методом потенціалів. Після кінцевого числа кроків або встановлюють, що вихідна задача не має опорного плану, або знаходять її оптимальний план. При цьому - оптимальний план вихідної задачі, якщо