Дата конвертації12.12.2019
Розмір46.7 Kb.
Типкурсова робота

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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Білоруський національний технічний університет

Факультет технологій управління і гуманітаризації

Кафедра «Менеджмент»

Розрахунково-графічна робота з дисципліни

«Економіко-математичні методи і моделі»

Тема розрахунково-графічної роботи:

«Рішення оптимізаційних управлінських завдань на основі

методів і моделей лінійного програмування »

Варіант № 17

виконавець:

студент (ка) групи 108158

Ядревская Юлія Сергіївна

керівник:

Калачова Тетяна Олександрівна

Мінськ 2009


ЗМІСТ

ВСТУП

1. Постановка задачі ОПЕРАЦІЙНОГО ДОСЛІДЖЕННЯ

2. Побудова БАЗОВОЇ АНАЛІТИЧНОЇ МОДЕЛІ

3. ОБГРУНТУВАННЯ І ОПИС ОБЧИСЛЮВАЛЬНОЇ ПРОЦЕДУРИ

4. РІШЕННЯ ЗАВДАННЯ ОПТИМІЗАЦІЇ НА ОСНОВІ ТЕХНОЛОГІЇ СІМПЛЕКС-МЕТОДУ

5. АНАЛІЗ РЕЗУЛЬТАТІВ БАЗОВОЇ АНАЛІТИЧНОЇ МОДЕЛІ ТА ПРОПОЗИЦІЇ ЩОДО ВНЕСЕННЯ ЗМІН ДО

6. ПЕРЕВІРКА ОПТИМАЛЬНОГО РІШЕННЯ У СЕРЕДОВИЩІ MSEXCEL. З ВИКОРИСТАННЯМ програмнного надбудови «ПОШУК РІШЕННЯ» (ПАКЕТ «SOLVER»)

7. Приклади ПОСТАНОВОК, ФОРМАЛІЗАЦІЇ І РІШЕННЯ ПЕРСПЕКТИВНИХ оптимізаційних управлінських ЗАВДАНЬ

8. ВИСНОВОК

9. Список використаної літератури


ВСТУП

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

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

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

За останні 30-40 років методи моделювання економіки розроблялися дуже інтенсивно. Вони будувалися для теоретичних цілей економічного аналізу і для практичних цілей планування, управління і прогнозу. Змістовно моделі економіки об'єднують такі основні процеси: виробництво, планування, управління, фінанси і т.д. Однак у відповідних моделях завжди упор робиться на який-небудь один процес (наприклад, процес планування), тоді як всі інші представляються в спрощеному вигляді.

Основні етапи процесу моделювання.

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

1. Постановка економічної проблеми та її якісний аналіз. Головне тут - чітко сформулювати сутність проблеми, прийняті допущення і ті питання, на які потрібно отримати відповіді. Цей етап включає виділення найважливіших рис і властивостей модельованого об'єкта і абстрагування від другорядних; вивчення структури об'єкта і основних залежностей, що пов'язують його елементи; формулювання гіпотез (хоча б попередніх), що пояснюють поведінку і розвиток об'єкта.

