Προβλήματα Μαθηματικών

Νοέμβριος 29, 2008

Γραμμικός προγραμματισμός

Filed under: Άλυτα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 8:32 μμ

Ένα γραμμικό πρόγραμμα είναι ένα πρόβλημα βελτιστοποίησης του εξής τύπου:

Ελαχιστοποίηση του εσωτερικού γινομένου {c^\top x}, υπό τους περιορισμούς

{A x \ge b}

όπου x=(x_1,\ldots,x_n)^\top \in {\mathbb R}^n είναι ένα διάνυσμα στήλη το οποίο αναζητούμε να βρούμε. Τα διανύσματα c=(c_1,\ldots,c_n)^\top και b=(b_1,\ldots,b_m)^\top είναι σταθερά διανύσματα και A είναι ένας σταθερός m \times n πίνακας. Τέλος γράφουμε u \ge v για δύο διανύσματα u,v αν η ανισότητα ισχύει κατά συνεταγμένες.

Τα γραμμικά προγράμματα είναι πολύτιμα εργαλεία: λύνονται εύκολα θεωρητικά (υπάρχει δηλ. αλγόριθμος πολυωνυμικού χρόνου για τη λύση τους) και πρακτικά (υπάρχουν πολλές μέθοδοι, π.χ. η μέθοδος simplex, που τα λύνουν τάχιστα).

Έχετε κάποια πειραματικά δεδομένα

{(X_1, Y_1), \ldots, (X_N, Y_N)}

(με X_j < X_{j+1}) στα οποία θέλετε να προσαρμόσετε μια ευθεία f(x) = ax+b. Θέλετε δηλ. να βρείτε τα a, b \in {\mathbb R} έτσι ώστε τα σημεία (X_j, Y_j) να είναι όσο το δυνατόν «κοντύτερα» στο να είναι πάνω στην ευθεία. Το πόσο καλή είναι μια επιλογή των a, b μπορεί να μετρηθεί με διάφορους τρόπους. Ο συνηθέστερος είναι η \ell^2 απόσταση (αλλιώς: ελάχιστα τετράγωνα) δηλ. η ελαχιστοποίηση της ποσότητας

{\sum_{j=1}^N (f(X_j)-Y_j)^2}.

Αυτό εύκολα βλέπει κανείς (παραγωγίζοντας ως προς a, b) ότι ανάγεται σε ένα απλό γραμμικό 2 επί 2 σύστημα.

Δείξτε πώς μπορεί κανείς να ελαχιστοποιήσει την \ell^1 απόσταση

{\sum_{j=1}^N |f(X_j)-Y_j|},

όπως και την \ell^\infty απόσταση

{\max_{j=1,\ldots,N}|f(X_j)-Y_j|}

χρησιμοποιώντας γραμμικό προγραμματισμό με O(N) μεταβλητές και O(N) περιορισμούς.

Advertisements

3 Σχόλια »

  1. Υπόδειξη:
    Αν t=|x| τότε το t είναι η λύση του προβλήματος ελαχιστοποίησης: \min\  t υπό τους περιορισμούς t \ge x,\ t \ge -x.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Δεκέμβριος 7, 2008 @ 10:41 μμ

  2. Υπόδειξη:

    Για να ελαχιστοποιήσετε την \ell^1 απόσταση

    \sum_{j=1}^N |f(X_j)-Y_j|

    εισάγετε από μια καινούργια μεταβλητή t_j για κάθε προσθετέο στο άνω άθροισμα και φροντίσετε να προσθέσετε περιορισμούς στο γραμμικό σας πρόβλημα ώστε στη λύση του να είναι εγγυημένο ότι

    t_j = |f(X_j)-Y_j|.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουνίου 2, 2009 @ 12:29 μμ

  3. Υποδειξη Νο. 3 (Ο λογος αυτης της υποδειξης ειναι να διαφημισει ενα συγκεκριμενο βιβλιο)

    Η λυση των παραπανω προβληματων περιγραφονται αναλυτικα στο βιβλιο Linear Programming του Dantzig (δημιουργου της μεθοδου Simplex).
    Το βιβλιο υπαρχει σε ηλεκτρονικη μορφη απο την βιβλιοθηκη του πανεπιστημιου κρητης:
    http://147.52.249.100/F/MJTAM2MLJGMQIC3MAKSB8NFSB5U494MVV3G1N441XE4F7BSRU8-01028?func=full-set-set&set_number=001050&set_entry=000002&format=999

    Πιστευω πως αξιζει να βρισκετε στην (ηλεκτρονικη) βιβλιοθηκη καθενος.

    Μου αρέσει!

    Σχόλιο από yannispantazis — Οκτώβριος 11, 2009 @ 4:27 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: