Покроковий опис методу потенціалів

Метод складається з двох етапів: визначення початкового опорного плану і поліпшення поточного опорного плану.

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

1. У невикресленій частині транспортної матриці вибирати клітинку (i, j) (ця клітинка відповідає базисній змінній x_ij і називається базисною) і покласти x_ij = min {b_i,p_j }.

2. У випадку, коли b_ip_j, потреби j-го споживача зменшити: p^’_j = p_j - x_ij, а і-й рядок транспортної матриці викреслити.

3. У випадку, коли b_i > p_j, запаси і-го постачальника зменшити: b^’_i = b_i - x_ij, а j-й стовпчик транспортної матриці викреслити.

Ітерації повторюються, доки транспортна матриця містить невикреслені елементи.

Другий етап являє собою ітераційну процедуру покращення поточного опорного плану. На кожній ітерації виконуються такі кроки.

1. Визначити потенціали u_i (i = 1, m), v_j (j = 1, n) (аналоги симплекс-множників) для поточної транспортної матриці. Для цього скласти систему рівняннь, у якій кожне рівняння відповідає окремій базисній змінній. Змінній x_ij відповідає рівняння c_ij + u_i + v_j = 0.

2. Приcвоїти довільному потенціалу нульове значення і визначити з отриманої системи усі інші потенціали.

3. Визначити у транспортній матриці небазисну клітинку (i, j), для якої c_ij + u_i + v_j < 0. Якщо така клітинка не існує, поточна транспортна матриця оптимальна – кінець алгоритму.

4. Починаючи з визначеної клітинки, побудувати у транспортній матриці цикл, що містить, крім клітинки (i, j), тільки базисні клітинки. Сусідні клітинки циклу повинні бути розташовані у одному стовпчику або у одному рядку.

5. Пронумерувати клітинки циклу за порядком обходу, присвоївши клітинці (i, j) номер 1. Серед клітинок з парними номерами визначити ту, нехай (r, s), якій відповідає мінімальний об’єм перевезення.

6. Для клітинок циклу з непарними номерами збільшити об’єми перевезень на величину x_rs, а для клітинок з парними - зменшити на x_rs. Після цього клітинка (r, s) стає небазисною, а (i, j) – базисною.

Незбалансована транспортна задача

У незбалансованій задачі b_i p_j. Така задача розв’язується шляхом зведення до збалансованої. Відрізняють два випадки.

Перший випадок - сума запасів перебільшує суму потреб:

b_i > p_j,

тобто увесь продукт перевезти від постачальників до споживачів не можливо, і частина продукту залишається у постачальників. Для приведення вихідної задачі до збалансованої уводиться фіктивний споживач, потреби p_n+1, якого визначаються таким чином p_n+1 = b_i - p_j. Ціни c_{i n+1} (i = 1, m) на перевезення товару до фіктивного споживача визначаються як штрафи за зберігання одиниці продукту у i-го постачальника. У результаті отримуємо збалансовану транспортну задачу.

F = c_ij x_ij min,

x_ij = p_j, j = 1, n+1,

x_ij = b_i, i = 1, m,

x_ij 0, i = 1, m, j = 1, n+1.

Якщо треба, щоб від деяких постачальників продукція обов’язково була вивезена, приймають, що штрафи за зберігання продукції у таких постачальників дорівнюють великому абстрактному числу M, що більше будь-якого конкретного. Зрузуміло, що сумарні запаси таких постачальників не повинні перебільшувати сумарних потреб реальних споживачів.

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

Другий випадок – сума потреб перебільшує суму запасів:

b_i < p_j,

тобто задовольнити потреби усіх споживачів не можливо, і для частини з них при будь-якому плані має місце недопостачання. Для приведення цієї задачі до збалансованої уводять фіктивного постачальника, запаси b_m+1, якого визначаються таким чином b_m+1 = p_j - b_i. Ціни c_m+1j (j = 1, n) на перевезення товару від фіктивного постачальника визначаються як штрафи за недопостачання одиниці продукту j-му споживачу. У результаті отримуємо збалансовану транспортну задачу.

F = c_ij x_ij min,

x_ij = p_j, j = 1, n,

x_ij = b_i, i = 1, m + 1,

x_ij 0, i = 1, m+1, j = 1, n.

Якщо треба, щоб до деяких споживачів продукція обов’язково була перевезена, приймають, що штрафи за недопостачання продукції до таких споживачів дорівнюють великому абстрактному числу M, що більше будь-якого конкретного. Зрузуміло, що сумарні потреби таких споживачів не повинні перебільшувати сумарних запасів реальних постачальників.

Якщо за недопостачання продукції до деякого споживача не треба сплачувати ніяких штрафів, то штрафу для цього споживача присвоюють нульове значення.

Дата добавления: 2014-01-13