Metod-leksiko-graficheskogo-uporyadochivaniya

1.

Метод лексикографического
упорядочивания
Министерство науки и высшего образования Российской
Федерации
ФГБОУ ВО «Университет»
Кафедра Прикладной математики
Семестровая работа по дисциплине «Методы оптимизации»

2.

Введение: Оптимизация
множества критериев
Многие прикладные задачи требуют оптимизации нескольких
показателей одновременно. Часто эти критерии конфликтуют:
улучшая один, мы ухудшаем другой.
Приоритет критериев
Метод лексико-графического упорядочивания задает строгий
приоритет критериев.
Единственное решение
Позволяет выбрать одно решение без построения полного
множества Парето.

3.

1. Описание метода
Название
Тип экстремума
Метод лексико-графического
Ориентирован на поиск
упорядочивания
глобального решения
(лексикографическая
относительно заданного
оптимизация, preemptive
множества допустимых
optimization).
решений X.
Применимость
Применим к одномерным и многомерным, гладким и негладким
функциям, включая дискретные и комбинаторные задачи.

4.

1.4 Описание алгоритма метода
Пусть заданы m критериев для минимизации в порядке важности: f1, f2, ..., fm.
01
02
03
Найти z1
Сузить множество X1
Найти z2
Найти значение z1 = minₓ∈X f1(x).
X1 = { x ∈ X | f1(x) = z1 }.
Найти z2 = minₓ∈X1 f2(x).
04
05
Сузить множество X2
Продолжать до fm
X2 = { x ∈ X1 | f2(x) = z2 }.
Итоговое множество Xm содержит лексикографически
оптимальные решения.
В численных задачах равенство f_k(x) = z_k заменяют на f_k(x) <= z_k + eps.

5.

1.5 Тестовый пример: Одна итерация
Задача с двумя критериями для x = (x, y) на области X: x ∈ [-2, 2], y ∈ [-2, 2].
Критерии минимизации:
Итерация 1 (оптимизация f1):
f1(x, y) = (x + y - 1)² (главный)
Минимум f1 достигается, когда x + y - 1 = 0, т.е. на
f2(x, y) = x² + y² (вторичный)
прямой x + y = 1.
Получаем z1 = 0 и множество X1 = { (x, y) ∈ X | x + y = 1 }.

6.

Тестовый пример:
Продолжение
Далее среди точек прямой x + y = 1 минимизируем f2.
f2 - квадрат расстояния
Ближайшая точка
f2 = x² + y² — это квадрат
Выбираем точку на прямой,
расстояния до начала
ближайшую к (0, 0).
координат (0, 0).
Проекция
Проекция (0, 0) на x + y = 1 дает x = 0.5, y = 0.5.
Лексикографически оптимальное решение: x* = (0.5, 0.5), при f(x*) = (0,
0.5).

7.

2. Программная
реализация на Python
Идея реализации
Аппроксимация сеткой
Программа реализует
лексикографическую
Для задач с непрерывными
минимизацию на конечном
переменными область X
наборе кандидатов.
аппроксимируется
регулярной сеткой.
Критерии как функции
Критерии задаются как функции Python, возвращающие числа.

8.

3. Задачи для проверки
программы
1
Задача 1: Непрерывная
Найти точку (x, y) в квадрате [-2, 2] x [-2, 2], минимизирующую (f1, f2).
f1(x, y) = (x + y - 1)², f2(x, y) = x² + y².
Приоритет: f1, затем f2. Решение функцией task1().
2
Задача 2: Дискретная
Выбрать поставщика из списка, минимизируя (цена, срок поставки,
процент брака).
Приоритет: цена -> срок -> брак. Решение функцией task2().

9.

Заключение
Метод лексико-графического упорядочивания предоставляет
прозрачное правило выбора решения в многокритериальной
задаче.
Простота
Прост для объяснения и реализации.
Сравнение векторов
Достаточно уметь сравнивать векторы критериев по
порядку важности.
Последовательность подзадач
Или решать последовательность одноцелевых
подзадач.

10.

Пример запуска
программы
Пример вывода при запуске файла:
Task1 best point: (0.5, 0.5) objectives: (0.0, 0.5)
Task2 best supplier: Supplier(name='F', price=90, days=6,
defect_pct=2.0) objectives: (90, 6, 2.0)
Эти результаты демонстрируют эффективность метода в
нахождении оптимальных решений для различных типов задач.