บันทึกที่ยอมรับได้ รูปแบบที่ยอมรับได้ของปัญหาการโปรแกรมเชิงเส้น ทฤษฎีบทอันดับของเมทริกซ์ TK

• บทช่วยสอน

สวัสดีเพื่อน! ในบทความนี้ ผมอยากจะพูดถึงอัลกอริทึมที่น่าสนใจจากสาขาวิชา “การวิจัยปฏิบัติการ” กล่าวคือ วิธีฮังการีและวิธีใช้เพื่อแก้ไขปัญหาการมอบหมายงาน ฉันจะกล่าวถึงทฤษฎีเล็กน้อยเกี่ยวกับกรณีใดบ้างและสำหรับงานใดบ้างที่ทฤษฎีนี้สามารถใช้ได้ อัลกอริทึมนี้ฉันจะวิเคราะห์มันทีละขั้นตอนโดยใช้ตัวอย่างสมมติ และแบ่งปันโค้ดสั้นๆ ของฉันสำหรับการนำไปใช้ในภาษา R มาเริ่มกันเลย!

คำไม่กี่คำเกี่ยวกับวิธีการ

เพื่อไม่ให้อธิบายทฤษฎีมากมายด้วยคำศัพท์และคำจำกัดความทางคณิตศาสตร์ฉันเสนอให้พิจารณาสองสามตัวเลือกสำหรับการสร้างปัญหาการมอบหมายงานและฉันคิดว่าคุณจะเข้าใจได้ทันทีว่าวิธีการของฮังการีสามารถใช้ได้ในกรณีใด:

• ปัญหาการมอบหมายคนงานเข้ารับตำแหน่ง จึงจำเป็นต้องกระจายคนงานไปประจำตำแหน่งดังกล่าว ประสิทธิภาพสูงสุดหรือเป็น ต้นทุนขั้นต่ำไปทำงาน.
• การกำหนดเครื่องจักรให้กับส่วนการผลิต การกระจายเครื่องจักรเพื่อให้เมื่อใช้งาน การผลิตจะมีผลกำไรมากที่สุดเท่าที่จะเป็นไปได้ หรือค่าใช้จ่ายในการบำรุงรักษามีน้อยที่สุด
• การคัดเลือกผู้สมัครสำหรับตำแหน่งงานว่างต่างๆ ตามการประเมิน เราจะดูตัวอย่างด้านล่างนี้

อย่างที่คุณเห็นมีตัวเลือกมากมายที่ใช้วิธีการของฮังการีและปัญหาที่คล้ายกันเกิดขึ้นในหลาย ๆ ด้านของกิจกรรม

เป็นผลให้ต้องแก้ไขปัญหาเพื่อให้นักแสดงหนึ่งคน (บุคคล เครื่องจักร เครื่องมือ ...) สามารถทำงานได้เพียงงานเดียว และแต่ละงานจะดำเนินการโดยนักแสดงเพียงคนเดียว

เงื่อนไขที่จำเป็นและเพียงพอสำหรับการแก้ปัญหาคือ ประเภทปิด- เหล่านั้น. เมื่อจำนวนนักแสดง = จำนวนผลงาน (N=M) หากไม่ตรงตามเงื่อนไขนี้ คุณสามารถเพิ่มนักแสดงสมมติหรือผลงานสมมติได้ ซึ่งค่าในเมทริกซ์จะเป็นศูนย์ สิ่งนี้จะไม่ส่งผลกระทบต่อการแก้ปัญหา แต่อย่างใด แต่จะให้เฉพาะประเภทปิดที่จำเป็นเท่านั้น

อัลกอริทึมทีละขั้นตอนเป็นตัวอย่าง

การกำหนดปัญหา:ให้มีเรื่องสำคัญ. การประชุมทางวิทยาศาสตร์- ในการดำเนินการ คุณจะต้องจัดเตรียมเสียง แสง รูปภาพ ลงทะเบียนแขก และเตรียมพร้อมสำหรับการพักระหว่างการแสดง มีผู้จัดงาน 5 คนสำหรับงานนี้ แต่ละคนมีการให้คะแนนที่แน่นอนสำหรับการปฏิบัติงานเฉพาะอย่าง (สมมติว่าการให้คะแนนเหล่านี้ถูกกำหนดเป็นค่าเฉลี่ยเลขคณิตของการรีวิวของพนักงาน) มีความจำเป็นต้องกระจายผู้จัดงานเพื่อให้คะแนนรวมสูงสุด งานมีลักษณะดังนี้:

หากปัญหาได้รับการแก้ไขจนถึงระดับสูงสุด (เช่นในกรณีของเรา) ในแต่ละแถวของเมทริกซ์จำเป็นต้องค้นหาองค์ประกอบสูงสุดให้ลบออกจากแต่ละองค์ประกอบของแถวที่เกี่ยวข้องแล้วคูณเมทริกซ์ทั้งหมดด้วย -1 หากปัญหาได้รับการแก้ไขอย่างน้อยที่สุด จะต้องข้ามขั้นตอนนี้ไป

จะต้องมีศูนย์ที่เลือกเพียงศูนย์เดียวในแต่ละแถวและแต่ละคอลัมน์ (เช่น เมื่อเลือกศูนย์ ศูนย์ที่เหลือในแถวนี้หรือในคอลัมน์นี้จะไม่นำมาพิจารณาอีกต่อไป) ในกรณีนี้ เป็นไปไม่ได้ที่จะทำเช่นนี้:

