Το Πρόβλημα Του Τετραγωνικού Προγραμματισμού

Abstract

Ο σκοπός της διπλωματικής εργασίας ήταν η μελέτη του προβλήματος του τετραγωνικού προγραμματισμού και η υλοποίηση αλγορίθμων επίλυσησ του προβλήματος του θετικά και μη - θετικά ορισμένου τετραγωνικού προγραμματισμού.Στην περίπτωση του θετικά ορισμένου τετραγωνικού προγραμματισμού, η λύση του προβλήματος είναι μοναδική (το γενικό ελάχιστο του προβλήματος) και η εύρεσή του είναι πάντοτε εφικτή. Για την επίλυση του προβλήματος αυτού εφαρμόστηκε η μέθοδος του ενεργού συνόλου.Σε αντίθεση με τον θετικά ορισμένο τετραγωνικό προγραμματισμό, στην περίπτωση του μη - θετικά ορισμένου τετραγωνικού προγραμματισμού, η λύση του προβλήματος δεν είναι μοναδική (μπορεί να είναι οποιοδήποτε τοπικό ελάχιστο του προβλήματος), ενώ η ύπαρξη της δεν είναι πάντοτε εξασφαλισμένη (μη - φραγμένα προβλήματα). Για την επίλυση του προβλήματος αυτού εφαρμόστηκε μία τροποποιημένη μέθοδος του ενεργού συνόλου η οποία προτείνεται απο τον R. Fletcher για τον εντοπισμό ενόσ τοπικού ελαχίστου του προβλήματος (το οποίο αρκετά συχνά είναι το γενικό ελάχιστο του προβλήματος).Το πρόγραμμα που κατασκευάστηκε είναι κατάλληλο για την επίλυση οποιασδήποτε επιτρεπτής μορφής την οποία μπορεί να πάρει το πρόβλημα του τετραγωνικού προγραμματισμού, ανάλογα με το είδος και το πλήθος των περιορισμών του.