Реферат: Исторический обзор экономико-математических методов и моделей

Теория воспроизводства Маркса позволила «развязать» ряд теоретических трудностей, проявившихся в полемике вокруг закона Сэя, и на многие десятилетия предвосхитила формирование таких разделов экономической теории, как моделирование экономического роста и анализ межотраслевых связей методом «затраты - выпуск».

6. Антуа́н Огю́ст Курно́ (фр. <#"704572.files/image002.gif">

в форме распределения продукции допускается построение уравнений в форме потребления продукции

где - материальные затраты j-й потребляющей отрасли; Vj + mj - ее чистая продукция; Vj - сумма оплаты труда; mj - чистый доход - прибыль.

………………………………………………………………………….

Это преобразование системы(1) приводит ее к обычной математической форме системы n линейных уравнений с n неизвестными х1, х2, … , хn (или у1, у2, … , уn) при заданных значениях коэффициентов аij и величин у1, у2, … , уn (или х1, х2, … , хn).

Коэффициенты называются коэффициентами прямых затрат. Для всех отраслей их задают в виде матрицы:

Коэффициенты прямых затрат в натуральном балансе означают технологические нормы расхода продукта i на производство единицы продукта j (например, расход сахара на банку плодово-ягодных консервов или на килограмм мороженного, киловатт-часов электроэнергии и тонн угля на один автомобиль и т.д.). в стоимостном балансе коэффициенты аij означают затраты отрасли I на каждый рубль валовой продукции отрасли j.

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

В системе уравнений (3) все неизвестные х1, х2, … , хn перенесем в левую часть уравнения ми получим новую фору записи системы уравнений межотраслевого баланса:

Модель межотраслевого баланса (5) имеет простую матричную форму записи (Е - А) Х = У и позволяет решить следующие задачи:

) определить конечный объем конечной продукции отраслей у1, у2, уn по заданным объемам валовой продукции у1, у2, … , уn (в матричной форме У = (Е - А) Х);

) по заданной матрице коэффициентов прямых затрат А определить матрицу коэффициентов полных затрат Р, элементы которой служат важными показателями для планирования развития отраслей (в матричной форме Р = (Е - А)-1);

) определить объемы валовой продукции отраслей х1, х2, … , хn по заданным объемам конечной продукции у1, у2, … , уn (в матричной форме Х = (Е - А)-1 У = Р У );

) по заданным объемам конечной или валовой продукции отраслей х1, х2, … , хn определить оставшиеся n объемов.

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

Для того чтобы матрица коэффициентов прямых материальных затрат А была продуктивной, необходимо и достаточно, чтобы выполнялось одно из перечисленных ниже условий:

1.       матрица (Е - А) неотрицательно обратима, т.е. существует обратная матрица (Е - А)-1 0;

2.       матричный ряд Е + А + А2 + А3 +….= сходится, причем его сумма равна обратной матрице (Е - А)-1;

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

.        все главные миноры матрицы (Е - А), т.е. определители матриц, образованные элементами первых строк столбцов этой матрицы, порядка от 1 до n, положительны.

Более простым способом проверки продуктивности матрицы А является ограничение на величину ее нормы. Если норма матрицы А строго меньше единицы, то эта матрица продуктивна. Данное условие является достаточным, но не необходимым условием продуктивной.

. История зарождения и создания линейного программирования

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

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

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

В автобиографии, представленной в Нобелевский комитет, Леонид Витальевич Канторович рассказывает о событиях, случившихся в 1939 году. К нему, 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда. Поэтому простой перебор вершин не годился. Леонид Витальевич писал: “оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков… Это настойчиво побудило меня к поиску эффективного метода их решения”. И уже летом 1939 года была сдана в набор книга Л.В.Канторовича “Математические методы организации и планирования производства”, в которой закладывались основания того, что ныне называется математической экономикой.

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

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

