11776

Пошук оптимального розв’язку багатокритерійних лінійних задач

Лабораторная работа

Информатика, кибернетика и программирование

Звіт до лабораторної роботи №5 на тему: Пошук оптимального розвязку багатокритерійних лінійних задач З курсу: Математичні методи дослідження операцій Мета: Вивчити методологію розвязання багатокритерійних оптимізаційних задач на прикладі задачі розпо...

Украинкский

2013-04-11

153.21 KB

16 чел.

З в і т

 до лабораторної роботи №5

на тему:

«Пошук оптимального розв’язку багатокритерійних лінійних задач»

З курсу: «Математичні методи дослідження операцій»

Мета: Вивчити методологію розв’язання багатокритерійних оптимізаційних задач на прикладі задачі розподілу ресурсів.

Теоретичні відомості

Багатокритеріальна оптимізація або програмування (англ. Multi-objective optimization) — це процес одночасної оптимізації двох або більше конфліктуючих цільових функцій в заданій області визначення.

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

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

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

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

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

Порядок виконання роботи

  1.  Сформулювати задачу в двох постановках: максимізація прибітку та мінімізація використаних ресурсів;
  2.  Ввести умову отриманої двокритерійної задачі;
  3.  Розв’язати задачу за двома функціями мети окремо з фіксуванням значень іншого критерію;
  4.  Розв’язати задачу та проаналізувати отриманий розв’язок;

16х1+12х2 - > MAX

1  +  3х2 <=  180

1  +    х2 <=  240

1  +  7х2 <=  426

х12>=0

Хід роботи

  1.  Сформулювати задачу в двох постановках: максимізація прибутку та мінімізація використаних ресурсів;

Мінімізація використаних ресурсів:

Т1 +Т2+Т3->MIN

1  +  3х2 1<=  180

1  +    х2 2<=  240

1  +  7х2 3<=  426+Т3

Т12 3>=0

Максимізація прибутку:

    16х1+12х2 - > MAX

1  +  3х2 <=  180+Т1

1  +    х2 <=  240+Т2

1  +  7х2 <=  426+Т3

Т12 3>=0

  1.  Ввести умову отриманої двокритерійної задачі;

Рис.1. Умови  двокритерійної задачі в табличному представленні

  1.  Розв’язати задачу за двома функціями мети окремо з фіксуванням значень іншого критерію;

Рис.2. Розв’язання задачі за мінімізацією витрачених ресурсів

Рис.2. Розв’язання задачі за максимізацією прибутку.

Рис.4. Представлення результатів розв’язання задачі  в табличному вигляді.

Рис.5. Звіт.

Змінивши обмеження щодо випуску продукції отримаємо такі результати:

Рис.6. Розв’язок задачі за мінімізацією витрачених ресурсів

Рис.7. Розв’язок задачі за максимізацією прибутку.

Рис.8. Звіт.

Висновок

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


 

А также другие работы, которые могут Вас заинтересовать

70551. Педагогика и психология: Лекции 746.5 KB
  Еще древний мудрец сказал что нет для человека интереснее объекта чем другой человек. Материалистический подход к пониманию психики был оттеснен идеалистической философией которая рассматривала психику человека как проявление его духовной жизни считая что она не подчиняется...
70552. Программирование: Конспект лекций 7.46 MB
  Обычно BASIC ассоциируется с простым в освоении и использовании средством программирования. Действительно, этот язык долго использовался в качестве учебного языка при изучении основ программирования.
70553. ФИЗИКА ТВЕРДОГО ТЕЛА 1.46 MB
  Физика твердого тела сводится, в сущности, к установлению связи между свойствами индивидуальных атомов и молекул и свойствами, обнаруживаемыми при объединении атомов или молекул в гигантские ассоциации в виде регулярно упорядоченных систем - кристаллов.
70554. ИНФОРМАЦИОННЫЙ МЕНЕДЖМЕНТ 857.5 KB
  Информация играет в обществе все более важную роль. Ее ставят в один ряд с фундаментальными понятиями мироздания: веществом и энергией. Упорядоченную, доступную и активно используемую информацию оценивают как ресурс наряду с материальными, энергетическими, финансовыми...
70555. Происхождение денег: различные подходы к вопросу 346 KB
  Необходимость появления денег была обусловлена объективным развитием производительных сил общества средства производства средства и предметы труда производимые материальные блага и производственных отношений отношения собственности на средства производства обмена...
70556. Конспект лекций: Основы экологии 802 KB
  В этих понятиях нашла отражение идея о единстве совокупности организмов с абиотическим окружением о закономерностях которые лежат в основе связи всего сообщества и окружающей неорганической среды о круговороте вещества и превращениях энергии.
70557. КОНСПЕКТ ЛЕКЦИЙ: ИНФОРМАЦИОННЫЙ МЕНЕДЖМЕНТ 747 KB
  Объектом управления в информационном менеджменте являются: информация в разных формах ее существования; информационные системы и информационные технологии; информационная индустрия и информационный рынок; кадры реализующие функции производства использования и хранения информации.
70558. ІСТОРІЯ ФІЛОСОФІЇ 791 KB
  Моральна філософія наука про правильні вчинки яка поділялась на етику науку про управління діями окремої людини економіку науку про управління господарством політику науку про управління державою. Виходячи із значення яке має філософія як наука в житті й діяльності людини поряд...
70559. Понятие информации, виды информации, сообщения, данные, сигнал 51.49 KB
  Существование информации как свва материи вытекает из фундаментальных свойств материи : структурности непрерывного движения и взаимодействия материальных объектов. Для получения информации имея данные нужны методы преобразования данных в восприятие сознания.