Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания
Дискретная оптимизация и моделирование в условиях неопределенности данных
Перепелица В. А., Тебуева Ф. Б.,
4.1.3. Дискретные задачи с интервальными данными
Применение интервального анализа и различных минимаксных (гарантированных) подходов обладает целым рядом преимуществ [13], [48]:
- не требуется знание вероятностных характеристик неопределенных факторов, которые редко бывают точно известны на практике;
- при минимаксном подходе можно получить строгие оценки для самих искомых величин, а не для вероятностей или математических ожиданий, что имеет большое значение при наличии малого числа замеров параметров и одной или нескольких реализаций;
- статистические характеристики не могут гарантировать определенный исход одного конкретного опыта;
- во всех случаях даются гарантированные двусторонние аппроксимации искомых решений.
Однако, процесс моделирования задач с интервальными данными требует осуществления алгебраических операций над областями, в результате чего на выходе используемых алгоритмов получаются области весьма сложной формы, что и порождает известные трудности решения интервальных задач. Главная проблема в решении реальных задач с интервальными данными – это проблема точности получаемого результата. В общем случае точность интервального результата полностью определяется следующими четырьмя факторами [72].
1. Неопределенность в задании исходных данных.
2. Округления при выполнении операций, изменяющих или порождающих интервальные объекты.
3. Приближенный характер используемого численного метода.
4. Степень учета зависимостей между участвующими в вычислении интервальными объектами (переменными и константами).
Численное решение интервальных задач базируется на интервальной арифметике [38].
4.1.3.1. Интервальная арифметика
Пусть 
– множество всех вещественных чисел.
Под интервалом 
, 
понимается замкнутый ограниченный отрезок на числовой оси.
Множество всех интервалов обозначим через 
. Элементы записываются прописными буквами. Если 
– элемент (
), то его левый и правый концы обозначим 
и 
, а также . Символы 
и т.п. понимаются в обычном теоретико-множественном смысле, причем 
обозначает не обязательно строгое включение, т.е. соотношение 
допускает равенство интервалов.
Два интервала , 
равны тогда и только тогда, когда 
, 
.
Отношение строгого порядка на множестве определяется следующим образом: 
тогда и только тогда, когда 
. Возможно также упорядочение по включению: не превосходит 
, если 
. Пересечение 
интервалов и пусто, если 
или 
, в противном случае 
является снова интервалом.
Для интервала 
симметричным, по определению, является интервал 
, у которого 
, 
.
Шириной 
интервала называется величина 
.
Середина 
есть полусумма его концов: 
.
Абсолютная величина 
определяется как 
.
Нетрудно заметить, что 
, когда , причем 
, если 
и 
.
Расстояние 
между элементами 
вводится равенством: 
.
Вырожденный интервал, т.е. интервал с совпадающими концами 
отождествляется с вещественным числом 
. Таким образом имеем включение 
.
Арифметические операции над интервальными числами определяются следующим образом. Пусть 
, , тогда
.(4.6)
В случае деления 
.
Определение (4.6) эквивалентно соотношениям:
(4.7)
(4.8)
(4.9)
(4.10)
Операцию вычитания можно выразить через сложение и умножение, положив 
и 
.
Если и – вырожденные интервалы, то равенства (4.7)-(4.10) совпадают с обычными арифметическими операциями над вещественными числами. Из определения (4.6) непосредственно видно, что интервальные сложения и умножение ассоциативны и коммутативны, т.е. для 
имеют место равенства
, 
,
, 
.
Роль нуля и единицы играют обычные 0 и 1, которые отождествляются с вырожденными интервалами 
и 
, т.е.
, 
.
Равенства (4.6)-(4.10) показывают, что если один из операндов является невырожденным интервалом, то и результат арифметической операции также невырожденный интервал. Исключение составляет умножение на 
. Отсюда следует, что для невырожденного интервала не существует обратных по сложению и умножению элементов, т.к. если 
, 
, то 
должны быть вырожденными, т.е. вычитание не является обратным сложению, деление не обратно умножению. Значит, 
, 
, когда 
. Всегда 
и 
.
Основная теорема интервальной арифметики отражает такое важное транзитивное свойство, как монотонность по включению. Это значит, что если 
, 
, то выполняются соотношения
, 
,
, 
(если 
).
4.1.3.2. Экстремальные задачи на графах с интервальными данными
Сформулируем интервальную экстремальную задачу на графах. В заданном 
-вершинном графе 
каждое ребро 
взвешено интервалом
, т.е. отрезком 
, где 
. Допустимое решение рассматриваемой задачи представляем в виде подграфа 
, 
, 
. Обозначим через 
МДР рассматриваемой задачи, на котором определена интервальная целевая функция (ИЦФ) вида MAXSUM
(4.11)
или ИЦФ вида MAXMIN
(4.12)
Значение этих ИЦФ можно получить из свойств представленных выше операций сложения интервалов (4.6), (4.7) и сравнения интервалов [64],откуда значение ИЦФ (4.11) или (4.12) также есть интервал
где 
, 
. Под решением интервальной задачи понимается такой элемент 
, на котором значение ИЦФ (4.11) или (4.12) достигает требуемого экстремума.
В случае интервальных весов нахождение оптимума наталкивается на проблему выбора наиболее целесообразного решения из множества несравнимых альтернатив [92]. В связи с этим необходимо ввести отношения предпочтения, эквивалентности и несравнимости [22], [58].
Определение 4.1. Бинарное отношение (БО) предпочтительности условимся обозначать символом 
, БО несравнимости – символом 
, БО эквивалентности – символом ~. БО предпочтительности определяется с учетом того, является ИЦФ максимизируемой (см. (4.11) и (4.12)) или, наоборот, она является минимизируемой. Из двух элементов 
и 
, 
, решение 
предпочтительнее решения 
(
), если 
, 
в случае минимизируемой ИЦФ и 
, в случае максимизируемой ИЦФ. Решения и несравнимы (
), когда имеет место строгое вложение интервалов 
, либо 
. Эти решения эквивалентны (
), если совпадают соответствующие им интервалы 
.
Отношения предпочтения и несравнимости порождают на МДР 
паретовское множество (ПМ) 
[74], состоящее из паретовских оптимумов (ПО).
Определение 4.2. Для задачи с ИЦФ (4.13) решение 
называется ПО, если не существует такого элемента 
, что 
.
В качестве искомого решения сформулированной задачи можно рассматривать как ПМ 
, так и используемое в многокритериальной оптимизации понятие ПМА 
[74].
Определение 4.3. ПМА есть подмножество 
минимальной мощности, содержащее по одному представителю на каждое значение 
, 
, где 
есть значение ИЦФ.
Весьма важным является принципиальная возможность сведения задач с интервальными данными к многокритериальным задачам [7].
В завершение анализа неопределенности данных отметим, что попытки применения какого-либо одного конкретного математического аппарата (детерминированных моделей, статистических методов, нечетких множеств, интервального анализа и т.д.) для моделирования и принятия решений в условиях неопределенности позволяет адекватно отразить в математической модели лишь отдельные виды данных, и, таким образом, может привести к потере информации других типов. Иными словами, речь идет о целесообразности комбинированного использования нескольких подходящих инструментариев при математическом моделировании в условиях неопределенности. Опыт реализации такого подхода показывает, что его реализация приводит к построению соответствующей многоуровневой математической модели.