Προς το περιεχόμενο

Προτεινόμενες αναρτήσεις

Δημοσ.

Παιδιά λίγο τη βοήθειά σας,

Λύνω ένα πρόβλημα σε γραμμικό προγραμματισμό. Αυτό που θέλω να διορθώσω στα constraints, είναι να αναγκάσω τους συντελεστές των μεταβλητών να είναι είτε 0, είτε 1.

Όχι, δεν είναι εργασία...😀

Δημοσ. (επεξεργασμένο)
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]. Σόρρυ αν μου ξεφεύγει κάτι.

Επεξ/σία από Lanike71
Δημοσ.

Αν θυμαμαι καλά, αυτό που θέλεις είναι πρόβλημα ακέραιου προγραμματισμού (integer programming).
Είναι ειδική περίπτωση του γραμμικού προγραμματισμού. Γενικά έχει πολύ θεωρία και είναι μπελάς...

-

  • Like 1
Δημοσ.
1 λεπτό πριν, V.I.Smirnov είπε

Αν θυμαμαι καλά, αυτό που θέλεις είναι πρόβλημα ακέραιου προγραμματισμού (integer programming).
Είναι ειδική περίπτωση του γραμμικού προγραμματισμού. Γενικά έχει πολύ θεωρία και είναι μπελάς...

-

Ναι και λίγο που διάβασα, το πρόβλημα του να ορίσεις όλες τις περιπτώσεις, όλων των μεταβλητών, είναι NP hard.

Αν δεν κάνω λάθος.

Δημοσ.
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 είναι μάπα...

Δημοσ.

Αυτό όπως το έγραψες δεν μου χτύπησε καμπανάκια για θεωρία.. γι'αυτό πήγα στα απλά.

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

Αν θες να δεις ακριβώς ποια είναι η θεωρία για την επίλυση μιας τέτοιας εξίσωσης θα πρέπει να δεις τα βιβλία της ενότητας ΠΛΗ 31 του ΕΑΠ

Δημοσ.
1 ώρα πριν, masteripper είπε

Αυτό όπως το έγραψες δεν μου χτύπησε καμπανάκια για θεωρία.. γι'αυτό πήγα στα απλά.

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

Αν θες να δεις ακριβώς ποια είναι η θεωρία για την επίλυση μιας τέτοιας εξίσωσης θα πρέπει να δεις τα βιβλία της ενότητας ΠΛΗ 31 του ΕΑΠ

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

Δημοσ.
23 λεπτά πριν, Lanike71 είπε

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

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

Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε

Πρέπει να είστε μέλος για να αφήσετε σχόλιο

Δημιουργία λογαριασμού

Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι πανεύκολο!

Δημιουργία νέου λογαριασμού

Σύνδεση

Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.

Συνδεθείτε τώρα
  • Δημιουργία νέου...