PENUGASANModel penugasan adalah model khusus dari program linear yang mirip dengan model transportasi. Pada model penugasan ini mempertimbangkan situasi dimana m petugas (atau pekerja) ke n tugas. Petugas i (i = 1, 2, 3,m) ketika ditugaskan ke tugas j (j = 1, 2, 3, n) memerlukan biaya Cij. Tujuannya adalah menugaskan petugas-petugas tersebut pada tugas-tugas (satu pekerja satu mesin) dengan biaya total terendah.

Disini petugas mewakili sumber dan tugas (bidang yang tersedia) mewakili tujuan. Penawaran yang tersedia di sumber adalah 1 dan permintaan yang diperlukan oleh tujuan adalah 1. Biaya pekerjaan i ke mesin j adalah Cij.Model matematis dari persoalan transportasi :

Fungsi tujuan :

Max/min Z = C11X11 + C12X12 + . + C1jX1j +.+ C1mX1n +.+ CijXij +.+ CmnXnm

Fungsi batasan :

X11 + X12 + .+ X1j + + X1n 1

X21 + X22 + .+ X2j + + X2n 1.

Xi1 + Xi2 + .+ Xij + + Xin 1

.

Xm1 + Xm2 + .+ Xmj + + Xmn 1

X11 + X21 + .+ Xi1 + + Xm1 1

X12 + X22 + .+ Xi2 + + Xm2 1

X1j + X2j + .+ Xij + + Xmj 1

X1n + X2n + .+ X1n + + Xmn 1

Tabel penugasan :T1T2...Tj...Tn

P1C11C12...C1j...C1n

P2C21C22...C2j...C2n

.....................

PiCi1Ci2...Cij...Cin

.....................

PmCm1Cm2...Cmj...Cmn

Masalah MinimisasiContoh :Suatu perusahaan mempunyai 4 pekerjaan yang berbeda untuk diselesaikan oleh 4 karyawan Tabel Matrik biaya PekerjaanKaryawanIIIIIIIV

A15201822

B14162117

C25202320

D17181816

Langkah-langkah Metode Hungarian1. Mengubah Matriks biaya menjadi matriks opportunity cost:Caranya: pilih elemen terkecil dari setiap baris, kurangkan pada seluruh elemen baris tersebut Reduced cost matrix PekerjaanKaryawanIIIIIIIV

A0537

B0273

C5030

D1520

2. Reduced-cost matrix terus dikurangi untuk mendapatkan total-opportunity-cost matrix.Pilih elemen terkecil dari setiap kolom pada RCM yang tidak mempunyai nilai nol, kurangkan pada seluruh elemen dalam kolom tersebut.Total opportunity cost matrix PekerjaanKaryawanIIIIIIIV

A0517

B0253

C5010

D1200

3. Melakukan test optimalisasi dengan menarik sejumlah minimum garis horisontal dan/atau vertikal untuk meliput seluruh elemen bernilai nol.

Penugasan optimal adalah feasible jika :jumlah garis = jumlah baris atau kolom Test of optimality PekerjaanKaryawanIIIIIIIV

A0517

B0253

C5010

D1200

4. Untuk merevisi total-opportunity matrix, pilih elemen terkecil yang belum terliput garis untuk mengurangi seluruh elemen yang belum terliput.

Tambahkan jumlah yang sama pada seluruh elemen yang mempunyai dua garis yang saling bersilangan.

PekerjaanKaryawanIIIIIIIV

A0406

B0142

C6010

D2200

5. Ulangi langkah ke-3. Melakukan test optimalisasi dengan menarik sejumlah minimum garis horisontal dan/atau vertikal untuk meliput seluruh elemen bernilai nol . PekerjaanKaryawanIIIIIIIV

A0406

B0142

C6010

D2200

Karena jumlah garis = jumlah baris atau kolom maka matrik penugasan optimal telah tercapai.

Matrix optimal PekerjaanKaryawanIIIIIIIV

A0406

B0142

C6010

D2200

Karyawan B ditugaskan untuk pekerjaan satu karena baris B hanya mempunyai satu nilai nol.

Skedul penugasanBiaya

A-IIIRp 18

B-IRp 14

C-IIRp 20

D - IVRp 16

Total BiayaRp 68

Masalah MaksimisasiContoh :Suatu perusahaan mempunyai 5 pekerjaan yang berbeda untuk diselesaikan oleh 5 karyawan PekerjaanKaryawanIIIIIIIVV

A10121085

B141091513

C987812

D131581611

E101314117

Langkah-langkah Batasan untuk petugas

Batasan untuk tugas