§ 1. Задачи оптимизации

В этом параграфе приводятся примеры оптимизационных задач. Описываются постановки и классификация таких задач.

1.1. Обозначения.

Всюду ниже R — множество вещественных, N — натуральных, а C — комплексных чисел. С самого начала мы будем использовать векторные обозначения. Всегда через R^m обозначается m-мерное вещественное линейное пространство. При этом мы всегда считаем, что в R^m фиксирован базис и отождествляем R^m с арифметическим m-мерным пространством (пространством упорядоченных наборов m вещественных чисел). Буква Q будет обозначать нуль пространства R^m. Индекс внизу всегда обозначает координату вектора, например, x_i — это i-ая координата вектора x. Последовательности мы обычно будем обозначать индексом вверху: {xⁿ}.

Через (· ,·) обозначается каноническое скалярное произведение в Rm: (x, y) = еmi=1xiyi. Если не оговорено противное,, порожденную скалярным произведением: || · || = (еmi=1xi2)1/2.

Обозначение B(x₀, r) закреплено для шара в пространстве R^m с центром в x₀ радиуса r: B(x₀, r) = {x О R^m: ||x - x₀|| Ј r}.

Если A = {a_ij}^{n, m}_{i=1, j=1}  —n×m-матрица, то через A также обозначается и линейный оператор из Rⁿ в R^m, задаваемый этой матрицей.

Для двух векторов x, y О R^m мы будем писать x Ј y, если x_i Ј y_i при всех i = 1, ..., m; здесь x_i и y_i — i-е координаты векторов x и y, соответственно.

Мы будем различать обозначение f: X ® Y отображения, действующего из множества X во множество Y, и обозначение f: x ® y (или x ® f(x)) отображения, переводящего точку x в точку f(x), а также обозначение f отображения и обозначение f(x) значения отображения f в точке x.

1.2. Задача наилучшего приближения.

Если рассматривать систему n линейных уравнений с m неизвестными

Ax = b

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

f(x) = ||Ax - b||.

(1)

Эту задачу символически записывают в виде

f(x) ® min

Норму в (1) можно брать разную. Например, если взята евклидова норма, то получается задача о наилучшем квадратичном приближении

ж и n е i = 1 к к m е j = 1 aijxj - bi к к 2 ц ш 1/2  ® min,

или, что эквивалентно,

n е i = 1 кк кк m е j = 1 aijxj - bi кк кк 2  ® min,

Геометрически эта задача интерпретируется как задача о нахождении на гиперплоскости A(R^m) в пространстве Rⁿ точки, ближайшей к точке b = (b₁, ..., b_n).

1.3. Задача Штейнера.

Классическая задача Штейнера формулируется так: требуется найти точку x О R^m, сумма расстояний от которой до заданных точек x¹, ..., xⁿ О R^m минимальна. Эта задача типично оптимизационная:

f(x) =def  n е i = 1 ||x - xi|| ® min

З а д а ч а  1.1. Найдите решение задачи Штейнера при m = 2, n = 3.

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

1.4. Задача о рационе.

Пусть имеется n различных пищевых продуктов, содержащих m различных питательных веществ. Обозначим через a_ij содержание (долю) j-го питательного вещества в i-ом продукте, через b_j — суточную потребность организма в j-ом питательном веществе, через c_i — стоимость единицы i-го продукта. Требуется составить суточный рацион питания минимальной стоимости, удовлетворяющий потребность во всех питательных веществах. Если обозначить через x_i суточное потребление i-го продукта, то эта задача может быть формализована следующим образом. Нужно минимизировать функцию

f(x1, ..., xn) =  n е i = 1 cixi   (стоимость рациона)

при условиях

n е i = 1 aijxi і bj,   j = 1, ..., m

Очевидно, также следует требовать, чтобы

xi і 0,   i = 1, ..., n.

В векторных обозначениях задача о рационе может быть записана так: минимизировать функцию

f(x) = (c, x),

где c = (c₁, ..., c_n) О Rⁿ; эту задачу, как обычно, мы записываем в виде

