| Περίληψη: | Ο Γραμμικός Προγραμματισμός διαδραματίζει ένα σημαντικό ρόλο στη ζωή μας. Λόγω
των επαναστατικών εξελίξεων τόσο στην τεχνολογία των υπολογιστών όσο και στους αλ-
γόριθμους για τη γραμμική βελτιστοποίηση, προβλήματα που δεν μπορούσαν να λυθούν πριν
από χρόνια, λόγω ενός απαιτούμενου υπολογιστικού χρόνου, για παράδειγμα ενός έτους,
μπορούν τώρα να λυθούν μέσα σε λίγα λεπτά. Μέχρι το 1984, η μέθοδος επίλυσης προ-
βλημάτων γραμμικής βελτιστοποίησης ήταν η μέθοδος Simplex. Η ανάπτυξη της μεθόδου
Simplex από τον George Dantzig είναι μία από τις πιο δημοφιλείς και πιο σημαντικές με-
θόδους για την εύρεση λύσης στα προβλήματα γραμμικού προγραμματισμού. Από την αρχική
διατύπωση της το 1947, η μέθοδος αυτή συνεχώς βελτιώνεται. Η μέθοδος Simplex προχωρά
από μια κορυφή της εφικτής περιοχής που ορίζεται από τους περιορισμούς του προβλήμα-
τος σε μια γειτονική κορυφή. Οι Klee και Minty έδειξαν ότι, στη χειρότερη περίπτωση, η
μέθοδος Simplex έχει εκθετική πολυπλοκότητα. Το ερώτημα που τίθεται είναι αν υπάρχει
άλλος αλγόριθμος για το γραμμικό προγραμματισμό που έχει πολυωνυμική πολυπλοκότη-
τα. Αυτή η ερώτηση απαντήθηκε από τον Karmarkar το 1984. Ο Karmarkar παρουσίασε
έναν αλγόριθμο με πολυωνυμικό χρόνο γνωστός ως προβολικός αλγόριθμος για το γραμμικό
προγραμματισμό. Ο αλγόριθμος του Karmarkar χρησιμοποιεί εσωτερικά σημεία της εφικτής
περιοχής για να προσεγγίσει τη βέλτιστη λύση.
Η παρούσα εργασία λοιπόν, μελετά τη μέθοδο Simplex και τη μέθοδο εσωτερικού σημείου
του Karmarkar, τη κύρια ιδέα πίσω από τις μεθόδους και τη θεωρία που χρησιμοποιείται
για την ανάπτυξη της κάθε μεθόδου. Στο τέλος, παρουσιάζεται ένα πρόβλημα γραμμικού
προγραμματισμού και λύνεται αρχικά με τον αλγόριθμο του Karmarkar και στη συνέχεια με
τη μέθοδο Simplex.
|
|---|
