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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· теория игр;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

q= с + v + m (1)

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

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

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

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

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

Рисунок

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

Q1=C1 + V1 + М1 (2)

Q2 = C2+V2 + M2 (3)



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

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

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

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

6. Антуамн Огюмст Курном (фр. Cournot; 28 августа 1801, Гре -- 30 марта, 1877, Париж) -- французский экономист, философ и математик

Родился в Гре 28 августа 1801. Учился в лицее в Безансоне, в 1821 поступил в Высшую нормальную школу HYPERLINK Парижа, в 1823 получил степень лиценциата в области науки, в 1827 - в области права.

Родоначальник математического направления в политической экономии, был ректором академии в Гренобле, затем в Дижоне. Его теория случая совершенно оригинальна; он первый с успехом приложил математические методы к политической экономии. Его труды, особенно первые, не имели, однако, большого успеха. Ему принадлежат также «Des Institutions d'instruction publique en France» (П., 1864), интересные доклады математического содержания в «Journal» Crelle'я и других сборниках, издание мемуаров маршала Гувион-Сен-Сира (Париж, 1831) и писем Эйлера (Париж, 1842).

Главным вкладом Курно в экономическую науку является Исследование математических принципов теории богатства (1838).

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

7. Леон Вальрас (1834 - 1910) -- швейцарский экономист, основатель лозаннской школы, которая является ветвью математической школы

Экономической теорией увлекся благодаря работам О. Круно. С 1870 года работал на кафедре политической экономии в Лозаннском университете. Его основная работа называется «Элементы чистой политической экономии» (1874 г.). Л. Вальрас -- создатель общей статистической экономико-математической модели хозяйства страны, известной под названием системы общего экономического равновесия.

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

В 50 -- 60-е годы модель Вальраса преобразована средствами линейного программирования.

В модели рынков отражено следующее:

? определены основные условия соответствия спроса и предложения товаров;

? взаимосвязь между основными показателями производства и обмена представлена системой уравнений;

? все сделки на рынке совершаются одновременно;

? модель статична (предполагает неизменность запаса и разнообразия продуктов);

? идеальная информированность субъектов производства;

? решение задачи для всего народного хозяйства на экстремум.

Цель модели - вывести общие законы действия системы цен при наличии множества рынков.

Государство, по мнению Л, Вальраса, должно осуществлять следующие функции:

1. контролировать стабильность денег;

2. обеспечивать безопасность граждан;

3. сдерживать спекулятивные процессы;

4. поддерживать всеобщее образование граждан;

5. гарантировать социальную защиту рабочим;

6. способствовать функционированию эффективной конкуренции;

7. поощрять производство и потребление полезных вещей.

8. В государстве должен действовать принцип равенства возможностей при неравенстве фактического положения.

Вильфредо Парето (1848 - 1923) - итальянский экономист, профессор политической экономии Лозаннского университета, последователь Л. Вальраса. В 1906 году В. Парето опубликовал «Курс политической экономии».

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

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

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

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

8. Основы экономико-математических моделей

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

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

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

Теоретические основы межотраслевого баланса были разработаны в СССР в 1923--1924 гг. В 30-е гг. для изучения американской экономики американский экономист Василий Леонтьев применил метод анализа межотраслевых связей с привлечением аппарата линейной алгебры. Метод стал известен под названием «затраты -- выпуск».

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

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

х1 = х11 + х12 + … + х1n + 0у1;

х2 = х21 + х22 + … + х2n + у2;

………………………………………………

хn = хn1 + хn2 + … + хnn + уn.

Различают два вида баланса: стоимостной - по отраслям производства и натуральный - по видам продукции в натуральном выражении.

В стоимостном балансе переменные х1, х2, … , хn означают объемы валовой продукции первой, второй, …, n-ой отрасли, xij - объемы затрат i-й отрасли на производство продукции j-й отрасли, уi - конечный продукт, который не поступает в сферу текущего производственного потребления, а идет на конечное потребление (в личное и общественное, на накопление, экспорт, возмещение потерь и т.д.). Систему (1), которую учитывает структуру сложившихся взаимных затрат отраслей, можно назвать «экономической картой» народного хозяйства.

В натуральном балансе переменные х1, х2, … , хn означают объемы n видов производственных продуктов в натуральных единицах (автомобилей в штуках, угля в тоннах и т.д.). Величина xij означает объем потребления продукта I при производстве продукта j (угля при производстве автомобилей, электроэнергии при добыче угля и т.д.), а величина уi - конечный продукт - ту часть продукции, которая не используется в производственном потреблении.

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

В матричной форме системы уравнений (1) межотраслевой стоимостной и межпродуктовый натуральный балансы имеют одинаковое выражение. В том и другом случае общий объем продукции хi разделяется на объем производственного потребления - промежуточный продукт хi1, хi2, хin и объем непроизводственного потребления - конечный продукт уi, причем удельный вес их для разных отраслей стоимостного баланса и различных продуктов натурального баланса неодинаков.

Однако стоимостной баланс в отличие от натурального наряду с уравнениями

xj =

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

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

Сделаем преобразование системы уравнений (1) - каждое из слагаемых xij разделим и умножим на xj и обозначим



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

х k R,

gi(x) $ 0, i = 1, 2, _, m,

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

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

X = {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) является и глобальным максимумом (для выпуклой функции это справедливо для минимумов). Это и другие свойства задачи выпуклого программирования существенно облегчают ее решение, так как большинство численных методов обеспечивает нахождение только локальных экстремумов. Заметим, что задача линейного программирования является частным случаем выпуклого программирования, но свойство линейности столь специфично, что позволяет применять специальные методы.

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

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

F (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) может оказаться чересчур сложным.

f 1(х) = 0

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

xk + 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) возрастает (такое направление называется возможным направлением возрастания функции f (x)), и по нему совершается шаг. Фактически в методе проекции градиента и в методе условного градиента мы находим такие направления. Однако там исходным было определение градиента, а допустимое направление определялось по нему однозначно. В методах же возможных направлений исходным пунктом являются описание всех допустимых направлений и выбор из них такого, вдоль которого функция f (x) возрастает и желательно скорейшим образом.

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

б f 1(xk), aс $ u, бg1(xk), aс $ u,

i k Ik | a j | # 1, j = 1, 2, _, n,

где

Ik = {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. Получим процесс

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

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

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

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

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

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

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

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

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

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