Л.В.Канторович: теория линейного программирования

Министерство  образования и науки, молодежи и  спорта Украины.

Крымский  экономический институт Киевского  национального экономического университета им. Вадима Гетьмана. 
 
 
 
 

Реферат

По дисциплине: «Основы экономики»

По теме: «Л.В.Канторович: теория линейного программирования» 
 
 

Выполнил  студент ЕП 11-11

Горда Глеб 
 
 
 
 
 
 
 
 

Симферополь 2011 г.

   Одним из наиболее значительных  и ярких достижений в области  экономико-математических исследований  было открытие Леонидом Витальевичем  Канторовичем (1912—1986) метода линейного  программирования. Линейное программирование  — решение линейных уравнений  (уравнений первой степени) посредством  составления программ и применения  различных методов их последовательного  решения, существенно облегчающих  расчеты и достижение искомых  результатов.

     За разработку метода линейного  программирования или, как сказано  в дипломе Шведской академии  наук, за «вклад в теорию оптимального  распределения ресурсов Л.В.Канторович  был удостоен Нобелевской премии  по экономике (1975). Премия была  присуждена ему совместно с  американским экономистом Тьяллингом Чарльзом Купмансом, который несколько позже, независимо от Канторовича, предложил сходную методологию.

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

     Заслуга Канторовичами состоит  в том, что он предложил математический  метод выбора оптимального варианта. Решая частную задачу наиболее  рациональной загрузки оборудования, ученый разработал метод, получивший  название метода линейного программирования. По сути дела, он открыл новый  раздел математики, получивший широкое  распространение в экономической  практике, способствовавший развитию  и использованию электронно-вычислительной  техники.

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

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

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

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

     Допустим, требуется решить транспортную  задачу, обосновать наиболее рациональное  распределение грузопотоков. Для  примера, всего нужно перевести  180т груза из трех источников  к трем потребителям, общий спрос  которых также равен 180 т. Сложность  в том, что груз распределен  неравномерно: у одного поставщика  имеется 50 т, у другого —  60 т, у третьего — 80 т.

   Также неравнозначен спрос потребителей: он составляет соответственно 40, 85 и 55 т. Неодинаковы и расстояния  — плечи перевозки грузов —  от 1 до 6 км. Задача заключается в  том, чтобы составить такой  план перевозок, который отвечал  бы требованию минимизации грузооборота (минимальному количеству тонно-километров).

Как решить эту задачу?

     В повседневной практике менеджеры  могут заняться монотонной работой  по длительному перебору возможных  вариантов. Постепенно они смогут  «пройти» от плана перевозок,  скажем, в 750 т-км к плану в  655 т-км. Поиск потребует массу  усилий, значительного количества  расчетов. Главное же — трудно  установить, какой из предлагаемых  вариантов является оптимальным.  Допустим, найден вариант плана  с грузооборотом в 575 т-км.

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

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

Метод линейного  программирования позволяет найти  оптимальное решение. Линейным оно  называется потому, что основывается на решении линейных уравнений. Неизвестные  в них только первой степени; ни одно неизвестное не перемножается на другое неизвестное. Такие уравнения  отражают зависимости, которые могут  быть изображены на графике прямыми  линиями.

     Несколько иной целевой критерий  в задаче о диете (кормовом  рационе). Задача сводится к поиску  оптимального рациона для кормления  скотины или птицы. При постоянном  изменении рыночных цен на  корма фермеры подбирают оптимальный  рацион при минимуме затрат, производя  соответствующие расчеты на компьютере.

Впервые работа, в которой излагалось существо предложенного Канторовичем метода, была опубликована в 1939 г. под названием  «Математические методы организации  планирования производства». Продолжая  исследования, ученый разрабатывает  общую теорию рационального использования  ресурсов..

В период Великой Отечественной войны, будучи профессором Военно-морской инженерной академии в блокадном Ленинграде, Канторович, опираясь на метод линейного  программирования, обосновывает оптимальное  размещение производственных и потребительских  факторов. В 1942 г. он подготовил книгу  «Экономический расчет наиболее целесообразного  использования ресурсов», которая  в тот период, к сожалению, не была опубликована.

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

     Для любой задачи линейного  программирования существует сопряженная  ей, или двойственная задача. Если  прямая задача заключается в  минимизации целевой функции,  то двойственная — в максимизации.

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

     При непосредственном участии  Канторовича и его ближайших  коллег — В. В. Новожилова (автора  идеи продуктово - трудового баланса) и В. С. Немчинова (обосновавшего глобальный критерий функционирования экономики) формировалась отечественная экономико-математическая школа. 
 
 
 
 
 
 
 
 
 
 
 

Ответы  Л.Канторовича на вопросы Сони Брентьес.

Глубокоуважаемая  Соня Брентьес!  

Прошу извинить за задержку ответа на Ваши письма, связанную  с занятостью другими делами, хотя Вашему намерению написать историю  вопроса вполне сочувствую и готов  помочь Вам.  

Отвечаю на Ваши вопросы:  

1) Почему  Вы занялись в 1939 году линейными  оптимальными задачами?

