Metodo de la gran M

Método de la gran M
Recuerde que el algoritmo simplex requiere una sfb inicial. En todos los problemas que se han resuelto hasta ahora se determino una sfb inicial usando las variables de holgura como si fueran variables físicas. Pero si un PL tiene alguna restricción ≥ o de igualdad, no sería tan evidente una sfb inicial. Mediante el ejemplo 4 se ilustra cuán difícil podría ser encontrar unasfb. Cuando una sfb no es evidente, el método de la gran M (o el método simplex de dos fases de selección) se podría explicar para resolver el problema. En esta sección se trata el método de la gran M, una versión del algoritmo simplex que determina primero un sfb mediante la suma de variables “artificiales” al problema. Naturalmente, la función objetivo de PL original se tiene que modificar paraque las variables artificiales sean iguales a cero en la conclusión del algoritmo simplex. El ejemplo siguiente ilustrara el método de la gran M.
Ejemplo 4 Bevco
Bevco elabora una bebida carbonatada sabor naranja que se llama Oranj mediante la combinación de agua carbonatada de naranja y jugo de naranja. Cada onza de agua carbonatada de naranja contiene 0.5 onzas de azúcar y 1 mg de vitamina C.Cada onza de jugo de naranja contiene 0.25 onzas de azúcar y 3 mg de vitamina C. Bevco gasta 2 centavos pro producir 1 onza de agua carbonatada de naranja y 3 centavos para producir 1 onza de jugo de naranja. El departamento de mercadotecnia de Bevco decidió que la botella de 10 onzas de Oranj debe contener por lo menos 20 mg de vitamina C y muchas 4 onzas de azúcar. Utilize la programación linealpara determinar como Bevco puede cumplir los requisitos del departamento de mercadotecnia a un costo mínimo.
Solución: sea
X1=cantidad de onzas de agua carbonatada de naranja en una botella de Oranj.
X2=cantidad de onzas de jugo de naranja en una botella de Oranj.
Entonces, el PL apropiado es
min⁡〖z=2x1+3x2〗
s.a 1/2 x1+1/4x2≤4(restriccion del azucar)
x1+3x2≥20(restriccion de la vitamina C)


s.a x1+x2=10(10 oz en una botella de oranj)
x1,x2≥0
(La solución se obtiene después en esta misma sección)
Para transformar a (17) en la forma estándar se agrega una variable de holgura s1 a la restricción del azúcar y se resta una variable deexcedente e2 de la restricción de la vitamina C. después de escribir la función objetivo como z-2x1-3x2=0 se obtiene forma estándar siguiente:
Renglon 0:z-〖2x〗_1-〖3x〗_2=0
Renglon 1:1/2 x_1-1/4 x_2+s_1=4
Renglon 2:x_1-〖3x〗_2-e_2=20
Renglon 3:x_1+x_2=10
Todas las variables son no negativas
En la búsqueda de una sfb se observa que s1=4 se podrá utilizar la variable básica (y factible) para elrenglón 1. Si se multiplica 2 por -1, entonces e2=-20 se podría usar como una variable básica en el renglón 2. Desafortunadamente, e2=-20 viola la restricción del signo e2 ≥ 0. Por último, no son evidentes las variables básicas en el renglón 3. Por lo tanto con el objeto de usar el algoritmo simplex para resolver (17), los renglones 2 y 3nesesitan cada una de las variables básicas (y factibles). Parasolucionar este problema, se “inventa” simplemente una variable básica factible por cada limitación que necesite una. Como nosotros creamos estas variables y no son variables reales, las llamamos variables artificiales. Si una variable artificial se suma en el renglón i, le denominamos ai. En el problema actual se requiere añadir una variable artificial a2 al renglón 2 y una variable artificial a3al renglón 3. El conjunto de ecuaciones resultantes es
z-2x_1-3x_2=0
1/2 x_1-1/4 x_2+s_1=4
x_1-〖3x〗_2-e_2+a_2=20
x_1+x_2+a_2=10
Entonces tiene una sfb: z=0, s1=4, a2=20, a3=10. No hay garantía desafortunadamente, de que esa solución optima en la cual una o más variables artificiales son positivas. Tal solución podría no ser factible en el problema original (17). Por ejemplo, al...