Метод потенціалів

Для того щоб початковий план був оптимальним, необхідно виконати такі умови:

а) для кожної зайнятої комірки сума потенціалів повинна дорівнюватися ціні одиниці перевезення, розміщеної в цієї комірці,

;

б) для кожної незайнятої комірки сума потенціалів повинна бути меншою або рівною вартості одиниці перевезення, розміщеної в цій комірці,

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

Таким чином, для перевірки плану на оптимальність необхідно спочатку побудувати схему потенціалів. Розглянемо алгоритм методу потенціалів та одночасно продемонструємо його впровадження на опорному плані, отриманому в (таблиці 6.3). Для цього в таблиці додаємо рядок і стовпець, в яких записується значення потенціалів.

1. Побудова системи потенціалів. Для побудови системи потенціалів використовуємо умову , де C_ij – вартість перевезення одиниці вантажу зайнятої комірки в і-му рядку та j-му стовпці.

Систему потенціалів можна побудувати лише для невиродженого опорного плану. Такий план містить m + n – 1 зайнятих комірок, тому для нього можна скласти систему із m + n – 1 лінійно незалежних рівнянь виду із m + n невідомими. Рівнянь на одне менше, ніж невідомих, тому система є неозначеною та одному невідомому (звичайно U₁) надається нульове значення. Після цього інші потенціали визначаються однозначно.

Таблиця 6.3

Нехай відомий потенціал U_i, тоді із рівності випливає .

Якщо відомий потенціал V_j, то із цієї рівності маємо . Таким чином, для визначення невідомого потенціалу від величини С_ij зайнятої комірки потрібно відняти невідомий потенціал.

У таблиці 6.2 опорний план вироджений, оскільки не вистачає однієї зайнятої комірки. Тому вибираємо рядок, який містить найбільшу кількість зайнятих комірок (рядок А₄), та припускаємо U₄=0. У рядку А₄ три зайнятих комірки (А₄В₂, А₄В₃ та А₄В₅), що зв’язують потенціал U₄ із потенціалами V₂, V₃, V₅. Визначаємо ці потенціали: С=C₄₂-U₄=8-0=8, V₃=C₄₃-U₄=12-0=12, V₅=C₄₅-U₄=13-0=13. За допомогою потенціалу U₄ визначаємо ще який небудь невідомий потенціал, тому його помічаємо знаком . Зараз по черзі продивляємось стовпці В₂, В₃ та В₅, для котрих потенціали вже визначені. У стовпці В₂ маємо дві зайняті клітинки (А₂В₂ та А₄В₄), які зв’язують потенціал V₂ із потенціалами U₂ та U₄; потенціал U₄ вже визначений, тому переходимо до комірки А₂В₂ і з допомогою С₂₂ визначимо невідомий потенціал U₂=C₂₂-V₂=7-8=-1. Відмітимо потенціал V₂ знаком та перейдемо до стовпця В₃. У цьому стовпці немає зайнятих комірок, що зв’язували б V₃ із невідомими потенціалами рядків. Помічаємо потенціал V₃ знаком і переходимо до стовпця В₅. У ньому одна зайнята комірка (А₃В₅), яка зв’язує V₅ із невідомим потенціалом U₃. Визначаємо його U₃=C₃₂-V₅=2-13=-11. Помічаємо потенціал V₃ знаком , адже невідомі потенціали стовпців використані, переходимо до невідомих потенціалів рядків, котрі ще не помічені знаком , потім проглядаємо відповідні їм рядки. Потенціал U₂ зайнятої комірки А₂В₁ зв’язаний із невідомим потенціалом V₁. Знаходимо цей потенціал: V₁=2-(-1)=3 та помічаємо потенціал U₂ знаком .

У рядку А₂ немає зайнятих комірок, які б зв’язували потенціал U₃ з невідомим потенціалом стовпця; потенціал U₃ помічаємо знаком .

Переходимо до невідомих потенціалів стовпців, що не відмічені знаком (це потенціал V₁). Але в стовпці В₁ немає зайнятих комірок, які б зв’язували б V₁ з невідомим потенціалом рядка, тому потенціал V₁ помічаємо знаком . Будова системи потенціалів перервалася, потенціали U₁ та V₄ залишилися невизначеними. Це трапилось тому, що опорний план вироджений (відсутня одна зайнята клітинка). Для усунення виродженності доповнюють кількість зайнятих комірок до m + n – 1 введенням нульових перевезень. Ці комірки називаються фіктивно зайнятими.

Для того щоб визначити потенціали U₁ та V₄, необхідно зробити фіктивно зайнятою одну з незайнятих комірок або рядок А₁, або стовпець В₄, для яких один із потенціалів визначений. Задача розв’язується на мінімізацію лінійної функції, тому потрібно зробити фіктивно зайняту комірку, в котрій стоїть найменша вартість.

Переглядаючи вартості, що стоять у незайнятих комірках рядка А₁ та стовпця В₄, вибираємо найменшу (min C_ij=2), яка відповідає комірці А₃В₄, до неї записуємо нуль і вважаємо зайнятою. Зараз комірка А₃В₄ зв’язує потенціал V₄ із потенціалом U₃, V₄=C₃₄-U₃=2-(-11)=13. Далі знаходимо U₁=C₁₄-V₄=1-13=12.

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

2. Перевірка виконання умови оптимальності для незайнятих комірок. Переглядаємо рядки та для кожної незайнятої комірки перевіряємо виконання умови , тобто сумуємо потенціали, на перетину котрих стоїть незайнята комірка, суму порівнюємо із вартістю, що зазначена в ній. Якщо для деяких комірок , то план неоптимальний. Тоді для кожної комірки, в якій не виконується умова оптимальності, знаходимо величину різниці (U_i+V_j)-C_ij>0 та записуємо її значення в лівій нижній кут цієї ж комірки.

У (таблиці 6.2) для незайнятих комірок послідовно отримуємо: для рядка А₁ -9<10, -4<7, 0<4, -8<4; для рядка А₂ для комірки А₂В₃ маємо 11>10 або 11-10=1; умова оптимальності порушена, різниця дорівнює 1, записуємо в цю комірку; для комірки А₂В₄ маємо 12>6, 12-6=6, умова теж порушена, різницю, що дорівнює 6, записуємо в цю комірку; для комірки А₂В₅ маємо 12>11, 12-11=1, різницю, яка дорівнює 1, записуємо в комірку;

для рядка А₃ -8<8, -3<5, 1<3;

для рядка А₄ 3<11, 13<16.

Таким чином, маємо три комірки, в яких порушена умова оптимальності; різниці відповідно рівні 2, 6 та 1.

3. Вибір комірки, в яку необхідно послати перевозення.

Транспортна задача лінійного програмування розв’язується на мінімум лінійної функції, тому алгоритм її розв’язання також наслідує загальні принципи алгоритму симплексного методу розв’язання задач на min.

У транспортній задачі значення Z_j замінене сумою потенціалів (U_i+V_j), тому завантаженню підлягає в першу чергу комірка, значення якої відповідає max[(U_i+V_j)-C_ij].

Таким чином, у цьому прикладі max (1;6;1)=6, комірку А₂В₄ необхідно зробити зайнятою. Для цього спочатку необхідно визначити, скільки одиниць вантажу повинно бути перерозподілено до неї.

4. Побудова циклу та визначення величини перерозподілу вантажу. Для визначення кількості одиниць вантажу, що підлягають перерозподілу, помічаємо знаком «+» незайняту комірку, яку потрібно завантажити. Це означає, що комірка приєднується до зайнятих комірок. У таблиці зайнятих комірок стало m + n, тому з’являється цикл, усі вершини котрого, за винятком комірки, помічені знаком «+», знаходяться в зайнятих комірках, причому цей цикл одиничний. Шукаємо цикл і починаємо переміщення від комірки, помічені знаком «+», по черзі проставляємо знаки «-» та «+». Далі знаходимо θ₀=min x_ij, де x_ij – перевезення, що стоять на вершинах циклу, помічаємо знаком «-». Величину θ₀ записуємо в незайняту комірку, помічаємо знаком «+», переміщуємо по циклу, віднімаємо θ₀ від об’єму перевезень, розташованих у комірках, помічених знаком «-», та додаємо до об’єму перевезень, які знаходяться у комірках, помічених знаком «+». Якщо θ₀ відповідають декілька мінімальних перевезень, то при відніманні залишаємо у відповідних комірках нульові перевезення в такій кількості, щоб в новому отриманому оптимальному плані зайнятих комірок було m + n-1.

У даному прикладі комірку А₂В₄ помічаємо знаком «+» та знаходимо цикл, приведений у таблиці 6.3. Маємо θ₀ = min (50;50;0)=0, тобто нульове перевезення необхідно перемістити в комірку А₂В₄, інші числа при відніманні, додаванні нуля, не зміняться.

5. У результаті перерозподілу θ₀ отримуємо новий оптимальний опорний невироджений план (табл. 6.4), який знов підлягає перевірці на оптимальність. Для перевірки на оптимальність нового опорного плану можна знову побудувати систему потенціалів і перевірити виконання умови оптимальності для кожної незайнятої комірки.

Якщо отриманий плані цього разу буде неоптимальним, то слід виконувати розрахунки, наведені в таблиці 6.4. Процес повторюють до тих пір, поки всі незайняті комірки не будуть задовольняти умову . Усі розрахунки оптимального плану рекомендуються виконувати в одній таблиці.

6. Зміна системи потенціалів. У новому опорному плані, записаному в таблиці 6.4. комірка А₂В₄ стала зайнятою. Для зайнятої комірки повинна виконуватися умова . Насправді .Отже, необхідно або U₂, або V₄ зменшити на шість. Звичайно, що зменшувати потрібно той потенціал, зменшення якого приводить до найменшого змінення інших потенціалів. Якщо змінити V₄, а потенціал U₂ залишити без змін, то зміні підлягає тільки потенціал U₁, в іншому випадку змінюються всі інші потенціали.

Таблиця 6.4

Значення потенціалу V₄ зменшилось на 6 од., тому вільні комірки в стовпці В₄, що не відповідають умові оптимальності, з’явитися не можуть. Якщо такі комірки були, то вони можуть зникнути, оскільки різниця дорівнює 6, максимальна для всіх комірок, в яких порушена ця умова. Вільні комірки, що не задовольняють умову оптимальності, можуть з’явитися тільки в рядку (стовпці), потенціал якого збільшився. Потенціал U₁ збільшився на 6 од., тому незайняті комірки рядка А₁ належить перевірити на оптимальність: -3<10; 2<7; 6>4; 7>4. Комірки А₁В₃ та А₁В₅ не відповідають цій умові; знаходимо для них величину різниць та записуємо їх у лівий нижній кут відповідних комірок.

Визначаємо max (2; 3; 1; 1)=3. Комірка А₁В₅ підлягає завантаженню, помічаємо її знаком «+» та встановлюємо цикл перерозподілу, показаний у таблиці 6.3 лінією. Помічаємо вершини циклу знаками «+» та «-», знаходимо θ₀=min (50; 50; 100)=50. За циклом робимо перерозподіл 50 од. вантажу в комірку А₁В₅ і отримуємо опорний план, приведений у таблиці 6.4.

Оскільки значення θ₀=50 здобувається для двох комірок циклу, відмічених знаком «-», то в отриманому опорному плані в комірці А₂В₂ залишене нульове перевезення.

Помітимо, що план внаслідок останньої ітерації покращився на 150 од. вартості. Це покращення знаходиться як добуток кількості одиниць вантажу, перенесеного у вільну комірку, на величину різниці в цій комірці. Величина різниці (U_i+V_j)-C_ij>0 у вільній комірці показує, на скільки зменшилась вартість плану перевезення, якщо одиницю вантажу перерозподіляємо в цю комірку.

Таблиця 6.5

В отриманому опорному плані змінюємо систему потенціалів та перевіряємо його на оптимальність. Умову оптимальності не задовольняють дві комірки з різницями, що дорівнюють 2 та 1, отже, вантаж потрібно перерозподілити в комірку А₁В₃. Помічаємо її знаком «+» і будуємо цикл перерозподілу, який позначений у (табл. 6.4) лінією. Цикли можуть мати різну конфігурацію.

Помічаємо вершини циклу знаками «-» чи «+» та знаходимо величини перерозподілу θ₀=min(50; 0; 100)=0. Нульове перевезення переносимо в комірку А₁В₃, отримуємо новий опорний план і заносимо зміни в систему потенціалів.

Таблиця 6.6

Побудована система потенціалів дає змогу зробити висновок, що план, наведений у таблиці 6.6, є оптимальним. Його вартість дорівнює 4150 од. вартості.

Другий спосіб знаходження оптимального плану

Перевірка опорного плану транспортної задачі на оптимальність

Перш ніж перевіряти на оптимальність опорний план, треба пересвідчитися, що в транспортній таблиці заповнена m + n –1 клітина, де m – кількість пунктів відправлення, а n – кількість пунктів призначення. Якщо заповнених клітин більше ніж m + n – 1, то план побудований неправильно, він не є опорним. План буде опорним тоді і тільки тоді, коли із заповнених клітин не можна утворити цикл. Циклом в транспортній задачі називають замкнену ламану лінію, вершини якої знаходяться в заповнених клітинах, а ланки – в рядках і стовпчиках. Причому у кожній вершині зустрічається одна горизонтальна й одна вертикальна ланка.

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

Таблиця 6.7

Після того як це зроблено, можна скористатися методом потенціалів для перевірки опорного плану на оптимальність. За цим методом кожному пункту відправлення Аі ставиться у відповідність деяке число α_i, а кожному пункту призначення Вj – число β_j. Ці числаназиваються потенціалами.

Для перевірки опорного плану на оптимальність виконуємо такі дії:

1. Для кожної заповненої клітини (i, j) запишемо рівняння виду α_i + β_j = с_ij, де cij– вартість перевезення одиниці вантажу із Аi в Вj. Таких рівнянь буде m+n–1. Потім розв’язують систему, складену з цих рівнянь. Очевидно, що невідомих в цій системі буде m + n, тобто на одне більше, ніж рівнянь. Отже, вона буде мати безліч розв’язків. Треба знайти будь-який її розв’язок. Для цього треба одному невідомому надати будь-якого значення, наприклад, значення 0, а потім поступово знайти значення всіх інших невідомих.

2. Для кожної незаповненої клітини знаходять числа

S_ij=β_j−α_i−c_ij.

Таблиця 6.8

Якщо всі Sij ≤ c_ij, то план, що перевіряється, є оптимальним. Якщо серед Sij −c_ij є додатні, то план, що перевіряється, не є оптимальним і можна перейти до нового опорного плану. Для цього серед додатних чисел Sij −c_ijвибирають найбільше. Нехай, наприклад, це буде Srk-с_rk. Тоді в клітинку (r, k) треба вписати невідомий поки що об’єм перевезень x_rk=ρ і побудувати для цієї клітинки цикл (його можна побудувати єдиним способом). Далі в вершину циклу, яка є сусідньою по циклу з вершиною, куди вписали p, вписуємо число (-p), потім у сусідню з нею по циклу число (+p)і так далі, поки не обійдемо весь цикл. Це робимо для того, щоб баланс по рядочках і стовпцях таблиці не порушився. Потім за p вибираємо найменший з об’ємів перевезень, які стоять у тих клітинах, куди вписали число (-p). Далі вибране значення p додаємо до поставок, що стоять у клітинах, де вписано p, і віднімаємо від поставок у тих клітинах, куди вписали (-p). Ту клітину, де при цьому об’єм перевезень став рівним нулю, звільняють. Якщо таких клітин виявилося декілька, то звільняють одну, а в інші вписують об’єм перевезень, рівний нулю. Отриманий план знову перевіряють на оптимальність, тобто переходять до пункту 1 і так далі, поки не знайдуть оптимальний план.