Оптимізація економічних показників
Контрольная работа - Экономика
Другие контрольные работы по предмету Экономика
БазисВx1x2x3x4x5x6min2x3488610006x45-12010-10x5124100103ІндекснийрядокF(X2)01-2000-1000000
Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться позитивні коефіцієнти. Враховуючи вказане будуємо новий план здійснивши відповідні розрахунки. У якості ведучого виберемо стовпець, відповідної змінної x1, так як найбільший коефіцієнт за модулем.
ПланБазисВx1x2x3x4x5x6min3x3240410-206x4802.25010.25-10x1310.25000.2503ІндекснийрядокF(X3)-30-2.2500-0.25-1000000
Остаточний варіант симплекс-таблиці оптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
Оптимальний план можна записати так:
x3 = 24
x4 = 8
x1 = 3
F(X) = -1*3 = -3
Визначаємо оптимальний план двоїстої задачі до поставленої задачі лінійного програмування.
F(Y) = -48Y1-5Y2+12Y3 (max)
Обмеження:
-8Y1+1Y2+4Y3?-1
-6Y1-2Y2+1Y3?2
Y1?0
Y2?0
Y3?0
лінійний програмування транспортна задача
Оскільки, у правій частині присутні відємні значення, перемножимо відповідні строки на (-1).
Визначимо максимальне значення цільової функції
F(X) = -48x1-5x2+12x3 при наступних обмеженнях:
8x1-x2-4x3?1
-6x1-2x2+x3?2
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
8x1-1x2-4x3-1x4 + 0x5 = 1
-6x1-2x2 + 1x3 + 0x4 + 1x5 = 2
Введемо штучні змінні х.
8x1-1x2-4x3-1x4 + 0x5 + 1x6 = 1
-6x1-2x2 + 1x3 + 0x4 + 1x5 + 0x6 = 2
Задачу на максимум цільову функцію запишемо так:
F(X) = -48x1-5x2+12x3 - Mx6 =>max
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,0,0,2,1)
ПланБазисВx1x2x3x4x5x60x618-1-4-101x52-6-21010ІндекснийрядокF(X0)0000000
Перейдемо до основного алгоритму симплекс-метода.
ПланБазисВx1x2x3x4x5x6min1x618-1-4-1010.125x52-6-210100ІндекснийрядокF(X1)00000000
ПланБазисВx1x2x3x4x5x62x10.1251-0.125-0.5-0.12500.125x52.750-2.75-2-0.7510.75ІндекснийрядокF(X2)0000000
Оптимальний план можливо записати так:
x1 = 0.125
x5 = 2.75
F(X) = -48*0.13 = -6
Завдання 3
Розвязати транспортну задачу.
147812002314115051323350120130200180110
Розвязок
Побудова математичної моделі. Нехай xij кількість продукції, що перевозиться з і-го пункту виробництва до j-го споживача . Оскільки , то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби:
У нашому випадку робиться це введенням фіктивного постачальника, оскільки .З уведенням фіктивного постачальника в транспортній таблиці додатково заявляється n робочих клітинок (додатковий рядок).
Виникає проблема, які ціни присвоїти цим клітинкам, щоб фіктивний рядок був нейтральним щодо оптимального вибору планових перевезень. Нейтральність забезпечується тим, що всі ціни у фіктивних клітинках вибираються однаковими, а оскільки ці ціни при поставках не повинні впливати на значення цільової функції f, то їх беруть усі рівними нулю.
Занесемо вихідні дані у таблицю.
В1В2В3В4В5ЗапасиА114781200А223141150А351323350А40000040Потреби120130200180110
Забезпечивши закритість розвязуваної задачі, розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, повязані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
minZ = 1x11 + 4x12 + 7x13 + 8x14 +1x15 + 2x21 + 3x22 + 1x23 + 4x24 +1x25 +5x31 + 1x32 + 3x33 + 2x34 +3x35 + 0x41+ 0x42 + 0x43 + 0x44+0x45.
Загалом математична модель сформульованої задачі має вигляд:
minZ = 1x11 + 4x12 + 7x13 + 8x14 +1x15 + 2x21 + 3x22 + 1x23 + 4x24 +1x25 +5x31 + 1x32 + 3x33 + 2x34 +3x35 + 0x41+ 0x42 + 0x43 + 0x44+0x45.
за умов:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом північно-західного кута.
AiBjuib1 = 120b2 = 130b3 = 200b4=180b5=110а1 = 2001
1204
807
8
1
u1 = 0а2 = 15023
501
1004
1
u2 = -1а3 = 350513
1002
1803
70u3 = 1а4 = 4000000
40u4 = -2vjv1 =1v2 =4v3 =2v4 =1V5 =2
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі:
Z1 = 1 120 + 4 80 + 3 50 + 1 100 + 3 100+ 2 180 + 3 70 + 0 40 = 1560
Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є невироджених.
Перевіримо оптимальність опорного плану, складемо систему рівнянь (для заповнених клітин таблиці) для визначення потенціалів першого опорного плану:
Записана система рівнянь є невизначеною, і один з її розвязків дістанемо, узявши, наприклад, u1 = 0. Тоді всі інші потенціали однозначно визначаються з цієї системи рівнянь: u1 =0, u2 = -1, u3 = 1, u4=-2, v1 =1, v2 =4, v3 =2 v4=1, v5=2. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ? cij(для порожніх клітинок таблиці):
А1B3 : u1 + v3 = 0 + 2 = 2 < 7;
А1B4 : u1 + v4 = 0 + 1 = 1 < 8;
А1B5 : u1 + v5 = 0 + 2 = 2 > 1;
А2B1 : u2 + v1 = -1 + 1 = 0 < 2;
А2B4 : u2 + v4 = -1 + 1 = 0 < 4;
А2B5 : u2 + v5 = -1 + 2 = 1 =1;
А3B1 : u3 + v1 = 1 + 1 = 2 < 5;
А3B2 : u3 + v2 = 1 + 4 = 5 > 1;
А4B1 : u4 + v1 = -2 + 1 = -1 < 0;
А4B2 : u4 + v2 = -2 + 4 = 2 > 0;
А4B3 : u4 + v3 = -2 + 2 = 0 = 0;
А4B4 : u4 + v4 = -2 + 1 = -1 < 0.
Опорний план не є оптимальним, тому що існую?/p>