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

У таблиці в куті кожної клітини ставиться ціна c_ij. Однак заповнення таблиці проводиться без урахування цих цін зверху вниз і з ліва на право по стовпчиках і рядках; у клітину поміщається x_ij = min (a_i; b_j)

Приклад

 

Спожив.   Пост.	В1	В2	В3	В4	В5	Запаси
А1		----	----	----	----
А2			----	----	----
А3	…				----
А4	----	----	----
Потреби

 

Загальний обсяг запасів (потреб) 850 од.

Рядок (стовпчик) з вичерпаним запасом (задоволеною потребою) прокреслюється.

У прикладі m=4; n=5; m+n-1=8

У таблиці число зайнятих клітин N=8, отже, план не вироджений.

Схема плану:

циклу немає, план є опорним.

 

 

Вартість плану Z = 6950 (гр.од.)

Метод мінімальної (найменшої) вартості

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

Спожив.   Постач.	В1	В2	В3	В4	В5	Запаси
А1	----	----	----		----
А2			----	----	----
А3	----	----	----	----
А4	----			----
Потреби

Схема плану:

 

 

Циклу немає, N=7<8

План опорний, вироджений. Вартість плану Z=4300 (гр.од.)

 

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

1. У кожному рядку знаходиться клітина з найменшою ціною і позначається позначкою.

2. Те ж саме проводиться для кожного стовпчика.

3. Заповнення таблиці починаємо з клітин, відзначених двома позначками.

4. Після цього заповнюються клітини з однією позначкою.

5. У таблиці, що залишилася, застосовується метод мінімальної вартості.

 

 

Спожив.   Постач.	В1	В2	В3	В4	В5	Запаси
А1	----	----	----	vv 1	----
А2	vv 2	----		----	----
А3	----	v 5 ----	V 3 ----	v 2 ----	vv 2
А4	----	v 8		----
Потреби

 

Схема плану:

N=7

План опорний, вироджений Z=4250 (гр. од.)

З трьох викладених методів даний метод, як правило, дає план з меншою загальною вартістю порівняно з іншими методами.

 

Контрольні запитання

1. Як економічно формулюється транспортна задача?

2. Якою є математична модель ТЗ?

3. Як треба будувати первісний план ТЗ за методом північно-західного кута?

4. Що таке цикл у таблиці ТЗ?

5. Якими є алгоритми методів найменшої вартості та подвійної переваги?

 

Лекція 6

Транспортна задача

Поліпшення плану

Розв’язування задачі у відкритій моделі

 

1. Загальний алгоритм розв’язування ТЗ

2. Перетворення виродженого плану у не вироджений

3. Метод потенціалів для оцінки плану

4. Поліпшення плану в циклі перерозподілу постачань. Приклад розв’язування ТЗ

5. Розв’язування ТЗ у відкритій моделі

 

1. Загальний алгоритм розв’язування транспортної задачі:

а)Побудова початкового опорного плану.

б)Оцінка плану на оптимальність.

в)Поліпшення плану, якщо він не є оптимальним.

г)Оцінка плану і т.д.

2. Для поліпшення плану необхідно провести його оцінку. Якщо є не вироджений опорний план, його можна оцінювати. Вироджений план необхідно зробити не виродженим. Для цього необхідно доповнити план клітиною з перевезенням, яке дорівнює нулю. Це не змінить розподіл товару, але збільшить на одиницю число зайнятих клітин. Вибір клітини, що доповнює план, варто зробити так, щоб не з'явився цикл (без втрати опірності).

3. Кожній зайнятій клітині ставиться у відповідність два числа – потенціали постачальника і споживача. При цьому їхня сума прирівнюється ціні, що міститься в цій клітині.

u_i-потенціал постачальника; v_j-потенціал споживача.

u_i+ v_j = c_ij (6.1)

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

Для кожної вільної клітини (i; j) обчислюється сума потенціалів постачальника і споживача

d_ij=u_i+v_j

і записується в цю клітину.

Якщо для всіх вільних клітин виконана нерівність

d_ij ≤ c_ij (6.2)

план перевезень оптимальний.

Якщо для деякої клітини

d_ij >c_ij (6.3)

план не є оптимальним і його можна поліпшити.

4. Поліпшення плану досягається перерозподілом постачань за циклом. Цикл повинен містити вершину в клітині з умовою (6.3), а інші вершини – у зайнятих клітинах. Обсяг товару, що перерозподіляється, дорівнює мінімумові з обсягів перевезень, що складаються в клітинах з парними номерами за циклом, початок якого знаходиться в обраній клітині з порушенням (6.2). (Інше пояснення буде в прикладі).

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

Спожив.   Постач.	В1	В2	В3	В4	Запаси	m=4; n=4; m+n- -1=7
А1
А2
А3
А4
Потреби

Вартість плану

Z= 1005 гр.од.

Схема плану:

 

План опорний.

Кількість зайнятих клітин N=7, план не вироджений.

 

Складемо систему рівнянь для потенціалів

 

u₁ + v₃ = 3 u₃ + v₂ = 2

u₁ + v₄ = 4 u₄ + v₂ = 3

u₂ + v₁ = 1 u₄ + v₄ = 7

u₃ + v₄ = 2

u₂ + v₄ = 9

 

Нехай u₁ = 0; тоді одержимо

v₃ = 3; v₄ = 4; u₂ = 5; v₁ = -4; u₄ = 3; v₂ = 0; u₃ = 2

Знайдемо суми потенціалів для вільних клітин і порівняємо з відповідними цінами

 

Спожив.   Постач.	В1	В2	В3	В4	Запаси	ui
А1	-4
А2
А3	-2			*
А4	-1
Потреби
vj	-4

 

План не оптимальний, тому що в клітині (2,3) 8 > 6 і в клітині (3,4) 6 > 4.

Виберемо клітину (3,4) і побудуємо цикл перерозподілу.

 

75 * 35 40

 

45 40 85

min (40, 45) = 40. Передача від «-» до «+» 40 од. товару

Одержали новий план перевезень; обчислимо його вартість, побудуємо схему плану і розрахуємо потенціали.

Спожив.   Постач.	В1	В2	В3	В4	Запаси	ui
А1	-1
А2			*
А3	-1
А4
Потреби
vj	-1

 

Вартість плану

Z= 925 гр.од. N = 7.

Схема плану:

План опорний, не вироджений і не оптимальний; у клітині (2,3) 8 > 6.

Побудуємо цикл перерозподілу

90 10 80 20

 

* 10 10

 

min (90, 10) = 10 – кількість одиниць товару, перерозподілена за циклом.

Новий план перевезень

Спожив.   Постач.	В1	В2	В3	В4	Запаси	ui
А1	-2
А2
А3	-2
А4	-1
Потреби
vj	-2

Вартість плану

Z= 905 гр.од.

План оптимальний, тому що для всіх вільних кліток виконана умова (6.3).