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

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

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

Всюду ниже R — множество вещественных, N — натуральных, а C — комплексных чисел. С самого начала мы будем использовать векторные обозначения. Всегда через R^m обозначается m-мерное вещественное линейное пространство. При этом мы всегда считаем, что в R^m фиксирован базис и отождествляем R^m с арифметическим m-мерным пространством (пространством упорядоченных наборов m вещественных чисел). Буква Θ будет обозначать нуль пространства 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) ≝  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 ≥ Θ.

В них первое неравенство связывает два вектора Ax и b из R^m, а второе – два вектора x и Θ из 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-ой электростанцией. Техническими условиями определяются возможный минимум μ_j и максимум M_j вырабатываемой j-ой электростанцией мощности. Допустим затраты на генерацию мощности x на j-ой электростанции равны e_j(x). Требуется сгенерировать требуемую мощность p при минимальных затратах. В наших обозначениях

f(x) ≝  m ∑ j = 1 ej(xj) → min,

m ∑ j = 1 xj = p,

μj ≤ xj ≤ Mj,   j = 1, ..., m.

Если обозначить ∑mj=1ej(xj)через f(x), ∑mj=1xj– p через g(x), а {x ∈ Rm: μ ≤ x ≤ M} через Ω, то эта задача переписывается так

f(x) → min, g(x) = 0, x ∈ Ω.

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

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

f(x) → min,   x ∈ Rm.

(2)

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

f(x) → min,   x ∈ Ω.

(3)

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

g0(x) = Θ,

(4)

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

g1(x) ≤ Θ,

(5)

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

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

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

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

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