contabilidad

25 de Junio de 2012

RESOLUCIÓN DE
MODELOS DE
PROGRAMACIÓN
ENTERA
MÉTODOS DE CORTE
CORTES DE GOMORY
Postgrado de Investigación de Operaciones
Facultad de Ingeniería
Universidad Central de Venezuela
Programación Entera

José Luis Quintero 1

Puntos a tratar

1. Idea básica de los métodos de corte
2. Aspectos de Programación Lineal (PL)
3. El Método Simplex Dual
4. Análisis desensibilidad en PL
5. Corte entero puro de Gomory
6. Corte entero mixto de Gomory

Programación Entera

José Luis Quintero 2

Métodos de corte
• La idea básica de los métodos de corte consiste en
reestructurar el espacio de soluciones originales
(continuas) de tal forma que la solución entera
aparezca como un punto extremo del espacio de
soluciones así modificado.
• Estareestructuración del espacio de soluciones se
lleva a cabo mediante la introducción de
restricciones (planos de corte) diseñadas para este
efecto que sistemáticamente cortan o truncan el
espacio de soluciones de tal forma que ningún
punto factible relevante sea excluído. Es decir,
estas restricciones, cortan o truncan partes no
factibles del espacio de soluciones.

Programación Entera

José LuisQuintero 3

Métodos de corte

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

• El primer algoritmo finito de cortes se debe a R.
Gomory en 1958 para el problema entero puro. Y
más adelante en 1960 expandió la teoría del
algoritmo para atacar problemasenteros mixtos.

Programación Entera

José Luis Quintero 4

Esquema general de los métodos de corte
• PASO 1. Resolver el modelo de programación lineal continuo
asociado al problema entero lineal.
a. Si la solución del modelo asociado es no factible, el
problema 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:
• PASO 2. Utilice el método de corte para generar un plano de
corte. Añada la restricción que representa el corte a las
restricciones del modelo y aplique el paso 1. La nueva
restricción elimina la solución óptima del modelo continuo de
la región factible y no elimina ningún punto entero. El métodose repite hasta alcanzar la solución óptima que satisfaga las
restricciones enteras.

Programación Entera

José Luis Quintero 5

Puntos a tratar

1. Idea básica de los métodos de corte
2. Aspectos de Programación Lineal (PL)
3. El Método Simplex Dual
4. Análisis de sensibilidad en PL
5. Corte entero puro de Gomory
6. Corte entero mixto de Gomory

Programación Entera

José LuisQuintero 6

Aspectos importantes de Programación Lineal
• Un modelo de minimización de PL, puede ser
expresado por:
P:

min z = cx

s.a. Ax = b
x≥0
donde c∈Rn (fila), A∈Rm,n y b∈Rm son conocidos.
• Las variables de decisión vienen representadas por
x∈Rn y z∈R es el valor de la función objetivo. El
poliedro que constituye la región factible del
espacio de opciones se denota por S.Programación Entera

José Luis Quintero 7

Aspectos importantes de Programación Lineal
• Con Ax = b se puede hacer la partición A = (B N),
donde B∈Rm,m y N∈Rm,(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:
 xB 
x= 
 xN 

donde xB∈Rm y xN∈R(n-m), las variables agrupadas
en xB sellaman variables básicas y las agrupadas
en xN son no básicas, entonces Ax = b es
equivalente a:
 xB 
(B N)  x  = b
 N
Programación Entera

José Luis Quintero 8

Aspectos importantes de Programación Lineal
• Al desarrollar BxB + NxN = b para obtener xB basta
premultiplicar por B-1:
xB = B-1 b - B-1 NxN
Si se hace xN=0 se tiene una solución básica
dada por xB=B-1b. Si...