Содержание к диссертации
Введение
1. Выбор модели и метода описания производственных систем (ПС) в условиях неопределенности внешней среды
1.1. Методология описания ПС 13
1.2. Классификация ПС 18
1.3. Описание исследуемого класса ПС 24
Выводы 34
2. Постановка задачи оптимизации траектории развития ПС в условиях неопределенности внешней среды
2.1. Содержательное описание траектории развития ПС 36
2.2. Формальная постановка задачи оптимизации траектории развития ПС 47
2.3. Информационное обеспечение задачи оптимизации траектории развития ПС 55
Выводы 65
3. Разработка метода и алгоритмов формирования решений для автоматизированной системы оптимизации траектории развития ПС в условиях неопределенности внешней среды
3.1. Анализ существующих методов оптимизации траектории развития ПС 67
3.2. Разработка метода формирования решений для оптимизации траектории развития ПС 79
3.3. Разработка алгоритмов формирования решений при оптимизации траектории развития ПС 95
3.4. Инструментальная поддержка задачи формирования решений при оптимизации траектории развития ПС 108
Выводы 115
4. Исследование и практическое применение метода и алгоритмов формирования решений для автоматизированной системы оптимизации траектории развития производственных систем в условиях неопределенности внешней среды
4.1. Принципы и уровни оценки эффективности метода и алгоритмов оптимизации траектории развития ПС 116
4.2. Оценка эффективности метода и алгоритмов оптимизации траектории развития ПС 122
4.3. Оптимизация траекторий развития реальных ПС 129
Выводы 141
Заключение 142
Список литературы 144
- Описание исследуемого класса ПС
- Содержательное описание траектории развития ПС
- Анализ существующих методов оптимизации траектории развития ПС
- Принципы и уровни оценки эффективности метода и алгоритмов оптимизации траектории развития ПС
Введение к работе
В нестабильной и неопределенной деловой среде и при нерутинной технологии работ предприятие должно быть более гибким, адаптивным, легко приспосабливаться к быстрым и частым внешним изменениям. В качестве элемента, оказывающего наиболее сильное влияние на уровень неопределенности внешней среды, целесообразно рассматривать нововведения, что естественно, т.к. процесс модификации предприятия определяется такими факторами, как быстро меняющийся потребительский спрос, расширение выпуска наукоемкой продукции и внедрение высоких технологий, распространение информационных технологий и телекоммуникаций, использование мощных информационных систем, повышение уровня интеллектуального потенциала, научных знаний и квалификации кадров, рост творческой активности и повышение ценности инновационной деятельности персонала. Внедрение нововведения всегда предполагает решения в условиях, для которых характерен некоторый уровень неопределенности, неуверенности со стороны внедряющей организации.
Этим вопросам посвящено значительное числр работ как отечественных /30, 33, 49, 66, 94, 105/, так и зарубежных авторов /3, 10, 23, 62, 73, 125, 134, 144/. Но как ни странно, роль неопределенности в большинстве моделей диффузии и адаптации не учитывается.
Изменения, прежде всего, будут затрагивать ведущую отрасль народного хозяйства - промышленность. Следовательно, предприятие должно рассматриваться, в первую очередь, как открытая производственная система (ПС), необходимым атрибутом которой является развитие, понимаемое не только как количественный рост, но и как изменение во времени ее технологической и организационной структуры и связей. В этом смысле все ПС динамичны, и их оптимизация должна обеспечивать выбор лучшей траектории развития в конкретных координатах времени.
Проявления фактора динамики должны в полной мере учитыватья в математических моделях для оптимизации ПС. В связи с этим такие модели должны удовлетворять следующим требованиям:
• проверять сбалансированность системы через некоторые малые временные этапы и выполнять условия перехода от этапа к этапу с тем, чтобы правильно учитывать изменение внешних связей;
• находить траекторию развития ПС, оптимальную для всего расчетного периода с учетом разновременности затрат, т.е. использовать динамический критерий оптимальности;
• учитывать дискретность развития объектов и нелинейность ряда технико-экономических зависимостей;
• допускать исследование окрестности 8-оптимального решения (зоны неопределенности оптимального решения) с целью обоснованного выбора траектории развития ПС.
Подавляющее большинство задач, соответствующих оптимизационным моделям ПС, принадлежит к классу NP-полных или NP-трудных. Многие NP-полные модели исследовались длительное время, однако эффективные алгоритмы их решения до сих пор не найдены /34, 108, 143/. С точки зрения практики вполне допустимы приближенные алгоритмы, позволяющие получить за полиномиальное время приближенные решения с требуемой точностью. Возможность получать решения практических задач большой размерности за допустимое время определила использование эвристических алгоритмов. В зарубежной и частично отечественной литературе термин "эвристический" получил несколько расплывчатое толкование. Условимся называть эвристическими только такие методы, которые на сегодняшний день не могут быть полностью записаны формально. Иначе говоря, применение эвристического метода не может быть полностью доверено ЭВМ и требует непосредственного вмешательства человека на некоторых стадиях решения задач/141/.
Точные методы могут использоваться в качестве вспомогательного инструмента лишь после того, как указана принципиальная стратегия поиска решения. Кроме того, точные методы не в состоянии отразить все качественные стороны проблемы, и поэтому могут быть использованы лишь на отдельных этапах подготовки решения.
Метод и алгоритмы оптимизации траектории развития ПС должны удовлетворять по крайней мере трем условиям:
• иметь наглядную интерпретацию, по возможности близкую существующим интуитивным представлениям о характере исследуемого процесса;
• обеспечить допустимость и преемственность поэтапных решений на промежуточных итерациях с тем, чтобы результат каждой из них был пригоден для практической реализации;
• иметь хорошую сходимость, по возможности малую трудоемкость расчета и позволять оценивать на каждой итерации степень приближения полученного решения к глобальному оптимуму ПС.
Данной тематике посвящено достаточно большое число работ /11, 15, 20, 27, 36, 74, 82, 119, 126, 132/. Однако основное внимание в них уделяется собственно модельным построениям - важной, но далеко не единственной части процедуры оптимизации. В то же время часто остаются в тени такие основополагающие вопросы, как насыщение моделей качественной и своевременной информацией, быстрая адаптация моделей к изменению реальных условий, внедрение и эффективность использования математического инструментария. Поэтому необходимо рассматривать всю технологическую цепочку оптимизации траектории развития ПС - от сбора необходимой информации до практического использования полученного решения.
Остановимся на понятии нечеткости информации, которое очень тесно связано с понятием структурированности задачи. Классификация Г.Саймона /171/ позволяет четко разделять возникающие задачи на структурированные, слабоструктурированные и неструктурированные. Задачи, возникающие при оптимизации траектории развития ПС в условиях неопределенности внешней среды являются слабоструктурированными, т.е. совмещают в себе знания ЛПР и возможности компьютера.
Таким образом, представляя промышленное предприятие в виде большой, сложной, динамической, многокритериальной, организационно-технической производственной системы с многоуровневой иерархической структурой управления, сразу следует сделать вывод о том, что комплекс средств и методов управления подобной системой не может быть простым. Он по сложности должен быть соизмерим с оптимизируемой системой. Современные методы преобразования предприятия связаны с информационными технологиями (ИТ), поэтому преобразования затронут не только организационно-технологическую структуру и процессы поддержки принятия решений, но и его информационную систему (ИС).
Эффективным инструментом управления подобными процессами является система поддержки принятия решений (СППР). В традиционном понимании СППР - это человеко-машинная технология принятия решений, включающая в себя методы и процедуры сбора, накопления, передачи, хранения и выдачи информации пользователю в удобном для него виде, работы с математическими моделями и комплексами моделей и т.п. Вопросы, связанные с созданием и использованием СППР достаточно полно разработаны в литературе /29, 38-40, 47, 89, 124, 137, 154, 158, 161-164/. Правда, нужно отметить, что методологии разработки таких систем, созданные в 70 - 80-е годы прошлого века и ориентированные на однородную внешнюю среду, устарели и неприемлемы для использования их предприятиями в условиях быстрой трансформации и непредсказуемости факторов внешней среды.
Поэтому естественно предложить расширительное толкование СППР: под принятием решений будем понимать формирование решений. Таким образом, система формирования решений (СФР) рассматривается не только как средство генерации и оценки альтернатив, но и как инструмент, способный помочь пользователю применять его неформальные знания, опыт, интуицию, а также способный обеспечить его консультированием и обучением на рабочем месте.
СФР - интерактивная автоматизированная система, использующая модели выработки решений, обеспечивающая пользователям легкий доступ к большой распределенной базе данных и предоставляющая им разнообразные возможности по отображению информации. В таком понимании СФР представляет собой совокупность следующих подсистем: комплекса распределенных технических средств, комплекса математических моделей анализа состояний и выработки решений, базы или баз данных, системы управления данными моделями, удобных для пользователя языков моделирования, обработки и отображения информации.
Ясно, что автоматизированные СФР (АСФР) имеют большую аналитическую мощность, чем другие системы: они построены с рядом моделей, чтобы анализировать данные; пользователь может изменять предположения и включать новые данные. АСФР помогает находить ответы не только на прямой вопрос "что, если", но и поддерживать такие виды анализа как, например, анализ примеров (оценка значений выходных величин для заданного набора значений входных переменных), параметрический анализ (оценка поведения выходных величин при изменении значений входных переменных), анализ чувствительности (исследование поведения результирующих переменных в зависимости от изменения значений одной или нескольких входных переменных), анализ возможностей (нахождение значений входной переменной, которые обеспечивают желаемый конечный результат), анализ влияния (выявление для выбранной результирующей переменной всех входных переменных, влияющих на ее значение, и оценка величины изменения результирующей переменной при заданном изменении входной переменной), анализ данных (прямой ввод в модель ранее имевшихся данных и манипулирование ими при прогнозировании), сравнение и агрегирование (сравнение результатов двух или более прогнозов, сделанных при различных входных предположениях, или сравнение предсказанных результатов с действительными, или объединение результатов, полученных при различных прогнозах или для разных моделей), командные последовательности (возможность записывать, исполнять, сохранять для последующего использования регулярно выполняемые серии команд и сообщений), анализ риска (оценка изменения выходных переменных при случайных изменениях входных величин).
Все вышеприведенные обстоятельства определяют безусловную актуальность проблемы разработки методов формирования решений для автоматизированной системы оптимизации траектории развития ПС в условиях неопределенности внешней среды.
Целью диссертационной работы является повышение качества принимаемых решений при определении наилучшего варианта развития предприятия на основе методов формирования решений для автоматизированной системы оптимизации траектории развития ПС в условиях неопределенности внешней среды.
Для достижения поставленной цели в рамках данной работы решаются следующие основные задачи:
• анализ современного состояния проблемы формирования решений при оптимизации ПС в условиях неопределенности внешней среды;
• выбор модели и метода описания ПС в условиях неопределенности внешней среды;
• постановка задачи оптимизации траектории развития ПС в условиях неопределенности внешней среды;
• разработка метода формирования решений для автоматизированной системы оптимизации траектории развития ПС в условиях неопределенности внешней среды;
• разработка алгоритмов, реализующих предлагаемый метод формирования решений при оптимизации траектории развития ПС в условиях неопределенности внешней среды;
• исследование эффективности предлагаемых метода и алгоритмов формирования решений при оптимизации траектории развития ПС в условиях неопределенности внешней среды;
• практическое применение разработанных методов формирования решений для автоматизированной системы оптимизации траектории развития ПС в условиях неопределенности внешней среды. Структура и объем работы.
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы (содержит 190 наименований). Объем диссертации составляет 148 страниц машинописного текста, в том числе 15 рисунков, 4 таблицы.
Во введении обосновывается актуальность исследования проблемы, а также описываются цели, задачи и основные результаты, полученные при реализации предложенного метода формирования решений для автоматизированной системы оптимизации траектории развития ПС в условиях неопределенности внешней среды.
В первой главе обосновывается выбор модели и метода описания ПС в условиях неопределенности внешней среды. Определяются и классифицируются основные характеристики ПС в условиях неопределенности внешней среды, предлагается методология описания ПС, позволяющая в полной мере исследовать данный класс ПС, дается краткое описание исследуемого класса ПС. Рассматривается содержательная сторона модели ПС - параметры, оказывающие влияние на выбор моделей ПС и методов решения задач. Исследуется структура процесса принятия решений как качественный этап построения ПС. Определяется цель работы и основные решаемые задачи.
Во второй главе подробно рассматриваются проблемы оптимизации траектории развития ПС в условиях неопределенности внешней среды. Приводится содержательное описание траектории развития ПС. Осуществляется формальная постановка задачи оптимизации траектории развития ПС. Описывается информационное обеспечение задачи оптимизации траектории развития ПС.
Формулируются основные особенности задачи оптимизации траектории развития ПС, формирующие требования к методу оптимизации.
В третьей главе подробно исследуются вопросы, касающиеся разработки метода и алгоритмов формирования решений для автоматизированной системы оптимизации траектории развития ПС в условиях неопределенности внешней среды. Анализируются существующие методы формирования решений. Предлагается метод оптимизации траектории развития ПС, адаптированный к исследуемому классу ПС. Описываются алгоритмы, реализующие предложенный метод. Описываются инструментальные средства поддержки задачи формирования решений для автоматизированной системы оптимизации траектории развития ПС.
В четвертой главе исследуется эффективность предложенного метода и алгоритмов формирования решений для автоматизированной системы оптимизации траектории развития ПС в условиях неопределенности внешней среды. Применение эвристических алгоритмов делает необходимым разработку методов определения эффективности эвристик, и в этой связи изложены возможные подходы к исследованию эффективности эвристических алгоритмов и предложена методика проведения такого исследования, синтезирующая эти подходы.
Оценивается эффективность метода и алгоритмов формирования решений для автоматизированной системы оптимизации траектории развития ПС.
В качестве специализированной АСФР использовался ПК «Project Expert».
Разработанный метод и алгоритмы использовались при оптимизации траектории развития ОАО «Увадрев» и показали эффективность предложенного метода и алгоритмов.
Описание исследуемого класса ПС
Кратко остановимся на основных характеристиках предприятия как ПС, функционирующей в условиях неопределенной внешней среды. Предприятие - иерархическая система, совокупность взаимосвязанных элементов: цехов, производственных участков, рабочих мест и т.п. Производственное, техническое, экономическое и организационное единство элементов системы обеспечивает взаимосвязь различных производственных процессов. Основное . назначение предприятия - выпуск определенной продукции как результат взаимодействия элементов производства в ходе производственных процессов. Таким образом, предприятие представляет собой, прежде всего производственную систему, которая характеризуется большим разнообразием ее элементов и структур. Признаки большой и сложной системы проявляются не только в том, что она имеет множество элементов, но и в наличии сложной их многосвязности.
Промышленное предприятие - динамическая система. Во-первых, реализуется производственный процесс. Во-вторых, со временем отдельные элементы предприятия изменяют свои характеристики (производительность, структура выпускаемой продукции, состав и связи элементов системы и т.п.).
Другой существенной особенностью предприятия является стохастический характер его элементов и всей системы в целом. Стохастика производственных мощностей и других элементов предприятия приводит к некоторой внутренней неопределенности системы, которая усугубляется зависимостью предприятия от внешних условий; последние, в свою очередь, тоже могут иметь стохастический характер. Предприятию свойственны черты экономической системы. Экономическая деятельность предприятия осуществляется в виде финансовых отношений с другими предприятиями, государством: реализация готовой продукции, закупка материальных ресурсов, взаимоотношения с бюджетом и т.п.
Другая важная характеристика, обусловливающая описание предприятия как сложной системы, - его многокритериальное . Деятельность предприятия оценивается многими показателями. При функционировании предприятия предполагается достижение сразу нескольких целей, каждой из которых ставится в соответствие один или несколько показателей, иногда противоречащих друг другу. Сложная зависимость между показателями затрудняет управление предприятием.
На функционирование предприятия большое влияние оказывает внешняя среда. Под внешней средой понимается часть окружающего ПС мира, с которой она взаимодействует как открытая система и адаптируется к ее требованиям. Оценим внешнюю среду по таким параметрам, как сложность, стабильность и неопределенность. Сложность определяется количеством и разнообразием элементов. Сложная деловая среда состоит из множества разнородных элементов, взаимодействующих друг с другом и влияющих на организацию, простая деловая среда - из трех-четырех групп однородных элементов. Стабильность и нестабильность связаны с тем, насколько динамичны элементы деловой среды. Нестабильная среда характеризуется частыми изменениями. Они могут быть связаны с действиями конкурентов, колебаниями спроса, появлением новых продуктов и технологий, могут носить непредсказуемый характер. Неопределенность означает отсутствие необходимой информации о деловой среде и непредсказуемость происходящих в ней изменений. Неопределенность значительно увеличивает степень риска.
Степень неопределенности внешней среды зависит от того, насколько она сложна и изменчива. Различные сочетания сложности и изменчивости деловой среды образуют четыре уровня неопределенности.
Если организация работает в простой и стабильной деловой среде, то ее неопределенность довольно низка. Если внешние условия достаточно определенны, то их можно заранее предвидеть, контролировать и учитывать при принятии решения. Сложная и стабильная деловая среда представляет для организации умеренную степень неопределенности. Элементы такого окружения не изменяются очень быстро и неожиданно. Умеренно высокая степень неопределенности характерна для простой и нестабильной среды. Несмотря на то, что на ПС оказывает влияние небольшое количество элементов внешнего окружения, их действия бывает очень трудно предсказать. Высокая степень неопределенности встречается в сложной и нестабильной деловой среде. Если у ПС такое окружение, то она сталкивается с большим разнообразием элементов, которые изменяются необычайно быстро и непредсказуемо. Естественно, не все элементы внешней среды имеют принципиальное значение для ПС. Поэтому важная часть анализа -выявление тех из них, которые играют значительную роль.
В качестве элемента, оказывающего наиболее сильное влияние на величину неопределенности (нестабильность) внешней среды, рассмотрим нововведения. Что естественно, т.к. процесс модификации организации определяется такими факторами, как: быстро меняющийся потребительский спрос; расширение выпуска наукоемкой продукции и внедрение высоких технологий; распространение информационных технологий и телекоммуникаций, использование мощных информационных систем.
Внедрение нововведения всегда предполагает решения в условиях, для которых характерен некоторый уровень неопределенности, неуверенности со стороны внедряющей организации. Но как ни странно, роль неопределенности в большинстве моделей диффузии и адаптации не учитывается.
Содержательное описание траектории развития ПС
Понятие траектории является одним из наиболее известных и общих средств описания изменения состояния любых, в том числе развивающихся систем. Под траекторией понимается функция, ставящая в соответствие отдельным моментам или интервалам времени различаемые состояния ПС. Для этого выделяется перечень существенных показателей, характеризующих систему. Один из них, например, время, выделяется в качестве параметра, и состояние системы в каждый момент времени описывается набором значений этих показателей. Геометрически каждому такому набору значений соответствует точка в пространстве показателей, а совокупность этих точек при всех значениях параметра образует траекторию.
Удобная с информационной точки зрения компактная форма представления данных в виде траектории является достаточно полным описанием полученного или желаемого решения. Если на этапе целеобразования желаемая траектория развития выбрана, то на последующих этапах процедуры при детализации показателей и ограничений она играет роль целевой установки (критерия качества функционирования ПС): максимально продвинуться по траектории к ее конечной точке. Другими словами, требуется обеспечить достижение заданных значений показателей, а если это не возможно, то приблизиться к ним, сохраняя намеченные траекторией пропорции развития. В первом случае цель достигнута, а в последнем случае полученное решение необходимо проанализировать и, возможно, пересмотреть, уточнить целевую установку.
Описание траектории развития ПС представляет собой поэтапную процедуру, обеспечивающую получение следующих четырех полностью взаимосвязанных классов решений.
1. Определение целей и задач, т.е. определение состояний, желательных для данной ПС, и определение времени, к которому должно быть обеспечено осуществление этих целей и задач.
2. Определение средств достижения этих целей и задач. Эти средства подразделяются на единичные действия, установившиеся способы действий, процедуры, программы и политики.
3. Определение ресурсов рабочей силы, материальных и финансовых ресурсов, необходимых для осуществления намеченных действий и политик; источников получения требуемых ресурсов; принципов распределения этих ресурсов между подсистемами ПС и ее различными программами.
4. Разработка организационной структуры и системы управления, способной обеспечить непрерывность процесса построения и оптимизации траектории развития ПС. В систему, обеспечивающую оптимизацию траектории должны входить три подсистемы: информационная система, собирающая данные и перерабатывающая их в информацию и предоставляющая эту информацию в требуемые сроки тем, кому такая информация необходима; система принятия решений, перерабатывающая информацию в инструкции и, наконец, система контроля, устанавливающая, какие из принятых в прошлом решений были ошибочны, и устраняющая их последствия, если такие решения уже были осуществлены. Система контроля должна также быть способна вскрывать благоприятные возможности, относительно которых нужно принимать решения, когда такие возможности возникают. Опишем траекторию развития ПС с помощью модели, которая известна в литературе как модель Андертона / 5/.
Будем считать, что ПС осуществляет регулирование двух типов. Она должна управлять доходами с тем, чтобы они оставались на некотором (предпочтительно стабильном) уровне, превышающем определенный минимум, гарантирующий безопасность. Во-вторых, она должна следить за соответствием качества выпускаемой продукции требованиям рынка.
Существует, по меньшей мере, два основных источника возмущений, против которых должно быть направлено это регулирование. Это колебания окружающей среды и циклы технических нововведений. Соответственно будем рассматривать два регулятора. Обобщенный и упрощенный вариант модели Андертона представлен на рисунке 2.1, где показано, как доходы порождают новые доходы и как этот поток зависит от рыночных условий и спроса. Согласно рисунку возмещение капвложений определяется соответствием между свойствами продукции (включая цену) и рыночным спросом (обусловленным экономическим климатом и имеющимися техническими альтернативами для удовлетворения одних и тех же нужд). Капвложения распределяются между освоением новой продукции, усовершенствованием старой продукции и повышением оперативности управления.
Анализ существующих методов оптимизации траектории развития ПС
Метод и алгоритмы оптимизации траектории развития ПС целесообразно анализировать с помощью теории сложности дискретных задач /25, 34, 80, 108/, которая позволяет классифицировать их по сложности. Алгоритм решения задачи считается эффективным, если число выполняемых им действий и объем требуемой памяти полиномиально зависят от размерности задачи. Размерность можно определить длиной входа, который описывает задачу. Алгоритм решения задачи является полиномиальным, если для любого ее входа время решения (число стандартных действий) равно 0(р(п)), где п - длина входа, р(») - полином. В теории сложности дискретных задач с оптимизационной проблемой связывается задача определения существования допустимого решения X со значением целевой функции f(X) f0 (в случае минимизации), f(X) f0 (в случае максимизации). Если такая задача (т.н. задача распознавания свойства) не может быть решена за полиномиальное время, то оптимизационная проблема также не может быть решена полиномиальным алгоритмом. В большинстве случаев оптимизационную задачу можно эффективно решить только тогда, когда существует полиномиальный алгоритм распознавания свойства.
Различают класс Р проблем распознавания свойств, которые решаются детерминированным алгоритмом за полиномиальное время, и класс NP, в который входят проблемы, решаемые недетерминированным алгоритмом за полиномиальное число действий. Для подавляющего большинства оптимизационных дискретных задач эффективные алгоритмы не известны. С точки зрения практики вполне допустимы приближенные алгоритмы, позволяющие получать за полиномиальное время приближенные решения с требуемой погрешностью. Можно считать эффективными приближенные алгоритмы, позволяющие за время р(п, І/є), р - полином, п - длина входа проблемы, получать приближенное решение с требуемой относительной погрешностью Є.
Ниже перечисляются некоторые наиболее часто используемые методы и алгоритмы, реализующие данные методы /15, 18, 21, 22, 36, 74, 85, 102, 121, 125/. Сначала рассмотрим эффективные точные методы. В основе метода динамического программирования лежит подход, позволяющий свести решение многомерной задачи к последовательности подзадач меньшей размерности и нахождению рекуррентных соотношений, позволяющих получать решение одних задач через другие. Возможности применения метода динамического программирования для задач выбора ограничиваются, в частности, следующими факторами: алгоритм на базе динамического программирования не всегда является эффективным алгоритмом, хотя при этом может быть существенно лучше метода полного перебора; задача выбора может быть устроена так, что нельзя найти "разумный" способ сведения ее к ряду подзадач.
Метод ветвей и границ представляет собой направленный перебор с отсеиванием "бесперспективных" вариантов. Перебор осуществляется на основе последовательного разбиения пространства решений (ветвления) и вычисления нижних границ стоимости решения с последующим отбрасыванием решений, для которых вычисленная нижняя граница превышает известную верхнюю. Следует подчеркнуть, что метод ветвей и границ - это не один специальный алгоритм, а широкий класс алгоритмов. Эффективность использования этого метода зависит от разработки способов разбиения пространства решений для данной задачи (стратегии ветвления) и тех алгоритмов, которые используются для вычисления оценок. Гибкость метода ветвей и границ, позволяющая учитывать специфику конкретной решаемой задачи комбинаторной оптимизации, и возможность использования внутри метода ветвей и границ других методов решения (для вычисления оценок), сделали этот метод наиболее популярным при решении задач комбинаторной оптимизации.
Еще одним подходом к решению NP-полных задач с позиции разработки точных алгоритмов является рассмотрение этих задач при наличии дополнительных ограничений, т.е. выделение полиномиально разрешимых частных случаев.
Отмеченные трудности построения эффективных точных алгоритмов приводят к необходимости рассмотрения приближенных или эвристических алгоритмов, которые не гарантируют получения точного решения, а находят только некоторое допустимое решение. Среди них можно упомянуть методы локальной оптимизации, градиентные алгоритмы, методы случайного поиска/7, 12, 20, 35, 74, 117, 141, 153/. Одна из основных проблем в теории приближенных алгоритмов -оценка их качества. Наиболее распространенным является следующий критерий качества: ( f(a) - f(b) )/f(b), где а и b - решения задачи, полученные соответственно некоторым приближенным и точным алгоритмами, a f(a) и f(b) - значения функционалов задачи на этих решениях. Одним из наиболее известных классов приближенных алгоритмов является класс градиентных алгоритмов. Более распространенным является применение градиентного алгоритма в некоторой сложной конструкции наряду с другими приемами. В последнее время получил развитие подход, связанный с разработкой s-оптимальных алгоритмов, т.е. приближенных алгоритмов с гарантированной верхней оценкой относительного отклонения получаемого решения от точного решения не более чем на заданное число..
Принципы и уровни оценки эффективности метода и алгоритмов оптимизации траектории развития ПС
В /50/ предложена методология экспертной оценки прикладных систем поддержки принятия решений, основными этапами которой являются экспертная оценка архитектуры системы; экспертная оценка организации данных; экспертная оценка программ. Используем эту методологию при исследовании эффективности АСФР при оптимизации траектории развития ПС в условиях неопределенности внешней среды. В отличие от классического варианта методологии, который используется на стадии проектирования системы, в данной работе методология применяется при добавлении к ней новых компонентов, когда основная часть прикладной системы (ПК «Project expert») уже функционирует.
Основное назначение процедуры оценки архитектуры АСФР -добиться высокого качества всех решений, получаемых при использовании системы. На данном этапе исследованию подлежат описание системы, стандарты предприятия или представления о приемлемом уровне производительности, узкие места системы, а также факторы, определяющие показатели готовности, производительности и гибкости системы.
При анализе эффективности организации данных рассматриваются различные способы удовлетворения требований пользователей средствами выбранной модели данных. Хотя производительность, гибкость, готовность и ориентированность на пользователя - базовые характеристики, исследуемые в процессе оценки системы, существуют и такие важные ее характеристики, как длительность разработки, затраты, связанные с обеспечением функционирования, аспекты физической организации и производительности программирования.
При анализе эффективности программного обеспечения основное внимание уделяется вопросу о том, следует ли разрабатывать программное обеспечение самостоятельно или приобрести уже готовое. Исследуемая практическая АСФР относится к одному из наиболее общих и сложных типов, определяемых следующими основными характеристиками. Информационная структура: комплексная многоуровневая сетевого типа с нелинейными связями. Задача (формирование траектории развития ПС): сложная, частично формализуемая, включающая исследовательские и практические подзадачи. Исполнители: коллектив исполнителей и технических средств, имеющих многоуровневую организационную структуру. Методы, алгоритмы: для исследовательских подзадач - формальные, для практических - из заданного класса дескриптивных, позволяющих работать с информацией по частям и удовлетворяющих ряду специальных требований.
Процедура: имеет общую последовательно-параллельную структуру, является итерационной человеко-машинной с многосторонним взаимодействием. Основным назначением АСФР является: информационное обеспечение и решение (в режиме диалога и многостороннего взаимодействия с ЛПР) каждой отдельной исследовательской или практической задачи, возникающей в процедурах; обеспечение их связи (согласования) в рамках каждого этапа процедуры; обеспечение информационной преемственности этапов процедур с первоочередной ориентацией на заключительный этап - управление реализацией программы развития ПС.
Общим требованием к АСФР, определяющим ее жизнеспособность (внедряемость), является обеспечение эффективности и удобства ее практического использования (т.е. возможности получения более предпочтительных решений и сокращения затрат труда и времени при условии органичного ее включения в естественные для J11 IP процедуры). Кроме того, важным общим требованием является возможность развития, оперативной модернизации и адаптации АСФР в процессе ее эксплуатации (расширение перечня задач, данных, их углубление, совершенствование и замена алгоритмов и т.п.).
Уточним, что понимаем под основными элементами диалоговой ЧМС, включающей в себя пользователя, ЭВМ и процедуру их взаимодействия.
1. Человек-пользователь (в частности J11 IP), в функции которого входит связь ЧМС с окружающей средой (анализ исходных данных и результатов, ответственность за результаты и т.п.), постановка и корректировка целей и задач, выбор метода решения, оценка и выбор варианта решения задачи в целом и т.п.
2. ЭВМ (точнее, комплекс технических средств и математического обеспечения), основной функцией которой является автоматизация части формализуемых операций, входящих в процедуру формирования, оценки и выбора решений. В данном разделе, если не оговорено специально, под ЭВМ будем понимать лишь ту часть математического обеспечения, которая связана с моделями и алгоритмами формирования и принятия решения. Каждая такая модель состоит из описания объекта, критериев и алгоритмов, осуществляющих выбор наиболее предпочтительного решения.
3. Процедура взаимодействия, основной функцией которой является регламентация обмена информацией между ЛПР и ЭВМ, приводящая к решению исходной задачи за приемлемое время. В общем случае процедура носит итеративный характер и состоит из элементарных циклов диалога. В сформулированы требования к ЧМС. Требования к результату ЧМ процедуры решения задачи можно сформулировать следующим образом: 1. Использование информации в содержательных категориях; 2. Итерационный характер процедуры, удобство корректировки данных и перестройки модели; 3. Отсутствие исключенных решений; 4. Возможность получения тестового решения; 5. Сходимость итерационной процедуры к наиболее предпочтительному решению за приемлемое число итераций; 6. Контролируемость ЧМ процедуры со стороны J11 IP: а) содержательная интерпретируемость моделей; б) алгоритмов; в) регулируемая степень автоматизации.
Известные методы частично или полностью не удовлетворяют перечисленным выше требованиям. Это означает, что для ЛПР такая ЧМС неудобна информационно, не вписывается в естественную структуру его деятельности при решении задач, сужает возможность его выбора, что ведет к снижению эффективности решений, перемещению ответственности, т.к. ЭВМ без ведома ЛПР отсеивает часть решений, к неспособности получить решение тестовой задачи, что вызывает недоверие ЛПР, не гарантирует сходимость, т.е. через 10-20 итераций ЛПР может получить решение, худшее, чем в начале, и вообще не имеет уверенности в возможности получения предпочтительного с его точки зрения решения, что может вызвать нежелание продолжить диалог, не дает возможности контроля за ходом решения, что вызывает недоверие и лишает возможности содержательно аргументировать выбор решения. В таблице
