MAKALAH

MASALAH PENUGASAN
PROGRAM LINEAR
Disusun untuk memenuhi Tugas Mata Kuliah Program Linear
Dosen Pengampu: Rahmat, [Link]., [Link].

DISUSUN OLEH:
KELOMPOK 3

1. Wa Ode Wanda Hamida (A1I121078)

2. Aliyusrin Alan Nicolas (A1I122003)
3. Dewi Rahmawati (A1I122007)

4. Padlia Ningsi (A1I122104)

5. Resy Dwi Oktaviani (A1I122106)
6. Sakinah (A1I122110)
7. Sinar Alam Embon (A1I122111)
8. Siswono Maude (A1I122112)
9. Suryadi Sandra (A1I122113)

JURUSAN PENDIDIKAN MATEMATIKA

FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN
UNIVERSITAS HALUOLEO
KENDARI

2023
 KATA PENGANTAR

Puji syukur ke hadirat Tuhan Yang Maha Esa atas rahmat dan hidayah-Nya, kami
dapat menyelesaikan tugas makalah ini yang berjudul "Masalah Penugasan” dengan tepat
waktu.

Makalah ini disusun untuk memenuhi tugas Mata Kuliah "Program Linier". Selain itu,
makalah ini bertujuan agar Mahasiswa mampu memahami serta mengaplikasikan materi yang
ada di dalam makalah ini.

Kami mengucapkan terima kasih kepada Pak Rahmat, [Link]., [Link]. selaku dosen
Mata Kuliah Program Linier. Dan ucapan terima kasih juga disampaikan kepada Rekan-rekan
kelompok serta semua pihak yang telah membantu menyelesaikannya makalah ini.

Kami menyadari bahwa makalah ini masih jauh dari kata sempurna. Oleh sebab itu,
kami mengharapkan kritik dan saran yang membangun demi kesempurnaan makalah ini.

Kendari, 1 Desember 2023

Tim Penyusun
 DAFTAR ISI

KATA PENGANTAR

DAFTAR ISI

BAB I PENDAHULUAN

A. Latar Belakang
B. Rumusan Masalah
C. Tujuan

BAB II PEMBAHASAN

A. Penugasan (Assigment)
B. Metode Hungarian
C. Metode Pinalti
D. Soal Minimisasi Biaya dan soal maksimisasi Penjualan

E. Contoh Masalah Penugasan

 BAB I
PENDAHULUAN

A. Latar Belakang
Assignment problem yang biasa dibentuk dengan matriks berbobot merupakan
salah satu masalah dalam dunia teknik informatika, dimana masalah ini merupakan
masalah yang metode penyelesaiannya cukup kompleks. Assignment problem adalah
suatu masalah mengenai pengaturan pada individu (objek) untuk melaksanakan tugas
(kegiatan), sehingga dengan demikian biaya yang dikeluarkan untuk pelaksanaan
penugasan tersebut dapat diminimalkan. Keterbatasan manusia dalam memberikan
solusi tanpa alat bantu merupakan salah satu kendala dalam mengoptimalkan solusi
yang ada. Apalagi jika harus menganalisis dan memilih ratusan atau bahkan ribuan
objek beban agar sesuai dengan kapasitas daya angkut media transportasi. Efisiensi
dalam penggunaan waktu juga menjadi pertimbangan dalam mendapatkan solusi yang
optimal. Oleh karena itu dibutuhkan suatu metode yang dapat membantu perusahaan
transportasi dalam penyelesaian permasalahan penugasan.
Permasalahan penugasan (Assignment) merupakan kasus dari persoalan
program linier dengan tujuan untuk mencari keuntungan maksimum dengan biaya
seminimum mungkin. Permasalahan penugasan (Assignment) kerap kali ditujukan
pada permasalahan ekonomi, militer, sosial, dan lain-lain dengan sumber daya yang
minim. Sumber daya dapat berupa uang, tenaga kerja, bahan mentah, kapasitas mesin,
waktu, ruangan atu teknologi. Tugas analisis adalah mencapai hasil terbaik yang
mungkin dengan keterbatasan sumber daya ini. Hasil yang diinginkan mungkin
ditujukan sebagai maksimisasi dari beberapa ukuran seperti profit, penjualan dan
kesejahteraan, atau minimisasi seperti biaya, waktu, dan jarak.
Model penugasan (Assignment) pada awalnya dikenal sebagai Hungarian
Method. Istilah ini dikenal untuk mengabadikan D. Konig, ahli matematika asal
Hungaria yang pertama kali mengembangkan model ini pada tahun 1916. Di dalam
perkembangannya, model ini lebih banyak diterapkan pada masalahmasalah
pemberian tugas atau pekerjaan kepada karyawan sehinggga model ini dikenal pula
dengan istilah Assignment atau penugasan.
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. Dengan tersedianya n jenis pekerjaan (jobs) di mana masing-
masing fasilitas (mesin, orang, dan peralatan lainnya) hanya dapat melaksanakan satu
jenis pekerjaan yang mana dikerjakan oleh mesin atau orang agar jumlah pengorbanan
(uang, waktu, tenaga) minimum.
Persoalan penugasan luas penggunaanya dalam bidang manajemen khususnya
keputusan untuk menentukan jenis pekerjaan apa yang harus dikerjakan oleh siapa
atau alat apa. Cara yang paling mudah akan tetapi tidak efisien ialah dengan jalan
permutasi yaitu kalau ada n fasilitas dengan n jenis, pekerjaan yang harus dilakukan
akan diperoleh suatu matriks dengan n baris dan n kolom, maka akan terdapat n! cara
pengaturan atau alternatif. Kita pilih permutasi dengan jumlah minimum. Penugasan
satu orang dengan job yang ada (1,2,…,n) menghasilkan biaya (cost) sebesar c(1,1)
dan orang 1 dengan job 2 menghasilkan biaya c(1,1), c(1,2),…, c(1,n), c(2,1),
c(2,2),…, c(2,n),…, c(n,n). Maka misalkan setiap 4 orang dengan 4 job yang ada
menghasilkan 4! Kemungkinan 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.
Salah satu metode dalam menyelesaikan persoalan ini adalah algoritma Brute
Force, dimana dalam algoritma ini seluruh kemungkinan solusi diperhitungkan
sebagai kandidat solusi. Dan algoritma penyelesaiannya menggunakan kompleksitas
faktorial. Tentu saja hal ini sangat menggunakan resource yang besar dan
penyelesaian dengan metode ini menjadi tidak efisien.
Alternatif lain dalam menyelesaikan masalah assignment ini adalah dengan
menggunakan algoritma Hungarian. Algoritma Hungarian adalah salah satu algoritma
yang digunakan untuk menyelesaikan persoalan masalah assignment. Versi awalnya,
yang dikenal dengan metode Hungarian, ditemukan dan dipublikasikan oleh Harold
Kuhn pada tahun 1955. Algoritma ini kemudian diperbaiki oleh James Munkres pada
tahun 1957. Oleh karena itu, algoritma ini kemudian dikenal juga dengan nama
algoritma Kuhn-Munkres. Algoritma yang dikembangkan oleh Kuhn ini didasarkan
pada hasil kerja dua orang matematikawan asal Hungaria lainnya, yaitu Denes Konig
dan Jeno Egervary.
Analisisis sensitivitas dapat dipakai untuk memprediksi keadaan apabila
terjadi perubahan yang cukup besar, misalnya terjadi perubahan pembagian atau
 alokasi tugas karena adanya perubahan nilai optimal yang sudah dicapai. Berubahnya
alokasi tugas ini menyebabkan berubahnya urutan prioritas yang baru dan tindakan
apa yang perlu dilakukan
B. Rumusan Masalah
1. Apa yang dimaksud dengan masalah penugasan ?
2. Bagaimana menyelesaikan masalah penugasan dengan menggunakan metode
Hungarian pada minimalisasi dan maksimisasi?
3. Bagaimana menyelesaikan masalah penugasan dengan menggunakan metode
Pinalti ?

C. Tujuan
1. Untuk mengetahui definisi masalah penugasan
2. Untuk mengetahui masalah penugasan dengan menggunakan metode
Hungarian pada minimalisasi dan maksimisasi
3. Untuk mengetahui masalah penugasan dengan menggunakan metode Pinalti
 BAB II
PEMBAHASAN

A. Penugasan (Assigment)
Model Penugasan (Assigment) pada awalnya dikenal sebagai Hungarian
Method. Istilah ini diberikan untuk mengabadikan D. Konig, ahli matematika asal
Hungaria yang pertama kali mengembangkan model ini (Siswanto, 2007).
Thomas J. Kakiay (2008) menyatakan bahwa masalah penugasan adalah
alokasi dari banyak pekerjaan atau individu pekerja yang dinyatakan dengan 𝑚
untuk mengerjakan pekerjaan atau mesin dengan unit atau biaya yang sudah
ditentukan. Pekerja dinyatakan dengan i, untuk i = 1, 2, … , 𝑚 yang akan ditugaskan
pada mesin atau pekerjaan yang dinyatakan dengan j, untuk j = 1, 2, … , 𝑛
dengan biaya yang dinyatakan dengan 𝐶ij. Tujuannya adalah untuk mengalokasikan
setiap pekerja pada satu pekerjaan dengan memperhatikan total biaya paling rendah.
Masalah penugasan, dalam penyelesaiannya harus memenuhi asumsi berikut ini
(Hillier, 2005) :
1. Jumlah petugas dan jumlah tugas sama.(Jumlah inidinyatakan dengan n).

2. Masing-masing petugas ditugaskan satu tugas saja.

3. Masing-masing tugas dilakukan oleh satu petugas saja.

4. Ada biaya 𝑐ijyang dihubungkan dengan petugas i(i = 1,2, … , 𝑛).

5. Tujuan penyelesaian masalah adalah menentukan bagaimana mengerjakan seluruh

𝑛 penugasan untuk meminimalkan total biaya.

Masalah penugasan ada dua, yaitu masalah penugasan seimbang dan penugasan
tidak seimbang. Masalah penugasan seimbang yaitu jika jumlah sumber sama dengan jumlah
tujuan. Sedangkan masalah penugasan tidak seimbang terjadi jika jumlah sumber tidak sama
dengan jumlah tujuan.

Secara umum dalam penyelesaiannya masalah penugasan dibagi menjadi dua yaitu
masalah minimasi dan masalah maksimasi. Masalah minimasi digunakan jika yang ingin kita
optimalkan adalah biaya dan waktu, sedangkan masalah maksimasi digunakan jika yang ingin
kita optimalkan adalah keuntungan.
Model matematis masalah penugasan secara umum adalah sebagai berikut :
Minimumkan 𝑍 = ∑𝑚 𝑛
𝑖=1 ∑𝑗=1 𝐶𝑖𝑗 𝑋𝑖𝑗

Dengan kendala :
𝑚

∑ 𝑖𝑗 = 1; 𝑖 = 1,2, … , 𝑚
𝑖=1
𝑛

∑ 𝑖𝑗 = 1; 𝑖 = 1,2, … , 𝑛
𝑖=1

X {1, jika sumber i ditetapkan pada tujuan j }

Ij {0, jika sumber i tidak ditetapkan pada tujuan j }

Keterangan :
Z : Fungsi tujuan yang dicari nilai optimalnya
n : Jumlah tugas yang akan diselesaikan
m : Jumlah pekerja yang akan menyelesaikan tugas
Xij : Penugasan dari sumber (pekerja (i)) ke tujuan (tugas (j))
Cij : Parameter alokasi dari sumber i ke tujuan j

Tabel 2. 1 Matriks Penugasan

Tujuan Kapasitas
Sumber sumber
1 2 ⋯ 𝑛

1 𝑐11 𝑐12 ⋯ 𝑐1𝑛 1

2 𝑐21 𝑐22 ⋯ 𝑐2𝑛 1

⁝ ⁝ ⁝ ⁝ ⁝ ⁝

𝑚 𝑐𝑚1 𝑐𝑚2 ⋯ 𝑐𝑚𝑛 1

1 1 ⋯ 1
B. Metode Hungarian

Metode Hungarian ditemukan oleh Harold Kuhn pada tahun 1955 dan
kemudian diperbaiki olehJames Munkres pada tahun 1957. Oleh karena itu metode
Hungarian biasa disebut juga metode Kuhn-Munkres. Untuk dapat menerapkan
Metode Hungarian, jumlah sumber-sumber yang ditugaskan harussama dengan
jumlah tujuan yang akan diselesaikan. Selain itu, masing- masing sumber
harusditugaskan hanya untuk satu tujuan. Jadi, masalah penugasan akan mencakup
sejumlah msumber yang mempunyai n tujuan. Metode Hungarian biasa digunakan
untuk menyelesaikan masalah penugasan yang seimbang. Jika untuk masalah tidak
seimbang, maka harus ditambahkan dummy.

Langkah penyelesaian metode penugasan menggunakan metode Hungarian

adalah sebagai berikut :
1. Identifikasi dan penyederhanaan masalah dalam bentuk matriks penugasan.
2. Menentukan nilai terbesar dari setiap baris, kemudian mengurangkan nilai
terbesar dengan setiap nilai dalam baris tersebut.
3. Memeriksa apakah setiap kolom telah mempunyai nilai nol. Jika sudah
lanjutkan ke langkah 4, jika belum kurangkan setiap kolom yang belum
memiliki elemen nol dengan nilai terkecil.
4. Menarik garis pada baris atau kolom yang mempunyai nilai nol dengan cara
memilih baris atau kolom yang memiliki nol terbanyak terlebih dahulu untuk
mendapatkan garis seminimal mungkin. Jika jumlah garis sudah sama dengan
jumlah baris atau kolom mata tabel telah optimal. Jika belum, maka lanjutkan
ke langkah 5.
5. Mengurangkan semua nilai yang tidak tertutup garis dengan nilai terkecil,
dannilai pada perpotongan garis ditambahkan dengan nilai terkecil.
6. Jika semua baris atau kolom yang mempunyai nilai nol sudah tertutup garis,
maka tabel sudah optimal.

Penyelesaian Menggunakan Metode Hungarian

Langkah-langkah penyelesaian menggunakan metode Hungarian adalah
sebagai berikut :
 Tabel 2.3 Matriks Awal Penugasan

Jabatan
Karyawan
1 2 3 4

A 3 2 4 8

B 10 11 11 6

C 5 11 14 10

D 9 11 12 11

Keterangan :
: Nilai terbesar baris 1 : Nilai terbesar baris ke-3
: Nilai terbesar baris ke-2 : Nilai terbesar baris ke-4

1) Menentukan nilai terbesar untuk setiap baris, mengurangkan nilai

terbesar dengan nilai pada masing-masing baris.
Tabel 2.4 Hasil Pengurangan Baris

Jabatan
Karyawan
1 2 3 4

A 5 6 4 0

B 1 0 0 5

C 9 3 0 4

D 3 1 0 1
Keterangan :
: Nilai terkecil kolom ke-1

2) Pada matriks diatas masih ada kolom yang belum memuat angka nol,
yaitu kolom pertama. Maka tentukan nilai terkecil pada kolom tersebut
dan kurangkan semua nilai pada kolom lima dengan nilai terkecil.
Maka, didapatkan solusi awal pada tabel berikut :
 Tabel 2.5 Solusi Awal Metode Hungarian

Jabatan
Karyawan
1 2 3 4

A 4 6 4 0

B 0 0 0 5

C 8 3 0 4

D 2 1 0 1

Selanjutnya menarik garis melewati nol seminimal mungkin untuk

menguji solusi optimal.

Tabel 2.6 Uji Optimalisasi Pertama

Jabatan

Karyawan 1 2 3 4
4
4 6 0

B 0 0 5

8 3 0 4

2 1 0 1
Keterangan :
: Nilai terkecil yang tidak terlewati garis

3) Tenyata hanya dengan tiga garis semua angka nol dapat tertutupi.
Karena jumlah garis tidak sama dengan jumlah baris atau kolom, maka
kurangkan angka terkecil yang tidak terlintasi garis terhadap semua
angka yang tidak terlintasi garis dan tambahkan pada angka yang
terlintasi perpotongan dua garis. Kemudian tarik garis untuk meliputi
semua angka nol.
 Tabel 2.7 Uji Optimalisasi Kedua

Jabatan

Karyawan 1 2 3 4
5
6

B 0 2

7 2 0 3

0 0

4) Dari matriks 2.6 ternyata garis uji yang dapat dibuat sama dengan
jumlah baris atau kolom yaitu lima, sehingga penugasan optimal bisa
dilakukan.

Tabel 2.8 Solusi Optimal Metode Hungarian

Jabatan
Karyawan
1 2 3 4

A 4 6 5 0

B 0 0 2 5

C 7 2 0 3

D 1 0 0 0

5) Setelah alokasi penugasan terpenuhi, maka diperoleh kinerja optimal

yaitu :
Z = 8 + 10 + 14 + 11 = 45
Dengan alokasi penugasan :
a. Karyawan A ditugaskan pada jabatan 4 dengan kinerja 8.
b. Karyawan B ditugaskan pada jabatan 1 dengan kinerja 10.
c. Karyawan C ditugaskan pada jabatan 3 dengan kinerja 14.
d. Karyawan D ditugaskan pada jabatan 1 dengan kinerja 11.
Jadi, kinerja maksimal adalah 45.
C. Metode Pinalti

Metode pinalti adalah suatu metode yang digunakan untuk menyelesaikan

masalah penugasan yang tidak seimbang (Uswatun, 2012). Metode pinalti terdiri dari
dua bagian yaitu mencari solusi awal dan solusi optimal. Jika jumlah sumber lebih
banyak dari jumlah tujuan maka metode yang kita gunakan adalah metode pinalti
kolom. Jika jumlah sumber lebih sedikit dari jumlah tujuan maka metode yang kita
gunakan adalah metode pinalti baris.

Langkah-langkah penyelesaian penugasan menggunakan metode pinaltiadalah

sebagai berikut :
1. Untuk setiap kolom dicari nilai pinalti dengan mencari selisih antara nilai
terbesar dengan nilai terbesar berikutnya.
2. Lihat kolom pinalti yang paling maksimum, pilih kegiatan terbesar sesuai
dengan baris atau kolom itu, dan lingkari. Kemudian coret baris dan
kolom yang sesuai dengan nilai tersebut. Jika sudah ada tanda pada kolom
pinalti maksimum maka pilih kegiatan terbesar dari kegiatan terkecil yang
sesuai.
3. Ulangi langkah 1 dan langkah 2 sampai hanya ada satu kolom yang tidak
dicoret. Kemudian pilih kegiatan terbesar dikolom terakhir, lingkari dan
coret baris dan kolom yang sesuai.