(c, x) ® min,

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

Ax і b,

x і Q.

В них первое неравенство связывает два вектора Ax и b из R^m, а второе – два вектора x и Q из Rⁿ.

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

1.5. Транспортная задача.

Эта задача — классическая задача линейного программирования. К ней сводятся многие оптимизационные задачи. Формулируется она так. На m складах находится груз, который нужно развезти n потребителям. Пусть a_i (i = 1, ..., n) — количество груза на i-ом складе, а b_j (j = 1, ..., m) — потребность в грузе j-го потребителя, c_ij — стоимость перевозки единицы груза с i-го склада j-му потребителю. Требуется минимизировать стоимость перевозок. Если обозначить через x_ij объем перевозок с i-го склада j-му потребителю, то транспортная задача формализуется так:

n е i = 1 m е j = 1 cijxij ® min,

n е i = 1 xij = bj,   j = 1, ..., m

m е j = 1 xij = ai,   i = 1, ..., n

xij і 0

З а д а ч а  1.2. Запишите транспортную задачу в векторном виде.

Это были примеры линейных задач условной оптимизации. Приведем один пример нелинейной задачи.

1.6. Задачи о распределении ресурсов.

Общий смысл таких задач — распределить ограниченный ресурс между потребителями оптимальным образом. Рассмотрим простейший пример — задачу о режиме работы энергосистемы. Пусть m электростанций питают одну нагрузку мощности p. Обозначим через x_j активную мощность, генерируемую j-ой электростанцией. Техническими условиями определяются возможный минимум m_j и максимум M_j вырабатываемой j-ой электростанцией мощности. Допустим затраты на генерацию мощности x на j-ой электростанции равны e_j(x). Требуется сгенерировать требуемую мощность p при минимальных затратах. В наших обозначениях

f(x) =def  m е j = 1 ej(xj) ® min,

m е j = 1 xj = p,

mj Ј xj Ј Mj,   j = 1, ..., m.

Если обозначить еmj=1ej(xj)через f(x), еmj=1xj- p через g(x), а {x О Rm: m Ј x Ј M} через W, то эта задача переписывается так

f(x) ® min, g(x) = 0, x О W.

1.7. О классификации задач оптимизации.

Один из классификационных признаков делит оптимизационные задачи на два класса: задачи безусловной оптимизации и задачи условной оптимизации. Первые из них характеризуются тем, что минимум функции f: R^m ® R ищется на всем пространстве:

f(x) ® min,   x О Rm.

(2)

В задачах же второго класса поиск минимума идет на некотором собственном подмножестве W пространства R^m:

f(x) ® min,   x О W.

(3)

Множество W часто выделяется ограничениями типа равенств

g0(x) = Q,

(4)

где g₀: R^m ® R^k, и/или ограничениями типа неравенств

g1(x) Ј Q,

(5)

где g₁: R^m ® R^l.

Другой классификационный признак задач оптимизации — свойства функций f и множеств W. Например задачи (2) и (3) называются линейными (часто говорят о задачах линейного программирования), если функция f — аффинная, а множество W — многогранное (множество W называется многогранным, если оно выделяется ограничениями вида (4) и (5) с аффинными функциями g₀ и g₁).

З а д а ч а  1.3*. Докажите, что линейная задача безусловной оптимизации (1) имеет решение (причем обязательно неединственное) в том и только том случае, если f(x) є const.

Если функции f, g₀ и g₁ квадратичные, то говорят о задачах квадратичного программирования или о квадратичных задачах оптимизации (условных или безусловных). Если эти функции выпуклые, то говорят о задачах выпуклого программирования (если множество W задается каким-либо другим образом, а не только ограничениями типа (4) и (5), то в задачах выпуклого программирования требуют его выпуклость). Наконец, в общем случае говорят о задачах нелинейного программирования. В таких задачах обычно предполагается гладкость фигурирующих в них функций. Именно этим задачам в данном пособии будет уделено основное внимание.

File based on translation from T_EX by T_TH, version 3.05.
Created 4 Jun 2002, 19: 17.