Lanike71 Δημοσ. 3 Μαΐου 2020 Δημοσ. 3 Μαΐου 2020 Παιδιά λίγο τη βοήθειά σας, Λύνω ένα πρόβλημα σε γραμμικό προγραμματισμό. Αυτό που θέλω να διορθώσω στα constraints, είναι να αναγκάσω τους συντελεστές των μεταβλητών να είναι είτε 0, είτε 1. Όχι, δεν είναι εργασία...😀
masteripper Δημοσ. 3 Μαΐου 2020 Δημοσ. 3 Μαΐου 2020 Αν θέλεις μόνο 0 και 1 τότε Boolean και False -- >0 True -- > -1 --> Abs(True) --> 1
Lanike71 Δημοσ. 3 Μαΐου 2020 Μέλος Δημοσ. 3 Μαΐου 2020 (επεξεργασμένο) 23 λεπτά πριν, masteripper είπε Αν θέλεις μόνο 0 και 1 τότε Boolean και False -- >0 True -- > -1 --> Abs(True) --> 1 Αν θέλεις γίνε λίγο πιο σαφής... Έστω έχω τις μεταβλητές x1,x2,x3 και θέλω να ελαχιστοποιήσω τη συνάρτηση x1+x2+x3>=2 Συνθήκες οι x1>=0, x2>=0, x3>=0. Μία λύση, αν και έχει πολλές, μπορεί να είναι οι συντελεστές 0,7, και 0,7 και 0,6. Εγώ θέλω να παίρνουν τιμές 0-1 οι συντελεστές, δηλαδή θα ήθελα τη λύση [0,1,1] ή [1,0,1] ή [1,1,0]. Σόρρυ αν μου ξεφεύγει κάτι. Επεξ/σία 3 Μαΐου 2020 από Lanike71
V.I.Smirnov Δημοσ. 3 Μαΐου 2020 Δημοσ. 3 Μαΐου 2020 Αν θυμαμαι καλά, αυτό που θέλεις είναι πρόβλημα ακέραιου προγραμματισμού (integer programming). Είναι ειδική περίπτωση του γραμμικού προγραμματισμού. Γενικά έχει πολύ θεωρία και είναι μπελάς... - 1
Lanike71 Δημοσ. 3 Μαΐου 2020 Μέλος Δημοσ. 3 Μαΐου 2020 1 λεπτό πριν, V.I.Smirnov είπε Αν θυμαμαι καλά, αυτό που θέλεις είναι πρόβλημα ακέραιου προγραμματισμού (integer programming). Είναι ειδική περίπτωση του γραμμικού προγραμματισμού. Γενικά έχει πολύ θεωρία και είναι μπελάς... - Ναι και λίγο που διάβασα, το πρόβλημα του να ορίσεις όλες τις περιπτώσεις, όλων των μεταβλητών, είναι NP hard. Αν δεν κάνω λάθος.
albNik Δημοσ. 3 Μαΐου 2020 Δημοσ. 3 Μαΐου 2020 Ναι, και η περίπτωση 0-1του integer programming παραμένει NP. Ψαξε μία 'Balas algorithm' http://user.engineering.uiowa.edu/~dbricker/Stacks_pdf8/Balas.pdf 1 1
Lanike71 Δημοσ. 3 Μαΐου 2020 Μέλος Δημοσ. 3 Μαΐου 2020 17 λεπτά πριν, albNik είπε Ναι, και η περίπτωση 0-1του integer programming παραμένει NP. Ψαξε μία 'Balas algorithm' http://user.engineering.uiowa.edu/~dbricker/Stacks_pdf8/Balas.pdf Πάνω που θα έγραφα @albNik "Help"... Οπότε με 200 μεταβλητές, θα πάω σε 2^200 ακόμα περιπτώσεις. Εντάξει, το λύσαμε κι αυτό. Και μερικοί λένε ότι οι greedy είναι μάπα...
masteripper Δημοσ. 3 Μαΐου 2020 Δημοσ. 3 Μαΐου 2020 Αυτό όπως το έγραψες δεν μου χτύπησε καμπανάκια για θεωρία.. γι'αυτό πήγα στα απλά. Επειδή δεν είναι εργασία σε ανάλογη περίπτωση η επίλυση γίνεται με γενετικούς αλγόριθμους ..ορίζεις το μήκος χρωμοσώματος, πληθυσμό,εποχές και ξεκινάς. Αν θες να δεις ακριβώς ποια είναι η θεωρία για την επίλυση μιας τέτοιας εξίσωσης θα πρέπει να δεις τα βιβλία της ενότητας ΠΛΗ 31 του ΕΑΠ
Lanike71 Δημοσ. 3 Μαΐου 2020 Μέλος Δημοσ. 3 Μαΐου 2020 1 ώρα πριν, masteripper είπε Αυτό όπως το έγραψες δεν μου χτύπησε καμπανάκια για θεωρία.. γι'αυτό πήγα στα απλά. Επειδή δεν είναι εργασία σε ανάλογη περίπτωση η επίλυση γίνεται με γενετικούς αλγόριθμους ..ορίζεις το μήκος χρωμοσώματος, πληθυσμό,εποχές και ξεκινάς. Αν θες να δεις ακριβώς ποια είναι η θεωρία για την επίλυση μιας τέτοιας εξίσωσης θα πρέπει να δεις τα βιβλία της ενότητας ΠΛΗ 31 του ΕΑΠ Σε ευχαριστώ, οι γενετικοί ήταν κάτι που δεν το σκέφτηκα. Θα το δοκιμάσω,για να δω πόσο κοντά στη βέλτιστη λύση φτάνει.
masteripper Δημοσ. 3 Μαΐου 2020 Δημοσ. 3 Μαΐου 2020 23 λεπτά πριν, Lanike71 είπε Σε ευχαριστώ, οι γενετικοί ήταν κάτι που δεν το σκέφτηκα. Θα το δοκιμάσω,για να δω πόσο κοντά στη βέλτιστη λύση φτάνει. Θεωρητικά προσεγγίζουν τέτοια προβλήματα σε σχεδόν καλύτερο δυνατό βαθμό.
velociraptoras Δημοσ. 6 Μαΐου 2020 Δημοσ. 6 Μαΐου 2020 Στις 3/5/2020 στις 4:11 ΜΜ, albNik είπε Ναι, και η περίπτωση 0-1του integer programming παραμένει NP. Ψαξε μία 'Balas algorithm' http://user.engineering.uiowa.edu/~dbricker/Stacks_pdf8/Balas.pdf ενα ευχαριστώ κι απο μένα μιας και το έψαχνα
Προτεινόμενες αναρτήσεις
Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε
Πρέπει να είστε μέλος για να αφήσετε σχόλιο
Δημιουργία λογαριασμού
Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι πανεύκολο!
Δημιουργία νέου λογαριασμούΣύνδεση
Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.
Συνδεθείτε τώρα