ΕΛΑΧΙΣΤΟΠΟΙΗΣΗ

Γενικά θέματα Μαθηματικών καί περί Μαθηματικών

Συντονιστής: Παύλος Μαραγκουδάκης

Λάμπρος Κατσάπας
Δημοσιεύσεις: 211
Εγγραφή: Σάβ Ιουν 17, 2017 10:17 pm
Τοποθεσία: Αθήνα

ΕΛΑΧΙΣΤΟΠΟΙΗΣΗ

#1

Μη αναγνωσμένη δημοσίευση από Λάμπρος Κατσάπας » Τετ Ιούλ 11, 2018 8:41 pm

Θεωρούμε n διακεκριμένα σημεία A_i(a_i),i=1,2,...,n πάνω σε μια ευθεία. Να βρεθεί σημείο B(b) της ευθείας για το οπoίο πετυχαίνουμε το

\displaystyle{min \sum_{i=1}^{n} |a_i-b| }.



Λέξεις Κλειδιά:
Altrian
Δημοσιεύσεις: 60
Εγγραφή: Τρί Μάιος 01, 2018 4:51 pm
Τοποθεσία: Βούλα, Αττική

Re: ΕΛΑΧΙΣΤΟΠΟΙΗΣΗ

#2

Μη αναγνωσμένη δημοσίευση από Altrian » Παρ Ιούλ 13, 2018 4:32 pm

Καλησπέρα,
Ζητάμε την ελαχιστοποίηση του αθροίσματος των n αποστάσεων του σημείου b από κάθε σημείο a_i. Αν τα σημεία είναι 2 (n=2) τότε το ελάχιστο άθροισμα δίνεται από κάθε σημείο b ανάμεσα στα a_1, a_2 ίσο με την απόσταση αυτών. Αν n=3 με έστω το τρίτο σημείο εντός του διαστήματος \left [ a_1, a_2 \right ] τότε έχουμε ελάχιστο για b=a_3. Αν n=4 με διάταξη έστω a_1, a_2, a_3, a_4 τότε το ελάχιστο προκύπτει για κάθε σημείο b εντός του εσωτερικού κεντρικού διαστήματος \left [ a_2, a_3 \right ]. Ουσιαστικά μιλάμε για το median των τιμών a_1, a_2,....,a_n που είναι το μεσαίο σε διάταξη σημείο αν n περιττός ή κάθε σημείο του μεσαίου σε διάταξη τμήματος αν n άρτιος.
Σημ. Ο median χρησιμοποιείται συνήθως σε διαγωνισμούς προμηθειών του Δημοσίου για αποκλεισμό υπερβολικά χαμηλών ή υπερβολικά υψηλών προσφορών ως μέγιστη επιτρεπόμενη ποσοστιαία απόκλιση από το median όλων των προσφορών.


Λάμπρος Κατσάπας
Δημοσιεύσεις: 211
Εγγραφή: Σάβ Ιουν 17, 2017 10:17 pm
Τοποθεσία: Αθήνα

Re: ΕΛΑΧΙΣΤΟΠΟΙΗΣΗ

#3

Μη αναγνωσμένη δημοσίευση από Λάμπρος Κατσάπας » Παρ Ιούλ 13, 2018 7:02 pm

Altrian έγραψε:
Παρ Ιούλ 13, 2018 4:32 pm
Καλησπέρα,
Ζητάμε την ελαχιστοποίηση του αθροίσματος των n αποστάσεων του σημείου b από κάθε σημείο a_i. Αν τα σημεία είναι 2 (n=2) τότε το ελάχιστο άθροισμα δίνεται από κάθε σημείο b ανάμεσα στα a_1, a_2 ίσο με την απόσταση αυτών. Αν n=3 με έστω το τρίτο σημείο εντός του διαστήματος \left [ a_1, a_2 \right ] τότε έχουμε ελάχιστο για b=a_3. Αν n=4 με διάταξη έστω a_1, a_2, a_3, a_4 τότε το ελάχιστο προκύπτει για κάθε σημείο b εντός του εσωτερικού κεντρικού διαστήματος \left [ a_2, a_3 \right ]. Ουσιαστικά μιλάμε για το median των τιμών a_1, a_2,....,a_n που είναι το μεσαίο σε διάταξη σημείο αν n περιττός ή κάθε σημείο του μεσαίου σε διάταξη τμήματος αν n άρτιος.
Σημ. Ο median χρησιμοποιείται συνήθως σε διαγωνισμούς προμηθειών του Δημοσίου για αποκλεισμό υπερβολικά χαμηλών ή υπερβολικά υψηλών προσφορών ως μέγιστη επιτρεπόμενη ποσοστιαία απόκλιση από το median όλων των προσφορών.
:clap2: Γεια σου φίλε μου. Το πρόβλημα είναι γνωστό στη ΣΤΑΤΙΣΤΙΚΉ. Από εκεί το πήρα. Η διάμεσος βέβαια δεν

χρησιμοποιείται μόνο εκεί που αναφέρεις αλλά και αλλού. Μας έμεινε η απόδειξη.


Άβαταρ μέλους
cretanman
Διαχειριστής
Δημοσιεύσεις: 3832
Εγγραφή: Πέμ Δεκ 18, 2008 12:35 pm
Τοποθεσία: Ηράκλειο Κρήτης
Επικοινωνία:

Re: ΕΛΑΧΙΣΤΟΠΟΙΗΣΗ

#4

Μη αναγνωσμένη δημοσίευση από cretanman » Τετ Ιούλ 18, 2018 11:54 pm

Λάμπρος Κατσάπας έγραψε:
Τετ Ιούλ 11, 2018 8:41 pm
Θεωρούμε n διακεκριμένα σημεία A_i(a_i),i=1,2,...,n πάνω σε μια ευθεία. Να βρεθεί σημείο B(b) της ευθείας για το οπoίο πετυχαίνουμε το

\displaystyle{min \sum_{i=1}^{n} |a_i-b| }.
Λάμπρο καλησπέρα,

Για n=7 (και όμοια για οποιοδήποτε περιττό) η απόδειξη είναι εδώ https://www.mathematica.gr/forum/viewto ... 88#p126088
Ακριβώς η ίδια μέθοδος του Δημήτρη λειτουργεί και για n άρτιο με την απάντηση να επιβεβαιώνει τα λεγόμενα του Altrian παραπάνω.

Αλέξανδρος

Υ.Γ. Ήμουν μαθητής στην Α Λυκείου εκείνη τη χρονιά... :)


Αλέξανδρος Συγκελάκης
Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 10440
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: ΕΛΑΧΙΣΤΟΠΟΙΗΣΗ

#5

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Τετ Αύγ 01, 2018 8:31 am

cretanman έγραψε:
Τετ Ιούλ 18, 2018 11:54 pm
Υ.Γ. Ήμουν μαθητής στην Α Λυκείου εκείνη τη χρονιά... :)
.
Αλέξανδρε, για την ιστορία το θέμα αυτό (Θαλής, Α' Λυκείου 1996) το είχα τοποθετήσει o ίδιος ως μέλος της τότε Επιτροπής Διαγωνισμών της ΕΜΕ. Η κατασκευή του προήλθε από τα εξής:

Δίδασκα εκείνο το εξάμηνο ένα μάθημα στο Μαθηματικό Κρήτης με τίτλο Θεωρητική Αριθμητική Ανάλυση. Αφού συζητήσαμε την απόσταση σημείων ως προς διάφορες νόρμες του \mathbb R^n φτάσαμε και στο παραπάνω παράδειγμα, του οποίου η περίπτωση της νόρμας p=2 είναι γνωστή. Πρόκειται για την απόσταση ελάχιστων τετραγώνων (least squares distance). Αναρωτήθηκα λοιπόν τι γίνεται με την περίπτωση της νόρμας p=1, και χάρηκα όταν διαπίστωσα ότι έχει ωραία απάντηση. Από εκεί ορμώμενος το πρότεινα ως θέμα στον ΘΑΛΗ.

Η λύση που έδωσα για τον διαγωνισμό είναι αυτή του αναφέρεις. Στους φοιτητές όμως έδωσα και την εξής δεύτερη λύση.

Εξετάζουμε το γράφημα της \displaystyle y =  \sum_{i=1}^{n} |x-a_i|. Αφού  |x-a_i| = \pm (x-a_i) είναι άμεσο το γράφημα αποτελείται από ευθύγραμμα τμήματα με άκρα στα σημεία με x = a_i. Οι κλίσεις των ευθυγράμμων τμημάτων είναι \pm 1 \pm 1 … \pm 1, δηλαδή ακέραιοι, ακριβέστερα περιττοί αν τα σημεία είναι περιττό πλήθος, και άρτιοι αλλιώς. Τα σχήματα παρακάτω είναι δύο ενδεικτικές περιπτώσεις, με 5 και με 6 σημεία, αντίστοιχα.

Από το σχήμα διαβάζουμε το ελάχιστο. Στην περίπτωση περιττού πλήθους είναι στο μεσαίο σημείο, αλλιώς είναι σε ολόκληρο διάστημα.
Συνημμένα
elahisto me apolita.png
elahisto me apolita.png (7.79 KiB) Προβλήθηκε 220 φορές


Απάντηση

Επιστροφή σε “Γενικά”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης