Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник С.Т. Вопросы нефтяной технической кибернетики
 
djvu / html
 

20 Некоторые принципы формирования иерархических структур
деления потока, выходящего из стока Л,Р Ь г п по стокам дерева 7 2,в не зависит от тою, какой сток дерева Г, является соседом оок А\. В т - т. е. конфигурация дерева 7, не зависит от конфигурации дерева 7 , в тех пределах, в которых стоки множества /з п принадлежат обоим деревьям.
Процесс построения дерева можно рассматривать как некоторую динамическую систему, в которой стоки . вместе с распределенным в них запасом ресурса являются ссстояниями системы на шаге т, а выбор стоков . ,-ц и выбор соседа дли каждого из них из множества (/3 ) соответствует переходу в состояние т-\ 1.
Из сказанного выше следует, что будущее этой системы (состояния на т 1, т. •-(• 2 и т. д. шаге) определяется только се состоянием и настоящем и не зависит от предыстории.
Известно, что для таких систем выполняется принцип оптимальности Беллмана [2].
Начинать построение сети можно как с Л0, перебирая всевозможные наборы СРОКОВ, для которых А, является соседом, так и с концевых стоков, перебирая всевозможные наборы концевых стоков и всевозможные способы подсоединения их к остальным. Однако более экономным является второй способ. Действительно, в первом случае приходится перебирать не только всевозможные наборы стоков, для которых А0 является соседом, но и комбинации потоков в каждый из них, тогда как поток но ребру, входящий в концевой сток, известен равен спросу этого стока. На любом шаге, начиная со второго, концевым стоком может быть сток А\(- № , , поток и него определяется выражением
Qi tf.-f-VQu, Ac:s ,V
>-J j
Рассмотрим более подробно процедуру построения оптимальной сети, начиная с концевых стоков-
Построение ведется по шагам. Первый шаг состоит в том, что в нуль-графе, вершинами которого являются стоки Л, и источник Л0, поочередно проводится одно из п2 звеньев (г, i) (( = 1, 2, ..., п, г = 0, 1, 2, ..., п; г -- • i). Каждому звену д-соответствует состояние 5J шага 1, которое
дает начало задаче, аналогичной исходной, по с числом стоков, равным п-1. На втором шаге каждый вариант сети, соответствующей состоянию S1K дополняется каким-либо звеном из (п-I)2 возможных. Таким образом, в каждом состоянии S шага т получается лес, состоящий пз
деревьев, которые будучи присоединенными к фиктивному источнику Ф() образуют дерево Т2.
Определение 3. Пусть для двух лесов С/, и G-,, заданных на множестве вершин Л = Д; i-=\,/i . выполняются условия:
1. Если некоторая вершина Л .- Л) является корневой вершиной
дерева в одном лесе, то она является корневой вершиной в другом.
2. Вели вершина AJ ( А является вершиной дерева с корнем Ак
в одном лесе, то она является корневой вершиной ;в другом. Тогда
леса G, и 6 2 сравнимы по множеству деревьев.
Определение 4. Классом сравнимости иазснем множсстю состояний 5 (к=1,2, . . . , ка> , леса которых с[аьнимы по деревьям.

 

1 10 20 21 22 23 24 25 26 27 28 29 30 40 50 60 70 80 90 100 110 120 130 140 150


Автоматизация производства в нефтяной и химической промышленности. Справочники, статьи