Norenkov.Osnovy.Avtomatizirovannogo.Proektirovania.2002 (525024), страница 42
Текст из файла (страница 42)
Математическое обеспечение синтеза проектных решенийПланирование процессов и распределение ресурсовВ отдельную группу задач структурного синтеза выделяют планированиепроцессов и распределение ресурсов. В нее входят синтез технологическихпроцессов в различных отраслях промышленности, проектирование вычислительных процессов для многопроцессорных систем и сетей, синтез логистических процессов (например, планирование перевозок грузов при наличии множества заказов и ограниченном числе транспортных средств), а такжепланирование работ при управлении проектами. Эти задачи объединяет общность ряда свойств и подходов к решению, как задач синтеза расписаний.Базовым понятием в синтезе расписаний является понятие работы — элементарной планируемой части процесса. Нужно составить план выполненияработ, в котором фиксируются объемы работ, распределение ресурсов всехвидов, моменты (даты) начала и окончания каждой работы, называемые событиями (или вехами), стоимости работ.
Ресурсы — обеспечивающие компоненты деятельности, включающие исполнителей, энергию, материалы, оборудование и т. д.С каждой работой можно связать функцию потребности в ресурсах. Различают ресурсы унарные и объемные. Единица унарного ресурса, называемаядалее сервером, может одновременно выполнять не более одной работы, и покаждому виду ресурса на работу может быть назначен не более чем одинсервер.
Примерами унарных ресурсов могут быть токарный станок, процессорЭВМ, водитель автомашины. Значение объемного ресурса (энергии, финансов,пропускной способности канала), назначаемое для конкретной работы, можетбыть выбрано в некотором диапазоне и от выбранного значения зависят длительность и (или) стоимость выполнения работы.Результаты синтеза обычно представляют в виде таблиц и диаграмм. PERTдиаграмма (сеть типа «вершина - событие») — ориентированный граф без контуров, имеющий одну исходную и одну завершающую вершины, в котором вершины поставлены в соответствие событиям, а дуги — работам.
ДиаграммаГанга (Gantt diagram) — горизонтальная линейная диаграмма, на которой задачи проекта представляются протяженными во времени отрезками, распределенными между серверами и характеризующимися датами начала и окончания, задержками и, возможно, другими временными параметрами.Для задач планирования процессов и управления проектами характерны следующие особенности:1) широкий диапазон размеров задач, причем верхняя граница диапазонаможет достигать значений в десятки тысяч и более работ;2) многокритериальность, основные критерии — время и стоимость выполнения плана, в качестве целевой функции часто выбирают стоимость, в числоограничений включают времена окончания работ и, возможно, ряд условий использования ресурсов;3) разнообразие типов управляемых переменных, среди которых могут бытьвеличины действительные, целые, нечисловые.Указанные особенности обусловливают сложность решения задач синтезарасписаний, являющихся задачами дискретной оптимизации.1784 4 Методы структурного синтеза в системах автоматизированного проектирования4.4.
Методы структурного синтеза всистемах автоматизированного проектированияМетод ветвей и границВыбор метода поиска решения - вторая проблема после формализации задачи. Если при формализации все управляемые параметры удалось представить в числовом виде, то можно попытаться применить известные методыДМП.Задача ДМП определяется следующим образом:extr F(\),XeD(4.30)D = { X | W(X) >0, Z(X) = 0 },где -F(X) — целевая функция; W(X), Z (X) — вектор-функции, связанные с представленными в ТЗ требованиями и ограничениями; D — дискретное множество. В полученной модели, во-первых, каждый элемент множества рассматриваемых законченных структур должен иметь уникальное сочетание значенийнекоторого множества числовых параметров, вектор которых обозначим X.Во-вторых, необходимо существование одной или нескольких функций Ф(Х),значения которых могут служить исчерпывающей оценкой соответствия структуры предъявляемым требованиям.
В-третьих, функции Ф(Х) должны отражать внутренне присущие данному классу объектов свойства, что обеспечитвозможность использования Ф(Х) в качестве не только средств оценки достигнутого при поиске успеха, но и средств указания перспективных направлений продолжения поиска. Эти условия выполнимы далеко не всегда, что и обусловливает трудности формализации задач структурного синтеза.Однако наличие формулировки (4.30) еще не означает, что удастся подобрать метод (алгоритм) решения задачи (4.30) с приемлемыми затратами вычислительных ресурсов.
Другими словами, применение точных методов математического программирования вызывает непреодолимые трудности в большинстве случаев практических задач типичного размера из-за их принадлежности к классу NP-трудных задач. Поэтому лидирующее положение средиметодов решения задачи (4.30) занимают приближенные методы, в частностидекомпозиционные методы, отражающие принципы блочно-иерархическогопроектирования сложных объектов. Декомпозиционные методы основаны навыделении ряда иерархических уровней, на каждом из которых решаются задачи приемлемого размера.Основу большой группы математических методов, выражающих стремление к сокращению перебора, составляют операции разделения множества вариантов на подмножества и отсечения неперспективных подмножеств. Этиметоды объединяются под названием метода ветвей и границ.
Основнаяразновидность метода ветвей и границ относится к точным методам решениякомбинаторных задач. Рассмотрим эту разновидность.1794. Математическое обеспечение синтеза проектных решенийПусть имеется множество решений М, в котором нужно выбрать оптимальный по критерию F(X ) вариант, где X — вектор параметров варианта т е М;пусть также имеется алгоритм для вычисления нижней границы ДМ4) критерия F(X'.) в любом подмножестве М^ множества М, т. е.
такого значения i(Mt),что F(X) > L(Mk) при любому (подразумевается минимизация F(X)). Тогдаосновная схема решения задач в соответствии с методом ветвей и границ содержит следующие процедуры: 1) в качестве М^ принимаем все множество М;2) ветвление: разбиение МА на несколько подмножеств М ; 3) вычислениенижних границ ЦМГ) в подмножествах М?; 4) выбор в качестве Mt подмножества М с минимальным значением нижней границы критерия (среди всехподмножеств, имеющихся на данном этапе вычислений), сведения об остальных подмножествах М? и их нижних границах сохраняются в отдельном списке; 5) если | MJ > 1, то переход к процедуре 2, иначе одноэлементное множество М^есть решение.Метод ветвей и границ в случае точного вычисления нижних границ относится к точным методам решения задач выбора и потому в неблагоприятныхситуациях может приводить к экспоненциальной временной сложности.
Однако метод часто используют как приближенный, поскольку можно применятьприближенные алгоритмы вычисления нижних границ.Среди других приближенных методов решения задачи ДМП отметим метод локальной оптимизации. Так как пространство D метризовано, то можно использовать понятие я-окрестности 8о(Х4) текущей точки поиска \k. Вместо перебора точек во всем пространстве D осуществляется перебор точектолько в So(Xt). Если F(X) > F(X.k) для всех X е 8я(Х4), то считается, чтонайден локальный минимум целевой функции в точке Хг В противном случаеточку X , в которой достигается минимум F(X) в Sa(Xt), принимают в качественовой текущей точки поиска.Элементы теории сложностиВ теории сложности выделяют массовые и индивидуальные задачи. Первые из них сформулированы в общем виде, вторые представлены с конкретными числовыми значениями исходных данных.
Исследования сложности проводятся в отношении массовых задач, и получаемые выводы, как правило,относятся к наихудшему случаю — к наиболее неблагоприятному возможномусочетанию исходных данных.Цель исследований — установление вида зависимости объема Q требуемых вычислений от размера задачи N. Объем вычислений может определяться числом арифметических и логических операций или затратами процессорного времени ЭВМ с заданной производительностью. Размер задачи в общемслучае связывают с объемом описания задачи, но в приложениях понятие размера легко наполняется более конкретным содержанием.Далее, в теории сложности задач выбора вводят понятия эффективных инеэффективных алгоритмов.
К эффективным относят алгоритмы с полино-1804.4. Методы структурного синтеза в системах автоматизированного проектированияТ а б л и ц а 4.1Q(N)Б,Б 2 =100Б,53=10006,NNI100 NIЮООЛГ,2N210 N231,6 N2N3N34,647/э10 N32"N46,64 + Я,9,97 + N4Nмиальной зависимостью Q onN, например, алгоритмы с функцией Q (N) линейной, квадратичной, кубической и др. Для неэффективных алгоритмов характерна экспоненциальная зависимость Q (N).Важность проведения резкой границы между полиномиальными и экспоненциальными алгоритмами вытекает из сопоставления числовых примеров роста допустимого размера задачи с увеличением быстродействия Б используемых ЭВМ (табл.
4.1, в которой указаны размеры задач, решаемых за одно и тоже время Т на ЭВМ с быстродействием Б; при различных зависимостях сложности Q от размера N). Эти примеры показывают, что выбирая ЭВМ в К разболее быстродействующую, получаем увеличение размера решаемых задачпри линейных алгоритмах в К раз, при квадратичных алгоритмах в К1'2 раз и т. д.Иначе обстоит дело с неэффективными алгоритмами. Так, в случае сложности 2" для одного и того же процессорного времени размер задачи увеличивается только на \gK I Ig2 единиц.
Следовательно, переходя от ЭВМ с Б = 1Гфлопс к суперЭВМ с Б = 1 Тфлопс, можно увеличить размер решаемой задачи только на 10, что совершенно недостаточно для практических задач. Действительно, в таких задачах, как, например, синтез тестов для БИС, число входных двоичных переменных может составлять более 100 и поэтому полныйперебор всех возможных проверяющих кодов потребует выполнения более 2100вариантов моделирования схемы.В теории сложности все комбинаторные задачи разделены на классы:• класс неразрешимых задач, в него входят массовые задачи, решение которых полным перебором принципиально невозможно с точки зрения современных научных представлений; этот класс отделяется от других задач такназываемым пределом Бреммермана, оцениваемым величиной N= 1093; отметим, что реальный предел неразрешимости значительно ниже;• класс Р, к нему относятся задачи, для которых известны алгоритмы решения полиномиальной сложности;• класс NP, включающий задачи, для которых можно за полиномиальноевремя проверить правильность решения, т.
е. ответить на вопрос, удовлетворяет ли данное решение заданным условиям; очевидно, что Р включено в NP, од-1814. Математическое обеспечение синтеза проектных решенийнако вопрос о совпадении этих классов пока остается открытым, хотя, по-видимому, на этот вопрос будет получен отрицательный ответ;• класс NP-полных задач, характеризующийся следующими свойствами:1) для этих задач не известны полиномиальные алгоритмы точного решения;2) любые задачи внутри этого класса могут быть сведены одна к другой заполиномиальное время. Последнее означает, что если будет найден полиномиальный алгоритм для точного решения хотя бы одной NP-полной задачи, то заполиномиальное время можно будет решить любую задачу этого класса.Из результатов теории сложности следуют важные практические рекомендации: 1) приступая к решению некоторой комбинаторной задачи, необходимосначала проверить, не принадлежит ли она к классу NP-полных задач, и еслиэто так, то не следует тратить усилия на разработку алгоритмов и программточного решения; 2) отсутствие эффективных алгоритмов точного решения массовой задачи выбора отнюдь не означает невозможности эффективного решения индивидуальных задач из класса NP-полных или невозможности получения приближенного решения по эвристическим алгоритмам за полиномиальноевремя.Методы локальной оптимизации и поиска с запретамиСреди приближенных методов решения задачи (4.30) часто используемымявляется метод локальной оптимизации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
