2.1. Сети с упорядоченными событиями
T(z) = ? Ds(Zs) (ZU)
s=1
Теорема 1. [2] T(z) - выпуклая функция z.
Задача. Определить {xis > 0, i = 1, n, s = 1, r }, удовлетворяющие условиям:
? xis = Wj, i = 1n (2.1.2)
seQi
и минимизирующие T(z).
Согласно теореме 1 это задача выпуклого программирования.
Рассмотрим применение приведенных выше общих результатов к задаче распределения дискретных ресурсов, когда количество ресурсов на каждой операции фиксировано. На практике такие задачи возникают при формировании календарных планов работы специализированных бригад. Обозначим, как и раньше, ti - продолжительность i-ой операции, aiJ - фиксированное количество ресурсов j-го вида на i-ой операции. Будем обозначать множество независимых операций комплекса через вектор x = (xb x2, ... , xn), где xi = 1, если i-ая операция принадлежит множеству, и xi = 0 в противоположном случае. Вектор x, удовлетворяющий условиям
?Nj, j = 1m, (2.1.3)
i=1
будем называть допустимым вектором. Пусть x1, x2, ... , xq - множество допустимых векторов. Обозначим через us продолжительность интервала, в котором выполняются операции, соответствующие вектору xs.
Задача. Определить us, s = 1,q , удовлетворяющие условиям
? xSus J=1,n
seQi
q
и минимизирующие T = ? us .
s=1
Это задача линейного программирования, в которой матрица ограничений задается косвенно, в виде (2.1.3). Пусть x1, x2, ...
, xn - базисные вектора некоторого начального решения. Обозначим через у1 вектор x, для которого x1 = 1, Xj = 0, j Ф i. Выразим у1 через базисные векторы. ПустьУ1 =Ё cijxj (2.1.4)
j=1
и обозначим b1 = ^ c1j .
j=1
Рассмотрим следующую вспомогательную задачу: определить вектор x, удовлетворяющий (2.1.3) и максимизирующий
С = S x1b1. (2.1.5)
1 =1
Если в оптимальном решении этой задачи c < 1, то начальное решение оптимально. В противном случае оптимальное решение вспомогательной задачи определяет вектор, который нужно ввести в базис согласно процедуре симплекс-метода.
Замечание 1. Так как допустимый вектор определяет множество независимых операций, то задача (2.1.3), (2.1.5) решается для каждого множества Rs независимо.
Замечание 2. Для исключения зацикливания процедуры следует запоминать вектора, исключаемые из базиса в случае, если им соответствует u = 0, до тех пор, пока не будет исключен вектор со значением u > 0.
Задача (2.1.3), (2.1.5) является задачей линейного целочисленного программирования с переменными, принимающими значения 0, 1, и в общем случае не имеет эффективных методов
решения. Рассмотрим несколько практически важных случаев, когда задача (2.1.3), (2.1.5) принимает более простой вид.
I) Пусть операции разбиты на m типов так, что операции j-го типа выполняются ресурсами j-го вида в количестве ai (i = 1, n). Обозначим через Rjs множество операций j-го типа, которые могут выполняться в s-ом интервале. В этом случае задача (2.1.3), (2.1.5) разбивается на несколько независимых подзадач, - для каждого Rjs Ф 0:
cjs = ? bixi ® max ,
ieRj,
(2.1.6)
? ajXj < Nj.
ieRj,
Задача (2.1.6) известна как «задача о ранце» и решается достаточно эффективно методом динамического программирования.
Начальное решение оптимально, если Cjs < 1, j = 1,m , s = 1,r
Cjs = 0, если RJs = 0.
Задача (2.1.6) решается элементарно, если все ai = 1. Очевидно, в этом случае cJs равно сумме Nj положительных максимальных bi (или просто сумме всех положительных bi, если их число меньше, чем Nj).
Пример 2.1.
Рассмотрим комплекс из пяти операций (рис. 2.1), данные о которых приведены в таблице 3. (номера операций указаны у дуг на рисунке).Таблица 3. i 1 2 3 4 5 ti 2 4 6 5 2 ai 6 5 4 4 6
Рис. 2.1.
Все операции выполняются ресурсами одного вида, количество которых равно N = 11.
1. Получение начального решения. Для получения начального решения мы применим эвристический алгоритм, согласно которому приоритет имеет операция с меньшим значением позднего момента
начала tj1 (это правило называется распределением по степени
критичности операций). В случае одинаковых tf начинаем любую
операцию. Значения t^ приведены ниже. i 1 2 3 4 5 t" 0 1 1 2 5 Применяя вышеприведенное эвристическое правило, получим следующее решение:
x1 = (1, 1, 0, 0, 0), uj = 2 x2 = (0, 1, 1, 0, 0), u2 = 2 x3 = (0, 0, 1, 1, 0), u3 = 4 x4 = (0, 0, 0, 1, 1), u4 = 1 x5 = (0, 0, 0, 0, 1), u5 = 1
Продолжительность комплекса составляет
T = J us = 10.
s=1
Выразим векторы y1 через базисные векторы:
У5 = x5, b5 =1
y4 = x4 - x5, b4 = 0
y3 = x3 - x4 + x5, b3 = 1
y2 = x2 - x3 + x4 - x5, b2 = 0
y1 = x1 - x2 + x3 - x4+ x5, bj = 1
Получаем следующую задачу о ранце:
xi + x3 + x5 ® max , 6x1 + 4x3 + 7x5 < 1. Задача разделяется на три независимых подзадачи:
x1 + x3 ® max , 6x1 + 4x3 < 11; x3 ® max , 4x3 < 11;
(2.1.9)
x3 + x5 ® max , 4x3 + 7x5 < 11.
Оптимальное решение задачи (2.1.7): x1 = x3 = 1, задачи (2.1.8): x3 = 1, задачи (2.1.9): x3 = x5 = 1. Решение задач (2.1.7) и (2.1.9) имеют одну и ту же величину с = 2.Поэтому вводим в базис любой вектор, например
x6 = (0, 0, 1, 0, 1) = y3 + y5 = x3 - x4 + 2x5. Определяем согласно процедуре симплекс-метода
u3.
u5u6 = min
12
и исключаем вектор х5. Новое решение
uj = Uj = 2; u2 = u2 = 2; u3 = u3 - ^ = 3,5; u4 = u4 +1 = 1,5; u6 = 2; T = 9,5.
Заменяя вектор
x5 = /(x6 - X3 + X4)
в формулах для y1, мы получим
1/2 1/2 1/2 1/2 1/2
b1 =
b2 = b3 = b4 = b5 =
y1 = x1 - x2 + 1/2x3 - 1/2X4+ 1/2X6,
2
y
3
x2 - V2x3 + 1/2x4 - 1/2x6, :/2x3 - :/2x4 + :/2x6,
y
:/2x6,
У4 = 1/2x1 + 1/2x3
y
-:/2x3 + :/2x4 + :/2x6,
Новые задачи о ранце имеют вид:
/(xj + x2 +x3) ® max, 6xj + 5X2 + 4x3 < 11;
/(x2 + x3 +x4) ® max , 5X2 + 4x3 + 4X4 < 11;
/(x3 + x4 +x5) ® max , 5X2 + 4x3 + 4X4 + 7X5 < 11. Все три задачи имеют оптимальное значение с = 1. Поэтому полученное решение является оптимальным.
Последовательность векторов xs полученного оптимального решения не является единственной. Этим в ряде случаев можно воспользоваться для того, чтобы найти решение с минимальным
числом прерываний операций. В работе [3] показано, что задача минимизации числа прерываний операций сводится к задаче коммивояжера. В нашем примере число прерываний равно 1 и уменьшить его нельзя, поскольку при выполнении комплекса без прерываний операций продолжительность его будет целым числом. Заметим, что начальное решение, полученное на основе эвристического правила является оптимальным решением без прерываний операций, поскольку продолжительность комплекса в этом решении Т = 10 является ближайшим целым числом, которое больше минимальной продолжительности Т1 = 9,5.
Как уже отмечалось выше, описанный метод дает оптимальное решение при заданном упорядочении событий сети. Если возможных упорядочений несколько, то необходимо решить задачу при каждом из них и выбрать лучшее решение. Однако, в ряде случаев можно судить об оптимальности полученного решения без перебора других упорядочений событий. Для этого необходимо решить задачу о ранце, не предполагая упорядоченности всех событий сети. Если в результате решения этой задачи будет получен вектор со значением c > 1, то следует решить задачу при новом упорядочении, при котором этот вектор будет допустимым.
В нашем примере достаточно рассмотреть следующую задачу о ранце:1/2(x1 +x2 + x3 + x4 +x5) ® max, 6x1 + 5x2 + 4x3 + 4x4 + 7x5 < 11. Легко видеть, что в оптимальном решении этой задачи с = 1, так что лучшего решения не существует, какое бы упорядочение событий мы ни взяли.
Для иллюстрации изменения упорядочения событий рассмотрим следующий пример.
Пример 2.2. Рассмотрим тот же сетевой график, что и в примере 2.1 с данными, приведенными в таблице 4.
Таблица 4. i 1 2 3 4 5 ti 4 5 3 2 6 ai 6 5 4 4 6 Начальное решение в данном случае будет следующим: x1 = (1, 1, 0, 0, 0), u1 = 4 x2 = (0, 1, 1, 0, 0), u2 = 1 x3 = (0, 0, 1, 0, 1), u3 = 2 x4 = (0, 0, 0, 1, 1), u4 = 2 x5 = (0, 0, 0, 0, 1), u5 = 2 Продолжительность комплекса Т = 11. Действуя, как и в примере 2.1, мы получим следующую задачу о ранце:
x2 + x5 ® max , 5x2 + 6x5 < 11.
При заданном упорядочении событий эта задача распадается на две независимые задачи и, очевидно, каждая из них будет иметь величину с = 1. Следовательно, полученное начальное решение является оптимальным при заданном упорядочении.
Заметим, однако, что если изменить очередность событий II и III, то операции 2 и 5 становятся независимыми. В этом случае оптимальное решение задачи о ранце будет следующим:
x2 = x5 = 1
со значением с = 2. Поэтому вводим в базис вектор
6 2 5 2 3 5
x = У + У = x - x + 2x,
•Гu2 u5^ u6 = mini —; — I = 1.
6 I 1 2 0
Исключаем из базиса любой из векторов, например вектор x5. Имеем
u1 = u1 = 4; u2 = U2 - u6 = 0; u3 = u3 + u6 =3;
ui = u4 = 2; u6 = 1; T1 = 10.
Повторяя процедуру, убеждаемся, что полученное решение является оптимальным.
Предложенный метод решения задачи позволяет также определить, на какую величину необходимо увеличить количество ресурса для того, чтобы было возможно дальнейшее уменьшение продолжительности комплекса. Для этого достаточно определить уровень ресурсов N, при котором решение задачи о ранце с больше чем 1, что позволит ввести в базис новый вектор.