Реферат: Оптимизация сетевой модели комплекса производственных работ

Государственноеобразовательное учреждение

высшегопрофессионального образования

Московскийгосударственный индустриальный университет

(ГОУМГИУ)

КафедраИДО № 72 «Экономики»

Курсоваяработа

По дисциплине «Экономико-математическое моделирование системуправления»

на тему «Оптимизация сетевой модели комплексапроизводственных работ»

Выполнил:студент группы №Ах07Э22п

Ф. И.О.студента: Бирюкова Е.К.

Проверил: Смирнов Г.Б

Ф. И. О.преподавателя

Казаков О.Л.

Москва2010

СОДЕРЖАНИЕ

Введение

1. Построение сетевого графика

2. Анализ сетевого графика

3. Оптимизация сетевого графика

Заключение

Списокиспользованной литературы

Задание курсовой работы (660)

«Оптимизациясетевой модели комплекса производственных работ»

студент учебнойгруппы

Весеннийсеместр 2009/10 учебного года

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

Содержание(оглавление) проекта:

ЗАДАНИЕкурсовой работы

ВВЕДЕНИЕ – потребностьв сетевом планировании и управлении (СПУ), возможности СПУ, цель и задачи работы

1. ПОСТРОЕНИЕСЕТЕВОГО ГРАФИКА – определение понятия «сетевой график» и технологии егопостроения, описание построения заданного сетевого графика, анализ адекватностипостроенного сетевого графика заданным в проекте исходным условиям (данным).

2. АНАЛИЗСЕТЕВОГО ГРАФИКА – определение понятий «полный путь» и «критический путь»,описание нахождения полных путей построенного сетевого графика и среди них –критического, анализ возможности доведения критического срока до заданнойпродолжительности выполнения рассматриваемого комплекса производственных работ.

3. ОПТИМИЗАЦИЯСЕТЕВОГО ГРАФИКА – определение понятий «оптимизация сетевого графика»,«критерий оптимизации», «показатель оптимизации и условия оптимизации»,постановка задачи оптимизации сетевого графика, выбор способов оптимизации,описание процедур оптимизации выбранными способами, сравнение результатовоптимизации разными способами, вывод об оптимальном результате для построенногосетевого графика.

ЗАКЛЮЧЕНИЕ – краткое описание перечнярезультатов, полученных в проекте; обоснование их достоверности и практическойценности, возможные перспективы совершенствования организации выполнениязаданного комплекса производственных работ.

Требования к отчету:

Титульный лист отчета (курсового проекта)должен соответствовать образцу на сайте МГИУ.

В отчет должны входить:

- Содержание(оглавление) с указанием страниц разделов отчета.

- Выданноезадание курсовой работы с подписью руководителя проекта.(Обязательно!!! – необходимо для проверки)

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

- Списокиспользованной литературы.

Рекомендуемая литература:

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

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

Исходные данные:

Вариант № 660

События (предки) начало работ готовность деталей готовность документации поступление дополнительного оборудования готовность блоков События (потомки) готовность деталей изготовление деталей (4/3) готовность документации подготовка документации (5/2) поступление дополнительного оборудования закупка дополнительного оборудования (10/5) готовность блоков сборка блоков (6/4) составление инструкций (11/6) готовность изделия установка дополнительного оборудования (12/6) компоновка изделия (9/6) Работы Нормальный вариант Ускоренный вариант Прирост затрат на одни сутки ускорения Время (сутки) Затраты (у.е.) Время (сутки) Затраты (у.е.) изготовление деталей 4 100 3 120 20 закупка дополнительного оборудования 10 150 5 225 15 сборка блоков 6 50 4 100 25 подготовка документации 5 70 2 100 10 установка дополнительного оборудования 12 250 6 430 30 составление инструкций 11 260 6 435 35 компоновка изделия 9 180 6 300 40 ВСЕГО 1060 ВСЕГО 1710

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

ВВЕДЕНИЕ

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

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

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

Основнаяцель сетевого планирования — сокращение до минимума продолжительности проекта.

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

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

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

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

 

1. ПОСТРОЕНИЕСЕТЕВОГО ГРАФИКА

 

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

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

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

— во-вторых,это конечный граф, то есть множество его ребер конечно;

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

Событиясетевого графика – это вершины графа (обычно изображаются кружками), работы –дуги графа (обычно обозначаются стрелками).

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

1. Определениеначального и конечного событий;

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

3. Составлениесписка работ, соединяющих намеченные события;

4. Определениепродолжительности выполнения каждой работы.

Припостроении сетевого графика для СПУ должны учитываться следующие правила:

1. Графикдолжен иметь только одно начальное событие и только одно конечное событие;

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

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

4. Графикдолжен быть упорядоченным.

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

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

Начальнымсобытием – истоком I является «начало работ», а завершающим событием – стоком S – «готовность изделия».Поэтому нужно пронумеровать их соответственно числами 1 и 6.

