Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции - Экономико-математические модели - файл 1. Введение. Классификация эконом-мат. модели..doc


Лекции - Экономико-математические модели
скачать (963.3 kb.)

Доступные файлы (5):

1. Введение. Классификация эконом-мат. модели..doc738kb.23.05.2007 12:58скачать
2. Симплекс-метод.doc1086kb.01.06.2007 17:26скачать
3. Задача о назначении. Модели теории игр.doc540kb.26.05.2007 13:18скачать
4. Решение задачи с помощью Excel.doc308kb.23.05.2007 12:39скачать
реферат.doc106kb.08.06.2007 20:51скачать

содержание

1. Введение. Классификация эконом-мат. модели..doc

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

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

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

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

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


^ Информация о математических методах и моделях

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

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

^ Экономико-математические модели: функции полезности; кривые безразличия; функции спроса; уравнение Слуцкого; Кривые «доход –потребление»; кривые «цены – потребление»; коэффициент эластичности; материальные балансы; функции выпуска продукции; производственные функции затрат ресурсов; модели поведения фирмы в условиях совершенной и несовершенной конкуренции; модели общего экономического равновесия; модель Эрроу – Гурвица; статистическая и динамическая модели межотраслевого баланса; общие модели развития экономики; модель Солоу.
^ Классификация и принцип построения экономико-

математических моделей
Основной путь исследования системы – это построение моде­ли. Моделирование – процесс, посредством которого исследова­тель стремится понять определенные аспекты реальной жизни. Модель не является точной копией реальности, а представляет со­бой упрощенный ее вариант, согласованный с задачами исследова­теля. Один и тот же объект в зависимости от целей исследования может иметь разные модели. Например, моделью человека может являться кукла, мешок с песком (100 кг) при испытании парашюта, ватный макет с большим числом датчиков при испытании противоударных средств в автомобиле, манекен при моделировании одежды и т.д..

С моделями мы часто встречаемся в обычной жизни, возможно, не подозревая, что это модели.

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

Моделирование как метод исследования имеет альтернативу. Это – словесный, или «вербальный», анализ, оперирующий произ­вольными категориями с расплывчатыми результатами, которые трудно оценить. Нисколько не умаляя достоинств этого метода ис­следования, уместно указать на часто встречающийся недостаток «вербального» анализа: «Не пользующаяся математическими сим­волами человеческая логика зачастую запутывается в словесных определениях и делает вследствие этого ошибочные выводы – и вскрыть эту ошибку за музыкою слов иногда стоит огромного тру­да и бесконечных, часто бесплодных, споров» (В.И. Арнольд «Жесткие и мягкие модели»).

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

Для того чтобы найти главные части и связи системы, следу­ет сосредоточить внимание на трех важных моментах:

  1. Определить главную цель системы, ответив на вопросы о том, зачем существует система и какие главные функции она выполняет.

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

  3. Установить важные связи между этими частями.

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

Пример:

В экономике есть два основополагающих понятия – спрос и предложение. Экономисты иногда шутят: «Научите попугая произносить два слова – спрос и предложение – и перед Вами готовый экономист». Однако исторически модель спро­са и предложения строилась не так просто. А. Смит, отец эко­номической науки, в своей знаменитой книге «Богатство на­родов» (1776) оставил будущим поколениям вопрос: «Что есть цена?» Чтобы получить ответ на него, понадобились более ста лет. Разрешить загадку пыталась теория трудовой стоимо­сти Д. Рикардо. Однако эта теория описывала предложение, но не описывала спрос. В результате она стала классической теорией издержек, но не теорией цены, Для того чтобы пре­вратиться в теорию цены, ей не хватало одного очень важного элемента – спроса. Аналогичный недостаток имела альтер­нативная теория – маргинализм. Она описывала спрос, но не описывала предложение. Загадка А. Смита была разгадана лишь в 1890 г. А. Маршаллом в книге «Принципы экономи­ческой теории», где в виде диаграммы была предложена мо­дель спроса и предложения. Этой модели уже более ста лет. Тем не менее, сегодняшняя микроэкономическая теория мало отличается от того, о чем писал А. Маршалл.

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

Пример:

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

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

  1. Чем проще модель, тем меньше возможность ошибочных выводов.

  2. Модель должна быть простой, но не проще, чем это воз­можно.

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

  4. Модель должна быть грубой: малые поправки не должны кардинально менять ее поведение.

  5. Модель и расчет не должны быть точнее исходных данных.


Основные принципы построения матема­тической модели

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

  2. Математическая модель должна отражать существенные черты иссле­дуемого явления и при этом не должна его сильно упрощать.

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

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

