Методы оптимизации

Назад § 1. Задачи оптимизации Вперед

... Скажи-ка мне лучше, как тебя зовут и зачем ты сюда явилась.

Меня зовут Алиса, а...

— Какое глупое имя, — нетерпеливо прервал ее Шалтай. — Что оно значит?

— Разве имя должно что-то значить? — проговорила Алиса с сомнением.

— Конечно, должно, — ответил Шалтай-Болтай и фыркнул. — Возьмем, к примеру, мое имя — оно выражает мою суть! Замечательную и чудесную суть!...

Льюис Кэрролл. Сквозь зеркало и что там увидела Алиса, или Алиса в Зазеркалье

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

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

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

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

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

Если A = {aij}n, mi=1, j=1  —n×m-матрица, то через A также обозначается и линейный оператор из Rn в Rm, задаваемый этой матрицей.

Для двух векторов x, y О Rm мы будем писать x Ј y, если xi Ј yi при всех i = 1, ..., m; здесь xi и yi 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(Rm) в пространстве Rn точки, ближайшей к точке b = (b1, ..., bn).

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

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

f(x) =def 

n
е
i = 1

||x - xi|| ® min

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

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

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

Пусть имеется n различных пищевых продуктов, содержащих m различных питательных веществ. Обозначим через aij содержание (долю) j-го питательного вещества в i-ом продукте, через bj суточную потребность организма в j-ом питательном веществе, через ci стоимость единицы i-го продукта. Требуется составить суточный рацион питания минимальной стоимости, удовлетворяющий потребность во всех питательных веществах. Если обозначить через xi суточное потребление 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 = (c1, ..., cn) О Rn; эту задачу, как обычно, мы записываем в виде

(c, x) ® min,

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

Ax і b,

x і Q.

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

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

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

Эта задача — классическая задача линейного программирования. К ней сводятся многие оптимизационные задачи. Формулируется она так. На m складах находится груз, который нужно развезти n потребителям. Пусть ai (i = 1, ..., n) — количество груза на i-ом складе, а bj (j = 1, ..., m) — потребность в грузе j-го потребителя, cij стоимость перевозки единицы груза с i-го склада j-му потребителю. Требуется минимизировать стоимость перевозок. Если обозначить через xij объем перевозок с 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. Обозначим через xj активную мощность, генерируемую j-ой электростанцией. Техническими условиями определяются возможный минимум mj и максимум Mj вырабатываемой j-ой электростанцией мощности. Допустим затраты на генерацию мощности x на j-ой электростанции равны ej(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: Rm ® R ищется на всем пространстве:

f(x) ® min,   x О Rm.(2)

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

f(x) ® min,   x О W.(3)

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

g0(x) = Q,(4)

где g0: Rm ® Rk, и/или ограничениями типа неравенств

g1(x) Ј Q,(5)

где g1: Rm ® Rl.

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

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

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


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