Thuật toán theo phương pháp Hungary để giải bài toán gán. Thuật toán Hungary hoặc cách toán học giúp phân bổ bài tập

+ +

h =1 

Giai đoạn đầu .



Giai đoạn thứ hai .



Kết quả giải bài toán gán bằng phương pháp Hungary, ta thấy dãy
=4,
=4,
=3,
=2,
=2 cho giá trị cực đại của hàm mục tiêu =15. Từ đó, để đẩy lùi một cuộc tấn công trên không của đối phương, lựa chọn hiệu quả nhất sẽ là lựa chọn gán AOC cho CC:

Bài tập .

Tìm kế hoạch tham khảo vấn đề vận chuyển phương pháp “Góc Tây Bắc”, “Chi phí thấp nhất”, “Vogel”:

Giải bài toán vận chuyển ở bài 1 bằng phương pháp phân phối.

Giải bài toán vận chuyển ở bài 1 bằng phương pháp thế.

Sử dụng phương pháp Hungary để giải bài toán gán khi tìm cực trị:

Sử dụng phương pháp Hungary để giải bài toán gán khi tìm giá trị nhỏ nhất:

Câu hỏi kiểm soát :

Đưa ra công thức của bài toán quy hoạch tuyến tính vận chuyển.

Bài toán vận tải cân bằng khác với bài toán vận tải không cân bằng như thế nào?

Có bao nhiêu biến cơ bản trong một bài toán cân bằng vận tải?

Xác định các khái niệm: phương án, phương án khả thi, phương án khả thi tham khảo, phương án tối ưu, sử dụng trong giải quyết bài toán giao thông.

Xây dựng thuật toán tìm mặt bằng tham chiếu bằng phương pháp góc Tây Bắc.

Xây dựng thuật toán tìm phương án tham chiếu bằng phương pháp chi phí thấp nhất.

Xây dựng thuật toán tìm phương án tham chiếu bằng phương pháp Vogel.

Xây dựng thuật toán tìm phương án tối ưu bằng phương pháp phân phối.

Xây dựng thuật toán tìm phương án tối ưu bằng phương pháp thế năng.

Đưa ra cách giải bài toán.

Làm thế nào trong vấn đề bài tập khi số lượng khác nhauđồ vật và phương tiện được hình thành Ma trận vuông cuộc hẹn?

Xây dựng thuật toán giải bài toán gán bằng phương pháp Hungary.

Ma trận gán ban đầu được hình thành như thế nào ở giai đoạn sơ bộ khi tối đa hóa hàm mục tiêu?

Ma trận gán ban đầu được hình thành như thế nào ở giai đoạn sơ bộ khi cực tiểu hóa hàm mục tiêu?

Bản chất của giai đoạn đầu tiên giải bài toán bằng phương pháp Hungary là gì?

Bản chất của giai đoạn thứ hai khi giải bài toán bằng phương pháp Hungary là gì?

Bản chất của giai đoạn thứ ba trong việc giải bài toán bằng phương pháp Hungary là gì?

Có thể có bao nhiêu giai đoạn thứ nhất, thứ hai và thứ ba trong một lần lặp lại việc giải bài toán gán bằng phương pháp Hungary? Trình tự các bước trong một lần lặp là gì?

Phải có bao nhiêu số 0 độc lập trong ma trận gán để quyết định rằng việc phân bổ vốn tối ưu cho các đối tượng đã được tìm thấy?

Ý tưởng của phương pháp này được nhà toán học Hungary Egervary trình bày như sau. Một kế hoạch vận chuyển ban đầu đang được xây dựng nhưng không đáp ứng được trường hợp chung mọi điều kiện của vấn đề (từ một số điểm sản xuất không xuất khẩu hết sản phẩm, nhu cầu của một số điểm tiêu thụ chưa được đáp ứng đầy đủ). Tiếp theo, quá trình chuyển đổi được thực hiện sang một kế hoạch mới, gần hơn với kế hoạch tối ưu. Việc áp dụng nhất quán kỹ thuật này qua một số lần lặp hữu hạn sẽ dẫn đến giải pháp của vấn đề.

