Математичне програмування
Контрольная работа - Экономика
Другие контрольные работы по предмету Экономика
виберемо елемент у стовбці х2.
План Базис В x1 x2 x3 x4 x5 x6 3 x3 2 0 0 1 -0.6667 0.3333 -0.3333 x2 0 0 1 0 0.3333 0.3333 -0.3333 x1 2 1 0 0 -0.1667 -0.6667 0.6667Індексний рядок F(X3) 2 0 0 0 0.5 0 1MОстаточний варіант симплекс-таблиці оптимальний, тому що в індексному рядку знаходяться позитивні коефіцієнти.
Оптимальний план можна записати так:
x3 = 2
x2 = 0
x1 = 2
F(X) = 1*2 + 2*0 = 2
Складемо двоїсту задачу до прямої задачі.
2y1+2y2+2y3?1
3y1+4y2+y3?2
6y1+4y2+4y3 => min
y1 ? 0
y2 ? 0
y3 ? 0
Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів.
Використовуючи останню ітерацію прямої задачі знайдемо, оптимальний план двоїстої задачі.
З першої теореми двоїстості випливає, що Y = C*A-1.
Складемо матрицю A з компонентів векторів, що входять в оптимальний базис.
Визначивши зворотну матрицю А-1 через алгебраїчні доповнення, отримаємо:
Як видно з останнього плану симплексного таблиці, зворотна матриця A-1 розташована в стовпцях додаткових змінних .
Тоді Y = C*A-1 =
Оптимальний план двоїстої задачі дорівнює:
y1 = 0
y2 = 0.5
y3 = 0
Z(Y) = 6*0+4*0.5+4*0 = 2
Завдання 3
Розвязати транспортну задачу.
523611501144232041235400100120100200300
Розвязок
Побудова математичної моделі. Нехай xij кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача . Оскільки , то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби:
У нашому випадку робиться це введенням фіктивного постачальника, оскільки . З уведенням фіктивного споживача транспортній таблиці додатково заявляється n робочих клітинок.
Ціни, додатковим клітинкам, щоб фіктивний стовбець був нейтральним щодо оптимального вибору планових перевезень, призначаються усі рівні нулю.
Занесемо вихідні дані у таблицю.
В1В2В3В4В5В6ЗапасиА1523610150А2114420320А3412350400Потреби10012010020030050
Забезпечивши закритість розвязуваної задачі, розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, повязані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
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.
за умов:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом північно-західного кута.
AiBjuib1 = 100b2 = 120b3 = 100b4=200b5=300b6=50а1 = 1505
1002
[-] 50361
[+]0u1 = 0 а2 = 32011
[+] 704
1004
[-] 15020u2 = -1а3 = 4004123
[+] 505
[-] 3000
50u3 = -2vjv1 = 5v2 = 2v3 = 5v4 = 5v5 = 7v6 = 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 додаємо до відповідних чисел, що розміщені в клітинках зі знаком +, та віднімаємо від чисел, що розміщені в клітинках, позначених знаком .
Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати