ПОСЛЕДОВАТЕЛЬНЫЙ АНАЛИЗ ВАРИАНТОВ

— метод решения задач оптимизации, основанный на последовательном построении, сравнении, анализе и отборе вариантов. С точки зрения методологии П. а. в. является естественным обобщением идей последовательного принятия решений (см. Последовательный анализ). С другой стороны, П. а. в. тесно связан с программированием динамическим. Алгоритм динамического программирования можно рассматривать как частный случай П. а. в., когда в основе правил отбора вариантов лежит Веллмана принцип оптимальности. В схеме П. а. в. условие задачи представляется в виде описания мн-ва вариантов и совокупности «контрольных опытов», с исходами которых связаны правила отбора вариантов. Процесс решения представляется в виде многоступенчатой структуры, напоминающей структуру сложного опыта. Каждая ступень связана с проверкой наличия у подмн-в вариантов тех или иных свойств (что сводится к получению исходов опытов) и ведет либо к непосредственному сокращению исходного мн-ва вариантов, либо подготавливает возможность такого сокращения в будущем. Ниже описана схема П. а. в. (на теоретико-множественном языке).

Пусть имеется три мн-ва: мн-во вариантов, мн-во опытов, мн-во индексов опытов. Во мн-ве выделено подмн-во , называемое контрольным. Далее имеется мн-во которое наз. мн-вом исходов. Для каждого опыта в мн-ве I определено подмн-во каждый элемент которого наз. исходом опыта Во мн-ве I выделено подмн-во Q I, на котором определен оператор сужения ставящий в соответствие каждому некоторое подмн-во Это соответствие распространяется на подмн-ва U мн-ва W следующим образом:

где На мн-ве опытов П определен оператор реализации Р, ставящий в соответствие каждому некоторый элемент из называемый реализацией опыта Задача состоит в определении такого макс. подмн-ва которое является инвариантным относительно любого элемент а — из контрольного мн-ва для каждого

Введем несколько определений. Схемой R решения задачи наз. последовательность ф-ций со значениями из где определена на прямом произведении раз). Процедурой соответствующей схеме решения последовательность реализации опытов где Процедура наз. конечной, если для нее существует некоторое i, для которого где I — элемент, принадлежащий мн-ву исходов I, появление которого ведет к остановке процедуры решения. Концом процедуры является где Если же такого не существует, то процедура наз. бесконечной. Решением задачи, соответствующим схеме мн-во W являющееся сужением мн-ва W в соответствии с процедурой где индекс пробегает все мн-во значений, для которых исходные получающиеся в результате реализации процедуры входят в . Говорят, что схема R дает полное и точное решение данной задачи, если для любого и не существует другого, отличного от мн-ва, удовлетворяющего этому условию и не входящего вид. Поясним значение приведенной схемы. Решение многовариантной задачи является массовой проблемой в том смысле, что заранее неизвестно, где находится искомое подмн-во W во мн-ве W. Известны лишь общие свойства вариантов всех , в совокупности выделяющих это подмн-во в W. Но проверка каждого из этих свойств и есть некоторый вычисл. процесс, называемый опытом. Эти опыты соответствуют мн-ву . Исходы опытов позволяют судить о том, где находится W в W (напр., отбрасывать некоторые подмн-ва, не имеющих общих частей с W и о том, целесообразно ли ставить последующие опыты, уточняющие его местонахождение. Часто полезно делать опыты, для которых , но которые также сужают W или подготавливают благоприятные условия для проведения опытов, соответствующих контрольному мн-ву . В большинстве приложений правила отбора вариантов соответствуют обобщенному принципу оптимальности. Пусть задано некоторое осн. мн-во X. Обозначим мн-во конечных

последовательностей вида

через этом мн-ве выделено некоторое подмн-во допустимых последовательностей свою очередь во мн-ве выделено подмн-во полных допустимых последовательностей . Пусть задана последовательность вида начальным отрезком этой последовательности будет последовательность вида

и -м конечным отрезком — последовательность вида

Если то соответствующие части сопряженными. Рассмотрим две допустимые последовательности выделены 1-й начальный отрезок конечный отрезок начальный отрезок и конечный отрезок Если функционал Ф, определенный на мн-ве , обладает тем свойством, что из следует , то он называется монотонно рекурсивным.

Пусть Последовательность максимальной, если Пусть задана допустимая последовательность -родовым мн-вом будет подмн-во состоящее из элементов, у которых является начальным отрезком. Мн-вом продолжений совокупность всех конечных отрезков элементов -родового мн-ва, сопряженных с . Теперь можно сформулировать обобщенный принцип оптимальности. Если задан монотоннорекурсивный функционал Ф и две допустимые последовательности причем

то элементы мн-ва не могут быть максимальными.

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

В качестве примера применения схемы П. а. в. рассмотрим задачу унификации изделий. Пусть при выполнении некоторого проекта требуется применить N видов изделий, причем изделие вида в единиц Стоимость выпуска партии изделий вида объема выражается ф-цией

причем при Известно, что изделия вида могут применяться вместо изделий видов из подмн-ва причем для любого I к из того, что следует, что Требуется определить, какие изделия и в каком к-ве надо выпускать, чтобы обеспечить выполнение проекта, по критерию минимума общих затрат на выпуск изделий.

Назовем частичным вариантом длины к последовательность где принимает значение 0 или соответствует тому, что изделия типа не выпускаются, тому, что изделия типа выпускаются. Для произвольного мн-ва М введем обозначение:

Назовем частичный вариант завершенным, h если U содержит все индексы от 1 до к.

Полный вариант — это завершенный вариант длины N. При решении описанной задачи оператор сужения строится на основе исходов сравнения оценок двух завершенных частичных вариантов длины к. Под оценкой варианта понимают величину

где

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

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

вариантов. П. а. в. разработан в 1960 в Вы-числ. центре АН УССР (теперь Ин-т кибернетики АН УССР).

Лит.: Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. «Кибернетика», 1965, JSIs 1—2. В. С. Михалевич, Н. 3. Шор.