автореферат диссертации по авиационной и ракетно-космической технике, 05.07.12, диссертация на тему:Алгоритмы поиска и сортировки алтернативных планов для оптимизации и прогнозирования аэрокосмических экспериментов

АЗЕРБАЙДЖАНСКОЕ НАЦИОНАЛЬНОЕ АЗР0К0СМИЧВСК0Е АГЕНТСТВО

На правах рукописи УДК 528.8:519.853:330.П5(043г3)

КЕРИМОВ ВАГШ> АСАД оглы

АЛГОРИТМЫ ПОИСКА И СОРТИРОВКИ АЛЬТЕРНАТИВНЫХ ПЛАНОВ дя ОПТИМИЗАЦИИ И ПРОГНОЗИРОВАНИЯ АЭРОКОСМИЧЕСКИХ ЭКСПЕРИМЕНТОВ

Специальность: 05.07.12 - дистанционные аэрокосмические исследования

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Г Г 5

1

Баку - 1997

Работа выполнена в Азербайджанском Национальном Аэрокосмическом Агентстве.

Научные руководители:

- доктор экономических наук, профессор

- кандидат технических наук, с»н*с«

А.Ф.МУСАЕВ Р.А.ТАГИЕВ

Официальные оппоненты:

- доктор технических наук, профессор

- кандидат технических наук, с.н.с

А.М.АББАСОВ

Р.М.РАГИМОВ

Ведущая организация: - Институт Кибернетики Академии

Наук Азербайджанской Республики

Защита^диссертации состоится "¿¿¿С1Г 1997 г.

в Л/ ьчасов на заседании Специализированного совета Н 0CA.3I.0I при Азербайджанском Национальном Аэрокосмическом Агентстве по адресу: 370106, Баку, проспект Азадлыг, 159.

С диссертацией можно ознакомиться в библиотеке Азербайджанского Национального Аэрокосмического Агентства.

Автореферат разослан " ОШ^^Щ 1997 г.

Ученый секретарь Сп ециа ли зирова нн ого совета 'к.т.н., с,н.с.

Р.А.ТАГИЕВ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Для достижения этой цели были поставлены и решены следующие задачи:

- разработать математическую модель, отражавшую альтерна-

- * -

тивные варианты планирования предстоящего аэрокосмического эксперимента;

- выявить перечень параметров и разработать необходимые критерии для оценки планов аэрокосмического эксперимента;

- разработать алгоритмы поиска оптимального по заданному критерии плана эксперимента из множества возаожных;

- разработать алгориты построения и сравнения ожидаемых планов аэрокосмического эксперимента;

- разработать методы для оценки вероятности наступления ожидаемых планов эксперимента.

Методы исследования. При проведении исследований б работе использовались методы теории графов, теории вероятностей, теории множеств и математической логики, методы искусстве ного интеллекта и методы сетевого планирования и управления ( СПУ ).

Научная новизна. Впервые предложена математическая модель для исследования планируемого аэрокосмического эксперимента. Такой моделью служит сеть типа "И/ИЛИ", которая раскрывает альтернативные варианты планирования эксперимента, обеспечив тем самым выбор оптимального из них. Кроме того, стохастическа сеть типа "И/ИЛИ" позволяет прогнозировать ожидаемые планы эксперимента.

Научные положения , выдвинутые в работе как объект защиты:

1. Принципы построения сетевой модели типа "И/ИМ" для планируемого аэрокосмического эксперимента.

2. Теоремы и математические формулы, являющиеся теоретическим обоснованием разработанных методов и алгоритмов.

3. Алгоритмы поиска и сортировки альтернативных планов, положенные в основу исследования планируемых аэрокосмических экспериментов.

Достоверность научных положений подтверждается теоремами доказанными в ходе работы над диссертацией и совпадением экспериментальных расчетов с теоретическими выводами.

Практическая ценность работы состоит в том, что разработанные методы и алгоритмы нашли практическое применение при решении тематических задании Института Экологии.

Адробация работы. Основные результаты работы докладывались

на:

- научно-технической конференции молодых ученых НПО Космических Исследовании, г. Баку, 1968 г.;

_ хШ-й школе -семинаре по математическому моделированию в проблемах, рационального природопользования, г. Ростов- на- Дону, 1990 г.;

- семинарах ученого Совета Института Космических Исследовании Природных .Ресурсов.

Основные положения работы апробированы также в утвержденных научных отчетах ЖИПР.

Публикации» По теме диссертации опубликовано семь печатных работ.''

Структура и объем диссертации.Диссертационная работа состоит из введения, четырех глав, заключения, приложения, списка литературы из 70 наименований. Содержание работы изложено на 125 страницах, включая 13 рисунков и 5 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Пусть имеется некоторый структурный план в виде сетевого графика для проведения предстоящего эксперимента. Построим на основе этого сетевого графика более расширенную сеть, отражающую множество возможных альтернативных планов. Такой сетью будет сеть типа "И/Ш1И". Предлагается нижеследующая схема для построения "И/ИЛИ" сети:

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

2. причинно- следственные связи между задачами строится методом сведения задач к подзадачам, т.е. размышлением в

обратном направлении;

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

Построенная "И/ИЛИ" сеть обладает такими свойствами , как ориентированность, конечность, связность. Такие сети характеризуются наличием логической связки при ее вершинах. Имеются два вида логических связок: конъюнктивная связка , дизъюнктивная связка. Каждый сетевой график- возможный структурный план - построен таким образом,что:I) его начальная и конечная вершины совпадают с начальной и конечной вершиной "И/ИЛИ" сети; 2) все логические связки при'..', его вершинах являются конъюнктивными.

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

Для прогнозирования поведения эксперимента предлагается схема:

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

2. определяются вероятности реализации этих продолжений.

Построенная сеть будет стохастической сетью типа "И/ИЛИ"

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

На рис. I приводится стохастическая сеть, описывающая альтернативные варианты проведения эксперимента, выполняемого для корректировки планов землепользования, сдесь каждая дуга описывает реальную работу, каждая пунктирная дуга - фиктивную работу, каждой вершине соответствует' событие, поэтому такая сеть по одному признаку является сетьв типа "И/ИЛИ" , по другому - сетью типа "бобытия - работы". В прямоугольниках указаны: в левой части - условная оценка продолжительности, в право] части - условная оценка стоимости соответствующей реальной работы. Стохастичность этой сети определяется наличием "решающих событий": 2,9,10.

В зависимости от результата аобытия 2 необходимо

50

90

Рис.1. Стохастическая сеть для прогнозирования поведения эксперимента, проводимого с целью корректировки планов землепользования.

выполнить работ у (3,5), либо работав,6) и (4,7). В зависимости от результата события 9 выполняется работа (10,12), либо работа (10,13), либо работы (II,В) и (11,15).

Веса, приписанные дугам показывают вероятность реализации альтернативных продолжений.

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

Работа, обозначенная дугой (3,5) - полевая проверка результатов камерального дешифрирования. Далее следуют работы: (4,6) - полевая проверка результатов камерального дешифрирования, совмещаемая с работой (4,7); (4,7) - полевое дешифрирование трудноопознаваемых объектов. Дугой (8,9) описывается комплекс следующих работ: определение координат опорных точек; инвентаризация фотограмметрических приборов с целью выбора вариантов для нанесения изменившейся ситуации на план.

(10.12) - нанесение изменений на план упрощенными способами (вариант I).

(10.13) - нанесение при помощи фотограмметрических приборов (вариант 2).

(II, 14) - нанесение при помощи элементов варианта I. Эта работа выполняется совместно с работой (11,15).

(11,15) - нанесение при помощи элементов варианта 2.

(16,17) - перенесение гориэонталей;окончательное вычерчивание контуров и горизонталей.

Вносимыми работами в первоначальный сетевой график, за которыми следуют альтернативные продолжения, являются: I.проверка наличия трудноопознаваемых объектов и выявление -выборочных зон для полевой проверки; 2. инвентаризация фотограмметрических приборов с целью выбора вариантов для нанесения изменившейся ситуации на план.

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

Сеть типа "й/ИШ,г полностью описывается тройкой & =(Х,А,Р),

где X = {х^ , ...,хЛ} - множество вершин, А ={а4 ,...ат}-множество дуг, Р - матрица размера , которую будем называть матрицей признаков вершин. Вводим в рассмотрение следующие предикаты:

Р<(х) - "вершина х связана со своими дочерними вершинами связкой "И"1 . Такую вершину назовем к-вершиной.

Рй 60 - "вершина х и ее дочерние вершины связаны связкой типа "ИЛИ". Такую вершину назовем о1-вершиной.

Р3 (х) -"х имеет единственную дочерную вершину" (унарная связка). Такую вершину назовем и.-вершиной.

Р^ОО - "х - конечная вершина".

Следовательно, Р = ||р60||£_^ \ х X.

Графы, описываемые предложенной тройкой будем называть сЬк -графами, а сети, описываемые этой тройкой - с1к-сетями.

Пусть множество всех с/к-графов,- ориентированных,

конечных, связных, а - множество всех Ык -сетей,- тоже

ориентированных, конечных, связных. Очевидно, что:

I&с1к\= 1£<?к1= С £2

Граф типа в=(Х,А,Р) назовем к-графом, если Ух £ X не является с| -вершиной.

Любой граф всегда содержит множество к-подграфов,

миноранта и мажоранта которых совпадают с минорантой и мажорантой графа & .

Пусть множество всех таких подграфов графа

як=1&<}. . , , ег} , где % = .А; ); ,

Аг " матРи«а признаков

вершин графа &^ ; ^ j .

При помощи параметра можно обозначить множество возможных структурных планов, а также множество ожидаемых структурных планов.

Пусть х ц -начальная вершина сети & , а х к - конечная. Пусть дугам (х £ ) £ А. приписаны веса Ъ ¿у ^ О , где

■t¿J ~.Ь(x¿ ,x¿ ) - продолжительности соответствующих работ.

Пусть Т^ - продолжительность критического пути плана .

Задача I: Поиск возможного плана с наименьшей продолжительностью.

Требуется найти такой план из , которому соответствует минимальное значение из всех Т£ . Зтот план обозначим через (г0 , а соответствующее время - через Т0 ;

Т0 = (I)

„ <1 _ Пусть у - такая функция, что она каждому плану сопоставляет продолжительность его критического пути.

Задача 2: Сортировка ожидаемых планов по возрастанию их продолжительности.

Требуется найти такие планы,' <3-^ > 6-2)* • • ) чт0(5ы:

(2)

где произвольный элемент из 52 Д V) . Приняв у

мы обеспечиваем полное упорядочение множества , в случае о^ ¿. у происходит частичное упорядочение к .

Пусть сСа'^Ч ) - стоимости, приписанные элементам множества

AJ , где \ £ I . Пусть - функция, которая каждому

плану (7^ сопоставляет его стоимость:

¥(<%)=£ (3)

Задача 3: Сортировка ожидаемых планов по возрастанию их стоимости.

I I

Требуется найти такие планы: } . . , } чтобы;

уф) £ • • * ч>с«ч) * (р (& ,•)

где V в: € Я Л и £г

4 к х 1=Л

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

обозначим тот, критический путь которого наименьший. Продолжительность критического пути графа &о обозначим Тех .

Пусть число дочерних вершин, вершиаы х € X равно <3 , которые обозначим через х^ .

Теорема I: Пусть

1) х есть к-вершина из X, тогда:

т* вт,,а»{Шх,х;) + ТвжО} (5)

(I

2) х есть с{-вершина из X, тогда:

Тсх = »гил[[-Ь (х, зс,,') ч- Т^ ] } (б)

В практике продолжительности работ выражаются случайными величинами, поэтому используются средние значения этих величин. В таком случае возникает необходимость для анализа параметра Т 0 . Сущность анализа заключается в определении вероятности того, что срок Г0 не превзойдет заданного директивного срока Т. Предполагается, что распределение продолжительностей работ является р -распределением. Пусть работа (х£ ) характеризуется следующими показателями: Ь0 (хй .х^- )- оптимистическая

оценка, Ь I .х^ )- пессимистическая оценка .-¿на (х £ ) -- наиболее вероятная оценка (мода).

Для расчета математического ожидания Ь (х£ ) и —2

дисперсии <3 используются следующие формулы:

I (X/ ос;)— 1»(7) ' 6 6

- 12 -

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

(! ...

Р(Х0^Т) =0,5'[ ¿Жт1^-) (9)

где Ф(...) - значение интеграла вероятностей Лапласа;

Согласно центральной предельной теореме Ляпунова надежность выводов, сделанных на основе формулы (9)прямо пропорциональна мощности Ьо .

Сортировка ожидаемых планов осуществлена на древовидном образе стохастического графа. Полученный образ является "И/ИЛИ" деревом. Это дерево строится при помощи составного отображения * Отображение вершинам построенного дерева присваивает имена из множества имен вершин графа.Поскольку множество вершин этого, дерева и множество их имен (номеров) не эквивалентны, то такое дерево в памяти ЭВМ запомнить не возможно, поэтому требуетоя перенумерация вериин. Перенумерации осуществляет следующее отображение 0/> .

о*(йк) = 4к (ю)

где А к - множество древовидных образов планов : = • • • , 2>г} (II)

Кроме того, отображение 0^. строит образ графа & : 0*(&) = 2> (12)

Теорема 2: Отображение = А к биективно»

Построение дерева £) =0^. ( & ) вызвано тем, что каждый раз

после выявления "наилучшего" исхода б^ , возникает необходимость снимать с рассмотрения ряда параметров, связанных с этим исходом. На графе & это сложное, может быть невозможное дело,

- 13 -

а на дереве 3) оно решается просто: после выявления каждого

на дереве 2> всегда обнаруживаются вершины и дуги, связанные только с Юс . Пусть - множество вершин, В ¿ - множество

дуг дерева 3>с . У^ состоит из объединения двух подмножеств:

I» Уг 4 - вершины, входящие только в дерево 5)с ; 2. У£д- вершины,

входящие не только в дерево £>с. * Аналогичные рассуждения приводят

к разбиению В^ на два подмножества соответственно: B¿J,Í ^BcJz *

Из теоремы 2 следует существование отображения :

О * ( ) = .

Для поиска - образа очередного "наилучшего" исхода

с 2) вычеркиваются вершины и дуги, описываемые множествами

^¿,-1 > соответственно.

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

В соответствии с определением отображения , вводим в рассмотрение следующие обозначения; ( &/) *» =

= Ъ * Qi' ^ (У ,В ' ^ Где " образ исхода *

Уд - множество вершин, В^ - множество дуг, - матрица признаков вершин дерева 3)^ , а У, В, О- - соответственно дерева Ю .

Каждой дуге дерева <9 припишем оценки, равные оценкам прообраза этой дуги . Тогда Ч € В будет иметь две оценки; -Ь (6) - продолжительность, с(&) - атоимоать.

Следствие I из теоремы 2: Пусть ( 2)р - продолжитель-

- И -

ность максимального пути дерева 3) j , тогда:

Пусть у такая функция, что: ^ С(€>)

Следствие 2 из теоремы 2:

Для разработки алгоритмов сортировки исходов на неявном дереве были использованы результаты алгоритма эвристического поиска решающего дерева на неявном дереве, с которым можно ознакомиться в работе Н. Нильсона "Искусственный интеллект", М,, "Мир", 1973 г.

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

л

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

Наши основные выводы: I. Если ,гй/ИЛИ* дерево потенциально конечно, и для любой открытой вершины х удовлетворяется услови

1а (х)^ К (х), то эвристический алгоритм упорядоченного поис допустим. Дело в том, что величина сГ >о в теореме использует для того, чтобы обеспечить конечность "'И/ИЛИ" дерева. Таки образом, оценки, приписанные дугам конечного графа в =(Х,А, могут быть равными нулю. 2. Если для всех концевых вершин уде

л

летворяется уеловие h (х) = h (х), то верхняя часть с0 оптимального решающего дерева , обнаруженная уже в начале поиска не будет перемещаться по "И/ИЛИ" дереву.

Задача 4; Найти такие деревья . . . , из Д к чтобы:

... ^ця^сцяс) а«

Эквивалентность решений задач 2 и Ч следует из следствия I,

Элементы У^ , GLj- являются образами элементов Ху , Pj' соответственно. Однако, ввиду того, что отображение определено на множестзе in^ » то мы не имеем право, например, написать: =0^ (Х^ ), Xj (У^ ) и т. д., для этой

цели используем обозначения : Yj =0Б( Х^ ), Х^' =0Б Л (У^ ) и т. д.

Введем в рассмотрение два параметра Jf^ ,Кс(С), определяемые на вершинах графа & » Начиная с вершины х k упорядочил вершины графа. Для х к эти параметры построим так:

(к.)

= о (I?)

Для всех других вермн зги параметры строятся рекуррентно по' нижеследующей схеме:

1. Если х является к-вершиной, то:

(18)

d=1 d d=1 4

bc(i)=Z CCd) (19)

2. Если x ^ является d-вершиной, то:

hc(C) = i^m{[c(x,:,xi/)+bc(L<jffl=c(a:(,.)a;(;o)4 (20) + hc(t.)

Теорема 3: Кс(д/)= С22)

Пусть X?- (а) - вероятность реализации работы, описываемой дугой а. Пусть ( ) - вероятность наступления иcxoJ

Теорема Для вероятности наступления исходов &^ справедлива формула:

В третьей главе излагаются разработанные алгоритмы поиска и сортировки альтернативных планов. Алгоритм ПК разработ; для поиска возможного' плана с наименьшей продолжительностью (П - поиск, К - критический путь). Для построения ПК были исп зозаны результаты теоремы I. Поиск ведется с помощью функции^

Ьм(эс)=Тв* С2Ю

Алгоритм ПС' разработан для поиска возможного плана с наименьшей стоимостью (П - поиск, С - стоимость). Были использованы результаты теоремы 3. Поиск ведется при помощи функци |гс( О и множества 1Í2¿ .

Алгоритмы СНЯ и СНН разработаны для сортировки ожидаемых планов по возрастанию их продолжительности (С - сортировка, К критический путь, Я - явное дерево, Н - неявное дерево).

Для построения этих алгоритмов были использованы результаты теоремы 2, кроме того, при разработке СКН использовалис! принципы алгоритма Нильсона. Алгоритм СКЯ ведет сортировку исходов при помощи функции К м (у):

= (25)

Н

где х= ОБ (у)

Алгоритм СКН исходы сортирует на основе функции Км (у) 1 параметра ^о *

Алгоритмы ССЯ л ССН разработаны для сортировки ожидаемых планов по возрастанию их стоимости (С - сортировка, С - стоимость, Я - явное дерево, Н - неявное дерево). Для разработки алгоритмов использовались теорема 2 и теорема 3 , кроме того, при разработке ССН использовались принципы алгоритма Нильсона. Алгоритм ССЯ ведет сортировку исходов на основе функции

Ь.'(О и множества :

с.

Ь'сСО-Не (об"1 С У:)) (26)

Я0В-^У1) (27)

где ов-^у.} значение параметра & , приписанное прообразу вершины у^

При разработке ССН использован также параметр 0

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

В четвертой главе излагаются вопросы, связанные с реализацией разработанных алгоритмов. Сюда входят такие вопросы, как результаты применения алгоритмов, принципы программирования ряда алгоритмов, способы хранения и организации данных и т. д. Изложены результаты применения алгоритмов: ПК, СКЯ, СКН, ССЯ, ССН. ОБъектом применения алгоритма ПК является абстрактная сетевая модель. Объектом применения других алгоритмов является сетевая модель, построенная для эксперимента, проводимого с целью корректировки планов землепользования. Результаты последних четырех алгоритмов отражаются в табл. I.

В таблице исходы представлены множеством вершин

(см. рис. I).

Табл. I

Результаты прогнозирования поведения эксперимента, проводимого для корректировки планов землепользования.

По возрастанию продолжительности ожидаемых аланов

1 №) £РС©-У

I I, 2» 3, 5, 8, 9, II, 14,15, К» П 183 0,35

2 I, 2, ¿1-, 6,7, 8, 9, II, »,15. 16-, 17 195 0,15

3 1,2,3, 5, 8, 9, 10, 13, 16, 17 212 0,21

I, 2, 3, 5, 8, 9,10, 12, 16, Г7 216 0,14

5 I, 2, 4, 6, 7, 8, 9, 10, 13, 16, 17 224 0,09

6 I. 2, 4, 6, 7, 8, 9, 10, 12, Ж, 17 228 0,06

По возрастанию стоимости ожидаемых планов

1 9(4)

I I, 2, 3, 5, 8, 9, II, 14,-15, 16, 17 297 0,35

2 I, 2, 3, 5, 8, 9, 10, 13, 16, 17 312 0,21

3 I, 2, 3, 5, 8, 9, 10, 12, 16, 17 316 0,14

I, 2, 4, 6, 7, 8, 9, II, 14,15,16,17 331 0,15

5 I, 2, 4, 6, 7, 8, 9, 10, 13, 16, 17 346 0,09

б I, 2, 4, 6, 7, 8, 9, 10, 12, 16, 17 350 0,06

ВЫВОДЫ

1. Проведены исследования для выбора математической модели, отражающей альтернативные варианты планирования аэрокосмических экспериментов. В качестве такой модели выбрана сетевая модель типа "И/МЙ™.

2. Сетью типа "И/ИЛИ1" обеспечивается построение множества возможных альтернативных планов предстоящего эксперимента; в связи с этим разработаны два алгоритма для выявления оптимального возможного плана. Первый алгоритм выявляет возможный план с наименьшей продолжительностью, второй - с наименьшей стоимостью.

3. Было выявлено, что: с помощью стохастической сетевой модели типа "й/ИЛИ" возможно прогнозирование поведения (развития) эксперимента. На базе такой модели возможно построение множества ожидаемых планов, в котором находит отражение поведение эксперимента.

Для оперативного сравнения ожидаемых планов - '"исходов", предлагается построение их упорядоченного множества. Для сортировки исходов по возрастанию их продолжительности разработаны два алгоритма. С точки зрения отражения общей картины и взаимосвязи исходов предпочтительным является первый алгоритм, а с точки зрения эксплуатации памяти ЭВМ, а также гибкооти вычислительных работ эффективным является второй алгоритм.

5. Для сортировки исходов по возрастанию их стоимости также разработаны два алгоритма. По аналогии а вышесказанным каждый из этих алгоритмов имеет преимущество в сравнении с другим.

6. Получена математическая формула для расчета вероятности наступления исходов.

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

8. На основании теоремы Ляпунова выявлено, что если за продолжительности работ принимаются средние значения экспертных оценок, ТО' надежность оценки вероятности выполнения выявленного

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

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

Основные положения диссертации опубликованы в следующю печатных работах:

1. Керимов В.А;, Ханмамедов O.K. Реализация алгоритма перебора вглубь в пространстве стратегий. Деп. ВИШИ № 6054 В - 87, 1987 г., 21 с.

2. Керимов В.А., Ханмамедов O.K. Реализация на ЭВМ алгоритма направленного перебора в пространстве стратегий. Деп. ВИНИТИ й 9138 В - 87, 1987 г., 20 с.

3. Керимов В.А. Алгоритмы перебора на графе стратегий и их выполнение на ЭВМ. Деп. ВИНИТИ № 3924 В - 88, 1988 г.,28 с.

4. Керимов В.А. Об организации машинной реализации алгоритма перебора вглубь. Труды У1 научно-технической конференции молодых ученых НПО КИ, ч. П.Баку, 1988 г.

5. Керимов В.А. Об одной особенности применения методов СПУ в задачах природопользования. Ростовский Государственный Институт механики и прикладной математики. Сборник тезисов ХУП пколы-семинара по математическому моделированию е проблемах рационального природопользования, 1990 г., 2с.

6. Керимов В.А,, Мусаев А.Ф., Портнов А.П. Разработка программно- математического метода поиска оптимальной топологии сетевых графиков для календарного планирования аэрокосмического эксперимента. Сообщения НПО КИ АН Аз. ССР, "Злм", Баку, 1990 г., с. 49 - 55.

7. Кэримов В.9., Мэчидов Д.Б. Еколсжи - игтисади системин дазаныглышрынын алгорившк модели. Еколоки^а Институтунун елш эсэрлэри гоплусу. П бурахылыш, Т Ршссэ, Т996-чы ил,Бакы,с.16-1'

В.Э.Кэримов

Аерокосмик експериментлэрин оптамаллашдырылмасы во прогнозлашдырылмасы учу" алтернатив планларын ахтарышы вэ чешидлэнмэси алгоритмлэри

Хуласэ

Аерокосмик експерименти елми чэьэтдэн эсасландырылмыш шэкилдэ Куата ксчирмуин эн муЬум амилпэриндэн бири онун ики парам стр-заман вэ дэ]эр- эсасында оптималлашдырьшмасы учун р!уазн усуллар Ьазырланмасыццан ибарэтдир. Дикэр муЬум аиил експериментнн К93ЛЭНИЛ9Н инкишаф истигамэтлэри Ьаггьшда прогноз информасща]а малик олмагдан ибарэтдир. Гдд сдилэн оптималлашдырма вэ прогнозлашдырма мэсэлэлэрини аерокосмик скспсримснт учун гурулмуш "ВЭ/ ВЭ ] А" тиши шэбэкэ модели эсасында Ьэлл егмэк алар. "ВЭ/ ВЭ ] А" типли шэбэкэ модели васитэси илэ експерименгн hэjaтa ксчирм^ин алтернатив планларыны вэ онун кезлэнилэн алтернатив инкишаф истигамэтлэрини экс етдирмэк мумкундур. Бу модел нэзэрдэ тутулая сксперименти тэшхил едэн ишлэр чохлугу, бу ишлэр арасында элэгэ зэнчирлэри, ишлэрин дэjэp вэ давамнцэти, прогнозлашдырма мэсэлэсшщэ исэ бунлардан башга ишлэриш еЬгнмаллары Ьаггьшда информасща эсасында гурулур. Нэзэрдэ тутулан експерчмептин тэЬлилиндэ оперативляк тэлэби онун хезлэнилэн инкишаф истигамэтлэрини верилшшл ме']'ар эсасында чешидлэмэк мэсэлэсинэ кэтярир. Эдэбицатдан мэ'лум олан усуллар- «-алгоритм вэ Н.Нилсон алгоритмлэри- гсдулан мэсэлэлэри Ьэлл стмэк учун кифajэт «мэдщн учун диссертасщада алты алгоритм тэклиф олунмушдур.

V,A.Kerimov

Searching and sorting algorithms of alternative plans for the

optimization and forecasting of the aerospace experiments.

Summary

One of the main condition for scientifically based conduction of the aerospace experiment is the development of mathematical methods of optimization of experiment on a certain criterion. The criteria of optimization, as a rule, have a cost or time. Another main condition is the forecasting of the variants of experiment development. The variants of experiment's development these are set of works, operations, means, methods necessary for the execution of experiments under consideration.

The solution of the mentioned tasks of optimization and forecasting is possible on the bases of net model "AND/OR" created for the aerospace experiments.

Net model "AND/OR" opens the possibilities for reflection of alternative plans for realization of experiment and its possible alternative variants of development. This model is created on the bases of information on the set works necessary for realization of experiment, interrelation between these works, cost and duration of work, besides it in the mentioned tasks of prognosising-probability completing of work. The condition of rapid planning of forthcoming results in the task of sorting its possible variants of developments on given criterion.

For settling these tasks the thesis proposes six algorithms and it has been shown,the available in literature method-a algorithm and algorithms of N.Nilson do not properly serve the requirements of task considered in this thesis.