GRUPO 5

Vista previa del material en texto

UNIVERSIDAD NACIONAL FEDERICO VILLAREAL
FACULTAD DE INGENIERÍA INDUSTRIAL Y SISTEMAS
ESCUELA PROFESIONAL DE INGENIERÍA INDUSTRIAL
CURSO : INVESTIGACION DE OPERACIONES II
FACILITADOR DEL CURSO: MARIA BENAVIDES
TEMA: “PROGRMACION ENTERA”
INTEGRANTES: 
	
1.INTRODUCCION
2
Diapositiva de análisis de proyecto 2
INTRODUCCION 
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 lineal entera pura;
Si se necesita que algunas de las variables de decisión sean números enteros, se tiene un problema de programación lineal 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 lineal entera binaria (digital); si se requiere que solamente algunas de las variables tomen valores de cero o uno, se tiene un problema de programación lineal entera binaria mixta.
PROGRAMACIÓN ENTERA 
3
2.OBJETIVOS
4
Diapositiva de análisis de proyecto 2
 
OBJETIVO GENERAL.
Definir la caracterisitca de un problema , enfocando su algoritmo de solución 
Formular un problema específico utilizando el método de programación entera 
Manejar algunas de la técnicas básicas utilizadas en la solución de problemas de programación entera.
Resolver problemas en los
que se empleen variables enteras, utilizando los algoritmos de solución que se ajusten a las características de dichos problemas.
OBJETIVOS ESPECIFICOS.
OBJETIVOS 
PROGRAMACIÓN ENTERA 
5
Series 1	Category 1	40	Series 2	Category 1	60	
Series 1	Category 1	60	Series 2	Category 1	40	
Series 1	Category 1	50	Series 2	Category 1	50	
3.CLASIFICACION 
6
La programación entera es un conjunto de técnicas operativa que permite solución a una variante para el programa lineal cuando las variables de decisión no pueden tomar valores fraccionarios, tradicionalmente se han considerado sub clases de la programación lineal sin embargo sus variables de decisión solo toman valores enteros, por lo que se debería considerar variables de programación entera
APLICACIÓN
Para asignar personas, maquinas o vehículos a las actividades, en cantidades enteras
Estas se clasifican en 
Puras 
Mixtas 
Binarias 
Pura 
Como su nombre lo indica, un problema en el que se exige que todas las variables tengan valores enteros
Problemas de asignación
Selección de invitados a una boda
Problemas de transporte 
Mixta 
Un problema en el que solo se requiere que algunas de las variables tomen valores enteros
Problemas de generación eléctrica
Incorporación de costos fijos
Un modelo de dicotomía
Binarias 
En estas se restringe el valor de la variables de 0 a 1, son de particular interés ya que se puede usar las variables de decisión 0 o 1
Ubicación de planta 
Elaboración de cartera 
4.METODOS DE SOLUCION 
12
Método de ramificación y acotación (Branch and Bound) 
𝑴𝒂𝒙 𝑭 𝒙 = 𝟒𝒙𝟏 + 𝟓𝒙𝟐
Sujeto a: 2𝑥1 + 𝑥2 ≤ 8
𝑥2 ≤ 5
𝑥1 , 𝑥2 ≥ 0 𝑦 𝑒𝑛𝑡𝑒𝑟𝑎𝑠
La solución a este problema, no teniendo en cuenta que las variables sean enteras, es:
𝑥1 = 1,5, 𝑥2= 5 𝑦 𝐹(𝑥) = 31
Esta solución no está verificando las condiciones de integridad, entonces se debe elegir la variable 𝑥 que no es entera y a partir de ella se generan dos restricciones:
x1 ≤ 1 y x1 ≥ 2
Que añadidas cada una de ellas al problema original, dan lugar a dos nuevos subproblemas que serían los siguientes:
	Max F(x) = 4x1 + 5x2	Max F(x) = 4x1 + 5x2
	Sujeto a: 2x1 + x2 ≤ 8	Sujeto a: 2x1 + x2 ≤ 8
	x2 ≤ 5	x2 ≤ 5
	x1 ≤ 1	x1 ≥ 2
	x1,x2 ≥ 0	x1,x2 ≥ 0
De esta forma se han eliminado todas las posibles soluciones no enteras del conjunto de oportunidades, tales que 1< x1 < 2.
El proceso se repite con cada uno de los dos subproblemas obtenidos, los cuales dan lugar a otros dos subproblemas cada uno de ellos y así sucesivamente, hasta que todos los subproblemas tengan solución entera o infactible
PRIMER DATO CURIOSO:
Utilizando únicamente la ramificación, el número de subproblemas a resolver crece exponencialmente, por este motivo para evitar el tener que resolver todos los subproblemas, la ramificación se combina con la acotación.
SEGUNDO DATO CURIOSO:
La acotación se basa en que los conjuntos de oportunidades de los subproblemas obtenidos en el ejemplo anterior, son a su vez subconjuntos del conjunto de oportunidades del problema. La solución óptima de los dos subproblemas siempre será (inferior para el problema de máximo o superior para problemas de mínimo) que la solución óptima del problema, por ser los conjuntos de elección menores.
RESUMIENDO
La acotación se basa en que los conjuntos de oportunidades de los subproblemas obtenidos en el ejemplo anterior, son a su vez subconjuntos del conjunto de oportunidades del problema. La solución óptima de los dos subproblemas siempre será inferior (problema de máximo o superior para problemas de mínimo) que la solución óptima del problema, por ser los conjuntos de elección menores.
De esta forma, el proceso de acotación consiste, para problemas de máximo, en tomar como cota inferior aquella solución entera con mayor valor de la función objetivo obtenida y dado que cualquier otro subproblema con solución no entera se sabe que al ramificarlo dará como resultado valores de la función objetivo menores o iguales, permite descartar como subproblemas a ramificar todos aquellos que tengan como solución óptima un valor de la función inferior a la cota establecida.
De este modo se reduce el número de subproblemas a ramificar y, por lo tanto, el tiempo necesario para la resolución de los problemas enteros.
Una vez resuelto el problema si la solución es entera, la solución es óptima y se ha dado una solución al problema original. Si no, se debe elegir una variable entera xi cuyo valor sea fraccional, posteriormente se resuelven los dos problemas lineales iguales al anterior con las restricciones adicionales: uno con la restricción Xi<[Xi] y el otro con la restricción Xi > [Xi]+1. Después se analiza el problema con la mejor solución que cualquiera de las soluciones enteras conocidas y se elige el problema que tenga el mejor valor de la función objetivo.
Max F(X) = 8x1 + 10x2
Sujeto a: 4x1 + 6x2 ≤ 24 
8x1 + 3x2 ≤ 24
x1≥0,x2≥0, x1,x2 ∈ Z+ 
Se obtiene la solución x1 = 2, x2 = 8/3, f(x) = 128/3.
Dado que esta solución no es entera se ramifica a partir de la variable x2 de la siguiente manera:
 Subproblema 1	 Subproblema 2
Max F(X) = 8x1 + 10x2 .	 Max F(X) = 8x1 + 10x2
Sujeto a: 4x1 + 6x2 ≤ 24	 Sujeto a: 4x1 + 6x2 ≤ 24
8x1 + 3x2 ≤ 24	 8x1 + 3x2 ≤ 24
x2 ≥ 3	 x2 ≤ 2
x1≥0,x2≥0	 x1≥0,x2≥0
Solución x1=1,5, x2=3,F(x)=42 Solución x1=2,5, x2=2,F(x)=38
Como la solución del subproblema 1 tiene el mayor valor de la función objetivo y no es entera, se debe ramificar este subproblema a partir de la variable x1, de la siguiente forma:
 Subproblema 1.1	 Subproblema 1.2
Max F(X) = 8x1 + 10x2 .	 Max F(X) = 8x1 + 10x2
Sujeto a: 4x1 + 6x2 ≤ 24	 Sujeto a: 4x1 + 6x2 ≤ 24
8x1 + 3x2 ≤ 24	 8x1 + 3x2 ≤ 24
x2 ≥ 3	 x2 ≥ 3
x1 ≤ 1	 x1 ≥ 2
x1≥0,x2≥0	 x1≥0,x2≥0
Solución x1=1, x2=10/3,F(x)=124/3	 Solución infactible
Dado que de todos los subproblemas todavía no ramificados (subproblemas 2, 1.1 y 1.2) el que tiene una mayor solución factible no entera es el subproblema 1.1, se ramificará este subproblema a partir de la variable x2, es decir:
Subproblema 1.1.1	 Subproblema 1.1.2Max F(X) = 8x1 + 10x2 .	 Max F(X) = 8x1 + 10x2
Sujeto a: 4x1 + 6x2 ≤ 24	 Sujeto a: 4x1 + 6x2 ≤ 24
8x1 + 3x2 ≤ 24	 8x1 + 3x2 ≤ 24
x2 ≥ 3	 x2 ≥ 3
x1≤ 1	 x1 ≤ 1
x2 ≤ 3	 x2 ≥ 4
x1≥0,x2≥0	 x1≥0,x2≥0
Solución x1=1, x2=3,F(x)=38 	Solución x1=0, x2=4,F(x)=40
Ya se conoce una solución entera x1=0, x2=4,F(x)=40. Esta solución actuará como cota inferior y solamente deberán ser ramificados aquellos subproblemas con soluciones factibles no enteras que tengan un valor para la función objetivo que 40. Como el único subproblema por ramificar es el subproblema 2 y la función objetivo vale 38, el proceso se da por terminado, siendo por tanto la solución óptima al problema entero x1 = 0, x2 = 4, F(x) = 40. El árbol del problema resuelto es el siguiente
Método de Gomory
1. Resolver la relajación lineal (PR). Sea x ∗ la solución óptima
 2. Si x ∗ ∈ Z+ terminar, x ∗ es el ´óptimo de (P). 
3. Si no, agregar una restricción a (PR), tal que sea satisfecha por toda solución entera de (P)
	 	Z	X1	X2	S1	S2	 	Adicionales
	S1	0	3	1	1	0	6	6
	S2	0	2	3	0	1	9	3
	Z-C		-3	-4	0	0	0	 
	 	Z	X1	X2	S1	S2	 	Adicionales	
	S1	0	2 1/3	0	1	- 1/3	3	1 2/7	Se elige al menor
	X2	0	 2/3	1	0	 1/3	3	4 1/2	 
	Z-C		- 1/3	0	0	1 1/3	12	 	 
	 	Z	X1	X2	S1	S2	 
	X1	0	1	0	 3/7	- 1/7	1 2/7
	X2	0	0	1	-0.285714	0.42857	2.142857
	Z-C		0	0	0.142857	1.28571	12.42857
	 	Z	X1	X2	S1	S2	S3	 	 
	X1	0	1	0	 3/7	- 1/7	0	1 2/7	 
	X2	0	0	1	- 2/7	 3/7	0	2 1/7	 
	S3	0	0	0	- 3/7	- 6/7	1	- 2/7	VALOR NEGATIVO
	Z-C		0	0	 1/7	1 2/7	0	12 3/7	 
	ADICIONALES		 	 	- 1/3	-1 1/2	 	 	SE ELEGI AL MENOR EN VALOR ABSOLUTO 
	 	Z	X1	X2	S1	S2	S3	 
	X1	0	1	0	0	-1	1	1
	X2	0	0	1	0	1	- 2/3	2 1/3
	S3	0	0	0	1	2	-2 1/3	 2/3
	Z-C		0	0	0	1	 1/3	12 1/3
	 		 	 	 	 	 	 
	 	Z	X1	X2	S1	S2	S3	S4	 
	X1	0	1	0	0	-1	1	0	1
	X2	0	0	1	0	1	- 2/3	0	2 1/3
	S3	0	0	0	1	2	-2 1/3	0	 2/3
	S4	0	0	0	0	0	-0.33333	1	-0.333333333
	Z-C		0	0	0	1	 1/3	0	12 1/3
	 	Z	X1	X2	S1	S2	S3	S4	 
	X1	0	1	0	0	-1	0	3	0
	X2	0	0	1	0	1	0	-2	3
	S3	0	0	0	1	2	0	-7	3
	S4	0	0	0	0	0	1	-3	1
	Z-C		0	0	0	1	0	1	12
	Z=12	x1=0	x2=3
