Алгоритмы оптимального планирования предполетной подготовки

6.
АЛГОРИТМЫ
РЕШЕНИЯ
ЗАДАЧ
ОПТИМАЛЬНОГО
ПЛАНИРОВАНИЯ
ПРЕДПОЛЕТНОЙ ПОДГОТОВКИ ЛЕТАТЕЛЬНЫХ
АППАРАТОВ
Задачи оптимального планирования предполетной подготовки летательных аппаратов, математические модели которых
приведены в разделе 5, относятся к классу экстремальных комбинаторных задач с линейной структурой.
Доказано, что подобные задачи относятся к числу так
называемых NP–полных задач, для которых характерна неполиномиальная зависимость продолжительности решения задачи от
ее размерности. Такие задачи считаются «труднорешаемыми» с
вычислительной точки зрения, то есть не поддающимися эффективному алгоритмическому решению [6]. Решение подобных
задач тривиальными методами может потребовать неприемлемо
больших затрат машинного времени. Поэтому основные усилия
разработчиков алгоритмов комбинаторной оптимизации
направлены на использование свойства конечности множества
вариантов решений и максимальное сокращение их перебора.
Наиболее эффективным методом решения экстремальных
комбинаторных задач является метод направленного перебора
вариантов, реализующий известную идею ветвей и границ [7].
Он предусматривает последовательное дробление множества
вариантов решения задачи, производимое до тех пор, пока не
устанавливается оптимальный план или факт несовместности
системы ограничений.
Критерий выбора подмножества вариантов для дальнейшего разбиения формулируется таким образом, чтобы сократить
до минимума количество шагов алгоритма, приводящих к искомому результату. В качестве такого критерия в большинстве
случаев используется оценка целевой функции на подмножествах вариантов решения комбинаторной задачи.
Получаемые в результате разбиения новые подмножества
вариантов подвергаются формальному анализу, целью которого
197
является максимальное сокращение объема информации, обрабатываемой на каждом этапе решения комбинаторной задачи.
6.1 Алгоритм решения экстремальных комбинаторных
задач с произвольными коэффициентами
Канонической формой экстремальных комбинаторных задач с линейной структурой является модель, приведенная в разделе 5:
(6.1)
f ( x)  ci xi  max ;

iI 0
g j ( x)   a ji xi  b j ;
j  1, n ;
(6.2)
iI j
x  ( xi i  1, m ) ; xi  0, 1, i  1, m ,
где I 0 , I j – множества номеров независимых переменных, входящих соответственно в целевую функцию и j -е ограничение
задачи;
a ji , b j , ci – произвольные целые числа.
К общей форме (6.1)–(6.2) сводится математическая модель задачи оптимального планирования технологических процессов подготовки группы летательных аппаратов к вылету,
рассмотренная в пункте 5.1.
В канонической постановке экстремальная комбинаторная
задача формулируется следующим образом: необходимо найти
вектор значений булевых переменных x  ( xi i  1, m ) , обращающий в максимум целевую функцию (6.1) при соблюдении
системы ограничений (6.2).
Вектор значений булевых переменных x  ( xi i  1, m ) ,
удовлетворяющий системе ограничений (6.2), называют допустимым планом задачи (6.1)–(6.2). Допустимый план, обращающий целевую функцию (6.1) в максимум, называется оптимальным планом.
198
Полное множество G вариантов решения экстремальной
комбинаторной задачи представляет собой прямое (декартово)
произведение:
G  X 1  X 2  ...  X m ,
где X i – множество возможных значений независимой переменной xi .
Поскольку X i  0, 1, i  1, m , множество G состоит из
2m различных двоичных m -разрядных комбинаций от (0, 0,…,
0) до (1, 1,…, 1) включительно.
6.1.1 Структуризация математической модели
Будем полагать, что к началу рассматриваемого этапа решения задачи (6.1)–(6.2) в полном множестве G вариантов выделены  непересекающихся подмножеств Gk , k  1,  , содержащих допустимые планы.
Пусть I k0 и I k1 – подмножества номеров независимых
переменных, получивших в планах k -го подмножества вариантов значения 0 и 1 соответственно, а I k – совокупность номеров
переменных, значения которых в G k не зафиксированы.
Набор значений переменных xi , i  I k0  I k1 , такой что
(i  I k0 )( xi  0) & (i  I k1 )( xi  1) ,
называется частичным планом k -го подмножества вариантов:
x C (k )  ( xi i  I k0  I k1 ) .
Любой набор значений переменных xi ; i  I k , удовлетворяющих условию бивалентности
(i  I k )( xi {0,1}) ,
называется дополняющим планом подмножества Gk :
199
x D (k )  ( xi i  I k ) .
Ограничение, которому не удовлетворяет хотя бы один
дополняющий план подмножества Gk , называется активным по
отношению к планам данного подмножества. Именно активные
ограничения определяют значений независимых переменных
xi , i  I k , не зафиксированных еще в планах k -го подмножества вариантов. Ограничения, не являющиеся активными, не
влияют на этот выбор и, следовательно, могут не учитываться
при рассмотрении данного подмножества.
Любое подмножество вариантов решения задачи определяется собственным частичным планом. Подстановка частичного плана в исходную модель приводит ее в строгое соответствие
рассматриваемому подмножеству вариантов. Следовательно,
каждому подмножеству Gk , k  1,  , соответствует собственная уникальная модель, называемая частной моделью k -го подмножества вариантов.
В процессе дальнейшей детализации подмножества Gk ,
1  k   , может оказаться, что соблюдение того или иного
ограничения частной модели возможно лишь при строго определенных значениях (только 0 или только 1) части переменных,
не зафиксированных еще в планах данного подмножества вариантов. Такие переменные называются безальтернативными.
Множества, аналогичные I k0 , I k1 и I k , но относящиеся к
целевой функции (6.1) и j -у ограничению системы (6.2), определяются по формулам:
I 00k  I 0 I k0 ; I 01k  I 0 I k1 ; I 0 k  I 0 I k ;
I
0
jk

 I I ;
