Τι είναι ο ακέραιος γραμμικός προγραμματισμός;

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

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

Ο γραμμικός προγραμματισμός γίνεται ακέραιος γραμμικός προγραμματισμός με την προσθήκη του ακέραιου περιορισμού.Αυτό σημαίνει ότι το πρόβλημα παραμένει το ίδιο, αλλά η απάντηση πρέπει να αποτελείται από ακέραιες τιμές για τις άγνωστες τιμές: πρέπει να είναι ολόκληροι αριθμοί.Μερικές φορές, αυτό σημαίνει ότι η λύση θα είναι υποβέλτιστη σε σύγκριση με την περίπτωση στην οποία επιτρέπονται κλάσματα.Είναι όμως αντανακλαστικό του πραγματικού κόσμου, στον οποίο τα αντικείμενα συχνά έρχονται σε διακριτές, αδιαίρετες μονάδες.Αυτό καθιστά τον ακέραιο γραμμικό προγραμματισμό σημαντικό για τις επιχειρηματικές εφαρμογές, καθώς οι επιχειρήσεις θέλουν να μεγιστοποιήσουν τα κέρδη όσο το δυνατόν περισσότερο, αλλά δεν μπορούν να επιλέξουν να πουλήσουν ένα κλάσμα ενός προϊόντος.-πλήρης.Αυτό σημαίνει ότι ο χρόνος που είναι απαραίτητος για έναν υπολογιστή για την επίλυση του συστήματος είναι απροσδιόριστη.Με τους ακέραιους περιορισμούς, οι υπολογιστές δεν μπορούν να χρησιμοποιήσουν το εργαλείο του παραγώγου, επειδή δεν υπάρχει καμία εγγύηση ότι το μηδενικό σημείο του παραγώγου θα πέσει σε ακέραιο.Η λύση θα είναι ο ακέραιος με την υψηλότερη ή τη χαμηλότερη τιμή από όλους τους ακέραιους, οπότε ο υπολογιστής θα πρέπει να τα ελέγξει όλα mdash;Μια διαδικασία που θα μπορούσε να πάρει ένα άπειρο χρονικό διάστημα. Οι προγραμματιστές έχουν αναπτύξει ευρετικά ή μεθόδους επίλυσης προβλημάτων, για να αντιμετωπίσουν την πολυπλοκότητα αυτών των προβλημάτων.Μία μέθοδος επίλυσης των ακέραιων προβλημάτων γραμμικού προγραμματισμού είναι ο αλγόριθμος κλάδου και δεσμευμένου, στον οποίο ο υπολογιστής επιλύει μια σειρά προβλημάτων που σχετίζονται με το αρχικό για να περιορίσουν το διαθέσιμο εύρος τιμών σε μία λύση.Για σύνθετα προβλήματα, ωστόσο, αυτό μπορεί να διαρκέσει πολύ.