Примерно в это время Купманс узнал, что еще до войны в далекой России уже было сделано нечто похожее на разработку начал линейного программирования. Как легко было бы Данцигу и Купмансу проигнорировать эту информацию! Маленькая книжица, изданная ничтожным тиражом, обращенная даже не к экономистам, а к организаторам производства, с минимумом математики, без четко описанных алгоритмов, без доказательств теорем - словом, стоит ли принимать такую книжку во внимание… Но Купманс настаивает на переводе и издании на западе книги Канторовича. Его имя и идеи становятся известны всем. Воздадим должное благородству американского ученого!

А самому Леониду Витальевичу - как естественно было бы ему, испытав первые грозные удары ретроградов, остеречься от “грехов” молодости, забыть про всю эту экономику и вернуться к математике. Но Л.В.Канторович продолжает писать математические работы, навеянные экономическими идеями, участвует и в конкретных разработках на производстве. При этом (одновременно с Данцигом, но, не зная его работ) он разрабатывает метод, позже названный симплекс-методом. Как только в 50-е годы образуется маленький просвет, и кое-что из запретного становится возможным, он организует группу студентов на экономическом факультете ЛГУ для обучения методам оптимального планирования. А, начиная с 1960 года, Леонид Витальевич занимается только экономической и связанной с нею математической проблемами. Его вклад в этой области был отмечен Ленинской премией в 1965 году (присуждена ему совместно с В.С.Немчиновым и В.В.Новожиловым) и, как уже говорилось, Нобелевской премией в 1975 году.

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

Общей задачей математического программирования называется задача нахождения глобального максимума функции f (x) при ограничениях

х k R,(x) $ 0, i = 1, 2, _, m,

где R - некоторое непустое подмножество n-мерного евклидова пространства, f (x), gi(x) - функции от n переменных.

Если ввести множество

= {x k R | gi(x) $ 0, i = 1, 2, _, m},

то кратко эту задачу можно записать как задачу нахождения х0, для которого

Множество Х называется допустимым множеством или множеством допустимых планов, а вектор х0 - решением или оптимальным планом.

Вообще говоря, в задаче математического программирования могут быть одновременно ограничения типа равенств и неравенств, однако такую задачу нетрудно преобразовать к указанному виду, так как ограничение типа равенства g(x) = 0 эквивалентно двум ограничениям типа неравенства g(x) $ 0 и g(x) # 0, а ограничения типа меньше или равно преобразуются в ограничения больше или равно умножением на -1. Также нет необходимости рассматривать отдельно задачу на минимум, так как она сводится к задаче на максимум путем умножения целевой функции f (x) на -1.

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

Частным случаем задачи (4) является задача линейного программирования, для которой функции f (x), gi(x) являются линейными, а множество R - неотрицательным ортантом. Таким образом, задача линейного программирования состоит в нахождении максимума линейной функции f (x) на многогранном множестве Х. При этом для нахождения максимума достаточно перебрать вершины множества Х, число которых конечно. Методы линейной алгебры позволяют достаточно эффективно описывать эти вершины, что и используется в общем методе решения задач линейного программирования - симплекс-методе, реализующем направленный перебор вершин [ 1].

Другой важный частный случай задачи (4) - задача выпуклого программирования, для которой множество Х является выпуклым, а функция f (x) - вогнутой (для задачи на минимум выпуклой). Для выпуклости Х достаточно выпуклости множества R и вогнутости функций gi(x).

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

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

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

(x, y0) # F (x0, y0) # F (x0, y) "x k R, y k Y.

Теорема двойственности. Если функция Лагранжа F (x, у) для задачи (4) имеет седловую точку (x0, у0) на прямом произведении множеств R i Y, то справедливо соотношение двойственности (7), причем х0 является решением задачи (4), а у0 - решением двойственной задачи.

Соотношение двойственности позволяет свести решение задачи (4) к решению двойственной задачи, которая иногда оказывается проще. Например, двойственная задача к задаче линейного программирования тоже является линейной, причем она может иметь меньшую размерность, что позволяет строить более эффективные методы решения (на этой идее основан двойственный симплекс-метод, см. [1]). Кроме того, соотношение двойственности позволяет установить сам факт существования решения (например, наличие хотя бы по одному допустимому плану у двойственных задач линейного программирования гарантирует существование оптимальных планов), проанализировать чувствительность решения к малым изменениям параметров задачи.