Algoritma untuk mencari solusi optimal adalah sebagai berikut :

1. Pilih sel non basis yang mempunyai kegiatan terbesar.
2. Langkah menentukan solusi optimal
1) Bentuk loop atau lingkaran yang mempertimbangkan dua sel basis dan
dua sel non basis, tidak lebih dari dua sel dalam loop pada baris dan
kolom.
2) Buatlah total kegiatan pada sel basis (T’) dan total kegiatan pada sel
non basis(T).
3) Jika 𝑇 = 𝑇′ maka ini menunjukkan bahwa ada solusi alternatif untuk
masalah penugasan yang diberikan.
4) Jika 𝑇 > 𝑇′ maka ini menunjukkan bahwa perbaikan dalam solusi awal
mungkin terjadi. Jika ada tanda pada kegiatan terkecil pada sel non
 basis maka pilih kegiatan terbesar yang memungkinkan maksimum.
Ganti sel non basis dan sel basis pada baris. Pilih lagi kegiatan terbesar
pada sel non basis dan lanjutkan langkah 2. Jika 𝑇 < 𝑇′ maka lanjut ke
langkah e.
5) Bentuk semua kemungkinan loop satu per satu yang memenuhi
kondisi bentuk loop sampai ditemukan nilai 𝑍 yang maksimum.

Contoh :

Bagian personalia perusahaan IBM baru saja mengadakan seleksi calon karyawan
yang akan ditugaskan pada empat jenis jabatan, kita sebut saja 1, 2, 3 dan 4. Dari
hasil seleksi terpilih empat orang yang memiliki hasil tes tertinggi. Keempat calon
tersebut yaitu: A, B, C dan D, dan kemudian diujicobakan pada empat jabatan itu
secara bergilir selama dua bulan. Selama uji coba tersebut kinerja mereka diukur dan
hasilnya bisa dilihat pada Tabel 2.2.

Tabel 2.2 Contoh Matriks Penugasan

Jabatan
Karyawan
1 2 3 4

A 3 2 4 8

B 10 11 11 6

C 5 11 14 10

D 9 11 12 11

Penyelesaian :
Berdasarkan tabel yang diberikan, maka diperoleh persamaan sebagai berikut :
Min Z = ∑4𝑖=𝑗 ∑4𝑗=1 𝐶𝑖𝑗 𝑋𝑖𝑗
Z = 3𝑥𝑎1 + 2𝑥𝑎2 + 4𝑥𝑎3 + 8𝑥𝑎4 + 10𝑥𝑏1 + 11𝑥𝑏2 + 11𝑥𝑏3 + 6𝑥𝑏4 + 11𝑥𝑐1 +
6𝑥𝑐2 + 5𝑥𝑐3 + 11𝑥𝑐4 + 14𝑥𝑑1 + 10𝑥𝑑2 + 9𝑥𝑑3 + 11𝑥𝑑4

Dengan kendala :
Karyawan A : xa1  xa 2  xa3  xa 4  1

Karyawan B : xb1  xb2  xb3  xb4  1

Karyawan C : xc1  xc2  xc3  xc4  1

Karyawan D : xd1  xd 2  xd 3  xd 4  1

Jabatan 1 : x1a  x1b  x1c  x1d  1

Jabatan 2 : x2a  x2b  x2c  x2d  1

Jabatan 3 : x3a  x3b  x3c  x3d  1

Jabatan 4 : x4a  x4b  x4c  x4d  1

Penyelesaian Menggunakan Metode Pinalti

Langkah-langkah penyelesaian masalah penugasan menggunakan metode pinalti
adalah sebagai berikut :
1) Menentukan nilai pinalti untuk setiap baris dengan mengurangkan nilai
terbesar dengan nilai terbesar berikutnya. Pilih baris nilai pinalti maksimum,
kemudian lingkari nilai terbesar sesuai baris pinalti tersebut. Garis kolom dan
baris yang sejajar dengan nilai yang dilingkari.

Tabel 2.9 Nilai Pinalti Baris

Jabatan Nilai Pinalti

Karyawan
1 2 3 4 P1 P2 P3

A 3 2 4 8 4 - -

B 10 11 11 6 0 0 1

C 5 11 14 10 3 3 -

D 9 11 12 11 1 1 2

Keterangan :

: Nilai pinalti baris 1 : Nilai pinalti baris ke-3

: Nilai pinalti baris ke-2
Setelah menghitung nilai pinalti, maka didapatkan solusi awal untuk
penugasan menggunakan metode pinalti.
 Tabel 2.10 Solusi Awal Metode Pinalti

Jabatan
Karyawan
1 2 3 4

A 3 2 4 8

B 10 11 11 6

C 5 11 14 10

D 9 11 12 11

