Методика економіко-математичного програмування
Контрольная работа - Экономика
Другие контрольные работы по предмету Экономика
?торів, які входять в оптимальний базис.
Визначивши обернену матрицю А-1 через алгебраїчне доповнення, отримаємо:
Як видно із останнього плану симплексної таблиці, обернена матриця A-1 розміщена у стовбцях додаткових змінних.
Тоді Y = C*A-1 =
Запишемо оптимальний план двоїстої задачі:
y1 = 0.11
y2 = 0
y3 = 0
Z(Y) = 45*0.11+42*0+4*0 = 5
Завдання 3
Розвязати транспортну задачу.
147912502312430021314150110801009070
Розвязок
Побудова математичної моделі. Нехай xij кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача . Оскільки , то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби:
У нашому випадку робиться це введенням фіктивного постачальника, оскільки . З уведенням фіктивного споживача транспортній таблиці додатково заявляється n робочих клітинок.
Ціни, додатковим клітинкам, щоб фіктивний стовбець був нейтральним щодо оптимального вибору планових перевезень, призначаються усі рівні нулю.
Занесемо вихідні дані у таблицю.
В1В2В3В4В5В6ЗапасиА1147910250А2231240300А3213140150Потреби110801009070250
Забезпечивши закритість розвязуваної задачі, розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, повязані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
minZ=1x11+4x12+7x13+9x14+1x15+0x16+2x21+3x22+1x23+2x24+4x25+0x26+2x31+1x32+3x33+1x34+ +4x35+0x36.
Загалом математична модель сформульованої задачі має вигляд:
minZ=1x11+4x12+7x13+9x14+1x15+0x16+2x21+3x22+1x23+2x24+4x25+0x26+2x31+1x32+3x33+1x34+ +4x35+0x36.
за умов:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом північно-західного кута.
AiBjuib1 = 110b2 = 80b3 = 100b4=90b5=70b6=250а1 = 2501
1104
807
[-]609
1
[+]0
u1 = 0а2 = 3002
3
1
[+]402
904
[-]700
100u2 = -6а3 = 1502
1
3
1
4
0
150u3 = -6vjv1 =1v2 =4v3 =7v4 =8v5 =10v6 =6
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є не виродженим.
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0:
u1=0, u2=-6, u3=-6, v1=1, v2=4, v3=7v4=8, v5=10, v6=6. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui+vj?cij(для порожніх клітинок таблиці).
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(1;5): 0 + 10 > 1
(1;6): 0 + 6 > 0
(3;4): -6 + 8 > 1
Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (А1B5): 1. Для цього в перспективну клітку (1;5) поставимо знак +, а в інших вершинах багатокутника чергуються знаки -, +, -. Цикл наведено в таблиці.
Тепер необхідно перемістити продукцію в межах побудованого циклу. З вантажів хij що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (1;3) = 60. Додаємо 60 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 60 з хij, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Для цього у порожню клітинку А1B5 переносимо менше з чисел хij, які розміщені в клітинках зі знаком . Одночасно це саме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком +, та віднімаємо від чисел, що розміщені в клітинках, позначених знаком .
Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n+m 1).
Отже, другий опорний план транспортної задачі матиме такий вигляд:
AiBjuib1 = 110b2 = 80b3 = 100b4=90b5=70b6=250а1 = 2501
1104
[-]807
9
1
[+]600
u1 = 0а2 = 3002
3
1
1002
904
[-]100
[+]100u2 = 3а3 = 1502
1
[+]3
1
4
0
[-]150u3 = 3vjv1 =1v2 =4v3 =-2v4 =-1v5 =1v6 =-3
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui, vi. по зайнятих клітинам таблиці, в яких ui + vi = cij, вважаючи, що u1 = 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi>cij
(2;1): 3 + 1 > 2
(2;2): 3 + 4 > 3
(3;1): 3 + 1 > 2
(3;2): 3 + 4 > 1
(3;4): 3 + -1 > 1
Вибираємо максимальну оцінку ?/p>