Restricción condicional en un programa lineal

Question

Estoy intentando escribir un programa lineal y no sé cómo formular una de las restricciones que necesito.

Necesito escribir una restricción que diga:

"Si $x_1 \le 2$ entonces $y\ge3$ ."

Supongo que tengo que utilizar un enfoque del método de la Gran M, pero no consigo averiguar nada más allá de eso.

ACTUALIZACIÓN

He hecho una tabla de verdad y he establecido las siguientes variables y restricciones:

Sea $z =0$ si $x\le 2$ y $z=1$ si $x\gt 2$

$x-2\le Mz$

$2-x\le M(1-z)$

$3-y \le Mz$

Si estoy haciendo mi tabla de verdad correctamente, de las 8 combinaciones posibles, debería permitir $x\le2, y\ge3, z=0$ y $x>2, y<3, z=1$ y $x>2, y\ge 3, z=1$ . Creo que mis limitaciones hacen esto. ¿Es una solución viable?

Answer 1

En primer lugar, observe que la región factible asociada a su restricción no es convexa. Por lo tanto, no es posible formular esta restricción utilizando únicamente la programación lineal.

Normalmente, este tipo de restricciones se formulan en programación entera mixta utilizando variables binarias 0-1 (el aspecto entero de la formulación) para activar y desactivar las restricciones. Utilizando este enfoque, es posible escribir restricciones para regiones factibles que pueden expresarse como uniones o intersecciones finitas de cerrado conjuntos convexos que pueden representarse mediante restricciones de desigualdad lineal (menor o igual que). Como has mencionado, es necesario incluir constantes "big-M" en las restricciones. La región factible resultante para el problema de programación lineal entera mixta (MILP) es siempre cerrada.

Su conjunto factible consiste en la unión del conjunto de puntos con $x_{1}>2$ y el conjunto de puntos con $x_{2} \geq 3$ . Desafortunadamente, debido a que el borde de la región factible donde $x_{1}=2$ y $x_{2} <3$ no está incluida en la región factible, tu región factible deseada no está cerrada, y por lo tanto no es posible formular el problema utilizando el enfoque que he mencionado.

Si está dispuesto a incluir este borde donde $x_{1}=2$ y $x_{2}<3$ en la región factible, entonces se puede lograr.

Comience añadiendo una variable 0-1 $z$ donde $z=0$ si $x_{1} \geq 2$ y $z=1$ es $x_{2} \geq 3$ . Escriba las restricciones como

$x_{1} + Mz \geq 2$

$x_{2} + M(1-z) \geq 3$

Aquí $M$ es una constante positiva grande. Dado que la primera restricción sería ineficaz si $x_{1}$ fue más negativo que $-(M-2)$ debe asegurarse de que $M$ es suficientemente grande. Sin embargo, es una buena idea mantener $M$ lo más pequeño posible para evitar problemas numéricos en la solución del problema.