Formas DEL Modelo DE P.L PDF

Preview

Summary

Forma de programacion lineal...

Description

UNIDAD II EL METODO SIMPLEX Iniciando con los métodos numéricos de solución, es el método simplex el que suele utilizarse al principio, ya que los demás métodos se desprenden o son variantes de el. En primer lugar para poder aplicar el método simplex, hay que conocer las formas básicas del modelo de P.L. FORMA CANÓNICA Esta forma tiene las siguientes características: 1.- La función objetivo debe ser del tipo maximizar. 2.- Las variables de decisión deben ser no negativas. 3.- Todas las restricciones deben ser del tipo ≤. n

Max f(x)  c j x j j 1 n

sujeta a

a

ij

x j  bi i 1,2,..., m.

j1

x j 0

Generalmente un modelo de P.L., no suele reunir estas características en su totalidad por lo que las siguientes transformaciones elementales ayudan a convertir cualquier modelo de P.L. a la forma canónica. a) Una función objetivo de un tipo es equivalente a la misma función pero del otro tipo pero con signo contrario. Ejemplo.- Minimizar f(x) = Maximizar – f(x).

b) Una restricción que tiene un sentido, puede ser cambiada al sentido contrario si se multiplican ambos lados de la restricción por menos uno. Ejemplo.x2 ≤ - b1

a1x1 + a2 x2 ≥ b1 equivale a - a 1x1 - a2

c) Una restricción de igualdad equivale a dos restricciones de desigualdad pero con sentidos opuestos. Ejemplo.a1x1 + a2 x2 = b1 ≤ b1 y a1x1 + a2 x2 ≥ b1 .

equivale a a1x1 + a2 x2

d) Una restricción cuyo lado izquierdo está en forma de valor absoluto equivale a dos restricciones con sentidos opuestos, pero la que tiene el mismo sentido que la original su lado derecho conserva su signo, pero la que está en sentido opuesto, su lado derecho cambia de signo. Ejemplo.- │ a1x1 + a2 x2 │≥ b1 equivale a a1x1 + a2 x2 ≥ b1 y a a1x1 + a2 x2 ≤- b1 . e) Si una variable en un modelo de P.L. se declara como irrestricta en signo, es equivalente a la diferencia de dos variables no negativas. Ejemplo.- sea x1 irrestricta en signo entonces =( x+1 -X-1) Donde x+1, x-1 ≥ 0

x1

Ejemplo.- Convierta a la forma canónica el siguiente modelo de P.L. Min f(x) 4x

 6 x 3 x 1 2 3 sujeta a 2x  x  x  4 1 2 x  3 x  2 x  8 1 2 - x  x  4 x 5 1 2 x , x , 0 1 2 x irrestrict a en signo. 3

3

3

3

primero la forma canónica pide que todas las variables sean no negativas por lo que a x se le sustituye por  x  x . 3





3

3

En 2o. lugar la función objetivo debe ser del tipo Max, por lo que se multiplica por - 1 para cambiarla, teniendo así. (Min f(x)  4x  6 x  3x ) * (-1)  Max  f(x) - 4x  6 x  3 x 1 2 3 1 2 3 Y por último todas las restriccio nes deben de ser del tipo , por lo que hay que hacer las transform aciones respectiva s cada restricció n para lograr lo anterior, teniendo así :

1a. restricció n 2x1  x 2  x3 4, como es del tipo hay que multiplicar por - 1 para hacerla , dando como resultado : - 2x1  x2  x 3  4 Para la 2a, restricción se tiene x1  3x 2  2x 3  8 entonces hay que sustituir por 2 restricciones de desigualdad con sentidos opuestos, lo cual da : x1  3x 2  2x 3  8 y x1  3x 2  2 x 3  8 y a esta última restricció n hay que multiplicar por - 1 para hacerla . - x1  3 x2 2 x3 8. A la 3a restricción no hay que hacerle cambios, y solamente resta que a todo el modelo donde  aparezca x 3 , hay que sustituir por (x  3  x 3 ). - x1  x 2  4 x 3 5

Convertir a la forma canónica el siguiente modelo PL Min f(x) - 2x1  x 2  4x 3  5x 4 sujeta a

2x1  x 2  x3  2x4  7 x1  x 2  x 3  x 4 6 - x1  x 2  4 x 3  8 x , x , 0 1 2 x 3, x 4 irrestrict as en signo

El resultado final en forma canónica es : Max g(x) - 4x  6 x  3( x   x  ) 1 2 3 3       4 sujeta a - 2x x x ) (x 1 2 3 3   x  3x  2 ( x  x )  8 1 2 3 3 - x 3 x  2 ( x   x  ) 8 1 2 3 3 - x  x  4 ( x  x ) 5 1 2 3 3   0 x ,x , x , x 1 2 3 3

FORMA ESTANDAR Esta forma sirve para poder inducir una solución ya que la forma canónica como utiliza desigualdades no es de mucha utilidad para ello. Las características de la forma estándar son las siguientes: 1.- Todas las variables de decisión deben ser no negativas. 2.- La función objetivo puede ser del tipo maximizar o minimizar. 3.- Todas las restricciones deben ser igualdades. 4.- El lado derecho de las restricciones debe ser positivo. Para convertir una restricción de desigualdad en igualdad se agrega al lado izquierdo de la restricción

una variable no negativa llamada variable de holgura o escasez, ( slack o surpplus), denotada por h i, con i = 1,2,..., m. De modo que si la restricción es del tipo  la variable se agrega sumando, pero si es del tipo  la variable se agrega restando.

Entonces el modelo viene dado n

Max o Min f(x)   c j xj j 1

por:

n

sujeta a

a

ij

x j b i i 1,2,..., m.

j 1

x j, b i 0

Por ejemplo.- Convierta a la forma estándar el modelo empleado en la forma canónica. Min f(x) 4x1  6x2  3x3 sujeta a 2x 1  x 2  x 3  4 x 1  3x 2  2x 3   8 - x1  x 2  4x 3  5 x1 , x 2  0 x 3 irrestrict a en signo Min f(x) 4x 1  6 x 2  3(x 3  x 3 ) sujeta a 2x1  x2  (x3  x3 )  h1  4 - x 1  3 x 2  2( x3  x3 ) 8 - x 1  x 2  4( x3  x3 )  h3 5 x 1, x 2 , x 3 ., x 3 , h1, h3 0

Convertir a la forma canónica el siguiente modelo PL Min f(x) - 2x1  x2  4 x3 sujeta a

 5x 4

2x1  x 2  x3  2 x 4   7 x 1 x 2  x3  x4  6 - x1  x2  4 x3   8 x , x , 0 1 2 x3 , x4 irrestrict as en signo

 Max g(x)  2x  x  4( x3 - x -3 ) - 5(x  4  x4 ) 1 2    sujeta a - 2x1  x 2  (x3 - x3 )  2(x 4  x 4 ) 7 -

 2x1  x2  ( x3 - x3 )  2(x 4  x4 ) 7 -

 x 1  x 2  (x 3 - x3 )  (x 4  x4 )6 -

- x1  x 2  (x3 - x3 )  (x4  x4 )  6  - x  x  ( x3 - x -3)  (x 4  x4 )   6 1 2 x  x  (x 3 - x -3 )  (x 4  x 4 )   6 1 2  - x1  x 2  4( x3 - x 3 )   8 -

 x1 , x 2 , x 3 , x 3 , x  4 ,x 4  0...