Solución al problema de maximización
En primer lugar, se debe tomar la función objetivo con el contrario de lo que aparece. Debido a que en este caso es minimización, se toma la maximización.
Luego se observa que los signos de las inecuaciones sean del mismo sentido, para el ejemplo todos son ≥, lo que significa que se debe aplicar el signo ≤.
Se toman los bi como variables:
Min Z = 3X1 + 5X2 + 2X3
Sujeto a:
Para este caso:
Max W = 11Y1 + 16Y2
Luego se construyen las restricciones tomando los costos asociados a esas variables, con el signo contrario al inicial y se toman como bi los valores de las variables reales Xi:
Sujeto a:
La primera restricción:
Y1 + 2Y2 ≤ 3
La segunda restricción:
2Y1 + 2Y2 ≤ 5
La tercera restricción:
Y1 + Y2 ≤ 2
Restricción implícita o de no negatividad:
Y1, Y2 ≥ 0
El modelo completo es:
Max W = 11Y1 + 16Y2
Sujeto a:
Se aplica el método simplex y se resuelve. Debido a que hay tres restricciones se hace necesario trabajar con tres variables artificiales y, debido a los signos de las inecuaciones, deben ser de tipo holgura: H1, H2 y H3.
Construcción del estado primal inicial
Max W = 11Y1 + 16Y2 + 0H1 + 0H2 + 0H3
Sujeto a:
La primera tabla, a la que también se le denomina iteración cero, es:
(Para ampliar la imagen haga clic sobre ella)
Se halla la columna pivote que resulta del valor de mayor negatividad del resultado de los Wj - Cj:
Wj = (Cx) X (Yi)
Entonces:
Para Y1 = (0 X 1) + (0 X 2) + (0 X 1)
Para Y2 = (0 X 2) + (0 X 2) + (0 X 1)
Para H1 = ((0 X 1) + (0 X 0) + (0 X 0))
Para H2 = ((0 X 0) + (0 X 1) + (0 X 0))
Para H3 = ((0 X 0) + (0 X 0) + (0 X 1))
Seguidamente se encuentran los Wj - Cj para cada columna:
Para Y1 = ((0 X 1) + (0 X 2) + (0 X 1)) - 11 = -11
Para Y2 = ((0 X 2) + (0 X 2) + (0 X 1)) - 16 = -16
Para H1 = ((0 X 1) + (0 X 0) + (0 X 0)) - 0 = 0
Para H2 = ((0 X 0) + (0 X 1) + (0 X 0)) - 0 = 0
Para H3 = ((0 X 0) + (0 X 0) + (0 X 1)) - 0 = 0
Por último, se encuentra W:
W = (Cx) X (bi)
W = (3 X 0) + (5 X 0) + (2 X 0) = 0
(Para ampliar la imagen haga clic sobre ella)
La variable a entrar es: Y2.
Se elige el renglón pivote que resulta de hallar la razón y escoger el número de menor positividad:
En la fila 1: 3/2 = 1.5
En la fila 2: 5/2 = 2.5
En la fila 3: 2/1 = 2
La variable a salir es H1:
(Para ampliar la imagen haga clic sobre ella)
A continuación, se obtiene el coeficiente pivote que es la intersección de la columna pivote y el renglón pivote.
Iteración cero
(Para ampliar la imagen haga clic sobre ella)
Por medio de la técnica de Gauss-Jordan se convierte el coeficiente pivote en uno y jugando con las filas se convierten los números dos y uno en cero.
Cabe aclarar que el juego de filas es consecuente con el tablero anterior; por ejemplo, en la iteración 1, la F1 corresponde a la F4, la F2 a la F5 y la F3 a la F6.
Iteración uno
Se convierte F4 con Y2 en uno, para lo cual se multiplica F1 por el inverso del coeficiente de Y2 que es (1/2), con lo cual F4 queda de la siguiente manera:
Y1 = 1 X (1/2) = 1/2
Y2 = 2 X (1/2) = 1
H1 = 1 X (1/2) = 1/2
H2 = 0 X (1/2) = 0
H3 = 0 X (1/2) = 0
Xb =Y2 variable que entra.
bi = 3 X (1/2) = 3/2
Se resuelve F5:
Y1 = (1/2 X - 2) + 2 = 1
Y2 = (1 X - 2) + 2 = 0
H1 = (1/2 X - 2) + 0 = - 1
H2 = (0 X - 2) + 1 = 1
H3 = (0 X - 2) + 0 = 0
Xb = H2
bi = (3/2 X - 2) + 5 = 2
Se resuelve F6:
Y1 = (1/2 X - 1) + 1 = 1/2
Y2 = (1 X - 1) + 1 = 0
H1 = (1/2 X - 1) + 0 = - 1/2
H2 = (0 X - 1) + 0 = 0
H3 = (0 X - 1) + 1 = 1
Xb = H3
bi = (3/2 X -1) + 2 = 1/2
Se resuelve Wj - Cj:
Y1 = ((1/2 X 16) + (1 X 0) + (1/2 X 0)) - 11 = - 3
Y2 = ((1 X 16) + (0 X 0) + (0 X 0)) - 16 = 0
H1 = ((1/2 X 16) + (- 1 X 0) + (- 1/2 X 0)) - 0 = 8
H2 = ((0 X 16) + (1 X 0) + (0 X 0)) - 0 = 0
H3 = ((0 X 16) + (0 X 0) + (1 X 0)) - 0 = 0
W = (3/2 X 16) + (2 X 0) + (1/2 X 0) = 24
Se construye la tabla que queda de la siguiente forma:
(Para ampliar la imagen haga clic sobre ella)
Iteración dos
A partir de la iteración anterior se observa si es posible continuar con la solución, para lo cual se observa que en los Wj - Cj todos los valores sean positivos o iguales a cero. En este caso hay un menos tres, lo que indica que se debe continuar con la solución, pues no se ha hallado el óptimo.
Se hallan la columna pivote, el renglón pivote y el coeficiente pivote:
(Para ampliar la imagen haga clic sobre ella)
Por medio de la técnica de Gauss-Jordan se convierte el coeficiente pivote en uno y los números uno y un medio en cero.
La variable a entrar es: Y1.
La variable a salir es: H3.
Cabe aclarar que el juego de filas es consecuente con el tablero anterior; por ejemplo, en la iteración 2, la F4 corresponde a la F7, la F5 a la F8 y la F6 a la F9.
(Para ampliar la imagen haga clic sobre ella)
A partir de la iteración anterior se observa si es posible continuar con la solución, para lo cual se constata si en los Wj - Cj todos los valores son positivos o iguales a cero. Debido a que esta condición se cumple es posible afirmar que se ha hallado el óptimo máximo del problema.
Seguidamente se procede a remplazar los valores resultantes de la iteración 2 (Y2 = 1, H2 = 1 y Y1 = 1) en la ecuación inicial que se encuentra en el estado primal inicial.
Max W = 11Y1 + 16Y2 + 0H1 + 0H2 + 0H3
Sujeto a:
Se remplazan los valores y se revisa que se cumplen en todas las restricciones.
Después de observar que se cumplen todas las restricciones se halla el valor máximo.
Max W = 11Y1 + 16Y2 + 0H1 + 0H2 + 0H3
Donde:
W = 11 X (1) + 16 X (1) + 0 X (1) + 0 x (0) + 0 x (0)
W = 27