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

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ОСНОВНЫЕ ПОНЯТИЯ СЕТЕВОГО ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ

1.1 Назначение систем сетевого планирования и управления

1.2 Возникновение методов сетевого планирования и управления

1.3 Основные понятия сетевых моделей

1.4 Элементы и параметры сетевого графика

1.5 Критический путь проекта

1.6 Оптимизация сетевых графиков. Типы оптимизационных задач

ГЛАВА 2. АЛГОРИТМ НАХОЖДЕНИЯ КРИТИЧЕСКОГО ПУТИ СЕТЕВОГО ГРАФИКА С ПОМОЩЬЮ ПРОГРАММЫ MICROSOFT EXCEL. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ 14

2.1 Математическая постановка задачи нахождения критического пути сетевого графика

2.2 Нахождения критического пути в сетевом графе с помощью программы Microsoft Excel

2.3 Нахождение временных характеристик сетевого графа

2.4 Оптимизация проекта по времени с использованием дополнительных средств

2.5 Оптимизация проекта по стоимости

ГЛАВА 3. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

3.1 Определение критического пути сетевого графика

3.2 Оптимизация проекта по времени

3.3 Оптимизация проекта по стоимости

ЗАКЛЮЧЕНИЕ

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



ВВЕДЕНИЕ

microsoft excel управление сетевой

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

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

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

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

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

Предметом исследования курсовой работы является сетевое планирование и управление.

Объектом данной работы является сетевая модель.

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

Основными задачами данной курсовой работы являются:

1. теоретическое изучение сетевого планирования и управления, определение его сущности, изучение основных элементов сетевой модели;

2. изучение преимуществ сетевого планирования и управления;

3. изучение правил построения модели;

4. расчеты всех параметров сетевой модели;

5. оптимизация сетевой модели.



ГЛАВА 1

ОСНОВНЫЕ ПОНЯТИЯ СЕТЕВОГО ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ

1.1 Назначение систем сетевого планирования и управления

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

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

Преимущества СПУ весьма велики, поскольку система позволяет:

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

- определить и мобилизовать резервы времени, материальных, финансовых, информационных, трудовых ресурсов;

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

- производить оперативную реализацию бизнес-проекта;

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

Характерные примеры использования методов СПУ:

- строительство и реконструкция объектов;

- выполнение НИОКР;

- подготовка производства к выпуску продукции;

- развертывание системы медицинских или профилактических мероприятий;

- перевооружение армии и т.п.

СПУ состоит из трех основных этапов:

1. Структурное планирование.

2. Календарное планирование.

З. Оперативное управление.

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

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

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

1.2 Возникновение методов сетевого планирования и управления

В 1956 г М. Уолкер из строительной фирмы "Дюпонд де Немур" и Д. Келли из фирмы "Ремингтон Рэнд" организовали исследовательскую группу для выработки рекомендаций по управлению инженерной деятельностью. Разработанный метод, основанный на использовании детерминированной сетевой модели (т.е. без применения вероятностных оценок времени проведения работ), получил название сначала "метода Уолкера-Келли", а потом - "метода критического пути" CPM (Critical Path Method).

Используя метод CPM, отдел специальных проектов управления США в 1958 г разработал "метод оценки и обзора программ" PERT (Project Evaluation and Review) с использованием вероятностных оценок времени (т.е. основанный на стохастической сетевой модели).

Самой популярной частью PERT является метод критического пути, опирающийся на построение сетевого графика.

На основе PERT были разработаны другие методы сетевого планирования и управления. Вот некоторые из них:

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

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

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

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

В настоящее время оба метод PERT и метод СРМ составляют единый метод сетевого планирования и управления программами.



1.3 Основные понятия сетевых моделей

Основными понятиями сетевых моделей являются: работа, событие, продолжительность работы, путь.

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

- работу-действие;

- работу-ожидание;

- зависимость (фиктивную работу).

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

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

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

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

Продолжительность работы (t_ij) - это время, необходимое для выполнения работы (i, j). Существуют сети, в которых продолжительности работ не заданы. Такие сети называются структурными.

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

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

Длина пути - продолжительность выполнения всей последовательности работ, составляющих этот путь.

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

1.4 Элементы и параметры сетевого графика

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

Отрезки называются дугами, если указана начальная вершина (рисунок 1.1), и ребрами, если ориентация не указана (рисунок 1.2).

Рисунок 1.1 - Ориентированный граф

Рисунок 1.2 - Неориентированный граф

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

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

При построении сетевых графиков используются следующие правила:

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

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

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

- в сети не должно быть контуров, т. е. цепей, соединяющих некоторые события с ними же самими. Если они есть, необходимо пересмотреть состав работ и добиться устранения контура (например, разделить одну работу на несколько). Чтобы исключить возможность появления контура, события нумеруются таким образом, что для любой работы (i, j) всегда i?j;

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

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

При анализе сетевых графиков, прежде всего, вычисляют их основные временные параметры:

- продолжительность критического пути (критический срок);

- сроки свершения и резервы событий;

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

1.5 Критический путь проекта

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

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

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

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

При нахождении критического пути бизнес-проекта операции представляются в виде дуг ориентированного графа.

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

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

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

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

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

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

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

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

Алгоритм нахождения критического пути сетевого графика с помощью программы Microsoft Excel,а также математическая постановка задачи рассмотрены в главе 2.

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

1.6 Оптимизация сетевых графиков. Типы оптимизационных задач

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

Оптимизация может осуществляться за счет:

- совершенствования выполнения работ критического пути;

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

- детализации работ (когда сложные работы можно разбить на несколько более простых) и др.

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

- частная - предполагает улучшение сетевого графика только по одному критерию;

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

Существует несколько наиболее типичных классов задач частной оптимизации:

- оптимизация по времени:

1. минимизация времени выполнения проекта без учета дополнительных ресурсов;

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

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

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

- оптимизация по ресурсам:

1. перераспределение ресурсов с целью ускорения выполнения проекта; выравнивание потребности в ресурсах;

2. минимизация сроков выполнения проекта с учетом ограничений на трудовые ресурсы;

- оптимизация по стоимости (частный случай оптимизации по ресурсам):

1. сокращение критического срока выполнения проекта до некоторого минимально возможного значения при наименьшем возрастании стоимости выполнения проекта;

2. минимизация общей стоимости ресурсов и штрафов за задержку выполнения проекта;

3. минимизация стоимости проекта при фиксированной его продолжительности;

- оптимизация по потоку:

1. минимизация времени простоя рабочих и оборудования;

2. минимизация определенного потока работ.



ГЛАВА 2

АЛГОРИТМ НАХОЖДЕНИЯ КРИТИЧЕСКОГО ПУТИ СЕТЕВОГО ГРАФИКА С ПОМОЩЬЮ ПРОГРАММЫ MICROSOFT EXCEL. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

2.1 Математическая постановка задачи нахождения критического пути сетевого графика

Рассмотрим ориентированный граф

G=(V,E,h),

где V={v₁,v₂,...,v_n} - конечное множество вершин;

Е={e₁, e₂,...,e_m} - конечное множество дуг

h:E > Z - весовая функция дуг.

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

c_ij=h(еk), (2.1.1)

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

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

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

(2.1.2)

2.2 Нахождения критического пути в сетевом графе с помощью программы Microsoft Excel

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

Требуется найти критический путь, соединяющий начальное событие v₁ с конечным событием v_s, так чтобы общая длина пути была максимальной.

Переменными математической модели задачи о критическом пути в сетевом графе являются переменные x_ij. Каждая из этих переменных принимает значение 1, если дуга (i, j) входит в критический путь, и 0 - в противном случае.

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

Рисунок 2.1 - Ввод данных

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

После появления диалогового окна Поиск решения следует задать:

- ячейку, содержащую целевую функцию;

- вариант оптимизации функции до максимума;

- переменные, которые будем изменять (массив переменных, находящихся в столбце С);

- ограничения задачи.

Общий вид диалогового окна спецификации параметров мастера поиска решения имеет следующий вид

Рисунок 2.2 - Параметры поиска решения

После выполнения расчетов программой Microsoft Excel будет получено количественное решение задачи.

