Halo teman-teman! Pada artikel ini saya ingin berbicara tentang algoritma yang menarik dari disiplin "Riset Operasional", yaitu tentang metode Hungaria dan bagaimana menyelesaikan masalah penugasan dengan bantuannya. Saya akan menyentuh teori tentang kasus apa dan untuk tugas apa algoritma ini berlaku, saya akan menganalisanya langkah demi langkah pada contoh yang saya buat, dan membagikan garis besar sederhana dari kode untuk penerapannya dalam bahasa R. Mari kita mulai!
Beberapa kata tentang metode ini
Agar tidak melukis banyak teori dengan istilah dan definisi matematika, saya mengusulkan untuk mempertimbangkan beberapa opsi untuk membangun masalah penugasan, dan saya pikir Anda akan segera memahami dalam kasus apa kita akan menerapkan metode Hongaria:
- Tugas menunjuk karyawan ke posisi. Penting untuk mendistribusikan pekerja ke posisi sehingga efisiensi maksimum tercapai, atau ada biaya pekerjaan yang minimal.
- Menugaskan mesin ke bagian produksi. Distribusi mesin-mesin sehingga selama operasi mereka produksi menguntungkan seperti mungkin, atau biaya pemeliharaannya minimal.
- Pemilihan kandidat untuk berbagai lowongan diperkirakan. Kami akan menganalisis contoh di bawah ini.
Seperti yang Anda lihat, ada banyak opsi yang dapat diterapkan metode Hongaria, dan tugas serupa muncul di banyak bidang kegiatan.
Akibatnya, tugas harus diselesaikan sehingga satu pemain (orang, mesin, alat, ...) dapat melakukan hanya satu pekerjaan, dan setiap pekerjaan dilakukan hanya oleh satu pemain.
Kondisi yang diperlukan dan cukup untuk menyelesaikan masalah adalah tipe tertutupnya. Yaitu ketika jumlah pemain = jumlah karya (N = M). Jika kondisi ini tidak terpenuhi, maka Anda dapat menambahkan pemain fiksi, atau karya fiksi, yang nilai-nilai dalam matriks akan menjadi nol. Ini tidak akan mempengaruhi solusi dari masalah, itu hanya akan memberikan itu tipe tertutup yang diperlukan.
Algoritme langkah demi langkah sebagai contoh
Pernyataan masalah: Biarkan konferensi ilmiah penting direncanakan. Untuk melakukan itu, Anda perlu mengatur suara, cahaya, gambar, mendaftar tamu dan bersiap untuk jeda antar pertunjukan. Ada 5 penyelenggara untuk tugas ini. Masing-masing dari mereka memiliki perkiraan kinerja tertentu dari pekerjaan tertentu (misalkan perkiraan ini ditetapkan sebagai rata-rata aritmatika dari ulasan karyawan mereka). Penting untuk mendistribusikan penyelenggara sehingga total skor mereka maksimum. Tugas memiliki bentuk berikut:
Jika masalah diselesaikan pada maksimum (seperti dalam kasus kami), maka di setiap baris matriks perlu untuk menemukan elemen maksimum, kurangi dari setiap elemen dari baris yang sesuai dan kalikan seluruh matriks dengan -1. Jika masalah diselesaikan seminimal mungkin, maka langkah ini harus dilewati.
Di setiap baris dan di setiap kolom hanya ada satu nol yang dipilih. (mis., ketika nol dipilih, nol yang tersisa di baris ini atau di kolom ini tidak lagi diperhitungkan). Dalam hal ini, ini tidak dapat dilakukan:
(
Jika masalah diselesaikan seminimal mungkin, maka Anda harus mulai dengan langkah ini ). Kami melanjutkan solusi lebih lanjut. Pengurangan matriks dengan baris (cari masing-masing elemen minimum di setiap baris dan kurangi dari masing-masing elemen):
Karena Karena semua elemen minimal adalah nol, matriks tidak berubah. Kami melakukan pengurangan kolom:
Sekali lagi, kita melihat sehingga di setiap kolom dan di setiap baris hanya ada satu nol yang dipilih. Seperti dapat dilihat di bawah, dalam hal ini tidak mungkin dilakukan. Saya menyajikan dua opsi untuk memilih nol, tetapi tidak ada yang memberikan hasil yang diinginkan:
Kami melanjutkan keputusan lebih lanjut. Coret baris dan kolom yang berisi elemen nol (
PENTING! Jumlah penyeberangan harus minimal ). Di antara elemen yang tersisa, kami mencari minimum, kurangi dari elemen yang tersisa (yang tidak dicoret) dan tambahkan ke elemen yang terletak di persimpangan baris dan kolom yang disilangkan (apa yang ditandai dengan warna hijau dikurangi di sana; apa yang ditandai dengan emas diringkas di sana; lalu, apa yang tidak dicat - jangan sentuh):
Seperti yang Anda lihat sekarang, di setiap kolom dan baris hanya ada satu nol yang dipilih. Kami menyelesaikan solusi masalah!
Ganti di tabel awal lokasi nol yang dipilih. Dengan demikian, kita mendapatkan rencana optimal, atau optimal, di mana penyelenggara didistribusikan di antara pekerjaan dan jumlah perkiraan ternyata maksimal:
Jika Anda memecahkan masalah dan masih tidak mungkin bagi Anda untuk memilih nol sehingga hanya ada satu di setiap kolom dan baris, maka kami ulangi algoritma dari tempat pengurangan dilakukan dengan baris (elemen minimum di setiap baris).
Memprogram implementasi bahasa R
Algoritma Hungaria diimplementasikan menggunakan rekursi. Saya harap kode saya tidak akan menyebabkan kesulitan. Pertama, Anda perlu mengkompilasi tiga fungsi, dan kemudian memulai perhitungan.
Data untuk menyelesaikan masalah diambil dari file example.csv yang memiliki bentuk:
Kode yang ditambahkan ke spoiler untuk artikel akan terlalu besar karenanya# library(dplyr) # csv ( - ; - ) table <- read.csv("example.csv",header=TRUE,row.names=1,sep=";") # unique_index <- hungarian_algorithm(table,T) # cat(paste(row.names(table[as.vector(unique_index$row),])," - ",names(table[as.vector(unique_index$col)])),sep = "\n") # cat(" -",sum(mapply(function(i, j) table[i, j], unique_index$row, unique_index$col, SIMPLIFY = TRUE))) #____________________ __________________________________ hungarian_algorithm <- function(data,optim=F){ # optim = T, if(optim==T) { data <- data %>% apply(1,function(x) (x-max(x))*(-1)) %>% t() %>% as.data.frame() optim <- F } # data <- data %>% apply(1,function(x) x-min(x)) %>% t() %>% as.data.frame() # zero_index <- which(data==0, arr.ind = T) # "" - unique_index <- from_the_beginning(zero_index) # "" , .. if(nrow(unique_index)!=nrow(data)) #.. "" - unique_index <- from_the_end(zero_index) # , if(nrow(unique_index)!=nrow(data)) { # data <- data %>% apply(2,function(x) x-min(x)) %>% as.data.frame() zero_index <- which(data==0, arr.ind = T) unique_index <- from_the_beginning(zero_index) if(nrow(unique_index)!=nrow(data)) unique_index <- from_the_end(zero_index) if(nrow(unique_index)!=nrow(data)) { #"" (! ) index <- which(apply(data,1,function(x) length(x[x==0])>1)) index2 <- which(apply(data[-index,],2,function(x) length(x[x==0])>0)) # min_from_table <- min(data[-index,-index2]) # data[-index,-index2] <- data[-index,-index2]-min_from_table # , data[index,index2] <- data[index,index2]+min_from_table zero_index <- which(data==0, arr.ind = T) unique_index <- from_the_beginning(zero_index) if(nrow(unique_index)!=nrow(data)) unique_index <- from_the_end(zero_index) # "" , .. if(nrow(unique_index)!=nrow(data)) #.. hungarian_algorithm(data,optim) else # "" unique_index } else # "" unique_index } else # "" unique_index } #_________________________________________________________________________________ #__________ "" -___________ from_the_beginning <- function(x,i=0,j=0,index = data.frame(row=numeric(),col=numeric())){ # , i, j find_zero <- x[(!x[,1] %in% i) & (!x[,2] %in% j),] if(length(find_zero)>2){ # i <- c(i,as.vector(find_zero[1,1])) # j <- c(j,as.vector(find_zero[1,2])) # data frame ( ) index <- rbind(index,setNames(as.list(find_zero[1,]), names(index))) # from_the_beginning(find_zero,i,j,index)} else rbind(index,find_zero) } #_________________________________________________________________________________ #__________ "" -___________ from_the_end <- function(x,i=0,j=0,index = data.frame(row=numeric(),col=numeric())){ find_zero <- x[(!x[,1] %in% i) & (!x[,2] %in% j),] if(length(find_zero)>2){ i <- c(i,as.vector(find_zero[nrow(find_zero),1])) j <- c(j,as.vector(find_zero[nrow(find_zero),2])) index <- rbind(index,setNames(as.list(find_zero[nrow(find_zero),]), names(index))) from_the_end(find_zero,i,j,index)} else rbind(index,find_zero) } #_________________________________________________________________________________
Hasil dari program:
Kesimpulannya
Terima kasih banyak telah meluangkan waktu untuk membaca artikel saya. Saya akan memberikan semua tautan yang digunakan di bawah ini. Saya harap Anda mempelajari sesuatu yang baru untuk diri sendiri atau memperbarui pengetahuan lama Anda. Semua kesuksesan, keberuntungan yang baik dan yang baik!
Sumber daya yang digunakan
1.
Wikipedia menyerbu2.
Dan situs bagus lainnya3.
Menekankan pada diri saya sendiri beberapa informasi dari artikel ini.