ARBOL DE DECISIONES

ARBOL DE DECISION

El árbol de decisión es un diagrama que representan en forma secuencial condiciones y acciones; muestra qué condiciones se consideran en primer lugar, en segundo lugar y así sucesivamente. Este método permite mostrar la relación que existe entre cada condición y el grupo de acciones permisibles asociado con ella.

Un árbol de decisión sirve para modelar funciones discretas, en las que el objetivo es determinar el valor combinado de un conjunto de variables, y basándose en el valor de cada una de ellas, determinar la acción a ser tomada.

Los árboles de decisión son normalmente construidos a partir de la descripción de la narrativa de un problema. Ellos proveen una visión gráfica de la toma de decisión necesaria, especifican las variables que son evaluadas, qué acciones deben ser tomadas y el orden en la cual la toma de decisión será efectuada. Cada vez que se ejecuta un árbol de decisión, solo un camino será seguido dependiendo del valor actual de la variable evaluada.

Se recomienda el uso del árbol de decisión cuando el número de acciones es pequeño y no son posibles todas las combinaciones.

Uso de árboles decisiones.

El desarrollo de árboles de decisión beneficiado analista en dos formas. Primero que todo, la necesidad de describir condiciones y acciones llevan a los analistas a identificar de manera formal las decisiones que actualmente deben tomarse. De esta forma, es difícil para ellos pasar por alto cualquier etapa del proceso de decisión, sin importar que este dependa de variables cuantitativas o cualitativas. Los árboles también obligan a los analistas a considerar la consecuencia de las decisiones.

Se ha demostrado que los árboles de decisión son eficaces cuando es necesario describir problemas con más de una dimensión o condición. También son útiles para identificar los requerimientos de datos críticos que rodean al proceso de decisión, es decir, los árboles indican los conjuntos de datos que la gerencia requiere para formular decisiones o tomar acciones. El analista debe identificar y elaborar una lista de todos los datos utilizados en el proceso de decisión, aunque el árbol de decisión no muestra todo los datos.

Si los árboles de decisión se construyen después de completar el análisis de flujo de datos, entonces es posible que los datos críticos se encuentren definidos en el diccionario de datos (el cual describe los datos utilizados por el sistema y donde se emplean). Si únicamente se usan árboles de decisiones, entonces el analista debe tener la certeza de identificar con precisión cada dato necesario para tomar la decisión.

Los árboles de decisión no siempre son la mejor herramienta para el análisis de decisiones. El árbol de decisiones de un sistema complejo con muchas secuencias de pasos y combinaciones de condiciones puede tener un tamaño considerable. El gran número de ramas que pertenecen a varias trayectorias constituye más un problema que una ayuda para el análisis. En estos casos los analistas corren el riesgo de no determinar qué políticas o estrategias de la empresa son la guía para la toma de decisiones específicas. Cuando aparecen estos problemas, entonces es momento de considerar las tablas de decision. 

EJEMPLO:

 

PROBLEMA 3 PROGRAMACION DINAMICA

Considere el problema de programacion de la produccion de un producto las 3 semanas siguientes. El costo unitario de produccion es de $100 para las 2 primeras semanas y $150 para las dos ultimas. Las demas semanales son 5,3 y 8 unidades respectivamente y tienen que ser satisfechas. Las plantas pueden producir un maximo de 7 semanales, Ademas, se oueden emplear horas extras durante 2 ultimas semanas, esto incrementa la produccion en 2 unidades por semana, pero el costo de produccion sube en $20 por unidad extra. El exceso de produccion se puede almacenar a un costo unitario de $3 por semana. Si al inicio se tiene 1 unidad de inventario y se desea tener al final 2 unidades¿cual debe ser el plan de produccion?

PROBLEMA 2 PROGRAMACION DINAMICA

Dado el siguiente problema de mochila:

Max = 5x1+4x2^2+2x3^3

sa 4x1+3x2+2x3<=8

xi>=0

PROGRAMACION DINAMICA DETERMINISTICA

BIOGRAFIA: RICHARD BELLMAN

Richard Ernest Bellman (1920–1984) fue un matemático aplicado, cuya mayor contribución fue la metodología denominada programación dinámica.

Bellman estudió matemáticas en la Universidad de Brooklyn, donde obtuvo una diplomatura, y luego en laUniversidad de Wisconsin, donde obtuvo su licenciatura. Posteriormente comenzó a trabajar en el Laboratorio Nacional Los Álamos en el campo de la física teórica. En 1946 obtuvo su doctorado en la Universidad de Princeton. También ejerció la docencia en la universidad del sur de California(EE. UU.), fue socio de la Academia Americana de las Artes y las Ciencias (1975) y de la Academia Nacional Americana de Ingeniería (1977). En 1979 el IEEE le otorgó la medalla de honor por su contribución a la teoría de los sistemas de control y de los procesos de decisión, en especial por su contribución con la programación dinámica y por la ecuación de Bellman.

Su primer estudiante de doctorado fue Austin Esogbue, que es actualmente profesor en el Instituto tecnológico de Georgia, en el departamento de ingeniería industrial y de sistemas.

PROGRAMACION DINAMICA

EJERCICIOS SOBRE LOGICA BINARIA

1. Si tienes 4 productos debes elegir a lo maximo 2

• X1+X2+X3+X4 <= 2

2. Si inviertes en dos negocios, no puedes invertir en cuatro

• X2+X4 <= 1

3. Si preparaste 6 anticuchos, solo debes elegir 4

• X1+X2+X3+X4+X5+X6 <= 4

4. Una máquina o bien puede producir el producto 1 o el producto 2

• X1+X2 <= 1

5. Si comes tambien te nutres

• X1 = X2

6. Tienes la opcion de elegir la pelicula 1 o 2

• Y1 = X1 + X2

7.Si invierte en el producto 2 tambien debes invertir en el producto 1

• Y2 <= Y1

8. Una maquina azucarera puede producir azucar rubia y azucar blanca

• Y1 <= X1 + X2

9. Si barres la casa, debes tambien enserar

• Y1 <= Y2

10. Para producir el producto 1 y 2 se debe producir el 3 y 4

• Y1 + Y2 <= Y3 + Y4

EJERCICIOS DE PROGRAMACION ENTERA

Problema 1.-

Una firma elabora dos productos, A y C. La capacidad de la línea A es de 7 unidades diarias. Cada unidad de C requiere 4 horas de secado, y hay un total de 22 horas disponibles al día para secado. Además, cada unidad de A requiere 2 horas de pulido y cada una de C, 3 horas. Diariamente hay un total de 19 horas de pulido disponibles. Las unidades A producen una utilidad de $1 y $3 las unidades de C, cada una. La firma quiere determinar el plan de producción diario que maximice la utilidad. Los productos A y C sólo se pueden fabricar en cantidades enteras.  El costo de alquiler de una secadora es de $150 y de una pulidora es de $300, además se desea  elaborar solo uno de los productos A ó C. Formule el plan como PLE.

	PRODUCTO  A	PRODUCTO C
CAPACIDAD	7 UNIDADES		DISP.
SECADO		4H/UNIDAD	22 H/SEM.
PULIDO	2 H/UNIDAD	3 H/UNIDAD	19 H/SEM.
UTILIDAD	$1/UNIDAD	$3/UNIDAD

 V.D.

      Xi= Número de unidades del producto i(i= A,B=1,2) a elaborar.

Modelo de P.L.E.

Maximizar (z) = x1 + 3x2

Sujeto a:

                        x1   <= 7

                        4x2 <= 22

               2x1 + 3x2 <= 19

no negatividad: Xi>=0 y entero.

Problema 2.- Programación en una aerolínea.  Alpha Airline desea programar no más de un vuelo desde Chicago hasta cada una de las siguientes ciudades: Columbus, Denver, Los Ángeles y Nueva  York. Los horarios  de salida disponible son 8, 10 y 12 de la mañana. Alpha arrienda los aviones al costo de $5000 hasta las 10, y de $3000 después de las 10 y está en posibilidad de arrendar cuando mucho 2 por horario de salida. En la tabla 2 se presenta la aportación a las utilidades en miles de dólares esperadas por vuelo  antes de los costos de arrendamiento. Elabore un modelo para una programa que maximice las utilidades, si además se debe cumplir con lo siguiente:

a)      Si sale un vuela a Columbus a las 8 a.m. ya no debe salir un vuelo a Denver a las 10 a.m..

b)      Si sale un avión a los Ángeles a las 10 a.m. también debe salir un vuelo a Columbus a las 12 m.

c)      Saldrá un vuelo hacia Nueva York solo si sale antes un vuelo hacia Columbus.

	ESPACIO   DE     TIEMPO
	8 a.m.	10 a.m	12 m
Columbus	10	6	6
Denver	9	10	9
Los Ángeles	14	11	10
Nueva York	18	15	10

V.D

   Xij= 0 si el avión no sale a la hora i(i=8,10,12=1,2,3) hacia la ciudad j(j=Columbus,Denver, Los Angeles, Nueva York=1,2,3,4)

          1 si el avión sale a la hora i(i=8,10,12=1,2,3) hacia la ciudad j(j=Columbus,Denver,LA, NY)

MAX[10x11+6x21+6x31+9x12+10x22+9x32+14x13+11x23+10x33+18x14+15x24+10x34
-5(x11+x12+x13+x14+x21+x22+x23+x24)-3(x31+x32+x33+x34)]*1000
Columbus	x11 + x21 + x31 <=1 y1		x11+x22<=1
Denver	x12 + x22 + x32<=1
Los Angeles	x13 + x23 + x33<= 1		x23=x31
Nueva York	x14 + x24 +x34 <= 1y4		y4<=y1
08:00 a.m.	x11+ x12x13+x14<=2y5
10:00 a.m.	x31+x32+x33+x34<=2y6
12 m	x21+x22+x23+x24<=2y7

Problema 3.- Un problema de instalación  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)