Модели МКО. Целевое программирование

Тема 4. Модели МКО. Целевое программирование Лекция 11 2 Формальная постановка задачи многокритериальной оптимизации H1 ( x)  max, H 2 ( x)  max, H r ( x)  max, x  ( x1 , x2 ,..., xn )  Dx 𝐷𝑥 – множество (область) допустимых решений 𝐻𝑘 (𝑥) – критерии (цели), 𝑟 ≥ 2 3 Особенности целевого программирования  упорядочение критериев по степени важности;  формализация целей не как целевых функций, а как ограничений в другой, более общей, модели;  применяется, в основном, для линейных задач. 4 Пример 1. Faze Linear Company Фирма Faze Linear производит компоненты для аудиосистем: звуковые усилители (ЗУ) и усилители мощности (УМ). Ресурс 5 На 1 компонент УМ Транзисторы, шт ЗУ - Суточный запас ресурса 1 40 шт. Время сборки, ч 1,2 4 240 ч Контрольное тестирование, ч ПРИБЫЛЬ, $ 0,5 1 81 ч 200 500 Цели:  получить прибыль, равную $ 40 000;  сократить (минимизировать) общее время тестирования готовых изделий Пример 1. Faze Linear Company. Математическая модель 1. Переменные 𝑥1 , шт. – количество ЗУ, производимых в плановый период 𝑥2 , шт. – количество УМ, производимых в плановый период 2. Целевая функция – прибыль: max( 200 x1  500 x2 ) 3. Ограничения: x2  40 – запас транзисторов 1,2 x1  4 x2  240 – время сборки 0,5 x1  1x2  81 – время тестирования x1  0, x2  0 6 Графическое решение задачи 7 Графическое решение задачи Решение: x2 x1*  105 шт., H1  200x1  500x2 x2*  28,5 шт., L*  $35250 40 B A ОДР O C D x1 200 162 8 Пример 1. Faze Linear Company Менеджеры Faze Linear стремятся к достижению двух целей:  Цель 1: получить прибыль равную $40 000,  Цель 2: сократить общее время тестирования готовых изделий 9 Поиск допустимых решений x2 200x1  500x2  40000 (1) x2  40 (2) 1,2 x1  4 x2  240 (3) 0,5 x1  x2  81 (4) 200 x1  500 x2  40000 (5) x1  0, x2  0 40 A B C ОДР O D 162 10 200 x1 Цель 1. Дополнительные переменные. 200 x1  500 x2  40000 200 x1  500 x2  d1  d1  40000 d1 , d1  0 – «недостаточная» переменная. Показывает, на сколько объем прибыли меньше $40 000. d1 , d1  0 – «избыточная» переменная. Показывает, на сколько объем прибыли больше $40 000. 11 Целевые ограничения (мягкие) 200 x1  500 x2  d1  d1  40000 d1  0, d1  0  – отвечает за степень достижимости Цели 1: 1 d   d 1 0  d1  0    d1  0  1  1 d 0 min d  0  12 Цель 1 достигнута Цель 1 недостижима Цель 2. Дополнительные переменные. 0,5 x1  x2  81 0,5x1  x2  d 2  d 2  81 d 2 , d 2  0 – «недостаточная» переменная. Показывает, на сколько общее время тестирования меньше 81 ч. d 2 , d 2  0 – «избыточная» переменная. Показывает, на сколько общее время тестирования больше 81 ч. 13 Целевые ограничения (мягкие) 0,5x1  x2  d 2  d 2  81 d 2  0, d 2  0 d  – отвечает за степень достижимости Цели 2: 2   d 2  0  d2  0     d 2  0  2  2 d 0 min d  0  14 Цель 2 достигнута Цель 2 недостижима Ограничения задачи x2  40 1, 2 x1  4 x2  240 0, 5 x1  x2  81 Жесткие ограничения x2  40 x1  0, x2  0 1,2 x1  4 x2  240 x1  0, x2  0 Мягкие ограничения 200 x1  500 x2  d1  d1  40000 0,5x1  x2  d 2  d 2  81 d1  0, d1  0, d 2  0, d 2  0 15 Новая задача многокритериального программирования min d1 min d 2 x2  40 1,2 x1  4 x2  240 x1  0, x2  0 200 x1  500 x2  d1  d1  40000 0,5x1  x2  d 2  d 2  81 d1  0, d1  0, d 2  0, d 2  0 16 Метод весовых коэффициентов решения задачи целевого программирования Целевая функция – взвешенная сумма целевых функций: r H ( x)   pi  H i ( x) i 1 H (x ) – обобщённая целевая функция (свёртка) pi 17 – веса, определяющие важность каждой из целей, 𝑖 = 1, … , 𝑟. Метод весовых коэффициентов решения задачи целевого программирования Математическая модель  min p1d1  p2 d 2  x2  40 1,2 x1  4 x2  240 x1  0, x2  0 200 x1  500 x2  d1  d1  40000 0,5 x1  x2  d 2  d 2  81 d1  0, d1  0, d 2  0, d 2  0 18 Метод приоритетов решения задачи целевого программирования 19 1. Ранжирование целей в порядке уменьшения значимости. 2. Последовательное решение однокритериальных задач (с первой до последней) при дополнительном условии: решение каждой последующей задачи не ухудшает значение более значимых задач. Графическое решение. Приоритеты: Цель 1, Цель 2 x2 81 80 0,5x1  x2  81 min d1 x2  40 1,2 x1  4 x2  240 d1 60 x1  0, x2  0 d1 200x1  500x2  40000 40 d 2 ОДР d 2 20 О 162 200 x1 Графическое решение. Приоритеты: Цель 1, Цель 2 x2 81 80 min d1 x2  40 1,2 x1  4 x2  240 200x1  500x2  40000 x1  0, x2  0 d1 60 d1 min d1  0  Цель 1 достигнута 40 A( 200 ,0) ОДР 21 О A 162 200 x1 Графическое решение. Приоритеты: Цель 1, Цель 2 x2 81 80 d 2  0,5  200  0  81  19 min d 2 x2  40 1,2 x1  4 x2  240 x1  0, x2  0 d1  0  1 d 60 min d 2  19  0  Цель 2 недостижима  1 d 40 d 2 ОДР A d 2 22 О A( 200 ,0) 162 200 x1 Графическое решение. Приоритеты: Цель 2, Цель 1 x2 81 80 min d 2 x2  40 1,2 x1  4 x2  240 x1  0, x2  0 0,5x1  x2  81 min d 2  0  Цель 2 достигнута 60 40 ОДР СD С d 2 – множество решений d 2 23 О 162 D 200 x1 Графическое решение. Приоритеты: Цель 2, Цель 1 x2 81 80 С: min d1 x2  40 1,2 x1  4 x2  240 0,5 x1  x2  81  1,2 x1  4 x2  240 d1 60 x1  0, x2  0 d 2  0 С (105 ;28,5) d1 40 ОДР С d 2 d 2 24 О 162 D 200 x1 Графическое решение. Приоритеты: Цель 2, Цель 1 x2 81 80 d1  40000  200 105  500  28,5   4750 d1 60 d1 40 ОДР С d 2 d 2 25 О 162 200 x1 Графическое решение. Приоритеты: Цель 2, Цель 1 x2 81 80 min d1  4750  0  Цель 1 недостижима d1 60 d1 40 ОДР С d 2 d 2 26 О 162 200 x1 Пример 2. Задача о размещении рекламы “Priceler” Рекламному агентству необходимо разместить на телевидении рекламу автомобильной компании «Priceler». В соответствие с пожеланиями «Priceler» данная реклама должна быть просмотрена:  не менее, чем 40 млн. мужчин, чей уровень дохода достаточно велик (HIM) – цель 1;  не менее, чем 35 млн. женщин, чей уровень дохода тоже велик (HIW) – цель 2;  не менее 60 млн. людей среднего достатка (LIP) – 27 цель 3. Пример 2. Задача о размещении рекламы “Priceler” Агентство может показывать рекламный ролик во время трансляции футбольного матча или во время «мыльной оперы». Суммарные расходы на рекламу не должны превысить $600 000. Время показа Футбольный матч «Мыльная опера» 28 HIM LIP HIW Стоимость 7 10 5 $100 000 3 5 4 $60 000 Пример 2. Задача о размещении рекламы “Priceler”. Математическая модель 1. Переменные 𝑥1 , шт. – количество показов рекламного ролика во время трансляции футбольного матча 𝑥2 , шт. – количество показов рекламного ролика во время «мыльной оперы» 2. Целевые функции 7 x1  3 x2  40 100000 x1  60000 x2  600000 5 x1  4 x2  35 x1  0, x2  0 10 x1  5 x2  60 29 3. Ограничения: Пример 2. Задача о размещении рекламы “Priceler” Математическая модель 7 x1  3 x2  40 5 x1  4 x2  35 10 x1  5 x2  60 100000 x1  60000 x2  600000 x1  0, x2  0 Множество допустимых решений 30 Поиск допустимых решений в Excel 31 Поиск допустимых решений в Excel 32 Системы ограничений в задаче  1  1  2  2 7 x1  3 x2  d  d  40 5 x1  4 x2  d  d  35 Мягкие ограничения 10 x1  5 x2  d3  d3  60  i  i d  0, d  0, i  1,..,3 100000 x1  60000 x2  600000 x1  0, x2  0 Жёсткие ограничения 33 Приоритеты  Цель 1: HIM ≥ 40  Цель 1: HIM = 40  Цель 2: HIW ≥ 35  Цель 2: HIW = 35  Цель 3: LIP ≥ 60  Цель 3: LIP = 60 34 Целевое программирование. Шаг 1. Математическая модель  1 min d 7 x1  3 x2  d1  d1  40 5 x1  4 x2  d 2  d 2  35  3  3 10 x1  5 x2  d  d  60 di  0, di  0 100000 x1  60000 x2  600000 x1  0, x2  0 35 Шаг 1. Начальное решение в Excel min d1 7 x1  3 x2  d1  d1  40 5 x1  4 x2  d 2  d 2  35 10 x1  5 x2  d3  d3  60 di  0, di  0 100000 x1  60000 x2  600000 x1  0, x2  0 7 x1  3x2  d1  d1 7 x1  3 x2 36 di di Шаг 1. Оптимальное решение в Excel Цель 1: HIM = 40 достигнута 37 Шаг 2. Математическая модель min d 2 d1  0 7 x1  3 x2  d1  d1  40 5 x1  4 x2  d 2  d 2  35 10 x1  5 x2  d3  d3  60 di  0, di  0 100000 x1  60000 x2  600000 x1  0, x2  0 38 Шаг 2. Начальное решение в Excel min d 2 d1  0 7 x1  3 x2  d1  d1  40 5 x1  4 x2  d 2  d 2  35 10 x1  5 x2  d3  d3  60 di  0, di  0 100000 x1  60000 x2  600000 x1  0, x2  0 39 Шаг 2. Оптимальное решение в Excel 40 Цель 2: HIW = 35 недостижима Шаг 3. Математическая модель min d3 d1  0 d 2  3,333 7 x1  3 x2  d1  d1  40 5 x1  4 x2  d 2  d 2  35  3  3 10 x1  5 x2  d  d  60 di  0, di  0 100000 x1  60000 x2  600000 x1  0, x2  0 41 Шаг 3. Начальное решение в Excel min d3 d1  0 d 2  3,333 7 x1  3 x2  d1  d1  40 5 x1  4 x2  d 2  d 2  35 10 x1  5 x2  d3  d3  60 di  0, di  0 100000 x1  60000 x2  600000 x1  0, x2  0 42 Шаг 3. Оптимальное решение в Excel 43 Цель 3: LIP = 60 недостижима Priceler. Решение задачи  Оптимальный план трансляции рекламных роликов x1  5, x2  1,67  Цель 1 достигнута: рекламный ролик просмотрят 40 млн. мужчин HIM  Цели 2 и 3 недостижимы. Минимальные отклонения от этих целей составляют: 44  От Цели 2: 3,33 млн. чел. (HIW)  От Цели 3: 1,67 млн. чел. (LIP) Priceler 1: Новые приоритеты 45  Цель 3: LIP = 60  Цель 1: HIM = 40  Цель 2: HIW = 35 Шаг 1*. Математическая модель min d  3 7 x1  3 x2  d1  d1  40 5 x1  4 x2  d 2  d 2  35 10 x1  5 x2  d3  d3  60 di  0, di  0 100000 x1  60000 x2  600000 x1  0, x2  0 46 Шаг 1*. Оптимальное решение в Excel 47 Шаг 2*. Математическая модель min d1 d3  0 7 x1  3 x2  d1  d1  40 5 x1  4 x2  d 2  d 2  35  3  3 10 x1  5 x2  d  d  60  i  i d  0, d  0 100000 x1  60000 x2  600000 x1  0, x2  0 48 Шаг 2*. Оптимальное решение в Excel 49 Шаг 3*. Математическая модель min d 2 d3  0 d1  0 7 x1  3 x2  d1  d1  40 5 x1  4 x2  d 2  d 2  35  3  3 10 x1  5 x2  d  d  60 di  0, di  0 100000 x1  60000 x2  600000 x1  0, x2  0 50 Шаг 3*. Оптимальное решение в Excel 51 Priceler 1. Решение задачи  Оптимальный план трансляции рекламных роликов x1  6, x2  0  Цель 3 достигнута: рекламный ролик просмотрят 60 млн. людей среднего достатка (LIP)  Цель 1 достигнута с избытком: рекламный ролик посмотрят 42 млн. мужчин , чей уровень дохода достаточно велик (HIM)  Цель 2 недостижима. Минимальное отклонение от этой цели составляет: 5 млн. чел. (HIW) 52 Priceler: Каков дефицит бюджета?   Прежние приоритеты: Новое целевое ограничение:  Цель 1: HIM = 40  Цель 2: HIW = 35  Цель 3: LIP = 60 7 x1  3 x2  d1  d1  40 5 x1  4 x2  d 2  d 2  35 10 x1  5 x2  d3  d3  60 100000 x1  60000 x2  d 4  d 4  600000 di  0, di  0, i  1,..., 4 x1  0, x2  0 53 Жесткие ограничения Дефицит бюджета. Шаг 1. Начальное решение в Excel min d1 7 x1  3 x2  d1  d1  40 5 x1  4 x2  d 2  d 2  35 10 x1  5 x2  d3  d3  60 100000 x1  60000 x2  d 4  d 4  600000 di  0, di  0, i  1,..., 4 x1  0, x2  0 54 Дефицит бюджета. Шаг 4. Оптимальное решение в Excel min d 4 d1  0 d 2  0 d3  0 7 x1  3 x2  d1  d1  40 5 x1  4 x2  d 2  d 2  35 10 x1  5 x2  d3  d3  60 100000 x1  60000 x2  d 4  d 4  600000 di  0, di  0, i  1,..., 4 x1  0, x2  0 55 Priceler 2. Решение задачи  Оптимальный план трансляции рекламных роликов x1  4,33; x2  3,33 56  Все Цели достигнуты  Дефицит бюджета составляет: $33 333,33 Лабораторная работа 5 Решите задачу методом целевого программирования. СРОК: 26.05.2020 Номер варианта: сумма цифр порядкового номера. Например, 23 выполняет 2+3=5 вариант 57