Hardprob/Minimum Generalized 0-1 Assignment — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Целая <em>m×n</em>-матрица <m>A\in Z^{m\cdot n}</m>, целый <em>m</em>-ве…») |
StasFomin (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
* Целая <em>m×n</em>-матрица <m>A\in Z^{m\cdot n}</m>, целый <em>m</em>-вектор <m>b\in Z^m</m> и целая <em>m×n</em>-матрица <m>C\in \{0,1\}^{m\cdot n}</m>. | * Целая <em>m×n</em>-матрица <m>A\in Z^{m\cdot n}</m>, целый <em>m</em>-вектор <m>b\in Z^m</m> и целая <em>m×n</em>-матрица <m>C\in \{0,1\}^{m\cdot n}</m>. | ||
* Найти <em>m×n</em>-матрицу <m>X\in \{0,1\}^{m\cdot n}</m>, в которой только одна единица в каждой колонке, и | * Найти <em>m×n</em>-матрицу <m>X\in \{0,1\}^{m\cdot n}</m>, в которой только одна единица в каждой колонке, и | ||
| − | <m>\displaystyle\sum\limits_{j=1}^{n} A_{i,j} X_{i,j}\le b_i ∀i\in [1..m]</m>. | + | <m>\displaystyle\sum\limits_{j=1}^{n} A_{i,j} X_{i,j}\le b_i \ \ \ ∀i\in [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>. | ||
Версия 09:40, 13 апреля 2023
- Целая m×n-матрица , целый m-вектор и целая m×n-матрица .
- Найти m×n-матрицу , в которой только одна единица в каждой колонке, и
.
- Минимизировать
.
Задача в лаб22 (рид-онли просмотр)