Математическая модель оптимизационной задачи

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

целевую функцию;

ограничения;

граничные условия.

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

(1.1)

где х_1; х₂,... х_п - искомые переменные, значения которых вычисляются в процессе решения задачи; общее количество переменных равно п.

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

Если переменная может принимать только значения целых чисел, такая переменная называется целочисленной.

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

Если переменная может принимать только определенные значения, такая переменная называется дискретной. Примером дискретной переменной может служить искомая мощность трансформатора или искомое сечение линии электропередачи. Значения таких величин регламентируются ГОСТами. Например, мощности трансформаторов составляют ряд... 630, 1000, 1600,... кВА, а сечения линии электропередачи - ряд... 50, 70, 95... мм. Распространенной задачей с дискретными переменными является задача выбора варианта из числа заданных.

Зависимость между переменными в целевой функции (1.1) может быть линейной или нелинейной. Напомним, что линейной называется такая зависимость, в которую переменные x_t (7=1, 2, 3,... n) входят только в первой степени и с этими переменными выполняются только действия сложения, вычитания и умножения на постоянный коэффициент. Во всех других случаях зависимость будет нелинейной.

Нелинейная целевая функция в заданном диапазоне изменения переменных может иметь один экстремум или несколько экстремумов. В первом случае функция будет одноэкстремальной, во втором - многоэкстремальной. На рис. 1.1 приведены примеры одноэкстремальной (один минимум) и многоэкстремальной (два минимума и один максимум) функции Z(x) одной переменной в диапазоне изменения этой переменной d <_х <_D.

Рис. 1.1 Одноэкстремальная (а) и многоэкстремальная (б) функции.

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

Ограничения представляют собой различные технические, экономические, экологические условия, учитываемые при решении задачи. Ограничения представляют собой зависимости между переменными х_1г х₂,... х_п, задаваемые в форме неравенств или равенств

(1.2)

Общее количество ограничений равно т. Правые части ограничений, представляющие собой постоянные коэффициенты bj (j=1, 2,... т), называются свободными членами.

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

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

2х₁ + 3х₂ х₃ - х₄ < 4, нет определенности на сколько его левая часть меньше 4.

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

2х₁ + 3х₂ х₃ - х₄ + х₅ = 4.

Совершенно аналогично неполное равенство типа

2х₁ + 3х₂ х₃ - х₄ < 4 обращается в строгое равенство

2х₁ + 3х₂ х₃ - х₄ + х₅ = 4.

Соотношения типа

2х₁ + 3х₂ х₃ - х₄ > 4 и 2х\ + 3х₂ х₃ - х₄ > 4

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

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

Предположим, что все m ограничений являются равенствами. При n = m система (1.2) имеет единственное решение. Например, одно уравнение m=1 с одним неизвестным n=1

2х₁ = 4 имеет единственное решение х₁=2. Поэтому в случае n = m нет места оптимизации.

При n < m система (1.2) не имеет решения и, следовательно, выбирать оптимальное решение не из чего. Например, система из двух уравнений m=2 с одним неизвестным n=1

2х₁ = 4,

3 х 1 = 4

не имеет решения.

При n > m система (1.2) имеет бесконечное множество решений, из которых можно выбрать оптимальное решение. Например, одно уравнение m =1 с двумя неизвестными n =2

х₁ + х₂ = 4

имеет бесконечное множество решений: х₁=0, х₂=4; х₁=1, х₂=3; х₁=5, х₂=-1;... Следовательно, поиск оптимального решения возможен лишь в случае, когда n > m.

Граничные условия устанавливают диапазон изменения искомых переменных

di < х i < Di, i=1, 2,... n, (1.3)

где d_i и D_i - соответственно нижняя и верхняя границы диапазона изменения переменной x_i.

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

При наличии ограничений и граничных условий ищется уже не абсолютный, а относительный экстремум целевой функции. На рис. 1.2 показана некоторая функция одного переменного Z(x). Указан диапазон изменения переменной х (нижняя граница d и верхняя граница D). Видно, что абсолютный минимум функции соответствует точке 1, а относительный минимум - точке 2, принадлежащей заданному диапазону изменения переменной х.

Рис. 1.2 Относительный и абсолютный минимумы функции.

Поиск по сайту: