3959

Прийняття рішень при векторному критерії оптимальності. Здачі багатокритеріальної оптимальності

Лекция

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

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

Украинкский

2012-11-10

115.12 KB

15 чел.

Лекція №2

ПРИЙНЯТТЯ РІШЕНЬ ПРИ ВЕКТОРНОМУ КРИТЕРІЇ ОПТИМАЛЬНОСТІ

Задачі багатокритеріальної оптимізації.

Перейдемо до розгляду інформаційних технологій розв'язку ряду задач векторної оптимізації. У

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

розв'язку задач будемо використовувати процесор електронних таблиць Excel, здатний досить

просто й ефективно вирішувати задачі подібного роду.

Приклад 1. Згортання системи показників ефективності

Розглянемо наступну задачу векторної оптимізації

F ( x1 , x2 ) = α 1 f1 ( x1 , x 2 ) + α 2 f 2 ( x1 , x 2 ) → max ;

де цільові функції й відповідні їм обмеження мають вигляд:

f1 ( x1 , x2 ) = 2 x1 + 5 x2 + 4 x3 ;

f 2 ( x1 , x2 ) = 3x1 + 4 x2 + 4 x3 ;

x1 + x2 + x3 ≤ 45;

x1 + 2 x2 + x3 ≤ 40;

2 x1 + 3x3 ≤ 75;

2 x1 + 4 x3 ≤ 90;

3x1 + 4 x2 ≤ 50;

3 x1 + 2 x2 ≤ 25;

x1 , x2 ≥ 0

Розв'яжемо задачу в Excel і проаналізуємо залежність одержуваного розв'язку від значення

коефіцієнтів α1 , α 2 .

Внесемо дані на робочий аркуш відповідно до Рис. 1. Під значення змінних відведемо

комірки A16:C16. У комірки A6:A8 і A10:A12 уведемо формули, що визначають обмеження на

значення змінних, у комірки E16 і G16 – формули для розрахунків відповідних цільових

функцій, у комірку F20 – формулу для розрахунків функції F ( x1 , x2 ) .

Надзвичайно важливим є використання в даному методі загальної для всіх функцій

системи обмежень.

1


Рис. 1. Дані для розв'язку прикладу 1.

Викличемо Пошук розв'язку й задамо область зміни змінних, цільову комірку й систему

обмежень стандартним чином. У результаті одержимо відповідь: ( для даних значень

параметрів α1 , α 2 (див. Рис. 1))

(1)

Fmax ( x1 , x2 ) =126.75.

Вважаючи значення параметрів рівними, наприклад, α1 = 0,7 , α 2 = 0,3 , одержимо інше

( 2)

оптимальне значення досліджуваної функції Fmax ( x1 , x2 ) =131.125.

Таким чином, можна

зробити висновок про досить істотну чутливість значень даної оптимізуємої функції до варіацій

вагових коефіцієнтів.

2


Приклад 2. Обмеження на критерії. Метод послідовних поступок.

Обмежимося для простоти задачею лінійної оптимізації (лінійного програмування).

Нехай необхідно розв'язати задачу векторної оптимізації наступного виду

F ( x) = { f 1 = x1 + 3 x 2 , f 2 = 40 x1 + 10 x 2 } → max

при обмеженнях

2 x1 + x 2 ≤ 90,

x1 + x 2 ≤ 60,

x 2 ≤ 50,

x1 , x 2 ≥ 0

методом послідовних поступків, якщо поступка за першим критерієм становить 10% від його

оптимального значення.

Розв'язок. Розв'яжемо задачу за критерієм f1 , у результаті чого одержимо f 1* = 160 . Відповідно

до

умови

задачі

величина

поступки

∆ 1 =16 .

Додаткове

обмеження

буде

мати

вигляд: f 1 (x) ≥ f 1* − ∆1 , тобто x1 + 3x 2 ≥ 160 − 16 = 144 . Вирішуючи задачу

{ f 2 = 40 x1 + 10 x 2 } → max

2 x1 + x 2 ≤ 90,

x1 + x 2 ≤ 60,

x 2 ≤ 50,

x1 + 3 x 2 ≥ 144,

