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



 

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

30401. Переход античных обществ к феодализму 45.38 KB
  Главная особенность сохранение на территории Византии многочисленных пережитков достижений античности: значительность рабского труда в экономике крупные города с развитым ремеслом и торговлей сильное централизованное государство развитая античная культура и римское право. Пережитки античности сдерживали развитие феодальных отношений. Территория Апеннин захвачена варварскими племенами которые сыграли двоякую роль: разрушены многие неэффективные технологии античности особенно рабовладение...
30402. Переход от феодальной к индустриальной цивилизации на истор. Примере 43.19 KB
  Формируется новая система представлений о предназначении и роли человека. Подъем производительных сил уровня материального производства связанный с успехами городов развитием ремесел и зарождением мануфактуры расширением внутренних и международных торговых связей вызвал к жизни потребность в новой идеологии новом отношении человека к самому себе и окружающему миру. Гуманисты эпохи Возрождения провозглашали что ценность человека определяется прежде всего его личными достоинствами а не положением в обществе. Одним из высших достоинств...
30403. Переход к локальной цивилизации в реликтовую фазу на историческом примере 40.1 KB
  Переход к локальной цивилизации в реликтовую фазу на историческом примере Наиболее характерным примером реликтовой цивилизации является остров Пасхи. Поэтому вся древесина ушла на удобрения и статуи задолго до конца цивилизации лишая население шанса покинуть остров каноэ из дерева. В ходе этих действий была разрушена политическая и духовная жизнь цивилизации. Вывод: гибель цивилизации о.
30404. Понятие «цивилизация». Развитие подходов к толкованию термина, история возникновения цивилизационной теории 44.96 KB
  Понятие цивилизация. а Понятие цивилизация Слово цивилизация связано с обозначением качественного рубежа в истории человечества. Понятие цивилизация впервые употребил французский экономист Виктор Мирабо 17151789 в трактате Друг законов в 1757 г. б Развитие подходов к толкованию термина В античные времена цивилизация в лице греческого и римского мира противопоставлялась варварам не владеющим греческим и латинским языками не знающим греческой и римской культуры.
30405. Цивилизационный и формационный подходы к толкованию термина: сходства и различия 73 KB
  Большее внимание уделяется внутреннему миру человека и общественному сознанию при этом сохраняется определяющее значение экономики в развитии человеческой цивилизации Формационный метод позволяет вывести общий закон исторического развития человеческого сообщества и отметить общие черты общественных укладов разных стран и разных народов находящихся на одной исторической ступени живущих при одном общественном строе. Формационный метод не раскрывает особенностей культур и исторических путей народов и других социальных общностей. В пределах...
30406. Цивилизационный и формационный подходы к изучению истории: сходства и различия 35.05 KB
  Формационный подход принцип единства исторического процесса. общественноэкономические формации общество находящееся на определенной ступени исторического развития общество со своеобразными отличительными характеристиками человечество в своем историческом развитии проходит пять основных стадий формаций: первобытнообщинную рабовладельческую феодальную капиталистическую и коммунистическую. однолинейный характер исторического развития некоторые страны не укладываются в эту схему чередования пяти формаций создает определенные...
30407. Структура цивилизации, ее основные элементы 42.35 KB
  Структура цивилизации ее основные элементы ОБЩЕСТВЕННОЕ СОЗНАНИЕ ДУХОВНЫЙ МИР наука культура образование мораль идеология религия СОЦИАЛЬНОПОЛИТИЧЕСКИЕ ОТНОШЕНИЯ социальные национальные политические государственные правовые ЭКОНОМИЧЕСКИЙ СПОСОБ ПРОИЗВОДСТВА структура воспроизводства формы собственности обмен распределение экономическое управление ТЕХНОЛОГИЧЕСКИЙ СПОСОБ ПРОИЗВОДСТВА средства труда источники энергии предметы труда природные ресурсы технологии организация производства ЧЕЛОВЕК СЕМЬЯ НАРОДОНАСЕЛЕНИЕ потребности способности...
30408. Неолитическая революция. Динамика развития цивилизации, этапы ее развития на историческом примере 33.35 KB
  Падают темпы роста производительности общественного труда разражается новый кризис завершающий фазу зрелости. В основе прогресса лежали ступени общественного разделения труда сделавшие возможным производство прибавочного продукта. Выделение скотоводов и земледельцев →новые орудия труда обмен продуктами труда. Признаки кризиса: недостаток орудий труда зависимость от источников сырья падение производительности труда и численности населения сложившаяся система экономических отношений не удовлетворяла запросы производителей...
30409. Переходный период цивилизаций: основные этапы и итоги 30.38 KB
  В духовной сфере зарождаются новые открытия экономические общественно-политические теории. Формируются новые технологии. Механизмы старой цивилизации рушатся а новые еще не установлены. Во время перехода на всех этажах пирамиды сталкиваются старые и новые.