Método del simplex

Publicada el marzo 2, 2015 por Fernando Revilla

Proporcionamos algunos ejercicios sobre el método del simplex.

    Enunciado
  1. Hallar el máximo de la función $z=2x_1+x_2$ con las restricciones $$\left \{ \begin{matrix} \displaystyle\begin{aligned} & 3x_1+2x_2\leq 10\\& x_1+3x_2\leq 5\\& x_1\geq 0,\;x_2\geq 0. \end{aligned}\end{matrix}\right.$$
  2. Hallar el máximo de la función $z=8x_1+4x_2+6x_3$ con las restricciones $$\left \{ \begin{matrix} \displaystyle\begin{aligned} & 2x_1+3x_2+x_3\leq 7\\& x_1+x_2+2x_3\leq 6\\& 2x_1+4x_2+3x_3\leq 15\\& x_1\geq 0,\;x_2\geq 0,\;x_3\geq 0. \end{aligned}\end{matrix}\right.$$
  3. Hallar el mínimo de la función $z=4x_1+8x_2+3x_3$ con las restricciones $$\left \{ \begin{matrix} \displaystyle\begin{aligned} & x_1+x_2\geq 2\\& 2x_2+x_3\geq 5\\& x_1\geq 0,\;x_2\geq 0,\;x_3\geq 0. \end{aligned}\end{matrix}\right.$$
  4. Minimizar la función $f(x_1,x_2,x_3,x_4)=x_1-6x_2+3x_3+x_4$ bajo las restricciones $$\left \{ \begin{matrix} \displaystyle\begin{aligned} & x_1-2x_2+x_3+3x_4\leq 8\\& 2x_1+3x_2-x_3+2x_4\leq 5\\& x_1+x_2-3x_3+4x_4\leq 6\\& x_i\geq 0\;\;(i=1,\ldots,4).\end{aligned}\end{matrix}\right.$$
    Solución
  1. Introducimos las variables de holgura $x_i\geq 0\;(i=3,4)$ y expresamos el problema en forma estándar: $$\left \{ \begin{matrix} \displaystyle\begin{aligned} & 3x_1+2x_2+x_3 =10\\& x_1+3x_2+x_4= 5\\& -2x_1-x_2+z=0\\& x_i\geq 0\quad (i=1,\ldots,4). \end{aligned}\end{matrix}\right.$$ Expresemos el problema en forma matricial escribiendo ordenadamente en filas los coeficientes de $x_1,\ldots,x_4,z$ y los términos constantes $$\left[\begin{array}{ccccc|c}
    \;\;3 & \;\;2 & \boxed{1} & 0 & 0 & 10 \\
    \;\;1 & \;\;3 & 0 & \boxed{1} & 0 & 5 \\
    -2 & -1 & 0 & 0 & 1 & 0
    \end{array}\right].$$ Una solución factible básica es $x=(0,0,10,5)^t,$ para la cual $z=0$. La solución no es máxima al existir algún coeficiente negativo para las $x_i$ correspondientes a la última fila. Eliminemos el menor coeficiente negativo es decir, $-2$. Como $3/10>1/5$ elegimos como pivote $a_{11}=3$ y fabricamos ceros en la primera columna: $$\left[\begin{array}{ccccc|c}
    \;\;\boxed{1} & \;\;2/3 & 1/3 & 0 & 0 & 10/3 \\
    \;\;1 & \;\;3 & 0 & \boxed{1} & 0 & 5 \\
    -2 & -1 & 0 & 0 & 1 & 0
    \end{array}\right],$$ $$\left[\begin{array}{ccccc|c}
    \boxed{1} & 2/3 & \;\; 1/3 & 0 & 0 & 10/3 \\
    0 & 7/3 & -1/3 & \boxed{1} & 0 & 5/3 \\
    0 & 1/3 & \;\;2/3 & 0 & 1 & 20/3
    \end{array}\right].$$ Una solución factible básica es $x=(10/3,0,0,5/3)^t,$ para la cual $z=20/3$. La solución es máxima al no existir coeficientes negativos para las $x_i$ correspondientes a la última fila. Por tanto, $$z_{\text{max}}\left(\frac{10}{3},0\right)=\frac{20}{3}.$$
  2. Introducimos las variables de holgura $x_i\geq 0\;(i=4,5,6)$ y expresamos el problema en forma estándar, escribiendo ordenadamente en filas los coeficientes de $x_1,\ldots,x_6,z$ y los términos constantes: $$\left[\begin{array}{ccccccc|c}
    \;\;\;2 & \;\;\;3 & \;\;\;1 & \boxed{1} & 0 & 0 & 0 & 7 \\
    \;\;\;1 & \;\;\;1 & \;\;\;2 & 0 & \boxed{1} & 0 & 0 & 6 \\
    \;\;\;2 & \;\;\;4 & \;\;\;3 & 0 & 0 & \boxed{1} & 0 & 15 \\
    -8 & -4 & -6 & 0 & 0 & 0 & 1 & 0
    \end{array}\right].$$ Una solución factible básica es $x=(0,0,0,7,6,15)^t,$ 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, $-8$. Como $2/7>1/6>2/45,$ elegimos como pivote $a_{11}=2$ y fabricamos ceros es la primera columna: $$\left[\begin{array}{ccccccc|c}
    \;\;\;\boxed{1} & \;\;\;3/2 & \;\;\;1/2 & 1/2 & 0 & 0 & 0 & 7/2 \\
    \;\;\;1 & \;\;\;1 & \;\;\;2 & 0 & \boxed{1} & 0 & 0 & 6 \\
    \;\;\;2 & \;\;\;4 & \;\;\;3 & 0 & 0 & \boxed{1} & 0 & 15 \\
    -8 & -4 & -6 & 0 & 0 & 0 & 1 & 0
    \end{array}\right],$$ $$\left[\begin{array}{ccccccc|c}
    \boxed{1} & \;\;\;3/2 & \;\;\;1/2 &\;\;\; 1/2 & 0 & 0 & 0 & 7/2 \\
    0 & -1/2 & \;\;\;3/2 & -1/2 & \boxed{1} & 0 & 0 & 5/2 \\
    0 & \;\;\;1 & \;\;\;2 & -1 & 0 & \boxed{1} & 0 & 8 \\
    0 & \;\;\;8 & -2 & \;\;4 & 0 & 0 & 1 & 28
    \end{array}\right].$$ Una solución factible básica es $x=(7/2,0,0,0,5/2,8)^t,$ para la cual $z=28$. 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 $3/5>2/8>1/7,$ elegimos como pivote $a_{23}=3/2$ y fabricamos ceros es la tercera columna:
    $$\left[\begin{array}{ccccccc|c}
    \boxed{1} & \;\;\;3/2 & \;\;\;1/2 &\;\;\; 1/2 & 0 & 0 & 0 & 7/2 \\
    0 & -1/3 & \;\;\;\boxed{1} & -1/3 & 2/3 & 0 & 0 & 5/3 \\
    0 & \;\;\;1 & \;\;\;2 & -1 & 0 & \boxed{1} & 0 & 8 \\
    0 & \;\;\;8 & -2 & \;\;4 & 0 & 0 & 1 & 28
    \end{array}\right],$$ $$\left[\begin{array}{ccccccc|c}
    \boxed{1} & \;\;\;5/3 & \;\;\;0 &\;\;\; 1/2 & 2/3 & 0 & 0 & 8/3 \\
    0 & -1/3 & \;\;\;\boxed{1} & -1/3 & 2/3 & 0 & 0 & 5/3 \\
    0 & \;\;\;5/3 & \;\;\;0 & -1/3 & -4/3 & \boxed{1} & 0 & 14/3 \\
    0 & \;\;\;22/3 & \;\;\;0 & \;\;10/3 & \;4/3 & 0 & 1 & 94/3
    \end{array}\right].$$ Una solución factible básica es $x=(8/3,0,5/3,0,0,14/3)^t,$ para la cual $z=94/3$. La solución es máxima al no existir coeficientes negativos para las $x_i$ en la última fila. Por tanto, $$z_{\text{max}}\left(\frac{8}{3},0,\frac{5}{3}\right)=\frac{94}{3}.$$
  3. Hallemos el máximo de la función $z’=-z=-4x_1-8x_2-3x_3.$ Introducimos las variables de holgura $x_i\geq 0\;(i=4,5)$ y expresamos el problema en forma estándar, escribiendo ordenadamente en filas los coeficientes de $x_1,\ldots,x_5,z’$ y los términos constantes: $$\left[\begin{array}{cccccc|c}
    1 & 1 & 0 & -1 & \;\;0 & 0 & 2 \\
    0 & 2 & 1 & \;\;0 & -1 & 0 & 5 \\
    4 & 8 & 3 & \;\;0 & \;\;0 & 1 & 0
    \end{array}\right].$$ Encontremos una solución factible básica. Elegimos como pivote el elemento $a_{11}=1$ y fabricamos ceros en la primera columna $$\left[\begin{array}{cccccc|c}
    \boxed{1} & 1 & 0 & -1 & \;\;0 & 0 & \;\;2 \\
    0 & 2 & 1 & \;\;0 & -1 & 0 & \;\;5 \\
    0 & 4 & 3 & \;\;4 & \;\;0 & 1 & -8
    \end{array}\right].$$ Tomamos ahora como pivote el elemento $a_{33}=1$ y fabricamos ceros en la tercera columna $$\left[\begin{array}{cccccc|c}
    \boxed{1} & \;\;1 & 0 & -1 & \;\;0 & 0 & \;\;2 \\
    0 & \;\;2 & \boxed{1} & \;\;0 & -1 & 0 & \;\;5 \\
    0 & -2 & 0 & \;\;4 & \;\;3 & 1 & -23
    \end{array}\right].$$ Una solución factible básica es $x=(2,0,5,0,0)^t,$ para la cual $z’=-23$. La solución no es máxima al existir algún coeficiente negativo para las $x_i$ en la última fila. Eliminemos el coeficiente negativo de la última fila. Como $1/2>2/5,$ tomamos el elemento $a_{12}=1$ como pivote y fabricamos ceros en la segunda columna $$\left[\begin{array}{cccccc|c}
    \;\;1 & \;\;\boxed{1} & 0 & -1 & \;\;0 & 0 & \;\;2 \\
    -2 & \;\;0 & \boxed{1} & \;\;2 & -1 & 0 & \;\;1 \\
    \;\;2 & \;\;0 & 0 & \;\;2 & \;\;3 & 1 & -19
    \end{array}\right].$$ Una solución factible básica es $x=(0,2,1,0,0)^t,$ para la cual $z’=-19$. La solución es máxima al no existir coeficiente negativos para las $x_i$ en la última fila. En consecuencia, $$z’_{\text{max}}\left(0,2,1\right)=-19,\text{ o bien } \;z_{\text{min}}\left(0,2,1\right)=19.$$
  4. Hallemos el máximo de la función $z=-f(x_1,x_2,x_3,x_4).$ Introducimos las variables de holgura $x_i\geq 0\;(i=5,6,7)$ y expresamos el problema en forma estándar, escribiendo ordenadamente en filas los coeficientes de $x_1,\ldots,x_7,z$ y los términos constantes: $$\left[\begin{array}{cccccccc|c}
    1 & -2 & \;\;\;1 & 3 & \boxed{1} & 0 & 0 & 0& 8 \\
    2 & \;\;3 & -1 & 2 & 0 &\boxed{1} & 0 & 0 & 5 \\
    1& \;\;1 & -3 & 0 & 0 & 0 & \boxed{1} & 0 & 6\\
    1 & -6 & \;\;3 & 1 & 0 & 0 & 1 & 0 & 0
    \end{array}\right].$$ Una solución factible básica es $x=(0,0,0,0,8,5,6)^t,$ 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 coeficiente negativo de la última fila. Como $3/5>1/6,$ tomamos el elemento $a_{22}=6$ como pivote y fabricamos ceros en la segunda columna $$\left[\begin{array}{cccccccc|c}
    1 & -2 & \;\;\;1 & 3 & \boxed{1} & 0 & 0 & 0& 8 \\
    2/3 & \;\;\boxed{1} & -1/3 & 2/3 & 0 & 1/3 & 0 & 0 & 5/3 \\
    1& \;\;1 & -3 & 0 & 0 & 0 & \boxed{1} & 0 & 6\\
    1 & -6 & \;\;3 & 1 & 0 & 0 & 0 & 1 & 0
    \end{array}\right],$$ $$\left[\begin{array}{cccccccc|c}
    7/3 & 0 & \;\;\;1/3 & \;\;13/3 & \boxed{1} & \;\;2/3 & 0 & 0& 34/3 \\
    2/3 & \boxed{1} & -1/3 & \;\;2/3 & 0 & \;\;1/3 & 0 & 0 & 5/3 \\
    1/3& 0 & -8/3 & -2/3 & 0 & -1/3 & \boxed{1} & 0 & 13/3\\
    5 & 0 & \;\;1 & \;\;5 & 0 & \;\;2 & 0 & 1 & 10
    \end{array}\right].$$ Una solución factible básica es $x=(0,5/3,0,0,34/3,0,13/3)^t,$ para la cual $z$ $=$ $10$. La solución es máxima al no existir coeficientes negativos para las $x_i$ en la última fila. Por tanto, $$z_{\text{max}}\left(0,\frac{5}{3},0,0\right)=10. \text{ o bien }\;f_{\text{min}}\left(0,\frac{5}{3},0,0\right)=-10.$$
Esta entrada ha sido publicada en Álgebra y etiquetada como , . Guarda el enlace permanente.