XIII Международная студенческая научная конференция Студенческий научный форум - 2021

Аннотация. В статье рассмотрены постановка задачи многокритериальной оптимизации и проблема выбора оптимального решения. Представлены несколько способов решения данных задач. Описанные способы реализованы на конкретных примерах.

Ключевые слова: эффективность, многокритериальная оптимизация, оптимальность, метод приоритетов, целевое программирование.

Annotation. The statement of the problem of multicriteria optimization and the problem of choosing the optimal solution are considered in the article. Several ways to solve these problems are presented. The described methods are implemented on specific examples.

Keywords: efficiency, multiobjective optimization, optimality, priority method, target programming.

Введение

Понятие «эффективность» или «оптимальность» впервые было принято, разработано и применено к экономическим процессам итальянским экономистом и социологом Вильфредо Парето. Предложение Парето позволяло сравнивать результаты различных решений участников.

Оптимальность по Парето – это состояние какой-либо системы, при котором значение каждого из показателя, характеризующего систему, не может быть улучшено без ухудшения других. Так же эту ситуацию называют Парето-оптимальным состоянием.

Проблема оптимальности в многокритериальных задачах

Есть задачи, в которых сформулирована единственная цель и тем самым единственная целевая функция. Однако часто возникают такие ситуации, когда качество решения оценивается по многим критериям. Тогда выбор наилучшего решения является более сложной задачей, появляется новая проблема: какое решение из множества будет оптимальным. Нужно искать компромиссное решение, учитывающее важность каждой целевой функции.

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

Очевидно, единого решения, которое удовлетворяло бы всем условиям и противоречивым требованиям, нет. Главная особенность заключается не в нахождении несуществующего решения, которое одновременно удовлетворяло бы всем критериям, а в отбрасывании заведомо плохих решений.

Постановкаи решение задач

Рассмотрим пример задачи, когда необходимо одновременное выполнение двух условий (критериев), противоречащих друг другу.

Из листа бумаги, квадратной формы со стороной L, требуется сделать коробку наибольшего объема V и при этом минимизировать отходы. Вырезав из куска четыре квадрата с наиболее выгодной стороной х и согнув оставшееся, получим желаемую коробку (рис. 1), объем V(x) которой равен:

V(x)= (L – 2x)²∙x.

При этом имеем потери бумаги площадью S(x)=4x² (площадь вырезанных квадратов).

Рис. 1

Видим, необходимо одновременное выполнение двух условий (критериев):

(1) V(x) = x∙ (L – 2x)² → max,

(2) S(x) = 4x² → min,

где 0 ≤ x ≤ L/2.

Неравенства 0≤x≤L/2очевидны: если x=0, то лист железа вообще не режем; если x=L/2, то весь лист уходит в отходы. Таким образом, x принимает следующие значения: 0≤x≤L/2.

Обратимся к графикам функций (рис. 2)

Рис. 2

где х (L – 2х)² → max, 4х² → min.

Откуда следует, что одновременно являться верными обоим критериям невозможно: минимум остатков получится при х = 0 (не резать вообще), а максимального объема коробка достигает при х = (1/6) L.

С подобными задачами сталкиваются в тех случаях, когда имеются цели, у которых не может быть один критерий (например, стоимость и надёжность). Требуется найти область допустимых решений, которая минимизирует или максимизирует все такие критерии.

Целевое программирование

В основе метода целевого программирования для решения многокритериальных задач лежит упорядочение критериев (целей) по степени важности. Поставленная задача решается путем последовательного решения ряда задач с одной целевой функцией таким образом, что решение задачи с менее важной целью не может ухудшить оптимального значения целевой функции с более высоким приоритетом.

Рассмотрим следующий пример.

Фирма N производит гаджеты: мобильные телефоны (А) и ноутбуки (Б). Для сборки каждого гаджета требуются один чип, суточный запас которых ограничен 40 единицами. При этом для сборки одного мобильного телефона требуется 1,2 часа, а для одного ноутбука – 4 часа. Суточные возможности по сборке ограничены 240 часами. После сборки каждый гаджет проходит контрольное тестирование. Для контрольного тестирования одного телефона требуется 0,5 часа, а для ноутбука – 1 час. Фирма обладает оборудованием, которое позволяет проводить тестирование в течение 81 часа. Удельная прибыль от продажи оставляет 200$ и 500$ соответственно.

Менеджеры фирмы стремятся к достижению двух целей:

цель 1 – получить прибыль, равную $40000;

цель 2 – ограничить (минимизировать) общее время тестирования готовых изделий.

Если решать задачу максимизации прибыли фирмы, то задача линейного программирования (ЛП) выглядит так: максимизировать прибыль

max (200х₁+ 500х₂ )

при ограничениях

x₂≤ 40 – запас чипов;

1,2 х₁ + 4 х₂≤ 240 – время сборки;

0,5 х₁+ х₂≤ 81 – время тестирования;

х₁, х₂ ≥ 0.

Оптимальное решение задачи ЛП: производить 28,5 штук телефонов и 105 штук ноутбуков, при этом общая прибыль плана составляет $35 250.

Для цели 1 введем две переменные отклонения:

d₁(-) недостаточная переменная, которая показывает, на сколько объем прибыли меньше величины 40 000$;

d₁(+) избыточная переменная, которая показывает, на сколько объем прибыли превосходит величину 40 000$.

Переменная d₁(-) отвечает за степень достижения первой цели, если d₁(-) = 0, то цель достигнута. Если min d₁(-) – величина положительная, то цель недостижима. Тогда целевое ограничение имеет вид:

200 х₁ + 500 х₂ + d₁ (-) – d₁ (+) = 40000,

d₁ (-) ≥ 0, d₁ (+) ≥ 0.

Предполагая, что 81 час – это стандартное время тестирования, можно сформулировать второе целевое ограничение.

Для цели 2 введем две переменные отклонения:

d₂(-) недостаточная переменная, которая показывает, на сколько время контроля меньше 81 часа;

d₂(+) избыточная переменная, которая показывает, на сколько время контроля превосходит 81 час.Переменная d₂(+) отвечает за степень достижения второй цели, если d₂(+) = 0, то цель достигнута. Если min d₂(+) – величина положительная, то цель недостижима. Запишем целевое ограничение:

0,5 х₁ + х₂ + d₂(-) – d₂(+) = 81,

d₂(-) ≥ 0, d₂(+) ≥ 0.

Множество вариантов выбора значений для «недостаточных» и «избыточных» переменных позволяет целевому программированию достичь компромиссного решения.

Метод приоритетов

В методе приоритетов n частных целевых функций распределяются в порядке важности, затем поочередно решаются задачи с одной целевой функцией, начиная с задачи, имеющей наивысший приоритет, и заканчивая задачей, имеющей минимальный приоритет. В ходе решения последовательных задач решение задачи с целевой функцией, имеющей более низкий приоритет, не может ухудшить полученные ранее решения задач, имеющих более высокий приоритет. В простейшем случае решение задачи может быть найдено графически.

В результате решения задачи имеем min P1(-)=0 и минимальное отклонение от цели 1 достигается в точке F (200,0).

Используя метод приоритетов, решим данную задачу графически (рис. 3).

Рис. 3

1) Строится множество допустимых решений задачи, оно определяется системой жестких ограничений:

х₂ ≤40, 1,2 х₁ + 4 х₂ ≤ 240

х₁, х₂ ≥0

2) Далее решается задача нахождения минимума отклонения от цели 1 на множестве допустимых решений: min d₁(-) при ограничениях:

х₂ ≤40, 1,2 х₁ + 4 х₂ ≤ 240,

х₁, х₂ ≥0,

200 х₁ + 500 х₂ + d₁(-) – d₁(+) = 40000,

0,5 х₁ + х₂ + d₂(-) – d₂(+) = 81,

d₁(-) ≥ 0, d₁(+) ≥ 0, d₂(-) ≥ 0, d₂(+) ≥ 0.

3) Решаем задачу нахождения минимума отклонения от цели 2, при условии, что сохраняется отклонение от цели 1, достигнутое на шаге 1: min d₂ (+) при ограничениях:

d₁(-) = 0, х₂ ≤40,

1,2 х₁ + 4х₂ ≤ 240, x₁, х₂ ≥0,

200 x₁ + 500 х₂ + d₁(-) – d1(+) = 40000,

0,5 x₁ + х₂ + d₂(-) – d₂ (+) = 81,

d₁(-) ≥0, d₁(+) ≥ 0, d₂(-) ≥ 0, d₂(+) ≥ 0.

Окончательно имеем решение: m P1(-) = 0 , которое достигается в точке F(200,0). Цель 1 достигается, а цель 2 – нет, отклонение от цели 2: min d2(+) = 100 – 81 = 19 часов. Если изменить приоритеты целей и считать главной целью минимизацию времени тестирования, то оптимальным решением будет точка C (105; 28,5). Отклонение от цели 1 составит min d2(+), отклонение от цели 2 будет

min d1(-) = 40000 – 35250 = 4750.

Вывод.

Как видим, основной проблемой при многокритериальной оптимизации является неоднозначность выбора «оптимального решения». Под оптимальным решением задачи многокритериальной оптимизации следует понимать одно из эффективных Парето-оптимальных решений. Целевое программирование используется для построения оптимального решения, в основном в линейных многокритериальных задачах. В линейных многокритериальных задачах в качестве оптимальных следует рассматривать только экстремальные эффективные решения.

Список литературы

1. Подиновский В.В. Ногин В.Д. Парето-оптимальные решения многокритериальных задач. – М.: Наука. Гл. ред. физ.-мат. Лит., 1982.

2.Зенкевич Н.А., Марченко И.В. Экономико-математические методы. Рабочая тетрадь №2. – СПб.: изд-во МБИ, 2005.

3.Хазанова Л.Э. Математическое моделирование в экономике. –Издательство БЕК, 1998.

Код для цитирования: Скопировать