Programación Lineal II: modelo y ejemplos

En esta entrada hago una breve introducción a los problemas de PM y PL, escogiendo algún ejemplo para una mejor comprensión de los conceptos.

Como ya hemos indicado en este blog,un problema de PM general tiene la forma:

\[
\begin{array}{lll}
(P) & Min & f(x)\\
&s.a & g_i(x) \leq 0, \ i=1,\ldots,n
\end{array}
\]
con \( f,\ g_i:\mathbb{R}^n \longrightarrow \mathbb{R} \).
La resolución del problema \((P)\) consiste en minimizar la función \(f(x)\) con \(x\) variando en el conjunto \( F=\left\{x \in \mathbb{R}: g_i(x) \leq 0  \ \forall i=1,\ldots,n \right\} \).
Un punto \( \bar{x} \) que minimiza \(f(x)\) sobre \(F\) se denomina óptimo o mínimo global de \( (P) \).
Dado cualquier óptimo \( \bar{x} \), al valor \( \bar{y}:=f(\bar{x}) \) se le denomina valor de \( (P) \) o valor en el óptimo de \( (P) \).
En ocasiones, en el planteamiento de un problema se desea maximizar (producción, beneficio, ...), en lugar de minimizar. No obstante, se puede reducir al mismo modelo de problema \( (P) \), sin más que observar que: \( \mathrm{max} \ f(x) = -\mathrm{min} -f(x) \).

(hacer click en la imagen para ampliar)

También se utilizan en ocasiones restricciones de igualdad, pero puede reducirse nuevamente al modelo \( (P) \) separando la igualdad en sus dos desigualdades:
\[ h(x)=0 \Leftrightarrow \left( h(x) \leq 0, \ -h(x) \leq 0 \right).\]
Un problema de PL es un problema de PM en el que la función objetivo, \(f(x) \) y las restriciones, \(g_i(x) \), son funciones lineales. Por ejemplo:


\[
\begin{array}{lll}
(P) & Min & -3x_1-2x_2-x_3\\
&s.a & x_1+x_2+x_3 \leq 1\\
& & x_1-x_3 \leq 3 \\
& & -x_1+x_3 \leq -3
\end{array}
\]

Veamos a continuación un ejemplo donde se modeliza un problema de PL.
Ejemplo: Un fabricante  de muebles artesanales produce sillas y taburetes de madera. El fabricante cree que la demanda de taburetes es prácticamente ilimitada, pero la de sillas la estima en 40 unidades diarias. La madera, que para simplificar suponemos que es la única materia prima requerida, la adquiere de una única serrería de la región, y su disponibilidad es ilimitada. Por lo que se refiere a la mano de obra, ya ha sido contratada, disponiéndose de 100h/día en carpintería y de 80h/día en acabado. Los precios y costes que aparecen en la tabla posterior son unitarios y se expresan en euros.

Se desea planificar la producción para maximizar el beneficio diario.

Solución:

1. Variables aleatorias:
\(x_1\): número diario de sillas producidas.
\(x_2\): producción diaria de taburetes.
Para simplificar la resolución vamos a obviar que dichos valores deben ser números enteros; es decir, se podrá vender una silla y media o tres taburetes y un tercio de otro.

2. Función Objetivo: Al precio de venta de cada unidad se le restan los costes.
Beneficio: \( (27-10-14)x_1+(21-9-10) x_2=3x_1+2x_2\)

3. Restricciones:
- La demanda de sillas es inferior a 40 unidades/día: \(x_1 \leq 40\)
- Límite de 100 h/día de carpintería: \(2x_1+x_2 \leq 100 \)
- Límite de 80 h/día de acabado: \( x_1+x_2 \leq 80 \)
- El número de sillas y taburetes debe ser un valor no negativo:  \( x_1 \geq 0, x_2 \geq 0 \)

El problema a resolver es:

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

o equivalentemente (tal como hemos indicado en el desarrollo previo) podemos resolver el problema

\[
\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.

Nota: Para ampliar conocimientos, recomiendo echar un vistazo a la web de Teodoro Coronado, donde muestra como se determina la región factible de un problema de PL.

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.