• Author / Uploaded
• Roi Milyardi

Citation preview

1. Problem 9-14 Hardrock Concrete’s owner has decided to increase the capacity at his smallest plant (see Problem 9-13). Instead of producing 30 loads of concrete per day at plant 3, that plant’s capacity is doubled to 60 loads.  Find the new optimal solution using the northwest corner rule and stepping-stone method.  How has changing the third plant’s capacity altered the optimal shipping assignment ? Discuss the concepts of degeneracy and multiple optimal solutions with regard to this problem. Answer : Initial Feasibel Solution Using Northwest Corner Rules To From

Project A

Plant 1

40

Plant 2

-

Plant 3

-

Project Requirements

40

Note: occupied squares

Project B

10

12

9

30

20

-

50

Project Dummy

Project C

4 10

5

7

-

30

30

60

11 10

8

6

-

-

30

30

= number rows + number columns – 1 3+4–1=6

Plant Capacities

0

0

0

70

50

60

180

Transport cost : Route From Plant 1 Plant 1 Plant 2 Plant 2 Plant 3 Plant 3

to Project A Project B Project B Project C Project C Dummy

Unit Shipped

Cost per Unit

Total Cost ( $ )

10 4 5 8 6 0

400 120 100 240 180 0 1040

40 30 20 30 30 30 Total

Diketahui total biaya awal (sebelum dioptimasi) adalah sebesar $ 1040. Selanjutnya dilakukan perhitungan apakah total biaya transportasi tesebut dapat dikurangi atau tidak.

Check for optimal solution  Plant 1 to Project C = 11 – 4 + 5 – 8 = 4 Closed Path: P1C – P1B + P2B – P2C  Plant 1 to dummy = 0 – 4 + 5 – 8 + 6 – 0 = -1 Closed Path: P1D – P1B + P2B – P2C +P3C – P3D  Plant 2 to Project A = 12 – 5 + 4 – 10 = 1 Closed Path: P2A – P2B + P1B – P1A  Plant 2 to dummy = 0 – 8 + 6 – 0 = -2 Closed Path: P2D – P2C + P3C – P3D  Plant 3 to Project A = 9 – 6 + 8 – 5 + 4 – 10 = 0 Closed Path: P3A – P3C + P2C – P2B + P1B –P1A  Plant 3 to Project B = 7 – 6 + 8 – 5 = 4 Closed Path: P3B - P3C + P2C – P2B Setelah dilakukan beberapa percobaan menggunakan stepping-stone method, didapat nilai terkecil yaitu -2, sehingga perubahan tabel menjadi seperti berikut:

First Solution To From

Project A

Plant 1

40

Plant 2

-

Plant 3

-

Project Requirements

40

occupied squares

Project B

10

30

12

9

20

-

50

Project Dummy

Project C

4 10

11 10

-

5

8

7

60

60

6

Plan Capacities

0

-

30

0

30

0

0

70

50

60

180

= number rows + number columns – 1 3 + 4 – 1 = 6 (tidak cocok)

Karena jumlah kotak yang terisi hanya 5, maka kotak “plant 3-dummy” diisi angka ‘0”, sehingga jumlah kotak yang terisi menjadi 6 Check for optimal solution  Plant 1 to Project C = 11 – 6 + 0 – 0 + 5 – 4 = 6 Closed Path: P1C – P3C + P3dummy – P2dummy + P2B – P1B  Plant 1 to dummy =0–0+5–4=1 Closed Path: P1dummy – P2dummy + P2B – P1B

 Plant 2 to Project A = 12 – 5 + 4 – 10 = 1 Closed Path: P2A – P2B + P1B – P1A  Plant 2 to Project C = 8 – 6 + 0 -0 = 2 Closed Path: P2C – P3C + P3dummy – P2dummy  Plant 3 to Project A = 9 – 0 + 0 – 5 + 4 – 10 = -2 Closed Path: P3A – P3dummy + P2dummy – P2B + P1B – P1A  Plant 3 to Project B = 7 – 0 + 0 – 5 = 2 Closed Path: P3B - P3dummy + P2dummy – P2B Karena masih ada yang negatif, hal ini menunjukkan bahwa masih dapat dioptimasi lagi. Second solution To From

Project A

Plant 1

Plant 2

40

Project Requirements

0

40

10

30

12

-

Plant 3

Project B

9

20

-

50

Project Dummy

Project C

4 10

11 10

-

5

8

7

60

60

Plan Capacities

0

-

30

6

0

0

30

70

50

60

180

occupied squares

= number rows + number columns – 1 3 + 4 – 1 = 6 ( sesuai)

Check for optimal solution  Plant 1 to Project C Closed Path:

= 11 – 10 + 9 – 6 = 4

 Plant 1 to dummy Closed Path:

=0–4+5–0=1

 Plant 2 to Project A Closed Path:

= 12 – 5 + 4 – 10 = 1

 Plant 2 to Project C Closed Path:

= 8 – 5 + 4 – 10 + 9 – 6 = 0

 Plant 3 to Project B Closed Path:

= 7 – 4 + 10 – 9 = 4

 Plant 3 to dummy Closed Path:

= 0 – 0 + 5 – 4 + 10 – 9 = 2

Semua hasil perhitungan telah menghasilkan hasil yang positif, dengan angka terkecil yaitu “0”, hal ini menunjukkan bahwa operasi yang dilakukan telah menghasilkan hasil yang optimum atau paling hemat. Besarnya biaya minimum yang dikeluarkan untuk transportasi tersebut ditunjukkan pada tabel berikut. Route Unit Shipped

Cost per Unit

Total Cost ($)

Project A

40

10

400

Plant 1

Project B

30

4

120

Plant 2

Project B

20

5

100

Plant 2

Project dummy

30

0

0

Plant 3

Project dummy

0

9

0

Plant 3

Project C

60

6

360

From

to

Plant 1

Total

980

Berdasarkan model terakhir, didapatkan biaya transportasi sebesar $ 980. Hal ini menunjukkan bahwa terjadi penghematan sebesar $ 1040 - $ 980 = $ 60 2. Problem 9-15 Formulate the Hardrock Concrete Company transportation problem in 9-13 as a linear transportation program and solve using computer software. What would change in the linear program if the change program in problem 9-14 were implemented?

Answer : Input data Data COSTS Plant 1 Plant 2 Plant 3 Demand

Project A Project B Project C Dummy Supply 10 4 11 0 70 12 5 8 0 50 9 7 6 0 60 40 50 60 30 180 \ 180

Shipments Shipments Project A Project B Project C Dummy Row Total Plant 1 40 30 70 Plant 2 20 30 50 Plant 3 30 30 60 Column Total 40 50 60 30 180 \ 180 Total Cost

1040

Output data Data COSTS Plant 1 Plant 2 Plant 3 Demand

Project A Project B Project C Dummy Supply 10 4 11 0 70 12 5 8 0 50 9 7 6 0 60 40 50 60 30 180 \ 180

Shipments Shipments Project A Project B Project C Dummy Row Total Plant 1 20 50 0 0 70 Plant 2 0 0 20 30 50 Plant 3 20 0 40 0 60 Column Total 40 50 60 30 180 \ 180 Total Cost

980

Berdasarkan hasil software QM, dapat dilihat bahwa hasil yang dilakukan dengan cara manual ( soal 9-14 ) adalah menghasilkan hasil yang sama ketika dikerjakan menggunakan software QM, yaitu sebesar $ 980

3. Problem 9-21 Finnish Furniture manufactures tables in facilities located in three cities—Reno, Denver, and Pittsburgh. The tables are then shipped to three retail stores located in Phoenix, Cleveland, and Chicago. Management wishes to develop a distribution schedule that will meet the demands at the lowest possible cost. The shipping cost per unit from each of the sources to each of the destinations is shown in the following table: To

Phoenix

Cleveland

Chicago

Reno

10

16

19

Denver

12

14

13

From

Pittsburgh

18

12

12

The available supplies are :  120 units from Reno  200 from Denver  160 from Pittsburgh Phoenix has a demand of 140 units, Cleveland has a demand of 160 units, and Chicago has a demand of 180 units. How many units should be shipped from each manufacturing facility to each of the retail stores if cost is to be minimized? What is the total cost? Answer : To From

