Багатокритеріальні задачі лінійного програмування в економіці

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

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

НАЦІОНАЛЬНИЙ АВІАЦІЙНИЙ УНІВЕРСИТЕТ

ІНСТИТУТ ЕКОНОМІКИ ТА МЕНЕДЖМЕНТУ

Кафедра економічної кібернетики

Курсова робота

з дисципліни: «Економічна кібернетика»

на тему: «Багатокритеріальні задачі лінійного програмування в економіці»

Виконала:

студентка 310 групи ФЕП

Коваленко Тетяна

Прийняв:

Касьянова Н. В.

Київ 2014



Зміст

Вступ

Розділ 1 Теоритичні відомості

Багатокритеріальність, існуючі методи розв'язку задач лінійного програмування

Постановка задачі

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

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

Двоїстий симплекс-метод

Транспортна задача

Розділ 2. Вибір методу і його опис

Вибір методу розв'язання багатокритеріальної задачі лінійного програмування. Симплекс метод

Розділ 3 Постановка і вирішення задачі

Висновки

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



Реферат

Курсова робота: 22 стор., 24 джерела

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

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

Мета роботи: розробка та дослідження методів знаходження оптимальних розв'язків багатокритеріальних задач лінійного програмування.

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

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

Ключові слова: Методи, моделі, багатокритеріальні задачі, лінійне програмування, вирішення задач, задача, симплекс-метод.



Вступ

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

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

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

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

раціональне використання сировини і матеріалів;

завдання оптимального розкрою;

-оптимізації виробничої програми підприємств;

-оптимального розміщення і концентрації виробництва;

-складання оптимального плану перевезень, роботи транспорту;

-управління виробничими запасами і ін.

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

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

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

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

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



Розділ 1 Теоритичні відомості

Багатокритеріальність, існуючі методи розв'язку задач лінійного програмування

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

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

Постановка задачі

Методи лінійного програмування - чисельні методи вирішення оптимізаційних задач, що зводяться до формальних моделей лінійного програмування[1].

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

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

В загальному постановка задачі має вигляд:

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

(1.1.1)

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

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

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

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

Перший крок при використанні графічного методу полягає в поданні області допустимих розв'язків, у якій водночас задовольняються всі обмеження моделі. Нехай шукана область (простір) розв'язків задачі показана. Умови невід'ємності змінних обмежують область їх допустимих значень. Інші межі простору розв'язків потрібно зобразити прямими лініями, побудованими по рівняннях, що отримані заміною знака «?» чи «?» знаком “=" в обмеженнях. Області, в яких відповідні обмеження виконуються як нерівності, указуються стрілками, спрямованими вбік допустимих значень змінних. Отримуємо простір розв'язків задачі. У кожній точці, що належить внутрішній області або межам, всі обмеження виконуються, тому розв'язки, що відповідають цим точкам, є допустимими. Серед безкінечного числа таких точок можна знайти точку оптимального розв'язку, якщо з'ясувати, в якому напрямку зростає цільова функція. На графік наносять лінію рівня цільової функції , де - довільне значення . Будують вектор , що є нормаллю до ліній рівня цільової функції й визначає напрямок оптимізації . Лінію рівня зрушують паралельно самій собі вздовж вектора доти, поки вона не вийде за межі області допустимих розв'язків. Остання точка цієї області й буде точкою оптимуму.

Значення та в розв'язуючій точці визначаються шляхом розв'язання системи рівнянь.

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

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



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

Симплекс-метод застосовується до рішення будь-якої задачі лінійного програмування[3].

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

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

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

Двоїстий симплекс-метод

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

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

.(1.4.1)

Нехай

(1.4.2)

де - одиничні вектори.

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

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

Транспортна задача

В найпростішому варіанті транспортна задача формулюється наступним чином: є n постачальників із запасами однорідного штучного товару та m споживачів із потребами цього товару . Не порушуючи загальності, можна вважати транспортну задачу закритою, тобто, що сума всіх запасів дорівнює сумі всіх потреб, в противному разі задача є відкритою і простими відомими методами (введенням фіктивного постачальника чи фіктивного споживача) зводиться до закритої. Нехай матриця є матрицею цін перевезень, тобто кожен її елемент є ціною за перевезення одиниці продукції від i-го постачальника j-му споживачу, а матриця такої ж розмірності є планом перевезень, тобто кожне є цілим невід'ємним числом, що дорівнює кількості товару, що перевозиться від i-го постачальника j-му споживачу. Метою розв'язку транспортної задачі є пошук такого плану перевезень Х, при якому загальна вартість перевезень була б найменшою з можливих за умови, що весь товар від постачальників перевозиться до споживачів. Транспортна задача є задачею цілочислового лінійного програмування. З основами лінійного програмування можна ознайомитись, з науковим обґрунтуванням алгоритмів розв'язку задач лінійного програмування, зокрема транспортної задачі. Відзначимо лише, що по-перше, жоден з відомих алгоритмів не є досконалим, а по-друге, зажди пропонується шукати один оптимальний план перевезень, а решта оптимальних планів залишається або без уваги, або в кращому випадку залишається на розгляд методами після оптимізаційного аналізу. Досі було важко запропонувати достойну альтернативу цим методам через відсутність потужної обчислювальної техніки, але тепер це можливо[4].

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

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

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



Розділ 2. Вибір методу і його опис

Вибір методу розв'язання багатокритеріальної задачі лінійного програмування. Симплекс метод

Проаналізувавши різні методи розв'язанням багатокритеріальних задач лінійного програмування, я обрала Симплекс-метод.

В останні роки в прикладній математиці велика увага приділяється новому класу задач оптимізації, які полягають у знаходженні в заданій області точок найбільшого або найменшого значення певної функції, що залежить від великого числа змінних. Це так звані завдання математичного програмування, що виникають у найрізноманітніших галузях людської діяльності і перш за все в економічних дослідженнях, в практиці планування і організації виробництва. Вивчення цього кола завдань і методів їх вирішення призвело до створення нової наукової дисципліни, що отримала пізніше назву лінійного програмування. В кінці 40-х років американським математиком Дж. Данцигом був розроблений ефективний метод вирішення даного класу завдань - симплекс-метод. До завдань, що вирішуються цим методом у межах математичного програмування належать такі типові економічні завдання як «Визначення найкращого складу суміші», «Завдання про оптимальний плані випуску продукції», «Оптимізація міжгалузевих потоків», «Завдання про вибір виробничої програми», «Транспортна задача» , «Завдання розміщення», «Модель Неймана розширюється економіки» та інші. Вирішення таких завдань дає великі вигоди як народному господарству в цілому, так і окремих його галузях.

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

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

Застосування симплекс-методу для задачі лінійного програмування передбачає попереднє приведення її формальної постановки до канонічної форми з n невід'ємними змінними: (X 1, ..., X n), де потрібно мінімізація лінійної цільової функції при m лінійних обмеженнях типу рівностей. Серед змінних завдання вибирається початковий базис з m змінних, для визначеності (X 1, ..., X m), які повинні матиневід'ємні значення, коли решта (nm) вільні змінні рівні 0. Цільова функція та обмеження рівності перетворяться до діагональної формі щодо базисних змінних, змінних, де кожна базисна змінна входить лише в одне рівняння з коефіцієнтом 1.

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



Верхній рядок симплекс-таблиці представляє цільову функцію завдання. Кожен рядок симплекс-таблиці, крім першої, відповідаєпевному обмеженню-рівності завдання. Вільні члени обмежень складають крайній лівий стовпець таблиці. Зліва від таблиці записані поточні базисні змінні (X 1, ..., X m). Зверху від таблиці наведено набір всіх змінних задачі, де X m +1, ..., X n - вільні змінні завдання.

На початковому кроці алгоритму симплекс-методу має бути вибрано базисне допустиме рішення (X 1, ..., X m)> = 0 при X j = 0 (j = m +1, ..., n), отже, всі вільні члени обмежень A i, 0> = 0 (i = 1, ..., m). Коли ця умова виконана, симплекс-таблиця називається прямо-допустимої, тому що в цьому випадку базисні змінні, рівні A i, 0, визначають дозволене рішення прямої задачі лінійного програмування.Якщо всі коефіцієнти цільової функції A 0, j> = 0 (j = 1, ..., m), то симплекс-таблиця називається двояко-допустимої, оскільки відповіднерішення є допустимим для двоїстої задачі лінійного програмування.

Якщо симплекс-таблиця є одночасно прямо і двояко допустимої, тобто одночасно всі A i, 0> = 0 і A 0, j> = 0, то рішення оптимально.

Дійсно, оскільки допустимими є лише невід'ємні значення керованих параметрів, то зміна цільової функції за рахунок варіації вільних змінних, через які вона виражена, можливо тільки в бік збільшення, тобто, буде погіршуватися. Якщо серед її коефіцієнтів є A 0, j <0, то значення цільової функції ще можна зменшити (т.e. поліпшити), збільшуючи значення будь-якої вільної змінної X j з негативним коефіцієнтом A 0, j при побічну зменшенні базисних змінних, щоб залишалися справедливі обмеження завдання. Теоретично можна використовувати будь-яку вільну змінну X j з A 0, j <0, але на практиці зазвичай діють у відповідності зі стратегією найшвидшого спуску, вибираючи мінімальний елемент A 0, p <0 з усіх негативних A 0, j <& nbsp0:

A 0, p = min A 0, j <0.

j

Стовпець p симплекс-таблиці, що відповідає обраному коефіцієнту A 0, p <0, називається провідним стовпцем. Вільна мінлива ведучого шпальти повинна бути введена в базис замість однієї з поточних базисних змінних. Очевидно, з базису слід виключити таку зміннуX q, яка раніше інших звертається в нуль при збільшенні змінної X p ведучого шпальти.

Її індекс легко визначити, якщо серед позитивних елементів ведучого шпальти p знайти елемент, здатний мінімізувати відношення (Ai, 0 / A i, p):

A q, 0 A i, 0

------ = Min ------, i = 1 ,..., m.

A q, p i A i, p

Елемент A q, p називається провідним елементом, c Троках q симплекс-таблиці, що містить ведучий елемент, називається, відповідно,провідною рядком. Змінна провідною рядки X q замінюється в базисі змінної ведучого шпальти X p і стає вільною змінної з значенням 0, у той час як нова базисна змінна X p досягне максимально можливого значення, рівного: max X p = (A q, 0 / A q, p).

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

множення рівняння E 1 (X) = 0 на константу K 1 і заміна рівняння E 1 (X) = 0 рівнянням K 1 * E 1 (X) = 0;

складання рівнянь E 1 (X) = 0 і E 2 (X) = 0 c наступною заміною рівняння E 2 (X) = 0 рівнянням E 1 (X) + E 2 (X) = 0.

Винятки Гауса дозволяють привести систему рівнянь до діагональної формі щодо бажаного безлічі змінних. У даному випадку виключення Гауса застосовується так, щоб всі елементи симплекс-таблиці у провідному стовпці, крім ведучого елемента A q, p, стали нульовими, а ведучий елемент став рівним одиниці:

A i, p = 0, якщо i не дорівнює q

і

A i, p = 1, якщо i = q.

Зазначені кроки симплекс-методу повторюються, поки не буде отримана симплекс-таблиця, яка одночасно є прямо і двояко допустимої. Якщо покладе в такій симплекс-таблиці поточні базисні змінні рівними A i, 0, а вільні - нулю, то буде отримано оптимальне рішення.

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



Розділ 3. Постановка і вирішення задачі

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

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

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

Алгоритм розв'язання задач симплекс - методом

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

Отримане математичний опис призводять до канонічної форми.

Канонічну форму призводять до матричному увазі.

Шукають перший допустиме рішення. Для цього матриця повинна бути правильною. Матриця в ЗЛП називається правильною, якщо вона містить мінімум m правильних (базисних) стовпців, де m - число рядків в матриці. Стовпець у канонічній ЗЛП називається правильним (базисним), якщо всі його елементи дорівнюють нулю, крім єдиного рівного одиниці.

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

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

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

Відповідь записується таким чином:

- Кожному негативного коефіцієнту у векторі рішення ставиться у відповідність нульовий коефіцієнт для відповідної змінної у відповіді.

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

- Фіктивні змінні у відповіді не враховуються.

Провідним може бути призначений будь-який стовпець, що задовольняє одній з умов:

1) Перший стовпець, що містить позитивний елемент у векторі рішень.

2) Стовпець, що містить найбільший позитивний елемент у рядку рішення.

3) Якщо стовпець задовольняє умові max (C j min b j / a ij) при вирішенні на max, і m in (C j min b j / a ij) при вирішенні завдань на min.

C j - коефіцієнт цільової функції в стовпці j, a ij - коефіцієнт у стовпці j і рядку i.

Рішення завдання

Визначимо максимальне значення цільової функції

F (X) = 5000 Х1 +4300 Х 2 +6500 Х 3 при наступних умовах обмежень.

2x 1 + 1 x 2 + 3x 3 <= 100

3 x 1 + 0,5 x 2 + 2x 3 <= 250

5 x 1 + 1,5 x 2 + 1 x 3 <= 500

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

2 x 1 + 1 x 2 + 3 x 3 + 1 x 4 + 0 x 5 + 0 x 6 = 100

3 x 1 + 0,5 x 2 + 2 x 3 + 0 x 4 + 1 x 5 + 0 x 6 = 250

5 x 1 + 1,5 x 2 + 1 x 3 + 0 x 4 + 0 x 5 + 1 x 6 = 500

З даних задачі створюємо вихідну симплекс таблицю:

Так як в стовбці вільних членів немає від'ємних елементів, то знайдено допустиме значення. В рядку F є від'ємні елементи, це означає що отримане рішення не оптимальне. Визначимо ведучий стовпчик. Для цього знайдемо в рядку F максимальний за модулем від'ємний елемент - це -6500. Ведучим рядком буде той для якого відношення вільного члена до відповідного елемента ведучого стовбця мінімальне. Ведучим рядком являється X4, а ведучий елемент 3.

