Hardprob/Minimum Vehicle Scheduling On Tree - История изменений

StasFomin: Массовая правка: замена \ldots на …

2023-04-17T22:45:13Z

Массовая правка: замена \ldots на …

StasFomin: Массовая правка: замена PCRE (\w)_(\w) на \1_\2

2023-04-17T22:33:38Z

Массовая правка: замена PCRE <m>(\w)_(\w)</m> на \1\2

StasFomin: Массовая правка: замена PCRE (\w)\s:\s(\w)\s→\s(\w) на \1: \2 → \3

2023-04-17T22:16:38Z

Массовая правка: замена PCRE <m>(\w)\s*:\s*(\w)\s*→\s*(\w)</m> на \1: \2 → \3

StasFomin: Массовая правка: замена \rightarrow на →

2023-04-17T11:34:13Z

Массовая правка: замена \rightarrow на →

StasFomin: Массовая правка: замена \geq на ≥

2023-04-17T11:29:37Z

Массовая правка: замена \geq на ≥

StasFomin в 08:38, 13 апреля 2023

2023-04-13T08:38:41Z

StasFomin в 08:38, 13 апреля 2023

2023-04-13T08:38:02Z

StasFomin в 23:10, 12 апреля 2023

2023-04-12T23:10:09Z

StasFomin: Новая страница: « * Дерево с выделенным корнем T=\left(V,E,v_0\right), ** на р…»

2023-04-12T23:09:18Z

Новая страница: « * Дерево с выделенным корнем <m>T=\left(V,E,v_0\right)</m>, ** на р…»

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

* Дерево с выделенным корнем <m>T=\left(V,E,v_0\right)</m>,
** на ребрах заданы времена проезда в
*** прямом <m>f : E \rightarrow N</m>
*** обратно направлении <m>b: E \rightarrow N</m>
** на вершинах
*** время отгрузки-загрузки <m>r: V \rightarrow N</m>
*** время обработки <m>h: V \rightarrow N</m>

Найти расписание автомобильного объезда, которое
* стартует в <m>v_0</m>,
* посещает все вершины в <m>T</m>
* возвращается в <m>v_0</m>
* для любой вершины <m>v_{i}</m>
** обработка стартует не раньше <m>r(v_i)</m>.

Т.е. найти перестановку <m>\pi</m> вершин <m>1, \ldots, \vert V\vert</m>, и функция ожидания w, такую что для любого i
<m>
\begin{displaymath}
d(v_0,v_{\pi(1)})+\sum_{j=1}^{i-1}[w(v_{\pi(j)})+h(v_{\pi(j)})+
d(v_{\pi(j)},v_{\pi(j+1)})] \geq r(v_{\pi(i)})
\end{displaymath}
</m>
где d(u,v) означает длину уникального пути из u в v.

Минимизировать полное время выполнения, т.е.
<m>
\begin{eqnarray*}
& & d(v_0,v_{\pi(1)})+\sum_{j=1}^{n-1}[w(v_{\pi(j)})+h(v_{\pi(j)}) + \\
& & d(v_{\pi(j)},v_{\pi(j+1)})] + w(v_{\pi(n)}) + h(v_{\pi(n)}) + d(v_{\pi(n)},v_0) → \min.
\end{eqnarray*}
</m>

----
{{hard-problem-on-lab17|{{PAGENAME}}}}




----

{{ViggoCode|node197}}





[[Категория:ClassicHardProblems]]

@@ Строка 15: / Строка 15: @@
 ** обработка стартует не раньше <m>r(v_i)</m>.
-Т.е. найти перестановку <m>\pi</m> вершин <m>1, \ldots, \vert V\vert</m>,  и функция ожидания <em>w</em>, такую что для любого <em>i</em>
+Т.е. найти перестановку <m>\pi</m> вершин <m>1, …, \vert V\vert</m>,  и функция ожидания <em>w</em>, такую что для любого <em>i</em>
 <m>
   \begin{displaymath}

@@ Строка 2: / Строка 2: @@
 * Дерево с выделенным корнем <m>T=\left(V,E,v_0\right)</m>,
 ** на ребрах заданы времена проезда в
-*** прямом <m>f : E →  N</m>
+*** прямом <em>f: E → N</em>
-*** обратно направлении <m>b: E →  N</m>
+*** обратно направлении <em>b: E → N</em>
 ** на вершинах
-*** время отгрузки-загрузки <m>r: V →  N</m>
+*** время отгрузки-загрузки <em>r: V → N</em>
-*** время обработки <m>h: V →  N</m>
+*** время обработки <em>h: V → N</em>
 Найти расписание автомобильного объезда, которое

@@ Строка 9: / Строка 9: @@
 Найти расписание автомобильного объезда, которое
-* стартует в <m>v_0</m>,
+* стартует в <em>v<sub>0</sub></em>,
 * посещает все вершины в <m>T</m>
-* возвращается в <m>v_0</m>
+* возвращается в <em>v<sub>0</sub></em>
 * для любой вершины <m>v_{i}</m>
 ** обработка стартует не раньше <m>r(v_i)</m>.

@@ Строка 18: / Строка 18: @@
 <m>
   \begin{displaymath}
-d(v_0,v_{\pi(1)})+\sum_{j=1}^{i-1}[w(v_{\pi(j)})+h(v_{\pi(j)})+ d(v_{\pi(j)},v_{\pi(j+1)})] \geq r(v_{\pi(i)})
+d(v_0,v_{\pi(1)})+\sum_{j=1}^{i-1}[w(v_{\pi(j)})+h(v_{\pi(j)})+ d(v_{\pi(j)},v_{\pi(j+1)})] ≥  r(v_{\pi(i)})
 \end{displaymath}
 </m>

@@ Строка 27: / Строка 27: @@
 <m>
- \begin{eqnarray*}
+d(v_0,v_{\pi(1)})+\sum_{j=1}^{n-1}[w(v_{\pi(j)})+h(v_{\pi(j)}) +
-& & d(v_0,v_{\pi(1)})+\sum_{j=1}^{n-1}[w(v_{\pi(j)})+h(v_{\pi(j)}) + \\
+d(v_{\pi(j)},v_{\pi(j+1)})] + w(v_{\pi(n)}) + h(v_{\pi(n)}) + d(v_{\pi(n)},v_0) → \min.
- & & d(v_{\pi(j)},v_{\pi(j+1)})] + w(v_{\pi(n)}) + h(v_{\pi(n)}) + d(v_{\pi(n)},v_0) → \min.
-\end{eqnarray*}
 </m>

@@ Строка 26: / Строка 26: @@
 Минимизировать полное время выполнения, т.е.
 <m>
   \begin{eqnarray*}

Hardprob/Minimum Vehicle Scheduling On Tree - История изменений

StasFomin: Массовая правка: замена \ldots на …

StasFomin: Массовая правка: замена PCRE (\w)_(\w) на \1\2

StasFomin: Массовая правка: замена PCRE (\w)\s*:\s*(\w)\s*→\s*(\w) на \1: \2 → \3

StasFomin: Массовая правка: замена \rightarrow на →

StasFomin: Массовая правка: замена \geq на ≥

StasFomin в 08:38, 13 апреля 2023

StasFomin в 08:38, 13 апреля 2023

StasFomin в 23:10, 12 апреля 2023

StasFomin: Новая страница: « * Дерево с выделенным корнем T=\left(V,E,v_0\right), ** на р…»

StasFomin: Массовая правка: замена PCRE (\w)_(\w) на \1_\2

StasFomin: Массовая правка: замена PCRE (\w)\s:\s(\w)\s→\s(\w) на \1: \2 → \3