События (предки) начало работ (1) готовность деталей готовность документации поступление дополнительного оборудования готовность блоков События (потомки) готовность деталей изготовление деталей (4/3) готовность документации подготовка документации (5/2) поступление дополнительного оборудования закупка дополнительного оборудования (10/5) готовность блоков сборка блоков (6/4) составление инструкций (11/6) готовность изделия (6) установка дополнительного оборудования (12/6) компоновка изделия (9/6)

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

События (предки) начало работ (1) готовность деталей (2) готовность документации поступление дополнительного оборудования (3) готовность блоков События (потомки) готовность деталей(2) изготовление деталей (4/3) готовность документации подготовка документации (5/2) поступление дополнительного оборудования (3) закупка дополнительного оборудования (10/5) готовность блоков сборка блоков (6/4) составление инструкций (11/6) готовность изделия (6) установка дополнительного оборудования (12/6) компоновка изделия (9/6)

Из этого события 2 (по горизонтали) выходят две работы-дуги, которыеведут к соответствующим событиям по вертикали. Их обозначим по порядку 4 и 5.Соответствующим событиям по горизонтали присвоим те же числа.

События (предки)

начало работ

(1)

готовность деталей(2)

готовность документации

(4)

поступление дополнительного оборудования

(3)

готовность блоков

(5)

События (потомки) готовность деталей(2) изготовление деталей (4/3) готовность документации(4) подготовка документации (5/2) поступление дополнительного оборудования(3) закупка дополнительного оборудования (10/5) готовность блоков(5) сборка блоков (6/4) составление инструкций (11/6) готовность изделия (6) установка дополнительного оборудования (12/6) компоновка изделия (9/6)

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

/> I

/>/> 4\3 10\5

/>

/>/> I

/>/> 12\6

/> 5\2

6\4 S

/> /> /> /> /> /> /> /> /> /> /> /> /> <td/> /> />

S 9\6

/> 11\6

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

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

Работы

Нормальный

вариант

Ускоренный

вариант

Прирост

затрат на одни сутки ускорения

Время

(сутки)

Затраты

(у.е.)

Время

(сутки)

Затраты

(у.е.)

1 — 2 4 100 3 120 20 1 — 3 10 150 5 225 15 2 — 5 6 50 4 100 25 2 — 4 5 70 2 100 10 3 — 6 12 250 6 430 30 4 — 5 11 260 6 435 35 5 — 6 9 180 6 300 40 ВСЕГО 1060 ВСЕГО 1710

 

/> /> /> /> /> /> /> /> />

2. АНАЛИЗСЕТЕВОГО ГРАФИКА

 

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

Проведеманализ сетевого графика:

Полные пути Продолжительность (сутки) Нормальный режим Ускоренный режим 1 – 2 – 5 – 6 19 13 1 – 3 –6 22 11 1 – 2 — 4- 5- 6 29 17

Полнымипутями при нормальном режиме будут:

путь 1-2-5-6(продолжительностью 4 + 6 +9=19 суток)

путь 1-3-6(продолжительностью 10 +12 = 22 суток)

путь 1-2-4-5-6(продолжительностью 4 + 5+11 +9=29 суток)

Полнымипутями при ускоренном режиме будут:

путь 1-2-5-6(продолжительностью 3 + 4 +6=13 суток)

путь 1-3-6(продолжительностью 5 + 6=11 суток)

путь 1-2-4-5-6(продолжительностью 3 + 2+6 +6=17 суток)

Критическимпутем будет путь 1-2-4-5-6, продолжительность которого при нормальном режимесоставит 29 суток, а при ускоренном режиме – 17 суток.

Максимальныйсрок завершения всей совокупности работ составит 29 суток, а минимальный – 17суток. Требуется довести продолжительность работ при нормальном режиме с 29 до19 суток, а при ускоренном режиме с 17 суток до 19 суток.

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

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

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

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

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

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

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

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

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

Оптимизациюможно провести двумя способами:

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

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

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

Требуетсяоптимизировать по критерию минимизации затрат сетевой график при заданнопродолжительности всего комплекса работ за 19 суток.

Представимрешение поставленной задачи первым способом в таблице:

№

шага

Суточный прирост затрат Работа Количество сокращаемых суток

Продолжительность

полного пути

Общий

прирост

затрат

1-2-5-6 1-3-6 1-2-4-5-6 - - - 19 22 29 - 1 10 2-4 3 ( 3) - - 26 30 2 15 1-3 5 ( 3) - 19 - 45 3 20 1-2 1 (1) 18 - 25 20 4 25 2-5

2 -

- - - - 5 30 3-6 6 - - -

-

- 6 35 4-5  5 (5) - - 20 175 7 40 5-6  1 (3) 17 - 19 40 В С Е Г О 310

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

На первомшаге рассматривается работа 2-4, которая входит в третий полный путь и еепродолжительность может быть сокращена на все 3 суток, т.к. продолжительность третьегополного пути, а следовательно и всего комплекса работ, все равно будет вышетребуемой. Такое снижение продолжительности рассматриваемой работы на 3 сутокприведет к увеличению затрат на выполнение этой работы, а следовательно и всегокомплекса работ в размере: 3*10=30 у.е.

На второмшаге рассматриваемая работа 1-3, которая входит во второй полный путь и еепродолжительность может быть сокращена на 3 суток, (из 5 возможных), т.к. приэтом продолжительность второго пути, в который она входит становится равнойзаданной: 22-3=19.Аналогично рассчитываем затраты на такое сокращение:3*15=45

На третьемшаге рассматриваемая работа 1-2 входит в первый и третий полный путь. Онаможет быть сокращена на максимально возможную величину (указанную в скобках) на1, т.к при этом продолжительность третьего полного пути все равно будет вышетребуемого. Аналогично рассчитываем затраты на такое сокращение: 1*20=20

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

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

На шестомшаге рассматриваемая работа 4-5 входит в третий полный путь. Она может бытьсокращена на максимально возможную величину (указанную в скобках) на 5, т.к приэтом продолжительность третьего полного пути все равно будет выше требуемого.Аналогично рассчитываем затраты на такое сокращение: 5*35=175

На седьмом шагерассматриваемая работа 5-6, которая входит в первый и третий полный путь и еепродолжительность может быть сокращена на 1 сутки, (из 3 возможных), т.к. приэтом продолжительность третьего полного пути, в который она входит становитсяравной заданной: 20-1=19, а продолжительность первого полного пути меньшетребуемого. Аналогично рассчитываем затраты на такое сокращение: 1*40=40

Подсчитавсуммарные дополнительные затраты на произведенное сокращение продолжительностейработ (310 у.е.) и зная первоначальную стоимость (1060 у.е.) всего комплекса работ врассматриваемом нормальном варианте его выполнения, получим, что при снижениипродолжительности выполнения всего комплекса работ с 29 суток до 19 сутокоптимальные затраты составят 1060+310=1370 (у.е.).

Представимрешение поставленной задачи вторым способом в таблице:

№ шага Суточный прирост затрат Работа Количество наращиваемых суток Продолжительность полного пути Общее снижение затрат 1-2-5-6 1-3-6 1-2-4-5-6 - - - 13 11 17 - 1 40 5-6  3 (2) 15 19 -80 2 35 4-5  5 (2) -

-

- - 3 30 3-6 6 (6) - 17

-

-180 4 25 2-5 2 (2) 17 - - -50 5 20 1-2 1 (1) - - - - 6 15 1-3  5 (2) - 19 - -30 7 10 2-4 3 - - - - - В С Е Г О -340

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

На первомшаге продолжительность работы 5-6 может быть увеличена только на 2 суток извозможных (3), т.к. при этом продолжительность третьего полного пути станет кактребуемая в задании. Тогда затраты на эту работу, с более поздним срокомвыполнения, снизятся на 2·40=80 (у.е.), т.е. -80 у.е.

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

Рассматриваяработу 3-6 на третьем шаге, увеличиваем продолжительность второго пути на 6суток, т.к. продолжительность второго полного пути станет как требуемая взадании.

На четвертомшаге продолжительность работы 2-5 в первом полном пути можно увеличить намаксимально возможное число суток.

Пятый шаг 1-2мы не используем.

Шестой шаг1-3 увеличиваем на 2 из 5 возможных, т.к. при этом продолжительность второгополного пути станет как требуемая в задании -19

Седьмой шаг2-4 мы не используем.

Подсчитав суммарноеснижение затрат из-за произведенного увеличения продолжительностей работ (-340у.е.) и зная первоначальную стоимость (1710 у.е.) всего комплекса работ врассматриваемом ускоренном варианте его выполнения, получим, что при увеличениипродолжительности выполнения всего комплекса работ с 17 суток до 19 суток оптимальныезатраты составят 1710-340=1370 (у.е.).

Итоговые результаты,полученные обоими способами оптимизации, должны совпадать. Проверим это:

1) продолжительностисоответствующих полных путей после оптимизации совпадают – 19,19,17;

2) стоимостивыполнения всего комплекса работ после оптимизации совпадают – 1370.

ЗАКЛЮЧЕНИЕ

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

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

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

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

1. АбланскаяЛ.В., Бабешко Л.О., Баусов Л.И. Экономико-математическое моделирование: М.:Экзамен, 2006г. – 800с.

2. 1. БакановМ.И., Шеремет А.Д. Теория экономического анализа: Учебник. — М.: Финансы истатистика, 1997.

3. ДрогобыцкогоИ.Н Экономико-математическое моделирование: М.: Экзамен, 2004г. – 323с.

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

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