Результатом решения поставленной задачи являются найденные оптимальные значения переменных x_ij=1 (остальные переменные равны 0). Найденному оптимальному решению соответствует значение целевой функции. Критический путь в сетевом графе содержит дуги (i, j), соответствующие критическим операциям моделируемого процесса.

2.3 Нахождение временных характеристик сетевого графа

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

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

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

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

- наиболее вероятная оценка t_нв.

Тогда планируемая продолжительность работы определяется по формуле:

(2.3.1)

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

Ранний срок (t_i^p) - самый ранний момент, к которому завершаются все работы, предшествующие этому событию:

(2.3.2)

(2.3.3)

Для завершающего события S:

. (2.3.4)

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

(2.3.5)

Для завершающего события S:

. (2.3.6)

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

(2.3.7)

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

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

Наиболее ранний возможный срок начала операции (i, j) (t_ij^рн) - определяется при допущении

(2.3.8)

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

(2.3.9)

Раннее начало работ, выходящих из исходного события 1, равно 0:

(2.3.10)

Раннее начало данной работы является ранним окончанием предшествующей работы:

(2.3.11)

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

(2.3.12)

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

(2.3.13)

Рисунок 2.3 - Время выполнения события

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

- полный резерв времени (R_ij^п) - это максимальный запас времени, на которое можно задержать начало работы или увеличить ее продолжительность, не нарушая критический срок:

(2.3.14)

- свободный (частный) резерв времени (R_ij^c) - показатель максимальной задержки работы (i, j), не влияющей на начало последующих работ:

(2.3.15)

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

Свободный резерв времени для определенной работы не может превышать полный резерв.

Критические работы, как и критические события, резервов времени не имеют.

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



2.4 Оптимизация проекта по времени с использованием дополнительных средств

Задачи оптимизации комплекса операций по времени решаются с привлечением дополнительных средств.

Задан сетевой график G(E,e?) выполнения комплекса операций, где E - множество событий графика, e? - множество операций. Время выполнения каждой операции (i, j) равно t_ij. Известно, что вложения x_ij дополнительных средств в операции (i, j) сокращает время выполнения с t_ij до

(2.4.1)

Но насыщение критических операций ресурсами не беспредельно. Для каждой операции существует минимально возможное время ее выполнения (d_ij).

Условие задачи: определить время начала t_ij^н и окончания t_ij^o выполнения операций, размер дополнительно вложенных средств x_ij в каждую из операций (i, j), при условиях:

- общее время выполнения комплекса операций минимально:

min (2.4.2)

- что сумма вложенных дополнительных средств не превышало заданной величины B:

(2.4.3)

- время выполнения каждой операции не меньше минимально возможного времени :

(2.4.4)

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

(2.4.5)

- (2.4.6)

- (2.4.7)

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

Критический путь в данной задаче является функцией от объемов дополнительно вкладываемых средств x_ij.

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

2.5 Оптимизация проекта по стоимости

Будем считать, что для имеющегося сетевого графика известны продолжительности выполнения работ d_ij и их стоимость в срочном режиме C_ij^max. Для срочного режима определены критическое время t_кр и стоимость выполнения проекта С₀. Стоимость при этом является максимальной.

Предполагается, что коэффициенты дополнительных затрат k_ij для каждой работы известны. Ставится задача минимизации стоимости проекта при фиксированном сроке его выполнения за счет увеличения времени выполнения отдельных работ. Критическое время может быть меньше заданного срока t₀ или равно ему. Если t₀=t_кр, то оптимизация возможна только за счет резервов некритических работ, при t₀>t_кр - за счет всех работ проекта.

Будем считать неизвестными задачи сроки свершения событий t_i. Продолжительность работы (i, j) равна

(2.5.1)

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

, (2.5.2)

где k_ij - коэффициент дополнительных затрат для работы (i, j).

Математическая формулировка задачи:

(2.5.3)

(2.5.4)

(2.5.5)

(2.5.6)

Очевидно, что данная задача принадлежит к классу задач линейной оптимизации.

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

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

После появления диалогового окна Поиск решения следует задать:

- ячейку, содержащую целевую функцию;

- вариант оптимизации функции до минимума;

- переменные, которые будем изменять (массив переменных t_i:t_j);

- ограничения задачи.

