Общий вид и схема счётной машины Б. Паскаля

На этой странице изображены общий вид и схема суммирующей машины, конструкционной одним из самых значительных людей в истории человека — Блезом Паскалем (1623—1662). Его портрет помещен слева. О Паскале, о его жизни, многочисленных научных достижениях, открытия, идеях и изобретения уже рассказывалось в «Кванте» (1973, № 8, с. 4). Там же рассказывалось и о построенной им машине (с. 10—11). Современники Паскале называют «паскалеевым колесом». О вычислительных машинах, об истории их изобретения, об устройстве (логическая и физическая) современных вычислительных машин и об их применениях подробно рассказано в интерсейной книге Р. С. Гутера и Ю. Л. Полунова «Математические машины», выпущенной издательством «Просвещение» в 1975 году. Советум ваме прочесть. С решением на эту книгу вы можете познакомиться на с. 50 этого номера журнала.

1

Главный редактор
академик И. К. Кикоин
Первый заместитель
главного редактора
академик А. Н. Колмогоров

Редакционная коллекция:
М. И. Башмаков
С. Т. Беляев
В. Г. Болтянский
Н. Б. Васильев
Ю. Н. Ефремов
В. Г. Зубов
П. Л. Капица
В. А. Кириллин
А. И. Климанов
(главный художник)
С. М. Козел
В. А. Лешковцев
(зам. главного редактора)
Л. Г. Макар-Лиманов
А. И. Маркушевич
Н. А. Патрикеева
И. С. Петраков
Н. Х. Розов
А. П. Савин
И. Ш. Слободецкий
М. Л. Смолянский
(зам. главного редактора)
Я. А. Смородинский
В. А. Фабрикант
А. Т. Цветков
М. П. Шаскольская
С. И. Шварцбург
А. И. Ширшов

Редакция:
В. Н. Березин
А. Н. Виленкин
И. Н. Клумова
Т. М. Макарова
(художственный редактор)
Т. С. Петрова
В. А. Тихомирова
Л. В. Чернова
(зав. редакцией)

В НОМЕРЕ:
2 Б. Алейников, П. Бузицкий, М. Дубсон. Симплекс-метод
9 Э. Казарян, Р. Саакян. Об одном методе решения задачи по электростатике
14 А. Дозоров. Зачем трансформатору сердечник?

Лаборатория «Кванта»
18 М. Головой. Фигура Гайдингара
Математический кругхок
21 Э. Готман. Задачи на доказательство
25 Я. Понарин. Вычисление площадей
Задачник «Кванта»
28 Задачи M391—M395; Ф403—Ф407
30 Решения задачи M351 — M353; Ф358 — Ф361

Практикум абитриента
37 Донецкий государственный университет
38 Московский институт управления им. С. Орджоникидзе
39 Московский институт электропровода машиностроения
40 Белоруссий институт инженеров железнодорожного транспорта
41 Донецкий политический институт
43 Марийский политический институт им. М. Горького
43 Ярославский политический институт
44 Московский государственный педагогический институт им. В. И. Ленина
45 Московский областной педагогический институт им. Н. К. Крупской

Х Всесоюзная олимпиада школьников
48 В. Березин, В. Тихомирова. Московская городская олимпиада школьников

Рецензии, библиография
50 Э. Белага. «Математические машины»
51 Л. Кармазина, Н. Меллер. «АЛГОЛ 60»
52 И. Клумова, М. Смолянский. Новые книги
«Квант» для младших школьников
54 Задачи
55 А. Орлов. Понск предмета
58 Ответы, указания, решения
Смесь (с. 47)

© Главная редакция физico-mатематической литературы издательства «Нука», «Квант», 1976 200

4

Решение $x_1^0, x_2^0, \ldots, x_n^0$ системы (1) называем допустимым решением ОЗЛП, если числа $x_1^0, x_2^0, \ldots, x_n^0$ неотрицательны. Оптимальный будем называть то из допустимых решений, которое обращает целевую функцию (2) в минимум.

Конкретная ОЗЛП может и не иметь решения: система (1) может быть несовместной, т. е. вообще не имеет решения; она может быть совместной, но не имеет допустимых решений; наконец, она может даже имеет допустимые решения, но среди них может не быть оптимального: функция (2) может быть не ограничена сизу на множество допустимых решений. Однако все эти описности поддержают нас только в специально придуманных задачах; в естественной возможности практических задач решение, как правило, существует.

Предположим, что система (1) совместна и ее уравнения линейно незаависимы, т. е. никакое из них не может быть выведено из других. Можно доказать, что тогда $m \leq n$.

Рассмотрим вначале случай, когда число уравнений $m$ равно числу переменных $n$. В линейной алгебре доказывается, что в этом случае система (1) имеет единственное решение. Если это решение допустимое, оно автоматически будет оптимальным.

Интерес представляет случай, когда $m < n$ (на практике это соответствует возможность выбора различных планов действия). Обозначим $n - m$ через $k$. В линейной алгебре доказывается, что можно какое-то $m$ переменных (они называются базисными) выразить через остальные $k$ переменных (их называют свободными). Система (1) имеет в рассмотрении случай бесконечное множество решений: придавая свободным переменным произвольны е значения и вычисляя соответствие базисных переменных, мы будем каждой раз получать новое решение системы (1). Некоторые решения системы (1) называется опорным, если значения по крайней мере $k$ переменных равны нулю. В теории линейного программирования доказывается, что оптимальное решение является опорным.

Из этой последней теоремы вытекает следующий план решения ОЗЛП: как-нибудь выбираем $k$ свободных переменных; разрешаем систему относительно $m$ оставшихся базисных переменных; полагая свободные переменные равными нулю, находим опорное решение; вычисляем соответствующее значение целевой функции. Перебрав все возможности выбора свободных переменных, увидим, на каком из опорных решений целевая функция примет наименьшее значение, — это и будет искомое оптимальное решение.

Для простых задач, в которых число переменных $n$ неверло, такой метод решения — «слепым» перебор — в принципие годится. Однако в задачах, возникших на практике, число переменных и число наложенных ограничений $m$ обычно очень велики — порядка сотен и даже тысяч. Для таких задач простой перебор практическим невозможен: число возможных способов выбора свободных переменных становится огромным!

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

Старейшим и наиболее известным из них является симплекс-method, созданный в конце сороковых годов американским математиком Дж. Данцгом.

Симплекс-method

Пусть, например, в качестве свободных переменных выбраны переные $k$ переменных $x_1, x_2, \ldots, x_k$, а остальные $m$ переменных выражены через

5

них:

$$\begin{align*} x_{k+1} &= \alpha_{k+1,1} x_1 + \alpha_{k+1,2} x_2 + \\ &\quad + \dots + \alpha_{k+1,k} x_k + \beta_{k+1}, \\ x_{k+2} &= \alpha_{k+2,1} x_1 + \alpha_{k+2,2} x_2 + \\ &\quad + \dots + \alpha_{k+2,k} x_k + \beta_{k+2}, \\ x_n &= \alpha_{n,1} x_1 + \alpha_{n,2} x_2 + \\ &\quad + \dots + \alpha_{n,k} x_k + \beta_n. \end{align*}$$

Положив все свободные переменные равными нулю, получим следующие системы (1):

$$\begin{align*} x_1^0 &= x_2^0 = \dots = x_k^0 = 0, \\ x_{k+1}^0 &= \beta_{k+1}, x_{k+2}^0 &= \beta_{k+2}, \dots \\ \dots, x_n^0 &= \beta_n. \end{align*}$$

Если все свободные члены $\beta_{k+1}, \beta_{k+2}, \dots, \beta_n$ неотрицательны, решение (6) является допустимым.

Чтобы проверить, является ли оно оптимальным, выразим целевую функцию $L$ через свободные переменные $x_1, x_2, \dots, x_k$, подставив выражения для $x_{k+1}, x_{k+2}, \dots, x_n$ из (5) в (2):

