Permodelan Matematika Dilema Penugasan Dan Metode Hungarian

Sebagai pengantar, anda sanggup perhatikan sebuah permasalahan di bawah ini.

Anda bekerja sebagai seorang manager pemasaran. Anda mempunyai 3 orang sales yang berada di kota A, kota B dan C. Anda ingin 3 sales tersebut mendistribusikan produk ke 3 kota lainnya yaitu kota D, E dan F. Adapun tabel biaya perjalanan (dalam ratus ribu rupiah) ke kota-kota tujuan (D,E,F) sebagai berikut.

Dari\Ke	D	E	F
A	250	400	350
B	400	600	350
C	200	400	250

Darimana, kemana barang tersebut harus dikirim supaya diperoleh biaya minimal dalam pengiriman barang?

Tabel biaya di atas sanggup dipresentasikan dalam bentuk matriks menjadi,

Adapun beberapa kemungkinan yang sanggup di trial dan error masing masing sebagai berikut,

Kemungkinan I AD=250 ; BE = 600 ; CF = 250 total biaya 1100
Kemungkinan II AD= 250 ; BF = 400 ; CE= 350 total biaya 1000
Kemungkinan III AE = 400 ; BF =350 ; CD = 200 total biaya 950

Makara biaya paling minimal ada pada kemungkinan ke-3. Terlihat gampang bukan. Untuk perkara ini alasannya ialah anda hanya mempunyai 3 sales untuk 3 kota. Bagaimana nanti jikalau permasalah yang ada itu sekian banyak kota, misalkan ada n. Artinya anda harus mencoba menciptakan semua kemungkinan sebanyak n.

Untuk mempermudah penyelesaian permasalah tersebut, salah satu cara yang sanggup dipakai ialah Hungarian Method (Metode Hungarian). Teorema Asumsi yang dipakai dalam Hungarian Method ini adalah

Jika sebuah bilangan ditambahkan atau dikurangkan pada salah satu baris atau kolom matriks, maka nilai optimum pada matriks yang telah dikurangkan/ditambahkan juga merupakan nilai optimum matriks semula.

Metode Hungarian (Hungarian Method)

Jika terdapat matriks nxn untuk penyelesaian permasalahan biaya maksimum/minimum maka langkah yang harus dilakukan dengan metode Hungarian ini sebagai berikut,

Kurangkan masing masing entri di baris dengan entri terkecil dari baris tersebut
Kurangkan masing masing entri pada kolom dengan entri terkecil di kolom tersebut
Buatlah garis yang melewati baris dan kolom dengan entri nol.Aturannya di sini garis melewati jumlah minimum secara horizontal dan vertikal
Uji Optimum. Syaratnya: Jika jumlah minimum garis yang terbnetuk n, maka permasalahan selesai. Jika masih kurang dari n maka ini harus dilanjutkan pada langkah 5,
Kurangkan entri yang pada baris yang tak tertutupi dengan angka terkecil yang tersisa. kemudian tambahkan dengan kolom yang tertutupi garis (karena akan ada nilai negatif). Kembali ke Langkah ke-3.

Sekarang akan kita cobakan menuntaskan permasalahan di atas dengan Hungarian Method.

Langkah 1.

Masing masing Entri baris dikurangkan dengan entri terkecil.

Pada baris pertama entri terkecil 250, semua entri pada baris pertama dikurangi dengan 250. Baris kedua entri terkecil 350, maka semua entri pada baris ke-dua dikurangkan dengan 350. Sama halnya dengan entri baris 3 dimana entri terkecil 200.

Langkah 2.

Sekarang kolom dikurangkan masing masing dengan entri terkecil pada kolom tersebut. Perhatikan,

Langkah 3

Garis semua baris/kolom yang memuat 0

Bisa anda lihat sudah terdapat 3 garis. Karena permasalahan kita n=3 dan sudah terdapat 3 garis. Artinya permasalahan ini sudah selesai. Solusi permasalahan ini anda perhatikan setiap kolom dengan entri 0.

Kembali ke teorema di atas, nilai minimum bersesuaian dengan matriks semula. Nilai minimum tersebut ada pada entri M12, M23 dan M31 (nilai 0) Maka jikalau disetarakan dengan matriks awal adalah: