автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Системная оптимизация плановых решений

ВВЕДЕНИЕ.

ГЛАВА I. МЕТОДОЛОГИЯ СИСТЕМНОЙ ОПТИМИЗАЦИИ

ПЛАНОВЫХ РЕШЕНИЙ.

1.1. Краткая характеристика объекта исследования.

1.2. Нормативная схема деятельности ЛПР. Психологические аспекты.

1.3. Обзор основных методов оптимизации решений.

1.4. Модельное представление задач планирования.

1.5. Нормативная схема деятельности ЛПР. Формальные аспекты.

1.6. Состав интерактивных средств.

1.6.1. Основные информационные объекты.

1.6.2. Средства управления генерацией альтернативных вариантов решений.

1.6.3. Средства информационного обслуживания.

1.6.4. Средства корректировки

ВЫВОДЫ.

ГЛАВА 2. АЛГОРИТМИЧЕСКИЕ АСПЕКТЫ СИСТЕМНОЙ ОПТИМИЗАЦИИ

ПЛАНОВЫХ РЕШЕНИЙ.

2.1. Метод условной минимизации негладкой функции специального вида.

2.1.1. Обзор основных методов решения задачи.

2.1.2. Теоретические предпосылки.

2.1.3. Некоторые обобщения.

2.2. Вычислительные схемы метода условной минимизации.

2.3. Оценка качества текущего варианта плана.

2.4. Оценка качества детализированной подмодели.

2.5. Метод конструирования детализированных подмоделей.

2.6. Задачи планирования с логическими условиями в задании уровня притязаний. вывода. ЮЗ

ГЛАВА 3. ОПИСАНИЕ ИНТЕРАКТИВНЫХ СРЕДСТВ СИСТЕМНОЙ

ОПТИМИЗАЦИИ.

3.1. Краткое описание системы ДИСКОП.

3.2. Организация диалога.

3.2.1. Указания информационного обслуживания. Структура диалога.

3.2.2. Указания корректировки. Структура диалога.

3.2.3. Указания управления генерацией альтернативных вариантов плана. Структура диалога.

3.3. Структура программных компонентов.

3.3.1. Структура средств информационного обслуживания.

3.3.2. Средства корректировки.

3.3.3. Средства управления генерацией альтернативных вариантов плана.

3.4. Результаты экспериментальных исследований.

ВЫВОДЫ.

Определенные в решениях ХОТ о"езда КПСС и последующих Пленумов ЦК КПСС направления дальнейшего совершенствования планового управления народнохозяйственным комплексом предусматривают повышение роли планирования, как центрального звена в управлении экономикой, что обусловливает необходимость повышения качества планирования, его научного уровня, использования в процессе принятия плановых решений достижений научно-технического прогресса и средств автоматизации.

Современный этап развития автоматизированных систем планирования /АСЕ/ характеризуется переходом от информационных систем пакетной обработки к интерактивным системам информационно-алгоритмической поддержки процесса принятия решений. Важные аспекты создания таких систем рассмотрены в работах Н.Н.Моисеева [i.I, 1.2] , Г.С.Поспелова [l.3, 1.4] , В.Н.Буркова [ 1.5, I.б], А.А.Пер-возванского [1.7J , В.С.Михалевича [l.8, 2.2] , В.Л.Волковича [1.8, 2.2], А.А.Макарова^.9] , и др.

В настоящее время накоплен значительный опыт использования вычислительной техники в планировании и имеются необходимые технические предпосылки. Вместе с тем круг проблем, исследование которых необходимо для разработки эффективных интерактивных АСП, является достаточно обширным. Так, остаются актуальными системное разрешение противоречия между эффективностью формального многоцелевого поиска решений и размерностью математической модели, реализация алгоритмических возможностей в условиях развитых информационных представлений проблемной области.' Данные проблемы являются важнейшими при разработке эффективных АСП. Методологические основы их решения разработаны В.М.Глушковым в рамках перспективного научного направления - системная оптимизация [i.II, 2.1 - 2.4, 2.6 ] . ;

Существеиными особенностями задач планирования являются: многокритериальное^, трудная формализуемость в целом и, в то же время, наличие отдельных этапов, поддающихся алгоритмизации, высокая размерность пространства поиска, использование ШР в процессе решения различных по степени детализации информационных представлений [и, 1.3, 1.9, 1.10, 1.12, 1.13, 1.14, 2.1, 2.3, 2.4 ] . Поэтому наиболее эффективным способом применения ЭВМ в планировании является предоставление ЛПР интерактивных инструментальных средств, реализующих процессы, поддающиеся эффективной алгоритмизации [1.3, 1.15, 2.1, 2.5, 3.1 ] .

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

Необходимость исследования данных проблем возникла в ходе внедрения и эксплуатации системы ДИУСАРП [1.16, 3.1 ] .

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

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

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

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

Использование разработанных процедур повышает качество принимаемых решений за счет рационального сочетания опыта, знаний ЛПР с алгоритмическими возможностями современной вычислительной техники.

Разработанные интерактивные процедуры включены в состав общесистемных средств диалоговой системы планирования и управления для АСУ информационно-управляющего типа, работающей в режиме коллективного пользования /ДИСКОП/. разработка системы ДИСКОП выполшется в соответствии с программой ГКПТ 0.80.06 по созданию комплексов прикладных программ, средств общесистемного и функционального назначения, прогрессивных методов и средств технологии программирования и автоматизации проектирования АСУ. Реализованные процедуры в составе подсистем формирования производственной программы и маневрирования ресурсами внедрены в ВПО "Союзэлектрока-бель". Долевой экономический эффект составляет 109 тыс.руб. Кроме того, результаты настоящей работы использованы в подсистеме АСУ -"Комплектация" отраслевой АСУ электротехнической промышленности.

Исследования выполнены по плану работ Киевского политехнического института по темам: 121 "Разработка и внедрение диалоговой системы планирования и управления для АСУ информационно-управляющего типа, работающей в режиме коллективного пользования /ДМСКОП/" /Ш гос.регистрации 81027652/, 964 "Разработка диалоговой системы принятия решений в АСУ - "Комплектация" /отраслевая программа Е1882105833/.

В программной реализации интерактивных процедур помимо автора принимали участие: С.С.Жевновак, В.П.Новинский, А.Г.Юдаков.

Научный консультант - к.т.н. Вольвах А.Г.

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

На защиту выносятся следующие основные положения:

1. Методология системной оптимизации плановых решений.

2. Процедура иерархической оптимизации решений, ориентированная на диалоговый режим.

3. Монотонный алгоритм условной минимизации негладкой функции специального вида.

4. Метод конструирования детализированных представлений.

5. Оценки качества агрегированных и текущих решений.

6. Способ сведения задачи планирования с логическими условиями в задании уровня притязаний к линейной дис1фетной модели.

7. Набор интерактивных средств, реализующих предлагаемую методологию.

Основные результаты, полученные в диссертационной работе, опубликованы в работах [1.16, 2.16, 2.17, 2.18, 2.19, 2.20 ] и докладывались на:

- Всесоюзном научно-техническом семинаре "Контроль параметров технологических потоков на горных предприятиях в условиях функционирования АСУ" /г.Киев, 1981 г./;

- Пятой школе-семинаре "Интерактивные системы" /г.Кутаиси, 1983 г./;

- II Всесоюзном научно-техническом семинаре "Оптимизация технических систем" /г.Винница, 1979 г./;

- научном семинаре кафедры АСУП КПИ "Методы оптимизации и проблемы построения АСУ /г.Киев, 1982, 1983, 1984 гг./.

ВЫВОДЫ

На основе нормативной схемы деятельности ЛПР по принятию плановых решений разработаны и реализованы программно интерактивные средства системной оптимизации плановых решений, которые обеспечивают ЛПР необходимый программно-алгоритмический сервис.

Разработанные программные средства вошли в состав общесистемных средств диалоговой системы планирования и управления для АСУ информационно-управляющего типа, работающей в режиме коллективного пользования /ДИСКОД/. Средства информационного обслуживания реализованы в общесистемных средствах отображения и частично в общесистемных средствах генерации отчетов. Средства корректировки реализованы в общесистемных средствах перенастройки. Средства управления генерацией альтернативных вариантов решения реализованы в общесистемных средствах генерации плановых альтернатив.

Использование разработанных процедур повышает качество принимаемых решений за счет рационального сочетания опыта, знаний ЛПР с алгоритмическими возможностями, современной вычислительной техники.

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

Программная реализация выполнена в среде ОС ЕС ЕВМ. В качестве терминалов могут быть использованы дисплейные станции ЕС-7906 или ЕС-7920.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

Построенную процедуру иерархической оптимизации целесообразно использовать также и для решения задач линейного программирования большой размерности.

На основе построенной нормативной схемы деятельности ЛПР по принятию планового решения разработаны интерактивные средства ее поддержки, которые обеспечивают ЛПР необходимый программно-алгоритмический сервис. Построенные средства образуют три класса:

- средства информационного обслуживания, которые предоставляют ЛПР произвольную информацию в пределах модельного представления;

- средства корректировки, позволяющие ЛПР модифицировать параметры моделей;

- средства управления генерацией альтернативных вариантов решения на основе иерархической системы моделей.

Интерактивные средства включены в состав общеактемных средств диалоговой системы планирования и управления для АСУ информационно-управляющего типа, работающей в режиме коллективного пользования /ДИСКЩ/. разработка системы ДИСКОП выполняется в соответствии с программой ГКНТ СССР 0.80.06 по созданию комплексов прикладных программ, средств общесистемного и функционального назначения.

Реализованные процедуры в составе подсистем формирования производственной программы и маневрирования ресурсами внедрены в ВПО "Союзэлектрокабель". Долевой экономический эффект составляет 109 тыс.руб.

Кроме того, результаты настоящей работы использованы в подсистеме АСУ - "Комплектация" отраслевой АСУ электротехнической промышленности.

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

1. Современное состояние теории исследования операций.

2. Под ред. Н.Н.Моисеева. М.: Наука, 1979. - 464 с.

3. Моисеев H.H., Иванилов Ю.П., Столяров Е.М. Методы оптимизации. М.: Наука, 1978. - 352 о.

4. Проблемы программно-целевого планирования и управления.

5. Под ред.Г.С.Поспелова. М.: Наука, I98I.-464 с.

6. Поспелов Г.С., йринов В.А. Программно-целевое планирование и управление /Введение / М.: Советское радио, 1976.440 с.

7. Бурков В.Н., Кондратьев В.В. Механизмы функционирования организационных систем. - М.: Наука, 1981. - 384 с.

8. Бурков В.Н. Основы математической теории активных систем. М., Наука, 1977. 256 с.

9. Первозванский A.A. , Гайцгори В.Г. Декомпозиция, агрегирование и приближенная оптимизация. М.: Наука, 1979. -344 с.

10. Михалевич B.C., Волкович В.Л. Вычислительные методы исследования и проектирования сложных систем М.: Наука, 1982.288 с.

11. Методы и модели согласования иерархических решений.' /Под ред. А.А.Макарова. Новосибирск: Наука, 1979. - 240 с.

12. Итеративное агрегирование и его применение в планировании. /Под ред.Л.М.Дудкина. М.: Экономика, 1979. - 328 с.

13. Глушков В.М. Макроэкономические модели и принципы построения ОГАС. М.: Статистика, 1975. - 160 с.

14. Козелецкий Ю. Психологическая теория решений. М.: Прогресс, 1979. - 504 с.

15. Ларичев О.И. Наука и искусство принятия решений. -М.: Наука. 1979. 200 с.