Método del Redondeo de la Solución de PL
Redondeo por defecto:
Redondeo por exceso :
	Max	4x1+	8x2	 
	Sa			 
	 	3X1+	2x2	≤15
	 	2X1+	3X2	≥4
	 			 
	 	X1,X2≥0 y enteros		 
Conclusión
La solución optima luego de aplicar el método de ramificación y acotación es menor que la solución del problema relajada el cual es 60 
Método aditivo de balas
METODO ADITIVO DE BALAS
 La denominación de este método es debido originalmente a Egon Balas (1965)
 El procedimiento consiste en generas una secuencia de soluciones parciales añadiendo en cada iteración una variable considerando las soluciones complementarias (resto de soluciones posibles).
 La selección de variable añadida se hace en función de reducir al máximo la infactibilidad en la solución actual y eliminar la redundancia.
El método aditivo de Egon Balas, hace referencia a un procedimiento de enumeración que encuentra el óptimo de manera más eficiente, evaluando algunas soluciones.
PROCEDIMIENTO
Se deben poner todas las variables iguales a cero y luego asignar a una por una de las variables el valor 1. Posteriormente se reemplaza en cada una de las restricciones y se averigua la infactibilidad.
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 de tipo entero con los lados derechos negativos de ser necesario. Después estas restricciones se convierten a ecuaciones, usando las variables auxiliares en el lado izquierdo de las restricciones.
 DATOS A TENER PRESENTE
Resuelve problemas de minimización con variables binarias: 0,1
Los coeficientes de la función objetivo tienen que ser todos postivos
Todas las restricciones del modelo deben ser del tipo ≤
MIN Z = 8 X1 + 7 X2 + 6X3 + 5 X4 + X5
 -6X1 - 3 X2 + 2X3 - 4 X4 - X5 ≤ -3
 -4X1 - 5 X2 - 4X3 - 3 X4 + 3X5 ≤ -7
 Xi,j = 0,1 ( binarias) 
En vez de analizar las =32 opciones de 0,1 para las variables como en el método de enumeración implícita, en el método aditivo solo analizaremos algunas de ellas, comenzando con todas las varibles igual a 0
X1 = X2 = X3 = X4 = X5 = 0 
-6*0 – 3*0 + 2*0 – 4*0 - 0 +3 ≤ 0 3 ≤ 0 
-4*0 – 5*0 - 4*0 – 3*0 + 3*0 +7 ≤ 0 7 ≤ 0 infactibilidad = 10
 
Primera iteración 
 X1 =1 ; X2 = X3 = X4 = X5 = 0
 
-6*1 – 3*0 + 2*0 – 4*0 - 0 +3 ≤ 0 -3 ≤ 0 
-4*1 – 5*0 - 4*0 – 3*0 + 3*0 +7 ≤ 0 3 ≤ 0 infactibilidad=3
X2 =1 ; X1 = X3 = X4 = X5 = 0
-6*0 – 3*1 + 2*0 – 4*0 - 0 +3 ≤ 0 0 ≤ 0 
-4*0 – 5*1 - 4*0 – 3*0 + 3*0 +7 ≤ 0 2 ≤ 0 infactibilidad= 2 
 
 X3 =1 ; X1 = X2 = X4 = X5 = 0
 
-6*0 – 3*0 + 2*1 – 4*0 - 0 +3 ≤ 0 5 ≤ 0 
-4*0 – 5*0 - 4*1 – 3*0 + 3*0 +7 ≤ 0 3 ≤ 0 infactibilidad=8
X4 =1 ; X1 = X2= X3 = X5 = 0
-6*0 – 3*1 + 2*0 – 4*1 - 0 +3 ≤ 0 -1 ≤ 0 
-4*0 – 5*1 - 4*0 – 3*1 + 3*0 +7 ≤ 0 4 ≤ 0 infactibilidad= 4 
 
 X5 =1 ; X1 = X2 = X3 = X4 = 0
 
-6*0 – 3*0 + 2*1 – 4*0 - 1 +3 ≤ 0 2 ≤ 0 
-4*0 – 5*0 - 4*1 – 3*0 + 3*1 +7 ≤ 0 10 ≤ 0 infactibilidad=12
 
		INFACTIBILIDAD
	X1=	10
	X2=	3
	X3=	2
	X4=	8
	X5=	4
	X6=	2
Segunda iteración (x2=1) 
 X1 =1 ; X3 = X4 = X5 = 0
 
-6*1 – 3*1 + 2*0 – 4*0 - 0 +3 ≤ 0 -6 ≤ 0 
-4*1 – 5*1 - 4*0 – 3*0 + 3*0 +7 ≤ 0 -2 ≤ 0 infactibilidad=0
X3 =1 ; X1 = X2 = X4 = X5 = 0
-6*0 – 3*1 + 2*1 – 4*0 - 0 +3 ≤ 0 2 ≤ 0 
-4*0 – 5*1 - 4*1 – 3*0 + 3*0 +7 ≤ 0 -2 ≤ 0 infactibilidad= 2 
 
Segunda iteración (x2=1) 
 X4 =1 ; X1 = X4 = X5 = 0
 
-6*0 – 3*1 + 2*0 – 4*1 - 0 +3 ≤ 0 -4 ≤ 0 
-4*0 – 5*1 - 4*0 – 3*1 + 3*0 +7 ≤ 0 -1 ≤ 0 infactibilidad=0
X5 =1 ; X1 = X2 = X4 = 0
-6*0 – 3*1 + 2*0 – 4*0 - 1 +3 ≤ 0 -1 ≤ 0 
-4*0 – 5*1 - 4*0 – 3*0 + 3*1 +7 ≤ 0 5≤ 0 infactibilidad= 5 
 
 Tomamos todos los casos en los que la infactibilidad=0
X1 =X2=1 ; X3 = X4 = X5 = 0
Z=8*1+7*1+6*0+5*0+0= 15
X2 =X4=1 ; X1 = X3 = X5 = 0
Z=8*0+7*1+6*0+5*1+0= 12
 
LA SOLUCION QUE MINIMIZA Z ES X2 =X4=1 ; X1 = X3 = X5 = 0 CON Z=12
5.TIPOS DE PROBLEMAS 
43
Problema
de costos fijos
ENUNCIADO:
Una empresa produce tres tipos de prendas: poleras, shorts y pantalones. La fabricación de cada tipo de prenda requiere de maquinaria especializada. La maquinaria puede ser arrendada a los siguientes costos: US$200, US$150 y US$100 al mes en el caso de las poleras, shorts y pantalones, respectivamente. La fabricación de cada prenda requiere las cantidades de tela y mano de obra indicadas. Cada mes se dispone de 150 horas de mano de obra y 160 yd2 de tela. Se debe maximizar el beneficio de la empresa. 
x1= número de poleras producidas mensualmente. 
X2 = número de shorts producidos mensualmente. 
X3 = número de pantalones producidos mensualmente.
La función objetivo corresponderá a la diferencia entre los ingresos por venta, menos los costos de producción, fijos y variables:
Z = (12x1 + 8x2 + 15x3) – (6x1 + 4x2 + 8x3) - (200y1 + 150y2 + 100y3)
    ingreso por venta   costos variables       costos fijos
Por lo tanto, la función objetivo a maximizar queda: 
               
                  Z = 6x1 + 4x2 + 7x3 - 200y1 - 150y2 – 100y3
La restricción de manode obra:
 3x1 + 2x2 + 6x3 ≤ 150
la restricción de la tela:
 4x1 + 3x2 + 4x3 ≤ 160 
		MANO DE OBRA (hrs) 	TELA (Yd2) 
	POLERAS 	3 	4 
	SHORTS 	2 	3 
	PANTALONES 	6 	4 
		PRECIO DE VENTA ($) 	COSTO VARIABLE ($) 
	POLERAS 	12 	6 
	SHORTS 	8 	4 
	PANTALONES 	15 	8 
Para que el modelo funcione, se debe garantizar que: 
Si xi > 0   yi = 1 
Si xi = 0   yi = 0 
Para ello, se deben incorporar las restricciones de activación de las variables binarias: 
x1 ≤ M1y1 
x2 ≤ M2y2 
x3 ≤ M3y3
los valores de Mi sólo deben ser lo suficientemente grandes para no restringir los valores de xi por lo que se escogería arbitrariamente: M1 = M2 = M3 = 100
De acuerdo a la selección anterior, el modelo final para el problema queda: 
Max Z = 6x1 + 4x2 + 7x3 - 200y1 - 150y2 - 100y3 
Sujeto a:
 3x1 + 2x2 + 6x3 ≤ 150 
 4x1 + 3x2 + 4x3 ≤ 160 
 
X1 ≤ M1Y1 
 X2 ≤ M2Y2 
 X3 ≤ M3Y3 
XI ∈ Z ∀ J = 1….3 
YI = 0,1 ∀ J = 1….3
PROBLEMA MODELO TIPO MOCHILA
UN EXCURSIONISTA PLANEA SALIR DE CAMPAMENTO. HAY 6 ARTICULOS QUE DESEA LLEVAR CONSIGO, PERO ENTRE TODOS SOBREPASAN LOS 8 LITROS DE LA CAPACIDAD DE LA MOCHILA .EN EL SGTE CUADRO SE MUESTRA EL VOLUMEN DE CADA ARTICULO Y COSTO BENEFICIO. ¿QUE ARTICULOS DEBERA LLEVAR MAXIMIZANDO EL VALOR TOTAL SIN SOBREPASAR LA RESTRICCION DEL VOLUMEN?
NO SE PUEDE LLEVAR MAS DE UN ARTICULO DEL MISMO TIPO
1.
2.
3.
Problema de transporte
ENUNCIADO:
Una ciudad tiene 10 zonas o áreas urbanas cada una de los cuales genera una determinada cantidad de basura (en toneladas) durante el periodo de planificación según se describe a continuación:
La basura generada debe ser transportada a centros de depósitos o vertederos entre un total de 5 candidatos posibles, cada uno de los cuales tiene un costo fijo de construcción en dólares.
Adicionalmente se ha estimado el costo de transportar una tonelada de basura desde una zona a cada uno de los potenciales centros de depósito, el cual depende básicamente de la distancia a recorrer y el tipo de transporte seleccionado.
	Zona 1 	Zona 2 	Zona 3 	Zona 4 	Zona 5 	Zona 6 	Zona 7 	Zona 8 	Zona 9 	Zona 10 
	550 	470 	430 	450 	170 	300 	290 	340 	780 	240 
		Deposito 1 	Deposito 2 	Deposito 3 	Deposito 4 	Deposito 5 
	Costo fijo ($) 	3 950 000 	4 150 000 	3 750 000 	4 500 000  	5 000 000 
Formule un modelo de Programación Entera Mixta que permita seleccionar los centros de depósito a construir y la política de transporte de basura que minimiza los costos totales.
		Deposito 1 	Deposito 2 	Deposito 3 	Deposito 4 	Deposito 5 
	Zona 1 	2 	6 	3 	1 	4 
	Zona 2 	2 	7 	5 	4 	9 
	Zona 3 	1 	6 	7 	2 	8 
	Zona 4 	3 	9 	8 	2 	1 
	Zona 5 	5 	2 	4 	3 	6 
	Zona 6 	3 	4 	2 	7 	5 
	Zona 7 	5 	9 	6 	6 	2 
	Zona 8 	6 	8 	3 	6 	7 
	Zona 9 	3 	9 	10 	3 	5 
	Zona 10 	3 	5 	7 	8 	4 
=>  Variables de Decisión: 
Sea i=1,2,3…,10 las Zonas y
 j=1,2,…,5 los Depósitos:
                                        
Xij: Toneladas de basura transportadas desde la zona (i) al deposito (j)
Yj: {1,     si se construye el deposito(j)
      0,     si no        
	  	Deposito 1 	Deposito 2 	Deposito 3 	Deposito 4 	Deposito 5 
	Capacidad (ton) 	1000 	1500 	900 	1850 	2000 
	Costo fijo ($) 	3950000 
	4150000 	3750000 	4500000 	5000000 
La función objetivo se puede representar a través de la siguiente expresión:
                   Minimizar ∑i=110∑j=15Tij∗ Xij+∑j=15Fj∗ Yj
DONDE:
Tij: Costo de transportar una tonelada de basura desde la Zona i al Depósito j
   Fj: Costo fijo de construcción del Depósito j
RESTRICCIONES:
 
∑j=15Xij=Ai        Para todo i
PARÁMETRO AI: CANTIDAD DE BASURA EN TONELADAS QUE GENERA LA ZONA I.
∑i=110Xij≤Cj∗ Yj        Para todo j
 PARÁMETRO CJ COMO LA CAPACIDAD DE ALMACENAMIENTO DE BASURA EN TONELADAS DEL DEPÓSITO J.
Finalmente establecemos condiciones de no negatividad para Xij>=0 Para todo i,j y Yj{0,1} para todo j.
	Yj 	1 	1 	1 	1 	1 	F. OBJETIVO 	21358110 
	Xij 	Deposito 1 	Deposito 2 	Deposito 3 	Deposito 4 	Deposito 5 	L.IZQ 	Basura(ton) 
	Zona 1 	0 	0 	0 	550 	0 	550 	550 
	Zona 2 	470 	0 	0 	0 	0 	470 	470 
	Zona 3 	430 	0 	0 	0 	0 	430 	430 
	Zona 4 	0 	0 	0 	0 	450 	450 	450 
	Zona 5 	0 	170 	0 	0 	0 	170 	170 
	Zona 6 	0 	0 	300 	0 	0 	300 	300 
	Zona 7 	0 	0 	0 	0 	290 	290 	290 
	Zona 8 	0 	0 	340 	0 	0 	340 	340 
	Zona 9 	0 	0 	0 	780 	0 	780 	780 
	Zona 10 	99.9999997 	0 	0 	0 	140 	240 	240 
	L.IZQ 	1000 	170 	640 	1330 	880 		
	CAP(ton) 	1000 	1500 	900 	1850 	2000 		
* Solución con Excel(solver) 
 
CONCLUSIONES:
La programación entera en su enfoque algorítmico combina el preprocesado automático de los problemas con sus ramificaciones, sin embargo,  aún existen diversas investigaciones en el área. La aplicación del método simplex en la programación entera es debido a que hay problemas que no serán posibles resolverlos solo usando los algoritmos, aunque la solución no suele ser satisfactoria ya que es difícil encontrar una solución entera factible.
Mx 3X1+ 4x2 
SA 
 
 
 3x1+ x2 ≤6 
 2x1+ 3X2 ≤9 
 X1,X2 son enteros y positivos 
 
3/7S1+(-1/7 -(-1))S2≥(9/7 -1)
3/7S1+6/7S2 ≥2/7
െଷௌଵ଻െ଺ௌଶ଻≤-2/7
(-2/3+1)S3≥(
7/3-2)
1/3S3 ≥1/3
െͳܵ͵͵൅ܵͶൌെͳ͵
ܺ௜≤ܺ௕௜
ܺ௜൒ܺ௕௜+1
X1X2Z
07.5060
50.0020
01.3310.666667
208
X1=0
X2=7.5
Z=60
X2 =8 no es factible
x2=7 si es factible
3x1+2(7) =15
X1=1/3
7≤X2≤8
Ahora 
Max
4(1/3)+8(7)
57.33
X1=1/3
X2=7X1=0 
Z=57.33X1=1 fuera de la sol optima
x2=7 X1=0
4X1+8X2
0≤X1≤1
X2=7
X1=0
Z=56