transportation problem using LP Model Formulation Example-2

Find Solution of Transportation Problem using LP Model Formulation
D1 D2 D3 D4 Supply
S1 4 6 8 13 50
S2 13 11 10 8 70
S3 14 4 10 13 30
S4 9 11 16 8 50
Demand 25 35 105 20

Solution:
Problem Table is

	`D_1`	`D_2`	`D_3`	`D_4`	Supply
`S_1`	4	6	8	13	50
`S_2`	13	11	10	8	70
`S_3`	14	4	10	13	30
`S_4`	9	11	16	8	50

Demand	25	35	105	20

Min Z`=4X_(A1)+6X_(A2)+8X_(A3)+13X_(A4)+13X_(B1)+11X_(B2)+10X_(B3)+8X_(B4)+14X_(C1)+4X_(C2)+10X_(C3)+13X_(C4)+9X_(D1)+11X_(D2)+16X_(D3)+8X_(D4)`

Supply constraint
`X_(A1)+X_(A2)+X_(A3)+X_(A4)<=50`

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

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

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

Demand constraint
`X_(A1)+X_(B1)+X_(C1)+X_(D1)=25`

`X_(A2)+X_(B2)+X_(C2)+X_(D2)=35`

`X_(A3)+X_(B3)+X_(C3)+X_(D3)=105`

`X_(A4)+X_(B4)+X_(C4)+X_(D4)=20`

Problem is

Min `Z`

`=`

`4`

`X_(A1)`

` + `

`6`

`X_(A2)`

` + `

`8`

`X_(A3)`

` + `

`13`

`X_(A4)`

` + `

`13`

`X_(B1)`

` + `

`11`

`X_(B2)`

` + `

`10`

`X_(B3)`

` + `

`8`

`X_(B4)`

` + `

`14`

`X_(C1)`

` + `

`4`

`X_(C2)`

` + `

`10`

`X_(C3)`

` + `

`13`

`X_(C4)`

` + `

`9`

`X_(D1)`

` + `

`11`

`X_(D2)`

` + `

`16`

`X_(D3)`

` + `

`8`

`X_(D4)`

subject to

`X_(A1)`

` + `

`X_(A2)`

` + `

`X_(A3)`

` + `

`X_(A4)`

≤

`50`

`X_(B1)`

` + `

`X_(B2)`

` + `

`X_(B3)`

` + `

`X_(B4)`

≤

`70`

`X_(C1)`

` + `

`X_(C2)`

` + `

`X_(C3)`

` + `

`X_(C4)`

≤

`30`

`X_(D1)`

` + `

`X_(D2)`

` + `

`X_(D3)`

` + `

`X_(D4)`

≤

`50`

`X_(A1)`

` + `

`X_(B1)`

` + `

`X_(C1)`

` + `

`X_(D1)`

`25`

`X_(A2)`

` + `

`X_(B2)`

` + `

`X_(C2)`

` + `

`X_(D2)`

`35`

`X_(A3)`

` + `

`X_(B3)`

` + `

`X_(C3)`

` + `

`X_(D3)`

`105`

`X_(A4)`

` + `

`X_(B4)`

` + `

`X_(C4)`

` + `

`X_(D4)`

`20`

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) >= 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 artificial variable `A_1`

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

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

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

After introducing slack,artificial variables

Min `Z`

`=`

`4`

`X_(A1)`

` + `

`6`

`X_(A2)`

` + `

`8`

`X_(A3)`

` + `

`13`

`X_(A4)`

` + `

`13`

`X_(B1)`

` + `

`11`

`X_(B2)`

` + `

`10`

`X_(B3)`

` + `

`8`

`X_(B4)`

` + `

`14`

`X_(C1)`

` + `

`4`

`X_(C2)`

` + `

`10`

`X_(C3)`

` + `

`13`

`X_(C4)`

` + `

`9`

`X_(D1)`

` + `

`11`

`X_(D2)`

` + `

`16`

`X_(D3)`

` + `

`8`

`X_(D4)`

` + `

`0`

`S_1`

` + `

`0`

`S_2`

` + `

`0`

`S_3`

` + `

`0`

`S_4`

` + `

`M`

`A_1`

` + `

`M`

`A_2`

` + `

`M`

`A_3`

` + `

`M`

`A_4`

subject to

`X_(A1)`

` + `

`X_(A2)`

` + `

`X_(A3)`

` + `

`X_(A4)`

` + `

`S_1`

`50`

`X_(B1)`

` + `

`X_(B2)`

` + `

`X_(B3)`

` + `

`X_(B4)`

` + `

`S_2`

`70`

`X_(C1)`

` + `

`X_(C2)`

` + `

`X_(C3)`

` + `

`X_(C4)`

` + `

`S_3`

`30`

`X_(D1)`

` + `

`X_(D2)`

` + `

`X_(D3)`

` + `

`X_(D4)`

` + `

`S_4`

`50`

`X_(A1)`

` + `

`X_(B1)`

` + `

`X_(C1)`

` + `

`X_(D1)`

` + `

`A_1`

`25`

`X_(A2)`

` + `

`X_(B2)`

` + `

`X_(C2)`

` + `

`X_(D2)`

` + `

`A_2`

`35`

`X_(A3)`

` + `

`X_(B3)`

` + `

`X_(C3)`

` + `

`X_(D3)`

` + `

`A_3`

`105`

`X_(A4)`

` + `

`X_(B4)`

` + `

`X_(C4)`

` + `

`X_(D4)`

` + `

`A_4`

`20`

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),S_1,S_2,S_3,S_4,A_1,A_2,A_3,A_4 >= 0`

Iteration-1

`C_j`

`4`

`6`

`8`

`13`

`11`

`10`

`8`

`14`

`4`

`10`

`13`

`9`

`11`

`16`

`8`

`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)`

`S_1`

`S_2`

`S_3`

`S_4`

`A_1`

`A_2`

`A_3`

`A_4`

MinRatio
`(X_B)/(X_(A1))`

`S_1`

`0`

`50`

`1`

`0`

`1`

`0`

`(50)/(1)=50`

`S_2`

`0`

`70`

`0`

`1`

`0`

`1`

`0`

---

`S_3`

`0`

`30`

`0`

`1`

`0`

`1`

`0`

---

`S_4`

`0`

`50`

`0`

`1`

`0`

`1`

`0`

---

`A_1`

`M`

`25`

`(1)`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

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

`A_2`

`M`

`35`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_3`

`M`

`105`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_4`

`M`

`20`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

---

`Z=185M`

`Z_j`

`M`

`0`

`M`

`Z_j-C_j`

`M-4``uarr`

`M-6`

`M-8`

`M-13`

`M-11`

`M-10`

`M-8`

`M-14`

`M-4`

`M-10`

`M-13`

`M-9`

`M-11`

`M-16`

`M-8`

`0`

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

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

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

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

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

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

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

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

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

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

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

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

Iteration-2

`C_j`

`4`

`6`

`8`

`13`

`11`

`10`

`8`

`14`

`4`

`10`

`13`

`9`

`11`

`16`

`8`

`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)`

`S_1`

`S_2`

`S_3`

`S_4`

`A_2`

`A_3`

`A_4`

MinRatio
`(X_B)/(X_(C2))`

`S_1`

`0`

`25`

`0`

`1`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

---

`S_2`

`0`

`70`

`0`

`1`

`0`

`1`

`0`

---

`S_3`

`0`

`30`

`0`

`1`

`(1)`

`1`

`0`

`1`

`0`

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

`S_4`

`0`

`50`

`0`

`1`

`0`

`1`

`0`

---

`X_(A1)`

`4`

`25`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_2`

`M`

`35`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`(35)/(1)=35`

`A_3`

`M`

`105`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_4`

`M`

`20`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

---

`Z=160M+100`

`Z_j`

`4`

`M`

`4`

`M`

`4`

`M`

`4`

`M`

`0`

`M`

`Z_j-C_j`

`0`

`M-6`

`M-8`

`M-13`

`-9`

`M-11`

`M-10`

`M-8`

`-10`

`M-4``uarr`

`M-10`

`M-13`

`-5`

`M-11`

`M-16`

`M-8`

`0`

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

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

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

Entering `=X_(C2)`, Departing `=S_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_5`(new)`= R_5`(old)

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

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

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

Iteration-3

`C_j`

`4`

`6`

`8`

`13`

`11`

`10`

`8`

`14`

`4`

`10`

`13`

`9`

`11`

`16`

`8`

`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)`

`S_1`

`S_2`

`S_3`

`S_4`

`A_2`

`A_3`

`A_4`

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

`S_1`

`0`

`25`

`0`

`1`

`-1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`(25)/(1)=25`

`S_2`

`0`

`70`

`0`

`1`

`0`

`1`

`0`

---

`X_(C2)`

`4`

`30`

`0`

`1`

`0`

`1`

`0`

---

`S_4`

`0`

`50`

`0`

`1`

`0`

`1`

`0`

---

`X_(A1)`

`4`

`25`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_2`

`M`

`5`

`0`

`(1)`

`0`

`1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`-1`

`0`

`1`

`0`

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

`A_3`

`M`

`105`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_4`

`M`

`20`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

---

`Z=130M+220`

`Z_j`

`4`

`M`

`4`

`M`

`-M+8`

`4`

`M`

`0`

`-M+4`

`0`

`M`

`Z_j-C_j`

`0`

`M-6``uarr`

`M-8`

`M-13`

`-9`

`M-11`

`M-10`

`M-8`

`-M-6`

`0`

`-6`

`-9`

`-5`

`M-11`

`M-16`

`M-8`

`0`

`-M+4`

`0`

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

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

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

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

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

`R_1`(new)`= R_1`(old) - `R_6`(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_7`(new)`= R_7`(old)

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

Iteration-4

`C_j`

`4`

`6`

`8`

`13`

`11`

`10`

`8`

`14`

`4`

`10`

`13`

`9`

`11`

`16`

`8`

`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)`

`S_1`

`S_2`

`S_3`

`S_4`

`A_3`

`A_4`

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

`S_1`

`0`

`20`

`0`

`(1)`

`1`

`-1`

`0`

`1`

`-1`

`0`

`1`

`0`

`1`

`0`

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

`S_2`

`0`

`70`

`0`

`1`

`0`

`1`

`0`

---

`X_(C2)`

`4`

`30`

`0`

`1`

`0`

`1`

`0`

---

`S_4`

`0`

`50`

`0`

`1`

`0`

`1`

`0`

---

`X_(A1)`

`4`

`25`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(A2)`

`6`

`5`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`-1`

`0`

---

`A_3`

`M`

`105`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`(105)/(1)=105`

`A_4`

`M`

`20`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

---

`Z=125M+250`

`Z_j`

`4`

`6`

`M`

`4`

`6`

`M`

`2`

`4`

`M-2`

`4`

`6`

`M`

`0`

`-2`

`0`

`M`

`Z_j-C_j`

`0`

`M-8``uarr`

`M-13`

`-9`

`-5`

`M-10`

`M-8`

`-12`

`0`

`M-12`

`M-15`

`-5`

`M-16`

`M-8`

`0`

`-2`

`0`

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

Minimum ratio is `20` 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_1`(new)

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

Iteration-5

`C_j`

`4`

`6`

`8`

`13`

`11`

`10`

`8`

`14`

`4`

`10`

`13`

`9`

`11`

`16`

`8`

`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)`

`S_1`

`S_2`

`S_3`

`S_4`

`A_3`

`A_4`

MinRatio
`(X_B)/(X_(B4))`

`X_(A3)`

`8`

`20`

`0`

`1`

`-1`

`0`

`1`

`-1`

`0`

`1`

`0`

`1`

`0`

---

`S_2`

`0`

`70`

`0`

`1`

`0`

`1`

`0`

`(70)/(1)=70`

`X_(C2)`

`4`

`30`

`0`

`1`

`0`

`1`

`0`

---

`S_4`

`0`

`50`

`0`

`1`

`0`

`1`

`0`

---

`X_(A1)`

`4`

`25`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(A2)`

`6`

`5`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`-1`

`0`

---

`A_3`

`M`

`85`

`0`

`-1`

`1`

`0`

`-1`

`1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

---

`A_4`

`M`

`20`

`0`

`1`

`0`

`(1)`

`0`

`1`

`0`

`1`

`0`

`1`

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

`Z=105M+410`

`Z_j`

`4`

`6`

`8`

`M-4`

`M-2`

`M`

`2`

`4`

`6`

`M-4`

`M-2`

`M`

`-M+8`

`0`

`-M+6`

`0`

`M`

`Z_j-C_j`

`0`

`-5`

`M-17`

`M-13`

`M-10`

`M-8``uarr`

`-12`

`0`

`-4`

`-7`

`M-13`

`M-16`

`M-8`

`-M+8`

`0`

`-M+6`

`0`

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

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

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

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

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

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

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

`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)

Iteration-6

`C_j`

`4`

`6`

`8`

`13`

`11`

`10`

`8`

`14`

`4`

`10`

`13`

`9`

`11`

`16`

`8`

`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)`

`S_1`

`S_2`

`S_3`

`S_4`

`A_3`

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

`X_(A3)`

`8`

`20`

`0`

`1`

`-1`

`0`

`1`

`-1`

`0`

`1`

`0`

`1`

`0`

---

`S_2`

`0`

`50`

`0`

`-1`

`1`

`(1)`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

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

`X_(C2)`

`4`

`30`

`0`

`1`

`0`

`1`

`0`

---

`S_4`

`0`

`50`

`0`

`1`

`0`

`1`

`0`

---

`X_(A1)`

`4`

`25`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(A2)`

`6`

`5`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`-1`

`0`

---

`A_3`

`M`

`85`

`0`

`-1`

`1`

`0`

`-1`

`1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`(85)/(1)=85`

`X_(B4)`

`8`

`20`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`Z=85M+570`

`Z_j`

`4`

`6`

`8`

`-M+16`

`M-4`

`M-2`

`M`

`8`

`2`

`4`

`6`

`-M+14`

`M-4`

`M-2`

`M`

`8`

`-M+8`

`0`

`-M+6`

`0`

`M`

`Z_j-C_j`

`0`

`-M+3`

`M-17`

`M-13`

`M-10``uarr`

`0`

`-12`

`0`

`-4`

`-M+1`

`M-13`

`M-16`

`0`

`-M+8`

`0`

`-M+6`

`0`

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

Minimum ratio is `50` 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_2`(new)

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

Iteration-7

`C_j`

`4`

`6`

`8`

`13`

`11`

`10`

`8`

`14`

`4`

`10`

`13`

`9`

`11`

`16`

`8`

`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)`

`S_1`

`S_2`

`S_3`

`S_4`

`A_3`

MinRatio
`(X_B)/(X_(D4))`

`X_(A3)`

`8`

`20`

`0`

`1`

`-1`

`0`

`1`

`-1`

`0`

`1`

`0`

`1`

`0`

---

`X_(B3)`

`10`

`50`

`0`

`-1`

`1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

---

`X_(C2)`

`4`

`30`

`0`

`1`

`0`

`1`

`0`

---

`S_4`

`0`

`50`

`0`

`1`

`0`

`1`

`0`

`(50)/(1)=50`

`X_(A1)`

`4`

`25`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(A2)`

`6`

`5`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`-1`

`0`

---

`A_3`

`M`

`35`

`0`

`1`

`-1`

`0`

`1`

`(35)/(1)=35`

`X_(B4)`

`8`

`20`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`(1)`

`0`

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

`Z=35M+1070`

`Z_j`

`4`

`6`

`8`

`6`

`8`

`10`

`8`

`2`

`4`

`6`

`4`

`M-4`

`M-2`

`M`

`M-2`

`-M+8`

`-M+10`

`-M+6`

`0`

`M`

`Z_j-C_j`

`0`

`-7`

