 |
 |
 |
 |
 |
 |
Startseite » Forum » Spalten tauschen beim TwoPhase-Simplex-Algorithmus
Spalten tauschen beim TwoPhase-Simplex-Algorithmus
Universität / Fachhochschule
Tags: Simplex Algorithmus
 
|
  |
|---|
|
Ich wollte mittels folgender Implementierung des TwoPhase-Simplex-Algorithmus optimale Werte von Nahrungsmitteln unter Einhaltung von Bedingungen ermitteln: algs4.cs.princeton.edu/65reductions/TwoPhaseSimplex.java.html Meine Constraints sind wie folgt: 0.841*x1 + 0.09*x2 + 0.31*x3 + 0.21*x4 <= 65 0.011*x1 + 0.69*x2 + 0.17*x3 + 0.02*x4 <= 20 0.011*x1 + 0.52*x2 + 0.005*x3 + 0.006*x4 <= 45 x1 >= 1 x1 <= 100 x2 >= 60 x2 <= 120 x3 >= 0 x3 <= 100 x4 >= 0 x4 <= 150 0.863*x1 + 0.679*x2 + 0.485*x3 + 0.236*x4 >= 0 0.863*x1 + 0.679*x2 + 0.485*x3 + 0.236*x4 <= 130 Dann habe ich noch als Bedingung, dass die zu maximierende Zielfunktion nur Werte zwischen 0 und 130 annehmen kann, also die Summe aus den ersten 3 Constraints. Ob dieses Contraint dann unbedingt notwendig ist, weiß ich nicht, da ja die Beschränkung schon implizit durch die ersten 3 Constraints ist. Die ersten 3 Zeilen der Spalten 1, 2, 3 und 4 sind so, dass sie jeweils nur als Block vorkommen können und so theoretisch von ihrer Reihenfolge her getauscht sein könnten. Natürlich auch mit den getauschten Constraints für die x1 >= 1 <= 100 usw. Also 0.09*x1, 0.069*x1, 0.52*x1, x1 >= 1, x1 <= 100 tauchen so immer zusammen in einer Spalte auf, ob diese nun bei x1, x2, x3 oder x4 liegt, spielt erste einmal keine Rolle, daher können sie getauscht sein Die Zielfunktion ergibt sich aus der Summe der Koeffizienten von x1, x2, x3 und x4, also damit dann: Z = 0.863*x1 + 0.679*x2 + 0.485*x3 + 0.236*x4 --> Max Die Matrix A und die Vectoren b und c habe ich dann wie im ersten Beispiel gesetzt. Wenn ich A, b und c dann zur Lösung in den oben Solver eingebe (der übrigens von Robert Sedgewick zu sein scheint), oder ich einen Online-Solver eingebe, ist mir aufgefallen, dass ich beim Tausch von Spalten mal eine optimale Lösung existiert oder eben anscheinend das Problem nicht lösbar ist. Warum, das verstehe ich gerade ehrlich gesagt nicht? Woran liegt das bzw. mache ich was falsch? Eine wichtige Frage wäre, wie kann ich dem denn vorbeugen? Alle Permutationen zu berechnen und zu schauen, welche von denen die beste Lösung bietet, wäre bei theoretisch freier Anzahl an Spalten etwas zu viel 1) Es gibt keine Optimale Lösung: double[,] A = { { 0.841, 0.090, 0.310, 0.210 }, // Constraint 1 coefficients: Protein proportion for each food { 0.011, 0.690, 0.170, 0.020 }, // Constraint 2 coefficients: Fat proportion for each food { 0.011, 0.520, 0.005, 0.006 }, // Constraint 3 coefficients: Carb proportion for each food { -1, -0, -0, -0 }, // Constraint 4: x1 >= 1 { 1, 0, 0, 0 }, // Constraint 5: x1 <= 100 { -0, -1, -0, -0 }, // Constraint 6: x2 >= 60 { 0, 1, 0, 0 }, // Constraint 7: x2 <= 120 { -0, -0, -1, -0 }, // Constraint 8: x3 >= 0 { 0, 0, 1, 0 }, // Constraint 9: x3 <= 100 { -0, -0, -0, -1 }, // Constraint 10: x4 >= 0 { 0, 0, 0, 1 }, // Constraint 11: x4 <= 150 { -0.863, -0.679, -0.485, -0.236 }, // Constraint 12: Sum of Proteins, Fats and Carbohydrates for each food >= 0 { 0.863, 0.679, 0.485, 0.236 }, // Constraint 13: Sum of Proteins, Fats and Carbohydrates for each food <= 130 }; // RHS for each of the Constraints double[] b = { 65, 20, 45, -1, 100, -60, 120, 0, 100, 0, 150, 0, 130 }; // Restrictions for the lines of the Matrix: sum Proteins <= 65, sum Fats <= 20, sum Carbohydrates <= 45 // Food 1 should be >= 1 and <= 100 // Food 2 should be >= 0 and <=150 // Food 3 should be >= 1 and <= 100 // Food 4 should be >= 0 and <= 100 // Optimize Target-Function between >= 0 and <= 130 (130 Optimum as Sum from 65 + 20 + 45) // 130 = Sum(65 + 20 + 45) // Coefficients of Objective/Target Function: f(x1, .., x4) = 0.679*x1 + 0.236*x2 + 0.863*x3 + 0.485*x4 --> MAX double[] c = { 0.863, 0.679, 0485, 0.236 }; 2) Eine optimale Lösung konnte gefunden werden: double[,] A = { { 0.310, 0.090, 0.841, 0.210 }, // Constraint 1 coefficients: Protein proportion for each food { 0.170, 0.690, 0.011, 0.020 }, // Constraint 2 coefficients: Fat proportion for each food { 0.005, 0.520, 0.011, 0.006 }, // Constraint 3 coefficients: Carb proportion for each food { -1, -0, -0, -0 }, // Constraint 4: x1 >= 1 { 1, 0, 0, 0 }, // Constraint 5: x1 <= 100 { -0, -1, -0, -0 }, // Constraint 6: x2 >= 60 { 0, 1, 0, 0 }, // Constraint 7: x2 <= 120 { -0, -0, -1, -0 }, // Constraint 8: x3 >= 0 { 0, 0, 1, 0 }, // Constraint 9: x3 <= 100 { -0, -0, -0, -1 }, // Constraint 10: x4 >= 0 { 0, 0, 0, 1 }, // Constraint 11: x4 <= 150 { -0.485, -0.679, -0.863, -0.236 }, // Constraint 12: Sum of Proteins, Fats and Carbohydrates for each food >= 0 { 0.485, 0.679, 0.863, 0.236 }, // Constraint 13: Sum of Proteins, Fats and Carbohydrates for each food <= 130 }; // RHS for each of the Constraints double[] b = { 65, 20, 45, 0, 100, -60, 120, 1, 100, 0, 150, 0, 130 }; // Restrictions for the lines of the Matrix: sum Proteins <= 65, sum Fats <= 20, sum Carbohydrates <= 45 // Food 1 should be >= 0 and <= 100 // Food 2 should be >= 60 and <=120 // Food 3 should be >= 1 and <= 100 // Food 4 should be >= 0 and <= 150 // Optimize Target-Function between >= 0 and <= 130 (130 Optimum as Sum from 65 + 20 + 45) // 130 = Sum(65 + 20 + 45) // Coefficients of Objective/Target Function: f(x1, .., x4) = 0.679*x1 + 0.236*x2 + 0.863*x3 + 0.485*x4 --> MAX double[] c = { 0.485, 0.679, 0.863, 0.236 }; |
|
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1571862
1571862