transportation problem using LP Model Formulation Example-1

1. Find Solution of Transportation Problem using LP Model Formulation
D1 D2 D3 D4 Supply
S1 19 30 50 10 7
S2 70 30 40 60 9
S3 40 8 70 20 18
Demand 5 8 7 14

Solution:
Problem Table is

	`D_1`	`D_2`	`D_3`	`D_4`	Supply
`S_1`	19	30	50	10	7
`S_2`	70	30	40	60	9
`S_3`	40	8	70	20	18

Demand	5	8	7	14

Min Z`=19X_(A1)+30X_(A2)+50X_(A3)+10X_(A4)+70X_(B1)+30X_(B2)+40X_(B3)+60X_(B4)+40X_(C1)+8X_(C2)+70X_(C3)+20X_(C4)`

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

`X_(B1)+X_(B2)+X_(B3)+X_(B4)=9`

`X_(C1)+X_(C2)+X_(C3)+X_(C4)=18`

Demand constraint
`X_(A1)+X_(B1)+X_(C1)=5`

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

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

`X_(A4)+X_(B4)+X_(C4)=14`

Problem is

Min `Z`

`=`

`19`

`X_(A1)`

` + `

`30`

`X_(A2)`

` + `

`50`

`X_(A3)`

` + `

`10`

`X_(A4)`

` + `

`70`

`X_(B1)`

` + `

`30`

`X_(B2)`

` + `

`40`

`X_(B3)`

` + `

`60`

`X_(B4)`

` + `

`40`

`X_(C1)`

` + `

`8`

`X_(C2)`

` + `

`70`

`X_(C3)`

` + `

`20`

`X_(C4)`

subject to

`X_(A1)`

` + `

`X_(A2)`

` + `

`X_(A3)`

` + `

`X_(A4)`

`7`

`X_(B1)`

` + `

`X_(B2)`

` + `

`X_(B3)`

` + `

`X_(B4)`

`9`

`X_(C1)`

` + `

`X_(C2)`

` + `

`X_(C3)`

` + `

`X_(C4)`

`18`

`X_(A1)`

` + `

`X_(B1)`

` + `

`X_(C1)`

`5`

`X_(A2)`

` + `

`X_(B2)`

` + `

`X_(C2)`

`8`

`X_(A3)`

` + `

`X_(B3)`

` + `

`X_(C3)`

`7`

`X_(A4)`

` + `

`X_(B4)`

` + `

`X_(C4)`

`14`

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

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

After introducing artificial variables

Min `Z`

`=`

`19`

`X_(A1)`

` + `

`30`

`X_(A2)`

` + `

`50`

`X_(A3)`

` + `

`10`

`X_(A4)`

` + `

`70`

`X_(B1)`

` + `

`30`

`X_(B2)`

` + `

`40`

`X_(B3)`

` + `

`60`

`X_(B4)`

` + `

`40`

`X_(C1)`

` + `

`8`

`X_(C2)`

` + `

`70`

`X_(C3)`

` + `

`20`

`X_(C4)`

` + `

`M`

`A_1`

` + `

`M`

`A_2`

` + `

`M`

`A_3`

` + `

`M`

`A_4`

` + `

`M`

`A_5`

` + `

`M`

`A_6`

` + `

`M`

`A_7`

subject to

`X_(A1)`

` + `

`X_(A2)`

` + `

`X_(A3)`

` + `

`X_(A4)`

` + `

`A_1`

`7`

`X_(B1)`

` + `

`X_(B2)`

` + `

`X_(B3)`

` + `

`X_(B4)`

` + `

`A_2`

`9`

`X_(C1)`

` + `

`X_(C2)`

` + `

`X_(C3)`

` + `

`X_(C4)`

` + `

`A_3`

`18`

`X_(A1)`

` + `

`X_(B1)`

` + `

`X_(C1)`

` + `

`A_4`

`5`

`X_(A2)`

` + `

`X_(B2)`

` + `

`X_(C2)`

` + `

`A_5`

`8`

`X_(A3)`

` + `

`X_(B3)`

` + `

`X_(C3)`

` + `

`A_6`

`7`

`X_(A4)`

` + `

`X_(B4)`

` + `

`X_(C4)`

` + `

`A_7`