Phoenix (A)

Reno (D)

120

Denver (E)

20

Pittsburgh (F)

-

Project Requirements

140

10

Cleveland (B)

18

16 10

-

12

Chicago (C)

160

-

160

14

12

19

20

160

180

13

12

Plan Capacities

120

200

160

480

Route From Reno Denver Denver Denver Pittsburg

to Pheonix Pheonix Cleveland Chicago Chicago

Unit Shipped

Cost per Unit

Total Cost ( $ )

10 12 14 13 12

1200 240 2240 260 1920 5860

120 20 160 20 160 Total

Stepping-stone method  Reno to Cleveland = 16 – 10 + 12 – 14 = 4 Closed Path: DB – DA + EA – EB  Reno to Chicago = 19 – 10 + 12 – 13 = 8 Closed Path: DC – DA + EA – EC  Pittsburgh to Phoenix= 18 – 12 + 13 – 12 = 7 Closed Path: FA – FC + EC - EA  Pittsburgh to Phoenix= 12 – 12 + 13 – 14 = -1 Closed Path: FB – FC + EC – EB Terdapat nilai minus 1 pada rute Pittsburgh ke phoenix. Hal ini menunjukkan bahwa operasi masih bisa dilakukan perbaikan untuk mendapatkan biaya yang paling minimum.

To From

Phoenix (A)

Reno (D)

120

Denver (E)

20

10

12

Cleveland (B)

-

-

16 10

14

Chicago (C)

-

180

19

13

Plan Capacities

120

200

Pittsburgh (F)

-

Project Requirements

140

18

160

160

12

-

180

12

160

480

Stepping-stone method  Reno to Chicago Closed Path:

= 19 – 10 + 12 – 13 = 8

DC – DA + EA – EC

Reno to Cleveland Denver to Clevelad Pittsburgh to Phoenix Pittsburgh to Chicago

= Tidak dapat dilakukan stepping-stone method = Tidak dapat dilakukan stepping-stone method = Tidak dapat dilakukan stepping-stone method = Tidak dapat dilakukan stepping-stone method

Tidak terdapat hasil yang negatif, sehingga proses iterasi dapat dihentikan. Total cost hasil optimasi dapat dilihat pada tabel berikut: Route From Reno Denver Pittsburg Denver

to Pheonix Pheonix Cleveland Chicago

Unit Shipped 120 20 160 180 Total

Cost per Unit

Total Cost ( $ )

10 12 12 13

1200 240 1920 2340 5700

Sehingga total cost yang minimum adalah sebesar $ 5700, dimana Cleveland mendapatkan supply dari Pittsburg sebanyak yang dibutuhkan Cleveland yaitu sebanyak 160. Begitupula dengan Chicago, yang mendapatkan supply sebanyak 180 dari Denver. Sementara Phoenix harus men supply dari dua tempat, yaitu dari Reno sebesar 120 dan dari Denver sebesar 20.

4. Problem 9-22 Finnish Furniture has experienced a decrease in the demand for tables in Chicago; the demand has fallen to 150 units (see Problem 9-21).  What special condition would exist?  What is the minimum-cost solution?  Will there be any units remaining at any of the manufacturing facilities? First Solution To From

Phoenix (A)

Cleveland (B)

Chicago (C)

Plan Capacities

Dummy 0

Reno (D)

120

10

16 10

-

19

120 0

Denver (E)

20

Pittsburgh (F)

-

Project Requirements

140

12

18

160

14

12

-

160

20

130

12

150

Cost for first alternatif = (120x10)+(20x12)+(160x14)+(20x13)+(130x12) = $5500 Stepping-stone Method  Reno to Cleveland  Reno to Chicago  Reno to Dummy

0

13

= 16 – 14 + 12 - 10 = 4 = 19 – 10 + 12 - 13 = 8 = 0 – 10 + 12 –13+12-0= 1

200

30

160

480

 Denver to Dummy = 0 – 13 + 12 - 0  Pittsburgh to Phoenix = 18 – 12 + 13 - 12  Pittsburgh to Cleveland = 12 – 12 + 13 - 14 = -1

