Содержание к диссертации
Введение
ГЛАВА I. Множества достижимости многосвязных систем со связи) по управлению
I. Описание множества достижимости 15
2. Применение к задаче о встрече 30
3. Задача терминального управления в стационарном случае 32
4. Задача терминального управления в нестационарном случае. 38
ГЛАВА II. Множества достижимости систем с распределенными параметрами
I. Предварительные сведения 45
2. Теорема о структуре множеств достижимости 49
3. Множества достижимости некоторых классов систем в банаховом пространстве 63
ГЛАВА III. Управляемость и наблюдаемость жнейных и бижнейных систем в гильбертовом пространстве
I. Об одном критерии управляемости 79
2. Теорема двойственности для линейных систем 82
3. Теорема двойственности для билинейных систем 86
ГЛАВА ІV. Прикладные задачи
I. Задача построения календарных план-графиков работы взаимосвязанных производств в системах оперативно-диспетчерского управления технологическими комплексами 91
2. Об одной задаче распределения ресурсов вычисли тельной системы 94
3. Задача о динамическом распределении сырья /энергии/ 98
4. Некоторые задачи оптимального распределения ресурсов при выполнении конплекса работ, связан ных сетевым графиком 102
5. Об одной задаче управления объектом с распреде ленными параметрами 114
Заключение 120
Указатель основных терминов и обозначений 122
Литература
- Задача терминального управления в стационарном случае
- Множества достижимости некоторых классов систем в банаховом пространстве
- Теорема двойственности для билинейных систем
- Об одной задаче распределения ресурсов вычисли тельной системы
Введение к работе
В настоящее время задачи исследования и оптимизации динамических процессов приобретают все более важное значение. Это , связано как с большим теоретическим значением этих задач, их связями со многими областями математики, механики и техники, так и с их важнейшими приложениями в экономике и производстве.
Динамика процесса описывается обычно дифференциальными и разностными эволюционными уравнениями, так как этот аппарат является достаточно гибким, позволяет адекватно описывать различные практические ситуации и достаточно хорошо изучен.
Важнейшей характеристикой такой системы является множество („ ( Т") , называемое множеством достижимости из начального состояния У0 за- время Т. Это множество равно замыканию в норме соответствующего пространства множества значений в момент Т решений уравнения /0.Ї/ с начальным данным U0 , соответствующих всевозможным допустимым управлениям.
С изучением этого множества связаны многие вопросы струк - 5 турной теории систем, такие как, например, управляемость, наблюдаемость, реализуемость уГ 3, 16, 39, 53 ] . После работ Калмана Г 28 J для линейных систем связь этих понятий для различного рода систем с дискретным временем получила развитие в рамках теории категорий [ 3J . .Для систем с непрерывным временем эффективным оказался дифференциально-геометрический подход. Обзор важнейших результатов этого направления можно найти в 2, 13, 33, 39j . В этих обзорах указаны также некоторые возможности использования множеств достижимости для задач оптимального управления.
Изучение свойств множеств достижимости /даже оценочных/ позволяет создавать эффективные алгоритмы оптимального управления, решать задачи о накоплении возмущений и многие другие.
Однако на сегодняшний день вопросы о построении множеств достижимости в различных ситуациях и, особенно, о применении этих множеств для решения динамических оптимизационных задач изучены весьма слабо. Это объясняется тем, что в общем случае структура этих множеств сложна и задача об их построении едва ли допускает простые конструктивные решения /отметим в этом плане работу j[33]J, в которой много внимания уделяется топологическим свойствам множеств достижимости/.
Целью настоящей работы является выделение частных случаев систем вида /ОЛ/, для которых такое построение возможно, По мнению автора, выделенные системы имеют важное теоретическое и прикладное значение.
У систем этого класса динамика задается в виде зависимости скорости процесса от выделяемых ресурсов управления, а на управления наложены нестационарные ограничения достаточно общего вида.
Характерным для этого класса является рассмотрение систем с достаточно сложной динамикой, но без ограничений на управление. В этом классе наибольший интерес представляют системы с распределенными параметрами, описываемые уравнениями с частными производными. В этом случае п -операторы /вообще говоря, нелинейные/ в банаховом пространстве У J , причём +о не предполагается непрерывным и может быть, например, дифференциальным оператором по пространственным переменным; tc ,(- 0- непрерывные операторы.
Изучению систем вида /0.3/ и некоторых их обобщений /которые мы также относим ко второму классу/ посвящена глава П.
Отметим, что системы вида /0.3/ с сосредоточенными параметрами интенсивно изучались, и имеющиеся результаты описаны в упоминавшихся выше обзорах. Поэтому целью настоящей работы было изучение систем с распределенными параметрами. Однако применяемый подход оказался эффективным и в конечномерных пространствах и привел к некоторым новым результатам даже для таких систем.
Что касается систем вида /0.2/, у которых правая часть не зависит от искомой функции Ч, С% ) , то они исключают возможность рассмотрении уравнений с частными производными, и для них наибольший интерес представляет случай конечномерного пространства. Основные результаты переносятся на бесконечномерный случай без особого труда. Поэтому в главе I рассматриваются только системы в конечномерном пространстве.
Общий подход при выделении систем с относительно простой структурой множества достижимости в главах I и П состоит в следующем. На основании изучения систем данного класса описывается структура множества, содержащего йь„ (Т) и далее формулиру-ются условия, при которых это множество /будем называть его верхней оценкой/ совпадает с fdua ( ).
В главе I эти верхние оценки задаются в виде некоторой системы неравенств, в главе П-в виде интегральных многообразий, порожденных инволютивной системой векторных полей, которая строится по системе /0.3/. Эти многообразия можно построить конструктивно, если имеется возможность находить общие решения эволюционных уравнений с оператором /с- , і - ОД,.... в правой части. В настоящее время такие решения построены для многих задач математической физики /см., например, [14 J /.
В случае, когда f0 - оператор в банаховом пространстве, не являющийся непрерывным, для соответствующих построений используется специальный вариант бесконечномерной дифференциальной геометрии, разработанный С.Н.Самборским 48 - 5ї] . При этом для систем, описываемых уравнениями с частными производными, обнаружены эффекты, которые не имеют место для случая систем, описываемых обыкновенными дифференциальными уравнениями. В частности, для линейных систем множество достижимости из 0 зависит от времени, откуда, как показано в главе Ш, такие свойства линейных систем, как управляемость и наблюдаемость зависят от времени, управления и наблюдения соответственно. В имеющихся работах, касающихся указанных вопросов для систем в частных производных это время принимается либо 0 либо сх ї, 58, 68 J , хотя рассматриваются несколько более общие вопросы.
За рамками работы остался обширный класс систем, динамика которых описывается уравнениями /0.1/, в правую часть которых входит искомая функция и(-) и на управления наложены ограничения. По-видимому, множества достижимости систем этого класса имеют гораздо более сложную структуру. Из работ, проводившихся в этом направлении, необходимо отметить два цикла статей Г 30 J и 55] , в которых изучаются линейные системы с ограничениями в виде эллипсоидов 55 ] и параллелепипедов 30 ] . Применяя различные оригинальные подходы, авторы строят эллипсоид 55 ] ж параллелепипед f30] , которые содержат множество &и„(Т) . Анализ этих результатов показывает, что даже для линейных систем с простейшими ограничениями /эллипсоиды, параллелепипеды/ множество Йи, ( Г) имеет довольно сложную структуру, и относительно просто удается построить лишь оценки этих множеств специального вида, зависящего от характера ограничений. Поэтому настоящая работа / целью которой является точное описание множеств IRu (Т) ограничивается рассмотрением систем вида /0.2/ и /0.3/. Традиционным является применение множеств достижимости для решения задач структурной теории систем, в частности, таких вопросов, как управляемость, наблюдаемость, реализуемость/"16, 53] . В настоящее время сложилось представление о двойственной связи управляемости и наблюдаемости линейных систем с непрерывным временем как о представлении фазового пространства системы в виде прямой суммы двух подпространств УЗ - $Зи Ф Jo , причём исходная линейная система управляема тогда и только тогда, когда Jou — JOt а сопряженная система наблюдаема тогда и только тогда, когда Лн —О [ 53 ] . Аналогичное представление можно получить для билинейных систем f66 ] . Результаты такого рода называются теоремами двойственности.
В случае систем с частными производными понятия управляемости и наблюдаемости, как уже указывалось, вообще говоря, зависят от времени. Это обстоятельство должно учитываться в формулировке теорем двойственности. Кроме того, для нелинейных /в частности, билинейных/ систем с частными производными наблюдаемость зависит от способов наблюдения. Поэтому возможны различные разложения фазового пространства, соответствующие этим способам. Некоторые из этих вопросов решаются в главе Ш.
Важнейшими приложениями множеств достижимости являются задачи оптимального управления. Если множество ew,T) описывается системой уравнений и неравенств или является многообразием /с краем или без края/, допускающим достаточно простую параметризацию, то естественным является его использование в задачах терминального управления и оптимального быстродействия.
Применение описанного подхода оказывается эффективным в некоторых динамических задачах оптимального проектирования, для которых характерна простая динамика и сложные:, часто нестационарные ограничения. В качестве примеров можно привести системы управления потоками газа в магистральных газопроводах; объекты, движущиеся на плоскости; системы оперативного управления сложными технологическими комплексами; задачи распределения ресурсов; практические задачи математической экономики и многие другие. Кроме того, модель /0.2/ может быть использована при построении программных управлений для устойчивых систем автоматического управления с малым перерегулированием С 52 2 . Сложные ограничения на управление и фазовые ограничения не позволяют эффективно применять для решения этих задач принцип максимума Понтрягина и другие классические методы оптимального управления. Во многих публикациях постановка задачи либо сильно упрощается, что не всегда допустимо для адекватного описания, либо для её решения применяются эвристические подходы.
Применяя точные описания множеств достижимости, можно лучше понять структуру задачи, исследовать её свойства и разработать алгоритмы решения, использующие схемы /0.4/, /0.5/. Модели прикладных задач, которые эффективно решаются описанным подходом, приведены в главе ІУ.
Рассмотрим подробнее содержание диссертации по главам.
Первая глава посвящена системам вида /0.2/.
В § показано, что задачи управления для таких систем можно свести к каноническому виду, в котором F (t3 V( t)j — и it) t а множество v(t) - выпукло и может быть задано в виде конечной или бесконечной системы линейных неравенств: В " - eCt), Далее для таких систем указаны условия на матрицу В и вектор-функцию &(•) , при которых множество /tL (Т) имеет вид:
Для систем, удовлетворяющих этим условиям, предлагается простой алгоритм нахождения управления, переводящего систему из состояния Ц0 в заданное состояние У . (Т) за время Т. Этот алгоритм при кусочно-постоянной функции SO) сводится к последовательному решению систем линейных неравенств. Полученные результаты используются в §§ 2-4 для решения задач оптимального управления системами, удовлетворяющими укзанным условиям и для построения приближенных алгоритмов для общего случая систем /0.2/, заданных в каноническом виде.
Изучению множеств достижимости систем второго класса посвящена глава П.
В § I приводятся необходимые сведения о свойствах системы векторных полей в банаховом пространстве, содержащей одно векторное поле f0 , не являющееся непрерывным, и связанной с ней симметричной управляемой системой вида:
В частности,для таких векторных полей при некоторых ограничениях вводится операция скобки Ли и понятие инволютивности. Результаты этого параграфа, принадлежащие С.Н.Самборскому, необходимы для дальнейшего изложения. Более подробно они описаны в [48 - 5ї] .
В § 2 формулируется и доказывается теорема о структуре множества достижимости системы /0.3/ при условиях, наложенных на алгебры Ли, порожденные векторными полями f0 и fL . Указанные условия применимы и для систем в конечномерном пространстве. В этом очень частном случае показано, что они являются менее жесткими, чем известные условия Хиршона [2, ЇЗ, 62 J .
Глава Ш посвящена приложению результатов главы П к некоторым вопросам структурной теории линейных и билинейных систем в гильбертовом пространстве. Решение этих вопросов принципиально отличается от аналогичной теории в конечномерном пространстве, о чём упоминалось выше.
Для билинейных систем вводятся различные определения наблюдаемости в зависимости от способа наблюдения /параллельная за время Т, соответствующая параллельному наблюдению состояний системы, при всевозможных управлениях; мгновенная в момент Т, соответствующая мгновенному наблюдению состояний системы свободно /то есть при нулевых управлениях/ эволюционирующей до момента Т; последовательная за время Т, соответствующая наблюдениям, не изменяющим траекторию свободного движения системы после момента Т/. Все эти определения при Т=0 и, следовательно, для конечномерного случая, эквивалентны.
Прикладные модели, на примерах которых показаны возможности применения полученных в работе результатов для решения практических задач, приведены в главе ІУ.
aВ §§ 1-4 рассмотрены модели, сводящиеся к системе /0.2/. Применяя схемы /0.4/, /0.5/ и используя полученные в главе I описания множеств достижимости, эти задачи могут быть решены методами оптимизации. При этом некоторые динамические задачи сводятся к классическим моделям исследования операций. Например, модель рас-мотренная в § 3 сводится к задаче размещения производства [38 ] , возможно, с дополнительными ограничениями на количество предприятий, и некоторым её обобщениям. Алгоритмы решения таких обобщенных задач приведены в работе автора /с Ю.А.Заком и Н.Л.Кирьян/ [9].
В § 4 показана возможность учёта фазовых ограничений, заданных сетевым графиком.
В § 5 на простом примере показана возможность использования в задачах управления множеств достижимости систем, описываемых уравнениями с частными производными, изученных в главе П. Для наглядности примеру придан экологический смысл. Заметим, что этот пример носит лишь иллюстративный характер.
Основные результаты диссертации и её приложения опубликованы в статьях [ 5 - її, 24, 4Ї, 42 J .
Результаты работы докладывались в ХУ Воронежской зимней математической школе /198I/, на 41-й научной конференции ЛГУ им. П.Стучки /Рига, 1982/, Всесоюзном семинаре "Применение.автоматизированных систем в проектировании объектов строительства"/Ново-сибирск, 198I/, а также на семинарах в Институте проблем управления, Институте кибернетики АН УССР, Институте математики АН УССР, на кафедрах прикладной математики и АСУП Киевского политехнического института.
Задача терминального управления в стационарном случае
Задача /1.33/ - /1.37/ содержит (УІ + І) целочисленных переменных и (П- -/) действительных переменных. Размерность задачи может быть снижена при дополнительном предположении: число используемых значений вектора управляющих воздействий.не может быть более, чем к ( к п) .в этом случае М к .
Так, при к = I задача /1.33/ - /1.37/ превращается в задачу целочисленного линейного программирования с /? переменными.
В [ 23 ] изучаются свойства класса задач, к которому относится задача /1.33/ - /1.37/ и предлагается один из алгоритмов их решения на основе метода ветвей и границ и статистических методов поиска.
В случае отсутствия фазовых ограничений и ограничений на правом конце получаем задачу /1.33/, /1.34/, /1.37/. Очевидно, что в оптимальном решении этой задачи только одно из чисел JL-L, L = Ї,..., И + отлично от 0. Поэтому задача сводится к следующей задаче линейного целочисленного программирования: (Ат9 U) УУІСП } DU d , U Z Если дискретное множество Ь с задано перечислением элементов Ьс {U\,. . UM}, то задача терминального управления сводится к задаче линейного программирования относительно переменных Л-с , = Ї,..., Af .
Многие задачи, в частности одна задача распределения ресурсов вычислительной системы, рассмотренная в главе ІУ, сводятся к задаче /I.3I/ в случае, когда все переменные являются непрерывными и ограничения не содержат связных компонент,, принадлежащих подмногообразию,размерности меньшей, чем размерность пространства, переменных. При использовании для решения таких задач статистических методов поиска целесообразно применять адаптивные алгоритмы, позволяющие существенно сократить время получения решения, близкого к оптимальному. Исследованию одного : класса таких адаптивных алгоритмов посвящена статья автора /с Ю.А.За- 1 ком/ [ 24] .
Рассмотрим теперь одно обобщение задачи /1.24/ -- /1.28/ в случае, когда \л/ — W (" ) , которое легко сводится к стационарному случаю. Введем дополнительную переменную ип (t ) , к /1.24/ добавим уравнение: +1С±) = u (t), #„+ (0)-0; ограничение /1.25/ Запишем в виде: #Ш U/(y + (О) Q Е 9 к системе /1.26/ добавим ограничение у + (т) - Г , а к /1.27/ - ограничение: - і и л () 1,
При этом потребуем, чтобы множество {(% ,„., и) с W(tfn ) О У«+1 Т} было выпуклым в t . Так, если фазовые ограничения /1.25/ заданы в виде: F(y) &( ), Р » гДе Fc ( ) - квазивыпуклые функции [ 25 J , то требуется, чтобы функции () были квазивогнутыми на отрезке 0,Tj. Если, например, в /1.29/ & ё„ +t t , то постановка задачи /1.29/ после описанных преобразований останется линейной.
Задача /I.31/ является в общем случае задачей нелинейного невыпуклого программирования. При различных допущениях для решения этой задачи могут быть разработаны специальные методы. Рассмотрим линейную задачу с целочисленным управлением, т.е. задачу /1.24/ - /1.28/ с дополнительным ограничением:
В случае применимости теоремы 1.2 алгоритм решения задачи /1.38/ - /1.40/ сводится к построению множества достижимости, описываемого этой теоремой и нахождению оптимального управления по алгоритму, описанному в пункте І.Ї.7.
Ниже рассматривается случай, когда условия теоремы 1.2 не выполняются. 1.4.2. Пусть X - линейное пространство, натянутое на базисные функции { ft (-) I *'= U- , } , неотрицательные на f'O.Tj, а X,- = {<*-&(*> UeR }. При этом U*it) является решением задачи /1.38/ - /1.40/, /1.42/, /1.43/ в силу утверждения І.Ї. Задача /1.53/ - /1.55/ является задачей математического программирования с континуальным множеством линейных ограничений. В случае линейного функционала такие задачи рассматривались в [2їЗ, В 461 исследуется алгоритм решения данного класса задач методом отсечений с очисткой на каждом шаге.
В некоторых случаях решение задачи /1.53/ - /1.55/, /1.56/ дает управление М () f оптимальное в классе кусочно-непрерывных функций. При этом задача может быть решена более простым методом.
Множества достижимости некоторых классов систем в банаховом пространстве
Векторное поле Ч Є dL называется 5 -проектируемым, если существует такое поле Ч Є С (% -/з ) , что V5 и Vх являются 5 -связанными. Будем считать, что выполнено Условие Е. При любом t Є С& "7" J каждое поле является St -проектируемым и поле S± Vs7 определено однозначно . Пример П.З. Рассмотрим линейную систему в банаховом пространстве у[ - А у ч- ис-ії с где А - линейный замкнутый оператор, С JE) СА ) .
Тогда X — зр {А С І к= О, i . . . } и можно положить (StA C)(y) = ± ААС /слева 5 применяется к векторно к к му полю (А С) (. ) = А С согласно приведенному выше определению, справа S± применяются к вектору А С Є 2D С А ) /. Таким образом, для линейных автономных систем выполняется условие Е. Для выполнения условия Е необходимо, чтобы из равенства уу - S6 уг следовало равенство D St L ) = & $ !& с для всех У Є Х . Поэтому при выполнении этого условия / в част ности, когда - образует сильно непрерывную группу/ для каж дого справедливо равенство -DStls- j. CSXy) , где Z= $ї $ -одно, из то чек в 7J , для которой 5 2 = у . Далее,- если Ъ г TJ і, О , іг $= 0 f то для ty Зю S±f + tt можно положить
Таким образом отображение 5 5 г ) на Jm. Stt+tz определено однозначно и равно St,+t2 Vе .В этом смысле будем говорить, что отображения S X ( с/ 7з ) обладают полугрупповым свойством.
В дальнейшем, не оговаривая, будем предполагать необходимые свойства гладкости этих отображений. с Т - ҐС?/ Утверждение П. 2. I. Отображение bt : J- u К "J fi ) ( t Є [0,T] ) является гомоморфизмом алгебр Ли. 2. Отображение / находится в инволюции с подалгебрами Ли St (іє[0,тп и ZT = &{StZ Iteio.Ti}. Доказательство. To, что 5 есть гомоморфизм алгебр Ли проверяется непосредственным вычислением. Легко показать, что Тогда из равенства следует, что (D St)0 \1о( (у ) - (D S \ 11с1уг iCtf ) и можно положить (Si X (у ) = (D St )0 \( s- )u loiy (( 5"Г),у), ч в J n ( S ) «В силу равенства /П. II/: ( 5е X +-, + поэтому для всех V X , т.е. отображение f находится в инволюции с алгебрами Ли . Из тождества Якоби сле дует, что f находится в инволюции и с алгеброй Ли т . Утверждение доказано.
Пусть Л == (%$$) - подалгебра Ли. Обозначим через ь У интегральное многообразие, порожденное алгеброй Ли Ji и проходящее через точку у 2/ .
Теорема П. 2. Пусть выполнены условия теоремы II Л, условие Е и следующие условия: а/ gh gXJ, = # V ?U,Vic[0,Tl /п.22/ б/ Подалгебры Ли StX ( t [0,71 ) и Х-г являются Ъ(-- регулярными. Тогда т.е. множество достижимости №#0 ( ) совпадает с интегральным многообразием, порожденным алгеброй Ли Хт - fa I Ъ єі } и проходящим через точку ST O. Доказательство. Нетрудно показать, что gAy-= ёу (s e(0 і еєА, te[a, ")}y где St? ( ) - группа отображений, порожденная отображением - 66 f U C( ;fl) , {${&) - группа преобразований, порожденная множеством — (? 2/3 . Поэтому можно положить
Если для алгебры Ли А можно одназначно построить отображения S ± } (і f09T])t удовлетворяющие условиям утверадения П.2, то 5у = -,, (о$У Т). В частности, Ь -& S 4, ( У + У2 Т ; Vi3yz 0). /П. ІЗ/ Покажем, что Я (Г7-) =? (? Г Sryfl. /П.Ї4/ Для этого заметим, что 6 = (-% 1 G \ t L О 1 s, т.е. &Xry = f(ng )/ 1 $е ; /= 4... J « = 4 /,... }. Из теоремы П.І следует, что если у, Є Ry0 ( ) , то у CL Поэтому, учитывая /П.ЇЗ/, легко показать, что {(fig ) Sr losy, ... у. r;«--4,,..Jc P/rj/n.i5/ d = / Применяя к левой и правой частям /П.Ї2/ отображение Sy , учитывая /П.ЇЗ/, получим ? f 6 Л - о 3 - v/ Тогда для и Є Jm S т :
Теорема двойственности для билинейных систем
Ядро ,// (Т) соответствует мгновенному наблюдению возможных состояний системы /Ш.12/, свободно эволюционирующей /т.е. при if; = 0, І = ,..., m / до момента Т. При этом за сколь угодно малое время возможно наблюдение системы с ядром // (Т) /т.е. два состояния различимы с точностью до М ( Г) / и возврат её в сколь угодно малую окрестность точки А0 С . Если , то система /ІБ.Ї2/, /ІИ.ЇЗ/ называется мгновенно наблюдаемой в момент Т. Последовательно ненаблюдаемым ядром за время Т называется подпространство J t&[D,Tl Ядро соответствует наблюдениям, сколь угодно мало изменящим траекторию свободного движения системы /ІПЛ2/ после момента Т /т.е. SAe ( Т) и0 сколь угодно близко к 5 (г)#, - решению задачи с ненулевым управлением, используемым для наб людения/. Если , то. система назы вается последовательно наблюдаемой за время Т. Имеют место следующие включения: jf"(T) ssf(T)mf (T) , Г 0. Естественно оігоеделить и тогда Поэтому имеется одно определение наблюдаемости билинейной системы за сколь угодно малое время.
Замечание. В конечномерном случае все три определения ненаблюдаемого ядра совпадают и не зависят от периода наблюдения Т. Поэтому для обыкновенных билинейных систем имеется одно определение наблюдаемости, не зависящее от периода наблюдения Гбб, J3, 39] .
Система удовлетворяет всем условиям теоремы П.2, кроме условия б/, т.е. условия регулярности,- связанных с системой /Ш.І7/ алгебр Ли. Однако в X имеется регулярная подалгебра Ли, интегральное многообразие которой / & » (0.)/ совпадает с интегральным многообразием алгебры Ли X , проходящим через 0. Учитывая это, легко показать, что /е; г)= spf л (V4V+» )) J 4Л Построенные подпространства дают полную информацию для решения вопроса о наблюдаемости системы /ЇІІ.Ї5/, /ІІІ.Ї6/. Так, например, для наблюдаемости за сколь угодно малое время необходимо и достаточно, чтобы система функций і \ & Э) і сі Є 6 { » І - О lj . 1 ша полной в Z.2 (&, ) .
Комплекс непрерывных технологических процессов состоит из конечных множеств: 7І - аппаратов, выполняющих технологический процесс; 7г - складов готовой продукции; 73 - складов сырья и поступающих со стороны полуфабрикатов; Уч - буферных ёмкостей.
Схема материальных и. энергетических потоков, включающая любые виды производственных связей /параллельные, последовательные, а также соединения типа обратных связей/ может быть представлена сетью материальных потоков с вершинами 71U72U7iUJ4 и дугами, задающими технологические и энергетические связи между ними. Каждой дуге /L , j / сопоставляется функция Mcj Ct") t задающая скорость перемещения потока по этой дуге. Как показано в [22, 8 ] система уравнений, описывающая состояние складов и буферных ёмкостей, имеет вид a4- - 92 - WO "J M + / ,ПАП «у CO, J flA(0 -"/ Ы - -S /Є ЪЛвСО і є 7U где ДСО (ВС О) - множество начал /концов/ дуг, входящих в /выходящих из/ вершину I ,
Описание аппарата, выполняющего j -й технологический процесс и соответствующий вершине J , задается в виде Ч Ю \ L UІ) ft), кєЬСЛ, j їі ; /ІУ-2/ где ,- - количество вещества, поступающего из L -го входного канала J. -го аппарата, необходимое для производства единицы к -го продукта /называется расходным коэффициентом/. На состояние складов и на скорости потоков в сети наложены следующие ограничения: - 93 - дуги сети;
Кроме того, могут быть наложены соотношения пропорциональности на скорости поступления сырья в аппараты, выполняющие технологические процессы.
Модель /1ІЛ/ - /ІУ.З/ с возможными дополнительными ограничениями хорошо описывает реальный технологический процесс непрерывного производства, если работа аппаратов аппроксимируется стационарным линейным многосвязным статическим объектом, и временем переналадки аппаратов для перехода с одного режима работы на другой можно пренебречь.
Задача управления описанным технологическим процессом может состоять, например, в максимизации выпуска продукции в течение заданного периода Т при ограничениях на состояния складов. Следовательно, объект, описываемый системой /ТУЛ/ - /ІУ.З/ и, возможно, дополнительными ограничениями на у нужно за время Т из начального состояния ( Хг (О) t с Є 72 U 7S(J7 ) пе_ ревести в заданную область С Xt С 7"), L Л Jv ) Є 3rj описывающую возможное в конце периода состояние складов, по такой траектории, чтобы достиг экстремального значения функционал
Об одной задаче распределения ресурсов вычисли тельной системы
Многие задачи оперативного планирования, внедрения новой техники, хода строительства объектов, выполнения научно-исследовательских и проектно-конструкторских разработок сводятся к моделям оптимального распределения взаимосвязанных ограниченных ресурсов по множеству работ, последовательность выполнения которых задана сетевым графиком [ 37 ] .
Скорость выполнения работы является некоторой функцией от объёмов ресурсов, выделенных для её выполнения. На выделяемые ресурсы в каждый момент времени накладываются ограничения.
Кроме того, сетевой график выполнения работ накладывает ограничения, связанные с тем, что данная работа не может быть начата до окончания некоторого подмножества предшествующих ей работ,
В этом параграфе рассматриваются динамические задачи оптимального распределения ограниченного объёма ресурсов при выполнении комплекса работ, последовательность выполнения которых задана сетевым графиком. В качестве критериев оптимальности могут быть приняты минимальное время выполнения комплекса - работ или минимальная стоимость его выполнения.
На основе полученной в главе I структуры множеств достижимости исследуются свойства оптимальных планов и предлагаются алгоритмы решения задач распределения ресурсов с указанными критериями.
Пусть имеется # работ, пронумерованных числами Ї,... П. ; величины Хс (t) характеризуют состояние (- -й работы в момент времени t . При этом Xc(f) = О означает, что рабдта і в момент і еще не была начата, a DCi(t) = і - что к моменту времени t работа L завершена.
Скорость выполнения работы зависит от выделенных ресурсов следующим образом: Os А( ї 21 fijCvjCtn , i-- .., n, /іу.зо/ /- s где UjCt) = 21 A ujs «) , /, - значения ре сурсов в момент времени t . Функции tL: (и) будем считать вогнутыми кусочно-линейны - 104 ми, так что j(u)=mn {j-cji tA/ " I - - Zv }. /ІУ.ЗЇ/ Тогда неравенство /ІУ.30/ можно представить в виде J-4 J /ІУ.32/ Таким образом, не ограничивая общности можно считать, что скорости выполнения работ зависят от объёмов выделяемых ресурсов следующим образом: 0 X -A" 9 /ІУ.ЗЗ/ где А - i&ij } c-rf і-ї " матрица с линейно-независи ыыми строками. При этом на ресурсы наложены ограничения: В U 4 , /ІУ.34/ где 5-{ yic-a = і ={&h ZX .
Ограничения на взаимную зависимость работ будем задавать в виде ориентированного графа Г, вершинам которого соответствуют работы, а входящие в L -ю веришину ребра указывают, какие работы должны быть завершены прежде, чем сможет начаться выполнение і -й работы. Будем обозначать это ограничение через /Г/. Ограничение /Г/ определяет невыпуклые оітраничения на фазовые координаты системы /ІУ.ЗЗ/ которые можно записать следующим образом: Y I [0,ll , в противном случае /Г/ где ОСО _ множество вершин графа Г, из которых выходят ребра, входящие в вершину . Заметим, что описание задачи в виде /ІУ.ЗЗ/, /ІУ.34/, /Г/ допускает использование одного ресурса несколькими, работами.
Ограничения /Г/ можно записать в виде системы уравнений ["273, однако для дальнейшего изложения удобней указанный вид этих ограничений.
Пусть первые столбцов матрицы А линейно независимы. Тогда рассмотрим систему /1.30/. Матрица А системы /1.30/ обратима. Поэтому можно ввести управление V- А и VL записать ограничение /ІУ.4/ в виде: На фиктивные переменные эс„+ъ . . . эсм фазовые ограни чения не накладываются. Таким, образом, не ограничивая общности, можно сформулировать задачу о составлении расписания выполнения заданного комплекса взаимосвязанных работ следующим образом: найти оптимальное в некотором смысле управление UС") t переводящее систему
