11776

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

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

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

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

Украинкский

2013-04-11

153.21 KB

15 чел.

З в і т

 до лабораторної роботи №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. Звіт.

Висновок

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


 

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

54562. Розробка уроків (пар) алгебри для 9-го класу з теми «Нерівності» 865 KB
  Разом з розв’язаними вправами вправами для розв’язування біля дошки приклади для самостійного розв’язку учнями роботою з картками домашніми завданнями завданнями для повторення матеріалу за попередні класи та теми все це є єдиним цілим для вчителя який візьме дану розробку і буде спиратися на неї як на свій власний конспект. Включення ж до теми методу інтервалів є логічним кроком при розгляді теорії нерівностей адже він просто губиться при подальшому викладанні і при нагоді може слугувати методом розв’язування квадратичних...
54563. Розвязування квадратичних нерівностей 231 KB
  Мета уроку: Формувати вміння та навички з розвязування Квадратичних нерівностей; розвивати логічне мислення, мову учнів; виховувати цікавість до математики, культуру математичних записів. Тип уроку: урок формування вмінь і навичок. Обладнання: компютера, таблиці.
54564. Лінійні нерівності з однією змінною 51.5 KB
  Мета уроку: систематизувати і узагальнити знання учнів по темі продовжити формувати практичні навики по розвязуванню нерівностей; на прикладах показати учням застосування нерівностей до практичних задач; стежити за дотриманням учнями графічної культури; розвивати математичну мову логічне мислення; вчити учнів працювати з підручником. Що називається розв`язком нерівності Що означає розв’язати нерівність 4. Сформулювати властивості які використовуються при розв’язуванні нерівностей. Ті учні які під час попередньої...
54565. Первые экономические школы. Меркантилисты и физиократы 18.69 KB
  В эту эпоху экономической идеологией молодой торговой буржуазии был меркантилизм (от mercantile — торговый). Меркантилисты не были профессиональными учеными, как правило, это были выходцы из купцов, мелких и средних буржуа. Они точно определили способы получения крупных состояний: торговля, кредит, война.
54566. Біологічне значення, загальний план будови, властивості та розвиток нервової системи 380 KB
  Обладнання: муляж Головний мозок таблиці Нервова система Головний мозок Спинний мозок Нервова клітина Схема рефлекторної дуги презентація Будова спинного і головного мозку роздавальний матеріал: будова нейрона опорний конспект Будова нервової системи Тип заняття: лекція 1год. Велика частина мислителів того часу не представляла значення мозку для психічної діяльності людини і навіть великий Аристотель вважав не мозок а серце вмістилищем душі. Гіппократ вперше відзначив що поранення голови часто ведуть до...
54567. Нетрадиционные формы урока как основная форма организации учебного процесса 192.5 KB
  Опыт школьных преподавателей и исследования педагогов-новаторов показали, что нетрадиционные формы проведения уроков поддерживают интерес учащихся к предмету и повышают мотивацию учения.
54568. Строение вещества. Молекулы 45.5 KB
  Задачи урока: дать представление об атоме и молекуле как о модели строения вещества; выделить значение средств экспериментального исследования в процессе познания; подчеркнуть значение моделирования вещества в познаваемости явлений окружающего мира; продолжить работу по формированию умений делать более общие выводы из наблюдений; формировать убеждения учащихся в познаваемости явлений природы. Еще две с половиной тысячи лет назад обдумывая вопрос о строении вещества греческий философ Демокрит выдвинул гипотезугипотезой называют любое...
54569. НЕТРАДИЦИОННЫЕ ФОРМЫ УРОКОВ МУЗЫКИ В 1 КЛАССЕ В АДАПТАЦИОННЫЙ ПЕРИОД 52.5 KB
  Песня – танец – Если нравится тебе – разучивание. И разучим новую песню Если б не было школ разучивается песня Ну а теперь поехали дальше. Познакомились с народной песней – игрой Бояре 4 УРОК ЛОТО – КОНЦЕРТ В 1 КЛАССЕ ТЕМА УРОКА – ПЕСНЯ ЗАДАЧИ УРОКА ПОЗНАКОМИТЬ УЧАЩИХСЯ С РАЗНЫМИ ВИДАМИ ВОКАЛЬНОГО ЖАНРА. Что такое песня Из самого слова видно – Песня – то что поют.
54570. Нетрадиционные уроки 70 KB
  Как правило у школьников во время такого урока возникает игровое состояние специфическое эмоциональное отношение к действительности. А знания полученные на уроке становятся для них личностно-значимыми эмоционально-окрашенными что помогает более лучше узнать прочувствовать изучаемую тему. Урок-викторина он повышает познавательный интерес творческую и мыслительную деятельность учащихся стимулирует мотивацию.