Математические методы в экономике

Математические методы в экономике

Попова Н.В.

Тема 1. Экономико-математическое моделирование и его этапы

Экономико-математическое моделирование является неотъемлемой частью любого исследования в области экономики. Бурное развитие математического анализа, исследования операций, теории вероятностей и математической статистики способствовало формированию различного рода моделей экономики.     Математические модели  экономических  процессов и явлений более кратко можно назвать экономико-математическими моделями. Для классификации этих моделей используются разные основания.          По целевому  назначению  экономико-математические  модели делятся на теоретико-аналитические,  используемые в исследованиях общих свойств и закономерностей экономических  процессов, и прикладные,  применяемые  в решении конкретных экономических задач (модели экономического анализа,  прогнозирования, управления).     Экономико-математические модели могут предназначаться для исследования разных  сторон  народного хозяйства (в частности, его производственно-технологической, социальной, территориальной структур) и его отдельных частей.  При классификации моделей по исследуемым экономическим  процессам  и  содержательной проблематике можно выделить модели народного хозяйства в целом и его подсистем — отраслей, регионов и т.д., комплексы моделей производства, потребления,  формирования и распределения доходов, трудовых ресурсов,  ценообразования,  финансовых связей и т.п.         Остановимся более подробно на характеристике таких  классов экономико-математических моделей,  с которыми связаны наибольшие особенности методологии и техники моделирования.          В соответствии  с общей классификацией математических моделей они подразделяются на функциональные  и  структурные,  а также включают  промежуточные  формы  (структурно-функциональные). В исследованиях на народнохозяйственном уровне чаще применяются структурные модели,  поскольку для планирования и управления большое значение имеют взаимосвязи подсистем.       Типичными структурными  моделями являются модели межотраслевых связей. Функциональные модели широко применяются в  экономическом регулировании, когда  на  поведение объекта («выход») воздействуют путем изменения «входа».  Примером может служить  модель поведения потребителей  в условиях товарно-денежных отношений.      Один и тот же объект может описываться одновременно и структурой, и функциональной моделью. Так, например, для планирования отдельной отраслевой системы используется структурная  модель, а на  народнохозяйственном  уровне  каждая  отрасль может быть представлена функциональной моделью.          Выше уже показывались различия между моделями дескриптивными и нормативными.  Дескриптивные модели отвечают на вопрос: как это происходит?  или как это вероятнее всего может  дальше развиваться? т.е.  они только объясняют наблюдаемые факты или дают вероятный прогноз. Нормативные модели отвечают на вопрос: как это должно быть?  т.е. предполагают целенаправленную деятельность. Типичным примером нормативных моделей являются  модели оптимального  планирования,  формализующие  тем  или иным способом цели экономического развития,  возможности и средства их достижения.          Применение дескриптивного подхода в моделировании  экономики объясняется  необходимостью  эмпирического выявления различных зависимостей в экономике,  установления  статистических закономерностей экономического   поведения  социальных  групп, изучения вероятных путей развития каких-либо процессов при неизменяющихся условиях или протекающих без внешних воздействий.     Примерами дескриптивных  моделей   являются   производственные функции и функции покупательского спроса, построенные на основе обработки статистических данных.     Является ли экономико-математическая модель дескриптивной или нормативной, зависит не только от ее математической структуры, но от характера использования этой модели. Например, модель межотраслевого баланса дескриптивна, если она используется для анализа пропорций прошлого периода. Но эта же математическая модель становится нормативной,  когда  она  применяется для расчетов сбалансированных вариантов развития народного хозяйства, удовлетворяющих  конечные  потребности  общества  при плановых нормативах производственных затрат.          Многие экономико-математические модели сочетают  признаки дескриптивных и нормативных моделей.  Типична ситуация,  когда нормативная модель сложной структуры объединяет отдельные блоки, которые являются частными дескриптивными моделями.  Например, межотраслевая модель может включать  функции  покупательского спроса, описывающие поведение потребителей при изменении доходов. Подобные примеры характеризуют тенденцию эффективного сочетания дескриптивного и нормативного подходов к моделированию экономических процессов.  Дескриптивный подход широко применяется в имитационном моделировании.          По характеру отражения причинно-следственных связей  различают модели  жестко  детерминистские  и модели,  учитывающие случайность и неопределенность. Необходимо различать неопределенность, описываемую вероятностными законами,  и неопределенность, для описания которой законы теории вероятностей  неприменимы. Второй  тип  неопределенности гораздо более сложен для моделирования.          По способам отражения фактора времени экономико-математические модели делятся на статические и динамические.  В статических моделях  все зависимости относятся к одному моменту или периоду времени.  Динамические модели характеризуют  изменения экономических процессов во времени. По длительности рассматриваемого периода времени различаются модели краткосрочного  (до года), среднесрочного (до 5 лет), долгосрочного (10-15 и более лет) прогнозирования и планирования.  Само  время  в  экономико-математических моделях  может  изменяться  либо непрерывно, либо дискретно.          Модели экономических  процессов  чрезвычайно разнообразны по форме математических зависимостей.  Особенно важно выделить класс линейных моделей,  наиболее удобных для анализа и вычислений и получивших вследствие этого  большое  распространение.     Различия между линейными и нелинейными моделями существенны не только с математической точки зрения,  но и в теоретико-экономическом отношении,  поскольку  многие зависимости в экономике носят принципиально нелинейный характер: эффективность использования ресурсов при увеличении производства, изменение спроса и потребления населения при увеличении производства, изменение спроса и потребления населения при росте доходов и т.п. Теория «линейной экономики» существенно отличается от  теории  «нелинейной экономики». От того, предполагаются ли множества производственных возможностей подсистем (отраслей, предприятий) выпуклыми или же невыпуклыми,  существенно зависят выводы о возможности сочетания централизованного  планирования  и  хозяйственной самостоятельности экономических подсистем.          По соотношению экзогенных и эндогенных переменных,  включаемых в модель, они могут разделяться на открытые и закрытые. Полностью открытых моделей не существует; модель должна содержать хотя  бы  одну эндогенную переменную.  Полностью закрытые экономико-математические модели, т.е. не включающие экзогенных переменных, исключительно редки; их построение требует полного абстрагирования от «среды»,  т.е. серьезного огрубления реальных экономических систем, всегда имеющих внешние связи. Подавляющее большинство экономико-математических  моделей  занимает промежуточное положение  и  различаются  по степени открытости (закрытости).          Для моделей народнохозяйственного уровня важно деление на агрегированные и детализированные.          В зависимости  от того,  включают ли народнохозяйственные модели пространственные факторы и  условия  или  не  включают, различают модели пространственные и точечные.          Таким образом, общая классификация экономико-математических моделей включает более десяти основных признаков. С развитием экономико-математических исследований проблема  классификации применяемых моделей усложняется. Наряду с появлением новых типов моделей (особенно смешанных типов) и новых признаков их классификации  осуществляется  процесс  интеграции  моделей разных типов в более сложные модельные конструкции.     Основные этапы процесса моделирования уже рассматривались выше. В различных отраслях знаний,  в том числе и в экономике, они приобретают свои специфические черты.  Проанализируем последовательность и содержание этапов одного цикла экономико-математического моделирования.          1. Постановка  экономической  проблемы  и ее качественный анализ. Главное здесь — четко сформулировать сущность  проблемы, принимаемые  допущения и те вопросы,  на которые требуется получить ответы. Этот этап включает выделение важнейших черт и свойств моделируемого  объекта  и абстрагирование от второстепенных; изучение структуры объекта  и  основных  зависимостей, связывающих его  элементы;  формулирование  гипотез  (хотя  бы предварительных), объясняющих поведение и развитие объекта.          2. Построение математической модели.  Это — этап формализации экономической проблемы,  выражения ее в виде  конкретных математических зависимостей  и отношений (функций,  уравнений, неравенств и т.д.). Обычно сначала определяется основная конструкция (тип) математической модели, а затем уточняются детали этой конструкции (конкретный перечень переменных и параметров, форма связей). Таким образом, построение модели подразделяется в свою очередь на несколько стадий.          Неправильно полагать, что чем больше фактов учитывает модель, тем она лучше «работает» и дает лучшие результаты. То же можно сказать  о  таких характеристиках сложности модели,  как используемые формы математических зависимостей (линейные и нелинейные), учет факторов случайности и неопределенности и т.д.     Излишняя сложность и громоздкость  модели  затрудняют  процесс исследования. Нужно  учитывать  не только реальные возможности информационного и математического обеспечения,  но и сопоставлять затраты  на моделирование с получаемым эффектом (при возрастании сложности модели прирост затрат может превысить  прирост эффекта).          Одна из важных особенностей математических моделей -  потенциальная возможность  их использования для решения разнокачественных проблем. Поэтому, даже сталкиваясь с новой экономической задачей,  не нужно стремиться «изобретать» модель; вначале необходимо попытаться применить для решения  этой  задачи уже известные модели.          В процессе построения модели осуществляется  взаимосопоставление двух  систем научных знаний — экономических и математических. Естественно стремиться к тому,  чтобы  получить  модель, принадлежащую  хорошо  изученному  классу математических задач. Часто это удается сделать  путем  некоторого  упрощения исходных предпосылок  модели,  не искажающих существенных черт моделируемого объекта. Однако возможна и такая ситуация, когда формализация экономической проблемы приводит к неизвестной ранее математической структуре.  Потребности экономической науки и практики в середине ХХ в.  способствовали развитию математического программирования, теории игр, функционального анализа, вычислительной математики. Вполне вероятно, что в будущем развитие экономической науки станет важным стимулом для  создания новых разделов математики.     3. Математический анализ модели.  Целью этого этапа является выяснение  общих свойств модели.  Здесь применяются чисто математические приемы исследования.  Наиболее важный момент — доказательство существования решений в сформулированной модели (теорема существования). Если удастся доказать, что математическая задача не имеет решения,  то необходимость в последующей работе по первоначальному варианту  модели  отпадает и  следует скорректировать  либо постановку экономической задачи, либо способы ее математической формализации. При аналитическом исследовании модели выясняются такие вопросы,  как,  например, единственно ли решение,  какие переменные (неизвестные)  могут входить в решение,  каковы будут соотношения между ними, в каких пределах и в зависимости от каких исходных условий они изменяются, каковы  тенденции их изменения и т.д.  Аналитической исследование модели по сравнению  с  эмпирическим  (численным) имеет то  преимущество,  что  получаемые выводы сохраняют свою силу при различных конкретных значениях внешних  и  внутренних параметров модели.          Знание общих свойств модели имеет столь важное  значение, часто ради  доказательства подобных свойств исследователи сознательно идут на идеализацию первоначальной модели.  И все  же модели сложных  экономических объектов с большим трудом поддаются аналитическому исследованию.  В тех случаях, когда аналитическими методами не удается выяснить общих свойств модели, а упрощения модели приводят к недопустимым результатам,  переходят к численным методам исследования.     4. Подготовка исходной информации. Моделирование предъявляет жесткие  требования  к системе информации.  В то же время реальные возможности получения информации  ограничивают  выбор моделей, предназначаемых для практического использования.  При этом принимается во внимание не только принципиальная  возможность подготовки информации (за определенные сроки), но и затраты на подготовку  соответствующих  информационных  массивов.     Эти затраты не должны превышать эффект от использования дополнительной информации.          В процессе  подготовки информации широко используются методы теории вероятностей,  теоретической и математической статистики. При  системном экономико-математическом моделировании исходная информация,  используемая в одних  моделях,  является результатом функционирования других моделей.     5. Численное решение. Этот этап включает разработку алгоритмов для численного решения задачи,  составления программ на ЭВМ и непосредственное проведение  расчетов.  Трудности  этого этапа обусловлены,  прежде всего, большой размерностью экономических задач,  необходимостью обработки значительных  массивов информации.     Обычно расчеты по экономико-математической  модели  носят многовариантный характер.  Благодаря  высокому  быстродействию современных ЭВМ удается проводить  многочисленные  «модельные» эксперименты, изучая  «поведение» модели при различных изменениях некоторых условий.  Исследование,  проводимое  численными методами, может существенно дополнить результаты аналитического исследования, а для многих моделей оно является единственно осуществимым. Класс экономических задач,  которые можно решать численными методами,  значительно шире,  чем класс задач, доступных аналитическому исследованию.     6. Анализ численных результатов и их применение.  На этом заключительном этапе цикла встает вопрос о правильности и полноте результатов моделирования,  о степени практической применимости последних.     Математические методы проверки могут выявлять  некорректные построения  модели  и  тем самым сужать класс потенциально правильных моделей.  Неформальный анализ теоретических выводов и численных результатов, получаемых посредством модели, сопоставление их с имеющимися знаниями и  фактами  действительности также позволяют обнаруживать недостатки постановки экономической задачи, сконструированной математической модели, ее информационного и математического обеспечения.     Взаимосвязи этапов.  На рис.1 изображены связи между этапами одного   цикла  экономико-математического  моделирования.     Обратим внимание на возвратные связи этапов,  возникающие вследствие того,  что  в  процессе исследования обнаруживаются недостатки предшествующих этапов моделирования.     Уже на этапе построения модели может выясниться, что постановка задачи противоречива или приводит  к  слишком  сложной математической модели.  В  соответствии с этим исходная постановка задачи корректируется. Далее математический анализ модели (этап  3) может показать,  что небольшая модификация постановки задачи или ее формализации дает интересный аналитический результат.     Наиболее часто необходимость  возврата  к  предшествующим этапам моделирования возникает при подготовке исходной информации (этап 4).  Может обнаружиться, что необходимая информация отсутствует или  же  затраты  на ее подготовку слишком велики. Тогда приходится возвращаться к постановке задачи и ее  формализации, изменяя их так,  чтобы приспособиться к имеющейся информации.     Поскольку экономико-математические   задачи   могут  быть сложны по своей структуре, иметь большую размерность, то часто случается, что известные алгоритмы и программы для ЭВМ не позволяют решить задачу в первоначальном виде.  Если невозможно в короткий срок разработать новые алгоритмы и программы,  исходную постановку задачи и модель упрощают:  снимают и объединяют условия, уменьшают число факторов,  нелинейные соотношения заменяют линейными, усиливают детерминизм модели и т.д.     Недостатки, которые не удается исправить на промежуточных этапах моделирования, устраняются в последующих циклах. Но результаты каждого  цикла  имеют и вполне самостоятельное значение. Начав исследование с  построения  простой  модели,  можно быстро получить полезные результаты,  а затем перейти к созданию более совершенной модели,  дополняемой  новыми  условиями, включающей уточненные математические зависимости.     По мере развития и  усложнения  экономико-математического моделирования его отдельные этапы обособляются в специализированные области исследований, усиливаются различия между теоретико-аналитическими и прикладными моделями,  происходит дифференциация моделей по уровням абстракции и идеализации.     Теория математического  анализа  моделей экономики развилась в особую ветвь современной  математики  -  математическую экономику. Модели,  изучаемые в рамках математической экономики, теряют непосредственную связь с экономической реальностью; они имеют дело с исключительно идеализированными экономическими объектами и ситуациями.  При построении таких моделей главным принципом  является  не  столько приближение к реальности, сколько получение возможно большего  числа  аналитических  результатов посредством  математических доказательств.  Ценность этих моделей для экономической теории  и  практики  состоит  в том, что они служат теоретической базой для моделей прикладного типа.     Довольно самостоятельными  областями  исследований становятся подготовка и обработка экономической информации и разработка математического  обеспечения экономических задач (создание баз данных и банков информации,  программ автоматизированного построения  моделей  и программного сервиса для экономистов-пользователей). На этапе практического использования моделей ведущую  роль  должны играть специалисты в соответствующей области экономического  анализа,   планирования,   управления. Главным участком  работы экономистов-математиков остается постановка и формализация экономических задач и  синтез  процесса экономико-математического моделирования.

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

