Симплексний метод лінійного програмування (стр. 3 из 4)

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

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

	В1	В2	В3	В4	В5	Запаси
А1	5	2	3	6	1	200
А2	1	1	4	4	2	150
А3	4	3	1	2	1	350
А4	0	0	0	0	0	70
Потреби	110	170	200	180	110

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

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

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

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

minZ=5x₁₁+2x₁₂+3x₁₃+6x₁₄+1x₁₅+1x₂₁+1x₂₂+4x₂₃+4x₂₄+2x₂₅+4x₃₁+3x₃₂+1x₃₃

+2x₃₄+ +1x₃₅+0x₄₁+0x₄₂+0x₄₃+0x₄₄+0x₄₅.

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

minZ=5x₁₁+2x₁₂+3x₁₃+6x₁₄+1x₁₅+1x₂₁+1x₂₂+4x₂₃+4x₂₄+2x₂₅+4x₃₁+3x₃₂+1x₃₃

+2x₃₄+ +1x₃₅+0x₄₁+0x₄₂+0x₄₃+0x₄₄+0x₄₅.

за умов:

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

Ai	Bj					ui
	b1 = 110	b2 = 170	b3 = 200	b4=180	b5=110
а1 = 200	5 110	2 [-] 90	3	6	1 [+]	u1 = 0
а2 = 150	1	1 [+] 80	4 [-] 70	4	2	u2 = -1
а3 = 350	4	3	1 [+] 130	2 180	1 [-] 40	u3 = -4
а4 = 70	0	0	0	0	0 70	u4 = -5
vj	v1 = 5	v2 = 2	v3 = 5	v4 = 6	v5 = 5

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

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

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

u₁=0, u₂=-1, u₃=-4, u₄=-5, v₁=5, v₂=2, v₃=5 v₄=6, v₅=5.

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

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

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

(1;3): 0 + 5 > 3

(1;5): 0 + 5 > 1

(2;1): -1 + 5 > 1

(2;4): -1 + 6 > 4

(2;5): -1 + 5 > 2

(4;4): -5 + 6 > 0

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

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

Для цього у порожню клітинку А₁B₄ переносимо менше з чисел х_ij, які розміщені в клітинках зі знаком «–». Одночасно це саме число х_ij додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».

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

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

Ai	Bj					ui
	b1 = 110	b2 = 170	b3 = 200	b4=180	b5=110
а1 = 200	5 110	2 [-] 50	3	6	1 [+] 40	u1 = 0
а2 = 150	1	1 [+] 120	4 [-] 30	4	2	u2 = -1
а3 = 350	4	3	1 [+] 170	2 [-] 180	1	u3 = -4
а4 = 70	0	0	0	0 [+]	0 [-] 70	u4 = -1
vj	v1 = 5	v2 = 2	v3 = 5	v4 = 6	v5 = 1

Перевіримо оптимальність опорного плану. Знайдемо потенціали u_i, v_i. по зайнятих клітинам таблиці, в яких u_i + v_i = c_ij, вважаючи, що u₁ = 0.

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

(1;3): 0 + 5 > 3

(2;1): -1 + 5 > 1

(2;4): -1 + 6 > 4

(4;1): -1 + 5 > 0

(4;2): -1 + 2 > 0

(4;3): -1 + 5 > 0

(4;4): -1 + 6 > 0

Вибираємо максимальну оцінку вільної клітини (А₄B₄): 0

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

З вантажів х_ij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (А₂B₃) = 30. Додаємо 30 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 30 з Х_ij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.

Ai	Bj					ui
	b1 = 110	b2 = 170	b3 = 200	b4=180	b5=110
а1 = 200	5 [-] 110	2 20	3	6	1 [+] 70	u1 = 0
а2 = 150	1	1 150	4	4	2	u2 = -1
а3 = 350	4	3	1 200	2 150	1	u3 = 1
а4 = 70	0 [+]	0	0	0 30	0 [-] 40	u4 = -1
vj	v1 = 5	v2 = 2	v3 = 0	v4 = 1	v5 = 1

Перевіримо оптимальність опорного плану. Знайдемо потенціали u_i, v_i. по зайнятих клітинам таблиці, в яких u_i + v_i = c_ij, вважаючи, що u₁ = 0.