50 лет линейному программированию

9

В 1975 году советский математик Л. В. Канторович и американский экономист Т. Купманс были удостоены Нобелевской премии.

Эти премии получили свое название в честь их учредителя — известного химикка и изобретателя Альфреда Нобеля. Согласно завершению Нобеля, они должны были присуждаться за научные открытия в области физики, химии, физологии или медицинны, за литературные произведения, «отражающие человечестве идеалы», а также тем, кто «внесет весомый вклад в сплошение народов, уничтожение работы, снижение численности существующих армей и соедейные мироной договоренности». Математик premия не предназначалась. Оdnako в 1969 году Шведский bank по служю 300-летия со дня своего образования учредил premio памяты А. Нобеля — по экономическим наукам. Она-то и была присуждана в 1975 году Л. В. Канторовичу и Т. Купмансу за создание новой математической теории (получшей навание линейного программирования) и применения этой теории к экономике.

В авторографии, представленной в Нобелевский комитет, Леонид Витальевич Канторович рассказывает о собственях, слушихся в 1939 году. К нему, 26-летнему профессору-математику, обращались за консультанцией сотрудники laboratorии фанерного треста, который нуждно было решить задачу о наиболее высоком распределении материалов между станками. Эта задача совпадла с нахождению максимума линейной функции, заданной на многограничке. Максимум такой функции достигается в вершине, однako число вершин в этой задаче достигало миллиарда… Поэтому простой перебор вершин не годился.

Леонид Витальевич писал:

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

И уже летом 1939 года была сделана в набор книга Л. В. Канторовича «Matематические методы организации и планирования производства», в котором заключалась основания того, чтоbine назвается математической экономикой.

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

Пусть на произведение нужно изготовить набольшее число комплектов из двух деталей. Имеются станки трех типов I, II и III, данные о которых приведены в таблице.

«Естественное распределение», применявшееся на практике, состоит в том, что на каждой группе станков производили набольшее число комплектов. Станки первого типа могут произвести 20 комплектов (например, так: первый и второй станок производят по 10 первых деталей, а третий — 20 вторых) и не могут произвести больше. Аналогичный смысл имеет число 36 для станков второго типа: первый станок производит только

10

ко первые детали, второй — только вторые, а третий — 4/5 времен производит первый, а 1/5 времен — второй детали. Аналогично — и для станков третього типа.

Как видно из таблицы, оптимальное распределение дает сущеенную выгоду — 9 лишних комплектов! — не требуется никаких дополнительных затрат.

Для того чтобы найти далеко не оченьное оптимальное распределение, надо перевести задачу на язык математики. Итак, в нашем распоряжении имеется семь станков — первый, второй и третий станки образуют первый тип, четвертый, пятый и шестой — второй и, наконец, seventh — третий тип. Требуется указыть доли времени, в течение которых каждый станок должен выработать первый и второй деталь. Пусть $\alpha_i$ — доля времени, в течение которого $i$-ый станок будет выработать первый деталь, а $\alpha'_i$ — доля времени его работы над второй деталью. Тогда $\alpha_i \geq 0$, $\alpha'_i \geq 0$, $\alpha_i + \alpha'_i \leq 1$, $i = 1, 2, \dots, 7$. Число первых деталей, сделанных станками, будет равно

$$10(\alpha_1 + \alpha_2 + \alpha_3) + 20(\alpha_4 + \alpha_5 + \alpha_6) + 30\alpha_7.$$

Аналогично, число вторых деталей равно

$$20(\alpha'_1 + \alpha'_2 + \alpha'_3) + 30(\alpha'_4 + \alpha'_5 + \alpha'_6) + 80\alpha'_7.$$

Число первых и вторых деталей должно быть одинаковым и как можно большем. Так мы приходим к задаче:

найти максимальное число $s$ такое, что

$$s = 10(\alpha_1 + \alpha_2 + \alpha_3) + 20(\alpha_4 + \alpha_5 + \alpha_6) + 30\alpha_7,$$

и подставим в выражение для $s$. Получим

$$s = \frac{230}{3} + \left(20 - \frac{50}{3}\right)y + \left(30 - \frac{110}{3}\right)z = \frac{230}{3} + \frac{10}{3}y - \frac{20}{3}z.$$

Теперь ясно, что самое большее значение суммы получится, когда $y = 3,$

12

ках тоже имеет такой вид:

$$\begin{cases} s = 10x + 20y + 30z, \\ 10x + 20y + 30z \geq 20(3-x) + 30(3-y) + 80(1-z), \\ 20(3-x) + 30(3-y) + 80(1-z) \geq 10x + 20y + 30z, \\ x \geq 0, 3 \geq x, y \geq 0, 3 \geq y, \\ z \geq 0, 1 \geq z. \end{cases}$$

«Многогранник», заданный системой неравенств, изображен снимм цветом на рисунке 1 — он совпится к плоскому патиугольнику. Вершина, в которой функиция s достигает максимума, помещена красным.

Л. В. Канторович предложил несколько подходов к решению формулированной общей задачи. Один из них основан на идее двойственности. Чтобы понять ее, решим задачу о станках другим способом.

Снова обозначим $\alpha_1 + \alpha_2 + \alpha_3$ через $x$, $\alpha_4 + \alpha_5 + \alpha_6$ — через $y$ и $\alpha_7$ — через $z$; введем новые обозначения: $x' = \alpha'_1 + \alpha'_2 + \alpha'_3$, $y' = \alpha'_4 + \alpha'_5 + \alpha'_6$, $z' = \alpha'_7$. Сопоставим каждому набору $(x, y, z, x', y', z')$, где все числа неотрицательны и связаны неравенствами

$$x + x' \leq 3, y + y' \leq 3, z + z' \leq 1,$$

(1) точку плоскости $(a; b)$ с координатами $a = 10x + 20y + 30z$, $b = 20x' + 30y' + 80z'$. (2)

Что же представляет собой множество $C$ всех точек, заданных соотношениями (1) и (2)? Это множество — сумма трех множеств: $C_1$, образованного теми точками $(a; b)$, для которых $a = 10x, b = 20x'$; $C_2$, состоящего из точек $(a; b)$, для которых $a = 20y$, $b = 30y'$; $C_3$, состоящего из точек $(a; b)$, для которых $a = 30z, b = 80z'$. При этом, конечно, выполнен неравенства (1). Множества $C_1, C_2$ и $C_3$ — это треугольники, изображенные на рисунке 2.

Чтобы построить искомое множество $C$, сначала найдем сумму $C_1$ и $C_2$, т. е. множество точек $(a; b)$ с координатами

$$a = 10x + 20y, b = 20x' + 30y'.$$

Для этого треугольник $C_2$ откладывается от верхней вершины треугольника $C_1$, а затем $C_2$ «съезжает с горки», образованной гипотенузой $C_1$. Получается четырехугольник, изображенный на рисунке 3.

Теперь можно построить и множество $C$. Отложим треугольник $C_3$ от верхней вершины на рисунке 3 и даим ему «съезжает с горки», образованной двухзвенной ломаной. Получается пятуюугольник $C$, изображенный на рисунке 4.

А что же требуется в задаче? Требуется найти такую точку $A = (a; b)$, что во-первых, $a = b$, а во-вторых, $a$ имеет наиболее значение. Эта точка лежит на пересечении биссектрисы и ломаной $KLMN$ (см. рис. 4) и имеет координаты $(86^2/3, 86^2/3)$.

Как нам добавиться до точки $A$? Пойдем к ней с двух сторон. Сделаем шаг по отрезку $KL$ из точки $K$ в точку $L$. При этом поднимемся на 80 единиц. Это соответствует тому, что станок треугольного типа должен изготовить 80 вторых деталей. Далее сделаем шаг из точки $N$ в точку $M$. При этом мы сдивимся вправо на 60 единиц. Это

13

соответствует тому, что станки второго типа должны работать лишь над первыми деталями и сделать их 60 штук.

А теперь мы движемся от $L$ к $A$ и от $M$ к $A$. Это соответствует тому, что первый станки работают $2^2/3$ из общих трех единиц времени над первой деталью (и мы сдигаемся впраvo на $26^2/3$) и $1/3$ времени над второй деталью (и мы поднимаемся вверх на $6^2/3$). В итоге мы попадаем в точку $A$.

Кстати, становится ясно, как надо поступать, если у нас не три, а $n$ типов станков. Тогда множество $n$ будет ограниченоломанной из $C$ звеньев, углы наклона которых будут упорядочены от нижней точки к верхней в порядке убывания. И снова надо идти от верхней и нижней точек навстречу друг другу. Все типы станков, кроме одного, будут обработать лишь одну деталь — «верхние» — первую, «низние» — вторую. И лишь на последнем участке одному типу станков придется «поделиться» — часть времени обработать первую, часть — вторую деталь.

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

Формализовав производенный задачу и указав некоторые решения, Л. В. Канторович увидел также замечательные перспективы в области экономики. Представьте себя на месте мастер, у которого в подчинении находится семь рабочих. Они работают на тех самых станках, с которых мы уже не раз встречались. Вы должны организовать производство так, чтобы изготовить как можно большие комплектов деталей.

Один путь — директивный. Мастер вызывает бригаду и строит головом распоряжается: «Ты, Петр, давай делай вторую деталь на станке третього типа; Иван, Николай и Александр — делайте первую деталь на станке первого типа» и так далее.

Но есть и другой путь, более деликатный. Вы можете вызывать бригаду и сказать так: «Ребята, нужно сделать на ваших станках детали двух видов. Первая стоит 2 рублей, а вторая — 1 рублей; за каждый комплект из деталей двух видов — премия по 10 копеек. Подумайте, как вам заработать побольшие».

Возможно, сначала рабочим в голову придет варант, называемый в нашей таблице «естественным распределением». При этом они заработают 238 рублей 70 копеек. Но потом они,

14

наверное, договорая, что есть и более выгодное — «оптимальное распределение».

Вопрос: Какую наиболее сумму может заработать бригада?

А откуда же взялись цены на детали? Посмотрите на рисунок 4. Прямая LM, на которой лежит оптимальная точка A, имеет уравнение 2a+b=260. Его коэффициенты 2 и 1 — это и есть цены. Если бы не премия за комплектность, то при ценах на детали в 2 и 1 рублей набольший заработок бригады отвецал бы любой из точек отрезка ML. А небольшая премия в 10 копеек делает наиболье выгодной именно точку A. Таково искусство правильного выбора цен!

Но вернемся в 1939 год. Говорят, что истина роздается ересью… Увы, так случайность и с идеями Л. В. Канторовича в области экономики. Они не встретили понятия в момент их зарождания, были объявлены ересью, и его работа была превращена.

Концепции Леонида Витальевича вскоре после конца войны были переоткрыты на Западе. Американский экономист T. Купманс в течение многих лет привлекал внимание математиков к ряду задач, связанных с военной тематикой. Он активно способствовал тому, чтобы был формирован математический коллектив для разработки этих проблем. В итоге было осознано, что надо научиться решать задачи о нахождения экстремумов линейных функций на многогранниках, задаваемых линейными неравенствами. По предложению Купманса этот раздел математики получил название линейного программирования.

Американский математик Д. Данцгг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название сумплекс-метода). Идей линейного программирования в течение пяты-шести лет получили градинозное распространение в мире, и именно Купманса и Данцгг стали повсюду широкого известны.

Примерно в это время Купманс узнал, что еще до войны в далекой России уже было сделано нечто по-

хожее на разработку начал линейного программирования. Как легко было Данцгг и Купмансу проигнорировать эту информацию! Маленькая книжца, изданная ничтожным трахом, обращенная даже не к экономистам, а к организаторам производства, с минимумом математики, без четко описанных алгоритмов, без доказательных теorem — словом, стоит ли принять такую книжку во внимание… Но Купманс настоявает на переводе и издании на Западе книги Канторовича. Его имя и идеи становятся известными всем. Воздадим должное благородство американского ученого!

А самому Леониду Витальевич — как естественное было бы ему, испытав первыеrozные ударыретоградов, отречься от «грехов» своей молодости, забиты про всю эту экономику и вернуть к математике. Но Л. В. Канторович продолжает писать математические работы, наявные экономические идеями, участует и в конкретих разработках на производстве. При этом (одновременно с Данцггом, но не зная его работ) он разработывает метод, позже названный модифицированным симплеекс-методом. Как только в 50-е годы образуется маленький просвет и кое-что из запретного ранее становится возможным, он организует группу студентов на экономическом факультете ЛГУ для обучения методом оптимального планирования. А начинается 1960 года, Леонид Витальевич занимается только экономикой и связанным с него математическим проблемами. Его включает в эти области был отечелен Ленинской премией в 1965 году (присудена ему совместно с В. С. Немчиновым и В. В. Новожиловым) и, как уже говорилось, Нобелевской премией в 1975 году.