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

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

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

1. Описание Евклидом

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

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

. Математика в древнем Египте

Древнейшие древнеегипетские математические тексты относятся к началу II тысячелетия до н. э. Математика тогда использовалась в астрономии, мореплавании, землемерии, при строительстве зданий, плотин, каналов и военных укреплений. Денежных расчётов, как и самих денег, в Египте не было. К сожалению, египтяне писали на папирусе, который сохраняется плохо, и поэтому наши знания о математике Египта существенно меньше, чем о математике Вавилона или Греции. Вероятно, она была развита лучше, чем можно представить, исходя из дошедших до нас документов - известно, что греческие математики учились у египтян.

Основные сохранившиеся источники: папирус Ахмеса или папирус Ринда (84 математические задачи) и московский математический папирус (25 задач), оба из Среднего царства, времени расцвета древнеегипетской культуры. Авторы текста нам неизвестны. Дошедшие до нас экземпляры - это копии, переписанные в период гиксосов. Носители научных знаний тогда именовались писцами и фактически были государственными или храмовыми чиновниками.

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

Полностью отсутствуют какие бы то ни было объяснения или доказательства. Искомый результат либо даётся прямо, либо приводится краткий алгоритм его вычисления.

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

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

. Математика Вавилона

Вавилоняне писали клинописными значками на глиняных табличках, которые в немалом количестве дошли до наших дней (более 500000, из них около 400 связаны с математикой). Поэтому мы имеем довольно полное представление о математических достижениях учёных Вавилонского государства. Отметим, что корни культуры вавилонян были в значительной степени унаследованы от шумеров - клинописное письмо, счётная методика и т. п.

Вавилонские математические тексты носят преимущественно учебный характер. Из них видно, что вавилонская расчётная техника была намного совершеннее египетской, а круг решаемых задач существенно шире. Есть задачи на решение уравнений второй степени, геометрические прогрессии. При решении применялись пропорции, средние арифметические, проценты. Методы работы с прогрессиями были глубже, чем у египтян. Линейные и квадратные уравнения решались ещё в эпоху Хаммурапи; при этом использовалась геометрическая терминология (произведение ab называлось площадью, abc - объёмом, и т.д.). Многие значки для одночленов были шумерскими, из чего можно сделать вывод о древности этих алгоритмов; эти значки употреблялись, как буквенные обозначения неизвестных в нашей алгебре. Встречаются также кубические уравнения и системы линейных уравнений. Венцом планиметрии была теорема Пифагора.

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

. Экономико-математические методы и модели

Как и всякое моделирование, экономико-математическое моделирование основывается на принципе аналогии, т.е. возможности изучения объекта посредством построения и рассмотрения другого, подобного ему, но более простого и доступного объекта, его модели.

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

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

. Экономико-статистические методы:

· экономическая статистика;

· математическая статистика;

· многофакторный анализ.

. Эконометрия:

· макроэкономические модели;

· теория производственных функций

· межотраслевые балансы;

· национальные счёта;

· анализ спроса и потребления;

· глобальное моделирование.

. Исследование операций (методы принятия оптимальных решений):

· математическое программирование;

· сетевое и планирование управления;

· теория массового обслуживания;

· теория игр;

· теория решений;

· методы моделирования экономических процессов в отраслях и на предприятиях.

. Экономическая кибернетика:

· системный анализ экономики;

· теория экономической информации.

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

· методы машинной имитации;

· деловые игры;

· методы реального экономического эксперимента.

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

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

Существуют следующие предпосылки использования методов экономико-математического моделирования.

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

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

. Теория воспроизводства К. Маркса

Своей теорией воспроизводства во II томе «Капитала» Маркс продолжил дело, начатое Экономической таблицей Ф. Кенэ: моделирование кругооборота общественного продукта.

Основу теории составляют схемы воспроизводства - абстрактные теоретические модели, построенные на целом ряде упрощающих предпосылок.

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

= с + v + m                                                                            (1)

где с - затраты постоянного капитала, соответствующие затратам средств производства, израсходованным при производстве данного товара;- затраты переменного капитала, соответствующие затратам на заработную плату рабочих;

т - прибавочная стоимость, составляющая конечный доход самих капиталистов.

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

Таким образом, для стандартного капитала в сфере производства (например, фермерского) будет справедливо следующее соотношение:

Рисунок

Во-вторых, экономика разделена на два сектора (подразделения): производство средств производства (подразделение - Q1,) и производство предметов потребления (II подразделение - Q2), в рамках которых создается весь общественный продукт. Таким образом, стоимость общественного продукта может быть представлена как сумма стоимости продуктов двух подразделений:

=C1 + V1 + М1                                                                      (2)= C2+V2 + M2                                                                  (3)

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

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

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

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

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]). Кроме того, соотношение двойственности позволяет установить сам факт существования решения (например, наличие хотя бы по одному допустимому плану у двойственных задач линейного программирования гарантирует существование оптимальных планов), проанализировать чувствительность решения к малым изменениям параметров задачи.

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

Теорема Куна-Таккера. Если задача (4) является задачей выпуклого программирования, удовлетворяющей условию Слейтера, то необходимым и достаточным условием оптимальности плана x0 k X является существование такого y0 k Y, что пара (x0, у0) является седловой точкой функции Лагранжа, то есть удовлетворяет (8).

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

Градиентные методы.

Рассмотрим сначала задачу максимизации функции f (x) без ограничений, то есть в случае, когда Х совпадает со всем пространством R n. Градиент функции f (x) обозначим f 1(х). Условие оптимальности в этом случае имеет вид, однако непосредственное решение системы уравнений (9) может оказаться чересчур сложным.

1(х) = 0

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

+ 1 = xk + ak f 1(xk), k = 1, 2, _

Число ak называют длиной шага или просто шагом. Если все ak равны между собой, то имеем процесс с постоянным шагом.

Процесс (10), лежащий в основе градиентных методов, представляет собой движение в сторону возрастания функции f (x), так как если f 1(хk) ? 0, то всегда можно выбрать ak так, что f (xk + 1) > f (xk). Существуют разные способы выбора ak . Вообще говоря, наилучшим является выбор такого ak , при котором обеспечивается максимальный рост функции f (x). Такое ak находится из условия

Градиентный метод поиска экстремума (10) с выбором шага по способу (11) называется методом скорейшего подъема (или спуска для задачи на минимум). Такой метод требует наименьшего числа итераций, но зато на каждом шаге приходится решать дополнительную задачу поиска экстремума (11) (правда, в одномерном случае). На практике часто довольствуются нахождением любого ak , обеспечивающего рост функции. Для этого берут произвольное ak и проверяют условие роста. Если оно не выполняется, то дробят ak до тех пор, пока это условие не будет выполнено (такое достаточно малое ak при f 1(хk) ? 0 существует всегда).

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

Если рассматривается задача максимизации f (x) при ограничениях, то есть когда Х не совпадает с R n, то непосредственное применение процесса (10) может привести к нарушению ограничений, даже если начальная точка x1 k X. Однако эту трудность можно преодолеть, например, если получаемую по формуле (10) очередную точку проектировать на множество Х. Если обозначить операцию проектирования х на множество Х через Рх(х), то соответствующий итеративный процесс имеет вид

хk + 1 = Рх(хk + ak f 1(хk))

Полученный метод носит название метода проекции градиента. Шаг ak в методе (12) может выбираться различными способами (например, как в методе скорейшего подъема). Стационарная точка этого процесса является решением задачи (4) в случае вогнутой функции f (x), а в общем случае требуется дополнительное исследование.

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

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

Если множество Х выпуклое, то хk + 1 k Х. Шаг ak выбирается из условия максимального роста функции f (x) или любым другим способом, обеспечивающим рост f (x). На практике обычно решают вспомогательную задачу не точно, а приближенно. В процессе (13) направление движения не совпадает с градиентом функции f (x) в точке хk , но определяется им, так как его компоненты берутся в качестве коэффициентов линейной целевой функции вспомогательной задачи.

Методы возможных направлений

Рассмотрим вариант метода возможных направлений применительно к задаче максимизации f (x) на множестве (3), где R = R n. Пусть мы имеем k-е приближение хk к решению этой задачи, и для построения следующего приближения поставим вспомогательную задачу: максимизировать u при ограничениях

б f 1(xk), aс $ u, бg1(xk), aс $ u,k Ik | a j | # 1, j = 1, 2, _, n,

