Lineare Programmierung - Absolutwert größer als eine Konstante

Question

Wie würden Sie die Abhängigkeit | x | konvertieren? > = 2, so dass es in einem linearen Programm funktionieren würde (insbesondere beim Lösen mit Simplex).

Ich verstehe, wie Sie | x | konvertieren < = 2 wie das würde werden x < = 2 und -x < = 2

Die gleiche Logik funktioniert jedoch nicht, wenn Sie eine Mindestkonstante haben.

Answer 1

Es gibt einfach keine Möglichkeit, eine Gleichung wie |x|>=2 zu einer reinen (kontinuierlichen) LP zu schärfen. Sie müssen x <= -2 OR x >= 2 formulieren, die nicht konvex ist. Dies erfordert eine binäre Variable, die das Problem zu einem MIP macht.

Eine Formulierung können sein:

x >= 2 - delta*M 
x <= -2 + (1-delta)*M 
delta in {0,1} 

wo M umsichtig große Zahl gewählt wird. Z.B. Wenn -100<=x<=100 dann können Sie M=102 wählen.