2) Memilih sel non-basis dengan nilai terbesar, yaitu 11. Kemudian membentuk
loop yang mempertimbangkan dua sel-basis dan non-basis. Tidak lebih dari
dua sel untuk setiap kolom dan baris.

3) Hitung total nilai basis (T') dan non-basis (T).

T = 11 + 12 + 10 + 3 = 36
T' = 8 + 10 + 14 + 11 = 45
Karena total T < T' maka tabel awal sudah optimal.
 Tabel 2.10 Solusi Optimal Metode Pinalti

Jabatan
Karyawan
1 2 3 4

A 3 2 4 8

B 10 11 11 6

C 5 11 14 10

D 9 11 12 11

Maka, kinerja yang optimal adalah sebagai berikut :

Maks Z = 10 + 11 + 14 + 8 = 45
Dengan alokasi penugasan :
a. Karyawan A ditugaskan pada jabatan 4 dengan kinerja 8.
b. Karyawan B ditugaskan pada jabatan 1 dengan kinerja 10.
c. Karyawan C ditugaskan pada jabatan 3 dengan kinerja 14.
d. Karyawan D ditugaskan pada jabatan 1 dengan kinerja 11. Dengan
kinerja maksimal adalah 45.

Jadi, solusi optimal yang didapatkan dengan metode Hungarian sama dengan
solusi optimal yang didapatkan menggunakan metode pinalti. MetodeHungarian
mendapatkan solusi optimal pada iterasi kedua, sedangkan pinalti optimal pada tabel
awal

D. Soal Minimisasi Biaya dan Soal Maksimisasi Penjualan

1. Tuanku Crop. Mempunyai 4 proyek pekerjaan yang berbeda untuk diselesaikan
oleh 4 team. Biaya penugasan setiap team untuk pekerjaan yang berbeda adalah
berbeda karena sifat pekerjaan berbeda-beda. Setiap karyawan dalam tam
mempunyai tingkat keterampilan, pengalaman kerja dan latar belakang
pendidikan serta latihan yang berbeda pula. Sehingga biaya penyelesaian
pekerjaan yang sama oleh para team yang berlainan juga berbeda.
 Dalam Jutaan Rupiah

Pekerjaan
Team
I II III IV
Ali 15 20 18 22
Burhan 14 16 21 17
Cicho 25 20 23 20
Dion 17 18 18 16

Bagaimana menugaskan ke-4 team untuk mengerjakan ke-4 tugas agar total biaya
minimum ?

Penyelesaian :
Langkah 1
Menyusun tabel biaya dari permasalahan yang disajikan.

Pekerjaan
Team
I II III IV
Ali 15 20 18 22
Burhan 14 16 21 17
Cicho 25 20 23 20
Dion 17 18 18 16

Langkah 2
Mencari biaya terkecil untuk setiap baris, kemudian menggunakannya untuk
mengurangi semua biaya yang ada pada baris yang sama.

Pekerjaan
Team
I II III IV
Ali 15 20 18 22
Burhan 14 16 21 17
Cicho 25 20 23 20
Dion 17 18 18 16
Langkah 3
Memastikan apakah setiap kolom telah mempunyai nilai nol. Apabila ada yang
belum, ditentukan nilai terkecil kolom tersebut kemudian nilai pada kolom
tersebut dikurangi dengan nilai terkecilnya.

Pekerjaan
Team
I II III IV
Ali 0 5 3 7
Burhan 0 2 7 3
Cicho 5 0 3 0
Dion 1 2 2 0

Pekerjaan
Team
I II III IV
Ali 0 5 1 7
Burhan 0 2 5 3
Cicho 5 0 1 0
Dion 1 2 0 0

Langkah 4
Menentukan penugasan optimum. Praktisnya adalah melakukan tes optimalisasi
dengan menutup semua nilai nol dengan menggunakan garis vertikal dan
horizontal seminimal mungkin.

Pekerjaan
Team
I II III IV
Ali 0 5 1 7
Burhan 0 2 5 3
Cicho 5 0 1 0
Dion 1 2 0 0
Sehingga, Garis Baris ≠ Garis Kolom artinya Pola Penugasan Belum Optimal.
Langkah 5
Merevisi tabel jika jumlah garis baris belum sama dengan jumlah kolom.
Ditentukan nilai terkecil yang tidak tertutup garis, lalu :
- Semua nilai yang tidak tertutup garis dikurangkan dengan nilai terkecil
tersebut, dan
- Semua nilai yang tertutup 2 garis ditambahkan dengan nilai terkecil
tersebut.

Pekerjaan
Team
I II III IV
Ali 0 4 0 6
Burhan 0 1 4 2
Cicho 6 0 1 0
Dion 2 2 0 0

Langkah 6
Ulangi langkah ke-4
Menentukan penugasan optimum. Praktisnya adalah melakukan tes
optimalisasi dengan menutup semua nilai nol dengan menggunakan garis
vertikal atau garis horizontal seminimal mungkin.

Pekerjaan
Team
I II III IV
Ali 0 4 0 6
Burhan 0 1 4 2
Cicho 6 0 1 0
Dion 2 2 0 0

Sehingga, Garis Baris = Garis Kolom artinya Pola Penugasan Sudah Optimal.
 Langkah 7
Tarik kesimpulan dan hitung total biaya !

Pekerjaan
Team
I II III IV
Ali 0 4 0 6
Burhan 0 1 4 2
Cicho 6 0 1 0
Dion 2 2 0 0

Dalam Jutaan Rupiah

Pekerjaan
Team
I II III IV
Ali 15 20 18 22
Burhan 14 16 21 17
Cicho 25 20 23 20
Dion 17 18 18 16

• Team Ali ditugaskan mengerjakan pekerjaan III dengan biaya =

Rp18.000.00
• Team Burhan ditugaskan mengerjakan pekerjaan I dengan biaya =
Rp14.000.00
• Team Chico ditugaskan mengerjakan pekerjaan II dengan biaya =
Rp20.000.00
• Team Dion ditugaskan mengerjakan pekerjaan IV dengan biaya =
Rp16.000.00
Sehingga, jika ditotalkan mendapatkan total biaya = Rp68.000.00

2. Tuanku Crop memiliki 5 orang Sales Promotor yang akan ditugaskan di 5

Shopping Mall. Berdasarkan kemampuan masing-masing sales dan kondisi
pasar di 5 Shopping mall, berikut ini hasil penjualan yang diperkirakan akan
diperoleh dengan penugasan masing-masing Sales ke Lokasi Shopping Mall.
 Dalam Puluhan Juta Rupiah

Shopping Mall
Sales
I II III IV V
Promotor
Anggi 10 12 10 8 15
Boni 14 10 9 15 13
Cici 9 8 7 8 12
Ditha 13 15 8 16 11
Vita 10 13 14 11 17

Bagaimana menugaskan ke-5 Sales Promotor ke-5 lokasi pemasaran (shopping

mall) agar total hasil penjualan semaksimal mungkin ?

Langkah 1
Menyusun tabel penugasan dari permasalahan yang disajikan.

Shopping Mall
Sales
I II III IV V
Promotor
Anggi 10 12 10 8 15
Boni 14 10 9 15 13
Cici 9 8 7 8 12
Ditha 13 15 8 16 11
Vita 10 13 14 11 17

Langkah 2
Mencari nilai terbesar untuk setiap baris, kemudian menggunakannya untuk
mengurangi semua angka yang ada pada baris yang sama.

Shopping Mall
Sales
I II III IV V
Promotor
Anggi 10 12 10 8 15
Boni 14 10 9 15 13
 Cici 9 8 7 8 12
Ditha 13 15 8 16 11
Vita 10 13 14 11 17

Langkah 3
Memastikan apakah setiap kolom telah mempunyai nilai nol. Apabila ada yang
belum, ditentukan nilai terkecil kolom tersebut kemudian nilai pada kolom
tersebut dikurangi dengan nilai terkecilnya.

Shopping Mall
Sales
I II III IV V
Promotor
Anggi 5 3 5 7 0
Boni 1 5 6 0 2
Cici 3 4 5 4 0
Ditha 3 1 8 0 5
Vita 7 4 3 6 0

Shopping Mall
Sales
I II III IV V
Promotor
Anggi 4 2 2 7 0
Boni 0 4 3 0 2
Cici 2 3 2 4 0
Ditha 2 0 5 0 5
Vita 6 3 0 6 0

Langkah 4
Menentukan penugasan optimum. Praktisnya adalah melakukan tes
optimalisasi dengan menutup semua nilai nol dengan menggunakan garis
vertikal atau horizontal seminimal mungkin.
 Shopping Mall
Sales
I II III IV V
Promotor
Anggi 4 2 2 7 0
Boni 0 4 3 0 2
Cici 2 3 2 4 0
Ditha 2 0 5 0 5
Vita 6 3 0 6 0

Sehingga, Garis Baris ≠ Garis Kolom artinya Pola Penugasan Belum Optimal

Langkah 5
Merevisi tabel jika jumlah garis baris belum sama dengan jumlah kolom.
Ditentukan nilai terkecil yang tidak tertutup garis, lalu :
- Semua nilai yang tidak tertutup garis dikurangkan dengan nilai terkecil
tersebut, dan
- Semua nilai yang tertutup 2 garis ditambahkan dengan nilai terkecil
tersebut.

Shopping Mall
Sales
I II III IV V
Promotor
Anggi 2 0 0 5 0
Boni 0 4 3 0 4
Cici 0 1 0 2 0
Ditha 2 0 5 0 7
Vita 6 3 0 6 2

Langkah 6
Ulangi langkah ke-4
Menentukan penugasan optimum. Praktisnya adalah melakukan tes
optimalisasi dengan menutup semua nilai nol dengan menggunakan garis
vertikal atau horizontal seminimal mungkin.
 Shopping Mall
Sales
I II III IV V
Promotor
Anggi 2 0 0 5 0
Boni 0 4 3 0 4
Cici 0 1 0 2 0
Ditha 2 0 5 0 7
Vita 6 3 0 6 2

Sehingga, Garis Baris = Garis Kolom artinya Pola Penugasan Sudah Optimal

Langkah 7
Tarik kesimpulan dan hitung total penjualan !

Shopping Mall
Sales
I II III IV V
Promotor
Anggi 2 0 0 5 0
Boni 0 4 3 0 4
Cici 0 1 0 2 0
Ditha 2 0 5 0 7
Vita 6 3 0 6 2

Dalam Puluhan Juta Rupiah

Shopping Mall
Sales
I II III IV V
Promotor
Anggi 10 12 10 8 15
Boni 14 10 9 15 13
Cici 9 8 7 8 12
Ditha 13 15 8 16 11
Vita 10 13 14 11 17
 • Sp Anggi ditugaskan ke shopping mall V dengan perkiraan penjualan
= Rp150.000.00
• Sp Boni ditugaskan ke shopping mall IV dengan perkiraan penjualan
= Rp150.000.00
• Sp Cici ditugaskan ke shopping mall I dengan perkiraan penjualan =
Rp90.000.00
• Sp Ditha ditugaskan ke shopping mall II dengan perkiraan penjualan =
Rp150.000.00
• Sp Vita ditugaskan ke shopping mall I dengan perkiraan penjualan =
Rp140.000.00
Sehingga, jika ditotalkan mendapatkan total biaya = Rp680.000.00

E. Contoh Masalah Penugasan

Waktu Minimisasi
1 2 3
Adam 11 14 6
Brown 8 10 11
Cooper 9 12 7
David 6 8 5

Langkah 1 :
Jumlah kolom harus sama dengan jumlah baris, karena kolomnya kurang satu sehingga
menambahkan satu kolom, d = dummy (pemeran pembantu).
1 2 3 d4
Adam 11 14 6 0
Brown 8 10 11 0
Cooper 9 12 7 0
David 6 8 5 0

Langkah 2 :
Mencari angka terkecil dari setiap baris, dari tabel angka tekecilnya yaitu 0
 1 2 3 d4
Adam 11 14 6 0
Brown 8 10 11 0
Cooper 9 12 7 0
David 6 8 5 0

Langkah 3 :
Carilah kolom yang belum memiliki angka 0, kemudian mencari angka terkecil disetiap
kolom yang tidak memiliki angka 0
1 2 3 d4
Adam 11 14 6 0
Brown 8 10 11 0
Cooper 9 12 7 0
David 6 8 5 0

Langkah 4 :
Kemudian mengurangi angka pada kolom dengan angka yang terkecil
1 2 3 d4
Adam 5 6 1 0
Brown 2 2 6 0
Cooper 3 4 2 0
David 0 0 0 0

Langkah 5 :
Menutupi angka 0 dengan garis menggunakan garis vertikal maupun garis horizontal
1 2 3 d4
Adam 5 6 1 0
Brown 2 2 6 0
Cooper 3 4 2 0
David 0 0 0 0

Sehingga, Jumlah Garis baris belum sama dengan jumlah garis kolom. Artinya pola
penugasan belum optimal
Langkah 6 :
Carilah angka yang terkecil diantara angka-angka yang tidak tertutup oleh garis, kemudian
mengurangi angka yang tidak tertutup garis dengan angka terkecil, lalu angka yang tertutup
oleh dua garis ditambah dengan angka terkecil
1 2 3 d4
Adam 4 5 0 0
Brown 1 1 5 0
Cooper 2 3 1 0
David 0 0 0 1

Langkah 7 :
Menutup semua 0 dengan menggunakan garis vertikal maupun garis horizontal
1 2 3 d4
Adam 4 5 0 0
Brown 1 1 5 0
Cooper 2 3 1 0
David 0 0 0 1

Karena jumlah garis pada kolom dan garis baris belum sama, maka melakukan kembali
langkah 6

Langkah 8 :
1 2 3 d4
Adam 4 5 0 1
Brown 0 0 4 0
Cooper 1 2 0 0
David 0 0 0 2

jumlah garis kolom sudah sama dengan jumlah garis baris, sehingga sudah optimal

Langkah 9 :
Kesimpulan
 1 2 3 d4
Adam 4 5 0 1
Brown 0 0 4 0
Cooper 1 2 0 0
David 0 0 0 2