ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2011, том 47, № 4, с. 37-43
К СТОЛЕТИЮ СО ДНЯ РОЖДЕНИЯ ЛЕОНИДА ВИТАЛЬЕВИЧА КАНТОРОВИЧА
ЗАДАЧА РАЦИОНАЛЬНОГО РАСКРОЯ В РАБОТАХ Л.В. КАНТОРОВИЧА И В.А. ЗАЛГАЛЛЕРА
© 2011 г. И.В. Романовский
(Санкт-Петербург)
ВВЕДЕНИЕ
Я хочу рассказать о замечательной книге Л.В. Канторовича и В.А. Залгаллера, которая была дважды опубликована - в 1951 г. под названием "Расчет рационального раскроя промышленных материалов" (Канторович, Залгаллер, 1951), а в 1971 г. под названием "Рациональный раскрой промышленных материалов" (Канторович, Залгаллер, 1971) - вызвала огромные последствия, часто цитируется в списках литературы и... никем сейчас не читается ввиду малой доступности. Отмечу, что книга практически неизвестна за рубежом. Все это несмотря на довольно значительный тираж - 5000 экз. первого издания и 4600 второго.
Книга важна как исторический документ, фиксирующий ход первого практического применения математико-экономических идей Л.В. Канторовича, начатый с простейших моделей и доведенный до практически использованных планов раскроя. В ней хорошо показано, как, по рекомендациям Л.В. Канторовича, на реальных задачах двойственные оценки (индексы) применяются вне рамок математической модели - для принятия решений при небольших изменениях исходных данных. Книга зафиксировала использование до 1950 г. таких важных математических инструментов, как метод последовательного улучшения плана, генерирование столбцов (раскроев), применение таблиц индексов в технике, известной сейчас как "динамическое программирование".
Готовясь к празднованию столетия со дня рождения Л.В. Канторовича, мы решили эту книгу переиздать. В.А. Залгаллер согласился с нашим предложением и принимает участие в переиздании.
В данной статье будет рассказано об истории книги, о достоинствах первого, а затем и второго издания, о развитии работ по оптимальному раскрою в СССР и в постперестроечной России, и в конце немного о плане третьего издания.
ИСТОРИЯ КНИГИ
Начнем с того, что во время войны Л.В. Канторович был на военной службе - он работал в Высшем инженерно-техническом училище, где преподавал военным строителям. В частности, он читал лекции по теории вероятностей и написал интересный учебник по этой дисциплине, изобилующий военными примерами в стиле "исследования операций".
В это время он работал над начатой еще до войны книгой, которая называлась тогда "Экономический расчет, обеспечивающий наиболее целесообразное использование ресурсов". В 1959 г. она была опубликована Издательством АН СССР (Канторович, 1959).
Подполковник Канторович был демобилизован из Советской армии в 1948 г. и возглавил в Ленинградском отделении Математического института АН СССР специальный Отдел приближенных вычислений, выполнявший расчеты, связанные с Атомным проектом (Атомный проект СССР, 1999).
Канторович взял в этот отдел выпускника математико-механического факультета (матмеха) Ленинградского университета В.А. Залгаллера (известного ему по литературной работе еще с
довоенных времен1) и... направил его на Вагоностроительный завод им. Егорова для практической проверки того, насколько удастся приложить экономические идеи Канторовича в реальных условиях - в раскрое материалов, используемых при изготовлении вагонов2.
Для Канторовича тема раскроя была не новой. В 1942 г. он опубликовал небольшую заметку в специальном издании Наркомата (министерства) боеприпасов (Канторович, 1942), а в 1949 г. давно написанную статью об оптимальном пилении бревен на доски (Канторович, 1949) - возможность публикаций представилась ему в связи с получением в 1949 г. Сталинской премии3.
Виктор Абрамович Залгаллер начал учиться на матмехе перед войной, всю войну провел в армии, после Победы демобилизовался, вернулся на матмех и в 1948 г. закончил его по кафедре геометрии с красным дипломом. С задачами раскроя и с довоенными работами Канторовича по линейному программированию он до этого поручения знаком не был. Да и сам этот термин Дж. Данциг еще только выбирал.
Поручение было выполнено. В.А. Залгаллер отобрал те из многообразных практических ситуаций раскроя, которые легче всего укладывались в схему Канторовича (их было достаточно много, и они были важны для производства), собрал данные и стал решать задачи оптимизации, создавая при этом методики расчетов. Попутно он занимался "научной организацией труда" раскройщиков, учил их приемам рациональной работы, совершенствовал оборудование их рабочих мест.
Найденные раскройные планы были внедрены. Они принесли заводу ощутимую экономию материалов и неожиданный выговор дирекции за срыв плана сдачи отходов. Этот опыт был также полезен. Он показал, что нелогично построенная система препятствует локальным попыткам рационального хозяйствования, даже если эти попытки ничем системе не угрожают.
Меньше чем через два года к печати была подписана книга (Канторович, Залгаллер, 1951). В ней описывались (впервые) задачи линейного программирования, к которым приводятся базовые модели массового раскроя, в терминах специальных индексов формулировались условия оптимальности раскроев (конечно, это были двойственные переменные, но двойственных задач Канторович не писал, в его терминологии это были разрешающие множители; прямая задача в форме Канторовича ставилась для задач раскроя очень удобно - как задача о максимальном выпуске комплектов деталей или, эквивалентно, как задача о минимальном использовании сырья на один комплект).
В книге рассмотрены модель одномерных заготовок с сырьем фиксированного размера, модель со случайной смесью исходных размеров, задача двумерного плоского гильотинного раскроя прямоугольников из прямоугольного сырья и некоторые задачи фигурного раскроя.
Методы расчета излагались в терминах решения систем линейных уравнений. Ничего, подобного симплекс-таблице Дж. Данцига (Данциг, 1966), у них не было и быть не могло, так что все вычисления В.А. Залгаллер проводил карандашом на бумаге. Но это обстоятельство обеспечивало вычислительную свободу, и уже тогда авторы увидели, что можно на каждой итерации вычислять наилучший раскрой для включения его в базисное решение. Говоря современным языком, это был метод генерирования столбцов с использованием для вычислений шкалы индексов, показывающей зависимость оценки сырья от его длины, того, что примерно через десять лет мы стали называть функцией Беллмана.
Авторы описали работу с двумерной шкалой индексов, также фактически с уравнением Белл-мана, и привели пример расчета, выполненного вручную. Но работа со шкалой для двумерного случая была слишком громоздка для ручного счета и не рекомендовалась. В.А. Залгаллер разработал много рекомендаций по порядку проведения вычислений. С одной из них мы ознакоми-
1 Студент Залгаллер по поручению лектора Канторовича преобразовал сжатый конспект его курса в полноценную книгу, которая была издана (с указанием на эту помощь).
2 Залгаллер вспоминал: "Вера Николаевна Фаддеева говорила о Леониде Витальевиче, что он чувствовал себя не в своей тарелке, если варит каши меньше, чем в пятидесяти котлах. У него ведь систематически шли работы в самых разных направлениях" (см. (Леонид Витальевич Канторович, 2002, с. 169)).
3 Тогда же была напечатана и написанная еще до войны статья с М.К. Гавуриным (Канторович, Гавурин, 1949) о транспортной задаче на сети с подробным изложением метода потенциалов.
лись особо, когда он оппонировал у нас диссертацию по программам раскроя и объяснил нам, на каких принципах нужно строить в ней начальный базисный план. Мы эти принципы немедленно включили в программу и с тех пор обязательно используем.
Очень интересен в книге раздел о круговых заготовках. Только сейчас, перечитывая книгу в связи с подготовкой к переизданию, я обратил внимание на упоминание участия в этой работе "сотрудника Кировского завода Г.Ш. Рубинштейна"4. Этот раздел, по-моему, был включен как дань истинной математической привязанности В.А. Залгаллера и Г.Ш. Рубинштейна - геометрии.
Книга показала способы, которыми можно совершенствовать раскрой материалов. Наряду с математическими моделями и очень простыми средствами их расчета она включала разнообразные практические рекомендации по расчету и раскрою. Например, в ней рекомендуется, казалось бы, совсем непрограммистское использование кальки при графическом решении уравнения Беллмана. Между тем аналог этому приему можно найти, например, во вполне компьютерном методе Дейкстры для нахождения кратчайших путей в графах. В первой отечественной компьютерной программе по раскрою (Булавский, Яковлева, 1961) использовался именно этот прием. Другой прием - особенности вычисления индексов при значительном преобладании нескольких заготовок программного воплощения - я еще не нашел.
При раскрое материалов смешанных длин рассматривается вопрос об экономической целесообразности заказа мерных длин5, даются рекомендации по организации предварительной сортировки поступающих единиц сырья и предлагается простой и эффективный сортировочный стеллаж.
Была предложена и построена специальная сменная линейка, которая градуировалась так, чтобы рабочий мог быстро принимать правильные решения по раскрою.
В книге есть несколько приложений, написанных В.А. Залгаллером. Л.В. Канторович особенно ценил Приложение I, в котором приводится доказательство существования индексов, связанных с максимально экономным планом раскроев, - на современном языке это условие оптимальности решения в данной конкретной задаче линейного программирования.
Но самым важным было широкое использование индексов, возникающих в задаче линейного программирования, при принятии внемодельных решений, то, к чему призывал Л.В. Канторович в своей книге (Канторович, 1959) (В.А. Залгаллер читал ее еще в рукописи).
ПОСЛЕ КНИГИ
Примечательно, что после эксперимента на Вагоностроительном заводе В.А. Залгаллер сохранил интерес к задачам раскроя.
По-видимому, самым важным из приложений была задача "о поставах". Поставом называется расстановка пил при распиловке древесного ствола на доски. Как вспоминает Виктор Абрамович (Залгаллер, 2011), заняться этой задачей ем
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.