Сетевая модель и её основные компоненты

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

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

СОДЕРЖАНИЕ

Введение

1 Сетевая модель и её основные компоненты. Порядок и правила построения сетевых графиков

2 Основные параметры сетевых графиков

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

Заключение

Список использованных источников



ВВЕДЕНИЕ

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

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

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

Первые системы, использующие сетевые графики, были применены в США в конце 50-х годов и получили название СРМ (английская аббревиатура, означающая метод критического пути) и PERT (метод оценки и обзора программы). Система СРМ была впервые применена при управлении строительными работами, система PERT - при разработке систем «Поларис».

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

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

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

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

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

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

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

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

Цель работы -- описать и усвоить, что, в общем, представляет собой сетевое планирование и управление (СПУ).

Для достижения поставленной цели следует решить следующие задачи:

- показать, в чём состоит сущность и назначение СПУ,

- дать определение основным элементам СПУ,

- указать правила построения и упорядочения сетевых графиков,

- описать временные показатели СПУ,

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

- определить алгоритм оптимизации комплекса операций по стоимости.

1. СЕТЕВАЯ МОДЕЛЬ И ЕЁ ОСНОВНЫЕ КОМПОНЕНТЫ. ПОРЯДОК И ПРАВИЛА ПОСТРОЕНИЯ СЕТЕВЫХ ГРАФИКОВ

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

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

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

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

Главными элементами сетевой модели являются работы и события.

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

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

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

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

Рисунок 1.1 - Основные элементы сетевой модели



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

Среди событий сетевой модели выделяют исходное и завершающее события. Исходное событие не имеет предшествующих работ и событий, относящихся к представленному в модели комплексу работ. Завершающее событие не имеет последующих работ и событий.

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

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

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

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

При построении сетевого графика необходимо соблюдать ряд правил:

- в сетевой модели не должно быть «тупиковых» событий, то есть событий, из которых не выходит ни одна работа, за исключением завершающего события. Здесь либо работа не нужна и её необходимо аннулировать, либо не замечена необходимость определённой работы, следующей за событием для свершения какого-либо последующего события. В таких случаях необходимо тщательное изучение взаимосвязей событий и работ для исправления возникшего недоразумения;

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

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

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

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

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

Рисунок 1.2 - Примеры введения фиктивных событий

Фиктивные работы и события необходимо вводить в ряде других случаев. Один из них -- отражение зависимости событий, не связанных с реальными работами. Например, работы А и Б (рисунок 2, а) могут выполняться независимо друг от друга, но по условиям производства работа Б не может начаться раньше, чем окончится работа А. Это обстоятельство требует введения фиктивной работы С.

Другой случай -- неполная зависимость работ. Например работа С требует для своего начала завершения работ А и Б, на работа Д связана только с работой Б, а от работы А не зависит. Тогда требуется введение фиктивной работы Ф и фиктивного события 3', как показано на рисунке 2, б.

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

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

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

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

Рисунок 1.3 - Неупорядоченный сетевой график



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

Поместив в I слое начальное событие 0, мысленно вычеркнем из графика это событие и все выходящие из него работы-стрелки. Тогда без входящих стрелок останется событие 1, образующее II слой. Вычеркнув мысленно событие 1 и все выходящие из него работы, увидим, что без входящих стрелок остаются события 4 и 2, которые образуют III слой. Продолжая этот процесс, получим упорядоченный сетевой график.

Рисунок 1.4 - Упорядочение сетевого графика с помощью слоёв

Теперь видим, что первоначальная нумерация событий не совсем правильная: так, событие 6 лежит в VI слое и имеет номер, меньший, чем событие 7 из предыдущего слоя. То же можно сказать о событиях 9 и 10.

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



Рисунок 1.5 - Упорядоченный сетевой график

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

2. ОСНОВНЫЕ ПАРАМЕТРЫ СЕТЕВЫХ ГРАФИКОВ

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

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

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

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

Таблица 1. Временные параметры сетевых графиков

Элемент сети, характеризуемый параметром	Наименование параметра	Условное обозначение параметра
Событие i	Ранний срок свершения события Поздний срок свершения события Резерв времени события	tp (i) tп (i) R(i)
Работа (i, j)	Продолжительность работы Ранний срок начала работы Ранний срок окончания работы Поздний срок начала работы Поздний срок окончания работы Полный резерв времени работы 1-ого вида Частный резерв времени работы 2-ого вида Или свободный резерв времени работы Независимый резерв времени работы	t (i,j) tрн (i,j) tро (i,j) tпн (i,j) tпо (i,j) Rп (i,j) R1 (i,j) Rc (i,j) Rн (i,j)
Путь L	Продолжительность пути Продолжительность критического пути Резерв времени пути	t (L) tкр R(L)

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

, (1)



где - любой пусть, предшествующий i-му событию, т.е. путь от исходного до i-му события сети.

Если событие j имеет несколько предшествующих путей, а следовательно, несколько предшествующих событий i, то ранний срок свершения события j удобно находить по формуле:

. (2)

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

Поэтому поздний (или предельный) срок свершения i - го события равен

, (3)

где - любой путь, следующий за i-м событием, т.е. путь от i-го до завершающего события сети.

Если событие i имеет несколько последующий путей, а следовательно, несколько последующих событий j, то поздний срок свершения события i удобно находить по формуле

. (4)

Резерв времени R(i) i - го события определяется как разность между поздним и ранним сроками его свершения:

(5)

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

Ранний срок начала работы:

(6)

Ранний срок окончательной работы:

(7)

Поздний срок окончания работы:

(8)

Поздний срок начала работы:

(9)

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



(10)

Частный резерв времени:

(11)

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

(12)

Независимый резерв времени:

(13)

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

3. АЛГОРИТМ ОПТИМИЗАЦИИ СЕТЕВОГО ГРАФИКА ПО СТОИМОСТИ

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

Приведём алгоритм оптимизации сетевого графика по стоимости и рассмотрим его на примере.

Пусть комплекс операций представлен сетевым графиком G(E,з). Оперирующая сторона для выполнения комплекса операций располагает m видами ресурсов в количествах R_s (s = 1, m). Каждая операция комплекса характеризуется продолжительностью выполнения t_ij и интенсивностью r(s)ij. Под интенсивностью операции (i,j) будем понимать требуемое количество ресурсов для ее выполнения в течение времени t_ij, например, требуемое количество рабочих или механизмов. Топологически сетевой график удовлетворяет технологическим ограничениям (ресурсные ограничения при составлении сетевого графика не принимались во внимание). Поэтому, прежде чем приступить к выполнению операций сетевого графика, необходимо определить потребное количество ресурсов по календарным срокам и сравнить его с наличными ресурсами. Если окажется, что в отдельные промежутки времени наличного количества ресурсов недостаточно для удовлетворения потребности в них, то ставится задача: найти такие календарные сроки начала и окончания операций сетевого трафика, при которых в любой момент планируемого периода было бы достаточно ресурсов для выполнения операций и время завершения комплекса было бы минимальным. Для простоты изложения алгоритма решения задачи рассмотрим случай, когда интенсивности постоянные и используется один вид ресурсов. Отметим, что приведенный ниже алгоритм не всегда позволяет найти оптимальное решение задачи, однако часто дает хорошее приближение к нему.

Алгоритм решения задачи

Предварительный шаг.

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

Первый шаг

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

Определяем полные резервы времени Rⁿ_ij операций, расположенных над промежутком (ф₀, ф₁). Нумеруем эти операции в порядке возрастания их полных резервов. Операции с одинаковыми полными резервами времени нумеруем в порядке убывания интенсивностей.

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

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

Общий шаг

Предположим, что выполнено k шагов алгоритма и получена линейная диаграмма, момент ф_кр которой является началом оставшейся части комплекса операций.

Проецируем на ось времени начало и конец каждой операции, расположенной над промежутком (ф_k, ф_кр), и обозначаем проекцию, ближайшую к ф_k, через ф_k+1. Таким образом, выделен новый промежуток ⁽ф_k^, ф_k+1⁾.

Определяем полные резервы времени Rⁿ_ij операций, расположенных над промежутком ⁽ф_k^, ф_k+1⁾, и нумеруем их. При этом в зависимости от постановки задачи возможны два случая: 1) операции не допускают перерыва в выполнении; 2) операции допускают перерывы в их выполнении. В первом случае сначала нумеруем операции (i,j), начатые левее момента ф_k, согласно возрастанию разностей между полными резервами этих операций и длительностями от начала момента до момента ф_k+1 (длительности операций обозначим через l_ij). Операции с одинаковыми разностями нумеруем в порядке убывания интенсивностей. Все остальные операции нумеруем в порядке возрастания их полных резервов, а с одинаковыми резервами -- в порядке убывания интенсивностей. Во втором случае все операции нумеруются согласно предписаниям пункта 2 первого шага.

Выполняем то же, что и в пункте 3 первого шага. Однако следует иметь в виду, что если сдвигу подлежит операция (i,j) начатая левее ф_k, то в первом случае сдвигаем всю операцию, т.е. начало этой операции устанавливаем в момент ф_k+1, а во втором случае операцию делим на части и первую часть операции -- отрезок продолжительностью от начала до ф_k -- оставляем на месте, а вторую часть -- от ф_k до конца сдвигаем вправо на величину промежутка (ф_k, ф_k+1). Части разделенной операции в дальнейшем рассматриваем как самостоятельные операции и присваиваем им соответствующие номера событий.

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

Рассмотрим приведённый алгоритм на примере.

Для выполнения комплекса операций, представленного сетевым графиком (рисунок 1), выделено 10 единиц возобновляемых ресурсов (R = 10). Каждой дуге графика приписаны два числа: первое - время выполнения операции в днях; второе -- требуемое количество ресурсов. Необходимо определить сроки выполнения операций таким образом, чтобы завершить весь комплекс за минимальное время. Операции не допускают перерыва в выполнении.

Рисунок 3.1 - Оптимизация комплекса операций по стоимости

Предварительный шаг. Составляем линейную диаграмму (график Ганта) комплекса операций (рисунок 2, а). Построим эпюру потребления ресурса без учета его ограниченности (рисунок 2, б). Из эпюры видно, что в первые четыре дня потребность ресурсов превышает наличное количество на 2 единицы, в 5-й и 6-й день имеется в избытке 3 единицы ресурса, в 7-й и 8-й день снова превышается потребность на 2 единицы, в 9-й день спрос равен 10 единицам, а в последующее время имеется в избытке 8 единиц ресурса.

Найдем на диаграмме критический путь: операция (3,5) заканчивается позже всех операций в момент времени t₅ = 12. Следовательно, она критическая и t_кp = 12. Так как операция (3,5) начинается во время t₃ = 8, то найдем операцию с конечным событием (3), которая заканчивается в это же время. Такой операцией является операция (2,3). Следовательно, (2,3) также критическая. Операции (2,3) непосредственно предшествует критическая операция (1,2). Таким образом, м_кр =(1 -- 2 -- 3 -- 5).

Первый шаг

Проецируем на ось времени начала и концы операций комплекса. Ближайшая проекция к началу координат ф₁ = 4. Рассматриваем промежуток (ф₀, ф₁), где ф₀ = 0.

Над промежутком (ф₀, ф₁) расположены операции (1,2), (1,3) и (1,4). Полные резервы этих операций равны: Rⁿ₁₂ = 0, Rⁿ₁₃ = 4, Rⁿ₁₄ = 3. Нумеруем эти операции по возрастанию полных резервов времени. Операция (1, 2) имеет номер 1, (1,4) - номер 2, и операция (1,3) с наибольшим резервом - номер 3.

Суммируем последовательно величины интенсивности операций, расположенных над промежутком (ф₀, ф₁) в порядке возрастания их номеров, и сравниваем полученные суммы с заданной величиной ресурса R. Так как интенсивность r₁₂ = 4 < R = 10, то операцию (1,2) оставляем на месте. Суммируя величины интенсивности операций (1,2) и (1,4), имеем r₁₂ + r₁₄ = 4 + 3 = 7 < 10. Следовательно, операция (1,4) тоже остается на месте. Добавив к сумме величину интенсивности операции (1,3), имеем r₁₂ + r₁₄ + r₁₃ = 4 + 3 + 5 = 12 > 10. Так как для выполнения операции (1,3) на промежутке (ф₀ , ф₁) не хватает 2 единиц ресурса, то операцию (1,3) сдвигаем вправо на величину отрезка (ф₀, ф₁), т.е. начало операции (1,3) устанавливаем в момент ф₁ = 4. Результаты сдвига отражены на новой линейной диаграмме (рисунок 2, в).

Так как не все операции комплекса просмотрены, то переходим ко второму шагу.

Второй шаг

Начало нового промежутка совпадает с ф₁ = 4, а конец ф₂ = 6 -- с моментом окончания операций (1,2) и (1,4).

Операции (1,2) и (1,4) начинаются левее момента ф₁ поэтому нумеруем их в первую очередь согласно возрастанию разностей Rⁿ₁₂ - l₁₂ = 0 - 6 = - 6 и Rⁿ₁₄ - l ₁₄ = 3 - 6 = - 3 . Таким образом, операция (1,2) имеет номер 1, операция (1,4) -- номер 2 и операция (1,3) -- номер 3.

Суммируя величины интенсивности операций согласно их нумерации и сравнивая с R, получаем, что сдвигу вправо на 2 единицы подлежит операция (1,3). В результате сдвига получаем новую линейную диаграмму (рисунок 2, г). Время выполнения операций по сравнению с исходным вариантом увеличилось на 2 дня: ф₅ = 14.

Решение не закончено, переходим к третьему шагу.

Третий шаг

Новый промежуток (ф₂, ф₃). Момент ф₃ = 8.

Над промежутком (ф₂, ф₃) операций, начатых левее момента ф₂, нет, следовательно, нумеруем операции, лежащие над промежутком по возрастанию полных резервов: (1,3) - номер 1, так как Rⁿ₁₃= 0; (2,3) - номер 2, так как Rⁿ₂₃ = 2; (4,5) - номер 3, (2,5) - номер 4, так как Rⁿ₄₅ = Rⁿ₂₅ = 5, r₄₅ = 5 > r₂₅ = 3. (Нумерация операций (2,5) и (4,5) произведена по убыванию их интенсивностей.)

Так как r₁₃ = 5 < 10 и r₁₃ + r₂₃ = 5 + 4 = 9 < 10, то эти операции не сдвигаются. Операции (4,5) и (2,5) сдвигаем вправо на 2 единицы, потому что добавление величины интенсивности приводит к превышению R = 10. Новая диаграмма приведена на рисунке 2, д.

Переходим к четвертому шагу.

Четвертый шаг

Момент ф ₄ = 10.

Операция (1,3) имеет номер 1, как начатая левее момента ф₃ = 8. Операции (4,5) приписываем номер 2, операции (2,5) - номер 3, так как Rⁿ₄₅ = Rⁿ₂₅ = 3, а r₄₅ = 5 > r₂₅ = 3.

Операции (1,3) и (4,5) не сдвигаются, так как r₁₃ = 5 < 10 и r₁₃ + r₄₅ = 10 = R, а операция (2,5) сдвигается вправо на 2 единицы. Новая диаграмма изображена на рисунке 2, е.



Рисунок 3.2 - Линейная диаграмма (график Ганта)



Пятый шаг

Новый промежуток (ф ₄, ф₅), ф₅ = 11.

Номера операций: (4,5) - номер 1, как начатая левее, (3,5) - номер

так как Rⁿ₃₅ = 0; (2,5) - номер 3, так как Rⁿ₂₅ = 1.

Все операции, лежащие над промежутком (ф ₄, ф₅), остаются на месте, потому что r₄₅ + r₃₅ + r₂₅ = 5 + 2 + 3 = 10 = R.

Так как конец рассмотренного промежутка ф₅ = 11 меньше ф₅ = 14, то переходим к следующему шагу.

Шестой и седьмой шаг

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

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

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

Рассмотрим более общий случай, когда

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

(14)

где . Учитывая, что величины известны, раскроем скобки в правой части (14) и обозначим через сумму

(15)

В результате получим (формула 16)

(16)

Здесь время выполнения операции равно разности между временем ее окончания и временем начала .

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



(17)

На неизвестные величины задачи налагаются следующие ограничения:

- продолжительность выполнения каждой операции должна быть не меньше и не больше (формула 18)

(18)

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

(19)

- выполнение комплекса операций должно быть завершено не позже директивного срока (формула 20):

(20)

где n - номер завершающего события

- переменные должны быть неотрицательными

; для всех , при этом , .

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

Исходные данные комплекса операций, представленного сетевым графиком (Рис. 3.3), приведены в таблице 2.

Требуется оптимизировать сетевой график по стоимости при

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

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

Таблица 2 Исходные данные для примера

Параметры	Операции
	(1,2)	(1,3)	(2,3)	(2,5)	(3,4)	(3,5)	(4,5)
	9	10	0	3	4	5	8
	11	15	0	5	7	8	10
	2	5		5	4	10	3
	20	40		30	45	50	25

Запишем , для всех , принадлежащих сетевому графику

;

;

;

;

;

;

При записи функции принято, что

Так как при параметрах меньше , то оптимизация возможна за счет всех операций сетевого графика.

Запишем ограничения по времени выполнения операций

Ограничения по предшествованию в выполнении операций:

Все неизвестные должны быть неотрицательными, т.е.

для всех операций сети.

В результате решения получим ответ



Таким образом, при заданном сроке выполнения проекта минимальная стоимость его реализации составляет 170 д.е.

ЗАКЛЮЧЕНИЕ

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

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

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

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

Методики сетевого планирования были разработаны в конце 50-х годов в США. В СССР начало работ по сетевому планированию относят к 1961 году. Тогда методы сетевого планирования нашли применение в строительстве и научных разработках.

Существуют различные методы сетевого планирования.

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

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

В настоящее время происходит расширение методов и приемов использования сетевых методов.

Итак, сетевая модель позволяет:

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

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

- проводить многовариантный анализ разных решений с целью улучшения плана;

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

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

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Исследование операций в экономике: Учеб.пособие для вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под редакцией проф. Н.Ш. Кремера - М.: ЮНИТИ, 2002 - 407с

Учебное пособие по решению задач по курсу «Экономико-математические методы и модели»/ Алесинская Т.В. Таганрог: Изд-во ТРТУ, 2002, 153 с.

Экономико-математические методы и модели в управлении производством. А.С. Пелих, Л.Л. Терехов, Л.А. Терехова /под общ. Ред. Пелих А.С. Издательство: «Феникс», 2005, - 248 с.

Экономико-математические методы и модели: Учеб. пособие / С.Ф. Миксюк, В.Н. Комков, И.В. Белько и др.; под общ. ред. С.Ф. Миксюк, В.Н. Комкова. - Мн.: БГЭУ, 2006. - 219 с.

Экономико-математические методы и модели: электронный учеб.-метод. комплекс для студентов юридического факультета / С.А. Марзан [и др.] ; под ред. Н.Н. Сендера. - Брест : БрГУ им. А.С.Пушкина, 2011. -605с.

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

...