RESOLUCIN DE

MODELOS DE
PROGRAMACIN
ENTERA
25 de Junio de 2012
Programacin Entera Jos Luis Quintero 1
ENTERA
MTODOS DE CORTE
CORTES DE GOMORY
Postgrado de Investigacin de Operaciones
Facultad de Ingeniera
Universidad Central de Venezuela
1. Idea bsica de los mtodos de corte
2. Aspectos de Programacin Lineal (PL)
3. El Mtodo Simplex Dual
Puntos a tratar
Programacin Entera Jos Luis Quintero 2
4. Anlisis de sensibilidad en PL
5. Corte entero puro de Gomory
6. Corte entero mixto de Gomory
La idea bsica de los mtodos de corte consiste en
reestructurar el espacio de soluciones originales
(continuas) de tal forma que la solucin entera
aparezca como un punto extremo del espacio de
soluciones as modificado.
Esta reestructuracin del espacio de soluciones se
lleva a cabo mediante la introduccin de
Mtodos de corte
Programacin Entera Jos Luis Quintero 3
Esta reestructuracin del espacio de soluciones se
lleva a cabo mediante la introduccin de
restricciones (planos de corte) diseadas para este
efecto que sistemticamente cortan o truncan el
espacio de soluciones de tal forma que ningn
punto factible relevante sea excludo. Es decir,
estas restricciones, cortan o truncan partes no
factibles del espacio de soluciones.
Los mtodos de corte tienen la importancia
histrica de ser los primeros algoritmos
(publicados) que se desarrollaron para resolver
modelos de programacin lineal entera.
Mtodos de corte
Programacin Entera Jos Luis Quintero 4
El primer algoritmo finito de cortes se debe a R.
Gomory en 1958 para el problema entero puro. Y
ms adelante en 1960 expandi la teora del
algoritmo para atacar problemas enteros mixtos.
PASO 1. Resolver el modelo de programacin lineal continuo
asociado al problema entero lineal.
a. Si la solucin del modelo asociado es no factible, el
problema original entero es no factible.
b. Si la solucin ptima satisface las restricciones enteras,
esta solucin es la solucin ptima del modelo original. FIN.
c. Si la solucin ptima no satisface las restricciones enteras:
Esquema general de los mtodos de corte
Programacin Entera Jos Luis Quintero 5
PASO 2. Utilice el mtodo de corte para generar un plano de
corte. Aada la restriccin que representa el corte a las
restricciones del modelo y aplique el paso 1. La nueva
restriccin elimina la solucin ptima del modelo continuo de
la regin factible y no elimina ningn punto entero. El mtodo
se repite hasta alcanzar la solucin ptima que satisfaga las
restricciones enteras.
1. Idea bsica de los mtodos de corte
2. Aspectos de Programacin Lineal (PL)
3. El Mtodo Simplex Dual
Puntos a tratar
Programacin Entera Jos Luis Quintero 6
4. Anlisis de sensibilidad en PL
5. Corte entero puro de Gomory
6. Corte entero mixto de Gomory
Un modelo de minimizacin de PL, puede ser
expresado por:
P: min z = cx
s.a. Ax = b
x 0
Aspectos importantes de Programacin Lineal
Programacin Entera Jos Luis Quintero 7
donde cR
n
(fila), AR
m,n
y bR
m
son conocidos.
Las variables de decisin vienen representadas por
xR
n
y zR es el valor de la funcin objetivo. El
poliedro que constituye la regin factible del
espacio de opciones se denota por S.
Con Ax = b se puede hacer la particin A = (B N),
donde BR
m,m
y NR
m,(n-m)
. Como B se construye
con las columnas linealmente independientes de A,
se garantiza la existencia de B
-1
.
Si se particiona x, es decir:
| || |

| || |

\ \\ \
| || |
= == =
B
x
x
x
Aspectos importantes de Programacin Lineal
Programacin Entera Jos Luis Quintero 8
donde x
B
R
m
y x
N
R
(n-m)
, las variables agrupadas
en x
B
se llaman variables bsicas y las agrupadas
en x
N
son no bsicas, entonces Ax = b es
equivalente a:
| || |


\ \\ \
= == =
N
x
x
( )
| |
=
|
\
B
N
x
B N b
x
Al desarrollar Bx
B
+ Nx
N
= b para obtener x
B
basta
premultiplicar por B
-1
:
x
B
= B
-1
b - B
-1
Nx
N
Si se hace x
N
=0 se tiene una solucin bsica
dada por x
B
=B
-1
b. Si adicionalmente se tiene que
x
B
0 entonces se trata de una solucin bsica
Aspectos importantes de Programacin Lineal
Programacin Entera Jos Luis Quintero 9
x
B
0 entonces se trata de una solucin bsica
factible.
Si se tiene una solucin factible cualquiera x, dada
por:
donde x
B
0 y x
N
0, entonces se puede expresar:
| || |
| || |

| || |


\ \\ \
| || |
= == =
N
B
x
x
x
luego:
donde es el conjunto de ndices no bsico
factible actual, a
j
es la j-sima columna de A y x
j
es la j-sima variable no bsica. Al evaluar el
objetivo en x se tiene:
( (( ( ) )) ) b Nx Bx
x
x
N B Ax
N B
N
B
= == = + ++ + = == =
| || |
| || |

| || |


\ \\ \
| || |
= == =
j j
j j
x x


= = =

1 1 1 1 j 1 j
B N
x B b B Nx B b B a B b y
Aspectos importantes de Programacin Lineal
Programacin Entera Jos Luis Quintero 10
objetivo en x se tiene:
Si x es una solucin ptima entonces la base
asociada B es tal que:
B
-1
b 0 ,
( (( ( ) )) )
N N B B
N
B
N B
x c x c
x
x
c c cx z + ++ +
| || |
| || |

| || |


\ \\ \
| || |
= == = = == = = == =
0

1
B N
c B N c
1. Idea bsica de los mtodos de corte
2. Aspectos de Programacin Lineal (PL)
3. El Mtodo Simplex Dual
Puntos a tratar
Programacin Entera Jos Luis Quintero 11
4. Anlisis de sensibilidad en PL
5. Corte entero puro de Gomory
6. Corte entero mixto de Gomory
Suponga que se tiene una solucin ptima pero infactible
para un problema de minimizacin. Ello significa que los
coeficientes de costo reducidos son no positivos, pero algn
elemento del vector de recursos es negativo. Ya se ver
cmo se puede llegar a esta situacin. Sea el siguiente
tablero correspondiente a un problema de minimizacin:
Z X
1
X
2
X
3
X
4
X
5
LD
1 -2 -3 -4 0 0 0
Ejemplo 1. La mecnica del Mtodo Simplex Dual
Programacin Entera Jos Luis Quintero 12
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 no
positivos, por lo que la solucin actual es ptima. Tambin se
observa que la solucin actual es infactible, pues hay
elementos negativos en el vector de recursos.
Se plantea el problema siguiente: es posible realizar una
secuencia de operaciones de pivoteo que permitan recuperar
factibilidad sin perder optimalidad? Es posible pivotear hasta
obtener una solucin factible que tambin sea ptima? La
respuesta es afirmativa.
La idea es hacer crecer los elementos del vector de recursos
hasta recuperar la factibilidad sin perder la optimalidad. Ello
requiere que si se hace un pivoteo, el elemento del vector de
recursos que sea negativo crezca hasta dejar de serlo, al
Ejemplo 1. La mecnica del Mtodo Simplex Dual
Programacin Entera Jos Luis Quintero 13
recursos que sea negativo crezca hasta dejar de serlo, al
mismo tiempo que ningn coeficiente de costo se haga
positivo.
De acuerdo al significado que se di a los coeficientes
tecnolgicos, si alguno de ellos es negativo entonces el
crecimiento de la variable asociada genera cantidades
adicionales de ese recurso en lugar de consumirlo, por lo
tanto su valor aumenta.
Este ltimo hecho indica que de hacer entrar una variable x
k
(k=1,2,...,n) a la base, ello ayudar a eliminar la infactibilidad
detectada en algn b
i
(aquel b
i
<0 para algn i=1,2,...,m),
siempre y cuando se cumpla que .
Luego, para hacer no negativo el elemento 4 del LD, se debe
pivotear en alguna de las posiciones sombreadas:
0 y
k
i
< << <
Ejemplo 1. La mecnica del Mtodo Simplex Dual
Programacin Entera Jos Luis Quintero 14
Z X
1
X
2
X
3
X
4
X
5
LD
1 -2 -3 -4 0 0 0
0 -1 -2 -1 1 0 -3
0 -2 1 -3 0 1 -4
lo cual llevara a entrar a la base a x
1
o a x
3
.
La seleccin de la variable que se debe hacer entrar a la base
depende del efecto del pivoteo sobre la optimalidad. La
relacin entre el coeficiente de costo reducido z
k
-c
k
y el valor
dado por (para ) indica en cunto se puede desmejorar
el valor actual del objetivo por un crecimiento unitario de la
variable x
k
que beneficie la factibilidad.
k
i
y 0 y
k
i
< << <
Ejemplo 1. La mecnica del Mtodo Simplex Dual
Programacin Entera Jos Luis Quintero 15
La idea es pivotear donde se desmejore lo menos posible el
valor actual de la funcin objetivo. Por ello, para escoger la
variable que va a entrar se hace un TRM entre los valores
negativos de la fila del objetivo y los valores negativos de la
fila pivote. El mtodo es como sigue:
1. Elija la fila pivote que corresponda al elemento del vector de
recursos ms negativo.
Ejemplo 1. La mecnica del Mtodo Simplex Dual
Programacin Entera Jos Luis Quintero 16
2. Elija la columna pivote haciendo el TRM entre los
coeficientes de costo reducidos y los valores negativos de la
matriz tecnolgica en esa fila pivote. Si no se puede hacer el
TRM por no encontrar denominadores negativos, el problema
no es factible.
En el ejemplo actual la fila pivote es la sombreada:
Z X
1
X
2
X
3
X
4
X
5
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:
Ejemplo 1. La mecnica del Mtodo Simplex Dual
Programacin Entera Jos Luis Quintero 17
Z X
1
X
2
X
3
X
4
X
5
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 X
1
X
2
X
3
X
4
X
5
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
Ejemplo 1. La mecnica del Mtodo Simplex Dual
Programacin Entera Jos Luis Quintero 18
Ahora se procede con la siguiente fila pivote, la cual se ha
sombreado:
Z X
1
X
2
X
3
X
4
X
5
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 X
1
X
2
X
3
X
4
X
5
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:
Ejemplo 1. La mecnica del Mtodo Simplex Dual
Programacin Entera Jos Luis Quintero 19
al pivotear se tiene:
Z X
1
X
2
X
3
X
4
X
5
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 adems
factible.
Grficamente, la situacin puede representarse en un caso
bidimensional como sigue:
ptimo infactible
Ganar factibilidad
sin perder optimalidad
x
2
Ejemplo 1. La mecnica del Mtodo Simplex Dual
Programacin Entera Jos Luis Quintero 20
(0,0) x
1
1. Idea bsica de los mtodos de corte
2. Aspectos de Programacin Lineal (PL)
3. El Mtodo Simplex Dual
Puntos a tratar
Programacin Entera Jos Luis Quintero 21
4. Anlisis de sensibilidad en PL
5. Corte entero puro de Gomory
6. Corte entero mixto de Gomory
INCLUSIN DE UNA NUEVA RESTRICCIN
Si se agrega una nueva restriccin, sta no afecta la
optimalidad pero si puede afectar la factibilidad: basta con que
la nueva restriccin haga que la solucin ptima actual sea
infactible. De ser ese el caso se puede aplicar el Mtodo
Simplex Dual para recuperar la factibilidad.
Se tiene una solucin ptima de base B, por lo que las
soluciones bsicas vienen dadas por la relacin:
Anlisis de sensibilidad
Programacin Entera Jos Luis Quintero 22
soluciones bsicas vienen dadas por la relacin:
y se agrega la restriccin
Esta ltima puede escribirse como:
donde y son, respectivamente, las componentes
bsicas y no bsicas del vector fila a
m+1
y x
n+1
es una variable
de holgura no negativa.
b B Nx B x
1
N
1 -
B

= == = + ++ +
1 m
1 m
b x a
+ ++ +
+ ++ +

1 m 1 n N
1 m
N B
1 m
B
b x x a x a
+ ++ + + ++ +
+ ++ + + ++ +
= == = + ++ + + ++ +
1 m
B
a
+ ++ + 1 m
N
a
+ ++ +
Luego, en la solucin ptima se tiene:
entonces, las primeras m soluciones bsicas vienen dadas por:
y la solucin bsica m+1, que es x
n+1
, ser factible si:
b B a b x x ) N B a a (
1 1 m
B 1 m 1 n N
1 1 m
B
1 m
N
+ ++ +
+ ++ + + ++ +
+ ++ + + ++ +
= == = + ++ +
b B Nx B x
1
N
1
B

= == = + ++ +
0 b B a b
1 1 m
B 1 m

+ ++ +
+ ++ +
Anlisis de sensibilidad
Programacin Entera Jos Luis Quintero 23
Es decir, si en el tablero ptimo, la holgura de la nueva
restriccin introducida es no negativa, entonces la nueva
restriccin no excluye la solucin ptima anteriormente
alcanzada. En ese caso la solucin ptima actual sigue siendo
factible, en caso contrario, debe recuperarse factibilidad con el
Mtodo Simplex Dual.
0 b B a b
B 1 m

+ ++ +
Sea el tablero inicial:
Z X
1
X
2
X
3
X
4
X
5
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. Inclusin de una nueva restriccin
Programacin Entera Jos Luis Quintero 24
cuyo tablero ptimo es:
Z X
1
X
2
X
3
X
4
X
5
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 restriccin
-x
1
+2x
3
2 ?
Al llevar la nueva restriccin a la forma se tiene:
x
1
- 2x
3
- 2 luego:
Como la solucin pasa a ser infactible, se agrega la nueva
( (( ( ) )) ) 0 8 6 2
10
6
1 1
0 1
0 1 2 b B a b
1 3
B 3
= == = = == = | || |

| || |

\ \\ \
| || |
| || |

| || |

\ \\ \
| || |
= == =

Ejemplo 2. Inclusin de una nueva restriccin
Programacin Entera Jos Luis Quintero 25
restriccin y se modifica el tablero anterior a:
Z X
1
X
2
X
3
X
4
X
5
X
6
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 cannica y se llega al tablero:
Z X
1
X
2
X
3
X
4
X
5
X
6
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
Ejemplo 2. Inclusin de una nueva restriccin
Programacin Entera Jos Luis Quintero 26
0 0 3 1 1 1 0 10
0 0 -1 -3 -1 0 1 -8
a partir del cual se puede aplicar el Mtodo Simplex Dual
para recuperar factibilidad.
1. Idea bsica de los mtodos de corte
2. Aspectos de Programacin Lineal (PL)
3. El Mtodo Simplex Dual
Puntos a tratar
Programacin Entera Jos Luis Quintero 27
4. Anlisis de sensibilidad en PL
5. Corte entero puro de Gomory
6. Corte entero mixto de Gomory
Sea P un modelo de programacin lineal entera pura de la
forma:
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

Programacin Entera Jos Luis Quintero 28

Se supondr que los datos son enteros. Suponga que se
resuelve el modelo lineal P y se halla x (solucin ptima). Si x
es entero FIN. En caso contrario, se genera una restriccin
(corte) que elimine a x de la regin factible y no elimine
ningn punto entero factible.
Sea B una base asociada a x, en tal caso
1
B b 0

1
B N
c B N c 0

Sea .
Si no es entero, entonces no es entero.
Se tiene donde al
descomponer se obtiene
Corte entero puro de Gomory
1 1 1 1 j 1 j
B N j j
j j
x B b B Nx B b B a x B b y x


= = =

B
x
x
0
| |
=
|
\
B k
k /(x )
1 1 1 j
B k k N k k j k
j
(x ) (B b) (B Nx ) (B b) y x

= =

1 j j
(x ) (B b) f ( y g )x

( (
= + +

Programacin Entera Jos Luis Quintero 29

con .
Como y , se sigue que .

1 j j
B k k k j k k
j
parte parte
parte
parte
fraccional fraccional
entera
entera
(x ) (B b) f ( y g )x

( (
= + +

j
k k
0 f 1 , 0 g 1 < < < <
k
0 f 1 < <
j
j k
j
g x 0

j
k j k
j
f g x 1

<

La restriccin
(1)
elimina con seguridad a la solucin ptima x porque en el
ptimo se exigi que , condicin que no es satisfecha
por la restriccin (1). A la restriccin (1) se le conoce como
CORTE ENTERO PURO DE GOMORY.
Corte entero puro de Gomory
j
k j k
j
f g x 0

k
0 f 1 < <
Programacin Entera Jos Luis Quintero 30
Para obligar a a tomar un valor entero, una vez que el
vector deje de ser nulo, basta que sea entero.
Por lo tanto la restriccin (1) es una condicin necesaria
para lograr el requisito del apartado anterior.
B k
(x )
N
x
j
k j k
j
f g x

Considere el siguiente modelo de programacin 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
= +
+
+

Programacin Entera Jos Luis Quintero 31

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 solucin ptima P1 = (x1,x2) = (20/9,14/9)
Ejemplo 3. Corte entero puro de Gomory
Programacin Entera Jos Luis Quintero 32
Se puede leer la solucin ptima P1 = (x1,x2) = (20/9,14/9)
W = -3520/9
El primer corte de Gomory viene dado por la restriccin
3 4
2 2 3 2 4 3 4 3 4
5 2 2 2 2 5
f g x g x x x 0 x x
9 9 9 9 9 9
=
Ejemplo 3. Corte entero puro de Gomory
Programacin Entera Jos Luis Quintero 33
En trminos 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
Ejemplo 3. Corte entero puro de Gomory
3 4 1 2
2 2 5
x x 2x 2x 7
9 9 9
+
3 4 5
2 2 5
x x x
9 9 9
+ =
Programacin Entera Jos Luis Quintero 34
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 Mtodo Simplex Dual para recuperar
factibilidad.
Despus del aplicar el Mtodo 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
Ejemplo 3. Corte entero puro de Gomory
Programacin Entera Jos Luis Quintero 35
Se puede leer la solucin ptima P2 = (x1,x2) = (5/2,1)
W = -380
El segundo corte de Gomory viene dado por la restriccin
3 5
1 1 3 1 5 5 5
1 1 1 1
f g x g x x 0 x
2 2 2 2
=
Ejemplo 3. Corte entero puro de Gomory
Programacin Entera Jos Luis Quintero 36
En trminos de las variables originales del problema se tiene
Al introducir el corte al tablero ptimo:
W X1 X2 X3 X4 X5 X6 LD
1 0 0 -40 0 -20 0 -380
Ejemplo 3. Corte entero puro de Gomory
5 1 2
1 1
x x x 3
2 2
+
5 6
1 1
x x
2 2
+ =
Programacin Entera Jos Luis Quintero 37
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
Se necesita aplicar el Mtodo Simplex Dual para recuperar
factibilidad.
Despus de aplicar el Mtodo 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
Ejemplo 3. Corte entero puro de Gomory
Programacin Entera Jos Luis Quintero 38
0 0 0 0 0 1 -2 1
Se puede leer la solucin ptima lineal entera
P3 = (x1,x2) = (3,0) W = -360
De modo que Z = 360.
Ejemplo 3. Corte entero puro de Gomory
Programacin Entera Jos Luis Quintero 39
1. Idea bsica de los mtodos de corte
2. Aspectos de Programacin Lineal (PL)
3. El Mtodo Simplex Dual
Puntos a tratar
Programacin Entera Jos Luis Quintero 40
4. Anlisis de sensibilidad en PL
5. Corte entero puro de Gomory
6. Corte entero mixto de Gomory
Sea P un modelo de programacin lineal entera mixta de la
forma:
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

Programacin Entera Jos Luis Quintero 41

Sea B una base asociada a x, en tal caso
1
B b 0

1
B N
c 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 al
descomponer se obtiene
Corte entero mixto de Gomory
1 1 1 1 j 1 j
B N j j
j j
x B b B Nx B b B a x B b y x


= = =

B k
k /(x )
1 1 1 j
B k k N k k j k
j
(x ) (B b) (B Nx ) (B b) y x

= =

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

(
= +

Programacin Entera Jos Luis Quintero 42

con .
Si se desea que sea entera, entonces se debe cumplir
solo una de las dos condiciones siguientes:

1 j
B k k k j k
j
parte
parte
fraccional
entera
(x ) (B b) f y x

(
= +

k
0 f 1 < <
B k
(x )
De la restriccin A se tiene que:
(2)
De la restriccin B se tiene que:
Corte entero mixto de Gomory
A. B.
1 1
B k k B k k
(x ) (B b) (x ) (B b) 1

( (
+

1 j
B k k k j k
j
(x ) (B b) f y x 0

(
=


Programacin Entera Jos Luis Quintero 43
De la restriccin B se tiene que:
(3)
Se definen
En funcin de y las restricciones (2) y (3) implican:
1 j
B k k k j k
j
(x ) (B b) f y x 1

(
=


{ } { }

j j
k k
J j / y 0 , J j / y 0
+
= > = <
J
+
J

(4)
(5)
Multiplicando ambos miembros de (5) por se tiene:
Corte entero mixto de Gomory
j j j j
k j k j k j j k
k k k k
j
j J j J j J
f y x f y x 0 f y x 0 y x f
+ + +

j j j j
k j k j k j j k k k k k
j
j J j J j J
f y x f y x 1 f y x 1 y x 1 f

k
f
0 >
Programacin Entera Jos Luis Quintero 44
Multiplicando ambos miembros de (5) por se tiene:
(6)
Como las condiciones (4) y (6) son exclusivas (por definicin)
se pueden combinar para obtener la restriccin
k
k
f
0
1 f
>

j
k
j k
k
k
j J
f
y x f
1 f

| |

|

(7)
A la restriccin (7) se le conoce como CORTE ENTERO
MIXTO DE GOMORY.
Corte entero mixto de Gomory
j j
k
j j k
k k
k
j J j J
f
y x y x f
1 f
+

| |

|

\

Programacin Entera Jos Luis Quintero 45
La restriccin (7) es una condicin necesaria para lograr
que sea entera.
B k
(x )
Considere el siguiente modelo de programacin 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
= +
+
+

Programacin Entera Jos Luis Quintero 46

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 estndar se tiene:

El tablero ptimo viene dado por
Ejemplo 4. Corte entero mixto de Gomory




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
=
+ + =
+ + =

Programacin Entera Jos Luis Quintero 47

El tablero ptimo viene dado por
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
Se puede leer la solucin ptima P1 = (x1,x2) = (24/5,13/5)
W = -63/5
El primer corte de Gomory viene dado por la restriccin
Ejemplo 4. Corte entero mixto de Gomory
4
4 3
5 1
1 4 1 3 1 4 3
4
1
5
f 3 2 3 4
y x y x f . x x
1 f 5 1 5 5 5
8 3 4


Programacin Entera Jos Luis Quintero 48

4 3
8 3 4
x x
5 5 5

Ejemplo 4. Corte entero mixto de Gomory
Programacin Entera Jos Luis Quintero 49
En trminos 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 -6/5 -1/5 0 -63/5
Ejemplo 4. Corte entero mixto de Gomory
3 4 1 2
3 8 5
x x x 6x 10
5 5 5
+
3 4 5
3 8 4
x x x
5 5 5
+ =
Programacin Entera Jos Luis Quintero 50
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
Se necesita aplicar el Mtodo Simplex Dual para recuperar
factibilidad.
Despus del aplicar el Mtodo 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
Ejemplo 4. Corte entero mixto de Gomory
Programacin Entera Jos Luis Quintero 51
0 0 0 3/8 1 -5/8 1/2
Se puede leer la solucin ptima P2 = (x1,x2) = (5,5/2)
W = -25/2
De modo que Z = 25/2.
Ejemplo 4. Corte entero mixto de Gomory
Programacin Entera Jos Luis Quintero 52
Pensamiento de hoy
Un experto es aquel que ya ha
cometido todos los errores
posibles en una materia muy
concreta.
Programacin Entera Jos Luis Quintero 53
concreta.
Niels Bohr