17. Характеристика методу розв'язання тз і його порівняння із см. Методи складання початкового опорного плану. Умова, при якій план перевезень буде опорним.

ТЗ є ЗЛП, отже, її можна розв’язати симплексним методом. Однак навіть у випадку 3 постачальників і 4 споживачів розмірність задачі досить велика: число змінних mn=3*4=12, а розмірність векторного простору задачі m+n-1=3+4-1=6, отже, симплексна таблиця буде містити 12 шестивимірних векторів і задача виявиться дуже громіздкою. Існує специфічний метод розв’язування ТЗ, що ґрунтується на використанні так званої таблиці планування перевезень. Як і симплекс-метод, він є методом послідовного поліпшення планів, тобто є процедурою напрямленого перебору, та складається з 3 етапів: 1)складання початкового опорного плану; 2) оцінки оптимальності планів; 3) переходу від одного опорного плану до кращого.

Існує кілька методів побудови поч. опорного плану.

Приклад.

a1=50 b1=30 (3 8 10 5)

a2=150 b2=70 C=(1 4 6 2)

a3=100 b3=90 (3 1 9 7)

b4=110

Ця ТЗ є закритою.

1) Метод північно-західного кута.

Складаємо план, спочатку заповнивши клітину А1В1, що міститься в північно-західному куті таблиці. Потужність А1 становить 50, а В1 вимагає 30 од., отже, в цю клітину заплануємо перевезення min (30,50)=30 од. Решту (20 од.) запишемо в клітину А1В2. Потужність другого постачальника 150 од. Попит В1 задовольнили, а другий споживач потребує 70-20=50 од. Запишемо це число в клітину А2В2 і т.д. Визначимо транспортні витрати, що відповідають такому плану:

Z1=3*30+8*20+4*50+6*90+2*10+7*100=1710

Недолік цього методу – не враховано тарифи перевезень.

2) Метод мінімального елемента в рядку.

У першому рядку вибираємо маршрут із мінімальним тарифом А1В1. За цим маршрутом можна відправити 30 од. вантажу. Остачу 20 од. відправимо за маршрутом А1В4, оскільки тут тариф найменший серед тих, що залишилися. Аналогічно розподіл-ся вантаж від решти постачальників. Вартість перевезень:

Z2=3*30+5*20+4*60+2*90+1*10+9*90=1430.

3) Метод мінімального елемента.

Знаходимо маршрут, якому відповідає мін. Тариф. У цьому разі таких маршрутів 2: А2В1 і А3В2. За маршрутом А2В1 можна відправити 30 од., а за А3В2 – 70 од. Попит В1 і В2 задовольнили, лишились В3 і В4. Вибираємо мін. тарифи серед маршрутів перевезень до цих споживачів і розподіляємо вантажі, враховуючи раніше виконані поставки. Сумарні затрати за цим планом:

Z3=10*50+1*30+6*10+2*110+1*70+9*30=1150.Отриманий план – найкращий з усіх 3 побудованих.

Умова, при якій план перевезень буде опорним: число заповнених клітин опорного плану не може перевищ. m+n-1. Ознакою опорності плану ТЗ є його ациклічність, тобто неможливість побудови циклу.

18. Метод потенціалів. Ознака оптимальності опорного плану. Алгоритм знаходження системи потенціалів для виродженого і невиродженого опорних планів.

Існує кілька методів оцінки оптимальності планів. Один з найефективніших – метод потенціалів. Нехай для деякої ТЗ задано набір чисел Ui (i=1,m) і Vj (j=1,n). Числа Ui і Vj наз-ся потенціалами постачальників (рядків) і споживачів (стовпців). Сума Ui+Vj=C^*ij – умовна вартість перевезень.

Теорема (ознака оптимальності опорного плану ТЗ). Якщо для деякого опорного плану Х* = (xij*) існують числа Ui та Vj, для яких виконується умова Ui + Vj = Cij, Xij > 0,

Ui + Vj <= Cij, Xij = 0 для всіх i=1,m та j=1,n, то він є оптимальним планом транспортної задачі.

Алгоритм знаходження системи потенціалів для виродженого і невиродженого опорних планів:

Попередній етап – перевірка балансу загальної пропозиції та загального попиту:

ТЗ закрита. Перший етап – складання першої транспортної таблиці та побудова початкового опорного невиродженого плану: Розмірність ТЗ m+n-1, тому повинно бути стільки ж ненульових поставок. Зауваження: якщо їх менше, то вводиться додаткова необхідна кількість 0-поставок, не порушуючи опорність. Для опорності плануються максимально можливі поставки. Х0 – початковий опорний невироджений план, який забезпечує загальну вартість перевезень Z(X0).

Другий етап – оцінка оптимальності, яка здійснюється аналізом перевищень (вони відіграють роль оцінок). Перевищення (оцінки): Δij=Ui+Vj-Cij. План неоптимальний, якщо є погані (додатні) перевищення. Якщо план неоптимальний, то здійсн-ся перерозподіл – перехід до наступного опорного невиродженого плану за циклом перерозподілу поставок. Перехід від одного опорного плану до іншого виконують заповненням клітинки, для якої порушено умову оптимальності. Якщо таких клітинок кілька, то для заповнення вибирають таку, що має найбільше порушення, тобто max { Δij=Ui+Vj-Cij}. Для вибраної порожньої клітинки будують цикл перерахування та виконують перерозподіл продукції в межах цього циклу за такими правилами:

1) кожній вершині циклу приписують певний знак, причому вільній клітинці — знак «+», а всім іншим по черзі — знаки «–» та «+»;

2) у порожню клітинку переносять менше з чисел xij, що стоять у клітинках зі знаком «–». Одночасно це число додають до відповідних чисел, які розміщуються в клітинках зі знаком «+».

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

Новий опорний план перевіряють на оптимальність за ознакою оптимальності опорного плану.

У разі якщо кількість заповнених клітин більша за m+n-1, то план є виродженим і його необхідно зробити не виродженим, додавши при цьому 0-постачальника.