Как написано в моей книге, я занялся линейной оптимизацией в связи с конкретной задачей об оптимальной загрузке лущильных станков, с которой  обратился к нам фанерный трест. Это было в начале 1938 года. Однако задача не поддавалась эффективному решению. В то же время я заметил, размышляя над этим вопросом, что  и целый ряд других проблем - рациональный раскрой, использование сельскохозяйственных земель и другие приводят к сходным  математическим задачам - максимизации функции при многих ограничениях. Это показало, что речь идет не о  случайной единичной задаче, а  о целом классе важных проблем, что  заставило более настойчиво искать решение проблемы. Сначала я предложил  некоторый геометрический метод, о  нем и комплексе задач я  докладывал в неопубликованном докладе  в ноябре 1938 года в Институте им. Герцена в Ленинграде. Но этот метод  не был достаточно алгорифмичен и меня не удовлетворил. Однако в конце 1938 года, в связи с некоторыми идеями функционального анализа, я открыл метод разрешающих множителей, который мне сразу показался весьма перспективным и благодаря его алгорифмичности, и благодаря содержательному экономическому значению этих множителей, которое мне стало ясным в ближайшие месяцы.

2) Занимались  ли Вы до 1939 года подобными  проблемами?

Такими  проблемами я непосредственно не занимался, но для интереса к проблеме и занятий ею, имело значение следующее.  

Данная  работа 1939 года является примерно 60-ой в списке моих научных публикаций с 1929 года, в частности, для меня повидимому имели значение следующие предыдущие циклы работ:  

а) Работы по вычислительной математике, в частности, книга «Приближенные методы высшего  анализа» (совм. с В.И. Крыловым изд. 1, 1936 г.).  

б) Некоторое  число связанных с предыдущим циклом работ по применению приближенных методов в различных задачах  механики. Это было связано с моей педагогической деятельностью в  инженерных вузах.  

в) Цикл работ по ункциональному анализу.  

г) Интерес, правда в то время дилетантский, к экономике (впрочем, во время студенческой практики в 1929 году, я работал несколько месяцев экономистом­статистиком).

3) Знали  ли Вы о работах Фурье, Фаркаша, Минковского и т.д.?

С этими  работами я познакомился позднее.

4) Кто  кроме Вас и проф. Гавурина  в Ленинграде и в СССР занимался  линейной оптимизацией?

В моей книге указано, что расчет примера, относящегося к задаче фанерного  треста, методом разрешающих множителей был проведен А.И. Юдиным. Абрам Исакович Юдин был тогда моим аспирантом по функциональному анализу. Очень способный молодой ученый, погиб на фронте в начале войны в 1941 году.  

Этот  расчет он выполнил самостоятельно и  квалифицированно, но специально этими  проблемами не заинтересовался.  

М.К. Гавурина я привлек к работе в 1940 году, в  связи с рассмотрением транспортной задачи. Наша работа, опубликованная в 1949 году, была написана фактически в  конце 1940 года и тогда же докладывалась  нами в нескольких учреждениях, в  том числе в секции математики ленинградского Дома ученых.  

Абстрактный вариант транспортной задачи - работа о перемещении масс, включая теорему  о потенциале и основу метода потенциалов, опубликована мною в 1942 году в Докладах Академии наук СССР (переведена в 1958 году журналом Management Science).  

Других  советских работ по линейной оптимизации (кроме Толстого, которую Вы знаете) не могу указать. Были некоторые работы по системам неравенств, например, работа Школьникова.

5) Каков  был резонанс на собраниях,  в которых Вы говорили о  значении этого класса экстремальных  задач? 

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

Некоторые из этих докладов вызвали попытки  практического применения этих методов. Отмечу начатую в 1940?41 гг. аспирантом Лен[инградского] политехнического института А.Ф. Метсом работу по использованию метода разрешающих множителей для загрузки прокатных станов, прерванную войной. Эта работа была опубликована им позднее - в 50х годах, а фактически широкое применение методов линейного программирования в этой задаче началось в 1960­х годах.  

Первое  доведенное до использования применение касается рационального раскроя, относится  к 1948–1950 годам (книга моя и В.А. Залгаллера).  

Применения  в технико-экономических проблемах встречали скорее трудности и неверие, чем принципиальные возражения. С последними пришлось встретиться по отношению к применениям в плановоэкономических вопросах. Эта дискуссия отражена в печати (например, «Математики и экономисты за круглым столом», 1965).

6) Вывели  ли Вы Лагранжевский алгорифм для решения экстремальных задач с дополнительными условиями посредством переработки Вашего алгорифма?

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

7) Каковы  были Ваши контакты с А.Н.  Толстым? 

Я не встречался с ним. С одной из его статей, которая цитируется в моей работе с М.К. Гавуриным, я познакомился уже в процессе работы над темой. В работе А.Н. Толстого имеется ряд  практических приемов решения задачи, но недостаточно эффективных и не универсальных. Общая характеристика оптимального плана транспортировки  и эффективные универсальные  методы были даны впервые в указанных  наших работах (в 1940 году).  

Впоследствии  в послевоенное время в 1947–48 гг. я знакомился с работами по планированию перевозок, которые велись в Министерстве путей сообщения. Работы по реализации оптимальных планов перевозок методами линейного программирования, в частности  на основе наших работ (на автотранспорте и других видах), начались в конце 50х годов.

8) Как  Вы оцениваете сами значение  Ваших работ для линейной оптимизации? 

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

Я Вам  посылаю мои биографии, опубликованные в связи с моим 50летием и 60летием, а также некоторые статьи, написанные в связи с этим. В частности, содержательную статью покойного Ал. Л. Вайнштейна в связи с 25летием линейного программирования. Посылаю также свою фотографию. Просил М.К. Гавурина также послать фотографию Вам.

 С  уважением 

Л. Канторович

24.2.75 г.