22.12.2011, 13:27

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

Основные понятия

     Математическое программирование — область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т. е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.     Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называютцелевой, показателем эффективности или критерием оптимальности. Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель. Математическая модель задачи — это отражение оригинала в виде функций, уравнений, неравенств, цифр и т. д. Модель задачи математического программирования включает:     1) совокупность неизвестных величин, действуя на которые, систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, управлением, стратегией, поведением и др.);     2) целевую функцию (функцию цели, показатель эффективности, критерий оптимальности, функционал задачи и др.). Целевая функция позволяет выбирать наилучший вариант — из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение. Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень обслуживания или дефицитности, число комплектов, отходы и т. д.;     Эти условия следуют из ограниченности ресурсов, которыми располагает общество в любой момент времени, из необходимости удовлетворения насущных потребностей, из условий производственных и технологических процессов. Ограниченными являются не только материальные, финансовые и трудовые ресурсы. Таковыми могут быть возможности технического, технологического и вообще научного потенциала. Нередко потребности превышают возможности их удовлетворения. Математически ограничения выражаются в виде уравнений и неравенств. Их совокупность образует область допустимых решений (область экономических возможностей). План, удовлетворяющий системе ограничений задачи, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным. Оптимальное решение, вообще говоря, не обязательно единственно, возможны случаи, когда оно не существует, имеется конечное или бесчисленное множество оптимальных решений.      Один из разделов математического программирования - линейным программированием.   Методы и модели линейного программирования широко применяются при оптимизации процессов во всех отраслях народного хозяйства: при разработке производственной программы предприятия, распределении ее по исполнителям, при размещении заказов между исполнителями и по временным интервалам, при определении наилучшего ассортимента выпускаемой продукции, в задачах перспективного, текущего и оперативного планирования и управления; при планировании грузопотоков, определении плана товарооборота и его распределении; в задачах развития и размещения производительных сил, баз и складов систем обращения материальных ресурсов и т. д. Особенно широкое применение методы и модели линейного программирования получили при решении задач экономии ресурсов (выбор ресурсосберегающих технологий, составление смесей, раскрой материалов), производственно-транспортных и других задач.     Начало линейному программированию было положено в 1939 г. советским математиком-экономистом Л. В. Канторовичем в работе «Математические методы организации и планирования производства». Появление этой работы открыло новый этап в применении математики в экономике. Спустя десять лет американский математик Дж. Данциг разработал эффективный метод решения данного класса задач — симплекс-метод. Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит в следующем:     1) умение находить начальный опорный план;     2) наличие признака оптимальности опорного плана;     3) умение переходить к нехудшему опорному плану.

Постановка задачи линейного программирования  и свойства ее решений

     Линейное программирование — раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополнительных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений.     Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений. Отсюда — необходимость разработки новых методов.     Формы записи задачи линейного программирования:     Общей задачей линейного программирования называют задачу                        (2.1)     при ограничениях                     (2.2)                         (2.3)                          (2.4)                                 (2.5)     - произвольные                  (2.6)     где  - заданные действительные числа; (2.1) – целевая функция; (2.1) – (2.6) –ограничения;  - план задачи.     Пусть ЗЛП представлена в следующей записи:                                                      (2.7)                                       (2.8)                                           (2.9)     Чтобы задача (2.7) – (2.8) имела решение, системе её ограничений (2.8) должна быть совместной. Это возможно, если  r этой системы не больше числа неизвестных n. Случай r>n вообще невозможен. При r=n система имеет единственное решение, которое будет при оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть r<n. В этом случае система векторов содержит базис — максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, вообще говоря, может быть несколько, но не более . Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные n – r переменных будут свободными, их обозначают СП. Не ограничивая общности, будем считать, что базис составляют первые m векторов . Этому базису соответствуют базисные переменные , а свободными будут переменные .     Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (8) называют опорным решением (планом).     Теорема. Если система векторов  содержит m линейно независимых векторов , то допустимый план                                       (2. 10)     является крайней точкой многогранника планов.     Теорема. Если ЗЛП имеет решение, то целевая функция достигает экстремального значения хотя бы в одной из крайних точек многогранника решений. Если же целевая функция достигает экстремального значения более чем в одной крайней точке, то она достигает того же значения в любой точке, являющейся их выпуклой линейной комбинацией.

