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