METODO SIMPLEX 02 DE MARZO 2024

 El método simplex

es un algoritmo utilizado para resolver problemas de programación lineal. Aquí Hay un ejemplo resuelto paso a paso:

Problema: Maximizar $�=3{�}_1+2{�}_2$ sujeto a:

$$\begin{array}{rl}{\displaystyle \mathrm{<span\; style="background-color:\; white;">2</span>}{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">1</span>}}<span\; style="background-color:\; white;">+</span>{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">2</span>}}}& {\displaystyle <span\; style="background-color:\; white;">\le </span>\mathrm{<span\; style="background-color:\; white;">20</span>}}\\ {\displaystyle <span\; style="background-color:\; white;">-</span>\mathrm{<span\; style="background-color:\; white;">4</span>}{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">1</span>}}<span\; style="background-color:\; white;">+</span>\mathrm{<span\; style="background-color:\; white;">5</span>}{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">2</span>}}}& {\displaystyle <span\; style="background-color:\; white;">\le </span>\mathrm{<span\; style="background-color:\; white;">10</span>}}\\ {\displaystyle {\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">1</span>}}<span\; style="background-color:\; white;">,</span>{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">2</span>}}}& {\displaystyle <span\; style="background-color:\; white;">\ge </span>\mathrm{<span\; style="background-color:\; white;">0</span>}}\end{array}$$

Paso 1: Convertir el problema a una forma estándar:

El primer paso en el método simplex es convertir el problema en una forma estándar. Esto implica agregar variables de holgura o exceso para convertir todas las desigualdades en ecuaciones, y asegurar que todas las variables sean no negativas.

Entonces, el problema se convierte en:

Maximizar $�=3{�}_1+2{�}_2$ sujeto a:

$$\begin{array}{rl}{\displaystyle \mathrm{<span\; style="background-color:\; white;">2</span>}{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">1</span>}}<span\; style="background-color:\; white;">+</span>{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">2</span>}}<span\; style="background-color:\; white;">+</span>{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">3</span>}}}& {\displaystyle <span\; style="background-color:\; white;">=</span>\mathrm{<span\; style="background-color:\; white;">20</span>}}\\ {\displaystyle <span\; style="background-color:\; white;">-</span>\mathrm{<span\; style="background-color:\; white;">4</span>}{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">1</span>}}<span\; style="background-color:\; white;">+</span>\mathrm{<span\; style="background-color:\; white;">5</span>}{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">2</span>}}<span\; style="background-color:\; white;">+</span>{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">4</span>}}}& {\displaystyle <span\; style="background-color:\; white;">=</span>\mathrm{<span\; style="background-color:\; white;">10</span>}}\\ {\displaystyle {\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">1</span>}}<span\; style="background-color:\; white;">,</span>{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">2</span>}}<span\; style="background-color:\; white;">,</span>{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">3</span>}}<span\; style="background-color:\; white;">,</span>{\mathrm{<span\; style="background-color:\; white;">�</span>}}_{\mathrm{<span\; style="background-color:\; white;">4</span>}}}& {\displaystyle <span\; style="background-color:\; white;">\ge </span>\mathrm{<span\; style="background-color:\; white;">0</span>}}\end{array}$$

Paso 2: Construir la tabla simplex inicial:

Iteración	${�}_1$	${�}_2$	${�}_3$	${�}_4$	zmax
${�}_3$	2	1	1	0	20
${�}_4$	-4	5	0	1	10
$�$	3	2	0	0	0

Paso 3: Determinar la variable de entrada y salida:

Para determinar la variable de entrada, seleccionamos la columna con el coeficiente más negativo en la fila $�$, que en este caso es ${�}_1$. Para determinar la variable de salida, calculamos el cociente de los valores en la columna de resultados (RHS) dividido por los valores correspondientes en la columna ${�}_1$, y seleccionamos la fila con el cociente más pequeño, que es la primera fila.

Paso 4: Realizar operaciones de pivote:

En este paso, realizamos operaciones de fila para hacer que el elemento ${�}_1$ en la fila ${�}_3$ sea igual a 0 y convertirlo en un 1.

Multiplicamos la fila ${�}_3$ por $1\mathrm{/}2$ y la suma con la fila ${�}_4$ para hacer 0 en ${�}_1$ en la fila ${�}_4$. Luego, multiplicamos la fila ${�}_3$ por $-1$ y la suma con la fila $�$ para hacer 0 en ${�}_1$ en la fila $�$.

La tabla después del pivote será:

Iteración	${�}_1$	${�}_2$	${�}_3$	${�}_4$	zmax
${�}_3$	1	0.5	0.5	0	10
${�}_1$	0	1.5	-0.5	0.25	5
$�$	0	-1	1.5	-1.5	30

Paso 5: Determinar la variable de entrada y salida (nueva iteración):

La variable de entrada será ${�}_2$ y la variable de salida será ${�}_3$.

Paso 6: Realizar operaciones de pivote (nueva iteración):

Multiplicamos la fila ${�}_2$ por $2\mathrm{/}3$ y la suma con la fila ${�}_3$ para hacer 0 en ${�}_2$ en la fila ${�}_3$. Luego, multiplicamos la fila ${�}_2$ por $-1$ y la suma con la fila $�$ para hacer 0 en ${�}_2$ en la fila $�$.

La tabla después del pivote será:

Iteración	${�}_1$	${�}_2$	${�}_3$	${�}_4$	c
${�}_3$	1	0	1	-0.25	5
${�}_2$	0	1	-0.333	0.167	3.333
$�$	0	0	2	-2	24

Como no hay coeficientes negativos en la fila $�$, hemos alcanzado la solución óptima.

Entonces, la solución óptima es $�=24$ cuando ${�}_1=5$, ${�}_2=3.333$, ${�}_3=0$ y ${�}_4=0$.