Графический способ решения ЗЛП

     Геометрическая интерпретация экономических задач дает возможность наглядно представить, их структуру, выявить особенности и открывает пути исследования более сложных свойств. ЗЛП с двумя переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в пространствах, размерность которых больше трех, графическое решение, вообще говоря, невозможно. Случай двух переменных не имеет особого практического значения, однако его рассмотрение проясняет свойства ОЗЛП, приводит к идее ее решения, делает геометрически наглядными способы решения и пути их практической реализации.     Пусть дана задача                                         (2.11)                                        (2.12)                                               (2.13)     Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (2.12), (2.13) задает на плоскости некоторую полуплоскость. Полуплоскость — выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений задачи (2.11) — (2.13)  есть выпуклое множество.     Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП — непустое множество, например многоугольник .           Выберем произвольное значение целевой функции . Получим . Это уравнение прямой  линии. В точках прямой NМ целевая функция сохраняет одно и то же постоянное значение . Считая в равенстве (2.11)  параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).     Найдём частные производные целевой функции по  и :     ,                                                (2.14)     .                                               (2.15)     Частная производная (2.14)  (так же как и (2.15)) функции показывает скорость ее возрастания вдоль данной оси. Следовательно,  и  — скорости возрастания  соответственно вдоль осей  и . Вектор  называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:          Вектор  указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.     Вектор  перпендикулярен к прямым  семейства  .     Из геометрической интерпретации элементов ЗЛП вытекает следующий порядок ее графического решения.     1. С учетом системы ограничений строим область допустимых решений .     2. Строим вектор  наискорейшего возрастания целевой функции — вектор градиентного направления.     3. Проводим произвольную линию уровня  .      4. При решении задачи на максимум перемещаем линию уровня  в направлении вектора  так, чтобы она касалась области допустимых решений в ее крайнем положении (крайней точке)В случае решения задачи на минимум линию уровня  перемещают в антиградиентном направлении.      5. Определяем оптимальный план  и экстремальное значение целевой функции .

