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

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

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

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

ГИБРИДНЫЕ

М ОДЕЛИ

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

И З Д А Т Е Л Ь С Т В О « Н А У К О В А Д У М К А » КИЕВ— 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