Математические методы управления проектом

Размещено на http://www.allbest.ru/

Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования

«Финансовый университет при Правительстве Российской Федерации»

Смоленский филиал Финуниверситета

Кафедра математики и информатики

Контрольная работа

«Математические методы управления проектом»



Введение

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

Начало развития динамического программирования относится к 50-м годам ХХ в. и связано с именем Ричарда Эрнеста Беллмана.

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

-при разработке правил управления запасами;

-при распределении инвестиционных ресурсов между альтернативными проектами;

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

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

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

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

· задача о наибольшей общей подпоследовательности;

· связь динамического программирования и регулярных выражений;

· задача об оптимальной триангуляции;

· задача о загрузке.

программирование динамический оптимальность



1. Предпосылки метода динамического программирования

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

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

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

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

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

Предпосылки динамического программирования:

· Характеристика системы зависит только от данного состояния системы, а не от того каким путем система пришла в это состояние.

· Переход системы из одного состояния в другое длится определенное конечное число шагов.

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

· Общий эффект за несколько шагов складывается из эффектов на каждом шаге.

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

Разбиение задачи на подзадачи меньшего размера.

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

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

Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).

Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи, <math> F_3 = F_2 + F_1 </math> и <math> F_4 = F_3 + F_2 </math> -- даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали <math>F_2</math> дважды. Если продолжать дальше и посчитать <math>F_5</math>, то <math>F_2</math> посчитается ещё два раза, так как для вычисления <math>F_5</math> будут нужны опять <math>F_3</math> и <math>F_4</math>. Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решения для задач, которые он уже решал.

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

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

· перекрывающиеся подзадачи;

· оптимальная подструктура;

· возможность запоминания решения часто встречающихся подзадач.

Динамическое программирование обычно придерживается двух подходов к решению задач:

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

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

Языки программирования могут запоминать результат вызова функции с определенным набором аргументов (мемоизация), чтобы ускорить «вычисление по имени». В некоторых языках такая возможность встроена (например, Scheme, Common Lisp, Perl), а в некоторых требует дополнительных расширений (C++).

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

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

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

2. Принцип оптимальности и уравнение Беллмана

Формулировка принципа оптимальности: "Оптимальное поведение обладает тем свойством, что, каковы бы ни были первоначальное состояние и решение (т.е. управление) в начальный момент, последующие решения должны составлять оптимальное поведение относительно состояния, получающегося в результате первого решения". Доказательство необходимости принципа оптимальности можно легко получить, рассуждая от противного: если вы не используете наилучшим образом то, чем вы располагаете, то вы никогда не распорядитесь наилучшим образом и тем, что вы могли бы иметь в дальнейшем. x (фазовая координата) x(t1) x*(t) 2 x() 1 x(t0) t0 t1 t (время) На рисунке дана иллюстрация принципа на примере задачи с одной фазовой координатой. Кривая x*(t) (t0tt1) - это фазовая траектория, соответствующая оптимальному управлению, начальное и конечное состояния - фиксированы. Вся траектория поделена на две части относительно момента времени . Согласно принципу оптимальности, траектория 2, определенная при tt1, должна представлять собой оптимальную траекторию по отношению к начальному состоянию x(). Следовательно, вторая часть оптимальной траектории сама по себе должна быть оптимальной траекторией, вне зависимости от того, что происходило с системой до того, как она пришла к состоянию, являющемуся начальным для второй части траектории. Предположим, что общая задача управления (1) имеет решение. Максимальное значение целевого функционала задачи с начальным состоянием x и начальным временем t J*(x, t) назовем функцией оптимального поведения. Отметим, что в то время как J представляет собой функционал, зависящий от {u(t)}, J* является функцией, зависящей от n+1 параметров x и t. Таким образом, задача оказывается "погруженной" в более широкий класс задач, характеризуемых значениями n+1 начальных параметров. Оптимальной значение целевой функции исходной задачи (1) имеет, таким образом, вид

J* = J*(x0, t0).

Если J*(x, t) является функцией оптимального поведения для задачи с начальным состоянием x в момент t, то, согласно принципу оптимальности J*(x+x, t+t) является функцией оптимального поведения для второй части оптимальной траектории с начальным моментом времени t+t и начальным состоянием x+x. Поскольку прирост функции оптимального поведения на протяжении всего промежутка времени между t и t+t может происходить только за счет изменения подынтегральной функции, то он равен I(x,u,t)t. Значения функции оптимального поведения на всем интервале времени, начавшимся в момент t, представляют собой оптимальную сумму вкладов двух частей этого интервала времени. Таким образом, приходим к основному рекуррентному соотношению

J*(x, t) = {I(x, u, t)t + J*(x+x, t+t)}

В динамическом программировании существенную роль играет предположение, что функция оптимального поведения J*(x, t) представляет собой однозначную и непрерывно дифференцируемую функцию от n+1 переменных. Иначе говоря, решения задач более широкого класса являются однозначными и непрерывными функциями относительно изменений начальных параметров. (Отметим, что во многих задачах эти предположения о гладкости не выполняются, кроме того, заранее вообще неизвестно, будут ли они выполнены в данной конкретной задаче). Благодаря этому предположению можно разложить J*(x+x, t+t) в точке (x, t) по формуле Тейлора

J*(x+x, t+t) = J*(x, t) + x + t + …

0 = {I(x, u, t) + + + … }.

Переходя к пределу при t 0 с учетом того, что = x' = f(x, u, t), получаем - {I(x, u, t) + f(x, u, t)}. (4) Уравнение (4) называется уравнением Беллмана и является основным дифференциальным уравнением в частных производных, используемых в динамическом программировании. Так как второе слагаемое в (4) представляет собой скалярное произведение вектора-строки и вектора-столбца f(x, u, t), то уравнение Беллмана можно записать как - = {I(x, u, t) +fj(x, u, t)}. С уравнением Беллмана связано в качестве граничного условия ограничение, налагаемое на конечное состояние:

J*(x(t1), t1) = F(x1, t1).

Это условие показывает, что значение функции оптимального поведения для задачи, начальным моментом и начальным состоянием которой являются соответственно конечный момент и конечное состояние, равно значению функции F, рассчитанному в данный момент времени при данном состоянии. Если бы уравнение Беллмана было решено, то мы получили бы функцию оптимального поведения и, следовательно, оптимальное значение целевой функции для исходной задачи можно было бы определить как частное значение этой функции при указанных в формулировке задачи конкретных начальных условиях. Однако в общем случае это уравнение в частных производных первого порядка, как правило, нелинейное, не имеет аналитического решения. В принципе можно решать уравнения Беллмана, представленные в виде разностных схем, на ЭВМ с большим быстродействием. Однако даже современные ЭВМ, работающие с высокой скоростью счета, не обладают такой машинной памятью, которая позволяла бы найти достаточно хорошее приближение к решению даже при не очень больших размерностях. Беллман назвал это препятствие "проклятьем размерности" ("curse of dimensionality"). Решение многошаговых задач оптимизации методом динамического программирования Во многих динамических задачах время рассматривается не как непрерывная, а как дискретная величина. Задачи такого типа называются многошаговыми задачами оптимизации. Они могут решаться методом динамического программирования. Рассмотрим некоторую динамическую систему S. Пусть на k-м шаге (k = 1, 2, ..., n) состояние системы определяется совокупностью чисел (фазовыми координатами) X =( ), которые получены в результате реализации управления Uk, обеспечивающего переход системы S из состояния X в состояние X . Будем полагать, что X зависит от X и Uk и не зависит от того, как система пришла в состояние X (свойство отсутствия последействия). Пусть Wk(X , Uk) есть доход (выигрыш), полученный в результате реализации k-го шага. Тогда общий выигрыш полагаем равным F = Wk(X , Uk) (свойство аддитивности целевой функции). Совокупность управлений, в результате реализации которых система S переходит за n шагов из начального состояния X0 в конечное X и при этом функция F принимает наибольшее значение, будем называть оптимальной стратегией управления. Принцип оптимальности Беллмана. Каково бы ни было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был бы максимальным. Оптимальную стратегию можно получить, если сначала найти оптимальную стратегию управления на последнем n-м шаге, за тем на двух последних шагах и т.д. вплоть до первого шага. Таким образом, решение задачи динамического программирования целесообразно начинать с определения оптимального решения на последнем n-м шаге. Для того, чтобы найти это решение, нужно сделать всевозможные предположения о том, как мог закончиться предпоследний шаг и с учетом этого выбрать управление , обеспечивающее максимальное значение функции Wn(X , Un). Такое управление , выбранное при определенных предположениях о том, как окончился предыдущий этап, называется условно оптимальным. Принцип оптимальности Беллмана требует находить на каждом шаге условно оптимальные управления для любого из возможных исходов предыдущего шага. Обозначим через Fn(X0) максимальный доход, получаемый за n шагов при переходе системы S из начального состояния X0 в конечное состояние X , а через Fn-k (X ) - то же при переходе из X в X и оптимальном управлении на последних n-k шагах. Тогда

Fn(X0) = [W1(X0, U1) + W2(X1, U2) + ... + Wn(X , Un)], Fn-k(X0) = [Wk+1(X, Uk+1) + Fn-k-1(X )],

Последнее соотношение называется основным функциональным уравнением Беллмана и представляет собой математическую формулировку принципа оптимальности. Положим k = n - 1. Тогда F1(X ) = [Wn(X , Un) + F0(X )], (*) где F0(X ) считаем известным. Используя (*) и рассматривая всевозможные допустимые состояния X , X , ... , X , ... , системы на (n-1)-м шаге находим условно-оптимальные управления (X ), (X ), ... , (X ), ... , и соответствующие значения функции (*): (X ), (X ),..., (X ), ... . Таким образом, на n-м шаге находим условно-оптимальное управление при любом допустимом состоянии системы после (n-1)-го шага. Т.е., в каком бы состоянии система не оказалась после (n+1)-го шага, нам уже известно, какое следует принять решение на n-м шаге. Известно и соответствующее значение функции (*). Переходим к рассмотрению функционального уравнения при

k = n - 2. F2(X ) = [Wn-1(X , Un-1) + F1(X )],

Для того, чтобы найти значение F2 для всех допустимых значений X , очевидно, необходимо знать Wn-1(X , Un-1) и F1(X ). Но F1(X ) мы уже определили на предыдущем шаге. Поэтому нужно произвести вычисления для Wn-1(X , Un-1) при некотором наборе допустимых значений X и соответствующих управлений Un-2. Эти вычисления позволят определить условно оптимальное управление U для каждого X . Каждое из таких управлений совместно с уже выбранным управлением на последнем шаге обеспечивает максимальное значение дохода на двух последних шагах. Последовательно осуществляя этот итерационный процесс, дойдем, наконец, до первого шага. На этом шаге нам известно, в каком состоянии может находиться система (в начальном). Поэтому уже не требуется делать предположения о допустимых состояниях системы, а остается лишь только выбрать управление, которое является наилучшим с учетом условно оптимальных управлений, уже принятых на всех последующих шагах. Таким образом, в результате последовательного прохождения всех этапов от конца к началу определяем максимальное значение выигрыша за n шагов и для каждого из них находим условно оптимальное управление. Чтобы найти оптимальную стратегию управления, то есть определить искомое решение задачи, нужно теперь пройти всю последовательность шагов, только на этот раз от начала к концу. А именно - на первом шаге в качестве оптимального управления возьмем найденное условно оптимальное управление U . На втором шаге найдем состояние X , в которое переводит систему управление . Это состояние определяет условно оптимальное управление U (X ), которое теперь будем считать оптимальным ( ). Зная , находим X = (X ), а значит - определяем = U (X ), и т.д. В результате этого находим решение задачи, то есть максимально возможный доход и оптимальную стратегию управления U*, включающую оптимальные управления на отдельных шагах ( , , ... , ). Таким образом, мы рассмотрели нахождение решения задачи динамического программирования в общем виде. Этот процесс является довольно громоздким, поэтому он используется обычно с применением ЭВМ. Отметим также, что изложена только идея, которая должна быть реализована в том или ином виде для каждого частного случая и далеко не всегда очевидно, как это сделать.

3. Формирование эффективного проекта с помощью методов сетевого моделирования

В задаче требуется:

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

2) рассчитать временные параметры сетевого графика (среднего времени выполнения работы, раннего и позднего сорока свершения событий);

3) определить полный и свободный резерв времени выполнения работ;

4) определить критический путь сетевого графика и осуществить его выделение на рисунке;

5) оценить вероятность выполнения комплекса работ в установленный срок;

6) рассчитать коэффициент сложности сетевого графика и коэффициенты напряжённости для заданных работ;

7) осуществить оптимизацию сетевого графика методом «время-стоимость».

При составлении некоторого проекта выделено 12 событий: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 и 24 связывающие их работы: (0>1), (0>3), (0>5), (1>2), (1>3), (1>4), (2>7), (3>4), (3>5), (3>6), (4>6), (4>7), (5>6), (5>8), (5>9), (6>7), (6>8), (6>9), (6>10), (7>10), (8>9), (9>10), (9>11), (10>11).

На основании исходных данных был построен и упорядочен сетевой график (рис 1).

Рис. 1 Сетевой график

Каждая работа имеет три временные оценки: оптимистическую, пессимистическую и наиболее вероятную; по формуле определяется среднее время выполнения работы (табл. 1.1).

Сред. длит. работы:



Таблица 1.1 Временные параметры работ

Работа Pi,j	аij	bij	mij		Работа Pi,j	аij	bij	mij		Работа Pi,j	аij	bij	mij
0,1	2	10	9	8	3,5	1	9	8	7	6,10	4	6	5	5
0,3	14	16	12	13	3,6	3	9	6	6	6,9	14	16	12	13
0,5	2	12	10	9	4,7	2	10	9	8	6,8	7	9	8	8
1,2	1	13	10	9	4,6	2	4	3	3	7,10	2	8	5	5
1,4	4	12	5	6	5,6	2	12	10	9	8,9	3	5	4	4
1,3	2	10	3	4	5,8	6	18	9	10	9,10	5	7	6	6
2,7	2	4	3	3	5,9	4	12	5	6	9,11	5	21	19	17
3,4	5	19	9	10	6,7	1	7	4	4	10,11	14	20	11	13

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

Ранний срок

tj=max (ti+tj)

Поздний срок

tj*=min (t*j-tij)

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

Полный резерв времени

M*ij=t*j-ti-tij

Свободный резерв времени

Mij=tj-ti-tij

Результаты расчетов сведены в табл. 1.2. В графе А указан порядковый номер работ, в графе Б - код работы. В графах со 2 по 5 приведены временные параметры событий.

Таблица 1.2

№ П/П	Работа Рi j	Пр.раб tij	Ожидаемое время	Предельное время	Резервы времени работ
			ti	tj	t*i	t*j	M*IJ	MIJ
1	0,1	8	0	8	0	9	1	0
2	0,3	13	0	13	0	13	0	0
3	0,5	9	0	20	0	20	11	11
4	1,2	9	8	17	9	40	23	0
5	1,4	6	8	23	9	26	12	9
6	1,3	4	8	13	9	13	1	1
7	2,7	3	17	33	40	43	23	13
8	3,4	10	13	23	13	26	3	0
9	3,5	7	13	20	13	20	0	0
10	3,6	6	13	29	13	29	10	10
11	4,7	8	23	33	26	43	12	2
12	4,6	3	23	29	26	29	3	3
13	5,6	9	20	29	20	29	0	0
14	5,8	10	20	37	20	38	8	7
15	5,9	6	20	42	20	42	16	16
16	6,7	4	29	33	29	43	10	0
17	6,10	5	29	48	29	48	14	14
18	6,9	13	29	42	29	42	0	0
19	6,8	8	29	37	29	38	1	0
20	7,10	5	33	48	43	48	10	10
21	8,9	4	37	42	38	42	1	1
22	9,10	6	42	48	42	48	0	0
23	9,11	17	42	61	42	61	2	2
24	10,11	13	48	61	48	61	0	0

Требуется оценить вероятность выполнения проекта в директивный срок, равный 63 временным единицам. Для данного сетевого графика дисперсии продолжительности работ критического пути рассчитываются по формуле (2.5); они равны:

уІ (0>3) = 0,1; уІ (3>5) = 1,8; уІ (5>6) = 2,8; уІ (6>9) = 0,1; уІ (9>10) = 0,1; уІ (10>11) = 1

Дисперсия длительности пути (2.5)

уijІ=

=

==2,43

Тогда искомая вероятность

P(tкр?63)=Ф()=Ф(0,82)=0,795?0,8

Рассчитаем нормальную функцию распределения с помощью функции «НОРМРАСП» в среде MS EXCEL.

Рассчитаем коэффициент сложности сетевого графика:

kсл==24/12=2 -

следовательно, сетевой график средней сложности.

Рассчитаем коэффициент напряженности для любой работы (1->4)

Kн==Кн==0.59

Максимальный путь, проходящий через работу 1>4: 0>1>4>6>9> 10>11, имеет продолжительность t(Lmax) =49 (временных единиц). Максимальный путь L4 совпадает с критическим на отрезке 6>9> 10>11 продолжительностью t'кр =32 временные единицы.

Работу 1>4 можно отнести к резервной зоне.

Проведём частную оптимизацию сетевого графика методом «время-стоимость». Граничные значения продолжительностей работ аij и bij, их стоимости сij, коэффициенты затрат на ускорение работ hi,j приведены в табл. 1.3. Свободные резервы времени работ были вычислены ранее (см. табл. 1.2). Их ненулевые значения даны в табл. 1.3. Там же представлены результаты частной оптимизации рассматриваемой сети.

В табл. 1.3 представлены параметры лишь тех работ, которые имеют свободный резерв времени. Стоимости ci,j остальных работ: c(0,1) = 50; c(0,3) = 45; c(1,2) = 82; с(3,4) = 55; с(3,5) = 72; с(5,6) = 30; с(6,7) = 26; с(6,9) = 75;с(6,8) = 42; с(9,10) = 35; с(10,11) = 10 (усл. ден. ед.). Подчеркнуты те работы, свободные резервы времени которых полностью использованы на увеличение их продолжительности.



Таблица 1.3 Оптимизация сетевого графика методом «время-стоимость»

№ п/п	Работа Рi,j	Продолжительность работы		сi,j	Коэффициент затрат на ускорение работы, hi,j	Уменьшение удельной стоимости проекта, ДСij
		ai,i		bi,i
1	0,5	5	9	14	11	60	8	40
2	1,4	4	6	10	9	28	4	16
3	1,3	3	4	6	1	37	12	12
4	2,7	2	3	7	13	86	6	24
5	3,6	4	6	9	10	92	10	30
6	4,7	3	8	14	2	48	5	10
7	4,6	1	3	6	3	64	12	36
8	5,8	5	10	18	7	15	1	7
9	5,9	3	6	12	16	86	7	42
10	6,1	2	5	10	14	44	5	25
11	7,10	1	5	15	10	74	4	40
12	8,9	2	4	8	1	20	3	3
13	9,1	11	17	23	2	40	4	8
Итого	694	-	293

Вывод: за счет сокращения резервов времени стоимость работ может быть снижена на 293 единицы.

Определим общую стоимость работ до оптимизации графика

С=?сij. С=694+ нулевые резервы работ c(0,1) = 50; c(0,3) = 45; c(1,2) = 82; с(3,4) = 55; с(3,5) = 72; с(5,6) = 30; с(6,7) = 26; с(6,9) = 75; с(6,8) = 42; с(9,10) = 35; с(10,11) = 10 = 1216.

После оптимизации сетевого графика стоимость проекта

С`=1216-293=923

(293/1216)*100%=24%,

т.е. стоимость уменьшилась почти на 24%

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

4. Задача. На станке производятся детали в количестве 20 тыс. штук в месяц. Эти детали используются для производства продукции на другом станке с интенсивностью 5000 шт. в месяц. По оценкам специалистов компании, издержки хранения составляют 5 руб. в год за одну деталь. Стоимость производства одной детали равна 2,50 руб., а затраты на подготовку производства составляют 1000 руб. Каким должен быть размер партии деталей, производимой на первом станке и с какой частотой следует запускать производство этих партий? Постройте график общих годовых затрат

Решение

В году 300 рабочих дней, следовательно интенсивность производства продукции на другом станке равна M = 5000 шт. /мес. *12 мес. = 60000шт. /год

Издержки h = 5 руб. /дет. в год. Затраты на подготовку K_опц = 1000 руб. Стоимость производства одной детали C = 2,5 руб. /дет. Производство детали на станке за год P = 20000 шт. /мес. *12 мес. = 240000 шт. /год

Определим размер партии деталей, производимой на первом станке:

Q _опт =

= 5656,854 ? 5656 (дет.)

Z₁ (Q) =

? 171213 (руб.) -

общие годовые затраты.

Строим график общих годовых затрат Z₁ (Q) с помощью таблицы:

Q	Копц*M/Q	h* (P-M) *Q/ (2*P)	Z1 (Q)
1000	6000	1875	211875
2000	3000	3750	183750
4000	1500	7500	172500
5656	1060,82	10605	171213,2
6000	1000	11250	171250
8000	750	15000	172500

Частота запуска производства:

10,6 ? 10 циклов в год.

Периодичность заказов:



0,09 (лет) *300 = 27 дней -

интервал между циклами.

Таким образом, экономичный размер партии равен 5656 деталей, производственных циклов примерно 10 через каждые 27 дней.



Заключение

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



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

1. Орлова И.В., Половников В.А. Экономико-математические методы и модели: компьютерное моделирование: Учеб. пособие. - 3-е изд., перераб. И доп. - М.: Вузовский учебник: ИНФРА-М, 2011. - 389 с.

2. Экономико-математические модели и методы. Линейное программирование: Учебное пособие для студентов экономических специальностей / Составители: Смирнов Ю.Н., Шибанова Е.В., Набережные Челны: Изд-во КамПИ, 2004, 81 с.

3. Гармаш А.Н., Орлова И.В. Математические методы в управлении. Учеб. пособие. - М.: Вузовский учебник: ИНФРА-М, 2012. - 272 с

4. Кузнецов А.В. и др. Высшая математика: Мат. программирование: Учеб./А.В. Кузнецов, В.А. Сакович, Н.И. Холод; Под общ. ред. А.В. Кузнецова. - Мн.: Высш. шк., 1994. - 286 с.: ил.

Размещено на Allbest.ru

...