0

使用 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 的一般问题？

4

2 回答 2

4

您正在尝试将以下形式的约束添加到线性程序：

(-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 <= 0B <= 0M

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足够大，这将捕获您的情况。

于 2016-04-29T19:11:30.557 回答
0

您的解决方案制定得很好，并且 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.
于 2016-05-02T16:47:57.070 回答