автореферат диссертации по документальной информации, 05.25.05, диссертация на тему:Разработка и исследование математических моделей повышения эффективности автоматизированных информационных банковских систем

Введение.

Глава 1. Проблемы повышения эффективности автоматизированных информационных банковских систем.

1.1. Анализ существующих подходов к автоматизации банковской деятельности.

1.2. Структура информационных потоков в коммерческом банке.ли.

1.3. Постановка задачи организации оптимальной обработки финансовой информации в АИБС.

1.4. Обзор существующих методов решения задачи минимизации времени формирования информационных массивов в АИБС.

Глава 2. Разработка и исследование различных стратегий поиска решения на дереве ветвлений.

2.1. Стратегии оптимизации поиска решения на дереве ветвлений.

2.2. Алгоритмы случайного упорядочения.

2.3. Алгоритмы, гарантирующие получение локально-оптимального решения.

2.4. Алгоритмы, гарантирующие получение глобально-оптимального решения.

Глава 3. Экспериментальное исследование разработанных алгоритмов и пакетов прикладных программ для решения задачи минимизации времени обработки информационных массивов в АИБС.

3.1. Постановка и результаты экспериментального исследования разработанных алгоритмов.

3.2. Разработка пакетов прикладных программ поиска минимальных деревьев.

3.3. Формирование выходных документов в коммерческом банке с помощью разработанных методов поиска решения.

Актуальность проблемы. Современный этап развития банковской сферы в России характеризуется очень большой динамикой изменений в банковской технологии, а также высокой конкуренцией между банками. При этом одним из важнейших инструментов конкурентной борьбы является автоматизация выполнения банковских функций. Сегодня практически все банки широко используют в своей деятельности технические и программные средства автоматизации. Более того, некоторые виды банковских продуктов могут существовать только в автоматизированном виде (например, пластиковые карточки), а большинство других могут обслуживаться вручную только теоретически, так как действующая технология и объемы производимых операций не позволяют обойтись без средств автоматизации.

В настоящее время в соответствии с законом РФ "Об информации, информатизации и защите информации", а также на основании постановлений Правительства и Центрального Банка РФ о совершенствовании информационных систем бухгалтерского учета и отчетности, в ЦБ РФ активно внедряется программа развития общероссийской информационной и телекоммуникационной системы обслуживания подразделений Центрального Банка и всех участников финансового и фондового рынков РФ.

В 1998 году произведен переход на новый план счетов и новых правил бухгалтерского учета. Все это налагает на все кредитные учреждения страны жесткие требования по совершенствованию внутренних автоматизированных информационных банковских систем, переходу на современные банковские технологии.

Автоматизированные информационные банковские системы (АИБС) являются разновидностью автоматизированных систем управления (АСУ), 5 методология которых достаточно хорошо проработана в нашей стране в 1970-1980 гг.

Развитие АИБС поставило ряд проблем, связанных с переработкой большого объема различной информации. Основной из них является проблема эффективной организации хранения, поиска и обработки данных, поскольку решение этих вопросов определяет структуру и принципы функционирования АИБС в целом.

Функционирование АИБС, как правило, бывает связано с обработкой большого числа информационных массивов (ИМ) и формированием потока выходных документов, что требует существенных затрат машинного времени.

Предложенный в работе подход заключается в использовании базы данных, основными элементами которой являются ИМ, предназначенные как для длительного, так и кратковременного хранения информации. Массивы данных, размещенные в базе данных системы для длительного хранения, централизованного их обновления и использования различными потребителями информации, называются основными. Все другие массивы, предназначенные для кратковременного хранения и использования какого-то массива каким-то конкретным потребителем информации, называются рабочими.

