Округление решения при отсутствии циклов

Основная идея заключается в округлении значений xij до 0 или tj. Однако мы не можем просто округлять большие значения в сторону увеличения, а меньшие — в сторону уменьшения.

Проблема в том, что решение задачи линейного программирования может назначить малые доли задания j на каждую из m машин, а следовательно, для некоторых заданий больших значений xij может не быть.

Наш алгоритм будет производить «слабое» округление x: каждое задание j будет назначаться на машину i с xij > 0, но возможно, некоторые малые значения придется округлять в большую сторону. Слабое округление уже гарантирует, что распределение является действительным в том смысле, что никакое задание j не назначается на машину i, не входящую в Mj (потому что если i ѯ Mj, то xij = 0).

Важно понять структуру нецелочисленного решения и показать, что хотя некоторые задания могут быть распределены по нескольким машинам, таких заданий не может быть слишком много.

Для этого мы рассмотрим следующий двудольный граф G(x) = (V(x), E(x)): множество узлов V(x) = M Ґ J, множество заданий и множество машин и ребро (i, j) Ѯ E(x) существуют в том, и только в том случае, если xij > 0.

Мы покажем, что при наличии решения для (GL.LP) можно получить новое решение x с такой же нагрузкой L, в котором G(x) не содержит циклов. Этот шаг очень важен, так как вы увидите, что решение x без циклов может использоваться для получения распределения с нагрузкой не более L + L*.

(11.29) Для решения (x,L) задачи (GL.LP), в котором граф G(x) не имеет циклов, решение x может использоваться для получения действительного распределения заданий между машинами с нагрузкой не более L + L* за время O(mn).

Доказательство. Так как граф G(x) не содержит циклов, каждая из его компонент связности является деревом. Распределение можно получить, рассматривая каждую компоненту по отдельности. 

Разместим корень дерева в произвольном узле и рассмотрим задание j. Если узел, соответствующий заданию j, является узлом дерева, пусть узел машины i является его родителем. Так как степень j в дереве G(x) равна 1, машина i — единственная машина, которой была назначена часть задания j, а следовательно, должно выполняться xij = tj.

В нашем распределении такое задание j будет назначено только на его соседнюю машину i. Задание j, узел которого не является листовым в G(x), назначается произвольному дочернему узлу соответствующего дочернего узла в корневом дереве.