Використання лінійного програмування для розв'язання задач оптимізації

Размещено на http://www.allbest.ru/

Державний вищий навчальний заклад «Придніпровська державна академія будівництва та архітектури»

ВИКОРИСТАННЯ ЛІНІЙНОГО ПРОГРАМУВАННЯ ДЛЯ РОЗВ'ЯЗАННЯ ЗАДАЧ ОПТИМІЗАЦІЇ

Задорожня Тетяна Євгенівна старший викладач

кафедри фундаментальних і природничих дисциплін

Шибко Оксана Миколаївна канд. техн. наук, доцент, доцент кафедри комп'ютерних наук, інформаційних технологій та прикладної математики

Анотація

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

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

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

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

Виклад основного матеріалу

Ефективність роботи сучасних підприємств, які є складними системами, залежить від якості організаційного управління. Процеси прийняття рішень лежать в основі будь-якої цілеспрямованої діяльності. При формуванні стратегічних і тактичних рішень керівник повинен враховувати безліч часом суперечливих міркувань, спиратися на складні критерії ефективності шляхів досягнення кінцевих цілей. У зв'язку з цим виникла необхідність застосовувати для аналізу і синтезу економічних ситуацій і систем математичні методи і сучасну обчислювальну техніку [1]. Такі методи об'єднуються під загальною назвою - математичне програмування. Завдання математичного програмування знаходять застосування в різних областях людської діяльності, де необхідний вибір одного з можливих варіантів дій, наприклад при вирішенні багато чисельних проблем управління і планування виробничих процесів, в задачах проектування та перспективного планування, при організації функціонування та розвитку соціальних процесів, їх координації з господарськими та економічними процесами. Оптимальні (ефективні) рішення дозволяють досягати мети при мінімальних витратах трудових, матеріальних і сировинних ресурсів. Найбільш розробленим в теперішній час розділом математичного програмування є лінійне програмування яке застосовується при розробці методів відшукання екстремуму (максимуму або мінімуму) лінійних функцій декількох змінних при лінійних обмеженнях, накладених на змінні. За типом вирішуваних завдань його методи можна розділити на універсальні і спеціальні. За допомогою універсальних методів (наприклад, симплекс-метод) можуть вирішуватися будь-які завдання лінійного програмування. Спеціальні методи враховують особливості цільової функції і системи обмежень [3].

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

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

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

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

Лінійне програмування найповніше розроблено до теперішнього часу і досить просто розуміння. Розробка цього почалася 1938 р. Л.В. Конторович займався вивченням практичної задачі - розробкою найкращої виробничої програми завантаження верстатів та з'ясував, що це завдання не піддається вирішенню відомими методами класичного аналізу. З'ясувалося також, що це завдання не випадкове, багато завдань наводяться до нього. Вивчення цього кола завдань та методів їх вирішення спричинило створення методу лінійного програмування. Слово "програмування" означає, що набір керованих змінних зазвичай складає програму (план) роботи конкретного підприємства.

Лінійне програмування є окремим випадком математичного програмування. Одночасно воно - основа кількох методів розв'язання задач цілісного та нелінійного програмування.

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

Завдання оптимізації виробничого плану підприємства

Постановка задачі. Підприємство може випускати n типів продукції, для яких є m видів ресурсів. Відомі: ay - норми витрат і - го виду ресурсу виробництва одиниці виробленої продукції j - го типу (і =1,2,..., m ; j =1,2,..., n ); b_i - повні обсяги наявних ресурсів на період планування; Cj - прибуток, одержувана підприємством від виробництва та реалізації одиниці виробленої продукції j - го типу. Маркетингові дослідження показали, що попит на асортимент продукції, що випускається підприємством, не обмежений [2].

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

Для зручності складання математичної моделі вихідні дані зведемо таблицю 1.

Позначимо план випуску продукції через X = (x_b x₂,..., x_n).

Таблиця 1

Зведення вихідних даних