XX Волков И.К., Загоруйко Е.А. Исследование операций (Зарубин В.С., Крищенко А.П. - Комплекс учебников из 21 выпуска), страница 7

Рассмотрим две точки А и В множества Парето. В силу принципа справедливой абсолютной уступки при переходе от А к В изменение вектора ДХ) характеризуется величиной ес сп ес ес ь =,'>.ь =',.(~'-©=~~'-Х:Ф Ыс! Ьм! !с=1 !с=1 где © ~Ь — значения скалярных критериев в точках А и В. Если Ь,е, ( О, то решение, соответствующее точке В, считается лучшим по сравнению с решением, соответствующим А. Поэтому наилучшим в смысле рассматриваемого принципа будет такое решение, для которого сл,л, 10 при переходе в любую другую точку.

Приведенные рассуждения показывают, что принцип справедливой абсолютной уступки сводится к минимизации суммы скалярных критериев на множестве 0*: сп ,'1 ~ь(Х) -+ ш1п . е=1 Недостаток этого принципа в том, что он допускает дифференциацию по отдельным критериям: низкое значение суммы ~1+11+...+1 может достигаться, когдаодни критерии имеют сравнительно низкий уровень, в то время как другие— сравнительно высокий уровень.

Потенциальная возможность такой дифференциации характерна для задач, в которых критерии выражены в различных единицах измерения. В таких задачах критерии необходимо нормализовать, т.е. привести к рдиному, желательно безразмерному, масштабу измерения. Синтез глобального критерия. Идея этого подхода очень проста: для задачи многокритериальной оптимизации (1.1) строят глобалькык скаллркыб криозериб с целевой функцией Р(Х) =ф[Д(Х),...,У (Х)) =ф(У(Х)), (1.0) зависящей от исходных скалярных целевых функций, таким образом, чтобы решение задачи математического программирования и (Х) -+ ппп ХЕО являлось решением исходной задачи (1.2) в смысле рассматриваемого принципа компромисса. Ограничимся лишь кратким обсуждением сиккзеза глобального скаллркого крккзеркл (от греческого вуп!Ьее!в— 44 Е ОСНОВНЫЕ ПОНЯТИЯ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ соединение, сочетание, составление) для задач многокритери- альной оптимизации'.

Поскольку система неравенств /ь(Хо) < Ь(Х), й = 1, т, Х Е С, эквивалентна системе неравенств 1ь/ь(Хо)+се < 1ь/ь(Х)+се, й = 1, т, Х Ест, где 1ь > О, й = 1, т, и сь ЕК, й= 1, т, могут быть выбраны произвольно, то допустимое решение Хо является решением задачи многокритериальной оптимизации (1.1) тогда и только тогда, когда Хо является решением задачи векторной оптимизации 1ь/ь(Х)+сь-е пнп, /с ее 1, т.

ХЕС Исходя из этого, рассмотрим те требования, которым должна удовлетворять функция Ф[/(Х)] в (1.5). Во-первых, функиия Ф[/м...,/' ] должна быть инварианкана отпноситпельно преобразования сдвиеа, т.е. для любого набора действительных чисел (сь)~, н для любого допустимого решения Х Е С должно выполняться равенство Ф[/, (Х),..., / (Х)] = Ф[/;(Х) + см...,/ (Х) + с ]. (1.6) Во-вторых, ф1/никия Ф[/1(Х),...,/ (Х)] должна быть инвариантна по отноияению к изменению масиатаба любого скалярного критерия ~ь, /с = 1, т, т.е.

для любого набора действительных положительных чисел (1ь)ь, и для любого допустимого решения Х Е С должно выполняться равенство Ф[/,(Х),...,/ (ХУ=Ф[У,(Х),...,1 / (Х)]. (1.7) 'Подробности по проблеме синтеза глобального скалярного критерия можно найти в специальной литературе. См., например; Вемшцеде Е.С., Гермейер Ю.Б.

или Ростриеон Л.А., а также: Теория прогнозирования и принятия решений / Под ред. С.А. Соркосямо. Е2. Об одном аспекте многокритеряальной оптимизации 45 Сформулированные требования означают, что, каков бы ни был набор действительных чисел сы и = 1, т, набор действительных положительных чисел 1ь, /с = 1, т и допустимое решение Х Е с/, верно равенство Ф[/1(Х),...,У (Х)]=Ф[1,Л(х)+с,,...,1 /1(х)+с ]. (1,8) 1о Р(Х) = ~1,,/„(Х), л=1 (1.9) где /ь(Х) — ппп /ь(Х) Х ЕС' шах /ь(Х) — ппп /ь(Х) ХЕО' ХбС' отвечает требованиям (1.6), (1.7). Кроме того, эта функция учитывает и требование нормализации критериев, так как вместо абсолютных значений скалярных критериев рассматриваются безразмерные величины их относительных отклонений от минимальных значений. Критерий (1,9) называют норлеированныле скаяярныле «ритериеяе, В специальной литературе рассматривают другой вид норМированного скалярного критерия, в котором учтена важность отдельных составляющих: ш Р(Х) ее,'» Ль/„(Х), (1.10) где Лы й = 1, т, — некоторые параметры, для которых ,'» Л,=1, О<Л„<1, й=1,т, (1Я1) л=! Выполнение требований (1.6), (1.7) или эквивалентного им требования (1.8), накладываемых на функцию Ф[/(Х)] при синтезе глобального скалярного критерия, определяемого согласно (1.5), может обеспечиваться различными способами.

В частности, функция Вопросы и задачи 47 46 Е ОСНОВНЫЕ ПОНЯТИЯ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ Зти параметры называют весовыма коэффициемпзамм. Весовые коэффициенты можно определять различными способами, но любой подход в конечном счете сводится к использованию экспертных оценок. Отметим, что для эксперта задача определения весовых коэффициентов ничуть не проще задачи ранжирования скалярных критериев, так как в данном случае приоритет каждого скалярного критерия он должен выразить количественно. Вопросы и задачи 1.1. Что понимают под исследованием операций? 1.2. Сформулируйте основную задачу исследования операций.

1.3, Существует ли связь между критерием оптимальности и принципом оптимальности? Ответ аргументируйте. 1.4. В чем заключается принципиальное различие статических и динамических задач исследования операций? 1.5. Приведите классификацию задач исследования операций по структуре информационного состояния „лица, принимающего решения". 1.6. Какую задачу исследования операций называют параметрической и в чем ее принципиальное отличие от задачи принятия решений в условиях неопределенности? 1.7. Приведите классификацию задач исследования операций по виду критерия оптимальности.

1.8. Какая существует связь между задачами математического программирования и векторной оптимизации? 1.8. Докажите свойства транзитивности предпочтения н транзитивности эквивалентности. 1.10. Что называют множеством Парето и почему его часто называют также множеством компромисса? 1.11. В чем заключается основная идея подхода к решению задач многокритериальной оптимизации, связанного с ранжированием скалярных критериев? Какие достаточные условия реализуемости этого подхода Вы знаете? 1.12. В каких ситуациях для решения задач многокритериальной оптимизации используют метод компромиссов? 1.13. Сформулируйте требования, которым должен удовлетворять глобальный скалярный критерий задачи векторной оптимизации, и приведите их обоснование. 1,14. Докажите эквивалентность требований (1.6), (1.7) и (1.8), предъявляемых к глобальному скалярному критерию задачи векторной оптимизации.

1.15. Изложите общую идею синтеза глобального скалярного критерия для задачи векторной оптимизации. 1.16. Какие можно предложить принципы оптимальности для задач многокритериальной оптимизации? 1.17. В примере 1.7 определите множество Парето й* и соответствующее ему подмножество С' множества С допустимых решений.

Ответ: 1.18. Пусть в задаче (1.1) многокритериальной оптимнзацпи т = 2, и = 2 и ~1 (Х) = хз/(х1 + хэ), 7з (Х) = х1 + хз, т С= ((х1 хз): хз 3 охи хз (~ух1, 0 (х, (И) У (1ч.Р)а (1+х Рис. 1.8 Рис, 1.7 48 1. ОСНОВНЫЕ ПОНЯТИЯ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ где д ) 0 и 0 < о < (1. Является ли рассматриваемая задача корректной? Если да, то найдите оптимальное решение Ха Е С.

Ответ: Хо=(0 0) . У к аз а н и е: проанализируйте рис. 1.7 и 1.8. 2. основы линейного ПРОГРАММИРОВАНИЯ Линейное программирование занимает особое место в исследовании операций. Теоретические разработки, опыт практической реализации и анализ результатов применения методов линейного программирования привели к значительным успехам в решении широкого круга практически важных задач, относящихся к таким сферам человеческой деятельности, как промышленное производство, военное дело, сельское хозяйство, экономика, транспорт, здравоохранение. Кроме того, линейное программирование послужило основой для разработки других математических методов исследования операций, например целочисленного и стохастическаго программирования. 2.1.Постановка общей задачи линейного программирования и ее анализ В соответствии с классификацией задач исследования операций (см.

1,1), если множество допустимых решений С С К"— вмпуклый многогранник, а критерий оптимальности — скалярная линейная целевая функция, определенная на С, то мы имеем дело с задачей линейного программирования. Теория этих задач составляет предмет исследований линейного «ро'йраммированил, а их примером может служить задача о со'ставлении пищевого пайка (см. пример 1.2). Говоря о задаче линейного программирования, мы фактически имеем в виду не саму задачу исследования операций, а ее 1натЕМатическУю модель, обладающую указанными специфиче1Э1ими свойствами. Отметим, что для решения одной и той же Нйдачи исследования операций могут быть использованы раз(ине математические модели.

3.1. Постановка общей задачи и ее аназнз 50 2. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 51 По виду инузормационного состояния „лица, принимаючцего решения", задачи линейного программирования являются статическими задачами исследования операций, а соответствующие процедуры принятия решений — одношаговыми. По структуре информационного состояния „лица, принимающего решения", задачи линейного программирования являются детерминированными параметрическими задачами исследования операций.