please use northwest corner method 5-13. MG Auto, of Example 5.1-1, produces fou

Question

please use northwest corner method

5-13. MG Auto, of Example 5.1-1, produces four car models: M1, M2, M3, and M4. The Detroit plant produces models M1, M2, and M4. Models M1 and M2 are also produced in New Orleans. The Los Angeles plant manufactures models M3 and M4. The capacities of the various plants and the demands at the distribution centers are given in Table 5.29. The mileage chart is the same as given in Example 5.1-1, and the transportation rate remains at 8 cents per car mile for all models. Additionally, it is possible to satisfy a percentage of the demand for some models from the supply of others according to the specifications in Table 5.30 (a) Formulate the corresponding transportation model (b) Determine the optimum shipping schedule. (Hint: Add four new destinations corre- demands at the new destinations are determined from the given percentages.) TABLE 5.27 Transportation Cost/Crate for Problem 5-11 sponding to the new combinations [M1, M2], [M3, M4], [M1, M3], and [M2, M4]. The Retailer 2 4 Orchard 1$1 Orchard 2 $2 Orchard 3 $1 $2 $4 $3 $3 $1 S5 $2 $2 $3 TABLE 5.28 Mileage Chart and Supply and Demand for Problem 5-12 Dealer 4 Supply Center 1 100 Center2 Center3 Demand 100 70 90 200 200 60 100 140 65 150 160 35 400 80 200 130 150 140 50 40 150

Explanation / Answer

TOTAL no. of supply constraints: 3
TOTAL no. of demand constraints: 2

D1

D2

Supply

S1

80

215

1000

S2

100

108

1500

S3

102

68

1200

Demand

2300

1400

Table-1

D1

D2

Supply

Row Penalty

S1

80

215

1000

135=215-80

S2

100

108

1500

8=108-100

S3

102

68

1200

34=102-68

Demand

2300

1400

Column
Penalty

20
=100-80

40
=108-68

The maximum penalty, 135, occurs in row S1.

The minimum cij in this row is c11 = 80.

The maximum allocation in this cell is 1000.
It satisfy supply of S1 and adjust the demand of D1 from 2300 to 1300 (2300 - 1000 = 1300).

Table-2

D1

D2

Supply

Row Penalty

S1

80(1000)

215

0

--

S2

100

108

1500

8=108-100

S3

102

68

1200

34=102-68

Demand

1300

1400

Column
Penalty

2
=102-100

40
=108-68

The maximum penalty, 40, occurs in column D2.

The minimum cij in this column is c32 = 68.

The maximum allocation in this cell is 1200.
It satisfy supply of S3 and adjust the demand of D2 from 1400 to 200 (1400 - 1200 = 200).

Table-3

D1

D2

Supply

Row Penalty

S1

80(1000)

215

0

--

S2

100

108

1500

8=108-100

S3

102

68(1200)

0

--

Demand

1300

200

Column
Penalty

100

108

The maximum penalty, 108, occurs in column D2.

The minimum cij in this column is c22 = 108.

The maximum allocation in this cell is 200.
It satisfy demand of D2 and adjust the supply of S2 from 1500 to 1300 (1500 - 200 = 1300).

Table-4

D1

D2

Supply

Row Penalty

S1

80(1000)

215

0

--

S2

100

108(200)

1300

100

S3

102

68(1200)

0

--

Demand

1300

0

Column
Penalty

100

--

The maximum penalty, 100, occurs in row S2.

The minimum cij in this row is c21 = 100.

The maximum allocation in this cell is 1300.
It satisfies supply of S2 and demand of D1.


Initial feasible solution is

D1

D2

Supply

Row Penalty

S1

80(1000)

215

1000

135 | -- | -- | -- |

S2

100(1300)

108(200)

1500

8 | 8 | 8 | 100 |

S3

102

68(1200)

1200

34 | 34 | -- | -- |

Demand

2300

1400

Column
Penalty

20
2
100
100

40
40
108
--

The minimum total transportation cost =80×1000+100×1300+108×200+68×1200=313200

Here, the number of allocated cells = 4 is equal to m + n - 1 = 3 + 2 - 1 = 4
This solution is non-degenerate

Optimality test using modi method...
Allocation Table is

D1

D2

Supply

S1

80 (1000)

215

1000

S2

100 (1300)

108 (200)

1500

S3

102

68 (1200)

1200

Demand

2300

1400

Iteration-1 of optimality test
1. Find ui and vj for all occupied cells(i,j), where cij=ui+vj

1. Substituting, u2=0, we get

2.c21=u2+v1v1=c21-u2v1=100-0v1=100

3.c11=u1+v1u1=c11-v1u1=80-100u1=-20

4.c22=u2+v2v2=c22-u2v2=108-0v2=108

5.c32=u3+v2u3=c32-v2u3=68-108u3=-40

D1

D2

Supply

ui

S1

80 (1000) 3.u1=?,v1=100
c11=u1+v1
u1=c11-v1
u1=80-100
u1=-20

215

1000

u1=-20 3.u1=?,v1=100
c11=u1+v1
u1=c11-v1
u1=80-100
u1=-20

S2

100 (1300) 2.v1=?,u2=0
c21=u2+v1
v1=c21-u2
v1=100-0
v1=100

108 (200) 4.v2=?,u2=0
c22=u2+v2
v2=c22-u2
v2=108-0
v2=108

1500

u2=0 1.u2=0
2.v1=?,4.v2=?,

S3

102

68 (1200) 5.u3=?,v2=108
c32=u3+v2
u3=c32-v2
u3=68-108
u3=-40

1200

u3=-40 5.u3=?,v2=108
c32=u3+v2
u3=c32-v2
u3=68-108
u3=-40

Demand

2300

1400

vj

v1=100 2.v1=?,u2=0
c21=u2+v1
v1=c21-u2
v1=100-0
v1=100
3.u1=?,

v2=108 4.v2=?,u2=0
c22=u2+v2
v2=c22-u2
v2=108-0
v2=108
5.u3=?,

2. Find dij for all unoccupied cells(i,j), where dij=cij-(ui+vj)

1.d12=c12-(u1+v2)=215-(-20+108)=127

2.d31=c31-(u3+v1)=102-(-40+100)=42

D1

D2

Supply

Ui

S1

80 (1000)

215 [127] 1.d12=c12-(u1+v2)=215-(-20+108)=127

1000

u1=-20

S2

100 (1300)

108 (200)

1500

u2=0

S3

102 [42] 2.d31=c31-(u3+v1)=102-(-40+100)=42

68 (1200)

1200

u3=-40

Demand

2300

1400

vj

v1=100

v2=108

Since all dij0.

So final optimal solution is arrived.

D1

D2

Supply

S1

80 (1000)

215

1000

S2

100 (1300)

108 (200)

1500

S3

102

68 (1200)

1200

Demand

2300

1400

The minimum total transportation cost =80×1000+100×1300+108×200+68×1200=313200

B) From the 2nd table using the percentage of the demand the final demand would be:

Denver            700      500      500      600

Miami              600      500      200      100

Denver            70        50        100      120

Miami              60        25        20        5

Total demand of Denver is 340

Total demand of Miami is 110

D1

D2

Supply

S1

80

215

1000

S2

100

108

1500

S3

102

68

1200

Demand

340

110

Solution:
TOTAL no. of supply constraints : 3
TOTAL no. of demand constraints : 2
Problem Table is

`D_1`

`D_2`

Supply

`S_1`

80

215

1000

`S_2`

100

108

1500

`S_3`

102

68

1200

Demand

340

110

Here Total Demand = 450 is less than Total Supply = 3700. So We add a dummy demand constraint with 0 unit cost and with allocation 3250.
Now, The modified table is

`D_1`

`D_2`

`D_(dummy)`

Supply

`S_1`

80

215

0

1000

`S_2`

100

108

0

1500

`S_3`

102

68

0

1200

Demand

340

110

3250

Table-1

`D_1`

`D_2`

`D_(dummy)`

Supply

Row Penalty

`S_1`

80

215

0

1000

`80=80-0`

`S_2`

100

108

0

1500

`100=100-0`

`S_3`

102

68

0

1200

`68=68-0`

Demand

340

110

3250

Column
Penalty

`20`
`=100-80`

`40`
`=108-68`

`0`
`=0-0`

The maximum penalty, 100, occurs in row `S_2`.

The minimum `c_(ij)` in this row is `c_23` = 0.

The maximum allocation in this cell is 1500.
It satisfy supply of `S_2` and adjust the demand of `D_(dummy)` from 3250 to 1750 (3250 - 1500 = 1750).

Table-2

`D_1`

`D_2`

`D_(dummy)`

Supply

Row Penalty

`S_1`

80

215

0

1000

`80=80-0`

