Хакимзянов Чубаров Воронина печатные лекции часть 2 (973558), страница 10
Текст из файла (страница 10)
Поэтомуприходится принимать некоторое компромиссное решение и первое, чтонужно для этого сделать, — попытаться сократить множество исходныхвариантов, исключив из анализа заведомо плохие варианты решений.Рассмотрим один из подходов к решению этой проблемы, основанныйна принципе Парето1 .Предположим, что сделан некоторый выбор x∗ ∈ Q и существуетb ∈ Q такой, что для всех критериев fi имеют местодругой выбор xнеравенстваfi (bx) > fi (x∗ ), i = 1, .
. . n.(5.29)b безусловно лучше, чем решеВ этом случае говорят, что решение xb.ние x∗ , а решение x∗ безусловно (или заведомо) хуже, чем решение xВсе безусловно плохие решения следует сразу исключить из рассмотрения. В результате этой безусловной оптимизации останутся толькоb , что для всех крите векторы x∗ , для которых не существует такого xтериев удовлетворяются неравенства (5.29).
Таким образом, какие быдва из оставшихся векторов мы не сравнили, любой из них будет лучшедругого хотя бы по одному критерию.Множество PQ всех оставшихся векторов называется множествомПарето и в качестве компромиссного решения следует брать какой-либо1 VilfredoPareto (1848–1923) — итальянский экономист и социолог, представительматематической школы в экономике. Согласно принципу Парето, чтобы сделать процесс работы более эффективным, необходимо выделять области по их значимостиили важности, устраняя те причины, которые вызывают наибольшее количествопроблем (несоответствий).92вектор x из множества PQ . Это правило и называется принципом Парето. Отметим, что принцип Парето не выделяет единственного решения,он только сужает множество альтернатив.
Окончательный выбор остается за лицом, принимающим решение.Пример 5.3. Перевозчики должны доставить продукцию со складов I и II с запасами a1 = 70, a2 = 50 потребителям A и B с потребностями b1 = 80 и b2 = 60, а продавцы должны продать всю привезенную продукцию. За единицу перевезенной продукции перевозчикиполучают вознаграждение, указанное на рис. 21, а, а продавцы — доход, указанный на рис. 22, а. Цель перевозчиков — максимизироватьфункцию (5.1), продавцов — (5.9). Предположим, что лицо, принимающее решение, должно сделать такой выбор объемов перевозок, чтобыпо возможности максимально удовлетворить цели перевозчиков и продавцов.Рассматриваемая задача является двухкритериальной. Обозначимкритерии (5.1) и (5.9) через f1 и f2 , соответственно.
С учетом равенств(5.6), (5.13) мы можем написать, чтоf1 (x) = 810 − 2x1 + x2f2 (x) = 650 + 3x1 − 2x2→ max,→ max,(5.30)где x = (x1 , x2 ) ∈ Q, Q — область допустимых решений, определяемаясистемой ограничений (5.7) и изображенная на рис. 21, б.Уравнения (5.30) определяют отображение области допустимых решений на множество достижимости Ω в плоскости критериев(см. рис. 23): каждому решению x = (x1 , x2 ) ∈ Q соответствует свояточка f = (f1 , f2 ) ∈ Ω. В частности, вершины многоугольника Q переходят при этом отображении в вершины многоугольника Ω (см.
табл. 1).Таблица 1Соответствие вершин многоугольников Q и Ω при отображении (5.30)Вершиныобласти Qabcdex11030707060x200405050Вершинымножества Ωa0b0c0d0e093f1790750710720740f2680740780760730x2e50f2d780c′∧fQ760cbd′b′74030e′720Q700Ω10a10680b305070x1710а730Ωb′750a′770790f1бРис. 23. Многокритериальная задача о перевозках: а — множествоПарето (линия abc) в области Q допустимых решений; б — его образ(линия a0 b0 c0 ) при отображении (5.30) в множестве достижимости ΩИз этой таблицы видно, что если лицо, принимающее решение, выбирает вариант a, то перевозчики получают наибольшую выгоду, а продавцы — наименьшую, а при выборе варианта с — наоборот.
Таким образом, имеет место противоречивость целей (5.30), вследствие чего лицо,принимающее решение, оказывается перед необходимостью искать компромисс, и одним из путей, облегчающих поиск наиболее приемлемогодля всех участников решения, является построение множества Парето.Возьмем, например, решение b ∈ Q и определим все заведомо худшие, чем b, решения x ∈ Q. Для этого через точку b0 = (750, 740) ∈ Ωпроведем прямые f1 = 750 и f2 = 740, которые выделят некоторое подмножество Ωb0 (изображено серым цветом на рис. 23, б) в множестведостижимости. Согласно уравнениям (5.30) прообразами этих прямыхв плоскости x1 Ox2 будут прямые, заданные уравнениями−2x1 + x2 + 60 = 0,3x1 − 2x2 − 90 = 0.Эти прямые высекают в области Q подмножество решений Qb (оно отмечено серым цветом на рис. 23, а), при этом образом множества Qb приотображении (5.30) будет множество Ωb0 .
Поскольку решения x ∈ Qbотображаются в точки f ∈ Ωb0 , имеющие координаты f1 6 750и f2 6 740, то все эти решения являются безусловно не лучшими, посравнению с решением b, и их можно исключить из дальнейшего рассмотрения, т. е. от множества Qb оставить для дальнейшего анализа94единственную точку b. Отметим, что точка e, попавшая в Qb , тоже относится к плохим решениям, в чем можно было убедиться и непосредственно, проанализировав данные табл.
1.Выполнив подобный анализ для всех других решений из области Q,можно убедиться, что множество Парето для данной задачи представляет собой часть abc границы области допустимых решений Q (штрихпунктирная линия на рис. 23, а), т. е.½¾¯h 0,x1 ∈ [10, 30],¯PQ = (x1 , x2 )¯ x1 ∈ [10, 70], x2 =. (5.31)x1 − 30, x1 ∈ [30, 70]При отображении (5.30) множество Парето преобразуется в частьa0 b0 c0 (штрих-пунктирная линия на рис. 23, б) границы области достижимости.
Видно, что если при переборе решений из множества Паретоодин из показателей растет, то другой непременно уменьшается.Пример 5.4. В предыдущем параграфе была рассмотрена приближенная экономическая модель (4.25), описывающая динамику капиталовооруженности и численности работающих. Если параметры α, β,m, δ этой модели зафиксировать, то в состоянии равновесия капиталовооруженность x∗ и численность работающих y∗ будут определяться двумя свободными параметрами k и s в соответствии с формулами (4.27):µ¶1/αβx∗ = x∗ (k, s) =,k(1 − s)mµ¶(α−1)/αsmβy∗ = y∗ (k, s) =.δk(1 − s)m(5.32)Предположим, что лицо, принимающее решение, заинтересованов максимальной капиталовооруженности производства и наибольшейзанятости, а областью Q его допустимых решений является множествопараметров (k, s) таких, что 0 < k1 6 k 6 k2 < 1, 0 < s1 6 s 6 s2 < 1,т.
е. прямоугольник Q, изображенный на рис. 20, а. Таким образом,получается проблема с двумя целямиx∗ (k, s) → max,y∗ (k, s) → max,(5.33)при этом каждому решению (k, s) ∈ Q будет соответствовать своя точка(x∗ , y∗ ) из области достижимости Ω, изображенной на рис. 20, б и являющейся образом области допустимых решений Q при отображении (5.32).95Как видно из рис. 24, критерий x∗ принимает максимальное значение при выборе решения d = (k1 , s2 ), но численность работающих приэтом будет очень мала. С другой стороны, наибольшая занятость будетпри выборе решения e, соответствующего параметрам k = k2 , s = α(см.
задачу 5.2), однако при таком выборе оказывается крайне низкойкапиталовооруженность производства. Таким образом, цели (5.33) являются противоречивыми и лицо, принимающее решение, должно пойтина некоторое компромиссное решение — наиболее приемлемое с точкизрения достижения целей (5.33).Из рис. 24 видно также, что многие варианты из области допустимыхрешений Q являются заведомо плохими, поэтому их можно сразу отбросить и компромиссное решение искать в множестве Парето.
Выясним,как оно выглядит. Выберем, например, решение c = (k2 , s2 ). В областидостижимости ему соответствует граничная точка c0 . Проведем черезточку c0 прямые, параллельные координатным осям. Тогда в областидостижимости получится подмножество Ωc0 (отмеченное серым цветомна рис.
24, б), состоящее из точек, у которых обе координаты не превосходят соответствующих координат точки c0 . Согласно формулам (5.32),проведенные прямые являются образами кривыхµ ¶α/(α−1)sk(1 − s) − k2 (1 − s2 ) = 0, k(1 − s) − k2 (1 − s2 )= 0, (5.34)s2ss2deQcs1∧c′Qαe′y*cΩc ′Ωb′afd′ba′k1аk2kбx*Рис. 24. Многокритериальная задача (4.25), (5.33): а — множествоПарето (линия dce) в области Q допустимых решений; б — его образ(линия d0 c0 e0 ) при отображении (5.30) в множестве достижимости Ω;α = 0, 6; k1 = s1 = 0, 2; k2 = s2 = 0, 896которые ограничивают подмножество Qc ⊂ Q (изображено серым цветом на рис.
24, а). Поскольку при отображении (5.32) образ каждой точки из Qc лежит в Ωc0 , то все эти точки являются безусловно не лучшими,чем решение c, поэтому их можно исключить из дальнейшего рассмотрения. Легко понять, что в результате такого отбора останутся только терешения из Q, которые отображаются на дугу d0 c0 e0 границы областидостижимости. Оставшиеся решения и составят множество Парето —часть dce границы области допустимых решений (штрих-пунктирнаялиния на рис. 24, а).5.3. После нахождения множества Парето встает вопрос о выбореединственного решения из этого множества, наиболее приемлемого длямногоцелевой задачиfi (x) → max,i = 1, .
. . n.(5.35)Поскольку в множестве Парето не существует безусловно лучших решений, то найти вектор x, на котором все критерии принимают максимальные значения, не удается. Поэтому при исследовании многокритериальных задач указывают некоторые условия согласования критериев.В частности, довольно часто используется метод скаляризации — сведение многокритериальной задачи с вектор-функцией целей f (x) к задачес одним, единым скалярным критерием F (x).Укажем некоторые подходы к скаляризации критериев. Линейнаясвертка критериев определяется формулойF (x) =nXCi fi (x) → max,(5.36)i=1где Ci — некоторые положительные числа, тем или иным способом нормированные, например,nXCi = 1.(5.37)i=1Коэффициенты Ci отражают ранжирование целей и предлагаются экспертами.Если функции fi и ограничения, наложенные на выбор компонентвектора x, линейны:fi (x) =lXdsi xs ,s=197i = 1, .
. . n,(5.38)lXαsj xs ≤ bj ,j = 1, . . . m,(5.39)s=1то одноцелевая задача с критерием (5.36) сводится к задаче линейногопрограммирования: определить максимум линейной формыF (x) =n XlXCi dsi xs(5.40)i=1 s=1при линейных ограничениях (5.39). Для решения полученной задачиможно использовать, например, рассмотренный выше симплекс-метод.Очень часто в задачах планирования и проектирования задаетсянекоторая система нормативов f1∗ , f2∗ , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
