RSumCi - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:07:54Z

rollbackEdits.php mass rollback

194.88.143.66 в 06:20, 1 сентября 2022

2022-09-01T06:20:34Z

Qradimir: /* Описание алгоритма */

2016-06-10T10:38:45Z

‎Описание алгоритма

Qradimir: /* Описание алгоритма */

2016-06-10T10:36:14Z

‎Описание алгоритма

Qradimir: точки

2016-06-07T02:47:03Z

точки

Qradimir: точки

2016-06-07T02:46:27Z

точки

Qradimir: Фиксы

2016-06-06T23:55:46Z

Фиксы

Qradimir: /* Время выполнения */

2016-06-06T09:38:47Z

‎Время выполнения

Qradimir: Конспект создан

2016-06-05T22:25:47Z

Конспект создан

Новая страница

<tex dpi="200">R \mid \mid \sum C_i</tex>
{{Задача
|definition=Дано <tex> n </tex> работ и <tex> m </tex> станков, причем для каждого станка длительность выполнения на нем <tex>i</tex>-й работы своя и равна <tex> p_{ij} </tex>. Необходимо минимизировать сумму времени выполнения работ.
}}
==Алгоритм==

===Описание алгоритма===
Рассмотрим произвольное допустимое расписание для этой задачи. Рассмотрим какую-то станок <tex> j </tex>, пусть на нем выполняется <tex>n_j</tex> работ. Тогда вклад этого станка в целевую функцию (не теряя общности, пронумеруем работы на этом станке от <tex>1 </tex> до <tex>n_j</tex>) рассчитывается как:

<tex> \sum\limits_{i=1}^{n_j} (p_ij + \sum\limits_{q=1}^{i-1} p_qj) = n_j p_{1j} + (n_j - 1) p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj} </tex>

Заметим, что в каждом допустимом расписании перед каждой работой окажется коэффициент <tex> k </tex>, означающий, что соответствующая работа выпллняется <tex> k </tex>-й с конца. Понятно, что в различных расписаниях <tex> k </tex> может принимать значения от <tex>1</tex> до <tex>n</tex>.

Сведем задачу к назначению каждой работы <tex> i </tex> позиции с конца <tex> k </tex> на станке <tex> j </tex> с помощью задачи [[Поток минимальной стоимости | mincost-maxflow]]. Поместим в левую долю графа работы, в правую долю — пары из станка и коэффициента и проведем соответствующие ребра пропускной способности <tex>1</tex> и стоимости <tex>k p_{ij}</tex>, соответствующие вкладу работы в целевую функцию, если она окажется в позиции <tex> k </tex> с конца на станке <tex> j </tex>. Проведем из стока в левую долю ребра стоимости <tex>0</tex> и пропускной способности <tex>1</tex>, из правой доли в сток — также ребра стоимости <tex> 0 </tex> и пропускной способности <tex>1</tex>. Максимальный поток минимальной стоймости в построенной сети будет ответом на исходную задачу.
{{Утверждение
|statement=Eсли ребро <tex> i \to (j, k) </tex> насыщено потоком, то работа <tex> i </tex> в оптимальном расписании должна стоять на станке <tex> j </tex> в позиции <tex> k </tex> с конца.
|proof=
# Целевые функции задачи mincost-maxflow и текущей задачи совпадают, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию.
# Расписание, построенное по вышепредставленному способу действительно будет допустимым.
## Благодаря ограничениям на поток, входящий в левую долю, каждая работа будет назначена только один раз.
## Благодаря ограничениям на поток, выходящий из правой доли, на каждую позицию будет назначено не более одной работы.
## Докажем, что не возникает ситуации такой, что существует такая позиция <tex> l </tex>, что в этой позиции с конца стоит какая-то работа, а в позиции <tex> l - 1 </tex> с конца — нет (это противоречит определению <tex>l</tex>-й с конца работы). Такая ситуация означает, что ребро <tex> i \to (j, l) </tex> оказалось насышено потоком, а ребро <tex>i \to (j, l - 1) </tex> — не насыщено. Но стоимость ребра <tex> i \to (j, l - 1) </tex> меньше стоимости ребра <tex> i \to (j, l) </tex>, поэтому можем переместить поток с ребра <tex> i \to (j, l) </tex> на ребро <tex> i \to (j, l - 1) </tex>, не нарушив свойства потока и улучшив целевую функцию, что противоречит оптимальности ответа для mincost-maxflow. Следовательно, такой позиции не возникнет и расписание будет допустимым.
}}