2. Побудова математичної моделі. Це етап формалізації економічної проблеми, вираження її у вигляді конкретних математичних залежностей і відносин (функцій, рівнянь, нерівностей і т.д.). Зазвичай спочатку визначається основна конструкція (тип) математичної моделі, а потім уточнюються деталі цієї конструкції (конкретний перелік змінних і параметрів, форма зв'язків). Таким чином, побудова моделі поділяється в свою чергу на кілька стадій.

Неправильно вважати, що чим більше фактів враховує модель, тим вона краще "працює" і дає кращі результати. Те ж можна сказати про такі характеристики складності моделі, як використовувані форми математичних залежностей (лінійні і нелінійні), облік факторів випадковості і невизначеності і т.д.

Зайва складність і громіздкість моделі ускладнюють процес дослідження. Потрібно враховувати не тільки реальні можливості інформаційного і математичного забезпечення, а й зіставляти витрати на моделювання з одержуваним ефектом (при зростанні складності моделі приріст витрат може перевищити приріст ефекту).

Одна з важливих особливостей математичних моделей - потенційна можливість їх використання для вирішення різноякісних проблем. Тому, навіть стикаючись з новою економічною задачею, не потрібно прагнути "винаходити" модель; спочатку необхідно спробувати застосувати для вирішення цього завдання вже відомі моделі.

У процесі побудови моделі здійснюється взаімосопоставленіе двох систем наукових знань - економічних і математичних. Природно прагнути до того, щоб отримати модель, що належить добре вивченого класу математичних задач. Часто це вдається зробити шляхом деякого спрощення вихідних передумов моделі, що не спотворюють істотних рис модельованого об'єкта. Однак можлива й така ситуація, коли формалізація економічної проблеми приводить до невідомої раніше математичної структурі. Потреби економічної науки і практики в середині ХХ ст. сприяли розвитку математичного програмування, теорії ігор, функціонального аналізу, обчислювальної математики. Цілком ймовірно, що в майбутньому розвиток економічної науки стане важливим стимулом для створення нових розділів математики.

3. Математичний аналіз моделі. Метою цього етапу є з'ясування загальних властивостей моделі. Тут застосовуються чисто математичні прийоми дослідження. Найбільш важливий момент - доказ існування рішень в сформульованої моделі (теорема існування). Якщо вдасться довести, що математична задача не має рішення, то необхідність в подальшій роботі за первісним варіантом моделі відпадає і слід скорегувати або постановку економічної задачі, які способи її математичної формалізації. При аналітичному дослідженні моделі з'ясовуються такі питання, як, наприклад, єдино чи рішення, які змінні (невідомі) можуть входити в рішення, які будуть співвідношення між ними, в яких межах і в залежності від яких вихідних умов вони змінюються, які тенденції їх зміни і т.д. Аналітичної дослідження моделі порівняно з емпіричним (числовим) має ту перевагу, що одержувані висновки зберігають свою силу при різних конкретних значеннях зовнішніх і внутрішніх параметрів моделі.

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

4. Підготовка вихідної інформації. Моделювання висуває жорсткі вимоги до системи інформації. У той же час реальні можливості отримання інформації обмежують вибір моделей, що призначаються для практичного використання. При цьому береться до уваги не тільки принципова можливість підготовки інформації (за певні терміни), а й витрати на підготовку відповідних інформаційних масивів. Ці витрати не повинні перевищувати ефект від використання додаткової інформації.

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

5. Чисельне рішення. Цей етап включає розробку алгоритмів для чисельного рішення задачі, складання програм на ЕОМ і безпосереднє проведення розрахунків. Труднощі цього етапу зумовлені, перш за все, великою розмірністю економічних задач, необхідністю опрацювання значних масивів інформації.

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

6. Аналіз чисельних результатів і їх застосування. На цьому заключному етапі циклу постає питання про правильність і повноту результатів моделювання, про ступінь практичної застосовності останніх.

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

Особливості дослідження операцій.

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

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

3. Однією з істотних особливостей дослідження операцій є прагнення знайти оптимальне рішення поставленої задачі. Однак часто таке рішення виявляється недосяжним через обмеження, що накладаються наявними ресурсами або рівнем сучасної науки. Наприклад, для комбінаторних завдань, зокрема завдань календарного планування при числі верстатів біліше 4 оптимальне рішення при сучасному рівні розвитку математики виявляється можливим знайти лише простим перебором варіантів. Однак навіть при невеликих n число можливих варіантів виявляється настільки велике, що перебір всіх варіантів при існуючих обмеженнях на швидкодію ЕОМ і допустиме машинний час практично немислимі,
тоді доводиться обмежуватися пошуком досить хорошого або субоптимального рішення.

4. Особливість операційних досліджень полягає і в тому, що вони проводяться комплексно, з багатьох напрямків. Для проведення такого дослідження створюється операційна група. До її складу входять фахівці різних областей: інженери, математики, економісти, соціологи, психологи.

У дослідженні операцій головна роль відводиться математичному моделюванню.В даний час математичні моделі застосовуються для аналізу, прогнозування та вибору оптимальних рішень в різних областях економіки. Це планування і оперативне управління виробництвом, управління трудовими ресурсами, управління запасами, розподіл ресурсів, планування та розміщення об'єктів, керівництво проектом, розподіл інвестицій і т.п. Моделі розробляються з метою оптимізації заданої цільової функції при деякій сукупності обмежень. Для побудови математичної моделі необхідно мати суворе уявлення про мету функціонування досліджуваної системи і мати інформацію про обмеження, які представляють область допустимих значень керуючих змінних. Аналіз моделі повинен привести до визначення найкращого керуючого впливу на об'єкт управління при виконанні всіх установлених обмежень. В основі побудови математичних моделей лежить припущення про те, що всі змінні, параметри і обмеження, а також цільова функція, кількісно вимірні.

Крім математичних моделей в дослідженні операцій використовуються також імітаційні та евристичні моделі. Для побудови імітаційних моделей не потрібне використання математичних функцій, явно що пов'язують ті чи інші змінні, і ці моделі, як правило, дозволяють імітувати поведінку дуже складних систем, для яких побудова математичних моделей і отримання рішень неможливо. Евристичні методи базуються на інтуїтивно або емпірично обираних правила, які дозволяють досліднику поліпшити вже наявне рішення.

У літературі, присвяченій питанням економіко-математичного моделювання, в залежності від обліку різних чинників (часу, способів його представленіяв моделях; випадкових факторів і т.п.) виділяють, наприклад, такі моделі:

1. детермінованість модель (лінійна модель, нелінійна модель, динамічна модель, графічна модель);

2. Стохастичний модель;

3. Невизначений модель (теорія ігор, імітаційні моделі).

В стохастичних моделях невідомі фактори - це випадкові величини, для яких відомі функції розподілу і різні статистичні характеристики (математичне очікування, дисперсія, середньоквадратичне відхилення і т.п.). Серед стохастичних характеристик можна виділити:

* Моделі стохастичного програмування, в яких або в цільову функцію, або в обмеження входять випадкові величини;

* Моделі теорії випадкових процесів, призначені для вивчення процесів, стан яких в кожен момент часу є випадковою величиною;

* Моделі теорії масового обслуговування, в якій вивчаються багатоканальні системи, зайняті обслуговуванням вимог.

Також до стохастичним моделей можна віднести моделі теорії корисності, пошуку і прийняття рішень.

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

У моделях теорії ігор завдання представляється у вигляді гри, в якій двоє (або більше) сторін переслідують різні цілі, а результати будь-якої дії кожної зі сторін залежать від заходів партнера. В економіці конфліктні ситуації зустрічаються дуже часто і мають різноманітний характер. До них відносяться, наприклад, взаємини між постачальником і споживачем, покупцем і продавцем, банком і клієнтом. У всіх цих прикладах конфліктна ситуація породжується відмінністю інтересів партнерів і прагненням кожного з них приймати оптимальні рішення, які реалізують поставлені цілі найбільшою мірою. При цьому кожному доводиться рахуватися не тільки зі своїми цілями, а й з цілями партнера, і враховувати невідомі заздалегідь рішення, які ці партнери будуть приймати.

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

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

Нелінійні моделі - це моделі, в яких або цільова функція, або яке-небудь з обмежень (або всі обмеження) нелінійні по керуючим змінним. Для нелінійних моделей немає єдиного методу розрахунку. Залежно від виду нелінійності, властивостей функції і обмежень можна запропонувати різні способи вирішення. Однак може статися і так, що для поставленої нелінійної задачі взагалі не існує методу розрахунку. У цьому випадку завдання слід спростити, або звівши її до відомим лінійним моделям, або просто лінеаризоване модель.

У динамічних моделях враховується фактор часу. Критерій оптимальності в динамічних моделях може бути самого загального виду (і навіть взагалі не бути функцією), однак для нього повинні виконуватися певні властивості. Розрахунок динамічних моделей складний, і для кожного конкретного завдання необхідно розробляти спеціальний алгоритм вирішення. По суті метод динамічного програмування являє собою алгоритм визначення оптимальної стратегії управління на всіх стадіях процесу.

Графічні моделі - використовуються тоді, коли завдання зручно представити у вигляді графічної структури.

У лінійних моделях цільова функція і обмеження лінійні по керуючим змінним. Побудова і розрахунок лінійних моделей є найбільш розвиненим розділом математичного моделювання, тому часто до них намагаються звести й інші завдання або на етапі постановки, або в процесі вирішення. До класичних задач лінійного програмування відносяться завдання на складання оптимального плану перевезень (транспортна задача), завдання про завантаження устаткування, про сумішах, про розкрої матеріалів, про асортимент продукції, про розміщення виробництва і управлінні виробничими запасами, завдання про харчування, про раціональне використання сировини і матеріалів та ін. Для лінійних моделей будь-якого виду і досить великої розмірності відомі такі стандартні методи рішення:

1. Графічний метод;

2. Симплекс-метод;

3. Двоетапний метод. Він дозволяє отримати спочатку стартову точку, тобто початкова дозволене рішення, а потім оптимальне рішення. У обмеження вводяться штучні змінні необхідні для отримання стартової точки;

4. Метод великих штрафів;

За змістом значної частини економічних завдань, що відносяться до завдань лінійного програмування, компоненти рішення повинні виражатися в цілих числах, тобто бути цілочисельними. Методи целочисленной оптимізації можна розділити на три основні групи: а) методи відсікання; б) комбінаторні методи; в) наближені методи.

Метод Гоморі. Суть методу полягає в тому, що спочатку завдання вирішується без умови целочисленности. Якщо отриманий план цілочисельний, задача вирішена. В іншому випадку до обмежень задачі додається нове обмеження, що володіє наступними властивостями:

- воно повинно бути лінійним;

- повинно відсікати знайдений оптимальний нецілочисельне план;

- не повинно відсікати жодного цілочисельного плану.

Додаткове обмеження, що володіє вказаними властивостями, називається правильним відсіканням.

Далі завдання вирішується з урахуванням нового обмеження. Після цього в разі потреби додається ще одне обмеження і т. Д.

Метод гілок і меж - один з комбінаторних методів. Його суть полягає в упорядкованому переборі варіантів і розгляді лише тих з них, які виявляються за певними ознаками перспективними, і відкиданні безперспективних варіантів. Метод гілок і меж полягає в наступному: безліч припустимих рішень (планів) деяким способом розбивається на підмножини, кожне з яких цим же способом знову розбивається на підмножини. Процес триває до тих пір, поки не отримано оптимальне цілочисельне рішення вихідної задачі.


1. Постановка задачі ОПЕРАЦІЙНОГО ДОСЛІДЖЕННЯ

При випуску двох видів хімічних добрив ( "Флора" і "Росток") підприємство використовує три види сировини: азотну кислоту, аміак і калійну сіль. Витрата кожного виду сировини на випуск 1 т добрив, обсяг запасів сировини (на добу) і прибуток від продажу 1 т кожного виду добрив наведені в таблиці:

види сировини Запас (т) Витрата сировини на 1 т добрив (т)
"Флора" "Росток"

Азотна кислота

аміак

калійна сіль

900

1000

800

1

2,5