j
0
k
I
0
jk

 I I ; I
1
k
j
jk

 I I ;
j
k
j  1, n .
Задача (6.1)–(6.2), приведенная в соответствие k -у подмножеству вариантов, формулируется следующим образом:
максимизировать целевую функцию
200
f k ( x)   ci xi  c1k  max
(6.3)
iI 0 k
при соблюдении ограничений
g jk ( x)   a ji xi  b jk ; j  J k
(6.4)
iI jk
где x  ( xi ; i  I k ) ; xi  0, 1; i  I k .
Здесь c1k – сумма коэффициентов целевой функции, с которыми в выражение (6.1) входили независимые переменные,
получившие в частичном плане подмножества G k значение
единицы:
ñ1k  ci ;

iI 01 k
b jk  свободный член j -го ограничения системы (6.2),
уменьшенный на сумму коэффициентов, с которыми в это ограничение входили независимые переменные, получившие в частичном плане k -го подмножества вариантов значение единицы:
b jk  b j  aij , j  J k ;

iI 1jk
J k – множество номеров ограничений системы (6.2), активных по отношению к планам подмножества вариантов G k .
Для исследования модели (6.3)–(6.4) на множествах I 0 k и
I jk ; j  J k выделяются следующие подмножества:
I 02k , I 03k – совокупности номеров независимых переменных, входящих в целевую функцию (6.3) соответственно с отрицательными и положительными коэффициентами:
I 02k  i  I 0 k : ci  0; I 03k  i  I 0 k : ci  0 ;
I 2jk , I 3jk – совокупности номеров независимых переменных, которые входят соответственно с отрицательными и положительными коэффициентами в j -е ограничение системы (6.4):
201


I 2jk  i  I jk : a ji  0; I 3jk  i  I jk : a ji  0 ;
I 2jk (i ) – множество номеров независимых переменных,
входящих в j -е ограничение системы (6.4) с отрицательными
коэффициентами, не превышающими значение a ji i   I 2jk :


I (i )  i   i  I : a ji  a ji ;
2
jk
2
jk


I (i) – множество номеров независимых переменных,
которые входят в j -е ограничение системы (6.4) с положительными коэффициентами, не меньшими, чем a ji  (i  I 3jk ) :
3
jk


I 3jk (i )  i   i  I 3jk : a ji  a ji .
В дальнейшем используются следующие обозначения:
mk – количество независимых переменных, значения которых в планах k -го подмножества вариантов не зафиксированы: mk  I k ;
m0( kp ) , m(jkp ) – количество независимых переменных, входящих соответственно в целевую функцию (6.3) и j -е ограничение системы (6.4) с отрицательными (при p  2 ) и положительными (при p  3 ) коэффициентами:
m0( kp )  I 0pk ;
m (jkp )  I jkp ;
j  Jk ;
p  2,3 ;
m0 k и m jk – количество независимых переменных, не
имеющих конкретных значений в планах k -го подмножества
вариантов и не входящих соответственно в целевую функцию
(6.3) и j -е ограничение системы (6.4):
m 0 k  mk  m0( 2k)  m0(3k) ; m jk  mk  m (jk2)  m (jk3) ;
j  Jk ;
s (jk2 ) и s (jk3) – суммы отрицательных и положительных коэффициентов j -го ограничения системы (6.4), соответственно:
202
p  2, 3; j  J k .
s (jkp )   a ji ;
iI jkp
6.1.2 Вычисление оценок целевой функции
Оценка целевой функции служит средством выбора одного из подмножеств вариантов решения задачи для дальнейшей
детализации.
Оценкой  (Gk ) целевой функции на k -м подмножестве
вариантов называется максимальное значение f (x) , вычисленное при соблюдении необходимых условий существования в Gk
допустимых планов.
В комбинаторных задачах необходимые условия существования допустимых решений в рассматриваемом подмножестве вариантов выражаются в виде двустороннего ограничения,
накладываемого на количество единиц в дополняющих планах
данного подмножества (другими словами, на количество независимых переменных, которые в дополняющих планах данного
подмножества могут принять значение единицы).
Границы диапазона [uk , vk ] допустимых значений этой
величины для k-го подмножества вариантов определяются согласно формулам:
u k  max u jk , j  I k ; v k  min v jk , j  I k ,




где u jk и v jk – соответственно минимальное необходимое и
максимальное допустимое количество единиц в дополняющих
планах подмножества G k , при котором возможно выполнение jго ограничения системы (2.4).
Процедура определения параметра u jk заключается в следующем.
Если b jk  0 , то u jk  0 .
В противном случае для определения u jk выполняются
следующие действия:
203
1) отрицательные коэффициенты j -го ограничения системы (6.4) a ji , i  I 2jk упорядочиваются по мере неубывания:
a ji1  a ji2  ...  a ji  ...  a ji 2 ;
m
jk
2) путем пошагового прибавления очередного элемента
этой последовательности к сумме предыдущих устанавливается
наименьшее количество lmin отрицательных коэффициентов,
сумма которых не превышает значения свободного члена b jk :
l


l min  min l  1 :  a ji  b jk  ;
 1


