Как Математик помог Бригадиру

40

В. Левитина

Как Математик помог Бригадиру

Главная цель статья — показать, что самые простые задачи, возникшие в практике, естественно приводят кfundamentalным понятиям математики.

1. Бригадир получает задачу

Наш Бригадир возглавляет бригаду из 10 человек, которая должна погрузить кирпич, находящийся на двух складах. На первом складе — 4 тысячи кирпичей, на втором — 8 тысячи. Склады устройства так, что на первом складе одновременно должны вести погрузку не менее шести рабочих, на втором могут работать от трех до шести рабочих. Бригадиру нужно распределить рабочих так, чтобы вся работа была выполена за минимальное время.

Как может поступить Бригадир? Например, так: отправить сначала всех рабочих на первый склад, а после окончания его погрузки шесть рабочих — максимальное допустимое число — перевести на второй склад. Предположим для простоты, что каждый рабочий за один час порузаем темыку кирпичей. Тогда время, за которое бригада выполнит всю работу по этому расписанию, очень high, равно $\frac{4}{10} + \frac{8}{6} = 1\frac{11}{15}$ (часа).

Будет ли такая организация работы налучшей? Если да, то почему? А если нет, то насколько она далека от оптимальной? Ответить на эти вопросы сам Бригадир не может. А вы? Попытайте — тогда вам будет значительно интереснее прочесть в следующих параграфах о встрече Бригадира с Математиком, к которой Бригадир обратился со своей задачей.

2. Математик создает модель задачи

Прежде чем взяться за решение задачи, Математик должен создать ее математическую модель.

Если обозначить через $u$ и $v$ количество на первом и втором складах, то для каждой момента времени числа $u$ и $v$ удовлетворяют следующим условиям:

1. $u \in \mathbb{Z}$ и $v \in \mathbb{Z}$,
2. $6 \leq u \leq 10$ или $u=0$,
3. $3 \leq v \leq 6$ или $v=0$,
4. $u + v \leq 10$.

Этим условиям удовлетворяют такие тринадцать режимов работы: $\langle 6,4 \rangle$ (на первом складе работает 6 человек, на втором — 4), $\langle 7,3 \rangle$, $\langle 6,3 \rangle$, $\langle 10,0 \rangle$, $\langle 9,0 \rangle$, $\langle 8,0 \rangle$, $\langle 7,0 \rangle$, $\langle 6,0 \rangle$, $\langle 0,0 \rangle$, $\langle 0,3 \rangle$, $\langle 0,4 \rangle$, $\langle 0,5 \rangle$ и $\langle 0,6 \rangle$. Изображим их точками координатной плоскости (рис. 1).

Порядок, в котором применяются различные режимы работы, безразличен. Например, если бы Бригадир послал сначала шесть рабочих разгрузить второй склад, а затем всего бригади направил на первый, работа бы выполнена за те же $1\frac{11}{15}$ часа. Поэтому мы можем считать, что погрузка организована так: сначала $t_1$ часов применяется режим $\alpha_1$, затем $t_2$ часов — режим $\alpha_2$ и т. д. При этом $t_i$ может равнять нулю, т. е. режим $\alpha_i$ может не использоваться. Например, при погрузке, расстояненной в п. 1, нулю не равны только $t_4 = \frac{4}{10}$ и $t_{13} = \frac{8}{6}$.

Пренебрежем временем переходов со склада на склад. Тогда общее время погрузки $t$ будет равно

$$t = t_1 + t_2 + \dots + t_{12} + t_{13}. \tag{1}$$

Поскольку каждый рабочий грузит в часычку кирпичей, количество рабочих, погруженного с первого склада ($x$ тысяч штук) и со второго склада

41

Рис. 1.

(у тысяч штук), выразятся равенствами
$$x = 6t_1 + 7t_2 + \ldots + 0t_{12} + 0t_{13},$$
$$y = 4t_1 + 3t_2 + \ldots + 5t_{12} + 6t_{13}.$$
Фиксируем $t$. Подставляя в (2) и (3) различные неотрицательные числа $t_1, t_2, \ldots, t_{13}$, удовлетворяющие условиями (1), мы будем получить, различные точки плоскости $\langle x, y \rangle$. Множество всех таких точек обозначаим через $A_t$; назовем его множество доступимости за время $t$. Это называние естественно: $A_t$ состоит из точек плоскости с координатами, равными колчеству кирпича (в тысяч штук), который может погрузить бригада — соответственно, с первого и второго складов — за время $t$.

Тепер задача Бригадира может быть сформирована следующим образом: составить такое расписание погрузки, при котором точка с координатами $\langle 4, 8 \rangle$ (эта точка соответствует заданным колчеством кирпича на складах) принадлежит множество $A_t$ и $t$ минимально.

3. Математик решает задачу

Первым делом Математик просит задачу: он ограничится отисканием множества $A_1$, поскольку любое множество $A_t$ готовится множество $A_1$ с коэффициентом готовности $t$ и центром готовности — началом координат.

Покажем, что множество $A_1$ является выпуклой оболочкой коей точек $\alpha_1, \alpha_2, \ldots, \alpha_{13}$.

Вспомним, что множество $M$ точек на плоскости называется выпуклым, если вместе с любой парой своих точек оно содержит весь отрезок с концами в этих точках («Геометрия 6», п. 39). Примеры выпуклых множества приведены на рисунке 2, множества на рисунке 3 не являются выпуклыми.

В выпуклая оболочка множества $M$ — это наименьшее выпуклое множество, содержащое $M$ (рис. 4). Поскольку пересечение произвольного числа выпуклых множества выпукло (доказите!), выпуклая оболочка произвольного множества $M$ совпадает с пересечением всех выпуклых множества, содержащих $M$ (такие множества всегда — каково бы ни было $M$ — существует; почему?). Выпуклую оболочку множества $M$ принято обозначать через сопр $M^*$).

Чтобы доказать, что множество достижимости $A_1$ является выпуклой оболочкой множества $\{\alpha_1, \alpha_2, \ldots, \alpha_{13}\}$, даим понятие выпуклой оболочки другое определение.

Рис. 2.

Рис. 3.

Рис. 4. В обеих парах правое множество есть выпуклая оболочка левого множества.

*) От латинского сопрхius («выпуклый»).

42

Для этого введем две операции с точками координатной плоскости. Суммой точек $\langle x_1, y_1 \rangle$ и $\langle x_2, y_2 \rangle$ мы будем называть точку $\langle x_1 + x_2, y_1 + y_2 \rangle$. Произведением точки $\langle x, y \rangle$ на число $t$ называем точку $\langle tx, ty \rangle$. Если каждой точке $\alpha$ сопоставить вектор, определяемый парой точек $O$, $\alpha$ ($O$ — начало координат), то введенные операции с точками совпадут с обычными операциями над векторами.

Докажите, что если множество $M$ выпукло, то и множество $tM$ (т. е. множество точек $t\beta$, где $\beta \in M$) тоже выпукло.

Определение. Точка $\beta$ называется выпуклой комбинацией точек $\beta_1, \beta_2, \dots, \beta_n$, если существует также неотрицательные числа $t_1, t_2, \dots, t_n$, что $t_1 + t_2 + \dots + t_n = 1$ и $\beta = t_1\beta_1 + t_2\beta_2 + \dots + t_n\beta_n$.

Теорема. Выпуклая оболочка множество $M$ состоит из всевозможных выпуклых комбинаций точек из $M$.

Доказательство. Обозначим множество выпуклых комбинаций точек из $M$ через $Q$. Если $\gamma$ и $\delta$ — произвольные точки, то множество точек вида $t\gamma + (1-t)\delta$, где $0 \leq t \leq 1$, совпадает с отрезком с концами $\gamma$, $\delta$. Отсюда легко вывести, что $Q$ — выпуклое множество (проделяйте это!). Кроме того, очень/no, $M \subset Q$. Следовательно, совп $M \subset Q$. Докажем теперь индукцией по $n$, что любая выпуклая комбинация $t_1\beta_1 + t_2\beta_2 + \dots + t_n\beta_n(t_1 + t_2 + \dots + t_n = 1)$ точек из $M$ принимает совп $M$. Это будет означает, что $Q \subset \text{conv } M$. При $n = 1$ соответствующое утверждение принимает вид: если $\beta \in M$, то $\beta \in \text{conv } M$. Это верно по определению выпуклой оболочки. Пусть теперь все выпуклы комбинации $n$ точек из $M$ принимают совп $M$. Докажем, что тогда и выпуклая комбинация $\delta = t_1\beta_1 + t_2\beta_2 + \dots + t_n\beta_n + t_{n+1}\beta_{n+1}$ (где $\beta_1, \beta_2, \dots, \beta_n, \beta_{n+1}$ — точки из $M$) принимают $M$:

$$\delta = (1 - t_{n+1}) \left[ \frac{t_1}{1 - t_{n+1}}\beta_1 + \frac{t_2}{1 - t_{n+1}}\beta_2 + \dots + \frac{t_n}{1 - t_{n+1}}\beta_n \right] + t_{n+1}\beta_{n+1}.$$

Из $t_1 + t_2 + \dots + t_n + t_{n+1} = 1$ следует, что

$$\frac{t_1}{1 - t_{n+1}} + \frac{t_2}{1 - t_{n+1}} + \dots + \frac{t_n}{1 - t_{n+1}} = 1.$$

По предположению индукции

$$\eta = \frac{t_1}{1 - t_{n+1}}\beta_1 + \frac{t_2}{1 - t_{n+1}}\beta_2 + \dots + \frac{t_n}{1 - t_{n+1}}\beta_n \in \text{conv } M.$$

Из (4) вытекает, что точка $\delta$ лежит на отрезке с концами $\eta$ и $\beta_{n+1}$. Так как $\beta_{n+1} \in M \subset \text{conv } M$, а conv $M$ — выпуклое множество, получаем $\delta \in \text{conv } M$. Теорема доказана.

Таким образом, каждая точка из conv $M$ является выпуклой комбинацией неокоторого конечного точек из $M$. Если множество $M$ конечно, то можно считать, что каждая точка из conv $M$ есть выпуклая комбинация в всех точек из $M$.

Оказывается, для произвольного множество $M$ на плоскости каждой точки $\beta$ множество совп $M$ может быть получена как выпуклая комбинация трех точек $\beta_1, \beta_2, \beta_3$ из $M$ (разумеется, для разных $\beta$ точки $\beta_1, \beta_2, \beta_3$, вообще говоря, разные). Эта теорема, вернее — ее $n$-мерный аналог, называется meoremой Кармедори. Попробуйте доказать ее!

По определению множество достижимости $A_1$ состоит из всевозможных точек $t_1\alpha_1 + t_2\alpha_2 + \dots + t_{13}\alpha_{13}$, для которых $t_1 + t_2 + \dots + t_{13} = 1$ (п. 2). Другими словами, $A_1$ состоит из всевозможных выпуклых комбинаций точек $\alpha_1, \alpha_2, \dots, \alpha_{13}$. По доказанному теореме

$$A_1 = \text{conv} \{ \alpha_1, \alpha_2, \dots, \alpha_{13} \}.$$

Из рисунка 1 ясно, что $A_1$ — множество точек четырехугольника $\alpha_1\alpha_2\alpha_3\alpha_{13}$ (точка $\alpha_2$ лежит на прямой $\alpha_1\alpha_4$).

Чтобы найти минимальное $t$, при котором множество $A_t = t \cdot A_1$ содержит точку $\beta$ ($\langle 4, 8 \rangle$ (рис. 5), вычислим координаты точки $\gamma$ пересечения прямых $\alpha_9$ $\beta$ и $\alpha_1\alpha_{13}$. Уравнение прямой, проходящей через

43

Жима работы $\alpha_1$ в течение $t \cdot t_1 = \frac{8}{9}$ (часа) и режима работы $\alpha_{13}$ в течение $t \cdot t_{13} = \frac{2}{3}$ (часа). Время, которое заняла бы вся работа по расписанию, составленному Бригадиром в п. 1, было равно $1 \frac{11}{15}$ часа, что больше найдеенного минимального времени в $1 \frac{4}{35}$ раза.

Подведем итоги. Мы видим, что совсем не геометрическая задача Бригадира естественно привела нас к выпуклым фигурам на плоскости. Оказывается, понятие выпуклости может быть определено не только для геометрических — плоских или пространственных — объектов, но и в значительной более общей ситуации (например, в так называемых векторных пространствах — см. «Квант», 1976, № 4, с. 2). В таком обобщенном виде оно «работает» во многих областях математики (функциональный анализ, математическое программирование, теория игры).

С интересными задачими, решаемыми с помощью понятия выпуклости, вы можете познакомиться в книге И. М. Яглома и В. Г. Болтянского «Выпуклые фигуры» (М. — Л., Гостехидат, 1951).

Задачу Бригадира можно решать и чисто алгебраически — методами линейного программирования. О том, как это делается, расскажалось в «Кванте», 1976, № 7, с. 2. При таком подходе полезно заметить, что можно (см. рис. 1) рассматривать только те расписания, при которых

$$t_3 = t_5 = t_6 = t_7 = t_8 = t_9 = t_{10} = t_{11} = t_{12} = 0.$$

Упражнения

1. Составить для Бригадира расписание, если
   a) на первом складе — 16 тысяч кирпичей, на втором — 4 тысяч;
   b) на первом складе одновременного должны работы не менее 7 человек.
2. Есть сковорода, на которой можно одновременно поджаривать две котлеты. Каждая котлета поджаривается с одной стороны одну минуту. За сколько времени удается поджарить три котлеты?