GRUPO 6

Vista previa del material en texto

UNIVERSIDAD NACIONAL FEDERICO VILLARREAL
FACULTAD DE INGENIERIA INDUSTRIAL Y SISTEMAS
TEMA: PROGRAMACIÓN ENTERA
CURSO: INVESTIGACIÓN DE OPERACIONES II
DOCENTE: ING. BENAVIDES MIRANDA, MARÍA ADELINA
Introducción
En el mundo de la industria y los negocios hay numerosas situaciones en las cuales se presentan
problemas de programación lineal para los cuales las variables de decisión sólo pueden tener valores de
números enteros y no fraccionarios. Esto debido a alguna razón física, por ejemplo si las variables de
decisión son números de personas, de artículos terminados, etc., será obvio que no podrán ser números
fraccionarios, pues esto no tendría ningún sentido.
Es aquí donde se plantea el problema de programación lineal como un caso de programación entera.
Para solucionar este tipo de problemas, hay algunos métodos que resultan adecuados, de los cuales en
este tema presentaremos los siguientes:
Algoritmo de Gomory
Método de ramificación y acotamiento
Objetivo general
Resolver problemas en los que se emplean variables enteras, utilizando los algoritmos de solución que se ajusten a las características de dichos problemas.
Objetivos específicos
Definir las características de un problema, enfocando su algoritmo de solución.
Formular un problema especifico utilizando el método de programación entera
Manejar algunas de las técnicas básicas utilizadas en la solución de problemas de programación entera.
Objetivos
¿Qué es programación entera?
La programación entera es el método empleado para resolver problemas que tienen variables de decisión enteras. Estos modelos se han considerado submodelos de la programación lineal con la característica de enteridad.
Si se requiere que todas las variables sean enteras se habla de programación entera pura; si se necesita que algunas de las variables de decisión sean números enteros, se tiene un problema de programación entera mixta.
En otro tipo de problemas solo se permite que las variables tomen un valor de cero o de uno; en estos casos se habla de programación entera binaria.
PROGRAMACIÓN ENTERA PURA
Un modelo entero puro es, como su nombre lo indica, un problema en el que se exige que todas las variables de decisión tengan valores enteros.
ALGORITMO DE GOMORY
El algoritmo Gomory es un procedimiento que se utiliza para encontrar soluciones enteras cuando los resultados arrojados son en decimales o fracciones, ya que antes se usó el método simplex para obtener soluciones positivas . Este método fue creado por Ralph Gomory
Modelo del entero puro
MAX Z= 7(X1) + 10(X2)
SUJETO A: -X1 + 3 X2 ≤ 6
 7 X1 + X2 ≤ 35
 X1 + X2 ≥ 0 
 X1, X2 
EJERCICIO APLICANDO EL MÉTODO DE GOMORY 
1° PASO:
Realizar el Método Simplex
(cambiar los signos de Z)
z= -7 X1 – 10 X2
2°PASO:
Se agrega una holgura en cada variable
Z= -7 X1 - 10 X2
-X1 + 3 X2 + S1= 6
7 X1 + X2 + S2= 35
3°PASO:
Se pasa a la tabla
		X1	X2	S1	S2	SOLUCIÓN
	S1	-1	3	1	0	6
	S2	7	1	0	1	35
	Z	-7	-10	0	0	0
Se busca el pivote para eso primero hallar la columna pivote y luego la fila pivote.
La columna pivote se toma en la Z, la fila con el número más negativo (-10)
	Tipo de desigualdad	Tipo de variable que aparece
	≥	- exceso + artificial
	=	+ artificial
	≤	+ holgura
4°PASO:
Se debe convertir en 1 toda la fila del pivote
La fila S1/3
		X1	X2	S1	S2	SOLUCIÓN
	S1	-1	3	1	0	6
	S2	7	1	0	1	35
	Z	-7	-10	0	0	0
Ahora hallar la fila pivote
Se tiene que dividir los valores de la solución entre los valores de la columna pivote (solución/ X2) y se toma el resultado menor positivo
El número pivote es la intersección de la columna y la fila pivote.
6/3=2
35/1=35
		X1	X2	S1	S2	SOLUCIÓN
	S1	-1	3	1	0	6
	S2	7	1	0	1	35
	Z	-7	-10	0	0	0
	X2	-1/3	1	1/3	0	2
	S2					
	Z					
5° PASO
Se halla los valores de S2 Y Z
		X1	X2	S1	S2	SOLUCIÓN
	S1	-1	3	1	0	6
	S2	7	1	0	1	35
	Z	-7	-10	0	0	0
	X2	-1/3	1	1/3	0	2
	S2	22/3	0	-1/3	1	33
	Z	-31/3	0	10/3	0	20
S2= X2(-1) + S2 , -1 es la inversa que se encuentra en la columna pivote
Z= X2(10) + Z , 10 es la inversa que se encuentra en la columna pivote
S2:
-1/3(-1)+7= 22/3
 1(-1)+1=0
 1/3(-1)+0= -1/3
 0(-1)+1= 1
 2(-1)+35= 33
Z:
-1/3(10)-7= -31/3
 1(10)-10= 0
 1/3(10)+0= 10/3
 0(10)+0= 0
 2(10)+0= 20
Se repite el procedimiento del SIMPLEX porque en Z quedó un resultado negativo
		X1	X2	S1	S2	SOLUCIÓN
	X2	-1/3	1	1/3	0	2
	S2	22/3	0	-1/3	1	33
	Z	-31/3	0	10/3	0	20
Se busca el pivote para eso primero hallar la columna pivote y luego la fila pivote.
La columna pivote se toma en la Z, la fila con el número más negativo (-31/3)
La fila se pivote seria el menor pero positivo.
2/ -(1/3)=- 6
33/ (22/3)=4.5
		X1	X2	S1	S2	SOLUCIÓN
	X2	-1/3	1	1/3	0	2
	S2	22/3	0	-1/3	1	33
	Z	-31/3	0	10/3	0	20
	X2	0	1	7/22	1/22	7/2
	X1	1	0	-1/22	3/22	9/2
	Z	0	0	63/22	31/22	133/2
X1/ (22/3)
X1(1/3) +X2
X1(31/3) +Z
Como salió positivo la solución pero fraccionario, utilizar el método GOMORY 
 Se debe realizar el método Gomory
1°PASO: Se tiene que elegir el menor valor de la última tabla
		X1	X2	S1	S2	SOLUCIÓN
	X2	-1/3	1	1/3	0	2
	S2	22/3	0	-1/3	1	33
	Z	-31/3	0	10/3	0	20
	X2	0	1	7/22	1/22	7/2
	X1	1	0	-1/22	3/22	9/2
	Z	0	0	63/22	31/22	133/2
	
X1= 9/2 X2= 7/2 Z= 133/2
2° PASO: Se elige X2= 7/2 y se toma en la restricción de la tabla
		X1	X2	S1	S2	SOLUCIÓN
	X2
	0	1	7/22	1/22	7/2
0X1+ 1X2 + (7/22)S1+(1/22)S2 =7/2
3° PASO: Se debe descomponer la restricción en enteros y fracciones menores a 1
0X1+ 1X2 + (7/22)S1+ (1/22)S2 = 7/2
1X2 + (7/22)S1+ (1/22)S2 = 3+1/2
4° PASO: Se acomodan los enteros de lado izquierdo y las fracciones al lado derecho
X2 – 3 = ½ -7/22 S1 – 1/22 S2
5° PASO: Se agrega el ≤ 0 a la restricción
X2 – 3 = ½ -7/22 S1 – 1/22 S2 ≤ 0 
6°PASO: Se eliminan los enteros
X2 – 3 = ½ -7/22 S1 – 1/22 S2 ≤ 0 
7°PASO: Se pasan de lado derecho los valores sin variable
-7/22 S1 – 1/22 S2 ≤ -1/2
8° PASO: Se agrega una variable de holgura
-7/22 S1 – 1/22 S2 + S3 = -1/2
9° PASO: Se agrega la restricción a la última tabla simplex
-7/22 S1 – 1/22 S2 + S3 = -1/2
		X1	X2	S1	S2	S3	SOLUCIÓN
	X2	0	1	7/22	1/22	0	7/2
	X1	1	0	-1/22	3/22	0	9/2
	S3	0	0	-7/22	-1/22	1	-1/2
	Z	0	0	63/22	31/22	0	133/2
10° PASO: Se busca el pivote, para eso se tiene que hallar la columna y fila pivote.
La columna pivote se halla dividiendo Z con S3, (Z/S3)
		X1	X2	S1	S2	S3	SOLUCIÓN
	X2	0	1	7/22	1/22	0	7/2
	X1	1	0	-1/22	3/22	0	9/2
	S3	0	0	-7/22	-1/22	1	-1/2
	Z	0	0	63/22	31/22	0	133/2
(63/22) / (-7/22)= 9
(31/22) / (-1/22)=31
Se elige el menor positivo
S3 será la fila pivote por tener en la solución un resultado(-1/2)
Se repite el método SIMPLEX
Se debe realizar otra vez el método de GOMORY, ya que hay resultados fraccionarios
		X1	X2	S1	S2	S3	SOLUCIÓN
	X2	0	1	7/22	1/22	0	7/2
	X1	1	0	-1/22	3/22	0	9/2
	S3	0	0	-7/22	-1/22	1	-1/2
	Z	0	0	63/22	31/22	0	133/2
	X2	0	1	0	0	1	3
	X1	1	0	0	1/7	-1/7	32/7
	S1	0	0	1	1/7	-22/7	11/7
	Z	0	0	0	1	9	62
S3/(-7/22)
S1(1/22) +X1
S1(-7/22) +X2
S1(-63/22) +Z
Se debe realizar el método Gomory
1°PASO: Se tiene que elegir el menor valor de la última tabla
X2=3 X1=32/7 S1=11/7 Z=62
		X1	X2	S1	S2	S3	SOLUCIÓN
	X2	0	1	7/22	1/22	0	7/2
	X1	1	0	-1/22	3/22	0	9/2
	S3	0	0	-7/22	-1/22	1	-1/2
	Z	0	0	63/22	31/22	0	133/2
	X2	0	1	0	0	1	3
	X1	1	0	0	1/7	-1/7	32/7
	S1	0	0	1	1/7	-22/7	11/7
	Z	0	0	0	1	9	62
	
2° PASO: Se elige S1=11/7 y se toma en la restricción de la tabla
		X1	X2	S1	S2	S3	SOLUCIÓN
	S1	0	0	1	1/7	-22/7	11/7
3° PASO: Se debe descomponer la restricción en enteros y fracciones menores a 1
0 X1 + 0 X2 + 1 S1 + (1/7) S2 –(22/7) S3 =11/7 
0 X1 + 0 X2 + 1 S1 + (1/7) S2 – (22/7) S3 = 11/7 
1 S1 + (1/7) S2 + (6/7) S3 – 4 S3 = 4/7 +1
4° PASO: Se acomodan los enteros de lado izquierdo y las fracciones al lado derecho
5° PASO: Se agrega el ≤ 0 a la restricción
6°PASO: Se eliminan los enteros
1 S1 -4 S3 – 1 = 4/7 – (1/7) S2 – (6/7) S3
1 S1 -4 S3 – 1 = 4/7 – (1/7) S2 – (6/7) S3 ≤ 0 
1 S1 -4 S3 – 1 = 4/7 – (1/7) S2 – (6/7) S3 ≤ 0 
7°PASO: Se pasan de lado derecho los valores sin variable
– (1/7) S2– (6/7) S3 ≤ -4/7
8° PASO: Se agrega una variable de holgura
9° PASO: Se agrega la restricción a la última tabla simplex
– (1/7) S2 – (6/7) S3 + S4 = -4/7
		X1	X2	S1	S2	S3	S4	SOLUCIÓN
	X2	0	1	0	0	1	0	3
	X1	1	0	0	1/7	-1/7	0	32/7
	S1	0	0	1	1/7	-22/7	0	11/7
	S4	0	0	0	-1/7	-6/7	1	-4/7
	Z	0	0	0	1	9	0	62
10° PASO: Se busca el pivote, para eso se tiene que hallar la columna y fila pivote.
La columna pivote se halla dividiendo Z con S4, (Z/S4)
		X1	X2	S1	S2	S3	S4	SOLUCIÓN
	X2	0	1	0	0	1	0	3
	X1	1	0	0	1/7	-1/7	0	32/7
	S1	0	0	1	1/7	-22/7	0	11/7
	S4	0	0	0	-1/7	-6/7	1	-4/7
	Z	0	0	0	1	9	0	62
S2= 1 / (-1/7) = 7
S3= 9 / (-6/7) = 10.5
Se elige el menor positivo
S4 será la fila pivote por tener en la solución un resultado negativo ( -4/7)
Se vuelve a realizar el método SIMPLEX
Se vuelve hacer el método SIMPLEX
		X1	X2	S1	S2	S3	S4	SOLUCIÓN
	X2	0	1	0	0	1	0	3
	X1	1	0	0	1/7	-1/7	0	32/7
	S1	0	0	1	1/7	-22/7	0	11/7
	S4	0	0	0	-1/7	-6/7	1	-4/7
	Z	0	0	0	1	9	0	62
	X2	0	1	0	0	1	0	3
	X1	1	0	0	0	-1	1	4
	S1	0	0	1	0	-4	1	1
	S2	0	0	0	1	6	-7	4
	Z	0	0	0	0	3	7	58
S4 / (-1/7)
S2 (-1/7) +S1
S2 (0) +X2
S2 (-1/7) + X1
S2 (-1) + Z
X1 = 4 X2 = 3 Z = 58
Método de Ramificación
Los métodos de ramificación y acotamiento pretenden hacer lo mismo que los métodos de corte con la diferencia de que estos utilizan la estrategia de
"Dividir y Vencerás" . Esto consiste en dividir la región factible de tal manera que la solución optima no entera no se incluya en la nueva región, dando
como resultado nuevos subproblemas a los cuales también se les llama "Métodos de Lang - Doig" y "Métodos de bifurcación de y acotamiento" .
El proceso consta de dividir el problema y subdividir los subproblemas hasta que se pueda demostrar que ninguno de los subproblemas tiene solución
óptima mejores a una solución entera calculable. 
Formulación
Hay problemas en los cuales los valores de las variables de decisión no pueden contener decimales.
Caso de fabricación de artefactos para su venta, asistencia de personas a eventos (binario), etc.
Estos se conocen como problemas de programación entera, para ellos hay métodos de resolución, dado que simplex entrega soluciones con números reales.
Ramificación y acotamiento (Branch and Bound)
Planos de corte
Ejemplo
	MAX Z(x)= 3x1+ 4x2
S.A
	2x1 + x2 ≤ 6
	2x1 + 3x2 ≤ 9
	x1;x2 ≥ 0 , enteras
Solución del problema:
x1 = 9/4 ; x2 = 3/2
	P0
	x1 = 9/4
x2 = 3/2
	Z = 12.75
	MAX Z(x)= 3x1+ 4x2
S.A
	2x1 + x2 ≤ 6
	2x1 + 3x2 ≤ 9
	x1 ≤ 2
	x1;x2 ≥ 0 , enteras
x1 = 2
	x2 ≤ 2
	x2 ≤ 5/3
	P1
	x1 = 2
x2 = 5/3
	Z = 12.667
	MAX Z(x)= 3x1+ 4x2
S.A
	2x1 + x2 ≤ 6
	2x1 + 3x2 ≤ 9
	x1 ≥ 3
	x1;x2 ≥ 0 , enteras
x1 = 3
	x2 ≤ 0
	x2 ≤ 1
	P2
	x1 = 3
x2 = 0
	Z = 9
x1 ≤ 2
x1 ≥ 3
Solución Entera
	P1
	x1 = 2
x2 = 5/3
	Z = 12.667
	MAX Z(x)= 3x1+ 4x2
S.A
	2x1 + x2 ≤ 6
	2x1 + 3x2 ≤ 9
	x1 ≤ 2
	x2 ≤ 1
	x1;x2 ≥ 0 , enteras
x2 = 1
	x1 ≤ 5/2
	x1 ≤ 3
	x1 ≤ 2
	P3
	x1 = 2
x2 = 1
	Z = 10
	MAX Z(x)= 3x1+ 4x2
S.A
	2x1 + x2 ≤ 6
	2x1 + 3x2 ≤ 9
	x1 ≤ 2
	x2 ≥ 2
	x1;x2 ≥ 0 , enteras
x2 = 2
	x1 ≤ 2
	x1 ≤ 3/2
	x1 ≤ 2
	P4
	x1 = 3/2
x2 = 2
	Z = 12.5
x2 ≤ 1
x2 ≥ 2
Solución Entera
	P4
	x1 = 3/2
x2 = 2
	Z = 12.5
	MAX Z(x)= 3x1+ 4x2
S.A
	2x1 + x2 ≤ 6
	2x1 + 3x2 ≤ 9
	x1 ≤ 2
	x2 ≥ 2
	x1 ≤ 1
	x1;x2 ≥ 0 , enteras
x1 = 1
	x2 ≤ 4
	x2 ≤ 7/3
	x2 ≥ 2
	P5
	x1 = 1
x2 = 7/3
	Z = 12.333
	MAX Z(x)= 3x1+ 4x2
S.A
	2x1 + x2 ≤ 6
	2x1 + 3x2 ≤ 9
	x1 ≤ 2
	x2 ≥ 2
	x1 ≥ 2
	x1;x2 ≥ 0 , enteras
x1 = 2
	x2 ≤ 2
	x2 ≤ 5/3
	x2 ≥ 2
	P6
	x1 = 2
x2 = ?
	Problema Infactible
x1 ≤ 1
x1 ≥ 2
	P5
	x1 = 1
x2 = 7/3
	Z = 12.333
	MAX Z(x)= 3x1+ 4x2
S.A
	2x1 + x2 ≤ 6
	2x1 + 3x2 ≤ 9
	x1 ≤ 2
	x2 ≥ 2
	x1 ≤ 1
	x2 ≤ 2
	x1;x2 ≥ 0 , enteras
x2 = 2
	x1 ≤ 2
	x1 ≤ 3/2
	x1 ≤ 2
	x1 ≤ 1
	P7
	x1 = 1
x2 = 2
	Z = 11
	MAX Z(x)= 3x1+ 4x2
S.A
	2x1 + x2 ≤ 6
	2x1 + 3x2 ≤ 9
	x1 ≤ 2
	x2 ≥ 2
	x1 ≤ 1
	x2 ≥ 3
	x1;x2 ≥ 0 , enteras
x2 = 3
	x1 ≤ 3/2
	x1 ≤ 0
	x1 ≤ 2
	x1 ≤ 1
	P8
	x1 = 0
x2 = 3
	Z = 12
x2 ≤ 2
x2 ≥ 3
Solución Final
Solución Entera
P0
Z = 12.75
P1
Z = 12.667
P2
Z = 9
P3
Z = 10
P4
Z = 12.5
P5
Z = 12.33
P6
Infactible
P7
Z = 11
P8
Z = 12
ÁRBOL DE SOLUCIÓN
Es un método perteneciente a la programación lineal, por lo que su base es un algoritmo matemático que tiene como finalidad resolver un problema indeterminado formulado a través de ecuaciones lineales, optimizando así una función objetivo también lineal que generalmente se refiere a costo o a tiempo. 
La programación binaria se utiliza en problemas de asignación o de toma de decisiones enfocadas a hacer o no una tarea.
Modelo PEB
Debido a que estos problemas involucran sólo dos posibilidades, este tipo de decisiones se puede representar mediante variables de decisión restringidas a sólo dos valores, por ejemplo, 0 y 1. De esta forma, la j-ésima decisión sí o no se puede representar por xj , tal que
xj={
1 Si la decisión j es sí 
0 Si la decisión j es no 
Programación Entera Binaria
Ejemplo:
VARIABLES DE DECISIÓN: debemos decidir que proyecto o mezcla de proyectos se deben emprender.
Xj={
 Para j= 1(convertidor catalítico),2(software),3(ampliación almacén)
MAXIMIZAR Z=25000x1 +18000x2 + 32000x3
Sujeto a
 8000x1 + 6000x2 + 12000x3 ≤ 20000
 7000x1 + 4000x2 + 8000x3 ≤ 16000
xj es binaria, para j=1,2,3
1(el proyecto j se realiza) 
0(en caso contrario)
Es un método muy parecido al de ramificación y acotamiento para modelos mixtos y puros. Sin embargo su diferencia radica en que al modelo se le agrega la restricción xj=0 y por otro lado al modelo se le agrega la restricción xj= 1. Esto genera que en cada nivel de ramificación el número de variables se vaya reduciendo.
Este modelos tiene tres partes:
Ramificación
Acotamiento 
Sondeo
Método De Ramificación y Acotamiento para PEB
Ramificación 
Cuando se manejan variables binarias, la forma más sencilla de partir el conjunto de soluciones factibles es fijar el valor de una variable en x1=0 para un subconjunto y en x1 =1 para el otro. Al hacer esto, el problema completo queda dividido en dos subproblemas más pequeños.
Acotamiento 
es necesario obtener, para cada subproblema, una cota que muestre el nivel de precisión de su mejor solución factible. La forma más común de hacerlo es resolver con rapidez un relajamiento sencillo del subproblema. el relajamiento de un problema se obtiene eliminando un conjunto de restricciones que dificultan obtener una solución. En los problemas de PE ,el relajamiento que más se usa es el relajamiento de PL que elimina este conjunto de restricciones. 
Sondeo
Un subproblema se puede sondear, y, por tanto, ya no tomarse en cuenta, en las tres formas:
PRUEBA 1.Tener una solución entera y se debe guardarse como la primera solución incumbente o de apoyo junto con su valor de Z. Este valor se denota por 
 Z* = valor de Z de la solución de apoyo actual
PRUEBA 2. un subproblema se sondea siempre que su 
 Cota ≤ Z*.
PRUEBA 3.Si el método simplex encuentra que el relajamiento de PL de un subproblema no tiene soluciones factibles, entonces el subproblema en sí no debe tener soluciones factibles, de forma que puede eliminarse.
La QUEMO CHEMICAL COMPANY esta considerando 3 posibles proyectos de mejora para su planta :un nuevo convertidor catalítico, un nuevo programa de computadora para controlar las operaciones y la expansión del almacén . Los requerimientos de capital y las limitaciones de presupuesto en los dos años siguientes impiden que la firma emprenda todo los proyectos en este momento , el valor actual neto(Van) de cada uno de los proyectos, los requerimientos de capital, y los fondos disponibles para los dos años siguientes se presentan en la siguiente tabla.
¿Qué proyectos deberían ejecutarse para maximizar la inversión?
EJERCICIO
	Año($)	Convertidor catalítico(x1)	Software(x2)	Ampliación de almacén (x3)	Fondos disponibles
	1	8000	6000	12000	20000
	2	70004000	8000	16000
	Valor actual neto	25000	18000	32000	
VARIABLES DE DECISIÓN: 
Xj={
 Para j= 1,2,3
El modelo MPB:
MAX Z(x)= 25000x1 + 18000x2 + 32000x3 
 SSR
 8000x1 + 6000x2 + 12000x3 ≤ 20000
 7000x1 + 4000x2 + 8000x3 ≤ 16000
Xj es binaria para j=1,2,3
1(el proyecto j se realiza) 
0(en caso contrario)
 Dividir el problema general en subproblemas.
 ITERACIÓN 1
Subproblema 1 : x1=0
MAX Z(x)= 0+ 18000x2 + 32000x3 
 SSR
 6000x2 + 12000x3 ≤ 20000
 4000x2 + 8000x3 ≤ 16000
Xj es binaria para j=1,2,3
Subproblema 2 : x1=1
MAX Z(x)= 25000 + 18000x2 + 32000x3 
 SSR
 6000x2 + 12000x3 ≤ 12000
 4000x2 + 8000x3 ≤ 9000
Xj es binaria para j=1,2,3
TODO
X1=1
X1=0
VARIABLE:
x1
RAMIFICACIÓN
Su relajamiento de PL se obtiene mediante la sustitución del último renglón del modelo (xj es binaria, para j=1, 2, 3, 4) por la siguiente nueva (relajada) versión de su restricción 
0 ≤ xj ≤ 1 para j = 1, 2, 3
Usando el método simplex para resolver con rapidez su relajación PL que se obtiene de su solución óptima.
 
(x1, x2, x3 ) = (0, 1, 1/2) con z = 59000 
Teniendo las dos subproblemas debemos hallar las cotas de cada una.
Relajamiento de PL del subproblema 1: x1 ≤ 0 y 0 ≤ xj ≤ 1 
 para j =1, 2, 3 . 
Solución óptima: (x1, x2, x3 ) = (0, 1, 1) con z = 50000 
Relajamiento de PL del subproblema 2: x1 ≤ 1 y 0 ≤ xj ≤ 1 
 para j =1, 2, 3 
Solución óptima: (x1, x2, x3 ) = (1,1,1/2) con z = 59000
TODO
X1=1
X1=0
VARIABLE:
x1
50000
(0,1,1)
59000
(1,1,1/2)
59000
(1,1,1/2)
Acotamiento
Árbol de solución después de la primera iteración.
SONDEO
Una forma se ilustra con los resultados del subproblema 1 que se dieron en el nodo x1=0 solución óptima de este relajamiento de PL, (x1, x2, x3)=(0, 1, 1) , es una solución entera. En consecuencia, esta solución debe ser también la solución óptima del subproblema 1, que debe guardarse como la primera solución incumbente o de apoyo del problema completo, junto con su valor de Z. 
Este valor se denota por:
 Z* = 50000
Ahora, como ya se resolvió, el subproblema 1 se sondea (elimina).
El subproblema 2 tiene una cota de 59000 que es mayor que 50000. No obstante, puede ocurrir más adelante, para los descendientes de este subproblema (nuevos problemas más pequeños creados al ramificar más este subproblema y quizá después al ramificarlo más en “generaciones” subsecuentes).
TODO
X1=1
X1=0
VARIABLE:
x1
50000 = z*
(0,1,1)=incumbente
59000
59000
Subproblema 3 : x1=1 , x2= 0
MAX Z(x)= 25000 + 32000x3 
 SSR
 0 + 12000x3 ≤ 12000
 0 + 8000x3 ≤ 9000
Xj es binaria para j = 3
Subproblema 4 : x1=1,x2=1
MAX Z(x)= 43000 + 32000x3 
 SSR
 12000x3 ≤ 6000
 8000x3 ≤ 5000
Xj es binaria para j = 3
Iteración 2
El único subproblema que queda corresponde al nodo x1=1 por lo que se ramificará este nodo para crear dos nuevos subproblemas.
Teniendo las dos subproblemas debemos hallar las cotas de cada una.
Relajamiento de PL del subproblema 3: x1 ≥ 1 , x2 ≤ 0 y 0 ≤ xj ≤ 1 para j =1, 2, 3 . 
 
Solución óptima: (x1, x2, x3 ) = (1, 0, 1) con z = 57000
Relajamiento de PL del subproblema 2: x1 ≥ 1 , x2 ≥ 1 y 0 ≤ xj ≤ 1 para j =1, 2, 3 
 
Solución óptima: (x1, x2, x3 ) = (1,1,1/2) con z = 59000
TODO
X1=1
X1=0
VARIABLE
x1
50000
59000
59000
X2=1
X2=0
59000
(1,1,1/2)
57000=Z*
(1,0,1) = incumbente
x2
Árbol de solución después de la segunda iteración
Sondeo
Las cota del subproblema 3 es mayor que Z*= 50000 y también es una solución entera .por lo tanto mi nueva solución incumbente o de apoyo es z*= 57000 .
En cambio para el subproblema 4 pude ser más adelante que los descendientes de este subproblema podemos encontrar nuevas soluciones de apoyo lo que se procede a ramificar .
ITERACIÓN 3
Como la variable de ramificación x3 es la última variable, si se fija su valor en 0 o en 1, se crea una solución y no un subproblema que requiera más investigación. Las soluciones creadas son
X3=0: ( x1, x2, x3) = (1, 1, 0) es factible, con Z = 43000 
X3=1: (x1, x2, x3 ) = (1, 1, 1) es factible.
Se sondea x3=0 por ser cota = 43000 ≤ Z* = 57000
Se tiene ahora el árbol de solución. Observe que no hay subproblemas restantes (sin sondear).
 la prueba de optimalidad indica que la solución de apoyo actual (x1, x2, x3) = (1, 0, 1) es óptima, y el problema termina aquí.
TODO
X1=1
X1=0
VARIABLE
x1
50000
59000
59000
X2=1
X2=0
59000
(1,1,1/2)
57000=Z*
(1,0,1) = incumbente
= solución optima
x2
X3=1
X3=0
x3
43000
(1,1,0)
CONCLUSIÓN
x1= convertidor catalítico
x3= ampliación almacén
z=57000
se logra obtener una mejor beneficio de las inversiones en escoger los proyectos convertidor catalítico y ampliación almacén
que es de $57000.
PROGRAMACION ENTERA MIXTA
Son aquellos en los que hay al mismo tiempo variables continuas y variables que sólo pueden tomar valores enteros.
Hay dos técnicas de resolución de este tipo de problemas:
La de los cortes de Gomory (CG). 
La de bifurcación y acotación (BA): Es la que más se utiliza y la más eficiente computacionalmente.
Algoritmo entero-mixto de Gomory
PROCEDIMIENTO: 
El algoritmo comienza en la solución optima de la programación lineal y modifica el área de solución añadiendo cortes. El corte se realiza a partir de los componentes fraccionales de los coeficientes del renglón fuente. La variable del renglón fuente es no entera.
PASOS:
Se resuelve el problema entero mixto como un problema lineal, sin considerar por el momento las condiciones enteras.
Si el resultado optimo del paso 1 o 4 las variables que son enteras lo son , se detiene el algoritmo. Se ha llegado al resultado optimo del problema original. De otra forma se continua con el paso 3.
Se selecciona el mayor XBi para generar un corte de la siguiente forma:
Se añade este corte como una restricción adicional junto con una variable de exceso. Se resuelve por el método dual simplex y se regresa al paso 2.
Ejemplo:
Max Z = 3X1 + 7X2
 2X1 + 2X2 ≤ 9
 X1 + 3X2 ≤ 11
 X2  ≥ 0 , enteras
 X1  ≥ 0 , continuas
Max Z = 3X1 + 7X2
Sujeto a: 2X1 + 2X2 + X3 = 9
 X1 + 3X2 + X4 = 11
 X2 + X3  ≥ 0 , enteras
 X1 + X4  ≥ 0 , continuas
En el siguiente ejemplo se usa el corte para variables enteras > h
RESOLVIENDO
PASO 1: Resolver sin tomar en cuenta las condiciones enteras 
F. entrante
F. saliente
F. vieja
- Coefi. Pivote 
x F.E
+ F.V
PASO 2: Como el resultado optimo de X1 = 5/4, pero como X2 = 39/12 no es entero se continua con el método Gomory.
PASO 3: Se selecciona la restricción X2 omitiendo el 0 y 1.
Como X3 debe ser entera y X4 es continua, el corte se reduce a:
Formula
Se realiza un corte.
Se debe descomponer las fracciones en enteros y fracciones menores que 1 positivas.
PASO 4: Se añade la restricción, se resuelve por el método simplex y se regresa al paso 2
PASO 2: El resultado optimo es: X1 = 3/2 , X2 = 3, X5 = 1/2, Max Z = 5/12.
El valor de X2 se detiene el algoritmo.
Se ha llegado al resultado optimo del problema original. 
Esta es la restricción que se agregara a la tabla
Valores óptimos
÷
½ : -1/12 = 6
2 : -1/2 = 4
¼ - 1/12X3 – 1/2X4 ≤ 0
Aplicaciones
Existen múltiplesaplicaciones de modelos de programación entera como apoyo a la toma de decisiones. Algunas aplicaciones típicas son:
Problemas de localización de instalaciones 
Consiste en decidir la ubicación de las instalaciones para satisfacer a los clientes maximizando las utilidades.
Problemas de ruteo vehicular
Es un problema complejo de optimización que tiene como objetivo minimizar los costos de transporte asociados a rutas de reparto.
Diseño de una red de producción y distribución
Despacho de envíos
Los problemas de programación entera surgen con frecuencia cuando los valores de algunas o de todas las variables de decisión deben restringirse a valores enteros. Existen también muchas aplicaciones que necesitan decisiones sí o no (aquí se incluyen las relaciones combinatorias que pueden expresarse en términos de tales decisiones) que se puede representar por variables binarias. Estos factores han hecho que la programación entera sea una de las técnicas de investigación de operación de mayor aplicación. 
Conclusión
GRACIAS