Clase 03_Lindo_simplex

Vista previa del material en texto

Investigación de Operaciones FIGMM
Casos especiales en el Método Geométrico 
Se presentan los siguientes casos(igual se presentara en el método simplex) Estos casos son: 
- Degeneración 
- Opciones óptimas 
- Soluciones no acotadas 
- Soluciones no existentes (o no factibles)
Casos de degeneración 
• En este caso se presenta cuando en la solución óptima una de las variables básicas (o de decisión) toma un valor estrictamente igual a cero. 
• Esta condición revela que el modelo tiene por lo menos una restricción redundante.
Ejemplo: 
F.O. Max Z = 3x1 + 9x2 s.a. 
x1 + 4x2 ≤ 8 
x1 + 2x2 ≤ 4 
X1,x2 >=0
Solucion
Casos de opciones óptimas 
• Este caso se 
presenta cuando 
la función 
objetivo es 
paralela a una 
restricción. 
Entonces la 
función óptima 
tomará el 
mismo valor 
óptimo en más 
de un punto. 
Ejemplo: 
F.O. Max Z = 2x1 +4 x2 s.a. 
x1 + 2x2 <= 5 
x1 + x2 <= 4 
x1, x2 ≥ 0
Solucion
Casos de solución no acotada 
• En algunos modelos los valores de las variables pueden aumentar en forma indefinida sin violar ninguna de las 
restricciones. 
• Esto significa que el espacio de soluciones es no acotado cuando menos el alguna dirección.
Casos de solución no acotada 
• Como resultado la función objetivo puede crecer (caso de maximización) o decrecer (caso de minimización) en forma indefinida. 
• Las irregularidades más probables para que un modelo sea no acotado son: 
•No se determinan adecuadamente algunos parámetros en alguna restricción. 
•No se toman en cuenta una o más restricciones redundantes.
Ejemplo: 
F.O. Max Z = 2x1 + x2 s.a. 
x1- x2 <= 10 
2x1 <= 40 
x1, x2 ≥ 0
Solucion
Casos de solución no factible 
• Este caso se presenta en un modelo de programación lineal cuando las restricciones no se pueden cumplir simultáneamente 
• Este caso no ocurre si todas las restricciones son del tipo ≤ 
• Esto quiere decir que el modelo no se ha formulado correctamente
Ejemplo: 
F.O. Max Z = 3x1 +2 x2 s.a. 
2x1 + x2 <= 2 
3x1 +4x2 ≥ 12 
x1, x2 ≥ 0
Solucion
3. Solución de Problemas utilizando el método Simplex
3.Solución de Problemas 
de PL. con el Simplex 
• A continuación se darán algunos enfoques para resolver problemas con mayor cantidad de variables y restricciones, que no se pueden resolver por el método geométrico. 
• Luego se resolverán los problemas con el software Lindo o Tora. 
• Se dará una pequeña guía para trabajar con el software respectivo.
3.1 Utilización del software 
• Cualquier modelo de programación lineal se puede resolver haciendo uso de herramientas computacionales. 
• El software, cualquiera que sea, hace uso de iteraciones consecutivas. 
• Estas iteraciones se hacen alrededor de los puntos críticos. (vértices de la región factible)
3.1 Utilización del software 
• Mediante el proceso iterativo el software lo que hace es recorrer los vértices de la región factible hasta encontrar aquel vértice para el cual la función objetivo alcanza su máximo (o mínimo valor) 
• Lo primero es convertir las 
restricciones en igualdades.
Restricciones convertidas en igualdades 
• El paso para convertir una restricción comúnmente (≥ , ≤ ) desigualdad a una igualdad es el siguiente: 
✔ Cualquier restricción ≤ puede ser convertida en una igualdad sumando una variable de holgura no negativa al lado izquierdo. 
✔Cualquier restricción ≥ puede ser convertida en una igualdad sumando una variable de excedente no negativa al lado izquierdo
Variables de holgura 
• Las variables de holgura se presentan en las restricciones del tipo: 
x1 + x2 ≤ cte. 
• A la inecuación se le agrega una variable no negativa, entonces tenemos: 
x1 + x2 + s = cte. 
s ≥ 0
Variables de holgura 
• La variable de holgura s será el “faltante”, es decir la cantidad adicional que debe ser sumada al lado izquierdo para convertir la desigualdad en igualdad. 
• Cada restricción ≤ tiene asociada una variable de holgura diferente para cada restricción del modelo
Variables de exceso 
• Para convertir una restricción ≥ en una igualdad, restamos una variable no negativa en el lado izquierdo y la desigualdad cambia a igualdad. 
x1 + x2 ≥ cte. 
• Esto genera las siguientes 
condiciones: 
x1 + x2- s = cte. 
s ≥ 0
Variables de exceso 
• Una variable de exceso es el 
excedente que debe ser reducido al lado izquierdo de la restricción de la desigualdad para convertirla en igualdad. 
• Cada restricción ≥ tiene asociada una variable excedente diferente para cada restricción de este tipo.
Valores óptimos de las variables de holgura y exceso 
• Las restricciones activas son 
precisamente aquellas para los cuales los valores óptimos de las variables de excedente o de holgura son nulos 
• Las restricciones inactivas son aquellas para las que los valores óptimos de las variables de excedente y de holgura son positivos.
Ejemplo: 
F.O. Max Z = x1 + x2 
s.a. 
8x1 + 7x2 ≤ 56 8x1 + 7x2 + s1 = 56 6x1- 10x2 ≥ 60 6x1-10x2 – s2 =60 x1 ≤ 6 x1 + s3 = 6 
- x1 + x2 ≤ 6 - x1 + x2 + s4 = 6 x1,x2 ≥ 0 x1,x2,s1,s2,s3,s4 ≥ 0 
Formato estándar 
• La función objetivo debe maximizarse o minimizarse. 
• Todos los valores del lado derecho de las restricciones son no negativas. 
• El formato estándar es aquel donde las restricciones están expresadas en forma de igualdades. Se aprecian variables de holgura y/o de exceso. 
• Todas las variables son positivas.
Ejemplo: 
F.O. Max Z = x1 + x2 s.a. 
8x1 + 7x2 + s1 = 56 
6x1-10x2 – s2 = 60 
x1 + s3 = 6 
- x1 + x2 + s4 = 6 
x1,x2 ,s1,s2,s3,s4 ≥ 0