Στοιχεία γραμμικού και ακέραιου προγραμματισμού

Abstract

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

The book is an introduction to the section of Mathematical Programming concerning the optimization of a linear function subject to a set of linear constraints. A distinction is made in respect to whether the domain of the variables is continuous or discrete. In the first case the section is referred to as Linear Programming while in the second case as Integer (Linear) Programming. The book covers a great range of the former while it presents basic knowledge of the latter. Three core features of the subject are explored in the book: a) the modeling development reflecting practical problems, b) the theoretical study of the underlying structures that these models describe, c) the algorithmic techniques for solving the models developed in (a) based on the analysis presented in (b). Consequently, the book is a holistic approach to this specific field; the presentation of the underlying theory and its exploitation for model solving, the algorithmic techniques developed for that purpose and the analysis of the information that they provide as an output as well as the wide range of applications are some of the feature of this book which aims at motivating the reader to become more involved in this fascinating subject.