= -1 = 7

Masih terdapat nilai yang negatif, sehingga perlu dilakukan iterasi Second solution To From

Phoenix (A)

Cleveland (B)

Chicago (C)

Plan Capacities

Dummy 0

Reno (D)

120

10

16 10

-

19

120 0

Denver (E)

20

Pittsburgh (F)

-

Project Requirements

140

12

18

30

130

160

14

150

12

0

13

12

200

30

150

480

Cost for second alternatif = (120x10)+(20x12)+(30x14)+(150x13)+(130x12) = $5370 Stepping-stone Method • • • •

Reno to Cleveland Reno to Chicago Reno to Dummy Denver to Dummy

= 16 – 14 + 12 - 10 = 19 – 10 + 12 - 13 = 0 – 10 + 12 – 14 + 12 - 0 = 0 – 14 + 12 - 0

160

= 4 = 8 = 0 = -2

• •

Pittsburgh to Phoenix = 18 – 12 + 14 - 12 Pittsburgh to Chicago = 12 – 13 + 14 - 12

= 8 = 1

Masih ada yang negatif, sehingga harus dilakukan iterasi lagi Third solution To From

Phoenix (A)

Cleveland (B)

Chicago (C)

Plan Capacities

Dummy 0

Reno (D)

120

10

16 10

-

19

120 0

Denver (E)

20

Pittsburgh (F)

-

Project Requirements

140

12

18

14

160

160

150

12

13

12

0

30

0

150

Reno to Cleveland Reno to Chicago Reno to Dummy Denver to Cleveland Pittsburgh to Phoenix Pittsburgh to Chicago

= 16 – 12 + 0 – 0 + 12 - 10 = 19 – 10 + 12 - 13 = 0 – 0 + 12 - 10 = 14 – 0 + 0 - 12 = 18 – 0 + 0 - 12 = 12 – 0 + 0 - 13

160

480

Cost for third alternatif = (120x10)+(20x12)+(150x13)+(30x0)+(160x12) = $5310 Stepping-stone Method      

200

= 6 = 8 = 2 = 2 = 6 =0

Sudah tidak ada yang negatif, hal ini menunjukkan bahwa sudah didapatkan komposisi yang optimum atau paling hemat. Yaitu sebesar $5310 atau terdapat penghematan sebesar $190 5. Problem 9.35 Don Levine Corporation is considering adding an additional plant to its three existing facilities in Decatur, Minneapolis, and Carbondale. Both St. Louis and East St. Louis are being considered. Evaluating only the transportation costs per unit as shown in the tables below and on the next page, which site is best? Answer : East St. Louis First Solution

From Decatur To

Minneapolis

Carbondale

17

20

East St. Louis

21

Supply Capacity 29

Blue Earth

250 250 25

Ciro

50

27

30

150

200 25

22

Des moines

20

22

30

50

150

150

350

200

150

150

800

Demand 300 Capacity Cost for first alternatif = (250x20)+(50x25)+(150x27)+(50x25)+(150x22)+(150x30) = 19,350 Stepping-stone method      

Decatur to Des Moines = 22-25+27-25 = -1 Minneapolis to Blue E = 17-27+25-20 = -5 Carbondale to Blue E = 21-22+25-27+25-20 = 2 Carbondale to Ciro = 20-22+25-27 = -4 East St. to Blue E = 29-30+25-27+25-20 = 2 East St. to Ciro = 30-30+25-27 = -2

Second Solution From Decatur To

Minneapolis

20

Blue Earth

Carbondale

17

East St. Louis

21

Supply Capacity 29

150

250

100 25

Ciro

27

20

30

200

200 25

22

Des moines

22

30

50

150

150

350

200

150

150

800

Demand 300 Capacity Cost for second alternatif = (100x20)+(200x25)+(150x17)+(50x25)+(150x22)+(150x30) = 18,600 Using the stepping-stone method, the following improvement indices are computed: Path:      

Decatur to Des Moines Minneapolis to Ciro Carbondale to Blue E Carbondale to Ciro East St. to Blue E East St. to Ciro

= 22-25+17-20 = -6 = 27-17+20-25 = 5 = 21-17+25-22 = 7 = 20-25+20-17+25-22 = 1 = 29-30+25-17 = 7 = 30-25+20-17+25-30 = 3

Third Solution From Decatur To

Minneapolis

20

Blue Earth

Carbondale

17

East St. Louis

21

Supply Capacity 29

200

250

50 25

Ciro

27

30

200

200 25

22

Des moines

20

50

22

30

150

150

350

150

150

800

Demand 300

200

Capacity

Cost for third alternatif = (50x20)+(200x25)+( 50x22)+(200x17)+(150x22)+(150x30) = 18,300

Using the stepping-stone method, the following improvement indices are computed: Path:      

Minneapolis to Ciro = 27-17+20-25 = 5 Minneapolis to Des M = 25-17+20-22 = 6 Carbondale to Blue E = 21-22+22-20 = 1 Carbondale to Ciro = 20-22+22-25 = -5 East St. to Blue E = 29-30+22-20 = -1 East St. to Ciro = 30-30+22-25 = -3

Fourth Solution From Decatur To

Minneapolis 17

20

Blue Earth

Carbondale

East St. Louis

21

Supply Capacity 29

200

250

50 25

Ciro

27

50

30

150 25

22

Des moines

20

200 22

200

30

150

350

150

800

Demand 300

200

150

Capacity Cost for fourth alternatif = (50x20)+(50x25)+( 200x22)+(200x17)+(150x20)+(150x30) = 17,550 Using the stepping-stone method, the following improvement indices are computed: Path:      

Minneapolis to Ciro = 27-17+20-25 = 5 Minneapolis to Des M = 25-17+20-22 = 6 Carbondale to Blue E = 21-20+25-20 = 6 Carbondale to Des M = 22-20+25-22 = 5 East St. to Blue E = 29-30+22-20 = -1 East St. to Ciro = 30-30+22-25 = -3

Fifth Solution From Decatur To

Minneapolis 17

20

Blue Earth

Carbondale

East St. Louis

21

Supply Capacity 29

200

250

50 25

27

Ciro

20

30

150 25

22

Des moines

50 22

200 30

250

100

350

150

800

Demand 300

200

150

Capacity Cost for fifth alternatif = (50x20)+( 250x22)+(200x17)+(150x20)+(50x30)+(100x30) = 17,400 Using the stepping-stone method, the following improvement indices are computed: Path:      

Decatur to Ciro = 25-30+30-22 = Minneapolis to Ciro = 27-30+30-22+20-17 = Minneapolis to Des M = 25-17+20-22 = 6 Carbondale to Blue E = 21-20+22-30+30-20 = Carbondale to Des M = 22-30+30-20 = 2 East St. to Blue E = 29-30+22-20 =

3 8 3 1

Kesimpulan : Transportation cost, which additional plant East St. Louis

= 17,400

Transportation cost, which additional plant St. Louis

= 17,250

Optimal Solution, additional plant St. Louis

= 17,250

St. Louis First Solution From Decatur To

Minneapolis

20

Carbondale

17

St. Louis

21

Supply Capacity

27

Blue Earth

250 250 25

Ciro

50

27

20

28

150 25

22

Des moines

200 22

31

50

150

150

350

200

150

150

800

Demand 300 Capacity

Cost for first alternatif = (250x20)+(50x25)+(150x27)+(50x25)+(150x22)+(150x31) = 19,500

Using the stepping-stone method, the following improvement indices are computed: Path:      

Decatur to Des Moines = 22-25+27-25 = -1 Minneapolis to Blue E = 17-27+25-20 = -5 Carbondale to Blue E = 21-20+25-27+25-22 = 2 Carbondale to Ciro = 20-22+25-27 = -4 St.Louis to Blue E = 27-31+25-27+25-20 = -1 St.Louis to Ciro = 28-31+25-27 = -5

Second Solution From Decatur To

Minneapolis 17

20

Blue Earth

Carbondale

St. Louis

21

Supply Capacity

27

150

250

100 25

Ciro

27

20

28

200

200 25

22

Des moines

22

31

50

150

150

350

200

150

150

800

Demand 300 Capacity

Cost for second alternatif : = (100x20)+(200x25)+(150x17)+(50x25)+(150x22)+(150x31) = 18,750 Using the stepping-stone method, the following improvement indices are computed: Path:      

Decatur to Des Moines Minneapolis to Ciro Carbondale to Blue E Carbondale to Ciro St.Louis to Blue E St.Louis to Ciro

= 22-25+17-20 = -6 = 27-17+20-25 = 5 = 21-22+25-17 = 7 = 20-25+20-17+25-22 = 1 = 27-31+25-17 = 4 = 28-31+25-17+20-25 = 0

Third Solution From Decatur To

Minneapolis 17

20

Blue Earth

Carbondale

St. Louis

21

Supply Capacity

27

200

250

50 25

Ciro

27

28

200

200 25

22

Des moines

20

50

22

31

150

150

350

150

150

800

Demand 300

200

Capacity

Cost for third alternatif = (50x20)+(200x25)+(50x22)+(200x17)+(150x22)+(150x30) = 18,300 Using the stepping-stone method, the following improvement indices are computed: Path:      

Minneapolis to Ciro Minneapolis to Des M. Carbondale to Blue E Carbondale to Ciro St.Louis to Blue E St.Louis to Ciro

= 27-17+20-25 = 5 = 25-17+20-22 = 6 = 21-22+22-20 = 1 = 20-25+22-22 = -5 = 27-31+22-20 = -2 = 28-31+22-25 = -6

Fourth Solution From Decatur To

Minneapolis 17

20

Blue Earth

Carbondale

St. Louis

21

Supply Capacity

27

200

250

50 25

Ciro

27

20

50

150 25

22

Des moines

28

200

22

200 31

150

350

Demand 300

200

150

150

800

Capacity Cost for fourth alternatif = (50x20)+(50x25)+(200x22)+(200x17)+(150x22)+(150x28) = 17,550 Using the stepping-stone method, the following improvement indices are computed: Path:      

Minneapolis to Ciro Minneapolis to Des M. Carbondale to Blue E Carbondale to Ciro St.Louis to Blue E St.Louis to Des M.

= 27-17+20-25 = 5 = 25-17+20-22 = 6 = 21-22+22-20 = 1 = 20-25+22-22 = -5 = 27-28+25-20 = 4 = 31-28+25-22 = 6

Fifth Solution From Decatur To

Minneapolis 17

20

Blue Earth

Carbondale

St. Louis

21

Supply Capacity

27

200

250

50 25

27

Ciro

50 25

22

Des moines

20

250

28

150 22

200 31

100

350

Demand 300

200

150

150

800

Capacity

Cost for fifth alternatif = (50x20)+(250x22)+(200x17)+(50x20)+(100x22)+(150x28) = 17,300 Using the stepping-stone method, the following improvement indices are computed: Path:      

Decatur to Ciro Minneapolis to Ciro Minneapolis to Des M. Carbondale to Blue E St.Louis to Blue E St.Louis to Des M.

= 25-20+22-22 = 5 = 27-20+22-22+20-17 = 10 = 25-22+20-17 = 6 = 21-20+22-22 = 1 = 27-28+20-22+22-20 = -1 = 31-28+20-22 = 1

Sixth Solution 22

From Decatur

To

Minneapolis 17

20

Blue Earth

Carbondale

St. Louis

21

Supply Capacity

27

200

250 50

25

27

Ciro

100 25

22

Des moines

20

300

28

100 22

200 31

50

350

Demand 300

200

150

150

800

Capacity

Cost for sixth alternatif = (300x22)+(200x17)+(100x20)+(50x22)+(50x27)+(100x28) = 17,250 Using the stepping-stone method, the following improvement indices are computed: Path:      

Decatur to Blue E = 20-22+22-20+28-27 = Decatur to Ciro = 25-20+22-22 = Minneapolis to Ciro = 27-28+27-17 = Minneapolis to Des M. = 25-22+20-28+27-17 = Carbondale to Blue E = 21-27+28-20 = 2 St.Louis to Des M. = 31-28+20-22 =

Diperoleh biaya minimum sebesar 17,250.

1 5 9 5 1