Применение оптимизационных методов к решению экономических задач. 2

Министерство  сельского хозяйства Российской Федерации

ФГОУ  ВПО  «Оренбургский государственный  аграрный университет» 
 

кафедра организации производства и 

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

Реферативно-прикладное

исследование

Тема: «Применение  оптимизационных методов

к решению  экономических задач» 
 

                                                                           Выполнил:

                                                                                         студент 41 группы

                                                                  отделения экономика и                                                                                                                                                                              управление на предприятии

Олейник Татьяна 

Проверила:

Спешилова Н.В.  
 
 
 

Оренбург  – 2011 г.

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

    Содержание

I Теоретические вопросы…………………………………………………………….3

1.1 Динамическое  программированием……………………………………………..3

1.2 Сетевое  планирование и управление……………………………………………7

1.3 Теория  игр ………………………………………………………………………11

1.4 Теория  массового обслуживания ……………………………………………...14

1.5 Параметрическое  программирование …………………………………………17

II Практические вопросы …………………………………………………………..21

2.1 Применение  параметрического программирования  к решению экономических задач ……………………………………………………………….21

Выводы ……………………………………………………………………………...25

Литература …………………………………………………………………………..27 
 

    I Теоретические вопросы

    1.1 Динамическое программирование

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

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

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

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

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

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

    При постановке задач динамического  программирования следует руководствоваться  следующими принципами:

1. Выбрать параметры (фазовые координаты), характеризующие состояние S управляемой системы перед каждым шагом.
2. Расчленить операцию на этапы (шаги).
3. Выяснить набор шаговых управлений x_i для каждого шага и налагаемые на них ограничения.
4. Определить какой выигрыш приносит на i-ом шаге управление x_i, если перед этим система была в состоянии S, т.е. записать «функцию выигрыша»:

5. Определить, как изменяется состояние системы S под влиянием управления x_i на i-ом шаге: оно переходит в новое состояние

6. Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш W_i(S) (начиная с i-го шага и до конца) через уже известную функцию W_i+1(S):

    Этому выигрышу соответствует условное оптимальное  управление на i-м шаге x_i(S) (причем в уже известную функцию W_i+1(S) надо вместо S подставить измененное состояние

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

8. Произвести условную оптимизацию (m-1)-го, (m-2)-го и т.д. шагов по формуле (1.3), полагая в ней i=(m-1),(m-2),…, и для каждого из шагов указать условное оптимальное управление x_i(S), при котором максимум достигается.

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

9. Произвести безусловную оптимизацию управления, «читая» соответствующие рекомендации на каждом шаге. Взять найденное оптимальное управление на первом шаге ; изменить состояние системы по формуле (1.2); для вновь найденного состояния найти оптимальное управление на втором шаге х₂^* и т.д. до конца.

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

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

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

    1.2 Сетевое планирование  и управление

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

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

    Методы  сетевого планирования и управления дают возможность:

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

    2. предсказать вероятное время выполнения;

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

    4. проверить ход выполнения работ  по плану;

    5. использовать информацию о ходе работ для своевременного планирования времени и затрат.

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

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

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

    Основные  понятия сетевой модели: событие, работа, путь.

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

    Рисунок 1.

    Работа характеризует любое действие, требующее затрат времени или ресурсов. Работами считаются и процессы, не требующие затрат времени и ресурсов, а устанавливающие зависимости выполнения работ. Такие работы называются фиктивными. Работа обозначается парой чисел (i,j) где i – номер события, являющимся начальным для данной работы, j – номер события, являющимся конечным для данной работы, в которое она входит. Каждая работа имеет свою продолжительность t(i,j). Работы на графах обозначаются дугами (стрелками), фиктивные работы обозначаются пунктирными стрелками.

    Событиями называются начало или завершение одной или нескольких работ. Они не имеют протяженности во времени. Событие совершается в тот момент, когда оканчивается последняя работа, входящая в него. На графе события изображаются кружками, внутри которых записывается номер события. В моделях СПУ имеется одно начальное событие (номер 0), одно конечное событие или завершающее (номер N) и промежуточные события (номер i).

    Путь – цепочка следующих друг за другом работ (дуг), соединяющих начальную и конечную его вершины. Полный путь L – путь, начало которого совпадает с начальным событием сети, а конец – с завершающим. Продолжительность пути определяется суммой продолжительностей составляющих его работ. . Путь, имеющий максимальную продолжительность, называют критическим (обозначение L_кр). Продолжительность критического пути обозначается как t_кр_. Работы, принадлежащие критическому пути, называются критическими. Их несвоевременное выполнение ведет к срыву сроков всего комплекса работ.

    Сетевая модель должна удовлетворяет следующим  требованиям:

1. Не должно быть событий с одинаковыми номерами.
2. Для каждой работы (i,j) должно выполняться i <j
3. Должны быть только одно начальное и одно конечное события.
4. Должны отсутствовать циклы, т.е. замкнутые пути, соединяющие событие с ним же самим.

    При выполнении этих требований можно приступать к вычислениям числовых характеристик  СМ.

    При расчетах для сетевой модели определяются следующие характеристики ее элементов.

    Характеристики событий

    1. Ранний срок свершения события tp(0) = 0, tР(j) =тахi{tр(i) + t(ij)}, j=1—N характеризует самый ранний срок завершения всех путей, в него входящих.

    2. Поздний срок свершения события t_п(N) = t_р(N), t_п (i) = min_j {(t_п(j)–t(ij)}, i=1—(N-1) характеризует самый поздний срок, после которого остается ровно столько времени, сколько требуется для завершения всех путей, следующих за этим событием.

    3. Резерв времени события R(T) = t_п(i) – t_р(i) показывает, на какой максимальный срок можно задержать наступление этого события, не вызывая при этом увеличения срока выполнения всего комплекса работ. 

    Характеристики  работы (i,j)

1. Ранний срок начала работы: .
2. Ранний срок окончания работы:
3. Поздний срок начала работы:
4. Поздний срок окончания работы:
5. Резервы времени работ:

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

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

    - свободный резерв  – максимальный запас времени, на который можно задержать начало работы или (если она началась в ранний срок) увеличит ее продолжительность, не изменяя ранних сроков начала последующих работ;

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

    Характеристики  путей.

    Путь  характеризуется двумя показателями — продолжительностью и резервом. 

    Продолжительность пути равна сумме продолжительностей составляющих ее работ.

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

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

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

    1.3 Теория игр

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

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

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

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

    В общем виде постановка задачи парной игры с нулевой суммой сводится к  следующему виду : если два игрока Р1 и Р2 играют в какую-либо игру, то как должен вести партию каждый из этих игроков, чтобы достигнуть наиболее благоприятного для себя исхода. При случайных ходах этих двух игроков естественной оценкой благоприятного исхода является среднее значение, которое обозначается символом аij. Если известны значения aij выигрыша, то парную игру можно записать в виде прямоугольной таблицы, которая называется матрицей выигрышей или платежной матрицей. Она имеет такой вид: 

        В матрице xi обозначают ходы игрока Р1, а yi – ходы игрока Р2.

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

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

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

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

    1.4 Теория массового  обслуживания

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

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