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

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

Q(x)=( Q₁(x), Q₂(x),¼, Q_s(x)), приводящий к модели принятия оптимального решения, которая называется задачей векторной (многокритериальной) оптимизации:

min Q(),

xÎD 

где D = {x½g_i(x)³0, i=1,2¼,m}.

Это выражение является сокращенной запьсью следующей модели принятия оптимального решения:

Найти значения x, которые обеспечивают одновременно минимальное значение по каждому из частных критериев оптимальности

min Q₁();min Q₂(); ¼ ;min Q_s()

x        x           x

при выполнении условий

g_i(x₁,x₂,¼,x_n)³ 0,      i=1,2,¼m;

x_j^- £ x_j £ x_j⁺ ,  j=1,2,¼n, здесь x_j^- и x_j⁺ - ограничения, накладываемые напеременные сверху и снизу.

Оптимальное решение задачи x^* в общем случае, не являясь оптимальным ни для одного из частных критериев Q_i(x) (в смысле постановки задачи параметрической оптимизации), должно быть компромиссным (в определенном смысле) для векторного критерия Q(x) в целом.

Одним из подходов к поиску компромиссного решения векторной оптимизации является сведение ее к задаче параметрической оптимизации

min Q().

xÎD 

Это значит:

Найти значения параметров X=(x₁,x₂,¼,x_n), обеспечивающих минимальное значение критерия оптимальности

Q = Q(x₁,x₂,¼,x_n)

при выполнении условий

g_i(x₁,x₂,¼,x_n)³ 0,      i=1,2,¼m;

x_j^- £ x_j £ x_j⁺ ,  j=1,2,¼n.

Оптимальным решением этой задачи является вектор x*, удовлетворяющий системе неравенств и обеспечивающий минимальное значение критерия оптимальности ./1/

2.  Определение Парето – оптимальности 

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

Введем понятие эффективной альтернативы (решения).

Альтернатива L₀ называется эффективной, если на множестве допустимых альтернатив не существует такой альтернативы Ĺ, для которой выполнялись бы неравенства

ƒ_i(Ĺ) ³ ƒ_i(L₀), "iÎI₁ ,

ƒ_i(Ĺ) £ ƒ_i(L₀), "iÎI₂

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

Здесь I₁={1,¼,m} – множество индексов для максимизируемых функций цели; I₂={m+1,¼,M} – для минимизируемых функций цели; ƒ_i – функция цели./2/

или

Противоречивость целой порождает противоречивость частных критериев. Возникает проблема их согласования, решением её является определенный компромисс. Ясно, что если компромисс основывается на рационализме, то его реализация должна исчерпать возможности одновременного улучшения значений всех частных критериев. Решения такого типа называют Парето-оптимальными или эффективными. Множество их обозначим U_p^*. Оказывается, что u^*ÎU_p^*, если и только если u^*ÎU и не существует uÎU такого, что Ф_j(u) ³ Ф_j(u^*), j=1.m, причем хотя бы одно из этих неравенств является строгим.  

3.  Методы скаляризации векторного критерия

Для расчета эффективных решений самым распространенным методом является скаляризация векторной задачи. Суть ее в следующем. Строится функция – свертка Ф_S:Rⁿ®R, называемая часто обобщенным