x1 , x 2 ≥ 0

*

*

*

*

*

*

одержимо x1 =18, x 2 = 42, f 2 ( x1 , x 2 ) = 1140, f 1 ( x1 , x 2 ) =144 .

Проведемо розв'язок задачі за допомогою Excel. Введемо дані на робочий аркуш

відповідно до Рис. 2.

Відведемо під значення змінних комірки A19 і B19, введемо формули, що визначають

обмеження вихідної задачі, у комірки A13:A15; формулу для цільової функції в комірку E19, а

формулу для розрахунків f 1 (x) ≥ f 1* − ∆1

у комірку H19. Пошук розв'язку дає значення

f1* =144 . Далі, копіюємо значення із комірки E19 у комірку З26 (використовується спеціальна

вставка – тільки значення). Потім відводимо під цільове гніздо E26, уводимо в неї формулу

для розрахунків f 2 , а в комірку A26 уводимо формулу =A19+3*B19, що представляє собою

додаткове обмеження задачі.

При вторинному запуску Пошуку розв'язку поряд із уже введеними на першому етапі

обмеженнями вводимо ще одне додаткове обмеження A26>=144.

3


У результаті розрахунків одержимо відповідь

*

*

*

*

*

*

x1 = 18, x 2 = 42, f 2 ( x1 , x 2 ) = 1140, f 1 ( x1 , x 2 ) = 144 .

Рис. 2. Дані для розв'язку задачі оптимізації по методу послідовних поступків.

Приклад 3. Цільове програмування

Провести оптимізацію вектор – функції F (x)

F (x) = { f1 , f 2 , f 3 } → max , где

f1 = ( x1 + 2 x2 ) ⋅ exp(− x2 ), f 2 = (3x1 + 2 x2 ) ⋅ exp(−(3 x1 + x2 )), f 3 = x1 + x2

при обмеженнях

2 x1 + x2 ≤ 2,

x2 − x1 ≤ 3,

x1 , x2 ≥ 0.

4


Рис. 3. Дані для розв'язку прикладу 3.

Розв'язок. Введемо дані на робочий аркуш відповідно до Рис.3.

Відведемо під значення змінних комірки A20 і B20; уведемо формули, що визначають

обмеження задачі, у комірки A16:A17; формули для розрахунків функцій f 1 , f 2 , f 3 у комірки

~

E20, G20 і I20, а формулу для розрахунків d ( F , F ) - у комірку C28. Оскільки наші функції

нелінійні, у вікні діалогу Параметри пошуку розв'язку необхідно зняти прапорець (покажчик)

лінійна модель.

Далі послідовно проводимо пошук оптимальних (максимальних) значень функцій

f 1 , f 2 , f 3 (цільовими комірками обираємо E20, G20 і I20); після знаходження оптимальних

значень кожної з функцій її максимальне значення затягуємо (використовуючи спеціальну

вставку) у комірки E24, G24 і I24 відповідно. Таким чином, у комірках виявляться значення:

1.0748 (E24), 0.7357 (G24), 2 (I24).

5


Після цього переходимо до заключного етапу. Оптимізуємо (мінімізуємо) значення

~

цільової функції d ( F , F ) (цільова комірка З28). Пошук розв'язку дає для оптимального значення

цільової функції значення 0,32534. При цьому в комірках E20, G20 і I20 виявляться значення

~

функцій f 1 , f 2 , f 3 , відповідні до значень x1 , x 2 , при яких відхилення F ( x1 , x 2 ) від F буде

мінімальним.

Таким чином, при даних значеннях вагових коефіцієнтів ми одержуємо наступні

оптимальні (з погляду досягнення оптимального значення “сукупної” функції F (x) ) значення

компонент вектор функції:

~

f1

f1

~

f2

f2

~

f3

f3

1,0748

0,7815

0,7358

0,3609

2

1,6784

З вищенаведеної таблиці видно, що в результаті оптимізації F (x) значення всіх трьох

функцій-складових зменшилися. Природно, при використанні інших вагових коефіцієнтів ми

одержали б інші значення

f 1 , f 2 , f 3 (але при будь-яких значеннях вагових коефіцієнтів

тенденція зменшення всіх компонентів вектор-функції зберігається).

Слід зазначити, що задача цільового програмування може формулюватися трохи іншим

способом. ЛПР може просто вказати, виходячи зі своїх міркувань, бажані з його погляду,

~ ~ ~

значення f1 , f 2 , f 3 , або діапазони, у яких ці значення повинні бути локалізовані. При цій

постановці задачі вирішується практично аналогічно, з тим відмінністю, що пошук

оптимальних значень компонент (перша частина розв'язку) не проводиться, а їх значення (або

діапазони зміни) уводяться в якості обмежень додатково до вихідних обмежень задачі.

6



 

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

83021. Господарсько-правовий статус інвестиційних фондів в Україні 74.88 KB
  Метою роботи є визначення поняття та видів інститутів спільного інвестування аналіз правового режиму та особливостей їх господарської діяльності а також виявлення недоліків та розробка основних напрямків вдосконалення діяльності інвестиційних фондів та інвестиційних компаній на ринку цінних паперів.
83022. Кадастрове забезпечення формування об’єктів земельної власності 260.5 KB
  Земельний кадастр це методологічно облаштований реєстр даних по земельні ділянки в межах окремої території або країни в цілому який базується на зйомках меж. Згідно із Законом України Про Державний земельний кадастр державний земельний кадастр - це єдина державна геоінформаційна система...
83023. Розробка системи автоматизованого керування процесу прання пральної машини-автомат 812 KB
  Пройшло багато часу і сучасні пральні машини зовсім не схожі на ті, які були сто років тому. У автоматичних пральних машинах, що представляють сьогодні майже весь асортимент машин, наявний на ринку, усі операції з прання виконуються автоматично відповідно з численними циклами.
83024. Бухгалтерський баланс 81.77 KB
  Метою практичної частина курсової роботи є закріплення теоретичних знань при заповненні вступного балансу, складанні бухгалтерських проводок, відкриття рахунків синтетичного і аналітичного обліку, складанні оборотної відомості, а також складанні заключного балансу з використання типової форми бухгалтерської звітності.
83025. Розробка конструкції моделі жіночого демісезонного пальто та її модифікай 459 KB
  Визначення вихідних для проектування нової моделі одягу. Огляд тенденцій моди по заданому асортименту одягу. Найбільшої сили естетичне виховання досягає лише тоді коли увесь предметний світ оточуючий людину буде пронизаний красою гармонією коли культура в поведінці і одягу стане нормою.
83026. РОЗРОБКА ОПТИМАЛЬНОГО СТРАТЕГІЧНОГО ВИКОРИСТАННЯ ЛЮДСЬКОГО ПЕРСОНАЛУ 458 KB
  Провідна роль високоякісної робочої сили у забезпеченні перспектив розвитку вітчизняних підприємств обумовлює обєктивну необхідність постійного зростання кваліфікаційного рівня персоналу що відбувається шляхом безперервного розвитку працівників.
83027. Аналізом собівартості продукції 364.5 KB
  Добре відомо що покупця в першу чергу цікавить якість продукції і її ціна. Резерви поліпшення цих показників якраз і поміщені в собівартості продукції. В узагальненому вигляді собівартість продукції відображає всі сторони господарської діяльності підприємств їх досягнення і недоліки.
83028. Динаміка метеорологічних величин на прикладі метеостанції міста Бережани з 1991 по 2013 роки 1.64 MB
  Поставлена мета обумовила необхідність розвязання наступних завдань дослідження: зібрати метеорологічні дані із фондових матеріалів метеостанції у місті Бережани за період від січня 1991 по грудень 2013 років; із отриманих даних створити бази даних у програмі Microsoft Аccess...
83029. Аудит виробничих запасів підприємства ТОВ «Комсомольськхліб плюс» 160.87 KB
  Мета курсової роботи полягає в дослідженні методології аудиту виробничих запасів та контролю за їх рухом і наявністю. Для досягнення поставленої мети аудиту а також задоволення потреб користувачів в отриманні нової правдивої та неупередженої інформації щодо запасів аудитору потрібно...