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

■ ^

о"

О -

¿О ^ - На правах рукописи

<5^ Ч» -

КУЗНЕЦОВ Александр Сергеевич

РАЗВИТИЕ ТЕОРЕТИЧЕСКИХ ОСНОВ ГИБКИХ АВТОМАТИЗИРОВАННЫХ ТЕХНОЛОГИЙ АНАЛИЗА СЛОЕНЫХ ПРОИЗВОДСТВЕННЫХ СИТУАЦИЙ (с припааеннями в горней! дела)

Специальности 05.' 13.16" - Применение вычислительной техники, з иоделирования и катедат в научных исследованиях

математического иоделирования и математических методов

Автореферат диссертации на соискание ученой степени доктора технических наук

*

Новосибирск - 1998

На правах рукописи

КУЗНЕЦОВ Александр Сергеевич

РАЗВИТИЕ ТЕОРЕТИЧЕСКИХ ОСНОВ ГИБКИХ АВТОМАТИЗИРОВАННЫХ ТЕХНОЛОГИЙ АНАЛИЗА СШВНЫХ ПР0ЙЗВ0ЖГГВЕНШХ СИТУАЦИЙ (с прилагёншши в горнем деле)

Специальность 05,13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Автореферат диссертации иа соискание ученой степени доктора технических наук

Новосибирск - 1998

Работа выполнена в Институте горного дела Сибирского отделения Российской Академии наук.

Официальные оппоненты-. д.ф.-м.н., проф.

Дементьев Владимир Тихонович,

д.т.н., проф.

Резниченко Семен Саулович,

■у

Д.Т.Н.. проф.

Бахтин Анатолий Егорович.

Ведущая организация - Институт проблем комплексного освоения недр РАН.

Защита состоятся 7 апреля 1998 г. в 16 часов на заседани диссертационного совета Д 063.98.01 при Новосибирском ГЬсудар ственном университете по адресу:

630090, г. Новосибирск-90, уд. Шрогова, 2, ауд. 317а.

С диссертацией можно ознакомиться в библиотеке НГУ.

Автореферат разослан 6 марта 1998 г.

Ученый секретарь П/

I. к.т.н. Ю.И.Ереш

диссертационного совета,

ОШАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Исследования выполнялись по программе "Сибирь", основная рема 3.2.1.5 (номер гос. регистрации 01860079149): "Развитие >аучных основ эффективных технологий разработки месторождений ■вердых полезных ископаемых в условиях больших глубин", разде-1Ы: "Разработка методического и математического обеспечения дя расчета и оценки параметров технологий добычи твердых по-¡езных ископаемых", "Разработка методов и средств совершенст-ования рудничной вентиляции", "Разработка математических ма-елей, алгоритмов и прикладных программ для решения задач ста-дартизации горных машин". Хоздоговорные работы: N 252-82 "Ра-работка математического обеспечения для решения на ЭВМ задач

оптимального воздухораспределения в вентиляционных сетях шахт и рудников*. N 83-82 "Разработка математичеасого обеспечения для анализа технологических схем ведения горных работ на разрезе "Березовский", N 537-39 "Оптимизация параметрического ряда буровых роботизированных комплексов и комплектов технологического инструмента" и другие.

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

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

Задачи исследований:

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

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

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

- исследование различных методов и алгоритмов с целью оценки их эффективности, проведение численных экспериментов;

- разработка математического обеспечения для решения ряда задач производственно-транспортного типа;

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

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

лирование, а также имитационное моделирование процессов составления и реализации планов.

Основные шучиьгэ результаты, завиваемые авторов:

- концепция создания гибких информационных технологий организации производства с применением персональных информационно-аналитических систем и принципы, на которых основывается построение подобных систем;

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

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

- метод решения специальных дискретных экстремальных задач большой размерности;

- модели и алгоритмы решения рассмотренных задач выбора.

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

Личный склад автора:

- осуществлена постановка ряда задач, возникающих на разных стадиях организации горнодобыващего производства (формирование парка, расстановка и замена оборудования, оценка его производительности, оптимизация режимов работы и резервов производства), а также при обосновании параметров горных машин (стадии НИР и ОКР) и планировании их выпуска, при этом найдены эффективные математические модели и алгоритмы, способствуииие принятию обоснованных решений;

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

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

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

- выполнены анализ и оценка алгоритмов типа неявного перебора вариантов в зависимости от радиуса, глубины и схемы поиска в условиях ограниченного времени;

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

Научная новизна результатов:

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

- найдены эффективные стратегии поиска, схемы организации диалога с ЭВМ в процессе неявного перебора вариантов;

- показана возможность использования идеи метода сокращения невязок (беспорядка) Форда-Фалкерсона для исследования в диалоге с ЭВМ области Парето-оптямальных решений;

- получены и сформулированы необходимые, а в ряде случаев достаточные условия оптимальности решений рассмотренных задач;

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

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

- выполненные исследования характеризуются учетом динами-

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

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

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

- обоснование типоразмерных рядов горных машин (шахтные вентиляторы, роботизированные буровые комплексы, ручные перфораторы, компоновочные схемы главных вентиляторных установок);

- выбор параметров транспортно-технологаческих схем, системы разработки и режимов работы основного горно-транспортного оборудования в условиях разреза "Березовский" (КАТЖ);

- обоснование номенклатуры и объемов выпуска рядовых, сортовых и марочных углей (при существенных начальных затратах).

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

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

Реализация работы. Разработанное математическое обеспечение в виде моделей, алгоритмов, методик, сложных оптимизационных процедур и другой программной продукции передано в различные лаборатории ИГД СО РАН и использовалось для проведения совместных исследований, связанных с обоснованием типоразмерного

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

Результаты исследований вошли в ГОСТ 25988-83 "Перфораторы ручные электромагнитные", в "Руководящий технический материал по выбору вентиляторов главного проветривания", утвержденный Минуглепроыоы СССР (РТМ 07.03.003-87). Программное и методическое обеспечение по оптимальному регулированию шахтных вентиляторных установок передано в Высший горно-геологический институт (Болгария), включено в подсистему "Вентиляция" САПР-"Уголь". Программная система для расчета оптимальных совместных режимов работы шахтных вентиляторов и моделирования воздухораспределения в сети горных выработок передана в ЦНИЛ ВГСЧ Урала, в институты Сибгипрошахт и ПромНИИпроект. Результаты исследований по совершенствованию типоразыерного ряда шахтных вентиляторов и параметров главных вентиляторных установок переданы в Донгипроуглемаш, ВНИИГМ им. М.М.Федорова и НПО Уралгормаш. Программная система и методические рекомендации по обоснованию номенклатуры и объемов выпуска сортовых и марочных углей, разработанные совместно с институтом КАТТЖНИИуголь, переданы в компанию "Росуголь". Система автоматизированного формирования транспортно-технологических схем ведения горных работ и динамики карьерного пространства передана на разрез "Бе-резовский-1", где она прошла производственные испытания.

Основные результаты и опыт по автоматизации исследований, организации диалога с ЭВМ представлены в монографии.

Апробация результатов. Научные результаты и положения работы докладывались на межведомственных и Всесоюзных семинарах и совещаниях по управлению вентиляцией и газодинамическими явлениями в шахтах (Новосибирск, 1976, 1979, 1981, 1987, Лени-набад, 1988), научно-практической конференции выпускников НГУ (Новосибирск, 1977), Всесоюзных конференциях: по проблемам теоретической кибернетики (Новосибирск, 1977, 1980), аэрологии современных горнодобывающих предприятий (Москва, 1980), по во-

просаы совершенствования и оптимизации горных работ (Новосибирск, 1985, 1989), развита» производительных сил Сибири и задача« ускорения научно-технического прогресса (Новосибирск, 1985), развита» стационарных установок угольных шахт (Донецк, 1983), областной научно-технической конференции по вычислительной технике и системному анализу (Новосибирск, 1980), Сибирском Конгрессе по прикладной и индустриальной математике (Новосибирск , 1996), Международной Симпозиуме по применению компьютеров и исследованию операций в горной промышленности -АРСШ-97 (Москва, 1997), на семинарах в Институтах: математики СО РАН (Новосибирск, 197В-1988, 1997), геотехнической механики (Днепропетровск, 1981), Донгнпроуглемаш (Донецк, 1991), Высшем горно-геологическом институте (Ccxjaa, 1982), Вычислительном центре СО РАН (Новосибирск. 1983, 1997) и других организациях.

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Созданию научных основ рационального, безопасного природопользования, критериев и иетодов оценки его эффективности посвяаены труды А.Г. Аганбегяна, М.И. Агошкова, A.C. Астахова,

A.Г.Гринберга, Л.В. Канторовича, М.В. Курлени, Н.В.Мельникова,

B.В. Ржевского, К.Н. Трубецкого, Е.И.Шемякина и других ученых.

Современное горнодобываидее (или просто горное) предприя-

гне - шахта, карьер, рудник - представляет собой сложную сис-гему с множеством подсистем и внутренних процессов, связанных г добычей полезных ископаемых. Особенности горного пронзводс-гва - его высокая опасность для человека и окружающей природной среды, динамичность (подвижность действующих объектов -забоев, фронта работ, рабочей зоны, сети выработок), убывание i невосполнимость извлекаемых ресурсов, ограниченность срока службы предприятия, жизненно важная взаимосвязь различных провесов и высокая неопределенность параметров среды в будущем. Зоследнее связано с принципиальной невозможностью получения

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

Математическое моделирование - основной, а зачастую единственный метод исследования сложных управляемых систем с целью выбора способов эффективной организации их жизнедеятельности. Совешенствованию планирования, организации горнодобывающего производства (с помощью математических методов и вычислительной техники), вопросам повышения эффективности горно-шахтного оборудования, выбора и обоснования параметров горного предприятия и его элементов посвящены работы В.М. Аленичева, А.И. Арсентьева. А.С.Бурчакова, В.Н.Вылегжанина, Э.И.ГЪйзмана, Г.П. Данилиной, Н.В.Дронова, д.р. Каплунова, Ю.Е.Капутмна, С.С.Кво-на, A.M. Курносова, А.И. Митейко, A.A. Ордина, С.И. Петровича, А.А.Пешкова, В.Я. Потемкина, Э.И. Реентовича, С.С. Реэниченко, Е.И.Рогова, А.В.Старикова, Г.А.Стрекачинского, И.Б. Табакмана,

A.C. Танайно, М.И.Устинова, Е.В.Фрейлиной, В.А. Харченко, B.C. Хохрякова. С.Цоя, других ученых. Обзор зарубежного опыта и современного состояния в области компьютеризации, численного моделирования процессов горного производства приводится в работах й.П.Астафьева, А.С.Зеленского, В.Л.Барона, А.Л.Крыловского.

Полученные результаты имеют большую научную и практическую значимость. Однако, современная действительность ставит множество новых нерешенных задач. Анализ работ позволяет выделить ряд проблем горного производства, машиностроения, каждая из которых связана с так называемой проблемой выбора. Существенный вклад в развитие теории, методов выбора или принятия решений внесли многие ученые. Среди них О.Г.Алексеев, К.А.Баг-риновс-кий, А.Е. Бахтин, Д.С. Беляев. В.Л.Береснев. Э.Х.Пшади, Н.И. Глебов, Е.Г. Гольштейн, D.H. Гордеев, В.Т.Дементьев, Е.А. .Щаниц, А.В.Карзанов, Н.Ю.Кузнецрв, О.И. Ларичев, С.С. Лебедев,

B.Д. Макаров, В.Д.Маршак, Н.Б.Мироносецкий, Г.А.Михайлов, B.C. Михалевич, В.А.Т^УСмн, Н.З.Шор, Д.Б.Юдин и другие.

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

и

ем или набором решений.

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

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

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

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

Основным инструментом исследований, направленных на составление планов, является частичный (неявный) перебор вариан-

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

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

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

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

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

Пусть ¿0.....моменты принятия решений (может быть

заранее неизвестные). В момент времени ^ принимается решение

об использовании одного из способов регулирования, допустимых в текущей ситуации S^. В результате - к моменту t имеем одну из возможных, новую ситуацию S^ ^ - продолжение, .

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

Введем обозначения. Пусть t - текущий момент времени (тот момент, когда принимается решение), t + at - момент принятия следующего решения, N(t) - множество нормальных ситуаций (в момент t), O(t) - допустимая область значений контролируемых параметров, Р(А) - оценка вероятности события А. U(t) - множество допустимых способов регулирования, f(t) - вектор контролируемых параметров (при фиксированном t), S(t) - ситуация, е е (0,1) - допустимый уровень ненадежности системы.

Ситуация оценивается как нормальная, если fit) е Ü(t) и

тах P(S(t*üt) е N(t+&t)) z 1 - г. (1)

ueu< и

Ситуация предкризисная, если f(t) е 0(t) и

тах P($(t+&t) е N(t+At)> < 1 - с. (2)

U€U< 1)

Кризисная, если f(t) t Q(t) и выполняется (1), экстремальная, если /Ш <t Q(t) и выполняется (2).

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

Выпишем критерий, выражавший стремление минимизировать будущие затраты:

min (с(х) + г(х)(1 - р(х)), х б D).

Здесь с(х) - оценка затрат на реализацию плана х, р(х) - надежность этого плана и величины с(х), причем р(х) не ниже заданного уровня; г(х) - оценка дополнительных затрат или потерь, штрафов, связанных с частичной неопределенностью информации, объективными и субъективными погрешностями решений, об-разуших план х, D - область допустимых решений. Этот критерий можно записать так:

min с(х), min r(x)(i - р(х)), р(х) > 1 - с, х € D.

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

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

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

План рассматривается как комплекс взаимосвязанных работ, намечаемых к выполнению (аналогично понятию системы, как совокупности взаимосвязанных элементов). Если имеется список таких работ U, и для каждой работы и е U определены, зафиксированы значения ее параметров х <*и2>••••*„„• 70 считается, что определен производственный процесс X - (хи, и е U>. Это достаточно гибкая программа действий, основанная на решениях, однозначно определенных лишь для ближайших подпериодов (с учетом

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

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

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

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

Для моделирования частично неопределенных параметров и оценки. достоверности показателей эффективности плана используется метод статистических испытаний. Предположим, что определено достаточно представительное дискретное множество состояний природы и имеется ш решений (вариантов), характеризующихся затратами с на реализацию ¿-го решения при ./-м состоянии природы, I е М = а,...,шУ, ) е N = <1,...,п>.

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

Упорядочим элементы i-й строки матрицы ) так, что с.. < е.. е.. , i = i.....т.

тогда указанные критерии формализуются следующим образом:

i

min с.. , т in Г Г с.. )/к.

м Ы » )

