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.
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\}$:
\[\begin{cases} ax_i \leq b \qquad \text{cuando } y = 1\\ ax_i \geq b \qquad \text{eoc.} \end{cases}\]Queda:
\[ax_i \leq b + m(1-y)\] \[ax_i \geq b - m(y)\]Técnica 3: Para funciones por partes.
si queremos modelar \(y = \begin{cases} ax + b \qquad \text{cuando } x \leq k\\ cx + d \qquad \text{eoc.} \end{cases}\)
Defino variables:
\[x_1 = \begin{cases} x \qquad \text{cuando } x \leq k\\ 0 \qquad \text{eoc.} \end{cases}\] \[x_2 = \begin{cases} x \qquad \text{cuando } x \geq k + 1\\ 0 \qquad \text{eoc.} \end{cases}\] \[w_1 = \begin{cases} 1 \qquad \text{cuando } x \leq k\\ 0 \qquad \text{eoc.} \end{cases}\] \[w_2 = \begin{cases} 1 \qquad \text{cuando } x \geq k + 1\\ 0 \qquad \text{eoc.} \end{cases}\]Las restricciones son:
\[y = (ax_1 + bw_1) + (cx_2 + dw_2)\] \[x_1 \leq k w_1\] \[x_2 \geq (k + 1) w_2\] \[x = x_1 + x_2\] \[1 = w_1 + w_2\]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 \(x_i = \begin{cases} 1 \qquad \text{cuando llevo producto } i\\ 0 \qquad \text{eoc.} \end{cases}\)
\[\max \sum_i x_i p_i\]s.a.
\[\sum_i x_i w_i \leq W\]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 \(w^t = \begin{cases} 1 \qquad \text{usé la maquina en } t\\ 0 \qquad \text{eoc.} \end{cases}\)
\[\min \sum_i\sum_t x_i^tc_i^t + y_i^th_i^t + w^tt k^tt\]s.a.
\[\sum_i x_i^t \leq 0 + mw^t\]Obtenemos esta restricción usando la técnica 2. Vemos que sólo si se prende la maquina ($w^t = 1$) podemos producir.
\[y_i^{t-1} + x_i^t = y_i^t + d_i^t \qquad \forall i,t\] \[x_{i}^t,y_i^t \geq 0 \qquad \forall i,t\]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 \(z^t = \begin{cases} 1 \qquad \text{encendí la maquina en } t\\ 0 \qquad \text{eoc.} \end{cases}\)
Son las mismas restricciones que las de arriba, sólo agrego:
\[z_t \geq w^t - w^{t-1}\]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 \(x_{ik} = \begin{cases} 1 \qquad \text{cuando nodo } i \text{ es de color } k\\ 0 \qquad \text{eoc.} \end{cases}\)
Defino \(y_{k} = \begin{cases} 1 \qquad \text{cuando uso color } k \\ 0 \qquad \text{eoc.} \end{cases}\)
\[\min \sum_k y_k\]s.a.
Todos los nodos con un color: \(\qquad \sum_k x_{ik} = 1 \qquad \forall i\)
Si uso un color se activa $y_k$: \(\qquad \sum_i x_{ik} \leq 0 + My_k \qquad \forall k\)
$x_{i,k} \rightarrow \neg x_{j, k}$ para nodos conectados: \(\qquad x_{ik} \leq 1- x{jk} \qquad \forall i, k, \forall j \in C_i\)