После выполнения расчетов программой Microsoft Excel будет получено количественное решение задачи.

Результатом решения поставленной задачи являются найденные оптимальные сроки свершения событий t_i и оптимальные продолжительности работ t_ij. Найденному оптимальному решению соответствует значение целевой функции.

Пример решения задачи оптимизации проекта по стоимости с помощью Microsoft Excel приводится в главе 3.



ГЛАВА 3

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

3.1 Определение критического пути сетевого графика

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

Таблица 3.1 - Сетевая модель

Работа (i,j)	Продолжительность tij	Работа (i,j)	Продолжительность tij
(1,2)	3	(3,4)	7
(1,3)	6	(3,5)	4
(1,4)	4	(3,6)	4
(2,3)	2	(4,6)	6
(2,5)	5	(5,6)	2

Решение.

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

Рисунок 3.1 - Сетевой график

Требуется решить следующую задачу оптимизации:

(3.1.1)

При ограничениях

(3.1.2)

(3.1.3)

(3.1.4)

(3.1.5)

(3.1.6)

(3.1.7)

(3.1.8)

Критический путь можно найти, используя Поиск решения Microsoft Excel.

Создадим форму ввода данных в Excel.

Введем обозначения для переменных. В ячейки В4:В13 вводим продолжительности каждой работы, а в Е8:Е13 - ограничения. Диапазон С4:С13 отведем под расчетные значения.

Рисунок 3.2 - Форма ввода данных

В результате решения задачи получим продолжительность критического пути равную 19. Критический путь: Х₁₃, Х₃₄, Х₄₆.

Рисунок 3.3 - Результат решения задачи



3.2 Оптимизация проекта по времени

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

Комплекс операций представлен сетевым графиком.

Рисунок 3.4 - Сетевой график

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

(3.2.1)

; ; ; ; (3.2.3)

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

Решение.

Целевая функция имеет вид:

(3.2.4)

Ограничения:

- сумма вложенных дополнительных средств не должна превышать их наличного количества:

; (3.2.5)

- время выполнения каждой операции должно быть не меньше минимально возможного времени:

(3.2.6)

(3.2.7)

(3.2.8)

(3.2.9)

(3.2.10)

(3.2.11)

(3.2.12)

- время начала выполнения каждой операции было не меньше времени окончания предшествующей ей операции:

(3.2.13)

(3.2.14)

(3.2.15)

(3.2.16)

(3.2.17)

(3.2.18)

(3.2.19)

- зависимость продолжительности операций от вложенных средств:

(3.2.20)

(3.2.21)

(3.2.22)

(3.2.23)

(3.2.24)

(3.2.25)

- условие неотрицательности неизвестных:

(3.2.26)

(3.2.27)

(3.2.28)

Данная математическая модель может быть решена при помощи функции «Поиск решения» Microsoft Excel.

Создадим на рабочем листе форму для ввода данных. Введем обозначения для переменных и отведем под расчетные значения X1-X17 диапазон ячеек А8:Q8. Времена начала и окончания операций (ячейки А6:К6) обозначим с помощью переменных Х1-Х11, а средства, вкладываемые в каждую из операций (Х₁₂, Х₁₃, Х₁₄, Х₂₃, Х₂₄), обозначим как Х12-Х16.

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

Таблица 3.2 - Формулы для расчета

Ячейка	Формула	Ячейка	Формула
K13	=A8+2,8*L8	A9	=A8
K14	=B8+2*M8	B9	=B8
K15	=C8+3*N8	C9	=C8
K16	=D8-E8+2,4*O8	E9	=D8-E8
K17	=F8-G8+0,2*P8	G9	=F8-G8
Продолжение таблицы 3.2
K18	=J8-K8+1,5*Q8	I9	=H8-I8
C13	=E8-A8	K9	=J8-K8
C14	=G8-A8
C15	=I8-D8
C16	=K8-C8
C17	=K8-H8
C18	=K8-F8

Рисунок 3.5 - Форма ввода данных

В результате решения задачи получаем следующий результат:

; ;

; ; .



3.3 Оптимизация проекта по стоимости

Комплекса операций проекта представлен сетевым графиком (рисунок 3.6), а его параметры заданы в таблице . Требуется оптимизировать проект по стоимости при директивном сроке t_o=17.

Рисунок 3.6 - Сетевой график

Таблица 3.3 - Параметры работ проекта

Парамеры	Работа
	(1,2)	(1,3)	(2,3)	(2,4)	(3,5)	(4,5)
dij	2	4	6	4	6	3
Cijmax	50	30	85	64	37	90
kij	5	3	12	7	4	6

Решение.

В соответствии с разделом 3.1 найдем критический путь проекта, продолжительность критического пути t_кр и его стоимость С.

Рисунок 3.7 - Определение критического пути проекта

Очевидно, что t_кр=14, критический путь: Х₁₂, Х₂₃, Х₃₅, а стоимость проекта для срочного режима С=C₁₂+C₁₃+C₂₃+C₂₄+C₃₅+C₄₅=50+30+85+64+37+90= =356.

Сформулируем модель проекта:

- целевая функция:

(3.3.1)

- ограничения:

(3.3.2)

(3.3.3)

(3.3.4)

(3.3.5)

(3.3.6)

(3.3.7)

(3.3.8)

(3.3.9)

(3.3.10)

Упростим выражения для ЦФ и введем данные на лист Microsoft Excel.

Рисунок 3.8 - Ввод данных

В результате решения задачи Поиском решений Microsoft Excel получим следующие результаты:

.

Продолжительности работ проекта после оптимизации равны:

.

Рисунок 3.9 - Результат решения задачи

Таким образом, если в срочном режиме проект может быть реализован за 14 дней и это потребует затрат 356 д.е., то при выполнении его за 17 дней стоимость уменьшится до 247 д.е.



ЗАКЛЮЧЕНИЕ

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

В рамках данной работы решены все поставленные задачи и достигнуты цели:

1. Изучен теоритический материал по теме «Экономико-математические методы сетевого планирования и управления» и основные элементы сетевой модели и правила ее построения;

2. Определены преимущества сетевого планирования и управления;

3. Приобретены навыки построения и расчета временных параметров моделей сетевого планирования и управления, оптимизации сетевой модели;



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

1. Баканов, М.И. Теория экономического анализа: Учебник / М.И. Баканов, М.В. Мельник, А.Д. Шеремет. - М.: Финансы и статистика, 2005. - 536с.

2. Гринберг, А.С. Информационные технологии оптимальных решений. Курс лекций для системы открытого образования / А.С. Гринберг, Б.В. Новыш, В.К. Шешолко. - Мн.: Академия управления при Президенте Республики Беларусь, 2003. 410 с.

3. Интрилигатор, М. Математические методы оптимизации и экономическая теория / М. Интрилигатор. - М.: Айрис Пресс, 2002.

4. Казаков, О.Л. Экономико-математическое моделирование: учебно-методическое пособие / О.Л. Казаков, С.Н. Миненко, Г.Б. Смирнов. - М.: МГИУ, 2006. - 136 с.

5. Конюховский, П.В. Математические методы исследования операций в экономике / П.В. Конюховский. - Санкт-Петербург: Питер 2003. - 208 с.

6. Миненко, С. Н. Экономико-математическое моделирование производственных систем: учебно-методическое пособие / С.Н. Миненко, О.Л. Казаков, В.Н. Подзорова. - М.: ГИНФО, 2002. - 128 с.

7. Мур, Дж.Х. Экономическое моделирование в Microsoft Excel / Дж.Х. Мур, Л.Р. Уэдерфорд, Г. Эллен, Ф. Гулд, Ч. Шмидт. - М.: Вильямс, 2004. 1018с.

8. Новицкий, Н. И. Сетевое планирование и управление производством / Н.И. Новицкий. - М.: Новое знание, 2004. - 159 с.

9. Экономико-математические методы и модели / Под редакцией А.В. Кузнецова. - Минск: БГЭУ, 2000. - 412с.

10. Экономико-математическое моделирование / Л. Абланская, Л. Бабешко, Л. Баусов, В. Бывшев, Н. Гринева, И. Дрогобыцкий, А. Ильинский, Л. Лабскер, И. Михеев, Р. Серегин. - М.: Экзамен, 2006. - 800с.

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

...