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

Завдання 1

Зібраний врожай зерна трьох сільськогосподарських артілей повинен бути перевезений на три елеватори, а саме: елеватор А₁ потужністю 100 тис. тонн, елеватор А₂ – 80 тис. тонн; А₃ – 90 тис. тонн. Визначити план перевезення зерна на елеватори, який мінімізує транспортні витрати.

С/г артіль	Затрати на перевезення 1 т зерна на елеватори, грн.			Запас зерна, тис. т
С/г артіль	В1	В2	В3	Запас зерна, тис. т
А₁	12,5	24,0	18,4	80
А₂	28,3	14,5	25,7	90
А₃	15,7	20,6	16,3	100
Потужність елеваторів	100	80	90

Розв’язок

Побудова математичної моделі. Нехай x_ij — кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача

Перевіримо необхідність і достатність умов розв'язання задачі:

Оскільки

, то умова балансу дотримується. Запаси рівні потребам. Отже, модель транспортної задачі є закритою.

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

В₁	В₂	В₃	Запаси
А₁	12,5	24,0	18,4	80
А₂	28,3	14,5	25,7	90
А₃	15,7	20,6	16,3	100
Потреби	100	80	90

Розпочинаємо будувати математичну модель даної задачі:

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

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

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

minZ=12,5x₁₁+24x₁₂+18,4x₁₃+28,3x₂₁+14,5x₂₂+25,7x₂₃+15,7x₃₁+20,6x₃₂+16,3x₃₃.

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

minZ=12,5x₁₁+24x₁₂+18,4x₁₃+28,3x₂₁+14,5x₂₂+25,7x₂₃+15,7x₃₁+20,6x₃₂+16,3x₃₃.

за умов:

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

A_i	B_j			u_i
A_i	b₁= 100	b₂= 80	b₃= 90	u_i
а₁= 80	12,5 80	24,0	18,4	u₁ = 0
а₂= 90	28,3 [-]20	14,5 [+]70	25,7	u₂ = 15,8
а₃= 100	15,7 [+]	20,6 [-]20	16,3 80	u₃ = 21,9
v_j	v₁=12,5	v₂=-1,3	v₃=-5,6

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

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

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

u₁=0, u₂=15,8, u₃=21,9, v₁=12,5, v₂=-1,3, v₃=-5,6. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.

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

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

(3;1): 21.9 + 12.5 > 15.7; ∆₃₁ = 21.9 + 12.5 - 15.7 = 18.7

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

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

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

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

A_i	B_j			u_i
A_i	b₁= 100	b₂= 80	b₃= 90	u_i
а₁= 80	12,5 80	24,0	18,4	u₁ = 0
а₂= 90	28,3 [-] 0	14,5 90	25,7 [+]	u₂ = 15,8
а₃= 100	15,7 [+] 20	20,6	16,3 [-]80	u₃ = 3,2
v_j	v₁=12,5	v₂=-1,3	v₃=13,1

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

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

(2;3): 15.8 + 13.1 > 25.7; ∆₂₃ = 15.8 + 13.1 - 25.7 = 3.2

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

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

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

A_i	B_j			u_i
A_i	b₁= 100	b₂= 80	b₃= 90	u_i
а₁= 80	12,5 80	24,0	18,4	u₁ = 0
а₂= 90	28,3	14,5 90	25,7 0	u₂ = 12,6
а₃= 100	15,7 20	20,6	16,3 80	u₃ = 3,2
v_j	v₁=12,5	v₂=1,9	v₃=13,1

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

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

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

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

F(x) = 12.5*80 + 14.5*90 + 15.7*20 + 16.3*80 = 3923

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

Завдання 2

математична модель екстремум транспортна задача

Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплексним методом і визначити оптимальний план іншої задачі. Оптимальні результати перевірити графічно.

Розв’язок

Розв’яжемо задачу лінійного програмування симплексним методом.

Визначимо максимальне значення цільової функції F(X) = 3x₁+x₂ за таких умов-обмежень.

-2x₁+6x₂≤2

4x₁-3x₂≤12

x₁-x₂≥3

Для побудови першого опорного плану систему нерівностей наведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми).

-2x₁ + 6x₂ + 1x₃ + 0x₄ + 0x₅ = 2

4x₁-3x₂ + 0x₃ + 1x₄ + 0x₅ = 12

1x₁-1x₂ + 0x₃ + 0x₄-1x₅ = 3

Введемо штучні змінні x.

-2x₁ + 6x₂ + 1x₃ + 0x₄ + 0x₅ + 0x₆ = 2

4x₁-3x₂ + 0x₃ + 1x₄ + 0x₅ + 0x₆ = 12

1x₁-1x₂ + 0x₃ + 0x₄-1x₅ + 1x₆ = 3

Для постановки завдання на максимум цільову функцію запишемо так:

F(X) = 3x₁+x₂ - Mx₆ =>max

Отриманий базис називається штучним, а метод рішення називається методом штучного базису.

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