Thuật toán của phương pháp Hungary bao gồm giai đoạn chuẩn bị và số lần lặp hữu hạn. Ở giai đoạn chuẩn bị, ma trận X0 (xij)m,n được xây dựng, các phần tử của ma trận này không âm và thỏa mãn các bất đẳng thức:

Nếu các điều kiện này bằng nhau thì ma trận Xo là lời giải cho bài toán vận chuyển. Nếu có sự bất bình đẳng giữa các điều kiện thì việc chuyển sang lần lặp đầu tiên sẽ được thực hiện. TRÊN lần lặp thứ k ma trận Xk (xij)m,n được xây dựng. Mức độ gần gũi của ma trận này với lời giải của bài toán được đặc trưng bởi số Dk - tổng sai phân của ma trận Xk:

Kết quả của lần lặp đầu tiên là ma trận Xl được xây dựng, bao gồm các phần tử không âm. Trong trường hợp này, Dl D0. Nếu Dl 0 thì Xl là phương án tối ưu cho bài toán. Nếu Dl 0 thì chuyển sang lần lặp tiếp theo. Chúng được thực hiện cho đến khi Dk tại một số k trở thành bằng 0. Ma trận tương ứng Xk là nghiệm của bài toán vận chuyển.

Phương pháp Hungary hiệu quả nhất khi giải quyết các vấn đề vận tải với khối lượng sản xuất và tiêu thụ là số nguyên. Trong trường hợp này, số lần lặp không vượt quá giá trị D0/2 (D0 là tổng sai lệch của giai đoạn chuẩn bị).

Ưu điểm của phương pháp Hungary là khả năng đánh giá mức độ gần gũi của kết quả của mỗi lần lặp với kế hoạch vận chuyển tối ưu. Điều này cho phép bạn kiểm soát quá trình tính toán và dừng nó khi đạt đến các chỉ số chính xác nhất định. Tài sản này cần thiết cho các vấn đề quy mô lớn.

Volkov I.K., Zagoruiko E.A. Nghiên cứu hoạt động: Proc. cho các trường đại học. dây cương thứ 2 / Biên tập bởi V.S. Zarubina, A.P. Krischenko. – M.: Uzd-vo MSTU im. N.E. Bauman, 2002. – 436 tr.

Zaichenko Yu.P. Nghiên cứu hoạt động: Proc. cẩm nang dành cho sinh viên đại học. – tái bản lần thứ 2, có sửa đổi. và bổ sung – Kiev: trường Vishcha. Nhà xuất bản chính, 1979. 392 tr.

I. A. Akulich. Lập trình toán học trong các ví dụ và bài toán. - M.: “ trường sau đại học", 1986.- 319 tr.

Sakovich V.A. Nghiên cứu hoạt động (Các phương pháp và mô hình xác định): Hướng dẫn tham khảo. - Mn.: Cao hơn. trường học, 1984.-256p.

Taha H. Giới thiệu về nghiên cứu hoạt động: trong hai cuốn sách. Cuốn sách 1,2 mỗi. từ tiếng Anh - M.: Mir, 1985.

Khazanova L.E. Lập trình toán học trong kinh tế: Hướng dẫn. – M.: Nhà xuất bản BEK, 1998. – 141 tr.

• Hướng dẫn

Xin chào các bạn! Trong bài viết này, tôi muốn nói về một thuật toán thú vị từ bộ môn “Nghiên cứu hoạt động”, cụ thể là Phương pháp Hungary và cách sử dụng nó để giải các bài toán về bài tập. Tôi sẽ đề cập một chút về các lý thuyết về trường hợp nào và nhiệm vụ nào nó có thể áp dụng được. thuật toán này, Tôi sẽ phân tích nó từng bước bằng cách sử dụng một ví dụ hư cấu và chia sẻ bản phác thảo khiêm tốn của tôi về mã để triển khai nó bằng ngôn ngữ R. Hãy bắt đầu!

Một vài lời về phương pháp