3

4

2

2

Прибуток (грош) 5 8

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

2. Побудова БАЗОВОЇ АНАЛІТИЧНОЇ МОДЕЛІ

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

X1-кількість виробленого добрива «Флора» (в тоннах);

Х2-кількість виробленого добрива «Паросток» (в тоннах);

Складемо обмеження, що враховують умову задачі.

Складемо обмеження на витрату азотної кислоти. На випуск однієї тонни добрива «Флора» витрачається 1 т азотної кислоти, значить,

витрата азотної кислоти на випуск усієї кількості добрива «Флора» складе X1 т. На випуск добрива «Паросток» буде витрачено 4X2т азотної кислоти. Таким чином, загальна витрата азотної кислоти складе

X1 + 4X2 т. Ця величина не повинна перевищувати 900 т, так як запас азотної кислоти становить 900 тон. Тому можна записати наступне обмеження:

X1 + 4X2 ≤ 900

Аналогічно можна скласти обмеження на аміак:

2,5X1 + 2X2≤1000

і на витрату калійної солі:

3х1 + 2Х2≤800

Крім того, змінні X1 іX2 за своїм фізичним змістом не можуть приймати від'ємних значень, так як вони позначають кількість тонн добрив. Тому необхідно вказати обмеження невід'ємності:

X1> 0, X2> 0.

У даній задачі потрібно визначити кількість тонн випускаються добрив, при якому прибуток від їх виробництва буде максимальною. Прибуток від випуску однієї тонни добрива «Флора» становить 5 ден. од .; значить, прибуток отвипуска добрива «Флора» складе 5X1 ден. од. Прибуток від випуску добрива «Паросток» складе 8X2 ден. од. Таким чином, загальний прибуток від випуску всіх виробів складе 5X1 + 8X2 ден. од. Потрібно знайти такі значеніяпеременних X1іX2, при яких ця величина буде максимальною. Таким чином, цільова функція для даного завдання буде мати наступний вигляд:

Е = 5X1 + 8X2 → max

Для вирішення завдання симплекс-методом потрібно привести її до стандартної форми. Всі обмеження завдання мають вигляд «менше або дорівнює». Їх необхідно перетворити в рівності. Для цього потрібно додати в кожне обмеження додаткову (залишкову) змінну. Математична модель задачі в стандартній формі матиме наступний вигляд:

Х1 + 4Х2 + Х3 = 900

2,5Х1 + 2Х2 + Х4 = 1000

3х1 + 2Х2 + Х5 = 800

Е = 5X1 + 8X2 → max

X1> 0, X2> 0.

де:

Х3-залишок азотної кислоти;

Х4-залишок аміаку;

Х5-залишок калійної солі.

3. ОБГРУНТУВАННЯ І ОПИС ОБЧИСЛЮВАЛЬНОЇ ПРОЦЕДУРИ

Необхідно вирішити задачу за критерієм максимізації прибутку і визначити оптимальний обсяг випуску добрив «Флора» та «Росток». Побудувавши математичну модель задачі, ми бачимо, що цільова функція і обмеження лінійні, отже, дана задача є задачею лінійного програмування. З безлічі методів вирішення завдань лінійного програмування, для вирішення даної, був обраний метод визначення оптимального рішення на основі симплекс-таблиць.

Пошук оптимального рішення на основі симплекс-методу полягає в цілеспрямованому переборі суміжних кутових точок ОДР в напрямку поліпшення значення цільової функції.Можна довести, що перехід з однієї кутової точки ОДР в іншу (суміжну) відповідає заміні однієї змінної в базисі. Така заміна означає, що одна з небазисних змінних (мала нульове значення) включається в базис, тобто збільшується, а одна з базисних змінних зменшується до нуля, тобто виключається з базису. Вибір таких змінних виконується за певними правилами, що забезпечує максимально швидке збільшення цільової функції.

Розглянемо алгоритм пошуку оптимального рішення на основі симплекс-таблиць:

1. Будується вихідна симплекс-таблиця.

2. Симплекс-таблиця будується за наступними правилами:

• в першому рядку перераховуються всі змінні завдання, як вихідні (X1, X2,..., X n), так і додаткові, введені при приведенні до стандартної форми (X n +1, X n +2, ..., Xk ). Для задач, що містять тільки обмеження «менше або дорівнює», додаткові змінні X n +1, X n +2, ..., Хк ~ це залишкові змінні;

• в першій колонці таблиці ( «Базис») перераховуються змінні, складові початковий базис завдання. Їх кількість завжди дорівнює кількості обмежень. Для задач, що містять тільки обмеження «менше або дорівнює», початковий базис складається з залишкових змінних X n +1, X n +2, ..., Xk. У цій же колонці вказується позначення цільової функції E;

• в рядку цільової функції вказуються коефіцієнти цільової функції з протилежним знаком. Для змінних, що не входять в цільову функцію (наприклад, для остаточнихпеременних X n +1, X n +2,..., Xk), вказуються нулі;

• в рядках базисних змінних вказуються коефіцієнти обмежень, в які входять ці змінні. Для змінних, що не входять в обмеження, вказуються нульові коефіцієнти;

