Составление оптимального годового плана ремонтов энергообъединения - сложная и трудоемкая задача. Под оптимальным следует понимать такой ремонтный план, который при принятой в энергообъединении организации ремонтного обслуживания электростанций (заданном составе и размещении ремонтных подразделений, т.е. неизменных капиталовложениях в ремонтную базу) может обеспечивать выполнение заданного графика нагрузки потребителей с надежностью не ниже нормативной и проведение планового объема ремонтных работ с минимальными затратами в энергообъединении (включая топливный и мощностный эффекты). При составлении ремонтного плана (при том или ином распределении во времени ремонта оборудования) должны учитываться многочисленные и противоречивые требования, влияние графика ремонта на годовой баланс рабочей силы ремонтных предприятий, расход топлива и баланс мощности в энергообъединении. Эта задача может быть успешно решена на основе принятых в стране методических положений с учетом особенностей энергоремонтного производства и современных средств вычислительной техники. Проведение ремонтных работ представляет собой комплекс взаимосвязанных мероприятий. Одним из основных методов планирования и управления ремонтными работами на производстве являются системы сетевого планирования и управления (СПУ). Они предназначены для управления деятельностью коллективов людей в целях достижения определенного конечного результата и используются в таких областях, как научные исследования, проектирование новой техники, подготовка и освоение производства новых видов изделий, материально-техническое снабжение, строительство и монтаж новых, равно как и реконструкция и ремонт действующих производственных объектов. Их применение особенно эффективно в тех случаях, когда достижение поставленной задачи требует согласованных (координированных) во времени действий многих участников комплекса работ, охвата большого числа разнообразных работ и взаимосвязей их исполнителей, а также учета степени воздействия каждого из них на конечный результат. Эти методы основываются на использовании сетевого графика в качестве модели процесса, который планируется и затем контролируется по ходу выполнения.
Сетевая модель - это графическое изображение комплекса взаимосвязанных работ, выполняемых в определённой последовательности. График состоит из элементов --- работ и событий (обозначаемых обычно стрелками и кружками).
События не имеют продолжительности во времени. Они отмечают факт окончания одной или нескольких работ, определяющий возможность начала последующих работ (например, агрегат остановлен, замена поверхностей нагрева экономайзера завершена). По роли в сетевом графике различают исходное (начальное) событие --- оно отмечает условие начала разработки, ему не предшествует ни одна работа рассматриваемого комплекса (например, решение о разработке изделия принято); завершающее (конечное), после которого не проводится ни одна работа, входящая в рассматриваемый комплекс, оно отмечает факт достижения конечной цели (например, испытания опытного образца завершены); промежуточные события, фиксирующие окончание предшествующих и начало последующих работ.
Сеть, имеющая одно завершающее событие, называется одноцелевой. По количеству входящих работ различают события простые и сложные; сложное имеет две и более входящие и (или) выходящие работы и считается свершившимся, если окончены все работы, входящие в него. События, изображаемые кружком (иногда эллипсом, квадратом и т. п.), получают в графике номер, или шифр. Исходное событие имеет нулевой номер, а все последующие события нумеруются в возрастающем порядке по мере перехода от предшествующих событий к последующим.
Работы - это отдельные процессы (операции) комплекса, выполнение которых связано с затратами времени, труда, ресурсов (средств). Работа в сетевом графике изображается стрелкой. По характеру потребления времени и ресурсов в сетевых графиках рассматриваются три вида работ - работы как таковые, т.е. потребляющие и время, и труд, и материальные средства, затем ожидание и фиктивные работы, или зависимости.
Ожидание - это процесс, требующий по технологическим или организационным причинам только затрат времени, но не труда или материальных ресурсов. Ожидание изображается сплошной стрелкой, как и собственно работа (твердение бетона, высыхание краски и др.). Фиктивная работа (логическая связь, зависимость) служит только для обозначения логических связей между окончанием одних работ и началом других. Зависимость изображается на графике штриховой стрелкой (рис. 10.3).
Каждая работа имеет одно начальное и одно конечное событие, вследствие чего она определяется в сетевом графике однозначно, с помощью кода, образуемого из номеров событий. Код работы состоит из номера предшествующего события работы и номера последующего события. Принято обозначать рассматриваемое событие через i, последующие через j, k, а предшествующие --- h (рис. 10.4). B соответствии с этим работы обозначаются h --- i ; i --- j; j --- k, а их продолжительности---t(h---i);t(i---j);t(j---h). При составлении сетевых графиков, чтобы избежать ошибок, следует соблюдать определенные правила. Например, если работы A, B, C выполняются последовательно, то на графике это изображается в виде последовательной цепочки работ и событий (рис. 10.5, а), если для выполнения работ B и C необходим результат одной и той же работы A, то на сетевом графике это изображается, как показано на рис. 10.5, б, если работе C должны предшествовать работы A и B, то на сетевом графике это изображается, как показано на рис. 10.5, в, в случае, когда работе B должна предшествовать только часть работы A, последняя разбивается на две работы A1 и A2 (рис. 10.5, г). Не должно быть событий (рис. 10.5, д), за исключением исходного, в которые не входит ни одна стрелка (событие 5), а также событий, за исключением завершающего, из которых не выходит ни одной стрелки (событие 4), не должно быть замкнутых контуров, т.е. путей, соединяющих некоторое событие с ним же самим (контур 2---3---6 на рис. 10.5, д).
Непрерывная последовательность взаимосвязанных работ в сетевом графике образует путь. Так как на выполнение отдельных работ требуются затраты времени, то пути в сетевом графике имеют определённую продолжительность, равную сумме продолжительностей работ, образующих данный путь. Последовательность взаимосвязанных работ от начального до конечного события называется полным путем. Полный путь наибольшей продолжительности называется критическим и обозначается Lкр. Продолжительность критического пути обозначается tкр (на графике принято выделять критический путь жирной линией). Критический путь определяет общую продолжительность выполнения комплекса работ или наиболее ранний возможный срок его выполнения. Пути, по продолжительности мало отличающиеся от критического, называются подкритическими. Все остальные полные пути сетевого графика называются ненапряженными.
Все пути, кроме критического, имеют определенные резервы времени. В связи с этим появляется возможность передать часть ресурсов с работ, лежащих на ненапряженных путях, на работы критического пути, сократив таким образом его продолжительность и ускорив окончание рассматриваемого комплекса работ. Разность между продолжительностью критического пути tкри продолжительностью tL полного пути L называется резервом времени полного пути L и обозначается через RL:
RL= tкр - tL.
Степень напряженности того или иного полного пути в сетевом графике характеризует коэффициент напряженности:
kн(L)=(tL- tкр(L))/(tкр---tкр(L)),
где tL --- продолжительность исследуемого пути, для которого определяется степень напряженности; tкр ( L) --- продолжительность критических работ, по которым частично проходит рассматриваемый путь; tкр --- продолжительность критического пути. Так как tL<tкр, то kн(L)<1, и, чем больше kн(L), тем большего внимания требуют работы, лежащие на этом пути. Сетевые графики выполняются без масштаба. Оценка продолжительности работы t проставляется над стрелкой в принятых единицах времени (час, смена и т.п.). В зависимости от характера комплекса работ (проектирование сложного объекта, ремонт агрегата и т.п.) используемые в сетевом графике оценки времени могут быть детерминированными (определенными, нормативными) или вероятностными; в первом случае сетевая модель называется детерминированной, во втором --- стохастической (изображающей вероятностные процессы). При наличии нормативной базы оценка времени t, сут, определяется, исходя из объема работы, нормы времени на единицу работы, количества исполнителей (рабочих) в смену и числа рабочих смен (в сутки) по формуле t=F(1+P)/(nр*m*f*nн), где F --- трудоемкость данной работы в днях; Р --- доля дополнительных работ, предполагаемых к выполнению данной группой работников попутно с работой, вошедшей в сетевой график; nр --- количество работников, участвующих в данной работе; m --- количество часов в рабочем дне; f --- коэффициент перевода рабочих дней в календарные с учетом отпусков работников (f = 0,66); nн --- коэффициент выполнения норм (1,1...1,3).
В стохастических сетях вероятностная оценка времени принимается методом усреднения на основе экспертных оценок специалистов, обладающих достаточным опытом выполнения соответствующих работ. При этом по каждой данной операции в качестве исходных принимаются следующие три значения: оптимистическое, т.е. минимально возможная продолжительность выполнения данной операции tmin (при самых благоприятных условиях); наиболее вероятное, т.е. такое, которое было бы дано, если бы требовалось только одно значение tв; пессимистическое, т.е. максимально возможная продолжительность выполнения работы tmax (при самых неблагоприятных условиях). По этим трем значениям определяется статистическое среднее значение --- ожидаемое время to, которое является средней (ожидаемой) продолжительностью выполнения данной операции в случае ее многократного повторения:
to = (tmin + 4tв + tmax)/6,
где tmin, tв, tmax, --- оптимистическая, наиболее вероятная и пессимистическая оценки времени. Очевидно, что чем шире отстоят друг от друга предельные, т.е. оптимистическая и пессимистическая оценки (чем больше размах распределения), тем больше неопределенность, связанная с оценкой времени по данной операции, вызываемая недостаточностью опыта (исходной информации).
Для определения ожидаемого продолжения времени выполнения работы применяется также и другой вариант расчета, основанный на использовании двух вероятностных оценок: максимальной tmax и минимальной tmin:
to = (3tmin + 2tmax)/5.
В детерминированных сетях, составляемых для комплексов работ, имеющих нормативную базу, неопределенность в оценке времени устранена. Время выполнения работы определяется ее трудоемкостью и количеством исполнителей. Например, для составления сетевого графика ремонта агрегата используются данные по объему работ, технологии их проведения, нормы продолжительности выполнения отдельных операций, сроки останова агрегата на ремонт и сдачи его в эксплуатацию после ремонта, сведения о ресурсах рабочей силы. На основании данных составляется таблица работ и ресурсов, называемая карточкой-определителем работ, в которой указываются продолжительность работ, нормативная продолжительность, трудоемкость, количество работающих.
Содержание работ и событий зависит от принятой детализации комплекса по операциям. Составление перечня работ является одним из наиболее ответственных этапов в сетевом планировании. По этим данным составляется исходный сетевой график. После его построения события шифруются таким образом, чтобы для каждой работы конечное событие имело номер больший, чем начальное. После определения оценок времени по каждой работе производится расчет сети. Каждая работа обычно требует затрат времени, труда, материалов, денежных средств. Поэтому сетевой график должен отражать сроки выполнения отдельных работ и всего комплекса, необходимые ресурсы рабочей силы и возможности маневрирования ею, затраты средств и др.
Расчет сети по времени заключается в определении следующих данных: ожидаемого срока окончания всего комплекса работ (т.е. нахождения величины критического пути), наиболее ранних возможных и наиболее поздних допустимых сроков начала и окончания работ, резервов времени. Этот расчет позволяет выявить работы критической зоны (критического и подкритических путей) и сосредоточить на них внимание. Для расчета на графике каждый кружок, изображающий событие, делится на четыре сектора. В верхнем секторе проставляется номер данного события i, в левом и правом --- соответственно ранний tip и поздний tiп сроки свершения данного события, а в нижнем секторе резерв события Rс (рис. 10.6). Расчет сети начинается с определения ранних возможных сроков свершения событий tip. При этом срок свершения начального события принимается за нуль (t0p = 0). Сроки свершения последующих событий рассчитываются после определения раннего срока свершения предшествующих событий thp путем прибавления продолжительности соответствующих работ.
сложным событиям ведут несколько путей (рис. 10.7). Ранний срок свершения такого события определяется самым продолжительным из них, т. е.
tip=max[thp+th--i],
где tip --- ранний срок свершения событий i; thp --- ранний срок свершения предшествующего события h; th -- i --- продолжительность работы (h -- i). На сетевом графике, изображенном на рис. 10.7, сложным является, например, событие 2. Ему предшествуют события нулевое и событие 1. Ранний срок свершения нулевого события t0p = 0, а ранний срок свершения события 1.
Соответственно этому в нижнем секторе кружка, обозначающего событие 2, указано событие 1, от которого велся отсчет и было получено значение t2p = 5 (оно записано в левом секторе кружка события 2.
Аналогично подсчитываются ранние сроки свершения всех остальных событий. В результате такого расчета определяется ранний возможный срок свершения конечного события, т.е. тем самым определяется продолжительность критического пути tкр, которая характеризует наиболее
ранний возможный срок окончания комплекса работ по данному графику. На рис. 10.7 критический путь обозначен жирной линией. Поскольку критическим является полный путь максимальной продолжительности, его обозначают (после расчета ранних сроков свершения событий), следуя указаниям в нижних секторах, от завершающего события к исходному. Другим параметром времени сетевого графика являются наиболее поздние допустимые сроки свершения событий tiп, при которых весь комплекс работ по данному графику может быть завершен за время tкр.
Сетевые графики, для которых продолжительность критического пути равна директивной (заданной) длительности tд выполнения всего комплекса работ, называются приведенными. В неприведенных графиках tкр < tд или tкр > tд. Если tкр < tд, то критический путь имеет резерв времени. Если tкр > tд, то график подлежит переработке («сжатию»), так как планирование выполнения комплекса работ в срок, превышающий директивный, недопустимо. В приведенных графиках tкр = tд время tкр является наиболее ранним и вместе с тем наиболее поздним сроком окончания всего комплекса работ по данному графику. Поэтому поздние сроки в отличие от ранних рассчитываются справа налево от завершающего события, срок свершения которого tкр уже определен. Для событий критического пути поздние сроки совпадают с ранними сроками их свершения, они не имеют резерва времени событий. События же, лежащие на некритических путях, могут свершаться в поздние сроки tiп > tip, т.е. некритические события имеют резерв времени события. Они могут свершиться в пределах отрезка времени tiп -- tip (при этом конечный срок выполнения всего комплекса работ остается неизменным, а в зависимости от срока свершения события в указанных пределах последующие работы будут выполняться более или менее напряженно. Поздний срок свершения события
tiп =min[tjп -ti-j],
где tjп --- поздний срок свершения последующего события j; ti - j --- продолжительность работы (i -- j). Для сетевого графика на рис. 10.7 имеем:
Определившиеся значения tjп записываются в правых секторах кружков, обозначающих события. Для каждого события разность Δ t = tjп -- tiр характеризует резерв времени события; для критических событий Δ t = 0. Далее могут быть определены параметры работ --- сроки начала и окончания и резервы времени (табл. 10.1). Поскольку каждое событие является моментом окончания всех предшествующих работ и открывает возможность начать последующие работы, то очевидно, что ранний срок свершения данного события является одновременно и наиболее ранним возможным сроком начала (так называемым ранним началом) tiр-- jн всех работ, выходящих из этого события.
Аналогично поздний срок свершения события tjп является наиболее поздним допустимым сроком окончания (так называемым поздним окончанием) thп - iо всех работ, входящих в него. Tаким образом, на сетевом графике при четырехсекторном методе расчета всегда указаны раннее начало и позднее окончание всех работ. В сетевом планировании различают полный Ri -- j и частный ri -- j резервы времени работ. Полный резерв времени работы --- это разность между поздним и ранним сроками начала (или окончания) работы. Это тот запас времени, который может быть использован на данной работе (путем перенесения срока начала или увеличения продолжительности работы) без ущерба для конечного срока всего комплекса, но при использовании которого последующие работы выполняются в свои поздние допустимые сроки, т.е. лишаются резерва времени. Частный резерв времени работы ri -- j, называемый иногда свободным сдвигом, возникает в случае сложных событий, т.е. когда срок свершения события определяется окончанием самого продолжительного из путей. Работы, входящие в то же событие, но лежащие на менее продолжительных путях, оканчиваются раньше, чем свершается их конечное событие. Вследствие этого их окончание не влияет на начало последующих работ. Такие работы могут быть сдвинуты во времени к моменту начала последующих работ, и эта передвижка никак не отразится на сроках выполнения последних. Величина возможного сдвига будет представлять собой частный резерв времени работы. При этом последующие работы могут выполняться в свои наиболее ранние сроки и не лишаются резерва времени. После расчета исходного сетевого графика начинается очень важный этап его улучшения (оптимизации) и приведения параметров в соответствие с заданными условиями и ограничениями (по срокам выполнения комплекса работ, ресурсам). Если критический путь превышает заданную (директивную) продолжительность комплекса работ, изыскивают возможности его сокращения. Этого можно достигнуть следующими путями: заменой последовательного выполнения работ параллельным (там, где это возможно по условиям технологии); перераспределением ресурсов между работами (передача рабочей силы, материалов, механизмов с работ ненапряженных путей на работы критической зоны с использованием дополнительных ресурсов и соответствующим сокращением времени на выполнение работ).
Для оптимизации сети по трудовым ресурсам строится линейная (ленточная) диаграмма, на которой работы в масштабе времени изображаются отрезками прямых, параллельных оси абсцисс. Начало каждого отрезка должно совпадать с ранним началом соответствующей работы (по расчету). Указываются коды работы (в начале и конце отрезка) и число исполнителей (над ним). Наносятся работы, лежащие на критическом пути, и другие работы в соответствии с технологической последовательностью их выполнения.
Далее строится график движения рабочей силы - эпюра ресурсов. Сравнивается по календарным периодам число исполнителей по графику и имеющееся в наличии. При необходимости производят сдвиг вправо тех работ, которые имеют наибольший резерв времени (в первую очередь тех, которые имеют меньший коэффициент напряженности). Таким образом, сдвигом работ в пределах резервов времени достигаются желаемое выравнивание графика движения рабочей силы и оптимизация использования трудовых ресурсов.
Они позволяют анализировать сетевую модель с точки зрения равномерности использования рабочей силы и ее соответствия имеющейся численности работающих. Такие графики широко используются, например, для оптимального планирования ремонтного обслуживания электростанций.
Оптимизация сетевого графика по времени предполагает одновременное перераспределение необходимых средств, т.е. одновременно с изменением оценок времени могут быть изменены и выделяемые на эту работу ресурсы. Поэтому при оценке эффективности путей улучшения составленного плана работ необходимо дополнительно к оценкам сроков учитывать влияние фактора стоимости. Для этих целей пользуются методом «время --- затраты», графически представленным на рис. 10.11, на котором для каждой работы указываются минимально возможные затраты денежных средств Зм при выполнении работы за нормальное время Tн и минимально возможное время выполнения работы Tм при повышенных затратах средств Зп.
С помощью аппроксимирующей прямой, соединяющей указанные характерные точки метода «время --- затраты», можно определять приближенную величину дополнительных затрат ΔЗ, необходимых для выполнения работы за более короткое время Тк по сравнению с временем Tн, руб.:ΔЗ = [(Зп -- Зм) (Тн -- Tк)]/( Тн -- Tм). При этом коэффициент возрастания затрат на единицу времени, руб/ед. времени, составляет з=(Зп --Зм)/(Тн --Tм).
Подсчитывая для каждого варианта (этапа) улучшения сетевого графика параметры времени и стоимости выполнения всего комплекса работ, можно получить зависимость между ними и использовать ее для принятия решения.
Взаимосвязь между временем и стоимостью имеет определенные границы. Нельзя, например, увеличивая продолжительность работы, добиться снижения затрат до нуля, и наоборот. Оптимизация проводится в пределах нормальных и предельных сроков и затрат методом последовательного приближения, в первую очередь путем сокращения продолжительности критических работ, имеющих наименьший коэффициент возрастания затрат. Задача заключается в достижении минимума затрат на выполнение комплекса работ в заданное время. Сетевыми графиками пользуются для оперативного управления выполнением работ. В определенные моменты времени отмечается состояние работ и сопоставляется продолжительность путей по невыполненным работам с остающимся временем на выполнение всего комплекса. На основе анализа этих данных при необходимости принимаются меры к ликвидации отставания.
В зависимости от масштаба комплекса работ различают системы СПУ большими разработками (с числом событий в сети более 10 тыс.), средними (от 1,5 до 10 тыс. событий) и малыми (до 1,5 тыс. событий). При небольшом числе событий с успехом могут применяться простейшие модели типа ленточных или цикловых графиков. В системах СПУ реализуется системный подход к решению вопросов управления, так как деятельность всех коллективов исполнителей рассматривается во взаимосвязи. Эти коллективы (независимо от ведомственной принадлежности) рассматриваются как звенья единой организационной системы, планирование параметров сети и оценка результатов производятся исходя из их роли в достижении конечной цели всего комплекса операций. Системы СПУ можно классифицировать по следующим признакам: важности и объему разработки; числу сетей, отображающих разработку; объему сетевой модели; количеству целей сетевой модели; контролируемым параметрам; ресурсным ограничениям. По количеству сетей, описывающих объект управления, различают односетевую модель и многосетевую; во втором случае совокупность работ описывается несколькими отдельными сетями, в которых взаимно увязаны сроки выполнения и другие показатели работ, принадлежащих разным сетям. По числу конечных целей различают модели одноцелевые и многоцелевые (в последнем случае сеть завершается несколькими событиями соответственно получаемым конечным результатам).
Наиболее разработанной и широко применяемой можно считать систему СПУ, с помощью которой производится оптимизация комплекса работ по времени достижения одной конечной цели. Сетевые графики являются активным средством планирования и управления производством, так как объем выходной информации, получаемой в результате расчета сетевого графика, значительно превышает объем исходной информации.
Алгоритм 2 (последовательный алгоритм компоновки)
Пусть задан граф G=(E,U) и подмножество запрещенных элементов QÍE, |Q|=q. Требуется найти такое разбиение P(G) графа G на m одинаковых кусков G1,G2,…,Gm, чтобы суммарное число соединяющих ребер было минимальным.
Рассмотрим последовательный алгоритм разбиения графа, приводящий к минимуму числа соединительных ребер за конечное число шагов при наличии ограничений.
Основная идея метода заключается в следующем. Сначала по кускам графа распределяются запрещенные вершины. Формирование первого куска начинается с вершины eεÎQ, которую априорно считаем входящей во множество вершин E1 первого куска G1=(E1,U1).
Составление кусков будем вести по уровням. Вершина eε в куске G1 образует первый уровень и на этом уровне E1={eε}.
Для определения вершин второго уровня, т.е. второй вершины, которую необходимо поместить в G1, строится множество вершин, смежных eε.
Обозначим множество, содержащее вершину eε, смежные ей вершины, и не содержащее других запрещенных вершин через Гeε.
Введем понятие относительного веса d(еi) для любой вершины еi графа G:
d(еi)=r(ei)-Srik, k=1,m
(4.1)
где Srik, k=1,m - число ребер, соединяющих вершину ei с вершинами сформированного подмножества E1, m=|E1|.
Из приведенного выражения (4.1) следует, что для получения требуемого куска из множества Гeε необходимо выбрать вершину с минимальной величиной d(еi*) (чем больше связей у вершины из Гeε с вершинами из G1, тем меньше разность в (4.1) и тем меньше величина d(еi))
d(еi*) = min d(еi), eiÎГeε
(4.2)
где iÎI=(1,2,…,t), t=|Гeε|
Вершина еi* является вершиной второго уровня. На втором уровне E1={eε,ei*}.
Далее рассматривается множество ГeεUГei*, и для каждой вершины еkÎГeεUГei*, определяется относительный вес по (4.1). Выбрав вершину еk* с минимальным весом, получим E1={eε,ei*,еk*}.
Указанный процесс продолжается до тех пор, пока множество вершин E1 не будет содержать n1 вершин. Полученный кусок G1 удаляется из графа G. Последующие куски формируются аналогично.
Если при формировании куска G1 графа G несколько рассматриваемых вершин имеют одинаковый относительный вес, то в кусок G помещается вершина, имеющая большую локальную степень. Покажем это.
Пусть для вершин ei,еjÎE графа G=(E,U) локальные степени r(ei)>r(ej). В рассматриваемом случае d(еi)=d(еj) , а по определению
d(еi) = r(ei) - Srik,
d(еj) = r(ej) - Srjk, k=1,m, т.е.
r(ei) - Srik=r(ej) - Srjk
(4.3)
r(ei) -r(ej) =Srik - Srjk
Т.к. r(ei)>r(ej), то
Srik>Srjk, k=1,m
(4.4)
Обозначим число внешних соединительных ребер куска Gi до внесения в него вершин еi и ej через zi. Тогда при внесении в кусок Gi вершины ei число внешних ребер станет
d*(еi)= zi-Srik+(r(ei)- Srik)= d(еi)+ zi-Srik
(4.5)
новое + старое число ребер
zi-Srik: zi – было внешних выводов в Gi; Srik – соединились с новым элементом и стали внутренними;r(ei)- Srik: r(ei)-было у ei внешних выводов; Srik – стали внутренними
А при внесении ej число внешних ребер станет
d*(еj)= zi-Srjk+(r(ej)- Srjk)=d(еj)+ zi-Srjk
(4.6)
Учитывая выражение (4.4), из (4.6) следует
Вычитая из (4.5) выражение (4.6) и учитывая (4.4), получаем:
т.е. при внесении вершины ei число внешних соединительных ребер уменьшилось.
ПРИМЕР
Дан сформированный кусок графа G Gi (рис. 4.1). Рассматриваются для внесения в него вершины еi и ej, расположение которых приведено на рис. 4.2. Число внешних соединительных ребер куска Gi до внесения в него вершин еi и ej zi=6.
4.При внесении ei число внешних соединительных ребер будет равным d*(еi)= zi-Srik+(r(ei)- Srik)=6-4+7-4=5;
5.При внесении ej число внешних соединительных ребер будет равным d*(еj)= zi-Srjk+(r(ej)- Srjk)=6-2+5-2=7, т.е. при внесении еi число внешних соединительных ребер меньше, чем при внесении ej, а по условию r(ei)> r(ej) что и требовалось показать.
Пример алгоритма 2
Дан граф G=(E,U), изображенный на рис. 4.3, матрица смежности которого имеет вид:
R =
e1
e2
e3
e4
e5
e6
e7
e8
e9
e10
e11
e12
e1
r(e1)=7
e2
r(e2)=8
e3
r(e3)=8
e4
r(e4)=8
e5
r(e5)=8
e6
r(e6)=5
e7
r(e7)=11
e8
r(e8)=4
e9
r(e9)=3
e10
r(e10)=11
e11
r(e11)=5
e12
r(e12)=8
Граф G необходимо разбить на три куска по четыре вершины в каждом. Множество запрещенных вершин Q={e1,e5,e10}.
Построим первый кусок G1.
Выбираем вершину e1 (можно e5 или e10) и записываем E1={e1}. Далее рассматриваем множество. Гe1={e1,e2,e3,e9} (вершин, смежных с e1). Вершина e10 в Гe1 не включается т.к. она является запрещенной.
По формуле (4.1) определяем относительные веса вершин из Гe1, кроме вершины e1, уже вошедшей в E1:
d(е2) = r(e2) - Sr2k=8 – 1 = 7 (k=1,|E1|)
d(е3) = r(e3) - Sr3k=8 – 4 = 4 (k=1,|E1|)
d(е9) = r(e9) - Sr9k=3 – 1 = 2 (k=1,|E1|)
Включаем вершину е9, имеющую min d(е9), в кусок G1=(E1,U), и получаем E1={e1,e9}.
Строим теперь множество вершин, смежных множеству вершин E1. Это множество Гe1ÈГe9={e1,e2,e3,e9}. Определяем относительные веса e3 и e2.
d(е3) = r(e3) - Sr3k=8 – (4+1) = 3 (k=1, 2=|E1|)
(где Sr3k, k=1,2 - число ребер, соединяющих вершину e3 с вершинами подмножества E1={e1,e9}).
d(е2) = r(e2) - Sr2k=8-(1+1) = 6 (k=1, 2=|E1|)
В кусок G1 помещаем вершину e3 т.к. она имеет наименьший относительный вес, тогда E1={e1e9,e3}.
Составляем множество Гe1ÈГe9ÈГe3= (e1,e2,e3,e9,е6) (вершин, смежных с e1,e3,e9) и находим
d(е2) = r(e2) - Sr2k=8-(1+1+0) = 6 (k=1, 3=|E1|)
(где Sr3k, k=1,3 - число ребер, соединяющих вершину e2 с вершинами подмножества E1={e1e9,e3}).
d(е6) = r(e6) - Sr6k=5-(0+0+1) = 4 (k=1, 3=|E1|)
(где Sr3k, k=1,3 - число ребер, соединяющих вершину e6 с вершинами подмножества E1={e1e9,e3}).
Включив вершину е6 в кусок G1, получим
E1={e1e9,e3,е6}.
Таким образом, кусок G1 сформирован. Удаляем его из графа G и получаем новый граф G’= G\G1. Его матрица получится, если из R вычеркнуть строки и столбцы, соответствующие e1e9,e3,е6:
R =
e2
e4
e5
e7
e8
e10
e11
e12
e2
r(e2)=5
e4
r(e4)=8
e5
r(e5)=8
e7
r(e7)=11
e8
r(e8)=4
e10
r(e10)=8
e11
r(e11)=5
e12
r(e12)=5
Сформируем теперь кусок G2. Берем запрещенную вершину е5 (можно и е10), тогда E2={e5}. Строим множество вершин, смежных e5: Гe5={e5,e2,e4,e7,e8}.
Рис. 4.1
Рис. 4.2
