[Συναρτήσεις] Άθροιση υπό όρους

[gr8styl]

Αρχική Δημοσίευση από mdragon

....
Κάθε μήνα γίνονται κάποιες εργασίες - ποσά (περίπου 100).
Θα πρέπει λοιπόν να επισυνάπτω πίσω από την πιστοποίηση - αρχικό ποσό
τις επιμέρους εργασίες και να συμφωνώ στο σύνολο μόνο με απόκλιση ολίγων λεπτών.
....

Συγνώμη αλλά δεν το καταλαβαίνω.
Δηλαδή το αρχικό ποσό δεν έχει σχέσει με τις εργασίες ?
Γίνονται εργασίες χωρίς να υπάρχουν χρήματα ?
πιστοποίηση = ???

Συγχωρέστε μου την άγνοια.

[mdragon]

Δυστυχώς Θανάση μου δεν μπορώ να στο εξηγήσω διαφορετικά για να το καταλάβεις.
Δεν έχω τον τρόπο.
Δέξου μόνο ότι έτσι έχουν τα δεδομένα 100 αριθμοί (περίπου) που με τον αντίστοιχο
συνδυασμό θα μας δίνουν σαν αποτέλεσμα το ποσό που θα ορίζω εγώ.





Φιλικά,
Μάρω

[kapetang]

Καλησπέρα στην παρέα

Όπως αναφέρθηκε (Θανάσης, Αλέξανδρος) ο αλγόριθμος για την επίλυση του προβλήματος της Μάρως απαιτεί τεράστιο αριθμό επαναλήψεων. Θεωρητικά 2^n , όπου n το πλήθος των κελιών που περιέχουν τους αριθμούς από τους οποίους θα σχηματιστεί το άθροισμα.
Χωρίς να ξέρω λεπτομέρειες, έχουν αναπτυχθεί αλγόριθμοι οι οποίοι περιορίζουν δραστικά το πλήθος των επαναλήψεων και δίνουν εφικτές λύσεις.
Το πρόβλημα προσομοιώνεται με την ακόλουθη εξίσωση: T1*X1+T2*X2+ …+ Tn*Xn=S των n μεταβλητών, όπου:

• Ti είναι τα κελιά που έχουν τις τιμές.
• Xi είναι μεταβλητές με τιμή 1, όταν επιλέγεται η τιμή του αντίστοιχου κελιού και 0 όταν δεν επιλέγεται.
• S Η τιμή προς την οποία θα συγκλίνει το άθροισμα.

Η παραπάνω εξίσωση είναι ακέραια γραμμική και μπορεί να λυθεί με τη μέθοδο Simlex.
Όπως διάβασα στο διαδίκτυο το πρόσθετο Solver (Επίλυση) του excel περιλαμβάνει τη μέθοδο Simlex και συνεπώς θα μπορούσε να χρησιμοποιηθεί για τη λύση του προβλήματος. Έτσι θα ξεπερνούσανε τον σκόπελο των συναρτήσεων και του κώδικα.
Αν και εγκατέστησα το πρόσθετο δε μπόρεσα να το εφαρμόσω, επειδή δε βρήκα στο διαδίκτυο λεπτομέρειες χρήσεις του στα ελληνικά. Με τα αγγλικά δεν έχω καλές σχέσεις.
Πιστεύω ότι η υπόλοιπη παρέα (Μάρω, Θανάσης, Αλέξανδρος, Τόλης ....) θα τα καταφέρει.Μια λύση «της πυρκαγιάς» είναι να εφαρμοστεί ο αλγόριθμος που δημιούργησα σε VBA για τη βέλτιστη κοπή ράβδων, με κάποια προσαρμογή και με κάποια δυσκολία για μένα που δεν είμαι εξοικειωμένος με τα αντικείμενα του excel.
Ο αλγόριθμος έχει περιορισμούς και προκειμένου να δω αν μπορεί να εφαρμοστεί, Μάρω θα σου βάλω δύσκολα.
Αν υποθέτουμε ότι οι τιμές στα 100 περίπου κελιά είναι ταξινομημένες κατά αύξουσα σειρά και έχουμε σχηματίσει και τα μερικά αθροίσματα, ποια είναι η τάξη του κελιού που για πρώτη φορά το μερικό άθροισμα υπερβαίνει τον αριθμό προς τον οποίο θα συγκλίνει το άθροισμα;
Αυτό εξαρτάται. Αν επιλέξουμε μεγάλο αριθμό και οι τιμές στα κελιά είναι μικρές μπορεί να γίνει πχ στο 90ο κελί, οπότε τη βάψαμε. Αν όμως ισχύει το αντίθετο μπορεί να γίνει πχ στο 7ο κελί, οπότε υπάρχει λύση.