• Vấn đề phân công công nhân vào các vị trí. Cần phân bố công nhân vào các vị trí sao cho hiệu quả tối đa, hoặc được chi phí tối thiểu làm việc.
• Phân công máy móc cho các bộ phận sản xuất. Việc phân phối máy móc sao cho khi vận hành, sản xuất mang lại lợi nhuận cao nhất có thể hoặc chi phí bảo trì ở mức tối thiểu.
• Lựa chọn ứng viên cho các vị trí tuyển dụng khác nhau dựa trên đánh giá. Chúng ta sẽ xem xét ví dụ này dưới đây.

Do đó, bài toán phải được giải sao cho một người thực hiện (người, máy, dụng cụ,...) chỉ có thể thực hiện một công việc và mỗi công việc chỉ được thực hiện bởi một người thực hiện.

Cần thiết và đủ điều kiện giải quyết một vấn đề là loại đóng của nó. Những thứ kia. khi số lượng người biểu diễn = số lượng tác phẩm (N=M). Nếu điều kiện này không được đáp ứng, thì bạn có thể thêm những người biểu diễn hư cấu hoặc các tác phẩm hư cấu mà các giá trị trong ma trận sẽ bằng 0. Điều này sẽ không ảnh hưởng đến việc giải quyết vấn đề theo bất kỳ cách nào, nó sẽ chỉ cung cấp cho nó kiểu đóng cần thiết.

Thuật toán từng bước làm ví dụ

Triển khai bằng ngôn ngữ lập trình R

Dữ liệu để giải quyết vấn đề được lấy từ tệp example.csv, có dạng như sau:

#Chúng tôi kết nối thư viện để thuận tiện cho việc tính toán thư viện(dplyr) #Đọc tệp csv (cột đầu tiên là tên các hàng; dòng đầu tiên là tên các cột) bảng<- read.csv("example.csv",header=TRUE,row.names=1,sep=";") #Проводим расчеты unique_index <- hungarian_algorithm(table,T) #Выводим cat(paste(row.names(table)," - ",names(table)),sep = "\n") #Считаем оптимальный план cat("Оптимальное значение -",sum(mapply(function(i, j) table, unique_index$row, unique_index$col, SIMPLIFY = TRUE))) #____________________Алгоритм венгерского метода__________________________________ hungarian_algorithm <- function(data,optim=F){ #Если optim = T, то будет искаться максимальное оптимальное значение if(optim==T) { data <- data %>% áp dụng(1,function(x) (x-max(x))*(-1)) %>% t() %>% as.data.frame() tối ưu<- F } #Редукция матрицы по строкам data <- data %>% áp dụng(1,function(x) x-min(x)) %>% t() %>% as.data.frame() #Tìm chỉ số của tất cả các số 0 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 %>% áp dụng(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)>1)) chỉ mục2<- which(apply(data[-index,],2,function(x) length(x)>0)) #Trong số các phần tử còn lại, chúng tôi tìm kiếm min_from_table tối thiểu<- min(data[-index,-index2]) #Вычитаем минимальный из оставшихся элементов data[-index,-index2] <- data[-index,-index2]-min_from_table #Прибавляем к элементам, расположенным на пересечении вычеркнутых строк и столбцов data <- data+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)( #Viết chỉ số hàng vào vector i<- c(i,as.vector(find_zero)) #Записываем индекс столбца в вектор j <- c(j,as.vector(find_zero)) #Записываем индексы в data frame (это и есть индексы уникальных нулей) index <- rbind(index,setNames(as.list(find_zero), 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)(tôi<- c(i,as.vector(find_zero)) j <- c(j,as.vector(find_zero)) index <- rbind(index,setNames(as.list(find_zero), names(index))) from_the_end(find_zero,i,j,index)} else rbind(index,find_zero) } #_________________________________________________________________________________

Bước 1.(Giảm hàng và cột). Mục tiêu của bước này là thu được số phần tử 0 tối đa có thể có trong ma trận chi phí. Để làm điều này, phần tử tối thiểu của hàng tương ứng được trừ khỏi tất cả các phần tử của mỗi hàng, sau đó phần tử tối thiểu của cột tương ứng được trừ khỏi tất cả các phần tử của mỗi cột của ma trận kết quả. Kết quả là, một ma trận chi phí giảm được thu được và tiến hành tìm kiếm các bài tập.