16. Дрейфус X. Чего не могут вычислительные машины. Критика искусственного разума. М.: Прогресс, 1978. - 344 с.

17. Ефимов Е.И. Решатели интеллектуальных задач. М.: Наука, 1982. - 320 с.

18. Цурков В.И. Декомпозиция в задачах большой размерности. М.: Наука, 1981. - 352 с.

19. Вилкас Э.Й., Майминас Е.З. Решения: теория, информация, моделирование. М.: Радио и связь, 1981. - 328 с.

20. Орфеев Ю.В,,Тюхтин B.C. Мышление человека и "искусственный интеллект". М.: Мысль, 1978. - 150 с.

21. Экономико-математические модели в системе управления предприятиями.

22. Под ред.Н.П.Федоренко и И.П.Шубкиной. М.: Наука, 1983.- 390 с.

23. Поспелов Д.А., Пушкин В.Н. Мышление и автоматы. М.: Советское радио, 1972. 224 с.

24. Ботвинник М.М. 0 решении неточных переборных задач. М.: Советское радио, 1979. 152 с.

25. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: Наука, 1980. 208 с.

26. Смолян Г.Л. Человек и компьютер. М.: Политиздат, 1981. - 192 с.

27. Холл А. Опыт методологии для системотехники. М.: Советское радио, 1975. - 448 с.

28. Шрейдер Ю.А. Равенство, сходство, порядок. -М.: Наука, 1971. 254 с.

29. Кини Р.Л., Райфа X. Принятие решений при многих критериях. Предпочтения и замещения. М.: Радио и связь, 1981.560 с.

30. Акофф Р.Л. Планирование в больших экономических системах. М.: Советское радио, 1972. - 224 с.

31. Шрейдер Ю.А., Шарев A.A. Системы и модели. М.: Ради о связь, 1982. - 152 с.

32. Иванилов Ю.П., Лотов A.B. Математические модели в экономике. М.: Наука, 1979, - 304 с.

33. Павлов A.A. Линейные модели в нелинейных системах управления. Киев: Техника, 1982. - 167 с.

34. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983. - 384 с.

35. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979. - 200 с.

36. Демьянов В.Ф., Васильев Л.В. Недифференцируемая оптимизация. М.: Наука, 1981. - 384 с.

37. Вагнер Г. Основы исследования операций, т.2, М.: Мир, 1973. 488 с.

38. Габасов Р., Кириллова Ф.М. Минск: Изд-во Белорусского государственного университета им.Ленина, ч.1, 1977.

39. Голыптейн Г., Юдин Д.Б. Новые направления в линейном программировании. М.: Советское радио, 1966. - 420 с.

40. Дикин И.И., Зоркальцев В.И. Итеративное решение задач математического программирования /алгоритмы метода внутренних точе^. Новосибирск: Наука, 1980. - 144 с.2. Статьи.

41. Глушков В.M. О системной оптимизации. Кибернетика, 1980, № 5, с.89-90.

42. Глушков В.М., Михалевич B.C., Волкович В.Л., Даленко Г.А. Системная оптимизация в многокритериальных задачах линейного программирования при интервальном задании предпочтений. -Кибернетика, 1983, № 3, с.1-8.

43. Глушков В.М. Вопросы оптимизации в АСУ. В сб. : Вопросы радиоэлектроники, серия автоматизированные системы управления, 1980, вып.З, с.5-28.

44. Глушков В.М. ДИСПЛАН новая технология планирования. -Управляющие системы и машины, 1980, № б, с.5-10.

45. Ларичев О.И., Поляков O.A. Человеко-машинные процедуры решения многокритериальных задач математического программирования /Обзор/. Экономика и математические методы, 1980, т.ХУ1, № I, с.129-145.

46. Глушков В.М. О диалоговом методе решения оптимизационных. Кибернетика, 1975, të 4.

47. Горлин Ю.М., Лившиц В.H. Системный анализ качества планирования деятельности сложных производственных комплексов. -В ich. : Социальные исследования. Методологические проблемы. Ежегодник, М.: Наука, 1981, с.60-86.

48. Вен В.Л. Агрегирование линейных моделей. /Обзор методов/. Известия АН СССР, серия техническая кибернетика, 1974, }Ь 2, с.

49. Леонтьев А.Н. Автоматизация и человек. В сб."Психологические исследования", М., Наука, вып.2, с.4-15.

50. Хагиян Л.Г. О скорости сходимости игровых процессов решения матричных игр. Журнал вычислительной математики иматематической физики, 1977, т.ХУЛ, № 6, с.131-142.

51. Хагиян Л.Г., Эрлих А.И. Серийные игровые процессы решения: задач выпуклого программирования. Известия АН СССР, техническая кибернетика, 1978, № 2, с.86-92.

52. Волкович В.Л., Волошин А.Ф. Об одной общей схеме последовательного анализа и отсеивания вариантов. Кибернетика,1978, № 5, с.98-105.

53. Руа Б. К общей методологии выработки и принятия решений. В сб. "Статистические модели и многокритериальные задачи принятия решений. М., Статистика, 1979, с.123-167.

54. Тихомиров O.K., Бе лавина И.Г. Интеллектуальная деятельность в условиях "диалога" с ЭВМ. В кн.: Интеллект человека и программы ЭВМ. М., Наука, 1979, с.11-44.

55. Рубахин В.Ф. "Искусственный интеллект" и принятие решений. В кн.: Интеллект человека и программы ЭВМ. М., Наука,1979, с.214-219.

56. Павлов A.A., Вольвах А.Г., Рудич С.Ф. О принципах построения диалоговых иерархических систем принятия плановых решений. В сб. "Кибернетика и вычислительная техника", Киев, 1982, вып.57, с.3-7.

57. Вольвах А.Г., Рудич С.Ф., Краков А.Г. Об иерархической модели задачи планирования. Вестник Киевского политехнического института, серия техническая кибернетика, Киев, 1982,6, с.26-29.

58. Рудич С.Ф. О проблеме согласования решений в системах с иерархической организацией. В сб. "Контроль параметров технологических потоков на горных предприятиях в условиях функционирования АСУ". М., ВДИИТЭИприборостроения, 1981, вып.З, с.77.

59. Павлов A.A., Вольвах А.Г., Рудич С.Ф., Юдаков А.Г.

60. О принятии решений коллективом ЛПР. Материалы пятой школы-семинара "Интерактивные системы", Тбилиси, Мецниереба, 1983, с.257-258.

61. Медницкий В.Г. Об оптимальности агрегирования в блочной задаче линейного программирования. В сб. "Математические методы решения экономических задач", М., Наука, вып.З, с.51-63.

62. Цурков В.й. Метод декомпозиции на основе агрегирования в блочном программировании. Журнал вычислительной математики математической физики, 1979, т. 19, №2, с.83-96.

63. Цурков В.И. Агрегирование в задаче отраслевого планирования. Экономика и математические методы, 1980, т.Ш, ¡Ь 3,с.135-141.

64. Вахутинский И.Я., Дудкин Л.Н., ¡Ценников Б.А. Итеративное агрегирование в некоторых оптимальных экономических моделях. Экономика и математические методы, 1973, т.IX, $ 3, с.121-129.

65. Герасимов H.A., Яковлев А.И. Управление структурной диалога в условиях неопределенности характеристик пользования.-Управляющие системы и машины, 1982, JS I, с.46-52.

66. Фишберн П., Кини Р. Обобщенная независимость по полезности и некоторые смежные вопросы. В кн.: Статистические модели и многокритериальные задачи принятия решений. М.: Статистика, 1979, с.45-62.3.Диссертации.

67. Вольвах А.Г. Исследование и разработка алгоритмического обеспечения задач планирования в АСУ. ДИС. канд.технических наук. - Киев, 1980. - 167 с.