Φιλικά/Γιώργος

[officeandi]

Αγαπητή Μάρω,

Νομίζω ότι κατάφερα να γράψω ένα πρόγραμμα που βρίσκει τα πιο κατάλληλα μερικά ποσά, όπως βλέπεις και στις φωτογραφίες που έχω ανεβάσει.

Από το Excel αρχείο που ανέβασες πήρα τις τιμές για να δοκιμάσω. Εδώ οι μεταβλητές είναι 8, οπότε τα αποτελέσματα τα έχεις σε χρόνο μηδέν.

Θα χρειαζόμουν όμως ένα παράδειγμα που να ανταποκρίνεται στην πραγματικότητα.

Όπως βλέπεις το πρόγραμμα δεν είναι γραμμένο σε Excel.
Εκτός από τις λύσεις που θα προσφέρει το πρόγραμμα, θα πρέπει να ληφθούν και ορισμένα άλλα πράγματα υπόψη.

• Επειδή δε ξέρω πόση ώρα θα δουλεύει το πρόγραμμα μέχρι να βρει τους πιο κατάλληλους συνδυασμούς, θα πρέπει τουλάχιστον ανά πάσα στιγμή να δείχνει που βρίσκεται και ο χρήστης να μπορεί να το διακόψει, (π.χ. έδωσε κάποια στοιχεία λάθος)
• Το PC θα πρέπει να μπορεί να κάνει συγχρόνως και άλλες δουλειές και το βασικότερο σε τακτά χρονικά διαστήματα να ενημερώνει το γραφικό περιβάλλον δίνοντας πληροφορίες που βρίσκεται και πόσο έχει ακόμη μπροστά του(π.χ. ProgressBar).

Σημειώνω για τα υπόλοιπα μέλη ότι τα παραπάνω είναι κάπως δύσκολο να υλοποιηθούν σε VBA, διότι στις πράξεις που γίνονται, αν δεν έχει ορισθεί διαφορετικά, τις αναλαμβάνει το UI-thread του Excel. Γι’ αυτό φαίνεται το Excel σα να έχει κολλήσει. Συνεπώς χρειάζεται κάτι σαν ένα BackgroundWorker.

Σε παρακαλώ, ανέβασε ένα από τα πραγματικά σου σενάρια όσο το δυνατό το γρηγορότερο για να κάνω κι εγώ μια σειρά από τεστ όσο το δυνατό το γρηγορότερο.

Φιλικά
Ανδρέας

[gr8styl]

Κατ αρχήν καλησπέρα/καλημέρα σε όλους.

Απλά θέλω να διευκρινίσω μερικά πράγματα
1) Από το 6ο ποστ του θέματος έχω ανεβάσει το from_cuts2sums.xls που λύνει το πρόβλημα με 12 αριθμούς και auto-calculation. Δείτε το εδώ
2) Η ΜΟΝΗ πλήρης και έγκυρη λύση για το πρόβλημα με 100 αριθμούς είναι η δημιουργία και ο έλεγχος των 2^100 συνδυασμών.
3) Η πρόταση του φίλου Γιώργου (kapetang) για χρήση της Επίλυσης (solver) δεν μας δίνει καμιά απολύτως εγγύηση όταν οι αριθμοί είναι περισσότεροι από 32

Για του λόγου το αληθές ενώ άφησα το PC μου να δουλεύει με Excel 2010 όλη νύχτα χθες με 100 τυχαίους αριθμούς (από 1,00 έως 9999,99) και ζητούμενο ένα τυχαίο άθροισμα μεταξύ 10.000,00 και 99.999,99 το πρωί βρήκα την λύση που θα δείτε στο συνημμένο η οποία είναι πλήρως αποδεκτή. Δείτε την συνημμένη εικόνα.

Όσες φορές όμως και αν ξαναπροσπάθησα να λύσω το πρόβλημα με "Επίλυση" δεν μου έδωσε καμιά αποδεκτή λύση.

