Mt_ЕММ_lab_MK. Методичні вказівки до виконання лабораторних робіт для студентів першого (бакалаврського) рівня вищої освіти
 Скачать 3.77 Mb.
|
|
ЛАБОРАТОРНА РОБОТА №9 ПОБУДОВА ЛІНІЙНОЇ МОДЕЛІ ОПТИМІЗАЦІЙНОЇ ЗАДАЧІ ТА ЇЇ АНАЛІЗ І. Загальні положення Загальною формою задачі лінійного програмування є задача на знаходження екстремуму (мінімуму чи максимуму) лінійної цільової функції при лінійній системі обмежень, що включає як рівності, так і нерівності обох знаків, і при невідомих змінних, з яких одні пов’язані умовою невід’ємності, другі – умовою недодатності, а на знак третіх ніяких умов не накладено. ІІ. Теоретичні відомості За допомогою задачі лінійного програмування можна вирішити багато задач оптимізації, зокрема задачу про раціональне використання наявних ресурсів. У загальному вигляді задача може бути сформульована таким чином. Припустимо, підприємство може випускати n видів продукції, використовуючи m видів ресурсів. При цьому відомі запаси кожного і-того виду ресурсу (  ), витрати кожного виду ресурсу на випуск кожного j-го виду продукції ( ) та прибуток, що отримується з одиниці випущеної продукції ( ). Мета задачі полягає у тому, щоб скласти такий план виробництва продукції ( ), при якому отриманий підприємством прибуток від виробництва Z був би найбільшим.Отже, математична модель задачі полягає в тому, щоб знайти виробничу програму, що максимізує цільову функцію (функцію мети)  . (9.1)При цьому, яка б не була виробнича програма, її компоненти повинні задовольняти умові, що сумарне використання кожного виду ресурсу при виробництві всіх видів продукції не повинно перевищувати наявну кількість даного виду ресурсу, тобто  ; (9.2) . (9.3)На значення  можуть бути додатково накладені обмеження стосовно обсягів виробництва ; (9.4) . (9.5)При цьому, оскільки компоненти виробничої програми – кількість виробів, то вони не можуть бути виражені від’ємними значеннями  . (9.6)Для аналізу стійкості важливим є діапазон зміни параметрів, в яких оптимальне рішення залишається оптимальним. У процесі пошуку оптимального рішення можна отримати так званий звіт про стійкість, у якому містяться межі коефіцієнтів цільової функції. Зміна коефіцієнтів в цих межах не призводить до зміни оптимального рішення. Аналогічні інтервали встановлюються для запасів ресурсів. При виході за визначені межі стійкості оптимальне рішення може мінятися як за номенклатурою продукції, що випускається, так і за обсягами випуску (без зміни номенклатури). Двоїстою до основної задачі (9.1) – (9.6) називається така задача: знайти сукупність значень y1, y2,…, ym, для яких функція  (9.7)досягає мінімуму і задовольняє систему нерівностей:  ; (9.8) ; (9.9) . (9.10)Багато задач лінійного програмування ставляться у вигляді основної або двоїстої задачі, тому є сенс говорити про пару двоїстих задач лінійного програмування. Якщо одна з пари двоїстих задач має розв’язок (тобто оптимальний план), то і друга – обов’язково має розв’язок, причому: max Z = min W. (9.11) Для побудови двоїстої задачі необхідно основну задачу звести до стандартного вигляду, враховуючи тип екстремуму цільової функції. Побудова двоїстої задачі до основної здійснюється в послідовності: І. Стандартизація основної задачі: 1) у всіх обмеженнях вільні члени розміщені в правій частині рівності (нерівності), а члени з невідомим – у лівій; 2) усі обмеження нерівності основної задачі мають бути записані так, щоб знаки нерівності у них були спрямовані в один і той самий бік, для цього достатньо окремі нерівності помножити на (-1); 3) загальний знак нерівності системи обмежень пов’язується з оптимізацією форми таким чином: якщо max, то  , якщо min, то  .Після стандартизації основної задачі виконується послідовність, спрямованих на формування задачі обмежень (пункт ІІ) та цільової функції (пункт ІІІ) двоїстої задачі. ІІ. При побудові системи обмежень двоїстої задачі слід дотримуватися таких правил: 1) кожному обмеженню вихідної задачі відповідає невідома уі в двоїстій задачі, причому двоїста невідома, що відповідає обмеженню нерівності має бути невід’ємною, а рівності можуть мати будь-який знак; 2) кожній невідомій хі вихідної задачі відповідає обмеження двоїстої. Ці обмеження будують так: множать коефіцієнти aij, що стоять при хі, на відповідні двоїсті невідомі уі, результати множення додають і ставлять у ліву частину обмежень, а в праву – коефіцієнт при хі в оптимізуючій формі сі; 3) у всіх обмеженнях двоїстої задачі ставлять один і той же знак нерівності, протилежний загальному знаку нерівності системи обмежень вихідної задачі. ІІІ. Для оптимізуючої форми двоїстої задачі мають задовольнятися умови: 1) форма W двоїстої задачі оптимізується у протилежному значенні (якщо Z  max, то W min, і навпаки);2) коефіцієнтами при двоїстих невідомих у формі W є відповідні вільні елементи системи обмежень вихідної задачі. Вільний елемент с0 форми Z переноситься без змін у форму W. Оптимальне значення кожної змінної двоїстої задачі визначає позитивний або негативний приріст значення цільової функції за рахунок одиничного приросту (позитивного чи негативного) значення константи в правій частині відповідного обмеження. Оптимальні значення змінних двоїстої задачі називають прихованими доходами або тіньовими цінами. Якщо константи в правих частинах обмежень задають обсяги наявних ресурсів, приховані доходи визначають внесок у прибуток, отриманий за рахунок одиниці кожного з ресурсів, відповідно до виду оптимального рішення прямої задачі. Коефіцієнти aij інтерпретуються як відповідні норми споживання і-го ресурсу в j-му виробничому процесі. Сумою  задається економічний ефект за рахунок j-го виробничо-технологічного процесу, обчислений з урахуванням прихованого доходу.ІІІ. Завдання ПП "Фаворит" виготовляє широкий асортимент копчених та варених ковбасних виробів (табл. 9.1). Таблиця 9.1 Ціни на ковбасні вироби ПП "Фаворит"
Для виготовлення ковбасних виробів необхідно м'ясо свине та волове, сало, спеції, харчові добавки. Витрати ресурсів подані в табл. 9.2. Таблиця 9.2 Витрати ресурсів на 1 кг готової продукції, кг
Продовження табл. 9.2
Щомісячно ПП "Фаворит" закуповує певну кількість ресурсів (табл. 9.3). Таблиця 9.3 Ресурси для виробництва продукції
При виробництві ковбасних виробів необхідно врахувати, що на постачання деяких видів укладені договори із організаціями-споживачами (табл. 9.4) Таблиця 9.4 Необхідна кількість деяких видів продукції згідно договорів
та попит на кожен вид продукції не перевищує 6000 кг. Необхідно: побудувати задачу лінійного програмування; визначити оптимальний план виробництва продукції; проаналізувати стійкість задачі; побудувати двоїсту задачу лінійного програмування. |