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

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

Таблиця 8.4

  Пункти Споживачі   Запаси
B1 B2 B3 B4
A1  
A2  
A3  
Потреби

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

Розв’язання

Найменша вартість відповідає клітині (1.4): с14=1. Заплануємо кількістьпродукції x14 = min(100; 250) = 100 одиниць і занесемо її в клітинку (2.1). Виключимо з розгляду четвертий стовпчик (потреби В4 задоволені повністю). З даних, які залишилися, найменша вартість знаходиться в клітинці (1.1) с11=2. Тому в неї заносимо x11 = min(250 – 100; 180) = 150 одиниць і виключаємо з розгляду перший рядок (запаси A1 вичерпані повністю). Але потреби споживача B1 повністю не задоволені. В першому стовпчику наступне за величиною значення вартості перевезення с12=3. В клітинку (1.2) заносимо значення x12 = min(180 – 150; 150) = 30 одиниць і виключаємо з розгляду перший стовпчик (потреби споживача B1 задоволені повністю). В другому рядку серед даних, які залишилися, наступне за величиною значення вартості у клітині (2.2) с22 = 4. Тому в неї заносимо x22 = min(150 – 30; 150) = 120 одиниць і виключаємо з розгляду другий рядок (запаси A2 вичерпані повністю). Але потреби споживача B2 повністю не задоволені. В другому стовпчику наступне за величиною значення вартості перевезення с32 = 5. В клітинку (3.2) заносимо значення x32 = min(150 – 120; 200) = 30 одиниць і виключаємо з розгляду другий стовпчик (потреби споживача B2 задоволені повністю). Нарешті, в клітинку (3.3) заносимо x33 = 170 одиниць, чим повністю вичерпуємо запаси продукції і задовольняємо потреби всіх споживачів (табл. 8.5).

Таблиця 8.5

  Пункти Споживачі   Запаси
B1 B2 B3 B4
A1
A2
A3  
Потреби

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

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

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

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

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

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

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

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

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

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

Якщо для деякого опорного плану Х*=(хij*) існують потенціали ui, vj, для яких виконуються умови

ui + vj = сij для всіх значень і, j , для яких хij > 0;

ui + vj Приклад. Методом мінімальної вартості знайти опорний план транспортної задачі, умова якої наведена в таблиці 8.4 - student2.ru сij для всіх значень і, j , для яких хij = 0,

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

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

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

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

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

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

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

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

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

Наши рекомендации