Q.Give mathematical form of Assignment problem.

The assignment problem is a 0-1 LP: minimise $\sum\sum c_{ij}x_{ij}$ with each row-sum and each column-sum equal to 1 and $x_{ij}\in\{0,1\}$.

Let $c_{ij}$ be the cost (or time) of assigning the $i^{th}$ job to the $j^{th}$ person, and let the decision variable be

$x_{ij}=\begin{cases}1,& \text{if job } i \text{ is assigned to person } j\\ 0,& \text{otherwise}\end{cases}$

Objective function: minimise the total cost

$Z=\sum_{i=1}^{n}\sum_{j=1}^{n} c_{ij}\,x_{ij}$

Constraints:

• Each job is assigned to exactly one person: $\displaystyle\sum_{j=1}^{n} x_{ij}=1,\quad i=1,2,\dots,n$ …