книги / Математические методы принятия решений

= (1,8; 1,1), /(1,8; 1,1) = —1,46, т. е. итерационный процесс идет в нужном направлении: оптимальное решение имеет координаты (0,75; 1,85) и значение целевой функции равно —2,8.

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

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

За последние десятилетия разработано много методов анали­ за и решения подобных задач. Эти методы являются диалоговыми (или интерактивными), состоящими в последовательном анализе возможных решений и выборе наиболее предпочтительного реше­ ния. Методы могут основываться на предварительном выделении множества неулучшаемых (эффективных) решений и представле­ нии ЛПР этого множества для принятия решений.

Многокритериальная задача линейного программирования (МКЛП) имеет вид

m ax{cjx = z\}, max{<^æ = Z2 ),

т а x{c\x = zk)

при х 6 D, или в матричной форме:

m ax{Cx = z \ x e D } .

Здесь к — число целевых функций (критериев); с* — градиент (век­ тор коэффициентов) г-й целевой функции (критерия); г* — значение г-ro критерия (целевой функции); D —множество допустимых зна­ чений переменных; max означает, что необходимо находить макси­ мум всех целевых функций одновременно; С — матрица критериев

размерностью к х п (матрица коэффициентов целевой функции, ее строки Ci являются градиентами критериев); z — вектор критериев.

Предположим, что ЛПР всегда имеет функцию полезности и: Rfc —> R 1. Эта функция отображает векторы критериев на дей­ ствительную прямую так, что большее значение на этой прямой соответствует более предпочтительному вектору критериев. Функ­ ции полезности бывают разных видов: неубывающие, возрастаю­ щие, вогнутые, строго вогнутые, убывающие, выпуклые, строго выпуклые, монотонные и т.д. Однако исходные функции полезно­ сти могут быть преобразованы таким образом, чтобы они приняли вид, необходимый ЛПР, например чтобы функция полезности стала покоординатно возрастающей.

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

Пусть D —допустимая область в пространстве решений, a Z — допустимое множество в пространстве критериев. Последнее пред­ ставляет собой множество образов всех точек из D :

Z = {z eR * I z = C x , x e D } .

Если известна функция полезности it, то многокритериальная задача преобразуется в однокритериальную задачу

max{it(z) | z = Сх, x e D } .

Этот подход применим только концептуально. Пример. Рассмотрим задачу МКЛП

где функция полезности имеет вид и = 2z\z-i.

1. В пространстве решений имеем и = 2х\ + 2X J X2. Из рис. 5.17 видно, что оптимальной точкой является точка (3,0), оптимальный вектор имеет вид (3, 3)т, оптимальным значением является и = 18.

Для критериальных векторов z вводится понятие доминирова­ ния. Пусть z 1, z2 е Ш.к —критериальные векторы.

Таким образом, никакой компонент вектора z 1 не меньше соот­ ветствующего компонента вектора z2, и, одновременно, по крайней мере один компонент вектора z 1 больше соответствующего компо­ нента вектора г 2.

Вектор z 1 сильно доминирует вектор z2 тогда и только тогда, когда z 1 > z2 (т. е. z\ > z2 для всех г).

Критериальный вектор считается недоминируемым, если он не доминируется ни одним из допустимых критериальных векторов. Вектор z 6 Z является недоминируемым тогда и только тогда, то­ гда не существует другого вектора z е Z такого, что z ^ z и z Ф z, иначе z является доминируемым критерием.

Критериальный вектор не может быть оптимальным, если он не является недоминируемым. Для каждого недоминируемого кри­ териального вектора существует покоординатно возрастающая функция полезности, для которой он является оптимальным.

Понятие доминируемости определено толыю в пространстве критериев; в пространстве решений вводится понятие эффектив­ ности.

Точка х 6 D эффективна тогда и толью тогда, когда не суще­ ствует другой точки х 6 D такой, что С х ^ С х и С х ф Сх. В про­ тивном случае точка х неэффективна. Точка х е D эффективна, если ее критериальный вектор недоминируем критериальными век­ торами других точек из D. Из эффективной точки невозможно сдви­ нуться допустимым образом так, чтобы увеличить один из крите­ риев, не уменьшив по крайней мере один из остальных.

