Главная » Просмотр файлов » Калиткин, Карпенко, Михайлов, Тишкин, Черненков - Математические модели природы и общества - 2005

Калиткин, Карпенко, Михайлов, Тишкин, Черненков - Математические модели природы и общества - 2005 (947500), страница 34

Файл №947500 Калиткин, Карпенко, Михайлов, Тишкин, Черненков - Математические модели природы и общества - 2005 (Калиткин, Карпенко, Михайлов, Тишкин, Черненков - Математические модели природы и общества - 2005) 34 страницаКалиткин, Карпенко, Михайлов, Тишкин, Черненков - Математические модели природы и общества - 2005 (947500) страница 342013-09-15СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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) Определение величин а„,„тоже неоднозначно.

Характеристики

Тип файла
DJVU-файл
Размер
5,02 Mb
Тип материала
Учебное заведение
Неизвестно

Список файлов книги

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6543
Авторов
на СтудИзбе
300
Средний доход
с одного платного файла
Обучение Подробнее