Математичне програмування (стр. 3 из 3)

Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:

minZ=3x11+5x12+1x13+4x14+4x21+1x22+2x23+3x24+1x31+2x32+3x33+4x34.

Загалом математична модель сформульованої задачі має вигляд:

minZ=3x11+5x12+1x13+4x14+4x21+1x22+2x23+3x24+1x31+2x32+3x33+4x34.

за умов:

Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».

Ai	Bj				ui
	b1 = 90	b2 = 110	b3 = 220	b4=80
а1 = 200	3	5	1200	4	u1 =
а2 = 140	490	150	2	3	u2 =
а3 = 160	1	260	320	580	u3 =
vj	v1 =	v2 =	v3 =	v4 =

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

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

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

Ai	Bj				ui
	b1 = 90	b2 = 110	b3 = 220	b4=80
а1 = 200	3	5	1200	4	u1 = 0
а2 = 140	4	1[-] 110	220	3[+] 10	u2 = 1
а3 = 160	190	2[+]	3	5[-] 70	u3 = 3
vj	v1 = -2	v2 = 0	v3 = 1	v4 = 2

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

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

Для розв’язку візьмемо останній опорний план.

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

u1=0, u2=0, u3=3, v1=-2, v2=0, v3=1 v4=2. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.

Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ≤ cij (для порожніх клітинок таблиці).

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

(3;2): 3 + 0 > 2; ∆32 = 3 + 0 - 2 = 1

(3;3): 3 + 1 > 3; ∆33 = 3 + 1 - 3 = 1

max(1,1) = 1

Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (3;2): 2. Для цього в перспективну клітку (3;2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.

Тепер необхідно перемістити продукцію в межах побудованого циклу. З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (3, 4) = 70. Додаємо 70 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 з хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.

Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).

Отже, другий опорний план транспортної задачі матиме такий вигляд:

Ai	Bj				ui
	b1 = 90	b2 = 110	b3 = 220	b4=80
а1 = 200	3	5	1200	4	u1 = 0
а2 = 140	4	140	220	380	u2 = 1
а3 = 160	190	270	3	5	u3 = 2
vj	v1 = -1	v2 = 0	v3 = 1	v4 = 2

Перевіримо оптимальність опорного плану, тобто повторюємо описані раніше дії.

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

u1 + v3 = 1; 0 + v3 = 1; v3 = 1

u2 + v3 = 2; 1 + u2 = 2; u2 = 1

u2 + v2 = 1; 1 + v2 = 1; v2 = 0

u3 + v2 = 2; 0 + u3 = 2; u3 = 2

u3 + v1 = 1; 2 + v1 = 1; v1 = -1

u2 + v4 = 3; 1 + v4 = 3; v4 = 2

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

Розрахуємо значення цільової функції відповідно до другого опорного плану задачі:

F(x) = 1*200 + 1*40 + 2*20 + 3*80 + 1*90 + 2*70 = 750

За оптимальним планом перевезень загальна вартість перевезень всієї продукції є найменшою і становить 750 грн.