Masalah Tugasan: Hungarian Method

24
Masalah Tugasan: Masalah Tugasan: Hungarian Method Hungarian Method

description

Masalah Tugasan: Hungarian Method. Kaedah Hungarian. Kaedah Hungarian menyelesaikan masalah peminimuman tugasan dengan m pekerja dan m tugasan. Pertimbangan khas termasuklah:. Bilangan pekerja tidak sama dengan bilangan tugas – tambahkan pekerja dummy atau tugas dengan kos tugasan 0 diperlukan. - PowerPoint PPT Presentation

Transcript of Masalah Tugasan: Hungarian Method

Page 1: Masalah Tugasan: Hungarian Method

Masalah Tugasan:Masalah Tugasan:Hungarian MethodHungarian MethodMasalah Tugasan:Masalah Tugasan:

Hungarian MethodHungarian Method

Page 2: Masalah Tugasan: Hungarian Method

Kaedah HungarianKaedah Hungarian

Kaedah Hungarian menyelesaikan Kaedah Hungarian menyelesaikan masalah peminimuman tugasan dengan masalah peminimuman tugasan dengan m pekerja dan m tugasan. m pekerja dan m tugasan.

Page 3: Masalah Tugasan: Hungarian Method

Pertimbangan khas termasuklah:Pertimbangan khas termasuklah:

Bilangan pekerja tidak sama dengan bilangan Bilangan pekerja tidak sama dengan bilangan tugas – tambahkan pekerja dummy atau tugas tugas – tambahkan pekerja dummy atau tugas dengan kos tugasan 0 diperlukandengan kos tugasan 0 diperlukan

Pekerja Pekerja ii tidak boleh melakukan tugasan tidak boleh melakukan tugasan jj – – letakkan letakkan ccijij = + = +MM

Obbjektif pemaksimuman – binakan matrik kos Obbjektif pemaksimuman – binakan matrik kos lepas dengan menolakkan semua keuntungan lepas dengan menolakkan semua keuntungan dari setiap tugasan dari keuntungan maksimum dari setiap tugasan dari keuntungan maksimum sebelum memulakan kaedah Hungarian sebelum memulakan kaedah Hungarian

Page 4: Masalah Tugasan: Hungarian Method

Langkah 1: Bagi setiap baris, tolakkan angka yang minimum dari semua nombor didalam baris tersebut.

Langkah 2: Bagi setiap lajur, tolakkan nombor yang minimum dari semua nombor didalam lajur tersebut.

Langkah-langkah Kaedah HungarianLangkah-langkah Kaedah Hungarian

Page 5: Masalah Tugasan: Hungarian Method

Langkah 3: Lukiskan bilangan garisan yang minimum untuk menutupi semua sifar. Jika nombor ini = m, BERHENTI – tugasan boleh dilakukan

Langkah 4: Kurangkan d (nombor minimum yang tidak ditutupi) dari nombor Tambah d bagi nombor dipersilangan dua garisan. Nombor yang ditutupi garisan masih lagi sama. Kemudia PERGI KE LANGKAH 3

Langkah-langkah Kaedah HungarianLangkah-langkah Kaedah Hungarian

Page 6: Masalah Tugasan: Hungarian Method

Mencari bilangan garisan minimum dan menentukan penyelesaian optimum

1. Langkah 1: Cari baris atau lajur dengan hanya satu sifar yang tidak ditutupi garis dan bulatkan. (Jika semua baris/lajur mempunyai dua atau lebih sifar yang tidak digaris pilih mana-mana sifar secara arbitrari)

Page 7: Masalah Tugasan: Hungarian Method

Langkah 2: Jika bulatan terletak didalam baris dengan satu sifar, lukiskan garisan melalui lajur. Jika bulatan didalam lajur mempunyai satu sifar, lukiskan garisan melalui baris. Satu mendekatan, jika semua baris dan lajur mempunyai dua atau lebih sifar, lukiskan garisan merisan yang melalui banyak sifar.

Langkah 3: Ulang langkah 2 sehungga semua bulatan digariskan. Jika bilangan garisan minimum sama dengan m, bulatan tersebut memberikan tugasan yang optimum

Page 8: Masalah Tugasan: Hungarian Method

ContohContoh Menyediakan Jadual Awal

Oleh kerana algorithma memerlukan bilangan baris dan lajur yang sama, tambahkan lajur Dummy oleh itu jadual pertama Oleh kerana algorithma memerlukan bilangan baris dan lajur yang sama, tambahkan lajur Dummy oleh itu jadual pertama adalah:adalah:

AA BB CC DummyDummy Westside 50 36 16 0Westside 50 36 16 0

Federated Federated 28 30 18 028 30 18 0 Goliath Goliath 35 32 20 035 32 20 0 Universal Universal 25 25 14 025 25 14 0

Page 9: Masalah Tugasan: Hungarian Method

Langkah 1: Tolakkan nombor minimum didalam setiap baris dari semua nombor didalam baris tersebut. Oleh kerana setiap baris mempunyai angka sifar, kita hanya membina matirk yang sama seperti diatas.

Langkah 2: Tolakkan nombor minimum didalam setiap lajur dari semua no,mbor didalam lajur. Bagi A ia adalah 25, B = 25, C = 14, Dummy = 0. Ini menghasilkan:

AA BB CC DummyDummy Westside 25 11 2 0Westside 25 11 2 0 Federated 3 5 4 0Federated 3 5 4 0 Goliath Goliath 10 7 6 10 7 6 00 Universal Universal 0 0 0 0 0 0 0 0

Page 10: Masalah Tugasan: Hungarian Method

Langkah 3: Lukiskan bilangan garisan minimum yang dapat menutupi semua sifar. Walaupun kita dapat melihatnya dengan jelas, gunakan algorithma berikut. Jika baris yang “masih tinggal” mempunyai hanya satu sifar, lukiskan garisan melalui lajur. Jika lajur yang masih tinggal mempunyai hanya satu sifar, lukiskan garisan melalui baris.

A B C Dummy Westside 25 11 2 0

Federated 3 5 4 0 Goliath 10 7 6 0 Universal 0 0 0 0

Page 11: Masalah Tugasan: Hungarian Method

Langkah 4: Nombor minimum yang tidak ditutupi ialah 2. Tolakkan 2 dari semua nombor yang tidak ditutupi oleh garisan; tambahkan 2 kepada sumua nombor dipersilangan dua garisan. Ini memberikan

A B C Dummy

Westside 23 9 0 0

Federated 1 3 2 0

Goliath 8 5 4 0

Universal 0 0 0 2

+2+2

Page 12: Masalah Tugasan: Hungarian Method

Langkah 3: Lukiskan bilangan garisan minimum untuk menutupi semua sifar.

A B C Dummy

Westside 23 9 0 0 Federated 1 3 2 0 Goliath 8 5 4 0 Universal 0 0 0 2

Page 13: Masalah Tugasan: Hungarian Method

Langkah 4: Angka minimum bagi nombor yang tidak digaris ialah 1. Tolakkan 1 dari semua nombor yang tidak digaris. Tambah 1 kepada nombor dipersimpangan dua garis. Ini memberikan:

A B C Dummy Westside 23 9 0 1

Federated 0 2 1 0 Goliath 7 4 3 0 Universal 0 0 0 3

+1+1

Page 14: Masalah Tugasan: Hungarian Method

AA BB CC DummyDummy

Westside 23 9 0 0 Westside 23 9 0 0

Federated 0 2 1 0 Federated 0 2 1 0

Goliath 7 4 3 0 Goliath 7 4 3 0

Universal 0 0 0 2Universal 0 0 0 2

Page 15: Masalah Tugasan: Hungarian Method

Langkah 3: Bilangan garisan minimum yang menutupi semua 1 ialah 4. Oleh itu, ia merupakan tugasan kos minimum 0 dengan jadual ini. Tugasan optimum ialah:

Subcontractor Project Distance

Westside C 16

Federated A 28

Goliath (unassigned)

Universal B 25

Total Distance = 69 miles

Page 16: Masalah Tugasan: Hungarian Method

ContohContoh

Projek 1 Projek 2 Projek 3 Projek 4 Projek 5

A 29.9 31.9 34.5 32.8 29.8

B 32.8 34.9 32.8 34.0 31.2

C 30.7 30.3 29.8 31.2 32.4

D 29.9 34.9 33.7 31.6 33.3

Page 17: Masalah Tugasan: Hungarian Method

Projek 1 Projek 2 Projek 3 Projek 4 Projek 5

A 29.9 31.9 34.5 32.8 29.8

B 32.8 34.9 32.8 34.0 31.2

C 30.7 30.3 29.8 31.2 32.4

D 29.9 34.9 33.7 31.6 33.3

Dummy 0.0 0.0 0.0 0.0 0.0

Page 18: Masalah Tugasan: Hungarian Method

Projek 1 Projek 2 Projek 3 Projek 4 Projek 5

A 0.1 2.1 4.7 3.0 0.0

B 1.6 3.7 1.6 2.8 0.0

C 0.9 0.5 0.0 1.4 2.6

D 0.0 5.0 3.8 1.7 3.4

Dummy 0.0 0.0 0.0 0.00.0

+0.5

Page 19: Masalah Tugasan: Hungarian Method

Projek 2 Projek 3 Projek 4 Projek 5

A 0.1 1.6 4.7 2.5 0.0

B 1.6 3.2 1.6 2.3 0.0

C 0.9 0.0 0.0 0.9 2.6

D 0.0 4.5 3.8 1.2 3.4

Dummy 0.5 0.0 0.5 0.0 0.5

Projek 1

+1.2

Page 20: Masalah Tugasan: Hungarian Method

Projek 1 Projek 2 Projek 3 Projek 4 Projek 5

A 0.1 0.4 3.5 1.3 0.0

B 1.6 2.0 0.4 1.1 0.0

C 2.1 0.0 0.0 0.9 3.8

D 0.0 3.3 2.6 0.0 3.4

Dummy 1.7 0.0 0.5 0.0 1.7

Page 21: Masalah Tugasan: Hungarian Method

Projek 1 Projek 2 Projek 3 Projek 4 Projek 5

A 0.0 0.3 3.4 1.2 0.0

B 1.5 1.9 0.3 1.0 0.0

C 2.1 0.0 0.0 0.9 3.9

D 0.0 3.3 2.6 0.0 3.5

Dummy 1.7 0.0 0.5 0.0 1.8

Page 22: Masalah Tugasan: Hungarian Method

Projek 1 Projek 2 Projek 3 Projek 4 Projek 5

A 0.0 0.3 3.4 1.2 0.0

B 1.5 1.9 0.3 1.0 0.0

C 2.1 0.0 0.0 0.9 3.9

D 0.0 3.3 2.6 0.0 3.5

Dummy 1.7 0.0 0.5 0.0 1.8

Page 23: Masalah Tugasan: Hungarian Method

Projek Pegawai Kos

1 A 29.90

2 Tidak ditugaskan 0.00

3 C 29.80

4 D 31.60

5 B 31.20

Jumlah 122.50

Page 24: Masalah Tugasan: Hungarian Method