Bước 2.(Định nghĩa nhiệm vụ). Ở bước này, bạn có thể sử dụng thuật toán tìm “kết quả khớp lớn nhất với ma trận của đồ thị hai bên (có các khả năng khác), nếu tất cả =0 của ma trận được thay thế bằng “1” và >0 bằng “0” .

Nếu không thể tìm thấy mục đích đầy đủ thì cần phải sửa đổi thêm ma trận chi phí, tức là. chuyển sang bước 3.

Bước 3. (Sửa đổi ma trận rút gọn). Đối với ma trận chi phí giảm:

a) Tính số số 0 trong mỗi hàng và mỗi cột không được gạch chéo.

b) Gạch bỏ hàng hoặc cột có số lượng số 0 tối đa.

c) Thực hiện các bước a) và b) cho đến khi gạch hết các số 0.

d) Từ tất cả các phần tử không chéo, trừ đi phần tử nhỏ nhất không chéo và cộng nó vào từng phần tử nằm ở giao điểm của hai đường thẳng.

Chuyển sang bước 2.

Lưu ý 3.Nếu bài toán ban đầu là bài toán tối đa hóa thì tất cả các phần tử của ma trận chi phí phải được nhân với (-1) và cộng với một số đủ lớn để ma trận không chứa các phần tử âm. Vấn đề sau đó sẽ được giải quyết như một vấn đề tối thiểu hóa.

Ví dụ 13.5. Chúng ta hãy chứng minh hoạt động của thuật toán Hungary bằng ví dụ về bài toán gán với ma trận chi phí sau:

Lặp lại 1

Bước 1. Giảm số hàng và cột.

Giá trị của các phần tử nhỏ nhất ở hàng 1, 2, 3 và 4 lần lượt là 2, 4, 11 và 4. Trừ giá trị tối thiểu tương ứng từ các phần tử của mỗi hàng, chúng ta thu được ma trận sau:

Giá trị của các phần tử nhỏ nhất của cột 1, 2, 3 và 4 lần lượt là 0, 0, 5 và 0. Trừ giá trị tối thiểu tương ứng từ các phần tử của mỗi cột, chúng ta thu được ma trận sau.

Bước 2. Tìm một giải pháp khả thi mà tất cả các nhiệm vụ đều có chi phí bằng 0. Chúng tôi sử dụng thuật toán để tìm kết quả phù hợp lớn nhất. Hãy chuyển đổi ma trận thành ma trận đồ thị lưỡng cực, sau đó thành một bảng tính:

Tìm sự phù hợp:

Sự kết hợp này không hoàn hảo, tức là. không có mục đích đầy đủ. Đến Bước 3.

Bước 3. Sửa đổi ma trận rút gọn.

a) Số chữ số 0 ở các dòng 1, 2, 3 và 4 lần lượt là 1, 1, 2 và 1. Đối với các cột, các giá trị tương ứng là 2, 1, 1 và 1.

b) Số lượng tối đa các số 0, mỗi số có hai số 0, ở dòng 3 và cột 1. Chọn dòng 3 và gạch bỏ tất cả các phần tử của nó bằng một đường ngang.

c) Số chữ số 0 không gạch chéo ở các dòng 1, 2 và 4 lần lượt là 1, 1 và 1. Đối với các cột, các giá trị tương ứng là 2, 1, 0 và 0. Vì vậy, chúng ta phải chọn cột 1 và gạch bỏ nó bằng một đường thẳng đứng. Sau này, sẽ chỉ còn lại một số 0 không bị đánh dấu - phần tử (2,2). Do đó, bạn có thể gạch bỏ hàng 2 hoặc cột 2. Gạch bỏ hàng 2 bằng một đường ngang, ta được ma trận sau:

d) Giá trị của phần tử không bị gạch chéo tối thiểu là 2. Trừ nó khỏi tất cả các phần tử không bị gạch chéo và cộng nó với tất cả các phần tử nằm ở giao điểm của hai đường, chúng ta thu được ma trận chi phí mới.

Đặc điểm cụ thể của các bài toán giao bài đã dẫn đến sự xuất hiện của một phương pháp hiệu quả của Hungary để giải chúng. Ý tưởng chính của phương pháp Hungary là chuyển từ ma trận chi phí bình phương ban đầu VỚI về ma trận tương đương C e với các phần tử không âm và hệ P các số 0 độc lập, trong đó không có hai số nào thuộc cùng một hàng hoặc cùng một cột. Để cho P tồn tại P các giải pháp khả thi. Nếu trong ma trận đích X sắp xếp Pđơn vị sao cho trong mỗi hàng, mỗi cột chỉ có một đơn vị, sắp xếp theo vị trí P các số 0 độc lập của ma trận chi phí tương đương C e thì ta thu được nghiệm khả thi của bài toán gán.

Hãy xem xét thuật toán của phương pháp Hungary bằng cách sử dụng ví dụ giải bài toán cho một ma trận chi phí nhất định

Cần lưu ý rằng đối với bất kỳ phép gán không hợp lệ nào, chi phí tương ứng được giả định có điều kiện bằng một số lượng đủ lớn. M trong các nhiệm vụ ở mức tối thiểu. Nếu ma trận ban đầu không phải là hình vuông thì cần thêm số lượng hàng hoặc cột bắt buộc và các phần tử của chúng phải được gán các giá trị được xác định bởi các điều kiện của bài toán, có thể sau khi giảm và các lựa chọn thay thế chiếm ưu thế, đắt tiền hoặc giá rẻ nên được loại trừ.

A. Giải quyết vấn đề với chi phí tối thiểu

1. Chúng ta rút gọn ma trận theo hàng và cột, như trong phương thức nhánh và giới hạn

• 2. Bằng cách thử và sai, chúng ta tìm kiếm một giải pháp có thể chấp nhận được mà tất cả các nhiệm vụ đều có chi phí bằng 0. Vì việc sắp xếp các phần tử 0 trong ma trận không cho phép tạo thành một hệ thống gồm 4 số 0 độc lập nên giải pháp này là không thể chấp nhận được.
• 3. Chúng tôi sửa đổi ma trận. Chúng tôi gạch bỏ các hàng và cột có càng nhiều phần tử 0 càng tốt - hàng 2 và 3, cột 1 và chúng tôi nhận được một ma trận rút gọn

Chúng ta trừ phần tử tối thiểu của ma trận rút gọn (2) khỏi tất cả các phần tử của nó và cộng nó với các phần tử nằm ở giao điểm của các hàng và cột bị gạch bỏ: 12 + 2 = 14; Ma trận rút gọn 3 + 2 = 5. Kết quả là ta thu được ma trận tương đương

4. Bằng phương pháp thử và sai, chúng ta xác định được ma trận gán X, cho phép bạn tính toán chi phí đích tối thiểu dựa trên các phần tử có vị trí tương tự của ma trận ban đầu (trong hình chữ nhật)

B. Giải quyết vấn đề để tối đa hóa lợi nhuận

1. Sửa đổi ma trận bằng cách nhân tất cả các phần tử với (-1) rồi cộng với phần tử lớn nhất của ma trận (17) sao cho ma trận không chứa phần tử âm:

2. Rút gọn ma trận theo hàng và cột, ta thu được ma trận tương đương

3. Bằng phương pháp thử và sai, chúng ta xây dựng ma trận gán X và sau đó chúng tôi tính toán lợi nhuận tối đa (trong các giá trị ma trận ban đầu trong hình chữ nhật):

Ví dụ 4.6. Phân phối sản xuất 3 loại hàng T|, T 2, T3 cho 5 doanh nghiệp P|, P 2, P:(, P 4, P-, nhằm thu được lợi nhuận tối đa từ việc bán hàng theo số liệu sau :

Chi phí sản xuất trên một đơn vị hàng hóa (USD)

Nhu cầu hàng năm (chiếc.) và giá sản phẩm (đô la)

Chúng tôi tạo thành một ma trận lợi nhuận hàng năm có tính đến nhu cầu (nghìn đô la)

2. Chúng tôi sửa đổi ma trận bằng cách nhân tất cả các phần tử với (-1) và cộng với số lượng tối đa của ma trận (8000) và để loại bỏ sự mất cân bằng, chúng tôi giới thiệu hai loại sản phẩm hư cấu T 4, T G) với lợi nhuận bằng 0, vì ma trận phải vuông:

3. Rút gọn ma trận theo hàng và cột:

4. Sửa đổi ma trận bằng cách loại trừ hàng 4, 5 và cột 3, 4, ta thu được ma trận rút gọn

Sau đó, chúng tôi xác định phần tử tối thiểu 180 trong đó, trừ nó khỏi tất cả các phần tử của ma trận này và tính tổng nó với các phần tử nằm ở giao điểm của các hàng và cột bị loại trừ của ma trận rút gọn (được đánh dấu bằng hình chữ nhật), kết hợp các kết quả và thu được một ma trận tương đương

trên đó chúng tôi xây dựng ma trận gán

và sử dụng nó, chồng nó lên ma trận dữ liệu ban đầu, chúng tôi xác định giá trị lợi nhuận tối đa

Như vậy, phương pháp Hungary có thể giải quyết được nhiều vấn đề trong hoạt động thương mại. Cần lưu ý rằng công việc phức tạp và tế nhị nhất là đặt ra các nhiệm vụ liên quan đến việc tính toán các yếu tố trong ma trận chi phí của ứng viên theo vị trí. Sau đó, cần phải xác định bằng một phương pháp nào đó tính hiệu quả của việc thể hiện nhân cách ở từng vị trí còn trống, chẳng hạn như kế toán, quản lý, doanh nhân hay chuyên gia tài chính. Trong trường hợp này, bạn có thể sử dụng so sánh danh sách yêu cầu về phẩm chất công việc cần và đủ - tiêu chuẩn (Bảng 4.18), chẳng hạn như một doanh nhân và phẩm chất thực tế của người nộp đơn. Tính phần tử ma trận c,y là sự khác biệt giữa các tiêu chí không thể thiếu của tiêu chuẩn và cá nhân, đồng thời có tính đến những phẩm chất tiêu cực của người nộp đơn.

Bảng 4.18

Ví dụ, với tư cách là ứng cử viên, chúng ta sẽ sử dụng những nhân vật văn học nổi tiếng như Gobsek, Chichikov, Sobakevich, Plyushkin, Ostap Bender, những nhân vật có phẩm chất tích cực và tiêu cực được mô tả trong các tác phẩm nổi tiếng (Bảng 4.19).

Bảng 4.19

Chúng ta bắt đầu giải pháp bằng việc xác định tầm quan trọng - tầm quan trọng của phẩm chất công việc (xem Bảng 4.18) bằng phương pháp so sánh cặp đôi (xem đoạn 1.3), bắt đầu từ giám đốc (Bảng 4.20).

Chúng tôi xác định xem ma trận có được điền chính xác hay không:

Trọng số chất lượng được xác định theo công thức M; = 5,-/và 2, ghi kết quả vào bảng. 4,20.

Sau đó, so sánh những phẩm chất cần thiết của vị trí giám đốc (xem Bảng 4.20) với phẩm chất của ứng viên (Bảng 4.21), chúng tôi xây dựng ma trận về sự hiện diện của những phẩm chất giám đốc giữa các ứng viên (xem Bảng 4.21) và tính toán các giá trị hiệu quả hệ số Su.

Ứng viên phù hợp nhất cho vị trí này là Gobsek, Su = 0,6224.

Dựa vào kết quả so sánh, chúng tôi xác định hệ số hiệu quả su và nhập nó vào bảng. 4.22.

Tương tự, chúng ta thực hiện các phép toán so sánh cho các vị trí khác và các giá trị kết quả Su Hãy trình bày nó dưới dạng ma trận hiệu quả (xem Bảng 4.22).

Giải ma trận thu được bằng phương pháp Hungary đến mức tối đa, ta thu được ma trận phân bố ứng viên tối ưu theo vị trí (Bảng 4.23).

Cần lưu ý rằng vị trí quản lý vẫn còn trống. Bạn có thể tiếp tục giải quyết vấn đề có tính đến ảnh hưởng của những phẩm chất tiêu cực của người nộp đơn, làm giảm giá trị của các hệ số hiệu quả.

Bảng 4.20

Bảng 4.22