Методы оптимальных решений

Содержание

 

Задание 1.8 3

Задание 2.8 14

Задание 3.8 21

Задание 4.8 23

Задание 5.8 28

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание 1.8

 

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

 

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

     Система СПУ  позволяет:

- формировать календарный  план реализации некоторого комплекса  работ;

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

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

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

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

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

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

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

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

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

Рисунок 1.1 – Сетевая модель

 

     Анализ сетевого  графика, представленного в графической или табличной (матричной) форме, позволяет:

- более четко выявить взаимосвязи этапов реализации проекта;

- определить наиболее оптимальный порядок выполнения этих этапов в целях, например, сокращения сроков выполнения всего комплекса работ.²

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

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

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

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

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

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

     Математический аппарат сетевых моделей базируется на теории графов.

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

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

     В экономике чаще всего используются два вида графов: дерево и сеть.

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

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

     В сетевой модели имеется начальное событие (с номером  1), из которого работы только выходят, и конечное событие (с номером N), в которое работы только входят.

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

     Перед расчетом СМ следует убедиться, что она удовлетворяет следующим основным требованиям:

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

- нумерация событий начинается с исходного события, которому присваивается № 1;

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

- затем вычеркивают работы, выходящие из события № 2, и вновь находят событие, в которое не входит ни одна работа, и ему присваивают № 3, и так продолжается до завершающего события, номер которого должен быть равен количеству событий в сетевом графике;

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

     2. Отсутствуют тупиковые события (кроме завершающего), т. е. такие, за которыми не следует хотя бы одна работа (событие 5).

     3. Отсутствуют события (за исключением исходного), которым не предшествует хотя бы одна работа (событие 7).

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

Рисунок 1.2 – Неверно построенная сетевая модель

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

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

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

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

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

     Ранний срок  свершения события определяется величиной наиболее длительного отрезка пути от исходного до рассматриваемого события, причем t_р(1)=0, a t_р(N)=t_Kp(L):

t_р(j) = max{t_р(j)+(i,j)};   j=2,…, N

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

t_n(i) = min{t_n(i)-t(i,j)};  j=2,…, N-1

     Этот показатель определяется «обратным ходом», начиная с завершающего события, с учетом соотношения t_n(N) = t_p(N).

     Все события, за исключением событий, принадлежащих критическому пути, имеют резерв R(i):

R(i) = t_n(i)-  t_p(i)

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

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

t_pn(i,j) = p(i)

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

t_po(i,j) = t_p(i) + t(i,j);

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

t_пн(i,j) = t_n(j) - t(i,j)

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

t_no(U) = t_n(j)

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

R_n(i,j) = t_n(j) - t_p(i) - t(i,j)