Assignment Problem using LP Model Formulation Example-2

Find Solution of Assignment problem using LP Model Formulation (MIN case)
_Work\^Job 1 2 3 4
A 9 14 19 15
B 7 17 20 19
C 9 18 21 18
D 10 12 18 19
E 10 15 21 16

Solution:
The number of rows = 5 and columns = 4

	`1`	`2`	`3`	`4`
`A`	9	14	19	15
`B`	7	17	20	19
`C`	9	18	21	18
`D`	10	12	18	19
`E`	10	15	21	16

Min Z`=9X_(A1)+14X_(A2)+19X_(A3)+15X_(A4)+7X_(B1)+17X_(B2)+20X_(B3)+19X_(B4)+9X_(C1)+18X_(C2)+21X_(C3)+18X_(C4)+10X_(D1)+12X_(D2)+18X_(D3)+19X_(D4)+10X_(E1)+15X_(E2)+21X_(E3)+16X_(E4)`

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

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

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

`X_(D1)+X_(D2)+X_(D3)+X_(D4)<=1`

`X_(E1)+X_(E2)+X_(E3)+X_(E4)<=1`

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

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

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

`X_(A4)+X_(B4)+X_(C4)+X_(D4)+X_(E4)=1`

Problem is

Min `Z`

`=`

`9`

`X_(A1)`

` + `

`14`

`X_(A2)`

` + `

`19`

`X_(A3)`

` + `

`15`

`X_(A4)`

` + `

`7`

`X_(B1)`

` + `

`17`

`X_(B2)`

` + `

`20`

`X_(B3)`

` + `

`19`

`X_(B4)`

` + `

`9`

`X_(C1)`

` + `

`18`

`X_(C2)`

` + `

`21`

`X_(C3)`

` + `

`18`

`X_(C4)`

` + `

`10`

`X_(D1)`

` + `

`12`

`X_(D2)`

` + `

`18`

`X_(D3)`

` + `

`19`

`X_(D4)`

` + `

`10`

`X_(E1)`

` + `

`15`

`X_(E2)`

` + `

`21`

`X_(E3)`

` + `

`16`

`X_(E4)`

subject to

`X_(A1)`

` + `

`X_(A2)`

` + `

`X_(A3)`

` + `

`X_(A4)`

≤

`1`

`X_(B1)`

` + `

`X_(B2)`

` + `

`X_(B3)`

` + `

`X_(B4)`

≤

`1`

`X_(C1)`

` + `

`X_(C2)`

` + `

`X_(C3)`

` + `

`X_(C4)`

≤

`1`

`X_(D1)`

` + `

`X_(D2)`

` + `

`X_(D3)`

` + `

`X_(D4)`

≤

`1`

`X_(E1)`

` + `

`X_(E2)`

` + `

`X_(E3)`

` + `

`X_(E4)`

≤

`1`

`X_(A1)`

` + `

`X_(B1)`

` + `

`X_(C1)`

` + `

`X_(D1)`

` + `

`X_(E1)`

`1`

`X_(A2)`

` + `

`X_(B2)`

` + `

`X_(C2)`

` + `

`X_(D2)`

` + `

`X_(E2)`

`1`

`X_(A3)`

` + `

`X_(B3)`

` + `

`X_(C3)`

` + `

`X_(D3)`

` + `

`X_(E3)`

`1`

`X_(A4)`

` + `

`X_(B4)`

` + `

`X_(C4)`

` + `

`X_(D4)`

` + `

`X_(E4)`

`1`

