Eng | Rus | Ukr
Исследование операций
24.12.2008

<< prev | ^up^ | next >>

9.7. многокритериальные ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ КАК ЗАДАЧИ НЕЧЕТКОГО МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

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

Возможен и другой подход к решению таких задач,  основанный на переходе от исходной задачи НМП к задаче многокритериальной оптимизации с дальнейшим применением соответствующего математического аппарата.

Задачи линейного программирования с нечеткими
целевыми функциями.

Весьма распространена на практике задача математического программирования с целевыми функциями, с интервально заданными параметрами вида

                      (9.7.1)

при ограничениях                            ,                         (9.7.2)

где - векторы,  - вектор коэффициентов целевой функции.

Рис. 9.10

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

Тогда задача ЛП имеет единственную ц.ф., а мы сталкиваемся с проблемой, которая содержит бесконечно много ц.ф. вида (9.7.1), которые должны быть минимизированы одновременно для , где . Все векторы
из ограниченного интервала     должны рассматриваться как параметры.

По аналогии с теорией ЛП с несколькими ц.ф. 'полное' решение задачи ЛП с интервальними коэффициентами вида

I)

определяется как:

.

Пример. 9.16. Рассмотрим задачу ЛП с множеством допустимых решений [7]:

 

и ц.ф. с интервально заданными коэффициентами:

при

Полное решение  этой оптимизационной задачи соответствует ломаной линии многоугольника от точки  через точки  к  (см. рис. 9.10).

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

Введем следующее определение.

Если функция -функция предпочтения для задачи (9.7.1)-(9.7.2), то элемент  называется компромиссным решением задачи (9.7.1) если  и .

Поиск компромиссного решения.

Чтобы определить компромиссное решение задачи ЛП, предложены различные функции предпочтения, которые преобразуют бесконечное множество ц.ф. в единственную компромиссную ц.ф. [1;18]

Самый простой способ такого подхода - это выбрать по одному представителю  для каждого интервала  и вместо задачи (9.7.1) перейти к задаче ЛП вида:

максимизировать .       (9.7.3)

При рассмотрении вопроса выбора подходящих компромиссных ц.ф. необходимо исключить два крайних случая:

 ,

так как они отражают либо слишком пессимистическую, либо слишком оптимистичную ситуацию.

Для достижения компромиссного решения  было бы разумным выбрать в качестве представителя для каждого интервала значение с наибольшими шансами появления. Однако обычно ЛПР не имеет достаточной информации и, следовательно,  он в основном выбирает середину интервала и, таким образом,

 .                 (9.7.4)

В качестве развития этого варианта, можно предложить ц.ф.,  основанную на решающем правиле Гурвица (см. гл. 1)

       (9.7.5)

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

1) указать вероятность состояний

2) определить для каждого состояния природы параметры настолько точно, насколько это возможно.

Тогда, согласно подходу Бернулли, ожидаемая величина

                             (6.7.6)

должна быть выбрана в качестве функции компромисса.

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

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

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

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

II)   .                     (9.7.7)

Эта редукция связана с уменьшением множества допустимых компромиссных решений, поскольку полное решение задачи ІІ, обозначаемое , есть собственное подмножество множества .

Множество компромиссных решений, однако, не ограничивается крайними точками многогранника .

Пример. 9.17. Рассмотрим вновь задачу оптимизаци из примера 9.16. Для нее система ІІ , полученная путем редукции ц.ф., дает векторную ц.ф. вида

максимизировать

 .                                         (9.7.8)

На рис. 9.10 полное решение  этой задачи векторной оптимизации соответствует ломаной линии от точки  к точке  через точки .

Чтобы найти компромиссное решение проблемы ІІ, можно использовать метод ограничений для задач векторной оптимизации (см. гл. 1) или аналогичный способ, предложенный Циммерманом [20].

В соответствии с этим подходом сначала определяем максимум целевых функций  как решения обычных задач ЛП

,                        (9.7.9)

.                     (9.7.10)

Если оптимальные решения  не определяются однозначно, то выбираются векторы, которые отличаются наиболее сильно.

Обозначим , .

 Разумно предположить, что ЛПР желает принять такое решение, которое имеет свойства  и .

Это предположение сокращает множество допустимых решений до подмножества  .

С такой добавочной информацией ЛПР способен выразить свои цели более точно, введя функции принадлежности, которые отражают его степень удовлетворения достигнутыми значениями ц.ф. Для удобства будем считать, что эти функции линейны и имеют вид

    (9.7.11)

Будем иметь следующую задачу векторной оптимизации.

ІІІ )                                 (9.7.12)

при условиях .

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

 .

Для вычисления компромиссного решения задачи ІІІ, применим следующий подход.

Введем величину , которую можно интерпретировать как степень удовлетворения ЛПР значениями ц.ф. Тогда компромиссное решение получим, решив задачу ЛП [20]

максимизировать                           (9.7.13)

при условиях

IV)                (9.7.14)

Пример 9.18. Для оптимизационной задачи в примере 9.16 использование нечетких ц.ф. типа (9.7.11) приводит к множеству допустимых решений ІІІ (заштрихованная область на рис. 9.10).

Крайние точки на ломаной линии , которые отображают полное решение этой проблемы, принадлежат множеству ХІІІ.

Находим

Соответствующая модель задачи (9.7.13), (9.7.14) принимает вид

найти

при условиях

Оптимальное решение этой задачи ЛП

 .

Определение компромиссного решения на основе
использования информации о функциях принадлежности.

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

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

Предположим, что нечеткие  множества выпуклые, тогда каждое -сечение функций  представляет собой замкнутый интервал .

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

 ,            (9.7.15)

где . Для каждой из этих  оптимизационных задач (9.7.15) компромиссное решение можно вычислить с помощью процедуры, описанной в задаче (9.7.13), (9.7.14).

Алгоритм формирования пары целевых функций уровня.

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

1. Редукция задачи. Каждая оптимизационная задача (модель) с интервально заданными параметрами сокращается до модели векторной оптимизации вида

 ,             (9.7.16)

которая содержит параметры .

2. Вычисление оптимального значения . Находим максимальные значения ц.ф. ,  решая соответствующие задачи ЛП: .

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

3. Вычисление минимума ц.ф. Для каждого вычисляем минимальные значения ц.ф. (нижние границы): , которые должны быть превышены в любом случае.

4. Выбор подходящей функции принадлежности. При рассмотрении каждой оптимизационной модели (9.7.16) ц.ф.  заменяется функцией принадлежности , которая отражает степень удовлетворения ЛПР значениями . Если используются линейные ц.ф., то они будут иметь вид

(9.7.17)

 

.

 
     (9.7.17)

Чтобы учесть информацию обо всех множествах - уровня, необходимо найти решение следующей задачи векторной оптимизации V

V) .                                  (9.7.18)

Пример 9.19. Для задачи, приведенной в примере 9.18, предположим, что ф.п.  и , приведены на рис. 9.11, 9.12 соответственно отображают информацию ЛПР.

Интервалы, показанные на рис. 9.11, 9.12 являются -сечениями, где , и равны соответственно:

 

Text Box: 
Рис. 9.12
Text Box: 
Рис. 9.11
Оптимизационные задачи (9.7.16), соответствующие этим -сечениям являются указанными выше значениями, имеют следующие решения:

а) соответствует ломаной линии от  через  на рис. 9.13;

б)  соответствует ломаной линии от  через ;

в)  соответствует ломаной линии от  через

г)  соответствует ломаной линии от  через

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

Модель эквивалентной задачи ЛП.

В случае использования линейных функций компромиссное решение задачи (9.7.18) можно получить как решение следующей задачи ЛП.

VI: Найти

при условиях

              (9.7.19)

Замечание. Если ограничения содержат также нечеткие коэффициенты, то такие нечеткие ограничения следует заменить на систему ограничений с интервально заданными коэффициентами. Поэтому - сечения ( ) должны быть сформированы для каждого значения нечеткого параметра таким образом, чтобы получить различные системы ограничений вида (9.7.20).

Если обозначить множество допустимых решений задачи (9.7.20) через , то множество  допустимых решений соответствующих моделей (9.7.18) есть подмножество множества .

МДР задачи (9.7.19) получим, дополнительно рассматривая ограничения .

Text Box: 
Рис. 9.13
  Для учета влияния всех  задач на компромиссное решение существенно важно, чтобы ни для одного уровня  соответствующее полное решение не состояло из одного элемента или не было пустым.

Пример 9.20. Для оптимизационной задачи в примере множество допустимых решений (МДР) VI представляет симплекс с крайними точками  на рис. 9.13, а полное решение  соответствует ломаной линии от  к . Соответствующее компромиссное решение задачи VI имеет вид:

максимизировать

при условиях

Решив эту задачу, получим .

Это оптимальное решение дает следующее среднее значение ц.ф.

 где .

Устойчивость решений, относящихся к разных - уровням.

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

Эти значения отражают степень (уровень) удовлетворенности ЛПР достигнутыми значениями ц.ф. .

В частности, для линейных ц.ф. вычисляем

 .                    (9.7.22)

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

Таблица 9.15

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

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

Таблица 9.16

Следовательно, при использовании дополнительной информации по различным - уровням получается более качественное решение.

С другой стороны, следует ожидать другого решения, если ЛПР ориентируется только на ц.ф. со значениями функций принадлежности, большими или равными 0,75 .

Соответствующая оптимизационная модель VI при  дает решение

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

Таблица 9.17

Если функцию  заменить так, что крутизна справа от пика несколько уменьшится (рис.9.14), а другую функцию  оставить неизменной, то МДР системы будут обладать свойством

В этом случае оптимизационная задача VIII будет иметь решение  

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

Таблица 9.18

Если игнорировать уровень , то оптимизационная модель VIII будет иметь решение .

Text Box: 
Рис. 9.14
  Таким образом, использование более широкого диапазона -уровней в модели оптимизации обеспечивает значительно высокий уровень устойчивости полученных решений и, следовательно, более качественное решение задачи ЛП с нечеткой целевой функцией.

<< prev | ^up^ | next >>

 
     
  Copyright © 2002-2004