`-3`

`0`

`-12`

`0`

`-4`

`-9`

`M-13`

`M-16`

`M-10``uarr`

`-M+8`

`-M+10`

`-M+6`

`0`

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

Minimum ratio is `20` and its row index is `8`. So, the leaving basis variable is `X_(B4)`.

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

Entering `=X_(D4)`, Departing `=X_(B4)`, Key Element `=1`

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

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

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

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

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

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

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

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

Iteration-8

`C_j`

`4`

`6`

`8`

`13`

`11`

`10`

`8`

`14`

`4`

`10`

`13`

`9`

`11`

`16`

`8`

`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)`

`S_1`

`S_2`

`S_3`

`S_4`

`A_3`

MinRatio
`(X_B)/(X_(D1))`

`X_(A3)`

`8`

`20`

`0`

`1`

`-1`

`0`

`1`

`-1`

`0`

`1`

`0`

`1`

`0`

---

`X_(B3)`

`10`

`70`

`0`

`1`

`0`

`1`

`0`

---

`X_(C2)`

`4`

`30`

`0`

`1`

`0`

`1`

`0`

---

`S_4`

`0`

`30`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`1`

`0`

`1`

`0`

`(30)/(1)=30`

`X_(A1)`

`4`

`25`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`(25)/(1)=25`

`X_(A2)`

`6`

`5`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`-1`

`0`

---

`A_3`

`M`

`15`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`(1)`

`1`

`0`

`-1`

`0`

`1`

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

`X_(D4)`

`8`

`20`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`Z=15M+1270`

`Z_j`

`4`

`6`

`8`

`-M+16`

`6`

`8`

`10`

`-M+18`

`2`

`4`

`6`

`-M+14`

`M-4`

`M-2`

`M`

`8`

`-M+8`

`-M+10`

`-M+6`

`0`

`M`

`Z_j-C_j`

`0`

`-M+3`

`-7`

`-3`

`0`

`-M+10`

`-12`

`0`

`-4`

`-M+1`

`M-13``uarr`

`M-13`

`M-16`

`0`

`-M+8`

`-M+10`

`-M+6`

`0`

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

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

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

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

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

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

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

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

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

Iteration-9

`C_j`

`4`

`6`

`8`

`13`

`11`

`10`

`8`

`14`

`4`

`10`

`13`

`9`

`11`

`16`

`8`

`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)`

`S_1`

`S_2`

`S_3`

`S_4`

MinRatio

`X_(A3)`

`8`

`35`

`0`

`1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`X_(B3)`

`10`

`70`

`0`

`1`

`0`

`1`

`0`

`X_(C2)`

`4`

`30`

`0`

`1`

`0`

`1`

`0`

`S_4`

`0`

`15`

`0`

`1`

`X_(A1)`

`4`

`10`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`1`

`0`

`X_(A2)`

`6`

`5`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`-1`

`0`

`X_(D1)`

`9`

`15`

`0`

`-1`

`0`

`-1`

`0`

`-1`

`1`

`0`

`-1`

`0`

`X_(D4)`

`8`

`20`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`Z=1465`

`Z_j`

`4`

`6`

`8`

`3`

`6`

`8`

`10`

`5`

`2`

`4`

`6`

`1`

`9`

`11`

`13`

`8`

`-5`

`-3`

`-7`

`0`

`Z_j-C_j`

`0`

`-10`

`-7`

`-3`

`0`

`-3`

`-12`

`0`

`-4`

`-12`

`0`

`-3`

`0`

`-5`

`-3`

`-7`

`0`

Since all `Z_j-C_j <= 0`

Hence, optimal solution is arrived with value of variables as :
`X_(A1)=10,X_(A2)=5,X_(A3)=35,X_(A4)=0,X_(B1)=0,X_(B2)=0,X_(B3)=70,X_(B4)=0,X_(C1)=0,X_(C2)=30,X_(C3)=0,X_(C4)=0,X_(D1)=15,X_(D2)=0,X_(D3)=0,X_(D4)=20`

Min `Z=1465`

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

2. Example-2