Прямые и обратные задачи информационных технологий

Исследования операций

 

Основные понятия и определения

Операция – последовательность действий, объединенных единым замыслом и общей целью.

Показатель эффективности – количественный критерий-мера эффективности операции и ее этапов. Поиск его максимума будем обозначать W => max, минимума W => min. Если при исследовании операции учитываются случайные факторы, то часто за показатель эффективности принимают его математическое ожидание (МО), при релейной («да-нет» постановке задачи) за показатель эффективности принимается вероятность достижения цели Р(А).

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

Если переменные или их часть имеют различную меру, то задача еще более осложняется. Так что в настоящее время нет достаточно удобных и общих методов ее решения. В частных случаях исследуются альтернативные варианты, строятся ранжированные последовательности, бинарные отношения, логики предпочтения и выбора доминантных вариантов (методы «Макбет», «Electre») и др.

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

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

Часто качественное решение во многом зависит от автора.

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

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

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

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

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

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

Фазовые координаты – переменные, которые составляют вектор х (х(1), х(2), … х(n)), определяющий многомерное с размерностью n поле переменных, на котором изучается функционирование исследуемой системы.

Управления – u(j) удобно также рассматривать, как вектор размерности m. m – число управлений.

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

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

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

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

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

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

Аналитические и статистические модели информационных технологий - рассмотренные выше подходы основаны на моделях составляющих два класса:

1. Аналитические модели.

2. Статистические модели.

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

Вторые - статистические модели дают большую точность, поскольку практически не требуют упрощающих предположений. Их недостаток в том, что они имеют меньшую «обзорность» и требуют дополнительных, часто весьма громоздких, алгоритмов поиска оптимальных решений. Пролонгирование результатов требует дополнительных, часто весьма объемных, расчетов на ЭВМ.

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

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

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

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

Многокритериальные задачи в информационных технологиях.

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

Простейшее решение этой проблемы, широко используемое в настоящее время состоит в том, что задается структура эффективности (РЭ).

Например, в виде дроби W=A(x_i)/B(x_j)

В числитель входят переменные x_i, рост которых увеличивает W, а в знаменатель x_j, которые снижают W.

Распространена также запись W в виде линейной функции по х.

W=Σ α х_к

С весовыми коэффициентами α =α _к , или, что расширяет возможности, но осложняет поиск решения, с весовыми функциями. Тогда W запишется так:

W=Σ f_кх_к

Перспективным подходом является использование нелинейных f_к , зависящих от нескольких переменных, а также использование рядов, записанных в удобном ортонормированном базисе.

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

В заключение следует отметить, что при поиске оптимальных решений, положительный результат дает решение прямых задач информационных технологий и наработка опытным путем множества возможных решений. Например, в поле показателей эффективности W₁, W₂ («плоская задача»). Среди них выделяются эффективные решения – такие, которые являются доминирующими (не улучшаемыми для пар каких- либо частных ПЭ: W₁, W₂) см.рис*

Они образуют множество Парэто, так называемое «переговорное множество», которое существенно сокращает число возможных решений и упрощает выбор оптимального из них лицом, принимающим окончательное («замыкающее») решение (ЛПР).

 

Основные принципы исследования сложных систем (системного подхода)

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

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

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

Какой из этого выход? Разумеется, не в жестком планировании работы всей системы в целом, при котором верхнее звено управления планирует работу всех без исключения своих звеньев (элементов). Это не только невозможно – к этому не надо и стремиться. Главный принцип управления сложной иерархической системой состоит в том, чтобы каждое вышестоящее звено давало задания (управляло) нижестоящим уровнем в соответствии с примыкающими к нему связями, которые определяются иерархической структурой: «вниз по вертикали» («по этажам») и «согласовывало» свои действия по линиям связи своего уровня («этажа»).

При этом если возможно, желательно функциональное («эластичное») представление связей.

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