GRUPO 14

Vista previa del material en texto

INVESTIGACIÓN DE 
OPERACIONES
PROGRAMACIÓN 
ENTERA
Ing. Maria Adelina Benavides Miranda
2
INTRODUCCIÓN
Muchas aplicaciones no se pueden abordar con los métodos de solución de la programación lineal porque tienen el principio de la "no divisibilidad", esto es, algunas o todas las variables deben tomar valores enteros. Con frecuencia deben construirse modelos para asignar personas, máquinas o vehículos a las actividades, en cantidades enteras. Si el problema de exigir valores enteros es la única diferencia que tiene un problema con su formulación en términos de programación lineal, entonces se trata de un problema de programación lineal entera o simplemente de programación entera. Así que el modelo de programación entera es simplemente un modelo matemático de programación lineal que agrega la condición de que algunas o todas las variables deben ser enteras. 
3
Definicion 
La programación entera es un conjunto de técnicas de la investigación operativa que permiten solución a una variante para el programa lineal cuando las variables de decisión no pueden tomar valores fraccionarios. Para el modelo de Programación Lineal se optimiza una función sobre una región convexa, mientras que en la Programación Entera se optimiza sobre una región de factibilidad que generalmente no es convexa. Por lo tanto, la solución de problemas enteros; resulta más complicada que la Programación Lineal. Es importante anotar que las técnicas desarrolladas hasta ahora, dentro de la Programación Entera, distan mucho de resolver el 100% de los problemas de decisión de variable entera. 
4
Aplicaciones
Análisis de inversión 
En ocasiones se usa programación lineal para tomar decisiones de presupuesto de capital acerca de cuánto invertir en diferentes proyectos. Sin embargo, algunas decisiones de presupuestos no se refieren a cuánto invertir sino al hecho de si debe invertirse una cantidad fija. 
5
Elección del sitio 
En la economía globalizada, muchas corporaciones instalan nuevas plantas en diversas regiones del planeta para aprovechar la mano de obra más barata y otras ventajas. Antes de elegir la ubicación de esas instalaciones, deben analizarse y compararse muchos sitios potenciales. 
6
Diseño de una red de producción y distribución
Los fabricantes de hoy se enfrentan a una gran presión competitiva para lograr que sus productos lleguen al mercado con mayor rapidez, así como para reducir sus costos de producción y distribución. 
7
Despacho de envíos 
Una vez que la red de producción y distribución haya sido diseñada y puesta en operación, deben tomarse decisiones operativas diarias acerca de cómo realizar los envíos. Algunas de estas decisiones también son de sí o no.
8
MODELOS
Las variantes del modelo de programación lineal, tienen que ver con las condiciones de valores enteros que tienen que tomar algunas de las variables de decisión. Los casos son los siguientes:
Modelo Entero (PE). 
Modelo Entero Mixto (PEM).
Modelo Entero Cero Uno o Binario (PECU).
9
Modelo entero (PE) 
Un modelo entero puro (PLE) es, como su nombre lo indica, un problema en el que se exige que todas las variables de decisión tengan valores enteros. Por ejemplo los problemas de transporte. 
10
Modelo Entero Mixto (PEM)
Un modelo de programación lineal entera mixta (PLEM) es un problema en el que solo se requieren que algunas variables tengan valores enteros mientras que otras pueden asumir cualquier valor continuo. Por ejemplo, los modelos de dicotomía. 
11
Problema Entero Cero Uno o Binario (PECU).
En los problemas enteros binarios se restringe el valor de las variables a 0 ó 1. Son de particular interés debido a que se pueden usar las variables 0-1 para representar decisiones dicotomicas (si ó no). Diversos problemas de asignación, ubicación de plantas, producción y elaboración de cartera, son de programación lineal entera 0-1. 
MÉTODO DE SOLUCIÓN GRÁFICO 
13
SOLUCIÓN DE PROBLEMAS ENTEROS
En primer lugar mostraremos con un ejemplo las dificultades que aparecen a la hora de calcular una solución óptima para un modelo lineal entero.
Sea el modelo lineal
 
 Max z = 80x1 + 45x2
 sujeto a
 x1 + x2 ≤ 7
 12x1 + 5x2 ≤ 60
 x1, x2 ≥ 0 y enteras
14
En la siguiente grafica aparecen señaladas las soluciones del modelo lineal entero
15
Otra manera de obtener una solución para el modelo entero es resolverlo sin tener en cuenta la restricción de que las variables deben tomar valores enteros y obtener la solución entera optima por redondeo. Es decir, resolvemos el problema de la página quitando la restricción de enteras a las variables; llamaremos a este problema relajado. En la siguiente grafica se da la solución óptima del problema relajado.
16
17
En la siguiente gráfica, donde se representan todas las aproximaciones por redondeo, se puede ver que el punto (4, 4) no verifica las restricciones.
18
Solución grafica de problemas enteros
En esta sección ilustraremos la técnica de ramificación y acotación resolviendo gráficamente el problema de la página anterior. Esta técnica consiste en resolver el problema relajado y, si la solución no es entera, se divide el problema relajado en dos (ramificar) quitando un trozo de la región que no contiene la solución del problema entero. Se resuelven los nuevos problemas y, si la solución no es entera, se hace una nueva ramificación.
19
Problema entero: PE	 Problema relajado: PR
Max z = 80x1 + 45x2 	Max z = 80x1 + 45x2
 sujeto a sujeto a
 x1 + x2 ≤ 7 x1 + x2 ≤ 7
 12x1 + 5x2 ≤ 60	 12x1 + 5x2 ≤ 60
x1, x2 ≥ 0 y enteras x1, x2 ≥ 0
20
 P2 P3
 Max z = 80x1 + 45x2	 Max z = 80x1 + 45x2 sujeto a sujeto a
 x1 + x2 ≤ 7	 x1 + x2 ≤ 7
 12x1 + 5x2 ≤ 60	 12x1 + 5x2 ≤ 60
 x1 ≤ 3	x1 ≥ 4
 x1, x2 ≥ 0 x1, x2 ≥ 0
21
22
Hay problemas no terminales y hay que seguir ramificando. Elegimos un problema para ramificar, en este caso solo tenemos la opción de elegir el problema P3. En ese problema elegimos una variable para ramificar, en este caso solo podemos elegir la variable x2. Se generan los dos problemas siguientes:
 P4 P5
 Max z = 80x1 + 45x2	 Max z = 80x1 + 45x2
 Sujeto a	 sujeto a
 x1 + x2 ≤ 7 x1 + x2 ≤ 7
 12x1 + 5x2 ≤ 60	 12x1 + 5x2 ≤ 60
 x1 ≥ 4, x2 ≤ 2	 x1 ≥ 4, x2 ≥ 3
 x1, x2 ≥ 0	 x1, x2 ≥ 0
23
La solución óptima para los dos problemas recién creados se recoge en la gráfica.
24
Repetimos el proceso de ramificación. Eligiendo el problema P4 y la variable x1 se añaden las restricciones x1 ≤ 4 y x1 ≥ 5 para crear los siguientes problemas:
 P6 P7
 max z = 80x1 + 45x2	 max z = 80x1 + 45x2
 sujeto a	sujeto a
 x1 + x2 ≤ 7	 x1 + x2 ≤ 7
 12x1 + 5x2 ≤ 60	 12x1 + 5x2 ≤ 60
 x1 ≥ 4, x2 ≤ 2, x1 ≤ 4	 x1 ≥ 4, x2 ≤ 2, x1 ≥ 5
 x1, x2 ≥ 0	 x1, x2 ≥ 0
25
En la gráfica dela Figura se dan las soluciones óptimas del problema P6 y del problema P7.
26
Todos los problemas son terminales y no es necesario seguir ramificando. La solución óptima del problema entero es la solución candidata
x∗PE	= (x1 , x2 ) = (3, 4) y z*PE = zI = 420.
27
En el diagrama se recoge la solución óptima de todos los problemas relajados generados por el método de ramificación y acotación. Para cada problema el valor óptimo de la función objetivo es una cota superior de la solución del problema entero en esa rama.
MÉTODO DE RAMIFICACIÓN Y ACOTACIÓN 
29
CONCEPTO
El método de Ramificación y Acotamiento (o  Branch and Bound) es un algoritmo diseñado para la resolución de modelos de Programación Entera. 
El algoritmo genera en forma recursiva cotas (o restricciones adicionales) que favorecen la obtención de valores enteros para las variables de decisión. 
30
TERMINOLOGÍA DEL MÉTODO DE BRANCH AND BOUND
PROBLEMA RELAJADO:
Dado un problema lineal entero, se llama problema relajado al mismo modelo lineal, pero prescindiendo de la restricción, de que las variables sean enteras.
SOLUCIÓN CANDIDATA:
Dado un problema entero, en cada iteración del proceso de resolución, llamamos solución candidata a la mejor solución entera obtenida hasta el momento.
Dado que la solución candidata puede ser la solución óptima del problema entero, una vez obtenida una solución candidata se debe mantener hasta obtener otra mejor. 
31
ALGORITMO DE RAMIFICACIÓN Y ACOTACIÓN
Pasos a seguir para la obtención de valores enteros para las variables de decisión.
Paso 1. Inicialización: 
Resolver el problema lineal relajado asociado al problema entero.
Si la solución óptima es entera parar y esa solución es óptima también para el problema entero.
En otro caso, fijar una cota inferior zI para el valor óptimo del problema entero. Si no se conoce ninguna solución candidata para el problema entero, hacer zI = −∞.
32
Paso 2. Ramificación: 
Seleccionar un problema no terminal. 
En dicho problema elegir una variable xj que, teniendo que ser entera, tome un valor no entero en la solución actual. 
Crear dos nuevos problemas añadiendo al problema las restricciones xj ≤ [xj] , xj ≥ [xj] + 1.
Paso 3. Acotación: 
Resolver cada uno de los dos problemas recién creados en el paso de ramificación.
33
Paso 4. Problemas terminales: 
Analizar los problemas que puedan contener la solución óptima y considerar terminales los que cumplen una de las siguientes condiciones.
El problema es infactible:
zS ≤ zI.
zS > zI y la solución es entera. Se actualiza la cota inferior haciendo
zI = zS y esta solución entera es la solución candidata.
34
Si todos los problemas son terminales, la solución candidata es la solución óptima. Si no hay solución candidata el problema entero es infactible.
Si hay problemas no terminales, volver al Paso 2 para continuar con el proceso de ramificación.
A pesar de que el proceso de búsqueda de la solución óptima requiere gran cantidad de cálculos, éste es el algoritmo más utilizado para resolver problemas enteros puros y mixtos.
35
EJERCICIO N1:
Resolver el problema siguiente, utilizando el algoritmo de ramificación y acotación.
max z = 80x1 + 45x2 
sujeto a:
x1 + x2 ≤ 7
12x1 + 5x2 ≤ 60; x1 , x2 ≥ 0
36
PRIMERA ITERACIÓN:
Paso 1. Inicialización: Resolver el problema relajado. La tabla óptima es
 Inicializar la cota inferior: zI = −∞.
Paso 2. Ramificación: La solución del problema relajado no es entera. Elegimos para ramificar la variable x1 y se crean dos nuevos problemas: el problema P2 y el problema P3.
Paso 3. Acotación: Resolvemos cada uno de estos problemas utilizando las técnicas de análisis de sensibilidad.
37
Solución del problema P2: 
En la tabla óptima del PR se introduce la restricción x1 ≤ 3, sumando la correspondiente variable de holgura, x5. Se tiene la siguiente tabla:
.
38
Operación elemental en la fila 3 de la tabla: fila 3 − fila 2.
39
Esta tabla no tiene factibilidad primal. Aplicando el algoritmo simplex dual se tiene la siguiente tabla que es óptima para el problema P2.
40
Solución del problema P3: 
Partiendo de la tabla óptima del PR, para añadir la restricción x1 ≥ 4 se multiplica por −1, −x1 ≤ −4, para poder sumar una variable de holgura x5 que permite ampliar la base. Se tiene la siguiente tabla:
41
Hacer la siguiente operación elemental: fila 3 + fila 2.
42
La tabla no tiene factibilidad primal. Aplicando el simplex dual se tiene la tabla que es óptima para el problema P3.
Tenemos así las soluciones del problema P2 y del problema P3.
43
Paso 4. Problemas terminales:
El problema P2 es terminal porque zS = 420 > zI y, además, la solución es entera, xS = (3,4). Esta solución es candidata y actualizamos zI = zS = 420. El problema P3 no es terminal porque no cumple ninguno de los criterios del Paso 4.
Hay problemas no terminales y volvemos al Paso 2.
44
SEGUNDA ITERACIÓN:
Paso 2. Ramificación: Seleccionamos un problema no terminal. En este caso sólo tenemos un problema no terminal, el problema P3. Seleccionamos en dicho problema una variable; en este caso seleccionamos la variable x2 que es la única variable no entera. Ramificamos añadiendo al problema P3 la restricción x2 ≤ 2 para crear el problema P4 y x2 ≥ 3 para crear el P5.
Paso 3. Acotación: Resolver los dos problemas recién creados. Para ello procedemos como en la iteración anterior siendo en este caso la tabla de partida la tabla óptima para el problema P3.
Paso 4. Problemas terminales.
El problema P5 es terminal por ser infactible. El problema P4 tiene un valor zS = 423.33 > zI = 420 y la solución no es entera. Por tanto, no es terminal. 
45
TERCERA ITERACIÓN: 
Paso 2. Ramificación: Elegimos para ramificar el problema P4 que es el único no terminal. Seleccionamos la variable x1 por ser la única no entera. Se crean así dos nuevos problemas, el problema P6 y el problema P7.
Paso 3. Acotación: Resolver los dos problemas recién creados. Para ello procedemos como en la primera iteración siendo en este caso la tabla de partida la tabla óptima para el problema P4.
Paso 4. Problemas terminales: 
El problema P6 es terminal zI = 420. El problema P7 es terminal porque zS = 400 < zI = 420.
Todos los problemas son terminales. La solución candidata es la solución óptima del problema entero
46
MÉTODO PLANO CORTANTE O GOMORY 
METODO DEL PLANO CORTANTE(METODO GOMORY)
48
Método de resolución de problemas de programación entera basado en añadir restricciones adicionales hasta encontrar una solución optima que tenga valores enteros.
Puede aplicarse cualquier problema que cumpla los siguientes condiciones :
Todas las variables, incluidas las variables de holgura y exceso, deben tomar valores enteros.
Todos los coeficientes tecnológicos y todos los recursos deben ser números enteros o racionales.
METODO DEL PLANO CORTANTE (METODO GOMORY)
49
EJERCICIO DE APLICACIÓN 
Max 3 + 
s.a
50
Problema relajado a forma estándar
min -3 - 
s.a
51
Procederemos a encontrar nuestra fila y columna pivote 
52
	BASE	VARIABLES DE DECISION		VARIABLES DE HOLGURA		SOLUCION
	 					R
		3	4	1	0	20
		2	1	0	1	9
	Z	-3	-1	0	0	0
20/3 = 6.667
9/2 = 4.5
Solución Optima del problema relajado
= 4.5 = 0 Z = 13.5
NOTA: Se repetirá el procedimiento del método simplex si queda en la fila z un resultado negativo, en este caso queda por terminado el método simplex.
53
	 					R
		0	5/2	1	-3/2	13/2
		0	1/2	0	1/2	9/2
	Z	0	1/2	0	3/2	27/2
METODO DEL PLANO CORTANTE(METODO GOMORY)
Paso 1) Identificar los valores fraccionales en la tabla simplex y seleccionar el que tenga menor valor 
 = 13/2 = 9/2 Z = 27/2
Paso 2) Seleccionar todos los valores de la tabla simplex de la restricción seleccionada 
Paso 3) Se debe de descomponer la restricción en enteros y que las fracciones tengan que ser menores que 1 
54
METODO DEL PLANO CORTANTE(METODO GOMORY)
Paso 4) se acomodanlos enteros al lado izquierdo y las fracciones al lado derecho 
 
Paso 5) se agrega el a la restricción y se eliminan los enteros.
 
Paso 6) se pasan al lado derecho los valores sin variable
 
Paso 7) Se agrega una variable de holgura 
 
55
METODO DEL PLANO CORTANTE(METODO GOMORY)
Paso 8) Se agrega la restricción en la penultima fila de la tabla simplex 
56
	 						R
		0	5/2	1	-3/2	0	13/2
		0	1/2	0	1/2	0	9/2
		0	-1/2	0	-1/2	1	-1/2
	Z	0	1/2	0	3/2	0	27/2
METODO DEL PLANO CORTANTE(METODO GOMORY)
PASO 9) Para sacar la columna pivote se escogerá el que tenga menor cociente de la división de z (
=1/2 /-(1/2)= 1 =3/2 /-(1/2)= 3 
Nota : sera la fila pivote por tener en la solución un resultado negativo 
El cociente si es negativo se tomará su valor absoluto para saber el menor.
57
	 						R
		0	5/2	1	-3/2	0	13/2
		0	1/2	0	1/2	0	9/2
		0	-1/2	0	-1/2	1	-1/2
	Z	0	1/2	0	3/2	0	27/2
METODO DEL PLANO CORTANTE(METODO GOMORY)
PASO 10 ) SE REPITE EL METODO SIMPLEX 
58
	 						R
		0	0	1	-4	5	4
		1	0	0	0	1	4
		0	1	0	1	-2	1
	Z	0	0	0	1	1	13
-2
Todos los resultados son enteros y positivos por lo que el Metodo Gomory se termina
Solución Óptima 
= 4 = 1 Z = 13
 
https://www.zweigmedia.com/utilities/lpg/index.html?lang=es
59
INTERPRETACIÓN GRÁFICA
Método aditivo de balas
Es debido originalmente a Egon Balas. Se llama aditivo porque todas las operaciones matemáticas que se realizan consisten en sumar y restar 
El procedimiento consiste en generar una secuencia de soluciones parciales añadiendo en cada interacción una variable y considerando las soluciones complementarias , estas variables solo pueden tomar valores binarios (0-1)
61
	 	8 posibles soluciones							
	X1	0	0	0	0	1	1	1	1
	X2	0	0	1	1	0	1	0	1
	X3	0	1	0	1	0	0	1	1
El método empieza poniendo todas las variables iguales a cero y luego por medio de un procedimiento sistemático de forma consecutiva se asigna a una por una de las variables el valor de 1
Para describir el algoritmo, se considera la forma general siguiente de una programación lineal con variable 0-1:
Paso 1: la función objetivo debe ser del tipo minimización, con todos los coeficientes no negativos
Paso 2: todas las restricciones deben ser del tipo £, con los lados derechos negativos de ser necesario. Luego, estas restricciones se convierten a ecuaciones, usando las variables auxiliares en el lado izquierdo de las restricciones 
“
”
Ejemplo
Max Z= 2 + 3 - 7 - 5 + 4 
Min W= -2 - 3 + 7 + 5 - 4 
Reemplazamos: 
Min W= 2 + 3 + 7 + 5 + 4 – 9
63
El número posible de soluciones es de , en donde n es el número de variables. En el ejemplo, el número posible de soluciones es 
	 	32 posibles soluciones																															
	X1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
	X2	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
	X3	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
	X4	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
	X5	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
EJERCICIO
64
																	
	Max.Z=	3	X1	+	2	X2	-	5	X3	-	2	X4	+	3	X5		
	s.a		X1	+		X2	+		X3	+	2	X4	+		X5	≤	4
		7	X1	+				3	X3	+	4	X4	+	3	X5	≤	8
		11	X1	-	6	X2	+				3	X4	-	3	X5	≥	3
			Xj ∈ (0,1),j=1,…..,5														
	Min.W=	-3	Y1	-	2	Y2	+	5	X3	+	2	X4	-	3	Y5		
	s.a		X1	+		X2	+		X3	+	2	X4	+		X5	≤	4
		7	X1	+				3	X3	+	4	X4	+	3	X5	≤	8
		11	X1	-	6	X2	+				3	X4	-	3	X5	≥	3
			Xj ∈ (0,1),j=1,…..,5														
SOLUCIÓN
	Min.W=	3	Y1	+	2	Y2	+	5	X3	+	2	X4	+	3	Y5			Y1	=	1	-	X1
	s.a		X1	+		X2	+		X3	+	2	X4	+		X5	≤	4	Y2	=	1	-	X2
		7	X1	+				3	X3	+	4	X4	+	3	X5	≤	8	Y5	=	1	-	X5
		11	X1	-	6	X2	+				3	X4	-	3	X5	≥	3					
			Xj ∈ (0,1),j=1,…..,5																			
																						
		g1=	-1	X1	-1	X2	-1	X3	-2	X4	-1	X5	+	4	≥ 0							
			g2=		-7	X1	-3	X3	-4	X4	-3	X5	+	8	≥ 0							
			g3=		11	X1	-6	X2	+	3	X4	-3	X5	-3	≥ 0							
“
”
 :
	X1=	0		 		X2=	0		X3=	0		X4=	0		X5=	0
				 												 
				 		g1=	4		≥ 0							 
				 		g2=	8		≥ 0							 
				 		g3=	-3		≥ 0							 
	 	 	Infactibilidad =						3							 
																Min.W=	0	+	2	+	0	+	0	+	3	=	5
	X1=	1		X2=	0		X3=	0		X4=	0		X5=	0													
																Y1	=	0									
				g1=	3		≥ 0									Y2	=	1									
				g2=	1		≥ 0									Y5	=	1									
				g3=	8		≥ 0																				
																											
	 	Infactibilidad =					0																				
Cuando X1=1, X2= X3= X4= X5=0
“
”
																Min.W=	0	+	0	+	0	+	0	+	3	=	3
	X1=	1		X2=	1		X3=	0		X4=	0		X5=	0													
																Y1	=	0									
				g1=	2		≥ 0									Y2	=	0									
				g2=	1		≥ 0									Y5	=	1									
				g3=	2		≥ 0																				
																											
	 	Infactibilidad =					0																				
	X1=	1		X2=	1		X3=	0		X4=	0		X5=	1
														
				g1=	1		≥ 0							
				g2=	-2		≥ 0							
				g3=	-1		≥ 0							
														
	 	Infactibilidad =					3							
Cuando X1=X2=1, X3=X4=X5=0
Cuando X1=X2=X5=1, X3=X4=0
“
”
	X1=	1		X2=	0		X3=	0		X4=	0		X5=	1
														
				g1=	2		≥ 0							
				g2=	-2		≥ 0							
				g3=	5		≥ 0							
														
	 	Infactibilidad =					2							
	X1=	0		X2=	1		X3=	0		X4=	0		X5=	0
														
				g1=	3		≥ 0							
				g2=	8		≥ 0							
				g3=	-9		≥ 0							
														
	 	Infactibilidad =					9							
Cuando X1=X5=1, X2=X3=X4=0
Cuando X2=1, X1= X3= X4= X5=0
“
”
	X1=	0		X2=	0		X3=	1		X4=	0		X5=	0
														
				g1=	3		≥ 0							
				g2=	5		≥ 0							
				g3=	-3		≥ 0							
														
	 	Infactibilidad =					3							
																Min.W=	3	+	2	+	0	+	2	+	3	=	10
	X1=	0		X2=	0		X3=	0		X4=	1		X5=	0													
																Y1	=	1									
				g1=	2		≥ 0									Y2	=	1									
				g2=	4		≥ 0									Y5	=	1									
				g3=	0		≥ 0																				
																											
	 	Infactibilidad =					0																				
Cuando X3=1, X1= X2= X4= X5=0
Cuando X4=1, X1= X2= X3= X5=0
“
”
	X1=	1		X2=	0		X3=	0		X4=	1		X5=	0
														
				g1=	1		≥ 0							
				g2=	-3		≥ 0							
				g3=	11		≥ 0							
														
	 	Infactibilidad =					3							
	X1=	0		X2=	1		X3=	0		X4=	1		X5=	0
														
				g1=	1		≥ 0							
				g2=	4		≥ 0							
				g3=	-6		≥ 0							
														
	 	Infactibilidad =					6							
Cuando X4=X1=1, X2=X3=X5=0
Cuando X4=X2=1, X1=X3=X5=0
“
”
	X1=	0		X2=	0		X3=	0		X4=	1		X5=	1
														
				g1=	1		≥ 0							
				g2=	1		≥ 0							
				g3=	-3		≥ 0							
														
	 	Infactibilidad =					3							
Cuando X4=X5=1, X1=X2=X3=0
	X1=	0		X2=	0		X3=	0		X4=	0		X5=	1
														
				g1=	3		≥ 0							
				g2=	5		≥ 0							
				g3=	-6		≥ 0							
														
	 	Infactibilidad =					6							
Cuando X5=1, X1= X2= X3= X4=0
“
”
Max.Z=3(1)+2(1)-5(0)-2(0)+3(0)=5
	Max.Z=	3	X1	+	2	X2	-	5	X3	-	2	X4	+	3	X5		
	s.a		X1	+		X2	+		X3	+	2	X4	+		X5	≤	4
		7	X1	+				3	X3	+	4	X4	+	3	X5	≤	8
		11	X1	-	6	X2	+				3	X4	-	3	X5	≥	3
			Xj ∈ (0,1),j=1,…..,5														
Gracias a los resultados, buscamos el menor Min.W que viene a hacer = 3, con los factores X1=1, X2=1, X3=0, X4=0, X5=0. Sustituiremos en nuestra función original Max.Z
“
”
73
CONCLUSION
Los problemas de PE 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 que se puede representar por variables binarias (0-1). 
Los problemas de PE son más difíciles de lo que serían sin la restricción de valores enteros, de manera que los algoritmos disponibles para programación entera, en general, son mucho menos eficientes que el método símplex. Sin embargo, ha habido enormes progresos en las últimas décadas en cuanto a la capacidad para resolver algunos problemas enormes de IP.
74
CONCLUSION
Los problemas de PE 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 aplicacionesque necesitan decisiones sí o no que se puede representar por variables binarias (0-1). 
Los problemas de PE son más difíciles de lo que serían sin la restricción de valores enteros, de manera que los algoritmos disponibles para programación entera, en general, son mucho menos eficientes que el método símplex. Sin embargo, ha habido enormes progresos en las últimas décadas en cuanto a la capacidad para resolver algunos problemas enormes de IP.
75
bibliografia
http://bdigital.unal.edu.co/46196/3/9588095093_part02.pdf
https://sites.google.com/site/unidaiiiprogramacionentera/3-tipos-de-modelos
io-9na edicion.hamdya.taha.pdf
http://www.alumnos.inf.utfsm.cl/~vpena/ramos/ili292/apuntes/entera_s2_2003.pdfl
https://ocw.ehu.eus/file.php/19/5._entera.pdf
76
https://www.google.com/url?sa=t&source=web&rct=j&url=https://ocw.ehu.eus/file.php/19/5._entera.pdf&ved=2ahukewixzfyzgvvrahwphrkghxbqbekqfjagegqiahab&usg=aovvaw3cvpijgt20aw5qbhp7llub
https://studylib.es/doc/2131/algoritmo-aditivo-de-balas
https://docs.ufpr.br/~volmir/po_ii_14_balas.pdf
http://virtual.umng.edu.co/distancia/ecosistema/ovas/ingenieria_civil/investigacion_de_operaciones_ii/unidad_5/dm.pdf
Lieberman,G. (2002). Investigación de operaciones. México, Editorial McGrawHill.
Bronson, R. (1993). Investigación de operaciones, México, Editorial McGrawHill.