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



 

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

10720. Проблема исторической памяти (ответственность за горькие и страшные последствия прошлого) 76.51 KB
  Проблема исторической памяти ответственность за горькие и страшные последствия прошлого Проблема ответственности национальной и человеческой была одной из центральных в литературе в середине 20ого века. Например А.Т.Твард
10721. Прозові тексти (оповідання) для аналітичної рецепції в курсі Теорія літератури 652.5 KB
  Прозові тексти оповідання для аналітичної рецепції в курсі Теорія літератури Укладач Б.І.Ніколаєв ЗМІСТ 1.Джойс Керол Оутс ЗДІЙСНЕННЯ БАЖАНЬ 2. Джон Чівер АНГЕЛ НА МОСТУ 3. Трумен Капоте ДІТИ В ДЕНЬ НАРОДЖЕННЯ 4. БОРИС ВІАН СТАТИСТ 5. ВОЛОДИМИР ДАНИЛЕНК...
10722. Избранные педагогические сочинения А.С. Макаренко Педагогическая логика 597.69 KB
  Избранные педагогические сочинения А.С. Макаренко Педагогическая логика Не может быть вопроса более для нас важного чем вопрос о логике педагогического средства. Интересно бросить взгляд на историю этого вопроса тем более что история эта очень коротка. Нам нечег...
10723. Прогрессивные технологические процессы (ТП) на основе современных достижений науки и техники 462.12 KB
  Введение Уровень сельскохозяйственного машиностроения является определяющим фактором всего хозяйственного комплекса страны. Важнейшими условиями ускорения развития хозяйственного комплекса являются рост производительности труда повышение эффективности произв...
10724. ИСПОЛЬЗОВАНИЕ ЭЛЕКТРОУСТАНОВОК В СЕЛЬСКОХОЗЯЙСТВЕННОЙ ПРАКТИКЕ 21.38 KB
  ИСПОЛЬЗОВАНИЕ ЭЛЕКТРОУСТАНОВОК В СЕЛЬСКОХОЗЯЙСТВЕННОЙ ПРАКТИКЕ Электрические сети в сельской местности. Электрическими сетями называют часть электрической системы состоящей из трансформаторных подстанций и линий различных напряжений. В сельской местности по эле...
10725. Проектирование системы автоматического регулирования, которая впоследствии была смоделирована в системе MatLab 938.36 KB
  ВВЕДЕНИЕ Важнейшей отраслью промышленности Украины является черная металлургия. От объема производства и качества металла зависит развитие народного хозяйства. Продукция предприятий черной металлургии составляет весомую долю в экспортной политике государства.
10726. Наводнения конца XX в 111.5 KB
  Наводнения конца XX в. Наводнения сопутствуют человеческому обществу с древнейших времен. До наших дней дошли сведения о катастрофических разливах Хуанхэ в 2297 г. до н.э. и на Ниле примерно 3 тыс. лет назад. Но если ранее эти стихийные бедствия были чрезвычайно редкими то за...
10727. СИСТЕМНЫЙ ПОДХОД К МЕНЕДЖМЕНТУ ПРЕДПРИЯТИЯ 64 KB
  Системный подход к менеджменту предприятия Содержание Организация как система и объект управления. Принципы системного подхода. Обеспечение системы управления. Комплексная система управления предприятием. 1.Организация как система и объект...
10728. Разработка сумматора-умножителя 213.7 KB
  Умножение закодированного двоично - четверичного множимого на два разряда в дополнительных кодах. Преобразование множителя производится для исключение из процесса умножения диады 10 и 11 множителя