Ім'я файлу: Транспортна задача.docx
Розширення: docx
Розмір: 52кб.
Дата: 25.06.2020

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



Вартість доставки одиниці вантажу з кожного пункту відправлення у відповідні пункти призначення задана матрицею тарифів




B1

B2

B3

B4

Запаси

A1

3

7

4

5

180

A2

4

3

4

5

200

A3

3

4

3

4

240

A4

2

3

7

4

160

Потреби

280

200

320

240




Перевіримо необхідна і достатня умова розв'язання задачі.

Σa = 180 + 200 + 240 + 160 = 780

Σb = 280 + 200 + 320 + 240 = 1040

Як видно, сумарна потреба вантажу в пунктах призначення перевищує запаси вантажу на базах. Отже, модель вихідної транспортної задачі є відкритою. Тобто жоден оптимальний план не може задовольнити умови повністю, враховуючи, що ПОТРЕБИ перевищують ЗАПАСИ.

Щоб отримати закриту модель, введемо додаткову (фіктивну) базу з запасом вантажу, рівним 260 (1040-780).

Тарифи перевезення одиниці вантажу з бази в усі магазини вважаємо дорівнюють нулю.

Занесемо вихідні дані в розподільну таблицю.




B1

B2

B3

B4

Запаси

A1

3

7

4

5

180

A2

4

3

4

5

200

A3

3

4

3

4

240

A4

2

3

7

4

160

A5

Фіктивна база

0

0

0

0

260

Потреби

280

200

320

240




Модель приведено до закритого типу Σa = Σb (за рахунок введення фікт. бази)

Етап I. Пошук першого опорного плану.

1. Використовуючи метод найменшої вартості, побудуємо перший опорний план транспортної задачі.

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

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

З решти таблиці вартостей знову вибирають найменшу вартість, і процес розподілу запасів продовжують, поки всі запаси не будуть розподілені, а потреби задоволені.

Далі приводимо ітерації пошуку опорн6ого плану

Шуканий елемент дорівнює c41 = 2. Для цього елемента запаси рівні 160, потреби 280. Оскільки мінімальним є 160, то віднімаємо його.

x41 = min (160,280) = 160.

3

7

4

5

180

4

3

4

5

200

3

4

3

4

240

2

x

x

x

160 - 160 = 0

0

0

0

0

260

280 - 160 = 120

200

320

240




Шуканий елемент дорівнює c11 = 3. Для цього елемента запаси рівні 180, потреби 120. Оскільки мінімальним є 120, то віднімаємо його.

x11 = min (180,120) = 120.

3

7

4

5

180 - 120 = 60

x

3

4

5

200

x

4

3

4

240

2

x

x

x

0

x

0

0

0

260

120 - 120 = 0

200

320

240




Шуканий елемент дорівнює c22 = 3. Для цього елемента запаси рівні 200, потреби 200. Оскільки мінімальним є 200, то віднімаємо його. В даному випадку неважливо, що саме ми оберемо…

x22 = min (200,200) = 200.

3

7

4

5

60

x

3

x

x

200 - 200 = 0

x

4

3

4

240

2

x

x

x

0

x

0

0

0

260

0

200 - 200 = 0

320

240




Шуканий елемент дорівнює c33 = 3. Для цього елемента запаси рівні 240, потреби 320. Оскільки мінімальним є 240, то віднімаємо його.

x33 = min (240,320) = 240.

3

7

4

5

60

x

3

x

x

200 - 200 = 0

x

4

3

4

240

2

x

x

x

0

x

0

0

0

260

0

200 - 200 = 0

320

240




Шуканий елемент дорівнює c13 = 4. Для цього елемента запаси рівні 60, потреби 80. Оскільки мінімальним є 60, то віднімаємо його.

x13 = min (60,80) = 60.

3

7

4

x

60 - 60 = 0

x

3

x

x

0

x

4

3

x

0

2

x

x

x

0

x

0

0

0

260

0

0

80 - 60 = 20

240




Шуканий елемент дорівнює c53 = 0. Для цього елемента запаси рівні 260, потреби 20. Оскільки мінімальним є 20, то віднімаємо його.

x53 = min (260,20) = 20.

3

7

4

x

0

x

3

x

x

0

x

4

3

x

0

2

x

x

x

0

x

0

0

0

260 - 20 = 240

0

0

20 - 20 = 0

240




Шуканий елемент дорівнює c54 = 0. Для цього елемента запаси рівні 240, потреби 240. Оскільки мінімальним є 240, то віднімаємо його.

x54 = min (240,240) = 240.

3

7

4

x

0

x

3

x

x

0

x

4

3

x

0

2

x

x

x

0

x

0

0

0

240 - 240 = 0

0

0

0

240 - 240 = 0




Далі, згідно з алгоритмом, шукаємо елементи серед тих, що залишились ( не викреслених).

3

7

4

5

180

4

3

4

5

200

3

4

3

4

240

2

3

7

4

160

0

0

0

0

260

280

200

320

240




Шуканий елемент дорівнює c42 = 3, так як обмеження виконані, то x42 = 0.




B1

B2

B3

B4

Запаси

A1

3[120]

7

4[60]

5

180

A2

4

3[200]

4

5

200

A3

3

4

3[240]

4

240

A4

2[160]

3[0]

7

4

160

A5

0

0

0[20]

0[240]

260

Потреби

280

200

320

240




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

2. Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m + n - 1 = 8. Отже, опорний план є невиродженим.

Значення цільової функції для цього опорного плану рівне:

F (x) = 3*120 + 4*60 + 3*200 + 3*240 + 2*160 + 0*20 + 0*240 = 2240

Етап II. Поліпшення опорного плану.

Перевіримо оптимальність опорного плану. Знайдемо попередні потенціали ui, vj. по зайнятих клітинам таблиці, в яких ui + vj = cij, вважаючи, що u1 = 0.

u1 + v1 = 3; 0 + v1 = 3; v1 = 3
u4 + v1 = 2; 3 + u4 = 2; u4 = -1
u4 + v2 = 3; -1 + v2 = 3; v2 = 4
u2 + v2 = 3; 4 + u2 = 3; u2 = -1
u1 + v3 = 4; 0 + v3 = 4; v3 = 4
u3 + v3 = 3; 4 + u3 = 3; u3 = -1
u5 + v3 = 0; 4 + u5 = 0; u5 = -4
u5 + v4 = 0; -4 + v4 = 0; v4 = 4




v1=3

v2=4

v3=4

v4=4

u1=0

3[120]

7

4[60]

5

u2=-1

4

3[200]

4

5

u3=-1

3

4

3[240]

4

u4=-1

2[160]

3[0]

7

4

u5=-4

0

0

0[20]

0[240]

Опорний план є оптимальним, так все оцінки вільних клітин задовольняють умові ui + vj ≤ cij.

Мінімальні витрати складуть:

F (x) = 3*120 + 4*60 + 3*200 + 3*240 + 2*160 + 0*20 + 0*240 = 2240

В результаті всі запаси вивезено, з мінімальними затратами . та максимально можливим варіантом забезпечення потреб.

Запропонований оптимальний план не задовольняє потреби магазину №3 на 20 одиниць продукції, магазин №4 – на 240 одиниць. Дана ситуація спричинена початковим перевищенням потреб над запасами (див. початок, аналіз задачі.)
скачати

© Усі права захищені
написати до нас