• в останньому стовпці ( «Рішення») вказуються значення базисних змінних (вони рівні правим частинам обмежень), а також початкове значення цільової функції (0).

Якщо таблиця побудована правильно, то в стовпці кожної базіснойпеременной має бути присутня тільки одна одиниця (в рядку обмеження, в яке входить ця змінна); інші коефіцієнти - нульові.

2. Якщо всі коефіцієнти в рядку цільової функції невід'ємні, то оптимальне рішення знайдено, і алгоритм завершується. Інакше здійснюється перехід до етапу 3.

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

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

5. Виконується перетворення симплекс-таблиці за такими правилами:

Нова ведуча рядок =

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

6. Знаходиться нове базисне рішення, відповідне новій структурі небазисних і базисних змінних. Здійснюється перехід до кроку 2.

Після закінчення реалізації алгоритму в стовпці "Базове рішення" знаходяться значення змінних, що увійшли в оптимальний базис, а також значення цільової функції, відповідне оптимального рішення. Змінні, які не ввійшли в оптимальний базис, в оптимальному рішенні дорівнюють нулю.

4. РІШЕННЯ ЗАВДАННЯ ОПТИМІЗАЦІЇ НА ОСНОВІ ТЕХНОЛОГІЇ СІМПЛЕКС-МЕТОДУ

Математична модель розв'язуваної задачі має наступний вигляд:

Х1 + 4Х2 + Х3 = 900

2,5Х1 + 2Х2 + Х4 = 1000

3х1 + 2Х2 + Х5 = 800

Е = 5X1 + 8X2 → max

X1> 0, X2> 0.

Складемо вихідну симплекс-таблицю (табл.1):

Таблиця 1

базис Х1 Х2 Х3 Х4 Х5 Рішення
E -5 -8 0 0 0 0
Х3 1 4 1 0 0 900
Х4 2,5 2 0 1 0 1000
Х5 3 2 0 0 1 800

Визначається змінна для включення в базис.

Для розглянутого прикладу в базис необхідно включити змінну X2, так як їй відповідає максимальний по модулю негативний коефіцієнт E-рядки (-8). Це означає збільшення випуску добрива «Паросток». З умови задачі і цільової функції видно, що збільшення випуску добрива «Паросток» призводить до більш швидкого зростання цільової функції, ніж збільшення випуску добрива «Флора»: випуск кожної тонни добрива «Паросток» збільшує цільову функцію (прибуток) на 8 ден. од., а випуск кожної тонни добрива «Флора» - тільки на 5 ден. од.

Визначимо змінну для виключення з базису. Для цього необхідно поділити коефіцієнти стовпця рішення на коефіцієнти ведучого шпальти Х2 (при цьому слід пам'ятати, щоб коефіцієнти ведучого шпальти були позитивні). У результаті вийдуть сімплексні відносини:

900/4 = 225; 1000/2 = 500; 800/2 = 400.

Сенс пошуку змінної, исключаемой з базису в наступному: при включенні нової змінної в базис, її значення збільшується. При цьому щоб дотримуватися вихідні обмеження завдання необхідно зменшувати базисні змінні. Зменшення змінних можливо тільки до 0. симплексному ставлення показує через скільки збільшень зміною, що включається в базис, дана базисна змінна наблизиться до нуля. Тому змінна, має мінімальне симплексному ставлення, виключається з базису. Рядок зі змінною, исключаемой з базису, називається провідною рядком. Отже, виключаємо з базису змінну Х3 (симплексних відношення мінімальне і одно 225), рядок Х3 є провідною. Елемент, що знаходиться на перетині провідного рядка Х3 і ведучого шпальти Х2, називається ведучим (що дозволяє) елементом. Для даної таблиці провідний елемент дорівнює 4.

Виконаємо перетворення таблиці за правилами симплекс-методу, описаним в розділі 3: ведуча рядок Х3 ділиться на провідний елемент, рівний 4; провідний стовпець Х2 заповнюється нулями; всі інші елементи таблиці перераховуються за "правилом прямокутника". Наприклад, коефіцієнт на перетині Е-рядка і стовпця Х1 перераховується наступним чином: [4 * (- 5) -1 * (- 8)] / 4 = -3. Отримана симплекс-таблиця наведена в табл.2 .:

Таблиця 2 Симплекс-таблиця 2

базис Х1 Х2 Х3 Х4 Х5 Рішення
E -3 0 2 0 0 1800
Х2 0,25 1 0,25 0 0 225
Х4 2 0 -0,5 1 0 550
Х5 2,5 0 -0,5 0 1 350

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

Табліца3- Симплекс-таблиця 3

базис Х1 Х2 Х3 Х4 Х5 Рішення
E 0 0 1,4 0 1,2 2220
Х2 0 1 0,3 0 -0,1 190
Х4 0 0 -0,1 1 -0,8 270
Х1 1 0 -0,2 0 0,4 140

Як видно з таблиці 3, в рядку цільової функції немає негативних коефіцієнтів. Це означає, що оптимальне рішення знайдено. Воно полягає в наступному:

Х1 = 140;

Х2 = 190;

Х4 = 270;

Х3 = Х5 = 0;

Е = 2220.

5. АНАЛІЗ РЕЗУЛЬТАТІВ БАЗОВОЇ АНАЛІТИЧНОЇ МОДЕЛІ ТА ПРОПОЗИЦІЇ ЩОДО ВНЕСЕННЯ ЗМІН ДО

Проаналізуємо отриманий результат рішення задачі:

Х1 = 140;

Х2 = 190;

Х4 = 270;

Х3 = Х5 = 0;

Е = 2220.

Значення змінних X1 = 140, X2 = 190 показують, що підприємство за планом має випускати 140 тонн добрива «Флора» та 190 тонн добрива «Паросток». У цьому випадку буде отримана максимальна прибуток в розмірі 2220 ден. од. (Значення цільової функції). Так як X3 = 0, значить, весь запас азотної кислоти (900 тонн) витрачається на випуск добрив. Аналогічно можна показати, що змінна X4представляет собою невитрачений залишок аміаку, а X5 - калійної солі. Таким чином, залишається невитраченим 270 тонн аміаку (витрата аміаку на випуск всіх добрив складе 1000 - 270 = 730 тонн). Невитрачений залишок калійної солі дорівнює нулю, значить, все 800 тонн калійної солі витрачаються на виробництво добрив.

Проведемо аналіз отриманого рішення на чутливість. Для початку визначимо статус наявних в завданні ресурсів. За статусом всі ресурси діляться на дефіцитні і недефіцитних. Якщо для реалізації оптимального рішення ресурс витрачається повністю, то він називається дефіцитним, якщо не повністю - недефіцитним. Статус ресурсів визначається за значеннями залишкових змінних. У цьому завданню дефіцитними ресурсами є азотна кислота і калійна сіль, тому що вони повністю витрачаються в процесі виробництва (Х3 = 0; Х5 = 0). Аміак - недефіцитним ресурс, так як 270 тонн аміаку залишаються невитраченими (X4 = 270) .Увеліченіе запасів дефіцитних ресурсів дозволяє збільшити цільову функцію (прибуток). Зниження запасів дефіцитних ресурсів призводить до зниження прибутку. Збільшення запасів недефіцитних ресурсів завжди недоцільно, так як воно призводить тільки до збільшення невитрачених залишків. Запас недефіцитних ресурсу можна знизити на величину його залишку; це ніяким чином не впливає на оптимальне рішення (в тому числі на оптимальні обсяги виробництва і на прибуток), зменшується тільки невитрачений залишок ресурсу. Якщо запас недефіцитних ресурсу знизиться на величину, що перевищує його залишок, то для визначення нового оптимального плану виробництва необхідно вирішувати задачу заново. У нашому випадку збільшення запасів азотної кислоти і калійної солі дозволить збільшити прибуток. Запас аміаку можна знизити на 270 т (тобто до 730 т); ці 270 т аміаку підприємство може, наприклад, продати або використати в іншому цеху. Наприклад, якщо запас аміаку складе не 1000 т, а тільки 800 т, то оптимальне рішення задачі буде наступним: X1 = 140; X2 = 190; X 3 = 0; X4 = 70; X5 = 0; E = 2220 ден. од. Таким чином, оптимальне рішення не зміниться (крім зниження неизрасходованного залишку аміаку) .Якщо запас стали знизиться більш ніж на 270 т (тобто складе менше 730 т), то для визначення нового оптимального плану виробництва необхідно вирішувати задачу заново. Для нового оптимального рішення зміняться не тільки значення змінних, але і склад змінних в оптимальному базисі (тобто в оптимальний базис будутвходіть не буде змінена X1, X2 і X5, а інші змінні). Значення цільової функції при цьому знизиться, тобто складе менше 2220 ден. од.

Визначимо цінність наявних ресурсів.Цінність ресурсу - це збільшення значення цільової функції (прибутку) при збільшенні запасу ресурсу на одиницю (або, відповідно, зниження цільової функції при зменшенні запасу ресурсу на одиницю).

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

У нашому випадку цінність азотної кислоти дорівнює 1,4 ден. од. / т, цінність калійної солі - 1,2 ден. од. / т. Це означає, наприклад, що збільшення запасу азотної кислоти на одиницю (тобто на 1 т) призводить до збільшення прибутку підприємства в середньому на 1,4 ден. од. Наприклад, якщо запас азотної кислоти збільшиться на 100 т (тобто складе 1000 т), то прибуток складе приблизно 2220 + 1,4 * 100 = 2360 ден. од. Зниження запасу азотної кислоти призведе до відповідного зниження прибутку.

Цінність недефіцитного ресурсу завжди дорівнює нулю. В даному прикладі цінність аміаку дорівнює нулю, так як збільшення його запасу не призводить до збільшення прибутку, а зниження (не більше ніж на 270 кг) - не призводить до зниження прибутку.

Цінність ресурсу показує максимальну (граничну) ціну, по якій вигідно закуповувати ресурси. Наприклад, в розглянутій задачі підприємству вигідно закуповувати азотну кислоту за ціною не більше 1,4 ден. од. / т, калійну сіль - за ціною не більше 1,2 ден. од. / т. Закупівля ресурсу за ціною, що перевищує його цінність, означає, що витрати підприємства на закупівлю ресурсу перевищують прибуток від його використання.

6. ПЕРЕВІРКА ОПТИМАЛЬНОГО РІШЕННЯ У СЕРЕДОВИЩІ MSEXCEL З ВИКОРИСТАННЯМ програмнного надбудови «ПОШУК РІШЕННЯ» (ПАКЕТ «SOLVER»)

Для вирішення оптимізаційних задач в середовищі MS Excel використовується інструмент «Пошук рішення» (пункт меню «Дані Пошук рішення»).

Для вирішення завдання необхідно виконати наступні етапи:

- Внести вихідні дані;

- Визначити осередки, в які буде поміщений кінцевий результат (змінювані осередки);

- Внести в певну комірку формулу для розрахунку цільової функції;

- Внести в осередку формули для розрахунку обмежень.

В результаті виходить наступне:

- Викликати надбудову «Пошук рішення» і, визначивши для неї основні параметри, визначити рішення:

Після того, як будуть заповнені всі основні форми, натискаємо кнопку «Виконати», після чого з'явиться діалогове вікно «Результати пошуку рішень» .Рішення завдання виглядає наступним чином:

1.Для повторного рішення задачі оптимізації слід видалити вміст комірок з елементами рішення і скинути отримані результати (клавіша «Delete»).

2.Фрагмент робочого листа MS Excel з результатами рішення задачі оптимізації зберігається і переноситься в документ MS Word (наприклад, за допомогою команд «Ctrl & PrintScreen» в середовищі MS Excel і «Вставити» в документі MS Word або за допомогою команд «Копіювати» та «Вставити », розташованих на панелі інструментів у всіх додатках пакета MS Office).

Оптимальне рішення, отримане за допомогою двоетапного методу, збігається з рішенням, отриманим в середовищі MS Excel за допомогою програмної надбудови «Пошук рішення».

7. Приклади ПОСТАНОВОК, ФОРМАЛІЗАЦІЇ І РІШЕННЯ ПЕРСПЕКТИВНИХ оптимізаційних управлінських ЗАВДАНЬ

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

Примітка. Графічний метод може застосовуватися також для вирішення завдань з будь-якою кількістю змінних, якщо можливо висловити всі змінні завдання через будь-які дві змінні.

ОДР - це безліч значень змінних X1, X2, ..., Xn, які відповідають обмеженням завдання. Для задач з двома змінними ОДР є безліч точок (X1; X2), тобто деяку область на площині (зазвичай - багатокутник). Для завдань з трьома змінними ОДР є багатогранник в просторі, для задач з великою кількістю змінних - деяку область багатовимірного простору. Можна довести, що екстремум (мінімум або максимум) цільової функції завжди досягається в одній з кутових точок ОДР. Іншими словами, оптимальне рішення завжди знаходиться в кутовій точці ОДР. Тому завдання лінійного програмування з двома змінними можна вирішити наступним чином:

- побудувати ОДР на площині в системі координат (X1; X2),

- визначити всі кутові точки ОДР,

- обчислити значення цільової функції в цих точках і вибрати оптимальне рішення.

Вирішимо графічним методом наступну задачу: підприємство хімічної промисловості випускає соляну і сірчану кислоту. Випуск однієї тонни соляної кислоти приносить підприємству прибуток в розмірі 25 грош, випуск однієї тонни сірчаної кислоти - 40 грош Для виконання державного замовлення необхідно випустити не менше 200 т соляної кислоти і не менше 100 т сірчаної кислоти. Крім того, необхідно враховувати, що випуск кислот пов'язаний з утворенням небезпечних відходів. При випуску однієї тонни соляної кислоти утворюється 0,5 т небезпечних відходів, при випуску однієї тонни сірчаної кислоти - 1,2 т небезпечних відходів. Загальна кількість небезпечних відходів не повинно перевищувати 600 т, так як перевищення цього обмеження призведе до виплати підприємством великого штрафу.

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

Складемо математичну модель задачі. Для цього введемо змінні. Позначимо через X1 кількість продукції, що випускається соляної кислоти (в тоннах), через X2 - кількість сірчаної кислоти (в тоннах).

Складемо обмеження, пов'язані з необхідністю виконання державного замовлення. Підприємству необхідно випустити не менше 200т. соляної кислоти. Це обмеження можна записати в такий спосіб: X1 ≥ 200. Аналогічно складемо обмеження, яке встановлює, що підприємство має випустити не менше 100 т. сірчаної кислоти: X2 ≥ 100.

Складемо обмеження на небезпечні відходи. При випуску однієї тонни соляної кислоти утворюється 0,5т. небезпечних відходів; значить, загальна кількість небезпечних відходів при випуску соляної кислоти складе 0,5 · X1 т. При випуску сірчаної кислоти утворюється 1,2 · X2 т небезпечних відходів. Таким чином, загальна кількість небезпечних відходів складе 0,5 · X1 + 1,2 · X2 т. Ця величина не повинна перевищувати 600 т. Тому можна записати наступне обмеження: 0,5 · X1 + 1,2 · X2 ≤ 600.

Крім того, змінні X1 і X2 за своїм фізичним змістом не можуть приймати від'ємних значень, так як вони позначають кількість випущених кислот. Тому необхідно вказати обмеження невід'ємності): X1 ≥ 0, X2 ≥ 0.