í<fi<» ■'i» ft=í is

Предположим, что заданы различные вероятности р. состояний природы. Пусть J - некоторое подмножество N, такое, что

Г р. ? р ила £ р.х. > р. где х- 1. jeJ.ii х- О, иначе, jej 1 j€N ■> J J 1

Обозначим через X множество n-мерных булевых векторов, для

которых выполняется последнее неравенство, тогда приведенные

критерии преобразуются к виду

mia min max с... mía mln £ c..x.. r* *ex lJ Í4Í4» l£X j&) } '

Таким образом получаем средние или верхние оценки затрат при определенном уровне их надежности.

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

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

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

- корректность, логичность, доступность модели для пользователя, возможность сбора и подготовки входной информации;

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

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

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

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

Компромиссное решение находится на основе опыта, интуиции в результате исследования эффективной области. Отметим, что любая оптимизационная задача вида min (f(x), х е 0>, эквивалентна проверке существования решения системы ограничений f(x) « у, х е О, при различных значениях у. Критерий - это показатель. плюс цель или условие. Речь можно вести не о целевой функции f(x), а о контролируемом показателе эффективности производства, другими словами, о зависимой переменной / = f(x) и управляемом параметре у. Бели осуществляется многокритериальная оценка качества решений, то, в принципе, все целевые функции можно перевести в систему ограничений. Но это не исключает возможность использования эффективных оптимизационных моделей.

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

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

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

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

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

Большинство исследуемых нами ситуаций можно представить укрупненное имеется отрезок (а,Ы (например, оси времени) на котором определен список подлежащих выполнению работ, т.е. в каждой точке х € С а,Ы задана количественная характеристика работы (функция спроса). Существует ряд способов (технологий, комплексов оборудования), с помощью которых могут быть выполнены работы. Требуется определить набор технологий и оборудования. интервал, границы использования того или иного способа так, чтобы затраты на выполнение работ были минимальны. Вопрос можно поставить и по-другому: что и когда изменить в технологическом процессе для повышения или поддержания его эффективности, я какие ресурсы при этом потребуются.

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

Первым шагом в организации (развитии, повышении эффективности) производства может бдаъ реализация одного из решений из множества 010). Далее, в зависимости от выбранного решения I е й'0), может быть принято следующее решение из множества альтернатив О1." . На следупцем шаге снова имеем какой-то набор допустимых действий и т.д. Изобразив в виде схемы все возможные варианты, получим дерево решений. Каждой дуге этого дерева припишем затраты, связанные с реализацией соответствующего решения (с учетом приобретенного ранее оборудования, созданных производственных фондов). Очевидно, что наиболее эффективным является кратчайший путь из всех путей, соеданяпщгх корень дерева с висячими вершинами. Строя такие пути, можно учитывать любые затраты и показатели. Но это возможно в тех случаях, когда количество путей сравнительно невелико или, когда анализ ситуации организован с использованием специальных знаний.

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

Будем учитывать, что любая дискретная оптимизационная за-

дача вида min (f(x), х е D> может быть представлена как задача с булевыми переменными. Поэтому далее считаем, что в D включены условия x¿ € f0,í>, i <= И = (í.....т>, х. - управляемые переменные, с помощью которых координируется развитие ситуации.

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

D„ ....,D так, что для каждого к = í,...,п либо может быть ' п <*}

найдено решение х задачи mía (f(x), хе Dk>, либо может быть установлено, что решение х* исходной задачи не содержится в Dt . Пусть К'- множество номеров, для которых выполняется первое условие, тогда f(x') - /(x,s>) - mía (f(xil>), к € К' >.

Область D элементарно разбивается на два подмножества = (х б О, xt= t) и 02= íx е D, xt= 0>, где к - произвольный номер из ff. Подобным образом D{ и 02 можно разевать до тех пор, пока не будут получены решаемые задачи. Процесс анализа ситуации хорошо иллюстрируется с помощью дерева решений. Корень дерева соответствует исходному множеству D. Если оно разбивается на ряд подмножеств 0(.....a ? 2, то каждому из

них ставится в соответствие новая вершина, корень связывается дугами с этими вершинами и т.д.

Каждое из подмножеств 04 просматривается, проверяется с тем. чтобы выяснить, содержится в нем решение исходной задачи или нет. Пусть хй - наилучшее из найденных решений, fR - f(xR), (хй,fk) - рекорд. Просмотр Dt заключается в решении задачи mía f(x) при х е Dt или (если эта задача еще нерешаемая) определении оценки его перспективности. Бели Dk перспективно в смысле вероятного существования в нем эффективного решения, то оно разбивается на подмножества.

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

Предположим, что зафиксированы значения каких-то к компонент вектора х ~ (х) ..,хж>, номера этих компонент образуют список I, остальные переменные свободные - их значения не определены. Т.о. имеем частичное решение z = (z{ .....z%), образованное из фиксированных значений переменных, и множество его продолжений D(z). Обозначим = (i/x¿= i, i е i). Список

1 - нерасширяемый, если включение в !¡ любого подмножества из Н\1 не приводит к более предпочтительному решению. В этом смысле / и соответствующее частичное решение неулучшаемы (получено так называемое тупиковое решение). Если множество I(г), соответствующее z, нерасширяемо, то решение x(z), образованное из элементов вектора z и x¿ = О, i е Н \ I, является наилучшим в подмножестве D(z) и оно оказывается проверенным.

Процедура построения нерасширяемого списка ¡(z) и локально оптимального, тупикового решения x(z) называется достройкой, а возвращение к одному из непросмотренных подмножеств -перестройкой. Чередуя эти процессы, получаем разбиение области D на подмножества, одновременно производится их проверка. В качестве процедуры достройки подходит любой градиентный метод, например, алгоритм покоординатного спуска (прямой, двойственный или прямо-двойственный).

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

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

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

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

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

Чтобы определить условия оптимальности решения х и иметь

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

min <f0(х), х € 0>, (А)

D = íx I í>. - f¿(x) * 0. i € М, х б Х>, fí(x) определены на X из £". Вводится функция Лагранжа

L(x.o) = fn(x> - V (Ь. - f.(x))v.,

'о . . t I I

i

где o.)0 - множители Лагранжа (двойственные переменные), со-

ответствушие первой группе ограничений иэ D (í f К).

Следупаая задача является двойственной к

max mía L(x,v). (ß)

о>0 хеХ

Если теперь В рассматривать как прямую задачу, то двойственную можно представить в виде:

mia шх Их,и). (С)

хеХ о*0

Перечислим некоторые свойства пары двойственных задач. Пусть ?Со> = mill {L(x,v>, х е X), fix) = max íL(x.u), о * OÍ.

1. Функция p(v) вогнута на любом выпуклом подмножестве ее области определения V. f(x) выпукла в любой выпуклой подобласти D. Для произвольных о е V и х е D выполняется неравенство /Сх) > f(v). Если /(х) = р(о), то х.о - оптимальные решения.

2. Пусть D - выпуклая область. Если х*е D, о"е К и выполняются условия дополняющей нежесткости С/.fx*J - ft.)о" = О,

t е Ä, то имеем оптимальные решения и /(x*J = fa(x") = p(v*).

Предположим, что прямая и двойственная задачи имеют вид:

F = min (ex; хеХ, Лх<Ь, хз€), Ф = mía Ссх - t»(i> - Ах)) —► max.

хеХ иЮ

3. Пусть х*. о* = v*<b) - оптимальные решения, v - допустимое, причем < о", i е Я. Тогда существует точка хеХи вектор у =у(о), соответствующий о (у и о связанны условиями v(y - Лх) = О), при этом у. * Ь., х = х(у) - решение прямой задачи, в которой вектор Ь заменен на у, о = а(у) - оптимальные двойственные оценки. Можно сформулировать и другие подОб-

ные утверждения. Их содержание выражается следуюцим образом:

у( о) > Ь «=> о (у) < v(b); ¡/(и) « 6 <=> и(у> > о(Ь).

4. Пусть о1 , о2 - допустимые векторы, причем и'< и2< о". Тогда существует у1 и у2, соответствующие о' и и2, такие, что 6 « у2* у' , при этом F(b) > F(yz) ï F(y1 ). Справедливо и обратное утверждение: если F(y' )< со и F(yz)< со (решения существуют) и у' > у2, то V1 < и2 и Ф(о' ) < Ф(о2), т.е. F(y) - не-возрастапцая функция, а Ф(о) - неубывающая.

Для дискретных задач существует выражение "разрыв двойственности", означающее, что оптимальные значения целевых функций прямой и двойственной задач могут не совпадать. Но неравенство f(x) > ç(v) на допустимых решениях остается в силе, поэтому <p(v) используется в качестве нижней оценки fix) (оценки перспективности подмножества решений), а также для оценки погрешности решения с = (f(x) - p(v))/p(u). Другие перечисленные свойства тоже оказываются полезными.

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

Декомпозиция по двойственным переменным заключается в переходе от исходной задачи к двойственной, т.е. к оптимизации функции Лагранжа, образованной из fa(x) и присоединенных к ней связывающих ограничений с весовыми коэффициентами - множителями Лагранжа. При удалении связывающих условий из системы ограничений получается совокупность решаемых задач (при фиксированном векторе и). Координирующая задача заключается в построении последовательности векторов о*41 , 14=1,2,..., которая приводит к требуемому решению.

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

которые соответствуют" текущему о. Бели это условие окажется нарушенным, то подправим значения переменных х или о..

Заменим в исходной задаче вектор Ь на у, т.е. введем искусственные переменные, с помощью которых будут координироваться исследования. Они связаны с прямыми и двойственными переменными (условиями дополняющей нежесткости), так что, все пе-переменные оказываются связанными между собой. Начальные значения у.. I «К, соответствуют нулевым оценкам дефицитности. Постепенно будем сужать область поиска, заменяя на каждой итерации вектор у на у'. такой что уЧ у. и, по крайней мере, для одного номера I е Н выполняется строгое неравенство.

Другими словами, исходная задача Я погружается в семейство задач РСу) с переменными правыми частями ограничений и расширенной областью допустимых решений 0(у). Таким образом, имеем задачи: исходную Р. параметрическую Р(у). двойственную к Р и двойственную к Р(у), причем каждая из них обладает полезными свойствами. Координирование основывается на этих свойствах. Постепенно область 0(у) сужается. Бели при этом получается двойственно-недопустимое решение, то производится его достройка. Исследования продолжаются до тех пор, пока не будет найдено эффективное решение.

Представленные методы использовались для решения различных задач: размещения производства, стандартизации и унификации. выбора парка оборудования и его замены, выбора состава технологических комплексов и других. В каждом конкретном случае сначала проводились численные, эксперименты, в которых исследовались характеристики алгоритмов, затем эти алгоритмы применялись для анализа ситуаций. Как показали результаты экспериментов и практический опыт, с помощью изложенных методов с частотой 0.92 - 0,96 за полиномиальное время удается найти решение, погрешность которого не превышает 3 - 5 %.

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

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

Рассматривая горное производство, в качестве объектов имеем разрабатываемые участки и блоки месторождения, а также забои, связанные между собой ограничениями по скорости подвигания. расстоянию и производительности. Возникают вопросы:

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

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

Эти вопросы могут объединяться требованием их совместного решения. Так что это условное, искусственное разделение задач. Вопросы, охватываемые вторым пунктом чаще относятся к задачам производственно-транспортного типа (глава 4).

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

Обычно выясняются причины незапланированных простоев оборудования. Допустим, имеется статистика по отказам, сбоям в обслуживании с указанием их причин и длительности восстановления. Суммарные за определенный (базовый) период времени длительности простоев по каждому из факторов - случайные величины, на основе которых рассчитывается коэффициент готовности к оборудования или комплекса. Он показывает долю простоев в общей »длительности производственного процесса. Это среднестатистический параметр, зависящий от продолжительности базового периода и тех случайных факторов, с учетом которых он рассчитывается. Используя различные наборы, сочетания факторов (обозначим такое сочетание через А) можно рассчитать требуемые коэффициенты готовности как к(А) = 1 - %(А), где Л(А) - та наиболее вероятная (средняя) часть рабочего времени или верхней оценки производительности оборудования за рассматриваемый период, которая теряется в результате простоев по причинам из А.

Пусть М - множество комплексов, и для каждого из них установлена зависимость коэффициента готовности А. от резерва фронта работы г4 этого комплекса а € ДО, т.е. от выполненных объемов предшествующих работ. Таким образом, предполагается,

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

тп

Г с (г.) —» mía , i-i 1 1 ч.г

с учетом индивидуальных и попарных ограничений, накладываемых на производительность комплексов q., i е И, требуемого общего объема выпуска и зависимостей, связывающих г с производительностью 1-го и смежных с ним комплексов (вообще говоря, с -это сумма затрат за период планирования, а г. и д. - векторы, размерность которых равна числу подпериодов). .

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

Предположим, что определены верхние оценки производительности q. каждого комплекса t из Я (за подпериод) без учета возможных потерь рабочего времени (соответственно, снижения производительности! по условиям, связывающим элементы системы между собой. Для оценки производственной мощности предприятия и автоматизированного формирования планов, допустимых по условиям, связывающим смежные объекты, можно воспользоваться моделью

£ Я —* »пах, ¿eMD 1 ' Ч

q. S a..q. + b.. . (i.j) e U. 0 < g. < g. , i- e H,

где Lf я 11 < К - множество пар взаимосвязанных элементов , НЬ -множество добычных комплексов.

Допустим, необходимо учесть общие элементы системы, через которые проходят потоки продукта. Все пути движения потоков внутри предприятия представим в виде сети G = (V• Пусть g -верхняя оценка производительности оборудования или пропускная

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

Е + Чи ' —*• тах-иеие, q

£ Ч * ~ Е ■ Ч =0. jef, , О < q < q , и е U .

4и и ^u J 1 ^и^и

иеи. uGU.

J - J

В процессе анализа ситуации определяются оценки разных критериев и контролируются все'существенные показатели, в том числе обший объем выпуска. Координирование осуществляется на основе этих показателей, неформализованных целей и ограничений с использованием переменных верхних границ q'u, и е U, связанных с qu и qu неравенствами дц< q^S дц.

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

Рассмотрим другую ситуацию. Пусть N = <1.....я> - множество объектов, на которых выполняются или будут выполняться какие-то работы. Имеется m комплексов. Каждый из них может использоваться для поочередного выполнения различных работ. Начатую работу можно временно прервать, приостановить, но нельзя перевести оборудование на другой, новый объект и начать там работу, если не завершена оставляемая. Допускаются разные сроки начала и окончания работ, темпы (интенсивность) их выполнения. Требуется определить эти параметры так, чтобы в каждом подпериоде обший объем выпуска был не менее намечаемого, а затраты на поддержание производства были минимальны.

Если попытаться формализовать эту ситуацию, то получим

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

Представим ситуацию с помощью сетевой модели. Пусть Uk -множество дуг, связываниях вершины из Vt, соответствущие к-ыу объекту и моментам времени, разделяпиим подпериоды. Каждая дуга и е Ut соответствует одному из возможных вариантов организации работ на объекте к е N. Эти варианты различаются сроками начала и окончания работ, темпами их ведения qut, затратами сц на реализацию и, возможно, какими-то техническими решениями. Сначала предположим, что объекты, работающие одновременно, не связаны между собой технологическими условиями.

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

Г с о —* min. ,

U U

uCÜ у

Z Уи - Z Уи = О, j е У; £ yuQui > ö{ , t е Т;

u€U* u€UT "€U

J J

у e (0,1>, и e U, и * й = (e,s); y_ = m .

u

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

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

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

объектов. Получаем модель

Г Г с. ж.. —* Kin ,

w ы И II

j£H ieм. J w x

J

Z Z Я1их * Q , t ç T;

je» ien'. 1 '

£ x. . = 1. j e N: x.. € fo. 1), i e M'., j e N. j

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

£ гиЮ ~* aiTl'

ueu q (задача Р)

£ q = 6. j e V, q < q < q и € U.

u€U. ~

J

Здесь q = <quK и e U, - поток в сети, ru - сопротивления дуг, преодолеваемые источниками потока. Для неориентированных дуг Яи - ~ Яи- Для ориентированных > О. Введем двойственные

переменные: тг. - потенциалы верши, соответствующе условиям сохранения потока в верванах сети, j € Y. и äu > 0, ßu z О, соатветствуюцае ограничениям на поток снизу и сверху, и € и. Пусть q - допустимый поток. Для его оптимальности необходимо и достаточно существования таких значений тс. н а^, ßu, что

С-г q2 + л., - л., + «х - ß )q -О,

или I ( U) J ( u) u u ^u

(q - q )oc =0, (q - q )в = О, и e U.

Здесь и далее i(и), j(и) - номера начальной и конечной верван дуга и в соответствии с направлением движения потока по ней, О. и g U. Суммируя первую группу условий и учитывая сохранение пото]ta в вершинах, получаем уравнение баланса мощностей

£ (г q2 * ß )q = £ a q . ueu u€U

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

давления (напор), создаваемый источником потока, установленным в дуге и, Ри - снижение давления в узле j(и), обусловленное сопротивлением регулятора, установленного в и.

Пусть G - махтная вентиляционная сеть, U - множество горных выработок, гц - их аэродинамические сопротивления. В сети выделено подмножество дуг - потребителей с требуемыми расходами воздуха с?ц, а также подмножество дуг í/g, в которых установлены вентиляторы. Воздух распределяется по сети с помощью регуляторов, размещенных в определенных дугах. Необходимо найти сопротивления регуляторов дгц и режима работа вентиляторов, при которых каждый потребитель обеспечивается требуемым количеством воздуха, а потребляемая мощность минимальна:

Е <ги ♦дги).|в®| = | 1*Х — ш

u€U q9n,n

о

2 ♦ % - £ - Чи = О. j * S U £; q <q í q и e U;

ueu. u€U. "

i J —

я.. % - я.. = г q2 + h , h i h < h , u e U.

l(U) J (u) u^u u -u u u

Описывается процесс решения задачи, при этом P(r,q,q) рассматривается как задача с. переменными коэффициентами целевой функции ги и переменными границами потоков в дугах сети. С их помощью координируется вычислительный процесс.

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

Допустим, ситуация формализуется в виде Fix,у) = ду * сх —*■ min, Ах - Ь, х i О у, х > О, у * О,

А и D - матрицы коэффициентов ограничений; д. с. Ь - заданные векторы. Двойственная задача:

Ф(ц) = mía Сс «• и)х —*■ max. Ах = b. х * О, uD «г g. и > О, X и

