Assignment Problem using LP Model Formulation Example-1

1. Find Solution of Assignment problem using LP Model Formulation (MIN case)
_Work\^Job 1 2 3
A 6 3 5
B 5 9 2
C 5 7 8

Solution:
The number of rows = 3 and columns = 3

	`1`	`2`	`3`
`A`	6	3	5
`B`	5	9	2
`C`	5	7	8

Min Z`=6X_(A1)+3X_(A2)+5X_(A3)+5X_(B1)+9X_(B2)+2X_(B3)+5X_(C1)+7X_(C2)+8X_(C3)`

Work constraint
`X_(A1)+X_(A2)+X_(A3)=1`

`X_(B1)+X_(B2)+X_(B3)=1`

`X_(C1)+X_(C2)+X_(C3)=1`

Job constraint
`X_(A1)+X_(B1)+X_(C1)=1`

`X_(A2)+X_(B2)+X_(C2)=1`

`X_(A3)+X_(B3)+X_(C3)=1`

Problem is

Min `Z`

`=`

`6`

`X_(A1)`

` + `

`3`

`X_(A2)`

` + `

`5`

`X_(A3)`

` + `

`5`

`X_(B1)`

` + `

`9`

`X_(B2)`

` + `

`2`

`X_(B3)`

` + `

`5`

`X_(C1)`

` + `

`7`

`X_(C2)`

` + `

`8`

`X_(C3)`

subject to

`X_(A1)`

` + `

`X_(A2)`

` + `

`X_(A3)`

`1`

`X_(B1)`

` + `

`X_(B2)`

` + `

`X_(B3)`

`1`

`X_(C1)`

` + `

`X_(C2)`

` + `

`X_(C3)`

`1`

`X_(A1)`

` + `

`X_(B1)`

` + `

`X_(C1)`

`1`

`X_(A2)`

` + `

`X_(B2)`

` + `

`X_(C2)`

`1`

`X_(A3)`

` + `

`X_(B3)`

` + `

`X_(C3)`

`1`

and `X_(A1),X_(A2),X_(A3),X_(B1),X_(B2),X_(B3),X_(C1),X_(C2),X_(C3) >= 0; `

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate

1. As the constraint-1 is of type '`=`' we should add artificial variable `A_1`

2. As the constraint-2 is of type '`=`' we should add artificial variable `A_2`

3. As the constraint-3 is of type '`=`' we should add artificial variable `A_3`

4. As the constraint-4 is of type '`=`' we should add artificial variable `A_4`

5. As the constraint-5 is of type '`=`' we should add artificial variable `A_5`

6. As the constraint-6 is of type '`=`' we should add artificial variable `A_6`

After introducing artificial variables

Min `Z`

`=`

`6`

`X_(A1)`

` + `

`3`

`X_(A2)`

` + `

`5`

`X_(A3)`

` + `

`5`

`X_(B1)`

` + `

`9`

`X_(B2)`

` + `

`2`

`X_(B3)`

` + `

`5`

`X_(C1)`

` + `

`7`

`X_(C2)`

` + `

`8`

`X_(C3)`

` + `

`M`

`A_1`

` + `

`M`

`A_2`

` + `

`M`

`A_3`

` + `

`M`

`A_4`

` + `

`M`

`A_5`

` + `

`M`

`A_6`

subject to

`X_(A1)`

` + `

`X_(A2)`

` + `

`X_(A3)`

` + `

`A_1`

`1`

`X_(B1)`

` + `

`X_(B2)`

` + `

`X_(B3)`

` + `

`A_2`

`1`

`X_(C1)`

` + `

`X_(C2)`

` + `

`X_(C3)`

` + `

`A_3`

`1`

`X_(A1)`

` + `

`X_(B1)`

` + `

`X_(C1)`

` + `

`A_4`

`1`

`X_(A2)`

` + `

`X_(B2)`

` + `

`X_(C2)`

` + `

`A_5`

`1`

`X_(A3)`

` + `

`X_(B3)`

` + `

`X_(C3)`

` + `

`A_6`

`1`

and `X_(A1),X_(A2),X_(A3),X_(B1),X_(B2),X_(B3),X_(C1),X_(C2),X_(C3),A_1,A_2,A_3,A_4,A_5,A_6 >= 0`

Iteration-1

`C_j`

`6`

`3`

`5`

`9`

`2`

`5`

`7`

`8`

`M`

`B`

`C_B`

`X_B`

`X_(A1)`

`X_(A2)`

`X_(A3)`

`X_(B1)`

`X_(B2)`

`X_(B3)`

`X_(C1)`

`X_(C2)`

`X_(C3)`

`A_1`

`A_2`

`A_3`

`A_4`

`A_5`

`A_6`

MinRatio
`(X_B)/(X_(B3))`

`A_1`

`M`

`1`

`0`

`1`

`0`

---

`A_2`

`M`

`1`

`0`

`1`

`(1)`

`0`

`1`

`0`

`(1)/(1)=1``->`

`A_3`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_4`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_5`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_6`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`(1)/(1)=1`

`Z=6M`

`Z_j`

`2M`

`M`

`Z_j-C_j`

`2M-6`

`2M-3`

`2M-5`

`2M-9`

`2M-2``uarr`

`2M-5`

`2M-7`

`2M-8`

`0`

Positive maximum `Z_j-C_j` is `2M-2` and its column index is `6`. So, the entering variable is `X_(B3)`.

Minimum ratio is `1` and its row index is `2`. So, the leaving basis variable is `A_2`.

`:.` The pivot element is `1`.

Entering `=X_(B3)`, Departing `=A_2`, Key Element `=1`

`R_2`(new)`= R_2`(old)

`R_1`(new)`= R_1`(old)

`R_3`(new)`= R_3`(old)

`R_4`(new)`= R_4`(old)

`R_5`(new)`= R_5`(old)

`R_6`(new)`= R_6`(old) - `R_2`(new)

Iteration-2

`C_j`

`6`

`3`

`5`

`9`

`2`

`5`

`7`

`8`

`M`

`B`

`C_B`

`X_B`

`X_(A1)`

`X_(A2)`

`X_(A3)`

`X_(B1)`

`X_(B2)`

`X_(B3)`

`X_(C1)`

`X_(C2)`

`X_(C3)`

`A_1`

`A_3`

`A_4`

`A_5`

`A_6`

MinRatio
`(X_B)/(X_(A2))`

`A_1`

`M`

`1`

`(1)`

`1`

`0`

`1`

`0`

`(1)/(1)=1``->`

`X_(B3)`

`2`

`1`

`0`

`1`

`0`

---

`A_3`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_4`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_5`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`(1)/(1)=1`

`A_6`

`M`

`0`

`1`

`-1`

`0`

`1`

`0`

`1`

---

`Z=4M+2`

`Z_j`

`2M`

`2`

`2M`

`M`

`Z_j-C_j`

`2M-6`

`2M-3``uarr`

`2M-5`

`-3`

`-7`

`0`

`2M-5`

`2M-7`

`2M-8`

`0`

Positive maximum `Z_j-C_j` is `2M-3` and its column index is `2`. So, the entering variable is `X_(A2)`.

Minimum ratio is `1` and its row index is `1`. So, the leaving basis variable is `A_1`.

`:.` The pivot element is `1`.

Entering `=X_(A2)`, Departing `=A_1`, Key Element `=1`

`R_1`(new)`= R_1`(old)

`R_2`(new)`= R_2`(old)

`R_3`(new)`= R_3`(old)

`R_4`(new)`= R_4`(old)

`R_5`(new)`= R_5`(old) - `R_1`(new)

`R_6`(new)`= R_6`(old)

Iteration-3

`C_j`

`6`

`3`

`5`

`9`

`2`

`5`

`7`

`8`

`M`

`B`

`C_B`

`X_B`

`X_(A1)`

`X_(A2)`

`X_(A3)`

`X_(B1)`

`X_(B2)`

`X_(B3)`

`X_(C1)`

`X_(C2)`

`X_(C3)`

`A_3`

`A_4`

`A_5`

`A_6`

MinRatio
`(X_B)/(X_(C1))`

`X_(A2)`

`3`

`1`

`0`

---

`X_(B3)`

`2`

`1`

`0`

`1`

`0`

---

`A_3`

`M`

`1`

`0`

`(1)`

`1`

`0`

`(1)/(1)=1``->`

`A_4`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`(1)/(1)=1`

`A_5`

`M`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_6`

`M`

`0`

`1`

`-1`

`0`

`1`

`0`

`1`

---

`Z=2M+5`

`Z_j`

`3`

`2`

`2M`

`M`

`Z_j-C_j`

`-3`

`0`

`-2`

`-3`

`-7`

`0`

`2M-5``uarr`

`2M-7`

`2M-8`

`0`

Positive maximum `Z_j-C_j` is `2M-5` and its column index is `7`. So, the entering variable is `X_(C1)`.

Minimum ratio is `1` and its row index is `3`. So, the leaving basis variable is `A_3`.

`:.` The pivot element is `1`.

Entering `=X_(C1)`, Departing `=A_3`, Key Element `=1`

`R_3`(new)`= R_3`(old)

`R_1`(new)`= R_1`(old)

`R_2`(new)`= R_2`(old)

`R_4`(new)`= R_4`(old) - `R_3`(new)

`R_5`(new)`= R_5`(old)

`R_6`(new)`= R_6`(old)

Iteration-4

`C_j`

`6`

`3`

`5`

`9`

`2`

`5`

`7`

`8`

`M`

`B`

`C_B`

`X_B`

`X_(A1)`

`X_(A2)`

`X_(A3)`

`X_(B1)`

`X_(B2)`

`X_(B3)`

`X_(C1)`

`X_(C2)`

`X_(C3)`

`A_4`

`A_5`

`A_6`

MinRatio

`X_(A2)`

`3`

`1`

`0`

`X_(B3)`

`2`

`1`

`0`

`1`

`0`

`X_(C1)`

`5`

`1`

`0`

`1`

`0`

`A_4`

`M`

`0`

`1`

`0`

`1`

`0`

`-1`

`1`

`0`

`A_5`

`M`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`A_6`

`M`

`0`

`1`

`-1`

`0`

`1`

`0`

`1`

`Z=10`

`Z_j`

`3`

`2`

`5`

`M`

`Z_j-C_j`

`-3`

`0`

`-2`

`-3`

`-7`

`0`

`-2`

`-3`

`0`

Since all `Z_j-C_j <= 0`

Hence, optimal solution is arrived with value of variables as :
`X_(A1)=0,X_(A2)=1,X_(A3)=0,X_(B1)=0,X_(B2)=0,X_(B3)=1,X_(C1)=1,X_(C2)=0,X_(C3)=0`

Min `Z=10`

also the artificial variable `A_4` appears in the basis with positive value `0`

This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then Submit Here

1. Example-1