Файл: Васильев, В. В. Гибридные модели задач оптимизации.pdf

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

При таком'способе представления задачи коммивояжера в виде унифицированного дерева маршрутов появляется возможность па­ раллельного анализа вариантов. Покажем, что это так.

Из исходного города коммивояжер может следовать в п — 1 го­ род. Так как неизвестно, какой из них он выберет, то рассматрива­ ем параллельно каждый из вариантов. Пусть он следует из перво­ го города во второй, тогда со второго он может следовать в третий, четвертый и т. д. в п-й город. Предположим, что коммивояжер сле­ дует из первого не во второй город, а в третий, тогда с третьего он может следовать во второй, четвертый и т. д. в п-й. Таким образом, рассматриваем одновременно все варианты последующего движе­ ния. В этом и состоит основное отличие предлагаемого метода от существующих, в которых производится последовательный анализ.

Способ построения унифицированного дерева задачи для шести городов показан на рис. 4. Перед построением все города должны быть в произвольном порядке пронумерованы. Удобно строить де­ рево как совокупность кустов, состоящих из ветвлений на каждом уровне. При таком представлении упрощается способ отыскания одинаковых продолжений. Построение дерева начинается из исход­ ного (первого) города, расположенного на первом уровне. В зоне этого уровня строим п — 1 = 5 ветвей, исходящих из первого во второй и т. д. пятый города. Эти ветви являются основой кустов дерева. Условно куст, имеющий в основе ветвь ѵп , пронумеруем первым и т. д., ѵіа — пятым кустом. Концы ветвей 1-й зоны образу­ ют второй уровень, из каждой вершины которого исходит п — 2 = = 4 ветви, т. е. в каждом последующем варианте исключаются го­

ствование различных ветвей в дереве. Концы их образуют третий уровень, с каждой вершины которого исходит п — 3 = 3 ветви. В зоне этого уровня располагается (п — 1) X (п — 2) X (п — 3) = = 5 x 4 x 3 ветвей. Отсюда видно, что на этом и на каждом по­ следующем уровнях начинаются повторения. Вершины, имеющие одинаковые продолжения, объединяются между собой. Закономер­ ность объединения следующая: в зоне третьего уровня объедине­ ния производится между кустами — объединяются ветвления 1-го рода, в зоне четвертого уровня объединения производится между ветвлениями 1-го рода, а затем между кустами; в зоне пятого уров­ ня объединения производится внутри ветвлений 1-го рода, затем между ветвлениями 1-го рода, затем между кустами; в зоне шестого уровня объединения производится внутри ветвлений 2-го рода, за­ тем между ветвлениями 2-го рода, затем между ветвлениями 1-го рода, а затем между кустами. Эту закономерность можно просле­ дить на рис. 4.

Таким образом, задача коммивояжера сведена к задаче о крат­ чайшем пути на расширенном графе с числом ветвей 2 (п — 1) +

20

Уровень I

+ (л — 1) (п — 2) • 2"-3, которое определяет объем памяти, не­ обходимый для решения этой задачи. Был исследован рост коли- 1 чества ветвей для полного и унифицированного деревьев с увеличе­ нием количества городов на единицу. На основании расчетных дан­ ных построены графики рис. 5: а — для унифицированного дерева, б — для полного, где по оси абсцис отложено отношение количества

ветвей дерева для л + 1 городов к количеству ветвей дерева для л го­ родов, а по оси ординат — чему это отношение равно. Видно, что при анализе (л — 1)! вариантов на полном дереве увеличение коли­ чества городов в задаче от л до л + 1 вызывает возрастание количе­ ства ветвей дерева в л + 1 раз, тогда как при анализе того же ко­ личества вариантов на унифицированном дереве увеличение коли­ чества городов на единицу вызывает рост количества ветвей в т < < 3 раз, а при увеличении л т стремится к двум, т. е.

22

Такой же рост памяти, наблюдаемый М. Хелдом и Р. Корном 112], характеризуется выражением (п — 1) 2п~2, т. е.

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

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

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

1.6.ЗАДАЧ А СЕТЕВОГО ПЛАНИРОВАНИЯ

ИУПРАВЛЕНИЯ

Как разновидность автоматизированных систем управления, системы сетевого планирования и управления в настоящее время получили широкое распространение. Вопросам теории и ме­ тодологии таких систем посвящено много работ [11, 95, 97, 142, 144, 156, 164].

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

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

23

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

Структура сетевого графика и характеристики работ могут но­ сить детерминированный или случайный характер, и от этого будут существенно изменяться особенности задач СПУ. Здесь мы будем рассматривать только детерминированные сети.

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

Рассмотрим постановку временной разновидности задачи расче­ та сетевого графика. Структура сетевого графика диктует необхо­ димость соблюдения определенной очередности выполнения работ. Так, работы № 4, 5 (рис. 6) не могут быть начаты, пока не оконче­ на работа № 1, работы № 8, 9 не могут быть начаты, пока не окон­ чены работы № 2, 5 и т. д. Нетрудно видеть, что минимальное вре­ мя, за которое может быть выполнен комплекс работ, определяет­ ся совокупностью наиболее медленных работ, тогда как целый ряд работ имеет резервы времени. В нашем примере такой совокупно­

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

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

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

4 — наиболее раннее (минимальное) время возможного наступле­ ния события 5/, определяется временем выполнения последней ра­

24 •

tpH— наиболее раннее (минимальное) время возможного начала! работы, соединяющей события S c и Sj, определяется как длина критического пути между начальным событием графика и началь­ ным событием выбранной работы:

t„ — наиболее позднее (максимальное) время допустимого на­ ступления события Sj, определяется как разность полного крити­ ческого пути и критического пути между событиями S) и Sk'-

tno — наиболее позднее (максимальное) время допустимого окон­ чания работы, соединяющей события S { и

^пн — наиболее позднее (максимальное) время допустимого на­ чала работы, соединяющей события S t и Sj, оно на величину про­

должительности выполнения работы меньше tlJ0:

S t и Sj, определяется как максимальное увеличение продолжитель­ ности работы, не приводящее к увеличению длины критического пути:

Р[І = іц = й* - 1%- 1%- 14; (1.27)

PlJ — свободный резерв времени, определяется как максималь­ но допустимое увеличение продолжительности работы, не нарущаю-

25