Физика и линейные неравенства

17

Физика и линейные неравенства
З. Я. Тымеладзе

Механика

Пушки революции грохотали на улицах Парижа. Картечь гвардейцев взрябила штукатурку у самой баррикады.
— Ты ранен, Этъен?
— Пустяки, царапина. Королевские гвардейцы стрелют из того особняка с колоннами. Если мы их не выьем оттуда, нам не продержаться до прихода отряда печатников.
— А наша пушка их не достanet?
— Нет, мало только от этой_maxины. Вот если бы ее удалось вкатить на ту площадку! Эй, Жан-Батист… Ох, это уже серbezнее,— простонал Этъен, схватившись за грудь.
— Что с вами, мосье?
— Гражданин Этъен, а не мосье! Ты уже не в монастые бенедиктище, мальчик, а в революционной армии. Пока меня переявывают, вкати с ребятами пушку вон на ту площадку.
— Слушаюсь, гражданин Этъен!
— Постойте,— вместе Пьер. — А выдержит ли площадка? Если она рухнет, мы лишимся единственной пушки.
— Это наш последний шанс,— проштал Этъен, теряя сознание.
— Что ты там рисуешь, Жан-Батист? Снова геометрия? Берись лучше за ружье, а пушкой нам нельзя рисковать!
— Гражданин Пьер! Пользуясь затишем, я готов доказать вам, что никакого риска нет. Пушку можно вкатывать.

— Ну, попробу! Я ведь пришел на баррикады из университета, из этого болота, где прошетают бездарности. Клянусь не возвращаться туда, пока профессорам не запретят читать лекции по шпаргалкам. Итак?

— Площадка имеет форму квадрата со стороны в 4 метра, она опирается на четыре столбца (см. рис. 1). Каждый столбецивает одну тонну, а пушка вместе с расчетом и ядрами весит 2,5 тонны. Сама площадка надежна, могут сломаться только столбцы, не так ли, гражданин Пьер?

— Допустим; но учти, столбцы вместе выдержат 4 тонны только в том случае, если положить груз в центр площадки. А пушку нам придется сdynнуть, так что ее центр тяжести будет в точке М — иначе не прострелять особняк.

— Давайте теперь определим, какую максимальную силу можно при-

Рис. 1.

18

ложить в точке $M$. Если эта сила больше всего пушки — то все в порядке, и мы заставим гвардейцев дорого заплаать за смертЬ ЭтЬена. Обозначим числа в столбах, на которые опирается площадка, через $R_1, R_2, R_3$ и $R_4$ и потребуем, чтобы было

$$\begin{cases} R_1 \leqslant 1, \\ R_2 \leqslant 1, \\ R_3 \leqslant 1, \\ R_4 \leqslant 1. \end{cases}$$

Положительные значения числий указывают на скатие в столбах, отпечатленные — на растяжение.

— Так-то оно так, но что из этого? Ведь это неравенства, а не уравнения, что о них можно сказать? Не помню, чтобы о них писали что-либо славные граждане Лагранж и Даламбер.

— И я не помню, хотя и изучал их труды. Но продолжим рассуждения. Силы $R_1, R_2, R_3$ и $R_4$ не могут быть любыми, они должны удовлетворять условиям равновесия. Два из них получается, если приравнять нулю моменты от всех сил, действующих на площадку, относительно линии 1—4 и 1—2. Учитывая, что момент — это произведение сил на плою, получаем два уравнения:

$$4R_2 + 4R_3 - P = 0,$$

$$4R_3 + 4R_4 - 2,5P = 0.$$

Третье уравнение равновесия нужно получить из равенства нулю суммы всех сил, действующих на площадку — иначе эта площадка упала бы вниз или вознеслась на небо.

— Подобно тому ловкачу, которое так чятит церковники! — встал Пьер.

— Отсюда получаем уравнение

$$R_1 + R_2 + R_3 + R_4 = P,$$

— записал Жан-Батист, покрасневское из-за богатыхственной остроты волнодумца, чем из-за пули, просвистшей у егоуха. Из трех уравнений (2), (3) и (4) четыре неизвестных $R_1, R_2, R_3, R_4$, конечно, не определять. Но можно добавить такое условие: сила $P$ должна быть максимальная. Запишем его так: $P \rightarrow \text{max.} \text{Кроме того, у нас есть еще неравенства (1).}$