Симплексный метод решение ЗЛП

     Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит     1) умение находить начальный опорный план;     2) наличие признака оптимальности опорного плана;     3) умение переходить к нехудшему опорному плану.     Пусть ЗЛП представлена системой ограничений в каноническом виде:     .     Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части  левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства — с коэффициентом, равным нулю.     Пусть система ограничений имеет вид          Сведем задачу к каноническому виду. Для этого прибавим к левым частям неравенств дополнительные переменные  . Получим систему, эквивалентную исходной:      ,     которая имеет предпочтительный вид      .     В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю  .     Пусть далее система ограничений имеет вид     .     Сведём её к эквивалентной вычитанием дополнительных переменных   из левых частей неравенств системы. Получим систему      .     Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные  входят в левую часть (при ) с коэффициентами, равными –1. Поэтому, вообще говоря, базисный план  не является допустимым. В этом случае вводится так называемый искусственный базис. К левым частям ограничений-равенств, не имеющих предпочтительного вида, добавляют искусственные переменные . В целевую функцию переменные , вводят с коэффициентом М в случае решения задачи на минимум и с коэффициентом - М для задачи на максимум, где М - большое положительное число. Полученная задача называется М-задачей, соответствующей исходной. Она всегда имеет предпочтительный вид.     Пусть исходная ЗЛП имеет вид     ,                      (2.16)     ,        (2.17)      ,                         (2.18)     причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:                (2.19)                           (2.20)                       (2.21)     Задача (2.19) — (2.21) имеет предпочтительный план. Её начальный опорный план имеет вид          Если некоторые из уравнений (2.17) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.     Теорема. Если в оптимальном плане                        (2.22)       М-задачи (2.19) — (2.21) все искусственные переменные  , то план   является оптимальным планом исходной задачи (2.16) — (2.18).     Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида, вводят искусственный базис и решают расширенную М — задачу, которая имеет начальный опорный план           Решение исходной задачи симплексным методом путем введения искусственных переменных  называется симплексным методом с искусственным базисом.     Если в результате применения симплексного метода к расширенной задаче получен оптимальный план, в котором все искусственные переменные , то его первые n компоненты дают оптимальный план исходной задачи.     Теорема. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.     Признаки оптимальности.     Теорема. Пусть исходная задача решается на максимум. Если для некоторого опорного плана все оценки  неотрицательны, то такой план оптимален.     Теорема. Если исходная задача решается на минимум и для некоторого опорного плана все оценки   неположительны, то такой план оптимален.

Теория двойственности

     Понятие двойственности рассмотрим на примере задачи оптимального использования сырья. Пусть на предприятии решили рационально использовать отходы основного производства. В плановом периоде появились отходы сырья m видов в объемах единиц . Из этих отходов, учитывая специализацию предприятия, можно наладить выпуск n видов неосновной продукции. Обозначим через  норму расхода сырья i-го вида на единицу j-й  продукции, - цена реализации единицы j-й продукции (реализация обеспечена). Неизвестные величины задачи:  — объемы выпуска j-й продукции, обеспечивающие предприятию максимум выручки.      Математическая модель задачи:                        (2.23)                          (2.24)                                       (2.25)     Предположим далее, что с самого начала при изучении вопроса об использовании отходов основного производства на предприятии появилась возможность реализации их некоторой организации. Необходимо установить прикидочные оценки (цены) на эти отходы. Обозначим их .      Оценки должны быть установлены исходя из следующих требований, отражающих несовпадающие интересы предприятия и организации:     1) общую стоимость отходов сырья покупающая организация стремится минимизировать;      2) предприятие согласно уступить отходы только по таким ценам, при которых оно получит за них выручку, не меньшую той, что могло бы получить, организовав собственное производство.     Эти требования формализуются в виде следующей ЗЛП.     Требование 1 покупающей организации – минимизация покупки:                          (2.26)     Требование 2 предприятия, реализующего отходы сырья, можно сформулировать в виде системы ограничений. Предприятие откажется от выпуска каждой единицы продукции первого вида, если , где левая часть означает выручку за сырьё идущее на единицу продукции первого вида; правая – её цену.     Аналогичные рассуждения логично провести в отношении выпуска продукции каждого вида. Поэтому требование предприятия, реализующего отходы сырья, можно формализовать в виде сл. системы ограничений:                           (2.27)     По смыслу задачи оценки не должны быть отрицательными:     .                          (2.28)     Переменные   называют двойственными оценками или объективно обусловленными оценками.     Задачи (2.23) — (2.25) и (2.26) — (2.28) называют парой взаимно двойственных ЗЛП.     Между прямой и двойственной задачами можно установить следующую взаимосвязь:     1. Если прямая задача на максимум, то двойственная к ней — на минимум, и наоборот.     2. Коэффициенты  целевой функции прямой задачи являются свободными членами ограничений двойственной задачи.     3. Свободные члены  ограничений прямой задачи являются коэффициентами целевой функции двойственной.     4. Матрицы ограничений прямой и двойственной задач являются транспонированными друг к другу.     5. Если прямая задача на максимум, то ее система ограничений представляется в виде неравенств типа . Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа .     6. Число ограничений прямой задачи равно числу переменных двойственной, а число ограничений двойственной — числу переменных прямой.     7. Все переменные в обеих задачах неотрицательны.

Основные теоремы двойственности и их экономическое содержание

     Теорема. Для любых допустимых планов  и прямой и двойственной ЗЛП справедливо неравенство , т.е.                                    (2.29)      – основное неравенство теории двойственности.     Теорема (критерий оптимальности Канторовича).     Если для некоторых допустимых планов  и  пары двойственных задач выполняется неравенство , то  и  являются оптимальными планами соответствующих задач.     Теорема (малая теорема двойственности).     Для существования оптимального плана любой из пары двойственных задач необходимо и достаточно существование допустимого плана для каждой из них.     Теорема. Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функций равны: . Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.     Экономическое содержание первой теоремы двойственности состоит в следующем: если задача определения оптимального плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения оценок ресурсов. Причем цена продукции, полученной при реализации оптимального плана, совпадает с суммарной оценкой ресурсов. Совпадение значений целевых функций для соответствующих планов пары двойственных задач достаточно для того, чтобы эти планы были оптимальными. Это значит, что план производства и вектор оценок ресурсов являются оптимальными тогда и только тогда, когда цена произведенной продукции и суммарная оценка ресурсов совпадают. Оценки выступают как инструмент балансирования затрат и результатов. Двойственные оценки, обладают тем свойством, что они гарантируют рентабельность оптимального плана, т. е. равенство общей оценки продукции и ресурсов, и обусловливают убыточность всякого другого плана, отличного от оптимального. Двойственные оценки позволяют сопоставить и сбалансировать затраты и результаты системы.     Теорема (о дополняющей нежесткости)       Для того, чтобы планы  и  пары двойственных задач были оптимальны, необходимо и достаточно выполнение условий:                   (2.30)                  (2.31)     Условия (2.30), (2.31) называются условиями дополняющей нежесткости. Из них следует: если какое-либо ограничение одной из задач ее оптимальным планом обращается в строгое неравенство, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом должно обращаться в строгое равенство.     Экономически это означает, что если по некоторому оптимальному плану  производства расход i-го ресурса строго меньше его запаса , то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его i-я компонента строго больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положительную оценку, а ресурс избыточный (используемый не полностью) имеет нулевую оценку.     Теорема (об оценках). Двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена соответствующего ограничения задачи математического программирования, точнее                          (2.32)

Тема 2. Методы линейного программирования. Основные виды экономических задач, сводящихся к ЗЛП

Задача о наилучшем использовании ресурсов. Пусть некоторая производственная единица (цех, завод, объединение и т. д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции (товаров), известных под номерами, обозначаемыми индексом j . Будем обозначать эту продукцию . Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т. д.). Все эти виды ограничивающих факторов называют ингредиентами . Пусть их число равно m; припишем им индекс i . Они ограничены, и их количества равны соответственно  условных единиц. Таким образом,  - вектор ресурсов. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т. д. Примем в качестве такой меры, например, цену реализации     , т.е. — вектор цен. Известны также технологические коэффициенты , которые указывают, сколько единиц i–го ресурса требуется для производства единицы продукции >j-го вида. Матрицу коэффициентов  называют технологической и обозначают буквой А. Имеем  . Обозначим через план производства, показывающий, какие виды товаров  нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах.     Так как - цена реализации единицы j-й продукции, цена реализованных  единиц будет равна , а общий объем реализации .     Это выражение — целевая функция, которую нужно максимизировать.     Так как - расход i-го ресурса на производство  единиц  j-й продукции, то, просуммировав расход i-го ресурса на выпуск всех n видов продукции, получим общий расход этого ресурса, который не должен превосходить  единиц:          Чтобы искомый план был реализован, наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объёмы   выпуска продукции:  .     Таким образом, модель задачи о наилучшем использовании ресурсов примет вид:                                 (2.33)     при ограничениях:                                 (2.34)                                        (2.35)     Так как переменные  входят в функцию  и систему ограничений только в первой степени, а показатели  являются постоянными в планируемый период, то (2.33)-(2.35) – задача линейного программирования.     Задача о смесях     В различных отраслях народного хозяйства возникает проблема составления таких рабочих смесей на основе исходных материалов, которые обеспечивали бы получение конечного продукта, обладающего определенными свойствами. К этой группе задач относятся задачи о выборе диеты, составлении кормового рациона в животноводстве, шихт в металлургии, горючих и смазочных смесей в нефтеперерабатывающей промышленности, смесей для получения бетона в строительстве и т. д.  Высокий уровень затрат на исходные сырьевые материалы и необходимость повышения эффективности производства выдвигает на первый план следующую задачу: получить продукцию с заданными свойствами при наименьших затратах на исходные сырьевые материалы.     Пример. Для откорма животных используется три вида комбикорма: А, В и С. Каждому животному в сутки требуется не менее 800 г. жиров, 700 г. белков и 900 г. углеводов. Содержание в  1 кг. каждого вида комбикорма жиров белков и углеводов (граммы) приведено в таблице:

Содержание в 1 кг.

Комбикорм

 

А

В

С

Жиры

320

240

300

Белки

170

130

110

Углеводы

380

440

450

Стоимость 1 кг

31

23

20

     Сколько килограммов каждого вида комбикорма нужно каждому животному, чтобы полученная смесь имела минимальную стоимость?     Математическая модель задачи есть:      - количество комбикорма А,В и С. Стоимость смеси есть:          Ограничения на количество ингредиентов:           Задача о раскрое материалов     Сущность задачи об оптимальном раскрое состоит в разработке таких технологически допустимых планов раскроя, при которых получается необходимый комплект заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму. Рассматривается простейшая модель раскроя по одному измерению. Более сложные постановки ведут к задачам целочисленного программирования.     Задача о назначениях     Речь идет о задаче распределения заказа (загрузки взаимозаменяемых групп оборудования) между предприятиями (цехами, станками, исполнителями) с различными производственными и технологическими характеристиками, но взаимозаменяемыми в смысле выполнения заказа. Требуется составить план размещения заказа (загрузки оборудования), при котором с имеющимися производственными возможностями заказ был бы выполнен, а показатель эффективности достигал экстремального значения.     Пример. Цеху металлообработки нужно выполнить срочный заказ на производство деталей. Каждая деталь обрабатывается на 4-х станках С1, С2, С3 и С4. На каждом станке может работать любой из четырех рабочих Р1, Р2, Р3, Р4, однако, каждый из них имеет на каждом станке различный процент брака. Из документации ОТК имеются данные о проценте брака каждого рабочего на каждом станке:

Рабочие

Станки

 

С1

С2

С3

С4

Р1

2,3

1,9

2,2

2,7

Р2

1,8

2,2

2,0

1,8

Р3

2,5

2,0

2,2

3,0

Р4

2,0

2,4

2,4

2,8

    Необходимо так распределить рабочих по станкам, чтобы суммарный процент брака (который равен сумме процентов брака всех 4-х рабочих) был минимален. Чему равен этот процент?      Обозначим за  - переменные, которые принимают значения 1, если i-й рабочий работает на j-м станке. Если данное условие не выполняется, то . Целевая функция есть:          Вводим ограничения. Каждый рабочий может работать только на одном станке, то есть           Кроме того, каждый станок обслуживает только один рабочий:          Кроме того, все переменные должны быть целыми и неотрицательными:  .

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

Математическая модель задачи         Линейные транспортные задачи составляют особый класс задач линейного программирования. Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения  n который, потребовал бы минимальных затрат. Если потребитель j  получает единицу продукции (по прямой дороге) со склада i, то возникают издержки Сij. Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы  kСij.      Далее, предполагается, что                                                       где ai есть количество продукции, находящееся на складе i, и bj – потребность потребителя >j. Такая транспортная задача называется закрытой. Однако, если данное равенство не выполняется, то получаем открытую транспортную задачу, которая сводится к закрытой по следующим правилам:     1. Если сумма  запасов  в  пунктах  отправления  превышает  сумму  поданных  заявок  то количество продукции, равное  остается на складах. В этом случае мы введем «фиктивного» потребителя n+1  с потребностью  и положим транспортные расходы pi,n+1 равными 0 для всех i.      2. Если сумма  поданных  заявок  превышает  наличные  запасы то потребность не может быть покрыта. Эту задачу можно свести к обычной транспортной задаче с правильным  балансом,  если  ввести  фиктивный пункт отправления m+1 с  запасом   и стоимость перевозок из  фиктивного  пункта  отправления  во  все  пункты  назначения  принять  равным  нулю.        Математическая модель транспортной задачи имеет вид:                                                          где xij количество продукции, поставляемое со склада i потребителю j, а Сij издержки (стоимость перевозок со склада i потребителю j).     Рассмотрим пример:     ПРИМЕР. Компания «Стройгранит» производит добычу строительной щебенки и имеет на территории региона три карьера. Запасы щебенки на карьерах соответственно равны 800, 900 и 600 тыс. тонн. Четыре строительные организации , проводящие строительные работы на разных объектах этого же региона дали заказ на поставку соответственно 300, 600, 650 и 750 тыс. тонн щебенки. Стоимость перевозки 1 тыс. тонн щебенки с каждого карьера на каждый объект приведены в таблице:

Карьер

Строительный объект

 

1

2

3

4

1

8

4

1

7

2

3

6

7

3

3

6

5

11

8

     Необходимо составить такой план перевозки (количество щебенки, перевозимой с каждого карьера на каждый строительный объект), чтобы суммарные затраты на перевозку были минимальными.      Данная транспортная задача является закрытой, так как запасы поставщиков 800+900+600=2300 равны спросу потребителей 300+600+650+750=2300. Математическая модель ЗЛП в данном случае имеет вид:      - количество щебенки, перевозимой с i–го карьера на j–й объект. Тогда целевая функция равна           Ограничения имеют вид          Составление опорного плана     Решение  транспортной  задачи   начинается  с  нахождения  опорного  плана. Для  этого  существуют  различные  способы. Например, способ северо-западного  угла, способ  минимальной  стоимости  по  строке, способ  минимальной  стоимости  по  столбцу  и  способ  минимальной  стоимости  таблицы.       Рассмотрим  простейший, так  называемый  способ  северо-западного  угла. Пояснить  его  проще  всего  будет  на  конкретном  примере:     Условия  транспортной  задачи  заданы транспортной  таблицей.     Таблица № 2.1

 

В1

В2

В3

В4

В5

Запасы а>i

А1

10

8

5

6

9

48

А2

6

7

8

6

5

30

А3

8

7

10

8

7

27

А4

7

5

4

6

8

20

Заявки bj

18

27

42

12

26

125

     Будем  заполнять  таблицу  перевозками  постепенно  начиная  с  левой  верхней ячейки («северо-западного угла» таблицы). Будем  рассуждать  при  этом  следующим  образом. Пункт  В1  подал  заявку    на  18 единиц груза. Удовлетворим эту заявку за счёт запаса 48, имеющегося  в  пункте  А1 , и  запишем  перевозку  18 в  клетке (1,1). После  этого  заявка  пункта  В1  удовлетворена, а  в  пункте  А1  осталось  ещё  30  единиц  груза. Удовлетворим  за  счёт  них  заявку  пункта  В2 (27  единиц), запишем  27  в  клетке (1,2); оставшиеся  3  единицы  пункта  А1  назначим  пункту  В3. В составе  заявки  пункта  В3  остались  неудовлетворёнными  39  единиц.  Из  них  30  покроем  за  счёт  пункта  А2, чем  его  запас  будет  исчерпан, и   ещё  9  возьмём  из  пункта  А3. Из  оставшихся  18  единиц  пункта  А3 12  выделим  пункту  В4;  оставшиеся  6  единиц  назначим  пункту  В5,  что  вместе  со  всеми  20  единицами  пункта А4  покроет  его  заявку.  На  этом  распределение  запасов  закончено;  каждый  пункт  назначения   получил  груз,  согласно  своей  заявки. Это  выражается  в  том, что  сумма  перевозок  в  каждой  строке  равна   соответствующему   запасу, а  в  столбце — заявке. Таким  образом, нами  сразу  же  составлен  план  перевозок,  удовлетворяющий  балансовым  условиям. Полученное  решение  является  опорным  решением  транспортной  задачи:        Таблица № 2.2

 

  В1  

  В2

  В3

  В4

  В5

Запасы а i

     А1  

10      

18

8     

27

5     

3

6

9

  48

     А2  

6

7

8    

30

6

5

  30

     А3  

8

7

10      

9

8    

12

7      

6

  27

     А4  

7

5

4

6

8     

20

  20

 Заявки           bj

  18

  27

  42

  12

  26

  125

     Составленный нами план перевозок, не является оптимальным по  стоимости, так  как  при  его   построении  мы  совсем  не  учитывали  стоимость   перевозок  Сij .     Другой способ — способ минимальной стоимости по строке — основан на том, что мы распределяем продукцию от пункта Ai не в любой из пунктов Bj, а в тот, к которому стоимость перевозки минимальна. Если в этом пункте заявка полностью удовлетворена, то мы убираем его из расчетов и находим минимальную стоимость перевозки из оставшихся пунктов Bj. Во всем остальном этот метод схож с методом северо-западного угла. В результате, опорный план, составленный способом минимальной стоимости по строке выглядит, так как показано  в таблице № 2.3.     При этом методе может получиться, что стоимости перевозок Cij  и Cik от пункта Ai к пунктам Bj и Bk равны. В этом случае, с экономической точки зрения, выгоднее распределить продукцию в тот пункт, в котором заявка больше. Так, например, в строке 2:  C21 = C24, но заявка b1 больше заявки b4, поэтому 4 единицы продукции мы распределим в клетку (2,1).    Таблица № 2.3

 

  В1  

  В2

  В3

  В4



Страницы: Первая | 1 | 2 | 3 | ... | Вперед → | Последняя | Весь текст


Предыдущий:

Следующий: