Поліпшений план транспортної задачі

Базисний план транспортного завдання

Постачальники (потужність)	Споживачі (потреба)	Коефіцієнт рядка
1 (800)	2 (1400)	3 (1300)
А (1500)
				-
Б (800)
-
В (1200)							-1
-		-
Коефіцієнти стовпчиків

Даній вершині (Б₁) із нульовою потребою ставиться знак плюс, а потім, у напрямі часової стрілки, всім іншим вершинам додається знак мінус та плюс. Потім із вершини, що відзначена знаком мінус і має меншу потребу, ніж інші сусідні до порожньої (від'ємні) вершини, потреба у вантажах переміщується в порожню (Б₁) клітинку. Переміщення вантажів по вершинах додаткового плану повинно відповідати першій сумі вантажів по ребрах додаткового плану. Так, наприклад, у клітинці А₁ значення вантажу після перерозподілу - 100 одиниць, тобто від (800+0), що було раніше по лівому ребру плану, треба відняти 700, що з'явилось у клітинці Б₁ У цілому процедури формування додаткового плану табл. 11.6. мають такий вигляд:

Рис. 11.1. Схема формування нового плану

Новий план розподілу вантажів (табл. 11.7) утворюється «накладанням» кінцевого додаткового плану табл. 11.6 на її базисний план.

Цільова функція поліпшеного плану (табл. 11.7):

Таблиця 11.7.

Постачальники (потужність)	Споживачі (потреба)	Коефіцієнт рядка
1 (800)	2 (1400)	3 (1300)
А (1500)
				-
Б (800)							-2
		-
В (1200)							-5
-		-
Коефіцієнти стовпчиків

Z= 100 · 4 + 1400 · 2 + 700 · 1 + 100 · 5 + 1200 · 2 = 6800.

Спочатку для поліпшеного плану (табл. 11.7.) визначаються коефіцієнти рядків і стовпчиків, які заповнюються у відповідні клітинки, а потім для незаповнених клітинок перевіряються умови оптимальності плану:

А₃: 3-(1+7) = -5;

Б₂: 3-(1-2) = 4;

В₁: 7-(3-5) = 9;

В₂: 6-(1-5) = 10;

Оскільки для клітинки А₃ умова оптимальності не витримується, то складається додатковий план з вершиною А₃, який має вигляд:

Після наступного перерозподілу вантажів у цьому додатковому плані він буде такий:

A3 (100)

Новий поліпшений план, який називається остаточним (табл. 11.8.), можна отримати "накладанням" щойно отриманого додаткового плану на табл 11.7. Значення цільової функції остаточного плану:

Z = 1400 · 2 + 100 · 3 + 800 · 1 + 1200 · 2 = 6300,

що на 3300 одиниць менш ніж бажаний план (майже на 30 %).

Таблиця 11.8.

Дата добавления: 2014-11-06