Teka-Teki Jembatan Konigsberg

A.      Latar Belakang

Graf merupakan salah satu cabang ilmu matematika yang merepresentasikan objek – objek diskrit dan hubungan antara objek – objek tersebut. Representasi visual dari graf adalah dengan menyatakan obyek dengan noktah dan hubungan antara objeknya dengan garis. Untuk selanjutnya kita sebut noktah pada graf sebagai simpul (vertex) dan garis pada graf sebagai sisi (edge).

Konigsberg, sebuah kota di bagian utara Jerman, memiliki  sebuah  kisah  terkenal yang memberikan pengaruh besar pada kehidupan seorang  bernama  Euler  dan  sejarah perkembangan teori Graf. Sungai Pregel yang melalui Konigsberg membagi wilayah daratan pada kota tersebut menjadi empat bagian. Tujuh buah jembatan dibangun di atas sungai tersebut pada bagian yang memungkinkan untuk bepergian antar keempat wilayah tersebut. Pada abad ke-17, warga Konigsberg gemar berjalan di tepi sungai, hingga  akhirnya  beberapa  dari  mereka memikirkan apakah mungkin untuk berjalan di Konigsberg dan melalui setiap jembatan hanya sekali. Hal inilah yang kemudian disebut Teka-Teki Jembatan Konigsberg yang tidak dapat terselesaikan untuk waktu yang cukup lama dan menjadi terkenal di seluruh negeri.

Teka-teki tersebut menarik perhatian Euler, yang diyakini ketika itu berada di St. Petersburg.  Ia kemudian meneliti  bahwa  kasus  tersebut  dapat direpsersentasikan dalam sebuah diagram Gbr1. Setelah  sekian  banyak  kegagalan  warga Konigsberg untuk menemukan cara melalui seluruh jembatan hanya sekali, hingga akhirnya pada tahun 1736 masalah tersebut dijadikan sebuah kasus matematika dan kemustahilan untuk menyelesaikan teka-teki tersebut terbukti.

B.       Pembahasan

Dalam kasus jembatan Konigsberg huruf C akan muncul sebanyak tiga kali (BAC, DAC, BDC) karena terdapat lima jembatan yang menyusun jalan menuju C. Kemudian, karena tiga jembatan menyusun jalan menuju A, maka A akan muncul sebanyak dua kali (CDA, BDA). Dengan cara serupa kita dapatkan bahwa kemunculan B dan D juga dua kali. Maka dalam kombinasi delapan huruf sebagai solusi dengan kemunculan huruf ,C dan D sebanyak masing-masing dua kali, ternyata kombinasi seperti itu tidak mungkin ada, sehingga kesimpulannya adalah bahwa teka-teki Konigsberg adalah mustahil.

Tujuh jembatan di Königsberg adalah permasalahan matematika yang cukup terkenal yang diinspirasi oleh keadaan nyata pada masa itu. Kota Königsberg, Prussia (sekarang Kaliningrad,  Russia) dibagi oleh sungai Pregel menjadi 2 daratan utama yang dihubungkan oleh 7 buah jembatan satu sama lain. Pertanyaannya adalah apakah sauatu hal yang mungkin untuk berjalan melintasi setiap jembatan sebanyak satu kali dan kembali pada tempat semula. Pada 1736, Leonhard Euler menyatakan bahwa hal itu tidaklah mungkin.

1.    Solusi Euler

Untuk membuktikan hasilnya, Euler memformulakan masalah itu dalam teori graf, dengan menganalogikan pada kasus Königsberg. Pertama, dengan mengeliminasi  semua fitur kecuali daratan dan jembatan yang menghubungkannya; kedua, dengan mengganti daratan dengan titik, disebut simpul(vertex) dan tiap jembatan dengan garis. Disebut sisi (edge). Hasil struktur matematikanya disebut graf. Bentuk dari graf dapat diubah-ubah dalam berbagai cara tanpa mengubah graf itu sendiri, selama sisi dari simpul tidak diubah. Tidak bermasalah antara sisi yang berbentuk lurus atau lengkung, atau simpul yang terletak di sisi kiri atau kanan sisi lainnya. Euler menyadari bahwa masalah itu dapat diselesaikan berdasarkan derajat dari simpul–simpulnya. Derajat dari tiap simpul adalah jumlah sisi yang bersinggungan dengannya, pada graf jembatan Königsberg, tiga simpul mempunyai derajat 3 dan salah satu berderajat 5. Euler menunjukkan sirkuit yang kita inginkan hanya mungkin jika tidak ada simpul yang berderajat negatif. Cara perjalanan itu disebut sirkuit euler. Karena graf Königsberg ini mempunyai 4 simpul yang berderajat ganjil maka graf ini tidak mempunyai sirkuit euler.

Masalah ini dapat dikembangkan seperti beriku ini, ketika kita diminta untuk menyusun rute yang melintasi semua jembatan tapi tidak perlu punya titik mula dan akhir yang sama. Lintasan ini disebut lintasan Euler. Lintasan ini dimungkinkan ada jika dan hanya jika:

a)    Graf ini tidak punya simpul yang berderajat ganjil.

b)   Tepat ada 2 simpul yang berderajat ganjil, dan kedua simpul itu akan menjadi titil awal dan akhir. (ini juga hal yang mustahil untuk graf jembatan Königsberg).

2.  Signifikasi dalam sejarah matematika

Pada sejarah perkembangan matematika, solusi Euler tentang jembatan Königsberg dianggap sebagai teorema pertama dari teori graf, yang sekarang digeneralisasi sebagai cabang ilmu kombinatorial (meskipun masalah kombinatorial telah ditemukan sebelumnya). Sebagai tambahan, sesuai pengakuan Euler bahwa kuncinya  terletak pada jumlah jembatan dan daftar dari titik akhirnya (lebih dari posisi aslinya) ditandai dengan perkembangan tipologi. Perbedaan antara layout nyata dan skema graf adalah contoh yang bagus dari ide bahwa topologi tidak berpatokan pada bentuk asli benda.

3.  Keadaan jembatan itu sekarang

Dua dari tujuh jembatan asli hancur saat pengeboman sekutu ke Königsberg pada Perang Dunia II. Dua lainnya dirusak oleh Rusia dan diganti dengan jambatan modern.Tinggal 3 lainnya yang tersisa, meskipun hanya ada 2 yang berasal dari masa Euler (salah satu dibangun ulang oleh Jerman pada 1935). Menurut teori graf, dua dari simpul sekarang mempunyai derajat 2, dan 2 lainnya punya derajat 3. Karena itu, sekarang lintasan Euler mungkin dapat dibentuk, tapi karena harus dimulai dari sebuah pulau dan berakhir pada pulau yang berbeda.

C.      Kesimpulan

Teka-teki jembatan Konigsberg adalah mustahil. Teka-Teki Jembatan Konigsberg telah membuka jalan bagi terciptanya teorema baru yang disebut teorema graf. Aplikasi teorema graf menganalogikan setiap jembatan sebagai sisi dan setiap daratan sebagai simpul pada graf, sehingga terbentuk sebuah graf lengkap. Dan dengan memperhitungkan derajat dari setiap simpul yang terdapat dalam graf, menggunakan metode yang diungkapkan dalam pembuktian di atas, kita akan dapat  mengetahui  apakah  graf tersebut merupakan suatu lintasan di mana setiap sisi dilalui hanya satu kali saja. Fakta bahwa teorema graf lahir ketika Euler menyelesaikan masalah berdasarkan Teka-Teki Jembatan Konigsberg menyatakan hubungan tersendiri antara jaringan spasial (seperti jalur transportasi) dengan graf.

Makalah Masalah Penugasan

BAB I

PENDAHULUAN

A.           Latar Belakang

Pemrograman Linier disingkat PL merupakan metode matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimumkan keuntungan dan meminimumkan biaya. PL banyak diterapkan dalam masalah ekonomi, industri, militer, social dan lain-lain. PL berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier.

Masalah transportasi berkaitan dengan keterbatasan sumber daya atau kapasitas perusahaan yang harus didistribusikan ke berbagai tujuan, kebutuhan atau aktivitas. Dengan demikian manfaat utama dari mempelajari masalah transportasi ini adalah mengoptimalkan distribusi sumberdaya tersebut sehingga mendapatkan hasil atau biaya yang optimal.

Masalah penugasan (assignment problem), seperti juga masalah transportasi merupakan suatu kasus khusus yang ditemui dalam pemrograman linear. Permasalahan penugasan atau assignment problem adalah suatu persoalan dimana harus melakukan penugasan terhadap sekumpulan orang yang kepada sekumpulan job yang ada, sehingga tepat satu orang yang bersesuaian dengan tepat satu job yang ada. Misalkan setiap 4 orang dengan 4 job yang ada menghasilkan 4! yaitu 24 kemungkinan yang ada. Namun yang dicari disini atau fungsi objektifnya adalah mencari biaya seminimum mungkin sehingga dalam penugasan ini bagi orang yang melakukan penugasan dapat mengeluarkan biaya seminimum mungkin. Walaupun untuk menyelesaikan masalah penugasan ini dapat digunakan metode numeratif ataupun metode transportasi, tetapi lebih disarankan untuk digunakan metode Hungarian. Metode Hungarian dikembangkan oleh seorang ahli matematika berkebangsaan Hungaria yang bernama D Konig pada tahun 1916.

B.            Permasalahan

Dalam masalah penugasan, kita akan mendelegasikan sejumlah tugas (assignment) kepada sejumlah penerima tugas (assignee) dalam basis satu-satu sehingga mendapatkan keuntungan yang maksimal atau kerugian yang minimal.

C.           Tujuan

Tujuan yang akan dicapai dengan menyelesaikan masalah ini adalah berusaha untuk menjadwalkan setiap assignee pada suatu assigment sedemikian rupa sehingga kerugian yang ditimbulkan minimal atau keuntungan yang didapat maksimal. Yang dimaksud dengan kerugian dalam masalah ini adalah biaya dan waktu, sedangkan yang termasuk keuntungan adalah pendapatan,laba, dan nilai kemenangan.

BAB II

PEMBAHASAN

Masalah penugasan berkaitan dengan keinginan perusahaan dalam mendapatkan pembagian atau alokasi tugas (penugasan) yang optimal, dala arti apabila penugasan tersebut berkaitan dengan keuntungan maka bagaimana alokasi tugas atau penugasan tersebut dapat  memberikan keuntugan yang  maksimal, begitu pula sebaliknya bila menyangkut biaya. Contoh kegiatan yang termasuk masalah penugasan antara lain yaitu: penempatan karyawan pada suatu posisi jabatan di perusahaan, pembagian wilayah tugas salesman, pembagian tugas dalam suatu tim renang estafet.

Pada bagian terdahulu telah disebutkan bahwa pada masalah penugasan disyaratkan suatu penugasan satu-satu, sehingga jumlah assignee dan assignment harus sama. Bila dalam suatu masalah ditemui jumlah assignee dan assignment berbeda, maka perlu ditambahkan suatu assignee/assignment dummy untuk menyamakan jumlahnya. Setelah data terpresentasi dalam bentuk tabel penugasan, maka kita dapat langsung menyelesaikan menggunakan metode Hungarian. Dalam penyelesaiannya, masalah penugasan terbagi menjadi dua, yaitu masalah minimalisasi dan masalah maksimalisasi.

Secara umum langkah-langkah penyelesaian masalah penugasan adalah:

1.    Identifikasi dan penyederhanaan masalah dalam bentuk tabel penugasan.

2.    Untuk kasus minimalisasi, mencari biaya terkecil untuk setiap baris, dan kemudian menggunakan  biaya  terkecil tersebut untuk mengurangi semua biaya yang ada pada baris yang sama. Sedangkan untuk kasus maksimalisasi, mencari nilai tertinggi untuk setiap baris yang kemudian nilai tertinggi tersebut dikurangi dengan semua nilai yang ada dalam baris tersebut.

3.    Memastikan semua baris dan kolom sudah memiliki nilai nol. Apabila masih ada kolom yang belum memiliki nilai nol, maka dicari nilai terkecil pada kolom tersebut untuk selanjutnya digunakan untuk mengurangi semua nilai yang ada pada kolom tersebut.

4.    Setelah semua baris dan kolom memiliki nilai nol, maka langkah selanjutnya adalah memastikan atau  mengecek apakah dalam tabel penugasan tersebut, telah berhasil ditemukan nilai nol, sebanyak sumber daya (bisa karyawan, mesin, alat transportasi, atau sumber daya lainnya) yang juga tercermin dengan jumlah barisnya. Misalnya bila yang akan ditugaskan adalah 4 karyawan, maka harus ditemukan nilai nol sebanyak 4 buah yang terletak di baris dan kolom yang berbeda. Sebaiknya dimulai dari baris yang hanya memiliki 1 nilai nol. Langkah ini menganduk arti bahwa setiap karyawan hanya dapan ditugaskan pada satu pekerjaan saja.

5.    Apabila belum, maka langkah selanjutnya adalah menarik garis yang menghubungkan minimal dua buah nilai nol dalam tabel penugasan tersebut.

6.    Selanjutnya, perhatikan nilai-nilai yang belum terkena garis. Pilih nilai yang paling kecil, kemudian pergunakan untuk mengurangi nilai-nilai lain yang belum terkena garis, dan gunakan untuk menambah nilai-nilai yang terkena garis dua kali.

7.    Dari hasil lagkah ke-6 tersebut, apakah sekarang telah berhasil ditemukan nilai nol sejumlah atau sebanyak sumber daya (bisa karyawan, mesin, alat transportasi, atau sumber daya lainnya) yang juga tercermin dengan jumlah barisnya.

8.     Jika sudah, maka masalah penugasan telah optimal, dan apabila belum maka perlu diulangi langkah penyelesaian ke-5 di atas.

Sebagai catatan, kasus penugasan dianggap normal apabila jumlah sumber daya yang akan ditugaskan dan jumlah pekerjaan atau tujuan adalah sama

Untuk lebih jelasnya, perhatikan contoh kasus berikut ini.

A.      Masalah Minimalisasi (untuk kasus normal)

Sebuah perusahaan memiliki 4 orang karyawan yang harus menyelesaikan 4 pekerjaan yang berbeda. Karena sifat pekerjaan dan juga ketrampilan, karakteristik dari masing masing karyawan, maka biaya yang timbul dari berbagai alternatif penugasan dari ke-4 karyawan tersebut juga berbeda, seperti terlihat dari tabel / matrik penugasan berikut ini:

Catatan : Nilai-nilai dalam tabel tersebut dalam rupiah.

Dari kasus penugasan tersebut di atas, penyelesaiannya adalah :

Langkah 1

Mencari biaya terkecil untuk setiap baris, dan kemudian menggunakan biaya terkecil tersebut untuk mengurangi semua biaya yang ada pada baris yang sama. Dengan langkah ini hasil yang diperoleh adalah :

0    5    3    7

0    2    7    3

5    0    3    0

1    2    2    0

Langkah 2

Memastikan semua baris dan kolom sudah memiliki nilai nol. Dan ternyata masih ada kolom yang belum memiliki nilai nol, yakni kolom 3. Dengan demikian perlu dicari nilai terkecil pada kolom tersebut untuk selanjutnya digunakan untuk mengurangi semua nilai yang ada pada kolom tersebut, sehingga akan menjadi:

0    5    1    7

0    2    5    3

5    0    1    0

1    2    0    0

Sekarang setiap baris dan kolom sudah memiliki nilai nol, maka langkah selanjutnya adalah:

Langkah 3

Langkah selanjutnya adalah memastikan atau mengecek apakah dalam tabel penugasan tersebut, telah berhasil ditemukan nilai nol, sebanyak sumber daya (bisa karyawan, mesin, alat transportasi, atau sumber daya lainnya) yang juga tercermin dengan jumlah barisnya. Misalnya bila yang akan ditugaskan adalah 4 karyawan, maka harus ditemukan nilai nol sebanyak 4 buah yang terletak di baris dan kolom yang berbeda. Sebaiknya dimulai dari baris yang hanya memiliki 1 nilai nol. Langkah ini menganduk arti bahwa setiap karyawan hanya dapan ditugaskan pada satu pekerjaan saja.

Perhatikan!

Dari matrik di atas ternyata nilai nol yang ditemukan dalam baris 1 dan 2, meskipun berbeda baris namun masih berada dalam kolom yang sama, sehingga dapat dipastikan masalah belum optimal dan perlu dilanjutkan ke langkah berikutnya.

Langkah 4

Karena belum optimal maka langkah selanjutnya adalah menarik garis yang menghubungkan minimal dua buah nilai nol dalam tabel penugasan tersebut, seperti terlihat pada tabel atau matrik berikut ini:

0    5    1   7

0    2    5   3

5    0    1   0

1    2    0   0

Dari langkah di atas terlihat bahwa garis yang berhasil dibuat adalah tiga, dengan menyisakan beberapa nilai yang tidak terkena garis.

Langkah 5

Selanjutnya, perhatikan nilai-nilai yang belum terkena garis. Pilih nilai yang paling kecil (dari tabel di atas adalah nilai 1), kemudian nilai 1 tersebut dipergunakan untuk mengurangi nilai-nilai lain yang belum terkena garis, dan gunakan untuk menambah nilai-nilai yang terkena garis dua kali. Dengan langkah ini hasilnya adalah:

0    4    0    6

0    1    4    2

6    0    1    0

2    2    0    0

Perhatikan !

Semua nilai yang tidak terkena garis nilainya akan berkurang sebesar nilai terkecil dari nilai yang belum terkena garis sebelumnya. Sementara itu nilai 5 dan 1 pada kolom 1 akan bertambah 1, karena kedua nilai tersebut terkena garis dua kali.

Langkah 6

Dari hasil lagkah di atas tersebut, apakah sekarang telah berhasil ditemukan nilai nol sejumlah atau sebanyak sumber daya (bisa karyawan, mesin, alat transportasi, atau sumber daya lainnya) yang juga tercermin dengan jumlah barisnya (mulai dari baris yang hanya memiliki 1 nilai nol)? Dari tabel atau matrik di atas ternyata telah berhasil ditemukan 4 nilai nol (sejumlah karyawan yang akan ditugaskan), yang berada di baris dan kolom yang berbeda.

0    4    0    6

0    1    4    2

6    0    1    0

2    2    0    0

Dari hasil di atas dapat dikatakan bahwa kasus penugasan tersebut telah optimal, dengan alokasi penugasan sebagai berikut :

Karyawan A ditugaskan mengerjakan pekerjaan III dengan biaya         Rp 18,-

Karyawan B ditugaskan mengerjakan pekerjaan I dengan biaya            Rp 14,-

Karyawan C ditugaskan mengerjakan pekerjaan II dengan biaya           Rp 20,-

Karyawan D ditugaskan mengerjakan pekerjaan IV dengan biaya         Rp 16,-

                                                                                                                 -------+

Total biaya                                                                                               Rp 68,-

Dengan demikian dapat disimpulkan bahwa dengan metode Hungarian, kasus penugasan dalam perusahaan di atas dapat diselesaikan dengan biaya optimal sebesar Rp 68,-

B.   Masalah Maksimalisasi (untuk kasus normal)

Sebuah perusahaan memiliki 5 orang karyawan yang harus menyelesaikan 5 pekerjaan yang berbeda. Karena sifat pekerjaan dan juga ketrampilan, karakteristik dari masing-masing karyawan, produktifitas atau keuntungan yang timbul dari berbagai alternatif penugasan dari ke-5 karyawan tersebut juga berbeda, seperti terlihat dari tabel / matrik penugasan berikut ini :

Catatan : Nilai-nilai dalam tabel tersebut dalam rupiah.

Dari kasus penugasan tersebut di atas, penyelesaiannya adalah :

Langkah 1

Mencari produktifitas atau keuntungan terbesar untuk setiap baris, dan kemudian nilai tersebut dikurangi dengan semua nilai produktifitas yang ada pada baris yang sama.

Dengan langkah ini hasil yang diperoleh adalah :

            5    3    5    7    0

            1    5    6    0    2

            3    4    5    4    0

            3    1    8    0    5

            7    4    3    6    0

Langkah 2

Memastikan semua baris dan kolom sudah memiliki nilai nol. Dan ternyata masih ada kolom yang belum memiliki nilai nol, yakni kolom 3. Dengan demikian perlu dicari nilai terkecil pada kolom tersebut untuk selanjutnya digunakan untuk mengunrangi semua nilai yang ada pada kolom tersebut, sehingga akan menjadi:

4    2    2    7    0

0    4    3    0    2

2    3    2    4    0

            2    0    5    0    5

            6    3    0    6    0

Sekarang setiap baris dan kolom sudah memiliki nilai nol, maka langkah selanjutnya adalah:

Langkah 3

Langkah selanjutnya adalah memastikan atau mengecek apakah dalam tabel penugasan tersebut, telah berhasil ditemukan nilai nol, sebanyak sumber daya (bisa karyawan, mesin, alat transportasi, atau sumber daya lainnya) yang juga tercermin dengan jumlah barisnya. Misalnya bila yang akan ditugaskan adalah 5 karyawan, maka harus ditemukan nilai nol sebanyak 5 buah yang terletak di baris dan kolom yang berbeda. Sebaiknya dimulai dari baris yang hanya memiliki 1 nilai nol. Langkah ini menganduk arti bahwa setiap karyawan hanya dapan ditugaskan pada satu pekerjaan saja.

Perhatikan !

Dari matrik di atas ternyata nilai nol yang ditemukan dalam baris 1 dan 3, meskipun berbeda baris namun masih berada dalam kolom yang sama, sehingga dapat dipastikan masalah belum optimal dan perlu dilanjutkan ke langkah berikutnya.

Langkah 4

Karena belum optimal maka langkah selanjutnya adalah menarik garis yang menghubungkan minimal dua buah nilai nol dalam tabel penugasan tersebut, seperti terlihat pada tabel atau matrik berikut ini:

4    2    2    7    0

            0    4    3    0    2

            2    3    2    4    0

            2    0    5    0    5

6    3    0    6    0

Dari langkah di atas terlihat bahwa garis yang berhasil dibuat adalah empat, dengan menyisakan beberapa nilai yang tidak terkena garis.

Langkah 5

Selanjutnya, perhatikan nilai-nilai yang belum terkena garis. Pilih nilai yang paling kecil (dari tabel di atas adalah nilai 2), kemudian nilai 2 tersebut dipergunakan untuk mengurangi nilai-nilai lain yang belum terkena garis, dan gunakan untuk menambah nilai-nilai yang terkena garis dua kali. Dengan langkah ini hasilnya adalah :

            2    0    0    5    0

0    4    3    0    4

0    1    0    2    0

            2    0    5    0    7

            6    3    0    6    2

Perhatikan !

Semua nilai yang tidak terkena garis nilainya akan berkurang sebesar (2) atau nilai terkecil dari nilai yang belum terkena garis sebelumnya. Sementara itu nilai 2, 5 dan 0 pada kolom 5 akan bertambah 2, karena kedua nilai tersebut terkena garis dua kali.

Langkah 6

Dari hasil lagkah di atas tersebut, apakah sekarang telah berhasil ditemukan nilai nol sejumlah atau sebanyak sumber daya (bisa karyawan, mesin, alat transportasi, atau sumber daya lainnya) yang juga tercermin dengan jumlah barisnya (mulai dari baris yang hanya memiliki 1 nilai nol, yakni baris ke-5)?. Dari tabel atau matrik di atas ternyata telah berhasil ditemukan 5 nilai nol (sejumlah karyawan yang akan ditugaskan), yang berada di baris dan kolom yang berbeda.

2    0    0    5    0

            0    4    3    0    4

            0    1    0    2    0

            2    0    5    0    7

            6    3    0    6    2

Dari hasil di atas dapat dikatakan bahwa kasus penugasan tersebut telah optimal, dengan alokasi penugasan sebagai berikut:

Karyawan A ditugaskan mengerjakan pekerjaan II dengan biaya          Rp 12,-

Karyawan B ditugaskan mengerjakan pekerjaan I dengan biaya            Rp 14,-

Karyawan C ditugaskan mengerjakan pekerjaan V dengan biaya           Rp 12,-

Karyawan D ditugaskan mengerjakan pekerjaan IV dengan biaya         Rp 16,-

Karyawan C ditugaskan mengerjakan pekerjaan III dengan biaya         Rp 14,-

                                                                                                               ---------+

Total biaya                                                                                               Rp 68,-

Namun demikian, alternatif lain dari penugasan di atas dapat dipilih seperti terlihat pada tabel berikut ini :

            2    0    0    5    0

            0    4    3    0    4

            0    1    0    2    0

            2    0    5    0    7

            6    3    0    6    2

Karyawan A ditugaskan mengerjakan pekerjaan V dengan biaya          Rp 15,-

Karyawan B ditugaskan mengerjakan pekerjaan IV dengan biaya         Rp 15,-

Karyawan C ditugaskan mengerjakan pekerjaan I dengan biaya            Rp   9,-

Karyawan D ditugaskan mengerjakan pekerjaan II dengan biaya          Rp 15,-

Karyawan C ditugaskan mengerjakan pekerjaan III dengan biaya         Rp 14,-

                                                                                                               -------- +

Total biaya                                                                                               Rp 68,-

Dengan demikian dapat disimpulkan bahwa dengan metode Hungarian, kasus penugasan dalam perusahaan di atas dapat diselesaikan dengan biaya optimal sebesar Rp 68,-

Catatan :

Dalam praktek sehari-hari, tidak semua masalah penugasan memiliki matrix biaya atau keuntungan seperti dalam dua contoh kasus di atas. Ada kalanya seorang karyawan misalnya, tidak dapat dialokasikan atau ditugaskan untuk sebuah pekerjaan tertentu (karena alasan, usia, jenis kelamin, ketrampilan yang tidak memadai, kondisi fisik, atau karena sebab lainnya). Dengan demikian karyawan dengan keterbatasan seperti itu tidak dapat dipaksakan mengerjakan sebuah pekerjaan yang memang tidak mungkin baginya.

Untuk mengatasi hal semacam ini, maka dalam proses penyelesaiannya, perlu ditambahkan sebuah bilangan yang sangat besar, dan disebut dengan bilangan M (untuk masalah minimalisasi) dan –M (untuk masalah maximalisasi). Proses penyelesaian selanjutnya dapat dilakukan dengan cara yang sama seperti pada kasus penugasan yang normal, hanya saja pada keptusan optimalnya akan dihindari menugaskan karyawan pada tugas yang memiliki bilangan M atau – M tersebut.

BAB III

PENUTUP

Kesimpulan

Masalah penugasan (assignment problem), seperti juga masalah transportasi merupakan suatu kasus khusus yang ditemui dalam pemrograman linear. Masalah penugasan berkaitan dengan keinginan perusahaan dalam mendapatkan pembagian atau alokasi tugas (penugasan) yang optimal, dala arti apabila penugasan tersebut berkaitan dengan keuntungan maka bagaimana alokasi tugas atau penugasan tersebut dapat  memberikan keuntugan yang  maksimal. Setelah data terpresentasi dalam bentuk tabel penugasan, maka kita dapat langsung menyelesaikan menggunakan metode Hungarian. Dalam penyelesaiannya, masalah penugasan terbagi menjadi dua, yaitu masalah minimalisasi dan masalah maksimalisasi.

Kolom/baris dummy ditambahkan bila jumlah assignee tidak sama dengan assignment, atau terkadang disebut sebagai masalah tak seimbang. Pada kolom/baris dummy ini diberikan nilai keuntungan/kerugian sebesar nol. Sedangkan untuk suatu hubungan assignee dan assignment yang tidak mungkin terjadi, untuk keduanya diberikan nilai keuntungan sebesar –M atau nilai kerugian sebesar M

DAFTAR PUSTAKA

http://arisbudi.staff.gunadarma.ac.id

http://elearning.gunadarma.ac.id/docmodul/pengantar_riset_operasional/bab6-masalah_penugasan.pdf

http://kiayati.staff.gunadarma.ac.id