Κανονικές εγγραφές. Κανονική μορφή προβλημάτων γραμμικού προγραμματισμού. Θεώρημα για την κατάταξη του πίνακα TK

• Φροντιστήριο

Γεια σας φίλοι! Σε αυτό το άρθρο θα ήθελα να μιλήσω για έναν ενδιαφέροντα αλγόριθμο από τον κλάδο «Έρευνα Επιχειρήσεων», δηλαδή Ουγγρική μέθοδοςκαι πώς να το χρησιμοποιήσετε για την επίλυση προβλημάτων ανάθεσης. Θα θίξω λίγο τις θεωρίες σχετικά με το σε ποιες περιπτώσεις και για ποιες εργασίες μπορεί να εφαρμοστεί. αυτόν τον αλγόριθμο, θα το αναλύσω βήμα προς βήμα χρησιμοποιώντας ένα πλασματικό παράδειγμα και θα μοιραστώ τη μικρή μου σκιαγράφηση του κώδικα για την εφαρμογή του στη γλώσσα R.

Λίγα λόγια για τη μέθοδο

Για να μην περιγράψουμε πολλές θεωρίες με μαθηματικούς όρους και ορισμούς, προτείνω να εξετάσουμε μερικές επιλογές για την κατασκευή του προβλήματος ανάθεσης και νομίζω ότι θα καταλάβετε αμέσως σε ποιες περιπτώσεις ισχύει η ουγγρική μέθοδος:

• Το πρόβλημα της τοποθέτησης εργαζομένων σε θέσεις. Είναι απαραίτητο να κατανεμηθούν οι εργαζόμενοι σε θέσεις έτσι ώστε μέγιστη αποτελεσματικότητα, ή ήταν ελάχιστο κόστοςγια να δουλέψω.
• Εκχώρηση μηχανημάτων σε τμήματα παραγωγής. Η διανομή των μηχανημάτων ώστε όταν λειτουργούν η παραγωγή να είναι όσο το δυνατόν πιο κερδοφόρα ή το κόστος συντήρησής τους να είναι ελάχιστο.
• Επιλογή υποψηφίων για διαφορετικές κενές θέσεις βάσει αξιολογήσεων. Θα εξετάσουμε αυτό το παράδειγμα παρακάτω.

Όπως μπορείτε να δείτε, υπάρχουν πολλές επιλογές για τις οποίες εφαρμόζεται η ουγγρική μέθοδος και παρόμοια προβλήματα προκύπτουν σε πολλούς τομείς δραστηριότητας.

Ως αποτέλεσμα, το πρόβλημα πρέπει να λυθεί έτσι ώστε ένας εκτελεστής (άτομο, μηχανή, εργαλείο, ...) να μπορεί να εκτελέσει μόνο μία εργασία και κάθε εργασία να εκτελείται μόνο από έναν εκτελεστή.

Απαραίτητη και επαρκής συνθήκη για την επίλυση ενός προβλήματος είναι αυτό κλειστού τύπου. Εκείνοι. όταν ο αριθμός των ερμηνευτών = ο αριθμός των έργων (Ν=Μ). Εάν δεν πληρούται αυτή η προϋπόθεση, τότε μπορείτε να προσθέσετε εικονικούς ερμηνευτές ή πλασματικά έργα, για τα οποία οι τιμές στη μήτρα θα είναι μηδέν. Αυτό δεν θα επηρεάσει με κανέναν τρόπο τη λύση του προβλήματος, θα του δώσει μόνο τον απαραίτητο κλειστό τύπο.

Αλγόριθμος βήμα προς βήμα ως παράδειγμα

