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



 

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

55780. Розв’язування комбінаторних задач 532.5 KB
  Мета дидактична (навчальна): формування умінь і навичок розв’язування різних видів комбінаторних задач, застосовування основних теорем комбінаторики – правил суми та добутку, закріплення відомих методів і способів на практиці, вміння застосовувати знання в комплексі;
55781. Таблиці з логічними зв’язками 1.39 MB
  комірка формула книга немає вірної відповіді Що робить Excel якщо в складеній формулі знаходиться помилка повертає 0 як значення комірки виводить повідомлення про тип помилки як значення комірки виправляє помилку у формулі видаляє формулу з помилкою Яке з посилань є абсолютним З22 R1C2 5 5 Впорядкування значень діапазону коміркок у певній послідовності називають. електронні таблиці графіки й діаграми діапазон комірок сортування й фільтрація Яких форматів числових даних не існує числовий грошовий процентний округлений Логічна функція...
55782. Методична розробка з інженерної графіки, збірка завдань та рекомендацій до виконання розрахунково-графічних завдань 4.87 MB
  Мета розробки - надання допомоги студентам в освоєнні теоретичних і практичних знань, графічних умінь і навиків, активізації процесу і пізнавального інтересу. Розвитку просторових уявлень, мислення і творчих здібностей.
55783. Поняття про мультимедійні дані. Формати аудіо- та відеофайлів. Мультимедійні програвачі 85 KB
  Мета: навчитися: додавати до графічних зображень та тексту слайдів анімаційні ефекти, що супроводжуються звуком; вставляти до слайду презентації звукові об’єкти і настроювати їх параметри.
55784. Музично-виконавський розвиток учня-піаніста в процесі роботи над творами малої форми в 4 класі ДМШ 144.5 KB
  Педагог оголошує тему уроку план уроку в який входять такі твори: П. Педагог. Кілька пєс з цих альбомів вже були в твоєму репертуарі Лєра багато ти чула в концертах Дитячої Філармонії школи а також у записах відомих виконавцівпедагогів. Педагог.
55785. Омбудсмени року 384.5 KB
  Ми не просто розпочати нашу програму з визначення права. Справа в тому що так ми наблизились до першого нашого конкурсу яке і має таку назву Знавці права.
55786. Ой, не вітер в полі грає, не орел літає – ото Сірко з товариством по степу гуляє! 61.5 KB
  Мета: увіковічення та вшанування визначного військово-політичного діяча козацького періоду Івана Сірка; популяризація козацьких звичаїв та традицій серед учнівської...
55787. ПОЛІТИКА ВЛАДИ У ЦАРИНІ КУЛЬТУРИ В 1921-1928 рр. УКРАЇНІЗАЦІЯ (КОРЕНІЗАЦІЯ) 311 KB
  Мета: методична удосконалення методики проведення лекціїдіалогу та активізації пізнавальної діяльності студентів шляхом використання групових форм роботи...
55788. Які правила визначають гармонію людини із собою та найближчим оточенням 245 KB
  Стежка Правдивості Команди слухають визначення понять Додаток 3 які вивчали на попередніх уроках етики потім радяться 30 секунд і записують кожне слово на окремому аркуші паперу.