Калиткин, Карпенко, Михайлов, Тишкин, Черненков - Математические модели природы и общества - 2005 (947500), страница 34
Текст из файла (страница 34)
(27) ье М 2 В„(Х) =- 2' А„. П, —.! е .=л Сравнивая с (3), получаем необходимое условие суцгествования ДНР: ~б А„) ~в Сп. (29а) е=! и=ч Достаточным условием существования ДНР является А„) С„для всех и. (29б) Если оно выполнено, то сугцествует по крайней мере тривиальное ДНР .с„,„ .:. ! (его смысл " ни один платеж не произведен).
Однако использование (29б) неудобно, так как конечные лимиты С„ ограничены начальными активами А„, которые для ехороших» банков с положительным сальдо невелики. С другой стороны, можно подобрать такие тестовые примеры, в которых условие (29а) не является достаточным для существования ДНР. Вопрос о необходимом и достаточном условии существования ДНР труден для решения. Однако на практике при большом Х и большом суммарном обороте системы решение при выполнении (29а) удастся найти. Введем величины сальдо банков при условии полного прохождения всех платежей (л„„, = 0): В, шВа(Х=О) =Ап+ 2 (А, „— А„,„). (30) Очевидно, если для всех и, выполняется условие В„ > С„ при 1 < и < Г, (3! ) Любая матрица, удовлетворяющая неравенствам (2б), (27), является решением в непрерывных переменных.
Будем называть его допустияыи непрерыенььн ре1иением (ДНР). При суммировании (25) по и все платежи банков взаимно сокращаются так что !82 Ел Ш Копгггыопгирные метода! клирингиеых риспйтои то х .,„:= 0 является ДНР. Такое решение можно считать идеальным (все платежи прошли). Нетрудно видеть, что (31) является необходимым и достаточным условием существования идеального решения.
Если условие (31) не выполнено, а (29) выполнено, то существует бесконечно много ДНР. Тогда можно ставить вопрос о нахождении оптимального (в каком-то смысле) решения. 4.5. Опимальное решение. ДНР, минимизирующее линейную целевую функцию в пр Д(г) = 2 2 гпп ! пт ' !гцг! спт (32) и.— ! т.—.! будем считать оптимильным непрерывным решением (ОНР). Очевидно, задача на минимум (32) при линейных ограничениях (26), (27) есть задача линейного программирования. В общем случае ОНР может быть не единственным достигаться на ребре или грани выпуклого многогранника условий. Даже если оно единственно, т. е.
достигается в вершине, возможна ситуапия, когда выходягцие из этой вер!пины ребро или грань окажутся почти параллельными плоскостям Л(х) = сонат. Тогда ОНР будет плохо обусловленным, и небольшие вариации величин спт. А„, А„или даже ошибки округления при вычислениях могут заметно изменить ре!пение (в частности, вызвать переброс решения на соседнюю вершину). Заметим, что если условие (29) является точным равенством, то ошибки округления могут превратить его в неравенство обратного знака, когда ДНР отсутствует.
Поэтому в алгоритм всегда нужно вводить неболыпую страховку от ошибок округления. Коэффициенты с„„, можно задать из разных соображений. Рассмотрим два случая, которые можно считать противоположными крайностями. В первом полагаем спт = Апт. (33) Такой выбор соответствует минимизации денежной суммы непрошедших платежей. На первый взгляд это требование разумно. Однако, при этом фактически предпочтение отдается крупным платежам. Может быть пеликом оторошен пакет из многих мелких платежных поручений ради некоторого увеличения процента прохождения большого пакета. Нелевую функцию.
соответствующую (33), обозначим Л,!(и!), а соответствующее ОНР через Хл. Противоположная крайность — выбор одинаковых весов. Без ограничения общности можно положить (34) с„= 1, п ф и!. Это означает равноправие малых и больших пакетов, минимизируется суммарный процент непрохождения платежей во всех пакетах. Такой выбор должен больше устраивать многочисленных некрупных клиентов 4 4 Банковские плитежи банков. Соответствующую целевую функцию и ОНР обозначим через Вп(х) и Хы.
Сравнение весов (33) и (34) проводилось на численных приме- рах, описанных далее в и. 10. О!ю показало, что алгоритм нахождения ОНР двойственным симплекс-методом очень устойчив при весах (34), а при весах (33) могут возникать осложнения. Более детальный анализ показал, что веса (33) приводят к параллельности некоторых ребер двойственного многогранника условий и плоскости целевой функции.
Если процесс приведет на такое ребро, то алгоритм иногда сбивается (на практике это встречается чрезвычайно редко). В принципе, небольшие изменения весов по сравнению с (33) долж- ны ликвидировать такое вырождения. Однако, это делать нецелесо- образно. Оказалось, что хотя Вп(Хп) > Б,г(Хл). но это превышение незначительно. Поэтому лучше использовать веса (11) и находить решение Хс, при этом алгоритм устойчив, целевая функпия Вы(х) точно минимизируется, а целевая функция Вл(х) близка к своему минимуму.
Рекомендапня: вести расчеты только с с, =" 1. 4.6. Задача линейного программирования (ЗЛП). Очевидно, именно такова задача минимизапии линейной функции (32) при линей- ных ограничениях (26), (27). Эта задача содержит Х(тХ вЂ” 1) неизвест- ных х„„„1 < и, т < Х, и ф и!. Переменные х„„вообще не вводятся. Если какой-то пакет платежей отсутствует, т. е. его А„„, .= О, то со- ответствующую переменную х „, можно, в принципе, также исключить нз расчета. Однако это заметно усложняет логику алгоритма. Выгоднее оказалос~ полагать в этом случае х„„.=. О, записывая это условие в виде неравенства 0 < х„.- О.
После этого исходная задача переписывается следующим образом: ге и, Цз!) '=' 2' 'т с„„„х„„, = шш, с„„, > 0 (обычно с„ы эь 1), (35а) и —.-! и —..! 2 (А„„,хн„, — А,„„х„н,) + („— Ов) > О, 1 < и < Х, (356) т —.- ! — х„+1>0 при А„„фО, 1<п,, и!<Х, мфги, (35в) -х„,в>0 при А„„,=-О, 1(н, гп(Х, пфт, (35г) — х„„,>0, 1<а, т Х, пфт, (35д) где В = В,„(Х вЂ” — 0) г. х(„ч- 2 (А„,„— А„„„), 1 < и < Х. (35е) еа —.— ! Это классическая неканоническая форма записи задачи линейного программирования. Неравенства (35д) выделяют первый координатный угол, а неравенства (356) — (35г) описывают многогранник ограничений.
184 !"л йу Колггьютерныо мотодь! клиринговых росчетов Замечание. Пусть для некоторого и выполняется А„т —. Л „—. О для всех ьм Это означает, что и;й банк ничего не посылает и ничего не получает. Задача (35) при этом вырождается, и п-й банк необходимо явно исключить из всех расчетов. 4.7. Двойственный симплекс-метод. Для решения задачи линейного программирования (ЗЛП), заданной в симметричной форме записи с!х! +саха ч-... +с:г = шш, о!!х+ о!з! + ° ч о!т ггь + (ь! > О г!,!х+ ожх+ ... + а„„х,„+ Ь! > О, (Зб) о„!.т, -1- аиэх + ... + оь„,хго + бь > О, х: >О, ! —. 1,...,ш используется двойственный симплекс метод.
Причем, для упрощения алгоритма используется условие, всегда выполняемое в данной прикладной задаче: (с ) > О при всех уг = 1,...,пн Построим так называемую в линейном программировании симплексную таблицу. Первыми располагаются !и столбпов из коэффициентов неравенств (ам, ! = 1, ..., и). Под ними строка С из коэффициентов целевой функпии (с„ц! = 1,..., и).
Справа столбец В из элементов (Ьб ! —. 1, ..., п). Слева и сверху — вспомогательные столбец и строка, содержащие только целые положительные числа. Первоначально во вспомогательную строку заносятся упорядоченные числа от 1 до гп, а во вспомогательный столбец числа от ш+! до ш + и,. Такое первоначальное заполнение соответствует условию х =- О для всех 1. Затем к симплекспой таблице применяют процедуру, называемую «жордапово исключениеь, до тех пор пока столбеп В нс будет содержать только неотрицательные элементы.
В последнем случае решение считается найденным и определяется следующим образом: в начале всем х присваивается нулевое значение; затем просматривается вспомогательный столбец; пусть значение его г-го элемента равно й и не превосходит гп; тогда хв присваивается значение !что элемента столбца В. Рассмотрим более подробно алгоритм применения жорданового исключения. Если все элементы столбца В оказались неотрицательными, то, как уже было сказано выше, решение найдено.
Если есть отрицательные, то ищем среди них минимальный. Обозначим его индекс как йп (в терминологии симплекс-метода найдена разрешающая строка с номером йп в симплексной таблице). 185 8 4 Банковские платежи Если в разрешающей строке нет положительных элементов, то задача не имееп решения. Затем из положительных элементов разрешающей строки выбираем элемент по наименьшему двойственному отноплению, т.е. отношению соответствующих элементов строки С и найденной разрешаю!цсй строки (с /ая„а).
Обозначим его индекс как Ьп (в терминологии симплекс- метода наиден разрешающий столбец с номером Ьпл). Элемент ая„в,в, стоян!ий на пересечении разрвшаюи1их строки и столбца, называется разрешаю!!!им элементом. С этим разрешаю!мин элементом делается один п!аг обыкновенных жордановых исключений: -. меняем местами 1пмй элемент вспомогательного столбца и 1ггп-й элемент вспомогательной строки.
— выполняем преобразование элементов симплексной таблицы по следующим формулам: для ! -р йп, ! ф йгп ал..л ал„л а,;„,,ы для ! = 1гп, у 7': йтгл 3 аы, л„, ал ~йп (37) для ! ф 1тгл, 1' = Атп гл вы = анталл.йп оьл = ал я для г = 1ггц уг = йлп ! алият = % ьт При этих преобразованиях для защиты от неустойчивости и от ошибок округления величины (а, ) и (с ), меньшие по модулю 10 !", заменяются нулями. На этом процедура однократного применения эжорданового исключениял закончена. 4.8.
Резерв. Рассмотрим, зачем и как вводятся С„. По банковским правилам решение Х допустимо, если сальдо всех банков неотрицательпы Ва(Х) > О. Однако, расчет в непрерывных переменных дает доли и„,„, которые (если они не равны 0 или 1) не могут, вообще говоря, быть точно представлены в виде суммы каких-то платежных поручений из данного пакета.
Поэтому на втором этапе алгоритма приходится формировать пакет, то есть находить какие-то наборы а,„„,л, г суммами, возможно более близкими к А„„„,ю„. Эти суммы могут быть болыпс или меныпе искомых величин; соответственно изменяются В„(Х), причем в любую сторону. Если первоначально было удовлетворено ограничение В„(Х) ) О, 186 Вл йУ Компьютерные методы клирингоеых рисчетое г гг 11г'я т —..1 (38) Определение величин а„,„тоже неоднозначно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