3) параметру u jk присваивается значение lmin .
Процедура определения параметра v jk такова.
Если s 2jk  s 3jk  b jk , то v jk  mk .
В противном случае для определения v jk выполняются
следующие действия:
1) положительные коэффициенты j -го ограничения системы (6.4) a ji , i  I 3jk упорядочиваются по мере убывания:
a ji1  a ji2  ...  a ji  ...  a ji ( 3) ;
m
jk
2) путем пошагового прибавления очередного элемента
этой последовательности к сумме отрицательных коэффициентов s (jk2 ) и предшествующих элементов устанавливается
наибольшее количество lmax положительных коэффициентов,
которые в общей сумме с отрицательными не превышают значения свободного члена b jk :
l


( 3)
( 2)
l max  maxl  m jk : s jk   a ji  b jk  ;
 1


3) параметру v jk присваивается следующее значение:
204
v jk  m (jk2)  m jk  l max .
Оценка  (Gk ) целевой функции на k -м подмножестве
вариантов решения линейной комбинаторной задачи вычисляется как сумма двух составляющих: константы c1k , определяемой
частичным планом данного подмножества, и приращения
 (Gk ) , которое является функцией независимых переменных,
образующих дополняющие планы G k .
 (Gk )  c1k   (Gk ) .
Процедура вычисления приращения  (Gk ) заключается в
следующем.
Если vk  0 , то  (Gk )  0.
При выполнении условия uk  m0 k  m0(3k)  vk величина
 (Gk ) принимает свое максимальное значение, равное сумме
положительных коэффициентов целевой функции (6.3):
 (Gk )   ci .
iI 03k
Во всех прочих случаях для вычисления  (Gk ) необходимо упорядочить коэффициенты целевой функции (6.3)
ci ; i  I 0 k по мере возрастания:
ci1  ci2  ...  ci  ...  cim0 k .
Тогда значение  (Gk ) может быть определено согласно
формуле:
 vk
åñëè m0(3k)  v k
  c i ,

 (G k )  ukm10 k
.
(
3
)

ci , åñëè u k  m 0 k  m0 k
 
 1
205
6.1.3 Анализ подмножеств вариантов решения задачи
Анализ подмножеств вариантов решения экстремальной
комбинаторной задачи производится с целью определения
свойств систем ограничений, соответствующих этим подмножествам. Результатами анализа того или иного подмножества вариантов может быть:
– установление факта отсутствия допустимых дополняющих планов в анализируемом подмножестве;
– выявление ограничений, утративших в процессе решения задачи свойство активности по отношению к дополняющим
планам анализируемого подмножества;
– выявление безальтернативных переменных в дополняющих планах анализируемого подмножества;
– формирование нового допустимого вектора значений
искомых переменных.
В зависимости от полученных результатов в цикле анализа выполняются следующие действия, направленные на сокращение объема дальнейших вычислений.
Подмножество вариантов, не содержащее допустимых
планов, исключается из дальнейшего рассмотрения.
Ограничения, не являющиеся активными по отношению к
дополняющим планам анализируемого подмножества, исключаются из соответствующей ему системы ограничений.
Безальтернативным переменным присваиваются допустимые значения. Это сразу же сокращает мощность рассматриваемого подмножества вариантов и тем самым сужает область поиска решения задачи. Кратность такого сокращения равна количеству безальтернативных переменных. Но при этом необходимо учитывать возможный «побочный эффект»: значение безальтернативной переменной, являющееся единственным допустимым для одного ограничения, может оказаться недопустимым
для другого ограничения частной модели. Поэтому после присваивания значений безальтернативным переменным необходимо реализовать повторный цикл анализа данного подмножества
вариантов.
206
Свойства подмножества вариантов решения задачи определяются свойствами неравенств, входящих в соответствующую
этому подмножеству систему ограничений.
Укрупнено свойства k-го подмножества вариантов можно
сформулировать в виде трёх следующих высказываний:
1) Если выполняется условие
min g jk ( x)  b jk ; j  J k ,
xGk
то j -у ограничению системы (6.4) не удовлетворяет ни
один из планов подмножества Gk . Следовательно, данное подмножество не содержит допустимых планов.
2) Если выполняется условие
max g jk ( x)  b jk ; j  J k ,
xGk
то j -у ограничению системы (6.4) удовлетворяет любой из планов подмножества Gk . Следовательно, это ограничение не является активным по отношению к планам данного подмножества
вариантов и может не учитываться при исследовании G k .
3) Если для некоторого подмножества Gk  Gk выполняется условие
min g jk ( x)  b jk  min g jk ( x) ; j  J k ,
xGk
xGk
то из всех планов подмножества G k j -у ограничению системы (6.4) могут удовлетворять лишь те, которые принадлежат
совокупности
Gk  Gk \ Gk .
В этом случае подмножество G k целесообразно заменить
имеющим меньшую мощность подмножеством G k вариантов
решения задачи. Если подмножество G k может быть выделено
в G k путём фиксации значений некоторых из переменных
xi , i  I k , то эти значения целесообразно присоединить к частичному плану подмножества G k .
207
Более детально свойства k -го ( k  1,  ) подмножества
вариантов решения комбинаторной задачи формулируются в
виде четырех следующих утверждений.
Утверждение 1. Подмножество G k не содержит допустимых планов, если для некоторого ограничения j  J k выполняется условие:
( I 2jk  ) & (b jk  0)  ( I 2jk  ) & ( s (jk2)  b jk ) .
Утверждение 2. Ограничение j  J k не является активным по отношению к планам подмножества G k , если для него
выполняется условие:
( I 3jk  ) & (b jk  0)  ( I 3jk  ) & ( s (jk3)  b jk ) .
Утверждение 3. Если I 2jk   ( j  J k ) и для некоторого i   I 2jk выполняется условие
s (jk2)  b jk  s (jk2)  a ji ,
то из дополняющих планов подмножества G k допустимыми
могут быть лишь те, в которых
i  I 2jk (i ) xi  1.


Утверждение 4. Если I 3jk   ( j  J k ) и для некоторого i   I 3jk выполняется условие:
( I 2jk  ) & (0  b jk  a ji )  ( I 2jk  ) & ( s (jk2)  b jk  s (jk2)  a ji )
,
то из дополняющих планов подмножества G k допустимыми
могут быть лишь те, в которых
i  I 3jk (i ) xi  0 .


Процедура анализа k -го подмножества вариантов решения линейной комбинаторной задачи заключается в последовательной проверке выполнения условий каждого из сформулированных утверждений для всех ограничений системы (6.4). В за208
висимости от результатов этой проверки в цикле анализа осуществляется то или иная последовательность действий.
1) Если для некоторого ограничения j  J k выполняется
условие утверждения 1, подмножество G k исключается из
дальнейшего рассмотрения.
2) Ограничения j  J k , для которых выполняется условие
утверждения 2, удаляются из системы (6.4), а их номера – из состава множества J k . Скорректированное таким образом множество номеров ограничений, активных по отношению к дополняющим планам подмножества вариантов Gk , будем, как и прежде, обозначать символом J k* .
3) Если для некоторого i  I 2jk ( j  J k* ) выполняется
условие
утверждения 3, то независимым переменным
xi , i  I (i) присваиваются значение единицы. Эти значения
2
jk
подставляются во все ограничения j  J k* , после чего осуществляется повторный цикл анализа k -го подмножества вариантов.
4) Если для некоторого i  I 3jk ( j  J k* ) выполняется
условие
утверждения 4, то независимым переменным
xi , i  I (i) присваиваются значения нуля. Эти значения под3
jk
ставляются во все ограничения j  J k* , после чего осуществляется повторный цикл анализа подмножества G k .
Проверку выполнения условия утверждения 3 для очередного j -го ограничения ( j  J k* ) рекомендуется начинать, рассматривая в качестве a ji минимальный (отрицательный) коэффициент функции g jk (x) :


a ji  min a ji ; i  I 2jk .
Если условие данного утверждения при этом не выполняется, то оно не будет выполнятся и для других возможных зна-
209
чений a ji  . В противном случае путем последовательного перебора следует определить максимальный из отрицательных коэффициентов функции g jk (x), который при подстановке вместо a ji  удовлетворяет неравенству
s (jk2)  a ji  b jk .
Именно этот коэффициент целесообразно использовать в
дальнейшем в качестве величины a ji  :


a ji  max a ji : (i  I 2jk ) & ( s (jk2)  a ji  b jk ) .
Выполнение условия утверждения 4 для очередного j -го
ограничения ( j  J k* ) первоначально проверяется для случая,
когда в качестве a ji выступает максимальный (положительный)
коэффициент функции g jk (x) :


a ji  max a ji ; i  I 3jk .
Если условие данного утверждения при этом не выполняется, то они не будут выполняться и для других возможных значений a ji  . В противном случае путем последовательного перебора определяется минимальный из положительных коэффициентов функции g jk (x), который при подстановке вместо a ji 
удовлетворяет неравенству
s 2jk  a ji  b jk .
В дальнейшем этот коэффициент используется в качестве
величины a ji  :


a ji  min a ji : (i  I 3jk ) & ( s (jk2)  a ji  b jk ) .
Такой выбор параметров a ji и a ji обеспечивает отсечение от G k наибольших по мощности подмножеств вариантов,
не содержащих допустимых планов.
210
Процедура анализа k -го подмножества вариантов решения задачи (6.3)–(6.4) прекращается, если:
а) оказывается, что анализируемое подмножество G k не
содержит допустимых планов;
б) множество J k* номеров ограничений, активных по отношению к планам данного подмножества, становится пустым;
в) в последнем цикле анализа ни одной из переменных
xi , i  I k не присваиваются фиксированные значения.
Схема алгоритма анализа подмножества вариантов представлена на рис. 6.1.
Блок WDA формирует рабочий массив исходных данных,
необходимых для выполнения процедуры анализа k -го подмножества вариантов. Он содержит:
– подмножество J k номеров ограничений, активных по
отношению к планам подмножества Gk ;
– подмножества I 2jk и I 3jk , j  J k номеров переменных,
входящих в ограничения частной модели с отрицательными и
положительными коэффициентами соответственно;
–
набор
векторов
коэффициентов
ограничений
a ji i  I jk , j  J k ;