Вместе с термином «эффективность» используют термины «неулучшаемость» или «оптимальность по Парето». На практике часто используют области Парето. В. Парето сформулировал про­ блему многокритериальной оптимизации в 1896 г., Л. Заде вернулся к ней в 1963 г. при проектировании систем управления. Область Парето задается в пространстве критериев, и любое принадлежа­ щее этой области решение нельзя улучшить одновременно по всем скалярным критериям. Вне области Парето можно улучшать реше­ ние по всем критериям одновременно, но ни по одному критерию оптимальное значение целевой функции здесь не достигается. Та­ ким образом, необходимым условием решения задачи многокрите­ риальной оптимизации является принадлежность решения области Парето, т. е. решение должно быть оптимальным по Парето, по­ скольку остальные решения заведомо не удовлетворяют сразу всем скалярным критериям. Однако, чтобы выбрать единственное реше­ ние на множестве оптимальных по Парето решений, необходима дополнительная информация.

Для примера рассмотрим двухкритериальную задачу. На плос­ кости критериев, где задано множество допустимых решений, пер­ вый критерий достигает своего оптимума в точке А, второй—в точ­ ке В. Кривая А В , принадлежащая области допустимых решений, определяет для данной задачи область Парето.

Множество всех эффективных точек называется эффективным множеством. Обычно легче показать, что точка неэффективна, чем доказать ее эффективность. Чтобы доказать неэффективность точ­ ки х \€ D достаточно найти другую точку хг е D, критериальный вектор которой доминирует критериальный вектор точки х\.

В задаче линейного программирования эффективная точка—это некоторая оптимальная точка, так как не существует точка х е D такая, что сТх > стх.

В задаче ЛП с одним критерием эффективное множество Е и оптимальное множество © совпадают и оба выпуклы. В много­ критериальной задаче множества Е и © обладают разными свой­ ствами:

1)оптимальное множество © может быть ограниченным и не­ связным (наличие более чем одной оптимальной точки не означает, что число их обязательно бесконечно);

2)в задаче МКЛП может быть более одного оптимального кри­ териального вектора (в задачах ЛП существует единственное оп­ тимальное значение критерия независимо от числа оптимальных точек);

3)эффективное множество Е может оказаться невыпуклым;

4)оптимальная точка не обязательно является граничной (мно­ гое зависит от вида функции полезности);

5)при сведении задачи МКЛП к однокритериальной задаче с по­ мощью функции полезности могут существовать локальные оптимумы, не являющиеся глобальными;

6)оптимальное множество © может быть пусто в том случае, когда не пусто эффективное множество Е.

Для решения задач МКЛП применяются различные методы све­ дения их к одному скалярному критерию: метод взвешенных сумм, методы сжатия допустимой области, метод е-ограничений, алгорит­ мы векторной максимизации, различные интерактивные процедуры

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

§5.13. Метод взвешенных сумм с точечным оцениванием весов

Метод взвешенных сумм с точным оцениванием весов заклю­ чается в следующем. Каждый критерий cjx умножается на поло­ жительный весовой коэффициент Xj, все к взвешенных критери­ ев суммируются и образуют составную целевую функцию \ гС х

(целевую функцию, состоящую из взвешенной суммы). Предполо­ жим, что все весовые векторы X Е R fe нормированы так, что сумма их координат X», i = 1,2, — , As, равна 1 (в норме пространства Ь\). Множество таких весовых векторов имеет вид

А =

При известных весовых векторах X е Л получаем однокритери­ альную задачу ЛП

max{XTC x | х е D},

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

Теорема 1. Точка х е D, в которой существует максимум взве­ шенных сумм задачи ЛП max{XTCx | х е D}, где ХеЛ, является эффективной точкой.

Теорема 2. Если х Е D — эффективная точка, то существует вектор X Е А, при котором х является решением задачи

т а х ^ С х | х е D }.

В силу этих теорем все точки, максимизирующие при X > 0 взве­ шенные суммы в задаче ЛП, являются эффективными.

Если взвешенная сумма ХтС х в задаче ЛП оказалась неограни­ ченной для некоторого весового вектора, то этому весовому векто­ ру нельзя поставить в соответствие ни одной эффективной точки, но могут существовать другие положительные весовые векторы, для которых взвешенные суммы будут ограничены.

Если один или более весовых коэффициентов равны нулю, то нельзя гарантировать, что все точки, максимизирующие взве­ шенную сумму в задаче ЛП, являются эффективными. Следует помнить, что стандартные пакеты программ ЛП могут не выяв­ лять все граничные точки, максимизирующие целевую функцию,

а выводят лишь первую подходящую точку, даже если эта точка не является эффективной.

Один из способов задать весовые коэффициенты — назначить разным критериям их так, чтобы градиент взвешенной суммы ХТС х

цируема. Градиент сложной функции и в точке х имеет вид

где частные производные du/dzi вычисляются в точке х, V xZi —

градиент г-го критерия:

V xZi = Ci.

Пусть du/dzi > 0. Введем положительные скаляры

_ du/dzi Wl du/dz\ ’

вычисленные в точке х. Тогда направление градиента V xu в точке х

можно задать в виде

к

V xu = WiCi. i—1

Нормируя скаляры го», получаем

к

Функция полезности и в общем случае нелинейна, и ее гради­ ент будет изменяться от точки к точке. Рассмотрим касательную гиперплоскость к поверхности уровня функции и в точке х:

где Zi = с]х, с[х = Zi. Разделив это уравнение на du/dz\ > 0, по­ лучим

1 • («1 - *0 + W2(Z2 - z 2) + ... + wk(zk - zk) = 0.

Для оценки скаляров Wi, i = 2 ,3 , ... , А:, вводится произволь­ ная величина Aj > 0, чтобы компенсировать изменения градиента,

Какие из критериев необходимо перевести в ограничения и ка­ кие задать значения правых частей ej, определяет пользователь. Например, неверный выбор ej может привести к несовместной за­ даче ЛП. Решение принимают на основе анализа серии подобным образом построенных задач ЛП, т. е. процедура решения задачи МКЛП носит интерактивный характер.

Анализ почти оптимальности — другой способ сжатия области допустимых решений. Рассмотрим алгоритм анализа эффективной точки.

1. Решим задачу ЛП со взвешенными суммами

тах{ХтСж = z}, x e D ,

иопределим величину z*

2.Выбрав некоторое z\ < z*, решим задачу ЛП для сжатой об­ ласти допустимых решений.

3.Вычислим все критериальные векторы г,; £ Rn, соответствую­ щие граничным точкам Х{ сжатой области.

4.Выберем точку Х{, соответствующую самому предпочтитель­ ному вектору, в качестве окончательного решения МКЛП.

Трудности здесь могут возникнуть при нахождении всех альтер­ нативных оптимумов для вычисления всех граничных точек.

Пусть D —множество допустимых решений, Е — эффективное множество. В общем случае задачи МКЛП приводят к следующим взаимоисключающим и исчерпывающим ситуациям:

1)D = 0,т.е. система ограничений несовместна;

2)D ф 0 , Е = 0 и значение по крайней мере одного критерия ограничено;

3)D = 0 , Е = 0 и значение всех критериев неограничены;

4)D ф 0 , Е содержит только одну точку;

5) D ф 0 , Е ограничено и содержит бесконечное число точек;

6)D ф 0 , Е неограничено и значение по крайней мере одного критерия неограничено;

7)D Ф 0 , Е неограничено и значения всех критериев неограни­

чены.

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

1) взвешенных сумм;

2)взвешенных сумм с использованием подзадачи-теста;

3)лексикографической максимизации;

4)лексикографической максимизации с использованием подза­ дачи-теста;

5)метод Эккера-Куоды;

6)метод Бенсона.

В методе взвешенных сумм выбирается некоторый вектор

к

i= 1

и решается задача max{XT(7x | х е D}.

Если область D ограничена и D ф 0 , то эффективная точка бу­ дет найдена. Если область D не ограничена, метод не гарантирует нахождения эффективной точки.

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

В методе лексикографической максимизации применяется сле­ дующая процедура сжатия допустимых областей:

D0 = D, D\ = { y e D \ c ) iy = max{cTh x \ x e D 0}},

D k = { y e D \ C j k y = m a x { c Tkj x \ x e D k - i } } ,

где Dh — область, полученная сжатием допустимой области после h максимизаций.

Процесс начинаем с максимизации целевой функции х в об­ ласти Do- Затем, ограничиваясь выбором точек из Do, максимизи­ руем j j-й критерий и получаем область D\. В области D\ максими­ зируем второй критерий cj2x, ограничиваясь рассмотрением точек из D\, максимизирующих j'2-й критерий; получаем область D2. Процесс продолжается до тех пор, пока не получим либо D^ Ф 0 ,