По числу критериев эффективности математические модели делятся на однокритериальные и многокритериальные (рис. 1). Многокритериальные матема-тические модели содержат два и более критерия.

По учету неизвестных факторов математические модели делятся на де­терминированные, стохастические и модели с элементами неопределен­ности.

^ В стохастических моделях неизвестные факторы – это случайные величины, для которых известны функции распределения и различные статистические характеристики (математическое ожидание, дисперсия, среднеквадратическое отклонение и т. п.). Среди стохастических можно выделить:

  • модели стохастического программирования, в которых либо в целе­вую функцию, либо в ограничения входят случайные величины;

  • модели теории случайных процессов, предназначенные для изучения процессов, состояние которых в каждый момент времени является слу­чайной величиной;

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

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

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

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

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

Для линейных моделей любого вида и достаточно большой размерности известны стандартные методы решения.


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

В этом случае задачу следует упростить, либо сведя ее к из­вестным линейным моделям, либо просто линеаризовав модель.

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

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

1. Определение цели, т.е. чего хотят добиться, решая поставленную задачу.

  1. Определение параметров модели, т.е. заранее известных фикси­рованных факторов, на значения которых исследователь не влияет.

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

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

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

  5. Выражение цели через управляющие переменные, параметры и неизвестные факторы, т.е. формирование целевой функции, на­зываемой также критерием эффективности или критерием оп­тимальности задачи.

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

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

Двойственность и основные соотношения двойственности

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

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

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

Прямая задача

Двойственная задача

Максимизировать

при ограничениях



Минимизировать

при ограничениях




Решение прямой задачи.

Строим область допустимых решений задачи. Для этого нумеруем ограничения задачи



В прямоугольной декартовой системе координат (рис. 2) строим прямую (p1), соответствующую ограничению (1) по двум точкам, например, (– 7; 0) и (– 4; 2). Находим, какая из полуплоскостей, на которые эта прямая делит всю координатную плоскость, является областью решений неравенства (1). Для этого достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство. Так как прямая p1 не проходит через начало координат, подставляем координаты точки в первое ограничение . Получаем строгое неравенство . Следовательно, точка О лежит в полуплоскости решений. Штриховкой отмечаем полуплоскость, содержащую точку О. Аналогично строим прямую (p2) по двум точкам (0; 8) и (8; 0) и определяем область решений ограничения (2).





Рис. 2

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

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

Определяем координаты точки В как пересечение прямых p1 и p2. Для этого решаем систему



Получаем:



Следовательно, координаты точки . Оптимальное решение х1* = 2, х2* = 6. Вычисляем максимум целевой функции: Уравнение опорной прямой имеет вид:
Решение двойственной задачи.

Для построения области допустимых решений занумеруем ограничения задачи:



Строим прямые p3 и p4, уравнения которых: – 2у1 + у2 = 2 и 3у1 + у2 = 7. Учитывая условия неотрицательности переменных, определяем область допустимых решений. Полученная область представляет неограниченный сверху выпуклый многоугольник (рис. 3). Нормаль линии уровня .

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

Определяем координаты точки D, как пересечение прямых p3 и p4. Для этого решаем систему



Получаем, что точка D имеет координаты . Оптимальное решение у1* = 1, у2* = 4. Вычисляем минимум целевой функции: Уравнение опорной прямой имеет вид: .









Рис. 3

Как видно из приведенных решений прямой и двойственной задач значения целевых функций равны:

При любом допустимом решении прямой задачи значение целевой функции «» (не превосходят) значений целевой функции двойственной задачи при ее допустимом произвольном решении.

Например, при допустимом решении прямой задачи значение целевой функции , а при допустимом двойственной задачи значение целевой функции , т.е. .
Пример 2. Решить графическим методом прямую и двойственную задачи (табл. 2).

Таблица 2

Прямая задача

Двойственная задача

Минимизировать

при ограничениях



Максимизировать

при ограничениях




Для решения прямой задачи вводим нумерацию ограничений задачи:



Аналогично примеру 1 строим область допустимых решений, которая представляет собой выпуклый многоугольник не ограниченный сверху. Нормаль линии уровня (рис. 4).







Рис. 4

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



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







Рис. 5

Взаимозависимость оптимальных решений пары двойственных задач определена следующими соотношениями:

Теорема (основное неравенство). Пусть Х – какое-нибудь допустимое решение прямой задачи, а Y – какое-нибудь допустимое решение двойственной задачи. Тогда справедливо неравенство

.

Следствие 1 (достаточный признак оптимальности). Если для каких-то допустимых решений и соответственно прямой и двойственной задач выполняется равенство

,

то есть оптимальное решение прямой задачи, а – оптимальное решение двойственной задачи.

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

Основная теорема. Если разрешима одна из пары двойственных задач, то разрешима и другая задача, причем .

Остальные теоремы двойственности будут сформулированы в следующих разделах данного пособия.

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

^ Формулировка прямой задачи

Пусть фирма располагает  видами ресурсов Р1 , Р2 ,… Рm и планирует организовать выпуск из них  n  видов продукции П1 , П2 ,…, Пn .

Известны следующие исходные данные:

aij – нормы расхода i-го ресурса на изготовление одной единицы j-ой продукции Пj;

cj  - прибыль от реализации одной единицы j-ой продукции Пj;

bi - количество ресурса i–го вида.

Требуется составить план выпуска продукции  П1, П2,…Пn. из имеющихся объемов ресурсов Р1, Р2 ,…Рm , при котором прибыль от ее реализации будет максимальной.

Построим математическую модель этой задачи.

Обозначим за x (j = 1,2,...,n) – число единиц продукции, запланированных к производству. Тогда прибыль от реализации j-го вида продукции составит  cjxj , а суммарная прибыль от реализации всей продукции будет равна: 

F = c1 x1 + c2 x2 + ...+ cn xn.

Согласно условиям задачи, она подлежит максимизации. 

Затраты ресурса  Pi на выпуск всей продукции  Х = (x1, x2 ,..., xn ) будут выражаться суммой произведений норм расхода aij на объемы выпуска и составят величину, равную  ai1 x1 + ai2 x2 + ... + ain xn . Поскольку запас ресурса Рi  равен  bi , а расход ресурса не может превышать имеющегося его количества, то приходим к ограничениям следующего вида:

ai1x1 + ai2x2 +… + ainxn £ bi, i = 1,2,...,m

Учитывая естественные условия неотрицательности объемов выпуска продукции,

xj0,  j=1,2,...,n,

придем к следующей задаче:

Найти такой план Х = (x1, x2 ,..., xn) выпуска продукции, удовлетворяющий системе неравенств

a11x1 + a12x2 + … + a1nxn £ b1,

a21x1 + a22x2 + … + a2nxn £ b2,

… … … … … … …

ai1x1 + ai2x2 + … + ainxn £ bi,

… … … … … … …

am1x1 + am2x2 + … + amnxn £ bm,

xj ³ 0, j = 1, 2, …, n,

при котором функция F = c1x1 + c2x2 + … + cnxn принимает максимальное значение.

^ Формулировка двойственной задачи

Предположим, что некоторая организация решила закупить ресурсы Р, Р,…, Рm фирмы и необходимо определить цены на эти ресурсы у1, у2,…, уm. Естественно, что покупающая организация заинтересована в том, чтобы затраты на покупку ресурсов в объеме b1, b2,…, bm по ценам у1, у2,…, уm были минимальны, то есть Z = b1y1 + b2y2 + … +bmym ® min.

Предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не меньше той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. На изготовление единицы продукции j-го вида расходуется сырье Р1 в объеме а1j, сырье Р2 в объеме а2j…, сырье Рm в объеме аmj по цене у1, у2,…, уm соответственно, то есть затраты на изготовление продукции Пj должны быть не меньше, чем цена ее реализации. Приходим к ограничениям следующего вида:

а1jу1 + а2jу2 + … + аmjуm ≥ сj , j=1,2,...,n.


Учитывая условия неотрицательности цены единицы i-го ресурса, приходим к следующей задаче:

Найти такой вектор У = 1, у2 ,..., уm) – цен ресурсов, удовлетворяющий системе неравенств

a11у1 + a21у2 + … + am1уm ≥ c1,

a12y1 + a22y2 + … + am2ym ≥ c2,

… … … … … … …

a1jy1 + a2jy2 + … + amjym ≥ cj,

… … … … … … …

a1ny1 + a2ny2 + … + amnym ≥ cn,

yi ³ 0, i = 1, 2, …, m,

при котором функция Z = b1y1 + b2y2 + …+ bmym принимает минимальное значение.

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

Сопоставим общие представления прямой и двойственной задач в табл. 3, причем прямая задача – это задача модели распределения ограниченных ресурсов.

Таблица 3

Прямая задача

Двойственная задача

Максимизировать F =

при ограничениях

; i=1,2,...,m

xj ³ 0, j = 1, 2, …, n,

Минимизировать Z =

при ограничениях

; j = 1, 2, …, n

yi ³ 0, i=1,2,...,m

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

1. Если первая задача имеет размеры (m–ограничений с n неизвестными), то вторая – размеры .

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

З. В правых частях ограничений в каждой задаче стоят коэффициенты при неизвестных в целевой функции другой задачи.

4. В прямой задаче все ограничения представляют собой неравенства типа «», причем в этой задаче требуется достичь . Напротив, в двойственной задаче все ограничения суть неравенства типа «», причем требуется достичь .

Графически эти правила представлены в таблице 4.

Таблица 4

Переменные двойственной задачи

Переменные прямой задачи




х1

х2



хi



xn

c1

c2



ci



cn

y1

y2

.

.

.

yn

a11

a21

.

.

.

am1

a12

a22

.

.

.

am2








a1i

a2i

.

.

.

ami







a1n

a2n

.

.

.

amn

b1

b2

.

.

.

bm













j-е ограничение

двойственной задачи







коэффициенты целевой функции

двойственной задачи



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

Из приведенных соотношений видно, что для всех допустимых решений прямой и двойственной задач значения целевой функции задачи минимизации всегда будет верхним пределом значения целевой функции задачи максимизации. Таким образом, итерационное решение задачи максимизации ведет к возрастанию значения целевой функции, а итерационное решение задач минимизации – к ее убыванию. В итоге, при успешном завершении процессов вычисления прямой и двойственной задач приходят к точке «равновесия», где значения целевых функций задач максимизации и минимизации становятся равными.

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

Теорема равновесия. Пусть Х* – какое-нибудь допустимое решение прямой задачи, а Y* – какое-нибудь допустимое решение двойственной задачи. Для одновременной оптимальности этих решений необходимо и достаточно выполнение равенств:



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

Учитывая условия неотрицательности переменных и знаки сомножителей в произведениях, можно получить следующее:

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

Если  ai1 x1* +  ai2 x2*+ ...  + ain xn* <  bi  ,  то      yi* = 0 .

Если  a1j y1*  + a2j y2*+ … + amj ym*  >  cjто   xj* = 0 .

Если какая-либо координата оптимального плана одной задачи положительна, то соответствующее ограничение другой задачи обращается в равенство:

Если      yi*  > 0 ,    то   ai1 x1* +  ai2 x2*+ ...  + ain xn* =  bi .

Если     xj* > 0 ,  то     a1j y1*  + a2j y2*+ + amj ym*  =  cj .

Экономическое содержание теоремы равновесия означает, что если по некоторому оптимальному плану Х* производства расход i-го ресурса строго меньше его запаса bi, то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равно нулю. Если же в некотором оптимальном плане оценок его i-ая координата строго больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует, что двойственные оценки служат мерой дефицитности ресурсов. Дефицитный ресурс, который полностью используется по оптимальному плану производства, имеет положительную оценку, а избыточный ресурс, не используемый полностью, имеет нулевую оценку.
Пример 3. Используя теорему равновесия, решить пару двойственных задач (табл.5).

Таблица 5

Прямая задача

Двойственная задача

Максимизировать

при ограничениях



Минимизировать



при ограничениях




Решим прямую задачу графическим методом.




Рис. 6
Аналогично примеру 1 строим область допустимых решений, которая представляет собой выпуклый многоугольник ОАВСD. Нормаль линии уровня (рис. 6).

Определяем координаты точки С как пересечение прямых p9 и p10. Для этого решаем систему



Получаем:



Следовательно, координаты точки . Оптимальное решение х1* = 4, х2* = 1. Вычисляем максимум целевой функции прямой задачи:

По основной теореме двойственности Z(Y*) = F(Х*) = 3. Подставим Х* = (4;1) в систему ограничений прямой задачи:



Первое ограничение прямой задачи на оптимальном плане выполняется как строгое неравенство, следовательно, соответствующая переменная двойственной задачи равна нулю: y1*= 0.

Второе и третье ограничение прямой задачи обращается в точное равенство, следовательно, соответствующие переменные двойственной задачи положительны: y2* > 0 и y3* > 0.

Условия равновесия можно записать в виде равенств:



Подставляя y1*=0 в последнюю систему уравнений, получим систему:



откуда получаем, что y2* = , y3= .

Оптимальное решение двойственной задачи Y*= (0; ;) при этом минимум целевой функции двойственной задачи: Zmin = Z(Y*) = 3.
Графический способ решения задач показывает, что оптимальное решение задач, сводящихся к линейным моделям, всегда ассоциируется с угловой точкой области допустимых решений.

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


Скачать файл (963.3 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации