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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена \in на ∈)
(Массовая правка: замена 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}\le b_i \ \ \ ∀i∈  [1..m]</m>.
+
<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 (рид-онли просмотр)