Nicht-negative Verhältnis Einschränkung mit linearer Programmierung in lp_solve

Question

Mit lp_solve Ich brauche das Verhältnis von zwei linearen Funktionen zu beschränken, um nicht negativ sein:

min: 13.21 y0 + 27.46 y1 + 35.66 y2 + 89.21 y3 + 60.69 y4; 

y0 + y1 + y2 + y3 + y4 >= 50000; 

y0 <= 69148; 
y1 <= 25460; 
y2 <= 34020; 
y3 <= 69873; 
y4 <= 737299; 

/* Spezification */ 
(-0.275 y0 + 0.15 y1 + 0.15 y2 + 0.236 y3 + 0.14745 y4)/(-0.175 y0 + 0.05 y1 + 0.05 y2 + 0.136 y3 + 0.04745 y4) >= 0; 

Aber lp_solve Klammer nicht bieten. Ist es möglich, es zu lösen, also brauche ich keine Klammern, oder ist das ein allgemeines Problem mit lp_solve?

Answer 1

Sie versuchen, eine Einschränkung der folgenden Form an ein lineares Programm hinzuzufügen:

(-0.275 y0 + 0.15 y1 + 0.15 y2 + 0.236 y3 + 0.14745 y4)/(-0.175 y0 + 0.05 y1 + 0.05 y2 + 0.136 y3 + 0.04745 y4) >= 0; 

Für Notations Einfachheit, ich A = (-0.275 y0 + 0.15 y1 + 0.15 y2 + 0.236 y3 + 0.14745 y4) und B = (-0.175 y0 + 0.05 y1 + 0.05 y2 + 0.136 y3 + 0.04745 y4) definieren werden. Ihre Einschränkung ist daher:

A/B >= 0 

Das bedeutet, eine der folgenden zwei Bedingungen erfüllt sind:

1. A >= 0 und B >= 0
2. A <= 0 und B <= 0

Dies stellt eine nicht-Konvexität in Ihrer Formulierung, weil Punkte (A, B) = (4, 4) und (A, B) = (-2, -6) sind beide machbar, aber ihr Mittelpunkt (A, B) = (1, -1) ist nicht machbar. Da Ihre machbare Menge nicht konvex ist, ist es tatsächlich unmöglich, Ihre Situation mit einem linearen Programm mit allen kontinuierlichen Variablen zu modellieren, wie Sie es in Ihrem Code versucht haben.

Sie müssen eine binäre Variable in Ihre Formulierung einführen, um diese Nichtkonvexität zu modellieren. Eine natürliche Möglichkeit, dies zu modellieren, wäre, die Binärvariable z gleich 1 zu machen, wenn A >= 0 und B >= 0 und z gleich 0 zu machen, wenn A <= 0 und B <= 0. Dann könnten Sie die folgenden Einschränkungen einführen (hier M ist eine große positive Konstante):

A <= Mz 
B <= Mz 
A >= M(z-1) 
B >= M(z-1) 
z binary 

Wenn z=0, dann die Einschränkungen geben uns -M <= A <= 0 und -M <= B <= 0, während, wenn z=1, dann sind die Zwänge geben uns 0 <= A <= M und 0 <= B <= M. Wenn der ausgewählte Wert M ausreichend groß ist, wird dies Ihre Situation erfassen.

Answer 2

Ihre Lösung ist gut formuliert und lpsolve gut gelöst. Aber die Ergebnisse sind möglicherweise nicht das, was Sie erwarten würden. Zum Beispiel habe ich: z = 0 und x187 = 0 (A = B = 0). Die Sache ist, dass A und B Ausdrücke sind, die nur von x187 abhängen, also sollten Sie diesen Teilungsausdruck vereinfachen! Das gewählte große M, sollte kleiner sein?

Model name: 'model build from GLP-Solve' - run #1  
Objective: Minimize(R0) 

SUBMITTED 
Model size:  12 constraints,  53 variables,   311 non-zeros. 
Sets:         0 GUB,     0 SOS. 

Using DUAL simplex for phase 1 and PRIMAL simplex for phase 2. 
The primal and dual simplex pricing strategy set to 'Devex'. 


Relaxed solution  276710632.306 after   23 iter is B&B base. 

Feasible solution  276710632.306 after   23 iter,   0 nodes (gap 0.0%) 

Optimal solution  276710632.306 after   23 iter,   0 nodes (gap 0.0%). 

Excellent numeric accuracy ||*|| = 0 

MEMO: lp_solve version 5.5.2.0 for 64 bit OS, with 64 bit REAL variables. 
     In the total iteration count 23, 17 (73.9%) were bound flips. 
     There were 0 refactorizations, 0 triggered by time and 0 by density. 
     ... on average 6.0 major pivots per refactorization. 
     The largest [LUSOL v2.2.1.0] fact(B) had 13 NZ entries, 1.0x largest basis. 
     The maximum B&B level was 1, 0.5x MIP order, 1 at the optimal solution. 
     The constraint matrix inf-norm is 1e+06, with a dynamic range of 6.39386e+08. 
     Time to load data was 0.001 seconds, presolve used 0.000 seconds, 
     ... 0.000 seconds in simplex solver, in total 0.001 seconds. 

---

Wenn wir die A, B und z Einschränkungen entfernen wir die gleichen Ergebnisse erhalten:

Model name: 'model build from GLP-Solve' - run #1  
Objective: Minimize(R0) 

SUBMITTED 
Model size:  6 constraints,  50 variables,   299 non-zeros. 
Sets:         0 GUB,     0 SOS. 

Using DUAL simplex for phase 1 and PRIMAL simplex for phase 2. 
The primal and dual simplex pricing strategy set to 'Devex'. 


Optimal solution  276710632.306 after   22 iter. 

Excellent numeric accuracy ||*|| = 0 

MEMO: lp_solve version 5.5.2.0 for 64 bit OS, with 64 bit REAL variables. 
     In the total iteration count 22, 17 (77.3%) were bound flips. 
     There were 0 refactorizations, 0 triggered by time and 0 by density. 
     ... on average 5.0 major pivots per refactorization. 
     The largest [LUSOL v2.2.1.0] fact(B) had 7 NZ entries, 1.0x largest basis. 
     The constraint matrix inf-norm is 1, with a dynamic range of 639.386. 
     Time to load data was 0.002 seconds, presolve used 0.001 seconds, 
     ... 0.001 seconds in simplex solver, in total 0.004 seconds.