У даній задачі потрібно визначити випуск кислот, при якому прибуток буде максимальною. Прибуток від випуску однієї тонни соляної кислоти становить 25 ден.ед .; значить, прибуток від випуску соляної кислоти складе 25 · X1 грош Прибуток від випуску сірчаної кислоти складе 40 · X2 грош Таким чином, загальний прибуток від випуску кислот складе 25 · X1 + 40 · X2 грош Потрібно знайти такі значення змінних X1 і X2, при яких ця величина буде максимальною.

Таким чином, цільова функція для даного завдання буде мати наступний вигляд:

E = 25 · X1 + 40 · X2 → max.

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

X1 ≥ 200

X2 ≥ 100 (1.3)

0,5 · X1 + 1,2 · X2 ≤ 600

X1 ≥ 0, X2 ≥ 0.

E = 25 · X1 + 40 · X2 → max.

У цьому завданні є два обмеження "більше або дорівнює" і одне обмеження "менше або дорівнює". Цільова функція підлягає максимізації.

Обмеження X1 ≥ 200 задається вертикальною лінією X1 = 200. Всі точки (X1; X2), розташовані праворуч від цієї лінії, задовольняють обмеження X1 ≥ 200, розташовані зліва - не задовольняють. Обмеження X2 ≥ 100 задається горизонтальною лінією X2 = 100. Всі точки, розташовані зверху від цієї лінії, задовольняють обмеження X2 ≥ 100, розташовані знизу - не задовольняють.