===Время выполнения===
Время выполнения mincost-maxflow равно <tex> O(V \cdot E^2) </tex>. Количество вершин в получаемой сети равно <tex> O(m \cdot n) </tex>. Количество ребер в сети равно <tex> O(m \cdot n^2) </tex>. Следственно, ассимптотика алгоритма равна <tex> O(m^3 \cdot n^5) </tex>.

==См. также==
* [[Поток минимальной стоимости]]
* [[Методы решения задач теории расписаний]]

@@ Строка 9: / Строка 9: @@
 <tex>
-\sum\limits_{i=1}^{n_j} \left( p_ij + \sum\limits_{q=1}^{i-1} p_qj \right) =
+\sum\limits_{i=1}^{n_j} \left( p_{ij} + \sum\limits_{q=1}^{i-1} p_{qj} \right) =
 n_j \cdot p_{1j} + (n_j - 1) \cdot p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj}
 </tex>

@@ Строка 9: / Строка 9: @@
 <tex>
-\sum\limits_{i=1}^{n_j} \left( p_ij + \sum\limits_{q=1}^{i-1} \cdot p_qj \right) =
+\sum\limits_{i=1}^{n_j} \left( p_ij + \sum\limits_{q=1}^{i-1} p_qj \right) =
 n_j \cdot p_{1j} + (n_j - 1) \cdot p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj}
 </tex>

@@ Строка 9: / Строка 9: @@
 <tex>
-\sum\limits_{i=1}^{n_j} \left( p_ij + \sum\limits_{q=1}^{i-1} p_qj \right) =
+\sum\limits_{i=1}^{n_j} \left( p_ij + \sum\limits_{q=1}^{i-1} \cdot p_qj \right) =
-n_j p_{1j} + (n_j - 1) p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj}
+n_j \cdot p_{1j} + (n_j - 1) \cdot p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj}
 </tex>

@@ Строка 1: / Строка 1: @@
 <tex dpi="200">R \mid \mid \sum C_i</tex>
 {{Задача
@@ Строка 36: / Строка 15: @@
 Заметим, что в каждом допустимом расписании перед каждой работой окажется коэффициент <tex> k </tex>, означающий, что соответствующая работа выпллняется <tex> k </tex>-й с конца. Понятно, что в различных расписаниях <tex> k </tex> может принимать значения от <tex>1</tex> до <tex>n</tex>.
-Сведем задачу к назначению каждой работы <tex> i </tex> позиции с конца <tex> k </tex> на станке <tex> j </tex> с помощью алгоритма [[Поток минимальной стоимости | поиска максимального потока минимальной стоимости]]. Поместим в левую долю графа работы, в правую долю — пары из станка и коэффициента и проведем соответствующие ребра пропускной способности <tex>1</tex> и стоимости <tex>k \cdot p_{ij}</tex>, соответствующие вкладу работы в целевую функцию, если она окажется в позиции <tex> k </tex> с конца на станке <tex> j </tex>. Проведем из стока в левую долю ребра стоимости <tex>0</tex> и пропускной способности <tex>1</tex>, из правой доли в сток — также ребра стоимости <tex> 0 </tex> и пропускной способности <tex>1</tex>. Максимальный поток минимальной стоймости в построенной сети будет ответом на исходную задачу.
+Сведем задачу к назначению каждой работы <tex> i </tex> позиции с конца <tex> k </tex> на станке <tex> j </tex> с помощью алгоритма [[Поток минимальной стоимости | поиска максимального потока минимальной стоимости]]. Поместим в левую долю графа работы, в правую долю — пары из станка и коэффициента и проведем соответствующие ребра пропускной способности <tex>1</tex> и стоимости <tex>k \cdot p_{ij}</tex>, соответствующие вкладу работы в целевую функцию, если она окажется в позиции <tex> k </tex> с конца на станке <tex> j </tex>. Проведем из стока в левую долю ребра стоимости <tex>0</tex> и пропускной способности <tex>1</tex>, из правой доли в сток — также ребра стоимости <tex> 0 </tex> и пропускной способности <tex>1</tex>. Максимальный поток минимальной стоймости в построенной сети будет ответом на исходную задачу.
 {{Утверждение
 |statement=Eсли ребро <tex> i \to (j, k) </tex> насыщено потоком, то работа <tex> i </tex> в оптимальном расписании должна стоять на станке <tex> j </tex> в позиции <tex> k </tex> с конца.
@@ Строка 44: / Строка 23: @@
 ## Благодаря ограничениям на поток, входящий в левую долю, каждая работа будет назначена только один раз.
 ## Благодаря ограничениям на поток, выходящий из правой доли, на каждую позицию будет назначено не более одной работы.
-## Докажем, что не возникает ситуации такой, что существует такая позиция <tex> l </tex>, что в этой позиции с конца стоит какая-то работа, а в позиции <tex> l - 1 </tex> с конца — нет (это противоречит определению <tex>l</tex>-й с конца работы). Такая ситуация означает, что ребро <tex> i \to (j, l) </tex> оказалось насышено потоком, а ребро <tex>i \to (j, l - 1) </tex> — не насыщено. Но стоимость ребра <tex> i \to (j, l - 1) </tex> меньше стоимости ребра <tex> i \to (j, l) </tex>, поэтому можем переместить поток с ребра <tex> i \to (j, l) </tex> на ребро <tex> i \to (j, l - 1) </tex>, не нарушив свойства потока и улучшив целевую функцию, что противоречит оптимальности ответа для mincost-maxflow. Следовательно, такой позиции не возникнет и расписание будет допустимым.
+## Докажем, что не возникает ситуации такой, что существует такая позиция <tex> l </tex>, что в этой позиции с конца стоит какая-то работа, а в позиции <tex> l - 1 </tex> с конца — нет (это противоречит определению <tex>l</tex>-й с конца работы). Такая ситуация означает, что ребро <tex> i \to (j, l) </tex> оказалось насышено потоком, а ребро <tex>i \to (j, l - 1) </tex> — не насыщено. Но стоимость ребра <tex> i \to (j, l - 1) </tex> меньше стоимости ребра <tex> i \to (j, l) </tex>, поэтому можем переместить поток с ребра <tex> i \to (j, l) </tex> на ребро <tex> i \to (j, l - 1) </tex>, не нарушив свойства потока и улучшив целевую функцию, что противоречит оптимальности ответа для mincost-maxflow. Следовательно, такой позиции не возникнет и расписание будет допустимым.
 }}

@@ Строка 6: / Строка 6: @@
 ===Описание алгоритма===
-Рассмотрим произвольное допустимое расписание для этой задачи. Рассмотрим какую-то станок <tex> j </tex>, пусть на нем выполняется <tex>n_j</tex> работ. Тогда вклад этого станка в целевую функцию (не теряя общности, пронумеруем работы на этом станке от <tex>1 </tex> до <tex>n_j</tex>) рассчитывается как:
+Рассмотрим произвольное допустимое расписание для этой задачи. Рассмотрим какой-то станок <tex> j </tex>, пусть на нем выполняется <tex>n_j</tex> работ. Тогда вклад этого станка в целевую функцию (не теряя общности, пронумеруем работы на этом станке от <tex>1 </tex> до <tex>n_j</tex>) рассчитывается как:
 <tex>

@@ Строка 1: / Строка 1: @@
 <tex dpi="200">R \mid \mid \sum C_i</tex>
 {{Задача
-|definition=Дано <tex> n </tex> работ и <tex> m </tex> станков, причем для каждого станка длительность выполнения на нем <tex>i</tex>-й работы своя и равна <tex> p_{ij} </tex>. Необходимо минимизировать сумму времени выполнения работ.
+|definition=Дано <tex> n </tex> работ и <tex> m </tex> станков, причем для каждого станка длительность выполнения на нем <tex>i</tex>-й работы  составляет <tex> p_{ij} </tex>. Необходимо минимизировать сумму времени выполнения работ.
 }}
 ==Алгоритм==
@@ Строка 8: / Строка 8: @@
 Рассмотрим произвольное допустимое расписание для этой задачи. Рассмотрим какую-то станок <tex> j </tex>, пусть на нем выполняется <tex>n_j</tex> работ. Тогда вклад этого станка в целевую функцию (не теряя общности, пронумеруем работы на этом станке от <tex>1 </tex> до <tex>n_j</tex>) рассчитывается как:
-<tex> \sum\limits_{i=1}^{n_j} (p_ij + \sum\limits_{q=1}^{i-1} p_qj) = n_j p_{1j} + (n_j - 1) p_{2j} + \dots + 2 p_{(n_j-1)j} + p_{n_jj} </tex>
+<tex>
 Заметим, что в каждом допустимом расписании перед каждой работой окажется коэффициент <tex> k </tex>, означающий, что соответствующая работа выпллняется <tex> k </tex>-й с конца. Понятно, что в различных расписаниях <tex> k </tex> может принимать значения от <tex>1</tex> до <tex>n</tex>.
-Сведем задачу к назначению каждой работы <tex> i </tex> позиции с конца <tex> k </tex> на станке <tex> j </tex> с помощью задачи [[Поток минимальной стоимости | mincost-maxflow]]. Поместим в левую долю графа работы, в правую долю — пары из станка и коэффициента и проведем соответствующие ребра пропускной способности <tex>1</tex> и стоимости <tex>k p_{ij}</tex>, соответствующие вкладу работы в целевую функцию, если она окажется в позиции <tex> k </tex> с конца на станке <tex> j </tex>. Проведем из стока в левую долю ребра стоимости <tex>0</tex> и пропускной способности <tex>1</tex>, из правой доли в сток — также ребра стоимости <tex> 0 </tex> и пропускной способности <tex>1</tex>. Максимальный поток минимальной стоймости в построенной сети будет ответом на исходную задачу.
+Сведем задачу к назначению каждой работы <tex> i </tex> позиции с конца <tex> k </tex> на станке <tex> j </tex> с помощью алгоритма [[Поток минимальной стоимости | поиска максимального потока минимальной стоимости]]. Поместим в левую долю графа работы, в правую долю — пары из станка и коэффициента и проведем соответствующие ребра пропускной способности <tex>1</tex> и стоимости <tex>k \cdot p_{ij}</tex>, соответствующие вкладу работы в целевую функцию, если она окажется в позиции <tex> k </tex> с конца на станке <tex> j </tex>. Проведем из стока в левую долю ребра стоимости <tex>0</tex> и пропускной способности <tex>1</tex>, из правой доли в сток — также ребра стоимости <tex> 0 </tex> и пропускной способности <tex>1</tex>. Максимальный поток минимальной стоймости в построенной сети будет ответом на исходную задачу.
 {{Утверждение
 |statement=Eсли ребро <tex> i \to (j, k) </tex> насыщено потоком, то работа <tex> i </tex> в оптимальном расписании должна стоять на станке <tex> j </tex> в позиции <tex> k </tex> с конца.
 |proof=
-# Целевые функции задачи mincost-maxflow и текущей задачи совпадают, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию.
+# Целевя функция текущей задачи совпадает со стомостью максимального потока в построенной сети, так как у ребер между долями пропускная способность 1, а у дополнительных ребер из истока и в сток нулевая стоимость, и они не могут внести вклад в целевую функцию.
 # Расписание, построенное по вышепредставленному способу действительно будет допустимым.
 ## Благодаря ограничениям на поток, входящий в левую долю, каждая работа будет назначена только один раз.
@@ Строка 24: / Строка 27: @@
 ===Время выполнения===
-Время выполнения mincost-maxflow равно <tex> \mathcal{O}(V \cdot E^2) </tex>. Количество вершин в получаемой сети равно <tex> \mathcal{O}(m \cdot n) </tex>. Количество ребер в сети равно <tex> \mathcal{O}(m \cdot n^2) </tex>. Следственно, ассимптотика алгоритма равна <tex> \mathcal{O}(m^3 \cdot n^5) </tex>.
+Время выполнения алгоритма поиска максимального потока минимальной стоймости равно <tex> \mathcal{O}(V \cdot E^2) </tex>. Количество вершин в получаемой сети равно <tex> \mathcal{O}(m \cdot n) </tex>. Количество ребер в сети равно <tex> \mathcal{O}(m \cdot n^2) </tex>. Следовательно, ассимптотика алгоритма равна <tex> \mathcal{O}(m^3 \cdot n^5) </tex>.
 ==См. также==
 * [[Поток минимальной стоимости]]
 * [[Методы решения задач теории расписаний]]