![Masalah Penugasan - Kelompok 4 - 2KA16 [PDF]](https://pdfs.asia/img/200x200/masalah-penugasan-kelompok-4-2ka16.jpg)
20 0 374 KB
MAKALAH MASALAH PENUGASAN
Disusun oleh : Kelompok 4 ALBERTUS DIMAS BAGUS KESOWO
(10119417)
ARISKY SISTITA BERLIANA
(11119043)
ARYA SIDA NUGRAHA
(11119085)
DICKY FIRMANSYAH EKADIPUTRA
(11119778)
MUHAMMAD RIDWAN
(14119393)
RIO SHOLLU SAPUTRA
(15119600)
YUDDA IMBARA
(16119739)
SISTEM INFORMASI FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS GUNADARMA DEPOK
Kata Pengantar Puji syukur kepada Allah SWT yang telah memberikan banyak rahmat, taufik, serta hidayah-Nya sehingga kami dapat menyelesaikan tugas pembuatan makalah “Masalah Penugasan” tepat pada waktunya. Adapun tujuan dari penulisan makalah ini adalah untuk memenuhi tugas Bapak Doni Fernando pada mata kuliah Matematika Sistem Informasi 2. Selain itu, makalah ini bertujuan untuk menambah wawasan tentang model penugasan bagi para pembaca dan juga bagi penulis. Kami menyadari bahwa masih banyak kekurangan dalam penyusunan makalah ini yang perlu diperbaiki, baik dalam segi tata bahasa, penyusunan kalimat, maupun isi. Oleh karena itu, dengan segala kerendahan hati, kami menerima segala kritik dan saran yang membangun dari pembaca guna memperbaiki kesalahan-kesalahan yang ada. Kami berharap makalah ini dapat memberikan manfaat dan menambah pengetahuan bagi kami pada khususnya dan bagi para pembaca pada umumnya.
Depok, 26 April 2021
Penulis
i
Daftar Pustaka
Kata Pengantar.............................................................................................................................................i Daftar Pustaka.........................................................................................................................................ii BAB I..........................................................................................................................................................1 PENDAHULUAN.......................................................................................................................................1 1.1
Latar Belakang.............................................................................................................................1
1.2
Permasalahan...............................................................................................................................1
1.3
Tujuan..........................................................................................................................................1
BAB II.........................................................................................................................................................2 PEMBAHASAN.........................................................................................................................................2 A.
Penentuan Optimal.......................................................................................................................2
B.
Dummy......................................................................................................................................11
C.
Penentuan Big M.......................................................................................................................17
BAB III......................................................................................................................................................20 PENUTUP.................................................................................................................................................20
ii
BAB I PENDAHULUAN 1.1 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.
1.2 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.
1.3 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.
1
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. Masalah penugasan juga merupakan suatu masalah yang sering muncul dalam banyak kasus pembuatan keputusan, yang mengenai pengaturan objek untuk melaksanakan tugas dengan tujuan meminimalkan biaya, waktu jarak dan sebagainya dan atau memaksimalkan keuntungan, kepuasan dan sebagainya. Seperti kasus menentukan siapa mengerjakan apa, menetapkan fungsi sebuah mesin, menentukan salesman untuk suatu wilayah pemasaran dan sebagainya. Masalah penugasan ada 2, yaitu : 1.
Maksimisasi
Bagaimana kita memaksimumkan keuntungan (kepuasan, laba, dan sebagainya). 2.
Minimasi
Bagaimana kita meminimumkan kerugian (biaya, waktu, jarak dan sebagainya)
A. Penentuan Optimal Dalam dunia usaha (bisnis) dan industri, manajemen sering menghadapai masalah masalah yang berhubungan dengan penugasan optimal dari bermacam-macam sumber yang produktif atau personalia yang mempunyai tingkat efisiensi yang berbeda-beda untuk tugas yang berbeda pula. Salah satu metode yang digunakan untuk masalah penugasan optimal adalah Metode Hungarian. Metode ini dikembnagkan oleh seorang ahli matematika yang berkebangsaan Hungaria yang bernama D Konig pada tahun 1916. Secara umum langkah-langkah penyelesaian masalah penugasan yang normal (optimal) adalah : 1. 2.
Identifikasi dan penyederhanaan masalah dalam bentuk tabel penugasan. Untuk kasus minimalisasi, mencari biaya terkecil untuk setiap baris, dan kemudian menggunakan biaya terkecil tersebut untuk mengurangi semua biaya yang ada pada baris 2
3.
4.
5. 6.
7.
8.
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. 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 mengunrangi semua nilai yang ada pada kolom. 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 pegawai, mesin, alat transportasi, atau sumber daya lainnya) yang juga tercermin dengan jumlah barisnya. Misalnya bila yang akan ditugaskan adalah 4 pegawai, 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 mengandung arti bahwa setiap pegawai hanya dapan ditugaskan pada satu pekerjaan. Apabila belum, maka langkah selanjutnya adalah menarik garis yang menghubungkan minimal dua buah nilai nol dalam tabel penugasan tersebut. 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. Dari hasil lagkah ke-6 tersebut, apakah sekarang telah berhasil ditemukan nilai nol sejumlah atau sebanyak sumber daya (bisa pegawai, mesin, alat transportasi, atau sumber daya lainnya) yang juga tercermin dengan jumlah barisnya. Jika sudah, maka masalah penugasan telah optimal, dan apabila belum maka perlu diulangi langkah penyelesaian ke-5 di atas.
Contoh Penentuan Optimal Maksimasi:
1. Seluruh elemen baris dikurangi dengan nilai maksimum baris tersebut, hasilnya adalah Matriks Opportunity Loss yang sebenarnya bernilai negatif. Pekerjaan Karyawan
1
2
3
4
5
A
1000
1200
1000
800
1500
B
1400
1000
900
1500
1300
C
900
800
700
800
1200
D
1300
1500
800
1600
1100
E
1000
1300
1400
1100
1700
3
Pekerjaan Karyawan
1
2
3
4
5
A
500
300
500
700
0
B
100
500
600
0
200
C
300
400
500
400
0
D
300
100
800
0
500
E
700
400
300
600
0
2. Minimumkan Opportunity Loss dengan cara mengurangi seluruh elemen dalam setiap kolom yang belum ada nolnya dengan elemen terkecil pada kolom tersebut. Pekerjaan Karyawan A
1
2
3
4
5
500
300
500
700
0
B
100
500
600
0
200
C
300
400
500
400
0
D
300
100
800
0
500
E
700
400
300
600
0
Pekerjaan Karyawan A
1
2
3
4
5
400
200
200
700
0
B
0
400
300
0
200
C
200
300
200
400
0 4
D
200
0
500
0
500
E
600
300
0
600
0
3. Menutup semua nilai nol dengan menggunakan garis vertikal/horizontal seminimal mungkin. Dapat dilihat bahwa seluruh elemen nol baru dapat dihimpit oleh 4 garis Pekerjaan
1
2
3
4
5
400
200
200
700
0
B
0
400
300
0
200
C
200
300
200
400
0
D
200
0
500
0
500
E
600
300
0
600
0
Karyawan A
4. Merevisi matriks dengan mengurangi elemen yang tidak tertutup garis dengan nilai terkecil dari elemen yang tidak tertutup garis dan menambah elemen yang tertutup 2 garis dengan elemen terkecil yang tidak tertutup garis. Pekerjaan
1
2
3
4
5
400
200
200
700
0
B
0
400
300
0
200
C
200
300
200
400
0
D
200
0
500
0
500
E
600
300
0
600
0
Karyawan A
5
Pekerjaan
1
2
3
4
5
A
200
0
0
500
0
B
0
400
300
0
400
C
0
100
0
200
0
D
200
0
500
0
700
E
600
300
0
600
0
Karyawan
5. Sama seperti Langkah 3, kita tutup lagi semua nilai 0 menggunakan garis vertical/horizontal Pekerjaan
1
2
3
4
5
A
200
0
0
500
0
B
0
400
300
0
400
C
0
100
0
200
0
D
200
0
500
0
700
E
600
300
0
600
200
Karyawan
PENUGASAN OPTIMAL Penugasan Alternatif 1 A=2 B=1 C=5 D=4 E=3 TOTAL
Keuntungan Rp 1200 Rp 1400 Rp 1200 Rp 1600 Rp 1400 Rp 6800
Penugasan Alternatif A=5 B=4 C=1 D=2 E=3 TOTAL
Keuntungan Rp 1500 Rp 1500 Rp 900 Rp 1500 Rp 1400 Rp 6800 6
Contoh Penentuan Optimal Minimasi:
Pada suatu lokasi konstruksi terdapat 4 mesin. Setiap mesin dialokasikan untuk suatu pekerjaan. Waktu yang diperlukan untuk mengalokasikan tiap mesin ke tiap pekerjaan pada table berikut: Mesin \ Pekerjaan
1 2 3 4 Mesin A 4 3 5 7 Mesin B 8 4 10 6 Mesin C 12 6 5 6 Mesin D 6 2 7 14 Temukan penugasan optimal untuk mesin terhadap pekerjaan, sehingga total waktu yang dibutuhkan untuk menyelesaikan pekerjaan bisa minimal?
Langkah 1 Mencari nilai minimum tiap baris, selisihkan tiap elemen baris dengan nilai minimum. Mesin \ 1 Pekerjaan Mesin A 4 Mesin B 8 Mesin C 12 Mesin D 6 Baris 1 nilai minimum = 3 Baris 2 nilai minimum = 4 Baris 3 nilai minimum = 5 Baris 4 nilai minimum = 2
2
3
4
3 4 6 2
5 10 5 7
7 6 6 14
Setelah diselisihkan dengan nilai minimum, maka didapatkan hasil sebagai berikut : Mesin \ 1 2 3 Pekerjaan Mesin A 1 0 2 Mesin B 4 0 6 Mesin C 7 1 0 Mesin D 4 0 5
4 4 2 1 12
Langkah 2 Memeriksa apakah setiap kolom telah mempunyai nilai nol. Apabila ada yang belum maka tentukan nilai terkecil pada kolom tersebut, kemudian nilai pada kolom tersebut dikurangi dengan nilai terkecil. 7
Mesin \ Pekerjaan Mesin A Mesin B Mesin C Mesin D
1
2
3
4
1 4 7 4
0 0 1 0
2 6 0 5
4 2 1 12
Setelah mendapatkan nilai terkecil pada kolom 1 dan 4 maka langkah selanjutnya adalah mengurangi angka pada kolom dengan nilai terkecil. Maka didapatkan hasil sebagai berikut : Mesin \ Pekerjaan Mesin A Mesin B Mesin C Mesin D
1
2
3
4
0 3 6 3
0 0 1 0
2 6 0 5
3 1 0 11
Langkah 3 Menentukan nilai optimal dengan cara menutup semua nilai dengan nol dengan menggunakan garis vertical/horizontal seminimal mungkin. Mesin \ 1 2 3 4 Pekerjaan Mesin A 0 0 2 3 Mesin B 3 0 6 1 Mesin C 6 1 0 0 Mesin D 3 0 5 11 Jika jumlah garis sudah sama dengan jumlah kolom dan baris, maka solusi optimal sudah tercapai. Tetapi jika belum maka lanjut pada step berikutnya. Rumus : Jumlah kolom = Jumlah Baris = Jumlah Garis
Langkah 4 Mencari nilai minimum pada baris atau kolom yang terbuka. Selisihkan tiap elemen dengan nilai minimum tersebut. Lalu, tambahkan nilai minimum dengan elemen pepotongan 2 garis. Mesin \ Pekerjaan
1
2
3
4
8
Mesin A Mesin B Mesin C Mesin D
0 3 6 3
0 0 1 0
2 6 0 5
3 1 0 11
Nilai minimum terdapat pada kolom 4 yaitu 1 sedangkan dengan elemen perpotongan 2 garis yaitu 6 dan 1. Maka didapatkan hasil sebagai berikut : Mesin \ 1 2 3 Pekerjaan Mesin A 0 0 1 Mesin B 3 0 5 Mesin C 7 2 0 Mesin D 3 0 4 Jika sudah tercapai yaitu Jumlah Garis 4, artinya tabel sudah optimal.
4 2 0 0 10
Langkah 5 Menentukan pengalokasian. Mesin \ Pekerjaan Mesin A Mesin B Mesin C Mesin D
1
2
3
4
0 3 7 3
0 0 2 0
1 5 0 4
2 0 0 10
Untuk kolom Biaya kita masukkan angka dari tabel yang pertama Mesin \ Pekerjaan Mesin A Mesin B Mesin C Mesin D Mesin Mesin A Mesin B Mesin C Mesin D Total Waktu
1 4 8 12 6 Pekerjaan 1 4 3 2
waktu 4 6 5 2 17
2
3
4
3 4 6 2
5 10 5 7
7 6 6 14 9
B.
Dummy
Syarat untuk menyelesaikan masalah penugasan dengan metode hungarian adalah jumlah baris sama dengan jumlah kolom (jumlah baris = jumlah kolom). Pada kasus persoalan dimana jumlah baris dan jumlah kolom tidak seimbang(jumlah baris jumlah kolom) maka harus menyeimbangkan jumlah baris dan jumlah kolom(jumlah baris = jumlah kolom). Tekniknya dengan menambah variabel dummy bernilai nol pada baris atau kolom. Jika (baris < kolom) maka variabel dummy ditambahkan pada baris,sebaliknya jika (baris > kolom) maka variabel dummy ditambahkan pada kolom. Contoh penyelesaian masalahmenggunakan Dummy: Sebuah perusahaan kecil memiliki 5 produk yang berbeda untuk dijual oleh 4 pekerja. Berikut adalah tabel penjualan produk oleh setiap pekerja Produk Pekerja
I.
II.
III.
IV.
V.
A
15
42
38
54
29
B
45
19
27
32
20
C
21
30
41
39
23
D
39
28
16
22
19
Bagaimana cara penugasa untuk tiap-tiap pekerja yang harus diambil perusahaan untuk memperoleh penjualan maksimum?
Langkah – langkah penyelesaian : 10
Langkah 1 Karena penugasan ini tidak seimbang, maka perlu ditambahkan variabel dummy. Tabel penjualan produk setelah ditambah dummy: Produk Pekerja
I.
II.
III.
IV.
V.
A
15
42
38
54
29
B
45
19
27
32
20
C
21
30
41
39
23
D
39
28
16
22
19
Dummy E
0
0
0
0
0
Langkah 2 Ditentukan nilai terbesar dari setiap baris, lalu mengurangkan semua nilai dalam baris tersebut dengan nilai terbesarnya. Hasil pengurangan dimutlakkan sehingga semua hasil pengurangan bernilai positif Produk Pekerja
I.
II.
III.
IV.
V.
A
15
42
38
54
29
B
45
19
27
32
20
C
21
30
41
39
23
D
39
28
16
22
19
Dummy E
0
0
0
0
0
III.
IV.
V.
Tabel berubah menjadi seperti berikut : Produk Pekerja
I.
II.
A
39
12
16
0
25
B
0
26
18
13
25
C
20
11
0
2
18
D
0
11
23
17
20
11
Dummy E
0
0
0
0
0
Langkah 3 Menentukan penugasan optimum, yaitu melakukan test optimalisasi dengan menutup semua nilai nol dengan menggunakan garis vertikal/horizontal seminimal mungkin. Produk Pekerja
I.
II.
III.
IV.
V.
A
39
12
16
0
25
B
0
26
18
13
25
C
20
11
0
2
18
D
0
11
23
17
20
Dummy E
0
0
0
0
0
Tabel diatas belum optimal karena jumlah garis tidak sama dengan jumlah pekerja atau produk. Maka kalau belum optimal. Cari kolom manakah yang tidak mengandung nilai nol tanpa memperhatikan nilai dummy Produk Pekerja
I.
II.
III.
IV.
V.
A
39
12
16
0
25
B
0
26
18
13
25
C
20
11
0
2
18
D
0
11
23
17
20
Pada tabel diatas, kolom yang tidak terkandung nilai nol adalah kolom II. dan kolom V.
Langkah 4 12
Mencari nilai terkecil pada kolom yang tidak mengandung nilai nol Produk Pekerja
I.
II.
III.
IV.
V.
A
39
12
16
0
25
B
0
26
18
13
25
C
20
11
0
2
18
D
0
11
23
17
20
Dummy E
0
0
0
0
0
III.
IV.
V.
Maka tabel akan menjadi seperti berikut : Produk Pekerja
I.
II.
A
39
1
16
0
7
B
0
15
18
13
7
C
20
0
0
2
0
D
0
0
23
17
2
Dummy E
0
0
0
0
0
13
Langkah 5 Mengulangi Step 3 Menentukan penugasan optimum, yaitu melakukan test optimalisasi dengan menutup semua nilai nol dengan menggunakan garis vertikal/horizontal seminimal mungkin.
Produk Pekerja
I.
II.
III.
IV.
V.
A
39
1
16
0
7
B
0
15
18
13
7
C
20
0
0
2
0
D
0
0
23
17
2
Dummy E
0
0
0
0
0
Tabel diatas sudah optimal karena jumlah garis sudah sama dengan jumlah pekerja atau produknya.
Langkah 6 Tentukan penugasan optimum untuk setiap pekerja Produk Pekerja
I.
II.
III.
IV.
V.
A
15
42
38
54
29
B
45
19
27
32
20
C
21
30
41
39
23
D
39
28
16
22
19
Dummy E
0
0
0
0
0
14
Produk Pekerja
I.
II.
III.
IV.
V.
A
39
1
16
0
7
B
0
15
18
13
7
C
20
0
0
2
0
D
0
0
23
17
2
Dummy E
0
0
0
0
0
Untuk kolom Biaya kita masukkan angka dari tabel yang pertama. Pekerja Produk A IV B I C III D II Dummy E V Total Biaya
C.
Biaya 54 45 41 28 0 168
Penentuan Big M
Dalam keseharian, tidak semua kasus memiliki matriks biaya atau keuntungan seperti dalam contoh kasus sebelumnya. Ada kalanya seorang karyawan tidak dapat dialokasikan atau ditugaskan ke sebuah pekeerjaan tertentu karena alasan usia, jenis kelamin, keterampilan yang tidak memadai, atau karena sebab lainnya). Dengan demikian karyawan tidak dapat dipaksakan 15
mengerjakan sebuah pekerjaan yang memang tidak mungkin baginya. Untuk menyelesaikan kasus tersebut kita membutuhkan metode Big M. Contoh penyelesaian masalah menggunakan Big M:
Sebuah perusahaan konveksi memiliki 4 pegawai bernama Wawa, Lili, Putu, dan Bebe. Pekerjaan yang dibutuhkan adalah membuat Celana, Topi, Rok dan Baju. Sedangkan salah satu pegawai tidak memiliki keterampilan dalam membut topi, yaitu Putu. Akhirnya pemiliki konveksi memutuskan tidak menugaskan Putu dalam pembuatan topi. Upah seorang pegawai untuk masing-masing pekerjaan berbeda-beda, seperti berikut:
(Ket : gaji dalam ribuan rupiah) Pertanyaan: Pemilik konveksi ingin meminimalkan biaya yang keluar untuk upah para pegawai agar mendapat keuntungan yang lebih besar. Bagaimana seharusnya pemilik konveksi memberikan pekerjaan pada para pegawai agar total biaya minimum?
Tahap penyelesaian : Tahap 1 Ditentukan nilai terkecil dari setiap baris, lalu mengurangkan semua nilai dalam baris tersebut dengan nilai terkecilnya.
16
Setelah pengurangan, tabel berubah menjadi seperti berikut :
Tahap 2 Diperiksa apakah setiap kolom telah mempunyai nilai nol. Apabila ada yang belum, ditentukan nilai terkecil kolom tersebut kemudian nilai pada kolom tersebut dikurangi dengannilai terkecilnya.
Setelah pengurangan di kolom ke 2, table berubah menjadi seperti berikut :
17
Tahap 3 Menentukan penugasan optimum. Praktisnya adalah melakukan tes optimalisasi dengan menutup semua nilai nol dengan menggunakan garis vertikal/horizontal seminimal mungkin.
Tabel sudah memenuhi syarat optimal, yaitu Jumlah Kolom = Jumlah Baris = Jumlah Garis Sehingga ditemukan penugasan optimum :
18
BAB III PENUTUP A. 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.
19
