<< Предыдущая

стр. 3
(из 10 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

здесь мы обсудим ряд требований к этим методам в системах поддержки
принятия решений. Для того, чтобы система поддержки принятия решений
была действительно полезной помощницей для лица, принимающего
решение (ЛПР), несущего ответственность за его последствия или для лица,
формирующего решения (ЛФР), аргументировано обосновывающего эти
решения перед ЛПР, эта система должна удовлетворять ряду требований.
Следуя [5], выделим основные требования к человеко-машиным системам
принятия решений:
1. Использование информации в содержательных категориях.
2. Итерационный характер процедуры, удобство корректировки
данных и перестройки модели.
3. Отсутствие исключенных решений.


17
4. Возможность получения тестового решения.
5. Сходимость процедуры к наиболее предпочтительному решению за
приемлемое число итераций.
6. Контролируемость процедуры со стороны ЛПР:
a) содержательная интерпретируемость моделей;
b) содержательная интерпретируемость алгоритмов;
c) регулируемая степень автоматизации.
Особенно выделим пункты 1 и 6. Лицо, принимающее или формирующее
решение, должно получать от системы поддержки принятия решений
рекомендации на понятном ему содержательном языке. Более того, ЛПР или
ЛФР должен понимать логику, заключенную в алгоритме решения задачи и
при необходимости проконтролировать этапы решения. Так, например,
задачу определения оптимальной обменной схемы, как будет показано ниже,
можно сформулировать в виде некоторой задачи линейного или
комбинаторного программирования, для которых существуют стандартные
программные средства.
Однако, непонимание логики, заложенной в методы решения,
отсутствие возможности проконтролировать и обосновать способ получения
результата, а значит и сам результат, ведет к недоверию со стороны ЛПР и
ЛФР к рекомендациям компьютерной программы и, как следствие, к отказу
от услуг такой системы поддержки принятия решений. На
интерпретируемость предлагаемых методов в содержательных категориях
мы будем обращать особое внимание.




18
2. Методы решения задач
оптимизации обменных схем


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

1
16
2
1,6

0
3
2 2
10

1 1
2
8

Рис.82.


Задача определения оптимального потока с усилением в дугах в
данном случае имеет вид: определить {xij ? 0, (i, j) ? U}, где U – множество
дуг сети, максимизирующие
Ф = x01 – x02 + 2x13 + x23 (2.1)
19
при ограничениях
x13 + x12 = 2x21 + 1,6x01
x21 + x23 = x02 + 2x12
? 10 (2.2)
x01 + x02
? 16
x12 + x13
?8
x21 + x23
Оптимальное решение этой задачи имеет вид
x12 = 4, x21 = 8, x13 = 12,
остальные xij = 0 со значением целевой функции Ф0 = 24 (это маргинальная
прибыль фирмы оператора).
Для того, чтобы убедиться, что это решение является оптимальным,
рассмотрим двойственную задачу: определить u1, u2, v0 ? 0, v1 ? 0, v2 ? 0,
минимизирующие:
F = 10v0 + 16v1 + 8v2 (2.3)
при ограничениях:
v0 – 1,6u1 ? -1
u2 ? -1
v0 –
u1 + v1 – 2u2 ? 0
(2.4)
u2 + v2 – 2u1 ? 0
?2
u 1 + v1
?1
u 2 + v2
Оптимальное решение двойственной задачи имеет вид:
u1 = 5/8; u2 = 1; v0 = 0; v1 = 11/8; v2 = ?
со значением целевой функции F = 24.
Совпадение значений целевых функций доказывает оптимальность
обоих решений.
Рассмотрим содержательный смысл полученного решения. Так как
x01 = x02 = 0, то фирма-оператор не тратит свой ресурс, получая при этом


20
весьма ощутимый доход! Фактически фирма-оператор выступает
посредником между фирмой 1 и фирмой 2, организуя обмен ресурсами
между ними (оптимальная схема обмена показана на рис 2 толстыми
дугами). Такие схемы обмена (не включающие ресурс фирмы оператора)
будем называть спекулятивными. Несмотря на всю привлекательность
спекулятивных схем для оператора, они относятся к схемам обмена с
повышенным риском. Действительно, достаточно велика вероятность того,
что фирмы 1 и 2 просто договорятся между собой напрямую, минуя
посредника (фирму-оператора) еще в процессе переговоров. Поэтому
спекулятивные схемы обмена следует рассматривать отдельно.
Гораздо большей надежностью (меньшим риском) обладают так
называемые продуктовые схемы обмена, в которых обменная схема
представляет собой последовательную цепочку фирм, каждая из которых
(включая фирму-оператора) получает какой-либо ресурс в обмен на свой.
Продуктовым схемам обмена соответствует простой путь в сети,
соединяющий вершину 0 с вершиной 3, то есть путь, каждая вершина
которого проходится только один раз. Для нашего примера таких путей
четыре:
µ1 = (0,1,2,3)
µ2 = (0,1,3)
µ3 = (0,2,1,3)
µ4 = (0, 2,3).
Нетрудно проверить, что оптимальным является путь и
(0,1,3)
соответствующий поток x01 = 10, x13 = 16, который обеспечивает чистый
доход Ф1 = 22, что на 2 единицы меньше, чем в спекулятивной схеме.
Наконец, возможны смешанные схемы обмена, включающие
одновременно и продуктовые и спекулятивные схемы. Так, если бы фирма 1
имела ресурс в количестве 24 единицы, то оптимальная схема обмена был бы
следующей: x01 = 5, x12 = 4, x21 = 8, x13 = 20 (остальные xij = 0), что дает
21
чистый доход Ф2 = 40. В данной схеме объединены продуктовая схема (0,1,3)
и спекулятивная (1,2,1,3). Высокий риск спекулятивной схемы может
привести к тому, что фактически будет реализована продуктовая схема
(0,1,3), что дает оператору чистый доход F3 = 11, что меньше чем в
оптимальной продуктовой схеме.
Рассмотренный выше пример показывает, что продуктовые и
спекулятивные схемы следует рассматривать отдельно.




22
3. Построение оптимальных
продуктовых схем обмена


Как было показано выше, задача поиска оптимальной продуктовой
схемы обмена сводится к задаче определения простого пути в сети ВО,
соединяющего начальную вершину сети 0 (вход) с конечной n (выход) и
дающего оператору максимальную маргинальную прибыль. Покажем, что
эта задача является в общем случае NP-трудной комбинаторной задачей,
решение которой требует перебора всех простых путей [4]. Для этого
примем, что ограниченным является только ресурс оператора, а остальные
элементы имеют неограниченное количество ресурса. В этом случае,
очевидно, оптимальной продуктовой схеме обмена соответствует простой
путь в сети, имеющий максимальное произведение обменных
коэффициентов дуг пути (это произведение будем называть усилением пути).
Заметим, что для выгод-ности обменной схемы усиление соответствующего
ей пути должно быть больше единицы. Определим длины дуг сети lij = ln kij.

?l
В этом случае длина любого пути µ будет равна L(µ) = ln K(µ) = , где
ij
i , j?µ


K(µ) – усиление пути µ.
Таким образом, задача поиска простого пути с максимальным
усилением эквивалентна задаче поиска пути максимальной длины. Как
известно, эта задача эффективно решается, если в сети отсутствуют контуры
положительной длины. В противном случае эффективных точных методов ее
решения не существует. В частности, если все обменные коэффициенты
больше 1, а значит длины всех дуг положительны, граф ВО является полным
графом и для любой тройки вершин i, j, k имеет место lij + ljk > lik, то задача
эквивалентна задаче коммивояжера, которая является NP-трудной [4].
Отсюда следует, что в общем случае для выбора оптимальной продуктовой
схемы обмена необходимо применять либо алгоритмы перебора, либо
23
эвристические алгоритмы. В случае если сеть ВО не имеет контуров с
усилением больше 1 (а значит контуров отрицательной длины), существуют
эффективные алгоритмы определения путей с максимальным усилением.
Предлагаемый метод решения задачи состоит из двух этапов.
На первом этапе строится сеть, не имеющая контуров с усилением
больше 1 или просто сеть без контуров, эквивалентная исходной сети.
Эквивалентность понимается в том смысле, что каждому простому пути
исходной сети соответствует простой путь в новой сети (возможно, не один)
и наоборот, каждому простому пути новой сети соответствует один и только
один простой путь в исходной сети.
На втором этапе определяется оптимальный простой путь в новой сети.
Рассмотрим сначала второй этап. Имеется сеть без контуров с
усилением больше 1.Требуется определить простой путь в этой сети и
допустимый поток по этому пути с максимальной величиной маргинальной
прибыли. Сначала рассмотрим алгоритм определения пути с максимальным
усилением.

Описание алгоритма

1 шаг. Помечаем вершину 0 индексом u1 = 1 , а все остальные вершины
0


индексом u1 = 0 , i = 1, n .
i


k-й шаг. Пусть u ik ?1 - индекс вершины i на (k-1) шаге, i = 1, n . Помечаем
вершину i индексом
u ik = max u k ?1 ? k ji , (3.1)
j
j?U i


где Ui – множество дуг, заходящих в вершину i.
За конечное число шагов индексы всех вершин установятся, то есть не
будут меняться при следующих шагах (доказательство этого факта мы дадим
ниже). Обозначим через Фi установившиеся индексы вершин, i = 1, n . В этом
случае величина Фn равна максимальному усилению. Для определения пути,

24
имеющего максимальное усиление, применяем метод «обратного хода», как
это делается в алгоритмах определения экстремальных путей в сетях [6]. А
именно, определяем вершину i1, такую что (i1,n)?U (U – множество дуг сети) и
Ф n = Ф i1 ? k i ,n .

Далее, определяем вершину i2, такую что (i2,i1)?U и
Фi1 = Ф i2 ? k i2 ,i1 ,

и т.д. Эта процедура за конечное число шагов p приведет к вершине ip = 0.
Покажем, что полученный простой путь µ0 = (0, ip-1, ip-2, … , i1, n) имеет
максимальное усиление.
Теорема 1. Полученный методом обратного хода путь определяет
оптимальную продуктовую схему обмена по критерию маргинальной
рентабельности, а сама маргинальная рентабельность равна индексу
конечной вершины n минус 1, то есть (Фn – 1).
Доказательство. Для любой дуги (i, j) имеет место Фj ? kijФi. Поэтому
для усиления K(µ) любого пути µ, соединяющего вход с выходом сети,
имеем
K(µ) ? Фn.
Отсюда следует, что если найдется путь µ0, такой что K(µ0) = Фn, то этот путь
имеет максимальное усиление. Но именно такой путь получается методом
обратного хода. Далее, маргинальная рентабельность
K(µ )x 0 ? x 0
МР = = K(µ) ? 1 ,
x0
где x0 – количество продукта, отдаваемое фирмой-оператором. Теорема
доказана.
Нас, однако, интересует путь, для которого соответствующая
продуктовая схема обмена имеет максимальную прибыль. Определим
максимальный поток x(µ0) по пути µ0 (величиной потока в сети с усилениями

<< Предыдущая

стр. 3
(из 10 стр.)

ОГЛАВЛЕНИЕ

Следующая >>