Для побудови лінії, яка задає обмеження 0,5 · X1 + 1,2 · X2 ≤ 600, зручно записати його у вигляді рівності: 0,5 · X1 + 1,2 · X2 = 600. Висловимо одну з змінних через іншу: X2 = -0,417 · X1 + 500. Це рівняння прямої. Побудуємо цю пряму. Вона розбиває координатну площину на дві півплощини. В одній з цих напівплощин знаходяться точки, що задовольняють обмеження, в іншого - не задовольняють. Щоб знайти напівплощина, що задовольняє обмеженню 0,5 · X1 + 1,2 · X2 ≤ 600, підставами в нього координати будь-якої точки, наприклад, (0; 0). Для цієї точки обмеження виконується. Значить, вона знаходиться в півплощині, що задовольняє обмеження.

Перетин всіх напівплощин, які відповідають обмеженням завдання, є ОДР. На рис.2 вона виділена кольором.

Малюнок 2. Рішення завдання графічним методом

Оптимальне рішення знаходиться в одній з кутових точок ОДР (на рис.2 вони позначені як A, B, C). Ці точки можна знайти шляхом вирішення відповідних систем з двох рівнянь. Знайдемо значення цільової функції в цих точках:

E (A) = 25 · 200 + 40 · 100 = 9000;

E (B) = 25 · 200 + 40 · 416,67 = 21666,8;

E (C) = 25 · 960 + 40 · 100 = 28000.

Таким чином, оптимальне рішення знаходиться в точці C = (960; 100). Це означає, що підприємству слід випустити 960 т соляної кислоти і 100 т сірчаної кислоти. Прибуток при цьому складе 28000 ден.ед. Можна також знайти кількість небезпечних відходів, яке буде отримано при виробництві кислот: 0,5 · 960 + 1,2 · 100 = 600 т.


ВИСНОВОК

В рамках даної роботи була вирішена одна з задач лінійного програмування. В результаті застосування процедури симплекс-методу було отримано оптимальне рішення поставленого завдання, відповідно до якого підприємству потрібно випустити 140 тонн добрива «Флора» та 190 тонн добрива «Паросток». При цьому кількість невикористаного аміаку складе 270 тонн, а азотна кислота і калійна сіль будуть використані повністю. При цьому підприємство отримає максимальний прибуток рівну 2220 грошових одиниць.

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

Перевірка результатів рішення задачі в середовищі MS Excel показала аналогічне рішення даної задачі оптимізації.

При виконанні даної роботи на прикладі було розглянуто графічний метод рішення задач.

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


Список використаних джерел

1. Замків О.О., Толстопятенко А.В., черешні Ю.Н. Математичні методи в економіці: Підручник. - М .: МГУ ім. М.В.Ломоносова, Видавництво «ДІС», 1997.

2. Конспект лекцій з предмету «Економіко-математичні методи і моделі».

3. Минюк С.А. Математичні методи і моделі в економіці: Учеб. посібник / Минюк С.А., Ровба Е.А., Кузьмич К.К. - Мн .: ТетраСистемс, 2002.

4. Смородинский С.С., Батин Н. В. Оптимізація рішень на основі методів і моделей математичного програмування. Мн .: БДУІР, 2003.

5.Економіко-математичні методи і моделі / Під. ред. А. В. Кузнєцова. Мн .: БГЕУ.1999.


Головна сторінка


    Головна сторінка



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