Programación Lineal III: resolución práctica y ejercicios

En esta entrada muestro cómo se resuelve un problema de P.L. mediante la conocida herramienta de software Matlab. También propongo algunos problemas sencillos para practicar.



En el ejemplo del fabricante de muebles de la entrada anterior, ya hemos visto que el problema de PL para resolver que se obtenía era:

\[
\begin{array}{lll}
(\tilde{P}) & Min & -3x_1-2x_2\\
&s.a & 2x_1+x_2 \leq 100\\
& & x_1+x_2 \leq 80 \\
& & x_1 \leq 40\\
& & -x_1 \leq 0\\
& & -x_2 \leq 0
\end{array}
\]

teniendo en cuenta que el valor en el óptimo de \( (P) \), es decir, el beneficio diario que obtiene el fabricante, será el valor en el óptimo de \( (\tilde{P}) \) cambiado de signo.
Para poder resolver el problema mediante Matlab, debemos escribir en forma matricial. Obsérvese que :
\[-3x_1-2x_2=\left(\begin{array}{cc}-3,-2 \end{array} \right) \left( \begin{array}{c} x_1\\x_2 \end{array} \right)  \]

Y que el conjunto de restricciones se puede escribir como:
\[\left( \begin{array}{c c}
2 & 1 \\
1 & 1 \\
1 & 0 \\
-1 & 0 \\
0 & -1 \\
\end{array} \right)
\left( \begin{array}{c} x_1\\x_2 \end{array} \right)=
\left( \begin{array}{c} 100\\80\\40\\0\\0 \end{array} \right)
 \]

Si llamamos
\[ x:=\left( \begin{array}{c} x_1\\x_2 \end{array} \right),
f:=\left( \begin{array}{c} -3\\-2 \end{array} \right),
A:=
\left( \begin{array}{c c}
2 & 1 \\
1 & 1 \\
1 & 0 \\
-1 & 0 \\
0 & -1 \\
\end{array} \right),
b:=\left( \begin{array}{c} 100\\80\\40\\0\\0 \end{array} \right)
 \]
podemos expresar el problema \( (\tilde{P})\) de la forma

\[
\begin{array}{lll}
(\tilde{P}) & Min & f'x\\
&s.a & Ax \leq b
\end{array}
\]

Los elementos \( f\), \( A\) y \( b\)  son los necesarios para resolver el problema mediante Matlab. Este software resuelve un problema como \( (\tilde{P})\) mediante la función linprog y la sintaxis básica:

>> [x, fval]=linprog(f,A,b)

Los valores de salida son x, el óptimo, y fval, el valor en el óptimo del problema.
Sólo hay que introducir los vectores \( f\) y \( b\) y la matriz  \(A\)  en el workspace de Matlab (mediante el Array Editor p.e.) y ejecutar el citado comando. Puede observarse el resultado obtenido en la figura siguiente.

(pinchar para ampliar)

se ha obtenido el óptimo x=(20,60)' y el valor en el óptimo -180. Por lo que hemos explicado antes, el valor en el óptimo del problema original \( (P)\), es decir, el beneficio diario del fabricante de muebles será 180.


Ejercicios:

Ejercicio 1. Una compañía fabricante de aparatos de televisión tiene que decidir entre el número de televisores a color y en blanco y negro que debe producir. Una investigación de mercado indica que por mes es posible vender como mucho 1000 unidades a color y 4000 en blanco y negro. El número máximo de horas-hombre disponibles es de 50000 por mes. Un televisor a color requiere 20 horas-hombre, y uno en blanco y negro requiere de 15 horas-hombre. Las ganancias por unidad de los televisores a color y en blanco y negro son de $60 y $30, respectivamente. Se desea encontrar el número de unidades de cada tipo de televisor que la compañía debe producir para maximizar sus ganancias.

Ejercicio 2. Un fabricante de plásticos planea obtener un nuevo producto mezclando cuatro compuestos químicos. Estos compuestos constan principalmente de 3 elementos químicos. Estos compuestos constan principalmente de 3 elementos químicos, A, B y C. A continuación se muestran la composición y el costo por unidad de estos compuestos:

El nuevo producto consta del 20% del elemento A, por lo menos 30% del elemento B y al menos 20% del elemento C. Debido a los efectos laterales de los compuestos A y B, no deben exceder del 30% y del 40% del contenido del nuevo producto respectivamente. Formular como un programa lineal el problema de encontrar la forma menos costosa de obtener el nuevo producto.



Ejercicio 3. Un fabricante de acero produce cuatro tamaños de vigas: pequeña, mediana, larga y extra larga. Estas vigas se pueden producir en cualesquiera de tres tipos de máquinas: A, B y C. A continuación se indican las longitudes (en pies) de cada tipo de viga que pueden producir la máquinas por hora.

Supóngase que cada máquina se puede usar hasta 50 horas por semana, y que los costos de operación por hora de las máquinas A, B y C son $30, $50 y $80 respectivamente. Además supóngase que semanalmente se requieren 10000, 8000, 6000 y 6000 pies de los distintos tamaños de viga de menor a mayor respectivamente. Formúlese como un programa lineal el problema de minimizar los costes de producción de las vigas.

Nota: para ampliar conocimientos acerca de los métodos de resolución de un problema de PL, recomiendo visitar la WEB de Teodoro Coronado.

Referencias:
- Optimización Lineal: teoría, métodos y modelos, Goberna. McGRAW-HILL.
- Programación Lineal y Flujo en Redes, Bazaraa. Limusa.


Enlaces de interés:
- http://thales.cica.es/rd/Recursos/rd98/Matematicas/29/intro.html.
- http://recursostic.educacion.es/descartes/web/materiales_didacticos/Programacion_lineal/program.htm.