В рядку F існують відємні елементи, це означає що отримане рішення не оптимальне. Визначимо ведучий стовпчик. Для цього знайдемо в рядку Fмаксимальний за модулем відємний елемент - це -2133.333. Ведучим рядком буде той для якого відношення вільного члена до відповідного елемента ведучого рядка мінімальне. Ведучим рядком являється Х5, а ведучим елементом 3,333.

Таблица 5

	X1	X5	X4	Своб член
F	400	640	1740	334000
X3	0.5	-0.1	0.4	15
X2	0.5	0.3	-0.2	55
X6	1	-2	1	100

Так як в рядку F немає від'ємних елементів, то знайдено оптимальне рішення

F=334000

при значеннях змінних: X3=15, X2=55, Х1=60.

Отже як висновок можна сказати. Що максимальний прибуток зоомагазину буде 334000 грн. якщо магазин буде продавати 60 вівчарок, 55 пекінесів та 15 чау-чау.

багатокритеріальність задача лінійна



Висновки

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

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

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

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

Хоч кожній залежній змінній одної задачі відповідає функція-умова (нерівність) двоїстої, і кожній функції-умові відповідає залежна змінна, ці пари величин приймають різні значення у розв'язку пари задач.

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



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

Василевич Л.Ф. Теория игр. Уч. Пособие. - Киев: КИИМ.,2000. -98 с.

Василевич Л.Ф. Анализ чувствительности и стабильности нечётких систем. \\ Кибернетика и системный анализ. - 1998. - №1. - С. 166- 171.

Вітлінський В.В., Верчено П.І. Аналіз, моделювання та управління економічним ризиком: Навчально-методичний посібник для самостійного вивчення дисчипліни. - К.:КНЕУ, 2000. - 292 с.

Гєєць В., Клебанова Т.С., Іванов В.В., Дубровіна Н.А., Черняк О.І., Ставицький А. Моделі та методи соціально-економічного прогнозування. -- Х.: Інжек, 2005. - 396 с.

Глухов В.В., Медников М.Д., Коробко С.Б. Математические методы и модели для менеджмента. 2-е изд., испр. и доп. - СПб.: Лань, 2005. - 528 с.

Дробышева В.В., Герасимов Б.И. Интегральная оценка качества жизни населения региона. - Тамбов: ТГТУ, 2004. - 108 С.

Гавриленко В., Пархоменко Л., "Решение задач аппроксимации средствами MS EXCEL", "Компьютеры+программы", №12/2002р., с.42.http://imcs.dvgu.ru/lib/nurmi/finmath/node42.html.

Зайченко Ю.П., Шумилова С.А. Дослідження операцій

Левин С.В., Александрова В.В.: «БАГАТОКРИТЕРІАЛЬНА ОПТИМІЗАЦІЯ З ВИКОРИСТАННЯМ ТЕОРЕТИКО-ІГРОВОГО ПІДХОДУ»: методичні вказівки до виконання курсової роботи з курсу «Математичні методи дослідження операцій» - Харків, Національний аерокосмічний університет ім. М.Є. Жуковського «Харківський авіаційний інститут», 2008 р.

Ліщенко «Лінійне і нелінійне програмування», М. 2003

Наконечний С.І. Математичне програмування / С.І. Наконечний. К.:Вид-во Європейського ун-ту, 2010. 254 с.

Орлов О.І. Теорія прийняття рішень. Навчальний посібник. - М.: Видавництво "Март", 2004

Хачатрян С.Р., Пинегина М.В., Буянов В.П. Методы и модели решения экономических задач: Учебное пособие. - М.: Издательство «Экзамен», 2005. - 384 с.

Черняк О.І, Геєць В.М., Клебанова Т.С. та інші. Моделі і методи соціально-економічного прогнозування: Подручник. - Х.: ВД «ІНЖЕК», 2005. - 396 С.

Черняк О.І., Ставицький А.В. Динамічна економетрика. - К.: КВІЦ, 2000. - 120 С.

Шелобаев С.И. Математические методы и модели в экономике, финансах, бизнесе: Учеб. пособие для вузов. - М.: ЮНИТИ: ДАНА, 2000. - 367 с.

Шелобаєв С.И. Математические методы и модели, Москва, «Юнити», 2000. - 368 С.

Шелобаєв С.И., Нефедова С.В. Моделирование процессов анализа, оценки и управления экономическими и финансовыми рисками, Москва, «Юнити», 2000. - 322 С.

Экономико-математические методы и прикладные модели: Учебное пособие для вузов/ В.В. Федосеев, А.Н. Гармаш, И.В. Орлова и др. - 2-е изд-во, перераб. и доп. - М.: ЮНИТИ-ДАНА, 2005- 304 с.

Размещено на Allbest.ru