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

 

 

 

 

 

Реферат

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Цель работы:

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

 

1. Теоретические вопросы
1. Динамическое программирование………………………………………….4
2. Сетевое планирование и управление……………………………………….7
3. Теория игр…………………………………………………………………..13
4. Теория массового обслуживания………………………………………….17
5. Стохастическое программирование………………………………………24
2. Применение динамического программирования  к решению

экономических задач……………………………………………………………….28

Выводы……………………………………………………………………………...32

Список использованной литературы……………………………………………...34

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

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

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

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

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

Итак, при решении оптимизационной  задачи методом динамического программирования необходимо учитывать на каждом шаге последствия, к которым приведет в будущем решение, принимаемое в данный момент. Исключением является последний шаг, которым процесс заканчивается. Здесь процесс можно планировать таким образом, чтобы последний шаг сам по себе приносил максимальный эффект. Спланировав оптимальным образом последний шаг, можно к нему «пристраивать» предпоследний так, чтобы результат этих двух шагов был оптимальным, и т. Д. Именно так от конца к началу — и можно развернуть процедуру принятия решений. Но чтобы принять оптимальное решение на последнем шаге, надо знать, чем мог закончиться предпоследний шаг. Значит, надо сделать разные предположения о том, чем мог закончиться предпоследний шаг и для каждого из предположений найти решение, при котором эффект на последнем шаге был бы наибольшим. Такое оптимальное решение, найденное при условии, что предыдущий шаг закончился определенным образом, называют условно-оптимальным.

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

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

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

 

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

 

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

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

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

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

- представление планов в виде  сети;

- определение календарных графиков;

- определение вероятных величин;

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

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

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

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

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

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

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

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

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

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

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

Сущность метода сетевого планирования и управления  заключается в особом моделировании исследуемого процесса, а именно – создаётся информационно-динамическая модель задачи.

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

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

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

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

Пример сетевого графика, приведенный на рисунке 1, описывает следующее положение.

Событие 1 обозначает, что  началась работа а. Событие 2 фиксирует окончание работы и начало работ b и c. Иначе, условием для начала работы b и работы c является окончание работы а. Работу d нельзя начать –до окончания работы b, а работу e — до окончания работы с. Наступление события 5 знаменует собой окончание работ d и е и одновременно завершение всего комплекса.

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

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

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

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

Работа – это некоторый процесс, приводящий к достижению определенного результата и требующий затрат каких-либо ресурсов, имеет протяженность во времени. Термин «работа» может иметь следующие значения:

1. действительная работа, требующая затрат времени и ресурсов на определённую операцию;

2. «ожидание» – т.е. процесс, не требующий затрат труда, но занимающий время (например, процесс отвердения бетона, высыхание краски и т.п.);

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

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

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

 

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

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

 

 

 

 

 

В описанном способе  представления комплекса работ  используют язык «события-работы».

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

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

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

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

1.3 Теория игр

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

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

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

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

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

Типы игр:

Кооперативная, либо коалиционная игра – это игра, в которой игроки могут объединяться в группы, накладывая на себя определенные обязательства перед другими участниками этой группы и координируя свои действия в выборе тактики приемлемой для достижения целей всей группы. Не кооперативная игра – это игра, где каждый игрок играет по принципу «каждый сам за себя».

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

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

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

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

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

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

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

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

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

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

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

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

 

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

 

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

Задачи теории массового  обслуживания

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