25 de Junio de 2012 RESOLUCIÓN DE MODELOS DE … Entera/Clases Magistrales... · El Método...

RESOLUCIÓN DE MODELOS DE PROGRAMACIÓN

ENTERA

25 de Junio de 2012

Programación Entera José Luis Quintero 1

ENTERAMÉTODOS DE CORTE

CORTES DE GOMORYPostgrado de Investigación de Operaciones

Facultad de Ingeniería

Universidad Central de Venezuela

1. Idea básica de los métodos de corte

2. Aspectos de Programación Lineal (PL)

3. El Método Simplex Dual

Puntos a tratar


4. Análisis de sensibilidad en PL

5. Corte entero puro de Gomory

6. Corte entero mixto de Gomory

• La idea básica de los métodos de corte consiste enreestructurar el espacio de soluciones originales(continuas) de tal forma que la solución enteraaparezca como un punto extremo del espacio desoluciones así modificado.

• Esta reestructuración del espacio de soluciones selleva a cabo mediante la introducción de

Métodos de corte


• Esta reestructuración del espacio de soluciones selleva a cabo mediante la introducción derestricciones (planos de corte) diseñadas para esteefecto que sistemáticamente cortan o truncan elespacio de soluciones de tal forma que ningúnpunto factible relevante sea excluído. Es decir,estas restricciones, cortan o truncan partes nofactibles del espacio de soluciones.

• Los métodos de corte tienen la importanciahistórica de ser los primeros algoritmos(publicados) que se desarrollaron para resolvermodelos de programación lineal entera.

Métodos de corte


• El primer algoritmo finito de cortes se debe a R.Gomory en 1958 para el problema entero puro. Ymás adelante en 1960 expandió la teoría delalgoritmo para atacar problemas enteros mixtos.

• PASO 1. Resolver el modelo de programación lineal continuoasociado al problema entero lineal.

a. Si la solución del modelo asociado es no factible, elproblema original entero es no factible.

b. Si la solución óptima satisface las restricciones enteras,esta solución es la solución óptima del modelo original. FIN.c. Si la solución óptima no satisface las restricciones enteras:

Esquema general de los métodos de corte


• PASO 2. Utilice el método de corte para generar un plano decorte. Añada la restricción que representa el corte a lasrestricciones del modelo y aplique el paso 1. La nuevarestricción elimina la solución óptima del modelo continuo dela región factible y no elimina ningún punto entero. El métodose repite hasta alcanzar la solución óptima que satisfaga lasrestricciones enteras.




Puntos a tratar





• Un modelo de minimización de PL, puede serexpresado por:

P: min z = cx

s.a. Ax = b

x ≥ 0

Aspectos importantes de Programación Lineal


donde c∈Rn (fila), A∈Rm,n y b∈Rm son conocidos.

• Las variables de decisión vienen representadas porx∈Rn y z∈R es el valor de la función objetivo. Elpoliedro que constituye la región factible delespacio de opciones se denota por S.

• Con Ax = b se puede hacer la partición A = (B N),donde B∈Rm,m y N∈Rm,(n-m). Como B se construyecon las columnas linealmente independientes de A,se garantiza la existencia de B-1.

• Si se particiona x, es decir:

==== Bxxx



donde xB∈Rm y xN∈R(n-m), las variables agrupadasen xB se llaman variables básicas y las agrupadasen xN son no básicas, entonces Ax = b esequivalente a:

====Nxx

( ) =

B

N

xB N b

x

• Al desarrollar BxB + NxN = b para obtener xB bastapremultiplicar por B-1:

xB = B-1 b - B-1 NxN

Si se hace xN=0 se tiene una solución básicadada por xB=B

-1b. Si adicionalmente se tiene quexB ≥ 0 entonces se trata de una solución básica



xB ≥ 0 entonces se trata de una solución básicafactible.

• Si se tiene una solución factible cualquiera x, dadapor:

donde xB ≥ 0 y xN ≥ 0, entonces se puede expresar:

====N

B

x

xx

luego:

donde η es el conjunto de índices no básicofactible actual, aj es la j-ésima columna de A y xjes la j-ésima variable no básica. Al evaluar elobjetivo en x se tiene:

(((( )))) bNxBxx

xN BAx NB

N

B ====++++====

====

j j

j j

x x− − − − −

∈η ∈η

= − = − = −∑ ∑1 1 1 1 j 1 jB Nx B b B Nx B b B a B b y



objetivo en x se tiene:

• Si x es una solución óptima entonces la baseasociada B es tal que:

B-1b ≥ 0 ,

(((( )))) NNBBN

BNB xcxc

x

xcccxz ++++

======== ====

0− − ≤1B Nc B N c




Puntos a tratar





• Suponga que se tiene una solución óptima pero infactiblepara un problema de minimización. Ello significa que loscoeficientes de costo reducidos son no positivos, pero algúnelemento del vector de recursos es negativo. Ya se verácómo se puede llegar a esta situación. Sea el siguientetablero correspondiente a un problema de minimización:

Z X1 X2 X3 X4 X5 LD

1 -2 -3 -4 0 0 0

Ejemplo 1. La mecánica del Método Simplex Dual


1 -2 -3 -4 0 0 0

0 -1 -2 -1 1 0 -3

0 -2 1 -3 0 1 -4

• En él se observa que todos los coeficientes de costos son nopositivos, por lo que la solución actual es óptima. También seobserva que la solución actual es infactible, pues hay

elementos negativos en el vector de recursos.

• Se plantea el problema siguiente: ¿es posible realizar unasecuencia de operaciones de pivoteo que permitan recuperarfactibilidad sin perder optimalidad? ¿Es posible pivotear hastaobtener una solución factible que también sea óptima? Larespuesta es afirmativa.

• La idea es hacer crecer los elementos del vector de recursoshasta recuperar la factibilidad sin perder la optimalidad. Ellorequiere que si se hace un pivoteo, el elemento del vector derecursos que sea negativo crezca hasta dejar de serlo, al



recursos que sea negativo crezca hasta dejar de serlo, almismo tiempo que ningún coeficiente de costo se hagapositivo.

• De acuerdo al significado que se dió a los coeficientestecnológicos, si alguno de ellos es negativo entonces elcrecimiento de la variable asociada genera cantidadesadicionales de ese recurso en lugar de consumirlo, por lotanto su valor aumenta.

• Este último hecho indica que de hacer entrar una variable xk(k=1,2,...,n) a la base, ello ayudará a eliminar la infactibilidaddetectada en algún bi (aquel bi<0 para algún i=1,2,...,m),siempre y cuando se cumpla que .

• Luego, para hacer no negativo el elemento –4 del LD, se debepivotear en alguna de las posiciones sombreadas:

0 yki <<<<



Z X1 X2 X3 X4 X5 LD

1 -2 -3 -4 0 0 0

0 -1 -2 -1 1 0 -3

0 -2 1 -3 0 1 -4

lo cual llevaría a entrar a la base a x1 o a x3.

• La selección de la variable que se debe hacer entrar a la basedepende del efecto del pivoteo sobre la optimalidad. Larelación entre el coeficiente de costo reducido zk -ck y el valordado por (para ) indica en cuánto se puede desmejorarel valor actual del objetivo por un crecimiento unitario de lavariable xk que beneficie la factibilidad.

kiy 0 yk

i <<<<



• La idea es pivotear donde se desmejore lo menos posible elvalor actual de la función objetivo. Por ello, para escoger lavariable que va a entrar se hace un TRM entre los valoresnegativos de la fila del objetivo y los valores negativos de lafila pivote. El método es como sigue:

1. Elija la fila pivote que corresponda al elemento del vector derecursos más negativo.



2. Elija la columna pivote haciendo el TRM entre loscoeficientes de costo reducidos y los valores negativos de lamatriz tecnológica en esa fila pivote. Si no se puede hacer elTRM por no encontrar denominadores negativos, el problemano es factible.

En el ejemplo actual la fila pivote es la sombreada:

Z X1 X2 X3 X4 X5 LD

1 -2 -3 -4 0 0 0

0 -1 -2 -1 1 0 -3

0 -2 1 -3 0 1 -4

El TRM indica la columna pivote:



Z X1 X2 X3 X4 X5 LD

1 -2 -3 -4 0 0 0

0 -1 -2 -1 1 0 -3

0 -2 1 -3 0 1 -4

TRM ⇑1 --- 1,333 --- ---

Al pivotear se llega a:

Z X1 X2 X3 X4 X5 LD

1 0 -4 -1 0 -1 4

0 0 -5/2 1/2 1 -1/2 -1

0 1 -1/2 3/2 0 -1/2 2



Ahora se procede con la siguiente fila pivote, la cual se hasombreado:

Z X1 X2 X3 X4 X5 LD

1 0 -4 -1 0 -1 4

0 0 -5/2 1/2 1 -1/2 -1

0 1 -1/2 3/2 0 -1/2 2

El TRM indica la columna pivote:

Z X1 X2 X3 X4 X5 LD

1 0 -4 -1 0 -1 4

0 0 -5/2 1/2 1 -1/2 -1

0 1 -1/2 3/2 0 -1/2 2

TRM --- ⇑1,60 --- --- 2

al pivotear se tiene:



al pivotear se tiene:

Z X1 X2 X3 X4 X5 LD

1 0 0 -9/5 -8/5 -1/5 28/5

0 0 1 -1/5 -2/5 1/5 2/5

0 1 0 7/5 -1/5 -2/5 11/5

el cual sigue siendo un tablero óptimo, pero es ademásfactible.

• Gráficamente, la situación puede representarse en un casobidimensional como sigue:

Óptimo infactible

Ganar factibilidadsin perder optimalidad

x2



(0,0) x1




Puntos a tratar





• INCLUSIÓN DE UNA NUEVA RESTRICCIÓN

Si se agrega una nueva restricción, ésta no afecta laoptimalidad pero si puede afectar la factibilidad: basta con quela nueva restricción haga que la solución óptima actual seainfactible. De ser ese el caso se puede aplicar el MétodoSimplex Dual para recuperar la factibilidad.

Se tiene una solución óptima de base B, por lo que lassoluciones básicas vienen dadas por la relación:

Análisis de sensibilidad


soluciones básicas vienen dadas por la relación:

y se agrega la restricción

Esta última puede escribirse como:

donde y son, respectivamente, las componentesbásicas y no básicas del vector fila am+1 y xn+1 es una variablede holgura no negativa.

bBNxBx 1N

1-B

−−−−====++++

1m1m bxa ++++

++++ ≤≤≤≤

1m1nN1m

NB1m

B bxxaxa ++++++++++++++++ ====++++++++

1mBa ++++ 1m

Na ++++

Luego, en la solución óptima se tiene:

entonces, las primeras m soluciones básicas vienen dadas por:

y la solución básica m+1, que es xn+1, será factible si:

bBabxx)NBaa( 11mB1m1nN

11mB

1mN

−−−−++++++++++++

−−−−++++++++ −−−−====++++−−−−

bBNxBx 1N

1B

−−−−−−−− ====++++

0bBab 11mB1m ≥≥≥≥−−−− −−−−++++

++++

Análisis de sensibilidad


Es decir, si en el tablero óptimo, la holgura de la nuevarestricción introducida es no negativa, entonces la nuevarestricción no excluye la solución óptima anteriormentealcanzada. En ese caso la solución óptima actual sigue siendofactible, en caso contrario, debe recuperarse factibilidad con elMétodo Simplex Dual.

0bBab B1m ≥≥≥≥−−−−++++

• Sea el tablero inicial:

Z X1 X2 X3 X4 X5 LD

1 2 -1 1 0 0 0

0 1 1 1 1 0 6

0 -1 2 0 0 1 4

cuyo tablero óptimo es:

Ejemplo 2. Inclusión de una nueva restricción


cuyo tablero óptimo es:

Z X1 X2 X3 X4 X5 LD

1 0 -3 -1 -2 0 -12

0 1 1 1 1 0 6

0 0 3 1 1 1 10

¿Qué ocurre si se agrega al problema original la restricción

-x1+2x3 ≥ 2 ?

Al llevar la nueva restricción a la forma ≤ se tiene:

x1 - 2x3 ≤ - 2 luego:

Como la solución pasa a ser infactible, se agrega la nueva

(((( )))) 086210

6

11

01012bBab 13

B3 ≤≤≤≤−−−−====−−−−−−−−====

−−−−−−−−====−−−− −−−−



restricción y se modifica el tablero anterior a:

Z X1 X2 X3 X4 X5 X6 LD

1 0 -3 -1 -2 0 0 -12

0 1 1 1 1 0 0 6

0 0 3 1 1 1 0 10

0 1 0 -2 0 0 1 -2

Se gana forma canónica y se llega al tablero:

Z X1 X2 X3 X4 X5 X6 LD

1 0 -3 -1 -2 0 0 -12

0 1 1 1 1 0 0 6

0 0 3 1 1 1 0 10



0 0 3 1 1 1 0 10

0 0 -1 -3 -1 0 1 -8

a partir del cual se puede aplicar el Método Simplex Dual

para recuperar factibilidad.




Puntos a tratar





• Sea P un modelo de programación lineal entera pura de laforma:

• Se supondrá que los datos son enteros. Suponga que se

Corte entero puro de Gomory

P min cx

s.a. Ax b

x 0

x entero

≤≥


• Se supondrá que los datos son enteros. Suponga que seresuelve el modelo lineal P y se halla x (solución óptima). Si xes entero FIN. En caso contrario, se genera una restricción(corte) que elimine a x de la región factible y no elimineningún punto entero factible.

• Sea B una base asociada a x, en tal caso

1B b 0− ≥ 1B Nc B N c 0− − ≤

• Sea .

• Si no es entero, entonces no es entero.

• Se tiene donde aldescomponer se obtiene


1 1 1 1 j 1 jB N j j

j j

x B b B Nx B b B a x B b y x− − − − −

∈η ∈η

= − = − = −∑ ∑Bxx0

=

B kk /(x )∃

1 1 1 jB k k N k k jk

j

(x ) (B b) (B Nx ) (B b) y x− − −

∈η

= − = −∑

1 j j(x ) (B b) f ( y g )x− = + − +∑


con .

• Como y , se sigue que .

��

�

1 j jB k k k jk k

jparte parteparteparte fraccional fraccionalenteraentera

(x ) (B b) f ( y g )x−

∈η

= + − + ∑��

jk k0 f 1 , 0 g 1< < < <

k0 f 1< < jjk

j

g x 0∈η

≥∑ jk jk

j

f g x 1∈η

− <∑

• La restricción

(1)

elimina con seguridad a la solución óptima x porque en elóptimo se exigió que , condición que no es satisfechapor la restricción (1). A la restricción (1) se le conoce comoCORTE ENTERO PURO DE GOMORY.


jk jk

j

f g x 0∈η

− ≤∑

k0 f 1< <


• Para obligar a a tomar un valor entero, una vez que elvector deje de ser nulo, basta que sea entero.

• Por lo tanto la restricción (1) es una condición necesariapara lograr el requisito del apartado anterior.

B k(x )

Nxj

k jk

j

f g x∈η

−∑

• Considere el siguiente modelo de programación entera pura

Ejemplo 3. Corte entero puro de Gomory

1 2

1 2

1 2

1 2

Max Z 120x 80x

s.a. 2x x 6

7x 8x 28

x ,x 0 , enteros

= ++ ≤

+ ≤≥


que resulta equivalente al modelo

1 2

1 2

1 2

1 2

Min W Z 120x 80x

s.a. 2x x 6

7x 8x 28

x ,x 0 , enteros

= − = − −+ ≤

+ ≤≥

• El tablero óptimo viene dado por

W X1 X2 X3 X4 LD

1 0 0 -400/9 -40/9 -3520/9

0 1 0 8/9 -1/9 20/9

0 0 1 -7/9 2/9 14/9

Se puede leer la solución óptima P1 = (x1,x2) = (20/9,14/9)




W = -3520/9

• El primer corte de Gomory viene dado por la restricción

3 42 2 3 2 4 3 4 3 4

5 2 2 2 2 5f g x g x x x 0 x x

9 9 9 9 9 9− − = − − ≤ ⇒ − − ≤ −

• En términos de las variables originales del problema se tiene

• Al introducir el corte al tablero óptimo:

W X1 X2 X3 X4 X5 LD

1 0 0 -400/9 -40/9 0 -3520/9


3 4 1 2

2 2 5x x 2x 2x 7

9 9 9− − ≤ − ⇒ + ≤

3 4 5

2 2 5x x x

9 9 9− − + = −


1 0 0 -400/9 -40/9 0 -3520/9

0 1 0 8/9 -1/9 0 20/9

0 0 1 -7/9 2/9 0 14/9

0 0 0 -2/9 -2/9 1 -5/9

• Se necesita aplicar el Método Simplex Dual para recuperarfactibilidad.

• Después del aplicar el Método Simplex Dual se obtiene:

W X1 X2 X3 X4 X5 LD

1 0 0 -40 0 -20 -380

0 1 0 1 0 -1/2 5/2

0 0 1 -1 0 1 1

0 0 0 1 1 -9/2 5/2



Se puede leer la solución óptima P2 = (x1,x2) = (5/2,1)

W = -380

• El segundo corte de Gomory viene dado por la restricción

3 51 1 3 1 5 5 5

1 1 1 1f g x g x x 0 x

2 2 2 2− − = − ≤ ⇒ − ≤ −



W X1 X2 X3 X4 X5 X6 LD

1 0 0 -40 0 -20 0 -380


5 1 2

1 1x x x 3

2 2− ≤ − ⇒ + ≤

5 6

1 1x x

2 2− + = −


1 0 0 -40 0 -20 0 -380

0 1 0 1 0 -1/2 0 5/2

0 0 1 -1 0 1 0 1

0 0 0 1 1 -9/2 0 5/2

0 0 0 0 0 -1/2 1 -1/2


• Después de aplicar el Método Simplex Dual se obtiene

W X1 X2 X3 X4 X5 X6 LD

1 0 0 -40 0 0 -40 -360

0 1 0 1 0 0 -1 3

0 0 1 -1 0 0 2 0

0 0 0 1 1 0 -9 7

0 0 0 0 0 1 -2 1



0 0 0 0 0 1 -2 1

• Se puede leer la solución óptima lineal entera

P3 = (x1,x2) = (3,0) W = -360

De modo que Z = 360.




Puntos a tratar





• Sea P un modelo de programación lineal entera mixta de laforma:

Corte entero mixto de Gomory

j

P min cx

s.a. Ax b

x 0

x entero si j J

J es un conjunto de índices de

≤≥

∈


• Sea B una base asociada a x, en tal caso

1B b 0− ≥ 1B Nc B N c 0− − ≤

J es un conjunto de índices de

var iables que son requeridas enteras

• Sea .

• Sea que debe ser entera y no lo es.

• Se tiene donde aldescomponer se obtiene


1 1 1 1 j 1 jB N j j

j j

x B b B Nx B b B a x B b y x− − − − −

∈η ∈η

= − = − = −∑ ∑

B kk /(x )

1 1 1 jB k k N k k jk

j

(x ) (B b) (B Nx ) (B b) y x− − −

∈η

= − = −∑

1 j(x ) (B b) f y x− = + −∑


con .

• Si se desea que sea entera, entonces se debe cumplirsolo una de las dos condiciones siguientes:

�

1 jB k k k jk

jparteparte fraccionalentera

(x ) (B b) f y x−

∈η

= + − ∑��

k0 f 1< <

B k(x )

• De la restricción A se tiene que:

(2)

• De la restricción B se tiene que:


A. B. 1 1B k k B k k(x ) (B b) (x ) (B b) 1− − ≤ ≥ +

1 jB k k k jk

j

(x ) (B b) f y x 0−

∈η

− = − ≤ ∑


• De la restricción B se tiene que:

(3)

• Se definen

• En función de y las restricciones (2) y (3) implican:

1 jB k k k jk

j

(x ) (B b) f y x 1−

∈η

− = − ≥ ∑

{ } { } j jk kJ j / y 0 , J j / y 0+ −= ∈ η > = ∈ η <

J+ J−

(4)

(5)

• Multiplicando ambos miembros de (5) por se tiene:


j j j jk j k j k j j kk k k k

jj J j J j J

f y x f y x 0 f y x 0 y x f+ + +∈η∈ ∈ ∈

− ≤ − ≤ ⇒ − ≤ ⇒ − ≤ −∑ ∑ ∑ ∑

j j j jk j k j k j j kk k k k

jj J j J j J

f y x f y x 1 f y x 1 y x 1 f− − −∈η∈ ∈ ∈

− ≥ − ≥ ⇒ − ≥ ⇒ − ≥ −∑ ∑ ∑ ∑

kf 0>


• Multiplicando ambos miembros de (5) por se tiene:

(6)

• Como las condiciones (4) y (6) son exclusivas (por definición)

se pueden combinar para obtener la restricción

k

k

f0

1 f>

−

jkj kk

kj J

fy x f

1 f−∈

≤ − −

∑

(7)

• A la restricción (7) se le conoce como CORTE ENTEROMIXTO DE GOMORY.


j jkj j kk k

kj J j J

fy x y x f

1 f− +∈ ∈

− ≤ − −

∑ ∑


• La restricción (7) es una condición necesaria para lograrque sea entera.B k(x )

• Considere el siguiente modelo de programación entera mixta

Ejemplo 4. Corte entero mixto de Gomory

1 2

1 2

1 2

1 2 1

Max Z x 3x

s.a. x 2x 10

x 3x 3

x ,x 0 , x entero

= ++ ≤

− + ≤≥


que resulta equivalente al modelo

1 2

1 2

1 2

1 2 1

Min W Z x 3x

s.a. x 2x 10

x 3x 3

x ,x 0 , x entero

= − = − −+ ≤

− + ≤≥

• En la forma estándar se tiene:



1 2

1 2 3

1 2 4

1 2 3 4 1

Min W x 3x

s.a. x 2x x 10

x 3x x 3

x ,x ,x ,x 0 , x entero

= − −+ + =

− + + =≥



W X1 X2 X3 X4 LD

1 0 0 -6/5 -1/5 -63/5

0 1 0 3/5 -2/5 24/5

0 0 1 1/5 1/5 13/5


W = -63/5

• El primer corte de Gomory viene dado por la restricción


44 3 511 4 1 3 1 4 34

1 5

f 3 2 3 4y x y x f . x x

1 f 5 1 5 5 5

8 3 4

− ≤ − ⇒ − − ≤ −− −


4 3

8 3 4x x

5 5 5⇒ − − ≤ −



W X1 X2 X3 X4 X5 LD

1 0 0 -6/5 -1/5 0 -63/5


3 4 1 2

3 8 5x x x 6x 10

5 5 5− − ≤ − ⇒ − + ≤

3 4 5

3 8 4x x x

5 5 5− − + = −


1 0 0 -6/5 -1/5 0 -63/5

0 1 0 3/5 -2/5 0 24/5

0 0 1 1/5 1/5 0 13/5

0 0 0 -3/5 -8/5 1 -4/5


• Después del aplicar el Método Simplex Dual se obtiene:

W X1 X2 X3 X4 X5 LD

1 0 0 -9/8 0 -1/8 -25/2

0 1 0 3/4 0 -1/4 5

0 0 1 1/8 0 1/8 5/2

0 0 0 3/8 1 -5/8 1/2



0 0 0 3/8 1 -5/8 1/2

Se puede leer la solución óptima P2 = (x1,x2) = (5,5/2)

W = -25/2

De modo que Z = 25/2.

Pensamiento de hoy

“Un experto es aquel que ya ha

cometido todos los errores

posibles en una materia muy

concreta”.


concreta”.

Niels Bohr

25 de Junio de 2012 RESOLUCIÓN DE MODELOS DE … Entera/Clases Magistrales... · El Método...

Documents

Transcript of 25 de Junio de 2012 RESOLUCIÓN DE MODELOS DE … Entera/Clases Magistrales... · El Método...