Файл: Клыков, Ю. И. Ситуационное управление большими системами.pdf

новка задачи линейного программирования. Современ­ ные методы решения задач линейного программирования можно разделить на два класса: конечные, т. е. гаранти-

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

задач управления большими системами эта величина до­ стигает нескольких сот и тысяч, что исключает возмож­ ность использования для их решения современных ЦВМ, позволяющих эффективно решать задачи управления, размерность которых не превышает ста. В ряде случаев удается свести к задаче линейного программирования многоэтапные процессы. Если критерий и ограничения являются нелинейными функциями, а процесс одноэтапный, то возникает задача нелинейного программирова­ ния, методов решения которой в общем виде не суще­ ствует. Специальные методы решения задачи нелинейно­ го программирования используются при определенных ограничениях, например когда функция Q дважды диф­ ференцируема, когда функция Q вогнутая и ограничения являются тоже вогнутыми функциями, если Q — поли­ ном второй степени относительно х и ограничения ли­ нейны и т. д. Возникающие здесь трудности имеют такой же характер, как и для линейного программирования. Для исследования многоэтапных процессов используется динамическое программирование. Общая постановка за­ дачи динамического программирования выглядит сле­ дующим образом. Из множества допустимых решений (законов управления) R найти такое решение Ri^R, ко­ торое переводит систему из начального состояния s0 eSo в конечное sI ( eSK так, чтобы некоторый критерий Q(R)

обращался в максимум, т. е.

(£* = m a x {Q(R)}.

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

10

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

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

3.) небольшое число возможных фазовых траекторий (десятки, сотни);

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

Основные трудности, возникающие при использова­ нии динамического программирования для решения за­ дач управления, связаны с большой размерностью фазового пространства, в котором необходимо искать опти­ мальное управление. Область поиска решений для слож­ ных систем, как правило, превышает 21 0 0 . Попытка вне­ сти в динамическое программирование так называемые «эвристики», сокращающие объем просматриваемых ва­ риантов, не является 'выходом из положения, так как всегда можно так увеличить сложность системы, что вве­ денные «эвристики» окажутся бессильными.

11

Многие задачи математического программирования могут быть решены с использованием принципа Л. С. Понтрягина [Л. 5]. Этот метод предназначен для решения задач математического программирования не­ прерывного характера. Суть метода состоит в таком ре­ шении системы обыкновенных дифференциальных урав­ нений, описывающей состояние объекта управления, при котором допустимые решения выбираются на каждом шаге из условия максимизации некоторой вспомогатель­ ной функции. С некоторыми видоизменениями этот прин­ цип применим и для решения дискретных задач. В этом случае его называют дискретным принципом максимума. Принцип максимума и динамическое программирование сводимы друг к другу, хотя и используют качественно разный подход. Динамическое программирование требу­ ет исследования с помощью поиска всей области измене­ ния переменных на одном шаге с .последующим выбором оптимального пути между шагами. Принцип максимума основан на нахождении сразу всего оптимального пути между шагами с последующим его улучшением путем удовлетворения граничных условий. При машинной реа­ лизации этого метода возникают принципиальные труд­ ности временного характера, связанные с необходи­ мостью решать краевую задачу. В настоящее время уста­ новлена связь динамического программирования и ди­ скретного принципа максимума с задачами линейного, нелинейного и целочисленного программирования.

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

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

12

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

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

Этот недостаток особенно ощутим в случае высоко- \ размерных задач, когда универсальные «эвристики»ста- ' новятся малоэффективными (например, понижение раз­ мерности задачи с 2 1 0 0 0 до 21 0 0 не обеспечивает возмож­ ность практического решения задачи на ЦВМ), а поиск специализированных «эвристик» является искусством, не всегда приводящим к решению.

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

13

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

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

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

Всякую систему можно представить как совокупность

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

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

14 .

)

построения языка имитации, мы рассмотрим на приме­ рах основные принципы решения задач управления сложными системами, положенные в основу языка. Подробное изложение этих принципов дано в [Л. 6].

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

дачи управления в соответ­ ствии с поставленной целью и оценочным функционалом.

Эта модель используется затем для управления объектом. Команды управления (решения) зачастую являются . указаниями на установление пространственно-временных и других отношений между объектами. В общем случае команда управления может указывать только характер отношения, а способ установления отношения формиру­ ется объектом, которому адресована команда. Например, диспетчер аэропорта В, которому адресована команда «самолет А посадить на аэродром В», решает задачу включения А в систему обслуживания аэродрома В.- После решения этой задачи диспетчер аэропорта форми­ рует команду передачи посадочных характеристик на борт самолета. В соответствии с этой командой пилот устанавливает органы управления самолета в положе­ ние, обеспечивающее посадку самолета на взлетно-поса-. дачную полосу аэродрома. Реализация исходного пространственно-временного отношения вызвала необхо­ димость решения нескольких задач, связанных с перемеще­ нием самолета в район аэродрома и его посадкой. В слу­ чае иерархического управления решения, принимаемые1 человеком на отдельных уровнях системы, формируются: на основе анализа состояний этих уровней и команд \ управления, поступающих из вышележащих уровней.;

15