Διατύπωση του προβλήματος:Ας υπάρξει ένα σημαντικό Επιστημονικό Συνέδριο. Για να το πραγματοποιήσετε, πρέπει να ρυθμίσετε τον ήχο, το φως, τις εικόνες, να εγγράψετε καλεσμένους και να προετοιμαστείτε για διαλείμματα μεταξύ των παραστάσεων. Υπάρχουν 5 διοργανωτές για αυτήν την εργασία. Κάθε ένα από αυτά έχει ορισμένες αξιολογήσεις για την απόδοση μιας συγκεκριμένης εργασίας (ας υποθέσουμε ότι αυτές οι αξιολογήσεις ορίζονται ως ο αριθμητικός μέσος όρος των αξιολογήσεων των υπαλλήλων τους). Είναι απαραίτητο να κατανεμηθούν οι διοργανωτές έτσι ώστε η συνολική τους βαθμολογία να είναι η μέγιστη. Η εργασία μοιάζει με αυτό:

Εάν το πρόβλημα λυθεί στο μέγιστο (όπως στην περίπτωσή μας), τότε σε κάθε γραμμή του πίνακα είναι απαραίτητο να βρείτε το μέγιστο στοιχείο, να το αφαιρέσετε από κάθε στοιχείο της αντίστοιχης σειράς και να πολλαπλασιάσετε ολόκληρο τον πίνακα με -1. Εάν το πρόβλημα λυθεί τουλάχιστον, τότε αυτό το βήμα πρέπει να παραλειφθεί.

Πρέπει να υπάρχει μόνο ένα επιλεγμένο μηδέν σε κάθε γραμμή και κάθε στήλη. (δηλαδή όταν επιλέγεται το μηδέν, τότε τα υπόλοιπα μηδενικά σε αυτήν τη γραμμή ή σε αυτήν τη στήλη δεν λαμβάνονται πλέον υπόψη). Σε αυτή την περίπτωση είναι αδύνατο να γίνει αυτό:

(Εάν το πρόβλημα λυθεί στο ελάχιστο, τότε πρέπει να ξεκινήσετε από αυτό το βήμα). Συνεχίζουμε τη λύση περαιτέρω. Μείωση του πίνακα κατά σειρές (αναζητούμε το ελάχιστο στοιχείο σε κάθε σειρά και το αφαιρούμε από κάθε στοιχείο ανάλογα):

Επειδή όλα τα ελάχιστα στοιχεία είναι μηδέν, τότε ο πίνακας δεν έχει αλλάξει. Πραγματοποιούμε τη μείωση κατά στήλες:

Και πάλι, βεβαιωθείτε ότι υπάρχει μόνο ένα επιλεγμένο μηδέν σε κάθε στήλη και κάθε γραμμή. Όπως φαίνεται παρακάτω, στο σε αυτήν την περίπτωσηείναι αδύνατο να γίνει αυτό. Παρουσίασα δύο επιλογές για τον τρόπο επιλογής μηδενικών, αλλά καμία από αυτές δεν έδωσε το επιθυμητό αποτέλεσμα:

Ας συνεχίσουμε με τη λύση. Διαγράψτε γραμμές και στήλες που περιέχουν μηδενικά στοιχεία ( ΣΠΟΥΔΑΙΟΣ! Ο αριθμός των χτυπημάτων πρέπει να είναι ελάχιστος). Από τα υπόλοιπα στοιχεία, αναζητούμε το ελάχιστο, το αφαιρούμε από τα υπόλοιπα στοιχεία (τα οποία δεν διαγράφονται) και το προσθέτουμε στα στοιχεία που βρίσκονται στη διασταύρωση διαγραμμένων σειρών και στηλών (αυτό που σημειώνεται με πράσινο αφαιρείται εκεί συνοψίζεται ό,τι σημειώνεται με χρυσό, δεν αγγίζουμε ό,τι δεν είναι βαμμένο):

Όπως μπορείτε τώρα να δείτε, υπάρχει μόνο ένα επιλεγμένο μηδέν σε κάθε στήλη και σειρά. Ολοκληρώνουμε την εργασία!

Αντικαθιστούμε τις θέσεις των επιλεγμένων μηδενικών στον αρχικό πίνακα. Έτσι παίρνουμε το βέλτιστο, ή βέλτιστο σχέδιο, στην οποία οι διοργανωτές κατανέμονται μεταξύ των έργων και το άθροισμα των βαθμών είναι το μέγιστο:

Εάν λύνετε ένα πρόβλημα και εξακολουθείτε να είναι αδύνατο να επιλέξετε μηδενικά έτσι ώστε να υπάρχει μόνο ένα σε κάθε στήλη και σειρά, τότε επαναλαμβάνουμε τον αλγόριθμο από το σημείο όπου πραγματοποιήθηκε η μείωση κατά μήκος των γραμμών (το ελάχιστο στοιχείο σε κάθε γραμμή ).

Υλοποίηση στη γλώσσα προγραμματισμού R

Ο ουγγρικός αλγόριθμος υλοποιήθηκε με χρήση αναδρομών. Ελπίζω ότι ο κωδικός μου δεν θα προκαλέσει δυσκολίες. Πρώτα, πρέπει να μεταγλωττίσετε τρεις συναρτήσεις και, στη συνέχεια, να ξεκινήσετε τους υπολογισμούς.

Τα δεδομένα για την επίλυση του προβλήματος λαμβάνονται από το αρχείο example.csv, το οποίο έχει την εξής μορφή:

#Συνδέουμε τη βιβλιοθήκη για τη διευκόλυνση των υπολογισμών library(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 %>% 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)>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) (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) } #_________________________________________________________________________________

Αποτέλεσμα εκτέλεσης προγράμματος:

Τα ειδικά χαρακτηριστικά των προβλημάτων ανάθεσης οδήγησαν στην εμφάνιση μιας αποτελεσματικής ουγγρικής μεθόδου για την επίλυσή τους. Η κύρια ιδέα της ουγγρικής μεθόδου είναι η μετάβαση από την αρχική μήτρα τετραγωνικού κόστους ΜΕστον ισοδύναμο πίνακα 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. Κατανείμετε την παραγωγή τριών τύπων αγαθών T|, T 2, T3 σε πέντε επιχειρήσεις 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

Τίτλος εργασίας	Ποιότητες
Διευθυντής	Υπευθυνότητα, διοργανωτής, εκπαίδευση, εργασιακή εμπειρία, θέληση, υγεία, διαίσθηση, ενθουσιασμός, κοινωνικότητα, αυτοκριτική, ισορροπία, αντικειμενικότητα, ικανότητα κατανόησης ανθρώπων, έλλειψη σύγκρουσης, γνώση της εθιμοτυπίας
Διευθυντής	Εκπαίδευση, εμπειρία, δεξιότητες επικοινωνίας, ισορροπία, εργασία με ανθρώπους, διαίσθηση, αποφασιστικότητα, επινοητικότητα, ευφυΐα, δραστηριότητα, συμβουλευτική^, αντίδραση
Οικονομολόγος	Εκπαίδευση, αναλυτική, εμπειρία, δεξιότητες επικοινωνίας, ισορροπία, εργασία με ανθρώπους, διαίσθηση, ακρίβεια, μη σύγκρουση, ικανότητα πρόβλεψης, αυτοπεποίθηση, ικανότητα κατάρτισης επιχειρηματικού σχεδίου, πρακτικότητα
Λογιστής	Εκπαίδευση, εμπειρία, προσοχή, επιμονή, αγάπη για το μέτρημα, σαφήνεια, ακρίβεια, επιμέλεια, υπευθυνότητα, αφοσίωση, ικανότητα ελέγχου, ακεραιότητα, λογική, πρακτικότητα, αυτοέλεγχος, αναλυτικότητα, φορμαλισμός, γραφειοκρατία
Kommer Άγιος Βασίλης	Κοινωνικότητα, μη σύγκρουση, ενθουσιασμός, πρακτικότητα, ευγένεια, ικανότητα πειθούς, δραστηριότητα, προοπτική σε ομάδες προϊόντων, δέσμευση, επιμέλεια, πολυμάθεια, ανταγωνιστικότητα, επινοητικότητα, αίσθηση του χιούμορ

Για παράδειγμα, ως υποψήφιοι, θα χρησιμοποιήσουμε γνωστούς λογοτεχνικούς χαρακτήρες όπως οι 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) και υπολογίζουμε τις τιμές της αποτελεσματικότητας συντελεστές Su.

Ο καταλληλότερος υποψήφιος για αυτή τη θέση είναι ο Gobsek, Σου = 0,6224.

Με βάση τα αποτελέσματα σύγκρισης, προσδιορίζουμε τους συντελεστές απόδοσης suκαι εισάγετέ το στον πίνακα. 4.22.

Ομοίως, πραγματοποιούμε πράξεις σύγκρισης για άλλες θέσεις και τις τιμές που προκύπτουν SuΑς το παρουσιάσουμε με τη μορφή πίνακα απόδοσης (βλ. Πίνακα 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)ου επανάληψη . Ας υποθέσουμε ότι κ-η επανάληψη έχει ήδη πραγματοποιηθεί και ως αποτέλεσμα προκύπτει ο πίνακας ΜΕ κ . Αν στο matrix ΜΕ κ υπάρχει ακριβώς Πμηδενίζει με έναν αστερίσκο, τότε η διαδικασία επίλυσης τελειώνει. Αν ο αριθμός των μηδενικών με αστερίσκο είναι μικρότερος Π, μετά πάμε στο ( κ+ 1)η επανάληψη.

Κάθε επανάληψη ξεκινά με το πρώτο και τελειώνει με το δεύτερο στάδιο. Μεταξύ τους, μερικά στάδια μπορούν να πραγματοποιηθούν αρκετές φορές: τρίτο - πρώτο. Πριν από την έναρξη της επανάληψης, το σύμβολο «+» χρησιμοποιείται για την επισήμανσηστήλες μήτρεςΜΕ κ , τα οποία περιέχουν μηδενικά ακολουθούμενα από έναν αστερίσκο.

Πρώτο στάδιο . Θέα μη επιλεγμένοστήλες μήτρας ΜΕ κ. Εάν δεν υπάρχουν μηδενικά στοιχεία μεταξύ τους, τότε μεταβείτε στο τρίτο στάδιο.

Αν το μη επιλεγμένο μηδέν του πίνακα ΜΕ κανιχνευθεί, τότε είναι δυνατή μία από τις δύο περιπτώσεις:

αυτή η γραμμή δεν περιέχει μηδέν με αστερίσκο.

ΣΕ πρώτη περίπτωση Σημειώστε το μη επιλεγμένο μηδέν με μια παύλαΚαι επιλέξτε γραμμή , στο οποίο περιέχεται, τοποθετώντας το σύμβολο «+» στα δεξιά του. Επειτα καταστρέψτε το σύμβολο "+" κυκλώνοντάς τοπάνω από αυτό στήλη , η τομή του οποίου με αυτήν την επιλεγμένη γραμμή περιέχει ένα μηδέν με έναν αστερίσκο.

 Αν είναι τέτοια μηδέν βρίσκεται και είναι το μόνο στη στήλη, λοιπόν Σημάδι του Εγκεφαλικό Και επιλέξτε γραμμή (γραμμές) που περιέχουν τέτοια μηδενικά σημειώνονται με το σύμβολο «+». Στη συνέχεια, κοιτάξτε μέσα από αυτήν τη γραμμή(ες), αναζητώντας ένα μηδέν με έναν αστερίσκο μέσα τους.

 Αν είναι τέτοια μηδέν βρίσκεται στη στήλη, αλλά δεν είναι το μόνο στη στήλη, τότε από αυτά τα μηδενικά θα πρέπει να επιλέξετε:

πρώτα απ 'όλα, ένα τέτοιο μηδέν, στην ίδια γραμμή με την οποία δεν υπάρχει 0*.

Δεύτερον, ένα μηδέν στην ίδια σειρά με το οποίο υπάρχει ένα 0*, αλλά στην ίδια στήλη με αυτό το 0* υπάρχει ένα μη επιλεγμένο μηδέν.

Τέλος, ένα τέτοιο μηδέν, σε μια σειρά με την οποία υπάρχει 0*, αλλά σε μια στήλη με αυτό το 0* δεν υπάρχει μη επιλεγμένο μηδέν.

Αυτή η διαδικασία, ένας πεπερασμένος αριθμός βημάτων, τελειώνει με ένα από τα ακόλουθα αποτελέσματα:

Αποτέλεσμα 1. Όλα τα μηδενικά του πίνακα ΜΕ κεπισημαίνεται, δηλαδή βρίσκεται σε επιλεγμένες σειρές ή στήλες. Σε αυτήν την περίπτωση πηγαίνετε στο τρίτο στάδιο;

Έξοδος 2. Υπάρχει ένα μη επιλεγμένο μηδέν σε μια γραμμή όπου δεν υπάρχει μηδέν με αστερίσκο. Επειτα μεταβείτε στο δεύτερο στάδιο, σημειώνοντας το τελευταίο μηδέν με μια πινελιά .

Σε δεύτερη περίπτωση , έχοντας σημειώσει το μη επιλεγμένο μηδέν με ένα κτύπημα, προχωρήστε αμέσως στο δεύτερο στάδιο.

Δεύτερη φάση . Κατασκευάστε την ακόλουθη αλυσίδα στοιχείων μήτρας ΜΕ κ: ένα αρχικό μηδέν με πρώτο, ένα μηδέν με έναν αστερίσκο που βρίσκεται στην ίδια στήλη με το πρώτο, ένα μηδέν με έναν πρώτο που βρίσκεται στην ίδια σειρά με ένα προηγούμενο μηδέν με έναν αστερίσκο, κ.λπ. η αλυσίδα σχηματίζεται από την κίνηση από 0" έως 0* κατά στήλη, από 0* έως 0" κατά γραμμήκαι τα λοιπά.

