Графические средства в интерактивном моделировании 7.1. диалоговые системы

Графические средства в интерактивном моделировании 7.1. диалоговые системы

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

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

ясность поведения системы для пользователя в любой стадии диалога;

простота пользования;

простота обучения работе с системой;

доступность системы в любой необходимый пользователю момент;

обеспечение идентификации и защиты данных;

самостоятельность, т. е. способность системы самостоятельно разбираться в «нештатных» ситуациях.

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

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

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

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

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

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

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

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

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

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

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

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

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

7.2. Сетевая модель

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

определить ближайший возможный срок завершения проекта;

выяснить, выполнение каких работ определяет завершение проекта;

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

Сетевые модели — это эффективный инструмент разработки календарных графиков, позволяющий осуществить:

оптимальное распределение имеющихся ресурсов (либо сводящее к минимуму потребности в них при своевременном осуществлении проекта, либо приближающее дату этого настолько, насколько допускают их наличные объемы);

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

поиск наилучших путей компенсации возникающих отклонений.

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

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

Система СПУ позволяет:

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

выявлять и мобилизовывать резервы времени, трудовые, материальные и денежные ресурсы;

осуществлять управление комплексом работ по принципу «ведущего звена» с прогнозированием и предупреждением возможных срывов в ходе работ;

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

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

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

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

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

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

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

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

Яуть — это последовательность работ, соединяющих начальную и конечную точки вершины.

Визуально сетевая модель, называемая иногда стрелочной диаграммой или сетью, это — множество точек-вершин (і 0,1, ...j, ...n) вместе с соединяющими их ориентированными дугами. Каждая из них как направленный отрезок имеет начало и конец, причем модель СОДерЖИТ ЛИШЬ ОДНУ Пару СИММетрИЧНЫХ ДУГ (Pj,Pj) И (Pj,Pj).

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

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

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

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

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

Пример расчета критического пути в приведенной на рис. 7.1 сетевой модели.

Наиболее эффективно при решении данной задачи является использование аппарата динамического программирования.

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

Первому событию сетевой модели присвоить номер этапа «О».

Событиям, непосредственно следующим за нулевым этапом, присвоить номер этапа «1».

Событиям, непосредственно следующим за первым этапом, присвоить номер этапа «2» и т. д. до последнего события сетевой модели.

Работу данного алгоритма можно наглядно проиллюстрировать при помощи нижеприведенной схемы:

©©©©©©©©

Трансформированный таким образом сетевой график будет иметь следующий вид (рис. 7.2).

Критический, т. е. самый длинный путь от начального события к конечному может быть рассчитан по следующей рекуррентной формуле:

F, = max{x;>у + Fj } при Fкон = 0, где х,^ — продолжительность работы между двумя смежными событиями і и j; F^Fj) — самый продолжительный путь от события до конечного события.

Решение модели

Первая итерация (4-й этап):

F8 = 0.

Вторая итерация (3-й этап):

F5 = max{x58 + F8} = 2.

F7 = max{x78+F8} = 3.

Третья итерация (2-й этап):

F, = max і Хз5+^5 Umax|4 + 21 = 8. x„+Fr [5 + 3J

F. => max^ Hmax^ } = 7.

Четвертая итерация (1-й этап):

Пятая итерация (0-й этап):

Таким образом, критическим в рассмотренной сетевой модели является путь через события 1, 3, 7, 8 с общей продолжительностью 15 единиц.

Читателям пособия предлагается самостоятельно найти критический путь на следующей сетевой модели (рис. 7.3).