Investigacion de operaciones

Programación Lineal El método simplex El método simplex es una herramienta algebraica que permite localizar de manera eficiente el óptimo entre los puntos extremos de una solución a un problema de programación lineal. Forma estándar de programación lineal (PL) y sus soluciones básicas El empleo de las soluciones básicas para resolver el modelo de PL requiere poner el problema en una formaestándar, cuyas propiedades son: 1. Todas las restricciones (con excepción de las restricciones de no negatividad sobre las variables) son ecuaciones con un lado derecho no negativo. 2. Todas las variables son no negativas. 3. La función objetivo puede ser del tipo de maximización o de minimización. a. Conversión de desigualdades a ecuaciones Una desigualdad del tipo = (=) se convierte a una ecuaciónaumentando su lado izquierdo con una variable de holgura (superávit) Ejemplos: 1) x1 + 2x2 = 3 es equivalente a x1 + 2x2 + S1 = 3 2) x1 + 2x2 = 3 es equivalente a x1 + 2x2 - S1 = 3 donde S1 = 0 b. 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 -, dondexj+,xj - = 0 Ejemplo: xj = -5 es equivalente a xj+ = 0 y xj - = 5; donde xj+,xj - = 0 c. Conversión de maximización a minimización La maximización de una función f(x1, x2, … , xn) es equivalente a la minimización de -f(x1, x2, … , xn), en el sentido que ambos problemas producen los mismos valores óptimos x1, x2, … , xn. Ejemplo: Maximizar G = 300 P + 500 V Sujeto a:
P 3P + = 2V = 2V = P, V = 412 18 0

Maximizar G = 300 P + 500 V Sujeto a:
P + 3P + 2V + 2V + S1 S2 + = = S3 = 4 12 18

P, V, S1, S2, S3 = 0 Determinación de soluciones básicas La forma estándar de PL incluye m ecuaciones lineales simultáneas en n incógnitas o variables (m < n). Una solución básica asociada se determina haciendo n – m variables iguales a 0 y luego, resolviendo las m ecuaciones con las restantes mvariables, siempre que la solución resultante exista y sea única. El número máximo de soluciones básicas factibles = (n m) = n! / m! (n-m)! En la PL nos referimos a las n-m variables que se hacen iguales a cero como variables no básicas y, a las m variables restantes como variables básicas (siempre y cuando exista una solución única). Se dice que una solución básica es factible si todos los valores desu solución son no negativos, en caso contrario es una solución básica infactible. Las soluciones básicas factibles son puntos extremos Ejemplo: ? n = 5, m = 3 (3 < 5) ? una solución básica esta asociada con n – m = 5 – 3 = 2 variables nulas. ? número máximo de soluciones básicas factibles: 5! / 3! 2! = 10 Variables: P, V, S1, S2 y S3 P X X X X X V X X X X S1 S2 S3

P V S1 S2 S3

X X X

X XX

V, P = 0
S1 S2 + = = S3 = 4 12 18

Solución básica factible: S1=4, S2=12, S3=18 P, S1 = 0
2V + 2V + S2 + = = S3 = 4 12 18

Solución inconsistente

P, S2 = 0
S1 2V + 2V + + = = S3 = 4 12 18

Solución básica factible: S1=4, V=6, S3=6 P, S3 = 0
S1 2V + 2V + S2 = = = 4 12 18

Solución básica infactible: S1=4, V=9, S2=-6 V, S1 = 0
P S2 3P + + = = S3 = 4 12 18

Solución básicafactible: P=4, S2=12, S3=6 V, S2 = 0
P + 3P + S1 + = = S3 = 4 12 18

Solución inconsistente V, S3 = 0
P + 3P S1 S2 = = = 4 12 18

Solución básica infactible: P=6, S2=12, S1=-2 S1, S2 = 0
P 3P + 2V 2V + + = = S3 = 4 12 18

Solución básica infactible: P=4, V=6, S3=-4 S1, S3 = 0
P 3P + 2V + 2V S2 = = = 4 12 18

Solución básica factible: P=4, V=3, S2=6 S2, S3 = 0
P + 3P + 2V 2V S1 = = = 412 18

Solución básica factible: V=6, P=2, S1=2

El algoritmo del método simplex El método simplex siempre comienza en una solución básica factible y después trata de encontrar otra solución básica factible que mejore el valor del objetivo. Esto es posible sólo si incremento en una variable cero actual (no básica) conduce a un mejoramiento del valor del objetivo. Sin embargo, para que una...