Metodo Simplex

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
3
2
1 1,5 4
Mario
Resaltado
Si maximizamos, iria restando
Continuar iterando hasta encontrar el optimo
3
2
1 1,5 4
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:
1) Explicar teóricamente la razón de estas situaciones
2) Dar una interpretación práctica del significado de estos resultados
3) Uso en análisis de sensibilidad.
Casos
1. Degeneración .
2. Soluciones múltiples (alternativas)
3. Soluciones no acotadas (poliedro abierto)
4. Soluciones inexistentes
Casos especiales en la aplicación del Método Simplex
1. 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
1. 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)
X1 = 2,5 X1 = 3
Xopt = * X2 = 0 + (1-)* X2 = 1
X3 = 0 X3 = 0
X4 = 1,5 X4 = 0
La solución es una combinación lineal de los puntos extremos del segmento
Casos especiales en la aplicación del Método Simplex
3. 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
4. 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.
Basica x1 x2 x3 x4 R Solucion
z -3 -2 0 0 -M 0
x3 2 1 1 0 0 2
R 3 4 0 -1 1 12
M=100
Observación: En el optimo hay una variable artificial INFACTIBLE