Благодаря тому, что содержимое различных рабочих ИМ часто пересекается, указанный выше подход к минимизации времени обработки информации можно дополнить построением такого порядка формирования ИМ, который бы сократил время их формирования за счет взаимодействия друг с другом. Иными словами, часть рабочих массивов формируется не непосредственно на основании основных ИМ, хранимых в базе данных, а с использованием ранее сформированных и "более доступных" массивов. При этом допустимо формирование промежуточных ИМ, которые не не6 обходимы для работы АИБС, но на основании которых резко сокращается время формирования рабочих массивов, необходимых для работы АИБС.

Решение этой задачи осуществлялось на базе построения минимального "частичного" дерева на взвешенном ориентированном графе, отвечающем данной задаче.

Трудности, связанные с решением этого типа задач, объясняются тем, что область допустимых значений является дискретной, а это существенно сужает возможности использования регулярных методов математического программирования, таких как линейное программирование, спуск по градиенту и т.п.

Чаще всего при решении задач оптимальной организации вычислительного процесса используются различные переборные процедуры, что обычно требует привлечения высокопроизводительной вычислительной техники. В этих условиях очевидно стремление оптимизировать организацию вычислительного процесса таким образом, чтобы иметь возможность эффективно реализовать ресурсы используемых ПК. При этом естественно воспользоваться спецификой банковских технологий, когда комплекс технических и программных средств используется для решения регулярно повторяющихся однотипных задач близкой размерности. Это позволяет накапливать информацию о топологии среды, в которой происходит поиск (дерево ветвлений), соответствующим образом адаптируя методы поиска. Так как задача оптимизации вычислительного процесса является комбинаторной, то затраты на ее решение могут превысить полученный в результате выигрыш и являются оправданными лишь в условиях АИБС, характеризующихся неоднократным решением однотипных задач.

Актуальность решения задачи повышения эффективности функционирования АИБС обусловила необходимость развития современных методов исследования операций и прикладных методов оптимизации. 7

Целью диссертации является разработка комплекса математических моделей эффективной организации вычислительного процесса и создание на их базе пакетов прикладных программ. Решение этой задачи направлено на повышение эффективности использования ПК и, в конечном счете, на рост производительности труда.

Методы исследования. При исследовании использовался аппарат теории графов, теории множеств, методы исследования операций, математической статистики.

Научная новизна работы. В результате выполненных в диссертации исследований получены следующие новые результаты:

- разработан подход, основанный на оптимизации последовательности работы с информационным массивами, позволяющий повысить эффективность программного обеспечения АИБС, связанного с обработкой большого числа информационных массивов;

- предложены математические модели, позволяющие сводить минимизацию времени обработки информационных массивов в АИБС к задачам поиска оптимальных деревьев на взвешенных графах;

- разработаны новые процедуры, базирующиеся на неявном переборе, причем каждой стратегии движения по дереву ветвлений ставятся в соответствие свои, наиболее эффективные для этой стратегии методы ветвления и вычисления оценки.

Практическая ценность работы состоит в: а) разработке подхода, позволяющего в ряде случаев повысить эффективность программного обеспечения АИБС, связанного с обработкой большого числа информационных массивов; б) создании на базе предложенного подхода пакета прикладных программ формирования выходных документов в коммерческом банке, по портфелю заказов коммерческой фирмы; 8 в) построении, обосновании и практической реализации методов типа ветвей и границ, позволяющих решать практические задачи поиска экстремальных деревьев на взвешенных графах на персональных компьютерах; г) получении экономического эффекта от внедрения пакета прикладных программ, который по предварительной оценке составляет порядка 200 тыс. руб. в год.

Апробация результатов. Основные результаты диссертационной работы докладывались и обсуждались:

- на научно-технической конференции "Социально-экономические проблемы перехода к рынку" (Ростов-на-Дону, Р-Д ИНХ, 1991 г.);

- на научно-технической конференции "Безопасность информационных технологий" (Москва, МИФИ, 1996 г.);

- на международной научной конференции "Проблемы регионального и муниципального управления" (Москва, РГГУ, 1999 г.);

- на семинарах кафедры информационно-вычислительных систем РГГУ.

По материалам диссертации опубликовано 4 печатных работы. Объем, структура работы. Диссертация состоит из введения, трех глав, списка использованной литературы и приложения, содержащего акты о внедрении результатов работы.

Заключение

В диссертационной работе получены следующие основные результаты.

1. Проведен анализ существующих подходов к автоматизации банковской деятельности. Определена взаимосвязь эффективности функционирования банковской системы и банковских технологий, а также исследована структура информационных потоков в коммерческом банке. Введено понятие информационного массива в автоматизированной информационной банковской системе.

2. Сформулирована содержательная постановка задачи повышения эффективности автоматизированных информационных банковских систем, которая заключается в минимизации времени обработки информационных массивов. Показано, что эта задача сводится к задаче поиска минимального "частичного" дерева на взвешенном орграфе, отвечающем данной задаче. В терминах теории графов разработана формальная постановка задачи.

3. Рассмотрены различные подходы к решению задачи минимизации времени формирования ИМ в АИБС, такие, как размещение массивов на внешних запоминающих устройствах, способов организации массивов, способы организации структуры массивов, системы кодирования информации. На основе анализа разработан подход, основанный „на оптимизации последовательности работы с ИМ, позволяющий повысить эффективность программного обеспечения АИБС, связанного с обработкой большого числа информационных массивов.

4. Разработаны стратегии ветвления по дереву решений в алгоритмах типа ветвей и границ. Приведено описание алгоритмов.

5. Разработаны и теоретически обоснованы новые способы вычисления оценки в алгоритмах типа ветвей и границ. Эксперимен

103 тальная проверка разработанных алгоритмов показала существенный прирост их эффективности по сравнению с традиционными.

6. Разработан пакет прикладных программ для решения задачи нахождения минимальных деревьев. В нем на основании экспериментального исследования эффективности различных алгоритмов осуществляется выбор наиболее эффективного алгоритма решения для заданной размерности задачи и времени, выделенного для ее решения.

7. Результаты внедрения пакета прикладных программ для решения задачи минимизации времени обработки информационных массивов в коммерческом банке позволили получить экономический эффект порядка 200 тыс. руб. в год.

104

1. Автоматизированные системы обработки финансово-кредитной информации: Учебник для вузов / Под ред. B.C. Рожнова. М.: Финансы и статистика, 1990.

2. Астахов А.Д. Организация кодирования в системе автоматической обработки данных//Автоматика и телемеханика. 1979. № 9. С. 168172.

3. Ахо А., Хопкрофт Дж., Ульмен Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536 с.

4. Берж К. Теория конечных графов и ее применение. М.: Иностранная литература, 1962. 319 с.

5. Блажкевич Б.И., Базилевич Р.П., Дерябина А.Г. О возможности поиска прадеревьев и деревьев графов с помощью ЦВМ // Теоретическая электротехника: Респ. межвуз. научно-техн. сб. Вып. 4. 1967. С. 3-10.

6. Бородкин A.M. Метод вторых разностей для локальной оптимизации в экстремальных комбинаторных задачах // Автоматика и телемеханика. 1976. № 10. С. 111-120.

7. Бородкин A.M., Бородкин Л.И., Турин H.H., Коган Я.А., Ляпичева Н.Г., Мучник И.Б. Оптимизация размещения информационных массивов на магнитных дисках //Автоматика и телемеханика. 1977. № 10. С. 149-158.

8. Бурков В.Н., Горгидзе И.А., Ловецкий С.Е. Прикладные задачи теории графов. Тбилиси: Мецниереба, 1974. 234 с.

9. Бурков В.Н., Троплен В.О. Разрезы в сильносвязных графах и потенциалы перестановок // Автоматика и телемеханика. 1972. № 6. С. 111-119.

10. Бурков В.Н., Клетин В.А. Минимизация времени формирования информационных массивов в автоматизированных системах управления // Автоматика и телемеханика. 1982. № 2. С. 86-91.

11. Бурков В.Н., Ловецкий С.Е. Комбинаторика и развитие техники. М.: Знание, 1979. 32 с.

12. Бурков В.Н., Рубинштейн М.И. Комбинаторное программирование. М.: Знание, 1977. 64 с.

13. Бурков В.Н., Рубинштейн М.И., Соколов В.Б. Некоторые задачи оптимального размещения информации в памяти большого объема // Автоматика и телемеханика. 1969. № 9. С. 83-91.

14. Бурков В.Н., Соколов В.Б. Оптимальное размещение информационных массивов в памяти на магнитных лентах для случая двунаправленного поиска // Автоматика и телемеханика. 1969. № 4. С. 107-117.105

15. Быков В.П., Сергиенко И.В. Один метод приближенного решения задач дискретного программирования // Кибернетика. 1978. № 3. С. 75-80.

16. Венгерова И.В., Финкельштейн Ю.Ю. Об эффективности метода ветвей и границ // Вычислительная техника в машиностроении: Сб. ст. Минск, 1973. Сентябрь. С. 18-19.

17. Волкович В.Д., Волонин А.Ф. Об одной схеме метода последовательного анализа и отсеивания вариантов // Кибернетика. 1978. № 4. С. 98-105.

18. Гаркавенко С.И., Бердникова A.C. Определение всех путей в ориентированном ациклическом графе // Кибернетика. 1979. № 4. С. 49-52.

19. Гармаш И.И., Казаков Б.С., Левитан В.Д., Фарбер М.Ш. Об одном методе организации информационных массивов в памяти прямого доступа // Автоматика и телемеханика. 1979. № 1. С. 167-183.

20. Гене Г.В., Левнер Е.В. Дискретные оптимизационные задачи и эффективные приближенные алгоритмы: обзор // Техническая кибернетика. 1979. № 6. С. 9-20.

21. Гене Г.В., Левнер Е.В. Приближенные алгоритмы для некоторых универсальных задач теории расписаний // Техническая кибернетика. 1978. № 6. С. 38-43.

22. Глушков В.Н. и др. Обработка информационных массивов в автоматизированных системах управления. Киев: Наукова думка, 1970.182 с.

23. Гроннен В.О. Задача о минимальном каркасе сети // Современные проблемы управления: Сб.ст. М.: Наука, 1974. С. 167-169.

24. Гроппен В.О. Повышение быстродействия рандомизированных алгоритмов для комбинаторных задач с булевыми переменными // Автоматика и вычислительная техника. 1978. № 5. С. 54-59.

25. Гроппен В.О. Повышение эффективности метода типа ветвей и границ для комбинаторных задач с булевыми переменными // Автоматика и телемеханика. 1978. № 5. С. 106-112.

26. Гроппен В.О. Связь задач о максимальной циркуляции и минимальном разрезе в сильно связанном графе с задачей о неоднородном потоке // Электронная техника: Научно-техническое обозрение. Серия 9. 1972. Вып. 3. С. 22-23.

27. Гроппен В.О. Экстремальные задачи на графах с минимаксным функционалом цели //Автоматика и телемеханика. 1977. № 6. С. 97102.

28. Гроппен В.О. Эффективные алгоритмы решения комбинаторных задач с булевыми переменными // Электронная техника: Научно-техническое обозрение. Серия 9. 1978. Вып. 2. С. 62-73.

29. Гроппен В.О., Дзюбко С.И., Клетин В.А., Цагараев Б.М. Планирование выпуска твердосплавной продукции в условиях106

30. АСУП // Тезисы докладов научно-технической конференции, посвященной 50-летию СКГМИ. Орджоникидзе: СОГУ, 1981. С. 164-165.

31. Джермейн К. Программирование на IBM/360. М.: Мир, 1973. 870 с.

