Векторные задачи линейного программирования с независимыми критериями

Рассмотрим векторную задачу линейного программирования, у которой имеется два подмножества критериев: Q и К_р где Q - подмножество независимых критериев (определение дано ниже); - подмножество зависимых между собой критериев; Q и K_t = К - множество критериев ВЗМП - подобные задачи возникают в задачах анализа и синтезе многоуровневых иерархических систем:

optF(X(t)) = {{F₁(X(t)) = maxf(X(t))= ?c]x.(t), q= Ш (12.1.1) y=i

{F₂(X(t)) = maxf_k(X(t))= f c5x.(t),k= IJj}, (12.1.2) ;=i

? a..(t)x.(t) < b^t), i = ЦЙ, (12.1.3)

j=i

^a.4(t)x.(t)q, q= 6Q, (12.1.4)

7 = 1 ______

x.(t)>O,j= 1,N, (12.1.5)

где X = {X_q = {x., j = 1,N }, q = 1,Q} - вектор вещественных переменных, то есть вектор из N-мерного евклидова пространства R^N, включающий в себя qe Q подмножество неизвестных N cN q-ro критерия; Q - множество независимых критериев, то есть удовлетворяющих условию Vq, к е К, N_qH N_k = 0, N_qc N, N_kc N, в приложении к иерархическим системам (ИС) вектор неизвестных X = {X_q, q = 1, Q} определяет виды (номенклатуру) и объемы продукции ИС в целом, в том числе ее локальными подсистемами (ЛП), из которых составлена ИС, N = и N ;

qeQ ⁴

F(X) - вектор-функция (векторный критерий), К представляет собой мощность множества К, F(X) = {f_k(X), k = 1, К}, имеет К = QjK_x компонент максимизации, Q - множество независимых критериев, Q(zK (в приложении к ИС Q - множество ЛП F^X) = {f (X), q = 1,Q}), и K_{ множество зависимых критериев, то есть в критерий входят переменные различных независимых критериев (в приложении к ИС К_{ — множество критериев, описывающих цели ИС в целом Fj(X) = {f_k(X), k = 1,Кс], с*, q = 1, Q, к = 1,К j - техникоэкономические показатели, характеризующие j-й вид продукции, например стоимость единицы j-го вида продукции, тогда у cSx. - пла-/=1

нируемые объемы продажи q-й ЛП, Vq е Q);

(12.1.3)-(12.1.4) - стандартные ограничения, накладываемые на переменные зависимых и независимых критериев. Предполагаем, что S = {X е R^N | X > О, G(X) < В} Ф 0 - множество допустимых точек, заданное стандартными ограничениями (12.1.3)—(12.1.4) и тривиальными ограничениями X > 0; в дальнейшем будем предполагать, что оно не пусто и представляет собой компакт.

В приложении к ИС, а.., аЯ - нормы i-ro ресурса на производство единицы j-ro вида продукции, затраченного ИС в целом и q-й ЛП, соответственно;

(12.1.5) предполагают неотрицательность каждого вида продукции.

Для решения ВЗЛП (12.1.1)-(12.1.5) используем алгоритм, основанный на нормализации критериев и принципе гарантированного результата.

При решении получим:

• • точки оптимума X*, к = 1,К и величины целевых функций в этих точках f*, к = 1,К, которые получились, если решать задачу (12.1.1)-(12.1.5) по одному k-му критерию;
• • наихудшую неизменяемую часть критерия fj, к = 1,К, которая получилась при решении задачи (12.1.1)-(12.1.5) по одному k-му критерию на min;
• • Х° - точку оптимума решения ВЗМП при равнозначных критериях, то есть при решении максиминной задачи и построенной на ее основе Х-задачи;

• - максимальную относительную оценку, являющуюся гаран

тированным уровнем для всех критериев в относительных единицах.

В точке Х° вычислим величины критериев f_k(X°) и относительных оценок (Х°) = (f_k(X °) - Р)/(Г* - Р), к = 1,К, которые удовлетворяют неравенству Х° < (Х°), к = 1,К. В ней все критерии больше или равны Л°. В других точках X < S⁰ меньший из критериев в относительных единицах Л = min (X) всегда меньше Л°.

кеК

Определение 1. Если в ВЗЛП (12.1.1)-(12.1.5) множество индексов вектора неизвестных, входящих в q G К критерий, N_qcN, Vq G К не пересекается с любым другим множеством вектора неизвестных k G К, N. с N, Vk G К, то есть

Vq, к G К, N n N = 0, N с N, Нс N, q к q ’к ’

то такие ВЗЛП назовем векторными задачами линейного программирования с независимыми критериями.

Заметим, что если в ВЗЛП (12.1.1)-(12.1.5) некоторые компоненты вектора X для каких-либо ЛП совпадают, то их можно переобозначить (переиндексировать), тем самым сделав все критерии независимыми.

Теоретические результаты

Теорема 1. Если в ВЗМП для любой пары индексов q, k g Q пересечение подмножеств индексов переменных пусто, то есть критерии независимы:

Vq, kGK, N_qnN_k = 0, N_qcN, N_kcN, (12.1.6) то в точке оптимума X°, полученной на основе нормализации критериев и принципа гарантированного результата, все относительные оценки равны между собой и равны максимальному относительному уровню Х°,

X» = X(X»),q=i^. (12.1.7)

Теорема 2. Если в ВЗМП с независимыми критериями (верны соотношения (12.1.6)) один из критериев qeQ имеет приоритет над другими k = 1, Q, то в точке оптимума Х°, полученной на основе нормализации критериев и принципа гарантированного результата, все относительные оценки равны между собой и равны максимальному относительному уровню Х°, умноженного на вектор приоритета:

X° = p^qX_q(X°), Vqe Q,k = 1,Q, (12.1.8)

где p J, к = 1,Q - заданный приоритет q-го критерия по отношению к остальным k = 1,Q критериям.

В приложении к иерархическим системам числовые показатели:

{Г, q = kQ , X = minX (X), Х° = minX (X⁰)} (12.1.9)

⁴ qeQ ⁴ qeQ ⁴

несут определенный экономический смысл. X = {X = {х., j = 1,N }, q=hQ}.

Величина f_q, q = 1,Q получается из задачи (12.1.1)—(12.1.5) при условии, что q-й ЛП отданы все глобальные ресурсы ИС (12.1.3), практически на f * оказывают влияние только свои собственные ограничения (12.1.4). Таким образом, f*, q = 1,Q может служить оптимальным показателем развития ЛП (например, подразделения (предприятия) внутри фирмы, отрасли в масштабе страны и т.д.), то есть на первом шаге алгоритма высшая управляющая подсистема как бы использует метод имитационного моделирования, исследует, как поведет себя ЛП, если ей предоставить неограниченные ресурсы, и в результате получает пределы f*, q = 1,Q, к которым должны стремиться все ЛП при их общей оптимизации.

X = min X (X) - уровень, который достигает экономика ИС при qeQ ^{4 >}

выпуске X_q, q = 1,Q объемов продукции по отношению к своим оптимальным показателям: Х_к(Х°) = (f (Х°) - P)/(f* - Р), q = 1,Q;

Х° = min X (Х°) = max min X (X) - это максимальный относи-qeQ ^q XeS qeQ ^q

тельный уровень, которого достигнет экономика ИС при выпуске Х° = {Х°, q = 1,Q} объемов продукции, относительно оптимальных показателей.

Все эти показатели ИС необходимы для принятия оптимального решения.

Теоремами 1-5 (раздел 10.4) доказывались для выпуклых задач, поэтому они справедливы и для векторной задачи линейного программирования, описывающей ИС с независимыми ЛП.

Свойства векторных задач линейного программирования с независимыми критериями X_k(X°) = (f(X°) - P)/(f* - Р), q = 1,Q; q,keQ.

1. При решении ВЗЛП по одному q е Q критерию в точке оптимума X*, q G Q величины всех остальных критериев k G К, а следовательно, и относительных оценок равны нулю.

f_k(x;) = o,(x;) = o, vq.ke к,_ч/к. (12.1.10)

2. В точке оптимума X" приоритет q-ro критерия над остальными к е К критериями при условии f’ = 0, Vq е Q равен <ю.

ЧЮ

Следовательно, при перемещении из Х° в X* вектор приоритетов р^¹, k = 1,Q лежит в пределах: 1 < р^< оо, q g Q, Vk G Q, q Ф k.

Приложение к части II