and `X_(A1),X_(A2),X_(A3),X_(A4),X_(B1),X_(B2),X_(B3),X_(B4),X_(C1),X_(C2),X_(C3),X_(C4),X_(D1),X_(D2),X_(D3),X_(D4),X_(E1),X_(E2),X_(E3),X_(E4) >= 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 slack variable `S_1`

2. As the constraint-2 is of type '`<=`' we should add slack variable `S_2`

3. As the constraint-3 is of type '`<=`' we should add slack variable `S_3`

4. As the constraint-4 is of type '`<=`' we should add slack variable `S_4`

5. As the constraint-5 is of type '`<=`' we should add slack variable `S_5`

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

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

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

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

After introducing slack,artificial variables

Min `Z`

`=`

`9`

`X_(A1)`

` + `

`14`

`X_(A2)`

` + `

`19`

`X_(A3)`

` + `

`15`

`X_(A4)`

` + `

`7`

`X_(B1)`

` + `

`17`

`X_(B2)`

` + `

`20`

`X_(B3)`

` + `

`19`

`X_(B4)`

` + `

`9`

`X_(C1)`

` + `

`18`

`X_(C2)`

` + `

`21`

`X_(C3)`

` + `

`18`

`X_(C4)`

` + `

`10`

`X_(D1)`

` + `

`12`

`X_(D2)`

` + `

`18`

`X_(D3)`

` + `

`19`

`X_(D4)`

` + `

`10`

`X_(E1)`

` + `

`15`

`X_(E2)`

` + `

`21`

`X_(E3)`

` + `

`16`

`X_(E4)`

` + `

`0`

`S_1`

` + `

`0`

`S_2`

` + `

`0`

`S_3`

` + `

`0`

`S_4`

` + `

`0`

`S_5`

` + `

`M`

`A_1`

` + `

`M`

`A_2`

` + `

`M`

`A_3`

` + `

`M`

`A_4`

subject to

`X_(A1)`

` + `

`X_(A2)`

` + `

`X_(A3)`

` + `

`X_(A4)`

` + `

`S_1`

`1`

`X_(B1)`

` + `

`X_(B2)`

` + `

`X_(B3)`

` + `

`X_(B4)`

` + `

`S_2`

`1`

`X_(C1)`

` + `

`X_(C2)`

` + `

`X_(C3)`

` + `

`X_(C4)`

` + `

`S_3`

`1`

`X_(D1)`

` + `

`X_(D2)`

` + `

`X_(D3)`

` + `

`X_(D4)`

` + `

`S_4`

`1`

`X_(E1)`

` + `

`X_(E2)`

` + `

`X_(E3)`

` + `

`X_(E4)`

` + `

`S_5`

`1`

`X_(A1)`

` + `

`X_(B1)`

` + `

`X_(C1)`

` + `

`X_(D1)`

` + `

`X_(E1)`

` + `

`A_1`

`1`

`X_(A2)`

` + `

`X_(B2)`

` + `

`X_(C2)`

` + `

`X_(D2)`

` + `

`X_(E2)`

` + `

`A_2`

`1`

`X_(A3)`

` + `

`X_(B3)`

` + `

`X_(C3)`

` + `

`X_(D3)`

` + `

`X_(E3)`

` + `

`A_3`

`1`

`X_(A4)`

` + `

`X_(B4)`

` + `

`X_(C4)`

` + `

`X_(D4)`

` + `

`X_(E4)`

` + `

`A_4`

`1`

and `X_(A1),X_(A2),X_(A3),X_(A4),X_(B1),X_(B2),X_(B3),X_(B4),X_(C1),X_(C2),X_(C3),X_(C4),X_(D1),X_(D2),X_(D3),X_(D4),X_(E1),X_(E2),X_(E3),X_(E4),S_1,S_2,S_3,S_4,S_5,A_1,A_2,A_3,A_4 >= 0`

Iteration-1

`C_j`

`9`

`14`

`19`

`15`

`7`

`17`

`20`

`19`

`9`

`18`

`21`

`18`

`10`

`12`

`18`

`19`

`10`

`15`

`21`

`16`

`0`

`M`

`B`

`C_B`

`X_B`

`X_(A1)`

`X_(A2)`

`X_(A3)`

`X_(A4)`

`X_(B1)`

`X_(B2)`

`X_(B3)`

`X_(B4)`

`X_(C1)`

`X_(C2)`

`X_(C3)`

`X_(C4)`

`X_(D1)`

`X_(D2)`

`X_(D3)`

`X_(D4)`

`X_(E1)`

`X_(E2)`

`X_(E3)`

`X_(E4)`

`S_1`

`S_2`

`S_3`

`S_4`

`S_5`

`A_1`

`A_2`

`A_3`

`A_4`

MinRatio
`(X_B)/(X_(B1))`

`S_1`

`0`

`1`

`0`

`1`

`0`

---

`S_2`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`(1)/(1)=1`

`S_3`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`S_4`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`S_5`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_1`

`M`

`1`

`0`

`(1)`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

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

`A_2`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_3`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_4`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

---

`Z=4M`

`Z_j`

`M`

`0`

`M`

`Z_j-C_j`

`M-9`

`M-14`

`M-19`

`M-15`

`M-7``uarr`

`M-17`

`M-20`

`M-19`

`M-9`

`M-18`

`M-21`

`M-18`

`M-10`

`M-12`

`M-18`

`M-19`

`M-10`

`M-15`

`M-21`

`M-16`

`0`

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

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

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

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

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

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

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

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

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

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

`R_7`(new)`= R_7`(old)

`R_8`(new)`= R_8`(old)

`R_9`(new)`= R_9`(old)

Iteration-2

`C_j`

`9`

`14`

`19`

`15`

`7`

`17`

`20`

`19`

`9`

`18`

`21`

`18`

`10`

`12`

`18`

`19`

`10`

`15`

`21`

`16`

`0`

`M`

`B`

`C_B`

`X_B`

`X_(A1)`

`X_(A2)`

`X_(A3)`

`X_(A4)`

`X_(B1)`

`X_(B2)`

`X_(B3)`

`X_(B4)`

`X_(C1)`

`X_(C2)`

`X_(C3)`

`X_(C4)`

`X_(D1)`

`X_(D2)`

`X_(D3)`

`X_(D4)`

`X_(E1)`

`X_(E2)`

`X_(E3)`

`X_(E4)`

`S_1`

`S_2`

`S_3`

`S_4`

`S_5`

`A_2`

`A_3`

`A_4`

MinRatio
`(X_B)/(X_(D2))`

`S_1`

`0`

`1`

`0`

`1`

`0`

---

`S_2`

`0`

`-1`

`0`

`1`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

---

`S_3`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`S_4`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`(1)/(1)=1`

`S_5`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(B1)`

`7`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_2`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`(1)`

`0`

`1`

`0`

`1`

`0`

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

`A_3`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_4`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

---

`Z=3M+7`

`Z_j`

`7`

`M`

`7`

`M`

`7`

`M`

`7`

`M`

`7`

`M`

`0`

`M`

`Z_j-C_j`

`-2`

`M-14`

`M-19`

`M-15`

`0`

`M-17`

`M-20`

`M-19`

`-2`

`M-18`

`M-21`

`M-18`

`-3`

`M-12``uarr`

`M-18`

`M-19`

`-3`

`M-15`

`M-21`

`M-16`

`0`

Positive maximum `Z_j-C_j` is `M-12` and its column index is `14`. So, the entering variable is `X_(D2)`.

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

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

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

`R_7`(new)`= R_7`(old)

`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_7`(new)

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

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

`R_8`(new)`= R_8`(old)

`R_9`(new)`= R_9`(old)

Iteration-3

`C_j`

`9`

`14`

`19`

`15`

`7`

`17`

`20`

`19`

`9`

`18`

`21`

`18`

`10`

`12`

`18`

`19`

`10`

`15`

`21`

`16`

`0`

`M`

`B`

`C_B`

`X_B`

`X_(A1)`

`X_(A2)`

`X_(A3)`

`X_(A4)`

`X_(B1)`

`X_(B2)`

`X_(B3)`

`X_(B4)`

`X_(C1)`

`X_(C2)`

`X_(C3)`

`X_(C4)`

`X_(D1)`

`X_(D2)`

`X_(D3)`

`X_(D4)`

`X_(E1)`

`X_(E2)`

`X_(E3)`

`X_(E4)`

`S_1`

`S_2`

`S_3`

`S_4`

`S_5`

`A_3`

`A_4`

MinRatio
`(X_B)/(X_(A4))`

`S_1`

`0`

`1`

`0`

`1`

`0`

`(1)/(1)=1`

`S_2`

`0`

`-1`

`0`

`1`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

---

`S_3`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`S_4`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`1`

`0`

---

`S_5`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(B1)`

