MODELOS DE OPTIMIZACION

Actividad 11 y 12
MAESTRO: RICARDO CHAVERO RODRIGUEZ
Edson Anuar Gracia Orona
 PROGRAMACION ENTERA

MIN Z=x1+3x2-2x3

S/A

4X1+8X2+6X3=25

7X1+5X2+9X3=30

X1,X2,X3≥0

Inicialización (iteración 1)
95 15 115
o Se resuelve el problema LP relajado Z = − 42 (X1,X2,X3) = (0,14, )
42
Iteración 2

o Se ramifica con la tercera variable que debiera ser entera y no lo es, X3.

4 31 43
o Rama 1: X3 ≤ 2 Z = 9 (X1,X2,X3) = (36,36, 2)
o Rama 2: X3 ≥ 3 No es factible, se poda la rama

Iteración 2

o Se ramifica con la primera variable en nodo 1 que debiera ser entera y no lo es, X1.

o Rama 3: X3 ≤ 2 No es factible, se poda la rama

• X1 ≤ 0

37 17 79
o Rama 4: X3 ≤ 2 Z = 42 (X1,X2,X3) = (1,14,42 )
• X1 ≥ 1

Iteración 2

o Se ramifica con la tercera variable en nodo 4 que debiera ser entera y no lo es, X3.
37 73 49
o Rama 5: X3 ≤ 2 Z = 9 (X1,X2,X3) = (36,36,1)

X1 ≥ 1
 X3 ≤ 1

o Rama 6: X3 ≤ 2 No es factible, se poda la rama.

X1 ≥ 1

X3 ≥ 2

Iteración 2

o Se ramifica con la primera variable en nodo 5 que debiera ser entera y no lo es, X1.

o Rama 7: X3 ≤ 2 No es factible, se poda la rama.

X1 ≥ 1

X3 ≤ 1

X1 ≤ 2

43 31
o Rama 8: X3 ≤ 2 Z= (X1,X2,X3) = (3,2,6 )
6

X1 ≥ 1
 X3 ≤ 1

X1 ≥ 3

Iteración 2

o Se ramifica con la tercera variable en nodo 8 que debiera ser entera y no lo es, X3.

70 115 55
o Rama 9: X3 ≤ 2 Z= (X1,X2,X3) = ( 36 ,36,0)
9

X1 ≥ 1

X3 ≤ 1

X1 ≥ 3

X3 ≤ 0

o Rama 10: X3 ≤ 2 No es factible, se poda la rama.

X1 ≥ 1

X3 ≤ 1

X1 ≥ 3

X3 ≥ 1

Iteración 2
 o Se ramifica con la primera variable en nodo 9 que debiera ser entera y no lo es, X1.
o Rama 11: X3 ≤ 2 No es factible, se poda la rama.

X1 ≥ 1

X3 ≤ 1

X1 ≥ 3

X3 ≤ 0

X1 ≤ 1

o Rama 12: X3 ≤ 2 No es factible, se poda la rama.

X1 ≥ 1

X3 ≤ 1

X1 ≥ 3

X3 ≤ 0

X1 ≥ 2

3.Criterio de optimalidad.

Ya no existen nodos por realizar y no cuenta con una solución optima

 ARBOL
Z = x1+3x2-2x3
S/A.
4x1+8x2+6x3 = 25
7x1+5x2+9x3 = 30
x1, x2, x3 ≥ 0 SUBPROBLEMA 2
SUBPROBLEMA 1
Z = x 1+3x 2-2x 3
Z = x 1+3x 2-2x 3
S/A.
S/A.
4x 1+8x 2+6x 3 = 25
4x 1+8x 2+6x 3 = 25
7x 1+5x 2+9x 3 = 30
7x 1+5x 2+9x 3 = 30
X3≥3
X3≤2
x 1, x 2, x 3 ≥ 0

x 1, x 2, x 3 ≥ 0

SUBPROBLEMA 4
Z = x 1+3x 2-2x 3
SUBPROBLEMA 3
S/A.
Z = x 1+3x 2-2x 3 4x 1+8x 2+6x 3 = 25
S/A. 7x 1+5x 2+9x 3 = 30
4x 1+8x 2+6x 3 = 25 X3≤2
7x 1+5x 2+9x 3 = 30 X1≥1
X3≤2 x 1, x 2, x 3 ≥ 0
X1≤0
SUBPROBLEMA 5
x 1, x 2, x 3 ≥ 0
Z = x 1+3x 2-2x 3
S/A.
4x 1+8x 2+6x 3 = 25
7x 1+5x 2+9x 3 = 30
X3≤2
X1≥1
X3≤1
x 1, x 2, x 3 ≥ 0
 SUBPROBLEMA 6
Z = x 1+3x 2-2x 3
S/A.
4x 1+8x 2+6x 3 = 25
7x 1+5x 2+9x 3 = 30
X3≤2
X1≥1
X3≥2
x 1, x 2, x 3 ≥ 0

SUBPROBLEMA 7 SUBPROBLEMA 8
Z = x 1+3x 2-2x 3 Z = x 1+3x 2-2x 3
S/A. S/A.
4x 1+8x 2+6x 3 = 25 4x 1+8x 2+6x 3 = 25
7x 1+5x 2+9x 3 = 30 7x 1+5x 2+9x 3 = 30
X3≤2 X3≤2
X1≥1 X1≥1
X3≤1 X3≤1
X1≤2 X1≥3
x 1, x 2, x 3 ≥ 0 x 1, x 2, x 3 ≥ 0

SUBPROBLEMA 9
Z = x 1+3x 2-2x 3 SUBPROBLEMA 10
S/A.
Z = x 1+3x 2-2x 3
4x 1+8x 2+6x 3 = 25
S/A.
7x 1+5x 2+9x 3 = 30
4x 1+8x 2+6x 3 = 25
X3≤2
7x 1+5x 2+9x 3 = 30
X1≥1
X3≤2
X3≤1
X1≥1
X1≥3
X3≤1
X3≤0
X1≥3
x 1, x 2, x 3 ≥ 0
X3≥1
x 1, x 2, x 3 ≥ 0
 SUBPROBLEMA 11 SUBPROBLEMA 12
Z = x 1 +3x 2 -2x 3 Z = x 1 +3x 2 -2x 3

S/A. S/A.

4x 1 +8x 2 +6x 3 = 25 4x 1 +8x 2 +6x 3 = 25

7x 1 +5x 2 +9x 3 = 30 7x 1 +5x 2 +9x 3 = 30

X3≤2
X3≤2
X1≥1
X1≥1
X3≤1
X3≤1
X1≥3
X1≥3
X3≤0
X3≤0
X2≤1
X2≤1
x 1, x 2, x 3 ≥ 0
x1, x2, x3 ≥ 0
1.¿Que es la programación por metas?
La Programación por metas (abreviada PM) apareció originalmente en un artículo de Charnes, Cooper y Ferguson en
1955 (Romero, 2002). Como se explicó anteriormente, se utiliza cuando existen varios objetivos o metas y se desea una
solución satisfactoria y suficiente (satisfaciente).

La estructura de cada meta seguiría este modelo:

fi(x) + ni – pi = ti

En la expresión anterior fi(x) representa la expresión matemática de la meta, a la que se le añaden dos variables de
desviación (ni y pi). La primera, ni, representa un valor faltante para llegar a la meta. La segunda variable de desviación
pi, representa un valor excedente por sobre la meta.

Por ejemplo, suponga que una empresa tiene dos productos: el primero le deja 3 pesos de ganancia y el segundo le
produce solo 1 peso. Se desea obtener 50 pesos de ganancia. La meta estaría representada por

3x1 + x2 + n – p = 50

Tal vez alguien en la empresa sugiere que deberían producir 10 productos x1 y 15 productos x2. Eso implicaría:

3(10) + 1(15) + n – p = 50

30+15 + n – p = 50

45 + n – p = 50

Se necesita que n valga 5 para alcanzar la meta. En otras palabras el beneficio quedó 5 pesos abajo de lo esperado
porque se obtuvo un faltante.

Ahora piense que otra persona en la empresa sugiere que se fabriquen 15 productos de cada tipo. La meta estaría
representada por:
 3(15) + 1(15) + n – p = 50

60 +n – p = 50

Ahora la meta quedó 10 unidades por encima de lo esperado.

Suponga que el plan de producción lo dejamos en 10 x1 y 20 x2. Ello implicaría:

50 + n – p = 50

Por lo que tanto n, como p valen 0. (No hay faltantes ni excedentes).

Variables de desviación no deseadas

2.Analizar un ejemplo de programación por metas

En cierto país de 20 000 habitantes se tienen las siguientes bases tributarias: 550 millones por predial. 35 millones por
alimentos y medicinas. 55 millones por ventas. El consumo anual de gasolina es de 7.5 millones de galones.

Se tienen las siguientes metas:

1. Tener un ingreso por impuestos de 16 millones.

2. Que el impuesto para alimentos y medicinas no exceda el 10% del total de impuestos
3. Que el impuesto sobre ventas no exceda el 20% del total de impuestos.
4. Que el impuesto para gasolina no exceda de 2 centavos por galón.

Así es que las variables serían:

• X1 = tasa tributaria predial

• X2 = tasa tributaria por alimentos y medicinas
• X3 = tasa tributaria por ventas
• X4 = impuesto para gasolina en centavos por galón.
 Las metas quedaría expresadas de la siguiente forma:

1. Tener un ingreso de impuestos de 16 millones.

550x1 + 35x2 + 55x3 + 0.075x4 >= 16

2. Que el impuesto para alimentos y medicinas no exceda el 10% del total de impuestos

35x2 <= .1 (550x1 + 35x2 + 55x3 + 0.075x4)

Haciendo las operaciones correspondientes, y simplificando, la meta anterior quedaría:

55x1 – 31.5x2 + 5.5x3 + 0.0075x4 >= 0

3. Que el impuesto sobre ventas no exceda el 20% del total de impuestos.

55x3 <= .2 (550x1 + 35x2 + 55x3 + 0.075x4)

Haciendo las operaciones correspondientes, y simplificando, la meta anterior quedaría:

110x1 + 7x2 – 44x3 + 0.015x4 >= 0

4. Que el impuesto para gasolina no exceda de 2 centavos por galón.

x4 <= 2

La planificación por metas (incluyendo las variables de desviación) sería:

550x1 + 35x2 + 55x3 + 0.075x4 + n1 – p1 = 16

55x1 – 31.5x2 + 5.5x3 + 0.0075x4 +n2 – p2 = 0

110x1 + 7x2 – 44x3 + 0.015x4 +n3 – p3 = 0

X4 + n4 – p4 = 0

Las variables de desviación no deseadas serían: n1, n2, n3, p4.

La función de logro sería:

Min g(n1, n2 , n3, p4)

Esperamos que esta explicación y este ejemplo te hayan permitido entender un poco más la programación por metas.

3.¿Que es la programación lineal?

La Programación Lineal corresponde a un algoritmo a través del cual se pueden resolver situaciones reales en las que se
pretende identificar y resolver dificultades para aumentar la productividad respecto a los recursos (principalmente los
limitados y costosos), aumentando así los beneficios. El objetivo primordial de la Programación Lineal es optimizar, es
decir, maximizar o minimizar funciones lineales en varias variables reales con restricciones lineales (sistemas de
inecuaciones lineales), optimizando una función objetivo también lineal.

4.¿Que es el algoritmo de ramificación y acotamiento?

El método de Branch and Bound (o Ramificación y Acotamiento) es un algoritmo diseñado para la resolución de modelos
de Programación Entera. Su operatoria consiste en linealizar el modelo de Programación Entera, es decir, resolver éste
como si fuese un modelo de Programación Lineal y luego generar cotas en caso que al menos una variable de decisión
(entera) adopte un valor fraccionario.

El algoritmo genera en forma recursiva cotas (o restricciones adicionales) que favorecen la obtención de valores enteros
para las variables de decisión. En este contexto resolver el modelo lineal asociado a un modelo de Programación Entera
se conoce frecuentemente como resolver la relajación continua del modelo entero .
 5.Analizar un ejemplo de ramificación y acotamiento
Consideremos el siguiente modelo de Programación Entera el cual resolveremos con el algoritmo de Branch and
Bound:

1.
El paso inicial consiste en resolver este problema como si fuese un modelo de Programación Lineal (relajación
continua). Si la solución de dicho problema llegara a respetar las condiciones de integralidad para las variables de
decisión, ésta ya sería la solución óptima del problema entero.
Si bien este procedimiento se puede extender a problemas de mayor dimensión, utilizamos un modelo en 2 variables
para poder representar los pasos del algoritmo gráficamente. El gráfico a continuación muestra dicha resolución:
 2.
La solución óptima del problema lineal asociado (que llamaremos P0) es X1=2,8 y X2=1,6 con valor óptimo V(P0)=20,8.
Claramente esta solución no cumple las condiciones de integralidad para las variables de decisión por tanto es necesario
generar cotas o restricciones adicionales de modo de poder obtener soluciones enteras. Para ello debemos seleccionar
una de las 2 variables de decisión con valores fraccionarios para poder generar cotas. En estricto rigor es indistinto cuál
de ellas seleccionemos debido a que el método nos debe llevar a conclusiones similares (aun cuando la cantidad de
pasos requeridos o rapidez de convergencia cambie).
En nuestro ejemplo generaremos cotas adicionales para la variable X1 aproximando su valor actual al entero inferior más
cercano (P1) y entero superior más cercano (P2).

La resolución gráfica del problema 1 (P1) nos da como solución óptima X1=2 y X2=2 que es una solución entera. El valor
óptimo del problema 1 es V(P1)=20. Notar que V(P1)<V(P0) lo cual es natural dado que el dominio de soluciones
factibles del P1 es menor (subconjunto) al dominio de soluciones factibles de P0.
Análogamente la resolución gráfica (Método Gráfico) del problema 2 (P2) determina
que X1=3 y X2=4/3 con V(P2)=20 según se observa a continuación:
Luego no sería del todo necesario seguir desarrollando el algoritmo dado que si generamos cotas para la variable X2
del P2 en ningún caso podríamos obtener una solución entera con valor óptimo superior a 20 (valor que reporta en la
función objetivo la actual solución entera de P1) y por tanto podríamos concluir que X1=2 y X2=2 es la solución óptima
del problema entero. No obstante el siguiente diagrama muestra los pasos adicionales en caso que quisiera agregar
cotas adicionales a partir del P2.
Un argumento similar al expuesto previamente en este caso explicaría la no necesidad de seguir ramificando el P21. Se
propone al lector verificar que se obtiene la misma solución óptima si luego del P0 ramificamos a través de X2 agregando
las restricciones X2<=1 y X2>=2.