INVESTIGACIÓN DE OPERACIONES I

¿Qué hacer en el caso de una minimización?

Hasta ahora nos hemos ocupado del caso de maximización. En problemas de
minimización, la condición de optimalidad requiere seleccionar la variable de entrada
como la variable no básica con el coeficiente objetivo más positivo en la ecuación
objetivo, la regla exacta opuesta del caso de maximización. Esto obedece a que máx z
equivale a mín (-z). En cuanto a la condición de factibilidad para seleccionar la variable
de salida, la regla no cambia.

C o n d i c i ó n d e o p t i m a l i d a d . La variable de entrada en un
problema de minimización es la variable no básica con el coeficiente más positivo en la
fila z. El óptimo se alcanza en la iteración en la cual los coeficientes en la fila z son no
positivos.

C o n d i ci ó n d e facti bilid a d. Tanto en problemas de

maximización como de minimización, la variable de salida es la variable básica
asociada con la relación mínima no negativa con el denominador estrictamente positivo.

Ejemplo
Minimizar z = 5x1 - 4x2 + 6x3 - 8x4
Sujeto a:

SOLUCIÓN ARTIFICIAL INICIAL

Como se demostró en algunos ejemplos anteriores, las PL en las que todas las
restricciones son de la forma ( ) con lados derechos no negativos ofrecen una
conveniente solución factible básica inicial con todas las holguras. Los modelos que
implican restricciones de la forma (=) o ( ) no lo hacen.
El procedimiento para iniciar PLs de “mal comportamiento” con restricciones
(=) y ( ) es utilizar v a r i a b l e s a r t i f i c i a l e s que desempeñan el papel
de holguras en la primera iteración, y que luego se desechan en una iteración posterior.
Aquí se presentan dos métodos estrechamente relacionados: el método M, y el método
de dos fases.

Método M
El método M se inicia con la PL en forma de ecuación. Si la ecuación i no tiene una
holgura (o una variable que pueda desempeñar el papel de una), se agrega una variable
artificial, Ri, para formar una solución inicial parecida a la solución básica de total
holgura. Sin embargo, las variables artificiales no forman parte del problema original, y
se requiere un “artificio” de modelado para igualarlas a cero en el momento en que se
alcance la iteración óptima (suponiendo que el problema tenga una solución factible).
La meta deseada se logra penalizando estas variables en la función objetivo utilizando
la siguiente regla:

1
Regla de penalización para variables artificiales
Dado M, un valor positivo suficientemente grande (matemáticamente (M ), el
coeficiente objetivo de una variable artificial representa una p e n a l i z a c i ó n
apropiada si:

Ejemplo

Si utilizamos x3 como variable de superávit en la segunda restricción y x4 como

variable de holgura en la tercera restricción, el problema en forma de ecuación es

La tercera ecuación tiene su variable de holgura, x4, pero la primera y segunda

ecuaciones no. Por lo tanto, agregamos las variables artificiales R1 y R2 en las primeras
dos ecuaciones y las penalizamos en la función objetivo con MR1 + MR2 (porque
estamos minimizando, en una maximización se restan las penalizaciones). La PL
resultante se da como:

La solución básica inicial es (R1, R2, x4) = (3, 6, 4)

2
Desde un punto de vista de cálculo, la solución del problema con la computadora
requiere que reemplace M con un valor numérico (suficientemente grande). No
obstante, en todos los libros de texto, M se maneja algebraicamente en la tabla simplex.
El resultado es una dificultad agregada innecesaria la cual puede evitarse sustituyendo
un valor numérico apropiado en lugar de M (lo que de cualquier modo tenemos que
hacer cuando usamos la computadora). Nos apartamos de la larga tradición de manejar
M algebraicamente y utilizar una sustitución numérica en su lugar. La intención es,
desde luego, simplificar la presentación sin perder la esencia.
¿Qué valor de M debemos utilizar? La respuesta depende de los datos de la programación
original. Recordemos que la penalización M debe ser lo bastante grande con respecto a los
coeficientes objetivos originales para forzar a las variables originales a ser cero en la solución
óptima.
Al mismo tiempo, como las computadoras son la herramienta principal para resolver PLs, no es
conveniente que M sea innecesariamente grande ya que ello nos puede conducir a un alto costo
computacional. En este ejemplo, los coeficientes objetivo de x1 y x2 son 4 y 1, respectivamente,
y parece razonable establecer M = 100.
Utilizando M = 100, la tabla simplex de inicio se da como sigue (por comodidad, la columna z
se elimina porque no cambia en todas las iteraciones):

Antes de proseguir con los cálculos del método simplex, la fila z debe hacerse
consistente con el resto de la tabla. El lado derecho de la fila z en la tabla en este
momento muestra z = 0.
Sin embargo, dada la solución no básica x1 = x2 = x3 = 0, la solución básica
actual es R1 = 3, R2 = 6 y x4 = 4, la cual da z = 100 x 3 + 100 x 6 + 4 x 0 = 900.
Esta inconsistencia se deriva del hecho de que los coeficientes de R1 y R2 no son
cero (-100, -100) en la fila z.
Para eliminar la inconsistencia, tenemos que sustituir R1 y R2 en la fila z por
medio de la siguiente operación de filas:
Nueva fila z = Anterior fila z + 100 x (fila R1 + fila R2)
Esta operación es la misma que sustituir R1 = 3 - 3x1 - x2 y R2 = 6 - 4x1- 3x2 + x3 en la
fila z.
Por tanto, la tabla modificada es:

3
El resultado es que R1 y R2 ahora se sustituyen (tienen coeficientes cero) en la fila z con
z = 900, como se deseaba.
La última tabla está lista para la aplicación de las condiciones de optimalidad y
factibilidad de simplex, tal como se explicó anteriormente. Dado que la función objetivo
se minimiza, la variable x1 que tiene el coeficiente más positivo en la fila z (= 696) entra
en la solución. La relación mínima de la condición de factibilidad especifica a R1 como
la variable de salida.
Una vez que se han determinado las variables de entrada y de salida, la nueva tabla se
calcula utilizando las conocidas operaciones de Gauss-Jordan.

La última tabla muestra que x1 y R2 son las variables de entrada y de salida,

respectivamente.
Continuando con los cálculos simplex, se requieren dos iteraciones más para alcanzar el
óptimo.
Observe que las variables artificiales R1 y R2 se salen de la solución básica (es decir, se
hacen iguales a cero) en la primera y segunda iteraciones, un resultado que es
consistente con el concepto de penalizarlas en la función objetivo.

Ejercicios.
1. Complete las iteraciones simplex del ejemplo anterior con cálculos manuales y
obtenga la solución óptima.

2. Resolver el siguiente problema de PL usando el método de la M

Maximizar z = x1 + 2x2+x3
Sujeto a:
x1 + x2 +x3= 7
2x1 - 5x2 +x3 10
x1, x2 , x3 0

4
Método de dos fases
En el método M, el uso de la penalización, M, puede conducir a un error de redondeo o
a altos costos computacionales.
El método de dos fases elimina el uso de la constante M. Como su nombre lo indica, el
método resuelve la PL en dos fases; en la fase I se trata de encontrar la solución factible
básica inicial y, si se halla una, se invoca la fase II para resolver el problema original.

Resumen del método de dos fases

F a s e I . Ponga el problema en forma de ecuación y agregue las variables
artificiales necesarias a las restricciones (exactamente como en el método M), para tener
la certeza de una solución básica. A continuación, determine una solución básica de la
ecuación resultante que siempre minimice la suma de las variables artificiales,
independientemente de si la PL es de maximización o minimización. Si el valor mínimo
de la suma es positivo, el problema de PL no tiene una solución factible. De lo
contrario, si el valor mínimo es cero, prosiga con la fase II.
F a s e I I . Use la solución factible de la fase I como una solución factible básica
inicial para el problema original.

Ejemplo

Utilizaremos el mismo ejemplo de minimización que se usó para el método de la M

5
 La tabla asociada es

Como en el método M, R1 y R2 se sustituyen en la fila r mediante las siguientes

operaciones de filas:
Nueva fila r = Anterior fila r + 1x (fila R1 + fila R2)
La nueva fila r se utiliza para resolver la fase I del problema, la cual da por resultado la
siguiente tabla óptima:

Como el mínimo r = 0, la fase I produce la solución factible básica , y

.
En este punto, las variables artificiales ya completaron su misión, y podemos eliminar
sus columnas de la tabla y continuar con la fase II.

Fase II

Después de eliminar las columnas artificiales, escribimos el problema original como:

6
En esencia, la fase I ha transformado las ecuaciones de restricciones originales de tal
forma que proporciona una solución factible básica inicial para el problema, si es que
existe una. La tabla asociada con la fase II del problema es por consiguiente:

Una vez más, como las variables básicas x1 y x2 tienen coeficientes diferentes a cero en
la fila z, deben ser sustituidas, mediante las siguientes operaciones:

La tabla inicial de la fase II es por consiguiente:

Como estamos minimizando, x3 debe entrar en la solución. La aplicación del método

simplex producirá el óptimo en una iteración.

Ejercicio.
Realice los cálculos necesarios para llegar a la solución óptima del ejemplo. Compruebe
que el resultado coincide con el obtenido con el método de la M.