`7`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(D2)`

`12`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_3`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_4`

`M`

`1`

`0`

`(1)`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

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

`Z=2M+19`

`Z_j`

`7`

`12`

`M`

`7`

`12`

`M`

`7`

`12`

`M`

`7`

`12`

`M`

`7`

`12`

`M`

`0`

`M`

`Z_j-C_j`

`-2`

`M-19`

`M-15``uarr`

`0`

`-5`

`M-20`

`M-19`

`-2`

`-6`

`M-21`

`M-18`

`-3`

`0`

`M-18`

`M-19`

`-3`

`M-21`

`M-16`

`0`

Positive maximum `Z_j-C_j` is `M-15` and its column index is `4`. So, the entering variable is `X_(A4)`.

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

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

Entering `=X_(A4)`, Departing `=A_4`, Key Element `=1`

`R_9`(new)`= R_9`(old)

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

`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_6`(new)`= R_6`(old)

`R_7`(new)`= R_7`(old)

`R_8`(new)`= R_8`(old)

Iteration-4

`C_j`

`9`

`14`

`19`

`15`

`7`

`17`

`20`

`19`

`9`

`18`

`21`

`18`

`10`

`12`

`18`

`19`

`10`

`15`

`21`

`16`

`0`

`M`

`B`

`C_B`

`X_B`

`X_(A1)`

`X_(A2)`

`X_(A3)`

`X_(A4)`

`X_(B1)`

`X_(B2)`

`X_(B3)`

`X_(B4)`

`X_(C1)`

`X_(C2)`

`X_(C3)`

`X_(C4)`

`X_(D1)`

`X_(D2)`

`X_(D3)`

`X_(D4)`

`X_(E1)`

`X_(E2)`

`X_(E3)`

`X_(E4)`

`S_1`

`S_2`

`S_3`

`S_4`

`S_5`

`A_3`

MinRatio
`(X_B)/(X_(D3))`

`S_1`

`0`

`1`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`1`

`0`

---

`S_2`

`0`

`-1`

`0`

`1`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

---

`S_3`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`S_4`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`(1)`

`1`

`0`

`-1`

`0`

`1`

`0`

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

`S_5`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(B1)`

`7`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(D2)`

`12`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_3`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`(1)/(1)=1`

`X_(A4)`

`15`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`Z=M+34`

`Z_j`

`7`

`12`

`M`

`15`

`7`

`12`

`M`

`15`

`7`

`12`

`M`

`15`

`7`

`12`

`M`

`15`

`7`

`12`

`M`

`15`

`0`

`M`

`Z_j-C_j`

`-2`

`M-19`

`0`

`-5`

`M-20`

`-4`

`-2`

`-6`

`M-21`

`-3`

`0`

`M-18``uarr`

`-4`

`-3`

`M-21`

`-1`

`0`

Positive maximum `Z_j-C_j` is `M-18` and its column index is `15`. So, the entering variable is `X_(D3)`.

Minimum ratio is `0` and its row index is `4`. So, the leaving basis variable is `S_4`.

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

Entering `=X_(D3)`, Departing `=S_4`, Key Element `=1`

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

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

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

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

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

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

`R_7`(new)`= R_7`(old)

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

`R_9`(new)`= R_9`(old)

Iteration-5

`C_j`

`9`

`14`

`19`

`15`

`7`

`17`

`20`

`19`

`9`

`18`

`21`

`18`

`10`

`12`

`18`

`19`

`10`

`15`

`21`

`16`

`0`

`M`

`B`

`C_B`

`X_B`

`X_(A1)`

`X_(A2)`

`X_(A3)`

`X_(A4)`

`X_(B1)`

`X_(B2)`

`X_(B3)`

`X_(B4)`

`X_(C1)`

`X_(C2)`

`X_(C3)`

`X_(C4)`

`X_(D1)`

`X_(D2)`

`X_(D3)`

`X_(D4)`

`X_(E1)`

`X_(E2)`

`X_(E3)`

`X_(E4)`

`S_1`

`S_2`

`S_3`

`S_4`

`S_5`

`A_3`

MinRatio
`(X_B)/(X_(A3))`

`S_1`

`0`

`1`

`(1)`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`1`

`0`

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

`S_2`

`0`

`-1`

`0`

`1`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

---

`S_3`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(D3)`

`18`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`1`

`0`

---

`S_5`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(B1)`

`7`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(D2)`

`12`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_3`

`M`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`-1`

`0`

`1`

`(1)/(1)=1`

`X_(A4)`

`15`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`Z=M+34`

`Z_j`

`7`

`M-6`

`M`

`15`

`7`

`M-6`

`M`

`15`

`7`

`M-6`

`M`

`15`

`-M+25`

`12`

`18`

`-M+33`

`7`

`M-6`

`M`

`15`

`0`

`-M+18`

`0`

`M`

`Z_j-C_j`

`-2`

`M-20`

`M-19``uarr`

`0`

`M-23`

`M-20`

`-4`

`-2`

`M-24`

`M-21`

`-3`

`-M+15`

`0`

`-M+14`

`-3`

`M-21`

`-1`

`0`

`-M+18`

`0`

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

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

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

Entering `=X_(A3)`, Departing `=S_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_6`(new)`= R_6`(old)

`R_7`(new)`= R_7`(old)

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

`R_9`(new)`= R_9`(old)

Iteration-6

`C_j`

`9`

`14`

`19`

`15`

`7`

`17`

`20`

`19`

`9`

`18`

`21`

`18`

`10`

`12`

`18`

`19`

`10`

`15`

`21`

`16`

`0`

`M`

`B`

`C_B`

`X_B`

`X_(A1)`

`X_(A2)`

`X_(A3)`

`X_(A4)`

`X_(B1)`

`X_(B2)`

`X_(B3)`

`X_(B4)`

`X_(C1)`

`X_(C2)`

`X_(C3)`

`X_(C4)`

`X_(D1)`

`X_(D2)`

`X_(D3)`

`X_(D4)`

`X_(E1)`

`X_(E2)`

`X_(E3)`

`X_(E4)`

`S_1`

`S_2`

`S_3`

`S_4`

`S_5`

`A_3`

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

`X_(A3)`

`19`

`0`

`1`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`1`

`0`

---

`S_2`

`0`

`-1`

`0`

`1`

`(1)`

`1`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

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

`S_3`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(D3)`

`18`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`1`

`0`

---

`S_5`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(B1)`

`7`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(D2)`

`12`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_3`

`M`

`1`

`-1`

`0`

`1`

`0`

`1`

`-1`

`0`

`1`

`-1`

`0`

`-1`

`0`

`1`

`(1)/(1)=1`

`X_(A4)`

`15`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`Z=M+34`

`Z_j`

`-M+26`

`13`

`19`

`15`

`7`

`M-6`

`M`

`M-4`

`7`

`M-6`

`M`

`M-4`

`-M+25`

`12`

`18`

`14`

`7`

`M-6`

`M`

`M-4`

`-M+19`

`0`

`-M+18`

`0`

`M`

`Z_j-C_j`

`-M+17`

`-1`

`0`

`M-23`

`M-20``uarr`

`M-23`

`-2`

`M-24`

`M-21`

`M-22`

`-M+15`

`0`

`-5`

`-3`

`M-21`

`M-20`

`-M+19`

`0`

`-M+18`

`0`

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

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

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

Entering `=X_(B3)`, Departing `=S_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_7`(new)`= R_7`(old)

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

`R_9`(new)`= R_9`(old)

Iteration-7

`C_j`

`9`

`14`

`19`

`15`

`7`

`17`

`20`

`19`

`9`

`18`

`21`

`18`

`10`

`12`

`18`

`19`

`10`

`15`

`21`

`16`

`0`

`M`

`B`

`C_B`

`X_B`

`X_(A1)`

`X_(A2)`

`X_(A3)`

`X_(A4)`

`X_(B1)`

`X_(B2)`

`X_(B3)`

`X_(B4)`

`X_(C1)`

`X_(C2)`

`X_(C3)`

`X_(C4)`

`X_(D1)`

`X_(D2)`

`X_(D3)`

`X_(D4)`

`X_(E1)`

`X_(E2)`

`X_(E3)`

`X_(E4)`

`S_1`

`S_2`

`S_3`

`S_4`

`S_5`

`A_3`

MinRatio
`(X_B)/(X_(E4))`

`X_(A3)`

`19`

