![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Розв’язання задач лінійного програмування графічним методомСтр 1 из 8Следующая ⇒
Вступ На практиці для випуску асортименту своєї продукції виробничі підприємства мають у своєму розпорядженні деякий запас, як правило, обмежених ресурсів (сировинних, трудових, енергетичних, паливних, грошових), деякий набір взаємозамінних технологій, устаткування і т.п. Транспортна фірма, що здійснює постачання від підприємств-виробників до замовників-споживачів, має можливість вибору в розподілі вантажу. Економіст або менеджер повинен скласти такий план випуску продукції, при якому досягається найкращий (оптимальний) результат: або підприємство максимізує прибуток, або максимізує випуск продукції, або мінімізує витрати на випуск продукції, або мінімізує виробничі відходи і т.п. Методи розв’язування подібних завдань вивчаються студентами ВНЗ у дисципліні «Економіко-математичне моделювання», зокрема в її першій частині - математичному програмуванні. Найбільш поширеним є клас задач лінійного програмування (ЗЛП); розгляду методів розв’язання деяких із них присвячені дані методичні вказівки. Спочатку вивчається графічний метод розв’язання ЗЛП, що дозволяє наочно представити як суть математичної постановки задачі, так і її результат. Потім вивчається розв’язання задачі з використанням убудованого в Microsoft EXCEL for WINDOWS інструмента «Поиск решения». Цей інструмент дозволяє розв’язувати більш складні задачі не тільки лінійного програмування. Традиційний симплексний метод розв’язання ЗЛП дозволяє одержати багато результатів, корисних для економічного аналізу рентабельності випуску окремих видів продукції, аналізу дефіцитності ресурсів, що використовуються, їхньої взаємозамінності. Однак цей метод досить трудомісткий. Вирішити цю проблему дозволяє Microsoft EXCEL із своєю вбудованою можливістю модифікації формул. Також вивчається розв’язання транспортної задачі, модель якої лінійна, однак розв’язання цієї задачі симплексним методом є досить трудомістким. Для розв’язання цієї задачі розроблений зручний і наочний метод потенціалів, що став класичним. Крім цього методу, розглянуто розв’язок транспортної задачі з використанням інструмента «Поиск решения». МЕТОДИ РОЗВ’ЯЗУВАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ ЗАВДАННЯ 1. Побудувати математичну модель економічної задачі. Розв’язати задачу за допомогою побудованої моделі
Зробити висновки в термінах постановки задачі. Розв’язання задач лінійного програмування графічним методом Розберемо розв’язок однієї задачі оптимального виробничого планування (або задачі про використання ресурсів). Змістовна постановка задачі. Для виготовлення взуття двох моделей на фабриці використовується два сорти шкіри. Тижневі ресурси робочої сили і матеріалу, витрати праці і матеріалу для виготовлення кожної пари взуття, а також прибуток від реалізації одиниці продукції наведені в таблиці.
Скласти план випуску взуття в асортименті, що максимізує щотижневий прибуток. Розв’язання. Спочатку складемо математичну модель поставленої задачі. Вона містить у собі змінні задачі, цільову функцію і систему обмежень. Змінні задачі. Оскільки в задачі потрібно скласти тижневий план випуску взуття, то змінними задачі є:
Цільова функція задачі. Оскільки прибуток від випуску 1 пари взуття моделі №1 складає 50 грн., а моделі №2 – 70 грн., то загальний тижневий прибуток від випуску
Система обмежень задачі. З урахуванням наведених у таблиці даних можна скласти такі обмеження у вигляді нерівностей.
Якщо обидві частини останньої нерівності поділити на 3, то одержимо: .
Таким чином, математична модель задачі має вигляд:
Математична модель виражається через дві змінні, тому для розв’язання задачі можна застосовувати графічний метод. На координатній площині Спочатку зауважимо, що система обмежень містить нерівності
Для цього знайдемо по дві пари точок, через які проходить кожна з цих прямих: 1. 2. 3. Ці прямі з відповідними мітками зображені на рис. 1.1. Множина точок, які задовольняють нерівності
Тепер зобразимо вектор
Для зображення цього вектора з'єднуємо спрямованим відрізком точки з координатами (0, 0) і (500, 700). Довільна лінія рівня цільової функції (L) проходить перпендикулярно до вектора Для пошуку точки області припустимих розв’язків, у якій цільова функція досягає свого максимуму (мінімуму), необхідно лінію рівня пересувати в напрямку вектора градієнта (відповідно у зворотному напрямку). Крайня точка
Із першого рівняння виразимо
Потім підставимо знайдений вираз у друге рівняння:
звідки одержимо Знаючи
У результаті дійдемо висновку, що
Відповідь. Для одержання максимального тижневого прибутку, що складає 34200 грн., фабрика повинна випускати 180 пар взуття моделі №1 і 360 пар взуття моделі №2 за тиждень. 1.2 Розв’язання задач лінійного програмування за допомогою інструмента “Поиск решения” Відповідно до математичної моделі поставленої задачі підготуємо аркуш EXCEL для застосування інструмента «Поиск решения» (див. рис. 1.2):
Внесемо формули, помітивши, що значення цільової функції (комірка D3) дорівнює сумі добутків невідомих значень змінних (комірки В2: С2) на коефіцієнти цільової функції (комірки В3: D3), а значення лівих частин системи обмежень (комірки D5, D6 і D7) дорівнюють сумі добутків невідомих значень змінних (комірки В2: С2) на коефіцієнти лівих частин системи обмежень (комірки В5: С5, В6: С6, В7: С7 відповідно). Для цього в цільову комірку D3 вносимо формулу СУММПРОИЗВ($B$2; $C$2; B3; C3), яку копіюємо в комірки D5, D6 і D7 з модифікаціями. Для внесення в комірку D3 зазначених формул необхідно
Після копіювання формул у комірки D5, D6 і D7 вони будуть модифіковані так, як показано на рис. 1.5.
Якщо перелік процедур «Сервис» у меню Microsoft EXEL не містить інструмент «Поиск решения», то для додавання цього інструмента в перелік необхідно виконати такі дії: 1) натиснути «Сервис», потім «Надстройки» (рис. 1.6 а); 2) в екранній формі, що з'явилася, відмітити «Поиск решения» (рис. 1.6, б).
У результаті пророблених операцій аркуш EXEL готовий для запуску процедури «Поиск решения». Вибираємо в “Сервис” процедуру “Поиск решения” (див. рис. 1.7).
В екранній формі «Поиск решения» (див. рис 1.8) 1) установлюємо цільову комірку $D$3, відзначаючи її на аркуші EXEL; 2) відзначаємо прапорцем тип оптимізації, виходячи з умов задачі: у даному випадку – це максимізація; 3) переводимо курсор в «Изменяя ячейки» і виділяємо на аркуші EXEL комірки $В$2: $С$2, що відповідають зарезервованим значенням змінних; 4) переводимо курсор в «Ограничения», натискаємо «Добавить»;
5) в екранній формі «Добавление ограничений» (рис. 1.9) а) робимо посилання на комірки (шляхом їхнього виділення на аркуші EXEL), що відповідають лівим частинам системи обмежень $D$5: $D$7; ці комірки містять результат обчислень відповідно до введених раніше формул; б) установлюємо знак, що відповідає знаку нерівності системи обмежень: у даному випадку це «< =»; якщо не всі обмеження мають однаковий знак, то, розташувавши поруч нерівності одного знака, програмують окремо кожну з груп, що утворилися; в) переводимо курсор в «Ограничения», посилаючись на комірки, що відповідають правим частинам системи обмежень $F$5: $F$7, виділяючи їх на аркуші EXEL; г) натискання «ОК» повертає нас в екранну форму «Поиск решения»; 6) натискаємо «Параметри», в екранній формі, що з'явилася, (рис. 1.10) відмічаємо прапорцями «Линейная модель» і «Неотрицательные значения», після чого натискання «ОК» повертає нас до екранної форми «Поиск решения»; 7) натискаємо «Выполнить», у результаті чого (рис. 1.11) на аркуші EXEL у комірках В2: С2 висвічуються шукані значення оптимальних змінних (оптимальний план), у комірці D3 значення цільової функції на оптимальному плані, а в екранній формі, що з'явилися, «Результаты поиска решения», пропонується зробити один з видів звіту, з яких вибираємо звіт по стійкості і натискаємо «ОК». Аркуш «Отчет по устойчивости» представлений на рис. 1.12.
|