11776

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

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

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

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

Украинкский

2013-04-11

153.21 KB

13 чел.

З в і т

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

Висновок

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


 

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

67597. Основные соотношения комбинаторики 217 KB
  Сколькими способами можно в совокупности добраться от Москвы до райцентра через Уфу 1. Сколькими способами можно выбрать конверт с маркой 1. Сколькими способами можно сделать этот выбор 1. Сколькими способами можно выбрать на шахматной доске белую и черную клетки не лежащие на одной горизонтали или вертикали...
67598. Теория графов 107.5 KB
  Понятия смежности инцидентности степени опр Если x={vw} ребро то v и w концы ребра x. опр Если x=vw дуга орграфа то v начало w – конец дуги. опр Если вершина v является концом ребра x неориентированного графа началом или концом дуги x орграфа то v и x называются инцидентными.
67599. Матрицы смежности и инцидентности 128 KB
  Пусть утверждение верно для цикла длиной k-1. Допустим, в цикле имеются совпадающие вершины: vi=vj, (если их нет, то цикл - простой). Тогда удалим из цикла часть, заключенную между viи vj (вместе с vj). Получившийся цикл имеет меньшую длину и в силу индуктивного предположения из него можно выделить простой цикл.
67600. Связность. Компоненты связности 135 KB
  Компоненты связности Определения. Компонентой связности графа G сильной связности орграфа D наз. Матрицы достижимости и связности Пусть D – матрица смежности ориентированного псевдографа D=VX или псевдографа G=VX где V={v1 vn}. Тогда отношение эквивалентности...
67601. Задача поиска маршрутов в графе (путей в орграфе) 362.5 KB
  Исходя из некоторой вершины всегда следовать по тому ребру которое не было пройдено или было пройдено в противоположном направлении. 3 Для всякой вершины отмечать ребро по которому в вершину попали в первый раз 4 Исходя из некоторой вершины идти по первому заходящему в ребру лишь тогда когда нет других...
67602. Минимальные пути, (маршруты) в нагруженных орграфах (графах) 223.5 KB
  Примеры латинских свойств. Не проходить через данную вершину (или через множество вершин). Не проходить через данную дугу (или через множество дуг). Быть простой цепью (или простым контуром). Быть цепью или контуром. Не проходить через каждую вершину более k раз.
67603. Эйлеровы циклы и цепи 62 KB
  Если в псевдографе G имеется хотя бы одно ребро и отсутствуют висячие вершины то G содержит хотя бы один простой цикл. Для того чтобы связный псевдограф G обладал эйлеровым циклом необходимо и достаточно чтобы степени всех его вершин были четными. Для того чтобы связный псевдограф G обладал эйлеровой цепью...
67604. Планарность и раскраска графов 97.5 KB
  Такая функция называется плоским мультиграфом. Внутренние грани плоского мультиграфа называется конечная плоскость окруженная простым циклом и не содержащая внутри себя никаких ребер. Называется её границей.
67605. Булева алгебра, математическая логика, алгебра логики 273 KB
  Каждому двоичному набору можно сопоставить число номер опр расстоянием Хемминга между вершинами и куба называется число опр наборы и называются соседними если и противоположными если все координаты разные.