СОДЕРЖАНИЕ

Перечень условных обозначений, символов, единиц, сокращений и терминов 7

Введение 8

1 Анализ предметной области 9

2 Постановка задачи условной оптимизации 13

3 Обзор существующих методов решения задач условной оптимизации 15

4 Математическое обеспечение элементов подсистемы оптимизации непрерывных параметров СУА 17

4.1 Алгоритм метода штрафов 17

4.2 Алгоритм комбинированного метода штрафных функций 21

4.3 Алгоритм градиентного метода штрафных функций 26

5 Выбор среды и языка программирования 29

6 Разработка программного средства 30

7 Экспериментальные исследования 32

7.1 Задача оптимального проектирования контейнеров 32

7.1.1 Постановка задачи 32

7.1.2 Подготовка и ввод исходных данных 33

7.1.3 Выполнение расчетов 34

7.1.4 Анализ полученных результатов 36

7.2 Задача распределения топлива в силовых установках 39

7.2.1 Постановка задачи 39

7.2.2 Решение задачи 42

Выводы 44

Перечень ссылок 45

Приложение А. Графический материал дипломной работы 46

Приложение Б. Руководство пользователя 54

Приложение В. Текст программы 70

Приложение Г. Спецификация 79

Приложение Д. Ведомость дипломной работы 81

Перечень условных обозначений, символов, едениц, сокращений и терминов

ГМДШ	– Градиентный метод с дроблением шага
КМШФ	– Комбинированный метод штрафных функций
МШ	– Метод штрафов
ПС	– Программное средство
САПР	– Система автоматизированного проектирования
СУА	– Системы управления и автоматики
ЭВМ	– Электронно-вычислительная машина

ВВЕДЕНИЕ

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

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

Задачей данной дипломной работы и является разработка одного из таких элементов, а именно элемента подсистемы оптимизации непрерывных параметров СУА.

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

АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ

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



Рисунок 1.1– Обобщенная структурная схема СУА

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

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

Оптимизация – это процесс приведения объекта (системы) в оптимальное (наилучшее) состояние. Для проведения оптимизации необходимы: математическая модель объекта, целевая функция и оптимизационный алгоритм (рис. 1.2). Целевая функция формализует требования, предъявляемые к объекту (максимизация коэффициента усиления, увеличение надежности, снижение стоимости, максимизация прибыли и т.д.). Оптимизационный алгоритм ищет экстремум целевой функции.



Рисунок 1.2– Составные части процесса оптимизации

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

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

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

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

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

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

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

Если помимо подбора параметров необходимо еще и определить структуру объекта (например, усилителя), то мы будем уже иметь дело со структурно-параметрическим синтезом, который решается при помощи алгоритмов дискретно-непрерывного математического программирования. Если задача параметрической оптимизации сейчас решается практически для любых объектов, то развитие структурно-параметрической оптимизация сейчас находится лишь на начальной стадии развития [1, 2, 3].

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

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

ПОСТАНОВКА ЗАДАЧИ УСЛОВНОЙ ОПТИМИЗАЦИИ

При формулировке реальных задач оптимизации – задач технического проектирования, задач распределения ресурсов и других – из физических, технических или экономических соображений обычно приходится накладывать на переменные известные ограничения. Например, на пассивной RC-цепи не может быть отрицательной емкости, нельзя распределять воду, если ее нет в резервуаре, нельзя увеличивать давление в сосуде, если этого не допускает прочность. Таким образом, хотя безусловная оптимизация и является очень важной для понимания основ методов оптимизации, в ней не содержится всего необходимого материала для решения многих практических задач, в которых возможен произвольный выбор точек . В подобных задачах этот выбор может производиться только из некоторого подмножества пространства . Подмножество обычно задается «неявно», системой дополнительных уравнений, называемых уравнениями ограничений или просто ограничениями. Эта система может состоять из ограничивающих равенств, ограничивающих неравенств или тех и других вместе. Если определяется совокупностью всех точек в , которые удовлетворяют системе уравнений:

, (2.1)

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

(2.2)

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

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

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

Требуется найти локальный минимум целевой функции на множестве , то есть такую точку , что

(2.3)

где

ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ УСЛОВНОЙ ОПТИМИЗАЦИИ

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

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

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

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

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

Можно выделить несколько подходов к решению задачи:

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

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

в) метод множителей Лагранжа. В данном методе добавление штрафной функции производится не к целевой функции, а к ее функции Лагранжа. В результате возникает модифицированная функция Лагранжа.

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

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

Последовательность строится по правилу:

, , (3.1)

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

К описанной группе методом относится метод проекции градиента и метод возможных направлений Зойтендейка [5,6,7].

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

Математическое обеспечение Элементов подсистемы оптимизации непрерывных параметров СУА

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

(4.1)

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

Штрафные функции конструируются, исходя из условий:



причем при невыполнении ограничений, в методе штрафов при а следовательно и , то есть чем больше , тем больше штраф за невыполнение ограничений, а в комбинированном методе при [5].

4.1 Алгоритм метода штрафов

Как правило, в МШ для ограничений типа равенств используется квадратичный штраф, а для ограничений типа неравенств – квадрат срезки. Для лучшего понимания смыслов данных штрафов, необходимо подробнее рассмотреть их. Итак, рассмотрим квадратичный штраф, используемый для учета ограничений-равенств (рис. 4.1):

(4.2)

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



Рисунок 1.3– Квадратичный штраф

Для учета ограничений-неравенств, в МШ, применяется штраф типа квадрата срезки (рис. 4.2):

, (4.3)

где - срезка функции:

(4.4)



Рисунок 1.4– Штраф типа квадрата срезки

Заметим прежде всего, что этот штраф внешний, и стационарные точки функции действительно могут оказаться недопустимыми. С другой стороны, недопустимые точки не создают в данном случае дополнительных сложностей по сравнению с допустимыми: различие между ними стоит лишь в том, что в допустимых и граничных точках штраф равен нулю. Штраф типа квадрата срезки весьма удобен, в частности, тем, что функция определена и непрерывна всюду. Вычисления необходимо проводить с положительным параметром и после решения очередной подзадачи безусловной минимизации увеличивать его [8].

Следовательно, функция штрафа в МШ будет иметь вид:

, (4.5)

а вспомогательную функцию можно записать следующим образом:

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

Блок-схема алгоритма МШ находится на рис. 4.3.



Рисунок 1.5– Блок-схема алгоритма МШ

Следует заметить, что:

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

б) начальное значение параметра штрафа должно быть больше нуля, а число больше единицы, обычно а ;

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

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

4.2 Алгоритм комбинированного метода штрафных функций

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

Смысл квадратичного штрафа подробно описан в пункте 4.1.

Переходя к ограничениям-неравенствам, можно сказать, что в КМШФ могут применяться два типа штрафов: логарифмический и задаваемый обратной функцией. Одним из самых применяемых внутренних штрафов является логарифмический (рис. 4.4):

(4.7)



Рисунок 1.6– Логарифмический штраф

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

Штраф заданный обратной функцией (рис. 4.5):

(4.8)



Рисунок 1.7– Штраф, задаваемый обратной функцией

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

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

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

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

(4.9).

Задача на условный минимум сводится к решению последовательности задач поиска минимума смешанной вспомогательной функции:

(4.10)

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

Блок-схема алгоритма комбинированного метода штрафных функций находится на рис. 4.6.

Следует заметить, что:

а) начальное значение параметра штрафа должно быть больше нуля, а число больше единицы, обычно а ;

б) можно использовать разные параметры штрафа для внешних и внутренних штрафов;

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



Рисунок 1.8– Блок-схема алгоритма комбинированного метода штрафных функций

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

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

е) на практике для получения решения исходной задачи с требуемой точностью достаточно бывает решить конечное (относительно небольшое) число вспомогательных задач. При этом нет необходимости решать их точно, а информацию, полученную в результате решения очередной вспомогательной задачи, обычно удается эффективно использовать для решения следующей. Поэтому точность нахождения оптимума в задачах безусловной оптимизации должна быть на несколько порядков меньше точности КМШФ;

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

4.3 Градиентный метод с дроблением шага

Градиентом дифференцируемой функции в точке называется
n-мерный вектор , компоненты которого являются частными производными функции , вычисленными в точке , то есть:

. (4.11)

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

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

(4.12)

где - параметр, определяющий длину шага.

В данном методе величина шага выбирается так, чтобы было выполнено неравенство:

(4.13)

Это требование на выбор шага - условие убывания, имеет смысл: функция должна убывать от итерации к итерации.

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

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

, (4.14)

где - заданная точность, а норма градиента:

(4.15).

Блок-схема алгоритма ГМДШ для функции нескольких переменных изображена на рис. 4.7.



Рисунок 1.9– Блок-схема алгоритма ГМДШ

Выбор среды и языка программирования

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

В качестве языка программирования был выбран Python (среда программирования Python v2.6.5), это обусловлено следующими факторами:

а) Python – это объектно-ориентированный, интерпретируемый, переносимый язык сверхвысокого уровня. Программирование на Питоне позволяет получать быстро и качественно необходимые программные модули. Интерпретатор Python является быстрый, эффективный и мощный, он может быть перенесён на любую платформу, будь то Unix, Windows, Linux, RiscOS, MAC, Sun. При написании кода на Python не приходится заботиться о конечной платформе, кроме тех случаев, когда используется специфические модули для данной системы. Таким образом, Python обеспечивает лёгкую переносимость, одновременно сочетая в себе средства доступа к ресурсам операционной системы. Python не столь строг к использованию объектов, но реализуются они столь просто, что любой программист легко понимает сущность объектно-ориентированного подхода. Кроме этого, модули Python могут быть с лёгкостью использованы в программах на С++. Python прост, мощен и его очень легко освоить

б) Python – стабильный и распространённый язык. Он используется во многих проектах и в различных качествах: как основной язык программирования или для создания расширений и интеграции приложений. На Python реализовано большое количество проектов, также он активно используется для создания прототипов будущих программ. Python используется во многих крупных компаниях.

в) Python – активно развивающийся язык программирования, новые версии (с добавлением/изменением языковых свойств) выходят примерно раз в два с половиной года.

Разработка программного средства

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

Итак, можно предъявить следующие требования к разрабатываемому ПС:

а) для упрощения использования:

– простой и приветливый графический интерфейс;

– возможность выбора метода оптимизации;

– присутствие полей ввода параметров используемых методов;

– иметь область для вывода входных и выходных данных;

– наличие процедуры очистки поля вывода;

б) для возможности интеграции с другими программными средствами или комплексами:

– входные данные должны считываться с файла, определенной структуры и содержания;

– наличие возможности сохранения результатов работы (выходных данных) в отдельный файл;

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

в) для предотвращения аварийных ситуаций:

– реализовать проверку на корректность введенных параметров.

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


Рисунок 1.10– Экранная форма разработанного ПС

Алгоритмы МШ и КМШФ используемые в программе Optimization подробно описаны в разделе 4. Вся необходимая для работы с программой информация находится в приложении Б, а код программы, написанный на языке Python в приложении В.

ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ

7.1 Задача оптимального проектирования контейнеров

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

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

7.1.1 Постановка задачи

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

а) емкость контейнера – 6 м³;

б) высота может составлять от 1 до 3 м;

в) основа контейнера должна быть квадратной;

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

Стоимость материала дна и стенок контейнера – 6 ден.ед./м², стоимость материала крышки – 4 ден.ед./м².

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

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

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

, (7.1)

, (7.2)

. (7.3)

Ограничение (7.1) устанавливает, что высота контейнера должна составлять от 1 до 3 м; ограничение (7.2) устанавливает, что емкость контейнера равняется 6 м³. Целевая функция (7.3) выражает стоимость контейнера (первое слагаемое – стоимость материала для основы, второе – стоимость материала для стенок, третье – для крышки).

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

7.1.2 Подготовка и ввод исходных данных

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



где, первая строка – целевая функция; вторая – координаты точки с которой будет начинаться итерационный процесс минимизации; с третьей по шестую строки – ограничения. Следует заметить, что для КМШФ стартовая точка должна лежать внутри множества допустимых значений, а для МШ выполнение данного условия не принципиально.

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

Рисунок 1.11–
Экранная форма файла содержащего исходные данные

Адрес файла с входными данными необходимо ввести в соответствующее поле программы и нажать кнопку «Загрузить», после чего выбрать метод с помощью которого будет производиться оптимизация и ввести все необходимые параметры метода, а именно:

E – точность вычислений для метода условной оптимизации (МШ или КМШФ);

E1 – точность вычислений для метода безусловной оптимизации (ГМДШ);

Alfa – начальный шаг для ГМДШ;

r[0] – начальное значение параметра штрафа;

С – положительное число для увеличений (уменьшений) параметра штрафа.

7.1.3 Выполнение расчетов

Для того чтобы выполнить оптимизацию необходимо нажать кнопку «Вычислить». На рис. 7.2 и 7.3 изображены экранные формы программного модуля Optimization и результаты его расчетов.



Рисунок 1.12– Результат оптимизации с помощью МШ



Рисунок 1.13 - Результат оптимизации с помощью КМШФ

Как видно из рис. 7.2 и 7.3 программа Optimization при заданных исходных данных с помощью выбранного метода нашла ближайший минимум функции и его координаты и . Также в окне программы можно увидеть количество шагов (за которые было найдено решение), конечное значение параметра штрафа , функции штрафа и нормы градиента, который служит критерием останова в ГМДШ.

7.1.4 Анализ полученных результатов

Проанализировав выходные данные программы, изображенные на рисунках 7.2 и 7.3, следует заметить, что с поставленной задачей КМШФ при заданной одинаковой точности вычислений, справился лучше чем МШ, так как ему понадобилось меньше шагов для достижения оптимальной точки, а значение целевой функции в ней оказалось меньше, чем аналогичное значение в точке минимума, найденного МШ. Но это не означает, что какой-либо из методов лучше другого, это лишь значит, что КМШФ целесообразнее использовать для решения подобных задач.

Для проверки правильности полученных результатов и наглядности их анализа воспользуемся программой Mathcad 14. На рис. 7.4 изображен трехмерный график целевой функции поставленной задачи оптимизации: .

На рисунке 7.5 изображены:

– линии постоянного уровня функции;

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

– дуга, образованная уравнением баланса;

– стартовые точки ;

– найденный минимум .


Рисунок 1.14– Трехмерный график исследуемой функции



Рисунок 1.15– Линии постоянно уровня функции и ограничения

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

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

Проведя несколько экспериментов с программным средством при различных начальных точках, при этом изменяя точность расчетов и , начальное значение параметра штрафа , начальный шаг для ГМДШ и число можно сделать следующие выводы:

- некорректный подбор параметров методов приводит к расходящемуся процессу;

- только правильное сочетание параметров дает выигрыш в вычислительных операциях и скорости нахождения условного минимума;

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

- точность метода условной оптимизации должна быть в 10-1000 раз больше чем точность метода безусловной оптимизации – это условие имеет большое влияние на скорость сходимости методов;

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

7.2 Задача распределения топлива в силовых установках

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

7.2.1 Постановка задачи

Каждый из двух электрических генераторов может работать на жидком топливе и газе или в любом их сочетании. Суммарная мощность, развиваемая обоими генераторами, должна составлять 50 МВт. Потребление газа ограничено – 10 ед./час. Необходимо выбрать схему работы каждого генератора так, чтобы минимизировать потребление жидкого топлива.

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

(7.4)

(7.5)

где и – затраты жидкого топлива и газа в час соответственно.

Аналогично для генератора 2 затраты топлива на обеспечение выходной мощности МВт составляют:

(7.6)

(7.7)

где и – затраты жидкого топлива и газа в час соответственно.

По эксплуатационным характеристикам генераторов может изменяться в диапазоне:

(7.8)

а – в диапазоне:

(7.9)

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



где также дает мощность, равную . Подобное предположение верно и для генератора 2.

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

(7.10)

при ограничении на использование газа:

(7.11)

ограничении на суммарную мощность:

(7.12)

и ограничениях на переменные (7.8) и (7.9), а также:

(7.13)

Примем что, а , тогда, на основании целевой функции (7.10) и ограничений (7.8), (7.9), (7.11), (7.12) и (7.13) для задачи распределения топлива можно построить следующую математическую модель:

7.2.2 Решение задачи

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

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

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

Для выполнения расчетов с помощью МШ в качестве стартовой точки выбрана лежащая вне области допустимых значений. На рис. 7.7 изображена экранная форма ПС содержащего результат решения задачи. Изменяя точность вычислений (при условии что ) проследили зависимость корректности результата от количества итераций (табл. 7.1).


Рисунок 1.16– Подготовленные входные данные



Рисунок 1.17– Результат решения задачи

Таблица 7.1 – Результаты работы программы при различных

Точность,	1	0.1	0.01	0.001	0.0001
Результаты
	28.885	30.0458	30.0004	30	30
	21.1034	19.9182	19.9988	19.9996	20
	0.760064	-0.0096625	-0.00021271	-1.0388e-05	-1.9104e-06
	0.872572	0.591997	0.583525	0.583643	0.583659
	10.1721	3.07975	3.05092	3.05114	3.05207
	50	630	1676	2566	5570

Как было сказано ранее – главный недостаток МШ это то, что найденное решение может оказаться в недопустимой области; полученные результаты (табл. 7.1) свидетельствуют об этом. Подобные случаи возникают из-за того, что решение задачи находится на границе ограничений-неравенств, а итерационный процесс нахождения минимума начинается из точки, которая находится в недопустимой области. Но это не значит, что найденное решение не верно.

Итак, на основании расчетов представленных в табл. 7.1, следует, что решение задачи будет: , при этом .

Практическая ценность решенной задачи заключается в следующем: если первый электрический генератор на 100% будет работать от газа, при этом его мощность будет составлять 30 МВт, а второй будет на 58% работать от жидкого топлива и на 42% от газа, выдавая при этом мощность равную 20 МВт, тем самым обеспечивая необходимую выходную мощность равную 50 МВт. В данном случае затраты жидкого топлива будут минимальны, и составят 3.052 единицы количества нефти в час, при этом затраты на газ не превысят 10 единиц количества нефти в час, а генераторы будут работать в нормальных режимах (мощности производимые генератором не выходят за пределы эксплуатационных характеристик).

ВЫВОДЫ

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

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

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

ПЕРЕЧЕНЬ ССЫЛОК

1. Сайт, посвященный проблемам автоматизации структурно-параметрического синтеза [электронный ресурс] http://www.structuralist.narod.ru.

2. Андронов С.А. Методы оптимального проектирования: Текст лекций. – СПбГУАП. Спб., 2001. 169 с.: ил.

3. Оптимизация решений на основе методов и моделей мат. программирования: Учебное пособие / С.С. Смородинский, Н.В. Батин. – Мн.: БГУИР, 2003. – 136 с.: ил.

4. Аоки М. Введение в методы оптимизации. – М.: Главная редакция физико-математической литературы издательства «Наука», 1977. – 344 с.

5. Методы оптимизации в примерах и задачах: Учебное пособие / А.В.Пантелеев, Т.А. Летова. – М.:Всш.шк., 2002. – 544 c.

6. Методы оптимизации в теории управления: Учебное пособие / И.Г. Черноруцкий. – Спб.: Питер, 2004. – 256 с.: ил.

7. Мину М. Математическое программирование. Теория и алгоритмы: Пер. с фр. и предисловие А.И. Штерна. – М.: Наука. Гл. ред. физ.-мат. лит., 1990. – 488 с.

8. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике: в 2-х кн. Кн. 1. Пер. с англ. – М.: Мир, 1986. – 349 с.

9. Химмельблау Д. – Прикладное нелинейное программирование. Пер. с англ. – М.: Мир, 1975. – 536.

10. Методичні вказівки з дипломного проектування бакалавра для студентів спеціальності 8.091401 – Системи управління та автоматики / Упоряд.: Е.Г.Петров, М.Ю. Вишняк, В.В. Євсєєв, В.М. Кузьменко, А.О. Овезгельдиєв, Л.М. Ребезюк, В.І. Грицюк. – Харків: ХТУРЕ, 2004. – 56 с.

11. Державний стандарт України. ДСТУ 3008-95: Документація. Звіти у сфері науки і техніки. Структура і правила оформлення. – К.: Держстандарт України, 1995.