где и - вектор двойственных переменных, соответствующих второй группе условий прямой задачи. Компоненты и связаны с переменными yi условиями дополняющей нежесткости u(Dy - х) - 0, так что и - и(у). С учетом этого, во всех рассматриваемых далее ситуациях исходная трудная задача сводится к решению серии или поеледовательностя решаемых задач. Они различаются коэффициентами целевой функции и границами потоков в дугах сети. Пропускные способности дуг получаемых сетей рассматриваются как уп-

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

f = Е aisl * Е Е с * —> min .

¿СМ i£M j€N J J х,у

Г х. . = 1, i е N, х.. < у , х.. е 10,1), i е ff, j е N.

¿IM lJ ч 1 lJ

Здесь i - технологический способ (пункт производства, типоразмер или комплекс оборудования); j - точка спроса (работа); g. - начальные затраты, связаннее с i; с - текущие расходы.

Приводится алгоритм решения задачи, в основе которого лежит неявный перебор вариантов. При этом используется введенное ранее понятие нерасширяемого множества 1. Координироние осуществляется по переменным у.. На каждой итерации имеем список I = (ij .....t^) номеров компонент у, значения которых фиксированы. / = /0U lt, (i I у.= 1>, I0= (i I у.= 0>. (yR,FR) -

рекорда FU) - значение функции F при фиксированном наборе изделий (технологий) / (у. - О, i <t /); Q - область допустимых решений двойственной задачи к непрерывной исходной при фиксированных у., t е /; Я(Dj> - нижняя оценка целевых функций прямой и двойственной задач. В начале работы алгоритма список I или пуст, или образован из номеров компонент у, равных единице; ук= у, 10= ф, lt = 1, q = |/|, Fr = F(I).

n.J. Определяем H(QJ). Если H(Q}) > г", то идем к п.4. п.2. Находим нерасширяемое множество /', q'=|/'| и F(I'). Если F(l') < Fr , то заменяем рекорд. Если q = q' или F(l') = ffiDj), то переходим к пункту 4. п.З. Полагаем yi - i. i € /'\/, / = /'. q - q'. п.4. Если у. = 1, то у. := О и возвращаемся к пункту 1.

1ч 1ч

п.5. Если q = 1, то вычисления заканчиваются, в противном

случае q заменяем на q-i, далее - к пункту 4. Общность этой схемы позволяет использовать ее для решения вбой из рассматриваемых далее задач. Достаточно определить роцедуру вычисления Я(0;) и способ построения нерасширяемого писка /'. Как отмечалось ранее, исследования, в принципе, мою организовать и без вычисления нижних оценок H(QJ). Необхо-

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

Пусть г - частичное решение, ¡(г) - нерасшнряемое множество. и. а(п).....о <2 4 ) - разбиение исходной области О,

порождаемое решением г, д = ///. Вектор у = у(г) = ул - решение задачи, если и только если ни в одном из подмножеств не содержится более эффективного решения.

Получаем схему исследований: имея разбиение 0, проверяем в какой-либо последовательности Ок, * = Находим под-

множество , содержащее вектор у', такой, что Р(у') < Г(уя). Заменяем рекорд, строим новое разбиение, соответствующее г(у'), и т.д. Заметим, что вершина, в которой производится ветвление, определяется по верхней оценке Г(у).

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

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

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

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

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

1. Находится близкое к оптимальному тупиковое решение и задачи В, двойственной к исходной, и определяется оценка ЯСО).

2. По этому решению и находится некоторое допустимое решение (х,у) - начальное приближение.

3. Далее (х,у) улучшается с помощью алгоритма ветвей и границ за ограниченное число итераций.

Она почти совпадает со схемой, предложенной В.Л. Бересне-вым, Э.Х. Гимади, В.Т. Дементьевым дпя построения приближенного решения задачи стандартизации. Различия - в третьем пункте. Основное из них в том, что используется направленный поиск (не односторонняя схема) и радиус поиска равен 2. Оценка трудоемкости алгоритма 0(т3п) операций. Погрешность получаемого решения не превышает 3 У. с частотой 0,92, среднее время решения задачи размерности тт = 10*100 и 35x100 около 3 и 6 секунд при быстродействии ЭВМ 106 операций в секунду.

Представим другую из рассматривавшихся (изучавшихся) ситуаций. Имеется множество N объектов и для каждого определены изменяющиеся со временем объемы работ. Работы можно выполнить с помошью различных типов или типоразмеров оборудования (машин, изделий, комплексов) из расширенного ряда М, включающего как выпускаемые машины, так и те, которые в принципе могли бы выпускаться. Изделия из Я различаются мощностью, надежностью, экономяческими показателями, включая начальные затраты на освоение производства новых иашин, капитальные вложения ., связанные с использованием ¿-го оборудования на )-м объекте, 1 эксплуатационные расходы с* для ^го подпериода. Предполагается, что оборудование не переставляется с одного объекта на фугой (намечены последовательности отработки блоков месторож-1ения; блоки, отрабатываемые в определенной последовательнос-ги, объединены в один объект). "Требуется определить ряд (парк) >борудования, его размещение так, чтобы затраты на выпуск обо-)удования, капитальные вложения, связанные с его использовани-

ем на объектах, и текущие расходы были минимальны-.

Г = У ((.г + Г (Ш .у.. + £ с'.х1.)) —» та, ¿н 1 1 »ет " ^

Е х1 = 1, ) е N. I е Г; х1. < у.. а г , х1. € (0,1> , I е N. ] € N. <бТ.

Пусть построено тупиковое решение двойственной задачи и по нему (с помощью условий дополняющей нежесткости) определено допустимое решение г,у. Множества , , образованные из номеров единичных компонент г,у. нерасширяемы. Это означает, что замена значений любых нулевых компонент г и у на единицу не приводит к повышению качества решения. Следовательно, решение г,у, возможно, удастся улучшить, лишь упорядочив использование намечаемых к выпуску изделий (оптимизируя у1} при текущих фиксированных значениях г.) и/или исключив из ряда одно или несколько каких-то изделий и далее снова оптимизируя -у (исходный расширенный ряд включает в себя и гипотетические машины).

При <|мксировашюм векторе г имеем последовательность задач РА г), j е Н, типа размещения производства. Чтобы получить общий алгоритм с полиномиальной оценкой трудоемкости, достаточно использовать эффективный алгоритм решения Р.(г) и ограничить число итераций величиной т, потребовав, чтобы значение каждой из переменных 1 менялось не более двух раз. Как показали результаты экспериментов, обычный покомпонентный спуск по 2 дает грубое решение, поэтому имеет смысл проверять подмножества DJi(z<*)), соответствующие частичному решению г'*1 (достройка чередуется с перестройкой).

Численные эксперименты по оценке качества алгоритмов проводились на классах задач К(т.п,р), для которых (., д.}. с|^ генерировались с помощью датчика псевдослучайных чисел, равномерно распределенных на интервалах (0,500), (10,200), (10,300) соответственно. =£(20,50,10), *2=£<30,50,10), К3=К(20,75,10) X =К(20,50,15). Ниже приведены максимальные и средние оценки погрешностей решений, получаемых с помощью предложенной схемы, а также среднее время решения одной задачи в секундах (из каждого класса случайным образом выбиралось по 25 задач, быстродействие ЭВМ 106 операций в сек.). Использовалась приближенная

нижняя оценка целевой фун-с 6,5 8,3 5,6 5,3 киии задачи, поэтому можно

mai

6,5 8,3 5,6 *4 5,3

4,9 6,6 4,2 4,1

27 44 36 35

с 4,9 6,6 4,2 4,1 ожидать, что действительные

ср

t 27 44 36 35 погрешности значительно ниже.

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

£ ♦ £ £ £ д\ х\ — та .

Î6N i€M j£N teT J J X.y

£ x* = 1, j Ç N , t Ç T; iÇH J

£ x1. £ y., i e M, t e T; x* € {o,i> V (t,j,t>.

j €N 1

Пусть u.t - двойственные переменные, соответствующие второй группе ограничений, Ф(и) - функционал двойственной задачи - вогнутая монотонно неубывающая функция, х,у - начальное приближение, соответствующее u.t= О, i € К. tel. Используется следующее свойство пары двойственных задач: с уменьшением значений у., значение Ф(и) не убывает. Декомпозиция осуществляется по переменно у., при этом используется прямо-двойственный метод. Если в процессе вычислений получается двойственно-недопустимое решение х,у, то производится его достройка. Кроме построенного таким образом алгоритма А проверялся двойственный алгоритм градиентного типа А.

Численные эксперименты проводились на задачах с псевдослучайными параметрами с., g^, равномерно распределенными на интервалах (10,с), (0,100) соответственно. Рассматривались классы задач, в которых m, а и р принимали значения: 1) 15,40,10; 2 ) 20,40,10 ; 3) 15,20,10; 4) 15,40,20. К. и К'. - L -й класс при с = 100 и с - 200. Максимальная оценка погрешности решений 3,59 У. получена в классе К'3, для остальных классов эти оценки не превысили 2 'А. Время счета в классе К , i = /,... ,4, (по 50 задач, 106 операций в секунду) соответственно 13,20,7,19 мин. Более точное решение двойственной задачи - при использовании в качестве начального приближения для Ай не нулевого решения, а значений uit, получаемых с помощью алгоритма А.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

новныу факторам, влияющим на эффективность выбора.

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

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

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

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

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

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

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

1. Кузнецов A.C. Моделирование и анализ производственных ситуаций (с примерами приложений в горном деле).- Новосибирск: Наука. 1996. - 132 с.

2. Кузнецов A.C. Задача выбора оборудования многоразового использования // Управляемые системы. '- Новосибирск: ИМ СО АН СССР, 1979, вып. 19, с. 40-50. . , .

3. Кузнецов A.C. Алгоритм вычисления • оценки точности для решения одной задачи выбора оборудования // Целочисленные экстремальные задачи (Управляемые системы). - Новосибирск: ИМ СО АН СССР, 1981, вып. 21, с. 26-32. ' , ""

4. Кузнецов A.C. Об одном обобщении задачи стандартизации // Вычислительная техника и системный анализ. - Новосибирск: ИМ СО АН СССР, i960, с. 108-111.

5. Кузнецов A.C. О задаче выбора оптимального типоразмер-ного ряда шахтных вентиляторов главного проветривания //Все-союз. конф. по проблемам теоретической кибернетики. - Новосибирск: ИМ СО АН СССР, 1980, с. 83-85.

6. Кузнецов A.C. Выбор оборудования для главных вентиляторных установок шахт и рудников// ФТПРПИ,- 1980, N5, с.106-110.

7. Кузнецов A.C. О применении моделей стандартизации для выбора оптимального типоразмерного ряда вентиляторов главного проветривания // Вентиляция и газодинамические явления в шахтах. - Новосибирск: ИГД СО АН СССР, 1981, с. 91-95.

8. Кузнецов А.С. Об эксперименте, связанном с задачей размещения // Второй Сибирский Конгресс по прикладной и индустриальной математике ("Исследование операций") - Новосибирск: ИМ СО РАН, 1996.

9. Кузнецов А.С. Об автоматизированном рабочем месте технолога угольного карьера // ФТПРПИ, 1997, N 1, с. 76-82.

10. Kuznetzov A.S. About the system for computer!sed for-mlng and analysis of technological solutions for coal open-pit mine // Международный Симпозиум "Применение компьютеров и исследование операций в горной промышленности - АРС0М-97" - М.-. МГГУ, 1997, с. 87-88.

11. Кузнецов А.С., Лукин С.М. Об одном подходе к расчету воздухораспределения в рудничных вентиляционных сетях // Управление вентиляцией и газодинамическими явлениями в шахтах. -Новосибирск: ИГЛ СО АН СССР,.1986, с. 37-39.

12. Кузнецов А.С., Лукин С.М. О применении потоковых алгоритмов для расчета воздухораспределения в вентиляционных сетях // ФТПРШ. - 1989. N 5. с. 56-63.

13. Кузнецов А.С., Кортелев О.В., Федоров Н.В. О некоторых вопросах, связанных с принятием решений при долгосрочном планировании в горном деле // Оптимизация горных работ и фрагменты САПР. - Новосибирск: ИГД СО АН СССР, 1990, с. 149-151.

14. Кузнецов А.С., Кортелев О.Б., Федоров Н.В., Сычев В.А. Некоторые модели производственно-транспортного планирования на разрезах КАТЭКа /У Вопросы совершенствования горных работ на шахтах и карьерах Сибири. - Новосибирск : ИГД СО РАН, 1990, с. 89-95.

15. Кузнецов А.С., Кортелев О.Б. Разработка методического и математического обеспечения локальных систем поддержки принятия решений в горном деле // Механика горных пород. Горное и строительное машиноведение. Технология горных работ. - Новосибирск: ИГД СО РАН, 1993, с. 209-212.

16. Кузнецов А.С., Савельев В.Н., Смоляницкий Б.Н., Сухарева Л.И. Задача выбора ряда буровых систем нового поколения // ФТПРПИ. - 1992, N 1, с. 56-58.

17. Кузнецов А.С., Шрейдер Д.Я., Андреева Л.Н. О выборе параметров вскрытия и плана развития горных работ шахты // Проектирование и строительство горных предприятий. - Новоси&рск:

ИГД СО АН СССР, 1985, с. 59-64.

18. Осокин А.Л., Кузнецов A.C. Оптимизация тнпоразнерного ряда ручных электромагнитных перфораторов // Основные направления повышения технического уровня и качества ручных машин.

- М.: ЩййГПЗстроймаш, 1989, с. 39-41.

19. Кортеяев О.Б., Кузнецов A.C., Сычев В.А., Иванов В.В. Оценка производительности выемочно-транспортных комплексов в процессе планирования и организации горного производства // ФТПРПИ. - 1992, N 4. с. 70-73.

20. Кортелев О.Б., Кузнецов A.C., Сычев В.А., Иванов Ю.В. Поиск и поддержка принятия решений в горном деле // ФТПРГ.И. -1992, N 3, с. 85-95.

21. Демидов Ю.В., Кортелев О.Б., Кузнецов A.C. О персональных автоматизированных системах анализа ситуаций в горном производстве // Уголь. - 1997, N 3, с. 23-24.

22. Кузнецов A.C., Петров H.H., Морозова Г.В., Петрова Л.Н. Методика выбора на ЭВМ оборудования для главных вентиляторных установок шахт и рудников // Управление вентиляцией и газодинамическими явлениями в шахтах. - Новосибирск: ИГД СО АН СССР, 1982, с. 56-61.

23. Кузнецов A.C., Морозова Г.В.. Петрова Л.Н. Аналитическое описание аэродинамических характеристик вентиляторов // Управление вентиляцией и газодинамическими явлениями в шахтах.

- Новосибирск: ИГД СО АН СССР. 1983, с. 74-83.

24. Кузнецов A.C., Морозова Г.В, Петрова Л.Н. Расчет на ЭВМ годовых эксплуатационных расходов по главным вентиляторным установкам // Управление вентиляцией и газодинамическими явлениями в шахтах. - Новосибирск: ИГД СО АН СССР, 1983, с. 88-94.

25. Кузнецов A.C., Морозова Г.В. Статистическое моделирование ожидаемых вентиляционных режимов при обосновании ряда вентиляторов главного проветривания // Управление вентиляцией и газодинамическими явлениями в шахтах. - Новосибирск: ИГД СО АН СССР, 1986. с. 28-33.

26. Кузнецов A.C., Морозова Г.В. Результаты предварительных расчетов по обоснованию параметров вентиляторных установок и ряда вентиляторов главного проветривания // Управление вентиляцией и газодинамическими явлениями в шахтах. - Новосибирск: ИГД СО АН СССР, 1986, с. 26-28.

Црес

—С- {{) Ш Щ/.

С

ífli

сЛб'Ц, V

..¿Л;

íssmmssя

1 /Л

л.

«ч .Г-' Л „ \ .....

Российская Академия наук • Сибирское отделение Институт гарного дела

На правах рукописи

КУЗНЕЦОВ Александр Сергеевич

РАЗВИТИЕ ТВЭРЕШЧШШХ ОСНОВ ГШШХ АВТШАШЗИРОВАННЫХ ТЕХНОЛОГИЙ АНАЛИЗА СЛОЖНЫХ ПРОШШЛСТВЕШЫХ СИТУАЦИЙ (с приложениями в горном деле)

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

Диссертация на соискание ученой степени доктора технических наук

Новосибирск - 1998

V,

V/

СОДЕРЖАНИЕ

ВВЕДЕНИЕ..........................................................4

Глава 1. ОБ ОЩЙХ ВОПРОСАХ, СВЯЗАННЫХ С ПРИНЯТИЕМ

РЕШЕНИЙ.......................................,26

1.1. Устойчиво эффективное развитие производственного процесса и принцип достаточности выбора....................26

1.2. Фактор времени........,..............................31

1.3. Принятие решений в условиях частичной неопределенности.................................34

1.4. О задачах, моделях и алгоритмах._________________39

1.5. Многокритериальность, принцип взаимной эффективности ................................................44

1.6. Декомпозиция, среда, координирование...................46

Глава 2. МАТЕМАТИЧЕСКИЕ ОСНОВЫ АНАЛИЗА СИТУАЦИЙ......................51

2.1. Простейшие задачи, допущения................................51

2.2. Неявный перебор вариантов.............58

2.3. Координирование на основе цен и с помощью цен (оценок дефицитности).............................65

2.4. Элементы потокового программирования....................74

2.5. Задача о назначениях, расстановка оборудования... 85

Глава 3. РАСПРЕДЕЛИТЕЛЬНЫЕ ЗАДАЧИ......................... 92

3.1. Расчет производительности комплексов оборудования (распределение работ между исполнителями)........ 94

3.2. Неэффективная формализация.......................104

3.3. Агрегированные модели............................107

3.4. Распределение транспортных средств и оптимизация грузопотоков.....................................112

3.5. Моделирование потоков в физических сетях.........114

Глава 4. М0ДЕ1Ш И АЛГОРИТМЫ ПР0ИЗВ0ДСТВЕНН0-ТРАНСП0РТБ0Г0

Ш1А.............................................123

4.1. Размещение производства и стандартизация.........125

4.2. Оптимизация затрат и выпуска..................... 141

4.3. Выбор и распределение парка оборудования_________ 152

4.4. Лругие задачи....................................167

ЗАКЛЮЧЕНИЕ.................................................175

ЛИТЕРАТУРА................................................ .178

ПРИЛОЖЕНИЯ.................................................201

П.1. Подготовка исходных данных для исследования параметров и способов регулирования шахтных

главных вентиляторных установок.................,201

П.2. Система автоматизированного формирования и анализа технологических решений для угольного карьера....................................... 210

П.2. Акты н справки о внедрении...................... .220

ВВЕШШШБ

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

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

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

Ориентация работы совпадает с одним из "Приоритетных направлений исследований в области горных наук'4 (определены отде-

лением геологии, геофизики и горных наук РАН): "Развитие методов компьютерного моделирования объектов и процессов горного производства на шахтах и карьерах с цель» повышения эффективности добычи полезных ископаемых в новых экономических условиях". Исследования выполнялись в соответствии с программой двухстороннего сотрудничества АН СССР и Болгарской АН <КЩЫ\0, а также по программе "Сибирь", тема 3.2.1.5 (номер гос.регистрации 01880079149): "Развитие научных основ эффективных технологий разработки месторождений твердых полезных ископаемых в условиях больших глубин", разделы: "Разработка методического и математического обеспечения для расчета и оценки параметров технологий добычи твердых полезных ископаемых", "Разработка методов 1 средств совершенствования рудничной вентиляции", "Разработка математических моделей, алгоритмов и прикладных программ для решения задач стандартизации горных машин". Хоздоговорные работы: N 252-82 "Разработка математического обеспечения для решения на ЭВМ задач оптимального воздухораспределения в вентиляционных сетях шахт и рудников", N 83-82 "Разработка математического обеспечения для анализа технологических схем ведения горных работ на разрезе "Березовский", N 537-39 "Оптимизация параметрического ряда буровых роботизированных комплексов и комплектов технологического инструмента" и другие.

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

