359 prog dinamica entera 2015_1

TRABAJO PRÁCTICO

ASIGNATURA: CÓD. ASIGNATURA: APLICACIONES DE PROGRAMACIÓN ENTERA Y DINAMICA 359 NOMBRE DEL ESTUDIANTE: CÉDULA DE IDENTIDAD: CORREO ELECTRÓNICO: TELÉFONO (S): CENTRO LOCAL: CÓD. CENTRO LOCAL: ARAGUA 0400 CARRERA: CÓD. CARRERA: INGENIERÍA DE SISTEMAS 236 ASESOR: FIRMA DEL ESTUDIANTE: _____________________________

LAPSO: 2015-1

UNIVERSIDAD NACIONAL ABIERTA AREA DE INGENIERÍA CARRERA DE INGENIERÍA DE SISTEMAS

2

Contenido

2 INTRODUCCIÓN........................................................................................................ 3

3 OBJETIVO 3 ................................................................................................................ 4

3.1 PLANTEAMIENTO DEL PROBLEMA .......................................................................................... 4

3.2 SOLUCIÓN .......................................................................................................................................... 5

4 OBJETIVO 4 ............................................................................................................. 11

4.1 PROBLEMA ..................................................................................................................................... 11

4.2 SOLUCIÓN ....................................................................................................................................... 11

5 OBJETIVO 7 ............................................................................................................. 15

5.1 PLANTEAMIENTO DEL PROBLEMA ....................................................................................... 15

5.2 SOLUCIÓN ....................................................................................................................................... 15

3

2 INTRODUCCIÓN

El presente trabajo tiene la finalidad de poner en práctica los

conocimientos adquiridos de la materia 359 APLICACIONES DE

PROGRAMACIÓN ENTERA Y DINAMICA.

En el objetivo 3 el planteamiento nos lleva a la empresa

productora de Cemento para analizar la mejor opción posible para

disminuir los costos en la reducción de la cantidad de partículas

de los diferentes contaminantes que se diseminan en el ambiente,

mejorando la calidad de vida de los habitantes de la zona.

En el objetivo 4 nos presentan una empresa que produce

juguetes en nuestro ejemplo de muñecas, la empresa quiere

conocer como minimizar los costos para producir la cantidad de

muñecas por tipo en las dos máquinas disponibles, de acuerdo a

una demanda establecida.

En el objetivo 7 nos presentan un problema de una empresa

de mercadeo que quiere conocer si saca uno de sus productos

fuera del mercado de acuerdo a unas probabilidades usando las

cadenas de Markov, se presentan las diferentes alternativas y

para cada una de ellas si se maneja o no publicidad.

4

3 OBJETIVO 3

3.1 PLANTEAMIENTO DEL PROBLEMA

Cemeca, es una empresa productora de cemento en el país, que

se encuentra ubicada en una zona cuya comunidad ha crecido y

prosperado junto a la compañía dando empleo a muchos de sus

habitantes. Sin embargo, al pasar el tiempo la contaminación no

controlada del aire debido a los hornos de la planta está en camino

de poner en peligro la salud de sus habitantes.

Es por ello que tanto la empresa como los pobladores de la zona

y la alcaldía han establecido tres tipos principales de

contaminantes, además los nuevos estándares de pureza en el

ambiente requieren que la empresa reduzca la emisión anual de

estos contaminantes en las cantidades que se presentan en la

siguiente tabla:

La planta dispone de hornos, filtros y combustibles que minimizan

la cantidad de partículas molidas contaminantes que en el proceso

de producción se disemina en el ambiente. La siguiente tabla

proporciona la reducción de la tasa de emisión (en millones de

libras por año).

5

La empresa requiere minimizar los costos anuales en que incurrirá

para reducir la contaminación, la siguiente tabla muestra los

costos por hornos, filtros y combustibles:

De igual forma, la empresa determinó unos costos fijos de 2

millones por cada uno de los Hornos altos y bajos por lo tanto k1 =

2 k2 = 2.

Dada la información anterior y debido a la naturaleza de encontrar

un plan que satisfaga los requerimientos con el menor costo

posible se formó un equipo de investigación de operaciones, éste

equipo decidió enfocar el problema desde un punto de vista de

Programación Entera.

Responda los siguientes ítems:

• Modele el problema de Programación Entera.

• Resuélvalo aplicando el paquete de programación que

disponga.

• Interprete los resultados.

3.2 SOLUCIÓN

Variables de decisión

Xi: Millones de toneladas de partículas contaminantes

molidas en los hornos de chimeneas altas. Donde i = 1, 2, 3.

1 Partículas contaminantes molidas de Polvo de Horno.

2 Partículas contaminantes molidas de Monóxido (CO).

3 Partículas contaminantes molidas de Óxido de Azufre.

6

Yi: Millones de toneladas de partículas contaminantes

molidas en los hornos de chimeneas bajas. Donde i = 1, 2, 3.




Zi: Millones de toneladas de partículas contaminantes

molidas usando filtros en chimeneas altas. Donde i = 1, 2, 3.




Wi: Millones de toneladas de partículas contaminantes

molidas usando filtros en chimeneas bajas. Donde i = 1, 2, 3.




Mi: Millones de toneladas de partículas contaminantes

molidas usando combustible en chimeneas altas. Donde i = 1, 2,

3.




Ni: Millones de toneladas de partículas contaminantes

molidas usando combustible en chimeneas bajas. Donde i = 1, 2,

3.


7



usamoslonoSi

altaschimeneasenhornosusamosSiK

0

11

usamoslonoSi

bajaschimeneasenhornosusamosSiK

0

12

Función Objetivo

MIN Costo = 2 K1 + 2 K2 + 8 X1 + 8 X2 + 8 X3 + 10 Y1 + 10 Y2

+ 10 Y3 + 7 Z1 + 7 Z2 + 7 Z3 + 6 W1 + 6 W2 + 6 W3 + 11 M1 + 11

M2 + 11 M3 + 9 N1 + 9 N2 + 9 N3

SUJETO A

12 X1 + 9 Y1 + 25 Z1 + 20 W1 + 17 M1 + 13 N1 = 60

35 X2 + 42 Y2 + 18 Z2 + 31 W2 + 56 M2 + 49 N2 = 120

37 X3 + 53 Y3 + 28 Z3 + 24 W3 + 29 M3 + 20 N3 = 125

- 84 K1 + X1 + X2 + X3 <= 0

- 104 K2 + Y1 + Y2 + Y3 <= 0

Programa usando LINDO 6.1 Resultado

LP OPTIMUM FOUND AT STEP 7

OBJECTIVE FUNCTION VALUE

1) 62.47108

VARIABLE VALUE REDUCED COST

K1 0.000000 2.000000

K2 0.022678 0.000000

8

X1 0.000000 4.640000

X2 0.000000 1.571429

X3 0.000000 1.005443

Y1 0.000000 7.499231

Y2 0.000000 2.304945

Y3 2.358490 0.000000

Z1 2.400000 0.000000

Z2 0.000000 3.693877

Z3 0.000000 1.706821

W1 0.000000 0.400000

W2 0.000000 0.306122

W3 0.000000 1.462990

M1 0.000000 6.240000

M2 0.000000 0.714286

M3 0.000000 5.517779

N1 0.000000 5.360000

N2 2.448980 0.000000

N3 0.000000 5.219158

ROW SLACK OR SURPLUS DUAL PRICES

2) 0.000000 -0.280000

3) 0.000000 -0.183673

4) 0.000000 -0.189042

5) 0.000000 0.000000

6) 0.000000 0.019231

NO. ITERATIONS= 7

9

RANGES IN WHICH THE BASIS IS UNCHANGED:

OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE K1 2.000000 INFINITY 2.000000

K2 2.000000 149.783768 2.000000

X1 8.000000 INFINITY 4.640000

X2 8.000000 INFINITY 1.571429

X3 8.000000 INFINITY 1.005443

Y1 10.000000 INFINITY 7.499231

Y2 10.000000 INFINITY 2.304945

Y3 10.000000 1.440229 INFINITY

Z1 7.000000 0.500000 INFINITY

Z2 7.000000 INFINITY 3.693877

Z3 7.000000 INFINITY 1.706821

W1 6.000000 INFINITY 0.400000

W2 6.000000 INFINITY 0.306122

W3 6.000000 INFINITY 1.462990