– вектор свободных членов ограничений b jk j  J k .
Блоки P1 , P 2 , P 3 и P 4 реализуют унифицированные
процедуры последовательной проверки условий утверждений 1–
4 для каждого ограничения частной модели, соответствующей
подмножеству вариантов Gk . Результаты этой проверки отображаются значениями параметров U 1 , U 2 , U 3 и U 4 , которые
используются как показатели выполнения или невыполнения
условий того или иного утверждения.
211
Начало
WDA
P1
Да
U1=1
Нет
P2
Да
U2=1
Нет
DJ
Нет
J k*  
Да
P3
Да
U3=1
Нет
F1
P4
Да
I 5jk (r )  
Да
U4=1
Нет
Нет
WRA
F0
Конец
Рис. 6.1. Схема алгоритма анализа подмножества вариантов решений экстремальной комбинаторной задачи
212
Если для некоторого ограничения анализируемой системы
блок P1 устанавливает факт выполнения условия первого
утверждения, то U 1  1 , в противном случае U 1  0 . При
U 1  1 процедура анализа завершается, поскольку анализируемое подмножество вариантов не содержит допустимых планов,
и управление передается блоку вывода результатов анализа
WRA . При U 1  0 активизируется блок P 2 , осуществляющий
проверку выполнения условия утверждения 2.
Если для некоторого ограничения выполняется условие
второго утверждения, то U 2  1 , в противном случае U 2  0 .
Все ограничения, для которых U 2  1 , исключаются из системы
как утратившие свойство активности по отношению к планам
подмножества Gk . По мере обнаружения таких ограничений
блок DJ удаляет их номера из состава множества J k , после
чего каждый раз проверяется наличие в нем значащих элементов. Если оказывается, что J k*   , процедура анализа прекращается и управление передается блоку вывода результатов анализа WRA . В противном случае инициируется блок P 3 , который проверяет выполнение условия утверждения 3.
Если для некоторого ограничения рассматриваемой системы выполняется условие третьего утверждения, то U 3  1 , в
противном случае U 3  0 . При U 3  1 блок F 1 присваивает
безальтернативным переменным значение единицы, производит
соответствующие преобразования анализируемой системы
ограничений и передает управление блоку P1 для повторного
цикла анализа преобразованной модели. При U 3  0 активизируется блок P 4 , проверяющий выполнение условия утверждения 4.
Если для некоторого ограничения выполняется условие
четвертого утверждения, то U 4  1 , в противном случае
U 4  0 . При U 4  1 и I 3jk (i)   инициируется блок F 0 , который присваивает безальтернативным переменным значение
нуля, производит соответствующие преобразования анализиру-
213
емой системы ограничений и передает управление блоку P1 для
повторного цикла анализа преобразованной модели. При
U 4  0 или U 4  1 , но I 3jk (i)   , процедура анализа подмножества вариантов Gk завершается и управление передается
блоку вывода результатов WRA .
6.1.4 Структура алгоритма
В общем случае на каждом этапе решения задачи (6.1)–
(6.2) согласно алгоритму направленного перебора вариантов
выполняются следующие действия.
1) Выбор подмножества вариантов, подлежащего разбиению.
Стремлению отыскать оптимальный план за минимальное
количество шагов алгоритма в наибольшей степени отвечает
следующее правило выбора подмножества вариантов для дальнейшей детализации: выбирается то подмножество, разбиение
которого приводит к появлению нового подмножества, обладающего наивысшей (среди всех новых подмножеств) оценкой
целевой функции.
Пусть  (Gk xi  p) – оценка целевой функции, вычисленная на множестве вариантов G k при условии, что переменной xi , i  I k присвоено значение p  0, 1.
Тогда сформулированное выше правило можно выразить
следующим образом: для дальнейшего разбиения выбирается
подмножество вариантов Gk * , 1  k *   , такое что


max  (Gk * xi*  0),  (Gk * xi*  1); i *  I k * 


 max  (Gk xi  0),  (Gk xi  1); k  1,  ; i  I k .
Может оказаться, что на рассматриваемом этапе решения
задачи существует несколько подмножеств вариантов, на кото-
214
рых наибольшие из оценок  (Gk xi  p), p  0, 1, i  I k
одинаковы и равны максимальному значению


 max  max  (Gk xi  0);  (Gk xi  1); i  I k ; k  1,  .
*
Пусть K – множество номеров таких подмножеств:
K *   k : (1  k   ) & max{ (G k xi  0),  (Gk xi  1); i  I k }   max  
.
В этом случае для дальнейшего разбиения целесообразно
выбрать такое подмножество Gk * , k *  K * , в планах которого
количество незафиксированных переменных минимально:
mk *  min mk ; k  K * .


Такой принцип выбора подмножества вариантов отвечает
стремлению достичь конечного результата вычислений за минимальное количество шагов алгоритма.
Использование сформулированного выше правила в некоторых случаях может потребовать неоправданно больших объемов вычислений, связанных с определением оценок целевой
функции для всех подмножеств вариантов и различных значений незафиксированных ранее независимых переменных. Поэтому более практичным представляется следующее правило:
для дальнейшего разбиения выбирается такое подмножество
вариантов Gk * , 1  k *   , которому соответствует максимальная оценка целевой функции:


 (Gk )  max  (Gk ) ; k  1,  .
*
При наличии нескольких подмножеств, на которых оценка
целевой функции принимает максимальное значение

 max  max  (Gk ) ;

k  1,  ,
для дальнейшего разбиения выбирается, как и прежде,
подмножество Gk * , k *  K * с минимальным количеством mk *
незафиксированных переменных. Здесь
K *   k : (1  k   ) & [ (Gk )   max ]  .
215
2) Выбор независимой переменной, значения которой
подлежат фиксации.
Для выбора переменной xi * , i*  I k * , которой на данном
этапе решения задачи присваиваются конкретные значения, целесообразно воспользоваться следующим правилом: наибольшая из величин  (Gk * xi *  p), p  0, 1 должна быть максимальной среди всех оценок целевой функции, вычисленных
на множестве вариантов G k * при поочередной фиксации значений переменных xi , i  I k * :


max  (Gk * xi*  0),  (Gk * xi*  1) 

 max  (Gk * xi  0),  (Gk * xi  1); i  I k *
.
Сформулированное правило предусматривает реализацию
весьма трудоемкой процедуры, заключающейся в последовательном вычислении 2 mk * оценок целевой функции. Поскольку
в процессе разбиения подмножества вариантов решения задачи
максимизации соответствующая ему оценка целевой функции
монотонно не возрастает, указанную процедуру можно ограничить установлением такой переменной xi * ; i*  I k * , для которой выполняется равенство:
max  (Gk * xk *  0),  (Gk * xk *  1)   (Gk * ) .
Нетрудно убедиться в том, что переменная xi * , удовлетворяющая этому равенству, удовлетворяет также и сформулированному выше правилу выбора.
Если вычисления оценок  Gk * xi  p , p  0, 1 ,


i  I k * требует чрезмерно больших затрат машинного времени,
то для выбора независимой переменной, значения которой подлежат фиксации на данном этапе детализации подмножества
Gk * , можно воспользоваться более простым правилом. Согласно
этому правилу в качестве такой переменной выбирается любая
216
из переменных xi * , i*  I 0 k * , которая входит в целевую функцию f k * ( x) с максимальным коэффициентом:
ci*  max ci ; i  I 0 k * .
Это правило наиболее приемлемо для случая, когда оценка целевой функции на рассматриваемом подмножестве вариантов G k * вычисляется без учета необходимых условий существования допустимых планов.
3) Разбиение подмножества вариантов G k * .
Путем фиксации значений выбранной переменной xi*
подмножество G k * разбивается на два непересекающихся подмножества: Gk0* и Gk1* . В планах первого из них xi*  0, в планах второго xi*  1.
4) Анализ подмножеств Gk0* и Gk1* .
Анализ вновь полученных подмножеств вариантов Gk0* и
Gk1* осуществляется последовательно для них согласно изложенной выше процедуре.
5) Проверка допустимых планов на оптимальность.
*
Пусть x – допустимый план, полученный к концу данного этапа решения задачи, а * – количество выделенных в G
подмножеств вариантов, оставшихся в поле рассмотрения после
анализа Gk0* и Gk1* . Предположим, что все подмножества вариантов пронумерованы числами натурального ряда от 1 до *
включительно.
Можно утверждать, что найденный допустимый план является оптимальным решением задачи (6.1)–(6.2), если значение
*
целевой функции f ( x ) не меньше максимальной из ее оценок, соответствующих выделенным подмножествам вариантов:
217
f ( x * )  max{ (Gk ), k  1, * } .
(6.5)
Нахождением оптимального плана x * завершается процесс решения экстремальной комбинаторной задачи. Если на
рассматриваемом этапе решения задачи условие (6.5) не выполняется, необходимо реализовать следующий этап вычислительного процесса.
Начинать решение целесообразно с анализа полного множества G вариантов. В определенных случаях это позволяет
априорно установить факт несовместности системы ограничений (6.2) или отсечь от G подмножество вариантов, не содержащее допустимых планов.
Укрупненная схема алгоритма решения экстремальных
комбинаторных задач представлена на рис. 6.2.
Любое подмножество вариантов решения задачи определяется собственным частичным планом. Для представления частичного плана каждого подмножества вариантов Gk , k  1, 
удобно использовать m -мерный вектор, в котором позиции с
номерами i  I k0 заполнены нулями, i  I k1 – единицами, а
i  I k  любыми символами, отличными от 0 до 1.
Для хранения таких векторов в памяти компьютера организуется специальный массив (файл) допустимых планов
MDP, в котором, наряду с частичными планами выделенных
подмножеств вариантов, целесообразно фиксировать соответствующие им оценки целевой функции.
С целью реализации объяснительных способностей интеллектуальной системы принятие решений в массиве MDP
хранятся также упорядоченные наборы номеров независимых
переменных, отражающие последовательность присваивания
аргументам конкретных значений в процессе формирования частичных планов каждого из выделенных подмножеств вариантов.
218
Начало
WD
2
1
A(GA)
V(Gk*)
D(GA)=1
Да
Да
Да
5
Нет
mk*=0
GA=G
Z(GA)
Нет
Нет
GA  Gk1
S(GA)
V(xi)
5
Нет
4
Да
Нет
xi*=0
3
GA  Gk0
Да
4
*  0
Нет
1
Да
5
M(Gk*)
xi*=1
WR
2
3
Конец
Рис. 6.2 Укрупненная схема алгоритма решения экстремальных
комбинаторных задач
Блок WD формирует рабочий массив с исходными данными, описывающими задачу (6.1)–(6.2). К ним относятся следующие наборы данных:
– вектор ci ; i  I 0  коэффициентов целевой функции
(6.1);
– совокупность
 a ; i  I  ; j  1, n  векторов коэфji
j
фициентов ограничений системы (6.2);
219


– вектор b j ; j  1, n правых частей ограничений системы
(6.2).
Блок А(G A ) реализует унифицированную процедуру анализа множества G A вариантов решения задачи. В качестве G A
может выступать полное множество вариантов G или любое из
подмножеств Gk0* и Gk1* , образованных вследствие разбиения
некоторого
предшествующего
подмножества
вариантов
Gk * , 1  k *   .
Результаты анализа множества G A определяют значение
параметра D(G A ) , который используется как показатель наличия (или отсутствия) допустимых планов в анализируемом подмножестве. Если факт отсутствия таких планов в G A не установлен, то D(G A )  1 ; в противном случае D(G A )  0 .
При D(G A )  1 блок Z (G A ) вычисляет оценку целевой
функции на G A , а блок S (G A ) заносит ее вместе с частичным
планом данного подмножества вариантов в массив допустимых
планов MDP .
Если в качестве анализируемого подмножества G A выступало подмножество Gk0* , переменной xi * , i*  I k * присваивается значение единицы. Далее блок M (Gk * ) преобразует математическую модель, соответствующую подмножеству вариантов G k * , к виду, адекватному подмножеству Gk1* . После этого
подмножества Gk1* подвергается анализу в блоке A(G A ) .
Если же в качестве анализируемого подмножества G A
выступало полное подмножество вариантов G или подмножество Gk1* , то после занесения его частичного плана и оценки
целевой функции в массив MDP инициируется блок V (Gk * ) .
220
Блок V (Gk * ) реализует процедуру выбора подмножества
вариантов решения задачи для дальнейшего разбиения среди тех
подмножеств, частичные планы которых вместе с оценками целевой функции зафиксированы в массиве допустимых планов
MDP .
Если применяемое правило выбора предусматривает использование оценок  Gk xi  p ; p  0, 1; i  I k ; k  1,  ,
то на данный блок возлагается функция преобразования исходной модели (6.1)–(6.2) к виду, адекватному каждому из рассматриваемых подмножеств вариантов, с последующим вычислением таких оценок. Информация, касающаяся выбранного для разбиения подмножества вариантов G k * , удаляется из массива допустимых планов MDP .
После выбора подмножества вариантов, подлежащего
разбиению, проверяется полнота его частичного плана. Если все
m независимых переменных имеют в частичном плане данного
подмножества конкретные значения и, следовательно, mk *  0 ,
то этот план является оптимальным решением x * задачи (6.1)–
(6.2). В этом случае инициируется блок вывода результатов
WR , поскольку в дальнейших вычислениях нет необходимости.
Если же mk *  0 , то инициируется блок V ( xi* ) , реализующий процедуру выбора независимой переменной xi * , i*  I k * ,
которой на данном этапе решения задачи присваиваются конкретные значения.
Блок V ( xi* ) осуществляет преобразование общей модели
(6.1)–(6.2) к виду, адекватному подмножеству вариантов G k * ,
если это не было сделано ранее блоком V (Gk * ) . При необходи-


мости он вычисляет оценки целевой функции  Gk * xi  p ;
p  0, 1; i  I k , а также выполняет прочие операции, преду*
сматриваемые используемым правилом выбора переменной xi* .
221
Выбранной переменной первоначально присваивается
значение нуля: xi*  0 . После этого блок M (Gk * ) преобразует
математическую модель, соответствующую подмножеству вариантов G k * , к виду, адекватному подмножеству Gk0* . Далее
подмножество Gk0* подвергается анализу в блоке A(G A ) .
Предположим, в процессе анализа некоторого множества
вариантов G A установлен факт отсутствия допустимых планов
и, следовательно, D(G A )  1 . Если в качестве анализируемого
множества G A выступало полное множество вариантов G , то
это означает, что система ограничений (6.2) при условии бивалентности независимых переменных несовместна и рассматриваемая задача не имеет решений. В этом случае инициируется
блок вывода результатов WR , поскольку дальнейшие вычисления не имеют смысла.
Если факт отсутствия допустимых планов установлен для
подмножества вариантов Gk1* , то проверяется наличие резервных частичных планов в массиве MDP . Если данный массив
пуст *  0 , это также свидетельствует об отсутствии решений
задачи (6.1)–(6.2) при бивалентных независимых переменных. В
противном случае *  0 инициируется блок V (Gk * ) , реали-




зующий процедуру выбора одного из выделенных подмножеств
вариантов для дальнейшего разбиения.
Если не содержащим допустимые планы оказывается
подмножество вариантов Gk0* (когда GA  G и GA  G1k * ),
инициируется формирование математической модели, адекватной подмножеству Gk1* .
Блок WR выводит следующие результаты вычислений:
– оптимальные и допустимые планы с указанием последовательности присваивания независимым переменным конкретных значений;
222
– сообщения об отсутствии решений модели (6.1)–(6.2),
содержащие списки номеров ограничений, которые не могут
быть выполнены;
– текстовую информацию, поясняющую логику вычислительного процесса и интерпретирующую полученные результаты в терминах физической постановки задачи, и др.
Описанный алгоритм решения экстремальных комбинаторных задач предусматривает неоднократное выполнение следующих процедур:
– анализ подмножества вариантов;
– вычисление оценки целевой функции;
– выбор подмножества вариантов для разбиения;
– выбор независимой переменной для присваивания значений;
– преобразование математической модели к виду, адекватному конкретному подмножеству вариантов.
При программной реализации алгоритма перечисленные
процедуры целесообразно унифицировать и представить в виде
отдельных подпрограмм.
Приведенные правила выбора подмножеств вариантов для
дальнейшего разбиения в сочетании с отсеиванием подмножеств, не содержащих допустимых планов, и присваиванием
единственных допустимых значений безальтернативным независимым переменным обеспечивает целенаправленность поиска
оптимального решения задачи экстремальных комбинаторных
задач.
6.2 Алгоритм решения экстремальных комбинаторных
задач с коэффициентами из множества {–1, 1}
Канонические формы математических моделей задач планирования передвижения летательных аппаратов при подготовке к вылету, планирования технологических процессов подготовки к вылету заданного количества летательных аппаратов за
минимальное время и планирования работы исполнителей технологических операций обладают рядом особенностей, позво-
223
ляющих упростить некоторые процедуры, предусмотренные алгоритмом направленного перебора вариантов.
Эти особенности заключаются в следующем:
1) коэффициенты системы ограничений равны либо –1,
либо +1:
(j  1, n)(i  I j )( a ji {1, 1}) ;
2) правые части ограничений также имеют значения –1
или +1:
(j  1, n)(b j {1, 1}) ;
3) коэффициенты целевых функций f 2 ( x) , f 3 ( x) , f 4 ( x)
и f 5 ( x) в задаче планирования передвижения летательных аппаратов при подготовке к вылету, целевой функции f (x) в задаче планирования технологических процессов подготовки к
вылету заданного количества летательных аппаратов за минимальное время, а также целевой функции f 2 ( x) в задаче планирования работы исполнителей технологических операций являются отрицательными числами:
(i  I 0 )(ci  0) ;
4) коэффициенты целевой функции f1 ( x) в задаче планирования работы исполнителей технологических операций
равны –1:
(i  I 0 )(ci  1) .
Упрощения алгоритмических процедур, обусловленные
перечисленными особенностями математических моделей указанных задач, касаются, в основном, вычисления оценок целевых функций и проверки выполнения условий утверждений, лежащих в основе анализа подмножеств вариантов.
Поскольку каноническая форма (6.1)–(6.2) предусматривает максимизацию целевой функции, а коэффициенты отмеченных выше целевых функций являются отрицательными числами, оценка  (Gk ) каждой из них на k -м подмножестве вариантов решения комбинаторной задачи приравнивается кон224
станте c1k , определяемой частичным планом данного подмножества:
 (Gk )  c1k .
