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

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

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

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

В1	В2	В3	В4	В5	В6	Запаси
А1	5	2	3	6	1	0	150
А2	1	1	4	4	2	0	320
А3	4	1	2	3	5	0	400
Потреби	100	120	100	200	300	50

Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі:

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

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

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

minZ=5x11+2x12+3x13+6x14+1x15+0x16+1x21+1x22+4x23+4x24+2x25+0x26+4x31+1x32+2x33+3x34+ +5x35+0x36.

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

minZ=5x11+2x12+3x13+6x14+1x15+0x16+1x21+1x22+4x23+4x24+2x25+0x26+4x31+1x32+2x33+3x34+ +5x35+0x36.

за умов:

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

Ai	Bj						ui
b1 = 100	b2 = 120	b3 = 100	b4=200	b5=300	b6=50
а1 = 150	5100	2[-] 50	3	6	1[+]	0	u1 = 0
а2 = 320	1	1[+] 70	4100	4[-] 150	2	0	u2 = -1
а3 = 400	4	1	2	3[+] 50	5[-] 300	050	u3 = -2
vj	v1 = 5	v2 = 2	v3 = 5	v4 = 5	v5 = 7	v6 = 2

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

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

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

u1 + v1 = 5; 0 + v1 = 5; v1 = 5

u1 + v2 = 2; 0 + v2 = 2; v2 = 2

u2 + v2 = 1; 2 + u2 = 1; u2 = -1

u2 + v3 = 4; -1 + v3 = 4; v3 = 5

u2 + v4 = 4; -1 + v4 = 4; v4 = 5

u3 + v4 = 3; 5 + u3 = 3; u3 = -2

u3 + v5 = 5; -2 + v5 = 5; v5 = 7

u3 + v6 = 0; -2 + v6 = 0; v6 = 2

Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.

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

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

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

(1;5): 0 + 7 > 1; ∆15 = 0 + 7 - 1 = 6

(1;6): 0 + 2 > 0; ∆16 = 0 + 2 - 0 = 2

(2;1): -1 + 5 > 1; ∆21 = -1 + 5 - 1 = 3

(2;5): -1 + 7 > 2; ∆25 = -1 + 7 - 2 = 4

(2;6): -1 + 2 > 0; ∆26 = -1 + 2 - 0 = 1

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

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

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

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

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

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

Ai	Bj						ui
b1 = 100	b2 = 120	b3 = 100	b4=200	b5=300	b6=50
а1 = 150	5[-] 100	2	3	6	1[+] 50	0	u1 = 0
а2 = 320	1[+]	1120	4100	4[-] 100	2	0	u2 = 5
а3 = 400	4	1	2	3[+] 100	5[-] 250	050	u3 = 4
vj	v1 = 5	v2 = -4	v3 = -1	v4 = -1	v5 = 1	v6 = -4

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

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

(2;1): 5 + 5 > 1; ∆21 = 5 + 5 - 1 = 9

(2;5): 5 + 1 > 2; ∆25 = 5 + 1 - 2 = 4

(2;6): 5 + -4 > 0; ∆26 = 5 + -4 - 0 = 1

(3;1): 4 + 5 > 4; ∆31 = 4 + 5 - 4 = 5

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

Вибираємо максимальну оцінку вільної клітини (2;1): 1

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

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

Ai	Bj						ui
b1 = 100	b2 = 120	b3 = 100	b4=200	b5=300	b6=50
а1 = 150	5[-] 0	2	3	6	1[+] 150	0	u1 = 0
а2 = 320	1[+] 100	1120	4[-] 100	4	2	0	u2 = -4
а3 = 400	4	1	2[+]	3200	5[-] 150	050	u3 = 4
vj	v1 = 5	v2 = 5	v3 = 8	v4 = -1	v5 = 1	v6 = -4

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

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

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

(1;3): 0 + 8 > 3; ∆13 = 0 + 8 - 3 = 5

(3;1): 4 + 5 > 4; ∆31 = 4 + 5 - 4 = 5

(3;2): 4 + 5 > 1; ∆32 = 4 + 5 - 1 = 8

(3;3): 4 + 8 > 2; ∆33 = 4 + 8 - 2 = 10

Вибираємо максимальну оцінку вільної клітини (3;3): 2

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

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

В результаті отримаємо новий опорний план.

Ai	Bj						ui
b1 = 100	b2 = 120	b3 = 100	b4=200	b5=300	b6=50
а1 = 150	5	2	3	6	1150	0	u1 = 0
а2 = 320	1100	1120	4[-] 100	4	2[+]	0	u2 = 6
а3 = 400	4	1	2[+] 0	3200	5[-] 150	050	u3 = 4
vj	v1 = -5	v2 = -5	v3 = -2	v4 = -1	v5 = 1	v6 = -4

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

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

(2;4): 6 + -1 > 4; ∆24 = 6 + -1 - 4 = 1

(2;5): 6 + 1 > 2; ∆25 = 6 + 1 - 2 = 5

(2;6): 6 + -4 > 0; ∆26 = 6 + -4 - 0 = 2

Вибираємо максимальну оцінку вільної клітини (2;5): 2

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

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

В результаті отримаємо новий опорний план.

Ai	Bj						ui
b1 = 100	b2 = 120	b3 = 100	b4=200	b5=300	b6=50
а1 = 150	5	2	3	6	1150	0	u1 = 0
а2 = 320	1100	1[-] 120	4	4	2[+] 100	0	u2 = 1
а3 = 400	4	1[+]	2100	3200	5[-] 50	050	u3 = 4
vj	v1 = 0	v2 = 0	v3 = -2	v4 = -1	v5 = 1	v6 = -4

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

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

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

Вибираємо максимальну оцінку вільної клітини (3;2): 1

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

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

В результаті отримаємо новий опорний план.