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

Размещено на http://www.allbest.ru/

Оглавление

Введение

1. Предпосылки возникновения линейного программирования

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

Заключение

Литература

Введение

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

Линейное программирование является частным случаем математического программирования. Одновременно оно - основа нескольких методов решения задач целочисленного и нелинейного программирования.

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

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

1. Предпосылки возникновения линейного программирования

Задачи линейного программирования были первыми, подробно изученными задачами поиска экстремума функций при наличии ограничений типа неравенств. В 1820 г. Ж. Фурье (Fourier J.B.J.) и затем в 1947 г. Дж. Данциг (Dantzig G.B.) предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции -- симплекс-метод, ставший основным при решении задач линейного программирования.

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

Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 30-м годам ХХ столетия. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман, знаменитый математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя; советский академик, лауреат Нобелевской премии (1975 г.) Л.В. Канторович, сформулировавший ряд задач линейного программирования и предложивший (1939 г.) метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода.

В 1931 г. венгерский математик Б. Эгервари рассмотрел математическую постановку и решил задачу линейного программирования, имеющую название «проблема выбора», метод решения получил название венгерского метода.

Л.В. Канторовичем совместно с М.К. Гавуриным в 1949 г. разработан метод потенциалов, который применяется при решении транспортных задач. В последующих работах Л.В. Канторовича, В.С. Немчинова, В.В. Новожилова, А.Л. Лурье, А. Брудно, А.Г. Аганбегяна, Д.Б. Юдина, Е.Г. Гольштейна и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования, так и приложение ее методов к исследованию различных экономических проблем. Методам линейного программирования посвящено много работ зарубежных ученых. В 1941 г. Ф.Л. Хитчкок поставил транспортную задачу. Основной метод решения задач линейного программирования -- симплекс-метод -- был опубликован в 1949 г. Дж. Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Куна (Kuhn H. W.), Таккера (Tucker A.W.), Гасса (Gass S.I.), Чарнеса (Charnes A.), Била (Beale E.M.) и др.

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

Начиная с 1955 г. опубликовано много работ, посвященных квадратическому программированию (работы Била, Баранкина (Barankin E.) и Дорфмана (Dorfman R.), Франка (Frank M.) и Вольфа (Wolfe P.), Марковича (Markovitz H.) и др.). В работах Денниса (Dennis J.B.), Розена (Rosen J.B.) и Зойтендейка (Zontendijk G.) разработаны градиентные методы решения задач нелинейного программирования.

В настоящее время для эффективного применения методов математического программирования и решения задач на компьютерах разработаны алгебраические языки моделирования, представителями которыми являются AMPL и LINGO.

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

линейное программирование моделирование канторович

Леонид Витальевич Канторович (1912--1986) родился в Санкт-Петербурге в семье врача. Его выдающиеся способности проявились рано -- в 14 лет он поступил в Ленинградский государственный университет. Закончив ЛГУ за 4 года, он поступил в аспирантуру. В 1932 г. он становится доцентом, а в 1935 г. -- профессором ЛГУ. В 1935 г. ему присвоено звание доктора физико-математических наук без защиты диссертации. В 1958 г. он избран членом-корреспондентом АН СССР по экономике, а в 1964 г. -- академиком.

За разработку метода линейного программирования Леонид Витальевич Канторович (1912-1986) был (совместно с американским экономистом Т. Купмансом) удостоен Нобелевской премии в области экономики (1975 г.).

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

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

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

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

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

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

В данном случае имеются четыре потребителя (квадратики) и три поставщика (кружочки). Линии, соединяющие пункты, изображают маршруты поставок (транспортную сеть). Цифры внутри квадратиков показывают объемы спроса (со знаком минус), внутри кружочков - размеры предложения (со знаком плюс).

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

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

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

Усилиями экономистов-математиков была разработана система оптимального функционирования экономики (СОФЭ); строились модели эффективного распределения и оценки ресурсов.

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

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

Результаты своих исследований Канторович изложил в брошюре «Математические методы организации и планирования производства», опубликованной в 1939 г. в издательстве Ленинградского университета тиражом 1000 экземпляров. В ней, наряду с задачей фанерного треста, получившей впоследствии наименование станковой, рассматривались и другие проблемы: наиболее полное использование механизмов, максимальное уменьшение отходов, наиболее рациональное использование топлива, наилучшее выполнение плана строительства, наилучшее распределение посевной площади, наилучший план перевозок. Метод Канторовича был пригоден для решения всех этих задач.

Идеи Канторовича долго не признавались экономистами. Когда в 1939 г. он выступал с докладами о своей работе, ему возражали, что она «использует математические методы, а на Западе математическая школа в экономике -- средство апологетики капитализма». Во время одной из дискуссий известный в то время статистик Б.С. Ястремский сказал Канторовичу: «Вы говорите об оптимуме, и Парето говорит об оптимуме. А ведь Парето -- фашист!». В связи с этим при написании брошюры Канторович был вынужден максимально избегать экономической терминологии; не удалось также подробно раскрыть экономический смысл разрешающих множителей, в частности проблему их связи с системой цен.

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

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

В своей работе Канторович рассмотрел возражения против применения математики в технико-экономических расчетах. Эти возражения были связаны с тем, что многие обстоятельства учесть математически невозможно, для применения метода разрешающих множителей нужно иметь много данных, они неточны, эффект от расчетов составляет всего 4-5%, применение метода порой невозможно из-за организационных препятствий. Канторович же полагал, что с помощью его метода многое нужно учесть, что требуемые данные нужны и для нормальной плановой работы, поэтому их неточность не имеет большого значения. При массовом применении эффект от их использования был бы очень велик, даже если бы он составлял 1%.

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

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

В 1940 г. он опубликовал математический вариант некоторых своих результатов. Из частных задач прежде всего следует выделить транспортную задачу. Работа, содержавшая ее решения, была подготовлена Л.В. Канторовичем и М.К. Гавуриным в 1940 г., однако из-за негативного отношения экономистов к математике в этот период ее долгое время не удавалось опубликовать. Абстрактный вариант транспортной задачи был опубликован Канторовичем в 1942 г.

Заключение

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

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

Литература

1. История экономических учений: Учебное пособие / Под ред. А.Г. Худокормова. - М.: Изд-во МГУ, 1994. - Ч. II, гл. 30.

2. Канторович Л.В. Экономический расчет наилучшего использования ресурсов. - М.: Изд-во АН СССР, 1959.

3. Капустин В.Ф., Шабалин Г.В. Л.В. Канторович и экономико-математические исследования: итоги, проблемы, перспективы // Вестник Санкт-Петербургского университета. Сер. 5. Экономика. 1996. Вып. 2.

4. Пезенти А. Очерки политической экономии капитализма. В 2 т. - М.: Прогресс, 1976. Т. II, гл. 14.

5. Шаталин С.С. Функционирование экономики развитого социализма. - М.: Изд-во МГУ, 1982.

6. Шухов Н.С. Ценность и стоимость. - М.: Изд-во стандартов, 1994. - Ч. 2, вып. 1, гл. 8.

Размещено на Allbest.ru