Εισαγωγή
Στα προβλήματα ακέραιου προγραμματισμού οι μεταβλητές μπορούν να πάρουν μόνο ακέραιες τιμές. Πρόκειται για προβλήματα γραμμικού προγραμματισμού με τον επιπλέον αυτό περιορισμό. Αν τον αγνοήσουμε μπορούμε να τα λύσουμε σαν κανονικά ΠΓΠ και να πετύχουμε μια πρώτη προσέγγιση της λύσης τους. Στρογγυλοποιώντας τη πρώτη προσέγγιση στους πλησιέστερες εφικτές ακέραιες τιμές παίρνουμς τη δεύτερη προσέγγιση της λύσης του προβλήματος.
Ο τρόπος αυτός εφαρμόζεται συχνά και μπορεί να είναι ακριβής όταν οι μεταβλητές παίρνουν σχετικά μεγάλες τιμές. Μια εφαρμογή αυτής της προσέγγισης είδαμε στο προηγούμενο τμήμα (1.5) με το πρόβλημα παραγωγής, όταν στο τελευταίο στάδιο επιλέξαμε ακέραιες τιμές για το πλήθος των κατοικιών μια και δεν νοείται να κατασκευάσουμε 11,11 ή 29,33 κατοικίες.
Όμως μια τέτοια προσέγγιση μπορεί να είναι ανακριβής όταν αφορά μικρούς αριθμούς. Για το λόγο αυτό έχουν αναπτυχθεί ειδικοί αλγόριθμοι που επιλύουν προβλήματα ακέραιου (γραμμικού) προγραμματισμού και οι οποίοι συνήθως προέρχονται από τροποποιήσεις της μεθόδου Simplex.
