Как теперь хорошо известно, линейное программирование — метод определе­ния максимума или минимума линейной функции множества переменных, подчи­ненных ограничениям в форме линейных уравнений, требованиям неотрицательно­сти и, возможно, более общим линейным неравенствам. Развитие линейного про­граммирования включает три аспекта:

1. Формулировка проблемы и демонстрация того, что обширная область опти­мизационных проблем в экономике может быть приведена к данной форме непо­средственно или после некоторых преобразований.
2. Разработка вычислительных методов и алгоритмов для практического ре­шения подобных проблем.
3. Прояснение теоретических аспектов и следствий.

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

Развитие линейного программирования оказывало большое влияние на разви­тие экономических исследований в течение последних 25 лет, и, несомненно, будет играть центральную роль также и в будущем. С одной стороны, было осознано, что широкую область практических проблем можно сформулировать как задачи линейного программирования, а поскольку были разработаны алгоритмы, которые делают возможным решение таких задач даже очень больших размеров (как и по числу переменных, так и по числу условий), линейное программирование откры­ло путь к практическому выполнению расчетов, направленных на оптимизацию использования ресурсов в самых разных областях.

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

Общепринятая история развития линейного программирования гласила, что первые шаги были сделаны группой математиков и экономистов, работавших над проблемой распределения ресурсов для ВВС США во время Второй мировой вой­ны. Членом этой группы был Дж. Данциг. Он сформулировал общую задачу линейного программирования и разработал метод ее решения в 1947 г. (симплекс- метод). Его работа была представлена в виде лекций, прочитанных в разных ме­стах, распространялся также предварительный отчет, но до 1951 г. она не была опубликована. В тот год она была включена в работу [1]. В этот том вошли также и многие другие работы по теории линейного программирования. С точки зрения экономической теории особое место занимает работа Т. Купманса.

С тех пор теория линейного программирования развивалась во многих направ­лениях: были составлены новые алгоритмы, особенно с использованием специаль­ных структур; мы знаем о большом числе важных и ценных практических прило­жений; были дальше развиты и теоретические вопросы. Что касается последних, то чрезвычайно стимулирующее значение имела книга Дорфмана, Самуэльсона и Солоу [2], помимо упомянутой работы Купманса.

Конечно, можно найти предшественников линейного программирования. Ра­боты Дж. фон Неймана по теории игр и его ранняя модель экономического роста содержат элементы, которые до некоторой степени предвосхищают линейное про­граммирование. В работах Р. Фриша 1930-х годов также можно найти идеи и ма­тематические методы, которые были некоторыми шагами в направлении линейного программирования. В работе 1941 г. Ф. Хичкок сформулировал и решил оптими­зационную транспортную задачу, которая является специальным случаем задачи линейного программирования, и независимо от него сходную задачу решил Т. Купманс в 1947 г. Были и другие, менее известные математики и экономисты, которые формулировали задачи и разрабатывали аналитические средства, предвосхищав­шие некоторые элементы линейного программирования. Однако ни один из этих предшественников не дал общей трактовки, которая охватывала бы все три выше­упомянутые аспекта, и, по-видимому, ни один из них не видел общего значения теории линейно-программного типа.

Вышеизложенное в большей или меньшей мере было общепризнанной исто­рией развития линейного программирования до тех пор, пока не стало широко из­вестным, что Л. В. Канторович еще в 1939 г. построил математическую модель «организации и планирования производства», которая по существу была линейно­программной моделью, внеся вклад во все три направления, перечисленные в на­чале раздела. Работа Канторовича 1939 г. стала известна и доступна коллегам из западных стран в 1960 г., когда в журнале «Management Science» появился ан­глийский перевод этой работы [а]. Инициатива этого перевода и публикации принадлежала Т. Купмансу, который до конца прояснил некоторые невнятные ссылки на работы Канторовича, относящиеся к транспортной задаче, и наладил контакт с ним. (Упомянутая работа Канторовича была опубликована также в другом английском переводе [b] на основе позднейшего русского издания. В целом, публикация в «Management Science» представляется лучшей.)