АЛГОРИТМЫ  УПРАВЛЕНИЯ  ПРОЕКТАМИ  НА  ОСНОВЕ  МОДЕЛЕЙ  И  МЕТОДОВ  ИДЕМПОТЕНТНОЙ  АЛГЕБРЫ

Пузиков  Александр  Юрьевич

магистр,  кафедра  системного  программирования,  математико-механический  факультет  Санкт-Петербургский  государственный  университет,  РФ,  г.  Санкт-Петербург

E-mail:  

1.Предварительные  сведения

Задачи  сетевого  планирования  возникают  на  производстве  при  попытках  организовать  проект,  который  оптимизирует  какие-либо  временные  характеристики  в  проекте,  при  различных  условиях,  которые  накладываются  на  порядок  выполнения  операций.  Будем  рассматривать  проект,  состоящий  из  n  операций,  которые  выполняются  при  ограничениях  типа  «старт-финиш»  и  «старт-старт».  Ограничение  «старт-финиш»  устанавливает  границу  для  минимального  времени  задержки  между  началом  одной  задачи  и  окончанием  другой.  Ограничение  «старт-старт»  определяет  минимальную  задержку  между  началом  двух  операций.

Для  каждой  задачи  в  проекте  i  =  1,…,n,  обозначим  через  x_i  —  время  начала,  y_i  —  время  завершения.  Пусть  a_ij  —  будет  минимально  возможная  задержка  между  началом  задач  j  =  1,…,n  и  завершением  i.  Ограничения  типа  «старт-финиш»  записываются  в  виде  неравенств:

при  этом  хотя  бы  одно  неравенство  должно  выполняться  как  равенство.  Заметим,  что  мы  подразумеваем    для  любого  i.  Если  для  некоторого  j  значение  c_ij  не  задано,  то  полагаем  .  Теперь  мы  объединим  все  эти  отношения  в  одно  равенство  вида

Кроме  того,  пусть  c_ij  будет  минимально  возможной  задержкой  между  началом  задач  j  и  i.  Будем  снова  считать,  что  ,  если  не  определена  задержка  между  j  и  i.  Запись  ограничения  «старт-старт»  выглядит  так

Далее  можно  переписать  как  одно  неравенство

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

Теперь  мы  можем  сформулировать  задачу  оптимизации  единовременного  завершения  всех  операций  в  проекте,  в  следующем  виде

Далее  задача  (6)   будет  представлена  в  терминах  тропической  (идемпотентной)  математики  и  полностью  решена  в  компактной  векторной  форме.

2. Принятые  обозначения  и  определения 

2.1. Идемпотентное  полуполе 

Пусть    —  множество,  замкнутое  относительно  двух  ассоциативных  и  коммутативных  операций:  сложения    и  умножения  ,  с  нейтральными  элементами:  нулем    и  единицей  .  Сложение  идемпотентно,  что  означает    для  любого  .  Умножение  дистрибутивно  относительно  сложения  и  обратимо,  то  есть,  для  любого    ,  где  есть  обратное  число    ,  которое  удовлетворяет  равенству  .  Таким  образом    образует  группу  по  умножению,  и  структура  (;  ;  ;  ;)  является  идемпотентным  полуполем.

Возведение  в  целую  степень  определяется  как  обычно.  Для  любого  и  целого  p  >  0,  можно  записать  x⁰  =  ;    ^p  =  ;  =    ,  и    =  ()^p  .

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

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

Например,  полуполе  R_maz;+  имеет  =  max  и    =  +,  а  так  же  нуль    =  1  и  единицу    =  0.  Для  любого    существует  обратный  элемент    ,  который  в  обычных  обозначениях  совпадает  с  .  Для  любого  ,  ,  степень    соответствует  арифметическому  произведению  .  Порядок,  порожденный  идемпотентным  сложением,  соответствует  естественному  линейному  порядку  на  R.

2.2                 Алгебра  матриц 

Теперь  рассмотрим  матрицы  над    и  обозначим  множество  матриц  с  m  строками  и  n  столбцами,  как    .  Матрица,  в  которой  все  элементы  равны  ,  называется  нулевой.  Матрица  регулярна  по  строкам  (столбцам),  если  она  не  имеет  нулевых  строк  (столбцов).  Матрица  регулярна,  если  она  регулярна  и  по  строкам  и  по  столбцам.

Операции  над  матрицами  определяются  так  же  как  и  в  обычной  алгебре,  при  условии  замены  операторов  на  их  идемпотентные  аналоги.  Для  любой  матрицы  A,  её  транспонированная  обозначается  A^T.

Для  любой  ненулевой  матрицы    =  ,  введем  мультипликативно-сопряженную  (или  просто  сопряженную)  матрицу    с  элементами    если  ,  и    в  противном  случае,  для  любого    и  .

Квадратная  матрица  ,  которая  на  диагонали  имеет    и  вне  диагонали  –  ,  называется  единичной  и  обозначается  I.  Для  любой  матрицы  A,  её  след  равен

Как  обычно,  матрица,  которая  состоит  их  одной  строки  (столбца)  называется  строчным  (столбцевым)  вектором.  Обозначим  множество  столбцевых  векторов  порядка  n  как  .

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

Пусть  x  —  регулярный  вектор-столбец  и  A  —  матрица.  Не  трудно  заметить,  что  вектор    регулярен  только  тогда,  когда  матрица    регулярна  по  строкам.  Точно  так  же  вектор-строка    регулярен  только  тогда,  когда  матрица    регулярна  по  столбцам.

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

Для  любых  двух  регулярных  векторов    и    одинакового  размера,  покомпонентное  неравенство    подразумевает    и  наоборот.

Для  любого  ненулевого  вектора  выполняется  .  Кроме  того,  если  вектор  регулярен,  то  .

Введем  так  же  понятие  собственного  значения  матрицы  в  терминах  тропической  математики.  Если  существует  ненулевой  вектор  x  такой,  что  выполняется  равенство  ,  то    —  собственное  значение  матрицы  ,  а  вектор    —  это  её  собственный  вектор.  Максимальное  собственное  число  (в  смысле  порядка  на  )  называется  спектральным  радиусом  матрицы  ,  который  вычисляется  по  формуле

  (8)

Спектральный  радиус  любой  матрицы  имеет  экстремальное  свойство

Введем  так  же  функцию,  которая  вычисляет  у  матрицы  число

При  условии  что  ,  мы  определим  матрицу 

при  любом    получим

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

Лемма  1.  Пусть  x  —  решение  неравенства    (10 ).  Тогда  выполняется  следующие  условия:  1.Если  ,  тогда    для  любого  регулярного  вектора  u.  2.Если  ,  тогда  не  существует  регулярного  решения.

3.  Just-in-time  оптимизация  проекта  с  использованием  идемпотентной  алгебры 

Рассмотрим  задачу,  записанную  в  форме    (6)   и  заметим,  что  представление  этой  задачи  в  обычных  терминах  включает  в  себя  только  операции  сложения  и  вычисления  максимума.  Поэтому  ее  можно  представить  в  терминах  полуполя  R_max;+.  Нахождение  минимума  целевой  функции  является  just-in-time  [2]  оптимизацией  проекта  в  терминах  управления  проектами.

Вначале  мы  представим  ограничения,  как  скалярные  равенства  и  неравенства

Если  использовать  матрично-векторные  обозначения

то  скалярные  ограничения  примут  форму

Кроме  того,  мы  перепишем  целевую  функцию  (5).  При  условии,  что  в  ,  целевая  функция  будет  выглядеть  как

Наконец,  объединяя  целевую  функцию  с  ограничениями,  получим  задачу

Решение  задачи  получено  в  [1]  в  следующем  виде.

Теорема  1 .  Предположим,  что  A  регулярна  и  C  матрица  с  .  Тогда  минимум  целевой  функции  равен    и  достигается  при

Далее  рассмотрим  задачу,  в  которой  нет  ограничений  типа  старт-старт,  то  есть

В  таком  случае  минимум  целевой  функции  достигается  при  регулярной  матрице    и  ,  и  при 

Список  литературы:

1.Krivulin  N.K.,  “Explicit  solution  of  a  tropical  optimization  problem  with  application  to  project  scheduling  in  Mathematical  Methods  and  Optimization  Techniques  in  Engineering,”  WSEAS  Press,  arXiv:1303.5457  [math.OC],  2013.

2.T’kind  V.  t  and  J.-C.  Billaut,  “Multicriteria  Scheduling:  Theory,  Models  and  Algorithms,”  Springer,  Berlin,  2006.