Контрольная работа: Симплексний метод лінійного програмування

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

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

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

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).