1 Programación Lineal Entera Antonio H. Escobar Z. 2013 Universidad Tecnológica de Pereira – Colombia Posgrado en Ingeniería – Maestría/Doctorado

2

3

4 En el problema Dual simplex canalizado se deben tener en cuenta las siguientes consideraciones: 1.Una variable básica asume normalmente un valor entre su límite inferior y su límite superior. 2.Una variable no básica se encuentra en su límite inferior o se encuentra en su límite superior. Se definen dos subconjuntos de índices de variables no básicas:

5

6 R 1 R 2 Condiciones iniciales que debe cumplir el cuadro: + - óptimo Un límite violado

7 Cuadro inicial con estilo Garfinkel:

8 La variable no básica que entra a la base debe disminuir su valor Caso 1: +

9 Por ejemplo, en el cuadro óptimo actual la variable básica tiene el valor = 2.75 y se adiciona la restricción: En este caso, para el nuevo problema, tiene su límite superior violado.

10 variable no básica que entra a la base y debe disminuir su valor Forma general de las variables básicas Nuevo valor de las variables básicas Cambio en las variables básicas

11 La variable no básica que entra a la base debe disminuir su valor variable básica que sale de la base + -

12 variables básicas que continúan en la base variables básicas que continúan en la base

13 - Para que el cuadro sea óptimo los coeficientes de costo reducido deben ser positivos si las variables no básicas están en el LS (R 2 ) - - + + Costos relativos de las variables no básicas que están en R 2

14 Para que el cuadro sea óptimo los coeficientes de costo reducido deben ser positivos si las variables no básicas están en el LS (R 2 ) Garantiza que el cuadro continua siendo óptimo - + -

15 Caso 2: La variable no básica que entra a la base debe aumentar su valor +

16 Forma general de las variables básicas Nuevo valor de las variables básicas Cambio en las variables básicas variable básica que sale de la base ++

17 Cambio en la variable no básica que entra a la base La variable no básica que entra a la base aumenta su valor variables básicas que continúan en la base variables básicas que continúan en la base

18 + - + + En general: + - +

19 ++ - -

20 Caso 3: La variable no básica que entra a la base debe disminuir su valor +

21 Por ejemplo, en el cuadro óptimo actual la variable básica tiene el valor = 2.75 y se adiciona la restricción: En este caso, para el nuevo problema, tiene su límite inferior violado.

22 variable básica que sale de la base y debe aumentar su valor Cambio en la variable no básica que entra a la base La variable no básica que entra a la base disminuye su valor

23 variables básicas que continúan en la base variables básicas que continúan en la base

24

25

26 Caso 4:

27 variable básica que sale de la base y debe aumentar su valor La variable no básica que entra a la base aumenta su valor Cambio en la variable no básica que entra a la base

28 variables básicas que continúan en la base variables básicas que continúan en la base

29

30

31

32

33

34

35

36

37

38

39 Cuadro óptimo

40 En el cuadro óptimo actual la variable básica = 2.75 y se adiciona la restricción: En este caso, para el nuevo problema, tiene su límite superior violado.

41 Las variables no básicas se encuentran en su límite inferior La variable básica viola su límite superior

42

43 La variable básica x 1 sale de la base y pasa a ser no básica en su límite superior La variable no básica x 5 que entra a la base aumenta de valor desde su límite inferior

44 El cuadro primal es óptimo pero infactible (dual factible y no óptimo) primal infactible primal óptimo

45 La variable básica viola su límite inferior x1x1 x3x3

46

47

48 La variable básica x 4 sale de la base y pasa a ser no básica en su límite inferior La variable no básica x 3 que entra a la base aumenta de valor desde su límite inferior

49 El cuadro primal es óptimo y factible primal factible primal óptimo