非負比率與約束線性編程lp_solve

Question

隨着lp_solve我需要限制的兩個線性函數的比例爲非負：

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; 

但是lp_solve不提供括號。有沒有可能解決它，所以我不需要括號，或者這是lp_solve的一個普遍問題？

Answer 1

您嘗試以下形式的約束添加到一個線性規劃：

(-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; 

爲了符號簡單起見，我將定義A = (-0.275 y0 + 0.15 y1 + 0.15 y2 + 0.236 y3 + 0.14745 y4)和B = (-0.175 y0 + 0.05 y1 + 0.05 y2 + 0.136 y3 + 0.04745 y4)。因此，您的約束是：

A/B >= 0 

這意味着下列兩個條件之一必須持有：

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

這引入非凸在你的公式中，因爲要點(A, B) = (4, 4)和(A, B) = (-2, -6)都是可行的，但他們的中點(A, B) = (1, -1)是不可行的。因爲你的可行集合是非凸的，所以實際上不可能用你所做的代碼中的所有連續變量使用線性程序來模擬你的情況。

您將需要在您的公式中引入二進制變量來模擬此非凸性。對此進行建模的一種自然方法是使得二進制變量z等於1，如果A >= 0和B >= 0並且使得z等於0如果A <= 0和B <= 0。然後，你可以介紹以下的限制（這裏M是一個大的正數）：

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

如果z=0，則約束給我們-M <= A <= 0和-M <= B <= 0，而如果z=1，則約束給我們0 <= A <= M和0 <= B <= M。如果選擇的值爲M足夠大，則會捕獲您的情況。

Answer 2

您的解決方案制定得很好，並且lpsolve解決得很好。但結果可能不是你所期望的。例如，我得到：z = 0和x187 = 0（A = B = 0）。 事情是，A和B是隻取決於x187的表達式，所以你應該簡化分割表達式！選擇的大M應該更小？

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. 

---

如果我們將A，B和Z的限制，我們得到了相同的結果：

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.