ПРИБЛИЖЕННЫЙ МЕТОД ПОСТРОЕНИЯ КОМПЛЕКСНЫХ РАСПИСАНИЙ ГРУППОВОЙ ОБРАБОТКИ ПАРТИЙ ПРИ НАЛИЧИИ ОШРАНИЧЕНИЙ 2 страница

1) количество требований рассматриваемого i-го типа в формируемых партиях не может быть меньше, чем 2 , т.е. , где h – идентификатор соответствующей партии требований i-го типа (номер столбца в i-ой строке матрицы (А)); если при формировании начального решения по составу партий требований i-го типа для задаваемого количества партий в сформированном решении для h=1 получено, что , то построение эффективных составов партий требований i-го типа должно быть завершено;

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

3) задаваемое первоначально количество партий требований i-го типа, для которого определяется эффективный их состав, равно 2 ( ), после чего количество партий увеличивается (при определении эффективного их состава) до тех пор, пока для начального решения по составу партий для задаваемого выполняется условие ; при выполнении условия (для начального решения) исследование состава задаваемого количества партий завершается;

4) формирование эффективных решений по составу партий (в количестве ) связано с увеличением (на 1) количества требований в партии с индексом (индекс столбца в соответствующей строке матрицы (А)) при одновременном уменьшении количества требований в партии с h=1; таким образом, направление отрицательного левого градиента изменения значений целевой функции сопоставлено с соответствующим идентификатором партии (столбца в матрице (А)), состав которой изменяется, что приводит к уменьшению значения ;

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

Сформулированному условию прекращения формирования решений по составу партий требований в количестве соответствует Теорема 1.

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

Доказательство. При формировании составов партий требований i-го типа определяется эффективное количество требований в каждой из партий, при этом порядок следования партий значения не имеет. Алгоритм метода формирования составов партий предполагает, что для партии, индекс которой является задаваемым в ходе выполнения алгоритма, реализуется увеличение количества требований в ней. При этом количество требований в остальных h-ых партиях (за исключением h=1) остается неизменным. Для партии с индексом h=1 количество требований определяется следующим образом: . Пусть на (s-1)-ом шаге алгоритма сформировано решение по составу партий в виде i-ой строки матрицы (А): . При этом значения элементов и получены такими, что: (т.е. ). На s-ом шаге в соответствии с алгоритмом метода преобразование элементов ( ) выполняется следующим образом: (при ), , . Получено, что при неизменных значениях элементов ( ). На (s+1)-ом шаге алгоритма выполняются следующие преобразования элементов ( ): ( ), , . В результате получено, что (т.е. ). Тогда и при неизменных значениях ( ), поэтому сформированное на (s+1)-ом шаге решение аналогично (дублирует) решению, полученному на (s-1)-ом шаге. Поэтому при (общем виде при ) формирование решений по составу партий должно быть закончено, т.к. формируются дублирующие решения, что и требовалось доказать.

На сформулированной теореме базируется алгоритм метода определения эффективного состава партий требований, который имеет следующий порядок шагов:

1) инициализация номера шага алгоритма s значением 0 (s = 0); инициализация идентификатора текущего рассматриваемого типа требований значением 1 ( , тогда ); инициализация параметров решения, определяющих начальное количество партий требований n типов значением 2 ( – первоначально рассматривается количество партий требований каждого типа, равное 2); инициализация значения глобального экстремума функции некоторым «большим» значением М ( );

2) формирование начального решения (состава партий) для требований типа следующим образом: а) при б) вычисление h-ых элементов i-ых строк матрицы (А) на основе выражений вида: , ; в) проверка условий корректного состава партий требований -го типа: либо ; г) если при построении начального решения для какого-либо i-го типа требований условия определения корректного состава партий не выполняются, то формируется одна фиксированная партия требований этого типа: , , при этом формируется новый состав множества I типов требований следующим образом: ;

3) формирование начального состава партий требований -го типа в количестве следующим образом (значение задано ранее): а) вычисление h-ых элементов -ой строки матрицы (А) на основе выражений вида: , ; б) проверка условий корректного начального состава партий требований -го типа: либо ; в) если какое-либо из приведенных условий не выполняется, то для требований -го типа формируется фиксированная партия , ; выполняется переход к шагу 26;

4) полученное начальное решение [(M),(A)] фиксируется как глобально эффективное для требований всех n типов, т. е. ;

5) передача текущего решения [(M),(A)] на второй уровень иерархии системы для формирования групп партий (при );

6) получение сформированного на втором уровне иерархии системы эффективного решения по составу групп партий в виде: ; вычисление значения критерия на верхнем уровне с использованием решения ;

7) полученное решение [(M),(A)] фиксируется как локально эффективное для партий требований рассматриваемого -го типа, т. е. (при этом ;

8) полученное решение [(M),(A)] фиксируется как локально эффективное для задаваемого количества партий требований -го типа: (при этом ;

9) для -го типа требований (состав партий которого оптимизируется) выполняется инициализация номера партии , состав которой будет изменяться, значением 2 ( );

10) для -ой партии требований -го типа увеличение количества требований в ней на 1 (при неизменном количестве партий ); т.е. изменение значения ( )-го элемента матрицы (А) следующим образом: формирование состава партий: при , т.е. ( ); ;

11) проверка выполнения условия окончания процесса изменения состава партий требований -го типа (при заданном количестве партий ): в случае выполнения данного условия, формирование решения по составу партий в количестве прекращается (решение [(M(s+1)), (A(s+1))] не формируется), реализуется переход к шагу 18;

12) при выполнении условия формируется решение [(M(s+1)),(A(s+1))], которое передается на второй уровень системы для определения эффективного состава групп партий , соответствующего текущему сформированному решению [(M(s+1)),(A(s+1))];

13) получение эффективного решения , сформированного на втором уровне системы, использование полученного решения для вычисления значения критерия ;

14) анализ эффективности решения [(M(s+1)),(A(s+1))] путем вычисления левого (правого) дискретного градиентов ( ) целевой функции (вдоль направления , соответствующего номеру партии, в которой изменяется состав; на основе веденных в [2] понятий дискретных градиентов и отношений частичных порядков между решениями); вычисление градиентов ( ) выполняется по формулам следующего вида:

а) при условии, что [(M(s+1)),(A(s+1))] [(M(s)),(A(s))];

б) при условии, что [(M(s)),(A(s))] [(M(s+1)), (A(s+1))];

в этих выражениях – номер партии, в которой изменяется состав требований, соответствующий направлению градиента целевой функции ;

15) в случае выполнения условия вдоль направления , сформированное решение является более эффективным, чем решение [(M(s)),(A(s))], тогда решение [(M(s+1)), (A(s+1))] рассматривается как некоторое промежуточное, подлежащее дальнейшей оптимизации (решение [(M(s+1)),(A(s+1))] фиксируется как локально эффективное для заданного количества партий : = ), т.е. решение = = является локально эффективным по составу партий для заданного их количества ; фиксируется значение как соответствующее локально эффективному решению для рассматриваемого количества партий ( ); выполняется переход к шагу 10;

16) при выполнении условия сформированное решение [(M(s+1)), (A(s+1))] не является более эффективным (при условии минимизации критерия ), чем решение (для количества партий ); тогда полученное решение [(M(s+1)),(A(s+1))] в дальнейшем не рассматривается, выполняется переход к шагу 17;

17) модификация значения индекса (номера) партии , состав которой модифицируется: если полученное значение удовлетворяет условию , то выполняется переход к шагу 10; при выполнении условия процесс формирования составов партий требований -го типа в количестве должен быть завершен (то есть завершается процесс поиска эффективного состава партий, количество которых равно ); переход к шагу 18;

18) выполняется сравнение значения критерия , соответствующего текущему (для данного количества партий ) эффективному решению , со значением критерия , соответствующего решению , являющемуся локально эффективным для требований заданного -го типа;

19) в случае выполнения условия текущее локально эффективное решение для заданного количества партий является локально эффективным по количеству и составу партий требований -го типа; тогда , ; переход к шагу 21;

20) в случае выполнения условия текущее эффективное решение не обеспечивает улучшение значения функции по сравнению с решением (тогда решение не фиксируется как локально эффективное для -го типа требований);

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

22) формирование начального состава партий требований -го типа в количестве – задание значений h-ых элементов -ой строки матрицы (А) с использованием выражений вида: ;

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

24) в случае выполнения условия окончания процесса формирования начального состава партий в количестве вида: исследование эффективности сформированных составов партий требований в количестве должно быть завершено (формирование состава партий требований -го типа должно быть завершено);