Метод идеальной точки excel
Метод идеальной точки
•Идеальной или точкой абсолютного максимума называют точку в
критериальном пространстве, в которой все критерии достигают своих
максимальных значений.
•Если эта точка принадлежит достижимому множеству G, то все
эффективное (паретовское) множество состоит из этой единственной точки
и проблемы как таковой в этом случае нет. Однако идеальная точка обычно
лежит вне множества G и поэтому нереализуема. В связи с этим ее иногда
называют также утопической.
•Идея метода состоит в том, чтобы на множестве G найти точку,
наиболее близкую к идеальной.
2
Решение задачи методом идеальной точки
Задача линейной многокритериальной максимизации с двумя
переменными и двумя целевыми функциями
Пример 1. Найти значения переменных, при которых функции
L1 = 2x1 + x2 + 1 → max
L2 = x1 - x2 + 5 → max
при ограничениях:
x1 + 2x2 ≤ 8,
0 ≤ x ≤ 6,
0 ≤ x ≤ 3.
3
Решение.
1) Построим область допустимых решений. Введем на плоскости прямоугольную
систему координат и построим множество X — область допустимых решений
данной задачи в указанной системе координат. Ограничительные условия
определяют на плоскости многоугольник ABCDE (Рис. 1), вершины которого
имеют соответственно координаты: (0; 0), (0; 3), (2; 3), (6; 1), (6; 0). Следовательно,
представляет собою многоугольник ABCDE.
4
Рисунок 1
2) Строим область допустимых решений в пространстве критериев. Подвергнем
координаты каждой точки плоскости преобразованиям L1 = 2x1+x2+1 → max и L2 = x1-x2+5
→ max . Получим плоскость OL1L2. При этом в силу линейности проводимых
преобразований прямоугольная система координат перейдет в прямоугольную систему
координат , а многоугольник ABCDE в многоугольник A*B*C*D*E*, вершины которого
имеют соответственно координаты: (1; 5), (4; 2), (8; 4), (14; 10), (13; 11) (рис. 2).
Для наглядности укажем описанное соответствие вершин: A(0; 0) → A*(1; 5), B(0; 3)
→ B*(4; 2), C(2; 3) → C*(8; 4), D(6; 1) → D*(14; 10), E(6; 0) → E*(13; 11).
Таким образом, все точки, координаты которых удовлетворяют условиям L 1= 2x1+x2+1
→ max, L2 = x1-x2+5 → max и (x1, x2) ϵ X, определяют на плоскости
многоугольник A*B*C*D*E*. Следовательно, область допустимых решений данной задачи
в системе координат (пространстве критериев) представляет собою
многоугольник A*B*C*D*E*.
5
Рисунок 2
3) Находим множество Парето. Это отрезок D*E*.
4) Находим точку утопии. Выбираем комбинацию наилучших значений всех
критериев. В данном случае это точка U с координатами (14; 11).
6
5) Находим идеальную точку. Теперь необходимо найти во множестве Парето
точку, расположенную ближе всех к точке утопии U. Из рис. 3 видно, что точка I ( I1,
I2 ), являющаяся основанием перпендикуляра, проведенного из точки U (14; 11) к
прямой D*E*, принадлежит отрезку D*E*. Это означает, что точка I — искомая.
Рисунок 3
7
6) Находим координаты идеальной точки. Сейчас необходимо вспомнить аналитическую
геометрию: находим уравнение прямой D*E* и находим точку пересечения перпендикуляра
проходящего через точку утопии U получаем координаты идеальной точки I ( I1, I2 ).
8
Замечание. При нахождении расстояния между точкой утопии и идеальной
точкой, учитывая топологию множества Парето, был применен «геометрический»
метод. В общем случае задача нахождения расстояния между указанными точками
решается как экстремальная. Необходимо найти на множестве Парето точку, такую,
что расстояние между ней и точкой утопии минимально.
9
Заключение
Таким образом, метод может быть использован для построения не
популяционных
алгоритмов
Парето-аппроксимации.
Задачу
Парето-
аппроксимации в этом случае сводят к многократному решению задачи
глобальной оптимизации.
10
Как видно, наивысшую ценность имеют альтернативы 2 и 8. Отрицательные значения ценности не должны приниматься во внимание, ибо нас интересуют только сравнительная только сравнительная ценность альтернатив. Таковыми являются альтернативы 3,7, 9 и 10. Наличие отрицательных значений еще раз показывает условность функции ценности, отсутствие у нее в большинстве случаев реального экономического и технологического смысла.
2.2.3.Метод главного критерия
В методе главного критерия в качестве целевого функционала выбирается один из критериальных выходных параметров, наиболее полно с точки зрения исследователя отражающий цели оптимизаций. Остальные частные критерии оптимальности учитываются с помощью введения необходимых критериальных ограничений, определяющих совместно с прямыми и функциональными ограничениями допустимое множество. Основные трудности такого подхода связаны с проблемой назначения критериальных ограничений. Кроме того, в большом числе случаев всегда есть несколько главных критериев, находящихся в противоречии друг с другом.
Главным критерием является , а для 2-го, 3-го и 4-го критерия допустимыми уровнями будут 5, 5 и 4 соответственно. и нам следует уменьшить, а и увеличить. В данном случае оптимальной альтернативой 3-му и 4-му критериям будет являться 2-я альтернатива. Также по главному критерию оптимальной альтернативой является 2-я. Но по главному критерию оптимальна и 9-ая альтернатива, но она не оптимальна по остальным критериям. Следовательно, 2-я альтернатива являются оптимальной при заданных уровнях значимости и данном главном критерии.
2.2.4.Метод идеальной точки
Особую разновидность количественных методов решения многокритериальных задач представляют те, в которых ценность альтернатив определяется не на основе агрегирования оценок по отдельным критериям (построения функции ценности), а путем определения меры близости решения к некому идеальному (так называемой точке идеала, или идеальной точке). Т.е решение должно обеспечивать наибольшее приближение к множеству одновременно недостижимых целей.
Данный метод используется при различных метриках, функциях расстояния. В общем случае:
(14)
где - желательное значение i- того критерия;
S- характеристика метрики.
При S=2 вычисляется евклидово расстояние:
(15)
При S=1 задача сводится к минимизации суммы модулей относительных с учетом «веса» отклонений:
(16)
При S=∞ имеем равномерную метрику, и задача целевого программирования сводится к минимизации максимального относительного отклонения, т.е.
(17)
Таким образом, с помощью табличного процессора MS Excel введем следующие формулы в ячейку B20:
Далее аналогично формулы вставляем по столбцам, и получим результат решения задачи методом идеальной точки (рис.16).
В данном примере лучшим вариантом по двум метрикам является альтернатива 5, по одной метрике альтернатива 2.
В данном примере мы оценивали 10 альтернатив с 4-мя критериями, из них и нам следует уменьшить, а и увеличить, по 4 методам:
· По методу Парето все 10 альтернатив являются оптимальными.
· По методу аддитивной функции ценности наивысшую ценность имеют альтернативы 2 и 8.
· По методу главного критерия 2-я альтернатива являются оптимальной при заданных уровнях значимости и данном главном критерии.
· По методу идеальной точки лучшим вариантом по двум метрикам является альтернатива 5, по одной метрике - альтернатива 2.
В Excel 2007 для включения пакета анализа надо нажать перейти в блок Параметры Excel, нажав кнопку в левом верхнем углу, а затем кнопку «Параметры Excel» внизу окна:
Далее в открывшемся списке нужно выбрать Надстройки, затем установить курсор на пункт Поиск решения, нажать кнопку Перейти и в следующем окне включить пакет анализа.
Для того чтобы решить задачу ЛП в табличном процессоре Microsoft Excel , необходимо выполнить следующие действия:
1. Ввести условие задачи:
a) создать экранную форму для ввода условия задачи:
· переменных,
· целевой функции (ЦФ),
· ограничений,
· граничных условий;
b) ввести исходные данные в экранную форму:
· коэффициенты ЦФ,
· коэффициенты при переменных в ограничениях,
· правые части ограничений;
c) ввести зависимости из математической модели в экранную форму:
· формулу для расчета ЦФ,
· формулы для расчета значений левых частей ограничений;
d) задать ЦФ (в окне "Поиск решения" ):
· целевую ячейку,
· направление оптимизации ЦФ;
e) ввести ограничения и граничные условия (в окне "Поиск решения" ):
· ячейки со значениями переменных,
· граничные условия для допустимых значений переменных,
· соотношения между правыми и левыми частями ограничений.
2. Решить задачу:
a) установить параметры решения задачи (в окне "Поиск решения" );
b) запустить задачу на решение (в окне "Поиск решения" );
c) выбрать формат вывода решения (в окне "Результаты поиска решения" ).
Рассмотрим подробно использование MS Excel на примере решения следующей задачи.
Фабрика "GRM pic" выпускает два вида каш для завтрака - "Crunchy" и "Chewy". Используемые для производства обоих продуктов ингредиенты в основном одинаковы и, как правило, не являются дефицитными. Основным ограничением, накладываемым на объем выпуска, является наличие фонда рабочего времени в каждом из трех цехов фабрики.
Управляющему производством Джою Дисону необходимо разработать план производства на месяц. В приведенной ниже таблице указаны общий фонд рабочего времени и число человеко-часов, требуемое для производства 1 т продукта.
Цех | Необходимый фонд рабочего времени чел.-ч/т | Общий фонд рабочего времени чел.-ч. в месяц | |
"Crunchy" | "Chewy" | ||
А. Производство | 10 | 4 | 1000 |
В. Добавка приправ | 3 | 2 | 360 |
С. Упаковка | 2 | 5 | 600 |
а) Сформулировать модель линейного программирования, максимизирующую общий доход фабрики за месяц.
б) Решить ее c помощью MS Excel.
Ввод исходных данных
Создание экранной формы и ввод исходных данных
Экранная форма для решения в MS Excel представлена на рисунке 1.
В экранной форме на рисунке 1 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка на листе Excel. Имя ячейки состоит из буквы, обозначающей столбец, и цифры, обозначающей строку, на пересечении которых находится объект задачи ЛП. Так, например, переменным задачи 1 соответствуют ячейки B4 (x1), C4 (x2), коэффициентам ЦФ соответствуют ячейки B6 (c1=150), C6 (c2=75), правым частям ограничений соответствуют ячейки D18 (b1=1000), D19 (b2=360), D20 (b3=600) и т.д.
Ввод зависимостей из формальной постановки задачи в экранную форму
Для ввода зависимостей определяющих выражение для целевой функции и ограничений используется функция MS Excel СУММПРОИЗВ , которая вычисляет сумму попарных произведений двух или более массивов.
Одним из самых простых способов определения функций в MS Excel является использование режима "Вставка функций" , который можно вызвать из меню "Вставка" или при нажатии кнопки fx (рисунок 2) на стандартной панели инструментов.
Рисунок 2
Так, например, выражение для целевой функции из задачи 1 определяется следующим образом:
· курсор в поле D6;
· нажав кнопку fx , вызовите окно "Мастер функций - шаг 1 из 2";
· выберите в окне "Категория" категорию "Математические";
· в окне "Функция" выберите функцию СУММПРОИЗВ (рис. 3);
Рисунок 3
· в появившемся окне "СУММПРОИЗВ" в строку "Массив 1" введите выражение B$4:C$4 , а в строку "Массив 2" - выражение B6:C6 (рис. 4);
Левые части ограничений задачи (1) представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи ( B3, C3 ), на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения ( B13, C13 - 1-е ограничение; B14, С14 - 2-е ограничение и B15, С15 - 3-е ограничение). Формулы, соответствующие левым частям ограничений, представлены в табл.1.
Таблица 1.
Формулы, описывающие ограничения модели (1)
Левая часть ограничения | Формула Excel |
10x1+4x2 или B3×B13+C3×C13 | =СУММПРОИЗВ(B4:C4;B13:C13)) |
3x1+2x2 или B3×B14+C3×C14 | =СУММПРОИЗВ(B4:C4;B14:C14)) |
2x1+5x2 или B3×B15+C3×C15 | =СУММПРОИЗВ(B4:C4;B15:C15) |
Дальнейшие действия производятся в окне "Поиск решения" , которое вызывается из меню "Сервис" (рис.5):
· поставьте курсор в поле "Установить целевую ячейку" ;
· введите адрес целевой ячейки $D$6 или сделайте одно нажатие левой клавиши мыши на целевую ячейку в экранной форме ¾ это будет равносильно вводу адреса с клавиатуры;
· введите направление оптимизации ЦФ, щелкнув один раз левой клавишей мыши по селекторной кнопке "максимальному значению".
Ввод ограничений и граничных условий
Задание ячеек переменных
В окно "Поиск решения" в поле "Изменяя ячейки" впишите адреса $B$4:$С$4 . Необходимые адреса можно вносить в поле "Изменяя ячейки" и автоматически путем выделения мышью соответствующих ячеек переменных непосредственно в экранной форме.
Задание граничных условий для допустимых значений переменных
Окно "Поиск решения" после ввода всех необходимых данных задачи (1) представлено на рис. 5.
Если при вводе условия задачи возникает необходимость в изменении или удалении внесенных ограничений или граничных условий, то это делают, нажав кнопки "Изменить" или "Удалить" (см. рис. 5).
Решение задачи
Установка параметров решения задачи
Задача запускается на решение в окне "Поиск решения" . Но предварительно для установления конкретных параметров решения задач оптимизации определенного класса необходимо нажать кнопку "Параметры" и заполнить некоторые поля окна "Параметры поиска решения" (рис. 7).
Рис. 7 - Параметры поиска решения, подходящие для большинства задач ЛП
Параметр "Максимальное время" служит для назначения времени (в секундах), выделяемого на решение задачи. В поле можно ввести время, не превышающее 32 767 секунд (более 9 часов).
Параметр "Предельное число итераций" служит для управления временем решения задачи путем ограничения числа промежуточных вычислений. В поле можно ввести количество итераций, не превышающее 32 767.
Параметр "Относительная погрешность" служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 до 1. Чем меньше количество десятичных знаков во введенном числе, тем ниже точность. Высокая точность увеличит время, которое требуется для того, чтобы сошелся процесс оптимизации.
Параметр "Допустимое отклонение" служит для задания допуска на отклонение от оптимального решения в целочисленных задачах. При указании большего допуска поиск решения заканчивается быстрее.
Параметр "Сходимость" применяется только при решении нелинейных задач.Установка флажка "Линейная модель" обеспечивает ускорение поиска решения линейной задачи за счет применение симплекс-метода.
Подтвердите установленные параметры нажатием кнопки "OK" .
Запуск задачи на решение
Запуск задачи на решение производится из окна "Поиск решения" путем нажатия кнопки "Выполнить" .
Решение с помощью таблиц Excel
Вначале построим на листе Excel решение системы неравенств.
Рассмотрим первое неравенство x1+3x2≤18.
Построим граничную прямую x1+3x2=18 по двум точкам. Прямую обозначим (L1)(или Ряд1). Координаты х2 считаем по формулам:
Для построения выбираем точечную диаграмму
Выбираем данные для прямой
Изменяем название прямой:
Выбираем макет диаграммы. Изменяем название осей координат:
Прямая (L1) на графике:
Решение строгого неравенства x1+3x2≤18 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L1). Например, с помощью точки (0; 0)Ï(L1).
При подстановке координат точки (0; 0), получаем неравенство
0 + 3×0 < 18 или 0 < 18 .
Неравенство является верным, следовательно решением неравенства (1) будет та полуплоскость, в которой пробная точка расположена (на рисунке ниже прямой L1).
Затем решаем неравенство (2) 2x1+x2≤16.
Построим граничную прямую 2x1+x2=16 по двум точкам. Прямую обозначим (L2).
Прямая (L2) на графике:
Решение строгого неравенства 2x1+x2≤16 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L2). Например, с помощью точки (0; 0)Ï(L2).
При подстановке координат точки (0; 0), получаем неравенство
2×0 + 0 < 16 или 0 < 16 .
Неравенство является верным, следовательно решением неравенства (2) будет та полуплоскость, в которой пробная точка расположена (на рисунке ниже прямой L2).
Затем решаем неравенство (3) x2≤5.
Построим граничную прямую x2=5 по двум точкам. Прямую обозначим (L3).
На листе Excel добавляем данные
Прямая (L3) на графике:
Решение строгого неравенства 2x2При подстановке координат точки (0; 0), получаем неравенство
0 < 5 .
Неравенство является верным, следовательно решением неравенства (3) будет та полуплоскость, в которой пробная точка расположена (на рисунке ниже прямой L3).
Затем решаем неравенство (4) 3x2≤21.
Построим граничную прямую 3x2=21 по двум точкам. Прямую обозначим (L4).
На листе Excel добавляем данные
Прямая (L4) на графике:
Решение строгого неравенства 3х1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).
При подстановке координат точки (0; 0), получаем неравенство
0 < 21 .
Неравенство является верным, следовательно, решением неравенства (4) будет та полуплоскость, в которой пробная точка расположена (на рисунке левее прямой L4).
Решением двух неравенств (5) и (6) x1≥0 и x2≥0 является 1-ая четверть, ограниченная координатными прямыми x1=0 и x2=0.
Система неравенств решена. Решением системы неравенств (1) – (6) в данном примере является выпуклый многоугольник в левом нижнем углу рисунка, ограниченный прямыми L1, L2, L3, L4 и координатными прямыми x1=0 и x2=0. Убедиться, что многоугольник выбран правильно, можно подстановкой пробной точки, например (1; 1) в каждое неравенство исходной системы. При подстановке точки (1; 1) получаем, что все неравенства, в том числе естественные ограничения, верные.
Рассмотрим теперь целевую функцию
F = 2x1 + 3x2.
Построим линии уровня для значений функции F = 0 и F = 12 (числовые значения выбраны произвольно). На листе Excel добавляем данные
Линии уровней на графике:
Построим вектор направлений (или градиент) . Координаты вектора совпадают с коэффициентами целевой функции F.
Добавляем на листе Excel координаты начальной и конечной точки вектора.
Вектор на рисунке:
Градиент указывает направление увеличения целевой функции F.
Теперь следует линию уровня F=0 передвинуть параллельно до последней точки угловой точки выпуклого многоугольника. Последней угловой точкой пересечения выпуклого многоугольника и передвинутой линии уровня будет точка пересечения прямых L1 и L2. Для нахождения координат точки решим систему уравнений
x1+3x2=18
2x1+x2=16
Решаем систему уравнений по формулам Крамера. Для этого на листе Excel создаем массивы для определителей. Для вычисления определителей используем математическую функцию МОПРЕД
Выделяем массив определителя
Находим значения х1 и х2
Пересечением прямых L1 и L2 будет точка с координатами (6; 4).
Подставляем координаты точки в целевую функцию
Fmax= 2×6 +3×4 = 24
Ответ: Fmax= 24 при x1=6 и x2=4.
Метод идеальной точки
•Идеальной или точкой абсолютного максимума называют точку в
критериальном пространстве, в которой все критерии достигают своих
максимальных значений.
•Если эта точка принадлежит достижимому множеству G, то все
эффективное (паретовское) множество состоит из этой единственной точки
и проблемы как таковой в этом случае нет. Однако идеальная точка обычно
лежит вне множества G и поэтому нереализуема. В связи с этим ее иногда
называют также утопической.
•Идея метода состоит в том, чтобы на множестве G найти точку,
наиболее близкую к идеальной.
2
Решение задачи методом идеальной точки
Задача линейной многокритериальной максимизации с двумя
переменными и двумя целевыми функциями
Пример 1. Найти значения переменных, при которых функции
L1 = 2x1 + x2 + 1 → max
L2 = x1 - x2 + 5 → max
при ограничениях:
x1 + 2x2 ≤ 8,
0 ≤ x ≤ 6,
0 ≤ x ≤ 3.
3
Решение.
1) Построим область допустимых решений. Введем на плоскости прямоугольную
систему координат и построим множество X — область допустимых решений
данной задачи в указанной системе координат. Ограничительные условия
определяют на плоскости многоугольник ABCDE (Рис. 1), вершины которого
имеют соответственно координаты: (0; 0), (0; 3), (2; 3), (6; 1), (6; 0). Следовательно,
представляет собою многоугольник ABCDE.
4
Рисунок 1
2) Строим область допустимых решений в пространстве критериев. Подвергнем
координаты каждой точки плоскости преобразованиям L1 = 2x1+x2+1 → max и L2 = x1-x2+5
→ max . Получим плоскость OL1L2. При этом в силу линейности проводимых
преобразований прямоугольная система координат перейдет в прямоугольную систему
координат , а многоугольник ABCDE в многоугольник A*B*C*D*E*, вершины которого
имеют соответственно координаты: (1; 5), (4; 2), (8; 4), (14; 10), (13; 11) (рис. 2).
Для наглядности укажем описанное соответствие вершин: A(0; 0) → A*(1; 5), B(0; 3)
→ B*(4; 2), C(2; 3) → C*(8; 4), D(6; 1) → D*(14; 10), E(6; 0) → E*(13; 11).
Таким образом, все точки, координаты которых удовлетворяют условиям L 1= 2x1+x2+1
→ max, L2 = x1-x2+5 → max и (x1, x2) ϵ X, определяют на плоскости
многоугольник A*B*C*D*E*. Следовательно, область допустимых решений данной задачи
в системе координат (пространстве критериев) представляет собою
многоугольник A*B*C*D*E*.
5
Рисунок 2
3) Находим множество Парето. Это отрезок D*E*.
4) Находим точку утопии. Выбираем комбинацию наилучших значений всех
критериев. В данном случае это точка U с координатами (14; 11).
6
5) Находим идеальную точку. Теперь необходимо найти во множестве Парето
точку, расположенную ближе всех к точке утопии U. Из рис. 3 видно, что точка I ( I1,
I2 ), являющаяся основанием перпендикуляра, проведенного из точки U (14; 11) к
прямой D*E*, принадлежит отрезку D*E*. Это означает, что точка I — искомая.
Рисунок 3
7
6) Находим координаты идеальной точки. Сейчас необходимо вспомнить аналитическую
геометрию: находим уравнение прямой D*E* и находим точку пересечения перпендикуляра
проходящего через точку утопии U получаем координаты идеальной точки I ( I1, I2 ).
8
Замечание. При нахождении расстояния между точкой утопии и идеальной
точкой, учитывая топологию множества Парето, был применен «геометрический»
метод. В общем случае задача нахождения расстояния между указанными точками
решается как экстремальная. Необходимо найти на множестве Парето точку, такую,
что расстояние между ней и точкой утопии минимально.
9
Заключение
Таким образом, метод может быть использован для построения не
популяционных
алгоритмов
Парето-аппроксимации.
Задачу
Парето-
аппроксимации в этом случае сводят к многократному решению задачи
глобальной оптимизации.
10
Читайте также: