Указанные выше три формы ЗЛП можно привести друг к другу с помощью эквивалентных преобразований.

КУРС ЛЕКЦИЙ

по дисциплине «Методы решения задач оптимизации»

для студентов заочной формы обучения

по направлению 230201

«Информационные системы и технологии»

Воронеж 2016

Формализация задач определения оптимальных вариантов.

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

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

Будем в дальнейшем называть их просто объектами, оптимальный вариант которых необходимо определить.

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

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

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

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

Совокупность внутренних и внешних параметров называется входными параметрами объекта.

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

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

Т.е., X – это вектор варьируемых параметров. Они могут иметь различную физическую интерпретацию.

Различают задачи структурной и параметрической оптимизации.

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

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

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

(1)

Здесь X = (x₁, …x_n) – вектор варьируемых параметров объекта; F(x) – целевая функция – функция, характеризующая важные и существенные свойства объекта и являющаяся критерием оценки качества каждого из вариантов. Ее еще называют критерием оптимальности, критерием эффективности, показателем качества объекта и т. д. На основании вычисления F(x) анализируются и сравниваются между собой различные варианты объектов.

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

Ограничения на варьируемые параметры вида x_imin £ x_i £ x_imax называют прямыми ограничениями. Здесь x_imin и x_imax верхние и нижние допустимые значения для i-го управляемого параметра.(так, например, если x_i – количество товара, то x_i ³ 0 и т. д.)

Ограничения вида g_i (x) ³ 0, h_l (x) = 0 – называют функциональными ограничениями и являются какими-либо функциями от входных параметров.

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

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

В противном случае - область невыпуклая.

Таким образом, решение задачи оптимизации сводится к определению значений управляемых параметров x₁ … x_n,обеспечивающих экстремум (max или min) целевой функции F(x) и удовлетворяющих системе ограничений. Такой вектор X называется оптимальным решением. Задачи определения экстремальных значений параметров на допустимом множестве параметров носят еще название задач математического программирования.

Пример.

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

где F(x) – производительность системы

x_i – интенсивность поступления i-го типа задач

j(x) – средняя длина очереди

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

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

При этом математическая модель объекта проектирования может быть:

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

2) аналитической, представляет собой совокупность аналитических зависимостей между входными и выходными параметрами;

3) алгоритмической, представляет собой алгоритм вычисления выходных параметров по значениям входных параметров (“черный ящик”);

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

Обобщенная схема принятия оптимальных решений.

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

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

, где x_i – константа, равная единице измерения параметра x_i и логарифмическую нормализацию

.

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

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

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

Далее устанавливаются параметры (постоянные величины) в зависимости от выбранного метода.

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

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

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

1) скорректировать начальное приближение;

2) изменить параметры метода;

3) изменить метод;

4) скорректировать оптимизационную модель.

Классификация задач оптимизации.

1. В зависимости от числа управляемых параметров различают задачи одномерной и многомерной оптимизации (и соответственно методы одномерной и многомерной оптимизации).

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

3. В зависимости от числа критериев оптимальности различают задачи однокритериальной и многокритериальной (векторной) оптимизации.

4. В зависимости от наличия ограничения различают задачи безусловной и условной оптимизации.

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

6. Если критерии оптимизации и допустимая область является выпуклыми, то мы имеем задачу выпуклого программирования.

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

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

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

($ методы непрерывной, дискретной оптимизации, линейного, нелинейного программирования и т.д.)

Эти методы инвариантны к предметной области их применения.

Линейная оптимизация

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

Формы записи задачи ЛП и их эквивалентность

В общем виде ЗЛП может быть записана следующим образом:

Стандартной (или симметричной) ЗЛП называется cледующая задача:

Для разработки вычислительных методов в качестве стандарта принята каноническая форма записи ЗЛП:

Каноническая форма ЗЛП характеризуется следующими условиями:

1. Целевая функция подлежит минимизации.

2. Все переменные должны быть неотрицательны.

3. Правые части ограничений должны быть неотрицательны.

4. Все ограничения записываются в виде равенств.

Указанные выше три формы ЗЛП можно привести друг к другу с помощью эквивалентных преобразований.

Не нашли, что искали? Воспользуйтесь поиском: