Η επιχειρησιακή έρευνα, η επιστήμη της χρήσης υπολογιστών για τη λήψη βέλτιστων αποφάσεων, έχει χρησιμοποιηθεί και εφαρμοστεί σε πολλούς τομείς του λογισμικού. Για να δώσουμε μερικά παραδείγματα, οι εταιρείες logistics το χρησιμοποιούν για να καθορίσουν τη βέλτιστη διαδρομή για να φτάσουν από το σημείο A στο σημείο B, οι εταιρείες ηλεκτρικής ενέργειας το χρησιμοποιούν για να καθορίσουν τα χρονοδιαγράμματα παραγωγής ενέργειας και οι κατασκευαστικές εταιρείες το χρησιμοποιούν για να βρουν τα βέλτιστα πρότυπα προσωπικού.

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

Αλγόριθμοι Έρευνας Επιχειρήσεων

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

Γραμμικοί αλγόριθμοι προγραμματισμού

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

Maximize a + b (objetive) Subject a: a <= 2 (restriction 1) b <= 3 (restriction 2)

Στο απλό μας παράδειγμα, μπορούμε να δούμε ότι το βέλτιστο αποτέλεσμα είναι 5, με a = 2 και b = 3. Ενώ αυτό είναι ένα αρκετά ασήμαντο παράδειγμα, μπορείτε πιθανώς να φανταστείτε ένα γραμμικό μοντέλο προγραμματισμού που χρησιμοποιεί χιλιάδες μεταβλητές και εκατοντάδες περιορισμούς. .

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

Maximize Subject to: Etc. ...

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

Αλγόριθμοι ακέραιου προγραμματισμού

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

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

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

Αντικείμενο	Αξία (μονάδες 10 $)	Μέγεθος (γενικές μονάδες)
ΦΩΤΟΓΡΑΦΙΚΗ ΜΗΧΑΝΗ	5	2
Μυστηριώδες ειδώλιο	7	4
Τεράστιο μπουκάλι μηλίτη μήλου	2	7
γαλλική κόρνα	10	10

Και το μοντέλο MIP θα μοιάζει με αυτό:

Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint)

Η βέλτιστη λύση, στην περίπτωση αυτή, είναι a = 0, b = 1, c = 0, d = 1, με την τιμή του συνολικού στοιχείου να είναι 17.

Το πρόβλημα που θα επιλύσουμε σήμερα θα απαιτήσει επίσης ένα ολόκληρο πρόγραμμα, καθώς ένας υπάλληλος σε ένα εργοστάσιο μπορεί ή δεν μπορεί να προγραμματιστεί για μια βάρδια - για λόγους απλότητας, δεν μπορείτε να προγραμματίσετε έναν υπάλληλο για 2/3 μιας βάρδιας σε αυτό το εργοστάσιο.

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

Παράδειγμα Πρόβλημα: Προγραμματισμός

Περιγραφή του προβλήματος

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

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

Shift 1	Shift 2	Shift 3	Shift 4	Shift 5
1 άτομο	4 άτομα	3 άτομα	5 άτομα	2 άνθρωποι

Και ας υποθέσουμε ότι έχουμε τους ακόλουθους εργαζόμενους:

Ονομα	Διαθεσιμότητα	Κόστος ανά βάρδια ($)
Μελισάνδρη	1, 2, 5	είκοσι
Πίτουρο	2. 3. 4. 5	δεκαπέντε
Τσερσέι	3. 4	35
Daenerys	Τέσσερα πέντε	35
Theon	2, 4, 5	10
Τζον	1, 3, 5	25
Τύριον	2, 4, 5	30
Τζέιμς	2, 3, 5	είκοσι
Άρια	1, 2, 4	είκοσι

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

Τα εργαλεία μας

Για το σημερινό πρόβλημα, θα χρησιμοποιήσουμε λογισμικό ανοιχτού κώδικα και κλάδου που ονομάζεται CBC. Θα αλληλεπιδράσουμε με αυτό το λογισμικό χρησιμοποιώντας το PuLP, το οποίο είναι μια δημοφιλής βιβλιοθήκη μοντελοποίησης ερευνητικών λειτουργιών για την Python. Μπορείτε να βρείτε πληροφορίες σχετικά με αυτό εδώ .

Το PuLP μας επιτρέπει να κατασκευάσουμε μοντέλα MIP με πολύ Πυθικό τρόπο και ενσωματώνεται πολύ καλά με τον υπάρχοντα κώδικα Python. Αυτό είναι πολύ χρήσιμο καθώς μερικά από τα πιο δημοφιλή εργαλεία χειρισμού και ανάλυσης δεδομένων γράφονται στο Python και τα περισσότερα ερευνητικά συστήματα επιχειρησιακών λειτουργιών απαιτούν εκτεταμένη επεξεργασία δεδομένων πριν και μετά τη βελτιστοποίηση.

Για να δείξετε την απλότητα και την κομψότητα του PuLP, εδώ είναι το πρόβλημα του σακιδίου από πριν και λύθηκε στο PuLP:

import pulp as pl # declarar algunas variables # cada variable es una variable binaria que es 0 o 1 # 1 significa que el artículo irá a la mochila a = pl.LpVariable('a', 0, 1, pl.LpInteger) b = pl.LpVariable('b', 0, 1, pl.LpInteger) c = pl.LpVariable('c', 0, 1, pl.LpInteger) d = pl.LpVariable('d', 0, 1, pl.LpInteger) # define el problema prob = pl.LpProblem('knapsack', pl.LpMaximize) # función objetivo - maximizar el valor de los objetos en la mochila prob += 5 * a + 7 * b + 2 * c + 10 * d # restricción: el peso de los objetos no puede exceder 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 estado = prob.solve() # resuelve usando el solucionador predeterminado, que es cbc print(pl.LpStatus[status]) # imprime el estado legible por humanos # imprime los valores print('a', pl.value(a)) print('b', pl.value(b)) print('c', pl.value(c)) print('d', pl.value(d))

Εκτελέστε αυτό και θα πρέπει να λάβετε την έξοδο:

Optimal a 0.0 b 1.0 c 0.0 d 1.0

Τώρα στο πρόβλημα προγραμματισμού μας!

Κωδικοποίηση της λύσης μας

Η κωδικοποίηση της λύσης μας είναι αρκετά απλή. Πρώτον, θα ορίσουμε τα δεδομένα μας:

import pulp as pl import collections as cl # data shift_requirements = [1, 4, 3, 5, 2] workers = { 'Melisandre': { 'availability': [0, 1, 4], 'cost': 20 }, 'Bran': { 'availability': [1, 2, 3, 4], 'cost': 15 }, 'Cersei': { 'availability': [2, 3], 'cost': 35 }, 'Daenerys': { 'availability': [3, 4], 'cost': 35 }, 'Theon': { 'availability': [1, 3, 4], 'cost': 10 }, 'Jon': { 'availability': [0, 2, 4], 'cost': 25 }, 'Tyrion': { 'availability': [1, 3, 4], 'cost': 30 }, 'Jaime': { 'availability': [1, 2, 4], 'cost': 20 }, 'Arya': { 'availability': [0, 1, 3], 'cost': 20 } }

Στη συνέχεια, πρέπει να ορίσουμε το μοντέλο:

# define el modelo: queremos minimizar el costo prob = pl.LpProblem('scheduling', pl.LpMinimize) # algunos modelos de variable cost = [] vars_by_shift = cl.defaultdict(list) for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable('%s_%s' % (worker, shift), 0, 1, pl.LpInteger) vars_by_shift[shift].append(worker_var) cost.append(worker_var * info['cost']) # establece el objetivo para que sea la suma del costo prob += sum(cost) # establece los requerimientos de cambio for shift, requirement in enumerate(shift_requirements): prob += sum(vars_by_shift[shift]) >= requirement

Και τώρα, σας ζητάμε να λύσετε και να εκτυπώσετε τα αποτελέσματα!

status = prob.solve() print('Result:', pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ 'shift': shift, 'workers': [var.name for var in vars if var.varValue == 1], }) for result in sorted(results, key=lambda x: x['shift']): print('Shift:', result['shift'], 'workers:', ', '.join(result['workers']))

Μόλις εκτελέσετε τον κώδικα, θα δείτε τις ακόλουθες εξόδους:

Result: Optimal Shift: 0 workers: Arya_0 Shift: 1 workers: Melisandre_1, Bran_1, Theon_1, Arya_1 Shift: 2 workers: Bran_2, Jon_2, Jaime_2 Shift: 3 workers: Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3 Shift: 4 workers: Bran_4, Theon_4

Αύξηση της δυσκολίας ελαφρώς: Πρόσθετοι περιορισμοί

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

Πρόσθετοι περιορισμοί

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

Ας υποθέσουμε επίσης ότι λόγω κάποιων διαρκών διαπροσωπικών συγκρούσεων έξω από το εργοστάσιό μας, οι Cersei και Jaime δεν μπορούν να εργαστούν με βάρδιες είτε με την Daenerys είτε με τον Jon. Επίσης, η Jaime και η Cersei δεν μπορούν να κάνουν μαζί βάρδιες. Τέλος, η Arya, που έχει ιδιαίτερα περίπλοκες διαπροσωπικές σχέσεις, δεν μπορεί να συνεργαστεί με τον Jaime, τον Cersei ή τον Melisandre.

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

Λύση

Ωστόσο, με μικτό ακέραιο προγραμματισμό, είναι πολύ πιο εύκολο. Πρέπει απλώς να τροποποιήσουμε τον κωδικό μας ως εξής:

Ορίστε τη λίστα απαγορεύσεων και ορισμένους περιορισμούς:

ban_list = { ('Daenerys', 'Jaime'), ('Daenerys', 'Cersei'), ('Jon', 'Jaime'), ('Jon', 'Cersei'), ('Arya', 'Jaime'), ('Arya', 'Cersei'), ('Arya', 'Melisandre'), ('Jaime', 'Cersei') } DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Συμπληρώστε μερικές μεταβλητές για να εφαρμόσετε τους περιορισμούς απαγόρευσης και μέγιστης αλλαγής:

for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable('%s_%d' % (worker, shift), 0, 1, pl.LpInteger) # almacena algunos datos variables para que podamos implementar la restricción de prohibición var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # almacena vars por variable para que podamos implementar la restricción de cambio máximo vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost'])

Προσθέστε τις μεταβλητές Dothraki:

for shift in range(len(shift_requirements)): dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger) cost.append(dothraki_var * DOTHRAKI_COST) dothrakis_by_shift[shift] = dothraki_var

Θα χρειαστούμε επίσης έναν ελαφρώς τροποποιημένο βρόχο για τον υπολογισμό των απαιτήσεων αλλαγής και απαγόρευσης:

# establece los requerimientos de cambio for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # establece los requerimientos de prohibición for shift, vars in vars_by_shift.items(): for var1 in vars: for var2 in vars: worker_pair = var1[1][0], var2[1][0] if worker_pair in ban_list: prob += var1[0] + var2[0] <= 1 # establece los estándares de trabajo: for worker, vars in vars_by_worker.items(): prob += sum(vars) <= 2

Και τέλος, για να εκτυπώσετε τα αποτελέσματα:

status = prob.solve() print('Result:', pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ 'shift': shift, 'workers': [var[1][0] for var in vars if var[0].varValue == 1], 'dothrakis': dothrakis_by_shift[shift].varValue }) for result in sorted(results, key=lambda x: x['shift']): print('Shift:', result['shift'], 'workers:', ', '.join(result['workers']), 'dothrakis hired:', int(result['dothrakis']))

Και πρέπει να είμαστε έτοιμοι. Εκτελέστε τον κωδικό και θα δείτε το αποτέλεσμα ως εξής:

Resultado: Óptimo Shift: 0 trabajadores: Arya dothrakis contratados: 0 Shift: 1 trabajador: Melisandre, Theon, Tyrion, Jaime dothrakis contratados: 0 Shift: 2 trabajadores: Bran, Jon dothrakis contratados: 1 Shift: 3 trabajadores: Bran, Daenerys, Theon, Tyrion, Arya dothrakis contratados: 0 Shift: 4 trabajadores: Melisandre, Jaime dothrakis contratados: 0

Και η voila, ένα αποτέλεσμα που σέβεται τη λίστα απαγορευμένων εργαζομένων ακολουθεί τους εργασιακούς κανονισμούς και χρησιμοποιεί τους εργαζομένους του Dothraki με σύνεση.

συμπέρασμα

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

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

Μπορείτε να βρείτε όλο τον κωδικό που σχετίζεται με αυτό το άρθρο στο GitHub . Αν θέλετε να συζητήσετε περισσότερα, μοιραστείτε τα σχόλιά σας παρακάτω!