З якої умови починають розв’язок транспортної задачі?

Теорема (умова існування розв’язку транспортної задачі): необхідною і достатньою умовою існування розв’язку транспортної задачі є її збалансованість: .

У розглянутій задачі має виконуватися умова:

. (5.5)

Транспортну задачу називають збалансованою, або закритою, якщо виконується умова (5.5). Якщо ж така умова не виконується, то транспортну задачу називають незбалансованою, або відкритою. Якщо , тоді потрібно ввести додаткового (фіктивного) споживача (або постачальника) з потребою, рівною різниці a_i та b_j. Собівартість перевезень для цього споживача (постачальника) мають бути нульовими, що означає перевезення можливі тільки умовно.

28.Умова якою перевіряють на оптимальність базові плани транс. задачі.

Оптимальним планом транспортної задачі називають матрицю , яка задовольняє умови задачі, і для якої цільова функція набирає найменшого значення.

Перевірка на оптимальність базисних планів здійснюється за умовою для всіх кліток, де u_i і v_j – потенціали, які знаходять за такими привалами. Вводять термінологію: клітка з вантажем – базисна клітка, клітка без вантажу – вільна клітка. Для базисних кліток с_ij = u_i + v_j, звідки надаючи одному з потенціалів довільного значення (наприклад 0), знаходять інші потенціали для всіх споживачів і постачальників (тобто стовпців і рядків). Значення суми потенціалів для кожної клітки проставляють у нижньому кутку клітки.

29. Умова за якою визначають потенціали для базисних планів транспортної задачі.

Оптимізація плану виконується за умови .

u_i та v_j – деякі величини які називаються потенціалами. Їх знаходять з рівняння для всіх заповнених баз кліток. u_{i +} v_{j =} c_ij.

Метод диференціальних рент.

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

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

Після деякого числа описаних вище ітерацій нерозподілений залишок стає рівним нулю. В результаті отримують оптимальний план даної ТЗ.

Описаний вище метод розв'язання ТЗ має більш просту логічну схему розрахунків, чим розглянутий вище метод потенціалів. Тому в більшості випадків для знаходження розв'язку конкретних ТЗ з використанням ЄВМ використовують метод диференціальних рент.

 

31.Суть методу потенціалів.

Метод потенціалів дозволяє, виходячи з деякого опорного плану перевезень, побудувати за скінчене число ітерацій рішення транспортної задачі шляхом послідовного переходу від опорного плану до оптимального.

Загальна схема методу така. У даному початковому опорному плані кожному пункту ставлять у відповідність деяке число, яке називається його попереднім потенціалом. Попередні потенціали обирають так, щоб їх різниця для будь-якої пари пунктів Аi и Вj, пов’язаних основною комунікацією, дорівнювала с_ij. Якщо відбудеться так, що різниця попередніх потенціалів для всіх інших комунікацій не перевищує с_ij, то даний план перевезень – оптимальне рішення задачі. У противному випадку вказують спосіб покращення опорного плану транспортної задачі.