— Чудня задача,— сморщил люб гражданин Пьер.— Я не удивюсь, если еще лет это пятьдесят она не будет иметь названия. Не говорю уже о гражданах Даламбере и Лагранже, у которых ее почему-то…

— Оставим в стороне проочеется и тени великих и решим эту несложную задачу,— продолжал Жан-Батист.— Для этого выразим из уравнения (2) и (3) $R_3$ и $R_4$:

$$R_3 = \frac{1}{4}P - R_2,$$

$$R_4 = \frac{1}{4}\left(\frac{5}{2}P - 4R_3\right) = \frac{3}{8}P + R_2$$

и подставим их значения в уравнение (4); получим:

$$R_1 + R_2 + \frac{1}{4}P - R_2 + \frac{3}{8}P + R_2 = P.$$

Отсюда можно найти $P$:

$$P = \frac{8}{3}(R_1 + R_2)$$

и подставить в уравнение (5):

$$R_3 = \frac{2}{3}R_1 - \frac{1}{3}R_2, \quad R_4 = R_1 + 2R_2.$$

Теперь систему неравенств (1) можно переписать лишь для двух переменных $R_1$ и $R_2$ (остальные исключены с помощью трех уравнений):

$$\begin{cases} R_1 \leqslant 1, \\ R_2 \leqslant 1, \\ \frac{2}{3}R_1 - \frac{1}{3}R_2 \leqslant 1, \\ R_1 + 2R_2 \leqslant 1. \end{cases}$$

— Хорошо, но нельзя ли посоречать? Огонь усиливается.

19

Рис. 2.

Рис. 3.

— Осталось немного. Давайте изобразим эти неравенства графически. Введем оси координат $R_1$ и $R_2$ (рис. 2).

Неравенство $R_1 \leqslant 1$ означает, что допустимые значения $R_1$ должны лежать не правее линии $R_1 = 1$, а $R_2 \leqslant 1$, — что не выше линии $R_2 = 1$ — обозначим это штриховкой. Полагая $R_1 = 0$, из третьего неравенства системы (7) находим $R_2 \geqslant -3$, а полагая $R_2 = 0$, получаем $R_1 \leqslant 3/2$. Проведя через точки с координатами $(0, -3)$ и $\left(\dfrac{3}{2}, 0\right)$ прямую и заштриховав ее сверху, получим графический образ третьего неравенства. Наконец, таким же способом изображаем и четвертое неравенство.

— Но, кажется, не все эти линии нужны.

— Верно! Самое существенное представлено на рисунке 3, где закрашена допустимая область значений сил $R_1$ и $R_2$. Точки внутри этой области, включая границу, удовлетворяют всем неравенствам. Но это еще не все. В допустимой области нужно найти такую точку, в которой $P$, определяемое равенством (6), принимает наибольшее значение. Для начала построим линию

$$P = \frac{8}{3}\,(R_1 + R_2) = 0.$$

Она проходит через начало координат, как показано на рисунке 3.

2*

— Но это нам мало что дает: ясно, что нулевую силу площадка выдержит.

— Разумеется. Но почему выдержит? Потому, что линия $P = 0$ пересекает допустимую область.

— Постой! Мне не совсем понятно. На линии $P = \dfrac{16}{9}$ есть точки, которые лежат вне допустимой области, скажем, точка $K$. Если в столбах возникнет распределение усилий, отвечающее этой точке, то площадка рухнет и…

— Вы не правы. Хотя я и не умею этого доказать, но чувствую: если материал столбов пластичен, то конструкция не разрушится при $P = \dfrac{16}{9}$. В ней возникнет распределение усилий, выражаемое какой-то точкой $E$ внутри допустимой области. Правда, неизвестно, какой именно точкой, но это уже неважно.

Рассмотрим теперь семейство линий $P = \dfrac{8}{3}\,(R_1 + R_2) = \mathrm{const} > 0$. Они параллельны линии $P = 0$ (ведь угловые коэффициенты у них одни и те же). Из этих линий нужно выбрать ту, которая дальше всего отстоит от линии $P = 0$, но при этом пересекает допустимую область. Это линия $P = \dfrac{8}{3}\,(1 + 0) = \dfrac{8}{3}$, проходящая через точку $B$ с координатами $R_1 = 1$, $R_2 = 0$. Понятно?

20

— Честно говоря, не совсем. Давно не занимался математикой. Революция требует от меня, чтобы я чаще заглядывал в географические карты, чем в учебник геометрии.

— Отлично! Вспомним географию! Представьте себе, что $ABC$ — это граница участка на местности, который равномерно повышается с юго-запада на северо-восток, а линии $P = \mathrm{const}$ — это горизонтали на географической карте. Чем выше отметка местности, тем больше в ней значение $P$. Ясно, что самая высокая отметка будет в точке $B$, где $P = \dfrac{8}{3} = 2\,\dfrac{2}{3}$. Это больше, чем весит наша пушка $\left(2\,\dfrac{2}{3} > 2\,\dfrac{1}{2}\right)$. Значит, пушку площадка выдержит.

— Закатывайте, граждане, пушку! — закричал Пьер вместо ответа: натиск гвардейцев нарастал, и медлить дальше было нельзя.— Гражданин Жан-Батист Фурье! Именно ты должен быть профессором математики! Смерть тиранам!

И Жан-Батист Фурье стал профессором математики созданного в 1794 году нового учебного заведения — Нормальной школы! Бездарные конкуренты не смогли этому помешать: в том же году революционный Конвент действительно издал закон, запрещавший профессорам пользоваться во время лекций записками.

Рождение линейного программирования

Только на склоне лет, в 1823 году, признанный математик Жан-Батист Фурье (1768—1830), бывший друг Наполеона, бывший префект департамента Изер и создатель «Теории теплоты», выступил во Французской Академии с несколько странным по тем временам докладом о линейных неравенствах, в котором он рассказал постановку и указал путь решения

описанной выше задачи. Но не была ли она ясна ему раньше, когда юношей он попал в революционный Париж? Ведь ничего особенно сложного в этой задаче нет — во всяком случае, теория рядов Фурье, принадлежащая тому же автору, куда сложнее.

Тем не менее название этой задачи — линейное программирование — родилось лишь в сороковых годах нашего века. Самые известные приложения линейного программирования связаны с экономикой *). Однако необходимость найти экстремум линейной функции при ограничениях в виде системы линейных уравнений и неравенств возникает в самых разнообразных задачах, в том числе и весьма далеких от экономики. Примером служит рассмотренная выше задача механики о действии сосредоточенной силы на квадратную пластинку — первое известное нам приложение линейного программирования.

В более общем виде задача линейного программирования формулируется так. Имеется n неизвестных $x_1, x_2, \ldots, x_n$. Требуется найти такие их значения, которые удовлетворяют системе ограничений

$$\left\{\begin{array}{l} a_{11}x_1 + \ldots + a_{1n}x_n \leqslant a_1, \\ a_{21}x_1 + \ldots + a_{2n}x_n \leqslant a_2, \\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot \\ a_{r1}x_1 + \ldots + a_{rn}x_n \leqslant a_r, \\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot \\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot\ \cdot \\ a_{m1}x_1 + \ldots + a_{mn}x_n \leqslant a_m \end{array}\right.$$

и доставляют максимум функции

$$z = p_1x_1 + p_2x_2 + \ldots + p_nx_n,$$

носящей название «целевой». Коэффициенты $a_{11}, a_{12}, \ldots, a_{mn}$ и свободные члены $a_1, \ldots, a_m$ при этом считаются заданными.

---

*) См. статью: А. Б. К а т о к, Экономика и линейные неравенства, «Квант», 1971, № 3, 4.

21

Иногда вместе максимума целевой функции требуется найти ее минимум — это зависит от смысла задачи (в этом случае можно искать максимум функции $z_1 = -z$). Заметим, что экстремум функции $z$ (minimum или максимум) всегда находится на границе допустимой области. Это остояльство использует самый распространенный метод решения задачи линейного программирования — симплекс-метод, которое мы здесь не касаемся.

А как же все-tаки быть с физическим обоснованием задачи Фурье? Прав ли он был, считая, что сама природа помогает конструкции найти то, быть может, единственное распределение внутренних условий, при котором конструкция способна выделять внешнюю нагрузку? Да, для плотного материала это так. Собственно, механики подозревали это obstructionное еще до Фурье, но строая теория была построена лишь в 1936 году советским ученым А. А. Гвоздевым. Согласно этой теории, конструкция как бы сама, повинуясь слим природы, решит вышепутомуную задачу линейного программирования и найти для себя наличище распределение внутренних условий. Найдет, если оно существует,— при нагрузке в 3 тонны на упомянутую площадную распределения условий в столбах уже не найдется, и площадка рухнет.

Электричество

Что бы убедиться в применимости линейного программирования к электрическим сетям, перенесемся с улиц Парижа в современную шкалу. Избретатели Витя и Коля собирают тиннственное устройство (о назначении которого они просили не говорить) по схеме, представленной на рисунке 4.

Устройство состоит из двух источников ЭДС, трех сопротивлений и трех приборов, называя которых

Рис. 4.

представляют профессиональную тайну изобретателей. Нам удалось только узнать, что прибор №1 требует тока не менее чем 2 а, прибор №2 — не менее 1 а, а на приборе №3 наряжение должно быть не менее 1,5 в. Все было готово к началу эксперимента, когда выяснили необходимое затруднение: у Вити и Коли оказалось всего 5 батареек с ЭДС 1 в каждая. Попытки включать их научд к успеху не приводили: приборы не сравывали. Изобретателиащили было в тупик, но тут Коля вспомнили о линейном программировании и начал рассуждать.

— Задачу можно сформировать следующим образом. Требуется подобрать источники ЭДС, чтобы они обеспечивали заданные токи и направления в сети и сумма ЭДС была минимальной:

$$z = E_1 + E_2 \rightarrow \min.$$ (8)

Формула (8) определяет целевую функцию задачи линейного программирования. Составим ограничения. Сумма токов в каждой сети должна быть равна нулю:

$$-I_1 + I_2 - I_3 = 0.$$ (9)

Сеть состоит из двух контуров, вдоль каждой из которых суммарное напряжение направляется сумме ЭДС:

$$I_1 + 2I_2 = E_1 + E_2,$$ (10)

$$2I_2 + I_3 = E_2.$$

22

Рис. 5.

Наконец, особенность секретных приборат требуют, чтобы токи и напряжения в них подчинялись ограничениям
$I_1 \geq 2, I_2 \geq 1, |U_3| \geq 1, 5$. (11)
Задача отыскания значений $I_1, I_2, I_3, E_1, E_2$, удовлетворяющих ограничениям (9)—(11) и доставляющих минимум целевой функции (8), есть задача линейного программирования. Выразив из уравнения (9) и (10) токи через ЭДС $E_1$ и $E_2$: $I_1 = \frac{1}{5} (3E_1 + E_2)$,
$I_2 = \frac{1}{5} (E_1 + 2E_2)$, $I_3 = \frac{1}{5} (-2E_1 + E_2)$, и подставив значения ЭДС в неравенства (11), получаем три ограничения:
$$\begin{cases} 3E_1 + E_2 \geq 10, \\ E_1 + 2E_2 \geq 5, \\ |-2E_1 + E_2| \geq 7, 5. \end{cases}$$

Не поняет, — сказал Витя, который тоже был знаком с линейным программированием. — Здесь есть знаки модели, что ты будешь с ним делать?

— Запишу третье ограничение в виде двух неравенств
$E_2 - 2E_1 \geq 7, 5; E_2 - 2E_1 \leq -7, 5,$
— отправовал Коля. — Тепер изобразим прямые, отвечающие всем неравенствам-огранчением (см. рис. 5), и получим две допустимые области $\Omega_1$ и $\Omega_2$ ($E_1$ и $E_2$ положительных)

Рис. 6.

и прямую, соответствующее целевой функция. Из рисунка видно, что оптимальное решение достигается в точке $A$, в котором $E_1 = 4, E_2 = 0, 5$.

— Дробить батарейки нельзя, — запротестивал Витя, хозяйн батареек. — Решение должно быть целочисленным. Давай округлим решение до целых: поставим вместе $E_1$ четыре батарейки, а вместе $E_2$ — одну.

— Не торопись и положки паяльник, — остановил его расудительный Коля. — Ведь видно, что точка $E_1 = 4, E_2 = 1$ лежит вне допустимой области, третий прибор работает не будет.

Так наши друзья выясниликовое свойство задачи линейного программирования: решения не всегда можно округлять до целых значений. Из-за этого пришлось специальное разработать целочисленное линейное программирование, которое справляется с этой трудностью. К счастью, ребятам