Σαν σήμερα, το 1956, ο Αμερικανός μαθηματικός George B. Dantzig, πιονιέρος του γραμμικού προγραμματισμού δημιουργεί ένα αλγόριθμο για την επίλυση του προβλήματος του σακιδίου. Ουσιαστικά πρόκειται για την εύρεση του πιο πολύτιμου υποσυνόλου n αντικειμένων που μπορούν να χωρέσουν σε ένα σακίδιο με δοσμένη χωρητικότητα.
Ο George B. Dantzig γεννήθηκε στο Πόρτλαντ του Όρεγκον.Οι γονείς του,τον ονόμασαν George Bernard προς τιμή του Τζορτζ Μπερνάρντ Σω, του Ιρλανδού συγγραφέα. Ο πατέρας του Tobias Dantzig ήταν Γερμανός μαθηματικός και γλωσσολόγος της Βαλτικής και η μητέρα του, Anja Dantzig Γαλλίδα γλωσσολόγος.O George Bernard Dantzig υπήρξε μαθηματικός διαμετρήματος με περγαμηνές στην στατιστική, στην επιστήμη των υπολογιστών, την οικονομική επιστήμη αλλά κυρίως στην επιχειρησιακή έρευνα. Γνωστός για την εργασία του στο γραμμικό προγραμματισμό και ειδικότερα για την δημιουργία του αλγορίθμου Simplex, ενός αλγόριθμου για την επίλυση προβλημάτων γραμμικού προγραμματισμού.
Το 1939, ενώ ήταν μεταπτυχιακός φοιτητής στο Berkeley πρωταγωνίστησε στο εξής περιστατικό. Καθυστερεί σε ένα μάθημα, όταν φτάνει,ο καθηγητής Jerzy Neyman είχε ήδη γράψει στον πίνακα δυο προβλήματα στατιστικής, ο Dantzig υποθέτει ότι τα προβλήματα ήταν μια εργασία στο σπίτι και τα σημειώνει. Η αλήθεια είναι ότι τα προβλήματα όπως ο ίδιος μετέπειτα έλεγε «φάνηκαν να είναι λίγο πιο δύσκολα από το συνηθισμένο», αλλά λίγες μέρες αργότερα έδωσε ολοκληρωμένες λύσεις και τις παρέδωσε όπως πίστευε καθυστερημένα στον Neyman.
Έξι εβδομάδες αργότερα, πρωί, κάποιος χτυπούσε μετ’ επιτάσεως την πόρτα του Dantzig, όταν άνοιξε την πόρτα είδε ένα κατενθουσιασμένο καθηγητή Neyman,ο οποίος του είπε ότι τα προβλήματα που είχε λύσει ήταν δύο από τα πιο διάσημα άλυτα προβλήματα στην στατιστική. Είχε προετοιμάσει μία από τις λύσεις του για δημοσίευση σε ένα μαθηματικό περιοδικό. Όπως είπε ο Dantzig σε μια συνέντευξη του 1986,στο Journal College Mathematics: "Ένα χρόνο αργότερα, όταν άρχισα να ανησυχώ για το ποιο πρέπει να είναι το θέμα της διατριβής μου, ο Neyman απλώς σηκώθηκε και μου είπε να ολοκληρώσω τα δύο προβλήματα να τα συρράψω και θα τα δεχόταν την διατριβή μου.'
Αυτή η ιστορία άρχισε να εξαπλώνεται και πήρε διαστάσεις με το όνομα του Dantzig σιγά-σιγά να αφαιρείται και τα γεγονότα να αλλάζουν, αλλά η βασική ιστορία παραμένει με τη μορφή αστικού μύθου και έμπνευση για την εισαγωγική σκηνή στην εξαίρετη ταινία Good Will Hunting.
Tο πρόβλημα του σακιδίου μελετάται για περισσότερο από έναν αιώνα, με αφετηρία περίπου το 1897. Από τα τέλη της δεκαετίας του 50, ο Tobias Dantzing (1884- 1956) ξεκίνησε τη μελέτη των Knapsack problems και έκτοτε η έρευνα τους εντάθηκε για δύο σημαντικούς λόγους. Πρώτον, τα προβλήματα αυτά έχουν άμεση εφαρμογή στη βιομηχανία, στη μηχανική, στο οικονομικό management και γενικότερα σε οποιονδήποτε τομέα υπάρχει ένα μοναδικό και σπάνιο αγαθό – πόρος που τον διεκδικούν πολλοί και δεύτερον για θεωρητικούς λόγους αφού τα Knapsack problems εμφανίζονται σε προβλήματα ακέραιου προγραμματισμού.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου