Элементы решения задачи оптимизации.

 

Решение задачи оптимизации с помощью ЭВМ включает следующие обязательные элементы: постановку задачи; математическую модель; алгоритм решения задачи; программную реализацию алгоритма; исходные данные; анализ технических средств; готовность персонала к решению задачи.

Постановка задачи. Она определяет успех всей работы. При выборе задачи необходимо учитывать следующие факторы: важность решения задачи; принципиальная возможность решения задачи на ЭВМ; существование различных вариантов решения задачи. Важность решения задачи обуславливается уровнем пользователя, т.е. лицом, которому нужны результаты. Очевидно, что при оптимизации работы участка результаты решения задачи не будут представлять интереса для руководства предприятия. Чем выше уровень, для которого решается задача, тем более эффективным будет её результат. При этом наибольшую эффективность дают многоуровневые задачи оптимизации как системы в целом, так и входящих в нее элементов. Принципиальная возможность решения задачи на ЭВМ не должна вызывать сомнений. Так, применение ЭВМ может обеспечить оптимальное распределение имеющихся ресурсов, но не может заменить ресурсы, если их недостаточно. Существование различных вариантов решения задачи определяется её постановкой. Например, если план предприятию задан, то нет задачи его определения. Следует очень четко видеть принципиальную возможность наличия различных вариантов. Если такой возможности в принципе не существует, то постановка задачи оптимизации невозможна.

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

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

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

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

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

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

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

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

Потребителями результатов являются специалисты по содержательной части задач оптимизации, разработчиками задачи – специалисты по моделированию и решению задачи на ЭВМ. Контакт и взаимопонимание между двумя группами обеспечивает успех в решении задачи. Чем активнее пользователь участвует в разработке модели, тем лучше он её знает, и, следовательно, тем больше он будет верить результатам, полученным на ЭВМ. Чем выше при этом служебный уровень пользователя, тем большую эффективность принесет решение задачи. Если специалисты понимают модель, а разработчики знают содержательную постановку задачи – это залог того, что модель будет соответствовать решаемой задаче. Эксплуатационники нужны тогда, когда задача решается систематически. Такими специалистами, как правило, являются сотрудники ВЦ. Для них знание всех нюансов задачи и модели необязательно. Но для успешной эксплуатации задачи эксплуатационники должны принимать участие в разработке задачи.

 

Виды задач оптимизации.

 

    В общем случае задача оптимизации может быть записана следующим образом:

    Система (1) представляет собой общий случай математической постановки задачи оптимизации. Она включает целевую функцию Е = f (x_j); ограничения g_i (x_j) <= b_i; граничные условия d_i <= x_j <= D_{j .} Суть такой постановки задачи заключается в следующем: необходимо определить такие значения x_{j ,} которые, находясь в граничных условиях d_j <= x_j <= D_j, удовлетворяли бы ограничениям g_i (x_j) <= b_i и при этом придавали бы целевой функции Е = f (x_j) искомое оптимальное значение.

   Функция f (x) имеет максимум в точке x = a, если, в достаточной близости от этой точки всем значениям x (как большим, так и меньшим a) соответствуют значения f (x) меньшие, чем f (a). Функция f (x) имеет минимум в точке x = a, если в достаточной близости от этой точки всем значениям x соответствуют значения f (x) большие, чем f (a).

Максимум и минимум объединяются понятием “экстремум”. (Латинское слово “экстремум” означает “крайнее”). Экстремум не может быть на границе рассматриваемого интервала. В задачах оптимизации нас интересует наибольшее (наименьшее) значение целевой функции, включая значения целевой функции на границах d_j <= x_j <= D_j. Наибольшее (наименьшее) значение целевой функции, включая ее значения на границах интервала [ d_jD_j ], называют оптимальным значением или оптимумом.

Если при нахождении экстремума накладываются дополнительные условия – ограничения на зависимости между переменными – то экстремум называется условным. Поскольку оптимум, как правило, определяется при наложении ряда дополнительных условий – ограничений, термин “условный оптимум” обычно не применяется. Задача (1) представляет собой задачу нахождения оптимума.

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

1. Зависимости между переменными в (1) входят в

 

 

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

    Линейными называются такие зависимости, в которых переменные или производные находятся в первой степени. Если в зависимостях имеются переменные в степени, отличной от первой, или произведения двух и более переменных, то такие зависимости называются нелинейными.

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

 

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

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

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

Дискретные переменные, в свою очередь могут быть целочисленными, заданными и булевыми. Целочисленными переменными называются также переменные, которые могут принимать только целые значения. В ряде случаев переменные могут принимать лишь определенные заданные значения. Например, диаметр трубы не может быть произвольным, он должен соответствовать ГОСТу и быть равным одному из заданных размеров: 100, 150, 200, 250 мм и т.д.

Важным видом дискретных переменных являются булевые переменные. Булевые переменные могут принимать только два значения: 0 или 1. Если принимать, что 1 соответствует «да», а 0 – «нет», то с помощью булевых переменных можно решать логические, комбинационные и ряд других специфических задач.

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

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

Результат решения задачи оптимизации, т.е. значения величин в оптимальном решении, является функцией заданных величин, входящих в модель, например, для задач ЛП функцией c_j, a_ij, b_i. Если эти величины являются детерминированными, то и величины x_j, как функции детерминированных величин, будут также детерминированными. Если же хотя бы одна из заданных величин будет случайной, то величины x_j, как функции случайных величин, будут также случайными величинами.

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

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