SOLART- CASPAR

Vista previa del material en texto

Programación Lineal
Restricciones ≥ o = Minimización
Variables de holgura, de superávit y no restringidas
Variable de holgura: Para las restricciones del tipo ( ). 
El lado derecho representa el límite de la disponibilidad de un recurso y el lado izquierdo: el empleo que hacen de ese recurso limitado las diferentes actividades. Entonces, la holgura representa la cantidad sobrante del recurso, de acuerdo al empleo que le dan las actividades.
Variable de superávit: Las restricciones del tipo ().
En general determinan requerimientos mínimos de especificaciones. Un superávit representa el exceso del lado izquierdo, sobre ese requerimiento mínimo. Un valor positivo de esta variable significa que se producirá una cantidad excedente.
Variable no restringida: Situaciones en las cuales una variable puede asumir cualquier valor, negativo o positivo
Solución Inicial Artificial
¿Cómo encontrar una solución básica inicial para los modelos que incluyen restricciones de (=) y ()?
El procedimiento es utilizar variables artificiales.
El Método de la M
Comienza con la PL en forma estándar. En toda ecuación i que tenga restricciones de (=) y (), se agrega una variable artificial Ri. 
Al ser ajenas al modelo les asignamos una penalidad en la función objetivo, para obligarlas a un nivel cero en una iteración posterior del algoritmo simplex. Debido a que M es un valor positivo suficientemente grande, la variable Ri es penalizada en la función objetivo utilizando -MRi en el caso de una maximización y +MRi en el caso de una minimización.
El Método de la M
Observaciones: 
1.-El empleo de la penalidad M puede no forzar a la variable artificial al nivel cero en la iteración simplex final. Esto es una indicación de que el problema no tiene una solución factible. 
 2.- La aplicación de esta técnica requiere M . Sin embargo, desde el punto de vista de utilizar la computadora; M debe ser finita y “suficientemente grande” para actuar como una penalidad, pero que no desequilibre la exactitud de los cálculos del simplex.
Ej: Problema de Minimización con restricción de  y de =
Min z = 4x1 + x2 
sujeto a:
1. 3 x1 + x2 = 3
2. 4 x1 + 3 x2  6
3. x1 + 2 x2  4
 x1  0 , x2  0 
Forma estándar
Min Z= 4x1 + x2 + 0x3 + 0 x4
s. a 3 x1 + x2 = 3
 4 x1 + 3 x2 - x3 = 6
	 x1 + 2 x2 + x4 = 4
 x1 , x2 , x3 , x4  0
Restricción de igualdad no tiene variable básica
Las variables básicas no pueden ser negativas
La primera y segunda ecuaciones no pueden ser variables básicas, por consiguiente se utilizarán las variables artificiales R1 y R2, resultando:
Min Z= 4x1 + x2 + 0x3 + 0 x4 + MR1 + MR2
sujeto a
 3 x1 + x2 + R1 = 3
 4 x1 + 3 x2 - x3 + R2 = 6
	 x1 + 2 x2 + x4 = 4
 x1 , x2 , x3 , x4, R1, R2  0
	SBF	x1 x2	 x3 R1 R2 x4 Solución	 	 	z -4 -1 0 -M -M 0 0	
 R1 3 1 0 1 0 0 3
 R2 	4 3 -1 0 1 0 6
 x4	1 2 0 0 0 1 4 
Se agrega una variable artificial para que sea básica
Se las penaliza en la función objetivo
Primero se debe transformar las variables básicos a 0 y 1
Después se continua con el método simplex
Tomamos: M =100
Continuar iterando hasta encontrar el optimo
Con M = 100
Convierto a variables básicas
La mas positiva porque estoy minimizando
Forma estándar de PL 
Conversión de una variable no restringida a variables
 no negativas
Una variable xj no restringida se puede expresar en términos de dos variables no negativas, utilizando la sustitución:
			xj = xj+ - xj- 
donde xj+, xj-  0
Ejemplo:
Min z = 2x1 + 3 x2 
sujeto a:				Reemplazando
1. x1 + x2 = 10	 (x1+ - x1-) + x2 = 10	
2. 2 x1 - 3 x2  5		2 (x1+ - x1-) - 3 x2  5	
3. 7 x1 - 4 x2  6		7 (x1+ - x1-) - 4 x2  6	
 x1 irrestricta , x2  0 	 x1+ ; x1- ; x2  0 
El Método de dos fases
Fase I. Expresar el problema en la forma estándar y añadir las variables artificiales necesarias (como en el método M) para obtener una solución básica inicial. Encontrar una solución básica de las ecuaciones resultantes que minimice la suma de las variables artificiales. Si el valor mínimo de la suma es positivo, el problema de PL no tiene una solución factible, lo que termina el proceso de solución. De lo contrario se avanza a la Fase II
Fase II. Utilizar la solución factible obtenida en la Fase I como solución factible inicial para el problema original. ___________________________________
Ej. Min r = R1 + R2 
sujeto a
 3 x1 + x2 + R1 = 3
 4 x1 + 3 x2 - x3 + R2 = 6
	 x1 + 2 x2 + x4 = 4
 x1 , x2 , x3 , x4 , R1 , R2  0
Otros métodos de resolución de programas de PL
El MS constituye el algoritmo de resolución de PL más difundido. Tiene modificaciones que lo hacen más eficiente. 
Explora el recinto de soluciones factibles por los extremos del poliedro. Es un algoritmo de naturaleza exponencial en lo que se refiere el nº de iteraciones necesario para arribar a la solución óptima.
Existen otros métodos que son de naturaleza polinomial y que se llaman de punto interior. Estos atraviesan el recinto internamente. El primero fue el denominado elipsoidal (Khachiyan 1979); en 1984 N. Karmarkar desarrolló un método aplicable a problemas de gran envergadura
Interés: 
Explicar teóricamente la razón de estas situaciones 
 Dar una interpretación práctica del significado de estos resultados
Uso en análisis de sensibilidad.
Casos
Degeneración . 
Soluciones múltiples (alternativas) 
Soluciones no acotadas (poliedro abierto) 
Soluciones inexistentes 
Casos especiales en la aplicación del Método Simplex
Degeneración 
Las soluciones básicas son aquellas que tienen por lo menos “n-m” variables iguales a cero.
 Las soluciones básicas “convencionales” tienen exactamente “n-m” variables nulas. Puede ocurrir que las soluciones básicas tengan variables nulas. En ese caso se dice que las soluciones son “degeneradas” o degradadas. 
Por lo menos una restricción es redundante. SE DETECTA EN LA BASE ANTERIOR AL OBSERVAR UN EMPATE EN LA RAZÓN MÍNIMA
Empate en la variable que sale
8/4 =2
4/2 =2
Variable básica = 0
Degeneración 
Si elijo la otra variable
2. Soluciones múltiples (alternativas) 
Cuando la función objetivo es paralela a una restricción que se satisface como ecuación, la función objetivo asumirá el mismo valor óptimo en más de un punto. 
SE DETECTA QUE SE HA LLEGADO A UNA SOLUCIÓN ALTERNATIVA CUANDO HABIENDO LLEGADO AL ÓPTIMO, HAY ALGÚN ZJ-CJ CORRESPONDIENTE A VARIABLE NO BÁSICA IGUAL A CERO. 
Se llama cero alternativo y se indica 0*. Se procede a ingresar a la base la variable que tiene el 0* y se saca la que corresponda. 
Las soluciones óptimas son infinitas y se expresarán como combinación lineal de los vértices del segmento solución 
X = X(A). + X(B). (1- ); siendo 0≤≤1
2. Soluciones múltiples (alternativas) 
La solución es unacombinación lineal de los puntos extremos del segmento
Casos especiales en la aplicación del Método Simplex
Soluciones no acotadas (poliedro abierto) 
Los valores de las variables se pueden incrementar indefinidamente sin violar ninguna restricción, lo que significa que el espacio es no acotado por lo menos en una dirección. 
Podría indicar una incorrecta formulación debido a la no inclusión de alguna restricción o valores incorrectos de los parámetros. 
SE IDENTIFICA CUANDO NO HABIENDO LLEGADO AL ÓPTIMO, NO EXISTE NINGÚN COCIENTE Bi/Aij NO NEGATIVO
Casos especiales en la aplicación del Método Simplex
Soluciones inexistentes 
Cuando las restricciones no se satisfacen simultáneamente (nunca puede ocurrir si todas las restricciones son del tipo ). Indica un problema en la formulación. 
SE IDENTIFICA PORQUE HAY AL MENOS UNA VARIABLE ARTIFICIAL EN UNA BASE QUE YA NO SE PUEDE MEJORAR.
M=100
Observación: En el optimo hay una variable artificial INFACTIBLE
3
2
11,54
3
2
11,54
X1=2,5X1=3
Xopt = 
a*
X2=0 + (1-
a)
*X2=1
X3=0X3=0
X4=1,5X4=0
Basicax1x2x3x4RSolucion
z-3-200-M0
x3211002
R340-1112