Авторефераты по всем темам >>
Авторефераты по истории
На правах рукописи
Андрианов Александр Львович
ЗАРОЖДЕНИЕ И РАННЯЯ ИСТОРИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Специальность 07.00.10 - История наук
и и техники
АВТОРЕФЕРАТ
диссертации на соискание учёной степени кандидата физико-математических наук Москва - 2012
Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте истории естествознания и техники им. С.И. Вавилова РАН.
Научный консультант: доктор физико-математических наук, Демидов Сергей Сергеевич
Официальные оппоненты: Тихомиров Владимир Михайлович, доктор физико-математических наук, профессор, Московский государственный университет имени М.В. Ломоносова, профессор кафедры оптимальных проблем управления механико-математического факультета;
Александрова Надежда Вячеславовна, кандидат физико-математических наук, доцент, Московский авиационный институт, доцент кафедры 803 дифференциальные уравнения
Ведущая организация: Российский государственный гуманитарный университет
Защита состоится 10 мая 2012 г. в 16:00 часов на заседании диссертационного совета Д 002.051.05 при Федеральном государственном бюджетном учреждении науки Институте истории естествознания и техники им. С.И. Вавилова РАН по адресу: 117861, Россия, г.
Москва, ул. Обручева, д. 30а, корпус В.
С диссертацией можно ознакомиться в Отделе истории физико-математических наук или Дирекции Федерального государственного бюджетного учреждения науки Институте истории естествознания и техники им. С.И. Вавилова РАН.
Автореферат разослан л_____ апреля 2012 г.
Ученый секретарь диссертационного совета, кандидат физико-математических наук И. О. Лютер
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Представленная работа содержит результаты историко-научного исследования возникновения и развития линейного программирования (ЛП) в 30-ых - 50-ых годах XX века, а также влияния этого процесса на теоретические и прикладные разработки того времени. Главное внимание уделено научной деятельности первооткрывателя ЛП Л. В.
Канторовича, работам его коллег, учеников и соавторов, а также деятельности основателя ЛП на Западе Дж. Б. Данцига и его коллег.
Исследования выполнены в Институте истории естествознания и техники им. С. И.
Вавилова РАН в 2006Ц2012 г.
Актуальность работы. Зарождение и развитие новых областей математической науки представляет собой одну из важнейших и интереснейших проблем истории математики. ЛП стало принципиально новой областью математической науки, получившей широкие применения и оказавшей огромное влияние как на развитие экономической науки, так и самой математики. Однако историко-математическое осмысление этого феномена по существу ещё не начиналось. Предпосылки возникновения ЛП в различных странах, в рамках разных школ и традиций, влияние на эти процессы особенностей политической, социальной и экономической среды, в контексте которой приходилось работать его авторам, практически не изучены. Не стали объектом исторического анализа и взаимосвязи исследований отдельных авторов, имевших непосредственное отношение к данной области, связи их работ с другими работами по экономической математике, а также с работами в других областях математики. Всё это приводит к недостаточно объективной оценке вклада отдельных учёных, отсутствию понимания их идейного взаимовлияния, и в итоге не позволяет воссоздать адекватную картину исторического процесса развития ЛП в целом, во всём многообразии внутренних взаимосвязей и связей со смежными областями.
Объектом диссертационного исследования является история возникновения и последующего становления и развития ЛП. Предметом диссертационного исследования являются работы математиков СССР и США - Канторовича, Данцига, Дж. фон Неймана и некоторых других, связанные с областью ЛП.
Целью работы является анализ специфики появления работ, связанных с областью ЛП, в научной деятельности разных авторов в разные годы, внутренних связей между этими работами и связей этих работ с исследованиями в смежных областях, изучение путей их восприятия научным сообществом и того исторического и научного контекста, в котором эти работы возникали, особенностей предыдущей научной деятельности их авторов, их взглядов на развитие математики, экономики и науки в целом, а также на актуальность и принципы выбора тем научных исследований. В связи с поставленной целью решаются следующие задачи: выделение определяющих факторов, инициировавших развитие в эти годы исследований по ЛП; анализ основных проблем и направлений исследований в рассматриваемый период, а также важнейших результатов, полученных главными действующими лицами, связанными с этой областью исследований; выявление причин того, что именно эти авторы и именно в этот исторический момент в своей исследовательской деятельности обратились к данной теме; выделение специфических особенностей, присущих деятельности каждого из них в силу различных (экономических, политических, и др.) причин; изучение взаимосвязей между работами этих авторов, а также их зависимости от их предшествующей научной деятельности; анализ деятельности авторов наиболее важных результатов по организации исследований и внедрению полученных достижений в практику, по выбору проблематики дальнейших исследований и руководству ими.
Особое внимание уделяется творческой деятельности Канторовича и Данцига - поиску ими проблематики, их роли организаторов, руководителей и общественных деятелей, борьбе за признание и продвижение собственных результатов, а также связям Данцига с другими учеными, прежде всего с Т. Ч. Купмансом и фон Нейманом, работавшими в близких областях и оказавшими значительное влияние как на его деятельность, так и на развитие области ЛП в целом; анализу наиболее значительных работ этих авторов, выявлению значения результатов, полученных ими, а также другими учеными (Купмансом, фон Нейманом, Ф. Л. Хичкоком и др.), имеющими непосредственное отношение к ЛП.
Методы исследования. Для решения поставленных задач комбинировались методы историко-научного анализа трудов Канторовича, Данцига, фон Неймана и некоторых других авторов 30Ц50-ых годов XX века в контексте современной им математики (антикваристский подход) и с позиций математики сегодняшнего дня (презентистский подход).
Научная новизна работы. Впервые в историко-научной литературе было проведено систематическое исследование процесса возникновения и развития ЛП - тех предпосылок, которые определили зарождение интереса к проблематике и само начало исследований и способствовали выработке методов исследования, основных путей развития теории в СССР и США в 30Ц50-ых годах XX века. Дан сравнительный анализ исследований в этой области Канторовича, с одной стороны, и американских авторов (Данцига, Купманса и фон Неймана), с другой.
Практическая ценность исследования. Результаты проведённого исследования могут быть использованы, во-первых, в обязательных и специальных курсах по ЛП и его истории, а также по истории математики, читаемых в высших учебных заведениях студентам математических и экономических специальностей, во-вторых, в дальнейших исследованиях по истории математики и математических методов в экономике.
На защиту выносятся следующие положения:
1. Общими предпосылками возникновения и успешного развития ЛП, его основных понятий, задач и методов их исследования, как в СССР, так и на Западе послужили:
Ц острая необходимость и инициированный ею со стороны соответствующих организаций запрос на решение определённого круга прикладных задач;
Ц атмосфера, установившаяся в мире в преддверии Второй мировой войны и лишь усугубившаяся в её ходе, а также на протяжении войны Холодной, оказавшая большое влияние на взгляды и приоритеты, определившие выбор тематики научных исследований создателями ЛП, подкреплённая необходимостью решения задач оборонного характера;
Ц традиции научной деятельности и творческих принципов ПетербургскойЦ Ленинградской математической школы, ярким представителем которой явился Канторович, для которой характерна практическая направленность исследований, базирующихся на мощном теоретическом фундаменте;
Ц мировоззрение и опирающиеся на него приоритеты и интересы Канторовича и Данцига, определявшие их выбор тем и методов исследований;
Ц предшествовавшая профессиональная карьера и имевшиеся на тот момент должностные связи и обязанности основных авторов - Канторовича и Данцига.
2. Причинами, приведшими Канторовича, Данцига и фон Неймана к задачам ЛП и способствовавшими дальнейшим их успехам в разработке этой дисциплины стали:
Ц наличие у Канторовича, Данцига и фон Неймана богатого опыта и идей, приобретенных в процессе предыдущей научной деятельности, которые непосредственно подсказали пути, на которых будет найден метод для успешного решения задачи ЛП;
Ц проявленная Данцигом способность быстро образовать круг единомышленников, поддержавших его идеи и внесших значительный вклад в их развитие и доработку;
Ц интересы влиятельных правительственных и деловых кругов, позволившие Данцигу получить сильную финансовую и административную поддержку для развития, внедрения и продвижения разрабатываемых им методов;
Ц поддержка работ по ЛП Канторовича крупнейшими советскими математиками, позволившая продолжать исследования в этой области несмотря на неоднозначную реакцию к этому направлению со стороны влиятельных кругов научного сообщества (в особенности представителей экономической науки) и не простую политическую обстановку.
3. Крупные достижения, полученные в области ЛП, были обусловлены:
Ц широким кругозором, опытом и выдающимся талантом Канторовича и Данцига;
Ц их выдающимися организаторскими способностями;
Ц активным использованием теоретических результатов в приложениях;
Ц начавшимся бурным развитием вычислительной техники и разработкой соответствующих математических методов моделирования и решения прикладных задач.
4. История создания и развития ЛП предлагает замечательный пример того как методы, порожденные по запросу одной науки (экономики), в рамках другой науки (математики) смогли оказать значительное влияние не только на первую (экономику), но и на последнюю (математику), примером чему служит полное решение проблемы Г. Монжа, полученное Канторовичем на основе открытых им ранее методов ЛП.
Апробация результатов. Основные результаты доложены на Годичных научных конференциях Института истории естествознания и техники им. С. И. Вавилова РАН, проходивших в 2007, 2008, 2009, 2010, 2011 годах; на Общемосковском научноисследовательском семинаре по истории и методологии математики и механики механикоматематического факультета МГУ им. М. В. Ломоносова в марте 2009 и 2010 годов, апреле 2011 года и марте 2012 года; на заседание сектора истории математики Института истории естествознания и техники им. С. И. Вавилова РАН 20 октября 2009; а также на VIII Международном Конгрессе по математическому анализу ISAAC 22 - 27 августа 2011 года в Москве.
Публикации: результаты диссертации опубликованы в 6 работах, в том числе в одной статье в издании, включённом в перечень ВАК, а также в тезисах VIII Международного Конгресса по математическому анализу ISAAC 22 - 27 августа 2011 г. в Москве.
Структура и объём работы. Диссертация состоит из введения, пяти глав, заключения и библиографии.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается новизна и актуальность выбранной темы, определяются цели и задачи, которые ставил перед собой исследователь, характеризуются использованные методы исследования, формулируются основные результаты диссертации, обсуждаются возможности их использования, дано краткое содержание работы.
Глава 1. Предыстория линейного программирования 1.1. Идеи Л. В. Канторовича в контексте экономических исследований советских ученых первой половины ХХ в. Задолго до того, как Канторович начал проводить свои научные изыскания в области экономики, в СССР уже существовал опыт проб применения методов математического и статистического анализа для решения задач экономики: такие исследования стали предприниматься уже в 20-ые годы XX века.
Среди этих работ необходимо отметить труды Е. Е. Слуцкого и А. А. Конюса, в которых ученые изучали модели потребления. Г. А. Фельдман работал над моделями роста, Н. Д. Кондратьев - над длинными циклами, в ЦСУ СССР были выполнены работы по шахматному балансовому анализу экономики. Позже это направление получило дальнейшее развитее, было математизировано и усовершенствовано В. В. Леонтьевым с широким использованием сведений и материалов экономики США. В тот же временной период Л.
Юшков выдвинул идею оптимального подхода к понятию норматива эффективности, впоследствии получившую плодотворное развитие в творчестве В. В. Новожилова.
Особое внимание уделено анализу достижений отдельных ученых, оказавших большое влияние на внедрение математических идей в область экономической науки.
Несмотря на то, что проведенные исследования, безусловно, не могут полностью охватить всё разнообразие достижений и методов рассматриваемого периода в данной области, они призваны дать правильное представление относительно особенностей того научного контекста, в рамках которого происходили последующие исследования Канторовича.
1.2. Математические предпосылки возникновения линейного программирования. Несмотря на то, что открытие ЛП и методов решения его задач связываются в первую очередь с именами таких ученых как Канторович, Купманс и Данциг, они не были первыми, кто занимался этими вопросами. И хотя, насколько известно, они не были знакомы с исследованиями своих предшественников, последние представляют большой интерес с точки зрения истории развития математики, связанной с этим вопросом.
Также необходимо заметить: как исследования, относящиеся непосредственно к ЛП, так и работы, изучающие полиэдры и линейные неравенства сами по себе, - все их можно считать имеющими прямое отношение к интересующему нас предмету в силу того, что эти три области являются ни чем иным, как взглядами с разных сторон (со стороны оптимизации, геометрии и алгебры, соответственно) на одни и те же вопросы. В силу этого в качестве предыстории ЛП рассматриваются важнейшие результаты во всех этих областях, родственная природа которых была замечена еще Ж. Б. Фурье.
Вероятно, то, что именно работа Данцига смогла стать тем решающим моментом, после которого ЛП получило широкое признание, а созданный им симплекс метод (СМ) приобрел огромную популярность, произошло благодаря прозрачности предложенной геометрической иллюстрации (ученый сказал, что, когда мы рассматриваем полиэдральное множество допустимых решений задачи ЛП, СМ является алгоритмом перехода от одной вершины выпуклого многогранника к новой, в результате которого мы приходим к вершине, означающей решение поставленной задачи) и тому, что направленный перебор вершин был заключен в форму достаточно удобного для осуществления алгоритма.
Фурье в 1826 году рассмотрел проблему отыскания для матрицы A из m строк и n столбцов и m-мерного вектора b минимума ||Ax - b||, где ||x||=max{|x1|, |x2|, Е, |xn|}. Приведя для случая m = 2 ход решения в виде описания перемещения по точкам чаши, как ученый ее называет, к ее низу (что можно назвать упрощенным вариантом будущего СМ), Фурье упомянул о возможности дальнейшего исследования при большей размерности выпуклой кусочно-линейной поверхности.
Если же говорить о многомерных задачах оптимизации ||Ax - b||, то начиная с конца XVIII века ученые обращались к их изучению в связи с вопросами теоретической механики и отысканием методов решения систем линейных неравенств. Более того, можно сказать, что ученые (Ж. Лагранж, Фурье, К. Гаусс, М. В. Остроградский) всерьез занялись изучением самих линейных неравенств, размышляя над вопросами, связанными с принципом виртуальных скоростей и теорией Лагранжа.
Важное место в вопросе о появлении идей, на которые опирается СМ, занимают исследования, связанные с чебышевским приближением, а именно, - с нахождением точки, наименее уклоняющейся по модулю от системы плоскостей (такая точка называется чебышевской). Данная задача эквивалентна задаче ЛП определенного вида.
Геометрическая теория полиэдров получила свое бурное продвижение в 19-м веке (О.
Коши, Я. Штейнер, Дж. Сильвестр, А. Кэли, А. Мебиус, Т. Кирман, А. Пуанкаре, Л. Шлефли, А. Тет).
Что касается двойственности и полярности, то основные представления о них начали появляться в результате исследований 1820Ц1830-ых годов Ж. Жергонна, Ж. В. Понселе и К.
Г. Х. фон Штаудта о двойственности вершин и фасет в политопах, а также о полиэдрах и выпуклых телах с использованием полярности. Что касается самой концепции двойственности в геометрии, то она развивалась в работах Понселе, Жергонна, Я. Штейнера и фон Штаудта и Ю. Плюккера.
Ближе к концу XIX века исследованием линейных неравенств занялись Г.
Минковский и Ю. Фаркаш, развивших в своих работах алгебраический подход к теории полиэдров.
Из утверждений, явно сформулированных в работах Фаркаша, принимая во внимание принцип двойственности, тут же следует утверждение (1935 г. Г. Вейль) о том, что любой конечно порожденный конус является полиэдральным.
В исследованиях Вейля, Минковского и Г. Ф. Вороного удалось определить, каким образом связаны друг с другом многогранники и полиэдры.
Работая над задачами теории чисел, Минковский пришел к изучению линейных неравенств и выпуклых тел и к 1896 году показал, что любой полиэдральный конус {x | Ax 0} конечно порожден; если матрица A имеет полный ранг по столбцам, то этот конус порожден лучами, каждый из которых определяется (n - 1) линейно независимыми уравнениями из Ax = 0. Из чего он, предполагая полный ранг A по столбцам, получил лемму Фаркаша. Из хода доказательства видно, что он знал о двойственности лучей и неравенств и о возможности приведения неоднородного случая к однородному.
Изучение вопросов тории чисел привело Вороного к исследованию в его работах свойств многогранников посредством решения конечной системы линейных неравенств.
Кроме выведения результатов Гордана относительно условий, при которых конус имеет полную размерность (иными словами, выяснив, когда система строгих неравенств разрешима), и результатов Фаркаша и Минковского относительно того, что любой полиэдральный конус конечно порожден, в его работах появилось понятие полярного конуса С* полиэдрального конуса C и был выведен ряд его свойств.
А. Хаар в своей работе 1918 года дал обобщение леммы Фаркаша для неоднородных систем.
В 1928 фон Нейманом было доказано равенство максимина и минимакса для произвольной матрицы, а это равносильно теореме двойственности ЛП, что было продемонстрировано Данцигом, а также Д. Гейлом, Х. У. Куном и А. У. Таккером. Причина такого глубокого взаимопроникновения ЛП и теории матричных игр была вскрыта Нейманом и Данцигом, показавшими возможность приведения любой матричной игры двух лиц с ненулевой суммой и конечным числом стратегий к паре двойственных задач ЛП и наоборот.
В ходе изучения модели расширяющейся экономики, выдвинутой фон Нейманом в статье 1937 года, он приходит к результатам, которые содержат в себе теорему двойственности для задач ЛП с положительными коэффициентами.
1.3. О математическом творчестве Л. В. Канторовича конца 1920Ц1930-х годов.
Первые шаги к разработке модели и методов ЛП были предприняты в качестве ответа Канторовича на запрос о необходимости решения совершенно конкретной экономическопроизводственной задачи фанерного треста. Однако, для понимания тех причин, по которым эти методы были предложены именно Канторовичем в тот самый момент времени и почему они получились такими, важно иметь представление об истоках и линии его научной жизни, которые предшествовали периоду обращения направления его творческого поиска в сторону вопросов экономического характера и началу работ над математическими методами в экономике. Именно для формирования такой картины приводится обзор математических исследований (по дескриптивной теории функций, конструктивной теории функций, приближенным методам анализа, функциональному анализу и теории полуупорядоченных пространств).
Глава 2. Развитие линейного программирования в ранних работах Л. В.
Канторовича Хотя интерес Канторовича к экономике проявился еще в студенческие годы, весь первый период своего научного творчества он был увлечен преимущественно математикой.
Однако, в 1936-1937 годах, заканчивая цикл работ по теме полуупорядоченных пространств, он почувствовал некоторую неудовлетворенность собственной деятельностью в области математики, вызванную ощущением приближающейся войны и сопряженным с ним чувством своей ответственности. Так под воздействием внешних факторов он стал задумываться над вопросами экономики.
Канторович начал заниматься вопросами линейной оптимизации в 1938 году в связи с задачей оптимальной загрузки станков фанерного треста. Он сразу заметил два основных обстоятельства: во-первых, то, что многие другие экономические проблемы приводят к аналогичным математическим задачам - максимизации функции при многих ограничениях, и, во-вторых, невозможность непосредственного применения методов математического анализа в ряде практических задач в силу того, что при этом возникает слишком большое число систем уравнений, делающее этот путь совершенно неприменимым практически.
В итоге Канторовичем был сначала предложен геометрический метод, доложенный впервые в 1938 году. Однако, так как этот метод не был достаточно алгоритмичен, работа продолжалась, и в конце того же года в связи с некоторыми идеями функционального анализа Канторович предложил общий метод решения подобных задач - метод разрешающих множителей, показавшийся автору перспективным благодаря алгоритмичности и содержательному экономическому значению этих множителей, в течение нескольких месяцев выявленному ученым. Соответствующие исследования были оформлены в 1939 году в виде работы Математические методы организации и планирования производства, ставшей первым трудом Канторовича по экономической тематике и сделавшей решение подобных задач осуществимым практически.
Рассматриваются основная идея предложенного в работе метода и некоторые важные с точки зрения математики и экономики моменты, разобранные в этой работе.
Изучаются также работы, которые стали непосредственным продолжением первого исследования Канторовича в области математических методов экономики. В этих работах содержатся, во-первых, наиболее общая математическая трактовка предложенного автором вариационного принципа и метода разрешающих множителей; во-вторых, общая формулировка условий экстремума при наличии ограничений в бесконечномерном пространстве, и, кроме того, постановка и решение ставшей впоследствии классической транспортной задачи и ее бесконечномерного аналога.
Описываются эквиваленты задачи C из первой публикации Канторовича в области математических методов экономики, связь разрешающих множителей, предложенных в этой работе, с решением двойственной задачи. Рассматривается также вопрос о взаимосвязи методов разрешающих множителей, корректировки множителей, потенциалов, последовательного улучшения плана и СМ, методов одновременного решения прямой и двойственной задач, метода ДанцигаЦФордаЦФулкерсона и пересмотренного СМ.
В классической математике задачи на условный экстремум рассматривались только для ограничений типа равенств, и в этом случае в качестве аппарата для их решения использовалось правило множителей Лагранжа. В то же время изучением собственно систем неравенств в отрыве от задач минимизации занимались Фурье, Минковский, Вейль и другие.
И хотя ими были достигнуты значительные успехи, и созданный в ходе их исследований аппарат позволял получать условия экстремума в задачах с ограничениямиЦнеравенствами, первые работы по экстремальным задачам с ограничениями общего вида появились только в конце 30-х - начале 40-х годов XX века.
К следующему периоду можно отнести исследования Чикагской школы (Г. Блисс, О.
Больца, Е. Макшейн, Л. М. Грейвс, М. Р. Хестенс и др.), для представителей которой характерен интерес возможно более широкой постановки вариационных задач. В этой связи упомянуты исследования Ф. Валентайна 1937 года по условиям экстремума для задач вариационного исчисления при наличии разного рода ограничений типа неравенств, В.
Каруша, исследовавшего гладкие конечномерные задачи минимизации с общими ограничениями и пришедшего в 1939 году к условиям экстремума I и II порядков, и Ф.
Джона, который в качестве темы исследования избрал экстремальные проблемы в геометрии и получил сходные результаты.
В СССР, как уже было сказано, пионером в этой области был Канторович. Первая его работа этой тематики вышла в 1939 году. Но первые его работы не получили единодушного признания и широкого распространения.
Прослеживается родство этих вопросов с теорией задач оптимального управления, которая появилась в результате взгляда на них с несколько иных позиций. Здесь необходимо отметить достижение таких ученых как Л. С. Понтрягин, В. Г. Болтянский и Р. В.
Гамкрелидзе, сформулировавших и доказавших необходимые условия оптимальности в форме так называемого принципа максимума. Сходными вопросами занимался так же Р.
Беллман, а позднее появился и цикл работ А. Я. Дубовицкого и А. А. Милютина, Б. Н.
Пшеничного, Л. Нейштадта, Г. Халкина, Дж. Варги и др., в которых были предложены общие схемы получения условий экстремума для абстрактных задач оптимизации с ограничениями.
В заключении раздела рассматриваются связи проведенных Канторовичем в довоенные годы исследований в области математических методов в экономике и использованных в них идей с его творчеством в области функционального анализа, которое, по упоминаниям самого ученого, имело огромное влияние на его последующие изыскания в области экономики. Говорится о связях с теорией двойственности, теоремой ХанаЦБанаха и теоремами линейной отделимости, теоремами об альтернативах, леммами Фаркаша, двойственностью ФенхеляЦЮнга в теории выпуклых функций и множеств, взглядами Данцига и фон Неймана.
Также отмечен следующий существенный момент: важнейший шаг при исследовании экстремальных задач для выпуклых числовых функционалов - применение теорем отделимости, основанных на теореме ХанаЦБанаха о продолжении линейных функционалов.
Очень ценным для разных приложений оказалось то, что теорема ХанаЦБанаха обобщается на случай продолжения мажорируемых линейных операторов со значениями в Kпространстве. Таким образом, теория K-пространств нашла широкое приложение в выпуклом анализе - ведь это те самые объекты, которые лежат в центре его внимания - и, посредством него, при исследовании экстремальных задач и в экономико-математических моделях.
Описана связь с дискретной математикой, теорией матричных игр, численными методами, методами приближенных вычислений, теорией K-пространств и лобратная связь математических методов экономики и чистой математики, то есть влияние экономических задач на математический аппарат, проявившееся в виде огромного роста интереса к изучению теории систем линейных неравенств, появившегося именно в связи с потребностями экономики. Также описано влияние исследования транспортной задачи, возникшей из экономики, на теорию вероятностей и функциональный анализ, проявившееся в виде введения в этих областях математики нового типа метрики. Кроме того, Канторович на основе обобщения идей, использованных во время исследования транспортной задачи, смог получить более полное решение известной проблемы Монжа (см. ниже).
Глава 3. Развитие линейного программирования в работах Л. В. Канторовича 1930Ц1950-х годов Дан анализ статей Канторовича, носящих прикладной характер, дающих представление о круге тем, которыми интересовался Канторович с точки зрения приложений разработанных им методов ЛП.
В частности, рассматриваются две статьи 1949 года, одна из которых, несмотря на то, что носила чисто прикладной характер, содержала в себе постановку и решение классической транспортной задачи, а также анализ задач об оптимальных перевозках грузов и алгоритмы решения этих задач в виде метода потенциалов.
Творчеству Канторовича присуще взаимопроникновение прикладных и теоретических исследований, что произошло и с экономико-математической тематикой. Так знаменитая работа 1959 г., за которую он был удостоен Ленинской премии, сочетает прикладные и теоретические исследования: она содержит как анализ разработанных экономических приложений ЛП, так и наиболее полное изложение математической теории и вычислительных методов, лежащих в его основе.
В других работах содержатся наиболее общая математическая трактовка предложенного Канторовичем вариационного принципа и метода разрешающих множителей, общая формулировка условий экстремума при ограничениях в бесконечномерном пространстве, дается постановка и анализ общей задачи производственного планирования. Среди прочих трудов необходимо упомянуть отдельно статью 1942 года, в которой был рассмотрен бесконечномерный аналог транспортной задачи, так как эта работа примечательна еще и тем, что, основываясь на ней, в 1948 году Канторовичем было получено более полное решение известной проблемы Монжа.
Среди важных работ, выполненных в соавторстве, необходимо выделить две статьи, выполненные совместно с Г.Ш.Рубинштейном, которые посвящены обобщениям задач ЛП на пространства вполне аддитивных функций множеств.
На пути продвижения и внедрения в практику экономических идей и методов, разработанных в процессе своей исследовательской деятельности, Канторовичу пришлось столкнуться с целым рядом трудностей и большим сопротивлением со стороны многих консервативно настроенных экономистов. Для того чтобы понять, насколько серьезным было противостояние, которое пришлось вести Леониду Витальевичу для того, чтобы отстоять свою точку зрения, рассматриваются основные этапы истории получения им Ленинской премии.
Также как и признание на родине, в СССР, международное признание пришло к Канторовичу не сразу и не совсем гладко. Одной из причин этого было то, что зарубежные ученые узнали о его трудах с большим запозданием.
Результаты исследований по транспортной задаче, полученные в 1940 году, были опубликованы лишь в 1949 году, когда они уже были повторно открыты на Западе. Подобная судьба постигла и множество других работ.
Все эти обстоятельства существенным образом затруднили признание приоритета Канторовича в разработке методов ЛП. Однако, приоритет Канторовича, тем не менее, все же был признан мировой общественностью, и ему совместно с Купмансом в 1975 году была присуждена Нобелевская премия по экономическим наукам за вклад в разработку теории оптимального использования ресурсов в экономике.
В заключении раздела описывается лобратная связь математических методов экономики, когда разработанный в связи с запросами экономики математический аппарат позволил получить существенное продвижение и в самой математике, примером чему служит полное решение проблемы Монжа, полученное Канторовичем на основе открытых им ранее методов ЛП.
Несмотря на то, что данной проблемой занимались многие известные математики, строгое доказательство гипотезы было дано только в 1884 г. в 200-страничном мемуаре П.
Аппеля. Позже автору удалось его упростить. Тем не менее, оно продолжало оставаться весьма сложным и базировалось на тонких теоремах уже развитого к тому моменту вариационного исчисления. Однако, доказательство гипотезы, причём для более широкого класса задач перемещения массы, получается в виде простого следствия признака оптимальности перемещения, разработанного Канторовичем и М. К. Гавуриным в связи с решением транспортной задачи и обобщённого затем Канторовичем на бесконечномерный случай.
Глава 4. Дж. Б. Данциг и линейное программирование. Джордж Б. Данциг известен в первую очередь в качестве отца ЛП и изобретателя СМ для решения его задач. В тот момент, когда Данциг только начал вести свои исследования по теме ЛП, уже существовали работы двух основных авторов, сделавших главный вклад в его открытие:
Канторовича и Купманса. Кроме них сходными исследованиями также занимались Хичкок и намного ранее Монж. Необходимо упомянуть и еще несколько человек, которые внесли вклад в предысторию ЛП: метод Фурье для решения систем линейных неравенств с элементами, подобными СМ; метод для поиска минимально отклоняющихся решений систем уравнений Шарля де ла Валле-Пуссена; исследования фон Неймана по теории конечных игр с участием двух лиц с нулевой суммой; а также диссертацию Т. Моцкина по исследованию систем линейных неравенств и работу Л. Л. Дайне, который, похоже, сконцентрировался на строгих неравенствах. В силу достаточных оснований можно утверждать, что все эти достижения были неизвестны Данцигу.
Однако, несмотря на то, что у Данцига был целый ряд предшественников, которые занимались сходными вопросами исследования систем линейных неравенств и чьи исследования потенциально могли вдохновить Данцига на его открытие, совсем не их работы стали отправной точкой его исследований - толчком для деятельности послужила работа Леонтьева по структуре Американской экономики (доведенная до внимания Данцига Д. Эвансом - его другом и бывшем коллегой по Bureau of Labor Statistics). Эта работа вдохновляла и тем, что в ней была создана количественная эмпирическая, а не чисто формальная, модель.
С 1946 года обязанности Данцига в Пентагоне включали механизацию процедур планирования для поддержания поэтапного по времени развертывания тренировочной и снабженческой деятельности военно-воздушных сил. Данциг создал линейную математическую модель, отражающую ситуацию, учитывая наличие запасов и необходимость их пополнения в течение многопериодного временного промежутка. Для выделения наилучшего решения, Данциг предложил линейную целевую функцию, подлежащую минимизации или максимизации, что было инновацией в планировании и тем достижением, которым Данциг чрезвычайно гордился.
Хотя открытие ЛП было сделано независимо от других работ, оно не происходило в изоляции. На каждом этапе присутствовало активное общение, способствовавшее ему. Среди важных контактов описываются связи с Л. Гурвицем, М. Гейслером и М. Вудом, А. Каном, Купмансом и, прежде всего, фон Нейманом. Показана также очень важная роль Таккера, который вместе со своими студентами Куном и Гейлом дал первое строгое доказательство теоремы двойственности, которую фон Нейман и Данциг обсудили во время их первой встречи.
Данциг доложил об открытии СМ 29 декабря 1947 года на заседании объединенного ежегодного собрания American Statistical Association (ASA) и Institute of Mathematical Statistics (IMS). По-видимому, доклад Данцига не привлек особого интереса и не был опубликован. Спустя почти год произошло следующее представление метода на заседании под председательством фон Неймана на объединенном национальном собрании IMS и Econometric Society, пробудившее интерес больше предшествовавшего.
Практическая важность ЛП была очевидна с самого его начала. Для Данцига и других ученых было очевидно существование семейства родственных задач, которые стали известны в качестве расширений ЛП.
В ранний период важные продвижения были сделаны в области нелинейной оптимизации. Кун и Таккер представили работу Нелинейное программирование. Эта статья дает необходимые условия оптимальности для задачи минимизации (возможно) нелинейной целевой функции в условиях ограничений в виде (возможно) нелинейных неравенств. Этот результат является наследником так называемого Метода множителей Лагранжа. Подобная теорема была ранее получена Ф. Джоном и опубликована в Courant Anniversary Volume за 1948 год. Вот уже некоторое время эти условия оптимальности называются условиями КарушаЦКунаЦТаккера в знак признания практически одинакового результата, представленного в (неопубликованной) магистерской диссертации Каруша в Чикагском университете в 1939 году.
В 1951 году появилась докторская диссертация Р. Дорфмана Приложение линейного программирования к теории фирмы, включая анализ монополистических фирм с помощью нелинейного программирования. Вероятно, это первый раз, когда словосочетание линейное программирование появилось в заглавии. Под нелинейным программированием в ее названии понимается квадратичное программирование - оптимизация квадратичной функции, подчиненной ограничениям в форме линейных неравенств.
Сам Данциг с 1952 года присоединился к RAND Corporation, где очень плодотворно работал над проблемами теории игр, ЛП и различных вариантов СМ, крупномасштабного ЛП, ЛП в условиях неопределенности, сетевой оптимизации, включая задачу коммивояжера, целочисленного ЛП и их многообразными приложениями.
Особенно важны были исследования, связанные с решением крупномасштабных линейных программ, для чего разрабатывались специальные разновидности СМ, в которых итерации осуществляются, полагаясь на базис сильно уменьшенного размера, так как вскоре было замечено, что эффективность СМ больше связана с количеством линейных ограничений, определяющим размер базиса, чем с числом переменных. Кроме того, ученый работал над вариантами СМ для специальных случаев, заслуживающих особого внимания.
Так, например, СМ очень эффективен для базиса треугольной или почти треугольной структуры, что привело к изучению СМ для случая базисов блочной треугольной структуры.
В поздние 1950-ые годы Данциг и Ф. Вольф предложили принцип декомпозиции.
Линейное и нелинейное программирование сыграли важную роль в формировании профессиональных организаций. Уже в 1948 году был основан Operational Research Club (позже переименованный в Operational Research Society (of the UK)), в 1952 году появилось Operations Research Society of America (ORSA), а годом позже - Institute of Management Sciences (TIMS). Две последние организации, каждая со своими журналами, объединились в 1995 году в Institute for Operations Research and the Management Sciences (INFORMS), насчитывающий сегодня около 12Т000 членов. В мире сейчас около 48 национальных обществ исследования операций (ИО) с общим членством порядка 25Т000 человек.
Математическое программирование (есть тенденция называть его лоптимизацией) было лишь одной из тематик, появлявшихся на страницах этих журналов, и первые их тома посвящали лишь маленькую часть объема математическому программированию, однако со временем это в корне изменилось: несколько лет спустя было учреждено множество научных журналов, чтобы идти наравне с этим полем активных исследований. В дополнение к журналу Mathematical Programming, сейчас существует около дюжины других, чьи названия включают лоптимизацию.
К началу 1950-ых годов курсы по ИО появились в различных университетах, а с ними пришло и ЛП. В 1953 году А. Чарнс и У. Купер начали читать лекции в Carnegie Tech, в тот год ИО и ЛП появились как программы аспирантов в Case Institute of Technology. В университете Стэнфорда ИО стало преподаваться в 1954 году, а ЛП было одной из тем. В Cornell преподавание по этим направлениям началось в 1955 году, в Northwestern - в 19году. В последовавшие десятилетия процесс шел лавинообразно. Учреждались отдельные факультеты ИО и появились программы получения ученых степеней; в других случаях эти слова (и альтернативы вроде наука управления или наука по принятию решений) добавлялись к названиям существующих факультетов. Междисциплинарная природа этой области знаний способствовала широкому кругу названий для этой тематики и мест ее преподавания (иногда даже внутри одной и той же организации, такой как университет Стэнфорда). И везде, где ИО получало устойчивое положение, такие предметы как ЛП тут же перерастали их место одной из тем вступительных курсов, становясь многими независимыми курсами - каждый из которых преподавался отдельно.
Вместе с развитием учебных курсов произошел и взрыв издательской активности.
Появились учебники, пособия, руководства, задачники по ИО, среди которых книги по математическому программированию составляли большую часть. Одна из наиболее важных книг этой тематики была написана самим Данцигом: Linear Programming and Extensions была так богата идеями, что ее назвали Библией ЛП. Кроме того, Данциг сыграл огромную роль в привлечении новых ученых в те области, которыми сам занимался, ведя активную организаторскую, административную и преподавательскую деятельность, что также описывается в этом пункте. В заключении обсуждается влияние всех видов деятельности Данцига на математику.
Глава 5. Работы других американских авторов, связанные с линейным программированием.
5.1. Фон Нейман, теория игр и ее связи с линейным программированием. Многие игры двух лиц описываются как поиск maxx miny xAy, когда x = {x1,Е, xm} и y = (y1,Е, yn)T пробегают множества неотрицательных векторов, x1 + Е + xm = 1, y1 +...+ yn = 1, A - известная (m n)-матрица.
Ясно, что maxx miny xAy miny maxx xAy. Э. Борель, исследуя данный вопрос, сосредоточивался на матрицах кососимметрического типа и выдвинул гипотезу, согласно которой существуют матрицы такого типа, для которых достигается строгое неравенство.
Но в 1928 году фон Нейманом была доказана справедливость равенства maxx miny xAy = miny maxx xAy для произвольной матрицы A. На самом деле, последнее утверждение равносильно теореме двойственности ЛП, что было продемонстрировано Данцигом, а также Гейлом, Куном и Таккером.
Несмотря на предшествующие работы, теория игр получила существенное распространение лишь в 1944 году вместе с выходом знаменитого труда Неймана и Моргенштерна Теория игр и экономическое поведение. Работа одновременно давала дальнейшее развитие математической стороны вопроса и пути приложения разрабатываемых методов к задачам экономики. Скоро к экономическим приложениям добавились военные.
Со временем теория игр продолжила расширять сферу своих исследований.
Особо глубокое взаимопроникновение ЛП и теории матричных игр было вскрыто Нейманом и Данцигом, показавшими, что любая матричная игра двух лиц с ненулевой суммой и конечным числом стратегий может быть приведена к паре двойственных задач ЛП и наоборот.
В данной работе приводятся основные понятия и результаты теории игр, имеющие прямое отношение к ЛП, раскрывается связь между ЛП и теорией игр и приводятся геометрические интерпретации.
Можно сказать, что фундамент математического аппарата, который используется в ЛП, создал в своих рабочих материалах еще фон Нейман. В своих исследованиях ученому удалось доказать равносильность отыскания max{cx | x 0, Ax b} и установления решения следующей системы линейных уравнений: x 0, Ax b, yA c, y 0, cx yb. После этого Гейл, Кун и Таккер представили формулировку и показали справедливость теоремы о двойственности ЛП: max{cx | x 0, Ax b} = min{yb | y 0, yA c}.
5.2. Теорема Каруша - Куна - Таккера и принцип Лагранжа. Каруш в своей диссертации рассмотрел проблему минимизации функции f при наличии ограниченийнеравенств. Из одного из полученных в работах ученого утверждений, предположив линейность всех функций, можно вывести теорему двойственности ЛП. Среди прочего Карушу удалось получить необходимые и достаточные условия оптимальности, описываемые с помощью первых и вторых производных.
Теорема Каруша стала фундаментальным для нелинейного программирования достижением, которое позднее получило обобщение в работах Ф. Джона, Куна и Таккера.
При исследовании задач ЛП можно использовать различные подходы. Некоторые из них появились одновременно с возникновением самого ЛП, другие добавлялись по мере исследований, как в этой области, так и в других областях, связанных с оптимизационными задачами. По мере появления всё новых подходов, формировалась целостная картина. На мой взгляд, одним из лучших является подход с позиций выпуклого анализа, поскольку он позволяет в достаточно общей форме формулировать задачу математического программирования и признаки оптимальности решения, раскрывая при этом связи с двойственной задачей и её решением, что имеет большое значение для понимания и экономической интерпретации результатов. При этом не требуется введения большего количества специальной терминологии. Основные понятия - пространства в двойственности и преобразование Лежандра. В диссертации приводятся условия экстремума для задач математического программирования, получившие широкую известность после работы Куна и Таккера 1950 года, описывающей нахождение необходимых условий оптимальности решения экстремальной задачи. Также показано использование доказанной в э той работе теоремы для раскрытия смысла принципа двойственности в выпуклом программировании. И приведен переход к классической формулировке задачи ЛП, являющейся частным случаем описанных выше результатов.
5.3. Другие работы, выполненные в США, связанные с линейным программированием. Условия, близкие, по сути, с теми, которые удалось вывести Карушу, через некоторое время получил Ф. Джон, исследовавший экстремальные задачи, связанные с нахождением эллипсоида, обладающего наименьшим объёмом, который описан вокруг определенного выпуклого тела. Труды Ф. Джона можно считать независимыми относительно, в том числе, исследований Каруша (в силу того, что открытие последнего, представленное в его магистерской диссертации, не было на тот момент издано), однако вышли они значительно позднее - только в 1948 году.
Транспортные задачи, которым посвящен соответствующий пункт выше, можно назвать одними из самых первых проблем, относящихся к области ИО. Также справедливо будет сказать, что на пути поиска решения данных проблем в работах Канторовича, Хитчкока и Купманса появлялось ЛП, и развивался и обогащался его аппарат.
В своей работе 1941 года алгебраист из MIT Хичкок исследовал следующую проблему:
mini = 1, Е, m j = 1, Е, n aijxij с условиями i = 1, Е, m xij = dj (j = 1,..., n) j = 1, Е, n xij = bi (i = 1,..., m) xij 0 (i = 1, Е, m; j = 1, Е, n).
Ученому удалось доказать достижение наименьшего значения в вершине допустимой области, а также представить путь для нахождения решения рассмотренной им проблемы, которой во многом схож, в том числе и преобразованиями на итерациях путем введения и выведения базисных переменных, с СМ.
В 1948 году Купманс изложил в своей работе задачи трансперевозок, их интерпретацию и суть описываемых ими вопросов, а также представил метод локального поиска для получения оптимального решения такого рода задач, указав, что он приводит к о009. - С. 323Ц339.
4. Андрианов А.Л. Линейное программирование в работах Л.В. Канторовича 1930Ц 1950-х гг. // Институт истории естествознания и техники им. С.И. Вавилова. Годичная научная конференция, 2009. - М.: Анонс Медиа, 2009. - С. 323Ц325.
5. Андрианов А.Л. Джордж Б.Данциг и история линейного программирования (ЛП) в США // Институт истории естествознания и техники им. С.И. Вавилова. Годичная научная конференция, 2011. - М.: Анонс Медиа, 2011. - С. 315Ц318.
6. Andrianov A. The full solution to Monge problem base on linear programming (LP) // Proceedings of the 8th Congress of the International Society for Analysis, its Applications, and Computation. - M.: PFUR, 2011. - P.220.
Подписано в печать: 01.04.2012 г.
Отпечатано: 01.04.2012 г.
Отпечатано в типографии ООО "Апаче Групп", ИНН 77077154г. Москва, ул. Бутырский вал, 48-Заказ № 321/Бумага офсетная. Печать цифровая.
Усл.печ.л. 1,0. Тираж 100 экз.