Методы решения задач оптимизации обменных схем
Однако, непонимание логики, заложенной в методы решения, отсутствие возможности проконтролировать и обосновать способ получения результата, а значит и сам результат, ведет к недоверию со стороны ЛПР и ЛФР к рекомендациям компьютерной программы и, как следствие, к отказу от услуг такой системы поддержки принятия решений. На интерпретируемость предлагаемых методов в содержательных категориях мы будем обращать особое внимание.
Методы решения задач оптимизации обменных схем
В предыдущей главе была рассмотрена задача оптимизации обменных схем. В работе [3] эта задача сведена к определению оптимальной циркуляции в графе с усилениями в дугах или к определению оптимального потока на сети с усилениями в дугах. Однако, полученная в результате решения этой задачи обменная схема может не удовлетворять ряду требований, которые не учтены в формальной постановке.
Чтобы разобраться в сути этих дополнительных требований, рассмотрим простой пример.
Пример 2.1. Рассмотрим сеть ВО из четырех вершин (рис. 2).
Вершины 0 и 3 соответствуют фирме-оператору, числа у дуг равны обменным коэффициентам, нижние числа в вершинах равны количеству ресурса, имеющегося у соответствующего элемента.
Ф = Х01 - Х02 + 2xi3 + X23
(2.1)
19
при ограничениях
Х13 + Х12 = 2x21 + 1,6x01 Х21 + Х23 = Х02 + 2X12 Оптимальное решение этой задачи имеет вид
Х12 = 4, Х21 = 8, Х13 = 12,
остальные Ху = 0 со значением целевой функции Ф0 = 24 (это маргинальная прибыль фирмы оператора).
Для того, чтобы убедиться, что это решение является оптимальным, рассмотрим двойственную задачу: определить u1, u2, v0 0, v1 0, v2 0,
минимизирующие:
F = 10v0 + 16v1 + 8v2 (2.3)
при ограничениях:
v0 - 1,6u1 -1 v0 - U2 -1
u1 + v1 - 2u2 0 u2 + v2 - 2u1 0
Оптимальное решение двойственной задачи имеет вид:
u1 = %; u2 = 1; v0 = 0; v1 = 11/8; v2 = У со значением целевой функции F = 24.
Совпадение значений целевых функций доказывает оптимальность обоих решений.
Рассмотрим содержательный смысл полученного решения. Так как Х01 = Х02 = 0, то фирма-оператор не тратит свой ресурс, получая при этом
весьма ощутимый доход! Фактически фирма-оператор выступает посредником между фирмой 1 и фирмой 2, организуя обмен ресурсами между ними (оптимальная схема обмена показана на рис 2 толстыми дугами). Такие схемы обмена (не включающие ресурс фирмы оператора) будем называть спекулятивными. Несмотря на всю привлекательность спекулятивных схем для оператора, они относятся к схемам обмена с повышенным риском.
Действительно, достаточно велика вероятность того, что фирмы 1 и 2 просто договорятся между собой напрямую, минуя посредника (фирму-оператора) еще в процессе переговоров. Поэтому спекулятивные схемы обмена следует рассматривать отдельно.
Гораздо большей надежностью (меньшим риском) обладают так называемые продуктовые схемы обмена, в которых обменная схема представляет собой последовательную цепочку фирм, каждая из которых (включая фирму-оператора) получает какой-либо ресурс в обмен на свой. Продуктовым схемам обмена соответствует простой путь в сети, соединяющий вершину 0 с вершиной 3, то есть путь, каждая вершина которого проходится только один раз. Для нашего примера таких путей четыре:
mi = (0,1,2,3) m2 = (0,i,3) тз = (0,2,i,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), что дает чистый доход Ф2 = 40.
В данной схеме объединены продуктовая схема (0,1,3) и спекулятивная (1,2,1,3). Высокий риск спекулятивной схемы может привести к тому, что фактически будет реализована продуктовая схема (0,1,3), что дает оператору чистый доход F3 = 11, что меньше чем в оптимальной продуктовой схеме.
Рассмотренный выше пример показывает, что продуктовые и спекулятивные схемы следует рассматривать отдельно.
Построение оптимальных продуктовых схем обмена
Как было показано выше, задача поиска оптимальной продуктовой схемы обмена сводится к задаче определения простого пути в сети ВО, соединяющего начальную вершину сети 0 (вход) с конечной n (выход) и дающего оператору максимальную маргинальную прибыль. Покажем, что эта задача является в общем случае NP-трудной комбинаторной задачей, решение которой требует перебора всех простых путей [4]. Для этого примем, что ограниченным является только ресурс оператора, а остальные элементы имеют неограниченное количество ресурса. В этом случае, очевидно, оптимальной продуктовой схеме обмена соответствует простой путь в сети, имеющий максимальное произведение обменных коэффициентов дуг пути (это произведение будем называть усилением пути).
Заметим, что для выгод-ности обменной схемы усиление соответствующего ей пути должно быть больше единицы. Определим длины дуг сети %j = *n kij.
В этом случае длина любого пути m будет равна L(m) = 9n K(m) = I V где
i,jem
K(m) - усиление пути m.
Таким образом, задача поиска простого пути с максимальным усилением эквивалентна задаче поиска пути максимальной длины. Как известно, эта задача эффективно решается, если в сети отсутствуют контуры положительной длины. В противном случае эффективных точных методов ее решения не существует.
В частности, если все обменные коэффициенты больше 1, а значит длины всех дуг положительны, граф ВО является полным графом и для любой тройки вершин i, j, k имеет место %j + j - ik, то задача эквивалентна задаче коммивояжера, которая является NP-трудной [4]. Отсюда следует, что в общем случае для выбора оптимальной продуктовой схемы обмена необходимо применять либо алгоритмы перебора, либо эвристические алгоритмы.
В случае если сеть ВО не имеет контуров с усилением больше 1 (а значит контуров отрицательной длины), существуют эффективные алгоритмы определения путей с максимальным усилением. Предлагаемый метод решения задачи состоит из двух этапов.
На первом этапе строится сеть, не имеющая контуров с усилением больше 1 или просто сеть без контуров, эквивалентная исходной сети. Эквивалентность понимается в том смысле, что каждому простому пути исходной сети соответствует простой путь в новой сети (возможно, не один) и наоборот, каждому простому пути новой сети соответствует один и только один простой путь в исходной сети.
На втором этапе определяется оптимальный простой путь в новой сети.
Рассмотрим сначала второй этап. Имеется сеть без контуров с усилением больше 1. Требуется определить простой путь в этой сети и допустимый поток по этому пути с максимальной величиной маргинальной прибыли.
Сначала рассмотрим алгоритм определения пути с максимальным усилением.
Описание алгоритма
1 шаг. Помечаем вершину 0 индексом u0 = 1, а все остальные вершины индексом u1 = 0, i = 1, n.
к-й шаг. Пусть uk-1- индекс вершины i на (k-1) шаге, i = 1,n. Помечаем вершину i индексом
uk = maxuk-1 ¦ kji, (3.1)
jeUi
где Ui - множество дуг, заходящих в вершину i.
За конечное число шагов индексы всех вершин установятся, то есть не будут меняться при следующих шагах (доказательство этого факта мы дадим ниже). Обозначим через Фі установившиеся индексы вершин, i = 1,n.
В этом случае величина Фп равна максимальному усилению. Для определения пути, имеющего максимальное усиление, применяем метод обратного хода, как это делается в алгоритмах определения экстремальных путей в сетях [6]. А именно, определяем вершину іь такую что (ii,n)eU (U - множество дуг сети) и
Ф = Ф. ¦ k.
n ii i,n
Далее, определяем вершину і2, такую что (i2,i1)eU и
Ф. = Ф. ¦ k- ¦
ii i2 i2,il ’
и т.д. Эта процедура за конечное число шагов p приведет к вершине ip = 0. Покажем, что полученный простой путь р0 = (0, ip-1, ip-2, ... , i1, n) имеет максимальное усиление.
Теорема 1. Полученный методом обратного хода путь определяет оптимальную продуктовую схему обмена по критерию маргинальной рентабельности, а сама маргинальная рентабельность равна индексу конечной вершины n минус 1, то есть (Фп - 1).
Доказательство. Для любой дуги (i, j) имеет место Фj kijФi. Поэтому для усиления K(m) любого пути m, соединяющего вход с выходом сети, имеем
K(m) Фп.
Отсюда следует, что если найдется путь р0, такой что K(m0) = Фп, то этот путь имеет максимальное усиление. Но именно такой путь получается методом обратного хода. Далее, маргинальная рентабельность
МР = K(m)x - x = K(m) -1, x0
где x0 - количество продукта, отдаваемое фирмой-оператором. Теорема доказана.
Нас, однако, интересует путь, для которого соответствующая продуктовая схема обмена имеет максимальную прибыль. Определим максимальный поток x(m0) по пути р0 (величиной потока в сети с усилениями в дугах будем считать поток, выходящий из начальной вершины). Имеем
x(mo) = .
i*n Ф.
Пусть минимум достигается в вершине q0. Эту вершину будем называть насыщенной. Тогда имеет место:
Теорема 2. Путь m0 определяет оптимальную схему обмена по критерию маргинальной прибыли среди всех путей, проходящих через насыщенную вершину.
Доказательство. Для всех путей, проходящих через вершину q0, поток из вершины q0 не превышает aqo. Поскольку Ф равно максимальному усилению среди всех путей, соединяющих начальную вершину с вершиной q0, то минимальное количество ресурса, отдаваемое оператором не менее
q0
x(m0) =
aq
q0
Далее, так как Фп/Ф^ равно максимальному усилению среди всех путей, соединяющих вершину q с конечной вершиной п, то оператор не может получить доход больше, чем
Ф
- ¦ aq .
Ф q0 q0
Окончательно получаем, что маргинальная прибыль оператора составляет
МП(т0) = Ф п ¦ x(m 0) - x(m) = (Ф п -),
^0
и эта прибыль максимальна на множестве обменных схем, включающих элемент q0. Теорема доказана.
Исключим вершину q0 и определим путь с максимальным усилением для оставшейся сети. Пусть это путь его усиление K(mi) и насыщенная вершина q1. Соответствующая маргинальная прибыль равна
МПі = Фу (K(mi) -1)
и она максимальна среди всех путей, проходящих через вершину qi и не проходящих через вершину q0. Удаляем вершину q1 и снова определяем путь с максимальным усилением в оставшейся сети, и т.д.
Процедура заканчивается, если насыщенной окажется вершина 0 или когда после удаления очередной вершины qm в сети не останется ни одного пути, соединяющего вход с выходом. Оптимальный путь по критерию маргинальной прибыли это путь щ, такой что
Насыщенная вершина q0 = 4. Величина маргинальной прибыли составит
МПо = 2(12 - 1) = 22.
2 шаг. Удаляем насыщенную вершину 4 и определяем путь с максимальным усилением в оставшейся сети (рис.4).
x(m0 = хо2 = min (3; 10A,; /2) = 2,5.
Насыщенная вершина q1 = 3, величина маргинальной прибыли
МП1 = (10 - 1)2,5 = 22,5.
3 шаг. Удаляем насыщенную вершину 3 и определяем путь с максимальным усилением в оставшейся сети (рис.5).
x(m2) = X01 = min (3; 6/u) = 3.
Насыщенная вершина q2 = 0, величина маргинальной прибыли
МП = 3(7,5 - 1) = 19,5.
Так как насыщенной оказалась входная вершина, процедура закончена. Сравнивая МП0, МП1 и МП2 видим, что оптимальным по критерию маргинальной прибыли является путь m = (0,2,3,1,5) с величиной маргинальной прибыли МП1 = 22,5.
Х0(Щ)) = Х02 = min (3, /
20/ .24 /4,
V12) = 2.
Преобразование произвольной сети к сети без контуров
Для того, чтобы применить описанный выше алгоритм к произвольной сети, необходимо преобразовать ее к сети без контуров с усилением больше
1. Однако, это достаточно сложная задача. В этом параграфе рассматривается более простая задача построения сети без контуров, такой что любому простому пути исходной сети соответствует один или несколько путей в преобразованной сети и наоборот, любому пути преобразованной сети соответствует один и только один простой путь исходной сети.
В основе алгоритма лежит процедура правильной нумерации вершин графа без контуров. Дадим описание этой процедуры.
1 шаг. Исключаем вершину 0 и все исходящие из нее дуги.
2 шаг. В полученной сети ищем вершину без заходящих дуг и исключаем ее вместе с исходящими дугами. Эта вершина получает номер 1.
Далее процедура повторяется, то есть мы снова находим вершину без заходящих дуг, присваиваем ей очередной номер, исключаем и т.д.
Очевидно, что если в сети имеются контуры, то на каком-либо шаге процедуры мы не найдем ни одной вершины без заходящих дуг. В этом случае находим все вершины из множества оставшихся, в которые заходят дуги, исходящие из уже исключенных вершин.
Рассматриваем каждую из этих вершин. Пусть, например, это вершина j. Тогда исключаем все дуги, заходящие в вершину j, и продолжаем процедуру правильной нумерации для оставшейся сети и т.д.
Пример 3. На рис. 6 приведена сеть ВО, состоящая из восьми вершин.
Если исключить вершину 0 вместе с дугами (0,1), (0,2), (0,3), то легко убедиться, что в оставшейся сети нет ни одной вершины без заходящих дуг. Поэтому рассматриваем три варианта: удаление вершины 1, вершины 2 и вершины 3, поскольку в каждую из них идет дуга из вершины 0.
Рассматриваем вершину 4 (это единственная вершина, в которую заходит дуга из исключенных вершин).
Исключаем вершину 4 с инцидентными дугами. Оставшаяся сеть опять не имеет вершин без заходящих дуг.
Рассматриваем вершины 2 и 7. Вершина 7 является конечной, и поэтому для нее процедура закончена. Исключаем вершину 2 со всеми инцидентными дугами.
Оставшаяся сеть не имеет контуров.
Окончательно ветвь с дугой (0,1) имеет вид, изображенный на рис. 7 (числа внизу указывают правильную нумерацию вершин).
2. Исключаем вершину 2 с инцидентными дугами. Получили сеть без контуров, допускающую правильную нумерацию, изображенную на рис.
8 (правильная нумерация вершины 2 равна 7, так как последний номер вершин сети на рис. 7 равен 6).
Помечаем ее номером 14 и исключаем вместе с исходящими дугами. Теперь вершина 5 не имеет заходящих дуг.
Помечаем ее номером 15 и исключаем вместе с исходящими дугами. В оставшейся сети нет ни одной вершины без заходящих дуг.
Рассматриваем две вершины, в которые заходят дуги из исключенных вершин. Это вершины 2 и 4. Рассматриваем вершину 2. Помечаем вершину 2 номером 16 и исключаем вместе с инцидентными дугами.
Оставшаяся сеть не имеет контуров. Помечаем вершины 1 и 4 соответственно номерами 17 и 18.
Рассматриваем вершину 4, помечая ее номером 19. Поскольку из вершины 4 в оставшейся сети в вершину 7 идет только один путь (точнее дуга (4,7)), то процедура закончена. Помечаем вершину 7 номером 20.
Эта сеть приведена на рис. 9.
Окончательный вид преобразованной сети приведен на рис. 10.
Число вершин сети увеличилось почти в три раза. Зато теперь мы можем применить алгоритм решения задачи, описанный в параграфе 3, который особенно эффективен для случая правильной нумерации сети.
Рассмотрим еще один пример.
Пример 4. Рассмотрим сеть, приведенную на рис. 11.
Рассмотрим дугу (0,1), помечая вершину 1 номером 1. Исключая вершину 1, помечаем вершину 2 номером 2. В оставшейся сети нет ни одной вершины без заходящих дуг. Исключая вершину 3 получаем сеть без контуров.
Наконец, рассматривая дугу (0,2)и исключая вершину 2, а затем 3, мы получаем требуемую сеть без контуров, показанную на рис.12.
Заметим, что в данном случае подсеть с дугой (0,2) можно было бы исключить, проведя дугу (0,2) в подсети с начальной дугой (0,1) (эта дуга показана пунктиром на рис. 12). При этом мы получаем преобразованную сеть с тем же числом вершин.
Однако, если бы в исходной сети была дуга (1,6) (показанная пунктиром на рис. 11), то такое преобразование уже не допустимо.
Вообще, проблема построения сети без контуров, эквивалентной исходной и имеющей минимальное число вершин является гораздо более сложной.
Оптимизация обменных схем по доходу
Выше мы рассмотрели задачу определения обменной схемы по критерию маргинальной прибыли.
Довольно часто в качестве критерия оптимальности выступает не маргинальная прибыль, а доход, получаемый оператором при реализации обменной схемы, то есть величина Д = K(m)-x(m). Например, если фирма оператор получила за свою продукцию или услуги от заказчика не деньги, а какую-либо продукцию, векселя или зачеты, то ее основная задача -реализовать уже полученный ресурс с максимальным доходом. Опишем алгоритм построения обменной схемы, оптимальной по критерию дохода.
Предполагаем, что вершины преобразованной сети ВО имеют правильную нумерацию.
0 шаг. Присваиваем входной вершине индекс uo = ao.
q-й шаг. Присваиваем вершине k индекс
uq = min
aq;n?qxuJkjq
(5.1)
(максимум, очевидно, берется по тем j, для которых существует дуга (j,q)). Индекс вершины n будет равен максимальному доходу оператора.
Для обоснования алгоритма покажем, что индекс вершины j ф n равен максимальному количеству ресурса, который можно получить от j-го элемента. Докажем этот факт по индукции.
Для выходной вершины j = 0 это очевидно. Пусть этот факт имеет место для всех вершин j q. Докажем, что это справедливо и для вершины q. Действительно, величина kjquj определяет максимальное количество ресурса, которое отдает элемент q, получив от элемента j ресурс в количестве uj, а значит выражение (5.1) определяет максимальное количество ресурса, которое может отдать элемент q, то есть существует обменная схема, в которой элемент q отдает uq единиц ресурса, и не существует обменной схемы, в которой элемент q отдает ресурса больше, чем Uq. Теперь очевидно, что максимальный доход оператора будет равен
maxUjkjn = un.
Пример 5. Рассмотрим сеть ВО, показанную на рисунке 13.
Для того, чтобы определить оптимальную обменную схему, модифицируем алгоритм обратного хода, описанный в параграфе 2 для задачи определения пути с максимальным усилением. А именно, начиная с вершины n определяем дугу (i,n), такую что
Un Uikin.
Далее находим дугу (i2,i1), такую что
maxUik-- = u; k;;
ii1 i ii1 i2 i2i1
и т.д., пока на очередном шаге k мы не получим дугу (0,ik). Путь (0,ik,ik-1, ... ,i2,i1,n) и определит искомую оптимальную обменную схему. В нашем примере
u5 = u4k45 = 48 maxuiki4 = u1k14 = 32.
i4
Следовательно, искомый оптимальный путь m0 = (0,1,4,5), поток по этому пути x0 = x01 = 3.
Учет риска
Риск является весьма существенным фактором, который следует учитывать при выборе обменной схемы. Как правило, риск обменной схемы зависит от рисков отдельных операций, входящих в схему.
Качественно риск операции является оценкой фирмой-оператором степени опасности того, что эта операция на осуществится (продукция не будет поставлена, зачет не будет произведен, курс бумаг упадет и т.д.).
Риск операции зависит от многих факторов, которые зачастую трудно оценить. Поэтому, на практике применяют дискретные шкалы для измерения риска. Наиболее принята дискретная трехоценочная шкала - низкий риск, средний риск, высокий риск.
Низкий риск, как правило, характерен для операций с уже проверенными, надежными партнерами, в достаточно стабильной (прогнозируемой) экономической ситуации (по крайней мере, на период реализации обменной схемы). Средний риск характерен для операций с новыми партнерами (но имеющими хорошую репутацию) в достаточно стабильной экономической ситуации, либо с проверенными , надежными партнерами хотя и в неустойчивой экономической ситуации.
Наконец, высокий риск характерен для операций с новыми партнерами в неустойчивой экономической ситуации.
Конечно, степень риска зависит и от применяемых механизмов перераспределения риска (страхование риска) а также от имеющихся рычагов влияния на участников сделок (гарантии государства, банков и т.д.). В первую очередь нас, безусловно, интересуют обменные схемы, включающие операции с низким риском.
Однако, если такие обменные схемы недостаточно эффективны, то имеет смысл рассмотреть более рисковые обменные схемы, включающие одну или две операции со средним риском, обращая особое внимание на среднерисковые операции и разрабатывая специальные компенсационные меры (меры снижения риска).
Наконец, допустимо включение в обменную схему операции с высоким риском, если такая схема имеет высокую эффективность. Безусловно, в этом случае высокорисковая операция особо контролируется, и обязательно прорабатывается система компенсационных мер.
Рассмотрим методы определения оптимальных обменных схем в случае, если допускаются среднерисковые и высокорисковые операции (не более одной). Если число таких операций (со средним или высоким риском) мало, то проще всего задачу решить методом перебора. А именно, включаем в сеть ВО операцию повышенного риска (среднего или высокого) и определяем оптимальную обменную схему. Затем исключаем эту операцию, включаем другую и т.д., пока не рассмотрим все операции повышенного риска.
Сравнивая полученные схемы по критерию маргинальной прибыли или дохода, определяем оптимальную схему.
При большом числе операций повышенного риска метод перебора становится достаточно трудоемким. В этом случае целесообразно разработать алгоритмы, не требующие перебора всех операций с повышенным риском.
Опишем один такой алгоритм для задачи выбора оптимальной обменной схемы по критерию дохода.
Алгоритм двойной индексации
Обозначим Uq - множество (возможно, пустое) дуг, соответствующих операциям с низким риском, заходящих в вершину q; Vq - множество (возможно, пустое) операций с повышенным риском, заходящих в вершину q.
0 шаг. Присваиваем входной вершине индекс uo = Vo = ao.
1 шаг. Если дуга (0,1) е Ui (операция с низким риском), то присваиваем вершине 1 индексы
u1 = min(a1; a0k01) и v1 = 0.
Если дуга (0,1) е Vi (операция повышенного риска), то присваиваем вершине 1 индексы
ui = 0 и vi = min(ao; aokoi).
q-й шаг. Пусть получены индексы ui, vi, i q-Присваиваем вершине q индексы
uq = min
aq; max Uikiq
q (i,q)eUq i iq
(6.1)
(6.2)
vq = min
max V:kin; max цк-
у(i,q)eUq q (i,q)eVq q j
aq;max
n-й шаг. Присваиваем вершине n индекс
max U:kin; max U:kin; max V:kin;
(i,q)eUn i in (i,q)eVn i in (i,q)eUn i in
(6.3)
un = max
Если какое-либо множество является пустым, то соответствующий максимум в (6.1) - (6.3) равен 0 по определению.
Докажем, что индекс un определяет максимальный доход фирмы-оператора среди всех обменных схем, включающих не более одной операции с повышенным риском. Как и ранее, доказательство проведем по индукции.
Предварительно введем определение i-части обменной схемы.
Определение. i-частью обменной схемы, включающей элемент i, называется начальная часть схемы, которой соответствует путь в сети ВО, соединяющий вход 0 с вершиной i.
Заметим, что для любой допустимой обменной схемы, включающей элемент i, ее i-часть может либо не иметь ни одной операции повышенного риска, либо иметь только одну такую операцию. Соответственно, i-часть, не имеющую операций повышенного риска, будем называть i-частью низкого риска, а имеющую - повышенного риска.
Докажем сначала, что индекс ui 0 (i ф n) равен количеству ресурса, такому что участвуя в любой схеме с i-частью низкого риска элемент i отдает не более ui единиц ресурса, и существует i-часть низкого риска, в которой элемент i отдает ровно Иі единиц ресурса.
