Федеральноеагентство по образованию
Государственноеобразовательное учреждение высшего профессионального образования
Московскийгосударственный индустриальный университет
Институтдистанционного образования (ГОУ ИДО МГИУ)
КУРСОВАЯ РАБОТА
по дисциплине«Экономико-математическое моделирование».
На тему «Сетевоепланирование и управление»
Выполнила:
студентка
группы 01Э31П
Фаттахова Г. М.
Проверил:
Смирнов Г. Б.
Москва 2006 г.
Содержание
Введение
1. Построение сетевого графика
2. Анализ сетевого графика
3. Способы оптимизации сетевого графика
Заключение
Списокиспользованных источников
Введение
Решение хозяйственных задач связано с осуществлением рядаработ (действий, мероприятий, операций), одни из которых можно выполнятьодновременно, параллельно, а другие – только в определенной последовательности.Например, чтобы начать производство нового изделия, необходимо прежде всегоразработать его конструкцию, технологию производства, а затем осуществлятьчетыре вида параллельных работ:
проектировать, заказывать, получать и монтироватьнеобходимое оборудование;
планировать размещение оборудования, рассчитыватьтребуемые площади и строить помещения;
заключать договора с другими предприятиями о поставкахнеобходимых материалов, сырья и комплектующих деталей;
набирать и готовить кадры будущих работников.
В современных условиях необходимо разработать ииспользовать сравнительно простые и эффективные методы руководства комплекснымиразработками, выполнением сложных проектов внедрения в экономическую практикуновейших научно-технических достижений. Необходимо вооружить руководителейсовершенным инструментом, позволяющим в любых даже самых сложных ситуациях,быстро принимать наиболее правильные решения.
Поиски эффективных способов планирования сложных процессови проектов привели к созданию методов сетевого планирования и управления (СПУ).Они применимы в тех случаях, когда конечная цель достигается путем выполненияряда взаимоувязанных и взаимозависимых работ, входящих в единый комплекс тойили иной разработки.
Эффект, достигаемый за счет применения СПУ, обусловлен впервую очередь внесением строгих логических элементов в формирование плана,позволивших привлечь для анализа и синтеза планов реализации проектовсовременный математический аппарат и средства вычислительной техники.
В силу универсальности СПУ этот аппарат используется дляформирования планов строительной индустрии во всех видах строительства, виндивидуальном и мелкосерийном производстве, в научно-исследовательских,опытно-конструкторских и проектных организациях, в производстве кинофильмов, вгорнодобывающей промышленности и геологоразведочных работах.
Объектом управления в системах СПУ является коллектив,располагающий определенными ресурсами и выполняющий комплекс работ, призванныйобеспечить достижение намеченной цели. Метод СПУ позволяет в любых, даже самыхсложных ситуациях, быстро принимать наиболее правильные решения, выявитьрезервы времени и средств на одних участках работы и перебросить их на другие,более напряженные.
Важной особенностью систем СПУ является системный подходк вопросам организации управления, согласно которому коллективы исполнителей,принимающих участие в проекте и объединенные общностью поставленной перед нимизадачи, рассматриваются как звенья единой сложной организационной системы.
Для отображения процесса выполнения проекта и управленияим в системах СПУ используется сетевая модель.
1. Построение сетевого графика
Система сетевого планирования и управления (СПУ) –система, применяемая в строительстве, в управлении крупными научно-техническимиразработками и другими комплексами работ, основанная на использовании ЭВМ исетевых графиков.
Системы СПУ можно характеризовать следующими признаками,определяющими структуру, основные принципы построения и функционирования СПУ,объемы информации, методы и технические средства ее сбора, передачи,переработки и отображения:
а) уровень руководства, использующий данную систему СПУ;
б) количество сетей, описывающих проект;
в) число конечных целей проекта;
д) ограничения по ресурсам;
е) планируемые и контролируемые параметры проекта.
На практике структура систем СПУ обусловленанеобходимостью выполнения основных процессов управления, получения информации осостоянии проекта (комплекса работ), преобразования информации, формированиякоманд управления, передачи и исполнения команд управления.
Под комплексом работ (комплексом операций или проектом)понимается всякая практическая задача, для выполнения которой необходимоосуществить достаточно большое количество разнообразных взаимосвязанных работ.Это может быть разработка и создание крупного территориально-промышленногокомплекса или строительство (реконструкция) завода, корабля, самолета, любогодругого сложного объекта. СПУ это сочетание как расчетных методов, так иорганизационных мероприятий и контрольных приемов. Конечным продуктом действиясистемы является выявление и мобилизация резервов времени и материальныхресурсов.
Основано СПУ на графическом изображении комплекса работ,т.е. работы в их логической и временной последовательности представляютсяграфической моделью – сетевым графиком (сетью), который является первым этапомпостроения сетевой модели этого комплекса или проекта работ.
Спектр приложений СПУ в экономике чрезвычайно широк. Этокалендарное планирование, подготовка производства, освоение новой техники,реконструкция предприятий (цехов, участков), строительство и т.д.
Сетевые графики составляются на начальном этапепланирования. Главными элементами сетевой модели являются события и работы.
Под работой понимаются действия, связанные с затратамиресурсов (материальных, финансовых, трудовых) и приводящие к определеннымрезультатам. Работы обозначаются на сетевом графике дугами.
Под событием понимают результат завершения одной илинескольких работ.
Вначале планируемый процесс разбивается на отдельныеработы и события, составляется перечень работ и событий, продумываются ихлогические связи и последовательность выполнения, работы закрепляются заответственными исполнителями. С их помощью оценивается длительность каждой работы.Затем составляется сетевой график. После упорядочения сетевого графикарассчитываются параметры событий и работ, определяются резервы времени икритический путь. Затем проводится анализ и оптимизация сетевого графика.
Отличительной особенностью сетевой модели является четкоеопределение всех временных взаимосвязей предстоящих работ.
С математической точки зрения, сетевой графикпредставляет собой связанный ориентированный граф без петель и контуров.
Наглядно граф можно представить как некоторое множество вершини множество ребер, соединяющие все или некоторые из этих вершин.
Если на ребре указано направление связи между вершинами,то оно называется дугой. Ориентация дуги указывается стрелками. Дуга,соединяющая вершину i с вершиной j, обозначается символом (i, j) или pij.
Если все соединения в графе изображаются дугами, то графназывается ориентированным, или орграфом.
Последовательность дуг, в которой конец каждой предыдущейдуги совпадает с началом следующей, называется путем в орграфе.
Путь, у которого начальная вершина совпадает с конечной,называется контуром. Контур с одной вершиной – петля.
Вершина, из которой дуги только выходят, но не входят,называется истоком.
Вершина, в которую дуги только входят, но не выходят,называется стоком.
Любой путь в сетевом графике от истока к стоку называетсяполным.
Если дугам (ребрам) графа сопоставлены какие-то числовыехарактеристики – весами.
Вершина хi («предок») предшествует в графе вершине хj(«потомок»), если существует путь из хi в хj .
Граф является упорядоченным, если в нем порядковый номер«предка» всегда меньше порядкового номера «потомка».
Графический номер упорядочения графа реализуется поалгоритму Фалкерсона:
1-ый шаг – выделяем вершины, не имеющие «предков», ипоследовательно нумеруем их в произвольном порядке;
2-ый шаг – мысленно вычеркиваем из графа все вершины,имеющие номера и дуги из них выходящие;
3-ый шаг – в получившемся графе повторяем процедуры 1-гои 2-го шагов до тех пор, пока все вершины не будут пронумерованы.
Граф называется связанным, если любые его две вершиныможно соединить путем, в котором не учитывается ориентация дуг.
Сетевой график – это связанный взвешенный орграф безконтуров (петель).
На изображении комплекса работ с помощью сетевого графикаосновано сетевое планирование и управление (СПУ).
События обозначаются на сетевом графике вершинами.
Подготовка исходных данных для построения сетевогографика включает:
— определение начального и конечного событий;
— составления перечня всех событий, следующих заначальным, и без которых не может произойти конечное событие;
— составление списка работ, соединяющих намеченныесобытия;
— определение продолжительности выполнения каждой работы.
При построении сетевого графика для СПУ должныучитываться следующие правила:
график должен иметь только одно начальное событие (исток)и только одно конечное событие (сток);
ни одно событие не может произойти до тех пор, пока небудут закончены все входящие в него работы;
ни одна работа, выходящая из какого либо события, неможет начаться до тех пор, пока не произойдет данное событие;
график должен быть упорядоченным;
в сетевом графике не должно быть «тупиковых» событий, изкоторых не выходит ни одна работа, за исключением завершающего события;
в сетевом графике не должно быть «хвостовых» событий,кроме, исходного (начального), которым не предшествует хотя бы одна работа;
в сети не должно быть замкнутых контуров и петель, т.е.путей, соединяющих некоторые события с ними же самими;
любые два события должны быть непосредственно связаны неболее чем одной работой-дугой.
В случае нарушения условия 1 или 8 рекомендуется ввестификтивное событие и фиктивную работу. Последовательность дуг, в которой конецкаждой предыдущей дуги совпадает с началом следующей, называется путем. Любойпуть от начальной вершины (истока) к конечной вершине (стоку) называетсяполным. Если дугам графа сопоставлены какие-то числовые характеристики, то графназывается взвешенным, а числовые характеристики – весами.
Упорядочение сетевого графика заключается в такомрасположении событий и работ, при котором для любой работы предшествующее ейсобытие расположено левее и имеет меньший номер по сравнению с завершающим этуработу событием. Другими словами, в упорядоченном сетевом графике всеработы-дуги направлены слева направо: от событий с меньшими номерами к событиямс большими номерами.
Критическим называется наиболее продолжительный из полныхпутей. Критический путь определяет минимально необходимое время выполнения всехработ, называемое критическим сроком. Работы и события, лежащие на критическомпути, называются критическими.
Задача. Построить сетевой график выполнения работ:
упорядочить построенный график;
отметить весами работы построенного графика;
определить полные пути для нормального и ускоренногосрока выполнения работ;
определить критический путь, ранние и поздние срокивыполнения работ и резервы времени выполнения работ.
Таблица 1 Cобытия (потомки) Cобытия (предки) Начало работ Готовность деталей Готовность документации Поступление дополнительного оборудования Готовность блоков Готовность деталей Изготовление деталей (4/3) Готовность документации Подготовка документации (5/2) Установка дополнительного оборудования (12/6) Составление инструкций (11/6) Поступление дополнительного оборудования Закупка дополнительного оборудования (10/5) Готовность блоков Сборка блоков (6/4) Готовность изделия Компоновка изделия (9/6)
Решение.
Построение сетевого графика.
2. Анализ сетевого графика
Цель анализа сетевого графика заключается в том, чтобывыявить резервы времени работ, не лежащих на критическом пути, и направить ихна работы, лимитирующие срок завершения комплекса работ. Результатом этогоявляется сокращение продолжительности критического пути.
Можно выделить следующие этапы анализа. Прежде всегоустанавливается, соответствует ли график требованиям к его построению. Еслитребования нарушены, то производится соответствующая корректировка. Здесьпересматривается топология сети и график упорядочивается.
Далее определяется время выполнения каждой работы, ирассчитываются параметры сетевого графика. Анализируются резервы временивыполнения работ и возможность их использования с целью сокращения сроковвыполнения работ, лежащих на критическом пути.
Полные пути и их продолжительности:
1 – 2 — 4 – 5 – 6 → 4/3 + 6/4 + 11/6 + 9/6 = 30/19
1 – 2 – 5 – 6 → 4/3 + 5/2 + 9/6 = 18/11
1 – 3 – 5 – 6 → 10/5 + 12/6 + 9/6 = 31/17
Нахождение критического пути.
Путь 1 – 3 – 5 – 6 – наиболее продолжительный из полныхпутей называется критическим.
31/17 – это минимальное время выполнения работ длядостижения поставленной задачи является критическим сроком и обозначается tкр.Работа и события, лежащие на критическом пути, называют критическими.
Если выполнение какой-либо критической работы будетзадержано, это задержит выполнение всего комплекса работ.
Чтобы ускорить выполнение поставленной задачи, необходимосократить сроки выполнения критических работ.
Некритические работы могут обладать резервами времени, накоторое можно задержать выполнение некритической работ, сократив при этомзатраты на выполнение всего комплекса работ.
Для определения резервов времени событий необходиморассчитать ранние и поздние сроки совершения событий.
Ранний (или ожидаемый) срок tp(j) совершения j-го событияопределяется продолжительностью максимального пути, предшествующего этомусобытию.
tp(j) = max t (Lnj),
где t (Lnj) – любой путь, предшествующий j-му событию,т.е. путь от исходного до j-го события сети. Если событие имеет несколькопредшествующих путей, а следовательно несколько предшествующих событий i, то дляоценки раннего срока совершения j-го события следует выбирать максимальный изпредшествующих путей,
tp(j) = maxi,j [tp (i) + t (i, j)].
Расчет раннего срока наступления событий для примера нарис. 1.
tp1 = 0;
tp2 = tp1 + t (1, 2) = 0 + 4= 4;
tp3 = tp1 + t (1, 3) = 0 + 10 = 10;
tp4 = tp2 + t (2, 4) = 4 + 6 = 10;
tp5 = max [ tp4 + t (4, 5); tp2 + t (2,5); tp3 + t (3; 5)] = max [(10 + 11); (4 + 5); (10 + 12)] = [21; 9; 22] = 22;
tp6 = tp5 + t (5; 6) = 22 + 9 = 31
Задержка свершения события по отношению к своему раннемусроку не отразится на сроке свершения завершающего события (а значит, и насроке выполнения комплекса работ) до тех пор, пока сумма срока свершения этогособытия и продолжительность максимального из последующих за ним путей не превыситдлины критического пути.
Поэтому поздний (или предельный) срок tp(j) свершенияj-го события равен:
tp(j) = tкр –max t(Lnj)
где Lnj – любой путь следующий за j-м событием, т.е. путьот j-го до завершающего события сети.
Если событие j имеет несколько последующих путей i, топоздний срок свершения j-го события находится как минимальный из последующихпутей.
tp(j) = min j,i [ tn(i) – t(j, i)].
Расчет поздних сроков свершения событий.
tn6 = tкр = 31;
tn5 = tn6 – t (5, 6) = 31 – 9 = 22;
tn4 = tn5 – t (4, 5) = 22 – 11 = 11;
tn3 = tn5 – t (3, 5) = 22 – 12 = 10;
tn2 = min [tn4 – t (2, 4); tn5 – t (2,5)] = [(11 – 6); (22 – 5)] = [5, 17] = 5;
tn1 = min [tn2 – t (1, 2); tn3 – t (1,3)] = [(5 – 4); (10 – 10)] = [1, 0] = 0;
Определение резерва времени события.
Резерв времени события определяется как разность междупоздним и ранним сроками его свершения.
R(j) = tn(j) – tp(j).
Резерв времени события показывает, на какой допустимыйпериод времени можно задержать наступление этого события, не вызывая при этомувеличения срока выполнения комплекса работ. Для работ отмечается полный резерввремени работы – максимальное количество времени, на которое можно задержатьначало работ или увеличить ее продолжительность, не изменяя длительностькритического срока:
Rпол(i, j) = tn(j) – tp(i) — t(i, j). Для этого примера
Rп (2, 5) = tп (5) — tр (2) — t(2, 5) = 22 – 4 – 5 = 13;
Rп (4, 5) = tп (5) — tр (4) — t(4,5) = 22 – 10 – 11 = 1;
3. Оптимизация сетевого графика экономического процесса
Оптимизация сетевого графика представляет процессулучшения организации выполнения комплекса работ с учетом срока его выполнения.
Оптимизация проводится с целью сокращения длительностикритического пути, выравнивания коэффициентов напряженности работ,рационального использования ресурсов. В первую очередь принимаются меры посокращению продолжительности работ, находящихся на критическом пути. Этодостигается
— перераспределением всех видов ресурсов, как временных(использование времени некритических путей), так и трудовых, материальных,энергетических (например, перевод части исполнителей, оборудования снекритических путей на работы критического пути);
— сокращением трудоемкости критических работ за счетпередачи части работ на другие пути, имеющие резервы времени;
— параллельным выполнением работ критического
При выполнении заказа используются следующие данные овыполнении работ и связанных с ними затрат:
Таблица 2Работы Нормальный вариант Ускоренный вариант Прирост затрат на одни сутки ускорения Время (сутки) Затраты (у.е.) Время (сутки) Затраты (у.е.) Изготовление деталей (4/3) 4 100 3 120 20 Закупка дополнительного оборудования (10/5) 10 150 5 225 15 Сборка блоков (6/4) 6 50 4 100 25 Подготовка документации (5/2) 5 70 2 100 10 Установка дополнительного оборудования (12/6) 12 250 6 430 30 Составление инструкций (11/6) 11 260 6 435 35 Компоновка изделия (9/6) 9 180 6 300 40 Всего 1060 1710
Требуется минимизировать затраты на выполнение всегокомплекса работ за 21 сутки.
Оптимизацию можно провести двумя способами:
Первый способ заключается в уменьшении продолжительностивыполнения работ, осуществляемых в нормальном режиме, начиная с тех, которыедают наименьший прирост затрат.
Алгоритм решения поставленной оптимизационной задачипредставлен первым способом в таблице:
Таблица 3№ шага
СуточныйПриростзатрат Работа Количество сокращаемых суток Продолжительность полного пути Общий прирост затрат 1256 12456 1356 - - - 18 30 31 - 1 10 2-5 - - - - - 2 15 1-3 5 - - 26 +75 3 20 1-2 1 - 29 - +20 4 25 2-4 2 - 27 - +50 5 30 3-5 4 - - 22 +120 6 35 4-5 5 - 22 - +175 7 40 5-6 1 - 21 21 +40 Итого +480
Итак, при снижении продолжительности выполнения всегокомплекса работ с 31 суток до 21 сутки оптимальные затраты составляют 1060 +480 = 1540.
Второй способ заключается в увеличении продолжительностивыполнения работ, осуществляемых в ускоренном режиме, начиная с тех, которыедают наибольший прирост затрат.
Таблица 4№ шага
Суточный
Прирост затрат Работа Количество наращиваемых суток
Продолжительность полного
пути
Общее снижение
затрат 12456 1356 1256 - - - 19 17 11 - 1 40 5-6 2 21 19 13 -80 2 10 2-5 3 - - 16 -30 3 30 3-5 2 - 21 - -60 Итого -170
Итак, при повышении продолжительности выполнения всегокомплекса ускоренного режима работ до 21 суток оптимальные затраты составляют1710 – 170 = 1540.
Заключение
В данной курсовой работе была решена задача по построениюсетевого графика; был проведен расчет ранних и поздних сроков завершения работи резервов времени по работам и событиям.
Была проведена оптимизация графика с целью минимизациизатрат для выполнения всего комплекса работ до 21 сутки.
Первый способ заключался в уменьшении продолжительностивыполнения работ, осуществляемых в нормальном режиме, начиная с тех, которыедают наименьший прирост затрат.
Итак, при снижении продолжительности выполнения всегокомплекса работ с 31 суток до 21 сутки оптимальные затраты составили 1060 + 480= 1540 рублей.
Второй способ заключался в увеличении продолжительностивыполнения работ, осуществляемых в ускоренном режиме, начиная с тех, которыедавали наибольший прирост затрат.
Итак, при повышении продолжительности выполнения всегокомплекса ускоренного режима работ до 21 суток оптимальные затраты составили 1710– 170 = 1540 рублей.
Список использованных источников
1. МиненкоС. Н., Казаков О. Л. Экономико-математическое моделирование производственныхсистем: Учебное пособие.- М.: ГИНФО, 2002 г.- 136 с.
2.Миненко С. Н., Казаков О. Л., Подзорова В. Н. Экономико-математическоемоделирование производственных систем: Учебно-методическое пособие.- М.: ГИНФО, 2002 г.- 128 с.