`14`

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),A_1,A_2,A_3,A_4,A_5,A_6,A_7 >= 0`

Iteration-1

`C_j`

`19`

`30`

`50`

`10`

`70`

`30`

`40`

`60`

`40`

`8`

`70`

`20`

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

`A_1`

`A_2`

`A_3`

`A_4`

`A_5`

`A_6`

`A_7`

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

`A_1`

`M`

`7`

`1`

`0`

`1`

`0`

---

`A_2`

`M`

`9`

`0`

`1`

`0`

`1`

`0`

---

`A_3`

`M`

`18`

`0`

`1`

`0`

`1`

`0`

`(18)/(1)=18`

`A_4`

`M`

`5`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_5`

`M`

`8`

`0`

`1`

`0`

`1`

`0`

`(1)`

`0`

`1`

`0`

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

`A_6`

`M`

`7`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_7`

`M`

`14`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

---

`Z=68M`

`Z_j`

`2M`

`M`

`Z_j-C_j`

`2M-19`

`2M-30`

`2M-50`

`2M-10`

`2M-70`

`2M-30`

`2M-40`

`2M-60`

`2M-40`

`2M-8``uarr`

`2M-70`

`2M-20`

`0`

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

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

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

Entering `=X_(C2)`, Departing `=A_5`, Key Element `=1`

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

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

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

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

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

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

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

Iteration-2

`C_j`

`19`

`30`

`50`

`10`

`70`

`30`

`40`

`60`

`40`

`8`

`70`

`20`

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

`A_1`

`A_2`

`A_3`

`A_4`

`A_6`

`A_7`

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

`A_1`

`M`

`7`

`1`

`(1)`

`0`

`1`

`0`

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

`A_2`

`M`

`9`

`0`

`1`

`0`

`1`

`0`

---

`A_3`

`M`

`10`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_4`

`M`

`5`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(C2)`

`8`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_6`

`M`

`7`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_7`

`M`

`14`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`(14)/(1)=14`

`Z=52M+64`

`Z_j`

`2M`

`8`

`2M`

`8`

`2M`

`8`

`2M`

`M`

`Z_j-C_j`

`2M-19`

`-22`

`2M-50`

`2M-10``uarr`

`2M-70`

`-22`

`2M-40`

`2M-60`

`2M-40`

`0`

`2M-70`

`2M-20`

`0`

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

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

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

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

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

Iteration-3

`C_j`

`19`

`30`

`50`

`10`

`70`

`30`

`40`

`60`

`40`

`8`

`70`

`20`

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

`A_2`

`A_3`

`A_4`

`A_6`

`A_7`

MinRatio
`(X_B)/(X_(C4))`

`X_(A4)`

`10`

`7`

`1`

`0`

---

`A_2`

`M`

`9`

`0`

`1`

`0`

`1`

`0`

---

`A_3`

`M`

`10`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`(10)/(1)=10`

`A_4`

`M`

`5`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(C2)`

`8`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_6`

`M`

`7`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_7`

`M`

`7`

`-1`

`0`

`1`

`0`

`(1)`

`0`

`1`

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

`Z=38M+134`

`Z_j`

`10`

`-2M+18`

`10`

`2M`

`8`

`2M`

`8`

`2M`

`M`

`Z_j-C_j`

`-9`

`-2M-12`

`-40`

`0`

`2M-70`

`-22`

`2M-40`

`2M-60`

`2M-40`

`0`

`2M-70`

`2M-20``uarr`

`0`

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

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

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

Entering `=X_(C4)`, Departing `=A_7`, 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_7`(new)

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

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

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

Iteration-4

`C_j`

`19`

`30`

`50`

`10`

`70`

`30`

`40`

`60`

`40`

`8`

`70`

`20`

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

`A_2`

`A_3`

`A_4`

`A_6`

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

`X_(A4)`

`10`

`7`

`1`

`0`

`(7)/(1)=7`

`A_2`

`M`

`9`

`0`

`1`

`0`

`1`

`0`

---

`A_3`

`M`

`3`

`(1)`

`0`

`1`

`0`

`-1`

`0`

`-1`

`1`

`0`

`1`

`0`

`1`

`0`

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

`A_4`

`M`

`5`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`(5)/(1)=5`

`X_(C2)`

`8`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_6`

`M`

`7`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

---

`X_(C4)`

`20`

`7`

`-1`

`0`

`1`

`0`

`1`

`0`

---

`Z=24M+274`

`Z_j`

`2M-10`

`-2`

`2M-10`

`10`

`2M`

`8`

`2M`

`20`

`2M`

`8`

`2M`

`20`

`M`

`Z_j-C_j`

`2M-29``uarr`

`-32`

`2M-60`

`0`

`2M-70`

`-22`

`2M-40`

`-40`

`2M-40`

`0`

`2M-70`

`0`

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

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

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

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

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

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

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

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

Iteration-5

`C_j`

`19`

`30`

`50`

`10`

`70`

`30`

`40`

`60`

`40`

`8`

`70`

`20`

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

`A_2`

`A_4`

`A_6`

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

`X_(A4)`

`10`

`4`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`-1`

`0`

`-1`

`0`

---

`A_2`

`M`

`9`

`0`

`1`

`0`

`1`

`0`

`(9)/(1)=9`

`X_(A1)`

`19`

`3`

`1`

`0`

`1`

`0`

`-1`

`0`

`-1`

`1`

`0`

`1`

`0`

---

`A_4`

`M`

`2`

`0`

`-1`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`1`

`0`

---

`X_(C2)`

`8`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`A_6`

`M`

`7`

`0`

`1`

`0`

`(1)`

`0`

`1`

`0`

`1`

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

`X_(C4)`

`20`

`10`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`1`

`0`

---

`Z=18M+361`

`Z_j`

`19`

`-2`

`19`

`10`

`2M`

`2M-21`

`2M`

`2M-9`

`29`

`8`

`29`

`20`

`M`

`Z_j-C_j`

`0`

`-32`

`-31`

`0`

`2M-70`

`2M-51`

`2M-40``uarr`

`2M-69`

`-11`

`0`

`-41`

`0`

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

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

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

Entering `=X_(B3)`, Departing `=A_6`, 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)

Iteration-6

`C_j`

`19`

`30`

`50`

`10`

`70`

`30`

`40`

`60`

`40`

`8`

`70`

`20`

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

`A_2`

`A_4`

MinRatio
`(X_B)/(X_(B2))`

`X_(A4)`

`10`

`4`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`1`

`-1`

`0`

`-1`

`0`

`(4)/(1)=4`

`A_2`

`M`

`2`

`0`

`-1`

`0`

`1`

`(1)`

`0`

`1`

`0`

`-1`

`0`

`1`

`0`

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

`X_(A1)`

`19`

`3`

`1`

`0`

`1`

`0`

`-1`

`0`

`-1`

`1`

`0`

`1`

`0`

---

`A_4`

`M`

`2`

`0`

`-1`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`1`

`(2)/(1)=2`

`X_(C2)`

`8`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`(8)/(1)=8`

`X_(B3)`

`40`

`7`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

---

`X_(C4)`

`20`

`10`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`1`

`0`

---

`Z=4M+641`

`Z_j`

`19`

`-2`

`-2M+59`

`10`

`2M`

`2M-21`

`40`

`2M-9`

`29`

`8`

`-2M+69`

`20`

`M`

`Z_j-C_j`

`0`

`-32`

`-2M+9`

`0`

`2M-70`

`2M-51``uarr`

`0`

`2M-69`

`-11`

`0`

`-2M-1`

`0`

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

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

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

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

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

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

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

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

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

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

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

Iteration-7

`C_j`

`19`

`30`

`50`

`10`

`70`

`30`

`40`

`60`

`40`

`8`

`70`

`20`

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

`A_4`

MinRatio

`X_(A4)`

`10`

`2`

`0`

`1`

`-1`

`0`

`-1`

`0`

`X_(B2)`

`30`

`2`

`0`

`-1`

`0`

`1`

`0`

`1`

`0`

`-1`

`0`

`X_(A1)`

`19`

`5`

`1`

`0`

`1`

`0`

`1`

`0`

`A_4`

`M`

`0`

`1`

`X_(C2)`

`8`

`6`

`0`

`1`

`0`

`-1`

`0`

`-1`

`0`

`1`

`0`

`X_(B3)`

`40`

`7`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`X_(C4)`

`20`

`12`

`0`

`-1`

`0`

`1`

`0`

`1`

`0`

`1`

`0`

`Z=743`

`Z_j`

`19`

`-2`

`8`

`10`

`51`

`30`

`40`

`42`

`29`

`8`

`18`

`20`

`M`

`Z_j-C_j`

`0`

`-32`

`-42`

`0`

`-19`

`0`

`-18`

`-11`

`0`

`-52`

`0`

Since all `Z_j-C_j <= 0`

Hence, optimal solution is arrived with value of variables as :
`X_(A1)=5,X_(A2)=0,X_(A3)=0,X_(A4)=2,X_(B1)=0,X_(B2)=2,X_(B3)=7,X_(B4)=0,X_(C1)=0,X_(C2)=6,X_(C3)=0,X_(C4)=12`

Min `Z=743`

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