Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,749

ВОЗМОЖНЫЙ СПОСОБ ПОИСКА КОМПРОМИССНОГО РЕШЕНИЯ В ЗАДАЧЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ВЕКТОРНОЙ ЦЕЛЕВОЙ ФУНКЦИЕЙ

Носков С.И. 1 Быкова О.В. 1 Некипелова О.Е. 1 Соколова Л.Е. 1
1 ФГБОУ ВПО «Иркутский государственный университет путей сообщения»
В статье рассматривается задача многокритериального линейного программирования с интервальной матрицей ограничений, правой частью и критериальной матрицей. Формулируются задачи, подлежащие решению в такой постановке. Методологической основой подхода, предлагаемого в работе, послужила ставшая уже классической статья американских математиков P.L. Yu и M. Zeleny, посвященная разработке многокритериального симплекс-метода в линейной программной задаче с векторной целевой функцией. Этот метод основан на доказательном факте связности множества паретовских вершин с симплексом. Кроме того, в упомянутой статье сформулирована и доказана теорема, представляющая собой необходимое и достаточное условие паретовости произвольного допустимого решения задач. Другим основополагающим фактором, на который опирается данная работа, является существование некоторого компромиссного решения исходной задачи, предложенной в работе одного из авторов.
многокритериальное
линейное программирование
множество Парето
симплекс-метод
1. Носков С.И. Точечная характеризация множества Парето в линейной многокритериальной задаче. – Иркутск: ИИТМ ИрГУПС.
2. О множестве решений линейного уравнения с интервально заданными оператором и правой частью / А.В. Лакеев, С.И. Носков // Сибирский математический журнал. – 1994. – Т.35, № 5. – С. 1074.
3. Определение гармоник сигнала монитора на основе методов регрессионного анализа /Я. А. Жигунова, С.И. Носков // Современные технологии. Системный анализ. Моделирование. – 2008. – № 4. – С. 89–90.
4. Построение экономических зависимостей с учетом критерия «согласованность поведения» / С.И. Носков // Кибернетика и системный анализ. – 1994. – № 1. – С. 177.
5. A Description of the set of solutions of a linear equation with interval defined operator and right-hand side /A.V. Lakeev, S.I. Noskov // Doklad Mathematics. – 1993. – Т.47, № 3. – Р. 518.
6. Approximate linear algebra is intractable / V. Kreinovich, A.V. Lakeev, S.I. Noskov // Linear algebra and its Applications. – 1996. – Т. 232, № 1–3. – С. 45–54.
7. Description of the solution set to linear equation with the intervally defined operator and right-hand side /A.V. Lakeev, S.I. Noskov // Доклады академии наук. – 1993. – Т. 330, № 4. – Р. 430.
8. Yu L., Zeleny M. The set of all nondominated solutions in linear cases and multycriteria simplex method // J. of Math. Anal. and Applic. – 1975. – Vol. 45, № 2. – P. 430–468.

Настоящая работа основана на материале, представленном в [1]. Приведём его краткое изложение.

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

nosov01.wmf (1)

nosov02.wmf (2)

Здесь, в отличие от обычной задачи линейного программирования (ЛП), С – матрица размерности l×n, а не вектор. А – матрица ограничений размерности m×n. Таким образом, многокритериальная задача (1), (2) предполагает максимизацию на многограннике X не одного линейного критерия, как в обычной задаче (ЛП), а l-критериев одновременно.

Заметим, что от нормальной формы задачи (1), (2) легко можно перейти к канонической. Ограничение х ≥ 0 также легко обходится.

Как правило, традиционного решения задачи (1), (2) не существует, то есть отсутствует точка x ∈X такая, что Cx ≥ Cy для всех y ∈ X, y ∈ x. В случае, когда у лица, принимающего решение (ЛПР), отсутствует какая-либо априорная информация относительно сравнительной важности критериев, под решением задачи (1), (2) будем понимать множество Парето. Обозначим его через N ∈ X. Решение x ∈ N называется паретовским (недоминируемым, неулучшаемым), если его нельзя улучшить по какому-то одному критерию, не ухудшив значение хотя бы одного из оставшихся. Или, формально,

nosov03.wmf

Проблеме построения множества Парето в задаче МЛП посвящена обширная литература. Вместе с тем одной из лучших (если не лучшей) публикацией на эту тему является, по-видимому, статья американских математиков P.L. Yu и M. Zeleny [8]. Именно здесь приведены хорошо теоретически обоснованные методы построения множества паретовских вершин Nex ∈ N и всего множества Парето.

Для построения множества Nex в [8] представлен так называемый многокритериальный симплекс-метод. Он основан на двух основных теоремах, формулировки которых мы приведем здесь без доказательства.

Теорема 1 ([8]). Множество Ne связно.

Теорема 2 ([8]).

nosov04.wmf

Здесь D = X/N, а ω – решение задачи ЛП

nosov05.wmf (3)

nosov06.wmf (4)

Суть алгоритма построения множества Nex, описанного в [8], состоит в следующем. Сначала ищется первая паретовская вершина x1. Для этого достаточно решить задачу ЛП с целевой функцией

nosov07.wmf, λ > 0.

После этого на паретовость путем решения задачи (3), (4) проверяются все соседние к x1 точки. Те из них, которые окажутся паретовскими, включаются в Nex, проверке подвергаются соседние к ним и т.д.

Следует отметить, что в [8] приведен (см. например, теорему 3.1 в [8]) ряд простых достаточных условий принадлежности некоторой произвольной точки y ∈ X множеству D, что существенно облегчает перебор.

Наряду с многокритериальным симплекс-методом в [8] показано, что для любой точки x ∈ Nex существует набор чисел λi ∈ (0, 1), nosov08.wmf такой, что

nosov09.wmf (5)

Это означает, что множество Nex можно построить, перебирая узлы l – мерной Σ-сети на множестве nosov10.wmf и решая для каждого узла задачу ЛП (5).

Далее в [2] показывается, как на основе Nex можно построить множество N. При этом N будет представлять собой объединение паретовских выпуклых комбинаций (граней многогранника X) точек из Nex.

Заметим, что со всем множеством Парето N работать трудно, поскольку оно содержит бесконечное число возможных «равноправных» решений, ЛПР же, как правило, для реализации требуется какое-то одно решение. В то же время вся объективная информация уже использована как будто бы при построении множеств Nex и N.

Казалось бы, выходом из этой ситуации может быть решение задачи ЛП(5) с равными весовыми коэффициентами nosov11.wmf. Это, однако, не так по двум причинам. Во-первых, такой способ предполагает одинаковую важность для ЛПР всех l критериев, что сужает постановку исходной задачи. И, во-вторых, такое решение непременно «выведет» на какую-нибудь точку из Nex (то есть на вершину), игнорируя, по существу, множество N/Nex.

Способ, позволяющий ЛПР выделить для реализации лишь одну точку из N и не требующий дополнительных соображений субъективного характера, может состоять в следующем. Заметим, что впервые он изложен в [8], в настоящей же работе произведено его уточнение и развитие.

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

Отметим далее, что такая характеризация – обозначим ее через nosov12.wmf – должна отражать конфигурацию множества N, в значительной мере задаваемую множеством Nex.

Основанная на учете этих двух соображений идея поиска решения nosov13.wmf состоит в следующем. Необходимо, считая каждую точку из Nex равноправной по отношению к другим, найти выпуклую комбинацию всех точек из Nex с равными весами. Обозначим её через x*:

nosov14.wmf (6)

где p – число элементов (мощность) множества Nex.

Ясно, что в общем случае точка x* не является паретовской. Поэтому естественно в множестве N выделить точку (ранее обозначенную через nosov15.wmf), в максимальной степени «улучшающую» x* по всем критериям.

Воспользуемся для этого теоремой 2 и решим задачу (3) на множестве

nosov16.wmf (7)

А теперь, основываясь на этом материале, поставим ряд интересных, подлежащих решению вопросов, связанных с интервально заданными исходными данными. То есть будем предполагать, что эти данные заданы не точечно, а интервально следующим образом:

nosov17.wmf

При этом будем считать, что любая информация, уточняющая расположение компонент указанных вектора и матриц, отсутствует. Некоторые приёмы оперирования интервальными данными представлены в работах [2–7].

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

Решению этих и смежных вопросов авторы намерены посвятить свои последующие работы.

