6ФОЛ П22 УДК 621.39 : 681.3(075.8) П22 Пашкеев С. Д., Минязов Р. И.. Могилевский В. Д. Машинные методы оптимизации в технике связи. Под ред. С. Д. Пашкеева. Учеб. пособие для вузов. М., «Связь», 1976. 272 с. с ил. Книга является методическим и справочным пособием по постановке и методам решения на ЭВМ задач оптимизации в технике связи. Рас- сматриваются элементы теории оптимизации и приводится общая мето- дика постановки и решения задач оптимизации на ЭВМ. Приводимые машинные методы оптимизации доводятся до блок-схем алгоритмов и алгол-программ и сопровождаются рекомендациями по применению и примерами, взятыми из области првектирования систем связи и управ- ления. Книга рассчитана в основном на студентов старших курсов техниче- ских вузов связи. Она может быть полезда также всем инженерам и на- учным работникам, интересующимся вопросами применения ЭВМ для ре- шения задач оптимизации. 30401—030 045(01)—76 —76 6Ф0.1 Сергей Дмитриевич Пашкеев Расим Ибрагимович Минязов Вадим Дмитриевич Могилевский МАШИННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ В ТЕХНИКЕ СВЯЗИ Редактор П о л и ек т о в а Т. Б. Художшик Андросов В. А. Технический редактор Черепова Е. Р. Корректор .Лев Г. Г. Сдано в набор 20/Х 1975 г. Подп. в печ. 21/1 1976 г. Т-01526 Формат 60x90/ie Бумага тип. № 3 17,0 усл.-печ. л. 18,29 уч.-изд. л. Тираж 10300 экз. Изд. № 16292 Зак. № 241 Цена 80 коп. Издательство <Связь». Москва 101000, Чистопрудный бульвар, д. 2 Типография издательства «Связь» Госкомиздата СССР Москва 101000, ул. Кирова, д. 40 © Издательство «Связь», 1976 г. Развитие науки, техники, экономики и производ- ства в настоящее время требует от инженеров всех специальностей умения ставить и решать задачи оптимизации в своей области, т. е. умения оптимизировать тот или иной процесс, устройство или систему. Известно, что достаточно сложные задачи оптимизации могут быть решены только с помощью ЭВМ на основе примене- ния современных математических методов. Однако в настоящее время в литературе отсутствуют система- тическое изложение и тем более методические справочные посо- бия по постановке и решению задач оптимизации на ЭВМ Пред- лагаемая книга является попыткой хотя бы частично восполнить этот пробел. В ней систематически излагаются и доводятся до алгоритмов и программ машинные методы оптимизации примени- тельно к технике связи, основанные на современных математиче- .ских 'методах, таких, как линейное и нелинейное программирова- ние, принцип максимума Л. С. Понтрягина, методы оптимизации в условиях неопределенности, методы теории игр, теории стати- стических решений, алгоритмы поиска экстремумов функций и функционалов, специальные методы оптимизации, методы опти- мизации графов и граф-сетей. iB книге приводятся также необходимые сведения из общей теории оптимизации и общая методика постановки и решения за- дач оптимизации на ЭВМ. Книга 'построена таким образом, что каждый машинный ме- тод оптимизации сопровождается необходимыми частными сведе- ниями из теории и читатель, не интересующийся общей теорией оптимизации и желающий лишь решить свою конкретную задачу, может пропустить гл. 1 и начать работу с книгой с гл. 2, а затем в зависимости от выбора машинного метода перейти непосредст- венно к той главе книги, в которой этот метод излагается. Материал книги базируется на трудах советских и зарубежных специалистов, а также работах авторов. Естественно, авторы не считают свою книгу «рецептом на все случаи» оптимизации. Наоборот, во многих случаях ее следует рассматривать лишь как сборник рекомендаций по решению хотя 'и широкого круга, но все же частных задач. Введение и гл. 2, 8 написаны С. Д. Пашкеевым, гл. 5, 6, 7, 10—Р. И. Минязовым, гл. 1, 3—В. Д. Могилевским. В написа. нии книги принимали участие также М. И. Рамоданов (гл. 4) и Б. В. Батырев (гл. 9). Отзывы и замечания по книге просьба направлять в издатель- ство «Связь» по адресу: 101000, Москва, Чистопрудный бульвар, Д. 2. Авторы Введение В настоящее время можно 'считать общеизвестным, что проблема оптимизации является одной из центральных в нау- ке и технике.. - Действительно, какую бы задачу не решал современный инже- нер, он всегда пытается получить наилучший (или, как принято называть, оптимальный) ответ. В этом смысле любые сколько-ни- - будь обоснованные решения и действия по разработке устройства, процесса, алгоритма или системы можно рассматривать как опта-. мальн.ые, ибо инженер предпочел их множеству других, т. е. по- считал их лучшими. При сознательной постановке любой инженерной задачи как задачи -оптимизации сразу же возникают три проблемы. Пер- вая — это формулирование и формирование критерия оптималь- ности данного объекта оптимизации. Решение этой проблемы не- редко сопряжено с большими трудностями, поскольку часто инже- нер хорошо знает, чего хочет, но сформулировать свое желание не может. Вторая проблема — это формальное представление (иденти- фикация) объекта оптимизации. Как известно, все множество ' объектов в науке и технике условно можно разделить на три ка- тегории: процессы, системы и алгоритмы. Каждая из этих групп имеет свои специфические математические методы для представ- ления объектов. Поскольку эти методы чрезвычайно разнообраз- ны и значительно отличаются друг от друга по сложности, воз- можностям, точности и другим характеристикам, то проблема формальной идентификации, т. е. проблема определения и пост- роения математической модели объекта оптимизации, в практиче- ских случаях оказывается весьма трудной. Третья проблема — это проблема выбора метода решения оп- тимальной задачи. Именно при рассмотрении этой проблемы вы- ясняется истинная цена разнообразия методов оптимизации. Здесь важно заметить, что алгоритмические (машинные) методы обыч- но не связаны с необходимостью описания условий задачи опти- мизации в аналитическом 'виде и поэтому могут охватить значи- тельно более широкий круг задач, чем аналитические методы, с помощью которых часто пытаются получить решение в замкнутой форме. Последнее обычно уводит инженера далеко за пределы тех реальных задач, которые он действительно хотел бы решить. Дело в том, что аналитические методы только на первый взгляд кажутся более привлекательными, чем другие, так как они при- водят к явному формульно'му решению задачи. Однако эта прив- лекательность достигается дорогой ценой резкого ограничения возможностей метода. Как правило, аналитические методы при- годны для решения относительно простых задач, которые часто могут быть сформулированы лишь благодаря далеко идущей идеа- лизации, когда фактически вместо поставленной задачи решается совсем иная. Алгоритмические же методы указывают алгоритм, т. е. после- довательность действий, осуществление которых приводит к неко- торому конкретному решению, причем класс задач, для которых можно указать алгоритм решения, чрезвычайно велик. В связи с широким применением ЭВМ алгоритмические методы приобре- тают доминирующее значение. Таким образом, задача оптимизации в каждом конкретном слу- чае так или иначе сводится к необходимости рассмотрения пере- численных выше проблем. В данной книге рассматриваются с необходимой для методиче- ского пособия степенью детализации все три проблемы оптими- зации как в теоретическом плане, так и, главным образом, в пла- не практического применения ЭВМ для решения задач оптими- зации в технике связи и управления. СПИСОК ЛИТЕРАТУРЫ B.I. Цыпкин Я. 3. Адаптация и обучение в автоматических системах. М., «Нау- ка», 1968, 400 с. В.2. Пашкеев С. Д. Основы мультипрограммирования для специализированных вычислительных систем. М., «Советское радио», 1972. 184 с. Глава Элементы теории оптимизации 1.1. ОСОБЕННОСТИ ЗАДАЧИ ОПТИМИЗАЦИИ В технических приложениях под системой обычно понимают совокупность материальных элементов, взаимодейству- ющих между собой в процессе функционирования устройства, вы- полняющего определенную задачу. Математически система опи- сывается в общем случае оператором или соотношениями, харак- теризующими взаимосвязь между входной и выходной информа- цией. Полное представление о системе можно получить, наблю- дая за процессами, происходящими в ней во время работы. По- этому .при изучении системы часто идентифицируют ее свойства с характером протекающих в ней процессов. При разработке системы естественно стремление сделать ее наилучшей в каком-либо смысле, т. е. оптимальной. Под этим под- разумевается синтез такой системы, в процессе функционирования которой обеспечивалось бы экстремальное (минимальное или мак- симальное) значение некоторого критерия или показателя каче- ства работы. Критерий должен отражать основное назначение си- стемы, характеризовать эффективность выполнения поставленных перед ней задач. Чем полнее критерий соответствует назначению системы, тем больше его практическая ценность. Процедура оптимизации по известному критерию оптимально- сти может осуществляться различными методами, на основе прив- лечения различного математического аппарата. Выбор того или иного метода зависит от свойств математической модели, описы- вающей работу системы (ее неизменяемой в процессе оптимиза- ции части); от вида и совокупности .параметров, которые подвер- гаются оптимизации; от различных ограничений, накладываемых на качество процессов в системе, на множество оптимизируемых параметров и т. д. Не вдаваясь в детальную классификацию си- стем, выделим ряд признаков, наиболее сильно сказывающихся на методах оптимизации системы или процессов, происходящих в ней. К числу таких признаков можно отнести: 1. Тип системы. Если под этим подразумевать наличие в си- стеме обратной связи, то можно классифицировать системы на замкнутые и разомкнутые. Однако наличие обратной связи в си- стеме еще не может служить признаком ее замкнутости с точки зрения процедуры оптимизации. С позиций оптимизации систему можно отнести к категории замкнутых, если требуется 'найти ха- рактеристики устройств, расположенных внутри контура, охва- ченного обратной связью. 2. Свойства модели. Под моделью системы будем понимать ее математическое описание, характеризующее зависимость выход- ных характеристик системы от входной информации. Например, производительность системы телефонной связи зависит от коли- чества подстанций, количества абонентов, быстродействия комму- таторов и т. д. Тогда, принимая за входной сигнал телефонный вызов, можно определить среднее время ожидания соединения с ' абонентом, которое будет зависеть от перечисленных характери- стик системы. В этом случае модель системы можно представить как некоторое алгебраическое соотношение — среднее время ожи- дания (суток, года) вызова. Если представляет интерес другая характеристика системы, например, соотношение сигнал/шум, то модель системы изменится. В общем случае модель системы опи- сывается соотношениями, отражающими сложный динамический характер зависимости выходного сигнала от входного. Например, пусть в качестве входного сигнала системы принята информация, поступающая от диктора системы радиовещания. Звуковые коле- бания после преобразования в электрические сигналы претерпе- вают целый ряд изменений в передающей и принимающей аппа- ратуре. На выходной сигнал влияют также свойства атмосферы и различные помехи. Математическое описание указанных зависи- мостей и составит модель системы радиовещания. Модели систем могут описываться весьма разнообразно и пред- ставлять собой алгебраические соотношения, дифференциальные или интегральные уравнения, рекуррентные соотношения, логи- ческие зависимости и т. д. 3. Условия работы системы. Система может работать в усло- виях наличия полной информации (детерминированный случай) или в условиях, когда информация, циркулирующая в системе, носит случайный, стохастический характер. В последнем случае приходится осуществлять оптимизацию в условиях неопределен- ности, уровни которой могут быть различными. Наихудшим ва- риантом являются условия, при которых о входной информации, о внешних возмущениях, действующих на систему, ничего не из- вестно. Более естественным считается случай, когда имеется не- которая априорная информация о вероятностных характеристиках полезных сигналов и помех. Важно подчеркнуть, что если в си- ' стему хотя бы в одном месте проникают случайные сигналы, то приходится ее условия работы относить к стохастическим. Строго говоря, работа всех реальных систем проходит в стохастических условиях, однако даже задачу анализа (не говоря уже об оптими- зации) в ряде случаев решить весьма трудно. Часто с удовлетво- рительной для практики точностью достаточно осуществить опти- мизацию в детерминированной постановке, а потом принять до- 7 полнительные меры по обеспечению требуемого качества работы системы в условиях случайных сигналов. 4. Характер информации. В зависимости от вида информации системы классифицируются как непрерывные и непрерывно-дис- кретные или дискретные. В первом типе систем сигналы непрерыв- ны, а их преобразования осуществляются непрерывными опера- торами, являющимися моделями отдельных устройств системы. В случае непрерывно-дискретных систем производится однократ- ное квантование сигнала ('по времени или по уровню), а для дис- кретных систем характерно двойное квантование — как .по вре- мени, так и по уровню сигнала. Последнее отвечает условиям ра- боты цифровых вычислительных машин. При квантовании сигна- ла происходит некоторая 'потеря информации, однако выгоды об- ращения с дискретными сигналами обусловливают их широкое применение. Как и в предыдущем пункте, систему, в которой хотя бы в одном месте тракта передачи информации осуществляется квантование сигнала, следует, строго говоря, относить к классу дискретных, даже если после этого производилось качественное декодирование. Итак, для того, чтобы корректно сформулировать задачу опти- мизации системы или процесса, происходящего в системе, необхо- димо иметь сведения о требованиях, предъявляемых к системе, и особенностях ее работы. Задачу оптимизации системы связи и уп- равления можно сформулировать, не используя термин «управле- ние» и рассматривая ее как процедуру, обеспечивающую системе наилучшие, в принятом смысле, свойства. Однако представляется, что привлечение подхода, развиваемого в теории управления, поз- волит с единых методических позиций рассмотреть многочислен- ные постановки задачи оптимизации и методы их решения, а так- же дать более наглядную трактовку проблеме. С этой точки зрения под управлением будем понимать опреде- ленным образом сконструированное воздействие на систему, не различая, когда оно осуществляется: во время функционирования системы (что характерно для систем управления), или заранее, в процессе ее синтеза и технического проектирования, что больше отвечает системам связи. Дальнейшая детализация такой интерпретации состоит в пред- ставлении системы в виде совокупности устройства управления и объекта управления. Первый элемент для выработки оптимально- го управления и его реализации осуществляет переработку инфор- мации, полученной от специальных измерителей в процессе функ- ционирования системы или на этапе анализа исходных данных, характеризующих работу системы. Второй элемент — объект уп- равления представляет собой часть системы, не подвергаемую процедуре оптимизации, и определяет ее некоторые неизменные свойства. Поведение объекта в процессе оптимизации (или рабо- ты) меняется из-за воздействия на него управлений или каких- либо внешних или внутренних возмущений. Тогда сама процеду- ра оптимизации заключается в нахождении математических соот- 8 ношении, описывающих устройство управления, которое .обеспечи- вает наилучшее в определенном смысле воздействие на объект, а значит, и оптимальные свойства всей системы. Таким образом, будем считать объектом оптимизации систе- му, подвергаемую оптимизации. Бели это динамическая система, то ее оптимизация эквивалентна приданию наилучших свойств процессу, происходящему в ней,-а в случае статической системы оптимизация сводится к наилучшему выбору совокупности пара- метров. Под объектом управления будем понимать часть системы, свойства которой не изменяются в процессе оптимизации, а зна- чит, ее математическая модель остается постоянной. Для осуществлении процедуры оптимизации необходимы сле- дующие сведения: — о критерии оптимальности, который представляет собой чис- ловую характеристику и отражает не только назначение системы, но и условия ее работы, характер информации, циркулирующей в системе; — о математической модели объекта оптимизации, что озна- чает известный характер поведения объекта при воздействии на него сигналов управления и возмущений. При этом на процессы, происходящие в объекте под действием управления и возмущений (будем говорить, что эти процессы описывают движение объек- та), может быть наложен ряд ограничений, которые следует'учесть при оптимизации; — о классе управлений. Оптимальные управления, реализую- щие воздействия на объект с целью достижения экстремума крите- рия, могут быть весьма разнообразными по своей физической при- роде и .математическому описанию. Так, управление может опи- сываться функциями, принадлежащими определенному классу, например, непрерывными; совокупностью констант, характери- зующих оптимальные свойства системы, наконец, управление мо- жет быть случайным, определяемым вероятностными характери- стиками. На управление могут быть наложены различные ограни- чения, выраженные в виде функциональных зависимостей, логи- ческих соотношений и др. Для каждой конкретной постановки задачи оптимизации мо- жет потребоваться и другая дополнительная информация, харак- теризующая специфические особенности системы. 1.2. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ КРИТЕРИИ ОПТИМАЛЬНОСТИ Математическое описание задачи оптимизации бу- дем производить, рассматривая последовательно критерии опти- мальности, формы описания объектов оптимизации и класс уп- равлений. 9 Качество системы характеризуется некоторым числовым пока- зателем У, который требуется в результате оптимизации обратить в экстремум, например, в максимум. Случай, когда необходимо Достичь минимума /, просто сводится к предыдущему и отдельно. изучаться не будет. • - Воздействие на систему Входная информация' Рис. 1.1 Оптимизируемая система Выходная характеристика Процесс оптимизации иллюстрируется рис. 1.1. По известно- му значению критерия в соответствии с методом оптимизации осу- ществляется направленное воздействие на систему (ее динамиче- ские характеристики, параметры), которое должно привести к до- стижению максимума /. Отсюда видно, что показатель системы в общем случае зависит от двух факторов: — от заданных характеристик системы, не 'подвергающихся процедуре оптимизации, которые будем описывать вектором а= {си, а2, ..., аз}, и • — от характеристик, определяемых 'в процессе оптимизации u={yi, Ыз, •••, Ur}, которые будем называть вектором управления. Векторы а и и -могут быть как функциями, так и числами, тогда J=J(s, u). (1.1) Вообще говоря, / зависит от входной информации и начального состояния системы, н'о так как система должна успешно работать в различных условиях, то эта зависимость обычно в критерии не находит отражения. В процессе оптимизации требуется обеспечить /°==J(ae, u°)==max/(«, u), (1.2) uet/ где u0—оптимальное управление, принадлежащее области допу- стимых управлений U. Критерий / в случае, когда u является функцией, 'представляет собой функционал — переменную величину, значение которой оп- ределяется выбором функции, играющей роль аргумента функцио- нала. Если же управление описывается совокупностью констант [и\, и-г, ..., и.т}, то / есть критериальная (целевая) функция. В практике исследования систем приходится иметь дело с кри- ' териями, представляющими собой ка.к функционал, так и функ- цию. Первый класс показателей качества шире, чем второй, соот- 10 ветствует динамическим системам, и его применение требует для формирования критерия глубокого анализа процесса функциони- рования системы. Так как путем .привлечения некоторых допол- нительных предположений (например, об известной структуре уп- равляющих воздействий) или сужения постановки задачи крите- рий, заданный в форме функционала, можно свести к целевой функции, то далее основное внимание будет уделено критериям более общего вида. Практически все рассуждения, относящиеся к функционалам, могут быть применены и к критериальным функ- циям. Следует особо отметить, что, как правило, существующие ме- тоды нахождения экстремумов 'позволяют выделить лишь один экстремум в допустимой области существования вектора управле- ния. Если же в этой области имеется несколько экстремумов (мно- гоэкстремальная задача), то определение глобального экстремума (например, наибольшего из максимумов) представляет сложную проблему, непреодолимую без существенного усложнения органи- зации вычислений. Выше указывалось на трудность формирования критерия опти- мальности для сложных, многоцелевых систем, работа которых характеризуется многими показателями качества. Однако фор- мально такая возможность существует и реализуется она следу- ющим образом. Пусть известен ряд показателей качества систе- мы Ji, i=l, 2..., где, например, /i—стоимость разработки, изго- товления, внедрения и эксплуатации системы; Jt—качество функ- ционирования системы; /з—потребляемая мощность; /4—надеж- ность работы системы и т. д. Совокупность этих характеристик. дает полное представление о том, насколько система удовлетво- ряет техническому заданию на разработку. Объединение различных 'показателей в единый многокомпо- нентный, составной критерий может осуществляться следующими способами: 1. Строится обобщенный критерий качества в аддитивной форме: J»^r,^. ' (!.3) i Тогда критерий представляет собой наиболее простую математи- ческую структуру, что облегчает задачу оптимизации, но при этом возникает проблема задания весовых коэффициентов с,. 2. Можно выделить какой-либо основной показатель, напри- мер, /г и потребовать, чтобы в результате оптимизации он дости- гал экстремального значения, а другие удовлетворяли системе не- равенств: Л<^1тр; ^3<^тр; ^*>^тр; • • . О-4) где величины в правых частях неравенств обусловлены техниче- ским заданием. 11 3. Бели в системе имеют место случайные процессы, то за обобщенный критерий можно принять вероятность Р удовлетворе- ния всем техническим требованиям: J = P[Ji < Лтр. J* > ^р> Js < ./тр. • • •I, (1.5) а в процессе оптимизации добиться максимума этого критерия. По приведенным формам описания обобщенного критерия сде- лаем несколько замечаний. Трудность' выбора критерия заключается в некотором субъек- тивизме в его представлении, который проявляется либо при за- дании требуемых значений отдельных показателей, либо при наз- начении весовых коэффициентов. Чтобы уменьшить этот субъек- тивизм и грамотно сформулировать требования к системе, необ- ходимо хорошо знать условия работы будущей системы и состояние техники в ближайшей перспективе. В противном случае, если тре- бования будут завышены, то их удастся выполнить лишь после длительной, скрупулезной проработки системы или не выполнить совсем. Если же требования низкие, то возникает вопрос об ак- туальности создания такой системы. Хотя формальное объединение совокупности требований к си- стеме в единый критерий производится достаточно просто, но осу- ществить оптимизацию по такому критерию, несмотря на всю 'его привлекательность, удается далеко не во всех случаях. Это объяс- няется отсутствием однозначной зависимости искомого оптималь- ного управления и° от частных показателей, зависящих от конст- руктивной проработки всей системы. Действительно, путем опти- мизации алгоритма преобразования информации в системе не всегда можно удовлетворить требованию, например, минимально- го потребления энергии, та'к как прямая связь между этими ха- рактеристиками или отсутствует, или становится 'очевидной лишь после реализации системы. Следует отметить одну опасность, возникающую при использо- вании обобщенных критериев. Дело в том, что коэффициенты ве- са Ci в (1.3) могут быть как положительными, так и. отрицатель- ными, последние определяют характеристики системы, которые целесообразно подавлять в процессе оптимизации (минимизиро- вать). Тогда максимум функционала может быть достигнут пу- тем компенсации положительных свойств системы отрицательным. Это вынуждает контролировать тенденции изменения частных по- казателей качеств в процессе оптимизации. Поэтому при технической разработке систем обычно исполь- зуют более простые критерии, включающие в себя лишь основ- ное требование к системе, а удовлетворение остальных проверя- ется после предварительной оптимизации. Если вспомогательные требования или ограничения не удовлетворяются, то система до- рабатывается. Рассмотрим некоторые распространенные критерии, начав с детерминированных показателей качества. 112 А. Детерминированные критерии. Для динамических систем в качестве критерия часто используют выражение т J(u, Хо. Q^K^i. Т)+ ^L[x(Q, u(t), t]dt, (1.6) <" где х„=х(^); Xi=x(T)=x(/„ x„, u(Q, T)— — векторы, характеризующие соответственно начальное и конеч- ное состояния системы; . К, L—функционалы заданного вида. Достоинствю данного критерия заключается в том, что он харак- теризует не только конечное состояние системы (первое слагае- мое правой части), но и процесс .перехода из начального состоя- ния в конечное. Если одному из показателей в этом .критерии сле- дует придать большую роль, что вытекает из самой постановки задачи, то следует ввести коэффициент веса (больше единицы) в соответствующее слагаемое. На практике могут использоваться отдельно, в качестве самостоятельных критериев, выражения: J,(u, x„, to)^K{^, Т); (1.7) J,(u, x„, /»)=JL[x(^ "(Q, t}dt. (1.8) '. В вариационном исчислении классифицируют задачи в том числе и по виду функционала, экстремум которого отыскивается: в слу- чае функционала (1.6)—задача Больца, (1.7)—задача Майера, (1.8) — задача Лагранжа. При конкретных исследованиях функ- ционал (1.7) имеет вид скалярного произведения некоторого пос- тоянного вектора, характеризующего вес или цену функционала, на вектор, определяющий состояние системы в момент окончания процесса: /<(Xi, Т)=сх(Г). (1.7') В практике оптимизации встречаются задачи, в которых, кро- ме достижения экстремума функционала, например (1.8), требу- ется выполнить дополнительное условие вида г [ N [х (t), u (/), t\ dt == const.. (1.9) 'о Такой случай имеет место, когда наряду с требованиями к ка- честву преобразования информации в системе существует огра- ничение (иногда его называют дисциплинирующим критерием), за- данное функционалом (1.9) и фиксирующее, например, допусти- мые расходы на достижение экстремума (1.8). Задачу указанно- го класса называют изопериметричеокой. Можно показать, что за- дачи изостериметрическиё, Больца, Лагранжа 'и Манера связаны между собой и при некотором изменении формулировок эквива- лентны друг другу. В соотношениях (1.7), (1.8) управление мо- жет быть не функцией какой-либо независимой переменной t, a 'IS иметь вид совокупности констант «i, Ua, . •., Ur (статические си- стемы). Тогда указанные соотношения суть критериальные функ- ции, заданные на некотором множестве скалярных параметров— констант. Например, в процессе оптимизации требуется отыскать г /=2Х.ы, <=i экстремум линейной формы г 2 а,у,^6. при ограничениях Если система предназначена для осуществления определенных преобразований над входным детерминированным сигналом (част- ный случай — следящая система), то в качестве меры качества ее работы обычно принимаются интегральные показатели типа J^i^\A(t)^pdf\l/f', (1.10) Ь. J где p^s\, Л(0=у*(0—у (0 — ошибка системы, выраженная в виде разности между реальным выходным сигналом у* (/) и сиг- налом, полученным на выходе идеализированной системы у (О, осуществляющей без ошибок требуемое преобразование входной информации. Детально 'критерии качества, основанные на исследовании про- цесса регулирования в системах автоматического управления, рас- смотрены в (11]. Б. Стохастические критерии. В стохастической постановке ког- да функция А (О является стационарным случайным процессом, удобной и наиболее простой мерой точности может служить сред- неквадратическая ошибка (Т .1/2 J^lim — fA2^ =(т[Л(/)]. (1.11) r<„ 2Г J^ j Процесс формирования критерия в системах с входным .полезным сигналом Xas(t) ('большие буквы обозначают векторную случай- ную фун'кцию, а малые — ее возможную реализацию), аддитивно смешанным с помехой Z(t), показан на рис. 1.2. Здесь Ф(<) — оператор реальной системы, Н(t)—оператор заданного пре- образования, а оператор W(t) т обеспечивает формирование по- —•— казателя качества системы. Рис. 1.2 Однако величина средне- квадратической ошибки явля- ется достаточно ограниченной оценкой работы стохастической системы, так как она дает лишь информацию о возможных разбросах ошибки относительно математического ожидания. Большей общностью обладает крите- рий, учитывающий и величину математического ожидания. Такого рода критерий, выражающийся в виде произвольной дифференци- 14 руемой функции от среднеквадратической ошибки (второй 'началь- ный момент) о(А(0] и математического ожидания ошибки Л1(Л(^)], имеет 'вид: /=F(M[A(Q1, (т[Д(01). (1.12) В качестве частного случая из (1.12) можно получить новый критерий, определяющий вероятность невыхода ошибки за изве- стные границы допуска. Если ошибка распределена по нормаль- ному закону, то -'/1 С. /=P(q\Y)=M[W (Y, У*)1У]= \W(Y, У*)Р(У*|У) й!Й(У*), (1.15) а (У) где Q (Y*) —область возможных значений Y*, a dQ,—ее бесконеч- но малый объем; Р(У*|У)—условная плотность вероятности Y* при заданном Y. 16 При известном законе обработки входного сигнала X(t), т. е. функции Ф(У*/Х), указанная плотность вероятности определяет- ся как Р(К*|У)=|Ф(У*|У)Р(Х|К)с?0, (1.16) "W а для нахождения плотности вероятности Р (X\Y} необходимо знать условия эксперимента, т. е. 'вероятностные характеристики шума и способ его комбинации с сигналом Y(t). Так как обычно приходится иметь дело с заранее неизвестной реализацией сигнала, то целесообразно произвести усреднение условного риска по всей совокупности возможных сигналов, для чего должна быть задана априорная плотность вероятности P(Y) передаваемых сигналов. Такая характеристика определяет сред- нее качество решения задачи и таким образом является безуслов- ным мalтeмia'тич•acкиiм ожиданием функции потерь.: г(Ф)==Л1[р(Ф|У)]= Ср(Ф|У)Р(У)йй. (1.17) а (V) Эта величина называется полным или средним риском. Практически все статистические критерии являются частным случаем критерия среднего риска, а конкретное представление того или иного критерия определяется формой задания функции потерь. Критерий средчего риска может быть успешно применен для оптимизации системы лишь в том случае, когда известна априор- ная плотность вероятности сигнала P(Y) [см. (1.17)]. Такая зада- ча называется байесовой, а результат ее решения—'байесовым. Если же полная информация о вероятностных характеристиках сигнала и наблюдаемой случайной функции отсутствует, то опти- мизация системы может быть осуществлена лишь для некоторых форм задания функции потерь. При этом объем априорной инфор- мации о воздействиях на систему определяет возможность реше- ния задачи и конкретный вид функции потерь [I.2]. Для того чтобы избежать недостаточности априорной информа- ции, можно задать неизвестную плотность вероятности P(Y). При этом, например, допустимо считать распределение равномерным, т. е. предполагать равновероятным появление любого сигнала в некоторой области Й(У), или руководствоваться сведениями о ра- боте других систем в аналогичных условиях, или, наконец, дове- риться интуиции. Указанный подход применим в ситуациях, не носящих конфликтный характер, когда нет оснований ожидать по- явления особым образом сконструированных «противником» сиг- налов с целью ухудшить оптимальные свойства системы. Такое положение принято классифицировать как взаимоотношения с природой. Рассмотренные критерии используются 'при решении задач, где в результате оптимизации должна быть найдена некоторая опти- мальная совокупность параметров системы. При формировании 17 критериальной функции следует выявить зависимость выходных характеристик, составляющих эту функцию, от указанных пара- метров. Если эта процедура выполнена, то рассмотренные крите- рии, построенные на определении функции потерь, могут быть применены для исследования статических систем без ка.ких-либо изменений. В. Минимаксные критерии. Несколько другой подход при оцен- ке качества работы 'как динамических, так и статических систем применяется .при исследовании конфликтных ситуаций, где взаи- модействуют объекты, интересы которых противоположны. В этих условиях естественно ожидать от противника таких направленных действий, которые .приведут к появлению сигналов на входе си- стемы с распределением, наиболее сильно отличающимся от ап- риорного, заложенного в систему при оптимизации, а значит, при- водящего к значительному отклонению свойств системы от опти- мальных. Конфликтная ситуация требует скептического отноше- ния к оценке качества системы, которое должно проявляться при определении априорной вероятности. А именно, на первом этапе определяется наихудший входной сигнал У при заданном законе его обработки Ф; критерием свойств входного сигнала с'лужит величина условного риска р(Ф|У)=тахр(Ф|У). Уе" (У) (1.18) Это выражение фактически означает оценку ущерба, который мо- жет нанести противник, подбирая наихудшее входное воздейст- вие для системы с определенными свойствами. Подобный эффект следует уменьшить путем изменения свойств системы за счет вы- бора соответствующего закона обработки сигнала. Тогда услов- ный риск принимает значение р (фв | у6} == min p (Ф, Y°) == min max р (Ф [ У). Ф Ф У (1.19) Этот критерий называется минимаксным, а оператор Ф", отвеча- ющий экстремуму,— минимаксно-оптимальным. Таким образом, решение, являющееся минимаксно-оптималь- ным. обеспечивает наилучшее поведение системы в наихудших условиях. Вообще говоря, при практических исследованиях про- цедура достижения минимаксного решения является итерационной, минимакс находится методом последовательных приближений: вначале удовлетворяется условие (1.18), затем (1.19), после чего вновь обращаются к (1.18), и цикл повторяется. Такая процедура адекватна реальным условиям, когда «противник» отвечает видо- изменением совокупности входных сигналов в ответ на стремление улучшить свойства системы путем выбора соответствующего Ф. При применении того или иного типа критерия для оптимиза- ции системы следует помнить, что понятие наилучших свойств, по существу, зависит от условий работы системы. Так, использование 18 детерминированных критериев и достижение их экстремума в .про- цессе оптимизации отвечает случаю, когда свойства системы будут оптимальными для .всех допустимых совокупностей начальных условий, входных сигналов и возмущений. Для каждых конкрет- ных условий работы процесс будет наилучшим. Такие системы иногда называют равномерно-оптимальными. При статистическом описании условий работы системы, когда степень достоверности априорной информации позволяет осущест- вить оптимизацию в рамках байесова подхода, невозможно обес- печить наилучшее поведение системы для каждой конкретной со- вокупности условий. Критерии оптимальности в этом случае явля- ются усредненными показателями качества системы, поэтому дос- тижение их экстремума в процессе оптимизации означает, что про- цессы в системе будут оптимальными в среднем при многократ- ном применении системы или в условиях ее длительной работы. Такие системы относят ж классу статистически-оптимальных. Наконец, использование .минимаксного критерия свидетельст- вует о необходимости проявить осторожность в оценке условий работы системы, априорная информация о которых мало досто- верна. Такого рода оптимальные системы в среднем обеспечивают наилучшее поведение системы 'в наихудших условиях. Другими словами, наихудший результат в минимаксно-оптимальной систе- ме лучше наихудшего результата в любой другой системе. Таким образом, при оптимнзадии системы наблюдается диа- лектичеюкое единство уровня достоверности априорной инфор- мации об условиях работы системы и степенью приближения каж- дого конкретного процесса в системе к оптимальному. Поэтому столь важное значение три проектировании системы имеют этан уяснения особенностей условий ее работы, четкое математическое описание входных сигналов и возмущений, определение поведения системы, ее реакций на воздействия. Перед тем как перейти к рас- смотрению способов описания свойств системы, сделаем еще два замечания о критериях оптимальности: 1. В случае, когда инфармация в схему формирования критерия (рис. 1.1) поступает дискретно, мерой качества работы системы является функционал дискретных значений аргумента. При этом в качестве критериев оптимальности могут рассматриваться все показатели, исследованные выше. Отличительная особенность ре- шения задачи оптимизации для такого рода систем заключается в том, что критерий можно интерпретировать как функцию (а не функционал) многих переменных. Последние суть не что иное, как дискретные значения вектора управления, принадлежащие обла- сти допустимых значений. При дискретном задании состояний системы возможно пред- ставление критерия в виде матрицы, где ее элементы означают значение критерия, соответствующее определенному состоянию. Пусть число состояний конечно и каждое из них определяется дву- мя параметрами: и„ и„ i==\, 2. .... m, j=l, 2, .... п. Тогда полное 19 представление о качестве системы доставляет матрица тХп, на- зываемая платежной: | v\ t/2 • • -"Л MI "2"m • • •Л. •И •'12 • • • • • ••/2» •/21 •'22 • • ..... . • • •Jmn fnn (1.20) Количество столбцов и строк матрицы может быть бесконечным и, в общем случае, число параметров, определяющих состояние системы, может превышать два. Последнее приводит 'к необходи- мости использовать совокупность платежных матриц для оценки качества системы. 2. Для процедуры оптимизации чрезвычайно удобно использо- вание квадратичных критериев. Это обусловлено тем, что в этом случае критерий является выпуклым, а квадратичная форма поз- воляет записать необходимые условия оптимальности в виде систе- мы линейных уравнений. Квадратичными формами описываются как детерминистские, так и статистические показатели качества, например, второй центральный момент ошибки системы. Приме- ром квадратичного критерия может служить выражение J{u}^^{t)dt; (1.21) <. 1Г(/) = х^х + x'Bu + u'Bx + u'Cu, где А, В, С — положительно определенные матрицы соответству- ющих размерностей, а индекс «т» означает применение операции транспонирования. Элемент субъективности при формировании та- кого критерия проявляется в выборе элементов матриц. ОБЪЕКТ ОПТИМИЗАЦИИ При математическом описании объекта, оптимиза- ции.и разработке модели его поведения обычно устанавливают: — свойства объекта, изменение выходных параметров объекта под действием управлений (входных сигналов) и возмущений или помех; — характер информации об изменении состояния объекта, ко- торая может быть получена с помощью измерителей или путем анализа априорных данных и использована для формирования управления; — требования, предъявляемые к объекту. 20 В объект оптимизации включают и неизменяемую часть систе- мы (объект управления), которая не подвергается процедуре оп- тимизации, но необходима для обеспечения работоспособности системы. Свойства объекта в указанном смысле характеризуются зави- симостью выходной величины х от дходяых величин управления и и помехи (возмущения) z. Так как эти величины являются функ- циями независимого переменного, в роли которого обычно высту- пает время —х(7), u(t), г(1), то зависимость между множества- ми функций определяется оператором общего вида: \=F(u, г, t\. (1.22) Для целого ряда объектов входные и выходные величины не за- висят от времени, т. е. являются константами. Физически это оз- начает, что изменение какого-либо параметра, характеризующего состояние объекта, приводит 'к скачкообразному изменению вы- ходной характеристики, которая впоследствии остается постоян- ной .вплоть до формирования нового управления. Тогда вместо (1.22) можно записать x-F(u, z). (1.22') Примером такого рода объектов может служить система теле- фонной связи, параметры которой (энергопотребление, длина ком- муникаций и др.) изменяются при подключении новых абонентов, По аналогии с системами объекты, характеристики 'которых зави- сят от 'времени (1.22), можно назвать динамическими, в отличие от статических (1.22'), параметры которых стационарны. Изуче- ние динамических объектов, естественно, требует привлечения бо- лее сложных математических методов. Структуры стационарных объектов могут рассматриваться как частные случаи динамиче- ских. Функции, входящие в (1.22), удобно представлять как векто- ры соответствующей размерности, определенные в некоторой эв- клидовой системе: х := { х!! ^2' ' ' 'i^n/i u={«i, u„ . . ..и,}; (1.28) 2={Zi, Z2, . . .,Z,}. Каждая проекция (составляющая) этих векторов характеризует отдельный процесс, происходящий в системе. Анализ поведения объекта (изменение вектора выходных коор- динат) чрезвычайно удобно проводить, используя геометрическую интерпретацию. С этой целью для динамических объектов вводит- ся фазовое пространство Х размерности п, в котором состояние объекта в некоторый момент времени <, фиксируется положением изображающей точки. Вектор, .проведенный из начала координат в эту точку 'x.(ti), однозначно описывает процесс в данный момент времени (в дискретных системах фазовые координаты {х\,х^...,х-п} часто называют параметрами состояния). Изменению во времени ai .переменных, характеризующих состояние системы, соответствует перемещение в пространстве Х изображающей точки, совершаю- щей некоторое движение по траектории, называемой фазовой (рис. 1.3). Фазовое пространство иногда удобно расширять, вклю- чая в него дополнительные координаты — время, величину кри- терия, управление. Аналог фазового пространства существует и для статических объектов. В этом случае, разумеется, нельзя говорить о движении Рис. 1.3 изображающей точки по фазовой' траектории, однако рассмотре- ние пространства параметров, описывающих состояние объекта (системы), дает возможность наглядно отобразить изменение па- раметров под действием управления, выявить допустимые диапа- зоны изменения параметров, допустимые области существования решений и т. д. В качестве примеров можно указать на класс за- дач, решаемых методами линейного и нелинейного программиро- вания, задачи на графах и др. Граничные условия. В задачах оптимизации динамических си- стем, как правило, в той или иной форме фиксируется начальное и конечное состояние системы. Простейший способ заключается в задании векторов х(/о) и х(Г), такого рода задачи называют за- дачами с закрепленными концами (принято определять начальное состояние левым концом фазовой траектории, а конечное—пра- вым). К числу простейших относится также вариант, когда до- пускается произвольное положение изображающей точки в момент окончания процесса управления Т (свободный правый конец тра- ектории). При этом выделяют случай фиксированного времени управления Т—to (задача с закрепленным временем). Наиболее общим случаем задания граничных (начальных или конечных) условий являются задачи с подвижными концами. Здесь предполагается, что в фазовом пространстве задаются два 'множества So и 5т, которым должна принадлежать изображающая точка в соответствующие моменты времени: x(^o)sSo, х(Г)^5т. Под действием управления осуществляется переход точки с Одного множества на другое. В фазовом пространстве указанные множе- 23 ства интерпретируются как гиперповерхности граничных условий, заданные в общем случае неявной формой ('рис. 1.4): 1) So [x M == 0; 2) S, [х (Т)] == 0. (1.24) Из всего множества фазовых траекторий, начинающихся на So и заканчивающихся на 5т, в процессе оптимизации выбирается та, которой соответствует экстремальное значение критерия. Множества So и 8т (иногда называемые целевыми множества- ми, что подчеркивает цель управления движением изображающей точки) могут задаваться совокупностью условий, например, ^[х(Г)]=0; 5,[х(Т)]==0, . . .,5,[х(Г)]=0. (1.25) Тогда граничное 'многообразие представляет собой пересечение указанных множеств и характеризуется требованием одновремен- ного выполнения всех условий (1.25). В фазовом .пространстве в этом случае граничные условия задаются некоторой гиперповерх- ностью, Я1вляющей|ся .результатом пересечения k отдельных гипер- поверхностей (1.25) (рис. 1.5). Рис. 1.6 Фазовые траектории граничные условия для которых заданы в ф•qplмe (1.24), соответЧственно называются траекториями с под- вижным левым и^и правым концами. Ограничения. Наряду с требованием .принадлежности, изобра- жающей точки в начале и конце процесса управления некоторым гиперповерхностям концевых условий, на последних могут быть выделены особые области допустимого расположения изображаю- щей точки. Такие требования формализуются в общем случае в виде, например, неравенств: 1) Go [х М < 0; 2) G, [х (Г)] < 0. ' (1.26) Совместное выполнение условий (1.24) и (1.25) выделяет в про- странстве Х некоторый криволинейный многогранник допустимых состояний системы в начальный или конечный момент времени (рис. 1.6). Этот многогранник может быть открытым или закры- 23 тым в зависимости от того, 'включены граничные точки в его со- став (выполнение равенства в (1.26)] или нет (строгое неравен- ство). Критерии «допустимости» движения системы могут быть и Дру- гими. Так, в пространстве Х системой условий 0. Приведенные необходимые и достаточные условия являются общими и могут применяться для решения практических задач. Однако, естественно, использование этих условий будет более про- дуктивным, если их конкретизировать для различных более узких постановок задач оптимизации. При подобной детализации возни- кают не только разнообразные рецепты решения той или иной задачи, но и различные математические методы. 1. Классическое вариационное исчисление. В соответствии с приведенной ранее классификацией вариацион- ное исчисление применяется для оптимизации непрерывных и дис- . кретных динамических систем, работающих в условиях частичной неопределенности или детерминизма. Наиболее значительные ре- зультаты в области применения методов классического вариаци- онного исчисления для оптимизации стохастических динамических систем получены в рамках корреляционной теории. Основная за- дача классического вариационного исчисления (задача Лагран- жа) заключается в нахождении максимума (минимума) функцио- нала: г J(u)= fL(u, u, t)df (1.42) f, —к этому виду приводится (1.8) при подстановке в него (1.22). При этом обычно предполагается непрерывность подынтегральной функции по совокупности ее аргументов, а также существование и непрерывность ее частных производных до третьего порядка включительно. Максимум отыскивается на классе кусочно-гладких функций и(/). Метод получения необходимых условий существования экстре- мума основывается на исследовании первой вариации функциона- 30 ла — линейной (по отношению к приращению аргумента функцио- нала би(0) части приращения функционала б/(и). Обращение этой вариации в нуль, характерное для стационарной точки u=u°(0, приводит к получению распространенного уравнения Эй- лера—Лагранжа: L .—L„=0, <=1,2, . . .,г. (1.43) l dt где L"<==^7L(U• "• ^ ^Г^^' "•/)> Характерной особенностью получения этого условия, определя- ющей область применения вариационного исчисления в задачах оптимизации, является предположение о том, что при варьирова- нии функция u(t)+6u(t) не достигает границы допустимой обла- сти, а значит, экстремум функционала лежит внутри этой области. Следовательно, если область управления замкнутая, то примене- ние вариационного исчисления возможно лишь при использова- нии специальных приемов [1.3]. Запись необходимых условий экстремума функционала в виде уравнения Эйлера—Лагранжа является не единственным пред- ставлением этих услов-ий. Известны ряд других соотношений — условие Лежандра, условие Вейерштрасса, условие Якоби, — ко- торые в рамках сформулированной задачи дают другие формы за- писи, отвечающие той же цели. Целесообразность их использова- ния зависит от формулировки конкретной задачи. Необходимые условия экстремума трансформируются в зависимости от вида функционала, который может включать производные высших по- рядов, .быть представлен в параметрической форме, зависеть от нескольких функций и т. д. Далеко не во всех практически важных задачах удается свес- ти оптимизацию к поиску экстремума функционала в простран- стве управлений, так как не всегда возможно подстановкой исклю^- чить промежуточные переменные в показателе качества, причиной чего является сложная взаимосвязь между управлением и фазовы- ми координатами. В этом случае наряду с функционалом критерия при решении задачи оптимизации приходится рассматривать урав- нения объекта, заданные 'каким-либо оператором. Если оператор объекта (1.22) переписать в скалярной форме в неявном виде как F,(x, u, f)==0, i== 1,2, • . ., п, (1.44) то доказывается, что задача на условный экстремум, которая по- лучается при необходимости учесть дополнительные связи, может быть сведена к задаче на безусловный экстремум,-рассмотренной выше. Для этого достаточно составить функционал (1.45) где Ki(t) — множители Лагранжа, и для нахождения его экстре- 31 для игровых задач представляет цену игры. В назначение цены игры закладываются субъективные положения, определяющие от- ношения игрока против природы к результатам игры. По Лапласу в предположении равномерного распределения стратегий природы цена игры характеризуется соотношением (1.30] п т S-7-S"^- (1.126) /=i »=i Если от природы ожидаются наихудшие с точки зрения игрока действия, то цена игры определяется по Вальду: min[y^V«,^1 (1.127) "/ L/=i и J и характеризует как наилучшую стратегию, обеспечивающую наи- больший выигрыш в наихудших условиях. Цену игры, доставляющую минимальную потерю выигрыша в наихудших условиях, определяет критерий Сэвиджа: mm "/ У UiJ,j—maxJtj ^1 "i (1.128) Наконец, критерий Гурвица выбором коэффициента веса позво- ляет варьировать уровнем «пессимизма» и ослабить предположе- ние о наихудших условиях: amaxfYu^)+(l-a)min(Yu.^), (1.129) "! \Й / "/ \^ ] где O^a^l. Перечисленные критерии сформулированы для чис- тых стратегий. Хотя их распространение на смешанные стратегии большого труда не составляет, однако применение последних в задачах с неопределенностью не имеет большого смысла из-за малой достоверности априорной информации, делающей нецелесо- образным усложнение решения. Общий подход к отысканию оптимальной стратегии .в условиях неопределенности состоит в моделировании итеративного вероят- ностного процесса игры с последовательным уточнением априор- ных вероятностей путем вычисления апостериорных характерис- тик процесса. Перспективным является направление корректного сведения игр в условиях неопределенности к играм с полной ин- формацией. СПИСОК ЛИТЕРАТУРЫ 1.1. Барковский В. В., Захаров В. Н., Шаталов А. С. Методы синтеза систем управления. М., «Машиностроение», 1969. 327 с. 1.2. Пугачев В. С. Теория случайных функций. М., Физматгиз, 1960. 883 с. 1.3. Фельдбаум А. А. Основы теории оптимальных автоматических систем. М.„ Фнзматгиз, 1963. 552 с. 72 1.4. Болтянский В. Г. Оптимальное управление дискретными системами. М., «Наука», 1973. 446 с. 1.5. Лаврентьев М. А., Люстерник Л. А. Курс вариационного исчисления. М., Гостехиздат, 1950. 296 с. 1.6. Цлаф Л. Я. Вариационное исчисление и интегральные уравнения. М., «Нау- ка», 1966. 176 с. 1.7. Демьянов В. Ф., Малоземов В. Н. Введение в минимакс. М., «Наука», 1972. 368 с. 1.8. Моисеев Н. Н. Численные методы в теории оптимальных систем. М., «Нау- ка», 1971. 424 с. 1.9. Понтрягин Л. С. и др. Математическая теория оптимальных процессов. М., «Наука», 1961. 392 с. 1.10. Лейтман Д. Введение в теорию оптимального управления. М., «Наука», 1968. 190 с. 1.11. Болтянский В. Г. Математические методы оптимального управления. М., «Наука», 1966. 307 с. 1.12. Атанс М., Фалб П. Оптимальное управление. М., «Машиностроение», 1968. 764 с. - . 1.13. Пропой А. И. О принципе максимума для дискретных систем.—«Автоматика и телемеханика», 1965, № 7, с. 14—01. 1.14. Фиакко А., Мак-Кормик Г. Нелинейное программирование. М., «Мир», 1972. 240 с. 1.15. Вентцель Е. С. Исследование операций. М., «Советское радио», 1972. 551с. 1.16. Ермольев Ю. М., Мельник И. М. Экстремальные задачи на графах. Киев, «Наукова Думка», 1968. 176 с. 1.17. Форд Л., Фалкерсон И. Потоки в сетях. М., «Мир», 1966. 276 с. 1.18. Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование. М., «Наука», 1969. 368 с. 1.19. Гаврилов В. М. Оптимальные процессы в конфликтных ситуациях. М., «Со- ветское радио», 1969. 160 с. 1.20. Беллман Р. Динамическое программирование. М., ИЛ, 1960. 400 с. 1.21. Красовский Н; Н. Игровые задачи о встрече движений. М., «Наука», 1970. 420 с. 1.22. Ц.ыпкин Я. 3. Адаптация и обучение в автоматических системах. М., «Нау- ка», 1968. 399 с. 1.23. Аоки М. Оптимизация стохастических систем. М., «Наука», 1971. 424 с. 1.24. Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслужива- ния. М., «Наука», 1966. 431 с. 1.25. Бусленко Н. П. и др. Лекции по теории сложных систем. М., «Советское радио», 1973. 439 с. 1.26. Дынкин Е. Б. Марковские процессы. М.—Л., Физматгиэ, 1963. 859 с. 1.27. Ховард Р. А. Динамическое программирование и марковские процессы. М., «Советское радио», 1964. 189 с. 1.28. Беллман Р., Дрейфус С. Прикладные задачи динамического программиро- вания. М., «Наука», 1965. 458 с. 1.29. Блекуэлл Д., Гиршик М. А. Теория игр и статистических решений. М., ИИЛ, 1958. 374 с. 1.30. Саати Т. Математические методы исследования операций. М., Воениздат, 1963. 420 с. 1.31. Солодов А. В., Петров Ф. С. Линейные автоматические системы с перемен- ными параметрами. М., «Наука», 1971. 620 с. Рассмотрение структурной схемы алгоритма оптимизации по- казывает, что для решения сложных задач оптимизации прихо- дится разрабатывать не только алгоритм собственно оптимиза- ции, но и алгоритмы модели оптимизируемого объекта и алгоритм вычисления критериальной функции или функционала. Кроме того, в отдельных случаях необходимо специально раз- рабатывать алгоритм включения модели объекта в общий алго- ритм оптимизации. Более подробно вопросы построения алгоритмов оптимизации рассматриваются в последующих главах на конкретных примерах. СПИСОК ЛИТЕРАТУРЫ 2.1. Пашкеев С. Д. Основы мультипрограммирования для специализированных вычислительных ристем. М., «Советское радио», .1972. 184 с. Глава 3 Машинные методы оптимизации. основанные на применении классических математических методов 3.1. ВВОДНЫЕ ЗАМЕЧАНИЯ Локализация классических математических мето- дов решения задач оптимизации, как и всякая классификация,яв- ляется достаточно искусственной. Однако можно определить неко- торые свойства, в основном относящиеся к критерию оптимально- сти и области его задания, которые делают указанное выделение обоснованным. К таким свойствам можно отнести: 1) выпуклость показателя оптимальности (функционала или функции) на мно- жестве его задания, единственность экстремума; 2) область зада- ния критерия является открытой, а экстремум расположен внутри области; 3) если в формулировке задачи и содержатся ограниче- ния на управление или изменение параметров состояния, то они принадлежат узкому классу, имеют специфическую форму и не нарушают общую методологию решения. Классические математические методы решения задач оптими- зации подразделяются на аналитические (непрямые) и численные (прямые). Аналитические методы ориентированы на определение матема- тических соотношений, характеризующих необходимые, в общем случае и достаточные, условия экстремума критерия оптимально- сти. Решение этих соотношений дает возможность найти точку в области задания критерия, отвечающую экстремуму (стационар- ную точку). Таким образом, при использовании непрямых мето- дов основная тяжесть решения задачи оптимизации ложится на получение аналитических уравнений, описывающих стационарную точку. Непосредственное же решение последних уравнений произ- водится широко известными математическими приемами с по- мощью вычислительных машин, хотя иногда составляет самостоя- тельную задачу. Прямые методы базируются на непосредственном отыскании экстремума критерия и соответствующей ему стационарной точки. Такая процедура связана со сравнением значений критерия в двух и более точках множества его задания и выбора для последующих действий приращения аргумента, обеспечивающего приближение к экстремуму. Для многомерных задач оптимизации используются градиентный метод или его модификации. Такой подход может 86 процедура совпадает с рассмотренной выше для критерия, приво- димого к квадратичной форме. В рассмотренных задачах оптимизации системы, состояние ко- торой определяется нелинейным ур-нием (3.41), проведение лине- аризации на каждом шаге процесса объяснялось стремлением по- лучить наилучшую вариацию управления v°(t). Однако можно построить процедуру [3.10], в которой процесс «улучшения» управ- ления будет производиться в замкнутом цикле автоматически, без линеаризации системы, а значит, без вычисления матриц A(f), В (t) для каждого Ui(t), х,(7). Разумеется, при этом нельзя ручаться, что на каждой итерации процесс деформации управления будет проходить наиболее эффективно в смысле скорейшего приближе- ния опорного управления Uo(t)(Ui(t)) к оптимальному u°(t). Итак, пусть состояние системы описывается ф-лой (3.41), а в качестве критерия примем частный случай ,/=(<:, х (Т)), (3.52) где с — вектор-столбец констант, его размерность п. Такой вид критерия позволяет наиболее просто записать условия трансвер- сальности на правом конце процесса: в соответствии с (3.49) 4(Т)=-с. (3.53) Следует отметить, что данный метод позволяет решать задачи и с более развитыми граничными условиями, при этом, конечно, усложняется процедура. Пусть известны начальные условия х(7о)=Хо и некоторое на- чальное управление Uo(t). Тогда интегрирование (3.41) дает воз- можность найти \o(t). В соответствии с процедурой использования эйлеровских уравнений, записанных в канонической форме, со- ставляется функция Гамильтона Н - (ф, f) (3.54) (3.55) и записывается сопряженная система дН д х ' Так как граничные условия (3.55) при t==T известны (3.53), то эта система может быть проинтегрирована справа налево (от t=T до t=to), при этом Н вычисляется при x==Xo(Q, u=Uo(0. При из- вестных ^io(t), ^o(t) находится оптимальное управление u°i(7) из условия ^ = 0, (3.56) д и и вся процедура вычислений повторяется. Блок-схема программы изображена на рис. 3.7. Вопрос о сходимости в общем случае остается открытым, но при успешно выбранном Uo(t) метод обес- печивает хорошую сходимость частных решений и°; (/) к оптималь- ному u°(t). 104 Рассмотренные методы (после соответствующей доработки) могут быть применены и в случае, когда на управление наложено ограничение. СПИСОК ЛИТЕРАТУРЫ 3.1. Цлаф Л. Я. Вариационное исчисление и интегральные уравнения. М., «Нау- ка», 1966. 176 с. 3.2. Моисеев Н. Н. Численные методы в теории оптимальных систем. М., «Нау- ка», 1971. 424 с. 3.3. Растригин Л. А. Статистические методы поиска. М., «Наука», 1968. 376 с. 3.4. Канторович Л. В., Крылов В. И. Приближенные методы высшего анализа. М.—Л., Физматгиз, 1962. 708 с. 3.5. Михлин С. Г. Численная реализация вариационных методов. М., «Наука», 1966. 432 с. 3.6. Гавурин М. К. Лекции по методам вычислений. М., «Наука», 1971. 3.7. Михлин С. Г. Прямые методы в математической физике. М.—Л., Гостех- издат, 1950. 428 с. 3.8. Курант Р., Гильберт Д. Методы математической физики. М.—Л., Гостех- издат, 1951. 476 с. 3.9. Методы оптимизации с приложением к механике космического полета. Под ред. Д. М. Лейтман. М., «Наука», 1965. 538 с. 3.10. Крылов И. А., Черноусько Ф. Л. О методе последовательных приближений для решения краевых задач. «ЖВМ и МФ», 1962, т. 2, № 6, с. 48—53. В блоке 1в определяется направление улучшения исходного вектора ф (<о). С этой целью рассчитываются производные функции (grad cp, ^ (t)) по фор- иуле (grad (p (xi (W, ф (/i)) — (grad (р (х, (^,)) ф, (?,)) 14- д -2, . . .,п+1. После этого исходный вектор tif/o) корректируется по следующей формуле: '<'1<('о)=^к(<о)-«^_1, 1=2, . . .,п+1, где а — положительная константа и вычисления проводятся вновь, начиная с &лока 2. Величину а целесообразно брать в .виде • /п———— \'^. <°1, 2, Если алгоритм приводит к расходящемуся процессу, то необходимо в качестве ^i(tn) взять другой вектор. СПИСОК ЛИТЕРАТУРЫ 4.1. Болтянский В. Г. Математические методы оптимального управления. М., «Наука», 1969. 408 с. 4.2. Болтянский В. Г. Оптимальное управление дискретными системами. М., «Наука», 1973. 446 с. 4.3. Ройтенберг Я. Н. Автоматическое управление. М., <Наука», 1971. 295 с. 4.4. Фань-Лянь-цэнь, Бань Чу-сен. Дискретный принцип максимума. Оптимиза- ция многоступенчатых процессов. М., «Мир», !967. 180 с. 4.5. Фельдбаум А. А. Основы теории оптимальных систем. М., «Наука» 1966. 623 с. 4.6. Гноенский Л. С., Каменский Г. А., Эльсгольц А. Э. Математические основы теории управляемых систем. М., «Наука», 1969. 512 с. Глава 5 Машинные методы оптимизации, основанные на теории линейного и нелинейного дискретного программирования 5.1. ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Линейное программирование наиболее развитая н законченная область математического программирования. Предметом линейного программирования является определение системы параметров, обеспечивающей оптимальное (в заданном смысле) качество управления в рамках сформулированных огра- ничений. Задачам линейного программирования присущи следую- щие специфические черты: показатель качества управления пред- ставляет собой линейную функцию от параметров управления; ог- раничения, накладываемые на область возможных решений, имеют вид линейных равенств или неравенств. Рассмотрим несколько примеров постановки задач линейного программирования. 1. 3 'а д а ч а о п р е д 'е л е .н и я о п т 'и м а л ь н о г о к о .м л л е к с а средств связи по критерию стоимости. Пусть имеет- ся в наличии п различных средств связи (коротковолновые и уль- тракоротковолновые радиостанции, средства радиорелейной, про- водной и спутниковой связи). Каждый из видов связи имеет свои преимущества и недостатки. Различен для них и показатель на- дежности, в качестве которого пусть используется коэффициент готовности К. Для обеспечения высокой надежности связи создается комп- лекс средств связи, работающий в различной обстановке (работа в условиях помех, частая смена пунктов управления и др.). Будем считать, что число различных вар-иантов обстановки равно т. Необходимо создать такой комплекс средств связи, чтобы при любой обстановке был обеспечен требуемый коэффициент готов- ности комплекса Ктк- Пусть известны: __ — стоимость средств связи t'-ro типа с< (<==!, п); — значения коэффициентов готовности средств связи t'-ro типе' при /-м варианте обстановки ft,j(/=l, m). Если в комплексе средств связи используются х,_ средств пер- вого типа, Хг — второго и т. д., то для /'-го варианта обстановки 5* 13Ь формирование вариантов: for j:=l step I until M do TH[J]:=t[kmin,j]; т1п(Тн, M, Tmin, jmin); T6:=Tmin: for 1:=1 step 1 until m do if c(l,i]^OAU[kmin, \]^OAT[kmw, 1]>T6 then T6:-T[kmin, 1]; формирование характеристик: ffl^M+l; for 1:=1 step 1 until m do if \=^i then begin T[(i),l]:=T[kmin, 1]; U[&),l]:=U[k min, 1] end; for ]':=! step 1 until M do if j^jmin then 1[(й,]]:=Тнй; TH[]"min]:=t[to, jmin]:=T[(u, i]:=T6+T[i], U[co,i]:==jmin: max (Тн, M,Tmax,l); Q[(o]:=Tmax; N[(i)]:=N[kmin]+l; M2: end формирования вариантов; goto Ml; M3: for i:=l step 1 until m do output (T[kmin, i]. U[kmin,i]); end end СПИСОК ЛИТЕРАТУРЫ 5.1. Юдин Д. Б., Гольштейн Е. Г. Линейное программирование. Теории и ко- нечные методы. M., Физматгиз, 1963. 775 с. 5.2. Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование. M., «Наука», 1969. 368 с. 5.3. Вентцель Е. С. Исследование операций. M., «Советское радио», 1972. 550 с. Глава 6 Машинные методы оптимизаций^ основанные на теории динамического 6.1. СУЩНОСТЬ ДИНАМИЧЕСКОГО ' ПРОГРАММИРОВАНИЯ В пятидесятых годах XX века был развит новый общий метод решения вариационных задач, названный динамиче- ским программированием. Динамическое программирование пред- ставляет собой математический метод оптимизации решений, при- способленный для исследования многошаговых (многоэтапных) операций, Рассмотрим некоторую физическую систему, которая с тече- нием времени может менять свое состояние. Пусть в любой мо- мент времени ей соответствует некоторый вектор состояния S. Обычно вектор S является многомерным, состоящим из конечногв набора величин Si, Ss. ..., Sn, называемых переменными состоя- ния. В качестве переменных состояния при изучении механических систем могут быть точки в фазовом пространстве (координаты и скорости); при изучении электрических цепей компоненты векто- ра S могут представлять собой токи и напряжения; в экономике— мощности или ресурсы нескольких взаимозависимых отраслей про- мышленности и т. п. Будем считать, что система из одного состояния в другое пере- водится под воздействием управления. Обозначим управление (т. е. всю систему мероприятий, с помощью которой система из- меняет свое состояние во времени) вектором U. Вектор управления U следует выбрать так, чтобы состояние S изменялось некоторым заранее предписанным образом. Иногда важно, чтобы S в течение всего процесса было как можно ближе к некоторой заданной функции Н. В другом случае нас может не интересовать, что происходит с S при О^К.Т, лишь бы его значение в конце процесса оказалось заданным вектором. С процессом изменения состояния S системы обычно связана некоторая оценка, выраженная численно с помощью критерия Q, который зависит от состояния системы S и от принятого управле- ния U. Запишем эту зависимость: Q==Q(S, U). Для постановки задачи оптимизации необходимо еще учесть условия, накладываемые на начальное состояние системы SW и конечное состояние «SW. В простейших случаях оба эти состояния полностью заданы. В других задачах эти состояния могут быть 6—241 161 else sj{j]:=P; з]Ц+1]:=г end; M4: TOp:=Tnp+T;n[k]; оценка .и выбор: for 1:=1 step 1 until p do if 1><о1 then goto M2 else begin for j:=l step 1 until M do if sj[j]^Sl[l,j] then goto M3; for j:=l step 1 until m do if(u[j]=OAUl[l,j]^0)V (u[j]^OUltl,j]=0) then goto M3; j:=sj[l]; 0:=ТЦ]+тпр; j:=Sl'tl,l]; Ql:=tl{l,j]+tnl[l]; if Q0(i^~]~n), (8.1) и выполняются ограничения, заданные в форме неравенств для не- которых функций этих переменных: ^i, • • -,Хп) > 0; (s == l~k; k $n). (8.2) Предполагается, что функции Q и Rs—непрерывные и диф- ференцируемые. Если на переменные наложены ограничения вида ^< мин < ^ < Xi „экс "ли 1 Xi | < nii, 203 3. Для / повторяется процедура пп. 1, 2. 4. Обход пунктов множества заканчивается при выполнении условия l=i(0). Суммарная длина пути вычисляется по формуле L==я^c^,Wxl.W (8-34) г=1 ^ xl,l+^=\• Заметим, что для определения полной длины пути коммивоя- жера к суммарному .пути необходимо еще прибавить расстояния •^oimax и c'im от исходной точки 0, т. е. полная длина пути будет п—1 '- == ^J cl, l+l xl. l+l 1 ^О ^япах х» tmax ' ci (0), xl (0),' (8.35) W ^ax-^/(о^- Рассмотренный формально-эвристический алгоритм на ряде задач показал точность около 5% и снижение затрат машинного времени по сравнению с методом ветвей и границ примерно в 20 раз. Таким образом, формально-эвристические 'методы и соответ- ствующие ям алгоритмы могут достаточно эффективно применять- ся для решения задач линейного программирования. При этом сформированный для данного класса задач набор эвристик рас- пространяется на все задачи класса. Точность решения задач линейного программирования фор- мально-эвристическими методами зависит от класса задач, от ви- да принимаемых эвристик и способа их формализации. Как 'мы видели, в определенных условиях точность формально-эвристиче- ского программирования сравнима с точностью строго формаль- ных методов. Сложность формалыно-эвристических алгоритмов, •их 'времен- ные характеристики я характеристики памяти зависят от вида принимаемых эвристик и способа их формализации. Время реше- ния задач на ЭВМ формально-эвристическими методами в сред- нем в несколько десятков и даже сотен раз меньше времени ре- шения тех же задач строго формальными методами. СПИСОК ЛИТЕРАТУРЫ 8.1. Юдин Д. Б. Математические методы управления в условиях неполной ин- формации. М., «Советское радио», 1974. 466 с. 8.2. Пашкеев С. Д. Некоторые формально-эвристические методы решения задач линейного программирования. — В кн.: Алгоритмы и организация решения экономических задач, вып. 2. М., «Статистика», 1978, с. 34—48. Глава 9 Машинные методы оптимизации в условиях неопределенности 9.1. ОПТИМИЗАЦИЯ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ При рассмотрении реальных проблем повсюду при- ходится сталкиваться с неопределенностью. Действительно, всякие измерения производятся с некоторой точностью, отдельные вели- чины не могут быть измерены принципиально, измерение других может быть связано с такими трудностями, что становится неце- лесообразным. Условия протеканяя процессов и функционирова- ния систем никогда не могут быть полностью определены, так как реальные процессы характеризуются множеством взаимосвязей. Часто появление неопределенности связано с ограниченностью (не- достаточностью) наших знаний о процессе, некоторые стороны протекания процессов (функционирования систем) бывают недо- статочно изучены и потому не представляется возможным вскрыть истинные закономерности их развития. Нередко сознательно аб- страгируются от некоторых сторон .протекания процесса, изучение которых связано с большими трудностями и лишь затемняет ос- новное содержание июследанания. Встречаются ситуации, когда неопределенность связана с сознательной деятельностью людей, образ действий которых неизвестен. Часто это так называемые конфликтные ситуации, когда цели участвующих в конфликте лиц прямо противоположны (и поэтому эти лица стремятся сохранить свои планы в тайне друг от друга). Наконец, существуют процессы ,и системы, развитие которых не описывается детерминированными законами — стохастические процессы и системы. Встречаются задачи, в которых нужно при- нять решение заранее, т. е. в неопределенных условиях. Практи- чески любое описание процессов и систем с помощью строго де- терминированных величин и закономерностей является более или менее далеко идущей идеализацией и связано с заменой реальных процессов и систем их моделями. Адекватное описание реального процесса или системы детерминированной моделью может был получено далеко не всегда. Таким образом, возникает проблема поиска оптимальных ре- шений в условиях неопределенности. При этом неопределенноста может проявляться как неопределенность цели и условий, харак- теризующих протекание процесса или функционирование системы возможность и эффективность управлений. ей ТАБЛИЦА 9.16 < i SB, SB; SB, / SA, SA, SA, s, s, s. s. p ч 1 3 9 0 11 2 2 9 0 0 9 0 9 0,0,1 0,1,0 2 2 11 9 п 2 4 18 0 4,5 9 4,5 9 0-*- ' "• 2 • 2 0,1,0 3 2 13 18 11 3 13 l8 11 3,67 6 4,5 6 О,-1——— 0 2 -'- ' 2 2 "• Q • Q 0 0 4 2 15 27 11 3 22** 18 22 2,75 5,5 4,5 5,5 0-^- 'V , > ---- „ ' 1 2 2 °'T- 2 5 1** 22 29 20 3 31 18 33 4,0 6,6 4,5 6,6 0,-1-,-1- о.уу 2 2 6 3 31 29 31 2 33** 27 33 4,84 5,5 4,84 5,5 1 1 1 6' 2' 3 ».t.t 7 Г* 38 31 40 2 35 36 33 4,43 5,14 4,84 5,14 1 1 1 4 3^УТ fi" 9* ЧU f, *J 8 2 40 40* 40 2- 37 45 33 5,0 5,61 5,0 5,14 1 1 1 A Q..^.t 4' 2' 4 9 2 42 49 40 3 46 45 44 4,45 5,11 5,0 5,11 -1 \ \ ".-К 4' 2' 4 10 1 49* 51 49 Г 53 47 53** 4,9 5,3 5,0 5,11 1 1 1 ^ А°4-1 4' 2'"4 J 0 11 3" 58 51 60 2 55 56 53 4,64 5,09 5,0 6,09 1 1 1 1 6 4 4' 2' 4 11 11 11 5,0 5,09 1 6 4 424 11 11 11 СПИСОК ЛИТЕРАТУРЫ 9.1. Вентцель Е. С. Исследование операций. М., «Советское радио», 1972. 552 с. 9.2. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления. М., «Наука», 1969. 120 с. 9.3 Миддлтон Д. Введение в стохастическую теорию связи. М., «•Советское ра- дио», т. 1, 1961. 782 с., т. 2, 1962. 831 с. 9.4. Мангейм М. Л. Иерархические структуры. М., <Мир», 1970. 180 с. 9.5. Дынкин Е. Б., Юшкевич А. А. Теоремы и задачи о процессах Маркова. М., «Наука», 1967. 232 с. 9.6. Ховард Р. А. Динамическое программирование и марковские процессы. 1964, 190 с. 9.7. Лыес Р. Д., Райфа X. Игры и решения. М., ИЛ, 1961. 642 с. 9.8. Мак-Кинсн Дж. Введение в теорию игр. М., Физнатгиз, 1960. 420 с. Глава 10 Машинные методы оптимизации графов и граф-сетей 10.1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ На практике с понятием графа встречаются очень часто. Если изобразить сеть дорог, связывающую некоторые горо- да линиями, а города кружками, то получается схема. Такая же по форме схема возникает, если изобразить сетку телеграфных узлов, систему электрических связей или схему информационных связей между алгоритмами некоторой сложной задачи. Таким об- разом, во многих случаях, отвлекаясь от физического смысла, мож- но изобразить в виде схемы системы различной физической приро- ды. Такие схемы в математике принято называть графами. Графом называется совокупность множества точек, называемых вершинами графа, и множества дуг, соединяющих эти точки. По- нятие графа лишь геометрически отражает связи между элемен- тами объектов. Для количественной оценки этих связей удобно пользоваться понятием сети. Сетью называется конечный граф без петель, у которого: 1) существует одна и только одна такая вершина Xi, которая не имеет входящих дуг (эта вершина называется входом или ис- точником сети); 2) существует одна и только одна такая вершина Хр, которая не имеет выходящих дуг (эта'вершина называется выходом или стоком сети); 3) каждой дуге графа и поставлено в соответствие некоторое число г (и), называемое пропускной способностью сети. Заметим, что хотя и сделано предположение о том, что сеть имеет лишь один источник и один сток, на практике встречаются задачи, когда, на самом деле, имеется несколько источников и стоков, когда разрешается поток из любого источника в любой сток. Но эти задачи легко свести к случаю единственного источ- ника и единственного стока добавлением к сети двух новых вер- шин. Сеть, моделирующая определенный физический процесс, назы- вается сетевой моделью данного процесса. При этом ориентация дуг графа осуществляется в соответствии с логикой (технологией) этого процесса. Виды сетевых моделей, различные по характеру отображения, возникают в результате различной интерпретации ,25.1 — Mj — вторая оценка пути. Этап 1. 1. Помечается начальная вершина t=A следующим набором признаков: N, == 0; f, = {1}; Е, == 0; Mi = т.; г = А. •2. Выбирается начальное приближение для величины кратчай- шего пути L по формуле L= mine,,, где i=A, J(i) —.подмножество /е-/ (О вершин /.удовлетворяющих условиям: т, < р^, если К (j) ф К (i); т, + т? < Р/, если К (j} = ?i (г); K(i) — подмножество вершин /д, включающее i. Этап 2. 1. Выбирается очередная помеченная вершина t==t* со своими пометками N„ fi, Е{, Mi. 2. Для ,f=i* выбираются для пометки вершины /==/*, которые удовлетворяют одному из множеств следующих условий: ^==1; МЛ-МО; ^L, (10.30) где i — вершины, принадлежащие к множеству помеченных вер- шин; /—.вершины, для .которых .выполняется одно из следующих множеств условий: а) т„ = 1, К (j) Ф К (0, т/ ^ р,; б) т„ == 1, ^ (j) = ^ (Q, М, + г, < р,. Среди чисел (10.30) определяется наименьшее и берется в ка- честве нового приближения для L. абв 2. Производится переход к этапу 2. Построение графа наименьшей длины. Боль- шое практическое значение имеет следующая задача, которую можно сформулировать в виде задачи о строительстве сети дорог (вместо сети дорог можно рассматривать сеть линий связи, линий электропередач и т. п.). Пусть имеется т городов, которые нужно соединить между собой сетью дорог. Для каждой пары городов ft, j) известна стоимость Сц строительства соединяющей их дороги. Задача состоит в том, чтобы построить самую дешевую из воз- можных сетей дорог. В графе, изображающем сеть дорог, верши- на'м f соответствуют города, а ребрам—дороги, их соединяющие. Назовем величину Ci, длиной ребра [г, /']. Тогда поставленная задача адекватна задаче построения графа минимальной длины. Граф наименьшей длины всегда является деревом, так как если бы он содержал цикл, то можно было бы удалить одно из ребер этого цикла и вершины все еще остались бы соединенными. Следовательно, для соединения т вершин достаточно построить т—1 ребро. Граф наименьшей длины можно построить, пользуясь следую- щим простым алгоритмом: 1. Присвоить нуль элементам матрицы плана {хц} и пометкам вершин Ui, i. ]=\, т. 2. Выбрать такую пару вершин i==:i*, j==j* графа, для которых выполняются следующие условия: пl Л п! = °; х!] = °> c^^ ,. = min min cih i j т. е. выбрать среди всех пар разноименных вершин (i, j) графа такую, у которой хотя бы одна из вершин не помечена, ребро [i, j] не включено в план {хц} и значение Сг, минимально. 3. Соединить вершины f* и /'* ребром, т. е. присвоить л'г»_,.=1 и пометить рассматриваемые вершины, т. е. присвоить /7,.=1, Я,.=1. Операции 2 и 3 повторить т—1 раз. Каждое дерево, построенное таким образом, будет иметь мини- мальную длину, равную сумме L = 2 2; Xijdj. i I СПИСОК ЛИТЕРАТУРЫ 10.1. Ермольев Ю. М., Мельник И. М. Экстремальные задачи на графах. Киев, «Наукова думка», 1968. 176 с. 10.2. Давыденко В. П., Лоскутов Н. Г., Иванов Л. А. Основы военной кибер- нетики. Л., Академия связи, 1970. 403 с. 10.3. Коршунов Ю. М. Математические основы кибернетики. М., «Энергия», 1972. 376 с. 10.4. Кофман А., Дебазей Г. Сетевые методы планирования и их применение. М.. «Прогресс», 1968. 181 с. 10.5. Барсук В. А., Губин Н. М. Математические методы планирования и управ- ления в хозяйстве связи. М., «Связь», 1966. 340 с. 10.6. Вагнер В. Основыв^сследования операций. М., <Мир», 1972. 335 с. 10.7. Романов А. Н., Фролов Г. А. Основы автоматизации систем управления. М., Воениздат, 1971. 248 с. 10.8. Форд Р., Фалкерсон Д. Потоки в сетях. М., «Мир», 1966. 276 с. 269 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Алгоритм оптимизации 82 Базисное решение 136 Байесов случай 221 Вариационное исчисление 86 Градиентные методы оптимизации 183 Граф 48, 251 Декомпозиция объекта оптимизации 76 Информация 8 — характер 8 Исчисление 30 " — вариационное 30 Игра 51 — методы 51, 68 — основная теорема 243 — стратегии 51, 243 Корреляционная теория 56 Критерий оптимизации 9, 78 Линейная форма 43 Модель 7 — математическая 9 — объекта оптимизации 77 Методы оптимизации 29 — — итерационные 97 — — прямые 92 — ветвей и границ 156 — Монте-Карло 204 Объект 9 — оптимизации 9, 76 —- управления 9 Оптимизация 9 — задачи 75 — критерии 9, 7'8 — методы 29, 81 Принцип максимума 35, 106 Программирование 39 — дискретное 151 — динамическое 39, 161 — целочисленное 151 — линейное 43 Процессы 58 — марковские 58, 229 Система 6 — тип б — условия работы 6 Статистические решения 63 Управление 8, 9 Условия неопределенности 217, 240 Функция (функционал) — критерия оптимизации 9, 78 Формально-эвристические методы оп- тимизации 208 ОГЛАВЛЕНИЕ Предисловие ................. 3 Введение .................. 4 Список литературы ............... 5 ' Глава 1. Элементы теории оптимизации 1.1. Особенности задачи оптимизации .......... 6 1.2. Математическая постановка задачи оптимизации ...... 9 1.3. Методы оптимизации в детерминированных задачах ..... 29 1.4. Методы оптимизации в стохастических задачах ...... 54 Список литературы .............. 72 Глава 2. Методика постановки и решения задач оптимизации на ЭВМ 2.1. Общие сведения ............... 74 2.2. Содержательная постановка задачи оптимизации ...... 75 2.3. Композиция и декомпозиция объектов оптимизации ..... 76 2.4. Выбор машинно-математической модели объекта оптимизации . . 77 2.5. Формирование критерия оптимизации ......... 78 2.6. Выбор машинного метода оптимизации ......... 81 2.7. Разработка и реализация машинного алгоритма оптимизации . . 82 Список литературы .............. 84 Глава 3. Машинные методы оптимизации, основанные на применении классических математических методов 3.1. Вводные замечания .............. 85 3.2. Методы оптимизации, основанные на классическом вариационном ис- числении ................. 86 3.3. Прямые методы оптимизации ........... 92 3.4. Итерационные методы оптимизации .......... 97 Список литературы . . ............ 105 Глава 4. Машинные методы оптимизации, основанные на принципе максимума 4.1. Формальная постановка задачи . . ......... 106 4.2. Различные постановки задач принципа максимума ..... 109 4.3. Оптимизация линейных систем . .......... 111 4.4 Задача оптимального быстродействия . ........ 116 4.5. Задача со свободным правым концом ......... 123 4.6. Задача с подвижным правым концом ......... 127 Список литературы . . ............ 130 Глава 5. Машинные методы оптимизации, основанные на теории линейного и нелинейного дискретного программирования 5.1. Постановка задачи линейного программирования ...... 131 5.2. Основная задача линейного программирования ...... 134 5.3. Симплексный метод решения задач линейного программирования . 135 5.4. Транспортная задача линейного программирования . . . . . 143 5.5. Сущность дискретного программирования . . ...... 151 5.6. Метод ветвей и границ . ............ 156 Список литературы . . ............ 160 271 Глава 6. Машинные методы оптимизации, основанные на теории динамического программирования 6.1. Сущность динамического программирования . ...... 161 6.2. Задача определения критического пути в графе ...... 164 6.3. Задача распределения ресурсов . . ......... 168 6.4. Процедура динамического программирования . . ..... 169 6.5. Машинный алгоритм оптимального планирования загрузки вычисли- тельной системы АСУ . . ........... 173 Список литературы . . ............ 182 Глава 7. Машинные методы оптимизации, основанные на градиентных методах 7.1. Сущность градиентных методов . . ......... 183 7.2. Метод градиента ............... 185 7.3. Метод наискорейшего спуска . .......... 192 7.4. Метод Гаусса—Зайделя . . . .......... 199 7.5. Поиск при наличии ограничений . .......... 200 Список литературы . . ............ 202 Глава 8. Специальные машинные методы оптимизации 8.1. Общие замечания . . ............. 203 8.2. Метод Монте-Карло . . . ........... 204 8.3. Метод обхода узлов пространственной сетки ....... 206 8.4. Некоторые формально-эвристические методы . ...... 208 Список литературы . . ............ 216 Глава 9. Машинные методы оптимизации в условиях неопределенности 9.1. Оптимизация в условиях неопределенности . . . . . . . 217 9.2. Байесовский случай . . . ........... ?21 9.3. Марковский случай . . ............ 229 9.4. Оптимизация в условиях полной неопределенности ..... 240 Список литературы . . ............ 250 Глава 10. Машинные методы оптимизации графов и граф-сетей 10.1. Основные понятия и определения . ......... 251 10.2. Алгоритм определения максимального потока в сети с ограниченны- ми пропускными способностями . ......... ??А 10.3. Метод определения кратчайшего пути в сети ....... :'\"<9 10.4. Метод определения допустимого кратчайшего пути в сети . . . 263 Описок литературы .............. 270 С Д. ПАШКЕЕВ р. и. минязов В. Д. МОГИЛЕВСНИЙ МАШИННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ В ТЕХНИКЕ СВЯЗИ ДОПУЩЕНО МИНИСТЕРСТВОМ СВЯЗИ СССР В КАЧЕСТВЕ УЧЕБНОГО ПОСОБИЯ ДЛЯ ЭЛЕКТРОТЕХНИЧЕСКИХ ИНСТИТУТОВ СВЯЗИ Под редакцией проф. С. Д. ПАШКЕЕВА Издательство «С в я зь» Москва 1976