Anda bekerja sebagai seorang manager pemasaran. Anda memiliki 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
|
Tabel biaya di atas bisa dipresentasikan dalam bentuk matriks menjadi,
Adapun beberapa kemungkinan yang bisa 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
Jadi biaya paling minimal ada pada kemungkinan ke-3. Terlihat mudah bukan. Untuk kasus ini karena anda hanya memiliki 3 sales untuk 3 kota. Bagaimana nanti jika permasalah yang ada itu sekian banyak kota, misalkan ada n. Artinya anda harus mencoba membuat semua kemungkinan sebanyak n.
Untuk mempermudah penyelesaian permasalah tersebut, salah satu cara yang bisa digunakan adalah Hungarian Method (Metode Hungarian). Teorema Asumsi yang digunakan 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. lalu tambahkan dengan kolom yang tertutupi garis (karena akan ada nilai negatif). Kembali ke Langkah ke-3.
Sekarang akan kita cobakan menyelesaikan 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 jika disetarakan dengan matriks awal adalah:
Intinya ambil angka pada matriks awal yang posisinya sama dengan matriks minimum. Jadi biaya minimum tersebut adalah..
AE 400 ; BF 350 ; CD 200 dengan total 950. Jika ingin lebih dalam, bisa anda lanjutkan membaca: Contoh Soal dan Penyelesaian Metode Hungarian.
Jadilah Komentator Pertama untuk "Permodelan Matematika Masalah Penugasan dan Metode Hungarian"
Post a Comment