`0`

`1`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`1`

`0`

---

`X_(B3)`

`20`

`0`

`-1`

`0`

`1`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

---

`S_3`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(D3)`

`18`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`1`

`0`

---

`S_5`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`(1)/(1)=1`

`X_(B1)`

`7`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(D2)`

`12`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_3`

`M`

`1`

`0`

`1`

`0`

`1`

`(1)`

`-1`

`0`

`-1`

`0`

`1`

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

`X_(A4)`

`15`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`(1)/(1)=1`

`Z=M+34`

`Z_j`

`6`

`13`

`19`

`15`

`7`

`14`

`20`

`16`

`M-13`

`M-6`

`M`

`M-4`

`5`

`12`

`18`

`14`

`M-13`

`M-6`

`M`

`M-4`

`-M+19`

`-M+20`

`0`

`-M+18`

`0`

`M`

`Z_j-C_j`

`-3`

`-1`

`0`

`-3`

`0`

`-3`

`M-22`

`M-24`

`M-21`

`M-22`

`-5`

`0`

`-5`

`M-23`

`M-21`

`M-20``uarr`

`-M+19`

`-M+20`

`0`

`-M+18`

`0`

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

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

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

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

`R_8`(new)`= R_8`(old)

`R_1`(new)`= R_1`(old) + `R_8`(new)

`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_8`(new)

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

`R_7`(new)`= R_7`(old)

`R_9`(new)`= R_9`(old) - `R_8`(new)

Iteration-8

`C_j`

`9`

`14`

`19`

`15`

`7`

`17`

`20`

`19`

`9`

`18`

`21`

`18`

`10`

`12`

`18`

`19`

`10`

`15`

`21`

`16`

`0`

`B`

`C_B`

`X_B`

`X_(A1)`

`X_(A2)`

`X_(A3)`

`X_(A4)`

`X_(B1)`

`X_(B2)`

`X_(B3)`

`X_(B4)`

`X_(C1)`

`X_(C2)`

`X_(C3)`

`X_(C4)`

`X_(D1)`

`X_(D2)`

`X_(D3)`

`X_(D4)`

`X_(E1)`

`X_(E2)`

`X_(E3)`

`X_(E4)`

`S_1`

`S_2`

`S_3`

`S_4`

`S_5`

MinRatio

`X_(A3)`

`19`

`1`

`0`

`-1`

`1`

`0`

`-1`

`1`

`0`

`-1`

`0`

`-1`

`0`

`X_(B3)`

`20`

`0`

`-1`

`0`

`1`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`S_3`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`X_(D3)`

`18`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`1`

`0`

`S_5`

`0`

`-1`

`0`

`1`

`0`

`1`

`X_(B1)`

`7`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`X_(D2)`

`12`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`X_(E4)`

`16`

`1`

`0`

`1`

`0`

`1`

`-1`

`0`

`-1`

`0`

`X_(A4)`

`15`

`0`

`1`

`0`

`1`

`-1`

`0`

`1`

`-1`

`0`

`1`

`0`

`1`

`0`

`Z=54`

`Z_j`

`6`

`13`

`19`

`15`

`7`

`14`

`20`

`16`

`7`

`14`

`20`

`16`

`5`

`12`

`18`

`14`

`7`

`14`

`20`

`16`

`-1`

`0`

`-2`

`0`

`Z_j-C_j`

`-3`

`-1`

`0`

`-3`

`0`

`-3`

`-2`

`-4`

`-1`

`-2`

`-5`

`0`

`-5`

`-3`

`-1`

`0`

`-1`

`0`

`-2`

`0`

Since all `Z_j-C_j <= 0`

Hence, optimal solution is arrived with value of variables as :
`X_(A1)=0,X_(A2)=0,X_(A3)=1,X_(A4)=0,X_(B1)=1,X_(B2)=0,X_(B3)=0,X_(B4)=0,X_(C1)=0,X_(C2)=0,X_(C3)=0,X_(C4)=0,X_(D1)=0,X_(D2)=1,X_(D3)=0,X_(D4)=0,X_(E1)=0,X_(E2)=0,X_(E3)=0,X_(E4)=1`

Min `Z=54`

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

2. Example-2