Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,222

POSSIBLE WAY OF SEARCH OF THE COMPROMISE SOLUTION IN A PROBLEM OF LINEAR PROGRAMMING WITH MULTI-CRITERION FUNCTION

Noskov S.I. 1 Bukova O.V. 1 Nekipelova O.E. 1 Sokolova L.E. 1
1 Irkutsk State University of Railway Transport
В статье рассматривается задача многокритериального линейного программирования с интервальной матрицей ограничений, правой частью и критериальной матрицей. Формулируются задачи, подлежащие решению в такой постановке. Методологической основой подхода, предлагаемого в работе, послужила ставшая уже классической статья американских математиков P.L. Yu и M. Zeleny, посвященная разработке многокритериального симплекс-метода в линейной программной задаче с векторной целевой функцией. Этот метод основан на доказательном факте связности множества паретовских вершин с симплексом. Кроме того, в упомянутой статье сформулирована и доказана теорема, представляющая собой необходимое и достаточное условие паретовости произвольного допустимого решения задач. Другим основополагающим фактором, на который опирается данная работа, является существование некоторого компромиссного решения исходной задачи, предложенной в работе одного из авторов.
In the paper, the problem of multi-criteria linear programming with interval matrix restriction matrix is considered. Current controversies are observed and possible ways to finding solutions are proposed. Methodological basis of the approach proposed in the paper, has served, has already become a classic, art American mathematicians P.L. Yu and M. Zeleny, dedicated to the development of multi- simplex method in linear programming task with the objective function vector. This method is based on evidence- connectedness of Pareto simplex vertices. Furthermore, in the same article stated and proved theorem, which is a necessary and sufficient condition for an arbitrary admissible paretovosti solving problems. Another fundamental factor, which is based on this work is the existence of a compromise solution of the original problem, proposed in one of the authors.
multicriteria
linear programming
the Pareto set
the simplex method
1. Noskov S.I. Tochechnaya harakteristika mnogestva Pareto v lineinoi mnogokriterialnoi zadache. Irkutsk: IITM IrGUPS.
2. O mnogestve resheniy lineinogo uravneniya s intervalno zadannymi operatorom i pravoi chastiu / A.V. Lakeyev, S.I. Noskov /Sibirskii matematicheskii zurnal, 1994, T.35, no. 5. рр. 1074.
3. Opredelenie garmonik signala monitora na osnove metodov regressionnogo analiza /Y.A. Zigunova, S.I. Noskov / Sovremennie texnologii.Sistemniy analiz. Modelirovanie, 2008, no. 4, pp. 89–90.
4. Postroenie ekonomicheskix zavisimostey s uchetom kriteriya «soglasovannostpovedeniya»/ S.I. Noskov // Kibernetika I sistemnii analiz, 1994, no. 1, pp. 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, no. 3, pp. 518.
6. Approximate linear algebra is intractable / V. Kreinovich, A.V. Lakeev, S.I. Noskov / Linear algebra and its Applications, 1996, Т. 232, no. 1–3, pp. 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, no. 4, pp. 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. no.2. pp. 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.