Идея - в создании гибких информационных технологий, автоматизированных рабочих мест, ориентированных на определенного

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

Задачи исследований:

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

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

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

- исследование различных методов и алгоритмов с целью оценки их эффективности, проведение численных экспериментов;

- разработка математического обеспечения для решения ряда задач производственно-транспортного типа;

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

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

Основные научные результаты, защищаемые автором:

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

но-аналитических систем и принципы, на которых основывается построение подобных систем;

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

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

- метод решения специальных дискретных экстремальных задач большой размерности;

- модели и алгоритмы решения рассмотренных задач выбора.

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

Яичшй вклад автора:

- осуществлена постановка ряда задач, возникающих на разных стадиях организации горнодобывающего производства (формирование парка, расстановка и замена оборудования, оценка его производительности, оптимизация режимов работы и резервов производства) , а также при обосновании параметров горных машин (стадии НИР I ОКР) и планировании их выпуска, при этом найдены эффективные математические модели и алгоритмы, способствуюте

принятию обоснованных решений;

- разработано и отлажено множество машинных программ, процедур, с помощь*« которых осуществлялась подготовка исходных данных, проводились численные эксперименты, создавались инфор-мацконво^нагатяческяе системы и исследовались реальные ситуации, связанные с оптимизацией параметров некоторых горных машин, обоснованием номенклатуры и объемов их выпуска;

- рассмотрены различные модификации, обобщения и частные случаи задачи о потоке минимальной стоимости (нелинейная транспортная задача на частично ориентированной сети, с переменными коэффициентами целевой функции„ с ограничениями возможностями регулирования и изменявшимися границами потоков, нелинейными начальными затратами), проведена серия численных экспериментов и получены относительные оценки эффективности некоторых алгоритмов решения указанных задач;

- выполнены анализ и оценка алгоритмов типа неявного перебора вариантов в зависимости от радиуса, глубины и схемы поиска в условиях ограниченного времени;

- предложена методология анализа сложных производственных ситуаций с помощью персональных систем поддержки принятия решений» выделены основные принципы* на которых базируется создание подобных систем.

Научная новизна:

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

~ найдены эффективные стратегии поиска, схемы организации диалога с ЭВМ в процессе неявного перебора вариантов при огра-

ниченной продолжительности исследований;

- показана возможность использования идеи метода сокращения невязок (беспорядка) Форда-Фалкерсона для исследования в диалоге с ЭВМ области Парето-оптимаяьных решений;

- получены и сформулированы необходимые, а в ряде случаев достаточные условия оптимальности решений рассмотренных задач;

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

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

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

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

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

- обоснование типоразмерных рядов горных машин (шахтные вентиляторы, роботизированные буровые комплексы, ручные перфораторы, компоновочные схемы главных вентиляторных установок);

- выбор параметров транспортно-технологических схем, системы разработки и режимов работы основного горно-транспортного оборудования в условиях разреза "Березовский" (КАТЭЮ;

- обоснование номенклатуры и объемов выпуска рядовых, сортовых и марочных углей (при начальных затратах на строительство установок для получения сортового топлива).

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

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

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

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

Результаты исследований вошли в ГОСТ 25988-83 "Перфораторы ручные электромагнитные", в "Руководящий технический материал по выбору вентиляторов главного проветривания", утвержденный Шнуглепромом СССР <РТМ 07.03.003-87). Программное и методическое обеспечение по оптимальному регулированию шахтных вентиляторных установок передано в Высший горно-геологический институт (Болгария), включено в подсистему "Вентиляция" САПР-"Уголь". Программная система для расчета оптимальных совместных режимов работы шахтных вентиляторов и моделирования воздухораспределения в сети горных выработок передана в ЦШШ ВГСЧ Урала, в институты Сибгипрошахт и ПромНййпроект. Результаты исследований по совершенствованию типоразмерного ряда шахтных вентиляторов и параметров главных вентиляторных установок переданы в Донгипроуглемаш, ШШГО им. М.М.Федорова и НПО Уралгормаш. Программная система и методические рекомендации по обоснованию номенклатуры и объемов выпуска сортовых и марочных углей, разработанные совместно с институтом КАТЭКНЙЙуголь, переданы в компанию "Росуголь". Система автоматизированного формирования транспортно-технолошческих схем ведения горных работ и динамики карьерного пространства передана на разрез "Березовский-! где она прошла производственные испытания.

Основные результаты и опыт автора по автоматизации иссле-

дований, организации диалога с ЭВМ представлены в его монографии: Моделирование и анализ производственных ситуаций (с примерами приложений в горном деле), - Новосибирск: Наука, 1996, - 132 с.

Апробация результатов. Научные результаты, положения работы докладывались на межведомственных и Всесоюзных семинарах и совещаниях по управлению вентиляцией и газодинамическими явлениями в шахтах (Новосибирск, 1976, 1979, 1981, 1987, Лени-набад, 1988), научно-практической конференции выпускников НГУ (Новосибирск, 1977), Всесоюзных конференциях по проблемам теоретической кибернетики (Новосибирск, 1977,1980), аэрологии современных горнодобывающих предприятий (Москва, 1980), по вопросам совершенствования и оптимизации горных работ (Новосибирск, 1985, 1Ш9), развитию производительных сил Сибири и задачам ускорения научно-техничес