Экономико-математическое моделирование в микроэкономике

Задача 5.

Формирование оптимального штата  фирмы

Фирма набирает в штат сотрудников. Она располагает группами различных  должностей по bj вакантных единиц в каждой группе. Кандидаты для занятия должностей проходят тестирование, по результатам которого их разделяют на m групп по ai кандидатов в каждой группе. Для каждого кандидата из i группы требуются определенные затраты Cij на обучения для занятия j должности. В частности некоторые Сij = 0. Т.е. кандидат соответствует должности или Сij = ∞, т.е. кандидат вообще не может занять данную должность. Требуется распределить кандидатов на должности, затратив минимальные средства на их обучения.

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

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

В качестве тарифов на перевозки  рассматриваются затраты на переобучение. Методы решения такие же как и  транспортные.

 

С=∑∑СijXijà max      (*)

 

∑Хij=ai , i=1…m

∑Хij=bj , j=1…n

∑ai=∑bj

Хij≥0

 

30.10.2012

Задачи о назначении

В общем виде задача о назначении формулируется следующим образом. Имеется n работ и n кандидатов для их выполнения. Затраты i кандидата на выполнение j работы составляют Cij. Каждый кандидат может быть назначен только на одну работу и каждая работа может быть выполнена только одним кандидатом. Требуется найти назначения кандидатов на работы, при котором суммарные затраты на выполнение работ минимальны.

Хij- переменная, значение которой = 1, если кандидат назначен на работы, 0 – если не назначен.

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

∑Хij=1, j=1….,n (при i=1 до n)

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

∑Хij=1 (при j=1 до n)

Хij ε{0,1}

ЦФ:

С=∑∑СijXijàmin

 

Задача.

Оптимальное исследование рынков.

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

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

Данная задача сводится к задаче о назначениях. С этой целью вводится величина rij = Pij*aj

Эта величина показывает число успешных опросов в j месте в течении i дня.

Хij=1, если в i день опрос проводится в j месте. = 0, если в противном случае.

R=∑∑rijXijàmax

Функция R характеризует суммарное число опросов. Его нужно максимизировать. Первое и второе ограничения соответствуют тому, что в течении одного дня можно находиться только в одном месте.

 

Задача.

Оптимальное использование торговых агентов.

Торговая фирма продает товары в n различных городах. Покупательная способность жителей оценивается как bj. Для реализации товаров фирма располагает n торговыми агентами, каждого из которых она направляет в один из городов. Профессиональный уровень агентов различен. Доля реализуемых i торговым агентом покупательных способностей составляет ai. Как следует распределить торговых агентов по городам, чтобы фирма получила максимальную выручку от продажи товаров. Оптимальное решение этой проблемы может быть найдено с помощью задачи о назначениях. В качестве кандидатов выступают торговые агенты, в качестве работ – торговые города.

Сij=ai*ij – характеризует покупательную способность, реализуемую i торговым агентом в городе.

Хij=1, если i агент направлен в j город. = 0 – в противном случае.

С=∑∑СijXijàmin

ЦФ – это сумма реализованных  покупательных способностей всеми  торговыми агентами во всех городах. Первое и второе ограничение формализуют  соответственно условия о том  что в каждый город направляется один торговый агент и один торговый агент не может работать в двух городах.

 

Динамическое программирование, модели динамического программирования

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

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

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

 

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

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

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

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

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

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

1.задача оптимизации интерпретируется, как n шаговый процесс управления

2.ЦФ = сумме целевых функций каждого  шага

3.выбор управления на k шаге зависит только от состояния системы на этом шаге и не влияет на предшествующие шаги, т.е. нет обратной связи.

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

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

 

Второе условие может быть формализовано  следующим образом:

F=∑φi(Xi-1,k)

Φi –

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

F=∑Пφi(Xi-1,k)

Но условие отсутствия последействия  как правило оставляют в силе. Наиболее сложным для восприятия и наиболее важным является определения  понятия состояния системы.

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

1.понятие этапа (шага) принятия  решения

2.понятие состояния и соответственно  смысл переменной состояния

3.понятие управляющего воздействия

4.функциональные соотношения, которые  используются для расчета ЦФ  в целом.

 

Модель динамического программирования с процедурой прямой прогонки

Задача 1.

Для расширения трех своих предприятий  фирма выделяет 5 млн.долларов. Каждое предприятие представляет на конкурс  проекты, каждый из которых характеризуется  затратами С и ожидаемыми доходами R. Цель фирмы –получение  максимальных доходов от инвестиций. Первые варианты проекта для всех предприятий в действительности означают сохранение статус кво. На каждое предприятие могут быть выделены инвестиции только для одного проекта.

 

Проект	Предприятие 1		Предприятие 2		Предприятие 3
	С1	R1	C2	R2	C3	R3
1	0	0	0	0	0	0
2	1	5	2	8	1	3
3	2	6	3	9	-	-
4	-	-	4	12	-	-

 

При постановке этой, так и любой  другой задачи, следует четко определить:

1.понятие этапа (шага) приятия  решения

2.понятие состояния и соответственно  смысл переменной состояния (хi)

3.понятие управляющего воздействия

Предположим, что распределение  капиталовложений по проектам осуществляется последовательно по следующим этапам:

1 этап. Выделение средств на  проект первого предприятия

2 этап. Выделение средств на  проект второго предприятий

3 этап. Выделение средств на  проект третьего предприятия

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

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

Х1 – объем инвестиций на первом этапе

Х2 – объем инвестиций, которые  могут быть распределены на первом и втором этапах

Х3 – на всех трех этапах

 

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

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

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

4.Для реализации проекта поиска  оптимального решения, вводятся  следующие математические объекты.  Ri(Ki) – доход i предприятия от реализации Кi проекта (на i этапе)