11776

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

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

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

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

Украинкский

2013-04-11

153.21 KB

12 чел.

З в і т

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

Висновок

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


 

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

36715. Имитационное моделирование случайных событий 117.5 KB
  В каждой задаче в соответствии с вариантом построить имитационную компьютерную модель имитирующую предлагаемое событие или события. С помощью имитационной модели оценить вероятность данного события событий и рассчитать необходимое количество экспериментов. Рассчитать аналитически вероятность предлагаемого события событий и сравнить с расчетами полученными методами имитационного моделирования. Постройте модель имитации данного события.
36716. РАЗРАБОТКА СХЕМЫ И СОЗДАНИЕ СТРУКТУРЫ РЕЛЯЦИОННОЙ БАЗЫ ДАННЫХ 193.5 KB
  Задание № 3 Использую возможности фильтрации данных постройте следующие фильтры для выборки данных в соответствии с приведенными критериями. С помощью Расширенного фильтра из таблицы Административные районы выбрать те районы в которых численность населения превышает 50 тыс. Удалить фильтр. В меню Записи выберите команду Фильтр Расширенный фильтр.
36717. Гидрологический режим реки Амазонки и ее устьевой области 1.61 MB
  Географическое положение бассейна реки (географическая зона, высотный пояс, удаленность от океанов, государственная принадлежность, координаты центра и крайних точек, основные морфометрические характеристики (площадь, длина, ширина бассейна, длина реки), основные притоки – карта-схема бассейна)
36718. Моделирование случайных величин 176 KB
  Три стрелка стреляют каждый по своей мишени делая независимо друг от друга по одному выстрелу. Рассматриваются три случайные величины: число попаданий первого стрелка; число попаданий второго стрелка; число попаданий третьего стрелка; Пусть случайная величина. Три стрелка стреляют каждый по своей мишени делая независимо друг от друга по одному выстрелу. Рассматриваются три случайные величины: число попаданий первого стрелка; число попаданий второго стрелка; число попаданий третьего стрелка; Пусть случайная величина.
36719. РАБОТА С ЗАПРОСАМИ В РЕЛЯЦИОННОЙ БАЗЕ ДАННЫХ СТАВРОПОЛЬСКИЙ КРАЙ 243.5 KB
  Лабораторная работа № 3 Лабораторная работа № 3 РАБОТА С ЗАПРОСАМИ В РЕЛЯЦИОННОЙ БАЗЕ ДАННЫХ СТАВРОПОЛЬСКИЙ КРАЙ Задание № 1 Создайте запрос на основе таблиц Административные районы и Административные центры выбирающий все районы центры которых являются городами. Технология работы Создайте запрос на основе связанных таблиц. Для этого в окне базы данных выберите объект 3апросы Создание запроса в режиме конструктора; В окне Добавление таблицы выделите в списке таблицу Административные районы и щелкните на кнопке Добавить; В...
36720. Заходи по розширенню долі аптечної мережі «Бажаємо здоров’я» на фармацевтичному ринку України 434 KB
  Кожна компанія зацікавлена тривалий час зберігати свій ринок і бути прибутковою. Для цього потрібне постійне вивчення ринку, розробка заходів по підвищенню конкурентоспроможності і збільшенню частки ринку. Збільшення частки ринку включає різноманітні заходи, сюди входять ребрендинг, комплекс просування, розширення існуючої мережі.
36722. РАБОТА С ФОРМАМИ И ОТЧЕТАМИ В РЕЛЯЦИОННОЙ БАЗЕ ДАННЫХ СТАВРОПОЛЬСКИЙ КРАЙ 130.5 KB
  Лабораторная работа № 4 Лабораторная работа № 4 РАБОТА С ФОРМАМИ И ОТЧЕТАМИ В РЕЛЯЦИОННОЙ БАЗЕ ДАННЫХ СТАВРОПОЛЬСКИЙ КРАЙ Задание 1 Создайте ленточную форму на основе таблицы Административные районы и добавьте вычисляемые поля в форму в режиме конструктора в которых будут выводиться итоговые суммы для полей число населенных пунктов площадь территории численность населения и среднее значение для поля плотность населения. Технология работы На основе таблицы Административные районы создайте форму ленточного вида используя Мастер по...