где= {i | 1 # i # m, gi(xk) = 0}, a = (a1, _, an).

Эта задача представляет собой задачу линейного программирования в (n + 1)-мерном пространстве векторов (a, u). Множество планов замкнуто, ограничено и непусто, так как a = 0, u = 0 является допустимым планом. Значит, вспомогательная задача имеет решение (ak, uk), причем uk $ 0. Если uk > 0, то нетрудно показать, что направление ak является возможным направлением возрастания функции f (x), то есть точка xk + 1 = xk + akak при достаточно малом ak принадлежит множеству Х и обеспечивает большее значение функции f (x), чем хk . Выбор пары (аk, uk) с возможно большим значением uk при этом означает выбор допустимого направления, наиболее близкого к градиенту функции, то есть возможного направления с наибольшим ростом функции. Если uk = 0, то получается стационарная точка процесса, которая для задачи выпуклого программирования дает решение, а в общем случае требует дополнительного исследования.

Методы множителей Лагранжа

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

(x) = (g1(x), _, gm(x)), Y = {y | y $ 0}.

Проекция на множество Y определяется весьма просто:

(y) = (Z1 , _, Zm), Zi = max (yi , 0), i = 1, 2, _, m.

Если R - неотрицательный ортант, то проекция на него определяется аналогичным образом.

Методы второго порядка

До сих пор мы рассматривали методы первого порядка, то есть методы поиска экстремума, использующие первые производные. Фактически в этих методах производится линеаризация, связанная с заменой максимизируемой функции f (x) линейным членом разложения ее в ряд Тейлора. Но если функция дважды непрерывно дифференцируема, то можно использовать для ее аппроксимизации два члена ряда Тейлора. Использование такой аппроксимизации в итеративном процессе может повысить скорость сходимости.

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

(x) = б f 1(xk), x - xk с + 0,5 б f "(xk)(x - xk), x - xk с

на множестве Х. Пусть тогда следующее приближение строится по формуле Шаг ak можно выбирать разными способами, в частности можно положить ak = 1, тогда в качестве следующего приближения принимается просто решение вспомогательной задачи, то есть .

Для задачи без ограничений, когда Х = R n, метод Ньютона существенно упрощается. Действительно, в этом случае то есть

Значит, для нахождения надо решить систему линейных уравнений (14). Если матрица f "(xk) не вырождена, то имеем просто (при ak = 1)

Достоинством метода Ньютона является высокая скорость сходимости, которая с лихвой компенсирует усложнение вычислений на каждой итерации. Недостатком метода является то, что он сходится при весьма жестких предположениях.

Методы штрафных функций

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

Рассмотрим общую задачу математического программирования (4). Методы штрафных функций основаны на описании множества Х с помощью функций со специальными свойствами. Одна группа методов использует функции вида F(х, с), которые обладают следующими свойствами:

В качестве такой функции можно взять, например, квадратичную функцию штрафа которая является дифференцируемой, если дифференцируемы функции ограничений gi(x). Можно показать, что если f (x) и gi(x), i = 1, 2, _, m, непрерывны на замкнутом, ограниченном множестве R и Х ? , то

При этом если х0(сn) реализует максимум в правой части (15), то любая предельная точка последовательности {x0(сn)} есть решение задачи (4).

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

Недостатком методов штрафных функций является ухудшение свойств вспомогательных задач (в правой части (15)) при больших значениях сn , в частности чувствительность к ошибкам вычислений. Эти недостатки преодолены в некоторых вариантах штрафных функций, в которых можно ограничиться конечными значениями штрафных констант сn , а также в близких к ним методах модифицированной функции Лагранжа [2].

Более подробно с задачами и методами нелинейного программирования можно познакомиться в [3-5].

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

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

Заключение

математика равновесие богатство маркс

Характерной особенностью научно-технического прогресса в развитых странах является возрастание роли экономической науки.

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

Применение математики в экономической науке, дало толчок в развитии как самой экономической науке, так и прикладной математике, в части методов экономико-математической модели. Пословица говорит: «Семь раз отмерь - Один раз отрежь». Использование моделей есть время, силы, материальные средства. Кроме того, расчёты по моделям противостоят волевым решениям, поскольку позволяют заранее оценить последствия каждого решения, отбросить недопустимые варианты и рекомендовать наиболее удачные.

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

Первое направление - прогнозирование и ᴨȇрсᴨȇктивное планирование. Прогнозируются темпы и пропорции развития экономики, на их основе определяются темпы и факторы роста национального дохода, его распределение на потребление и накопление и т.д. Важным моментом является использование экономико-математических методов не только при составлении планов, но и в деле оᴨȇративного руководства по их реализации.

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

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

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

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

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

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