Tarea

PROGRAMACIÓN LINEAL ENTERA
MÉTODOS DE RESOLUCIÓN
Redondeo: DESACONSEJABLE:
•
•

Por producir “malas” soluciones
Por producir soluciones infactibles

Ejemplo
Max F(X) = 4x1 + 3x2
s.a.

2x1 + x2 ≤ 2
3x1 + 4x2 ≤ 6

x1 ≥ 0 , x2 ≥ 0 x1 , x 2 ∈ {0,1}

PLA
Max F(X) = 4x1 + 3x2
s.a.

2x1 + x2 ≤ 2
3x1 + 4x2 ≤ 6

0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1
Solución
x1 = 0,4 , x2 = 1,2 y F(X) = 5,2.

(0,1) F=3

(O.4,1.2) F=5,2(1,0) F=4

* Redondeo Æ Infactible
Max F(X) = 8x1 + 10x2
s.a.

4x1 + 6x2 ≤ 24
8x1 + 3x2 ≤ 24
x1≥0,x2≥0, x1,x2∈Z+

PLA
Max F(X) = 8x1 + 10x2
s.a.

4x1 + 6x2 ≤ 24
8x1 + 3x2 ≤ 24
x1≥0,x2≥0

Solución:

x1=2, x2=8/3, F(X)= 128/3

Redondeo:

x1=2, x2=3

(0,4) F= 40

4x1+6x2 =24

(0,3) F=30

(1,3) F=38
(2,8/3) F= 128/3

F(x) = 8x1+10x2

(0,2) F=20

(1,2) F=28

(1,3) F=38

8x1+3x2=24
(0,1) F=10

(0,0)F=0

(1,1) F=18

(1,0) F=8

(2,1) F=26

(2,0) F=16

(3,0) F=24

Metodos generales:
-Enumeración
-Algebraicos

Enumeración: Identificar todas las soluciones del problema.
Algebraicos: Determinar la envoltura convexa.

Enumeración total: Variables binarias:
Variables
1
2
3

Numero de Soluciones
2
4
8

n

2n

Si n = 100

2100

1,26765E+30

Ordenador capaz de analizar 100 millones de operaciones
porsegundo. Cuanto tiempo tardará?
Unos pocos segundos
Unos pocos minutos
Un par de horas
Una mañana
Dos dias
Tres semanas
Cuatro meses.
Solución:

4,075522763 billones de siglos

MÉTODO DE RAMIFICACIÓN Y ACOTACIÓN
(Branch and Bound).
Pasos:
Ramificacion:

Variables

Acotación:

Valor de la función objetivo

A partir de la solución del PLA:
La ramificación consiste en dividir cada problema en dosnuevos subproblemas,
obtenidos mediante la imposición de restricciones excluyentes que dividen el conjunto
de oportunidades del problema original en dos partes, pero eliminando en ambas partes
la solución no entera del problema original.
Si xbi no entero, entonces se generan a partir de dicho valor dos restricciones xi ≤ [xbi] y
xi ≥ [xbi]+1 (siendo [xbi] la parte entera por defecto de xbi ), queañadidas cada uno por
separado al problema original, da lugar a dos nuevos subproblemas.
Por ejemplo la variable x1 tiene que ser entera, pero en la solución anterior (PLA u
otro), la variable vale: x1 = 6.8. Esta solución no es valida, ya que no es admisible un
valor fraccional, por tanto se introduciran las siguientes restricciones: x1≤ 6 y x1≥ 7, de
forma que se ha eliminado una porción delconjunto donde no hay soluciones enteras,
pero se mantienen las enteras:

Asi se prosigue con todas las variables hasta que sean enteras.
Si al proceso de ramificación no se mejora de alguna forma, llegariamos a
analizar TODAS las soluciones enteras (Enumeracion Total). Por eso, se añade la fase
de Acotación, esta tiene que ver con el valor de la función objetivo.
A medida que se va ramificando seobtienen soluciones enteras y otras que no lo
son.
No podemos asegurar que la primera solución entera obtenida sea la solución optima,
sino que es necesario comprobar si existen otras soluciones enteras o no.

El análisis del PLA: Ramificación se realiza siempre a partir de aquel problema que
tiene el mejor valor de la función objetivo, y siempre que exista alguna solución (no
entera) con un valor dela función objetivo
Ejemplo: (Maximización)
*

Solucion del PLA:

FO: 5487,33 (Solución no entera)

Primera Ramificación:
Problema 1:

FO: 5340, 75 (solución no entera)

Problema 2:

FO: 5425.10 (solución no entera).

Segunda Ramificación:
A partir del problema 2, por tener un mejor valor de la función objetivo:
Problema 21: FO: 5405, 30 (solución no entera)
Problema 22: FO: Infactible.
Como nohay solución entera hemos de seguir ramificando: Por donde?. Problema 22
tiene mejor valor que problema 1.
Tercera ramificación:
A partir del problema 21
Problema 211: FO = 5350 (solución entera)
Problema 212 F= = 5385.25 (solución no entera).
La solución del problema 211 (5350) es la optima?

NO, ya que ramificando por el problema 212 se podrían encontrar mejores soluciones.
Pero lo que es...