При этом необходимо иметь в виду следующее. Центральной проблемой, связанной с решением многокритериальной линейной задачи в интервальной постановке, является классическая для интервального анализа проблема отыскания решения интервальной системы линейных алгебраических уравнений (ИСЛАУ – принятая в интервальном анализе аббревиатура)

Az = B,

где А – интервальная вещественная матрица размерности (n×m); B – n-мерный интервальный вектор, элементами которых являются соответственно интервалы и nosov18.wmf, nosov19.wmf, z Є Rm. Множество решений ИСЛАУ может быть определено различными способами в зависимости от того, какими кванторами связаны коэффициенты матрицы и правой части. Наиболее часто в литературе встречаются следующие множества решений, подробно описанные в работах У. Оэттли, У. Прагера, И. Рона, А.В. Лакеева, С.И. Носкова, С.П. Шарого:

nosov20.wmf – объединенное множество решений ;

nosov21.wmf – допустимое множество решений ;

nosov22.wmf – множество впервые рассмотренной при решении интервальной задачи модельного управления;

nosov23.wmf – множество всех точечных алгебраических интервальных решений.

Множества nosov24.wmf, nosov25.wmf представимы также в виде

nosov26.wmf

nosov27.wmf

nosov28.wmf

nosov29.wmf

Здесь A–, A+ и b–, b+ – матрицы и вектора, состоящие из элементов nosov31.wmf и nosov32.wmf, nosov33.wmf, nosov34.wmf соответственно.

Очевидны следующие соотношения между Ri, nosov35.wmf:

nosov36.wmf

В работах указанных авторов показано, что множества решений ИСЛАУ представимы в виде:

nosov37.wmf

nosov38.wmf

nosov39.wmf

nosov40.wmf

Анализ описаний Ri, nosov41.wmf показывает, что лишь множество R2 (допустимое множество решений ИСЛАУ) представляет собой область совместности системы линейных неравенств. Остальные множества R1, R3, R4 описываются системами линейных неравенств и нелинейным условием (z1, z2) = 0, которое сильно затрудняет работу с этими множествами. От него можно избавиться посредством расширения размерности задачи введением булевых переменных σi, nosov42.wmf по правилу:

0 ≤ z1i ≤ σiM;

0 ≤ z2i ≤ (1 – σi)M; σi = 0,1, nosov43.wmf,

где М – заранее выбранное большое положительное число.

После введения таких переменных для работы с множествами R1, R3, R4, в частности, решения на них различных оптимизационных задач, можно воспользоваться программными средствами решения задач частично-целочисленного линейного программирования.

Нетрудно также показать обратное, а именно то, что любую задачу булевого программирования можно заменой переменных свести к задаче с условиями типа z1 ≥ 0, z2 ≥ 0, (z1, z2) = 0. Действительно, рассмотрим задачу булевого программирования

Aσ ≤ b

σi = 0,1, nosov44.wmf

(c, σ) → max.

Тогда, введя вещественные переменные z1i, z2i, nosov45.wmf по правилу

σ = z1 + z2;

0 ≤ z1 ≤ 1, 0 ≤ z2 ≤ 1,

(z1, z2) = 0,

получим эквивалентную постановку

A(z1, z2) ≤ b;

0 ≤ z1 ≤ 1, 0 ≤ z2 ≤ 1;

(z1, z2) = 0;

(c, z1 + z2) → max.

Рецензенты:

Кузьмин О.В., д.ф.-м.н., профессор, заведующий кафедрой теории вероятностей и дискретной математики Иркутского государственного университета, г. Иркутск;

Лакеев А.В., д.ф.-м.н., ведущий научный сотрудник ИДСТУ СО РАН, г. Иркутск.

Работа поступила в редакцию 11.04.2014.


Библиографическая ссылка

Носков С.И., Быкова О.В., Некипелова О.Е., Соколова Л.Е. ВОЗМОЖНЫЙ СПОСОБ ПОИСКА КОМПРОМИССНОГО РЕШЕНИЯ В ЗАДАЧЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ВЕКТОРНОЙ ЦЕЛЕВОЙ ФУНКЦИЕЙ // Фундаментальные исследования. – 2014. – № 6-3. – С. 502-505;
URL: https://fundamental-research.ru/ru/article/view?id=34189 (дата обращения: 29.11.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074