Hardprob/Minimum Generalized 0-1 Assignment — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Целая <em>m×n</em>-матрица <m>A\in Z^{m\cdot n}</m>, целый <em>m</em>-ве…»)
 
Строка 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 (рид-онли просмотр)