Переходя к вычислительным методам, следует указать, что главный момент в методе Канторовича в 1939 г. — введение некоторых переменных, названных «разре­шающими множителями», с интерпретацией, аналогичной множителям Лагранжа в классических задачах определения экстремума. Это, однако, нечто гораздо боль­шее, чем тривиальная модификация классического анализа, поскольку линейность и ограничения в виде неравенств выдвигают совершенно новые математические проблемы. Канторович показал, что если значения этих множителей известны для некоторой задачи, то значения первоначальных неизвестных — переменных, кото­рые характеризуют производственные, транспортные планы и т. п. в натуральных единицах — можно найти сравнительно просто. Как правило, число таких мно­жителей будет намного меньше числа переменных, характеризующих физический план. Поэтому многообещающим должен быть подход, состоящий в попытке най­ти значения этих множителей как средства нахождения неизвестных переменных, описывающих оптимальный план в натуральных показателях. Для этой цели Канторович разработал метод пошаговой аппроксимации (итеративный метод). Начи­нают с задания предварительных оценок множителей и вычисляют, каким должен быть соответствующий физический план. Затем проверяют, удовлетворяет ли фи­зический план всем ограничениям (уравнениям и неравенствам). В той мере, в какой наблюдаются расхождения, множители корректируются. Проводятся новые расчеты соответствующих физических планов и новые испытания выполнения или нарушения ограничений и т. д. Если расхождения используются надлежащим спо­собом как индикаторы того, как следует корректировать множители, то такой по­шаговый подход даст в конце оптимальный план или очень хорошее приближение к нему.

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

Этот метод имеет определенную слабость с алгоритмической точки зрения, особенно в связи с программированием для современных ЭВМ (конечно, это сооб­ражение более уместно в настоящее время, чем в 1939 г.). В оригинальной работе Канторовича метод был сформулирован таким образом, что на некоторых шагах требовались специальные проверки и решение на основе суждения, т. е. метод не был полностью механическим и требовал дальнейших уточнений. С этой точки зрения метод, позднее разработанный Данцигом (симплекс-метод), более полон и легче программируется для ЭВМ. В соответствии с этим именно данный метод, а не первоначально предложенный Канторовичем, стал стандартным методом реше­ния задач линейного программирования. (Существует множество его вариантов, ориентирующихся на использование особенностей ЭВМ или на задачи со специаль­ной структурой.) Два эти различных метода обладают определенным сходством в том, что они — итеративные методы, в которых приближение к правильному реше­нию идет последовательными шагами, и в обоих множители типа Лагранжа играют важную роль. В обоих методах такие множители используются для описания оп­тимума. Вероятно, можно сказать, что в шагах, ведущих к оптимуму, эти множители играют более заметную роль в методе Канторовича, чем в симплекс-методе, поскольку изменения, которые делаются на каждом шаге по методу Канторови­ча, включают в первую очередь корректировку множителей, за которой следует корректировка переменных, характеризующих план в натуральных показателях, тогда как в симплекс-методе на каждом шаге сначала корректируют переменные, характеризующие план, а затем производят соответствующую корректировку мно­жителей. Выше изложены только очень грубые и неопределенные соображения, но рассмотрение технических подробностей выходит за рамки настоящей работы. Однако этот момент представляет некоторый интерес в связи с рядом дальнейших заключений относительно организации планирования и управления, которые Кан­торович выводит из своего анализа линейного программирования. Мы коснемся этого позднее в настоящей статье.

Я видел ссылки на дальнейшие разработки метода Канторовича, выполнен­ные как самим Канторовичем, так и другими русскими математиками, в других довольно ранних изданиях, но эти работы были недоступны для меня.

В западной литературе обсуждался вопрос о вкладе Канторовича в методы вычислений, сделанном в его первой работе. Данциг указывает [6, с. 22-23], что объяснение, данное Канторовичем, как корректировать множители — неполно, и что это — сложная проблема. Это является главным моментом в критическом рассмотрении метода Канторовича у Чарнса и Купера [4]. Я думаю, что моя ха­рактеристика и сравнение, приведенные выше, дают приблизительно верное пред­ставление.

Интересно также рассмотреть некоторые соображения Чарнса и Купера [4]. В заключительном параграфе они отмечают, что Канторович и другие русские математики работали с вычислительными методами, предназначенными для спе­циальных структур в пределах класса задач линейного программирования, и что позднее это стало очень важной областью западных исследований по математиче­скому программированию. Цитирую их заключения:

Хотя западные исследования по линейному программированию, по-видимому, привели к разработ­ке более эффективных алгоритмов, тем не менее в соответствии с вышеизложенным возможно, что эти ранние методы, предложенные Канторовичем, но которые, кажется, никогда полностью не были доработаны2), содержат идеи, которые все еще могут оказаться весьма важными.