Модель задачи стохастического программирования имеет вид: минимизировать

/о(Х,ш) (7.211)

при ограничениях

/г(Х,юХО, i = l,m; (7.212)

Х^Х, (7.213)

j,g щ - элемент некоторого вероятностного пространства; X - множество решений.

С каждым решением X можно связать числовые параметры /(jf, ю), £ = О, 1,..т, зависящие от него и от случайных параметров ю. Решения X в одних задачах могут быть детерминированными, а в других - зависящими от случайного параметра ю.

Различают задачи оперативного и задачи перспективного стохастического программирования.

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

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

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

В задачах перспективного стомстического программирования при детерминированном решении X модель (7.211) - (7.213) часто заменяется следующей моделью: минимизировать

Foil) = Efo{X,iB) =jfoiX,(ii)P{dw) (7.214)

при ограничениях

Fi (X) = Efi {X, ю) = ; А (Х, (О) Р (dw); i = (7.215)

Х^Х (7.216)

или минимизировать

Ч*-о(Х) =-Р{/о(Х,ш) >G} (7.217)

при ограничениях

Ч*-г(Х) = Р{/г(.юХО} - р,>0, i = l,m; (7.218) Х^Х, (7.219)

где е(Х)-математическое ожидание функции /(Х, ю), 1=0, \,...,т; (X) - вероятность отклонения функции f{X,a), t,=0, 1,m; а, pt - некоторые константы.

Могут рассматриваться модели (7.214), (7.218), (7.219) или (7.217), (7.215), (7.216).

Рассмотренные модели могут быть дополнены дисперсиями функций f{X,(o), ,==0, 1,m, или другими моментами этих функций.

В задачах оперативного стохастического программирования решение X зависит от случайного параметра ю, т. е. является случайным. В результате эксперимента из всей совокупности событий, образуюш,их 0-алгебру F основного вероятностного пространства, доступна наблюдению некоторая часть событий некоторой о-под-алгебры G, Gsf. Поэтому функция Х(а)) должна быть измеримой относительно G (G-измеримой).

В этих условиях модель задачи стохастического программирования имеет вид: минимизировать

/=о(Х(ш)) =£/о(Х((о),ш) (7.220)

при ограничениях

/=г(Х(ш)) =£fi(X((u),(o)<0, i=l,m; (7.221)

ХеХ. (7.222)

Таким образом, задача стохастического программирования за-ключается в том, что необходимо найти G-измеримую вектор-функцию X(ю) = (Xi(ю), Х2((d), ...,Хп((,:>)), которая удовлетворяет ограничениям (7.221) -(7.222) и минимизирует целевую функцию (7.220).

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

Рассмотрим методы решения задач стохастического программирования.

В задачах, описываемых моделью (7.214) -(7.216), обычно имеется возможность определить в результате эксперимента значения функций [е(Х, (о), =0,J,га, для фиксированных ю. Если математические ожидания (Х), =0, \,...,т, можно определить, задача (7.214)-(7.216) сводится к задаче нелинейного программирования, так как стохастическая природа такой задачи прояв^ ляется только при определении математических жиданий функций /е(Х, (о), 5=0, \,...,т, т. е. при определении е(Х, ю), =0, l,...,/ -

Часто стремятся определить Fi{X, ю), i=0, 1,...,т, а затем, применяя методы нелинейного программирования, решить задачу стохастического программирования (7.214) -(7.216).

В случае невозможности определения Fi{X, со), i=0, 1, m, задачу (7.214) - (7.216) заменяют приближенным детерминированным эквивалентом, полученным при замене случайной величины ю его средним значением ю.

Методы решений, основанные на информации о значениях fi(X, ю), 1=0, 1,...,т, называют прямыми методами стохастического программирования, все остальные методы - непрямыми.

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

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

Если в задаче (7.214) - (7.216) вектор X - детерминированный (задача перспективного стохастического программирования), то эта задача формально является задачей нелинейного программирования. Если вектор X - функция G-измеримая относительно исходного вероятностного пространства (Q, F, Р) (задача оперативного стохастического программирования), то задача (7.214) - (7.216) является задачей программирования в абстрактных пространствах. Полученные условия оптимальности в этих случаях нельзя проверить на оптимальность, так как производные функций Fi {X) неизвестны.

В практических задачах решение X (ю) кроме измеримости относительно некоторой 0-подалгебры решений должно удовлетворять определенным требованиям реализуемости рассматриваемой системе принятия решений. Например, если X (w) -управляющее воздействие в системе управления движением объекта и (О - отклонение этого объекта от расчетной траектории, то Х((о) можно отыскивать не среди всевозможных функций от ю, а только среди линейных функций ц>{У, ю) (где Y - неизвестные параметры) , так как принцип управления пропорционально отклонению легко реализуется.

Отыскание вектора Х{(л) в классе измеримых функций связа- но с большими временными затратами, а решение задачи часто необходимо внедрять быстро, непосредственно за наблюдением. Поэтому прибегают к параметризации решения Z((o), т. е^ реше-ние Х^а)) отыскивается в виденаперед заданной функции X (а)- =Х(У, (o) - [xi{Y, a),...,Xn(Y, ю)], определенной с точностью до вектора Y={yi,...,yi), значение которого вычисляется в зависимости от распределения P(d(o) до наблюдения ю. В результате такой параметризации задача оперативного стохастического программирования сводится к задаче перспективного стохастического программирования.

Рассмотрим частные случаи.

Допустим, что пространство наблюдений совпадает с пространством состояний, т. е. в £езультате наблюдений ю становится известным. В этом случае Х{а) является решением задачи: минимизировать

/о(Х,(о) (7.223)

при ограничениях

/г(Х,(оХО, f=l,m; (7.224)

Х^Х. (7.225)

Часто возникает задача, как определить решение Х{а) при новом значении ю, не прибегая к решению задачи (7.223) - (7.225), а используя решение при старом ю.

1. Пусть задача (7.223) - (7.225) является задачей линейного программирования при заданном ю: минимизировать

СХ (7.226)

при ограничениях

AXAo(w); (7.227)

X > 0. (7.228)

В этом случае X {(о) =ZAo{(o), где Z - детерминированная матрица с неизвестными элементами, значения которых определяются до наблюдения Ао{а). Матрицу Z можно выбрать из условия минимума

Fo (Z) = Р {С, ZZo ( )} > а (7.229)

при ограничениях

Fi (Z) = Р{{AZAo(ю)) г < aio (ш)} > Рг, i=l,m, (7.230)

где а. Pi, t = 1, tn - некоторые константы.

2. Пусть имеется задача стохастического программирования с линейными ограничениями: минимизировать

п

ЕсЛ(о)Хз (7.231)

при ограничениях

Е (ю) Xj < а^о (со), t = 1, m; (7.232)

ij=i

Xj>0, i=hn. (7.233)

Решение X- {xi,Xn) выбирается после наблюдения ю. Пусть Zij удовлетворяют условиям:

Ei3-=hO<Zij\,i=l,m; j = l,n. (7.234)

Задачу (7.231) - (7.233) можно свести к п задачам минимизации:

минимизировать

Cj{c)xj (7.235)

при ограничениях

ац (ю) Xj < aio ((о) гц, г = 1, т; (7.236)

Xj > О, (7.237)

где можно рассматривать как часть ресурса i, направленного для производства /.

Поскольку решение задачи (7.235) - (7.237) зависит от ю

Z = {zij, i = 1, m; / = 1, n},

т. е. X является функцией от Z и ю, то можно рассмотреть задачу: минимизировать

F{Z) = Ei:Cj(w)Xj{Z,w) (7.238)

При о'-раничениях

Zij = l, i = l,m; (7.239) .

0<Zij<l, i=\,m; j=l,n. (7.240)

Решая задачу (7.238) - (7.240), получим оптимальное решение Z = {Zij, i = \,т; j = В некоторых случаях для задачи (7.235) - (7.237) можно опре-

п

делить функцию распределения величины Cj ((o)Xj (Z, ю), опреде-

п

лить математическое ожидание F(Z) = £ Cj (a))Xj (Z, со) и ре-

шить задачу нелинейного программирования.

3. Пусть известно математическое ожидание ю-Еа. Тогда задачу (7.211) -(7.213) можно заменить задачей нелинейного программирования: минимизировать

/о(Х,£ю) . (7.241)

при ограничениях

fi (Х, Еш) < О, i=l,m; (7.242)

Х^Х. (7.243)

Если fi{X, ю), i=l,m,- линейные функции относительно ю, то решение задачи (7.241) - (7.243) совпадает с решением задачи (7.211) - (7.213), а при малой дисперсии со ее решение будет близким к решению задачи (7.211) -(7.213).

Если выполняется условие

Fi (Х) = Efi (X, ю)< fi {Х,Еа>), i = О, 1,т, (7.244)

то любое допустимое решение задачи (7.241) - (7.243) является допустимым для задачи (7.211) - (7.213) и

min Fo {X) < min fo {X, E&). (7.245J

в других случаях решение задачи (7.241) - (7.243) существенно отличается от решения задачи (7.211) - (7.213).

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

Пусть дана задача: минимизировать

t(xu...,Xn) (7.246)

при ограничениях

Х= {х ...,Хг.) Х, (7.247)

где f{X)-выпуклая вниз функция (точные значения f{X) и ее производных вычислить нельзя); X - выпуклое замкнутое множество.

Пусть (Q, А, Р) - некоторое исходное вероятаостное пространство, (О - множество элементарных событий, а Х'(а)), /=0, I,...,- последовательность случайных точек, определенная по правилу

= я.(Х' - рф?Ч )). / = О, 1,(7.248)

где пх - оператор проектирования на множество X; Х° - производная точка пространства R; pi - шаг движения; yi - нормирующий множитель (величины рг и yi измеримы относительно о-под-алгебры Gi); Чш) -случайный вектор, условное математическое ожидание которого

£(Ч ) °. XI) = а^т 1 = 0,1,...; (7.249)

ai и Б' = (Ьь Ьп) - неотрицательная случайная величину и случайный вектор, зависящие от последовательности (Х°,X) или, более точно, измеримые относительно о-подалгебры Gi, индуциро-

А

ванной семейством случайных величин (Х°.....X); fl{X)-обоб

щенный градиент, т. е. вектор, удовлетворяющий для любых Z неравенству

fiz)-f(xi)>{fxm,z-x).

Вектор удовлетворяющий условию (7.249) с точностью до ai и B, в^среднем совпадет с вектором обобщенного градиента. Если а[=1,В'=0, то вектор t является стохастическим обобщенным градиентом (стохастическим квазиградиентом), а процедура (7.248) называется методом проектирования стохастических квазиградиентов.

Процедура (7.246) - (7.249) может сходиться к решению задачи (7.246) - (7.247) в различном смысле: по вероятности, в сред-

нем квадратичном, с вероятностью 1. В последнем случае за приближенное решение задачи при большом / можно принять ХК

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

Стохастические задачи на безусловный экстремум позволяет решать метод стохастической аппроксимации. В этом методе при минимизации целевой функции Ef{X, ю) направлением спуска выбирают антиградиент функц™ f(X, ю) вместо неизвестного антиградиента- Fx{X), где F{X)=Ef(X,(ii), т. е. вместо обычного градиентного метода рассматриваются итеративные процедуры поиска, определяемые соотношениями

Xi+ = Xi-pMXKw), / = 0,1.....

Если при каждом ю градиент fx{X,a) вычислить нельзя, то градиент определяется численно и

3=1 (7.250)

где е' - орт j-й оси; (nh, s - О, 1,...,п - результаты независимых по / = О, 1,... наблюдений случайной величины ю; р/ - длина шага в 1-й итерации; Аг - смещение по осям. Можно считать ю' = = О) = = (о'п =

Метод (7.250) является частным случаем процедуры (7.248) - (7.249) при

п flX -\- Aiei,(oi) -f{X,(oj

= Z-К7--

г л a в a 8

СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ

8.1. ОБЩАЯ ХАРАКТЕРИСТИКА СИСТЕМ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ

На современном этапе развития единого интегрированного процесса наука - техника - производство все более важная роль отводится системам автоматизированного проектирования (САПР) -одному из важнейших факторов ускорения научно-технического прогресса и эффективного использования ЭВМ в области управления сложными системами.

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

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

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

Отмеченные особенности современного проектирования делают этот процесс чрезвычайно сложным с точки зрения получения конечных оптимальных результатов. К этому следует добавить огромные масштабы и трудоемкость проектно-конструкторских работ. Например, в области строительства в нашей стране функционирует свыше 1700 проектно-изыскательных организаций, в которых занято более 750 тыс. человек. Ежегодно в отрасли строительства выполняется огромный объем проектных работ на сумму около трех миллиардов рублей. Традиционная технология проектирования, основанная на безмашинной (ручной) форме организации проектирования, использующая простейшие технические средства проектирования - кульманы, логарифмические линейки, готовальни и т. д., не может удовлетворять требованиям ускорения научно-технического -прогресса.

Существенное усложнение проектируемых объектов, многовариантность проектирования, противоречивость критериев оптимальности, дефицит трудовых ресурсов, огромные масштабы и краткие сроки проектно-конструкторских работ остро поставили вопрос широкого применения автоматизированных технологий проектирования объектов, изделий, систем во всех областях народного хозяйства. КПСС и Советское правительство придают огромное значение развитию методов и средств автоматизированного проектирования. В Основных направлениях экономического и социального развития СССР на 1986-1990 годы и на период до 2000 года, принятых на XXVII съезде КПСС, говорится:

Развивать специализацию проектных и изыскательских организаций... Шире внедрять автоматизированную систему проекти-

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

В области строительства вопросы широкого внедрения автоматизации проектирования стоят очень остро. При сохранении традиционных методов проектирования с использованием реальной численности проектировщиков в самое ближайшее время можно удовлетворить не более 50 % потребностей прироста объемов про-ектно-изыскательных работ, вызванного развитием капитального строительства. Без использования методов и средств автоматизированного проектирования невозможно удовлетворить возрастаю-nUi- требования к качеству проектов, снижению стоимости и материалоемкости проектируемых объектов, повышению темпов проектных работ. Перед проектными организациями поставлена задача довести уровень автоматизации проектных работ в целом по стране до 20 %.

Основными целями внедрения САПР в отрасли строительства являются: существенное повышение производительности труда при выполнении проектных работ; снижение капитальных затрат на строительство; сокращение расходов материалов и технико-экономических ресурсов.

Под автоматизированным проектированием понимается проектирование, при котором преобразования описаний объекта и алгоритма его функционирования, а также представление описаний на различных языках и в различной форме осуществляются взаимодействием человека и ЭВМ. Системы, основанные на использовании ЭВМ и экономико-математических методов, предусмотренные для автоматизации проектно-конструкторских работ, получили название систем автоматизированного проектирования (САПР). САПР - организационно-техническая система или иначе- система человек - машина , в которой сбор, хранение и обработка информации, необходимой для эффективного и качественного проектирования, осуществляются на основе комплекса средств автоматизации проектирования, взаимосвязанных с необходимыми подразделениями проектных организаций или коллективом специалистов - пользователями системы.

Основу комплекса технических средств (КТС) САПР составляет ЭВМ и связанное с ней разнообразное периферийное оборудование. Характерной особенностью САПР является комплексное использование ЭВМ как для .автоматизации творческого труда, так и для автоматизации рутинных операций. В первом направлении ЭВМ используется как мощная логико-вычислительная система для автоматизированного поиска и выбора оптимального варианта проектно-конструкторских решений на базе проектирова-

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

Задача заключается в том, чтобы наиболее полно использовались возможности человека и ЭВМ, дополняющие друг друга в сложном процессе проектирования. К кругу вопросов, решение которых недоступно машине и, следовательно, возлагается на человека, относятся, прежде всего, формулировка конечной цели-, декомпозиция ее на отдельные иерархические уровни. В отличие от ЭВМ человек способен оценить те аспекты решаемых задач, которые трудно поддаются количественной оценке, например социальные, эстетические и другие факторы. Человек способен формулировать критерии оценки решаемых задач, учитывать факторы, возникающие в процессе проектирования, включать их в механизм оценки, использовать опыт, интуицию, воображение, принимать решение при неполных исходных данных. Короче говоря, главная отличительная черта человека, определяющая его роль и место в САПР как человеко-машинной системе,- способность к неформальному мышлению, к изменению стратегии действий в любой момент процесса проектирования, гибкость мышления.

В свою очередь, ЭВМ, в отличие от человека, способна хранить огромные объемы информации при очень коротком времени доступа к ней, имеет чрезвычайно высокое быстродействие, высокие надежность и производительность в выполнении шаблонных операций. ЭВМ в САПР реализует сложнейшие законы управления многими техническими, в частности, исполнительными устройствами.

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

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