Mtodo Simplex de 2 Fases. Esta estrategia algortmica se aplica cuando luego de llevar un modelo de programacin lineal a su forma estndar no se dispone de una solucin bsica factible inicial.Fase 1: Consideramos un problema auxiliar que resulta de agregar tantas variables auxiliares a las restricciones del problema, de modo de obtener una solucin bsica factible. Luego se debe resolver utilizando el Mtodo Simplex un nuevo problema que considera como funcin objetivo la suma de las variables auxiliares. Si el valor ptimo alcanzado al finalizar la Fase 1 es cero ir a la Fase 2. En caso contrario, no existe solucin factible.Fase 2: Resolver a travs del Mtodo Simplex el problema original a partir de la solucin bsica factible inicial hallada en la Fase1.Ejemplo Simplex de 2 FasesConsidere el siguiente modelo de Programacin Lineal:

FASE 1:Al agregar S1 como variable de exceso en la restriccin 1 resulta evidente que no se dispone de una solucin bsica factible inicial, por tanto utilizaremos una variable auxiliar "y" que incluiremos en el lado izquierdo de la restriccin y que servir como variable bsica inicial. Esto define el problema inicial de la Fase 1 junto a su tabla.

Luego la variable X2 entra a la base (costo reducido negativo) y claramente "y" deja la base. Se actualiza la tabla utilizando el mtodo simplex:

Con esta tabla finaliza la Fase 1. Notar que el valor de la funcin objetivo al finalizar la Fase 1 es cero, por tanto podemos continuar la Fase 2.FASE 2:Se elimina la columna asociada a la variable artificial "y" y se actualiza el vector de costos reducidos considerando la funcin objetivo original. De esta forma se obtiene la tabla inicial de la Fase 2.

Dado que X2 es variable bsica al finalizar la Fase 1 buscamos dejar esta misma variable como bsica al iniciar la Fase 2. Para ello multiplicamos por -3 la fila 1 y luego la sumamos a la fila 2.

En este sencillo ejemplo se llega inmediatamente a la tabla final de la Fase 2, con solucin ptima X1=0 y X2=10. El valor ptimo V(P)=-30.

METODO M O DE PENALIZACIN.EL MTODO DE LA GRAN M (PENALIZACIN)El mtodo de la gran M consiste en modificar el problema original para dar lugar a un nuevo problema agregando una variableLlamada artificial y que se penalizara mediante un costoMde valores grandes y positivos, y esto permite que la funcin objetivo tome valores muy grandes.CuandoWsalga de la base en ese momentoW=0 y esto indica haber regresado al problema original, pero si se llega aW>0, entonces el problema no tendr solucin.MinZ= Cx+ MwSujeta a las restricciones y penalizando a Zw1- Cw Condicin de introduccin de las variablesRestriccin>restaRestriccin=) o (=). Estas variables se denominan variables artificiales y su adicin hace que las restricciones correspondientes.Esta dificultad se elimina asegurando que las variables sean 0 en la solucin final. Esto se logra asignando una penalizacin muy grande por unidad a estas variables en la funcin objetivo. Tal penalizacin se designar como M para problemas de maximizacin y +M para problemas de minimizacin.3. Utiliza las variables artificiales en la solucin bsica inicial; sin embargo la funcin objetivo de la tabla inicial se prepara adecuadamente para expresarse en trminos de las variables no bsicas nicamente. Esto significa que los coeficientes de las variables artificiales en la funcin objetivo deben ser 0 un resultado que puede lograrse sumando mltiplos adecuados de las ecuaciones de restriccin al rengln objetivo.4. Proceda con los pasos regulares del mtodo simplex.EJEMPLO:Minimizar Sujeto a:

Minimizar Sujeto a:

Minimizar Sujeto a:

Minimizar Sujeto a:V.B.ZX1X2X3S1S2R1Solucin

Z1-3-2-400-M0

R10223-10115

S2023101012

V.B.ZX1X2X3S1S2R1Solucin

Z1-3+2M-2+2M-4+3M-M0015M

R10223-10115

S2023101012

Criterio para seleccionar la variable entrante:Maximizacin: El valor mayor negativo del rengln Z.Minimizacin: El valor mayor positivo del rengln Z.V.B.ZX1X2X3S1S2R1Solucin

Z1-1/32/30-4/304/3-M20

X302/32/31-1/301/35

S204/37/301/31-1/37

V.B.ZX1X2X3S1S2R1Solucin

Z1-5/700-10/7-2/710/7-M18

X302/701-3/7-2/73/73

X204/7101/73/7-1/73

Mtodo Simplex Revisado.El mtodo del simplex expuesto, que se denomina bsico, se desarrolla a travs de cada iteracin transformando completamente una sucesin de tableros al ir cambiando de base. Teniendo en cuenta que muchos de estos clculos no hacen falta para la determinacin de cada nueva base y basados en el algoritmo del simples revisado, el cual es realmente un esquema de ordenacin de los clculos que se llevan a cabo con el mtodo del simplex bsico, prescindiendo y evitando aquellos que sean innecesarios en relacin con la solucin final del problema. El inconveniente de este mtodo es que por la forma en que se lleva a cabo induce ms fcilmente a errores en los clculos a mano que el simplex bsico, aspecto que evidentemente no ocurre si est implementado en computador.En el mtodo del simplex revisado partimos como en el bsico, del problema lineal en forma estndar:MAX Z =cxSujeta a: A x = b

x0Dada la base factible B, hay que evaluar si alguna variable no bsicaXjpuede entrar a la base para mejorar la funcin objetivo; para ello utilizamos el costo reducido:ZjCj=CBBajCjEl vectorCBest formado por los coeficientes de la funcin objetivo de las variables y Baj representa el vectorajen trminos de la actual base. El mtodo del simplex revisado no cambia los vectores yj en cada tabla como el bsico, sino que utiliza siempre el vector aj inicial con los multiplicadores de los simples:S=CBBQue si cambian con la base. Es claro que se alcanza una solucin ptima cuando:SaJ-CJ0 para todo jLa seleccin de la variable de salida se hace con el mismo criterio que en el simplex bsico: si Xkes la variable seleccionada para entrar a la base, la columna pivote esBaky los valores actuales de las variables bsicasBb.Se aplica la regla de la mnima razn a estos elementos, que dando as determinada la variableXrque sale de la base. Finalmente, la nueva matriz bsica se obtiene sustituyendo la columna ar por laaken la anterior matriz B. Ejemplo:MAX Z = 2X1+X2+ 3X3Con sus restricciones:

Resolver el anterior problema de Programacin Lineal aplicando el Mtodo Simplex Revisado.Solucin analtica:Agregamos variables de holguraX4yX5a cada restriccin con coeficientes cero (0) en la funcin objetivo para tener el problema en la forma estndar; la base inicial B y el vectorCBson:

Z1 C1 = 2; Z2 C2 = 1; Z3 C3 = 3El valor que ms se aleja de cero (0) por la izquierda esZ3C3:X3es la variable que entra a la base; la razn mnima es 8/2, luego S2 es la variable que sale de la base.Las variables bsicas son ahora (S1,X3) con matriz bsica (sustituyendoa5pora3):

CB= (0 3);S= (0, 3/2) y los indicadores de las variables no bsicas son:Z1C1= 3/2 2 = 1/2;Z2C2= 9/2 1 = 7/2;Z3C3 = 3/2 0 = 3/2 yX1 es la variable que entra a la base; para determinar la variable de salida calculamos:Bb = (3,4) yBa1= (5/2,1/2); la razn mnima es 6/5, luegoX4es la variable que sale de la base.Las variables bsicas son ahora (X1,X3) y la nueva matriz bsica (reemplazando en la anteriora4pora1) es:

CB= (2 3);S= (1/5, 7/5) y los indicadores de las variables no bsicas son:Z2C2= 23/5 1 = 18/5;Z4C4= 1/5 0 = 1/5;Z5C5= 7/5 0 = 7/5 y al ser todos positivos se ha alcanzado la optimalidad. La solucin ptima es:XB= (X1,X3) =Bb = ( 1.2, 3.4)Solucin ptima nica:X*1= 1,2;X*2= 0;X*3= 3,4;S*1= 0;S*2= 0;Z* = 12,6.

Mtodo Dual Simplex.Elmtodo simplex dualresulta ser una estrategia algortmica eficiente cuando luego de llevar un modelo de programacin lineal a su forma estndar, la aplicacin del mtodo simplex no es inmediata o ms bien compleja, por ejemplo, puede requerir la utilizacin delmtodo simplex de 2 fases.Una aplicacin tpica del mtodo simplex dual es en la resolucin de problemas con una funcin objetiva de minimizacin, con restricciones del tipo mayor o igual y donde las variables de decisin son mayores o iguales a cero.Ejemplo Simplex DualConsidere el siguiente modelo de Programacin Lineal:

Paso 1: Se lleva el modelo a su forma estndar. En nuestro ejemplo esto se logra agregando variables de exceso en cada una de las restricciones (3 primeras: S1, S2, S3, respectivamente). Luego, se multiplica cada fila de las restricciones por -1 de modo de disponer una solucin bsica inicial (infactible) en las variables de exceso S1, S2 y S3. De esta forma se obtiene la siguiente tabla inicial.ABCS1S2S3

-15-2-1100-200

-7,5-3-1010-150

-5-2-1001-120

315110500000

Paso 2: Se selecciona el lado derecho "ms negativo" lo cual indicar cul de las actuales variables bsicas deber abandonar la base. En el ejemplo el lado derecho ms negativo se encuentra en la primera fila, por tanto S1 deja la base. Para determinar cul de las actuales variables no bsicas (A, B, C) entrar a la base se busca el mnimo de {-Yj/aij} donde aij es el coeficiente de la respectiva variable no bsica en la fija i (del lado derecho ms negativo, marcado en verde) y donde Yj es el costo reducido de la respectiva variable no bsica. De esta forma se obtiene: Min {-315/-15, -110/-2, -50/-1} = 21, donde el pivote (marcado en rojo) se encuentra al hacer el primer cociente, por tanto A entra a la base.Paso 3:Se actualiza la tabla anterior siguiendo un procedimiento similar al utilizado en elMtodo Simplex. En el ejemplo se debe dejar a la variable A como bsica y S1 como no bsica. La tabla que resulta es la siguiente:ABCS1S2S3

12/151/15-1/150040/3

0-2-1/2-1/210-50

0-4/3-2/3-1/301-160/3

068292100-4.200

Paso 4: Continuar las iteraciones y siguiendo el mismo procedimiento hasta disponer de una solucin bsica factible. Luego de unas iteraciones se obtiene la siguiente tabla final:

ABCS1S2S3

100-1/1001/108

0101/4-13/410

00102-360

00041036-6.620

La solucin ptima esA=8,B=10,C=60(marcado en verde) con valor ptimoV (P)=6.620(marcado en rojo - se obtiene con signo cambiado). Tambin es interesante notar que los costos reducidos de las variables artificiales S1, S2 y S3 (marcado en amarillo), corresponde a la solucin ptima del modelo presentado en eltutorial de solver, esto dado que dicho modelo resulta ser elproblema dualde nuestro ejemplo.

Anlisis de SensibilidadElanlisisde sensibilidad busca determinar los efectos que se producen en lasolucinptima al realizar cambios en cualquiera de losparmetrosdel modelo deprogramacinlineal planteado inicialmente. Entre los cambios que se investiganestn: los cambios en los coeficientes de lasvariables en lafuncinobjetivo tanto para variablesbsicascomo para las variables nobsicas, cambios en los recursos disponibles de las restricciones,variacinde los coeficientes deutilizacinen las restricciones eintroduccinde una nuevarestriccin.A modo general, cuando se realiza unanlisisde sensibilidad a unasolucinptima se debe verificar cadaparmetrode forma individual,dgaselos coeficientes de lafuncinobjetivo y los lmites de cada una de las restricciones. En ese sentido se plantea el siguiente procedimiento:

1. Revisindel modelo: se realizan los cambios que se desean investigar en el modelo.2. Revisinde la tabla finalSimplex: se aplica el criterio adecuado para determinar los cambios que resultan en la tabla finalSimplex.3. Conversina la forma apropiada deeliminacinGauss: se convierta la tabla en la forma apropiada para identificar y evaluar lasolucinbsicaactual, para lo cual se aplica lametodologadeeliminacinGauss si es necesario.4. Prueba de factibilidad: se prueba lafactibilidadde estasolucinmediante laverificacinde que todas las variablesbsicasde la columna del lado derecho aun tengan valores no negativos.5. Prueba de optimalidad: se verifica si estasolucines ptima y factible, mediante lacomprobacin de que todos los coeficientes de las variables nobsicasdelreglnZpermanecen no negativos.6. Re optimizacin: si estasolucinno pasa una de las pruebas indicadas en los puntos 4 y 5 anteriores, se procede a buscar la nuevasolucinoptima a partir de la tabla actual como tablaSimplexinicial, luego de aplicadas las conversiones de lugar, ya sea con elmtodoSimplexo elSimplexDual.Mtodo de Transporte.El modelo de transporte busca determinar un plan de transporte de una mercanca de varias fuentes a varios destinos. Los datos del modelo son:Nivel de oferta en cada fuente y la cantidad de demanda en cada destino.El costo de transporte unitario de la mercanca a cada destino.Como solo hay una mercanca un destino puede recibir su demanda de una o ms fuentes. El objetivo del modelo es el de determinar la cantidad que se enviar de cada fuente a cada destino, tal que se minimice el costo del transporte total.La suposicin bsica del modelo es que el costo del transporte en una ruta es directamente proporcional al nmero de unidades transportadas. La definicin de unidad de transporte variar dependiendo de la mercanca que se transporte.EJERCICIOTres empresas suministran ordenadores a cuatro detallistas. La cantidad de demanda semanal de los cuatro detallistas es de 150, 150, 400 y 100 ordenadores respectivamente. La oferta de las tres empresas esta dictada por la mano de obra regular disponible y se calcula en 250, 300 y 250 unidades a la semana. El costo en euros del transporte por unidad viene detallado en la siguiente tabla.

TABLA DE COSTOS

VARIABLES DEDECISIN:Xij, Donde i= Numero de empresas. j= Numero de Detallistas.Cij= Costos del transporte.i:1-3.j: 1-4.

FORMAESTNDARDEPROGRAMACINLINEAL:Funcin Objetivo:Min:Z= X11C11+ X12C12+ X13C13 +X14C14 +X21C21 + X22C22 +X23C23 +X24C4 +X31C31 +X32C32 +X33C33 +X34C34. Reemplazando el valor de Cij con los valores de tabla de costos:Min: Z=10X11 +20X12 +30X13 +20X14 +20X21 +40X22 +10X23 +20X24 +10X31 +30X32 +50X33 +30X34.

RESTRICCIONES

OFERTA:X11+X12+X13+X14