32. Евдокимов А.Г., Завизиступ Ю.Ю., Кривуля Г.Ф., Трунов Е.В. Исследование численных алгоритмов определения дерева минимальной длины // Приборы и системы автоматики. Респ. межвед. научно-техн. сб. Вып. 15. 1971. С. 105-111.

33. Емеличев В.А. К теории дискретной оптимизации. ДАН СССР, 1971. №2 (198). С. 273-276.

34. Ермольев Ю.М., Мельник И.М. Экстремальные задачи на графах. М.: Наука, 1969. 176 с.

35. Жимерин Д.Г., Мясников В.А. Автоматизированные и автоматические системы управления. М.: Энергия, 1979. 592 с.

36. Банковские технологии: журнал. 1998. № 1-3.

37. RS-Club Журнал. 1997. № 1, 3.

38. Зыков A.A. Теория конечных графов. М.: Наука, 1969. Т.1.

39. Исследование операций. Модели и применения / Под ред. Дж. Моудера, С. Элмаграби. М.: Мир, 1981. Т. 2. 677 с.

40. Киесов В.А. Задача рационального расположения массивов информации на магнитной ленте // Кибернетика. 1968. № 4.

41. Клемышов О.Ф. Некоторые задачи о покрытии // Техническая кибернетика. 1978. № 4. С. 205-208.

42. Клетин В.А. Анализ эффективности комбинаторных алгоритмов поиска экстремальных деревьев на взвешенных орграфах // Автоматика и телемеханика, 1979. № 11. С. 134-141.

43. Клетин В.А., Мецатунян М.В., Росс Г.В. Автоматизированные информационные информационные системы в коммерческих банках.// Международная научная конференция "Проблемы регионального и муниципального управления". М. РГГУ, 1999. С.153-154.

44. Клетин В.А., Мецатунян М.В., Росс Г.В. Модели оптимальной обработки информационных массивов в человеко-машиных системах. // Международная научная конференция "Проблемы регионального и муниципального управления". М. РГГУ, 1999. С.155-156.

45. Козлова Е.П., Галанина E.H. Бухгалтерский учет в коммерческих банках. М.: Финансы и статистика, 1996.

46. Колесников В.И., Кроливецкая Л.П. Банковское дело. М.: Финансы и статистика, 1996.

47. Корбут A.A., Финкелынтейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. 368 с.

48. Кофман А., Анри-Лабордер М. Методы и модели исследования операций. Целочисленное программирование. М.: Мир, 1977. 432 с.107

49. Кофман А., Дебазей Г. Сетевые методы планирования и их применение. М.: Прогресс, 1968. 181 с.

50. Лавров С.С., Гончарова Л.И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971.

51. Литвинов В.А. К вопросу об оптимизации размещения массивов информации на магнитной ленте // Проблемы создания больших информационно-вычислительных систем: Тезисы докладов I Всесоюзной конференции. Киев, 1968. Ч. 1.

52. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981.323 с.

53. Мамиконов А.Г. Методы разработки автоматизированных систем управления. М.: Энергия, 1973. 336 с.

54. Мамиконов А.Г., Кульба В.В., Цвиркун А.Д. Модели и методы, используемые при создании автоматизированных систем управления // Автоматика и телемеханика. 1971. № 7.

55. Мамиконов А.Г., Пискурнов А.Н., Цвиркун А.Д. Модели и методы проектирования информационного обеспечения АСУ. М.: Статистика, 1978. 221 с.

56. Мартинг Д. Организация баз данных в вычислительных системах. М.: Мир, 1980. 662 с.

57. Матер Е.А., Фимина Н.Е. Оптимизация размещения массивов информации на магнитной ленте в АСУ: обзор // Кибернетика. 1971. №6. С. 130-139.

58. Мецатунян М.В. Проектирование индустриальных технологий автоматизированного управления. // Социально-экономические проблемы перехода к рынку. Ростов-на-Дону: Р-Д ИНХ, 1991. С.114-117.

59. Мецатунян М.В. Принципы организации комплексной системы безопасности коммерческого банка. // "Безопассность информационных технологий." М.: МИФИ, 1996, №2. С.85-88.

60. Мелихов А.Н. Ориентированные графы и конечные автоматы. М.: Наука, 1971. 416 с.

61. Моцкус И.Б. Многоэкстремальные задачи в проектировании. М.: Наука, 1967. 215 с.

62. Насекин В .Я. Метод решения монотонных задач целочисленного программирования//Кибернетика. 1979. № 5. С. 106-108.

63. Пискунов А.Н., Цвиркун А.Д. Оптимальная организация информационных массивов // Автоматика и телемеханика. 1972. № 2. С. 131-138.

64. Плецидевский И.А. Задачи размещения данных в информационной системе при фиксированном распределении запоминающих устройств // Проблемы создания больших информационно-вычислительных систем: Тезисы докладов I Всесоюзной конференции. Киев, 1968. Ч. 1.108

65. Рейнгольд Э., Нивергельт Ю., Део. Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 476 с.

66. Романовский И.В. Алгоритмы решения экстремальных задач. М.: Наука, 1977. С. 352.

67. Рудакова О.С. Электронные банковские услуги. М.: Финстатинформ, 1997.

68. Синки Дж. Ф. Управление финансами в коммерческих банках. Пер. с англ. 4-е изд., перераб. / Под ред. Р.Я. Левиты, Б.С. Пинскера. М.: Calallaxy, 1994.

69. Соколов Р.В. Экономико-информационное моделирование процессов преобразования информации в АСУП. JI.: Ленингр. гос. ун-т, 1980. 152 с.

70. Солянкин А.А. Компьютеризация финансового анализа и прогнозирования в банке. М.: Финстатинформ, 1998.

71. Титоренко Г.А., Суворов В.И. Компьютеризация банковской деятельности. М.: Финстатинформ, 1997.

72. Трахтенгерц Э.А. Программное обеспечение автоматизированных систем управления. М.: Статистика, 1974.

73. Фрэнк Г., Фриш И. Сети, связь и потоки. М.: Связь, 1978. 448 с.

74. Харари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. 324 с.

75. Чернявский А.П. Метод неявного перебора и его применение для решения комбинаторных задач // Проблемы расширения возможностей автоматов: Сб. ст. Вып. 1. 1971. С. 80-100.

76. Шендерев И.Б. Модификация алгоритма случайного поиска решения задач дискретного программирования // Техническая кибернетика. 1978. № 4. С. 203-205.

77. Cardenas A.F. Evaluation and Selection of File Organization // A Model and System. Communications ACM, 16, 1973, № 9, P.540-548.

78. Chen Wai-Kai. Iterative Procedure for Generating Trees and Direct Trees / Electron Letters. 1968. 4. № 23. P. 516-518.

79. Chu W.W. Optimal File Allocation in a Multicomputer Information System. Proc. IFIP Conf., North-Holland, Amsterdam, F30-F85, 1968.

80. Day R.H. On Optimal Extracting from a Multiple File Data Storage System An Application of Integer Programming Operations Res., 13, 1965, № 3., P. 482-492.

81. Gao Andrew Chi-Chin. An 0( | E | log log | V |) algorithm for finding minimum spanning trees. Inform. Process. Lett. 1975, 4, № 1, P. 21-23.

82. Jung H.A. Uber die Bestimmung minimaler Wege und Gerbste in Graphen. Computing, 1974, 13, № 3-3, P.249-252.

83. Kennedy S.R. The Use of Access Frequencies in Data Base Organization. Ph.D. Dissertation, Cornell University, 1973.

84. Nyssen G.M. Undesed Sequential Versus Random. LAG J., 4, 1, 1971 March, P. 29-37.