Оценка целевой функции f1 ( x) на k -м подмножестве
вариантов решения задачи планирования работы исполнителей
технологических операций равна количеству искомых переменных, получивших в частичном плане подмножества Gk значение единицы:
 (Gk )  I 01k .
Приведенные упрощенные формулы вычисления  (Gk )
не относятся к задаче планирования передвижения летательных
аппаратов при подготовке к вылету в случае использования целевой функции f1 ( x) , коэффициенты которой положительны.
Оценка этой функции вычисляется по правилам, приведенным в
пункте 6.1 для линейных комбинаторных задач общего вида
(6.1)–(6.2).
Формальные выражения утверждений, лежащих в основе
процедуры анализа подмножеств вариантов решения комбинаторной задачи, приобретают следующий вид.
Утверждение 1. Подмножество G k не содержит допустимых планов, если для некоторого ограничения j  J k выполняется условие:
[(   i  I jk )( a ji  1)] & (b jk  0)  [( i  I jk )( a ji  1)] & ( I jk  b jk )
.
Утверждение 2. Ограничение j  J k не является активным по отношению к планам подмножества G k , если для него
выполняется условие:
[(  i  I jk )( a ji  1)] & (b jk  0)  [( i  I jk )( a ji  1)] & ( I jk  b jk )
.
225
Утверждение 3. Если для некоторого ограничения j  J k
выполняется условие:
[( i  I jk )(a ji  1)] & (b jk  0) ,
то из дополняющих планов подмножества G k допустимыми
могут быть лишь те, в которых
(i  I jk )( xi  1) .
Утверждение 4. Если для некоторого ограничения j  J k
выполняется условие:
[( i  I jk )(a ji  1)] & (b jk  0) ,
то из дополняющих планов подмножества G k допустимыми
могут быть лишь те, в которых
(i  I jk )( xi  0) .
Структура алгоритма решения перечисленных функциональных задач, правила проверки допустимых планов на оптимальность, принципы организации вычислительного процесса и
признаки его завершения аналогичны тем, что были рассмотрены ранее в пункте 6.1 в отношении линейных комбинаторных
задач общего вида (6.1)–(6.2).
6.3 Алгоритм решения экстремальных комбинаторных
задач с коэффициентами, равными единице
Более существенные упрощения алгоритмических процедур возможны при решении задачи планирования технологических процессов подготовки к вылету максимального количества
летательных аппаратов за заданное время, поскольку каноническая форма ее математической модели обладает следующими
особенностями:
1) коэффициенты целевой функции равны единице:
(i  I 0 )(ci  1) ;
2) коэффициенты системы ограничений равны единице:
(j  1, n)(i  I j )( a ji  1) ;
226
3) правые части ограничений равны единице:
(j  1, n)(b j  1) .
Это позволяет представить каноническую форму данной
задачи в следующем виде: максимизировать целевую функцию
f ( x)  xi  max
(6.6)

iI 0
при соблюдении ограничений
g j ( x)   xi  1;
j  1, n ;
(6.7)
iI j
xi {0, 1} , i  1, m .
Задача (6.6)–(6.7), приведенная в соответствие k -у подмножеству вариантов, формулируется следующим образом:
максимизировать целевую функцию
f k ( x)   xi  I 01k
iI 0 k
при соблюдении ограничений
g jk ( x)   xi  b jk ; j  J k ,
iI jk
где x  ( xi ; i  I k ) ; xi  0, 1; i  I k .
1
Здесь I 0k – количество независимых переменных, получивших в частичном плане подмножества G k значение единицы;
b jk  свободный член j -го ограничения системы (6.7),
уменьшенный на количество независимых переменных, которые
входили в это ограничение и получили в частичном плане подмножества G k значение единицы:
b jk  1  I 1jk ; j  J k ;
J k – множество номеров ограничений системы (6.7), активных по отношению к планам подмножества вариантов G k .
227
Оценка  (Gk ) целевой функции на k -м подмножестве
вариантов решения задачи (6.6)–(6.7) вычисляется как сумма
двух составляющих: константы
I 1jk , определяемой частичным
планом данного подмножества, и приращения  (Gk ) , равного
количеству независимых переменных, образующих дополняющие планы G k :
 (Gk )  I 1jk   (Gk )  I 1jk  I jk .
Формальные выражения утверждений, лежащих в основе
процедуры анализа подмножеств вариантов решения задачи
(6.6)–(6.7), приобретают следующий вид.
Утверждение 1. Подмножество G k не содержит допустимых планов, если для некоторого ограничения j  J k выполняется условие:
(b jk  0) .
Утверждение 2. Ограничение j  J k не является активным по отношению к планам подмножества G k , если для него
выполняется условие:
( I jk  ) & (b jk  0)  ( I jk  1) & (b jk  1) .
Утверждение 3 не рассматривается, поскольку
(  k  1,  )(  j  J k )( I 2jk  ) .
Утверждение 4. Если для некоторого ограничения j  J k
выполняется условие:
( I jk  ) & (b jk  0) ,
то из дополняющих планов подмножества G k допустимыми могут быть лишь те, в которых
(i  I jk )( xi  0) .
Структура алгоритма решения задачи (6.6)–(6.7), правила
проверки допустимых планов на оптимальность, принципы ор-
228
ганизации вычислительного процесса и признаки его завершения в основном аналогичны тем, что были рассмотрены ранее в
пункте 6.1 в отношении линейных комбинаторных задач общего
вида (6.1)–(6.2). Единственным отличием является то, что при
реализации алгоритма выполнение условия утверждения 3 не
проверяется.
229