Maximizar $$$7 x + 2 y$$$, sujeto a $$$\begin{cases} 3 x + 5 y \geq 20 \\ 3 x + y \leq 16 \\ - 2 x + y \leq 1 \\ x \geq 0 \\ y \geq 0 \end{cases}$$$
Tu aportación
Maximiza $$$Z = 7 x + 2 y$$$, sujeto a $$$\begin{cases} 3 x + 5 y \geq 20 \\ 3 x + y \leq 16 \\ - 2 x + y \leq 1 \\ x \geq 0 \\ y \geq 0 \end{cases}.$$$
Solución
El problema en forma canónica se puede escribir de la siguiente manera:
$$Z = 7 x + 2 y \to max$$$$\begin{cases} 3 x + 5 y \geq 20 \\ 3 x + y \leq 16 \\ - 2 x + y \leq 1 \\ x, y \geq 0 \end{cases}$$Agregue variables (holgura o excedente) para convertir todas las desigualdades en igualdades:
$$Z = 7 x + 2 y \to max$$$$\begin{cases} 3 x + 5 y - S_{1} = 20 \\ 3 x + y + S_{2} = 16 \\ - 2 x + y + S_{3} = 1 \\ x, y, S_{1}, S_{2}, S_{3} \geq 0 \end{cases}$$Como no tenemos una base, agregue una variable artificial:
$$Z = 7 x + 2 y \to max$$$$\begin{cases} 3 x + 5 y - S_{1} + Y_{1} = 20 \\ 3 x + y + S_{2} = 16 \\ - 2 x + y + S_{3} = 1 \\ x, y, S_{1}, S_{2}, S_{3}, Y_{1} \geq 0 \end{cases}$$Penalizar la variable artificial en la función objetivo:
$$Z = 7 x + 2 y - M Y_{1} \to max$$$$\begin{cases} 3 x + 5 y - S_{1} + Y_{1} = 20 \\ 3 x + y + S_{2} = 16 \\ - 2 x + y + S_{3} = 1 \\ x, y, S_{1}, S_{2}, S_{3}, Y_{1} \geq 0 \end{cases}$$Escriba el cuadro símplex:
Basic | $$$x$$$ | $$$y$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | $$$S_{3}$$$ | $$$Y_{1}$$$ | Solución |
$$$Z$$$ | $$$-7$$$ | $$$-2$$$ | $$$0$$$ | $$$0$$$ | $$$0$$$ | $$$M$$$ | $$$0$$$ |
$$$Y_{1}$$$ | $$$3$$$ | $$$5$$$ | $$$-1$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$20$$$ |
$$$S_{2}$$$ | $$$3$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ | $$$16$$$ |
$$$S_{3}$$$ | $$$-2$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ |
Haga que la fila Z sea consistente con el resto del cuadro.
Reste la fila $$$2$$$ multiplicada por $$$M$$$ de la fila $$$1$$$: $$$R_{1} = R_{1} - M R_{2}$$$.
Basic | $$$x$$$ | $$$y$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | $$$S_{3}$$$ | $$$Y_{1}$$$ | Solución |
$$$Z$$$ | $$$- 3 M - 7$$$ | $$$- 5 M - 2$$$ | $$$M$$$ | $$$0$$$ | $$$0$$$ | $$$0$$$ | $$$- 20 M$$$ |
$$$Y_{1}$$$ | $$$3$$$ | $$$5$$$ | $$$-1$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$20$$$ |
$$$S_{2}$$$ | $$$3$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ | $$$16$$$ |
$$$S_{3}$$$ | $$$-2$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ |
La variable entrante es $$$y$$$, porque tiene el coeficiente más negativo $$$- 5 M - 2$$$ en la fila Z.
Basic | $$$x$$$ | $$$y$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | $$$S_{3}$$$ | $$$Y_{1}$$$ | Solución | Ratio |
$$$Z$$$ | $$$- 3 M - 7$$$ | $$$- 5 M - 2$$$ | $$$M$$$ | $$$0$$$ | $$$0$$$ | $$$0$$$ | $$$- 20 M$$$ | |
$$$Y_{1}$$$ | $$$3$$$ | $$$5$$$ | $$$-1$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$20$$$ | $$$\frac{20}{5} = 4$$$ |
$$$S_{2}$$$ | $$$3$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ | $$$16$$$ | $$$\frac{16}{1} = 16$$$ |
$$$S_{3}$$$ | $$$-2$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ | $$$\frac{1}{1} = 1$$$ |
La variable saliente es $$$S_{3}$$$, porque tiene la proporción más pequeña.
Agregue la fila $$$4$$$ multiplicada por $$$5 M + 2$$$ a la fila $$$1$$$: $$$R_{1} = R_{1} + \left(5 M + 2\right) R_{4}$$$.
Basic | $$$x$$$ | $$$y$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | $$$S_{3}$$$ | $$$Y_{1}$$$ | Solución |
$$$Z$$$ | $$$- 13 M - 11$$$ | $$$0$$$ | $$$M$$$ | $$$0$$$ | $$$5 M + 2$$$ | $$$0$$$ | $$$2 - 15 M$$$ |
$$$Y_{1}$$$ | $$$3$$$ | $$$5$$$ | $$$-1$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$20$$$ |
$$$S_{2}$$$ | $$$3$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ | $$$16$$$ |
$$$y$$$ | $$$-2$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ |
Reste la fila $$$4$$$ multiplicada por $$$5$$$ de la fila $$$2$$$: $$$R_{2} = R_{2} - 5 R_{4}$$$.
Basic | $$$x$$$ | $$$y$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | $$$S_{3}$$$ | $$$Y_{1}$$$ | Solución |
$$$Z$$$ | $$$- 13 M - 11$$$ | $$$0$$$ | $$$M$$$ | $$$0$$$ | $$$5 M + 2$$$ | $$$0$$$ | $$$2 - 15 M$$$ |
$$$Y_{1}$$$ | $$$13$$$ | $$$0$$$ | $$$-1$$$ | $$$0$$$ | $$$-5$$$ | $$$1$$$ | $$$15$$$ |
$$$S_{2}$$$ | $$$3$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ | $$$16$$$ |
$$$y$$$ | $$$-2$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ |
Reste la fila $$$4$$$ de la fila $$$3$$$: $$$R_{3} = R_{3} - R_{4}$$$.
Basic | $$$x$$$ | $$$y$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | $$$S_{3}$$$ | $$$Y_{1}$$$ | Solución |
$$$Z$$$ | $$$- 13 M - 11$$$ | $$$0$$$ | $$$M$$$ | $$$0$$$ | $$$5 M + 2$$$ | $$$0$$$ | $$$2 - 15 M$$$ |
$$$Y_{1}$$$ | $$$13$$$ | $$$0$$$ | $$$-1$$$ | $$$0$$$ | $$$-5$$$ | $$$1$$$ | $$$15$$$ |
$$$S_{2}$$$ | $$$5$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$-1$$$ | $$$0$$$ | $$$15$$$ |
$$$y$$$ | $$$-2$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ |
La variable entrante es $$$x$$$, porque tiene el coeficiente más negativo $$$- 13 M - 11$$$ en la fila Z.
Basic | $$$x$$$ | $$$y$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | $$$S_{3}$$$ | $$$Y_{1}$$$ | Solución | Ratio |
$$$Z$$$ | $$$- 13 M - 11$$$ | $$$0$$$ | $$$M$$$ | $$$0$$$ | $$$5 M + 2$$$ | $$$0$$$ | $$$2 - 15 M$$$ | |
$$$Y_{1}$$$ | $$$13$$$ | $$$0$$$ | $$$-1$$$ | $$$0$$$ | $$$-5$$$ | $$$1$$$ | $$$15$$$ | $$$\frac{15}{13}$$$ |
$$$S_{2}$$$ | $$$5$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$-1$$$ | $$$0$$$ | $$$15$$$ | $$$\frac{15}{5} = 3$$$ |
$$$y$$$ | $$$-2$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ | $$$\frac{1}{-2}$$$ (denominador negativo, ignorar) |
La variable saliente es $$$Y_{1}$$$, porque tiene la proporción más pequeña.
Divide la fila $$$1$$$ entre $$$13$$$: $$$R_{1} = \frac{R_{1}}{13}$$$.
Basic | $$$x$$$ | $$$y$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | $$$S_{3}$$$ | $$$Y_{1}$$$ | Solución |
$$$Z$$$ | $$$- 13 M - 11$$$ | $$$0$$$ | $$$M$$$ | $$$0$$$ | $$$5 M + 2$$$ | $$$0$$$ | $$$2 - 15 M$$$ |
$$$x$$$ | $$$1$$$ | $$$0$$$ | $$$- \frac{1}{13}$$$ | $$$0$$$ | $$$- \frac{5}{13}$$$ | $$$\frac{1}{13}$$$ | $$$\frac{15}{13}$$$ |
$$$S_{2}$$$ | $$$5$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$-1$$$ | $$$0$$$ | $$$15$$$ |
$$$y$$$ | $$$-2$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ |
Agregue la fila $$$2$$$ multiplicada por $$$13 M + 11$$$ a la fila $$$1$$$: $$$R_{1} = R_{1} + \left(13 M + 11\right) R_{2}$$$.
Basic | $$$x$$$ | $$$y$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | $$$S_{3}$$$ | $$$Y_{1}$$$ | Solución |
$$$Z$$$ | $$$0$$$ | $$$0$$$ | $$$- \frac{11}{13}$$$ | $$$0$$$ | $$$- \frac{29}{13}$$$ | $$$M + \frac{11}{13}$$$ | $$$\frac{191}{13}$$$ |
$$$x$$$ | $$$1$$$ | $$$0$$$ | $$$- \frac{1}{13}$$$ | $$$0$$$ | $$$- \frac{5}{13}$$$ | $$$\frac{1}{13}$$$ | $$$\frac{15}{13}$$$ |
$$$S_{2}$$$ | $$$5$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$-1$$$ | $$$0$$$ | $$$15$$$ |
$$$y$$$ | $$$-2$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ |
Reste la fila $$$2$$$ multiplicada por $$$5$$$ de la fila $$$3$$$: $$$R_{3} = R_{3} - 5 R_{2}$$$.
Basic | $$$x$$$ | $$$y$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | $$$S_{3}$$$ | $$$Y_{1}$$$ | Solución |
$$$Z$$$ | $$$0$$$ | $$$0$$$ | $$$- \frac{11}{13}$$$ | $$$0$$$ | $$$- \frac{29}{13}$$$ | $$$M + \frac{11}{13}$$$ | $$$\frac{191}{13}$$$ |
$$$x$$$ | $$$1$$$ | $$$0$$$ | $$$- \frac{1}{13}$$$ | $$$0$$$ | $$$- \frac{5}{13}$$$ | $$$\frac{1}{13}$$$ | $$$\frac{15}{13}$$$ |
$$$S_{2}$$$ | $$$0$$$ | $$$0$$$ | $$$\frac{5}{13}$$$ | $$$1$$$ | $$$\frac{12}{13}$$$ | $$$- \frac{5}{13}$$$ | $$$\frac{120}{13}$$$ |
$$$y$$$ | $$$-2$$$ | $$$1$$$ | $$$0$$$ | $$$0$$$ | $$$1$$$ | $$$0$$$ | $$$1$$$ |
Agregue la fila $$$2$$$ multiplicada por $$$2$$$ a la fila $$$4$$$: $$$R_{4} = R_{4} + 2 R_{2}$$$.
Basic | $$$x$$$ | $$$y$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | $$$S_{3}$$$ | $$$Y_{1}$$$ | Solución |
$$$Z$$$ | $$$0$$$ | $$$0$$$ | $$$- \frac{11}{13}$$$ | $$$0$$$ | $$$- \frac{29}{13}$$$ | $$$M + \frac{11}{13}$$$ | $$$\frac{191}{13}$$$ |
$$$x$$$ | $$$1$$$ | $$$0$$$ | $$$- \frac{1}{13}$$$ | $$$0$$$ | $$$- \frac{5}{13}$$$ | $$$\frac{1}{13}$$$ | $$$\frac{15}{13}$$$ |
$$$S_{2}$$$ | $$$0$$$ | $$$0$$$ | $$$\frac{5}{13}$$$ | $$$1$$$ | $$$\frac{12}{13}$$$ | $$$- \frac{5}{13}$$$ | $$$\frac{120}{13}$$$ |
$$$y$$$ | $$$0$$$ | $$$1$$$ | $$$- \frac{2}{13}$$$ | $$$0$$$ | $$$\frac{3}{13}$$$ | $$$\frac{2}{13}$$$ | $$$\frac{43}{13}$$$ |
La variable entrante es $$$S_{3}$$$, porque tiene el coeficiente más negativo $$$- \frac{29}{13}$$$ en la fila Z.
Basic | $$$x$$$ | $$$y$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | $$$S_{3}$$$ | $$$Y_{1}$$$ | Solución | Ratio |
$$$Z$$$ | $$$0$$$ | $$$0$$$ | $$$- \frac{11}{13}$$$ | $$$0$$$ | $$$- \frac{29}{13}$$$ | $$$M + \frac{11}{13}$$$ | $$$\frac{191}{13}$$$ | |
$$$x$$$ | $$$1$$$ | $$$0$$$ | $$$- \frac{1}{13}$$$ | $$$0$$$ | $$$- \frac{5}{13}$$$ | $$$\frac{1}{13}$$$ | $$$\frac{15}{13}$$$ | $$$\frac{\frac{15}{13}}{- \frac{5}{13}}$$$ (denominador negativo, ignorar) |
$$$S_{2}$$$ | $$$0$$$ | $$$0$$$ | $$$\frac{5}{13}$$$ | $$$1$$$ | $$$\frac{12}{13}$$$ | $$$- \frac{5}{13}$$$ | $$$\frac{120}{13}$$$ | $$$\frac{\frac{120}{13}}{\frac{12}{13}} = 10$$$ |
$$$y$$$ | $$$0$$$ | $$$1$$$ | $$$- \frac{2}{13}$$$ | $$$0$$$ | $$$\frac{3}{13}$$$ | $$$\frac{2}{13}$$$ | $$$\frac{43}{13}$$$ | $$$\frac{\frac{43}{13}}{\frac{3}{13}} = \frac{43}{3}$$$ |
La variable saliente es $$$S_{2}$$$, porque tiene la proporción más pequeña.
Multiplique la fila $$$2$$$ por $$$\frac{13}{12}$$$: $$$R_{2} = \frac{13 R_{2}}{12}$$$.
Basic | $$$x$$$ | $$$y$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | $$$S_{3}$$$ | $$$Y_{1}$$$ | Solución |
$$$Z$$$ | $$$0$$$ | $$$0$$$ | $$$- \frac{11}{13}$$$ | $$$0$$$ | $$$- \frac{29}{13}$$$ | $$$M + \frac{11}{13}$$$ | $$$\frac{191}{13}$$$ |
$$$x$$$ | $$$1$$$ | $$$0$$$ | $$$- \frac{1}{13}$$$ | $$$0$$$ | $$$- \frac{5}{13}$$$ | $$$\frac{1}{13}$$$ | $$$\frac{15}{13}$$$ |
$$$S_{3}$$$ | $$$0$$$ | $$$0$$$ | $$$\frac{5}{12}$$$ | $$$\frac{13}{12}$$$ | $$$1$$$ | $$$- \frac{5}{12}$$$ | $$$10$$$ |
$$$y$$$ | $$$0$$$ | $$$1$$$ | $$$- \frac{2}{13}$$$ | $$$0$$$ | $$$\frac{3}{13}$$$ | $$$\frac{2}{13}$$$ | $$$\frac{43}{13}$$$ |
Agregue la fila $$$3$$$ multiplicada por $$$\frac{29}{13}$$$ a la fila $$$1$$$: $$$R_{1} = R_{1} + \frac{29 R_{3}}{13}$$$.
Basic | $$$x$$$ | $$$y$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | $$$S_{3}$$$ | $$$Y_{1}$$$ | Solución |
$$$Z$$$ | $$$0$$$ | $$$0$$$ | $$$\frac{1}{12}$$$ | $$$\frac{29}{12}$$$ | $$$0$$$ | $$$M - \frac{1}{12}$$$ | $$$37$$$ |
$$$x$$$ | $$$1$$$ | $$$0$$$ | $$$- \frac{1}{13}$$$ | $$$0$$$ | $$$- \frac{5}{13}$$$ | $$$\frac{1}{13}$$$ | $$$\frac{15}{13}$$$ |
$$$S_{3}$$$ | $$$0$$$ | $$$0$$$ | $$$\frac{5}{12}$$$ | $$$\frac{13}{12}$$$ | $$$1$$$ | $$$- \frac{5}{12}$$$ | $$$10$$$ |
$$$y$$$ | $$$0$$$ | $$$1$$$ | $$$- \frac{2}{13}$$$ | $$$0$$$ | $$$\frac{3}{13}$$$ | $$$\frac{2}{13}$$$ | $$$\frac{43}{13}$$$ |
Agregue la fila $$$3$$$ multiplicada por $$$\frac{5}{13}$$$ a la fila $$$2$$$: $$$R_{2} = R_{2} + \frac{5 R_{3}}{13}$$$.
Basic | $$$x$$$ | $$$y$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | $$$S_{3}$$$ | $$$Y_{1}$$$ | Solución |
$$$Z$$$ | $$$0$$$ | $$$0$$$ | $$$\frac{1}{12}$$$ | $$$\frac{29}{12}$$$ | $$$0$$$ | $$$M - \frac{1}{12}$$$ | $$$37$$$ |
$$$x$$$ | $$$1$$$ | $$$0$$$ | $$$\frac{1}{12}$$$ | $$$\frac{5}{12}$$$ | $$$0$$$ | $$$- \frac{1}{12}$$$ | $$$5$$$ |
$$$S_{3}$$$ | $$$0$$$ | $$$0$$$ | $$$\frac{5}{12}$$$ | $$$\frac{13}{12}$$$ | $$$1$$$ | $$$- \frac{5}{12}$$$ | $$$10$$$ |
$$$y$$$ | $$$0$$$ | $$$1$$$ | $$$- \frac{2}{13}$$$ | $$$0$$$ | $$$\frac{3}{13}$$$ | $$$\frac{2}{13}$$$ | $$$\frac{43}{13}$$$ |
Reste la fila $$$3$$$ multiplicada por $$$\frac{3}{13}$$$ de la fila $$$4$$$: $$$R_{4} = R_{4} - \frac{3 R_{3}}{13}$$$.
Basic | $$$x$$$ | $$$y$$$ | $$$S_{1}$$$ | $$$S_{2}$$$ | $$$S_{3}$$$ | $$$Y_{1}$$$ | Solución |
$$$Z$$$ | $$$0$$$ | $$$0$$$ | $$$\frac{1}{12}$$$ | $$$\frac{29}{12}$$$ | $$$0$$$ | $$$M - \frac{1}{12}$$$ | $$$37$$$ |
$$$x$$$ | $$$1$$$ | $$$0$$$ | $$$\frac{1}{12}$$$ | $$$\frac{5}{12}$$$ | $$$0$$$ | $$$- \frac{1}{12}$$$ | $$$5$$$ |
$$$S_{3}$$$ | $$$0$$$ | $$$0$$$ | $$$\frac{5}{12}$$$ | $$$\frac{13}{12}$$$ | $$$1$$$ | $$$- \frac{5}{12}$$$ | $$$10$$$ |
$$$y$$$ | $$$0$$$ | $$$1$$$ | $$$- \frac{1}{4}$$$ | $$$- \frac{1}{4}$$$ | $$$0$$$ | $$$\frac{1}{4}$$$ | $$$1$$$ |
Ninguno de los coeficientes de la fila Z es negativo.
Se alcanza el óptimo.
Se obtiene la siguiente solución: $$$\left(x, y, S_{1}, S_{2}, S_{3}, Y_{1}\right) = \left(5, 1, 0, 0, 10, 0\right)$$$.
Respuesta
$$$Z = 37$$$A se logra en $$$\left(x, y\right) = \left(5, 1\right)$$$A.