De acuerdo a lo visto la clase pasada, un problema de programación lineal puede escribirse en la siguiente forma:
\begin{equation} \begin{array}{ll} \min_{x_1,\dots,x_n} & f_1x_1+\dots+f_nx_n \\ \text{s. a. } & a^{eq}_{j,1}x_1+\dots+a^{eq}_{j,n}x_n=b^{eq}_j \text{ para } 1\leq j\leq m_1 \\ & a_{k,1}x_1+\dots+a_{k,n}x_n\leq b_k \text{ para } 1\leq k\leq m_2, \end{array} \end{equation}donde:
Equivalentemente, el problema puede escribirse como
\begin{equation} \begin{array}{ll} \min_{\boldsymbol{x}} & \boldsymbol{f}^T\boldsymbol{x} \\ \text{s. a. } & \boldsymbol{A}_{eq}\boldsymbol{x}=\boldsymbol{b}_{eq} \\ & \boldsymbol{A}\boldsymbol{x}\leq\boldsymbol{b}, \end{array} \end{equation}donde:
Nota: el problema $\max_{\boldsymbol{x}}\boldsymbol{g}(\boldsymbol{x})$ es equivalente a $\min_{\boldsymbol{x}}-\boldsymbol{g}(\boldsymbol{x})$.
Para trabajar con pyomo
:
pyomo
a parte de contener funciones para optimización, es en sí un lenguaje de programación. No tiene solucionadores instalados, utiliza solucionadores externos (glpk, ipopt).Una compañía produce dos productos ($X_1$ y $X_2$) usando dos máquinas ($A$ y $B$). Cada unidad de $X_1$ que se produce requiere 50 minutos en la máquina $A$ y 30 minutos en la máquina $B$. Cada unidad de $X_2$ que se produce requiere 24 minutos en la máquina $A$ y 33 minutos en la máquina $B$.
Al comienzo de la semana hay 30 unidades de $X_1$ y 90 unidades de $X_2$ en inventario. El tiempo de uso disponible de la máquina $A$ es de 40 horas y el de la máquina $B$ es de 35 horas.
La demanda para $X_1$ en la semana actual es de 75 unidades y de $X_2$ es de 95 unidades. La política de la compañía es maximizar la suma combinada de unidades de $X_1$ e $X_2$ en inventario al finalizar la semana.
Formular el problema de decidir cuánto hacer de cada producto en la semana como un problema de programación lineal.
Sean:
con
In [1]:
import numpy as np
In [2]:
f = np.array([-1, -1])
A = np.array([[50, 24], [30, 33], [-1, 0], [0, -1]])
b = np.array([2400, 2100, -45, -5])
In [3]:
import pyomo_utilities
In [5]:
x, obj = pyomo_utilities.linprog(f, A, b)
In [8]:
obj
Out[8]:
Mónica hace aretes y cadenitas de joyería. Es tan buena, que todo lo que hace lo vende.
Le toma 30 minutos hacer un par de aretes y una hora hacer una cadenita, y como Mónica también es estudihambre, solo dispone de 10 horas a la semana para hacer las joyas. Por otra parte, el material que compra solo le alcanza para hacer 15 unidades (el par de aretes cuenta como unidad) de joyas por semana.
La utilidad que le deja la venta de las joyas es \$15 en cada par de aretes y \$20 en cada cadenita.
¿Cuántos pares de aretes y cuántas cadenitas debería hacer Mónica para maximizar su utilidad?
Formular el problema en la forma explicada y obtener la solución gráfica (puede ser a mano).
Sean:
con
In [ ]:
In [ ]:
In [ ]:
Este es un caso curioso, con solo 6 variables (un caso real de problema de transporte puede tener fácilmente más de 1.000 variables) en el cual se aprecia la utilidad de este procedimiento de cálculo.
Existen tres minas de carbón cuya producción diaria es:
En la zona hay dos centrales termoeléctricas que consumen:
Los costos de mercado, de transporte por tonelada son:
Si se preguntase a los pobladores de la zona cómo organizar el transporte, tal vez la mayoría opinaría que debe aprovecharse el precio ofrecido por el transportista que va de "a" a "d", porque es más conveniente que los otros, debido a que es el de más bajo precio.
En este caso, el costo total del transporte es:
Para un total 1.400 monedas.
Sin embargo, formulando el problema para ser resuelto por la programación lineal se tienen las siguientes ecuaciones:
Restricciones de la producción:
Restricciones del consumo:
La función objetivo será:
$$\min_{x_1,\dots,x_6}2x_1 + 11x_2 + 12x_3 + 24x_4 + 13x_5 + 18x_6$$
In [ ]:
In [ ]:
In [ ]:
In [ ]:
La solución de costo mínimo de transporte diario resulta ser:
para un total de $1280$ monedas, $120$ monedas menos que antes.