Modul 6 MODEL PENUGASAN Model penugasan merupakan model yang biasanya diterapkan pada suatu jaringan guna mendapatkan nilai optimal dari jaringan tersebut. Pemodelan ini merupakan pemodelan khusus dari model program linear. Sebelum melakukan model penugasan, yang perlu diperhatikan adalah gambaran dimana setiap subyek hanya ditugaskan pada satu area tujuan saja, atau setiap area tujuan hanya dikuasai satu subyek saja. Setelah itu, yang perlu dipertimbangkan adalah parameter yang akan digunakan dalam menyelaraskan penentuan solusi dan tujuannya, apakah
11
memaksimumkan atau meminimumkan. Alternatif wacana tersebut dapat digambarkan
Tujuan
Antok
I
Ek M o Te an Pra kn aje se ik me ty In n o fo S rm ai at ns ik a U M
Riska
G
Subyek
20
contoh sebagai berikut.
II
Mariam
III
Roni
IV
METODE UNTUK MENENTUKAN SOLUSI OPTIMAL
Ada beberapa metode yang dapat dilakukan untuk menemukan solusi optimal. Salah satunya adalah metode Hungarian. Metode ini diperkenalkan oleh seorang ilmuwan Hungaria, sehingga metode ini diberi nama Metode Hungarian. Adapun langkah-langkah metode Hungarian adalah sebagai berikut: 1. Menyusun data dalam bentuk bujur sangkar. Maksudnya, jumlah baris harus sama dengan jumlah kolom. Jika yang dicari adalah nilai maksimal, maka matrik data dikalikan dengan (–1). 84
2. Menentukan nilai terkecil dari setiap baris matrik, kemudian unsur-unsur dari setiap baris dikurangi dengan nilai terkecil menurut barisnya. 3. Menentukan nilai terkecil dari setiap kolom matrik, kemudian unsur-unsur dari setiap kolom dikurangi dengan nilai terkecil menurut kolomnya. 4. Membuat garis vertikal atau horizontal. Garis yang dibuat harus melintasi unsur nol dan diusahakan seminimal mungkin menggunakan garis. 5. Menghitung jumlah garis yang melintasi kolom atau baris, jika jumlah garis sama dengan jumlah baris atau kolom maka menuju ke langkah-8. 6. Menentukan nilai terkecil dari unsur-unsur yang tidak dilintasi garis, kemudian unsurunsur tersebut dikurangkan dengan nilai terkecil tersebut. Akan tetapi, unsur-unsur yang dilintasi dua garis ditambah oleh nilai terkecil tersebut.
11
7. Kembali ke langkah-4.
20
8. Solusi optimal ditemukan dengan menentukan pasangan penugasan optimal (MPPO) dari model penugasan ditunjukkan oleh unsur nol yang terletak pada baris atau kolom
Ek M o Te an Pra kn aje se ik me ty In n o fo S rm ai at ns ik a U M
Keterangan:
G
yang ditunjuk.
Menurut langkah 1 di atas, matrik bujur sangkar adalah matrik yang jumlah kolom dan barisnya sama. Cara untuk menjadikan baris dan kolom agar sama adalah dengan menambah nilai 0, seperti yang terlihat pada contoh berikut:
Baris > kolom
Asal
Menjadi
1
26
11
1
1
26
11
1
0
15
8
19
20
15
8
19
20
0
6
81
11
6
6
81
11
6
0
7
1
68
77
7
1
68
77
0
81
79
55
91
81
79
55
91
0
85
Baris < kolom Asal
Menjadi
26
11
1
81
1
26
11
1
81
15
8
19
20
79
15
8
19
20
79
6
81
11
6
55
6
81
11
6
55
7
1
68
77
91
7
1
68
77
91
0
0
0
0
0
20
11
1
G
Khusus untuk langkah 2 dan langkah 3 bisa dilakukan pertukaran urutan, maksudnya
Ek M o Te an Pra kn aje se ik me ty In n o fo S rm ai at ns ik a U M
melakukan proses reduksi kolom kemudian reduksi baris atau sebaliknya. Begitu juga dalam membuat garis yang melintasi baris atau kolom yang memiliki nol, karena prinsipnya adalah meminimalisir penarikan garis terhadap nilai nol.
Dari langkah-langkah di atas dapat digambarkan diagram alir (flow chart) sebagai berikut :
86
START
Menyusun data dalam matrik bujur sangkar
Menentukan nilai terkecil pada baris
11
Melakukan reduksi baris dengan nilai terkecilnya
Ek M o Te an Pra kn aje se ik me ty In n o fo S rm ai at ns ik a U M
G
20
Menentukan nilai terkecil pada kolom
Melakukan reduksi kolom dengan nilai terkecilnya
Menarik garis pada baris atau kolom yang ada
Yes
Banyaknya garis = r
No
Menentukan nilai terkecil ( k ) di luar garis
Unsur di luar garis dikurang k Unsur dilalui dua garis ditambah k
87
MPPO
END
Contoh 6-1 Suatu perusahaan memiliki empat operator dan empat mesin. Manager perusahaan ingin mengetahui kombinasi keadaan kerja operator dan mesin yang dimilikinya. Manager menganggap seluruh operator layak mengoperasikan seluruh mesin. Maka manager harus tahu: a. Berapa waktu terpendek yang bisa dikerjakan oleh keempat operator tersebut? (meminimumkan) b. Berapa waktu terlama yang bisa dikerjakan oleh keempat operator tersebut? (memaksimumkan) Tabel pengoperasian mesin oleh operator
III
IV
A
15
21
5
6
B
11
20
15
7
14
12
16
9
10
7
9
10
C D
20
II
G
I
Ek M o Te an Pra kn aje se ik me ty In n o fo S rm ai at ns ik a U M
Operator
11
Mesin
satuan waktu = menit Penyelesaian
a) waktu terpendek (meminimalkan) Mesin
Operator
I
II
III
IV
A
15
21
5
6
- Menentukan nilai terkecil pada baris
B
11
20
15
7
- Kurangkan baris dengan nilai
C
14
12
16
9
D
10
7
9
10
terkecilnya
88
10
16
0
1
4
13
8
0
5
3
7
0
3
0
2
3
7
16
0
1
- Menentukan nilai terkecil pada kolom - Kurangkan kolom dengan nilai terkecilnya
- Menarik garis pada baris atau kolom dengan jumlah seminimal mungkin
13
8
0
2
3
7
0
0
0
2
3
7
16
0
2
- Tentukan nilai terkecil (k) yang berada di luar garis
20
11
1
Ek M o Te an Pra kn aje se ik me ty In n o fo S rm ai at ns ik a U M
G
- Unsur di luar garis dikurang 1
0
12
7
0
1
2
6
0
0
0
2
4
- Unsur dilalui dua garis ditambah 1 - Menarik garis pada baris atau kolom
Menentukan
pasangan
penugasan
optimal
7
16
0
2
0
12
7
0
B – 1 11 menit
1
2
6
0
C – 4 9 menit
0
0
2
4
A – 3 5 menit
D – 2 7 menit Mencapai
solusi
optimal
waktu terpendek = 32 menit
89
dengan
b) waktu terlama (memaksimalkan) Mesin Operator
I
II
III
IV
A
15
21
5
6
B
11
20
15
7
C
14
12
16
9
D
10
7
9
10
-15
-21
-5
-6
-11
-20
-15
-7
-14
-12
-16
-9
-10
-7
-9
-10
- Matrik dikalikan dengan -1
11
- Menentukan nilai terkecil pada
Ek M o Te an Pra kn aje se ik me ty In n o fo S rm ai at ns ik a U M
G
20
baris
6
0
16
15
9
0
5
13
2
4
0
7
0
3
1
0
6
0
16
15
9
0
5
13
2
4
0
7
0
3
1
0
-
Mengurangkan baris dengan nilai terkecilnya
-
Menentukan nilai terkecil pada kolom
-
Mengurangkan kolom dengan nilai terkecilnya
-
Menarik garis pada kolom atau baris
90
6
0
16
15
9
0
5
13
2
4
0
7
0
3
1
0
1
0
11
10
4
0
0
7
- Unsur dilalui dua garis ditambah 5
2
5
0
7
- Menyesuaikan garis dengan nol
0
4
1
0
1
0
11
10
- Menentukan nilai terkecil di luar garis
G
20
11
- Unsur di luar garis dikurang 5
Ek M o Te an Pra kn aje se ik me ty In n o fo S rm ai at ns ik a U M
- Menentukan pasangan penugasan
4
0
0
7
2
9
0
7
0
8
1
0
optimal
Total waktu terlama tidak ditemukan karena ada satu operator yang tidak fungsional dan ada satu mesin yang tidak digunakan yang disebabkan operator tidak mungkin mengerjakan dua mesin sekaligus.
Contoh 6-2
Sebuah perusahaan memiliki lima orang sales dan 4 wilayah pemasaran. Seorang manager pemasaran dari perusahaan tersebut ingin mengetahui volume hasil penjualan yang dilakukan oleh karyawannya sehingga bisa diketahui karyawan mana saja yang memiliki kerja optimal. (memaksimumkan)
91
Wilayah Pemasaran Sales
I
II
III
IV
A
315
121
405
366
B
411
220
415
207
C
314
212
516
119
D
110
157
229
310
E
220
421
366
241
Satuan pemasaran : volume penjualan (unit)
20
11
Penyelesaian
I
II
III
IV
V
-315
-121
-405
-366
0
-411
-220
-415
-207
0
-314
-212
-516
-119
0
-110
-157
-229
-310
0
-220
-421
-366
-241
0
-315
Ek M o Te an Pra kn aje se ik me ty In n o fo S rm ai at ns ik a U M
Sales
G
Wilayah Pemasaran
-121
-405
-366
0
-411
-220
-415
-207
0
-314
-212
-516
-119
0
-110
-157
-229
-310
0
-220
-421
-366
-241
0
A
- Menjadikan matrik menjadi matrik bujur sangkar
B C D E
- Mengalikan setiap unsur dengan (-1)
- Mencari nilai terkecil dari setiap kolom
92
0
300
111
0
0
96
201
101
159
0
- Mengurangkan unsur-unsur kolom dengan nilai terkecilnya - Menarik garis yang melintas
1
209
0
247
0
205
264
287
56
0
115
0
150
125
0
0
300
111
0
56
40
145
45
103
0
1
209
0
247
56
yang dilalui dua garis dengan
149
208
231
0
0
nilai terkecil
115
0
150
125
56
nilai nol - Menentukan nilai terkecil dari unsur di luar garis
- Mengurangkan semua unsur di luar garis dengan nilai terkecil
40 1 149
111
0
56
145
45
103
0
B–50
209
0
247
56
C – 3 516
208
231
0
0
0
150
125
11
Solusi optimal telah ditemukan
300
A – 1 315
D – 4 310 E – 4 421
115
20
G
- Menyesuaikan garis dengan nol
Ek M o Te an Pra kn aje se ik me ty In n o fo S rm ai at ns ik a U M
0
- Menambahkan semua unsur
56
1562 unit
93
