В этом параграфе приводятся примеры оптимизационных задач. Описываются постановки и классификация таких задач.
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.
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).
3. Задача Штейнера.
Классическая задача Штейнера формулируется так: требуется найти точку x О Rm, сумма расстояний от которой до заданных точек x1, ..., xn О Rm минимальна. Эта задача типично оптимизационная:
f(x) =(def)
n
е
i = 1
||x - xi|| ® min
З а д а ч а 1.1. Найдите решение задачи Штейнера при m = 2, n = 3.
Приведенные выше задачи представляют собой задачи безусловной оптимизации — на искомое решение не налагается никаких дополнительных условий, кроме того, что оно должно доставлять минимум некоторой функции (другими словами, минимум функции ищется на всем пространстве — области определения функции). Чаще встречаются задачи условной оптимизации, примеры которых мы приводим ниже.
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.
По легенде одним из первых приложений задачи о рационе к реальной жизни была попытка рассчитать оптимальный рацион для американской армии во время второй мировой войны. Результат был неожиданным: солдат в день должен выпивать литр уксуса и съежать килограм бобов (цифры и продукты условные).
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. Запишите транспортную задачу в векторном виде.
Это были примеры линейных задач условной оптимизации. Приведем один пример нелинейной задачи.
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.
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), то в задачах выпуклого программирования требуют его выпуклость). Наконец, в общем случае говорят о задачах нелинейного программирования. В таких задачах обычно предполагается гладкость фигурирующих в них функций. Именно этим задачам в данном пособии будет уделено основное внимание.