Programacion entera

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=388x1+3x2=24
(0,1) F=10 (1,1) F=18 (2,1) F=26

(0,0) F=0

(1,0) F=8

(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 n Si n = 100 Numero de Soluciones 2 4 8 2n 2100 1,26765E+30

Ordenador capaz deanalizar 100 millones de operaciones por segundo. 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: Acotación: A partir de la solución del PLA: La ramificación consiste en dividir cada problema en dos nuevossubproblemas, 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 del conjuntodonde no hay soluciones enteras, pero se mantienen las enteras: Variables Valor de la función objetivo

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. Amedida que se va ramificando se obtienen 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 existaalguna solución (no entera) con un valor de la función objetivo Ejemplo: (Maximización) * Solucion del PLA: FO: 5487,33 (Solución no entera)

Primera Ramificación: Problema 1: Problema 2: FO: 5340, 75 (solución no entera) 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 no hay 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...