`S_2`

100

108

0(1500)

0

--

`S_3`

102

68

0

1200

`68=68-0`

Demand

340

110

1750

Column
Penalty

`22`
`=102-80`

`147`
`=215-68`

`0`
`=0-0`

The maximum penalty, 147, occurs in column `D_2`.

The minimum `c_(ij)` in this column is `c_32` = 68.

The maximum allocation in this cell is 110.
It satisfy demand of `D_2` and adjust the supply of `S_3` from 1200 to 1090 (1200 - 110 = 1090).

Table-3

`D_1`

`D_2`

`D_(dummy)`

Supply

Row Penalty

`S_1`

80

215

0

1000

`80=80-0`

`S_2`

100

108

0(1500)

0

--

`S_3`

102

68(110)

0

1090

`102=102-0`

Demand

340

0

1750

Column
Penalty

`22`
`=102-80`

--

`0`
`=0-0`

The maximum penalty, 102, occurs in row `S_3`.

The minimum `c_(ij)` in this row is `c_33` = 0.

The maximum allocation in this cell is 1090.
It satisfy supply of `S_3` and adjust the demand of `D_(dummy)` from 1750 to 660 (1750 - 1090 = 660).

Table-4

`D_1`

`D_2`

`D_(dummy)`

Supply

Row Penalty

`S_1`

80

215

0

1000

`80=80-0`

`S_2`

100

108

0(1500)

0

--

`S_3`

102

68(110)

0(1090)

0

--

Demand

340

0

660

Column
Penalty

`80`

--

`0`

The maximum penalty, 80, occurs in row `S_1`.

The minimum `c_(ij)` in this row is `c_13` = 0.

The maximum allocation in this cell is 660.
It satisfy demand of `D_(dummy)` and adjust the supply of `S_1` from 1000 to 340 (1000 - 660 = 340).

Table-5

`D_1`

`D_2`

`D_(dummy)`

Supply

Row Penalty

`S_1`

80

215

0(660)

340

`80`

`S_2`

100

108

0(1500)

0

--

`S_3`

102

68(110)

0(1090)

0

--

Demand

340

0

0

Column
Penalty

`80`

--

--

The maximum penalty, 80, occurs in row `S_1`.

The minimum `c_(ij)` in this row is `c_11` = 80.

The maximum allocation in this cell is 340.
It satisfy supply of `S_1` and demand of `D_1`.


Initial feasible solution is

`D_1`

`D_2`

`D_(dummy)`

Supply

Row Penalty

`S_1`

80(340)

215

0(660)

1000

80 | 80 | 80 | 80 | 80 |

`S_2`

100

108

0(1500)

1500

100 | -- | -- | -- | -- |

`S_3`

102

68(110)

0(1090)

1200

68 | 68 | 102 | -- | -- |

Demand

340

110

3250

Column
Penalty

20
22
22
80
80

40
147
--
--
--

0
0
0
0
--

The minimum total transportation cost `= 80 xx 340 + 0 xx 660 + 0 xx 1500 + 68 xx 110 + 0 xx 1090 = 34680`

Here, the number of allocated cells = 5 is equal to m + n - 1 = 3 + 3 - 1 = 5
`:.` This solution is non-degenerate

Optimality test using modi method...
Allocation Table is

`D_1`

`D_2`

`D_(dummy)`

Supply

`S_1`

80 (340)

215

0 (660)

1000

`S_2`

100

108

0 (1500)

1500

`S_3`

102

68 (110)

0 (1090)

1200

Demand

340

110

3250

Iteration-1 of optimality test
1. Find `u_i` and `v_j` for all occupied cells(i,j), where `c_(ij) = u_i + v_j`

`1.` Substituting, `v_3 = 0`, we get

`2. c_13 = u_1 + v_3=>u_1 = c_13 - v_3=>u_1 = 0 -0=>u_1 = 0`

`3. c_11 = u_1 + v_1=>v_1 = c_11 - u_1=>v_1 = 80 -0=>v_1 = 80`

`4. c_23 = u_2 + v_3=>u_2 = c_23 - v_3=>u_2 = 0 -0=>u_2 = 0`

`5. c_33 = u_3 + v_3=>u_3 = c_33 - v_3=>u_3 = 0 -0=>u_3 = 0`

`6. c_32 = u_3 + v_2=>v_2 = c_32 - u_3=>v_2 = 68 -0=>v_2 = 68`

`D_1`

`D_2`

`D_(dummy)`

Supply

`u_i`

`S_1`

80 (340) `3. v_1=?,u_1=0`
`c_11 = u_1 + v_1`
`=>v_1 = c_11 - u_1`
`=>v_1 = 80 -0`
`=>v_1 = 80`

215

0 (660) `2. u_1=?,v_3=0`
`c_13 = u_1 + v_3`
`=>u_1 = c_13 - v_3`
`=>u_1 = 0 -0`
`=>u_1 = 0`

1000

`u_1=0` `2. u_1=?,v_3=0`
`c_13 = u_1 + v_3`
`=>u_1 = c_13 - v_3`
`=>u_1 = 0 -0`
`=>u_1 = 0`
`3. v_1=?`,

`S_2`

100

108

0 (1500) `4. u_2=?,v_3=0`
`c_23 = u_2 + v_3`
`=>u_2 = c_23 - v_3`
`=>u_2 = 0 -0`
`=>u_2 = 0`

1500

`u_2=0` `4. u_2=?,v_3=0`
`c_23 = u_2 + v_3`
`=>u_2 = c_23 - v_3`
`=>u_2 = 0 -0`
`=>u_2 = 0`

`S_3`

102

68 (110) `6. v_2=?,u_3=0`
`c_32 = u_3 + v_2`
`=>v_2 = c_32 - u_3`
`=>v_2 = 68 -0`
`=>v_2 = 68`

0 (1090) `5. u_3=?,v_3=0`
`c_33 = u_3 + v_3`
`=>u_3 = c_33 - v_3`
`=>u_3 = 0 -0`
`=>u_3 = 0`

1200

`u_3=0` `5. u_3=?,v_3=0`
`c_33 = u_3 + v_3`
`=>u_3 = c_33 - v_3`
`=>u_3 = 0 -0`
`=>u_3 = 0`
`6. v_2=?`,

Demand

340

110

3250

`v_j`

`v_1=80` `3. v_1=?,u_1=0`
`c_11 = u_1 + v_1`
`=>v_1 = c_11 - u_1`
`=>v_1 = 80 -0`
`=>v_1 = 80`

`v_2=68` `6. v_2=?,u_3=0`
`c_32 = u_3 + v_2`
`=>v_2 = c_32 - u_3`
`=>v_2 = 68 -0`
`=>v_2 = 68`

`v_3=0` `1. v_3 = 0`
`2. u_1=?`,`4. u_2=?`,`5. u_3=?`,

2. Find `d_(ij)` for all unoccupied cells(i,j), where `d_(ij) = c_(ij) - (u_i + v_j)`

1. d_12 = c_12 - (u_1 + v_2) = 215 - (0 +68) = 147

2. d_21 = c_21 - (u_2 + v_1) = 100 - (0 +80) = 20

3. d_22 = c_22 - (u_2 + v_2) = 108 - (0 +68) = 40

4. d_31 = c_31 - (u_3 + v_1) = 102 - (0 +80) = 22

`D_1`

`D_2`

`D_(dummy)`

Supply

`u_i`

`S_1`

80 (340)

215 [147] `1. d_12 = c_12 - (u_1 + v_2) = 215 - (0 +68) = 147 `

0 (660)

1000

`u_1=0`

`S_2`

100 [20] `2. d_21 = c_21 - (u_2 + v_1) = 100 - (0 +80) = 20 `

108 [40] `3. d_22 = c_22 - (u_2 + v_2) = 108 - (0 +68) = 40 `

0 (1500)

1500

`u_2=0`

`S_3`

102 [22] `4. d_31 = c_31 - (u_3 + v_1) = 102 - (0 +80) = 22 `

68 (110)

0 (1090)

1200

`u_3=0`

Demand

340

110

3250

`v_j`

`v_1=80`

`v_2=68`

`v_3=0`

Since all `d_(ij)>=0`.

So final optimal solution is arrived

`D_1`

`D_2`

`D_(dummy)`

Supply

`S_1`

80 (340)

215

0 (660)

1000

`S_2`

100

108

0 (1500)

1500

`S_3`

102

68 (110)

0 (1090)

1200

Demand

340

110

3250

The minimum total transportation cost `= 80 xx 340 + 0 xx 660 + 0 xx 1500 + 68 xx 110 + 0 xx 1090 = 34680`

D1

D2

Supply

S1

80

215

1000

S2

100

108

1500

S3

102

68

1200

Demand

2300

1400

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.