Σε ξένα sites βρήκα διάφορα περί "επίλυσης", αλλά από ότι δείχνουν τα πειράματά μου και οι δοκιμές μου ( αλλά και τα σχόλια των χρηστών στα ξένα sites) όταν έχουμε πολλές μεταβλητές (στη περίπτωσή μας 100) ο περιορισμός δυαδικών τιμών (binary) δεν λαμβάνεται υπόψιν από το πρόσθετο της επίλυσης. Ο solver μπερδεύεται όπως λένε οι δημιουργοί του.

Τώρα η φίλη Μάρω από την άλλη δεν μας δίνει τα αναγκαία στοιχεία
"Δέξου μόνο ότι έτσι έχουν τα δεδομένα 100 αριθμοί (περίπου) που με τον αντίστοιχο συνδυασμό θα μας δίνουν σαν αποτέλεσμα το ποσό που θα ορίζω εγώ."
άρα μάλλον μιλάμε για να μιλάμε και να καταναλωνόμαστε.

Μάρω μου, και εγώ θέλω 10.000.000 euro αλλά που θα τα βρω δεν με απασχολεί. Εσύ θα πρέπει να μου απαντήσεις απλά δεχόμενη ότι θέλω 10 εκατομμύρια. Φαντάζομαι ότι δεν μπορείς να βοηθήσεις σε αυτή την περίπτωση. Νομίζω θα συμφωνήσεις μαζί μου !!!

Πιστεύω ότι σαφώς πρέπει να υπάρχει σχέση μεταξύ αριθμών και ζητούμενου αποτελέσματος αλλιώς δεν είναι δυνατόν να εγγυηθούμε κάποια λύση, και προσωπικά δεν διαθέτω τις γνώσεις για τον προσδιορισμό αυτής της σχέσης, αφού μάλλον αγνοώ τι σημαίνει "πιστοποίηση".

Αν σας έλεγα βρείτε τους πραγματικούς θετικούς αριθμούς που μας δίνουν σαν σύνολο άθροισμα 5 η απάντηση είναι ότι οι αριθμοί μπορεί να είναι άπειροι.
Αν σας έλεγα όμως να βρείτε του ακέραιους θετικούς αριθμούς τότε θα μπορούσατε να δώσετε μια ή περισσότερες απαντήσεις.
Αν σας έδινα κάποιους αριθμούς και σας ζητούσα να βρείτε αυτούς που μας δίνουν άθροισμα 5 θα μου απαντούσατε ότι ότι απλά δεν στέκει το ερώτημα και σαν λείπουν λεπτομέρειες, γιατί αν όλοι οι αριθμοί είναι μεγαλύτεροι του ζητούμενου αθροίσματος ΔΕΝ ΥΠΑΡΧΕΙ ΛΥΣΗ. Το αν υπάρχει λύση και ποια, εξαρτάται από τους συγκεκριμένους αριθμούς και το πλήθος τους.

Ελπίζω να είναι σαφές ότι η φίλη Μάρω πρέπει να βοηθήσει περισσότερο αν θέλει να βρεθεί κάποια λύση στο ζητούμενο, αλλιώς όποιος θέλει μπορεί να παλέψει το "έλεγχος όλων των 2^100 συνδυασμών" με κάποιο κώδικα.
Εναλλακτικά αν θέλετε παίξτε με το χωρισμό των 100 αριθμών σε δωδεκάδες (ποστ #6) και μοιράστε το τελικό ποσό σε ανάλογα τμήματα οπότε να υπολογίσετε 8-9 επιμέρους αθροίσματα.

Συγνώμη αν υπήρξα κουραστικός αλλά ήθελα να κάνω τις παραπάνω διευκρινήσεις.


Δείτε το συνημμένο xlsx (excel 2010) για το πως θα μπορούσε να γίνει χρήση του πρόσθετου Επίλυση (solver) που πρότεινε ο φίλος Γιώργος, και σε μια νύχτα έδωσε αποδεκτή λύση για τους συγκεκριμένους 100 τυχαίους αριθμούς και το συγκεκριμένο επιθυμητό αποτέλεσμα αθροίσματος !!!
Δεν θα το διακινδυνεύσω να πω ότι μέσω solver έχετε τη λύση.


Θανάσης.

[Tasos]

Καλημέρα σε όλους!
Δείτε το συνημμένο παράδειγμα παρακάτω για αρχή.

Θεωρητικά μπορεί να συνδυάζει 1000 νούμερα και νομίζω ότι είναι αρκετά γρήγορο.
Έχει ακόμα μεγάλα περιθώρια βελτίωσης αλλά κι έτσι που είναι λειτουργεί ικανοποιητικά.

Τα λέμε... καλό ξημέρωμα!

Τάσος

[gr8styl]

Αρχική Δημοσίευση από Tasos

Καλημέρα σε όλους!
Δείτε το συνημμένο παράδειγμα παρακάτω για αρχή.

Θεωρητικά μπορεί να συνδυάζει 1000 νούμερα και νομίζω ότι είναι αρκετά γρήγορο.
Έχει ακόμα μεγάλα περιθώρια βελτίωσης αλλά κι έτσι που είναι λειτουργεί ικανοποιητικά.

Τα λέμε... καλό ξημέρωμα!

Τάσος

Πολύ καλό !!!
ΜΠΡΑΒΟ Τάσο.

Θα πρότεινα να το ανεβάσεις στα χρήσιμα.

[kapetang]

Καλησπέρα στην παρέα

Φίλε Θανάση ευχαριστώ για τις πληροφορίες σχετικά με το Solver και τις δοκιμές, που έκανες. Πίστευα ότι είναι κομμένο και ραμμένο για το πρόβλημα της Μάρως. Φαίνεται όμως ότι ήμουν υπερβολικά αισιόδοξος.
Αγαπητέ Αλέξανδρε θα με ενδιέφερε να δω την προσέγγισή σου ( έτσω με εικονικά δεδομένα) και πιστεύω σ’ αυτό να συμφωνούν και οι υπόλοιποι.
Τάσο μου χτύπησες την κατάλληλη στιγμή. Είχα αρχίσει να προσαρμόζω, στο ζητούμενο, τη λύση για τη βέλτιστη κοπή, που έχει πολλούς περιορισμούς και ευτυχώς με πρόλαβες.
Ένα μεγάλο μπράβο και από μένα . Θα μελετήσω τον κώδικα και ίσως αντιληφθώ τον «σφαιράτο» αλγόριθμο, που χρησιμοποίησες. Διαφορετικά θα ζητήσω φροντιστήριο .
Αγαπητή Μάρω συνέχισε να βάζεις δύσκολα και να μας προβληματίζεις.

Γιώργος

[mdragon]

Αρχική Δημοσίευση από gr8styl

Τώρα η φίλη Μάρω από την άλλη δεν μας δίνει τα αναγκαία στοιχεία
"Δέξου μόνο ότι έτσι έχουν τα δεδομένα 100 αριθμοί (περίπου) που με τον αντίστοιχο συνδυασμό θα μας δίνουν σαν αποτέλεσμα το ποσό που θα ορίζω εγώ."
άρα μάλλον μιλάμε για να μιλάμε και να καταναλωνόμαστε.

Μάρω μου, και εγώ θέλω 10.000.000 euro αλλά που θα τα βρω δεν με απασχολεί. Εσύ θα πρέπει να μου απαντήσεις απλά δεχόμενη ότι θέλω 10 εκατομμύρια. Φαντάζομαι ότι δεν μπορείς να βοηθήσεις σε αυτή την περίπτωση. Νομίζω θα συμφωνήσεις μαζί μου !!!

Πιστεύω ότι σαφώς πρέπει να υπάρχει σχέση μεταξύ αριθμών και ζητούμενου αποτελέσματος αλλιώς δεν είναι δυνατόν να εγγυηθούμε κάποια λύση, και προσωπικά δεν διαθέτω τις γνώσεις για τον προσδιορισμό αυτής της σχέσης, αφού μάλλον αγνοώ τι σημαίνει "πιστοποίηση".

Θανάσης.

Φίλε Θανάση καλησπέρα,
νομίζω πως με παρεξήγησες ...... δεν κατάφερα να σε κάνω να με καταλάβεις για τον ίδιο λόγο που δεν θα καταλάβαινα τη δουλεία ενός γιατρού αφού είμαι μια απλή λογίστρια
Από την άλλη νομίζω πως το παράδειγμα σου ήταν ατυχές γιατί δεν χρησιμοποιώ την excel για να παίξω tetris ούτε να περάσω την ώρα μου. Ειναί κλειδί της δουλειάς μου και για το λόγο αυτό σου είπα απλά να δεχτείς ότι έτσι έχουν τα πράγματα.
Στην προσπάθεια να κατανοήσεις το πρόβλημά μου "κόλλησες" στη λέξη πιστοποίηση..... είναι αυτό που λέμε ...... βλέπεις το δέντρο και χάνεις το δάσος !!!!
Και για να μην σε αφήσω με την απορία πιστοποίηση είναι η ανάλυση της δουλειάς κάποιου μεταφραζόμενη σε ποσότητα επι τιμή (αναλυτικά). Στην ουσία εκεί πρέπει αναφέρεις λεπτομερώς τις εργασίες σου κοστολογόντας τις.
Όπως και να έχει σε ευχαριστώ για την προσπάθειά σου.
???


Σας ευχαριστώ ΟΛΟΥΣ πραγματικά για την ανταπόκρισή σας στο πρόβλημα μου και σας εύχομαι καλά Χρίστουγεννα με υγεία.
Ένα μεγάλο-μεγάλο ευχαριστώ στο Forum και έυχομαι να χιλιάσει τα μέλη του για να έχουμε περισσότερα προβλήματα να λύνουμε και συνεπώς περισσότερο ελεύθερο χρόνο για όλους μας.

Μάρω

[officeandi]

Καλησπέρα σε όλους,

Κι εγώ θα ήθελα να συγχαρώ τον Τάσο για τη λύση που δίνει, αφού οι περισσότεροι από εμάς δε φαντάζονταν να φτάνει κανείς τόσο γρήγορα στο αποτέλεσμα. Εγώ μάλιστα συνεχίζω να είμαι αυτής της άποψης.

Θα ήθελα όμως να το σχολιάσω και λίγο.

1) Από το 6ο ποστ του θέματος έχω ανεβάσει το from_cuts2sums.xls που λύνει το πρόβλημα με 12 αριθμούς και auto-calculation. Δείτε το εδώ
2) Η ΜΟΝΗ πλήρης και έγκυρη λύση για το πρόβλημα με 100 αριθμούς είναι η δημιουργία και ο έλεγχος των 2^100 συνδυασμών.
3) Η πρόταση του φίλου Γιώργου (kapetang) για χρήση της Επίλυσης (solver) δεν μας δίνει καμιά απολύτως εγγύηση όταν οι αριθμοί είναι περισσότεροι από 32

