Неотрицательное отношение ограничение с линейным программированием в 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, поэтому вы должны упростить это деление! Выбранный большой М должен быть меньше?

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. 

---

Если мы удалим А, В и ограничении 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.