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 (обсуждение | вклад) (Массовая правка: замена PCRE \\le\s на ≤) |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> | ||
| − | * Целая <em>m×n</em>-матрица <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> | + | * Найти <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 (рид-онли просмотр)