<<
>>

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

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

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

Важно понять структуру нецелочисленного решения и показать, что хотя не- которые задания могут быть распределены по нескольким машинам, таких заданий не может быть слишком много. Для этого мы рассмотрим следующий двудольный граф G(х) = (V(х), E(x)): множество узлов V(х) = M U J, множество заданий и мно- жество машин и ребро (i, j) ^ E(x) существуют в том, и только в том случае, если

х..

> 0.

и

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

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

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

Распределение можно получить, рассматривая каждую компоненту по отдельности. Возьмем одну из компонент, которая пред- ставляет собой дерево; ее узлы соответствуют заданиям и машинам, как показано на рис. 11.11.

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

Очевидно, что этот метод может быть реализован за время O(mn) (включая время создания графа G(х)). Он определяет действительное распределение, так как задача линейного программирования (GL.LP) требует х. = 0 для i ί M.. Что- бы завершить доказательство, необходимо показать, что нагрузка не превышает L + L*. Пусть i —любая машина, а J — множество заданий, назначенных на маши- ну i. Задания, назначенные на машину i, образуют подмножество соседей i в G(х): множество J содержит дочерние узлы узла i, которые являются листьями, а так- же, возможно, родителя p(i) узла i. Чтобы ограничить нагрузку, мы рассмотрим родителя p(i) отдельно. Для всех остальных заданий j = p(i), назначенных i, х. = t, а следовательно для ограничения нагрузки можно воспользоваться решением х:

∑ tj

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. Статья 45. Отмена решения суда о признании физического лица безвестно отсутствующим
  2. Статья 406. Нарушение уставных правил взаимоотношений между военнослужащими при отсутствии отношений подчиненности
  3. Для любого из нас совершенно немыслимо оставаться в браке при отсутствии полной гармонии, самореализации и глубокой цели.
  4. Бардиян Д. В.. Видеосамоучитель. 500 типичных проблем и их решений при работе на ПК, 2009
  5. Типологические предпочтения: ваши действия при решении этических проблем
  6. Наложение циклов
  7. Наложение циклов
  8. Право ребенка выражать свое мнение при решении любого вопроса, затрагивающего его интересы
  9. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  10. § 36 Задаток и его значение. – Употребление задатка в России. – Задаток при продаже. – При публичных торгах. – По казенным подрядам.
  11. 1. Отсутствие юридических последствий
  12. 2. Последствия признания гражданина безвестно отсутствующим