Ограничение «старт-финиш» устанавливает границу для минимального времени задержки между началом одной задачи и окончанием другой. Ограничение «старт-старт» определяет минимальную задержку между началом двух операций.
Для каждой задачи в проекте i = 1,…,n, обозначим через xi — время начала, yi — время завершения. Пусть aij — будет минимально возможная задержка между началом задач j = 1,…,n и завершением i. Ограничения типа «старт-финиш» записываются в виде неравенств:
при этом хотя бы одно неравенство должно выполняться как равенство. Заметим, что мы подразумеваем 
для любого i. Если для некоторого j значение cij не задано, то полагаем 
. Теперь мы объединим все эти отношения в одно равенство вида
Кроме того, пусть cij будет минимально возможной задержкой между началом задач j и i. Будем снова считать, что 
, если не определена задержка между j и i. Запись ограничения «старт-старт» выглядит так
, 
Далее можно переписать как одно неравенство
Критерий оптимальности, который характеризует разброс времени завершения операций в проекте, определяется как
Теперь мы можем сформулировать задачу оптимизации единовременного завершения всех операций в проекте, в следующем виде
Далее задача (6) будет представлена в терминах тропической (идемпотентной) математики и полностью решена в компактной векторной форме.
2. Принятые обозначения и определения
2.1. Идемпотентное полуполе
Пусть 
— множество, замкнутое относительно двух ассоциативных и коммутативных операций: сложения 
и умножения 
, с нейтральными элементами: нулем 
и единицей 
. Сложение идемпотентно, что означает 
для любого 
. Умножение дистрибутивно относительно сложения и обратимо, то есть, для любого 
, где 
есть обратное число 
, которое удовлетворяет равенству 
. Таким образом 
образует группу по умножению, и структура (; ; ; ;
) является идемпотентным полуполем.
Возведение в целую степень определяется как обычно. Для любого
и целого p > 0, можно записать x0 = ; p = ;
= 
, и 
= ()p .
Далее для краткости не будем указывать знак умножения , как и в обычной математике.
Отметим, что идемпотентное сложение порождает частичный порядок ≤, такой, что 
только в том случае, если 
. Предполагается, что этот частичный порядок можно расширить до полного порядка на всем . Далее символы отношений и формулировки задач оптимизации рассматриваются в контексте этого порядка.
Например, полуполе Rmaz;+ имеет 
= max и = +, а так же нуль = 1 и единицу = 0. Для любого 
существует обратный элемент , который в обычных обозначениях совпадает с 
. Для любого , 
, степень 
соответствует арифметическому произведению 
. Порядок, порожденный идемпотентным сложением, соответствует естественному линейному порядку на R.
2.2 Алгебра матриц
Теперь рассмотрим матрицы над и обозначим множество матриц с m строками и n столбцами, как 
. Матрица, в которой все элементы равны , называется нулевой. Матрица регулярна по строкам (столбцам), если она не имеет нулевых строк (столбцов). Матрица регулярна, если она регулярна и по строкам и по столбцам.
Операции над матрицами определяются так же как и в обычной алгебре, при условии замены операторов на их идемпотентные аналоги. Для любой матрицы A, её транспонированная обозначается AT.
Для любой ненулевой матрицы 
= 
, введем мультипликативно-сопряженную (или просто сопряженную) матрицу 
с элементами 
если 
, и 
в противном случае, для любого 
и 
.
Квадратная матрица 
, которая на диагонали имеет и вне диагонали – , называется единичной и обозначается I. Для любой матрицы A, её след равен
Как обычно, матрица, которая состоит их одной строки (столбца) называется строчным (столбцевым) вектором. Обозначим множество столбцевых векторов порядка n как 
.
Вектор, у которого все компоненты равны , называется нулевым. Вектор считается регулярным, если у него нет нулевых элементов.
Пусть x — регулярный вектор-столбец и A — матрица. Не трудно заметить, что вектор 
регулярен только тогда, когда матрица регулярна по строкам. Точно так же вектор-строка 
регулярен только тогда, когда матрица регулярна по столбцам.
Для любого ненулевого вектора
, его мультипликативно-сопряженный вектор — это строчный вектор 
, где 
если 
и
в противном случае. Нетрудно проверить следующие свойства мультипликативно-сопряженных векторов.
Для любых двух регулярных векторов и 
одинакового размера, покомпонентное неравенство подразумевает 
и наоборот.
Для любого ненулевого вектора выполняется 
. Кроме того, если вектор регулярен, то 
.
Введем так же понятие собственного значения матрицы в терминах тропической математики. Если существует ненулевой вектор x такой, что выполняется равенство 
, то 
— собственное значение матрицы , а вектор — это её собственный вектор. Максимальное собственное число (в смысле порядка на ) называется спектральным радиусом матрицы , который вычисляется по формуле
(8)
Спектральный радиус любой матрицы
имеет экстремальное свойство
Введем так же функцию, которая вычисляет у матрицы число
При условии что 
, мы определим матрицу
при любом 
получим
Дана матрица 
, рассмотрим задачу нахождения регулярных векторов, которые будут удовлетворять неравенству:
Лемма 1. Пусть x — решение неравенства (10 ). Тогда выполняется следующие условия: 1.Если 
, тогда 
для любого регулярного вектора u. 2.Если 
, тогда не существует регулярного решения.
3. Just-in-time оптимизация проекта с использованием идемпотентной алгебры
Нужна помощь в написании статьи?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.
Рассмотрим задачу, записанную в форме (6) и заметим, что представление этой задачи в обычных терминах включает в себя только операции сложения и вычисления максимума. Поэтому ее можно представить в терминах полуполя Rmax;+. Нахождение минимума целевой функции является 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.