Evaluacion De Calculo Vectorial

INSTITUTO TECNOLÓGICO SUPERIOR DE MISANTLA

INVESTIGACION DE OPERACIONES

UNIDAD V

METODO DE RAMIFICACION Y ACOTAMIENTO

METODO DE PLANOS CORTANTES

ING.ROSARIO CASTRO Y GARCIA

LILIANA ALVARADO FLORES

ING. INDUSTRIAL

PROGRAMACION ENTERA

En algunos casos se requiere que la solución óptima se componga de valores enteros para algunas de las variables. La resolución de este problema se obtiene analizando las posibles alternativas de valores enteros de esas variables en un entorno alrededor de la solución obtenida considerando las variables reales. Muchas veces la solución del programa lineal truncado esta lejos de ser el óptimo entero, por lo que se hace necesario usar algún algoritmo para hallar esta solución de forma exacta. El más famoso es el método de 'Ramificar y Acotar' o Branch and Bound por su nombre en inglés. El método de Ramificar y Acotar parte de la adición de nuevas restricciones para cada variable de decisión (acotar) que al ser evaluado independientemente (ramificar) lleva al óptimo entero.

Un modelo de programación entera es aquel que contiene restricciones y una función objetivo idénticas a la formuladas en programación lineal , la única diferencia en que una o mas variables de decisión deben tomar valor entero en la solución final.

CLASIFICACIÓN:

Existen tres tipos de modelos por programación entera

A) PURA : Son modelos similares a los de programación entera

Forma General :

Max (Min ) = A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn

Sujeto a : A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn >= (<=)(=) Bi

No negatividad : Xi >= 0 y ENTERO

B) BINARIA : Estos modelos lineales , las variables sólo toman valores 0 y 1 , son usadas para uso probabilistico Donde 0 se rechaza la opción y 1 se acepta la opción.

Forma General :

Max (Min ) = A1Y1+A2Y2+A3Y3+A4Y4+A5Y5+..........+AnYn

Sujeto a : y1+y2+y3+y4+..........+yn >= (<=)(=) Bi

No negatividad : yi >= 0 v 1

C) MIXTA : En estos tipos de modelos , integra las variables puras y las mixtas

Max (Min )

= A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn+A1Y1+A2Y2+A3Y3+A4Y4+A5Y5+..........+AnYn

Sujeto a :

A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn >= (<=)(=) Bi

y1+y2+y3+y4+..........+yn >= (<=)(=) Bi

No negatividad :

Xi >= 0 y ENTERO

Xi >= 0 v 1

* Tipos de Restricciones Usadas en la Programación Entera Mixta :

1) Excluyentes : Solo sirve para elegir una alternativa de varias posibles

2) Pre-requisito : Cuando necesitas realizar una acción antes de proceder con la siguiente

3) Incluyente : Dicha restricción se da para cuando realizas una acción "A" entonces debes hacer la acción "B"

4) Costo Fijo : Cuando se nombra un costo fijo , es sinónimo de uso de variable mixta

Ejemplo Aplicativo

Un problema que afronta todos los días un electricista consiste en decidir qué generadores conectar. El electricista en cuestión tiene tres generadores con las características que se muestran en la tabla 3. Hay dos periodos en el día. En el primero se necesitan 2900 megawatts. En el segundo. 3900 megawatts. Un generador que se conecte para el primer periodo puede ser usado en el segundo sin causar un nuevo gasto de conexión. Todos los generadores principales (como lo son A, B y C de la figura ) son apagados al término del día. Si se usa el generador A también puede usarse el generador C,no se usa generador B si se usa generador A. Formule este problema como un PLEM.

GENERADOR COSTO FIJO DE

CONEXIÓN COSTO POR PERIODO POR MEGAWATT USADO CAPACIDAD MAXIMA EN CADA PERIODO ( MW )

A $ 3000 $ 5 2100

B 2000 4 1800

C 1000 7 3000

V.D.

Xij= Número de megawatts a usar del generador i(i=A,B,C) en el periódo j(j=1,2).

Yi= 0 No arranca el generador i(i=A,B,C)

1 Si arranca el generador i(i=A,B,C)

Restricciones:

Demanda en el periodo 1:

xa1 +xb1+xc1 >= 2900

Demanda en el periodo 2:

xa2+xb2+xc2>= 3900

Capacidad de generador A:

xa1 <= 2100y1( enlace variable entera con variable binaria)

xa2<=2100y1( enlace variable entera con variable binaria)

Capacidad de generador B:

xb1<=1800y2( enlace variable entera con variable binaria)

xb2<=1800y2( enlace variable entera con variable binaria)

Capacidad de generador C:

xc1<=3000y3( enlace variable entera con variable binaria)

xc2<=3000y3( enlace variable entera con variable binaria)

Función Objetivo:

Minimizar(z)= 5(x11+x12) +4(x21+x22) + 7(x31+x32) +3000(y1)+2000(y2) + 1000(y3)

METODO DE RAMIFICACION Y ACOTAMIENTO:

El método de Branch and Bound (en español Ramificación y Acotamiento) aborda la resolución de modelos de programación entera a través de la resolución de una secuencia de modelos de programación lineal que consituirán los nodos o subproblemas del problema entero. Si bien el procedimiento es extendible a un número mayor de variables, para efectos prácticos ilustraremos su aplicación para modelos de programación entera en 2 variables.

Tiempo: Toma tiempo resolver un solo modelo por método Simplex. Pero eso es solo en el mejor caso. En el peor caso no se puede determinar cuántos modelos se resuelven por método Simplex hasta llegar a una solución entera.

Valor menor al óptimo: El valor que se obtiene por el método de ramificación y acotamiento casi siempre es menor al valor obtenido en el método Simplex para el caso no entero.

PRODECIMIENTO:

1) Se tiene un modelo de programación lineal entera.

2) Escoja un criterio de selección del subproblema a resolver. Ese criterio será utilizado en toda la resolución por ramificación y acotamiento. Se tienen dos criterios:

a) Subproblema más reciente: Escoger siempre nodo correspondiente

...