В поисках оптимального раскроя

44

В понсках оптимального раскрой

Кандидат физико-математических наук
М. В. ВАЛК,
Г. М. ЛАНДМАН

Завод детских игрушек присутствил к массовому выпуску нового изделия, одна из деталей которого — небольшой многоугольник определяющий формы и размеров (рис. 1) из тонкойжести. На заводе имелся станок, на котором легко и быстро можно было нарезать из листа жести прямогольники любых заданных размеров. Поэтому технически было принято решение: нарезать сначала одинаковые прямогольные заготовки надлежащих размеров, а затем уже обрезать каждый такой прямогольник так, чтобы из него получить требуемую многоугольную деталь. А размеры прямогольников следует, естественно, выбрать так, чтобы отходы на обрезки были минимальными. Так возникла математическая задача, о решении которого мы расс克拉ем в данной заметке.

Основная задача. Указать алгоритм, который позволяет среди всех прямугольников П, вместе соихих в себе данные многоугольник М, выбрать тот, который имеет наименьшую площадь.

Примугольник, удовлетворяющий условияю этой задачи, мы будем называвать оптимальным. Если какой-либо прямогольник вместе в себе многоугольник M, а на контур прямогольника нет ни одной вершины многоугольника, то можно прямогольник улущить, т. е. заменить его другим прямогольником меньшей площади, также содержащим в себе многоугольник M. Для этого достаточно перевести параллельно самой себе каждую из четырех прямых, содержащих стороны прямогольника M так, чтобы они (после перемена) уже проходили через какие-то вершины многоугольника M. На рисунке 1 таким «улущенный» прямогольником (по сравнению с П) является П′.

Принято называть опорной прямой для данного многоугольника M любую прямую, которая содержит хотя бы одну точку контур многоугольника и не содержит ни одной его внутренней точки (например, на рисунке 1 прямые a и b — опорные для многоугольника M, а прямая c — не опорная). Примугольник, все четыре стороны которого лежат на опорных прямых для многоугольника M, будем называть описанным около M. Таким

45

Является прямогольник $\Pi'$ на рисунке 1. Как только мы для заданного многоугольника $M$ (рис. 1) выбрали опорную прямую $(a)$, мы тем самым уже однозначно задали прямогольник, описанный около $M$. Описанный около $M$ прямогольник обладает, очевидно, тем свойством, что на каждой его стороне (быть может, в ее конце) помещается хотя бы одна вершина многоугольника (рис. 1). Из двух прямогольников, описанных около данного многоугольника $M$, будем называть лучшим тот, который имеет меньше шифу площадь. Оптимальный прямогольник, о котором говорится в основной задаче, следует, очевидно, искать среди прямогольников, описанных около $M$.

Технологи завода высказали две гипотезы:

Гипотеза I. Оптимальный прямогольник для многоугольника $M$ — это тот описанный прямогольник, у которого одна сторона содержит наиболее ширую сторону многоугольника.

Гипотеза II. Оптимальный прямогольник — тот описанный прямогольник, у которого одна сторона параллельна наиболее шириной многоугольника.

На этот этапе задача была предложена математику.

С чего начал математик

Matematик начал с совсем, казалось бы, неинтересного и малосодержательного вопроса: «А существенно ли вообще оптимальный прямогольник?»

Выберем на плоскости какую-нибудь точку $O$ и проведем через нее ось $l_0$ (рис. 2a). Затем проведем через $O$ произвольно луч $l = l_\varphi$ и пусты он образует угол $\varphi$ с осью $l_0$. Мы можем построить для многоугольника $M$ опорную прямую, параллельную лучу $l$, и затем — тот (единистенный) описанный прямогольник $P$, две стороны которого параллельны лучу $l$; его площадь обозначим через $S(\varphi)$. Будем изменять угол $\varphi$; пусты этот угол растет от 0 до $\pi$; при этом будет меняться и прямогольник $P$, и мы получим все возможные прямогольники, описанные около $M$; будет непрерывно изменяться и $S$ (т. е. при малом изменении угла $\varphi$ мало изменится и величины $S(\varphi)$). Но функция, непрерывная на некотором отрезке (в нашем случае — на отрезке [0; $\pi$]), обязана принять при каком-то (хотя бы при одном) значении $\varphi$ из этого отрезка своего наименьшего значения («Алгебра и начала аналiza 9—10», с. 89). Значит, найдется такой угол $\varphi$, что соответствующий описанный около $M$ прямогольник будет иметь наименьшую возможность площадь (будет оптимальным). Иначе говоря, среди прямогольников, описанных около многоугольника $M$, называя имеется (хотя бы один) оптимальным.

Удостоверившись в существование решения, математик приступил к его поиску.

Рассмотрим произвольный многоугольник — невпуклый или выпуклый. Слушай невпуклого многоугольника, однако, легко свойства к случаю выпуклого многоугольника. В самом деле, пусты $M$ — невпуклый многоугольник. Расмотрим наименьший выпуклый многоугольник $M'$, содержащий многоугольник $M$ ($M'$ называют выпуклой оболочкой многоугольника $M$, рис. 26). Легко понять, что прямогольник $P$ содержит в себе многоугольник $M$ в том и только том случае, когда он содержит его выпуклую оболочку $M'$. Следовательно, задача поиска оптимального прямогольника для многоугольника $M$ равносильна той же задаче для выпуклого многоугольника $M'$.

Чтобы освободятся с ней, попытаться сначала ее в простейшем частном случае, когда $M$ — треугольник.

Решение задачи для треугольника

Пусть $M$ — треугольник $ABC$, а $P$ — какой-либо прямогольник, описанный около $M$. На каждой из четырех сторон прямогольника должна быть хотя бы одна вершина треугольника. Поэтому по крайней мере одна вершина треугольника «обслуживает» две

46

стороны прямогольника $\Pi$, являясь их общим концом. Однако остальные две вершины могут располагаться по-разному на сторонах (или внутри) прямогольника, и возможно 4 прициппально разных случая (рисунки 3, $a-ε$) в зависимости от их расположения.

Обозначим площад треугольника $ABC$ через $\sigma$, а через $S$ — площад прямогольника $\Pi$.

В случае $\sigma$ имеем, очевидно: $S=2\sigma$.
В случае $\varepsilon$ и $\varepsilon$): $S>2\sigma$.

Как обстоит дело в случае $a$)? Проведем через $B$ параллель к стороне $AK$ прямогольника и отметим точки $F$ и $D$ ее встречи со стороной треугольника и стороной прямогольника. Тогда
$$S=S_{AKBD}+S_{BDNL}>2S_{BFA}+2S_{BFC}=2\sigma,$$
т. е. $S>2\sigma$.

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

Алгоритм получения оптимального прямогольника оченьен.

А как быть в случае четырехугольника?

Рассмотренный выше способ решения настоящего прост, что даже в голову не приходит искать друг способ. А между тем наш способ обладает одним кругпным недостатком: он не переносится на сluчай многоугольника, у которого больше трех сторон. Поэтому прикинем, какой другой, более перспективный, подход мог бы — в случае треугольника — привести нас к решению. В случае $a$) мы могли бы вычислить суммарную площадь отрезаемых треугольников (обозначим ее через $T$), выразив ее через угол $t$ (угол наклона стороны треугольника $AB$ к опорной прямой $AK$) и через элементы треугольника; можно показать, что эта сумма имеет вид
$$T=T(t)=A_1\sin 2t+A_2\sin(2t+\theta_2)+A_3\sin(2t+\theta_3),$$
где $A_1, A_2, A_3, \theta_2, \theta_3$ — какие-то числа, которые не зависит от $t$ (а зависит только от элементов треугольника $ABC$). Затем мы могли бы попытаться отбросить те значения $t$, для которых эта сумма завершено не принимает минимального значения. Этот способ в случае треугольника может показаться неоправданно громоздким, но в случае четырехугольника и других многоугольников он приводит к решению — и, как оказывается, не так уж сложно.

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

Задание 1. Каждую сумму вида
$$T(t)=A_1\sin(2t+\theta_1)+A_2\sin(2t+\theta_2)+\dots+A_m\sin(2t+\theta_m)$$
можно всегда привести к виду
$$T(t)=\rho\sin(2t+\theta),$$
(1)
где $\rho \geq 0$ и числа $\rho$ и $\theta$ зависит только от чисел $A_1, \dots, A_m, \theta_1, \dots, \theta_m$ (но не зависит от $t$).

Задание 2. Если для всех значений $t$ из некоторого интеграла вида $(t_0-\varepsilon; t_0+\varepsilon)$ (концы не входят) функция $\sin(2t+\theta)$ неотрицательна, то найдется на этом интеграле такое значение $t_1$, что верно строгое неравенство:
$$\sin(2t_1+\theta)<\sin(2t+0).$$
(2)

Случай произвольного $n$-угольника

Пусть $M$ — произвольный выпуклый $n$-угольник ($n \geq 4$), а $\Pi_0$ — ка-

47

кой-нибуд описанный около него прямогольник. Сначала рассмотрим те случаи, когда ни одна сторона многоугольника $M$ не лежит на стороне прямогольника $\Pi_0$. При таком требовании могут на контур прямогольника $\Pi_0$ оказаться не более четырех вершин многоугольника $M$. При этом возможны следующие три варианта:

I. Две вершины многоугольника $M$ служат концами диагонали прямогольника $\Pi_0$, а остальные вершины $M$ — внутри $\Pi_0$, рис. 4, а).

II. Одна вершина многоугольника $M$ служит вершиной прямогольника $\Pi_0$, две вершины многоугольника $M$ являются внутренними точками двух сторон $\Pi_0$, а остальные вершины $M$ — внутри $\Pi_0$, рис. 4, в).

III. Какие-то четыре вершины многоугольника $M$ являются внутренними точками четырех сторон прямогольника $\Pi_0$, а остальные вершины многоугольника $M$ лежат внутри $\Pi_0$, рис. 4, в).

Все три варианта рассматриваются единобразным примемом: вычисляется площадь описанного прямогольника и выясняется, нельзя ли его путем «малого шевления» улушить, т. е. получить описанный прямогольник с меньшей площадью; если окажется, что можно, то рассматриваемый прямогольник $\Pi_0$ зависит не оптимальный.*)

Мы рассмотрим здесь вариант I — наиболее простой. Обозначим через $A$ и $C$ те две вершины $M$, которые служат концами диагонали описанного прямогольника $\Pi_0$ ($F_0K_0L_0N_0$). Пусть $AB$ — сторона $M$, лежащая внутри $\Pi_0$ (кроме конца $A$); можно считать, что $AB$ — в $\triangle F_0K_0L_0$. Обозначим величины угла $BAK_0$ через $t_0$, величины угла $CAB$ через $\lambda$. Вычисляем площадь $S_{\Pi_0}$:

$$S_{\Pi_0} = \frac{1}{2} AC^2 \sin (2t + 2\lambda).$$

В силу задачи 2 существует такой угол $t$ на интервале $(t_0 - \varepsilon; t_0 + \varepsilon)$, что $\sin (2t + 2\lambda) < \sin (2t_0 + 2\lambda)$, а следовательно, $S_{\Pi_0} < S_{\Pi_0}$. А это означает, что прямогольник $\Pi_0$, появляющийся в варианте I, — не оптимальный: его можно «улушить». Разбор оставшихся двух случав мы оставляем читателю в качестве задач.

Задание 3. Докажите, что в варианте III — прямогольник $\Pi_0$ не оптимальный.

Задание 4. Докажите, что и в варианте II — прямогольник $\Pi_0$ не оптимальный.

Видим, что пока описанный прямогольник не содержит ни одной стороны многоугольника $M$ (см. варианта).

*) Подробно о примере «малого шевления» см. «Квант», 1979, № 4, с. 4 или книгу Балк М. В., Балк Г. Д. Пошк решения, М.: Детская литература, 1983, с. 86.

Рис. 4.

Рис. 5.

48

ты I, II, III), он не может оказаться оптимальным. Но оптимальный прямоугольник, как мы уже знаем, существует. Таким образом математик получил следующий алгоритм решения.

Алгоритм решения основной задачи

1. Если данный $n$-угольник $M$ — выпуклый, то начерти все описанные прямоугольники, содержащие хотя бы одну сторону многоугольника (таких прямоугольников не более $n$).
2. Вычисли плошади этих прямоугольников и выберя среди прямоугольников все такие, чья плошадь — наименьшая. Каждый из них является оптимальным прямоугольником для расматриваемого $n$-угольника. Других оптимальных прямоугольников не существует.
3. Если многоугольник $M$ невыпуклый, то сначала построй для него выпуклую оболочку $M'$, а затем найди для многоугольника $M'$ оптимальный прямоугольник — он будет и оптимальным прямоугольником для многоугольника $M$.

Когда понск упрощается
Мы видели, что нахождение оптимального прямоугольника для данного выпуклого $n$-угольника $M$ состоит к перебору не более, чем $n$ прямоугольников. Имеются важные случаи, когда этот перебор упрощается. Мы их формируем в виде задач. Здесь следует учеть, что у выпуклого $n$-угольника, отличного от прямоугольника, не более трех нетупых углов (в противном случае сумма углов не будет равной $180^\circ$ ($n-2$)).

Задача 5. Пусть в некотором выпуклом многоугольнике $M$ имеется лишь одна сторона, к которой прилегают два нетупых угла. Доказите, что тогда среди прямоугольников, описанных около $M$, имеется лишь один оптимальный — наименьшая. Если такой существует, то как его найти?

7. Пусть $M$ — заданный выпуклый $n$-угольник. Пусть $\{A_1, A_2, \dots, A_k\}$ — всевозможные выпуклы $k$-угольника с заданным угламми $a_1, a_2, \dots, a_k$ ($a_1 + a_2 + \dots + a_k = (k-2)n$), описанные около $n$-угольника $M$. Доказите, что если среди этих $k$-угольников имеется такой, чья плошадь минимальная, то хотя бы на одной его стороне содержится сторона $n$-угольника $M$ (так что оптимальных $k$-угольников не более, чем $n$).