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

Обновлено: 02.07.2024

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

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

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

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

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

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

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

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

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

Инструментарий этого направления Канторович и его ученики довели до практического применения, он выявлял разные классы задач — от раскройки материала и выбора оборудования до задач народнохозяйственного уровня, проблем инноваций и технического прогресса.

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

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

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

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

"В 1959 г. ученому поручили найти оптимальные тарифы такси в пределах страны. Математик с 20 сотрудниками, детально проанализировав огромный массив данных, за неделю выдал свои рекомендации. В частности, предложил снизить тариф и ввести небольшую плату за посадку. Новые тарифы были внедрены и использовались до 1990-х гг.".

Интересно, по каким правилам после 90-ых стали взимать плату за проезд не только на такси, но и на остальных видах транспорта.

А по диаметрально противоположным: по тем, по каким они все набивают свою мошну. Когда же она лопнет у них?!
Спасибо, Анатолий, за внимание и за такие своевременные раздумья!

Портал Проза.ру предоставляет авторам возможность свободной публикации своих литературных произведений в сети Интернет на основании пользовательского договора. Все авторские права на произведения принадлежат авторам и охраняются законом. Перепечатка произведений возможна только с согласия его автора, к которому вы можете обратиться на его авторской странице. Ответственность за тексты произведений авторы несут самостоятельно на основании правил публикации и законодательства Российской Федерации. Данные пользователей обрабатываются на основании Политики обработки персональных данных. Вы также можете посмотреть более подробную информацию о портале и связаться с администрацией.

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

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

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

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

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

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

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

Только примерно через 10 лет метод линейного программирования в другой форме был переоткрыт в США. Первые статьи по линейному программированию были опубликованы в США лишь в 1949 г. В них американский ученый Дж.Б.Данциг выступил тогда с изложением своего симплексного метода. Симплексный метод Дж.Б. Данцига имеет очень много общего с методом последовательного улучшения плана, применявшимся в дальнейшем (после 1939 г.) Л.В. Канторовичем и его сотрудниками для решения ряда практических задач, представляющих конкретную реализацию метода разрешающих множителей. Однако есть и отличия их в некоторых существенных частях.

Еще до Л.В. Канторовича в нашей стране были опубликованы работы, которые можно считать зародышами линейного программирования. Так, в 1930 г. советские экономисты-транспортники (А.Н. Толстой и др.) для построения оптимального плана перевозок составили транспортную задачу в сетевой форме и решили ее без математического обоснования, применяя метод последовательного улучшения плана. В 1941 году Хичкок поставил транспортную задачу.

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

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

Несколько позднее (в 1951г.) Дж.Б.Данцигом был разработан аналогичный метод, получивший название модифицированного распределительного метода. Это название является общим и относится по существу к целой группе близких друг другу методов, включающей как частные виды симплексный метод Дж.Б. Данцига, метод разрешающих слагаемых А.Л. Лурье и др.

В 1958 г. советский ученый А.Л. Лурье разработал метод разрешающих слагаемых для решения транспортных задач.

В 50-е годы кроме различных методов и их модификаций для решения задач линейного программирования появляется целый ряд работ, в которых излагаются методы нелинейного и динамического программирования. Так, в 1951 г. американские ученые Х. Кун и А. Таккер опубликовали работу по решению нелинейных задач. В 1954 г. А. Чарнс и Лемке разработали и опубликовали метод решения задач с сепарабельной выпуклой целевой функцией и линейными ограничениями. В этом же году появляются работы по методам целочисленного линейного программирования. К ним относится и метод Го- мори, опубликованный в США в 1958 г.

Также в 50-е годы американским математиком Р. Беллманом разрабатываются методы динамического программирования, появляется ряд работ, посвященных квадратичному программированию, например работы Е. Баранкина, Р. Дорфмана, Е. Била и др.

Внедрение экономико-математических методов и ПК создаёт реальную научную базу совершенствования планирования.

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

$c:\users\иван\downloads\linear.jpg$

2. Методы линейного программирования.

2.1. Симплекс-метод.

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

Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый также полиэдральным комплексом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

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

2.2. Двухфазный симплекс-метод.

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

Различия между дополнительными и вспомогательными переменными.

После того, как было модифицировано условие, создаётся вспомогательная целевая функция. Если вспомогательные переменные были обозначены, как >, > , то вспомогательную функцию определим, как

> ^y_\to min>

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

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

МЕТОД ВЕТВЕЙ И ГРАНИЦ

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

Метод ветвей и границ впервые предложили в 1960 году Аилсой Ленд и Элисон Дойг для решения задач целочисленного программирования .

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

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

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

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

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

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

Дело в том, что отказавшись после окончания университета по некоторым причинам от аспирантуры, я работал в военно-морском ВЦ, и заинтересовался задачей многомерного наилучшего приближения как прикладник. Одной из моих задач в этом ВЦ было представление таблиц стрельбы в ЭВМ, и я предложил аппроксимировать их вместо того, чтобы хранить в памяти ЭВМ. Я сформулировал некоторое обобщение задачи о наилучшем приближении, а именно, о кусочно полиномиальном наилучшем приближении (ни о каких сплайнах тогда нам известно не было) для функций нескольких переменных. Позже, когда я уже стал работать в университете, в 60-х гг. этой задачей занимались мои первые дипломанты. Еще позже была написана подробная статья об этом.

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

