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

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

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

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

Тема: «Динамическое программирование»

Оренбург 2005

Содержание

I Цель работы

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

2.1 Теория игр

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

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

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

III Практическое применение динамического программирования

IV Выводы по результатам работы

Список литературы

I Цель работы

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

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

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

- рассмотреть понятие «динамическое программирование»;

- показать механизм решения экономической задачи при помощи динамического программирования;

- ознакомиться с элементами теории игр;

- показать методы сетевого планирования и управления;

- ознакомиться с моделированием систем массового обслуживания;

- сделать выводы по результатам работы.

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

2.1 Теория игр

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

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

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

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

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

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

v₁ + v₂ + ... + v_i + … + v_n = 0 (1)

Число v₁ может быть положительным, отрицательным и равным нулю. При v₁ > 0 - выигрыш, v₁ < 0 - проигрыш и v₁ = 0 - ничейный исход.

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

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

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

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

В общем виде постановка задачи парной игры с нулевой суммой сводится к следующему: если два игрока P₁ и P₂ играют в какую-либо игру, то как должен вести партию каждый из этих игроков, чтобы достигнуть наиболее благоприятного исхода для себя. При случайных ходах (действиях) этих игроков естественной оценкой благоприятного исхода (выигрыша) является его среднее значение, которое обозначается символом a_ij. Если известны значения a_ij выигрыша, то парную игру можно записать в виде прямоугольной таблицы, которая называется матрицей выигрышей или платежной матрицей. Она имеет такой вид:

В матрице x₁ обозначают ходы игрока Р₁, а y_j - ходы игрока Р₂.

В любой игре важное значение имеет стратегия, под которой понимается совокупность правил, определяющих выбор при каждом личном ходе игрока, в зависимости от ситуации, сложившейся в процессе игры. В матричных играх применяются чистые и смешанные стратегии. Стратегии с компонентом, равным единице, называются чистыми стратегиями. Они обозначаются для игрока Р₁ через = (0,..., 0,1,0, …, 0), где единица стоит на i-м месте (i= 1,2, …, m), и аналогично для игрока Р₂ = (0, …,0,1,0, …,0), где единица стоит на j-м месте (j=1,2, …,n). Стратегии с отличными от единицы компонентами, представляющими вероятные её доли, называются смешанными. Если игра ведется в смешанных стратегиях, то игрок Р₁ из своих m чистых стратегий может их выбирать с частотами x₁, x₂, …,x_m, а игрок Р₂ имеющий n чистых стратегий, может их выбрать с частотами y₁, y₂, …, y_n. Набор смешанных стратегий, используемых в игре, должен отвечать требованиям (2) и (3) :

для игрока Р₁

x₁+x₂+…+x_m=1(2)

x₁>=0, x₂>=0, …, x_m>=0

для игрока Р₂

y₁+y₂+…+y_n=1(3)

y₁>=0, y₂ >=0, …, y_n >=0

Как видно, чистая стратегия является частным случаем смешанной стратегии, в которой все стратегии, кроме одной, применяются с нулевыми частотами, а одна применяется с частотой 1. (2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В принципе динамическое планирование может разворачиваться и в прямом направлении, т. е. от первого шага процесса к последнему. (4)

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

Сетевое планирование и управление возникло в 1957 - 1958 гг. под названием «метод критического пути» и метод PERT (метод оценки и пересмотра планов).

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

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

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

3) определение вероятностных величин;

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

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

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

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

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

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

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

4) проверить ход выполнения работ по плану после того, как план приведен в действие;

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

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

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

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

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

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

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

Помимо графического изображения работ, которые предполагается выполнить для достижения намеченной цели, сетевой график содержит некоторые оценки (времени, стоимости, ресурсов, технической надежности элементов), даваемые каждой работе в отдельности. Эти оценки могут быть точными или приближенными. С известной вероятностью появления каждой из них. Сетевой график с нанесенными на него оценками служит основой для последующего анализа возможных изменений и контроля за его выполнением. Основными параметрами, которые оцениваются при таком анализе, служат время и затраты. Эти два фактора, как правило, находятся в непосредственной зависимости один от другого: чем короче заданный срок выполнения работ, тем больше затрат потребуется на их выполнение, и наоборот. Анализ сетевого графика в системе СПУ позволяет выбрать оптимальный вариант плана, обеспечивающий выполнение всех работ в заданные сроки с минимальными затратами. Система СПУ предусматривает либо одну оценку времени для выполнения каждой работы - «наиболее вероятное время», либо три оценки: «оптимистическую», «пессимистическую» и «наиболее вероятную» оценки времени по каждой работе. Эти три оценки используются для расчета среднего ожидаемого времени выполнения работ и вычисления вероятности выполнения программы в заданные сроки. Несмотря на указанные и некоторые другие различия в методах анализа сетевых моделей, общая их идея одна - все они используют графическое построение в виде сети с временными или другими оценками для планирования действий, приводящих в конечном итоге к желаемому результату. (5)

III Практическое применение динамического программирования

Задача о выборе наиболее экономного маршрута доставки груза.

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

рис. 1

Для решения задачи методом динамического программирования разобьем все пункты сети на группы (табл. 1).

Таблица 1

К группе I отнесем пункт 1, к группе II - пункты, в которые можно попасть из пункта 1 (таковыми будут 2; 3; 4), к группе III отнесем пункты, в которые можно попасть непосредственно из любого пункта группы II (таковыми будут 5; 6; 7), и т.д. в результате движение транспорта с грузом из пункта 1 в пункт 10 примет поэтапный характер: на первом этапе транспорт перемещается из пункта 1 в какой-то пункт группы II, на втором этапе - из пункта группы II в пункт группы III и т.д. Вместе с этим и процесс нахождения наиболее экономного маршрута из пункта 1 в пункт 10 распадается на шаги. На каждом шаге надо так выбрать маршрут следования груза в пункт соседней группы, чтобы доставка груза по всему маршруту была сопряжена с минимальными затратами. Избранный нами подход к решению задачи учитывает особенности сети, изображенной на рис. 1: после разбиения на группы пункты, оказавшиеся в одной и той же группе, дорогами не соединены.

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

В данном случае процесс состоит из четырех шагов (рис. 2). Будем оптимизировать каждый шаг, начиная с последнего - четвертого. На этом шаге в пункт 10 можно попасть из пункта 8 или 9, причем из каждого пункта только одним способом. Если предпоследний, третий, шаг привел груз в пункт 8, то дальше следует двигаться по маршруту 8 - 10, и затраты на перевозку единицы груза будут равны единице; если же в пункт 9 - то следует двигаться по маршруту 9 - 10, на котором затраты составят 4 единицы. Условное оптимальное решение помечаем на сети стрелкой, выходящей из соответствующего кружка, а величину затрат записываем в нижней половинке кружка.

1 шаг 2 шаг 3 шаг 4 шаг

рис.2

Переходим к оптимизации предпоследнего, третьего, шага. Для этого рассмотрим все возможные исходы предшествующего, второго, шага. После этого шага груз может оказаться только в одном из пунктов - 5,6,7. Для каждого пункта выбираем условное оптимальное решение - оптимальный маршрут в пункт 10 и соответствующие минимальные затраты. Так, если груз оказался в пункте, 5, то далее можно следовать либо через пункт 8, либо через пункт 9. В первом случаи затраты равны 7+1=8 единицам, во втором - 5+4=9 единицам. Значит, условный оптимальный маршрут из пункта 5 в пункт 10 проходит через пункт 8, а условные минимальные затраты составляют 8 единиц. На ребре 5 - 8 сети ставим стрелку, а в кружке 5 записываем минимальные затраты: 8=7+1. ребро 5 - 9 остается без стрелки. Аналогично для пункта 6 находим условно-оптимальный маршрут 6 - 8 - 10 с затратами в 4 единицы; для пункта 7 - условно-оптимальный маршрут 7 - 9 - 10 с затратами в 5 единиц.

Далее оптимизируем путь доставки груза на втором шаге процесса. Для этого рассматриваем все возможные исходы первого шага. После первого шага груз мог оказаться только в одном из пунктов: 2, 3 или 4. При нахождении условного оптимального решения в каждом из этих пунктов надо просмотреть все возможные маршруту их этого пункта и для каждого из них найти сумму затрат на этом шаге и условных минимальных затрат на оптимальном продолжении маршрута, уже построенном для следующего пункта. Этого требует принцип оптимальности. Из всех возможных маршрутов выбирается тот, для которого эта сумма меньше (если суммы равны, выбирается любой маршрут). Для пункта 2 оптимальным будет маршрут 2 - 6 - 8 - 10 с затратами 12+4=16 единиц; для пункта 3 - маршрут 3 - 7 - 9 - 10 с затратами 7+5=12 единиц; для пункта 4 - маршрут 4 - 7 - 9 - 10 с затратами 13+5=18 единиц.

Оптимизируем, наконец, первый шаг. Для выбора условного оптимального решения рассматриваем три возможных маршрута: через пункты 2, 3 или 4. Устанавливаем, что наивыгоднейшим будет маршрут 1 - 3 с затратами в 17 единиц. Итак, этап условной оптимизации закончен, и остается пройти процесс в направлении от пункта 1 к пункту 10 и прочитать оптимальный маршрут: 1 - 3 - 7 - 9 - 10.

Заметим, что на первом этапе нами выбран маршрут 1- 3 доставки груза, по которому затраты в 2,5 раза превышают затраты на маршруте 1 - 2 и в 5 раз на маршруте 1 - 4. Оказалось, что с точки зрения всего четырехэтапного маршрута, а не одного первого этапа, следует пойти на «жертву» на первом этапе с тем, чтобы минимизировать общие затраты на всем четырехэтапном маршруте. Это иллюстрирует одну из главных особенностей метода: выбирать решение на каждом шаге, руководствуясь не выгодой, получаемой на данном шаге, а общей выгодой, получаемой по окончании всего процесса.

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

рис. 3

IV Выводы по результатам работы

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

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

Список литературы:

1. Баканов М.И., Шеремет А.Д. Теория экономического анализа: Учебник. - 4-е изд., доп. и перераб. - М.: Финансы и статистика, 1999

2. Браславец М.Е. Экономико-математические методы в организации и планировании сельскохозяйственного производства, 1974

3. Кравченко Р.Г., Попов И.Г., Толпекин С.З. Экономико-математические методы в организации и планировании сельскохозяйственного производства, 1974

4. Кузнецов А.В., Холод Н.И. Математическое программирование: [ Учеб. Пособие для эконом. спец. вузов]. - Мн.: Выш. шк., 1984. - 221 с., ил.

5. Кузнецов Ю. Н. и др. Математическое программирование. Учеб. пособие для вузов. М., «Высш. школа», 1976. - 352с. с ил.