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

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

Таблиця 8.4

А також оцінити затрати на перевезення при отриманому опорному плані.

Розв’язання

Найменша вартість відповідає клітині (1.4): с₁₄ =1. Заплануємо кількістьпродукції x ₁₄ = min(100; 250) = 100 одиниць і занесемо її в клітинку (2.1). Виключимо з розгляду четвертий стовпчик (потреби В₄ задоволені повністю). З даних, які залишилися, найменша вартість знаходиться в клітинці (1.1) с₁₁ =2. Тому в неї заносимо x ₁₁ = min(250 – 100; 180) = 150 одиниць і виключаємо з розгляду перший рядок (запаси A₁ вичерпані повністю). Але потреби споживача B₁ повністю не задоволені. В першому стовпчику наступне за величиною значення вартості перевезення с₁₂ =3. В клітинку (1.2) заносимо значення x ₁₂ = min(180 – 150; 150) = 30 одиниць і виключаємо з розгляду перший стовпчик (потреби споживача B₁ задоволені повністю). В другому рядку серед даних, які залишилися, наступне за величиною значення вартості у клітині (2.2) с₂₂ = 4. Тому в неї заносимо x ₂₂ = min(150 – 30; 150) = 120 одиниць і виключаємо з розгляду другий рядок (запаси A₂ вичерпані повністю). Але потреби споживача B₂ повністю не задоволені. В другому стовпчику наступне за величиною значення вартості перевезення с₃₂ = 5. В клітинку (3.2) заносимо значення x ₃₂ = min(150 – 120; 200) = 30 одиниць і виключаємо з розгляду другий стовпчик (потреби споживача B₂ задоволені повністю). Нарешті, в клітинку (3.3) заносимо x ₃₃ = 170 одиниць, чим повністю вичерпуємо запаси продукції і задовольняємо потреби всіх споживачів (табл. 8.5).

Таблиця 8.5

Оскільки кількість заповнених клітин дорівнює 7 = m + n – 1, то отриманий опорний план є невиродженим.

Оцінимо загальну вартість перевезень складеного опорного плану. Як випливає з таблиці 8.5

F = 150*2 + 100*1 + 30*3 + 120*4 + 30*5 + 170*3 = 1630 (одиниць вартості).

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

Метод подвійної переваги

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

Етап 3. Після того, як знайдено початковий опорний план ТЗ, кожному пункту A_i (кожному рядку) ставиться у відповідність деяке число u_i (i = 1…m), а кожному стовпчику B_j (j = 1…n) – деяке число v_j. Числа u_i, v_j називаються потенціалами пункту A_i і споживача B_j. Далі визначаються потенціали опорного плану. Для цього розв’язується система рівнянь u_i + v_j = с_ij, яка формується для всіх заповнених клітинок транспортної таблиці.

Оскільки для невиродженого опорного плану зайнятих клітинок є m + n – 1, то для визначення чисел u_i, v_j необхідно розв’язати систему з m + n – 1 рівнянь з m + n невідомими. Така системалінійних рівнянь є невизначеною. Для усунення невизначеності одній з невідомих надається довільне значення, наприклад нуль. Тоді розв’язок системи визначається однозначно.

Етап 4. Після визначення потенціалів опорний план перевіряється на оптимальність. При цьому керуються такою теоремою.

Теорема (умова оптимальності опорного плану транспортної задачі).

Якщо для деякого опорного плану Х ^*=(х_{i j}^*) існують потенціали u_i, v_j, для яких виконуються умови

u_i + v_j = с_ij для всіх значень і, j, для яких х_{i j} > 0;

u_i + v_j с_ij для всіх значень і, j, для яких х_{i j} = 0,

то він є оптимальним планом транспортної задачі.

Якщо хоча б для однієї клітинки ця умова не виконується, тобто u_i + v_j > с_ij, то поточний план не є оптимальним і від нього переходять до нового опорного плану.

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

Для вибраної клітинки будують цикл перерахування та виконують перерозподіл продукції в межах цього циклу за такими правилами:

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

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

У результаті цих дій клітинка, яка була вільною, стає заповненою, а відповідна клітинка з мінімальним числом х_{i j} стане порожньою. У результаті такого перерозподілу продукції отримується новий опорний план транспортної задачі.

Етап 5. Далі повторюються кроки алгоритму, починаючи з кроку 3.

Розглянемо застосування методу потенціалів на прикладі.