20т
25т
10т
15т
20т
Требуется найти наиболее выгодный вариант перевозок, т.е. вариант, для которого общее количество тонно-километров будет наименьшим.
Рис. 6
Решение. Обозначим через x и y количество сырья, которое нужно вывезти со склада C1 соответственно на заводы З1, З2. Тогда со второго склада нужно довезти на эти заводы 10 - x и 15 - y тонн сырья. Так как общее количество имеющегося на складах сырья совпадает с потребностью заводов, т.е. все сырье должно быть вывезено со складов на заводы, то после обеспечения заводов З1 и З2 оставшееся на складах сырье полностью вывозится на завод З3, т.е. со склада C1 на завод З3 вывозится 20 - x - y, а со склада C2 25 - (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-мерных пространств при n > 3 диктуется также математическими задачами физики, химии, биологии и других областей знания. Таким образом, хотя пространственные свойства окружающего мира хорошо описываются геометрическим трехмерным пространством, потребности практической деятельности человека приводят к необходимости рассмотрения пространств любой размерности n.