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

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

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

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

Экономика

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

Экономика

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

Завдання 1

 

Для виготовлення виробів №1 і №2 є 100 кг металу. На виготовлення виробу №1 витрачається 2 кг металу, а на виріб №2 4 кг.

Скласти план виробництва, що забезпечує одержання найбільшого прибутку від продажу виробів, якщо відпускна вартість одного виробу №1 становить 3 грн. од., а виробу №2 2 грн. од., причому виробів №1 потрібно виготовити не більше 40 штук, а виробів №2 20 шт.

 

СировинаВиробиКількість сировиниВ1В2Метал24100Вартість, грн. кг32

Розвязок

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

 

∫ = 3х1+2х2.

 

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

 

CI =2х1+4х2,

 

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

 

2х1+4х2≤100

Окрім того, виробів №1 потрібно виготовити не більше 40 штук, а виробів №2 20 шт., тобто повинні виконуватись ще нерівності: х1≤40, х2≤20.

Таким чином, приходимо до математичної моделі:

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

 

 

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

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

 

2x1 + 4x2 + 1x3 + 0x4 + 0x5 = 100

1x1 + 0x2 + 0x3 + 1x4 + 0x5 = 40

0x1 + 1x2 + 0x3 + 0x4 + 1x5 = 20

 

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

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

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

x3, x4, x5

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

X1 = (0,0,100,40,20)

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

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

 

ПланБазисВx1x2x3x4x5min1x31002410050x4401001040x520010010Індексний рядокF(X1)0-3-20000

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

 

ПланБазисВx1x2x3x4x5min2x320041-205x140100100x5200100120Індексний рядокF(X2)1200-20300

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

 

ПланБазисВx1x2x3x4x5min3x25010,25-0,505x140100100x51500-0,250,5120Індексний рядокF(X3)130000,5200

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

 

Завдання 2

 

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

 

 

Розвязок

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

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

 

9x1+10x2≥45

5x1-x2≤42

-x1+13x2≤4

 

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

 

9x1 + 10x2-1x3 + 0x4 + 0x5 = 45

5x1-1x2 + 0x3 + 1x4 + 0x5 = 42

-1x1 + 13x2 + 0x3 + 0x4 + 1x5 = 4

 

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

 

9x1 + 10x2-1x3 + 0x4 + 0x5 + 1x6 = 45

5x1-1x2 + 0x3 + 1x4 + 0x5 + 0x6 = 42

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

 

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

 

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

 

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

X1 = (0,0,0,42,4,45).

 

ПланБазисВx1x2x3x4x5х60х645910-1001x4425-10100х54-1130010Індексний рядокF(X0)0000000

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

 

ПланБазисВx1x2x3x4x5x6min1х645910-10015,5x4425-101000х54-11300100,3077Індексний рядокF(X1)00000000

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

 

ПланБазисВx1x2x3x4x5x6min2х641,929,770-10-0,769214,29x442,314,920010,076908,59х20,3077-0,07691000,076900Індексний рядокF(X2)00000000

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

 

ПланБазисВx1x2x3x4x5x6min3х14,2910-0,10240-0,07870,10240x421,18000,503910,4646-0,503945,59х20,637801-0,007900,07090,00799Індексний рядокF(X3)00000000

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

 

ПланБазисВx1x2x3x4x5x64х1511,11-0,1111000,1111x4170-6,560,555610-0,5556х59014,11-0,1111010,1111Індексний рядокF(X4)0000000

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

x1 = 5

x4 = 17

x5 = 9

F(X) = 1*5 = 5

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

 

9y1+5y2-y3≤1

10y1-y2+13y3≤3

45y1+42y2+4y3 => max

y1 ≥ 0

y2 ≤ 0

y3 ≤ 0

 

Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів. Використовуючи останню інтеграцію прямої задачі знайдемо, оптимальний план двоїстої задачі. Із теореми двоїстості слідує, що Y = C*A-1.

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

Визначивши обернену матрицю А-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 2 >