|
80 Р(Х) множество конечных последовательностей вида: р=(хь ... ... ,хкр) xteX, \<\<кр В X выделено некоторое подмножество допустимых последовательностей FT(JV)c Р(Х). В fV(X) выделено подмножество полных допустимых последовательностей 1Р(Х). p/=(xi,... ... ,х/) начальный отрезок последовательности; рч=(хй,... ,х„ ..., хлз) конечный отрезок последовательности. При q=l+\ одна из них продолжает другую. Назовем такие последовательности сопряженными. Рассмотрим две произвольные допустимые последовательности р\ и р2 и выделим в р\ /j-начальный отрезокри\ и сопряженный ему конечный отрезок Рх1м , а в р2 выделим /2-начальный отрезок p2i2 и сопряженный ему конечный отрезок /?2/2+1Функционал Ф, определенный на множестве W(X) будет монотонно-рекурсивным, так как он обладает свойством: puleW(X), pll2e>V(X), p,'M-pJM, Ф(Д„)<Ф(Л,2) => (2.35) =>ф(р,)<ф(р2) Пусть Ф* = яирф(р), тогда последовательностьр* будет максимальной, pefF" если Ф(р*)=Ф*, р*еИ/П. Для заданной допустимой последовательности р р-родовым множеством назовем подмножество R^aP^iX), состоящее из тех полных допустимых последовательностей, у которых р является начальным отрезком. Множеством продолжений Р(р) будет совокупность всех конечных отрезков элементов р-родового множества, сопряженных с р. Обобщенный принцип оптимальности состоит в утверждении. Пусть заданы монотонно-рекурсовный функционал Ф и две допустимые последовательности р\ и р2, причем: |
Последовательное приближение плана строится начиная с некоторого начального. В качестве начального возьмем план-график, оптимальный по времени реализации всех объектов. Пусть X базовое множество. Р(Х) множество конечных последовательностей вида р=(хи ... ,хь ..., Xkp) XieX, 1 В W(X) выделено подмножество полных допустимых последовательностей ^(XJc W(X). pi=(xь ... Л , ..., х/) начальный отрезок последовательности; Pq==(xn, ••• X, ■■■ ,хлз) конечный отрезок последовательности. При g=l+1 одна из них продолжает другую. Назовем такие последовательности сопряженными. Рассмотрим две произвольные допустимые последовательности р\ и ^ и выделим в р\ 1\-начальный отрезок р\ц и сопряженный ему конечный отрезок pill+1, а в рг выделим /2 -начальный отрезок рт и сопряженный ему конечный отрезок p2 +l. Функционал Ф, определенный на множестве ЩХ) будет монотонно-рекурсивным, так как он обладает свойством рт Щ Х ) , рт е Щ Х ), р Р '^ р Р ', Ф(рт) <Ф(р,п) =’ tHpi) Множеством продолжений Р(р) будет совокупность всех конечных отрезков элементов р-родового множества, сопряженных с р. Обобщенный принцип оптимальности состоит в утверждении. Пусть заданы монотонно-рекурсовный функционал Ф и две допустимые последовательностир\ и рг, причем Ф(р{) < Ф(рг) P(Pi) С Р(Рг) <2'59) Тогда элементы множества R(pi) не могут быть максимальными. Таким образом, метод, определения максимального элемента для монотонно-рекурсивных функционалов сводится к следующему: 1. Рассматривается некоторое ограниченное число допустимых последовательностей таких, что объединение их родовых множеств и тех из рассматриваемых последовательностей, которые являются полными допустимыми, в совокупности дает все множество полных допустимых последовательностей. 2. На основе обобщенного принципа оптимальности исключается часть родовых множеств; из рассматриваемых полных допустимых последовательностей оставляются только те, которые дают набольшее значение функционалу; исключаются из рассмотрения последовательности, для которых родовое множество пусто. 3. Выбирается некоторая допустимая последовательность из числа рассмотренных, для которой родовое множество не пусто и не исключалось. Рассматривается некоторое ограниченное число допустимых последовательностей, являющихся продолжением выбранной последовательности и таких, что объединение их родовых множеств и тех из них, которые являются полными, в совокупности дают родовое множество выбранной последовательности. 4. Для множества, состоящего из вновь образованных в п.З. допустимых последовательностей и неисключенных и непродолженных ранее допустимых последовательностей, производятся операции, указанные в п.2 . |