Método del simplex. Aplicación

Proporcionamos una aplicación del método del simplex.

Enunciado
En el proceso semanal de fabricación de una empresa se producen $43,46$ y $42\; Tm$ de unas substancias $S_1,S_2,S_3$ que no se pueden venderse directamente al mercado, pero permiten obtener unos productos $P_1,P_2,P_3$ que reportan unos beneficios unitarios de $3,5,2$ respectivamente. Para cada $Tm$ de $P_1$ se necesitan $1,3$ y $1\; Tm$ de $S_1,S_2,S_3$ respectivamente y análogamente $1,2,0$ por $Tm$ de $P_2$ y $2,0,4$ por $Tm$ de $P_3$ . Se pide:

1.  Plantear y resolver un problema de programación lineal para organizar la producción de $P_1,P_2,P_3$ de manera que se maximicen los beneficios.
2. Para evitar la contaminación existen disposiciones legales que obligan a consumir cada semana la totalidad de la substancia $S_3$ producida. Calcular la pérdida de beneficios que el cumplimiento de dichas disposiciones supone para la empresa.

(Propuesto en examen, Álgebra, ETS de Ing. de Montes, UPM).

Solución
1. Llamemos $x_1,x_2,x_3$ al número de Tm a fabricar de los productos $P_1,P_2,P_3$ respectivamente. Se trata de maximizar la función $z=3x_1+5x_2+2x_3$ sujeta a las restricciones:

$\left \{ \begin{matrix}  x_1+x_2+2x_3\leq 43\\3x_1+2x_2\qquad \leq 46\\2x_1\qquad +4x_3\leq 42\\ x_1\geq 0,x_2 \geq 0,x_3\geq 0.\end{matrix}\right.
$

Introducimos las variables de holgura $x_i\geq 0\;(i=4,5,6)$ y expresamos el problema en forma estándar:

$\left \{ \begin{matrix}x_1+x_2+2x_3+x_4=43\\3x_1+2x_2\qquad +x_5= 46\\2x_1\qquad +4x_3+x_6= 42\\-3x_1-5x_2-2x_3+z=0\\ x_1\geq 0,x_2 \geq 0,x_3\geq 0 .\end{matrix}\right.
$

Expresemos el problema en forma matricial escribiendo ordenadamente en filas los coeficientes de $x_1,\ldots,x_6,z$ y los términos constantes:

$\left[\begin{array}{ccccccc|c}
\;\;\;1 & \;\;\;1 & \;\;\;2 & \boxed{1} & 0 & 0 & 0 & 43 \\
\;\;\;3 & \;\;\;2 & \;\;\;0 & 0 & \boxed{1} & 0 & 0 & 46 \\
\;\;\;2 & \;\;\;0 & \;\;\;4 & 0 & 0 & \boxed{1} & 0 & 42 \\
-3 & -5 & -2 & 0 & 0 & 0 & 1 & 0
\end{array}\right]$

Una solución factible básica es $x=(0,0,0,43,46,42),$ para la cual $z=0$. La solución no es máxima al existir algún coeficiente negativo para las $x_i$ en la última fila. Eliminemos el menor coeficiente negativo es decir, $-5$. Como $2/46>1/46>0/42$ elegimos como pivote $a_{22}=2$ y fabricamos ceros es la segunda columna:

$\left[\begin{array}{ccccccc|c}
\;\;\;1 & \;\;\;1 & \;\;\;2 & 1 & 0 & 0 & 0 & 43 \\
\;\;\;3/2 & \;\;\;1 & \;\;\;0 & 0 & 1/2 & 0 & 0 & 23 \\
\;\;\;2 & \;\;\;0 & \;\;\;4 & 0 & 0 & 1 & 0 & 42 \\
-3 & -5 & -2 & 0 & 0 & 0 & 1 & 0
\end{array}\right]$

$\left[\begin{array}{ccccccc|c}
-1/2 & \;\;\; 0 & \;\;\;2 & \;\;\;\boxed{1} & -1/2 & 0 & 0 & 20 \\
\;\;3/2 & \;\;\;\boxed{1} & \;\;\;0 & \;\;\;0 & \;\;\;1/2 & 0 & 0 & 23 \\
\;\;2 & \;\;\;0 & \;\;\;4 & \;\;\;0 & \;\;\;0 & \boxed{1} & 0 & 42 \\
\;\;9/2& \;\;\;0 & -2 & \;\;\;0 & \;\;\;5/2 & 0 & 1 & 115
\end{array}\right]$

Una solución factible básica es $x=(0,23,0,20,0,42),$ para la cual $z=115$. La solución no es máxima al existir algún coeficiente negativo para las $x_i$ en la última fila. Eliminemos el único coeficiente negativo es decir, $-2$. Como $2/20>4/42>0/23$ elegimos como pivote $a_{13}=2$ y fabricamos ceros es la primera columna:

$\left[\begin{array}{ccccccc|c}
-1/4 & \;\;\; 0 & \;\;\;1 & \;\;\;1/2 & -1/4 & 0 & 0 & 10 \\
\;\;3/2 & \;\;\;1 & \;\;\;0 & \;\;\;0 & \;\;\;1/2 & 0 & 0 & 23 \\
\;\;2 & \;\;\;0 & \;\;\;4 & \;\;\;0 & \;\;\;0 & 1 & 0 & 42 \\
\;\;9/2& \;\;\;0 & -2 & \;\;\;0 & \;\;\;5/2 & 0 & 1 & 115
\end{array}\right]$

$\left[\begin{array}{ccccccc|c}
-1/4 & \;\;\; 0 & \;\;\;\boxed{1 }& \;\;\;1/2 & -1/4 & 0 & 0 & 10 \\
\;\;3/2 & \;\;\;\boxed{1} & \;\;\;0 & \;\;\;0 & \;\;\;1/2 & 0 & 0 & 23 \\
\;\;3 & \;\;\;0 &\;\;\; 0 & -2 & \;\;\;1 & \boxed{1} & 0 & 2 \\
\;\;4& \;\;\;0 & \;\;\;0 & \;\;\;1 & \;\;\;2 & 0 & 1 & 135
\end{array}\right]$

Una solución factible básica es $x=(0,23,10,0,0,2),$ para la cual $z=135$. La solución es máxima al no existir coeficientes negativos para las $x_i$ en la última fila. En consecuencia, se optimizan los beneficios fabricando $0\;Tm$ de $P_1$, $23\;Tm$ de $P_2$ y $10\;Tm$ de $P_3$, siendo el beneficio máximo de $135$.

2. Basta imponer que $2x_1+4x_3=42$. Despejando obtenemos $x_1=21-2x_3$ con lo cual el problema se reduce a usar el método gráfico en el plano $x_2x_3$.