(หากปัญหาได้รับการแก้ไขให้เหลือน้อยที่สุด คุณต้องเริ่มจากขั้นตอนนี้- เราดำเนินการแก้ไขปัญหาต่อไป การลดเมทริกซ์ลงทีละแถว (เรามองหาองค์ประกอบขั้นต่ำในแต่ละแถวและลบออกจากแต่ละองค์ประกอบตามลำดับ):

เพราะ องค์ประกอบขั้นต่ำทั้งหมดเป็นศูนย์ ดังนั้นเมทริกซ์จึงไม่เปลี่ยนแปลง เราดำเนินการลดตามคอลัมน์:

ขอย้ำอีกครั้งว่ามีเพียงศูนย์ที่เลือกไว้เพียงศูนย์เดียวในแต่ละคอลัมน์และแต่ละแถว ดังที่เห็นด้านล่างใน ในกรณีนี้มันเป็นไปไม่ได้ที่จะทำเช่นนี้ ฉันนำเสนอสองตัวเลือกสำหรับวิธีเลือกศูนย์ แต่ทั้งสองตัวเลือกไม่ได้ให้ผลลัพธ์ที่ต้องการ:

เรามาดำเนินการแก้ไขปัญหากันต่อไป ขีดฆ่าแถวและคอลัมน์ที่มีองค์ประกอบเป็นศูนย์ ( สำคัญ! จำนวนขีดฆ่าควรน้อยที่สุด- ในบรรดาองค์ประกอบที่เหลือเรามองหาค่าต่ำสุดลบออกจากองค์ประกอบที่เหลือ (ซึ่งไม่ถูกขีดฆ่า) และเพิ่มลงในองค์ประกอบที่อยู่ที่จุดตัดของแถวและคอลัมน์ที่ถูกขีดฆ่า (สิ่งที่ทำเครื่องหมายด้วยสีเขียวจะถูกลบออก) ที่นั่นสิ่งที่ทำเครื่องหมายด้วยทองคำจะถูกสรุปไว้ที่นั่น เราจะไม่แตะต้องสิ่งที่ไม่ได้ทาสีทับ):

ดังที่คุณเห็นแล้วว่า มีศูนย์ที่เลือกเพียงศูนย์เดียวในแต่ละคอลัมน์และแถว เราทำภารกิจให้สำเร็จ!

เราแทนที่ตำแหน่งของศูนย์ที่เลือกลงในตารางเริ่มต้น ดังนั้นเราจึงได้ค่าที่เหมาะสมที่สุดหรือ แผนการที่เหมาะสมที่สุดโดยผู้จัดงานจะกระจายไปตามผลงานและคะแนนรวมสูงสุดคือ:

หากคุณกำลังแก้ไขปัญหาและยังคงเป็นไปไม่ได้ที่จะเลือกศูนย์เพื่อให้มีเพียงอันเดียวในแต่ละคอลัมน์และแถว เราจะทำซ้ำอัลกอริธึมจากตำแหน่งที่ดำเนินการลดตามเส้น (องค์ประกอบขั้นต่ำในแต่ละบรรทัด ).

การใช้งานในภาษาโปรแกรม R

อัลกอริทึมของฮังการีถูกนำมาใช้โดยใช้การเรียกซ้ำ ฉันหวังว่ารหัสของฉันจะไม่ทำให้เกิดปัญหาใดๆ ขั้นแรก คุณต้องคอมไพล์ฟังก์ชันสามฟังก์ชัน จากนั้นจึงเริ่มคำนวณ

ข้อมูลสำหรับการแก้ปัญหานำมาจากไฟล์ example.csv ซึ่งมีลักษณะดังนี้:

#เราเชื่อมต่อไลบรารี่เพื่อความสะดวกในการคำนวณไลบรารี(dplyr) #อ่านไฟล์ csv (คอลัมน์แรกคือชื่อของแถว; บรรทัดแรกคือชื่อของคอลัมน์) ตาราง<- 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 %>% ใช้(1,ฟังก์ชั่น(x) (x-สูงสุด(x))*(-1)) %>% t() %>% as.data.frame() ปรับให้เหมาะสม<- 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 %>% ใช้ (2, ฟังก์ชั่น (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)) ดัชนี2<- which(apply(data[-index,],2,function(x) length(x)>0)) #ในบรรดาองค์ประกอบที่เหลือ เรามองหา min_from_table ขั้นต่ำ<- 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)( #เขียนดัชนีแถวลงในเวกเตอร์ 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)(ผม<- 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) } #_________________________________________________________________________________

ผลลัพธ์ของการรันโปรแกรม:

ลักษณะเฉพาะของปัญหาการมอบหมายงานทำให้เกิดวิธีการแก้ปัญหาแบบฮังการีที่มีประสิทธิภาพ แนวคิดหลักของวิธีการของฮังการีคือการย้ายจากเมทริกซ์ต้นทุนกำลังสองดั้งเดิม กับไปยังเมทริกซ์ที่เทียบเท่า C e ที่มีองค์ประกอบที่ไม่เป็นลบและระบบ ปศูนย์อิสระ ซึ่งไม่มีสองตัวอยู่ในแถวเดียวกันหรือคอลัมน์เดียวกัน สำหรับการให้ ปมีอยู่จริง ปโซลูชั่นที่ยอมรับได้ หากอยู่ในเมทริกซ์ปลายทาง เอ็กซ์จัด ปหน่วยเพื่อให้ในแต่ละแถวและแต่ละคอลัมน์มีเพียงหน่วยเดียวโดยจัดเรียงตามที่ตั้ง ปศูนย์อิสระของเมทริกซ์ต้นทุนที่เทียบเท่า C e จากนั้นเราจะได้แนวทางแก้ไขที่เป็นไปได้สำหรับปัญหาการมอบหมาย

ให้เราพิจารณาอัลกอริทึมของวิธีฮังการีโดยใช้ตัวอย่างการแก้ปัญหาสำหรับเมทริกซ์ต้นทุนที่กำหนด

โปรดทราบว่าสำหรับการมอบหมายที่ไม่ถูกต้องใด ๆ ต้นทุนที่สอดคล้องกันจะถือว่ามีเงื่อนไขเท่ากับจำนวนที่มากเพียงพอ มในงานให้น้อยที่สุด หากเมทริกซ์ดั้งเดิมไม่ใช่สี่เหลี่ยมจัตุรัสก็ควรเพิ่มจำนวนแถวหรือคอลัมน์ที่ต้องการเพิ่มเติมและควรกำหนดค่าองค์ประกอบโดยพิจารณาจากเงื่อนไขของปัญหาซึ่งอาจเป็นไปได้หลังจากการลดลงและทางเลือกที่โดดเด่นซึ่งมีราคาแพง หรือถูกก็ควรยกเว้น

ก. การแก้ปัญหาด้วยต้นทุนขั้นต่ำ

1. เราลดเมทริกซ์ลงตามแถวและคอลัมน์ เช่นเดียวกับในวิธีสาขาและผูกไว้

• 2. เราค้นหาวิธีแก้ปัญหาที่ยอมรับได้โดยใช้การลองผิดลองถูก ซึ่งงานทั้งหมดไม่มีค่าใช้จ่ายใดๆ เนื่องจากการจัดเรียงองค์ประกอบที่เป็นศูนย์ในเมทริกซ์ไม่อนุญาตให้สร้างระบบที่มีศูนย์อิสระสี่ตัว การแก้ปัญหาจึงไม่เป็นที่ยอมรับ
• 3. เราแก้ไขเมทริกซ์ เราขีดฆ่าแถวและคอลัมน์ที่มีองค์ประกอบเป็นศูนย์มากที่สุดเท่าที่จะเป็นไปได้ - แถวที่ 2 และ 3 คอลัมน์ที่ 1 และเราได้เมทริกซ์ที่ลดลง

เราลบองค์ประกอบขั้นต่ำของเมทริกซ์ลดขนาด (2) ออกจากองค์ประกอบทั้งหมดและเพิ่มด้วยองค์ประกอบที่อยู่ที่จุดตัดของแถวและคอลัมน์ที่ขีดฆ่า: 12 + 2 = 14; 3 + 2 = 5 เมทริกซ์รีดิวซ์ เป็นผลให้เราได้เมทริกซ์ที่เท่ากัน

4. ใช้การลองผิดลองถูกเพื่อกำหนดเมทริกซ์การกำหนด เอ็กซ์,ซึ่งช่วยให้คุณสามารถคำนวณต้นทุนขั้นต่ำของปลายทางโดยพิจารณาจากองค์ประกอบที่อยู่ในตำแหน่งเดียวกันของเมทริกซ์ดั้งเดิม (เป็นรูปสี่เหลี่ยมผืนผ้า)

ข. การแก้ปัญหาเพื่อเพิ่มผลกำไรสูงสุด

1. แก้ไขเมทริกซ์โดยการคูณองค์ประกอบทั้งหมดด้วย (-1) แล้วบวกเข้ากับองค์ประกอบสูงสุดของเมทริกซ์ (17) เพื่อให้เมทริกซ์ไม่มีองค์ประกอบที่เป็นลบ:

2. การลดเมทริกซ์ลงตามแถวและคอลัมน์ เราจะได้เมทริกซ์ที่เทียบเท่ากัน

3. เราสร้างเมทริกซ์การมอบหมายงานโดยใช้การลองผิดลองถูก เอ็กซ์จากนั้นเราคำนวณกำไรสูงสุด (ในค่าเมทริกซ์ดั้งเดิมเป็นรูปสี่เหลี่ยมผืนผ้า):

ตัวอย่างที่ 4.6 กระจายการผลิตสินค้า 3 ประเภท T|, T 2, T3 ใน 5 องค์กร P|, P 2, P:(, P 4, P- เพื่อให้ได้กำไรสูงสุดจากการขายสินค้าตามข้อมูลต่อไปนี้ : :

ต้นทุนการผลิตต่อหน่วยสินค้า (ดอลลาร์)

ความต้องการรายปี (ชิ้น) และราคาสินค้า (ดอลลาร์)

เราสร้างเมทริกซ์ของกำไรประจำปีโดยคำนึงถึงความต้องการ (พันดอลลาร์)

2. เราแก้ไขเมทริกซ์โดยการคูณองค์ประกอบทั้งหมดด้วย (-1) และเพิ่มด้วยจำนวนสูงสุดของเมทริกซ์ (8000) และเพื่อกำจัดความไม่สมดุล เราขอแนะนำผลิตภัณฑ์สมมติ T 4, T G) สองประเภทที่มีกำไรเป็นศูนย์ เนื่องจาก เมทริกซ์จะต้องเป็นรูปสี่เหลี่ยมจัตุรัส:

3. ลดเมทริกซ์ตามแถวและคอลัมน์:

4. เราแก้ไขเมทริกซ์โดยไม่รวมแถว 4, 5 และคอลัมน์ 3, 4 เราจะได้เมทริกซ์แบบรีดิวซ์

จากนั้นเรากำหนดองค์ประกอบขั้นต่ำ 180 ในนั้นลบออกจากองค์ประกอบทั้งหมดของเมทริกซ์นี้และรวมเข้ากับองค์ประกอบที่อยู่ที่จุดตัดของแถวและคอลัมน์ที่แยกออกของเมทริกซ์ที่ลดลง (เน้นด้วยสี่เหลี่ยม) รวมผลลัพธ์และรับ เมทริกซ์ที่เท่ากัน

ที่เราสร้างเมทริกซ์การมอบหมายงาน

และใช้มันโดยวางทับบนเมทริกซ์ข้อมูลเริ่มต้น เราจะกำหนดมูลค่ากำไรสูงสุด

ดังนั้นวิธีการของฮังการีจึงสามารถแก้ปัญหาต่างๆ ของกิจกรรมเชิงพาณิชย์ได้ ควรสังเกตว่างานที่ซับซ้อนและละเอียดอ่อนที่สุดคือการกำหนดงานที่เกี่ยวข้องกับการคำนวณองค์ประกอบของเมทริกซ์ต้นทุนของผู้สมัครตามตำแหน่ง จากนั้นจึงจำเป็นต้องกำหนดประสิทธิผลของการแสดงบุคลิกภาพในแต่ละตำแหน่งที่ว่างด้วยวิธีการบางอย่าง เช่น นักบัญชี ผู้จัดการ นักธุรกิจ หรือนักการเงิน ในกรณีนี้ คุณสามารถใช้การเปรียบเทียบรายการคุณสมบัติงานที่จำเป็นและเพียงพอ - มาตรฐาน (ตาราง 4.18) เช่น นักธุรกิจ และคุณสมบัติที่แท้จริงของผู้สมัคร คำนวณองค์ประกอบเมทริกซ์ c,y เป็นความแตกต่างระหว่างเกณฑ์รวมของมาตรฐานและบุคคล รวมถึงคุณสมบัติเชิงลบของผู้สมัครด้วย

ตารางที่ 4.18

ชื่องาน	คุณภาพ
ผู้อำนวยการ	ความรับผิดชอบ ผู้จัดงาน การศึกษา ประสบการณ์การทำงาน เจตจำนง สุขภาพ สัญชาตญาณ ความกระตือรือร้น การเข้าสังคม การวิจารณ์ตนเอง ความสมดุล ความเป็นกลาง ความสามารถในการเข้าใจผู้คน การขาดความขัดแย้ง ความรู้เรื่องมารยาท
ผู้จัดการ	การศึกษา ประสบการณ์ ทักษะการสื่อสาร ความสมดุล การทำงานร่วมกับผู้คน สัญชาตญาณ ความมุ่งมั่น ความมีไหวพริบ ความฉลาด กิจกรรม การให้คำปรึกษา^ ปฏิกิริยาโต้ตอบ
นักเศรษฐศาสตร์	การศึกษา การวิเคราะห์ ประสบการณ์ ทักษะในการสื่อสาร ความสุขุม การทำงานร่วมกับผู้คน สัญชาตญาณ การตรงต่อเวลา ไม่มีความขัดแย้ง ความสามารถในการมองการณ์ไกล ความมั่นใจ ความสามารถในการจัดทำแผนธุรกิจ การปฏิบัติจริง
นักบัญชี	การศึกษา ประสบการณ์ ความเอาใจใส่ ความอุตสาหะ ความรักในการนับ ความชัดเจน ความตรงต่อเวลา ความขยัน ความรับผิดชอบ ความเด็ดเดี่ยว ความสามารถในการควบคุม ความซื่อสัตย์ ตรรกะ การปฏิบัติจริง การควบคุมตนเอง การวิเคราะห์ พิธีการ ระบบราชการ
คอมเมอร์ ซานต้า	การเข้าสังคม การไม่ขัดแย้ง ความกระตือรือร้น การปฏิบัติจริง ความสุภาพ ความสามารถในการโน้มน้าวใจ กิจกรรม มุมมองในกลุ่มผลิตภัณฑ์ ความมุ่งมั่น ความขยันหมั่นเพียร ความรู้ความสามารถแข่งขัน ไหวพริบ มีอารมณ์ขัน

ตัวอย่างเช่นในฐานะผู้สมัครเราจะใช้ตัวละครในวรรณกรรมที่มีชื่อเสียงเช่น Gobsek, Chichikov, Sobakevich, Plyushkin, Ostap Bender ซึ่งอธิบายคุณสมบัติเชิงบวกและเชิงลบไว้ในผลงานที่มีชื่อเสียง (ตาราง 4.19)

ตารางที่ 4.19

	ความฉลาด, ไหวพริบ, ความสมดุล, ความแน่วแน่, การปฏิบัติจริง, ความระมัดระวัง, ความยับยั้งชั่งใจ, ความเข้าใจ, การศึกษา, ความชำนาญ, ประสิทธิภาพ, ความอวดดี, ความไม่ไว้วางใจ, องค์กร, ความสามารถในการเข้าใจผู้คน, ความรับผิดชอบ, จุดมุ่งหมาย, ความสามารถในการควบคุม, ตรรกะ, ความกระตือรือร้น, เจตจำนง, สัญชาตญาณ, ความเที่ยงธรรม ความรู้เรื่องมารยาท ปฏิกิริยา สติปัญญา ความมีไหวพริบ เจตจำนง สุขภาพ	ความโลภ ความไม่มีความรู้สึก ความอาฆาตพยาบาท ความเข้มงวด ความเจ้าเล่ห์ ความพยาบาท ความตระหนี่ ความเห็นแก่ตัว ความตระหนี่ ขาดการสื่อสาร ความขัดแย้ง
	ความเป็นผู้ประกอบการ, ความมีไหวพริบ, การมองโลกในแง่ดี, การเข้าสังคม, ความเฉลียวฉลาด, ความชำนาญ, อารมณ์ขัน, ไม่โอ้อวด, อหังการ, การปรับตัว, ความสมดุล, ความสามารถในการทำงานกับผู้คน, สัญชาตญาณ, ความมุ่งมั่น, สติปัญญา, กิจกรรม, การให้คำปรึกษา, การตอบสนองอย่างรวดเร็ว, ความกระตือรือร้น, สุขภาพ, ผู้จัดงาน, จะ ทักษะเข้าใจคน ความรู้เรื่องมารยาท ความเอาใจใส่ การควบคุม ตรรกะ การควบคุมตนเอง การวิเคราะห์	การเห็นแก่ประโยชน์ส่วนตน ความประมาทเลินเล่อ ความไม่ซื่อสัตย์ ความหลอกลวง ความหยิ่งทะนง การค้าขาย การใช้เล่ห์เหลี่ยม จินตนาการ ความหยิ่งผยอง การพนัน
	ความแม่นยำ, ความอุตสาหะ, ความอวดดี, ความรอบคอบ, จุดมุ่งหมาย, ความประหยัด, การปฏิบัติจริง, องค์กร, การควบคุมตนเอง, ความอดทน, สัญชาตญาณ, ความชำนาญ, ประสิทธิภาพ, ความระมัดระวัง, การศึกษา, ความสมดุล, ความสามารถในการทำงานกับผู้คน, การเข้าสังคม, กิจกรรม, การให้คำปรึกษา, การตอบสนองอย่างรวดเร็ว, ความรับผิดชอบ , ความกระตือรือร้น, สุขภาพ, ผู้จัดงาน, ความเที่ยงธรรม, ความสามารถในการเข้าใจผู้คน, ความรู้เรื่องมารยาท, ความเอาใจใส่, ความสามารถในการควบคุม, ตรรกะ, การวิเคราะห์, พิธีการ, ระบบราชการ	การนับถือยศ ความโลภ การค้าขาย การลักขโมย การทุจริต การติดสินบน การหลีกเลี่ยง ความลื่นไหล ความไม่สมดุล

	ความประหยัด ประสิทธิภาพ ความรอบคอบ ความเฉียบแหลม ความสามารถในการต่อรองราคา ความแม่นยำในการดำเนินธุรกิจ ความไม่ไว้วางใจ ความมุ่งมั่น ความเอาใจใส่ ความชัดเจน ความขยัน ความสามารถในการควบคุม การปฏิบัติจริง สุขภาพ สัญชาตญาณ ความเที่ยงธรรม ความสามารถในการเข้าใจบุคคล ความเด็ดเดี่ยว มุมมองในกลุ่มผลิตภัณฑ์ ความสามารถในการแข่งขัน การวิเคราะห์ ประสบการณ์ สัญชาตญาณ	ความซุ่มซ่าม, ความหยาบคาย, ความไม่รู้, กลอุบาย, ความสงสัย, ขาดวัฒนธรรม, ใจแคบต่อผู้คน, ความขัดแย้ง, ขาดความตั้งใจ
		การจัดการที่ผิดพลาด ขาดความเข้าใจในสินค้า ความโลภ ขาดจิตวิญญาณทางการค้า ความตระหนี่ การไม่ใส่ใจ การกักตุน การทำไม่ได้ ความไม่สมดุล

เราเริ่มต้นการแก้ปัญหาโดยการกำหนดน้ำหนัก - ความสำคัญของคุณภาพงาน (ดูตาราง 4.18) โดยใช้วิธีการเปรียบเทียบคู่ (ดูย่อหน้าที่ 1.3) โดยเริ่มจากผู้อำนวยการ (ตาราง 4.20)

เราพิจารณาว่าการกรอกเมทริกซ์ถูกต้องหรือไม่:

น้ำหนักของคุณภาพถูกกำหนดโดยสูตร M; = 5,-/และ 2 ใส่ผลลัพธ์ลงในตาราง 4.20.

จากนั้น เมื่อเปรียบเทียบคุณสมบัติที่จำเป็นของตำแหน่งผู้อำนวยการ (ดูตาราง 4.20) กับคุณสมบัติของผู้สมัคร (ตาราง 4.21) เราสร้างเมทริกซ์ของการมีอยู่ของคุณสมบัติของกรรมการในหมู่ผู้สมัคร (ดูตาราง 4.21) และคำนวณค่าประสิทธิภาพ ค่าสัมประสิทธิ์ สุ.

ผู้สมัครที่เหมาะสมที่สุดสำหรับตำแหน่งนี้คือ Gobsek ซู = 0,6224.

จากผลการเปรียบเทียบ เราจะกำหนดค่าสัมประสิทธิ์ประสิทธิภาพ ซูและใส่มันลงในตาราง 4.22.

ในทำนองเดียวกัน เราดำเนินการเปรียบเทียบสำหรับตำแหน่งอื่นๆ และค่าผลลัพธ์ สุนำเสนอในรูปแบบของเมทริกซ์ประสิทธิภาพ (ดูตาราง 4.22)

เมื่อแก้เมทริกซ์ผลลัพธ์โดยใช้วิธีฮังการีให้ได้ค่าสูงสุด เราจะได้เมทริกซ์ของการกระจายผู้สมัครที่เหมาะสมที่สุดตามตำแหน่ง (ตารางที่ 4.23)

ควรสังเกตว่าตำแหน่งผู้จัดการยังว่างอยู่ คุณสามารถแก้ไขปัญหาต่อไปได้โดยคำนึงถึงอิทธิพลของคุณสมบัติเชิงลบของผู้สมัครซึ่งจะลดค่าสัมประสิทธิ์ประสิทธิภาพ

ตารางที่ 4.20

คุณภาพ กรรมการ

คุณสมบัติของกรรมการ

1. ความรับผิดชอบ

2. การศึกษา

3. ความกระตือรือร้น

4. สุขภาพ

5. ออแกไนเซอร์

7. สัญชาตญาณ

8. ประสบการณ์การทำงาน

9. ทักษะการสื่อสาร

10. การวิจารณ์ตนเอง

11. ยอดคงเหลือ

12. ความเที่ยงธรรม

14.ความรู้เรื่องมารยาท

คุณสมบัติของกรรมการ		ผู้ท้าชิง
1. ความรับผิดชอบ
2. การศึกษา
3. ความกระตือรือร้น
4. สุขภาพ
5. ออแกไนเซอร์
7. สัญชาตญาณ
8. ประสบการณ์การทำงาน
9. ทักษะการสื่อสาร
10. การวิจารณ์ตนเอง
11. ยอดคงเหลือ
12. ความเที่ยงธรรม
13.ความสามารถในการเข้าใจผู้คน
14.ความรู้เรื่องมารยาท

ตารางที่ 4.22

ขั้นตอนเบื้องต้น .

ขั้นตอนที่ 1- ที่ เพิ่มฟังก์ชันวัตถุประสงค์ให้สูงสุด กับค้นหาองค์ประกอบสูงสุดและลบแต่ละองค์ประกอบของคอลัมน์นี้ออกจากค่าสูงสุด ที่ ลดฟังก์ชั่นวัตถุประสงค์ให้เหลือน้อยที่สุด(ผลรวมของตัวบ่งชี้ประสิทธิภาพตามใบสั่งยา) ในแต่ละคอลัมน์ของเมทริกซ์ กับหาองค์ประกอบขั้นต่ำแล้วลบออกจากแต่ละองค์ประกอบของคอลัมน์นั้น

กับ ด้วยองค์ประกอบที่ไม่เป็นลบ ในแต่ละคอลัมน์ของเมทริกซ์ กับ มีอย่างน้อยหนึ่งศูนย์

ขั้นตอนที่ 2- ในแต่ละแถวของเมทริกซ์ กับ ค้นหาองค์ประกอบขั้นต่ำและลบออกจากแต่ละองค์ประกอบของสตริงนี้

เป็นผลให้เกิดเมทริกซ์ขึ้น กับ 0 ที่มีองค์ประกอบไม่เป็นลบ ในทุกคอลัมน์และทุกแถวของเมทริกซ์ กับ 0 มีอย่างน้อยหนึ่งศูนย์ในแต่ละ

ขั้นตอนที่ 3- ทำเครื่องหมายศูนย์ใดๆ ในคอลัมน์แรกด้วยเครื่องหมายดอกจัน เริ่มจากคอลัมน์ที่สอง ดูแต่ละคอลัมน์ของเมทริกซ์ กับ 0 และทำเครื่องหมายด้วยเครื่องหมายดอกจันเป็นศูนย์ที่อยู่ในบรรทัดที่ไม่มีศูนย์ด้วยเครื่องหมายดอกจัน สามารถทำเครื่องหมายด้วยเครื่องหมายดอกจันได้เพียงศูนย์เดียวในแต่ละคอลัมน์ แน่นอน ค่าศูนย์ของเมทริกซ์ กับ 0 ที่มีเครื่องหมายดอกจันไม่ขึ้นกับโครงสร้าง นี่เป็นการสรุปขั้นตอนเบื้องต้น

( เค +1)ธ การวนซ้ำ . สมมุติว่า เค- การวนซ้ำครั้งที่แล้วได้ดำเนินการไปแล้วและด้วยเหตุนี้จึงได้เมทริกซ์มา กับ เค . ถ้าอยู่ในเมทริกซ์ กับ เค มีอยู่ตรงนั้น ปให้เป็นศูนย์ด้วยเครื่องหมายดอกจัน จากนั้นกระบวนการแก้ปัญหาจะสิ้นสุดลง หากจำนวนศูนย์ที่มีเครื่องหมายดอกจันน้อยกว่า ปจากนั้นเราไปที่ ( เค+ 1) การวนซ้ำครั้งที่

การวนซ้ำแต่ละครั้งจะเริ่มต้นด้วยขั้นตอนแรกและสิ้นสุดด้วยขั้นตอนที่สอง ระหว่างนั้นสามารถดำเนินการได้หลายครั้ง: สาม - ครั้งแรก. ก่อนที่จะเริ่มวนซ้ำ เครื่องหมาย "+" จะถูกใช้เพื่อไฮไลต์คอลัมน์ เมทริกซ์กับ เค ซึ่งมีเลขศูนย์ตามด้วยเครื่องหมายดอกจัน.

ขั้นแรก - ดู ไม่ได้เลือกคอลัมน์เมทริกซ์ กับ เค- หากไม่มีองค์ประกอบเป็นศูนย์ให้ไปที่ ขั้นตอนที่สาม.

หากไม่ได้เลือกศูนย์ของเมทริกซ์ กับ เคตรวจพบ จึงเป็นไปได้หนึ่งในสองกรณี:

บรรทัดนี้ไม่มีศูนย์ที่มีเครื่องหมายดอกจัน

ใน กรณีแรก ทำเครื่องหมายศูนย์ที่ไม่ได้เลือกด้วยเครื่องหมายขีดกลางและ เลือกบรรทัด ซึ่งมีอยู่โดยการใส่เครื่องหมาย “+” ทางด้านขวาของมัน แล้ว ทำลายเครื่องหมาย "+" โดยวงกลมไว้มากกว่านั้น คอลัมน์ จุดตัดของบรรทัดที่เลือกนี้จะมีศูนย์พร้อมเครื่องหมายดอกจัน

 หากเป็นเช่นนั้น ศูนย์ จะพบและเป็นอันเดียวในคอลัมน์นั้น เครื่องหมาย ของเขา จังหวะ และ เลือกบรรทัด (บรรทัด) ที่มีศูนย์ดังกล่าวจะถูกทำเครื่องหมายด้วยเครื่องหมาย “+” จากนั้นมองผ่านบรรทัดนี้ โดยมองหาศูนย์ที่มีเครื่องหมายดอกจันอยู่

 หากเป็นเช่นนั้น ศูนย์ พบได้ในคอลัมน์ แต่ไม่ใช่คอลัมน์เดียวในคอลัมน์ ดังนั้นคุณควรเลือกจากศูนย์เหล่านี้:

ประการแรก เลขศูนย์ดังกล่าวอยู่ในบรรทัดเดียวกันกับที่ไม่มี 0*;

ประการที่สอง ศูนย์ในแถวเดียวกันกับที่มี 0* แต่ในคอลัมน์เดียวกันกับ 0* นี้ จะมีศูนย์ที่ไม่ได้เลือก

สุดท้ายนี้ เป็นศูนย์ ในแถวเดียวซึ่งมี 0* แต่ในคอลัมน์เดียวที่มี 0* นี้ จะไม่มีศูนย์ที่ไม่ได้เลือก

กระบวนการนี้มีจำนวนขั้นตอนที่จำกัด และจบลงด้วยผลลัพธ์อย่างใดอย่างหนึ่งต่อไปนี้:

ผลลัพธ์ 1- ศูนย์เมทริกซ์ทั้งหมด กับ เคไฮไลต์ เช่น อยู่ในแถวหรือคอลัมน์ที่เลือก ในกรณีนี้ ไปที่ขั้นตอนที่สาม;

อพยพ 2- มีศูนย์ที่ไม่ได้เลือกในสตริงที่ไม่มีศูนย์ที่มีเครื่องหมายดอกจัน แล้ว ไปที่ขั้นตอนที่สอง, ทำเครื่องหมายศูนย์สุดท้ายด้วยขีด .

ใน กรณีที่สอง เมื่อทำเครื่องหมายศูนย์ที่ไม่ได้เลือกด้วยเส้นขีดแล้ว ให้ไปยังขั้นตอนที่สองทันที

ระยะที่สอง - สร้างสายโซ่ขององค์ประกอบเมทริกซ์ต่อไปนี้ กับ เค: ศูนย์นำหน้าด้วยจำนวนเฉพาะ, ศูนย์ที่มีเครื่องหมายดอกจันอยู่ในคอลัมน์เดียวกับตัวแรก, ศูนย์ที่มีจำนวนเฉพาะอยู่ในแถวเดียวกันกับศูนย์ที่อยู่ข้างหน้าด้วยเครื่องหมายดอกจัน เป็นต้น ดังนั้น โซ่เกิดขึ้นจากการเคลื่อนไหว จาก 0" ถึง 0* ตามคอลัมน์, จาก 0* ถึง 0" ตามบรรทัดฯลฯ

สามารถพิสูจน์ได้ว่าอัลกอริธึมที่อธิบายไว้สำหรับการสร้างลูกโซ่นั้นไม่คลุมเครือและมีขอบเขต โดยที่ ห่วงโซ่จะเริ่มต้นและสิ้นสุดเสมอ ศูนย์ด้วยจำนวนเฉพาะ - ถัดไป ใส่เครื่องหมายดอกจันเหนือองค์ประกอบของห่วงโซ่ที่อยู่ในตำแหน่งคี่ (0") เพื่อทำลายพวกมันเหนือองค์ประกอบคู่ (0*) จากนั้นทำลายเส้นขีดทั้งหมดที่อยู่เหนือองค์ประกอบของเมทริกซ์ กับ เคและเครื่องหมาย "+" ในกรณีนี้ จำนวนศูนย์อิสระจะเพิ่มขึ้นหนึ่งตัว. (เค + 1) การวนซ้ำครั้งที่ 2 เสร็จสมบูรณ์.

ขั้นตอนที่สาม - คุณควรจะก้าวไปสู่ขั้นนี้ หลังจากขั้นตอนแรก ถ้า ศูนย์ทั้งหมดของเมทริกซ์ กับ เค เน้นกล่าวคืออยู่ในแถวหรือคอลัมน์ที่เลือก ในกรณีนี้ ในบรรดาองค์ประกอบที่ไม่ได้เลือกของเมทริกซ์ กับ เค เลือก องค์ประกอบขั้นต่ำและทำเครื่องหมายไว้ ชม. > 0.

ลบ ชม. ของทั้งหมด องค์ประกอบ เมทริกซ์ กับ เค , อยู่ในบรรทัดที่ไม่ได้เลือก , และ

เพิ่ม ชม.ทั้งหมด องค์ประกอบ เมทริกซ์ กับ เค , ตั้งอยู่ในคอลัมน์เฉพาะ .

ผลลัพธ์ที่ได้คือเมทริกซ์ใหม่เทียบเท่ากับ กับ เค .

เนื่องจากอยู่ในองค์ประกอบที่ไม่ได้เลือกของเมทริกซ์
ศูนย์ใหม่จะปรากฏขึ้น (ตามคำจำกัดความ) คุณควรไปที่ด่านแรกและแทนที่จะเป็นเมทริกซ์ กับ เค ดูที่เมทริกซ์
.

เสร็จสิ้นขั้นตอนแรกหรือไปที่ ขั้นตอนที่สอง , หากศูนย์ที่ไม่ได้เลือกอยู่ในสตริงที่ไม่มีศูนย์ที่มีเครื่องหมายดอกจัน, หรือ กลับสู่ขั้นตอนที่สามอีกครั้ง , หากเป็นผลมาจากระยะแรกศูนย์เมทริกซ์ทั้งหมด
จะถูกเน้น.

ในกรณีแรก หลังจากขั้นตอนที่สอง การวนซ้ำสิ้นสุดลง.

ในกรณีที่สองหลังจากขั้นตอนที่สามจะได้รับเมทริกซ์
~
~กับ เค- ในเมทริกซ์
ศูนย์ที่ไม่ได้เลือกจะปรากฏขึ้น และจะต้องทำซ้ำลำดับการดำเนินการทั้งหมดตั้งแต่ขั้นตอนแรก หลังจากการทำซ้ำในจำนวนจำกัด ขั้นแรกถัดไปจะต้องจบลงด้วยการเปลี่ยนแปลง สู่ขั้นที่สอง ในระหว่างนี้จำนวนศูนย์อิสระจะเพิ่มขึ้นทีละหนึ่ง และ หลังจากนั้น (เค+1)ธ การวนซ้ำสิ้นสุดลง.

ตัวอย่างที่ 9มาแก้ไขปัญหาโดยใช้วิธีฮังการี:

เรือผิวน้ำต่อสู้มีอาวุธยิงต่อต้านอากาศยาน (ASF) 5 ชนิด มีการโจมตีทางอากาศของศัตรูพร้อมกันจำนวน 5 หน่วยบนเรือ ศักยภาพอันน่าทึ่งของทุกคน ฉัน-เอไอเอ เจ-เครื่องบินข้าศึกลำที่หนึ่งมีค่าเท่ากับ (จำนวนที่อาจถูกทำลายได้ เจ–x เครื่องบินระหว่างการโจมตีของ NK โดยเครื่องบินหนึ่งลำ) สันนิษฐานว่า AAM ใดๆ ก็ตามสามารถยิงไปที่เป้าหมายใดก็ได้

กระจายการคุ้มครองสิ่งแวดล้อมทั่วทั้ง CC ในลักษณะที่อาจเกิดความเสียหายโดยรวมสูงสุดภายใต้เงื่อนไขต่อไปนี้:

สามารถกำหนด ZOS ให้กับ CC ได้เพียงตัวเดียวเท่านั้น

เป้าหมายทั้งหมดจะต้องถูกยิงโดยเอไอเอ

สารละลาย :

ขั้นตอนเบื้องต้น .





ทำซ้ำครั้งแรก .

ขั้นแรก .

+ +



ใน

+ +

ขั้นตอนที่สอง .



ทำซ้ำครั้งที่สอง .

ป

+ +

ขั้นแรก .



เนื่องจากเมทริกซ์ศูนย์ทั้งหมด กับ 1 ถูกไฮไลต์ คุณควรไปยังขั้นตอนที่สาม

ขั้นตอนที่สาม .

+ +

+ +

ชม. =1 

ขั้นแรก .



ระยะที่สอง .



จากการแก้ปัญหาการมอบหมายงานโดยใช้วิธีฮังการีพบว่ามีลำดับ
=4,
=4,
=3,
=2,
=2 ให้ค่าสูงสุดของฟังก์ชันวัตถุประสงค์ =15. จากนี้ไปเพื่อขับไล่การโจมตีทางอากาศของศัตรู ตัวเลือกที่มีประสิทธิภาพมากที่สุดคือตัวเลือกในการกำหนด AOC ให้กับ CC ต่อไปนี้:

การออกกำลังกาย .

ค้นหาแผนอ้างอิงของปัญหาการขนส่งโดยใช้วิธี "มุมตะวันตกเฉียงเหนือ", "ต้นทุนน้อยที่สุด", "Vogel":

						ก ฉัน
การใช้งาน ข เจ

แก้ไขปัญหาการขนส่งจากภารกิจที่ 1 โดยใช้วิธีการกระจาย

แก้ไขปัญหาการขนส่งจากภารกิจที่ 1 โดยใช้วิธีที่เป็นไปได้

ใช้วิธีฮังการีในการแก้ปัญหาการกำหนดเมื่อค้นหาค่าสูงสุด:

ใช้วิธีฮังการีในการแก้ปัญหาการมอบหมายงานเมื่อค้นหาค่าขั้นต่ำ:

คำถามควบคุม :

ให้สูตรของปัญหาการเขียนโปรแกรมเชิงเส้นการขนส่ง

ปัญหาการขนส่งที่สมดุลแตกต่างจากปัญหาการขนส่งที่ไม่สมดุลอย่างไร

ปัญหาการขนส่งที่สมดุลควรมีตัวแปรพื้นฐานกี่ตัว

กำหนดแนวคิด: แผน แผนที่เป็นไปได้ แผนที่เป็นไปได้อ้างอิง แผนที่เหมาะสมที่สุด ใช้ในการแก้ไขปัญหาการขนส่ง

กำหนดอัลกอริทึมสำหรับการค้นหาแผนอ้างอิงโดยใช้วิธีมุมตะวันตกเฉียงเหนือ

กำหนดอัลกอริทึมสำหรับการค้นหาแผนอ้างอิงโดยใช้วิธีต้นทุนน้อยที่สุด

กำหนดอัลกอริทึมสำหรับการค้นหาแผนอ้างอิงโดยใช้วิธี Vogel

กำหนดอัลกอริทึมสำหรับการค้นหาแผนการที่เหมาะสมที่สุดโดยใช้วิธีการแจกแจง

กำหนดอัลกอริทึมสำหรับการค้นหาแผนการที่เหมาะสมที่สุดโดยใช้วิธีการที่เป็นไปได้

ให้การกำหนดปัญหาการมอบหมายงาน

เมทริกซ์จตุรัสของการมอบหมายเกิดขึ้นในปัญหาการมอบหมายสำหรับจำนวนวัตถุและวิธีการที่แตกต่างกันอย่างไร

กำหนดอัลกอริทึมสำหรับการแก้ปัญหาการมอบหมายงานโดยใช้วิธีภาษาฮังการี

เมทริกซ์การมอบหมายเริ่มต้นเกิดขึ้นอย่างไรในขั้นตอนเบื้องต้นเมื่อเพิ่มฟังก์ชั่นวัตถุประสงค์ให้สูงสุด?

เมทริกซ์การมอบหมายเริ่มต้นเกิดขึ้นอย่างไรในขั้นตอนเบื้องต้นเมื่อลดฟังก์ชั่นวัตถุประสงค์ให้เหลือน้อยที่สุด?

สาระสำคัญของขั้นตอนแรกของการแก้ปัญหาการมอบหมายงานโดยใช้วิธีการของฮังการีคืออะไร?

สาระสำคัญของขั้นตอนที่สองของการแก้ปัญหาการมอบหมายงานโดยใช้วิธีฮังการีคืออะไร?

สาระสำคัญของขั้นตอนที่สามในการแก้ปัญหาการมอบหมายงานโดยใช้วิธีฮังการีคืออะไร?

สามารถมีขั้นตอนที่หนึ่ง สอง และสามได้กี่ครั้งในการวนซ้ำของการแก้ปัญหาการมอบหมายงานโดยใช้วิธีภาษาฮังการี ลำดับขั้นตอนในการวนซ้ำคืออะไร?

ต้องมีศูนย์อิสระจำนวนเท่าใดในเมทริกซ์การกำหนดเพื่อตัดสินใจว่าพบการกำหนดเงินทุนที่เหมาะสมที่สุดให้กับวัตถุหรือไม่