иду продукції, запас bi відповідного виду сировини і прибуток cj від реалізації одиниці j-го виду продукції задані таблицею:
Таблиця 1
Види сирьяВіди продукцііЗапаси сирьяIIIA2220B1110C2636прібиль74план (од.) x 1 x 2
1. Для виробництва двох видів продукції I і II з планом x 1 і x 2 одиниць скласти математичну модель, тобто цільову функцію прибутку F і відповідну систему обмежень щодо запасів сировини, припускаючи, що потрібно виготовити в сумі не менше n одиниць обох видів продукції.
2. Знайти оптимальний план X *=(x 1, x 2) виробництва продукції, що забезпечує максимальний прибуток F max. Визначити залишки кожного виду сировини. Завдання вирішити симплекс-методом.
. Побудувати по отриманій системі обмежень багатокутник допустимих рішень і знайти оптимальний план виробництва геометричним методом. Визначити максимальний прибуток F max.
. Скласти математичну модель двоїстої задачі (систему обмежень за одиничною прибутку і цільову функцію загальних витрат на сировину Z); знайти оптимальний набір цін на сировину Y *=(y 1, y 2, y 3), що забезпечує мінімум загальних витрат на сировину Z min.
. Провести аналіз первинних і додаткових змінних вихідної і двоїстої задач, зробити висновки.
. Вирішити завдання оптимізації в MS Excel в режимі «пошук рішення». Провести дослідження отриманого рішення, використовуючи звіти за результатами, по стійкості, по межам; зробити висновки. Відповіді, отримані в результаті рішень «вручну» і за допомогою Excel, повинні збігатися.
Рішення:
Припустимо, що буде використано х 1 сировини А для виготовлення продукції I, х 2 сировини для виробу II. Тоді загальний прибуток складе 7х 1 + 4х 2.
Так як загальна кількість сировини А не може перевищувати 27 одиниць, то повинно виконуватися наступне нерівність:
х 1 + 2х 2? 20.
Аналогічні міркування щодо можливо використання решти кількості сировини приведуть до слідуючи нерівностей:
х 1 + х 2? 10;
х 1 + 6х 2? 36.
При цьому, так як кількість виготовлених виробів не може бути негативним, то:
х 1? 0, х 2? 0 (1)
Нехай F - прибуток підприємства, так як за умовою необхідно скласти план виробництва двох видів виробів, що забезпечує максимальний прибуток, отже, функція F, за умови, що виготовлено х 1 одиниць виробів I і х 2 одиниць виробів II буде максимизироваться:
F=7х 1 + 4х 2? max
Таким чином, ми приходимо до наступної математичної задачі:
Дана система:
(2)
трьох лінійних нерівностей з двома невідомими хi (i=1,2). І лінійна функція відносно цих же змінних:
=7х1 + 4х2 (3)
потрібно серед всіх невід'ємних рішень системи нерівностей (2), знайти таке, при якому функція (3) прийме максимальне значення.
Знайдемо рішення сформульованої задачі, використовуючи її геометричну інтерпретацію. Спочатку визначимо багатокутник рішень. Для цього в нерівностях системи обмежень і умов не заперечності змінних знаки нерівностей замінимо на знаки точних рівностей і знайдемо відповідні прямі.
Прямі S1 - S3, зображені на малюнку 4.
Кожна з побудованих прямих ділить площину на дві півплощини. Координати точок одній півплощині задовольняють вихідного нерівності, а інший - ні. Визначимо шукану напівплощина через точку О (0; 0).
Припинення отриманих площин визначає багатокутник рішень даної задачі.
Малюнок 4 - Багатокутник рішень
Як видно з малюнка 4, багатокутником рішень є чотирикутник ОАВС.
Таким чином, серед точок чотирикутника ОАВС нам потрібно знайти такі, в яких функція F=7х1 + 4х2 приймає максимальне значення. Для знаходження цих точок побудуємо нульову лінію рівня (F0) 7х1 + 4х2=0 і вектор N=(7; 4).
Пересуваючи дану пряму паралельно самій собі в напрямку вектора N, бачимо, що її останньою крапкою з багатокутником рішень задачі є точка C. Отже, в цій точці функція F приймає максимальне значення. Координати точки С:
х1=10 і х2=0.
Таким чином, максимальне значення функції Fmax=7 * 10 + 4 * 0=70 + 0=70.
Рішення симплекс-методом
Математична модель задачі:
х1, х2? 0
F=7х1 + 4х2
Запишемо цю задачу у формі основної задачі ЛП:
Для цього перейдемо від обмежень нерівностей - до обмежень равенствам.
Введемо 3 додаткові змінні, в результаті чого обмеження запишуться у вигляді систем обмежень...
