| Περίληψη: | Ο Ακέραιος Προγραμματισμός είναι κλάδος του Γραμμικού Μαθηματικού Προγραμματισμού, και αποτελεί τμήμα της συνδιαστικής βελτιστοποίησης. Στόχος της χρήσης του είναι η βελτιστοποίηση συστημάτων παραγωγής ή διοίκησης. Ο Ακέραιος Προγραμματισμός χρησιμοποιείται για την επίλυση πρακτικών προβλημάτων, όπως:
• Χρονοδιαγράμματα (Scheduling)
• Σχεδιασμός παραγωγής
• Παράλληλη εκτέλεση εργασιών
• Τηλεπικοινωνίες
Μπορεί να φαίνεται ότι τα προβλήματα ακεραίου προγραμματισμού είναι εύκολο να λυθούν. Παρ’όλ’αυτά, κάτι τέτοιο δεν ισχύει, διότι οι αστρονομικά μεγάλοι ακέραιοι αριθμοί, καθώς επίσης και η στρογγυλοποίηση και αφαίρεση μη ακεραίων λύσεων από ένα πρόβλημα γραμμικού προγραμματισμού οδηγούν σε προβλήματα και λανθασμένα συμπεράσματα.
Οι κυριότερες τεχνικές Ακεραίου Προγραμματισμού είναι οι εξής:
• Μέθοδος κλάδου και φραγής (Branch and Bound)
• Τεχνικές περιορισμού του εφικτού χώρου (Cutting Planes)
• Μέθοδοι απαρίθμησης
• Διαμεριστικοί αλγόριθμοι
• Αλγόριθμοι βασισμένοι στη θεωρία ομάδων (Gomory)
Η προπτυχιακή αυτή διπλωματική εργασία έχει στόχο να παρουσιάσει δύο από αυτές τις τεχνικές λεπτομερώς, την μέθοδο κλάδου και φραγής και τεχνικές περιορισμού του εφικτού χώρου, και να κάνει κατανοητή τη χρησιμότητα των αλγορίθμων αυτών μέσα από παραδείγματα που αφορούν προβλήματα ακέραιου προγραμματισμού.
|
|---|
