1.2 История линейного программирования

Идеи Л. В. Канторовича в контексте экономических исследований советских ученых первой половины XX в. Задолго до того, как Канторович начал проводить свои научные изыскания в области экономики, в СССР уже существовал опыт проб применения методов математического и статистического анализа для решения задач экономики: такие исследования стали предприниматься уже в 20-ые годы XX века.

Среди этих работ необходимо отметить труды Е. Е. Слуцкого и А. А. Конюса, в которых ученые изучали модели потребления. Г. А. Фельдман работал над моделями роста, Н. Д. Кондратьев - над «длинными циклами», в ЦСУ СССР были выполнены работы по шахматному балансовому аначизу экономики. Позже это направление получило дальнейшее развитее, было математизировано и усовершенствовано В. В. Леонтьевым с широким использованием сведений и материатов экономики США. В тот же временной период Л. Юшков выдвинул идею оптимального подхода к понятию норматива эффективности, впоследствии получившую плодотворное развитие в творчестве В. В. Новожилова.

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

Математические предпосылки возникновения линейного программировании. Несмотря на то, что открытие ЛП и методов решения его задач связываются в первую очередь с именами таких ученых как Канторович, Купманс и Данциг, они не были первыми, кто занимался этими вопросами. И хотя, насколько известно, они не были знакомы с исследованиями своих предшественников, последние представляют большой интерес с точки зрения истории развития математики, связанной с этим вопросом. Также необходимо заметить: как исследования, относящиеся непосредственно к ЛП, так и работы, изучающие полиэдры и линейные неравенства сами по себе, — все их можно считать имеющими прямое отношение к интересующему нас предмету в силу того, что эти три области являются ни чем иным, как взглядами с разных сторон (со стороны оптимизации, геометрии и алгебры, соответственно) на одни и те же вопросы. В силу этого в качестве предыстории ЛП рассматриваются важнейшие результаты во всех этих областях, родственная природа которых была замечена еще Ж. Б. Фурье.

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

Если же говорить о многомерных задачах оптимизации, то начиная с конца XVIII века ученые обращались к их изучению в связи с вопросами теоретической механики и отысканием методов решения систем линейных неравенств. Более того, можно сказать, что ученые (Ж. Лагранж, Фурье, К. Гаусс, М. В. Остроградский) всерьез занялись изучением самих линейных неравенств, размышляя над вопросами, связанными с принципом виртуальных скоростей и теорией Лагранжа.

Важное место в вопросе о появлении идей, на которые опирается СМ, занимают исследования, связанные с чебышевским приближением, а именно, - с нахождением точки, наименее уклоняющейся по модулю от системы плоскостей (такая точка называется чебышевской). Данная задача эквивалентна задаче ЛП определенного вида.

Геометрическая теория полиэдров получила свое бурное продвижение в 19-м веке (О. Коши, Я. Штейнер, Дж. Сильвестр, А. Кэли, А. Мебиус, Т. Кирман, А. Пуанкаре, Л. Шлефли, А. Тет).

Что касается двойственности и полярности, то основные представления о них начали появляться в результате исследовании 1820-1830-ых годов Ж. Жергонна, Ж. В. Понселе и К. Г. X. фон Штаудта о двойственности вершин и фасет в политопах, а также о полиэдрах и выпуклых телах с использованием полярности. Что касается самой концепции двойственности в геометрии, то она развивалась в работах Понселе, Жергонна, Я. Штейнера и фон Штаудта и Ю. Плюккера.

Ближе к концу XIX века исследованием линейных неравенств занялись Г. Мннковский и Ю. Фаркаш, развивших в своих работах алгебраический подход к теории полиэдров.

Из утверждений, явно сформулированных в работах Фаркаша, принимая во внимание принцип двойственности, ту т же следует утверждение (1935 г. Г. Вейль) о том, что любой конечно порожденный конус является полиэдральным.

В исследованиях Вейля, Мннковского и Г. Ф. Вороного удалось определить, каким образом связаны друг с другом многогранники и полиэдры.

Работая над задачами теории чисел, Мннковский пришел к изучению линейных неравенств и выпуклых тел и к 1896 году показал, что любой полиэдральный конус Ах < 0 конечно порожден: если матрица А имеет полный ранг по столбцам, то этот конус порожден лучами, каждый из которых определяется (и - 1) линейно независимыми уравнениями из Ах = 0. Из чего он, предполагая полный ранг А по столбцам, получил лемму Фаркаша. Из хода доказательства видно, что он знал о двойственности лучей и неравенств и о возможности приведения неоднородного случая к однородному.

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

А. Хаар в своей работе 1918 года дал обобщение леммы Фаркаша для неоднородных систем.

В 1928 фон Нейманом было доказано равенство максимина и миннмакса для произвольной матрицы, а это равносильно теореме двойственности ЛП, что было продемонстрировано Данцигом, а также Д. Гейлом, X. У. Куном и А. У. Таккером. Причта такого глубокого взаимопроникновения ЛП и теории матричных игр была вскрыта Нейманом и Данцигом, показавшими возможность приведения любой матричной игры двух лиц с ненулевой суммой и конечным числом стратегий к паре двойственных задач ЛП и наоборот.

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

О математическом творчестве Л. В. Канторовича конца 1920-1930-х годов. Первые шаги к разработке модели и методов ЛП были предприняты в качестве ответа Канторовича на запрос о необходимости решения совершенно конкретной экономическо-производственной «задачи фанерного треста». Однако, для понимания тех причин, по которым эти методы были предложены именно Канторовичем в тот самый момент времени и почему они получились такими, важно иметь представление об истоках и линии его научной жизни, которые предшествовали периоду обращения направления его творческого поиска в сторону вопросов экономического характера и началу работ над математическими методами в экономике. Именно для формирования такой картины приводится обзор математических исследований (по дескриптивной теории функций, конструктивной теории функций, приближенным методам анализа, функциональному анализу и теории полуупорядоченных пространств).

Метод внутренних точек был впервые упомянут И. И. Дикиным в 1967 году.