Пример 1. Сумма n чисел равна единице. Каковы должны быть эти числа, чтобы сумма их квадратов была наименьшей?
Решение. Получим ответ на поставленный вопрос геометрическим путем, рассматривая сначала случай n = 2, затем n = 3, а потом обсудим ситуацию при n > 3.
Итак, пусть сначала n = 2. Иначе говоря, рассматриваются числа x,y, удовлетворяющие условию x + y = 1, и требуется найти, в каком случае сумма квадратов x2 + y2 будет наименьшей.
Уравнение x + y = 1 определяет на координатной плоскости прямую l (рис. 4). Рассмотрим окружность S с центром в начале координат, которая касается этой прямой (точка A). Если точка M(x;y) прямой l отлична от A, то она лежит вне окружности S и потому |OM| больше радиуса r этой окружности, т. е. x2 + y2> r2. Если же M = A, то сумма x2 + y2 равна r2, т.е. именно для точки A эта сумма принимает наименьшее значение. Точка A имеет координаты x = y = 1/2; это и есть решение поставленной алгебраической задачи (при n = 2).
Рис. 4
Пусть теперь n = 3. Уравнение x + y + z = 1 определяет в пространстве плоскость α. Рассмотрим сферу S с центром в начале O, касающуюся этой плоскости в некоторой точке A (рис. 5). Для любой точки M ∈α, отличной от A, ее расстояние от точки O больше радиуса r сферы S, |OM|2> r2, и потому x2 + y2 + z2> r2, а при M = A имеем x2 + y2 + z2 = r2. Таким образом, именно для точки A сумма x2 + y2 + z2 принимает наименьшее значение. Точка A имеет равные координаты: x = y = z (поскольку при повороте пространства, переставляющем оси координат: x → y; y → z, z → x, и плоскость α, и сфера S переходят в себя, а потому их общая точка остается неподвижной). А так как x + y + z = 1, то точка A имеет координаты x = y = z = 1/3; это и есть решение поставленной задачи (для n = 3).
Рис. 5
Рассмотрим, наконец, произвольное n; рассуждения будем вести в n-мерном пространстве, точками которого являются последовательности (x1,x2,...,xn), состоящие из n действительных чисел. Уравнение x1 + x2 + ... + xn = 1 определяет в этом пространстве «плоскость» α, имеющую размерность n-1 (например, при n = 3, т.е. в трехмерном пространстве, такое уравнение определяет плоскость размерности 2, т.е. на единицу меньшей размерности, чем все пространство). Математики называют плоскости, имеющие размерность n-1, гиперплоскостями в n-мерном пространстве. Рассмотрим сферу S с центром в начале координат O, касающуюся гиперплоскости α в некоторой точке A. Все точки гиперплоскости α, кроме A, лежат вне сферы S, т.е. находятся от начала координат O на расстоянии, большем, чем радиус r сферы S, а точка A находится от O на расстоянии, равном r. Следовательно, сумма x12 + x22 + ... + xn2 принимает в точке A наименьшее значение по сравнению со всеми другими точками гиперплоскости α. Заметим теперь, что все координаты точки A равны между собой: x1 = x2 = ... = xn (поскольку поворот пространства, переставляющий оси x1→ x2, ..., xn-1→ xn, xn→ x1, переводит гиперплоскость α в себя и сферу S тоже в себя, а потому оставляет точку A неподвижной), откуда x1 = x2 = ... = xn = 1/n. Итак, при x1 + x2 + ... + xn = 1 сумма квадратов x12 + x22 + ... + xn2 принимает наименьшее значение для x1 = x2 = ... = xn = 1/n.
Разумеется, это геометрическое решение читатель может признать корректным лишь в случае, если он уже владеет понятиями n-мерной геометрии, но характер этого решения и польза n-мерной геометрической интерпретации для рассмотренной алгебраической задачи очевидны.
Пример 2. На три завода З1,З2,З3 (рис. 6) нужно завезти сырье одинакового вида, которое хранится на двух складах C1,C2 в соответствии с данными, указанными в таблице. Наличие сырья | Потребность в сырье | |||
C1 | C2 | З1 | З2 | З3 |
20т | 25т | 10т | 15т | 20т |
Требуется найти наиболее выгодный вариант перевозок, т.е. вариант, для которого общее количество тонно-километров будет наименьшим.
Рис. 6
Решение. Обозначим через x и y количество сырья, которое нужно вывезти со склада C1 соответственно на заводы З1, З2. Тогда со второго склада нужно довезти на эти заводы 10 - x и 15 - y тонн сырья. Так как общее количество имеющегося на складах сырья совпадает с потребностью заводов, т.е. все сырье должно быть вывезено со складов на заводы, то после обеспечения заводов З1 и З2 оставшееся на складах сырье полностью вывозится на завод З3, т.е. со склада C1 на завод З3 вывозится 20 - x - y, а со склада C225 - (10-x) - (15-y) = x + y тонн. Учитывая расстояния (рис. 6), находим общее число тонно-километров:
5x + 7y + 10(20 - x - y) + 3(10 - x) + 4(15 - y) + 6(x + y) = 290 - 2x - y.
Заметим теперь, что все величины, выражающие количество перевозимого по разным дорогам сырья, неотрицательны: x ≥ 0, y ≥ 0, 20 - x - y ≥ 0, 10 - x ≥ 0, 15 - y ≥ 0, x + y ≥ 0. Каждое из этих неравенств определяет в системе координат x,y полуплоскость, а система всех неравенств определяет пересечение этих полуплоскостей, т. е. выпуклый многоугольник Q (рис. 7). Заметим, что последнее неравенство можно отбросить: оно является следствием первых двух.
Рис. 7
Таким образом, задача о нахождении наиболее выгодного варианта перевозок сводится математически к нахождению точки M(x,y) многоугольника Q, в которой функция 290 - 2x - y достигает наименьшего значения. Вместо этой функции можно рассматривать функцию -2x - y. Действительно, если будет найдено наименьшее значение функции -2x - y на многоугольнике Q, то, прибавив к этому значению 290, получим наименьшее значение функции 290 - 2x - y.
На рис. 8 показано, что наименьшее значение линейной функции -2x - y, рассматриваемой на многоугольнике Q, достигается в вершине C. Иначе говоря, наиболее выгодный вариант перевозок соответствует точке C(10;10), т.е. x = 10, y = 10. Общее количество тонно-километров для этих значений x,y равно 290 - 2·10 - 10 = 260. Как видим, геометрическая модель позволила полностью решить поставленную задачу
Рис. 8
В рассмотренной задаче все объемы перевозок со складов на заводы удалось выразить через две переменные x,y. Это позволило дать геометрическую интерпретацию получившейся системы неравенств на координатной плоскости. Допустим, однако, что при тех же двух складах число заводов равно четырем с потребностью в сырье соответственно 8, 10, 12 и 15 т. Тогда нужно будет ввести три переменные x,y,z, обозначающие количество сырья, вывозимого со склада C1 на первые три завода. Если задать расстояния от складов до заводов, то можно будет составить выражение для общего числа тонно-километров. Можно написать и неравенства, выражающие неотрицательность количества сырья, вывозимого со складов на заводы. Теперь эти неравенства будут зависеть от трех переменных x,y,z. Каждое из этих неравенств задает полупространство, а система всех неравенств определяет пересечение полупространств, т.е. выпуклый многогранник в трехмерном пространстве. Таким образом, для четырех заводов задача о перевозке сырья будет математически формулироваться как задача о наименьшем значении линейной функции на трехмерном выпуклом многограннике.
Для двух складов и пяти заводов (при сохранении того условия, что все сырье должно быть вывезено полностью) потребуются уже четыре переменные, обозначающие количество сырья, вывозимого со склада C1, на первые четыре завода. Теперь мы будем иметь неравенства с четырьмя переменными, и для получения геометрической интерпретации потребуется четырехмерное пространство, а при большем числе складов и заводов – пространства еще большей размерности.
К нахождению наибольших значений линейных функций на выпуклых многогранниках приводят и другие практические задачи, на первый взгляд никакого отношения к многогранникам не имеющие. Сюда относятся не только задачи о нахождении наиболее выгодных вариантов перевозок, но также задачи о наиболее выгодных способах раскроя материала, наиболее эффективных режимах работы предприятий, задачи о составлении производственных планов и т.п. Такие задачи объединяются новым научным направлением, получившим название линейное программирование. Тот факт, что эти задачи решаются геометрически с помощью нахождения наименьших или наибольших значений линейных функций на многогранниках (причем, как правило, в пространствах, имеющих размерность, большую трех), был впервые подмечен академиком Л. В. Канторовичем. Необходимость рассмотрения n-мерных пространств при