Hardprob/Minimum Generalized 0-1 Assignment — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Массовая правка: замена \in на ∈) |
StasFomin (обсуждение | вклад) (Массовая правка: замена PCRE \\le\s на ≤) |
||
| Строка 2: | Строка 2: | ||
* Целая <em>m×n</em>-матрица <m>A∈ Z^{m\cdot n}</m>, целый <em>m</em>-вектор <m>b∈ Z^m</m> и целая <em>m×n</em>-матрица <m>C∈ \{0,1\}^{m\cdot n}</m>. | * Целая <em>m×n</em>-матрица <m>A∈ Z^{m\cdot n}</m>, целый <em>m</em>-вектор <m>b∈ Z^m</m> и целая <em>m×n</em>-матрица <m>C∈ \{0,1\}^{m\cdot n}</m>. | ||
* Найти <em>m×n</em>-матрицу <m>X∈ \{0,1\}^{m\cdot n}</m>, в которой только одна единица в каждой колонке, и | * Найти <em>m×n</em>-матрицу <m>X∈ \{0,1\}^{m\cdot n}</m>, в которой только одна единица в каждой колонке, и | ||
| − | <m>\displaystyle\sum\limits_{j=1}^{n} A_{i,j} X_{i,j} | + | <m>\displaystyle\sum\limits_{j=1}^{n} A_{i,j} X_{i,j}≤b_i \ \ \ ∀i∈ [1..m]</m>. |
* Минимизировать | * Минимизировать | ||
<m>\displaystyle\sum\limits_{i=1}^{m} \displaystyle\sum\limits_{j=1}^{n} C_{i,j} X_{i,j} → \min</m>. | <m>\displaystyle\sum\limits_{i=1}^{m} \displaystyle\sum\limits_{j=1}^{n} C_{i,j} X_{i,j} → \min</m>. | ||
Текущая версия на 21:28, 17 апреля 2023
- Целая m×n-матрица , целый m-вектор и целая m×n-матрица .
- Найти m×n-матрицу , в которой только одна единица в каждой колонке, и
.
- Минимизировать
.
Задача в лаб22 (рид-онли просмотр)