Операции сетевого планирования

Задачи сетевого планирования и управления. Виды операций: составные, параллельные, зависимые и независимые. Полный и независимый резерв времени для критических операций. Приведение модели к каноническому виду. Решение задач двойственным симплекс-методом.

Рубрика Экономико-математическое моделирование
Вид курсовая работа
Язык русский
Дата добавления 20.05.2014
Размер файла 2,9 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

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

Введение

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

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

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

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

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

Глава 1. Задачи сетевого планирования и управления

Определим понятие графа. Для этого рассмотрим множество, состоящее из конечного числа элементов, которые обозначим буквами Х1, Х2, ..., Хп, а само множество -- буквой X; запишем это символически:

X = {X1, X2,...,Xn}.(1)

Каждому элементу Xi , принадлежащему X, поставим в соответствие нуль, один или несколько элементов из X; мы построим тогда, пользуясь терминологией теории множеств некоторый "граф". Обозначив через Г закон, представляющий данное соответствие, запишем граф символически: G = (X, Г).

Возьмем пример для иллюстрации этого определения. Пусть мы имеем множество из 6 элементов: X = {A, B, C, D, E, F}, и рассмотрим следующее соответствие, определенное с помощью символа Г:

ГА = {B,C,D}, ГВ = {A,B,C}, ГС = {B,D,E,F}, ГD = {C,D,E}, ГЕ = {C,E}, ГF = O,

где символ O означает, пользуясь терминологией теории множеств, пустое множество и аналогичен нулю при числовой нумерации.

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

В теории множеств "графом" называют всякое отображение множества в себя. Символ Г представляет это отображение.

Элемент множества, образующего граф, называется "вершиной". На рис. 1 элементы А, В, С, D, Е и F представляют собой вершины графа. Некоторыми авторами вершина называется также "точкой".

Ориентированная пара (Xi Xj) вершин Xt и Xj называется "дугой". Так, на рис. 1, (А, В), (В, А), (А, С), (Е, Е),(С, F) представляют собой дуги.

Таблица 1. Матрица графа

A

B

C

D

E

F

A

0

1

1

1

0

0

B

1

1

1

0

0

0

C

0

1

0

1

1

1

D

0

0

1

1

1

0

E

0

0

1

0

1

0

F

0

0

0

0

0

0

Обозначим через U множество дуг, тогда в нашем примере:

U = {(А, В), (А, С), (А, D), (В, А), (В, В), (В, С), (С, В), (С, D),

(С, Е), (С, F), (D, С), (D, D), (D, Е), (Е, С), (Е, Е)}.

Граф может обозначаться через G = (X, Г) или G = (X, U)Путь - это последовательность сцепленных дуг, позволяющих пройти из одной вершины в другую; (А, В, С, F), (А, С, D, Е,С, F), (А, В, А), (А, D), (А, В, В, С) представляют собой пути.

Контур - это путь, начальная вершина которого совпадает с конечной: (А, С, В, А), (А, D, Е, С, В, А), (А, С, В, А, С, В, А),(А, В, А), (В, В) являются контурами, см. рис. 1.

Петля - это дуга, начало и конец которой совпадают: (В, В), (D, D) и (Е, Е) представляют собой петли, см. рис. 1.

Длина пути или контура - это число дуг пути или контура. Так, длина (А, В, С, F) равна 3, длина (А, D, Е, С, В, А) равна 5.

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

Например, на рис. 1. между А и D есть ребро. Нет ребра между В и D. Ребро обозначается (А, D) или ( А, В); множество ребер обозначим U. Так, в нашем примере, см. рис. 1:

U = {(A,B), (A,C), (A,D),(B,C), (C,D), (C,E), (C,F), (D,E)}

Цепь - это последовательность сцепленных ребер, т. е. последовательность дуг, сцепленных без учета их ориентации. Так, на рис. 1 (В, С, A, D, Е) не есть путь (из-за дуги АС), но это цепь. Всякий путь является, очевидно, цепью, но, как видно, цепь не всегда является путем.

Граф называется "связным", если между всякой парой его вершин существует хотя бы одна цепь. Граф на рис. 1 связен. Граф "сильно связен", если между всякой парой его вершин существует хотя бы один путь. Граф на рис. 1 не является сильно связным, т.к. не существует путей от F к другим вершинам. Антисимметричный" граф. Рассмотрим множество U дуг графа. Если для всякой дуги (Xi Xj), принадлежащей U, дуга (Xj, Xi), т. е. противоположная ей, не принадлежит U, то говорят, что граф "антисимметричен". В силу этого определения антисимметрический граф не может содержать петель. Например, граф на рис. 3 "антисимметричен".

Рассмотрим граф без контуров. На рис. 3 мы видим граф, не содержащий ни одного контура. Очевидно, что всякий граф без контура антисимметричен, но обратное утверждение неверно.

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

Проект может быть представлен сетью, называемой "сетевой моделью проекта" или логической диаграммой, дуги которой представляют операции. Времена выполнения операций или длительности операций предполагаются известными и приписываются дугам как неотрицательные величины. Вершины сети, называемые событиями и обозначаемые Ei могут интерпретироваться как результаты выполнения отдельных частных задач (например, окончания монтажа блока). Если разбиение произведено слишком детально (при этом операции все более и более упрощаются, а их длительности уменьшаются), то в этом случае практическое значение рассматриваемых событий значительно снижается, за исключением тех из них, которые фиксируют основные этапы проекта. Длительность операции Рij, участвующей в реализации события Ej, будет обозначаться tij. На приведенном ниже рис. 4 представлен некоторый проект.

Рис. 4

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

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

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

1 разработка проекта

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

3 подписание контракта

4 подвоз материалов к стройке (бетон, плиты, кирпич)

5 подвод электричества и воды к стройке

6 фундамент

7 кирпичная кладка

8 плотницкие работы

9 покрытие

10 грунтовка

11 перегородки (из пустотелого кирпича)

12 трубы (вода, центральное отопление, газ)

13 внутренняя электропроводка

14 установка рам и окон

15 обработка стен и перегородок (цемент)

16 установка двух дымовых труб

17 плиточная облицовка -- санитарное оборудование -- кухонный настил

18 штукатурка

19 установка штепселей и электрических выключателей

20 установка дверей и окон

21 покраска и оклейка обоев

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

23 подвоз земли для сада

24 установка счетчиков и подвод радио, телевидения, телефона, воды

25 уборка строительной площадки

26 предварительный прием.

Рассмотрим построение сети, изображенной на рис. 5. Обозначим через Е1 начальное событие (т. е. начало выполнения работ), а через Е2 -- событие: контракт может быть подписан. Между Е1 и Е2 находятся две операции: составление плана и получение разрешения на строительство. Если административный порядок предполагает, что разрешение на строительство не может быть выдано без представления проекта (что обычно имеет место), поместим между Е1 и Е2 событие Е3: разработка проекта закончена. После события Е2 можно приступить одновременно к операциям е и с с длительностями операций t24 и t25. Действительно, подвод электричества и воды не есть, вообще говоря, дело подрядчика. Событие Е5 означает подписание контракта. После этого можно приступить к операции d с временем операции t54. Операция f с временем t46 помещается после события Е4, так как она может начаться только после окончания операций d и e. И так далее по операциям.

Представление проекта с помощью сети может быть сделано и другим образом. Будем изображать вершинами не события, а операции. Дуги же используем для представления порядка, в котором операции Oij и Ojk должны следовать так, чтобы можно было задавать сроки между началом Oij и началом Ojk .В этом представлении принято называть "работами" то, что раньше мы назвали операциями, и "связями" -- дуги, которым приписаны сроки. На рис. 6 приведена сеть, соответствующая рис. 5 после такой замены.

Чтобы до конца разъяснить переход от одного представления к другому, возьмем другой пример -- переход от рис. 7 к рис. 9. Как видно на рис. 8 и 9, принято добавлять две работы D и F, представляющие начало (debut) и конец (fin) проекта.

Рис. 7

На рис. 9, видно, что работа g помещается после работ b и d. Между g b существует связь: g может начаться только тогда, когда пройдет 6 единиц времени после начала b. Между g и d существует связь: g может начаться только тогда, когда пройдет 4 единицы времени после начала d. В свою очередь работы d, f и е могут начаться только после того, как пройдет 3 единицы времени после начала а. Оба представления обладают и преимуществами и недостатками. Обычно выбирают то или другое представление в зависимости от существа той задачи, для которой составляется проект. Заметим, однако, что представление "работы--связи" позволяет вводить в проект новые связи или изменять отношения порядка между работами простым добавлением дуг без перестройки сети в целом.

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

1) составные операции. Рассмотрим операцию а, состоящую из трех элементарных операций: а1 , а2 и а3, см. рис. 10, и пусть операция с следует за аи d следует за а2 и b следует за а3. Рис. 11 представляет эту ситуацию в терминах, "работы--связи". Рис. 12 показывает, что это представление можно упростить; исчисление новых связей не представляет трудностей.

2) параллельные операции. Предположим, что между двумя событиями Ei и Ej находятся две различные операции b и с, следующие за операцией а. Введем тогда фиктивное событие Еj` и дополнительную фиктивную операцию х между Ej` и Ej. В случае, когда имеется три, четыре и т. д. параллельные операции, поступают так же, вводя для каждой из них фиктивное событие и дополнительную фиктивную операцию. На рис. 15, введение фиктивных событий и операций нецелесообразно.

3) операции зависимые и независимые. Рассмотрим на рис. 16 операции c и d, следующие за а и b. Предположим теперь, что с следует за. а и b, но d следует только за b и не обязано следовать за а. В этом случае уже нельзя пользоваться данной сетью и необходимо ввести событие Ез` и фиктивную операцию х, см. рис. 17.

В представлении "работы--связи" нет необходимости вводить фиктивные события и операции. Рис.18 соответствует рис.16, а рис. 19 --рис. 17.

Имеют значение также особые ограничения и условия на сроки начала выполнения операций. Предположим, что некоторая операция может быть начата только по наступлении какого-то момента, т. е. по прошествии некоторого срока после события Е1 , принимаемого за начальное. Такое ограничение выражается введением фиктивной операции между E1 и событием Еi , где начинается рассматриваемая операция, см. рис. 20. В другом представлении вводится связь между D и b, см. рис. 21.

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

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

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

Это можно понять с помощью простейшей сети, изображенной на рис. 2.2. Событие Е3 означает выполнение трех операций Р13, Р12 ,и Р23. Для того чтобы все эти операции могли быть реализованы, необходимо 8 единиц времени.

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

Рис. 22

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

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

Рассмотрим рис. 23. В Е2 входит только одна дуга (1,2). Поскольку для Е1 имеем 0, то для Е2 получим 0 + 8 = 8. В Е3 входят две дуги (2,3) и (1,3): сравнивая 8 + 4=12 с 0+13=13, приписываем Е3 значение 13, это означает, что наступление события Ез нельзя ожидать раньше 13. В Е4 входят две дуги (3,4) и (1,4): сравнивая 13 + 7 = 20 с 0 + 9 = 9, приписываем Е4 значение 20. Е5 приписываем значение 17. В Е6 входят две дуги (2,6) и (3,6): сравнивая 8 + 6=14 с 13+10 = 23, приписываем Е6 значение 23. В Е8 входят три дуги (6,8), (3,8) и (4,8): сравнивая 23 + 3 = 26, 13 + 6=19 и 20 + 9 = 29, приписываем Е8 значение 29. Так продолжаем вплоть до события Е12, которому приписываем окончательно значение 61.

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

Рис. 23

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

Операции Р13, Р34, Р48, Р8,11, Р11,10, Р10,12 называются "критическими операциями". С них нужно начинать работу после наступления начальных событий соответствующих дуг. Так, к примеру, операция Р48 должна начаться в первую очередь после реализации события Е4, т. е. в момент 20. Если критическая операция будет задержана, это вызовет запаздывание выполнения всего проекта. Например, если операция Р48 начнется только, в момент 22, проект будет завершен не раньше, чем к моменту 63.

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

Приходим к выводу, что для каждого некритического события Ei важно знать предельный срок его наступления, т. е. срок, превышение которого приведет к задержке выполнения всего проекта. Для этого рассмотрим событие Еi. Минимальное время, необходимое для наступления всех событий, расположенных между событиями Ei и Еп, получается определением в сети "самого длинного" пути от Ei до Еп. Эта процедура обеспечивает нам уверенность в возможности действительного выполнения операций, следующих за Ei, с учетом соответствующих им длительностей. Искомый предельный срок ti* получается вычитанием этого минимального времени из времени tn наступления конечного события Еп.

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

время ti , ожидаемое время наступления события Ei ,

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

Ожидаемое время ti иногда называют "наиболее ранний срок", а пре- дельное время ti* -- "наиболее поздний срок". Для критических событий предельный срок ti* совпадает с ожидаемым временем ti. Эти события не допускают никакого запаздывания в сроках их наступления, или (что означает то же самое) критические операции не допускают никакой задержки в их выполнении.

Интервал [ti , ti*] называется интервалом свободы события (резервным интервалом). Резервный интервал - это интервал времени, в течение которого может наступить событие Еi без изменения общего времени завершения всех работ. Длина интервала свободы события (резервного интервала), т. е. величина ti* - ti , называется резервом времени события Ei.

Обратимся опять к примеру постройки дачи и вычислим граничные сроки ti*, используя тот же метод, как и при вычислении ti,, но отправляясь на этот раз от конечного события Е12. Рассмотрим сначала, см. рис. 24, событие Е1, отделенное от события Е11 операцией длительностью 4, так что операция P7,11 может начаться за четыре недели до события Е11 и, следовательно, событие Е7 должно произойти в интервале [37, 38]. Событие E9 отделено от события Е10 операцией длительностью 5, так что операция Р9,10 может начаться за пять недель до события Е10 и поэтому событие E9 должно произойти в интервале [33,43]. Событие Е6 отделяет от события E9 операция в 8 недель, от события Е8 -- 3 недели, от события Е7 -- 5 недель; из сравнения 43--8 = 35, 29--3 = 26 и 38--5 = 33 видно, что событие Е6 должно произойти не позднее момента 26 (наименьшее из трех), чтобы не вызвать нарушений, которые отразились бы на завершающей дате. Числа, которые при этом получаются, выписаны на рис. 2.21 и заключены в скобки, чтобы не путать их с теми числами, которые были получены при нахождении критического пути. Событию Е5 припишем 40; событию Е2 после сравнения 40--9 = 31, 26--6 = 20, 13--4 = 9 припишем 9.

Рис. 24

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

Для каждой операции Pij также важно знать, какая задержка может быть допущена при ее выполнении без того, чтобы это привело к нарушению срока наступления события Ej. Эта возможная отсрочка начала выполнения операции Pij - есть "свободный резерв времени" операции Рij, обозначаемый в дальнейшем через Мij.

Если ti и tj -- ожидаемые сроки наступлений событий Ei и Ej, между которыми имеется операция Рij длительностью tij, то ее свободный резерв времени равен:

Мij =tj - ti - tij. (2)

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

Таким же образом определяются для каждой операции "полный резерв времени" и "независимый резерв времени".

По определению полный резерв времени операции Рij равен:

tj* - ti - tij , (3)

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

tj - ti * - tij (4)

Резервы событий и операций характеризуют эластичность проекта. Чем более они уменьшаются, тем жестче сеть проекта. Сеть проекта "полной жесткости" такова, что все ее пути являются критическими. В ней нет ни резервов событий, ни свободных резервов операций. При таком положении недопустимы никакие задержки ни по какой из операций.

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

Другой аспект понятия свободный резерв может быть выявлен в случае, когда продолжительность некритических операций может быть удлинена. В этом случае свободный резерв Мij соответствует возможному удлинению длительности операции Pij,, оставляющему неизменными сроки ti и tj наступления событий Ei и Ej,, определяющих эту операцию.

Эта разница между резервом события и свободным резервом, или полным резервом операции, лучше всего видна в сети, изображенной на рис. 24 и воспроизведенной на рис. 25.

Здесь интервал свободы события Е6 есть [23, 26]. Свободный резерв операции Р69 равен:

М69 = 33 -- 23 -- 8 = 2.

Следовательно, операция Р69 может начаться в момент 23+2 = 25 без изменения времени t9 -- срока наступления события E9, который остается равным 33. Свободные резервы операций указаны на рис. 25 в скобках.

Рис. 25

Полный резерв операции Р69 равен 43--23--8 =12. Таким образом, операция Р6э может начаться в момент 23+12=35, не вызывая задержку выполнения всего комплекса работ.

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

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

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

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

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

В таблице 2 пунктирные стрелки указывают порядковые отношения различных операций. Проект начинается с операций А, В и Е.

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

Рис. 27

Рис. 26

Таблица 2. Виды работ и операции

Таблица 3 Длительности операций (в днях)

A - 10

B - 3

C - 15

D - 10

E - 15

F - 5

G - 30

H - 20

I - 4

J - 18

K - 60

L - 20

M - 5

N - 25

O - 5

P - 20

Q - 43

R - 35

S - 40

T - 2

U - 20

V - 20

W - 35

X - 55

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

· Сеть, соответствующая организации строительства с приоритетом первого пролета.

Обозначим детализированные операции - это операции--Л, С, К, L, M, N, R, S, U, V. Обозначения операций и их длительности указаны в таблице 4. Теперь можно вычертить сеть проекта и вычислить ожидаемые сроки наступления различных событий, см. рис. 28

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

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

Рис. 28

Таблица 4. Длительности операций

Сеть, соответствующая строительству с приоритетом двух пролетов.

Новые длительности операций характеризуются следующими данными:

Таблица 5. Длительности операций (в днях)

K1 - 24

K2 - 36

L1 - 8

L2 - 12

M1 - 2

M2 -3

N1 - 10

N2 -15

R1 - 14

R2 - 21

S1 - 16

S2 - 24

U1 - 8

U2 - 12

V1 - 8

V2 - 12

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

Рис. 29

· Сеть, соответствующая строительству с приоритетом трех пролетов

Новые длительности операций характеризуются следующими данными:

Таблица 6. Длительности операций (в днях)

K1 - 36

K2 - 24

L1 - 12

L2 - 8

M1 - 3

M2 -2

N1 - 15

N2 -10

R1 - 21

R2 - 14

S1 - 24

S2 - 16

U1 - 12

U2 - 8

V1 - 12

V2 - 8

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

Рис. 30

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

Глава 2. Практическая часть

Задача 1.

Max Z = 3X1 + 2X2 + X3

3X1 + 4X2 + 5X3 ? 5

2X1 + 4X2 + 8X3 ? 8

6X1 + 6X2 + 4X3 ? 4

X1 ? 0; X2 ? 0; X3 ? 0.

Решение:

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

Z = 3X1 + 2X2 + X3 + 0X4 + 0X5 + 0X6 > max

3X1 + 4X2 + 5X3 + X4 = 5

2X1 + 4X2 + 8X3 + X5 = 8

6X1 + 6X2 + 4X3 + X6 = 4

X1 ? 0; X2 ? 0; X3 ? 0.

На основе канонической модели строим так называемую симплексную таблицу.

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

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

Вывод:

Z0 = 2; X4 = 3, X5 = 6? , X1 = ?, X2 = X3 = X6 = 0.

Задача 2

Min Z = 5X1 + 3X2 + 4X3 + X4

X1 + 3X2 + 8X3 + 7X4 ? 24

3X1 + 2X2 + X3 + 4X4 ? 12

4X1 + 3X2 + 5X3 + X4 ? 24

X1 ? 0; X2 ? 0; X3 ? 0; X4 ? 0.

Решение:

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

Для превращения неравенств в равенства введем дополнительные переменные:

Z = 5X1 + 3X2 + 4X3 + X4 - 0X5 - 0X6 - 0X7 > min

X1 + 3X2 + 8X3 + 7X4 - X5 = 24

3X1 + 2X2 + X3 + 4X4 - X6 = 12

4X1 + 3X2 + 5X3 + X4 - X7 = 24

X1 ? 0; X2 ? 0; X3 ? 0; X4 ? 0.

Поскольку в двойственном симплекс-методе мы исходим из недопустимости планов, то базис можно получить умножением системы ограничений на - 1. Тогда получим:

Z = 5X1 + 3X2 + 4X3 + X4 - 0X5 - 0X6 - 0X7 > min

-X1 - 3X2 - 8X3 - 7X4 + X5 = -24

-3X1 - 2X2 - X3 - 4X4 + X6 = -12

-4X1 - 3X2 - 5X3 - X4 + X7 = -24

X1 ? 0; X2 ? 0; X3 ? 0; X4 ? 0.

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

Видим, что все значения Z-строки положительны, т.е. решение оптимально. Но оно, в то же время, является недопустимым, так как свободные члены (Bi) отрицательны. Это базисное решение называется псевдопланом.

Преобразование симплексных таблиц в двойственном симплекс-методе осуществляется так же, как и в прямом алгоритме. Единственное различие осуществляется в правилах определения ключевого элемента. Здесь он находится следующим образом: вначале выбирается ключевая строка, соответствующая базисной переменной, для которой Bi является наименьшей величиной среди всех отрицательных Bi.Затем определяется вектор, вводимый в базис (ключевой столбец), для чего рассчитывается величина Qj = ZJ - CJ/ аij , причем аij должны быть отрицательны и принадлежать ключевой строке. Ключевой столбец соответствует переменной, для которой ¦ Qj ¦ > min. Ключевой элемент находится на пересечении ключевой строки и ключевого столбца.

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

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

Вывод:

Z0 = 372/19; X3 = 84/19, X4 = 36/19, X5 = 468/19, X1 = X2 = X6 = X7 =0.

Задача 3

Max Z = X1 + 2X2 + 3X3

4X1 + 3X2 + 2X3 + X4 ? 20

4X1 + 3X2 + 2X3 ? 27

2X1 + 2X2 + X3 + X4 ? 18

2X1 + X2 + X3 ? 20

X1 ? 0; X2 ? 0; X3 ? 0.

Решение:

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

Z = X1 + 2X2 + 3X3 + X4 + 0X5 + 0X6 - 0X7 - МX8 + 0X9

4X1 + 3X2 + 2X3 + X4 + X5 = 20

4X1 + 3X2 + 2X3 + X6 = 27

2X1 + 2X2 + X3 + X4 - X7 - X8 = 18

2X1 + X2 + X3 + X9 =20

X1 ? 0; X2 ? 0; X3 ? 0.

Некоторые значения Z-строки отрицательны, а задача на максимум, следовательно, решение не оптимально. Строим новую симплексную таблицу.

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

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

Итак, значения Z-строки положительны, а задача на максимум, следовательно, решение оптимально.

Вывод:

Z0 = 22; X3 =2; X4 =16; X6= 23; X9 = 18; X1 = X2 = X5 = X7 = X8 =0.

Задача 4

Min Z = Х1 + 2Х2

1 + 4Х2 ? 30

1 + 5Х2 ? 30

1 ? 12

1 + 4Х2 ? 24

1 + 7Х2 ? 30

1 + 8Х2 ? 30

Решение:

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

Z = Х1 + 2Х2 + 0Х3 + 0Х4 +0 Х5 - 0 Х6 + МХ7 - 0Х8 + МХ9 - 0 Х10 + МХ11> min;

1 + 4Х2 + Х3 =30

1 + 5Х2 + Х4 =30

1 + Х5 =12

1 + 4Х2 - Х6 + Х7 =24

1 + 7Х2 - Х8 + Х9 =30

1 + 8Х2 - Х10 + Х11 = 30

Строим первоначальную симплексную таблицу.

сетевой планирование операция симплекс

Некоторые значения Z-строки - положительные значения, а задача на минимум, то строим новую симплексную таблицу.

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

По значениям Z-строки мы видим, что решение не оптимально. Можно продолжить преобразование, однако, по значениям В-столбца видно, что дальнейшее преобразование не имеет смысла.

Вывод: данная задача не имеет решения.

Задача 5

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

Условие: предприятие выпускает машины трех различных моделей: модель А, модель В и модель С. Каждая машина указанных моделей приносит предприятию доход в размере 8, 15 и 25 рублей, соответственно. Необходимо, чтобы предприятие выпускало за неделю не менее 100 машин модели А, 150 машин модели В и 75 машин модели С. Каждая модель характеризуется определенным временем на изготовление комплектующих, на сборку и упаковку. Так, на 10 машин модели А требуется 10 часов на изготовление комплектующих, 4 часа на сборку и 1 час на упаковку. Соответствующие показатели в расчете на 10 машин модели В равняются 4, 5 и 1,5 часам, а на 10 машин модели С - 5, 3 и 3 часа. В течение ближайшей недели предприятие может израсходовать на производство комплектующих 150 часов, на сборку 200 часов и на упаковку 60 часов. Определить недельный выпуск машин каждой модели, максимизирующий доход предприятия.

Решение:

Пусть i -модели машин, i = 1, m =1,3. А j -индекс вида работ, j = 1,n = 1,3.

Тогда Mij - время каждого j-го вида работ, необходимого для производства каждой i-той модели машин;

Вj - фонд времени на каждый j-тый вид работ;

Сi - доход предприятия от каждой i-той машины;

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

Построим математическую модель в общем виде:

Z = ?Yi Xi > max

? Mij Xi ? Вj j = 1, n

Xi ? 0.

ЭММ в развернутом виде будет иметь вид:

С1 Х1 + С2 Х2 + С3 Х3 > max

M11 Х1 + M12 Х2 + M13 Х3 ? 150

M21 Х1 + M22 Х2 + M23 Х3 ? 200

M31 Х1 + M32 Х2 + M33 Х3 ? 60

Х1 ? 100; Х2 ? 150; Х3 ? 75.

Задача 6

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

Трудоемкость изготовления деталей, мин.

фонд времени рабочего, ч.

А

Б

В

1 рабочий

6

8

10

180

2 рабочий

4

4

7

180

3 рабочий

12

16

21

160

Цена детали, руб.

0,6

1,5

2,8

Решение:

Пусть i - индекс № рабочего, i = 1, m =1,3,

j - индекс (А,Б,В) детали, j = 1,n = 1,3.

Тогда Аij - трудоемкость изготовления каждой i-той детали на каждом j-том станке,

Вi - фонд времени каждого i-того рабочего,

Сj - цена одной детали j-того,

Хj - какое количество деталей каждого j-того вида выпустить, чтобы максимизировать валовой выпуск деталей.

ЭММ в общем виде:

Z = ? Cj Xj > max

? Аij Хj ? Вi i = 1, m =1,3

Хj ? 0.

ЭММ в развернутом виде:

Z = С1 Х1 + С2 Х2 + С3 Х3 > max

А11 Х1 + А12 Х2 + А13 Х3 ? В1

А21 Х1 + А22 Х2 + А23 Х3 ? В2

А31 Х1 + А32 Х2 + А33 Х3 ? В3

Х1,2,3 ? 0.

Задача 7

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

Для решения задачи необходимо рассчитать потенциалы:

вj= бi+cij ; бi= вj-cij


Подобные документы

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

    лекция [313,1 K], добавлен 09.03.2009

  • Основные параметры сетевой модели системы планирования и управления. Правила построения сетевых графиков. Характеристики элементов сетевой модели. Метод пересмотра планов. Численная реализация задачи сетевого планирования. Метод графической оценки.

    реферат [154,4 K], добавлен 19.03.2015

  • Сравнение экономико-математических методов сетевого планирования при решении практических задач управления. Временные характеристики и правила построения сетевых графиков. Оптимизация проекта по времени и стоимости. Особенности метода критического пути.

    курсовая работа [1,5 M], добавлен 29.03.2015

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

    контрольная работа [669,9 K], добавлен 14.02.2011

  • История создания средств цифровой вычислительной техники. Методы и модели линейного программирования. Экономическая постановка задачи. Выбор метода реализации задачи. Особенности выбора языка программирования. Решение задачи сетевым методом планирования.

    курсовая работа [842,1 K], добавлен 19.02.2015

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

    контрольная работа [296,3 K], добавлен 28.03.2012

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

    курсовая работа [54,1 K], добавлен 05.03.2010

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

    контрольная работа [192,0 K], добавлен 15.04.2014

  • Алгоритм решения оптимизационной задачи линейного программирования (ЗЛП) – планирования производства симплекс методом и при помощи средства "Поиск решения" в Microsoft Excel. Описание работы, графический интерфейс и схема программы для решения ЗЛП.

    дипломная работа [2,3 M], добавлен 19.09.2010

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

    курсовая работа [39,6 K], добавлен 07.12.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.