Школа численных методов линейного программирования в СССР была исключительно сильной, и в этом безусловная заслуга Л.В. и двух его основных помощников первой поколения -- В.А.Залгаллера и Г.Ш.Рубинштейна, а позже И.В.Романовского и его группы, В.Л.Булавского, в Москве -- Д.Б.Юдина и Е.Г.Гольштейна и др. В последующем с развитием вычислительной и программистской техники численное решение любых задач разумной размерности стало доступным.

В) Метрика Канторовича.

Однажды весной 1957 г. Г.Ш.Рубинштейн рассказал мне, что он наконец понял, как можно использовать теорему Л.В. о задаче Монжа (теперь ее называют задачей Монжа - Канторовича), доказанную им в заметке ДАН 1942 г. - а именно, как метрику Канторовича, т.е. оптимальное значение целевого функционала в транспортной задаче, использовать для введения нормы в пространстве мер и как критерий Л.В. становится теоремой двойственности с пространством функций Липшица. По сути дела, это было важным методическим замечанием, так как сама метрика уже была описана в заметке Л.В. Но именно эта работа Л.В. и Г.Ш., появившаяся в Вестнике ЛГУ в 1958 г., в выпуске, посвященном Г.М.Фихтенгольцу, содержала общую теорию знаменитой теперь метрики, назывемой иногда метрикой Канторовича-Рубинштейна, или транспортной.

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

С тех пор я превратился в постоянного пропагандиста этой замечательной метрики, и убедил очень многих математиков наших и зарубежных, в приоритете Л.В. и в важности этой работы. Она переоткрывалась огромное число раз и потому имеет очень много названий (метрика Вассерштейна, Орнштейна и т.д., не знавших о работе Л.В.) а сам метод ее введения известен как спаривание (coupling), как метода фиксированных маргинальных мер и т.д. Ее применения обширны и в самой математике, и в статфизике, и в математической статистике, в эргодической теории и в других приложениях. О ней написаны книги, которые далеко не исчерпывают всех ее сторон. Весьма близки к ней метрика Леви - Прохорова - Скорохода, популярная в теории вероятностей. Возможность дальнейшего обобщения этой метрики для широкого круга задач оптимизации была понята несколько позже, этому посвящены одна моя работа в "Успехах" 1970 г. и ее развитие в статье с М.М.Рубиновым.

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

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

Г) Связи с вариационным исчисленим и множителями Лагранжа.

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

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

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

Я занялся ими в середине 60-х годов, когда стал обдумывать популярные тогда работы по инвариантным формулировкам механики (Арнольд, Годбийон, Марсден и др.). Увидев в неголономной механике -- падчерице классической механики -- нетривиальную оптимизационную задачу, я понял, как ее поставить в современной форме. В те годы у нас был молодежный образовательный семинар в ЛОМИ -- по дифференциальной геометрии, теории представлений, группам Ли и всему остальному (Л.Д.Фаддеев, Б.Б.Венков, я и др.).

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

Д) Линейные модели и марковские процессы.

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

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

Е) Глобализация линейного программирования.

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

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

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

Ж) Линейное программирование и методы вычислений.

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

3. Л.В. и подготовка кадров.

Одна из важных инициатив Л.В. того периода - начало подготовки кадров математиков-экономистов. Ряд дипломантов и учеников по этой теме у Л.В. были еще в 50-х, но в сравнении с другими многочисленными его занятиями и темами учеников в этой области было немного. Всерьез подготовка началась в 1959 году, когда был организован так называемый шестой курс на экономическим факультете ЛГУ для окончивших факультет, где слушатели знакомились с математической экономикой и идеями Л.В. Шестой курс кончали известные в дальнейшем экономисты - А.А.Анчишкин, С.С.Шаталин, И.М.Сыроежин и др. Этот курс (он существовал один год) стал центром математической переподготовки экономистов в то время.

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

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

Несколько позже (уже после отъезда Л.В. в Новосибирск, но при его участии) это же было сделано и на мат-мехе - сначала специальность "исследование операций" была создана в недрах вычислительной кафедры мат-меха (с 1961-62 гг), а позже (с 1970) организована кафедра исследования опреаций. В ее становлении на факультете основную роль играли М.К.Гавурин и И.В.Романовский, который с 60-х гг. вел свой оптимизационный семинар с уклоном в вычислительные аспекты.

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

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

Рекомендуем скачать другие рефераты по теме: зимой сочинение, 5 баллов рефераты.

ГОСТ

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

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

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

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

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

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

Использование методов с целью характеристики экономических явлений;
Для определения зависимости между ними.

Готовые работы на аналогичную тему

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

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

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

Характеристика метода линейного программирования

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

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

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

Линейное программирование применяется также при анализе переменных величин, когда имеют место определенные ограничивающие факторы.

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

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

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

Общая задача линейного программирования

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

В каждой задаче элементы решения – это ряд неотрицательных переменных $x_1, x_2,…, x_n$. Следует так выбирать значения данных переменных, чтобы:

Действовали некоторые ограничения вида линейных неравенств или же неравенств в отношении переменных $x_1, x_2,…, x_n$.
Линейная функция $f$ переменных являлась максимумом (минимумом).

Общая задача линейного программирования – это задача, где оптимизируемая функция цели является линейной комбинацией известных коэффициентов $c_j$ и неизвестных переменных $x_j$ вида:

Рисунок 1. Функция. Автор24 — интернет-биржа студенческих работ

Функция $f$ также называется целевой функцией или же критерием эффективности.

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

Читайте также: