книги из ГПНТБ / Васильев, В. В. Гибридные модели задач оптимизации

А К А Д Е М И Я Н А У К У К Р А И Н С К О Й С С Р

Институт электродинамики

В. В. ВАСИЛЬЕВ А. Г. ДОДОНОВ

ГИБРИДНЫЕ

М ОДЕЛИ

ЗАДАЧ ОПТИМИЗАЦИИ

И З Д А Т Е Л Ь С Т В О « Н А У К О В А Д У М К А » КИЕВ— 1974

6Ф7

В19

УДК 681.142.33 : 330.115

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

Вкниге обобщены результаты исследования авторов по раз­ работке методов и средств электронного моделирования задач

оптимизации.

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

Ответственный редактор академик АН УССР Г. Е. Пухов

Рецензенты: доктор технических наук Л. Я- Нагорный, кандидаты технических наук В. В. Петров, А. Ф..Катков

Редакция физико-математической литературы

3314—019 В М22Ц04)—74 14—74

©Издательство «Наукова думка», 1974 г.

Введение

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

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

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

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

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

а

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

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

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

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

Под руководством академика АН УССР Г. Е. Пухова разрабо­ таны принципы построения специализированных вычислительных устройств с использованием элементов непрерывной вычислитель­ ной техники. На основе этих принципов созданы специализирован­ ные моделирующие машины «Оптимум-2» и «АСОР-1», которые в настоящее время выпускаются серийно.

Машина «Оптимум-2» предназначена для механизации вычис­ лений, связанных с планированием транспортных перевозок. Элект­ ромоделирующая установка «АСОР-1» предназначена для модели­ рования и оперативного расчета сетевых графиков при планирова­ нии и управлении ходом новых разработок в различных областях науки и техники. Временные характеристики получаются в виде

4

Г л а в а 1

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

1.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ГРАФОВ

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

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

Множество элементов W графа G изображают кружками и на­

тированные и неориентированные ребра Г В общем случае граф можно определить следующим образом.

Говорят, что задан граф G (W, U, Р), если даны два множества эле­ ментов W к U (W О U = 0 ) , называемых соответственно множест­ вом вершин и ребер, и трехместный предикат Р, называемый инциндентором, который удовлетворяет следующим условиям:

1) Р определен на всех таких упорядоченных тройках элемен­ тов X, у, и, для которых X, у £ X и и £ V, т. е. ребро и соединя­

ет вершину X с вершиной у, или и соединяет пару ху упорядочен­ ных вершин;

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

6

3. Существует такая пара х, у, для которой х Ф у и Р {х, и, у)

исуществует Р (у, и, х).

Всоответствии с этим множество U разбивается на три попар-

но непересекающихся подмножества U, U, U. Элементы множества

U, для которых истинно первое высказывание, называются дуга-

О

ми, элементы множества U, для которых справедливо второе усло­

вие — петлями, а элементы U, для которых выполняется третье утверждение — звеньями.

В зависимости от вида ребер графы разделяются на три вида: *+

если U Ф 0 , то граф называется ориентированным или орграфом;

обозначать І~ (х, и), а множество дуг, входящих в вершину, соот­ ветственно /+ (х, и).

Путем в графе G назовем конечную последовательность, в кото­ рой конец каждой ветви, кроме последней, совпадает с началом сле­ дующей. Каждая дуга графа может характеризоваться парамет­ ром di/.

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

1.2. ЗАДАЧИ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ ПО ДЛИНЕ ПУТЕЙ НА ГРАФЕ

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

где Lp — длина пути; Sp — множество дуг, которые принадлежат пути Р. Большое количество задач сводится к отысканию L3KCTp для графа G (W, U) относительно двух различных элементов мно­ жества W или U.

В зависимости от логической функции, реализуемой вершинами xt графа, последние можно подразделить на конъюнктивные и дизъюнктивные.

7

Конъюнктивным называется граф G (W, И), элементы множест­ ва W которого реализуют функцию конъюнкции относительно /~ (х, и) (рис. 1):

Ри Л P2.J Л • • • Л Pm.l gu Л gl.l Л • • • Л gn.l- (1.2) Так как в практических приложениях этого типа графа допу­ скается параллельное и последовательное выполнение множества /+ (х, и), то в общем случае конъюнкция в правой части может быть

Конъюнктивные графы по логичес­ ким функциям множества вершин W не могут иметь циклов, т. е. таких путей, у которых хг = хп.

Дизъюнктивным граф G (W, V) Рис. 1 называется при условии, если он реализует функцию, которую мож­

но записать как импликацию, в правой части которой конъюнк­ ция или дизъюнкция относительно элементов 1+ (х, и), а в левой — дизъюнкция относительно элементов І~ (х, и):

P u V Р-2.1 V V P m J—*-g\,l Л g 2 ,i Л А gn.l- (1.5)

Решение для такого графа состоит в отыскании множества ми­ нимальных (кратчайших) путей

■^-тіл 6 G (W, U).

Когда все элементы множества W реализуют одну и ту же ло­ гическую функцию относительно множества І~ (х , и), то граф на­ зывают однородным. Если же среди элементов множества W содер­

Широта практического приложения экстремальных сетевых за­ дач, к которым сводятся, например, задачи выбора наиболее эко­ номного маршрута, определения наиболее надежного пути в систе­ мах связи, анализа транспортных сетей, исследования информа­ ционных систем, сетевого анализа сложных комплексов работ и многие другие, явилась одной из причин значительного интереса исследователей к этим задачам, что в свою очередь обусловило появ­ ление большого числа различных методов и их модификаций, на­ правленных на определение экстремальных путей в сетях [75, 79, 80, 94].

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

8

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

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

1. Множество узлов сети упорядочивается таким образом, чтобы номер конечного узла каждой ветви был больше номера ее началь­ ного узла [94] (рис. 2, б).

2.Начальному узлу се­ ти приписывается число нуль.

3.Выбирается мини­

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

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

1.3.ПУТИ ЗАДАННОЙ ДЛИНЫ НА ГРАФАХ

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

ряда вопросов оперативно-календарного планирования и управле­ ния [209].

9