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



 

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

42375. Адміністрування безпеки операційної системи WINDOWS 2k 479 KB
  С помощью утилиты NET. Выполнить исследование локальной сети с помощью утилиты NBTSTT программы PWLTOOLS. С помощью утилит User2sid и Sid2user определить перечень логинов пользователей на том же удаленном компьютере что и в пункте 4.] Выполнить тестирование компьютера указанного в пункте 4 с помощью программы DDoSPing.
42376. Програмні засоби для шифрування та приховування інформації 1.79 MB
  С помощью программы PGP выполните обмен зашифрованной информацией. Для этого необходимо: а с помощью утилиты PGPkeys создать ключевую пару подчиняясь следующему порядку: выполнить запуск Strt Пуск Progrms Программы PGP PGPkeys необходимо указать собственное имя Full nme и адрес электронной почты Emil ddress не забывая что именно эти данные будут ассоциированы программой с вашими ключами выбор типа ключа Key Pir Type: ключ RS действительно архаичнее и медленнее своего ретивого молодого собрата DiffieHellmn DSS однако...
42377. Використання M.EXCEL в розвязанні матричних ігор 437.5 KB
  Планується до випуску Кі варіанти конструкції нового товару. Виготовлення їх можливо за допомогою одного з альтернативних технологічних процесів Тj . Експерти оцінили споживчі властивості конструкції Кі , виготовленої за допомогою технологічного процесу Тj за десятибальною шкалою в аij балів. Конструкція, яка має більший бал якості, має також і більшу собівартість. Ресурси обмежені, тому менеджерам необхідно прийняти компромісне рішення. Обґрунтувати прийняте рішення.
42378. Работа с пакетом Microsoft Office (Word, Excel, Access, PowerPoint) 699.5 KB
  Для таких целей следует использовать команду меню Формат Абзац и в диалоговом окне установить необходимые отступы и интервалы. Установка первых строк производится с помощью команды меню Формат Абзац или масштабной линейки. Изучите пункты меню панели инструментов и элементы окна. Рисунок 1 Рабочее окно программы Word Установите поля: левое 25 см правое 15 см верхнее и нижнее 2 см через меню Файл команду Параметры страницы.
42379. Текстовый процессор Word «Приемы и средства автоматизации разработки текстовых документов» 63 KB
  Формула задается как выражение в котором использованы: абсолютные ссылки на ячейки таблицы в виде списка 1; B5; E10 или блока 1:F10; ключевые слова для ссылки на блок ячеек: LEFT ссылка на ячейки расположенные в строке левее ячейки с формулой; RIGHT ссылка на ячейки расположенные в строке правее ячейки с формулой; BOVE ссылка на ячейки расположенные в столбце выше ячейки с формулой; BELOW ссылка на ячейки расположенные в столбце ниже ячейки с формулой; константычисла текст в двойных кавычках; закладки...
42380. Операционная система Windows XP: настройка операционной системы Windows, оформление Рабочего стола, настройка Проводника 148.5 KB
  Работа с архиватором WinZip: создание самораспаковывающегося и защищенного архива извлечение файлов из ZIPархива. Что такое многотомный архив Как добавить файл в архив Какие вы знаете архиваторы Их особенности для различных видов информации. ПРИЛОЖЕНИЕ В Работа с архиватором WinZip Запустите WinZip 8. Дайте команду File New rchive Файл Создать архив.
42381. Приемы и средства автоматизации разработки текстовых документов в Excel 62 KB
  Изучите основные понятия: Относительная ссылка указывает на ячейку основываясь на ее положении относительно ячейки в которой находится формула например на две строки выше. Относительная ссылка это изменяющийся при копировании и перемещении формулы адрес ячейки содержащий исходное данное. Абсолютная ссылка это не изменяющийся при копировании и перемещении формулы адрес ячейки содержащих исходное данное. Заполните таблицу: При заполнении таблицы используйте: Выделите А1:Е1 выберите Формат Ячейки Выравнивание Объединение ячеек...
42382. Построение диаграмм с помощью мастера диаграмм 221 KB
  Требования к изученному материалу: уметь строить графики математических функций; строить диаграммы по экономическим задачам; уметь изменять тип параметры построенных диаграмм; уметь добавлять диапазон данных к построенной диаграмме; уметь добавлять легенды. В Excel существуют стандартные и нестандартные диаграммы. В следующем окне рисунок 2 появляется образец диаграммы. Далее подписать заголовки: название диаграммы График квадратной функции; Ось Х Х; Ось У У; убрать линии сетки и подписи.
42383. Текстовый процессор Word «Шаблоны. Создание шаблона» 36.5 KB
  Создание шаблона Цель этой практической работы создать шаблон доверенности и затем оформить доверенность на основе созданного шаблона. Доверенность это документ выдаваемый организациейдоверителем физическому лицу поверенному на право выполнения от имени организациидоверителя указанных в доверенности действий. Формуляр доверенности включает в себя следующие реквизиты: наименование вида документа и его порядковый номер дата составления документа место составления документа текст подпись руководителя организациидоверителя В тексте...