Modelación Linear Discreta

Parte dos de la guia para estudiar la materia del curso ICS1113 Optimización (curso de la Pontificia Universidad Católica de Chile). Faltan algunos.

Técnica 1: Formular restricciones usando lógica proposicional y luego traducir.

  • $i \rightarrow j$ lo reescribimos como $i \leq j$.
  • $\neg i$ lo reescribimos como $1 - i$.
  • un $\lor$ a la izquierda divide en dos condiciones: $i \lor j \rightarrow k$ se reescribe como $i \leq k$ y $j \leq k$.
  • un $\land$ a la izquierda: $i \land j \rightarrow k$ se reescribe como $i + j \leq k + 1$

Técnica 2: Para restricciones condicionadas.

$ax \leq b $ cuando $y$ se escribe: $ax \leq b + m(1-y)$. Donde m es un valor muy grande, así tenemos que cuando $y=0$ la restricción funciona como si fuera un $ax \leq b + \infty = \infty$ que siempre se cumple.

$ax \geq b $ cuando $y$ se escribe: $ax \geq b - m(1-y)$.

Ejemplo para $y \in \{0, 1\}$:

Queda:

Técnica 3: Para funciones por partes.

si queremos modelar

Defino variables:

Las restricciones son:

Problema de seleccionar: Knapsack

Llevar el producto $i$ me aporta $p_i$ dolares y me cuesta $w_i$. Tengo un total de $W$ dolares. Maxmimizar el precio de los productos que llevo.

Defino

s.a.


Problema con costos fijos: Producción e inventario con costos fijos 1

El mismo problema de producción e inventario (ver publicación pasada), pero si uso maquina en $t$ tengo un costo adicional $k^t$ (o sea, si produzco algo, tengo costo fijo).

Primero, como es un problema de producción e inventario defino $x_i^t$ como la cantidad de $i$ que produzco en $t$, y $y_i^t$ como hay almacenado de $i$ en $t$.

Defino

s.a.

Obtenemos esta restricción usando la técnica 2. Vemos que sólo si se prende la maquina ($w^t = 1$) podemos producir.


Problema con costos fijos y continuidad: Producción e inventario con costos fijos 2

Imaginemos ahora que en el problema anterior no hay costo fijo si la maquina estuvo prendida en $t-1$ (ej. no es necesario prenderla).

Defino

Son las mismas restricciones que las de arriba, sólo agrego:


Problemas de subdivision/asignación: Coloring

2 nodos en un grafo no pueden tener el mismo color si están conectados ($C_i$ son los nodos conectados con $i$). Minimice la cantidad de colores usados.

Defino

Defino

s.a.

Todos los nodos con un color:

Si uso un color se activa $y_k$:

$x_{i,k} \rightarrow \neg x_{j, k}$ para nodos conectados:

Written on April 21, 2019