M1 11.000000 INFINITY 6.240000

M2 11.000000 INFINITY 0.714286

M3 11.000000 INFINITY 5.517779

N1 9.000000 INFINITY 5.360000

N2 9.000000 0.483871 INFINITY

N3 9.000000 INFINITY 5.219158

10

RIGHTHAND SIDE RANGES

ROW CURRENT ALLOWABLE ALLOWABLE

RHS INCREASE DECREASE

2 60.000000 INFINITY 60.000004

3 120.000000 INFINITY 120.000000

4 125.000000 INFINITY 124.999992

5 0.000000 INFINITY 0.000000

6 0.000000 2.358490 INFINITY

El costo mínimo según la solución óptima es: Costo = 62.47108

Bolívares fuertes. Esto le corresponde a la solución continua.

El costo mínimo correspondiente a la solución entera es: Costo =

64.425720 Bs.

La solución óptima establece que no debe usarse el horno en

chimeneas altas

Moler 2.358.490 partículas contaminantes de Óxido de azufre en

los hornos de chimeneas bajas (Y3).

Moler 2.400.000 partículas contaminantes de Polvo de horno

usando filtros en chimeneas altas (Z1).

Moler 2.448.980 partículas contaminantes de Monóxido (CO)

usando combustible en chimeneas bajas (N2).

11

4 OBJETIVO 4

4.1 PROBLEMA

La compañía de Juguetes JVG. C.A. es la compañía más grande

en su ramo, entre sus diferentes marcas produce las muñecas

Pily, Alix y Mela. Cada una de estas muñecas se produce en dos

máquinas. A la máquina (1) le lleva por lo menos 6,5 horas

elaborar las tres muñecas y la máquina (2) se demora por lo

menos 9,5 horas en fabricar tres de Pily, uno de Alix y cuatro de

Mela.

La demanda de Pily es de un máximo de una muñeca, mientras

que Alix es de un máximo de dos muñecas, para Mela se espera

sea de un máximo de cuatro muñecas. Si los costos de producción

de Pily, Alix y Mela son 1, 3, y 5 Unidades Monetarias (UM).

Cuánto se debe producir de cada una de las tres muñecas para

minimizar los costos de producción, para ello aplique

Programación Entera (PE) y realice lo siguiente:

a. Modele el problema de Programación Entera.

b. Enumera las soluciones posibles del problema.

c. Aplique el Algoritmo de Corte para lograr la solución óptima.

d. Conclusiones.

4.2 SOLUCIÓN

Evaluando el problema nos enfrentamos en principio a un

problema de programación lineal entera ya que:

1. El número de muñecas a producir es entero.

2. Podemos considerar el manejo de dos variables de decisión

(0 y 1) que son:

a. La primera decisión si las muñecas se producen en la

maquina 1.

12

b. La segunda si las muñecas se producen en la

maquina 2.

3. No tenemos una restricción de tiempo, el cual es un

problema ya que esto ocasiona una restricción infinita en el

tiempo.

4. La especificación de la producción de cada máquina no es

clara:

a. Para la maquina 1 dice que produce simultáneamente

los tres tipos de muñecas en 6,5 horas, pero no está

definido el tiempo que toma cada una.

b. Para la maquina 2 ocurre algo similar produce

simultáneamente 3 de Pily, 1 de Alix y 4 de Mela en

9,5 horas sin especificar el tiempo en cada una.

5. La demanda es contradictoria con la producción definida en

el punto 4, si probamos lo siguiente:

a. Si usamos la maquina 1, el modelo Pily solo podemos

producir una sola muñeca.

b. Si usamos la maquina 2, el mismo modelo se pueden

producir 3 solo si la usamos una sola vez.

c. Si usamos la maquina 1 solo podemos producir una

sola muñeca de cada tipo.

6. Al analizar el tiempo empleado para producir las muñecas

en las dos máquinas, podemos constatar que el mismo es

independiente, usamos la maquina 1 para producir por

separado cada tipo de muñeca, pero para ello

necesitáremos una restricción del tiempo al utilizar dicha

máquina, igual razonamiento se le aplicaría a la maquina 2.

En la tabla a continuación se muestra unas consideraciones

de posibles alternativas para la producción de dichas

muñecas.

13

Pily Alix Mela Pily Alix Mela Pily Alix Mela

1 0 0 1 2 0 0 1 1

1 0 1 1 2 1 0 1 2

1 0 2 1 2 2 0 1 3

1 0 3 1 2 3 0 1 4

1 0 4 1 2 4 0 2 0

1 1 0 0 0 1 0 2 1

1 1 1 0 0 2 0 2 2

1 1 2 0 0 3 0 2 3

1 1 3 0 0 4 0 2 4

1 1 4 0 1 0

Montando el problema en el paquete de programación Winqsb da

un problema no factible, ver prueba 1:

LP MatrixFormat Juguetes JVG 3 5

Variable --> X1 X2 X3 Direction R. H. S.

Minimize 1 3 5

C1 1 1 1 <= 6.5

C2 3 1 4 <= 9.5

C3 1 0 0 >= 1

C4 0 1 0 >= 2

14

C5 0 0 1 >= 5

LowerBound 0 0 0

UpperBound M M M

VariableType Integer Integer Integer

En Lindo 6.1

Conclusión: Se probaron distintas formas y por las razones

descriptas anteriormente, este problema no es factible desde el

punto de vista de lo planteado.

15

5 OBJETIVO 7

5.1 PLANTEAMIENTO DEL PROBLEMA

El gerente de mercadeo de una empresa revisa cada año el

estado de uno de sus productos importantes y debe decidir si tiene

que retirarlo del mercado, clasifica sus volúmenes de ventas

durante cada mes en a) regular b) bueno c) excelente. Estudios

de mercados indican que en un año las siguientes matrices 𝑃1y

𝑃2 representan las probabilidades de transición sin y con

publicidad durante cualquier año. Los ingresos correspondientes

se representan con las matrices 𝑅1 y 𝑅2

Para una táctica permanente K= 1 o K = 2 y r = 0.9 determine la

esperanza matemática del valor actualizado para ambas tácticas

sin y con publicidad.

5.2 SOLUCIÓN

Conjunto de los posibles estados es: 3,2,1 , que le

corresponden a los volúmenes de venta para cada mes:

(1) si el volumen de venta es regular.

(2) si el volumen de venta es bueno.

(3) si el volumen de venta es excelente.

El conjunto de decisiones está constituido por los dos niveles

referentes a la publicidad: 2,1U , donde:

(1) representa que no se realiza publicidad

16

(2) representa que si se realiza publicidad.

Como 2,1U , entonces:

2

2

2

,

1

2

2

,

2

1

2

,

1

1

2

,

2

2

1

,

1

2

1

,

2

1

1

,

1

1

1

K 76

Paso 1:

A la táctica permanente

1

1

11

K , le corresponden las matrices:

1

3

3,5

;

100

150

367

;

100

5,05,00

3,05,02,0)1()1()1(

qyRT

donde el vector )1(

q , lo calculamos de la siguiente manera:

1

3

3,5

))1(*1()0*0()0*0(

)1*5,0()5*5,0()0*0(

)3*3,0()6*5,0()7*2,0()1(

q

Paso 2:


2

1

12


4,0

3

3,5

;

236

150

367

;

55,04,005,0

5,05,00

3,05,02,0)2()2()2(

qyRT

donde el vector )2(

q , se calculó de manera semejante al )1(

q .

17

Paso 3:


1

2

13


1

1,3

3,5

;

100

047

367

;

100

3,06,01,0

3,05,02,0)3()3()3(

qyRT

Paso 4:


2

2

14


4,0

1,3

3,5

;

236

047

367

;

55,04,005,0

3,06,01,0

3,05,02,0)4()4()4(

qyRT

Paso 5:


1

1

25


1

3

7,4

;

100

150

156

;

100

5,05,00

1,06,03,0)5()5()5(

qyRT

Paso 6:

18


2

1

26


4,0

3

7,4

;

236

150

156

;

55,04,005,0

5,05,00

1,06,03,0)6()6()6(

qyRT

Paso 7:


1

2

27


1

1,3

7,4

;

100

047

156

;

100

3,06,01,0

1,06,03,0)7()7()7(

qyRT

Paso 8:


2

2

28


4,0

1,3

7,4

;

236

047

156

;

55,04,005,0

3,06,01,0

1,06,03,0)8()8()8(

qyRT

Inicio del esquema de aproximaciones sucesivas, con

1

1

110 KK

Iteración 1:

19

Formula:

(1) )0()1()1()0()0( ,,,)0()0(

KrsTqrKrsTqrKrsKK

Sustituyendo y resolviendo:

)0()0()0( ,*

9,000

45,045,00

27,045,018,0

9,0

7,2

77,4

,

100

5,05,00

3,05,02,0

1

3

3,5

9,0, KrsKrsKrs

9,0

7,2

77,4

,*

9,000

45,045,00

27,045,018,0

, )0()0( KrsKrs , de donde:

9,0

7,2

77,4

,*

9,000

45,045,00

27,045,018,0

100

010

001)0(

krs

9,0

7,2

77,4

,*

1,000

45,055,00

27,045,082,0)0(

krs

al despejar: )0(,Krs , nos queda:

9,0

7,2

77,4

1,000

45,055,00

27,045,082,0

,

1

)0(krs

calculamos la matriz inversa usando Matlab y nos queda:

)0(

)0(

)0(

)0(

,,3

,,2

,,1

9

4545,2

5067,1

9,0

7,2

77,4

*

1000

1818,88182,10

2827,79978,02195,1

,

krs

krs

krs

krs

20

(2) Determinamos Kk )1(, mediante la ecuación:

)()()()( ,max,)1()1( lkk

Kk

lkkkrsTqkrsTq

ll

Como el vector: )0()()( ,krsTqkk , posee tres componentes,

entonces la ecuación antes mencionada es un sistema de tres

ecuaciones independientes, las cuales son:

)0(

)0(

)0(

)(

33

)(

32

)(

31

)(

23

)(

22

)(

21

)(

13

)(

12

)(

11

3

2

1

,,3

,,2

,,1

*

krs

krs

krs

ppp

ppp

ppp

q

q

q

kkk

kkk

kkk

k

k

k

Primera ecuación:

)0()(

13

)0()(

12

)0()(

11

)(

1 ,,3*,,2*,,1* krspkrspkrspqkkkk .

Segunda ecuación:

)0()(

23

)0()(

22

)0()(

21

)(

2 ,,3*,,2*,,1* krspkrspkrspqkkkk

Tercera ecuación:

)0()(

33

)0()(

32

)0()(

31

)(


Se analiza cada ecuación por separado:

Primera ecuación: Como por definición de “K”, la primera

componente k1 de cualquier táctica permanente “k”, solo toma

valores de 1 y 2, entonces.

Si k1 = 1, la ecuación queda como:

21

)0()1(

13

)0()1(

12

)0()1(

11

)1(

1 ,,3*,,2*,,1* krspkrspkrspq

sustituyendo tenemos:

5,3 + (0,2 * 1,5067) + (0,5 * (-2,4545)) + (0,3 * (-9)) = 1,67409


)0()2(

13

)0()2(

12

)0()2(

11

)2(



4,7 + (0,3 * 1,5067) + (0,6 * (-2,4545)) + (0,1 * (-9)) = 2,77931

Como 77931,277931,2;67409,1max , entonces la primera

componente de )1(

k es de 2.

Segunda ecuación:


)0()1(

23

)0()1(

22

)0()1(

21

)1(



3 + (0 * 1,5067) +( 0,5 * (-2,4545)) + (0,5 * (-9)) = -2,72725


)0()2(

23

)0()2(

22

)0()2(

21

)2(



22

3,1 + (0,1 * 1,5067) +( 0,6 * (-2,4545)) + (0,3 * (-9)) = -0,92203

Como 92203,092203,0;72725,2max , entonces la segunda

componente de )1(

k es de 2.

Tercera ecuación:


)0()1(

33

)0()1(

32

)0()1(

31

)1(



-1 + (0 * 1,5067) +( 0 * (-2,4545)) + (1 * (-9)) = -10


)0()2(

33

)0()2(

32

)0()2(

31

)2(



0,4 + (0,05 * 1,5067) + (0,4*(-2,4545)) + (0,55 * (-9)) = -5,456465

Como 456465,5456465,5;10max , entonces la tercera

componente de )1(

k es 2.

Por lo tanto: 081

2

2

2

KKK

, se tiene que iterar de nuevo.

Iteración 2:

23

(1) Usamos la ecuación:

)1()8()8()1()1( ,,,)1()1(

KrsTqrKrsTqrKrsKK

= )1()1( ,*

495,036,0045.0

27,054,009,0

09,054,027,0

36,0

79,2

23,4

,

55,04,005,0

3,06,01,0

1,06,03,0

4,0

1,3

7,4

9,0 KrsKrs

36,0

79,2

23,4

,*

495,036,0045,0

27,054,009,0

09,054,027,0

, )1()1(KrsKrs

Donde:

36,0

79,2

23,4

,*

495,036,0045,0

27,054,009,0

09,054,027,0

100

010

001)1(

krs

36,0

79,2

23,4

,*

505,036,0045,0

27,046,009,0

09,054,073,0)1(

krs

al despejar )1(,Krs , nos queda:

36,0

79,2

23,4

505,036,0045,0

27,046,009,0

09,054,073,0

,

1

)1(krs

calculamos esa matriz inversa usando Matlab:

)1(

)1(

)1(

)1(

,,3

,,2

,,1

9951,17

2744,21

7503,23

36,0

79,2

23,4

*

5776,145760,48464,0

2706,38113,59181,0

9837,28629,41533,2

,

krs

krs

krs

krs

(2) Determinamos Kk )2( , mediante la ecuación:

24

)()()()( ,max,)1()1( lkk

Kk

lkkkrsTqkrsTq

ll

Como el vector: )1()()( ,krsTqkk , posee tres componentes,

entonces la ecuación antes mencionada es un sistema de tres

ecuaciones independientes, las cuales son:

)1(

)1(

)1(

)(

33

)(

32

)(

31

)(

23

)(

22

)(

21

)(

13

)(

12

)(

11

3

2

1

,,3

,,2

,,1

*

krs

krs

krs

ppp

ppp

ppp

q

q

q

kkk

kkk

kkk

k

k

k

Primera ecuación:

)1()(

13

)1()(

12

)1()(

11

)(


Segunda ecuación:

)1()(

23

)1()(

22

)1()(

21

)(


Tercera ecuación:

)1()(

33

)1()(

32

)1()(

31

)(


Primera ecuación: Como por definición de “K”, la primera

componente k1 de cualquier táctica permanente “k”, solo toma

valores de 1 y 2, entonces.


)1()1(

13

)1()1(

12

)1()1(

11

)1(



25

5,3 +(0,2 * 23,7503) +(0,5 * 21,2744) +(0,3 *17,9951) = 26,08579


)1()2(

13

)1()2(

12

)1()2(

11

)2(



4,7 + (0,3 * 23,7503) +( 0,6 * 21,2744) + (0,1 * 17,9951) = 26,38924

Como 38924,2638924,26;08579,26max , entonces la primera

componente de )2(k es de 2.

Segunda ecuación:


)1()1(

23

)1()1(

22

)1()1(

21

)1(



3 + (0 * 23,7503) +( 0,5 * 21,2744) + (0,5 * 17,9951) = 22,63475


)1()2(

23

)1()2(

22

)1()2(

21

)2(



3,1 + (0,1 * 23,7503) +(0,6 * 21,2744) + (0,3 *17,9951) = 23,6382

Como 6382,236382,23;63475,22max , entonces la segunda

componente de )2(k es de 2.

26

Tercera ecuación:


)1()1(

33

)1()1(

32

)1()1(

31

)1(



-1 + (0 * 23,7503) +( 0 * 21,2744) + (1 * 17,9951) = 16,9951


)1()2(

33

)1()2(

32

)1()2(

31

)2(



0,4 +(0,05*23,7503)+(0,4 *21,2744)+(0,55 *17,8851) = 19,99458

Como 99458,1999458,19;9951,16max , entonces la tercera

componente de )2(k es 2.

Resultado final:

Por lo tanto: 82

2

2

2

KK

, entonces la táctica permanente óptima

es K

2

2

22

K , el valor de la función objetivo actualizado

27

sobre una infinidad de periodos correspondiente a

K es:

9951,17

2744,21

7503,23

, )1(krs

359 prog dinamica entera 2015_1

Documents