Калиткин, Карпенко, Михайлов, Тишкин, Черненков - Математические модели природы и общества - 2005 (947500), страница 36
Текст из файла (страница 36)
Были проведены расчеты с разными коэффициентами свободных средств г и резерва с?. Очевидна следующая зависимость ОНР от них: чем больше г. тем меньше величина непрохождения платежей д; при г = О она максимальна, при г = 1 обращается в нуль. Наоборот, чем больше сб тем болыпе д (поэтому энеулучшасмоеь ОНР при данном г получается при д = 0). Такая зависимость иллюстрируется левой частью табл.
13. 191 Б 4 Бинкоаские плите зги мым (не приведет к отрицательному сальдо). Расчеты других тестов показывают, что в целом поведение близко не к горизонтальной прямой, а к наклонной слева-вверх. Интересен также средний процент прохождения числа платежных поручений. Для ОНР он совпадает с процентом прохождения денежных сумм (левая часть табл. 13). Но наш алгоритм формирования пакета использует значительное количество мелких платежей для заполнения «пустот». Поэтому процент прохождения числа платежей (правая часть табл. 13) при этом сильно уменьшается по сравнению с ОНР. 4.11.
Тактика расчетов. В реальных расчетах нет коэффициента г, а заданы действительные свободные средства А„. Поэтому единственным свободным коэффициентом остается гб Можно рекомендовать следующую тактику. Производим серию расчетов с несколькими значениями гб включая 9 = 1 и о = О, например. 9 = 1,0; 0,8: 0,6; 0,4; 0,2 и О. Выберем из данной серии те варианты, когда решение со сформированными пакетами приемлемо (т. е. все сальдо неотрицательны).
Из них оставим вариант с наименьшим значением д. ОНР при 9 = 0 показывает верхнюю грань для процента прохождения платежей (д„,, = пцп). Если итоговое значение б близко к б„„ то алгоритм формирования пакета сработал хорошо. Если часто Оудут встречаться ситуации с заметью отличающимися д и д„„то алгоритм желательно усовершенствовать. Если прн каком-то д не найдено приемлемого решения, это означает, что свободные средства А„ у каких-то банков недостаточны, то есть им требуются кредиты. Кредиты. Эффективность кредитов может сильно зависеть от того, какому банку они предоставлены. В некоторых случаях кредит обслужит единственный платеж.
Тогда сумма неплатежей в системе уменьшится на величину кредита. Но если кредит инициирует длинную цепочку платежей, он особенно эффективен: уменьшение суммы неплатежей станет во много раз больше. Данная программа дает возлшжность найти места для наиболее целесообразного предоставления кредитов. Увеличим Ап некоторого банка на величину Ь.4„н вычислим соответствующее уменьшение суммы неплатежей.
Совершая это для всех банков поочередно, найдем тот банк, для которого это уменьшение максимально. Ему и следует в первую очередь предоставлять кредит. Можно разработать алгоритм нахождения наиболее целесообразной величины такого кредита, найти следующий банк для кредитования и т.д. Данный метод решения задачи клирингового расчета настолько быстр, что позволяет проделывать все эти эксперименты на компьютере за небольшое время. 192 Гл Ш Кокгггьгитерньге иетогГьг клирингиеьт риекетие Применение двойственного симплекс-метода к задаче линейного программирования может натолкнуться на сложности, если задача вырождсна.
Геометрически это означает, что одинаковые значения целевой функции достигаются более чем в одной вершине двойственного многогранника условий. В этом случае одно или несколько с, на каком- либо шаге оказываются равными нулю для иии, > О. 3 а м е ч а н и е. Так как с, изменяется на каждом шаге (37), то с, =- О возможно даже при г',"ь ф О для всех (.
Например, для си, = Аит получаем некоторые с = О уже после первого шага. Тогда в качестве разрешающего столбца берем как раз столбец с г. —. О, аии > О, так как именно на нем достигается наименьшее двойственное отношение. Легко заметить, что в этом случае значение целевой функции ( не изменяется. При этом гипотетически возможна ситуация, когда после ряда преобразований можно вернуться к уже встречавшемуся ранее набору базисных персмспггых 1В2 (значению элементов вспомогательного столбца). Таким образом, лгы сталкиваслгся с зацикливанием двойственного симплекс-лгетода. Оказывается, зацикливание можно предотвратить, если внести в симплекс-алгоритм определенные уточнения для выбора вводимых и выводимых базисных переменных 1ВУ.
Доказано, что зацикливания не возникает (то есть после конечного числа шагов либо получим ответ. что данное значение целевой функции оптимально, либо перейдем к другому значению целевой функции г', либо окажется, что задача не илгсет решения), если при выборе разрешающих строки и столбца пользоваться следующим алгоритмолк реализованным в программе 51МР(.1)1. Для упрощения программы используется предположение, справедливое для решаемой здесь прикладной задачи, что (с.) > О у == 1,...,т. 4.12. ЯЗВ$?О()Т1ХЕ ЯМРЕ1)1 (и, ш, А, Хгп, Мгпх, В, Г, 1ВХ, 1$'ьг, (гЫ). Входные данные: п, гп — размерность решаемой задачи; Хгпх, Мщх — максимально возможные размеры задачи; А(Хгпх, Мпгх) — матрица коэффициентов (а,,) неравенств; В(Хгпх) — вектор свободных членов (бь) неравенств; Г(Мгпх) — вектор коэффициентов (с ) целевой функции.
Рабочие массивы: 1ВХ(Хшх) номера расширенных переменных, являющиеся базис- ными; (оЪ'(Мгпх) номера расцгиренных переменных, являюгциеся свободными. Выходные данные: Г(Мгпх) — значения решения (л,,). 1. Подготовительная часть: проверяется, что все элементы массива Г больше О; 193 Э 4 Банковские платежи — подготавливаются массивы !ВХ и !ЯН% !ВНО) = 7, 7' = !,щ, !ВХ(!) —. ьп + Е ! — !,п. 2.
Ищем разрсиааюи!Бю строку: Если все элементы массива В положительны, то решение найдено и идем к п. 5. Если нет, то среди всех отрицательных элементов В ищем минимальный, который определяет разрешающую строку. Если минимальных несколько, то в качестве разрешающей строки берем строку с наименьшим индексом. Обозначим этот индекс как Ь~ (в терминологии симплекс-метода -- найдена разрешающая строка с номером кп). 3. Ищем разрешаюи1ий столбец по наименьшему двойственному отношению, т.е. для всех положительных элементов разрешающей с~роки (А(ьп,Я, у =.
1, т) находим отношение элементов г-строки к элементам данной разрешающей строки: (Г(1),7А(г;п,Я, 1 = 1,тп). Рассмотрим множество Со, состоящее из тех у, на которых достигается минимум соотношения (г О)7А(7гп, Я, А(агап,у) > О, у = 1, гп). 3 а м е ч а н и е. Если в разрешающей строке нет положительных элементов, то задача не имеегп решения. Если множество Со содержит более одного элемента, то составляем множество Сп В С~ входят такис у < Сп, что на них достигается минимум отношения (А(1, Я,7А(Ьи, Я, А(йп, Я ) О, ук < Со).
Если в С| входит более одного элемента, то составляем множество Сз. В Сэ входят такие 7 < С, что на них достигается минимум отношения (А(2,7),7А(йгку), А(1тВЯ > О, 7' < еС), и так далее, пока не будет получено множество См состоягцее из одного элемента. Строго доказано, что такое ! (1 < 1 < и) существует. Единственный элемент множества С, и определяет разрешающий столбец нап =- 7, у ~ <С. 4.
Элемент, стоящий на пересечении разрещаюи!их строки и столбца, называется рпзраиааюи1иж элементом — А(йп, йгп). С этим разрешаюи!иж элементом производим один шаг обыкновенных жордановых исключений: — Обмен содержимого ячеек !ВНОгт) и !ВХ(7ап) для 1ф кп, 7' фЬп для 1= оп, ф йт Вг а, = — ' , Ьаи иь ь для ! ф йп, у = 7гт пн, = —, Хьт '1 аа„л„, 7 Пол рад В Ф.
Тишкина 194 Гл Ш 1гомпьютерние.ветоши клирингиеьы рисчетое для г =. А"и,, 1 — — Лги имл ии ~ ь для защиты от неустойчивости и от ошибок округления величины (а, ) и Ц,), меньшие по модулю 1О "1', заменяем нулями. Возвращаемся к п. 2 данной программы. 5. Решение найдено: Массив (В(г), г —" 1, и) содержит решение в расширенном базисе. Массив (тВУ(1), г. = 1, п,) содержит номера расширенных переменных, являющиеся базисными. Надо выбрать только реальные переменные (л, ) с номерами, не превосходящими оь если у' =- 1ВХ(1) < гн -- ГЯ =- В(1) для остальных е Ц) — Г(,)) = 0 Включение в алгоритм дополнительных действий по формированию множеств Со, Сы..., Сг — достаточно трудоемкая процедура.
Она усложняет программу и увеличивает время расчета. Однако практические расчеты показывают, что явление зацикливания настолько редкое, что использование описанных алгоритмов вряд ли оправдано. Какую же тактику расчетов выбирать? Р е к о и е н д а ц и и. При решении задачи следует из Со выбирать минималыюе значение. то есть 1гпи — —. гттшо), Этот алгоритм был исэеыа пользован в основной программе двойственного симплекс-лгетода. Если же зацикливание все-таки возникает, то для расчетов придется воспользоваться описанным вьпце правилом преодоления зацикливания.
9 5. Оценка долгов Ниже рассмотрена проблема продажи долгов, требующая объективной оценки того, какая часть долга может быть возвращена. Сформулированы и исследованы математические постановки возникающих при этом задач. Эти подходы могут быть применены для задачи взаимозачета долгов. Построен эффективный алгоритм расчета вероятности возврата долгов, составлена программа для персонального компьютера и произведены методические расчеты с числом предприятий до б40.
Проанализированы результаты этих расчетов. Показано, что скорость алгоритма достаточна для расчета системы порядка миллиона предприятий, так что алгоритм пригоден для включения в федеральные системы. 5.1. Проблема. Продажа долгов (разумеется, со скидкой) по частным соглашениям между юридическими лицами происходит не первый год. О подобных сделках кос-что сообщала пресса. Так, во время финансового кризиса в августе 1998 г некоторые предприятия скупали за полцены долговые обязательства тех банков, которым сами были 195 9 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
