Економіко-математичне програмування

На підприємстві виготовляються вироби двох видів А і В. Для цього використовується сировина чотирьох типів І, ІІ, ІІІ, ІV,

Економіко-математичне програмування

Контрольная работа

Экономика

Другие контрольные работы по предмету

Экономика

Сдать работу со 100% гаранией

Завдання 1

 

Побудувати математичну модель задачі.

На підприємстві виготовляються вироби двох видів А і В. Для цього використовується сировина чотирьох типів І, ІІ, ІІІ, ІV, запаси якої дорівнюють, відповідно, 21; 4; 6; 10 од. Для виготовлення одного виробу А необхідна така кількість одиниць сировини чотирьох видів: 2; 1; 0; 2. Для виробу В 3; 0; 1; 1 од. відповідно. Випуск одного виробу А дає 3 грн. од. прибутку, типу В 2 грн. од. Скласти план виробництва, який забезпечує найбільший прибуток.

 

СировинаНорма витрат сировини, одЗапаси сировини, од.АВІ2321ІІ104ІІІ016ІV2110Ціна, грн. од.32

Розвязок

 

Складаємо математичну модель задачі. Позначимо через х1 кількість виробів 1-ї моделі, що виготовляє підприємство за деяким планом, а через х2 кількість виробів 2-ї моделі. Тоді прибуток, отриманий підприємством від реалізації цих виробів, складає

∫ = 3х1+2х2.

Витрати сировини на виготовлення такої кількості виробів складають відповідно:

CI =2х1 + 3х2,

CII =1х1 + 0х2,

CIII =0х1 + 1х2,

CIV =2х1 + 1х2,

Оскільки запаси сировини обмежені, то повинні виконуватись нерівності:

2х1 + 3х2≤ 21

1х1≤ 4

1х2≤ 6

2х1 + 1х2≤ 10

Оскільки, кількість виробів є величина невід'ємна, то додатково повинні виконуватись ще нерівності: х1> 0, х2> 0.

Таким чином, приходимо до математичної моделі (задачі лінійного програмування):

Знайти х1 , х2 такі, що функція ∫ = 3х1+2х2досягає максимуму при системі обмежень:

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

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

2x1 + 3x2 + 1x3 + 0x4 + 0x5 + 0x6 = 21

1x1 + 0x2 + 0x3 + 0x4 + 0x5 + 1x6 = 4

0x1 + 1x2 + 0x3 + 1x4 + 0x5 + 0x6 = 6

2x1 + 1x2 + 0x3 + 0x4 + 1x5 + 0x6 = 10

де х1,...,х6>0

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

F(X) = 3 x1 +2 x2 - M x6 =>max

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

Складаємо симплекс-таблицю:

 

ПланБазисВx1x2x3x4x5x6min1x32123100010.5x641000014x460101000x5102100105Індексний рядокF(X1)-400000-100003-200000

Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1, оскільки значення коефіцієнта за модулем найбільше.

 

ПланБазисВx1x2x3x4x5x6min2x31303100-24.33x141000010x460101006x5201001-22Індексний рядокF(X2)120-20001000030

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

 

План Базис В x1 x2 x3 x4 x5 x6Min 3 x3 7 0 0 1 0 -3 4 4.33 x1 4 1 0 0 0 0 1 0 x4 4 0 0 0 1 -1 2 6 x2 2 0 1 0 0 1 -2 2Індексний рядокF(X3) 16 0 0 0 0 299999 0

Оскільки всі оцінки >0, то знайдено оптимальний план, що забезпечує максимальний прибуток: х1=4, х2=2. Прибуток, при випуску продукції за цим планом, становить 16 грн.

 

Завдання 2

 

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

 

Розвязок

 

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

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

2x1+4x2≥10

3x1+2x2≥11

4x1+7x2≤32

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

2x1 + 4x2-1x3 + 0x4 + 0x5 = 10

3x1 + 2x2 + 0x3-1x4 + 0x5 = 11

4x1 + 7x2 + 0x3 + 0x4 + 1x5 = 32

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

2x1 + 4x2-1x3 + 0x4 + 0x5 + 1x6 + 0x7 = 10

3x1 + 2x2 + 0x3-1x4 + 0x5 + 0x6 + 1x7 = 11

4x1 + 7x2 + 0x3 + 0x4 + 1x5 + 0x6 + 0x7 = 32

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

F(X) = 3x1+2x2+Mx6+Mx7 => min

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

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

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

З рівнянь висловлюємо штучні змінні:

x6 = 10-2x1-4x2+x3

x7 = 11-3x1-2x2+x4

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

F(X) = 3x1 + 2x2 + M(10-2x1-4x2+x3) + M(11-3x1-2x2+x4) => min

або

F(X) = (3-5M)x1+(2-6M)x2+(1M)x3+(1M)x4+(21M) => min

Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:

 

24-10010320-10014700100

Базисні перемінні це змінні, які входять тільки в одне рівняння системи обмежень і при тому з одиничним коефіцієнтом.

Вирішимо систему рівнянь відносно базисних змінних:

x6, x7, x5,

Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:

X1 = (0,0,0,0,32,10,11)

 

ПланБазисВx1x2x3x4x5x6x70x61024-10010x711320-1001x5324700100Індексний

рядокF(X0)21M-3+5M-2+6M-1M-1M000

Переходимо до основного алгоритму симплекс-методу.

 

ПланБазисВx1x2x3x4x5x6x7min1x61024-100102.5x711320-10015.5x53247001004.57Індексний

рядокF(X1)21M-3+5M-2+6M-1M-1M0000

Оскільки, в індексному рядку знаходяться позитивні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х2, оскільки значення коефіцієнта за модулем найбільше.

 

ПланБазисВx1x2x3x4x5x6x7min2x22.50.51-0.25000.2505x76200.5-10-0.513x514.50.501.7501-1.75029Індексний

рядокF(X2)5+6M-2+2M0-0.5+0.5M-1M00.5-1.5M00

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

ПланБазисВx1x2x3x4x5x6x73x2101-0.3750.2500.375-0.25x13100.25-0.50-0.250.5x513001.630.251-1.63-0.25Індексний

рядокF(X3)11000-10-1M1-1M

Остаточний варіант симплекс-таблиці оптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.

Оптимальний план можна записати так:

x2 = 1

x1 = 3

x5 = 13

F(X) = 3*3 + 2*1 = 11

Складемо двоїсту задачу до прямої задачі.

2y1+3y2+4y3≤3

4y1+2y2+7y3≤2

10y1+11y2+32y3 => max

y1 ≥ 0

y2 ≥ 0

y3 ≤ 0

Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів.

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

З першої теореми двоїстості випливає, що Y = C*A-1.

Складемо матрицю A з компонентів векторів, що входять в оптимальний базис.

 

Визначивши зворотну матрицю А-1черезалгебраїчнідоповнення, отримаємо:

 

Як видно з останнього плану симплексного таблиці, зворотна матриця A-1розташована в стовпцях додаткових змінних.

Тогда Y = C*A-1 =

 

Оптимальний план двоїстоїзадачідорівнює:

y1 = 0

y2 = 1

y3 = 0

Z(Y) = 10*0+11*1+32*0 = 11

 

Завдання 3

 

Розвязати транспортну задачу.

 

1421230022313903456770100207090180

Розвязок

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

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

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

 

В1В2В3В4В5ЗапасиА114212300А22231390А33456770Потреби100207090180

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

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

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

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

minZ=1x11+4x12+2x13+1x14+2x15+2x21+2x22+3x23+1x24+3x25+3x31+4x32+5x33+6x34+ +7x35.

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

minZ=1x11+4x12+2x13+1x14+2x15+2x21+2x22+3x23+1x24+3x25+3x31+4x

Похожие работы

1 2 >