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. Звіт.

Висновок

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


 

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

53570. Управление запасами 29 KB
  Большая величина инвестиций, необходимых для создания запасов материалов группы А и В требуют применения специальных методов для управления их запасами.
53571. Кейс-технология на уроках русского языка 4.22 MB
  Респондентам людям от 15 до 25 лет было предложено объяснить значения слов которые широко употреблялись представителями предыдущих поколений: честь совесть этика мораль патриотизм и др. Респондентам людям от 15 до 25 лет было предложено объяснить значения слов которые широко употреблялись представителями предыдущих поколений: честь совесть этика мораль патриотизм и др. Респондентам людям от 15 до 25 лет было предложено объяснить значения слов которые широко употреблялись представителями предыдущих поколений: честь...
53572. Продукти харчування і здоров’я 156.5 KB
  Мета уроку: Навчальна: формування поняття про харчові добавки штрихкод генномодифіковані продукти. Форма проведення: урокконсультація Тип уроку: урок засвоєння нової інформації Обладнання: виставка інформаційних джерел про здорове харчування і харчові добавки; епіграф уроку; плакати про штрихкод шкідливі добавки про правила покупця; чорний ящик; набори упаковок продуктів...
53573. Харківщина - моя Батьківщина 169 KB
  Кожна дитина повинна зрозуміти що не тільки вчитель а й сам він учень є вихованцем самого себе як індивідуальності а саме: вдосконалювати себе поєднувати в собі єдність слова і діла поглядів і вчинків моралі і поведінки та розвивати традиції народу. Звучить пісня Бабаї Учень Що стоїть за словом Батьківщина Може то садочок пишним цвітом Чи криниця з чистою водою Поле що так смачно пахне літом Чи стеблина поєна росою Учень Знаєш брате мабуть Батьківщина То наша родина й домівка То земля що зветься Україна То село якому...
53574. Театральне та літературне життя Харкова початку ХХ століття 474.5 KB
  Учитель з художньої культури Доброго дня З великим задоволенням пропоную вам розпочати урок під час якого ми познайомимося з надзвичайно цікавою інформацією яка допоможе не тільки краще зрозуміти культурномистецьке життя Харкова на початку ХХ століття а також дасть можливість усвідомити культурні зв’язки між митцями. Заснування стаціонарного театру мало велике значення для розвитку культурномистецького життя.Старицький повість Оборона Буші драматичні твори За двома зайцями та Циганка Аза пісня що стала народною Ніч яка...
53575. Управление дебиторской задолженностью 28.5 KB
  Дебиторская задолженность представляет собой долг покупателей за проданную им продукцию. Длительность финансового цикла и соответственно требуемый объем инвестиций в его обеспечение во многом зависит от периода оборачиваемости дебиторской задолженности.
53576. Источники финансирования деятельности предприятия 26.5 KB
  По отношению к организации источники финансирования подразделяются на внутренние и внешние. К внутренним источникам относятся ресурсы, сформированные внутри организации, а к внешним – средства, формируемые вне предприятия.
53577. Чай пить – не дрова рубить 70.5 KB
  Цели мероприятия: усиление межпредпредметных связей; формирование ответственности за свою работу и работу в группе; ознакомление учащихся с историей чая как напитка; изучение некоторых свойств чая; формирование системы знаний обеспечивающих эстетическое воспитание. Задачи мероприятия: изучение состава и свойств веществ входящих в состав чая; определение основных показателей качества сырья; ознакомление учащихся с информацией о благоприятном влиянии чая на организм человека; стимулирование желания...
53578. Взаимосвязь финансового левериджа и финансового риска 25 KB
  С категорией финансового левериджа связано понятие финансового риска. Финансовый риск — это риск, обусловленный возможным недостатком средств для выплаты процентов по ссудам и займам.