Trucos con Binarias y Linealización

Reformular un modelo para dejarlo lineal y correcto: condiciones lógicas con binarias, big-M y costos fijos, min-max y valor absoluto, producto binaria×continua (McCormick) y cómo auditar un modelo. Arquetipos I2-A y E-A.

Creado por

SebastianZ28

Valoración0 votos

-.-

psychology

Condiciones lógicas con binarias

Traducir reglas del enunciado a desigualdades

Con variables binarias $x_{i} \in {0, 1}$ (representan decisiones sí/no) se codifican reglas lógicas del enunciado como desigualdades lineales. Estos cuatro patrones cubren casi todo lo que piden en la I1.

Dependencia ("si $j$ , entonces $h$ ")

"No puedo elegir $j$ sin elegir también $h$ ". Si $x_{j} = 1$ obliga $x_{h} = 1$ :

x_{j} \leq x_{h}

Conflicto ("a lo más uno")

Dos opciones incompatibles, no pueden coexistir:

x_{i} + x_{c} \leq 1

Grupo ("todo o nada")

Dos decisiones van juntas: o ambas o ninguna:

x_{i} = x_{s}

Activación ("si hago algo, debo abrir")

Para usar cualquiera de las opciones $m \in M$ debo primero activar $x_{j}$ :

x_{m} \leq x_{j} \forall m \in M o de forma agregada m \in M \sum x_{m} \leq ∣ M ∣ x_{j}

Para chequear una restricción lógica, prueba los casos de las binarias: pon $x_{j} = 0$ y $x_{j} = 1$ y confirma que la desigualdad permite exactamente lo que dice el enunciado. Si algún caso permitido queda prohibido (o al revés), la restricción está mal.

Cómo verificar

Cargando Quiz...

tune

Big-M y costos fijos

Vincular una cantidad continua con un interruptor binario

El truco big-M conecta una variable continua $z \geq 0$ con una binaria $y$ : "solo puedo producir/enviar $z > 0$ si abrí la instalación ( $y = 1$ )". Con $M$ una cota superior de $z$ :

z \leq M y, y \in {0, 1}, z \geq 0

Si $y = 0 \Rightarrow z \leq 0 \Rightarrow z = 0$ (nada permitido). Si $y = 1 \Rightarrow z \leq M$ (la cota queda floja y $z$ es libre hasta $M$ ).

Costo fijo

El big-M permite cobrar un costo fijo $f$ por "abrir" (independiente de cuánto produzcas) más un costo variable $c$ por unidad. La binaria $y$ paga el fijo, la continua $z$ paga lo variable:

min i \sum (f_{i} y_{i} + c_{i} z_{i}) s.a. z_{i} \leq M_{i} y_{i} \forall i

M

debe ser una cota superior válida de

z

, lo más ajustada posible. Si

M

es demasiado grande la relajación lineal se debilita (B&B más lento); si es demasiado chico recortas soluciones factibles y el modelo queda incorrecto. Usa la capacidad real del enunciado como

M

Elegir M

Cargando Quiz...

functions

Min-max y valor absoluto

Convertir objetivos y restricciones no lineales en lineales

Minimizar un máximo (min-max)

min max_{i} (c_{i}^{⊤} x + f_{i})

no es lineal, pero se linealiza con una variable auxiliar

z

que "atrapa" el máximo: minimizas

z

y obligas a

z

a ser

\geq

que cada término.

min z s.a. c_{i}^{⊤} x + f_{i} \leq z \forall i

El caso simétrico $max min$ usa $z \leq$ cada término. Y una restricción $max {A, B} \leq K$ equivale simplemente a $A \leq K$ y $B \leq K$ .

Valor absoluto

Una restricción $∣ a^{⊤} x ∣ \leq b$ se desdobla en dos desigualdades lineales (el valor absoluto acota por ambos lados):

∣ a^{⊤} x ∣ \leq b ⟺ a^{⊤} x \leq b y - a^{⊤} x \leq b

max → min: negar, no solo renombrar

Pasar de maximizar a minimizar exige negar el objetivo completo: $max f (x) \equiv min (- f (x))$ . Las funciones estrictamente crecientes (como $exp$ , $ln$ ) se pueden quitar del objetivo sin cambiar el argmax: optimizar $exp (g (x))$ equivale a optimizar $g (x)$ .

"Pasar a mínimo" no es escribir 'mín' delante de la misma expresión: hay que negar el término que depende de $x$ . $max x$ con $0 \leq x \leq K$ da $x^{*} = K$ ; pero $min x$ da $x^{*} = 0$ (¡el punto opuesto!). Lo correcto es $min (- x)$ , que sí da $x^{*} = K$ .

Error común

Cargando Quiz...

calculate

Producto binaria × continua

Linealizar $w = y \cdot z$ (McCormick / big-M)

El producto de una binaria $y \in {0, 1}$ por una continua acotada $z \in [0, U]$ es no lineal (bilineal), pero se linealiza exactamente introduciendo una variable nueva $w = yz$ y cuatro desigualdades:

0 \leq w \leq U y, z - U (1 - y) \leq w \leq z

Verifica los casos: si $y = 0$ , las cotas fuerzan $w = 0$ ; si $y = 1$ , fuerzan $w = z$ . Luego sustituyes $w$ donde aparecía $yz$ (en la FO o en restricciones), sin tocar las cotas originales de $z$ .

Si el enunciado impone $K^{m i n} \leq z \leq K^{m a x}$ sin condicionarla a $y$ , es INCORRECTO reescribir esa cota como $K^{m i n} y \leq z \leq K^{m a x} y$ : eso fuerza $z = 0$ cuando $y = 0$ , lo cual reinterpreta el modelo, no lo linealiza. La forma fiel es introducir $w = yz$ con McCormick y dejar la cota de $z$ intacta.

Error común (detectado en Examen 2026-1)

Cargando Quiz...

warning

Auditar un modelo dado

El arquetipo "encuentra el error" (I2 y Examen)

Un arquetipo recurrente de la I2 y el examen te entrega un modelo (a veces "hecho por una IA") y pide detectar y corregir errores, o extenderlo con una nueva condición. Es puntaje casi regalado si tienes una checklist mental.

Checklist de auditoría

Índices: ¿cada restricción tiene el $\forall$ correcto? ¿los índices de la suma calzan con los de la variable?
FO: ¿es min o max según el enunciado? ¿están todos los costos (fijos y variables)?
Sentido de las desigualdades: ¿ $\leq$ vs $\geq$ ? (capacidad es $\leq$ , demanda suele ser $\geq$ ).
Coherencia de unidades: ¿sumas cantidades comparables? ¿mezclas dinero con unidades?
Dominio: ¿faltó $x \geq 0$ , integralidad o $x \in {0, 1}$ ?
Lógica big-M: ¿el $M$ es una cota válida? ¿la binaria activa correctamente la continua?

Cuando extiendas un modelo con una condición nueva, no reescribas todo: agrega solo la(s) restricción(es) que faltan y, si hace falta, una variable nueva. Deja claro qué agregaste. Corregir es más rápido que modelar de cero — por eso este arquetipo conviene priorizarlo.

Estrategia

Cargando Quiz...

Condiciones lógicas con binarias

Traducir reglas del enunciado a desigualdades

Dependencia ("si j, entonces h")

Conflicto ("a lo más uno")

Grupo ("todo o nada")

Activación ("si hago algo, debo abrir")

Big-M y costos fijos

Vincular una cantidad continua con un interruptor binario

Costo fijo

Min-max y valor absoluto

Convertir objetivos y restricciones no lineales en lineales

Minimizar un máximo (min-max)

Valor absoluto

max → min: negar, no solo renombrar

Producto binaria × continua

Linealizar w=y⋅z (McCormick / big-M)

Auditar un modelo dado

El arquetipo "encuentra el error" (I2 y Examen)

Checklist de auditoría

Dependencia ("si $j$ , entonces $h$ ")

Linealizar $w = y \cdot z$ (McCormick / big-M)