$$L(x_1, x_2, \dots, x_n) = d_0 + d_1 x_1 + d_2 x_2 + \dots + d_k x_k.$$

Из (6) вытекает, что $L(x_1^0, x_2^0, \dots, x_n^0) = d_0$. Посмотрим, не может ли мы уменшить значение целевой функции $L$, увеличивая значения свободных переменных $x_1, x_2, \dots, x_k$ (уменьшать мы их не можем, так как в решении (6) они равны нулю, а мы ищем допустимое решение).

Если все коэффициенты $d_1, d_2, \dots, d_k$ в равенстве (7) неотрицательны, то, увеличивая значения свободных переменных, мы будем уменшать значение функции $L$, т. е. будем уличать решение. В этом случае нам решение не является оптимальным.

Пусть, например, в равенстве (7) отрицательен коэффициент $d_1$. Если в системе (5) все коэффициенты при $x_1$ неотрицательны, то любое увеличение значения переменной $x_1$ оставит значения переменных $x_{k+1}, x_{k+2}, \dots, x_n$ неотрицательными и мы не выйдем из области допустимых решений. Значение же функции $L$ будет при этом неограниченно уменьшаться. Таким образом, в этом случае уравнения системы (5) есть также, в которых коэффициент при $x_1$ отрицательен. Для переменных, стоящих в левых частях этих уравнений, увеличение значения переменной $x_1$ описано: оно может сделать их отрицательными.

Если, например, $\alpha_{k+1,1} < 0$, то, очевидно, значение переменной $x_1$ можно уменшить только до $-\frac{\beta_{k+1}}{\alpha_{k+1,1}}$. (При $x_1^0 = -\frac{\beta_{k+1}}{\alpha_{k+1,1}}$, $x_2^0 = \dots = x_k^0 = 0$ получим $x_{k+1}^0 = 0$.)

Средние переменных, для которых увеличение значения переменной $x_1$ описано, выберем ту, которая равше всех обратится в нуль, т. е. ту, для которой увеличина $-\frac{\beta_l}{\alpha_l,1}$ меньше всего.

Пусть такая «наиболее угрожаемая» переменная будет $x_r$.

Выведем теперь из числа свободных переменных $x_1$ и переведем вместе в группу свободных переменных $x_r$, т. е. разрешим систему (1) относительно базисных переменных

$$x_1, x_{k+1}, \dots, x_{r-1}, x_{r+1}, \dots, x_n.$$

Дальше все повторяется: положив все свободные переменные $x_2, \dots, x_k, x_r$ равными нулю, найдем соответствующое решение; выразим целевую функцию $L$ через новые свободные переменные; если все коэффициенты при переменных в полученном выражении

6

Для $L$ неотрицательны, найденное решение — оптимальное; в противном случае процесс выбора базисных переменных и улучшения решения продолжается.

Описанный алгоритм и называется симплекс-методом. (Обратили ли Вы, читатель, внимание, что в нашем изложении алгоритма оставлена одна «дырка»: одна возможность не рассмотрена?)

Два примера

Рассмотрим сначала общую школьную задачу.

Задача 1. Три циклника хотим добраться до лесного озера, расположенного в 20 км от дома. У них есть один двухместный мoped, на котором можно ехать со скоростью 36 км/час. Пешком каждой циклника может идти со скоростью 4 км/час. Как организовать движение, чтобы всем проимь быстрее добраться до озера? Каково наименьшее время, за которой это можно сделать?

Очевидно, что многократная смена пассажиров на море не сможет дать никакой выгоды во времени по сравнению с однократной. Поэтому составим такой план организации движения: в начальной момент времени из дома $\Delta$ одновременно выезжают на моредева школьника и выходит пешком третий школьник. В промежуточной точке $T$ водитель мореда высказывает свое определение $t_1 = t_2$.

Нам надо найти такое $x$, при котором функция $t = \max (t_1, t_2)$ принимает наименьшее значение. Кроме того, нам надо найти значение функции $max (t_1, t_2)$ при этом $x$, т. е. числом ($\max (t_1, t_2)$). Из рисунка 2 (на нем красным цветом нарисован график функции $t_1(x)$, черным — функция $t_2(x)$, синним — функция $max (t_1, t_2)$) сразу видно, что искомое $x$ определяется из уравнения $t_1 = t_2$.

Тем не менее, чтобы проиллюстрировать общий метод, поставим и решим данную задачу как задачу линейного программирования. Переформулируем ее так: найти наименьшее $t$, для которого одновременно $t \geq t_1$ и $t \geq t_2$. Итак, нам надо найти неотрицательные значения переменных $x$ и $t$, которые удовлетворяют бы системе неравенств

$$\begin{cases} t \geq \frac{x}{36} + \frac{20-x}{4}, \\ t \geq \frac{5}{9} + \frac{2}{45} x \end{cases}$$

7

и обращали в минимум функцию $L$:
$$L(x, t) = 0 \cdot x + 1 \cdot t = t. \tag{9}$$
Мы получили задачу линейного программирования. Сведем ее к ОЗЛП.
Система (8) равносильна системы
$$\begin{cases} 2x + 9t - 45 \geq 0, \\ -2x + 45t - 25 \geq 0. \end{cases} \tag{10}$$

Обозначим $2x + 9t - 45$ через $y_1$, $-2x + 45t - 25$ через $y_2$. Тогда $2x + 9t - 45 = y_1$, $-2x + 45t - 25 = y_2$ и $y_1 \geq 0, y_2 \geq 0$. Нашу задачу мы можем теперь сформулировать так: найти неотрицательные значения переменных $x, t, y_1, y_2$, которые удовлетворяют бы системе уравнения
$$\begin{cases} 2x + 9t - y_1 = 45, \\ -2x + 45t - y_2 = 25 \end{cases} \tag{11}$$

и обращали в минимум целевую функцию $L(x, t, y_1, y_2) = t$. А это уже ОЗЛП. Решим ее симплекс-методом.

Выберем в качестве базисных переменных $y_1$ и $y_2$ (систему (11) легче всего решить относительно них) и выразим их через свободные переменные $x, t$:
$$\begin{cases} y_1 = 2x + 9t - 45, \\ y_2 = -2x + 45t - 25. \end{cases} \tag{12}$$

Полагая свободные переменные равными нулю, получим решение системы (12) и (11):
$$x^{(1)} = t^{(1)} = 0, y_1^{(1)} = -45, y_2^{(1)} = -25.$$
Это решение не является допустимым.

Выберем теперь в качестве базисных переменных две другие переменные, например $t$ и $y_2$. (В теории линейного программирования существует метод, указывающий, каким образом выбирать новые свободные переменные так, чтобы приближаться к области допустимых решений. Здесь мы этот метод не излагаем.) Разрешим систему (11) относительно них:
$$\begin{cases} t = -\frac{2}{9}x + \frac{1}{9}y_1 + 5, \\ y_2 = -12x + 5y_1 + 200. \end{cases} \tag{13}$$

Полагая свободные переменные равными нулю, получим решение системы (13) и (11):
$$x^{(2)} = y_1^{(2)} = 0, t^{(2)} = 5, y_2^{(2)} = 200. \tag{14}$$

Решение (14) уже является допустимым. Чтобы проверить, является ли оно оптимальным, выразим целевую функцию $L$ через свободные переменные $x$ и $y_1$. Из (9) и (13)
$$L(x, t, y_1, y_2) = -\frac{2}{9}x + \frac{1}{9}y_1 + 5. \tag{15}$$

Значение целевой функции $L$ на решении (14) равно 5.

Поскольку коэффициент при $x$ в (15) отрицательен, решение (14) не является оптимальным: увеличивая значение переменной $x$, мы будем уменьшать значение целевой функции $L$.

В общих уравнениях системы (13) коэффициенты при $x$ отрицательны. Поэтому увеличение значения переменной $x$ описано как для $t$, так и для $y_2$. Это увеличение может сделать их отрицательными. Из первого уравнения системы (13) следует, что значение переменной $x$ можно увеличать до $-5 / \left(-\frac{2}{9}\right) = \frac{45}{2} = 22 \frac{1}{2}$ (при таком значении $x$ и при $y_1 = 0$ получим $t = 0$; при дальнейшем увеличении $x$ значение переменной $t$ становится отрицательным); из второго — до $-\frac{200}{12} = \frac{50}{3} = 16 \frac{2}{3}$. Таким образом, при увеличении значения переменной $x$ равше обратится в нуль переменная $y_2$: она находится в «болееугрожаемом» положении, чем $t$.

8

Выведем теперь из числа свободных переменных $x$ и переведем вместо нее в группу свободных переменных $y_2$, т. е. разрешим систему (11) относительно базисных переменных $x$ и $t$:

$$\begin{cases} x = \frac{5}{12} y_1 - \frac{1}{12} y_2 + \frac{50}{3}, \\ t = \frac{1}{54} y_1 + \frac{1}{54} y_2 + \frac{35}{27}. \end{cases}$$

Полягая свободные переменные равны нулю, получим решение системы (16) и (11):

$$y_1^{(3)} = y_2^{(3)} = 0, \quad x^{(3)} = \frac{50}{3}, \\ t^{(3)} = \frac{35}{27}.$$

Выразим целевую функцию $L$ через $y_1$ и $y_2$. Из (9) и (16)

$$L(x, t, y_1, y_2) = \frac{1}{54} y_1 + \frac{1}{54} y_2 + \frac{35}{27}.$$

Значение целевой функции $L$ на решении (17) равно $\frac{35}{27}$.

Поскольку все коэффициенты при переменных в (18) неотрицательны, решение (17) является оптимальным. Итак, задача решения: попеду надо ссадить пассажира на расстоянии $x^{(3)} = \frac{50}{3} = 16\frac{2}{3}$ (км); наименьшее время, за которое можно добрать до озера, равно $t^{(3)} = \frac{35}{27} = 1\frac{8}{27}$ (час).

Приведем теперь типичную практическую задачу, естественно ставшую как задача линейного программирования. Это так называемая «задача о диете», или «задача о пищевом рационе».

Задча 2. Директору столовой нужно составить меню. В его распоряжении имеется 5 видов продуктов: хлеб, овощи, фрукты, мяса, рыба.

Известно, что килограмм хлеба стойит $c_1$ рублей, килограмм овощей — $c_2$ рублей и м. д. Известно также, что килограмм хлеба содержит $a_{11}$ ке белков, $a_{12}$ ке жиров и $a_{13}$ ке углеводов и м. д. (содержание белков, жиров и углеводов в килограмме каждой вида продуктов указано в таблице на рисунке 3). Требуется максимальное меню, чтобы в нем содержалось не менее $b_1$ ке белков, не менее $b_2$ ке жиров и не менее $b_3$ ке углеводов, причем стойимость его была минимальной.

Обозначим через $x_1$ количество хлеба, которое войдет в меню, через $x_2$ — количество овощей и т. д. Общая стоимость меню $L$, очевидно, выразится равенством

$$L(x_1, x_2, x_3, x_4, x_5) = \sum_{i=1}^{5} c_i x_i.$$

Ограничения на питательность меню выражаются системой неравенств

$$\begin{cases} a_{11}x_1 + a_{21}x_2 + a_{31}x_3 + a_{41}x_4 + \\ + a_{51}x_5 \geq b_1, \\ a_{12}x_1 + a_{22}x_2 + a_{32}x_3 + a_{42}x_4 + \\ + a_{52}x_5 \geq b_2, \\ a_{13}x_1 + a_{23}x_2 + a_{33}x_3 + a_{43}x_4 + \\ + a_{53}x_5 \geq b_3. \end{cases}$$

Наша задача приняла вид: найти неотрицательные значения переменных $x_1, x_2, x_3, x_4, x_5$, которые удовлетворили бы системе неравенств (20) и обращали в минимум функцию $L$ из (19). Это — задача линейного программирования.