![]()
Главная Обратная связь Дисциплины:
Архитектура (936) ![]()
|
Невырожденным поток в сети. Остовное дерево. Критический путь
Поскольку задача (3.15)-(3.17) является частным случаем задачи линейного программирования, ее можно привести к канонической форме. При этом достаточно просто устанавливается, что ранг матрицы задачи равен m-1, где m — количество вершин в сети. Введем дополнительно еще некоторые понятия, используемые при описании свойств сетевых задач. Остовом сети (I, D, G) называется любое ее частичное дерево (частичный граф, являющийся деревом). Справедливо утверждение: Произвольному остову сети (I, D, G) соответствует базис задачи (3.15)-(3.17) и наоборот. Пусть имеется некоторый поток Х={хd}d?D. Рассмотрим множество дуг D(X)= {d ?D| 0 < xd< rd}.Опорой потока Х называется частичный граф (I, D(X), G). Говорят, что поток Х невырожден, если егоопора (7, D(X), G) является остовом сети (I, D, G). Иными словами, используя терминологию транспортной задачи, в невырожденном потоке, которому отвечает допустимый базисный план задачи, дороги, покоторым осуществляются перевозки груза, не достигающие по объему ограничения на пропускную способность, образуют остов (связанную подсеть без циклов) рассматриваемой транспортной сети.1°. Предполагается, что в начале очередной итерации q имеется некоторый допустимыйневырожденный потокХ={хd(q)}d?DПо имеющемуся потоку Х(q) строится система потенциалов пунктов сети. Для этого выбираетсяпроизвольный пунктi0, потенциал которого полагаетсяvi0=0. Множество вершин, смежныхс i0,обозначимчерез I(i0). Тогда для любой вершины j ? I(i0) потенциалы рассчитываются по правилуесли (i0,j) ? D(X(q)) (дуга направлена от i0),иесли (j,i0)?G(D(X(q))) (j,i0)?D(X(q)) (дуга направлена к i0).Получив очередную группу вершин с известными потенциалами, мы имеем возможность на основе(3.22)-(3.23) вычислить потенциалы для следующей группы смежных вершин и т. д., пока не будутопределены все потенциалы. Возможность сделать это единственным образом вытекает из свойстваотсутствия циклов у остова сети. Имея полную систему потенциалов, для всех дуг следует проверить условия критерия оптимальности(3.19)-(3.21). Если они выполняются, то текущий поток Х(q)— оптимальный и, следовательно, алгоритмзавершен; в противном случае — переходим к построению следующего «улучшенного» потока.
Алгоритм о нахождении кратчайшего пути. Этапы методов сетевого планирования. Методы сетевого планирования. 1. метод критического пути (СРМ) 2. система планирования и руководства программами разработок. Основные этапы критического пути СРМ: 1. определяются процессы проекта 2. построение сети 3. вычисление 4. построение временного графика. Построение сети: Каждый процесс проекта обозначается в сети дугой, ориентированной по направлению выполнения проекта. Все узлы устанавливают отношение предшествования между процессами проекта. 3 правила построения сети: 1. каждый процесс в проекте представляется только одной дугой. 2. каждый процесс проекта идентифицируется двумя узлами. 3. Для поддержания правильных отношении предшествования при включении в сеть нового процесса необходимо ответить на след вопросы: А) Какой процесс непосредственно предшествует текущему? Б) Какой процесс должен выполняться непосредственно после текущего? В) Какой процесс выполняется параллельно с текущим? После выполнения вычисления получаем следующую информацию. 1) Общая продолжительность проекта. 2) разделение множества процессов, составляющих проект на критические и не критические. Процесс является критическим, если он не имеет резерва времени, своего начала и завершения. Для некритического процесса возможен некоторый резерв времени , его начало и завершения, но в определенных границах, когда время его начала не влияет на продолжительность выполнения проекта. Определим событие как точку на временной оси, где завершается один процесс и начинается другой. □j- самое раннее возможное время наступления события j. ∆j-самое позднее возможное время наступления события j Dij – продолжительность процесса ij. Вычисление критического пути выполняется в 2 этапа (подхода) - при проходе вперед вычисляются самые ранние времена наступления событий. - при проходе назад вычисляться самые поздние времена наступления тех же событий. Проход вперед: Вычисления начинается в 1 узле и заканчивается в последнем Шо: □1=0 Основной шаг: Для узла i определяем узлы, которые непосредственно связаны с текущим узлом процессами. для которых уже вычислены ранние времена начальных событий. □j=max {□p+Dpj,….□q+Dqj} Проход вперед заканчивается, когда будет вычислена величина раннего времени события По определению самое раннее время наступления события n = продолжительности проекта. Проход назад - вычисление начинается в последнем узле и заканчивается в первом Шо: самое позднее время наступления событий n= самому раннему ∆n=□n Основной шаг: Для узла i определяем узлы, которые непосредственно связаны с исходным узлом i процессами, для которых уже вычислены самые поздние времена наступления событий(∆n). ∆j=min {∆p-Djp,….,∆q-Djq} Проход назад заканчиваеться когда будет вычислен величина ∆1. Процесс ij будет критическим, если выполняется следующее условие 1. ∆i=□i 2.∆j=□j 3.∆j-∆i=□j-□i=Dij 34 Построение временного графика и основных характеристик.На сетевом графике отображены временные параметрысобытий: ранний и поздний срок свершения события, резерв события. Событие – это момент времени, когда завершаются одни работы и начинаются другие. Например, фундамент залит бетоном, старение отливок завершено, комплектующие поставлены, отчеты сданы и т.д. Событие представляет собой результат проведенных работ и, в отличие от работ, не имеет протяженности во времени. Событие, не имеющее предшествующих ему событий, т.е. с которого начинается проект, называют исходным. Событие, которое не имеет последующих событий и отражает конечную цель проекта, называется завершающим. Работа – это некоторый процесс, приводящий к достижению определенного результата, требующий затрат каких-либо ресурсов и имеющийпротяженность во времени. По количеству затрачиваемого времени, работа может быть: - действительной, т.е. требующей затрат времени; -фиктивной, т.е. формально не требующей затрат времени и представляющей связь между какими-либо работами, например: передача измененных чертежей от конструкторов к технологам; сдача отчета о технико-экономических показателях работы цеха вышестоящему подразделению. При построении сетевого графика необходимо следовать следующим правилам: - длина стрелки не зависит от времени выполнения работы; - стрелка может не быть прямолинейным отрезком; - для действительных работ используются сплошные, а для фиктивных –пунктирные стрелки; - каждая операция должна быть представлена только одной стрелкой; - между одними и теми же событиями не должно быть параллельных работ, т.е. работ с одинаковыми кодами; - следует избегать пересечения стрелок; - не должно быть стрелок, направленных справа налево; - номер начального события должен быть меньше номера конечного события; - не должно быть висячих событий (т.е. не имеющих предшествующих событий), кроме исходного; - не должно быть тупиковых событий (т.е. не имеющих последующих событий), кроме завершающего; - не должно быть циклов. К временным параметрам событий относятся: 1)T р(i) – ранний срок наступления события i. Это время, которое необходимо для выполнения всех работ, предшествующих данному событию i. Оно равно наибольшей из продолжительности путей, предшествующих данному событию. Tр(i)=max{Tр(k)+t(k,i)}, max берется по всем работам, входящим в событиеi, t(k,i)- длительность работы k. 2)Tп(i) – поздний срок наступления события i. Это такое время наступления события i, превышение которого вызовет аналогичную задержку наступления завершающего события сети. Поздний срок наступления любого события i равен разности между продолжительностью критического пути и наибольшейиз продолжительностей путей, следующих за событием i. T n(i)=min{ T n(j)-t(i,j)} min берется по всем работам, выходящим из события i. 3)R(i) – резерв времени наступления события i. Это такой промежуток времени, на который может быть отсрочено наступление события i безнарушения сроков завершения проекта в целом. R(i)=Tn(i)-T р(i) Начальные и конечные события критических работ имеют нулевые резервы событий. К временным параметрам работ относятся: - ранний срок начала работы: Tрн(i, j)=T р(i) - поздний срок начала работы: Tпн(i, j)=T п(j) - t(i, j) - ранний срок окончания работы: Tрo(i, j)=T р(i) + t(i, j) -поздний срок окончания работы: Tпo(i, j)=T п(j) - полный резерв: Rп (ij)=Tп(j) - Tр(i) - t(i, j); показывает максимальный запас времени, на который можно отсрочить начало или увеличить длительность работ так, чтобы срок завершение проекта в целом, не нарушился. -частный резерв: Rч (ij)=Tп(j) - Tп(i) - t(i, j); показывает часть полного резерва, на которую можно увеличить продолжительность работы, не изменив позднего срока её начального события. -свободный резерв: Rс (ij)=Tр(j) - Tр(i) - t(i, j); показывает максимальное время, на которое можно увеличить продолжительность работы или отсрочить её начало, не меняя ранних сроков начала последующих работ. -независимый резерв: Rн (ij)=Tр(j) - Tп(i) - t(i, j); показывает запас времени, при котором все предшествующие работы заканчиваются в поздние сроки, а все последующие начинаются в ранние.Линейная математическая модель поставленной задачи. Она содержит ml неизвестных (управляющих переменных) и п+тограничений, не считая условий неотрицательности переменных Xjk. После расчета модели определяется количество материала каждого вида, раскраиваемого различными способами. Вместо критерия минимизации себестоимости в задаче может бытьвзят, например, критерий минимизации отходов. В этом случае в условии должно быть задано количество отходов, получаемых при каждом способе раскроя для единицы материала каждого вида.
![]() |