Καταρχήν, συμφωνώ απολύτως με το Θανάση και στα τρία σημεία που επισημαίνει.

Τάσο, αν κατάλαβα καλά, το πρόγραμμα με την εκκίνηση ακολουθεί βάση του recursion που έχει, μια δενδροειδή αναζήτηση, έτσι ώστε στην κατεύθυνση που ψάχνει, αν δεν καταλήξει εντός ορίων ανοχής, να κάνει το backtracking. Δηλαδή να αλλάξει κατεύθυνση, δίχως να χρειάζεται να διανύσει όλο το δρόμο προς τα πίσω. Αν κατά το ψάξιμο πετύχει ένα άθροισμα να είναι εντός ορίων ανοχής, τότε σταματά.

Αν στέκουν τα παραπάνω, τότε σίγουρα έχει βρει την πρώτη λύση. Αυτό δε σημαίνει ότι έχει βρει και την ιδανική.

Θα σου ήμουν ευγνώμων, αν μου(μας) εξηγούσες λίγο τη στρατηγική που ακολουθείς.

Στη συνέχεια (κάτι άσχετο με το πρόβλημα) παρατήρησα ότι χρησιμοποιείς το DoEvents, και θυμήθηκα τον πονοκέφαλο που μου έχει προξενήσει αυτή η εντολή. Με την εντολή αυτή καταφέρνει το παράθυρο του Excel (και συνεπώς το UI-thread) να επεξεργαστεί τυχόν μηνύματα που στέλνει το λειτουργικό (message-pump). Έτσι μπορεί το παράθυρο να αντιδρά σε εντολές του χρήστη. Αυτό όμως επιτρέπει στο χρήστη παράλληλα, να ξεκινήσει δεύτερη αναζήτηση, ενώ τρέχει η πρώτη!



Φιλικά
Ανδρέας