Tugasan 2Sebuah organisasi mempunyai pejabat cawangan di A, B, C, D, E, F, G dan H. Jadual di bawah menunjukkan kos penghantaran bungkusan (Ringgit Malaysia per kilogram) dari satu pejabat ke pejabat yang lain dengan perkhidmatan pengangkutan yang sedia ada.

ABCDEFGH

A-1289----

B12-6-10---

C86-10-10--

D9-10---12-

E-10---11-20

F--10-11-1818

G---12-18-14

H----201814-

(i)Bina satu rangkaian dengan menggunakan bucu-bucu A hingga H untuk mewakili maklumat yang ditunjukkan dalam Jadual di atas.

(ii)Suatu bungkusan perlu dihantar dari pejabat A ke semua pejabat yang lain, sama ada secara langsung atau melalui pejabat lain. Guna Algoritma Prim atau Kruskal untuk menentukan jumlah kos yang minimum untuk penghantaran bungkusan ke semua pejabat.

(iii)Pejabat C memiliki perkhidmatan tambahan tersendiri. Perkhidmatan tambahan itu membolehkan Pejabat C menghantar bungkusan dengan separuh kos asal. Walaubagaimanapun, perkhidmatan itu tidak merendahkan kos penerimaan bungkusan. Hitungkan kos minimum untuk menghantar bungkusan dari pejabat A ke pejabat lain dengan menggunakan perkhidmatan tambahan Pejabat C.

Penyelesaian :

(i)Rangkaian

(ii) Algoritma Kruskal dipilih untuk mencari penyelesaian menentukan jumlah kos yang minimum untuk penghantaran bungkusan ke semua pejabat. Lengkuk pada jadual disusun mengikut urutan menaik kos penghantaran bungkusan.Kos Penghantaran Bungkusan

(RM per kilogram)Lengkuk

6CB

8AC

9AD

10BE, CD, CF

11EF

12AB, DG

14GH

18FG, FH

20EH

Jadual 1Langkah 1 : Pilih lengkuk yang paling pendek terlebih dahulu iaitu BC.

Langkah 2 : Pilih lengkuk AC.

Langkah 3 : Pilih lengkuk AD.

Langkah 4 : Pilih lengkuk BE.

Langkah 5 : Lengkuk CD tidak dipilih kerana D telah berkait melalui A. Seterusnya pilih lengkuk

CF.

Langkah 6 : Lengkuk EF tidak dipilih kerana E telah berkait melaluit B dan C. Lengkuk AB tidak dipilih juga kerana B telah berkait melalui C. Pilih lengkuk DG.

Langkah 7 : Pilih lengkuk GH.

Langkah 8 : Lengkuk FG, FH dan EH tidak dipilih kerana semua titik telah disambung. Penyelesaian adalah seperti pokok rentang dibawah.

Kos minimum = AC + AD + CB + CF + BE+ DG + GH

= 8 + 9 + 6 + 10 + 10 + 12 + 14

= 69

Jumlah kos yang minimum untuk penghantaran bungkusan ke semua pejabat ialah RM 69 per kilogram.(iii) Rangkaian baru dengan syarat tambahan.

Jadual kos penghantaran bungkusan baru berdasarkan rangkaian baru.

Kos Penghantaran Bungkusan

(RM per kilogram)Lengkuk

3CB

5CF, CD

8AC

9AD

10BE

11EF

12AB, DG

14GH

18FG, FH

20EH

Jadual 2Pokok rentang yang baru dilukis mengikut Jadual 2.

Langkah 1 : Pilih lengkuk yang paling pendek iaitu lengkuk CB.

Langkah 2 : Pilih lengkuk CF dan CD.

Langkah 3 : Pilih lengkuk AC.

Langkah 4 : Lengkuk AD tidak dipilih kerana D telah dikait melalui C. Seterusnya, lengkuk BE dipilih.

Langkah 5 : Lengkuk EF tidak dipilih kerana E telah dikait melalui B dan C. Lengkuk seterusnya yang dipilih ialah AB dan DG.

Langkah 6 : Pilih lengkuk GH.

Langkah 7 : Suatu pokok rentang yang mempunyai syarat tambahan telah dihasilkan.

Kos Penghantaran Bungkusan dengan menggunakan perkhidmatan tambahan pejabat C.Kos Penghantaran Bungkusan

(RM per kilogram)Lengkuk

3CB

5CF, CD

8AC

9AD

10BE

12AB, DG

14GH

20EH

Jumlah kos penghantaran bungkusan = RM 3 + RM 5 + RM 5 + RM 8 + RM 9 + RM 10 + RM 12 + RM 12 + RM 14 + RM 20

= RM 57

Jumlah kos penghantaran bungkusan adalah RM 57 akan tetapi kos ini hanya untuk kos penghantarann bagi CB, CF, CD, AC, BE, AB, DG, GH dan EH sahaja. Kos penerimaan adalah seperti berikut :

Kos penerimaan bagi lengkuk BC adalah RM 6 dan FH adalah RM 10 dan lengkuk lain adalah sama kerana kos penerimaan bungkusan tidak mendapat potongan separuh daripada kos asal. Jadi, jumlah kos minimum untuk menghantar bungkusan dari Pejabat A ke Pejabat lain dengan menggunakan perkhidmatan tambahan Pejabat C adalah seperti berikut :Kos minimum = RM 57+ RM 6 + RM 10

= RM 73

A

B

C

D

E

F

G

H

12

14

12

20

18

10

18

10

11

9

8

10

6

H

F

E

D

C

B

A

G

H

F

E

D

C

B

A

G

H

F

E

D

C

B

A

G

H

F

E

D

C

B

A

G

H

F

E

D

C

B

A

G

H

F

E

D

C

B

A

G

H

F

E

D

C

B

A

G

H

F

E

D

C

B

A

G

H

F

E

D

C

B

A

G

6

6

6

6

8

6

8

9

6

8

9

10

10

8

9

6

10

10

8

9

10

10

8

9

6

12

10

10

8

9

H

12

14

10

F

E

12

14

D

C

B

A

G

3

5

8

9

11

10

18

5

18

20

12

14

12

H

F

E

D

C

B

A

G

H

F

E

D

C

B

A

G

H

F

E

D

C

B

A

G

H

F

E

D

C

B

A

G

H

F

E

D

C

B

A

G

H

F

E

D

C

B

A

G

H

F

E

D

C

B

A

G

3

3

5

3

5

8

3

5

5

8

3

5

5

10

8

5

3

5

10

8

5

3

5

12

10

8

5

H

F

12

14

10

E

5

12

14

D

C

B

A

G

6

10

8

10

5

12

14