Επιστροφή στο Forum : EXCEL πρόβλημα
kostas_1966
29-12-11, 17:57
Οι εφαρμογές του παρακάτω προβλήματος είναι πολλές,ενδεικτικά αναφέρω μερικές:
Δίκαιη κατανομή μεριδίων ή αξιών,
Εξομάλυνση αποδόσεων σε πλειστηριασμούς,επενδύσεις
Αξιοποίηση χωρητικότητας ενός μέσου κατά την εγγραφή αρχείων(πχ επιλογή αρχείων για ισόνομη κατανομή τους σε DVD) και πολλές άλλες.
Το πρόβλημα
Έστω ότι έχουμε ένα πλήθος αριθμών π.χ
400 960 620 620 395 390 680 3600 1550 1450 570 580
τους οποίους θέλουμε να τους ομαδοποιήσουμε σε 2 ή περισσότερες ομάδες με κριτήριο τον μέσο όρο τους.
Με άλλα λόγια θέλουμε οι ομάδες να είναι όσο το δυνατόν εξισορροπημένες από την άποψη να δίνουν παραπλήσια αθροίσματα.
Φυσικά δεν θα βάλουμε τους μεγαλύτερους αριθμούς στην ίδια ομάδα.
Αν μπορούσα να βρω την μέθοδο που πρέπει να ακολουθηθεί με ένα στοιχειώδες λογικό διάγραμμα ροής (με χαρτί και μολύβι) ίσως να μπορούσα να κατασκευάσω μόνος μου την φόρμουλα στο excel.
Κάθε βοήθεια,είτε έχει να κάνει με μαθηματικούς τύπους είτε με εξειδικευμένες εντολές excel,είναι ευπρόσδεκτη.
Πολύ γρήγορη σκέψη:
Κρατάς τα αθροίσματα της κάθε στήλης. Προσθέτεις τον επόμενο αριθμό στη στήλη με το μικρότερο άθροισμα.
Θεωρητικά σε μεγάλο πλήθος στοιχείων δεν θα έχεις πρόβλημα με το πλήθος αριθμών κάθε στήλης. Εκτός αν θέλεις απαραίτητα να είναι ίσο το πλήθος κάθε στήλης οπότε το παραπάνω... άκυρο.
παραθέτω στο συνημμένο excel έναν τρόπο για ομαδοποίηση σε ομάδες των δύο στοιχείων. Αν είναι για 3, θα πρέπει να αλλαξει ελαφρώς ο πίνακας στα δεξιά.
παραθέτω στο συνημμένο excel έναν τρόπο για ομαδοποίηση σε ομάδες των δύο στοιχείων. Αν είναι για 3, θα πρέπει να αλλαξει ελαφρώς ο πίνακας στα δεξιά.Η πρώτη στήλη (Η) έχει ΜΟ 749 και η 2η 305. Οι γραμμές (Η+J) έχουν σταθερά αθροίσματα αλλά νομίζω ο OP το ζητάει για τις στήλες.
Έξυπνη υλοποίηση πάντως ;)
εγώ καταλαβα οτι θελει τα στοιχεια της στήλης Α να τα μοιράσει σε ομάδες των δύο στοιχείων (στοιχείο πρωτο στην στηλη Η και στοιχειο δευτερο της κάθε ομάδας στη στήλη Ι) ώστε ο μεσος όρος καθε ομαδας (στήλη J) να είναι κατα το δυνατόν ίσοι.
Πολύ ενδιαφέρον πρόβλημα.
Για να το μαθηματικοποιήσουμε ας δούμε τα εξής:
Έστω S το πλήθος όλων των αριθμών (12 στο παράδειγμά μας)
Έστω m οι ομάδες που ζητάμε (π.χ. ζητάμε 4 ομάδες στο παράδειγμα)
Έστω n = S / m το πλήθος των αριθμών σε κάθε ομάδα (άρα από 3 αριθμούς σε κάθε ομάδα).
Αν κάνουμε όλες τις μεταθέσεις των αριθμών (S!) και για κάθε μετάθεση χωρίζουμε τους αριθμούς διατεταγμένα σε m ομάδες των n αριθμών, αυτό που θέλουμε είναι το minimum του stdev του αθροίσματος κάθε ομάδας, για όλες τις μεταθέσεις των αριθμών.
Αυτό φυσικά, αν θεωρήσουμε ότι ζητάμε σταθερό πλήθος των αριθμών σε κάθε ομάδα.
Βέβαια, η παραπάνω προσέγγιση είναι brute force με την έννοια ότι δοκιμάζουμε όλες τις μεταθέσεις. Θα πρέπει να βρούμε έναν έξυπνο τρόπο που αποκλείει κάποιες μεταθέσεις, γιατί στο παράδειγμά μας για 12 αριθμούς, οι μεταθέσεις είναι 12! = 479.001.600 που θα κάνει δύσκολο τον υπολογισμό.
Και βεβαίως θέλει προγραμματισμό, και όχι Excel functions.
........Auto merged post: MichaelSE πρόσθεσε 7 λεπτά και 49 δευτερόλεπτα αργότερα ........
Update:
Μπορούμε να μειώσουμε τον αριθμό των δοκιμών, αν αντί να πάρουμε όλες τις μεταθέσεις, πάρουμε όλους τους συνδυασμούς ως εξής:
(s ανά n) * ((s-n) ανά n) * ... * (n ανά n)
όπου βέβαια από κάθε ομάδα - παράγοντα του πολλαπλασιασμού θα αφαιρούνται οι αριθμοί που μπήκαν σε ομάδες μέχρι και τον προηγούμενο παράγοντα.
άρα στο παράδειγμά μας θα είναι:
(12 ανά 3) * (9 ανά 3) * (6 ανά 3) * (3 ανά 3) = 369.600 που είναι ένας διαχειρίσιμος αριθμός
kostas_1966
03-01-12, 18:41
Καλή χρονιά παιδιά (Κύριοι, αν το επιθυμείτε) με υγεία.
Σας ευχαριστώ για τις απαντήσεις σας, όλες έχουν λόγο ύπαρξης διότι δείχνουν κατευθύνσεις.
yiapap("Πολύ γρήγορη σκέψη:
Κρατάς τα αθροίσματα της κάθε στήλης. Προσθέτεις τον επόμενο αριθμό στη στήλη με το μικρότερο άθροισμα"). αυτό είναι το ζητούμενο μα ψάχνω τον μηχανισμό. Μη σε ξεγελούν οι 12 αριθμοί του παραδείγματος που εύκολα μαντρώνονται,σκέψου ότι έχουμε πολλούς παραπάνω και κάθε φορά διαφορετικούς. Αν,ας πούμε, είχες 100 αρχεία για back up συνόλου 42 gb, θα μπορούσες να τα περάσεις σε 10 dvd; Άνευ μεθοδολογίας ούτε σε 12,πίστεψέ με.
gavrinos έχω ανοιχτό το book1.xls που φαίνεται οn the road. Ωστόσο, να διευκρινίσω πως, ως κριτήριο για την σύσταση ομάδας δεν λαμβάνουμε το πλήθος των στοιχείων αλλά μια συγκεκριμένη σταθερά που την δίνουμε ως input. Φαντάσου πχ έναν πατέρα που έχει-στο παράδειγμα που ανέφερα- 12 τίτλους μετοχών με διαφορετικές αποτιμήσεις (η αξία τους είναι οι 12 αριθμοί) και θέλει να τους μοιράσει στα 2 παιδιά του χωρίς να τα αδικήσει.( Έστω ας δεχθούμε ότι θα υπάρξει μια πολύ μικρή απόκλιση την οποία ο πατέρας θα καλύψει με μετρητά). Η ελπίδα που μου γεννήθηκε βλέποντας ότι το κελί Ε4 δέχεται να φτιάξει ομάδες από το input στο Ε1 κατέληξε σε πλάνη αφού τελικά δεν λειτούργησε. Πήρα όμως μια ιδέα και ίσως να προσπαθήσω να το προχωρήσω από εκεί που δε δούλεψε.
MichaelSE υπέροχη και κατανοητή η μαθηματική σου προσέγγιση. Εδώ αισθάνομαι ότι φταίω γιατί μάλλον δεν έγινα όσο σαφής θα ήθελα:
S & m σύμφωνοι, ως σταθερές που πρέπει να καταχωρούμε για την κάθε περίπτωση.
n=s/m δεν είναι απαραίτητο. Φτιάχνεται ομάδα λιγότερων μελών εάν αυτά τα μέλη είναι μεγαλύτερα σε αξία. Στις παραπάνω εφαρμογές που έφερα ως παραδείγματα, ο yiapap πχ θα χαραμίσει ένα dvd για να γράψει μόνο ένα αρχείο αν αυτό το αρχείο αξιοποιεί τη χωρητικότητα του μέσου, είναι ας πούμε κοντά στα 4,3 gb. Δεν μπορεί να κάνει αλλιώς ούτε ο πατέρας που θα δώσει έναν "ογκόλιθο" τίτλο μετοχής αν ισοδυναμεί πχ με το άθροισμα των υπολοίπων. Ίση κατανομή είναι το ζητούμενο και όχι ισοπληθείς ομάδες.
Το S! με "αρρωσταίνει" και μόνο που το αντικρύζω, σκέτη καταστροφή. Άλλωστε γιατί πρέπει να μας νοιάζουν οι εσωτερικές μετακινήσεις των μελών(αριθμών) εντός της ομάδας τους; Δεν αλλάζει κάτι με τα πέρα δώθε εντός του ίδιου πλαισίου.
Το STDEV το βλέπω ως καρύκευμα. Είναι απλή ενημέρωση για τις αποκλίσεις που συνεκτιμά την "πειθαρχία" των αριθμών και πόσο τιθασεύσιμοι είναι όσον αφορά την εισαγωγή τους σε ομάδες.
Στο update σου θα συμφωνήσω αν και το 369.600 δεν θα τον έλεγα διαχειρίσιμο αριθμό, άρα χρειάζονται κριτήρια για περαιτέρω περιορισμό.
Τέλος το excel είναι ένα πολύ δυνατό εργαλείο,παραπάνω από αποτελεσματικό στα χέρια του γνώστη.
Ειδικά στις τελευταίες του εκδόσεις το θεωρώ ασυναγώνιστο αν όχι πανάκεια δια πάσαν μαθηματικήν "νόσον".
Ως τεκμήριο της αποτελεσμνατικότητάς του καθώς και για τον εμπλουτισμό αυτής της ανταλλαγής γνώσεων και προσεγγίσεων, μεταφέρω και μια άλλη ιδέα που μου έδωσε κάποιος φίλος. Έχει να κάνει με ένα πρόσθετο του excel το οποίο εμπεριέχεται στη φαρέτρα του από την έκδοση 2003. Ονομάζεται solver και στο λίγο που ασχολήθηκα μαζί του φαίνεται πανίσχυρο.
Το ότι δεν μου έλυσε το πρόβλημα φταίει που στόχευσε σε...λάθος στήλη όπως μπορείτε να δείτε:
1) Όλους τους αριθμούς τον έναν κάτω από τον άλλο στην στήλη Α
2) Πεδίο D1: sum της Α / 2 για να βρείς το άθροισμα-στόχο κάθε ομάδας
3) Στήλη B κενή
4) Πεδίο C1: Α1*Β1 και σέρνεις προς τα κάτω μέχρι να γεμίσεις όλα τα πεδία που αριστερά στην A υπάρχει αριθμός
5) Πεδίο D2: sum της C
6) Data --> Solver
Set objective: D2
To value of: Την τιμή του πεδίου D1
By changing variable cells: Τα πεδία της B που αριστερά τους υπάρχει τιμή στην Α
Subject to constraints: Add για να προσθέσεις περιορισμό τα πεδία της B να είναι binary
Options-->Constraint precision: 0,001 (μετακινείς την υποδιαστολή δεξιά αν δεν βρίσκει λύσεις και αριστερά για μεγαλύτερη ακρίβεια)
Πατάς solve. Ότι βγει με 1 θα πάει στην μία ομάδα, ότι βγει με 0 στην άλλη.
Εννοείται ότι αν δεν θέλεις να είναι ισοπληθείς οι ομάδες, η μέθοδος που σκέφτηκα δεν ισχύει. Δεν ήταν δικό σου λάθος, μάλλον δικό μου που δεν το κατάλαβα από την αρχή, αφού έδωσες και το παράδειγμα του DVD που προφανώς εκεί δεν σε ενδιαφέρει το πλήθος των αρχείων αλλά μόνο το μέγεθος.
Το Excel είναι όντως πανίσχυρο εργαλείο και κάτι παραπάνω. Όταν έγραφα προγραμματισμό και όχι Excel functions εννοούσα VBA μέσα στο Excel (Γι' αυτό έγραψα Excel functions και όχι απλά Excel).
Απλά θα διαφωνήσω στο "μαθηματική" που είπες και εγώ θα προτιμούσα το "αριθμητική". Γιατί τα μαθηματικά είναι περισσότερο συμβολικά και θεωρητικά και πολύ λίγο (μόνο στις εφαρμογές τους) έχουν να κάνουν στην πραγματικότητα με αριθμούς. Εκεί το Excel δεν βοηθάει και υπάρχουν εξειδικευμένα πακέτα (Mathematica, Matlab κτλ).
Για τους αριθμητικούς υπολογισμούς όμως είναι απλά κορυφαίο. Είτε είναι στατιστική, είτε αριθμητική ανάλυση είτε οτιδήποτε άλλο. Εγώ προσωπικά δεν έχω δει τίποτα που δεν μπορεί να γίνει. Το πολύ πολύ να χρειάζεται και λίγη VBA.
...
Το ότι δεν μου έλυσε το πρόβλημα φταίει που στόχευσε σε...λάθος στήλη όπως μπορείτε να δείτε:
...
Καλησπέρα!
Ελπίζω να έχεις λύσει το πρόβλημα σου από τότε, αλλά η συγκεκριμένη μέθοδος που σου έδωσα δε στόχευε σε καθόλου λάθος στήλη... Αν ακολουθήσεις τις οδηγίες προσεκτικά, θα σου βγει. :oneup:
Το πρόβλημα που έχει τεθεί είναι παραπλήσιο με το
http://en.wikipedia.org/wiki/Knapsack_problem
στη 0-1 εκδοχή του, με όλα τα items να έχουν value ίδιο με το weight τους. Απαιτεί pseudo polynomial χρόνο.
Ένας online solver είναι εδώ:
http://www.cs.ucsb.edu/~jacopo/BB/index.html.en
Το απλό knapsack πρόβλημα είναι να γεμίσεις ένα "dvd" με την επιλογή αρχείων που αφήνουν τον ελάχιστο δυνατό κενό χώρο. Αν θέλουμε πολλά επαναλαμβάνουμε εκ νέου τη διαδικασία με τα υπόλοιπα αρχεία.
Δείτε και το
http://en.wikipedia.org/wiki/Partition_problem
@ ADSLgr.com All rights reserved.