Μπορεί να αποδειχθεί ότι ο περιγραφόμενος αλγόριθμος για την κατασκευή μιας αλυσίδας είναι σαφής και πεπερασμένος. Εν η αλυσίδα πάντα αρχίζει και τελειώνει μηδέν με πρώτο . Στη συνέχεια, βάλτε αστερίσκους πάνω από τα στοιχεία της αλυσίδας που βρίσκονται σε μονές θέσεις (0"), καταστρέφοντάς τα πάνω από τα ζυγά στοιχεία (0*). Στη συνέχεια, καταστρέψτε όλες τις πινελιές πάνω από τα στοιχεία της μήτρας ΜΕ κκαι τα σημάδια "+". Σε αυτήν την περίπτωση, ο αριθμός των ανεξάρτητων μηδενικών θα αυξηθεί κατά ένα. (κ + 1)η επανάληψη ολοκληρώθηκε.

Τρίτο στάδιο . Θα πρέπει να προχωρήσετε σε αυτό το στάδιο μετά το πρώτο στάδιο αν όλα τα μηδενικά του πίνακα ΜΕ κ τονίζεται, δηλαδή βρίσκονται σε επιλεγμένες σειρές ή στήλες. Σε αυτήν την περίπτωση, μεταξύ των μη επιλεγμένων στοιχείων του πίνακα ΜΕ κ επιλέγω ελάχιστο στοιχείοκαι σημειώστε το η > 0.

αφαιρώ η από όλους στοιχεία μήτρες ΜΕ κ , βρίσκεται σε μη επιλεγμένες γραμμές , Και

Προσθήκη ησε όλους στοιχεία μήτρες ΜΕ κ , βρίσκεται σε αφιερωμένες στήλες .

Το αποτέλεσμα είναι ένας νέος πίνακας ισοδύναμος με ΜΕ κ .

Αφού μεταξύ των μη επιλεγμένων στοιχείων του πίνακα
θα εμφανιστούν νέα μηδενικά (σύμφωνα με τον ορισμό), θα πρέπει να πάτε στο πρώτο στάδιο και αντί για τον πίνακα ΜΕ κ κοιτάξτε τη μήτρα
.

Έχοντας ολοκληρώσει το πρώτο στάδιο ή μεταβείτε στο δεύτερο επίπεδο , αν το μη επιλεγμένο μηδέν βρίσκεται σε μια συμβολοσειρά που δεν περιέχει μηδέν με αστερίσκο, ή επιστρέψτε ξανά στο τρίτο στάδιο , εάν ως αποτέλεσμα του πρώτου σταδίου όλα τα μηδενικά του πίνακα
θα τονιστεί.

Στην πρώτη περίπτωση μετά το δεύτερο στάδιο η επανάληψη τελειώνει.

Στη δεύτερη περίπτωση, μετά το τρίτο στάδιο, λαμβάνεται ο πίνακας
~
~ΜΕ κ. Στη μήτρα
Θα εμφανιστούν μη επιλεγμένα μηδενικά και πρέπει να επαναληφθεί ολόκληρη η ακολουθία πράξεων, ξεκινώντας από το πρώτο στάδιο. Μετά από έναν πεπερασμένο αριθμό επαναλήψεων, το επόμενο πρώτο στάδιο θα τελειώσει αναγκαστικά με μια μετάβαση στο δεύτερο στάδιο , κατά την οποία ο αριθμός των ανεξάρτητων μηδενικών θα αυξηθεί κατά ένα, και μετά το οποίο (κ+ 1)ου η επανάληψη τελειώνει.

Παράδειγμα 9.Ας λύσουμε το πρόβλημα χρησιμοποιώντας την ουγγρική μέθοδο:

Το πλοίο μάχης επιφανείας διαθέτει 5 αντιαεροπορικά πυροβόλα όπλα (ASF). Στο πλοίο πραγματοποιείται ταυτόχρονη αεροπορική επιδρομή του εχθρού σε ποσότητα 5 μονάδων. Οι εκπληκτικές δυνατότητες του καθενός Εγώ-ος ΔΑΑ ι-ο εχθρικό αεροσκάφος ισούται με (αριθμός πιθανών κατεστραμμένων ι–x αεροσκάφος κατά την επίθεση του ΝΚ από ένα αεροσκάφος). Υποτίθεται ότι κάθε AAM μπορεί να πυροβολήσει σε οποιονδήποτε στόχο.

Κατανείμετε την προστασία του περιβάλλοντος σε όλο το CC με τέτοιο τρόπο ώστε το συνολικό δυνητικό ζημία να είναι μέγιστο, υπό τις ακόλουθες συνθήκες:

Μόνο ένα ZOS μπορεί να εκχωρηθεί σε ένα CC.

όλοι οι στόχοι πρέπει να πυροβοληθούν από τον ΔΑΑ.

Λύση :

Προκαταρκτικό στάδιο .





Πρώτη επανάληψη .

Πρώτο στάδιο .

+ +



ΣΕ

+ +

δεύτερο επίπεδο .



Δεύτερη επανάληψη .

Π

+ +

πρώτο στάδιο .



Αφού όλα τα μηδενικά μηδενικά ΜΕ 1 επισημαίνονται, θα πρέπει να προχωρήσετε στο τρίτο στάδιο.

Τρίτο στάδιο .

+ +

+ +

η =1 

Πρώτο στάδιο .



Δεύτερη φάση .



Ως αποτέλεσμα της επίλυσης του προβλήματος ανάθεσης χρησιμοποιώντας την ουγγρική μέθοδο, βρήκαμε ότι η ακολουθία
=4,
=4,
=3,
=2,
Το =2 δίνει τη μέγιστη τιμή της αντικειμενικής συνάρτησης =15. Από αυτό προκύπτει ότι για την απόκρουση μιας εχθρικής αεροπορικής επίθεσης, η πιο αποτελεσματική επιλογή θα είναι η ακόλουθη επιλογή ανάθεσης συστήματος αεράμυνας στο CC:

Γυμνάσια .

Βρείτε το σχέδιο αναφοράς του προβλήματος μεταφοράς χρησιμοποιώντας τις μεθόδους «Βορειοδυτική γωνία», «Λαχότερο κόστος», «Vogel»:

						ένα Εγώ
Εφαρμογές σι ι

Λύστε το πρόβλημα μεταφοράς από την εργασία 1 χρησιμοποιώντας τη μέθοδο διανομής.

Λύστε το πρόβλημα μεταφοράς από την εργασία 1 χρησιμοποιώντας τη μέθοδο δυναμικού.

Χρησιμοποιώντας την ουγγρική μέθοδο για την επίλυση του προβλήματος ανάθεσης κατά την αναζήτηση του μέγιστου:

Χρησιμοποιώντας την ουγγρική μέθοδο για την επίλυση του προβλήματος ανάθεσης κατά την αναζήτηση του ελάχιστου:

Ερωτήσεις ελέγχου :

Δώστε τη διατύπωση του προβλήματος γραμμικού προγραμματισμού μεταφοράς.

Πώς διαφέρει ένα πρόβλημα ισορροπημένης μεταφοράς από ένα πρόβλημα μη ισορροπημένης μεταφοράς;

Πόσες βασικές μεταβλητές πρέπει να υπάρχουν σε ένα πρόβλημα ισορροπημένης μεταφοράς;

Ορίστε τις έννοιες: σχέδιο, εφικτό σχέδιο, αναφορά εφικτό σχέδιο, βέλτιστο σχέδιο, που χρησιμοποιείται για την επίλυση του προβλήματος των μεταφορών.

Διατυπώστε έναν αλγόριθμο για την εύρεση του σχεδίου αναφοράς χρησιμοποιώντας τη μέθοδο βορειοδυτικής γωνίας.

Διατυπώστε έναν αλγόριθμο για την εύρεση του σχεδίου αναφοράς χρησιμοποιώντας τη μέθοδο του ελάχιστου κόστους.

Διατυπώστε έναν αλγόριθμο για την εύρεση ενός σχεδίου αναφοράς χρησιμοποιώντας τη μέθοδο Vogel.

Διατυπώστε έναν αλγόριθμο για την εύρεση του βέλτιστου σχεδίου χρησιμοποιώντας τη μέθοδο κατανομής.

Διατυπώστε έναν αλγόριθμο για την εύρεση του βέλτιστου σχεδίου χρησιμοποιώντας τη μέθοδο του δυναμικού.

Δώστε τη διατύπωση του προβλήματος ανάθεσης.

Πώς σχηματίζεται ένας τετραγωνικός πίνακας αναθέσεων στο πρόβλημα ανάθεσης για διαφορετικούς αριθμούς αντικειμένων και μέσων;

Διατυπώστε έναν αλγόριθμο για την επίλυση του προβλήματος ανάθεσης χρησιμοποιώντας την ουγγρική μέθοδο.

Πώς σχηματίζεται ο αρχικός πίνακας ανάθεσης στο προκαταρκτικό στάδιο κατά τη μεγιστοποίηση της αντικειμενικής συνάρτησης;

Πώς σχηματίζεται ο αρχικός πίνακας ανάθεσης στο προκαταρκτικό στάδιο κατά την ελαχιστοποίηση της αντικειμενικής συνάρτησης;

Ποια είναι η ουσία του πρώτου σταδίου επίλυσης του προβλήματος της ανάθεσης χρησιμοποιώντας την ουγγρική μέθοδο;

Ποια είναι η ουσία του δεύτερου σταδίου επίλυσης του προβλήματος ανάθεσης χρησιμοποιώντας την ουγγρική μέθοδο;

Ποια είναι η ουσία του τρίτου σταδίου επίλυσης του προβλήματος ανάθεσης χρησιμοποιώντας την ουγγρική μέθοδο;

Πόσα πρώτα, δεύτερα και τρίτα στάδια μπορεί να υπάρχουν σε μία επανάληψη επίλυσης του προβλήματος ανάθεσης χρησιμοποιώντας την ουγγρική μέθοδο; Ποια είναι η ακολουθία των βημάτων σε μια επανάληψη;

Πόσα ανεξάρτητα μηδενικά πρέπει να υπάρχουν στον πίνακα εκχώρησης για να αποφασιστεί ότι έχει βρεθεί η βέλτιστη εκχώρηση κεφαλαίων σε αντικείμενα;