CERTEZA , RIESGO , INCERTIDUMBRE !!!

CERTEZA:

•    Las elecciones Peru 2011 serán el dia 5 de junio del 2011. 
•    El 25 de Diciembre se celebra la Navidad .
•    El 28 de julio celebra el mes de patria del Perú.
•     En la semana 16  se acaba el ciclo 2011-I.
•    El 23 de setiembre es el dia de la primavera .

RIESGO:

• La busqueda de Ciro Castillo Rojo Saldremos invictos este ciclo  cuando viajamos pro primera vez  a un lugar determinado .
• No sabemos quien ganara las elecciones presidenciales del Perú.
• Aprobarémos  el curso de invope II.
•    Al escoger un artículo de una marca desconocida, se corre el riesgo de que no sea confiable.

 

 

INCERTIDUMBRE: 

•  El nuevo gobierno que entrara en vigencia este 28 de  julio  gobernara bien el Pais ?. Sera el fin del mundo el 2012 ....
• Cuando será el fin del mundo.
•   Que  sucederá mañana.
•  La elección del nuevo Presidente del Perú.

ARBOL DE DECISIONES

Examen de Dinamica Parte 2

DINAMICA PROBABILISTICA PROBLEMA 4

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 la Universidad 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 Americanade 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.

Trabajo
Ecuación de Bellman: Programación Dinámica

Una ecuación de Bellman, también conocida como la ecuación de programación dinámica, es una condición necesaria para la optimalidad asociado con el método de optimización matemática conocida como la programación dinámica. Casi cualquier problema que se puede resolver utilizando la teoría de control óptimo también se puede resolver mediante el análisis de la correspondiente ecuación de Bellman. La ecuación de Bellman se aplicó por primera vez a la teoría de la ingeniería de control y otros temas de matemáticas aplicadas, y, posteriormente, se convirtió en una herramienta importante en la teoría económica.

 

Ecuación de Hamilton-Jacobi-Bellman

La ecuación de Hamilton-Jacobi-Bellman (HJB) es una ecuación diferencial parcial que es fundamental para la teoría de control óptimo. La solución de la ecuación HJB es la "función de valor", que da a la óptima función de los costos un determinado sistema dinámico con una función de costos asociados. Clásicos problemas variacionales, por ejemplo puede resolverse utilizando este método.

La ecuación es el resultado de la teoría de programación dinámica que fue creado en los 50’s por Richard Bellman y compañeros de trabajo. La ecuación correspondiente en tiempo discreto que normalmente se conoce como la ecuación de Bellman. En tiempo continuo, el resultado puede ser visto como una extensión del trabajo anterior en la física clásica en la ecuación de Hamilton-Jacobi por William Rowan Hamilton y Carl Gustav Jacob Jacobi.

Algoritmo de Bellman-Ford

El algoritmo de Bellman-Ford, a veces conocido como el algoritmo de corrección de la etiqueta, calcula un solo proveedor o caminos más cortos en un digrafo ponderado (donde algunos de los valores pueden ser negativos). El algoritmo de Dijkstra logra el mismo problema con un tiempo de baja en ejecución, pero requiere de pesos ventaja de ser no-negativas.

Publicaciones

A lo largo de su carrera ha publicado 619 artículos y 39 libros. Aquí una pequeña selección:

 

1957. Programación Dinámica1959. Comportamiento asintótico de las soluciones de las ecuaciones diferenciales1961. Introducción a las desigualdades1961. Control de Procesos Adaptativos: Un Tour guiado1962. Programación Dinámica Aplicada1967. Introducción a la Teoría Matemática de Control de Procesos1972. Programación Dinámica y Ecuaciones Diferenciales Parciales1982. Aspectos matemáticos de Programación y Aplicaciones1983. Métodos Matemáticos en Medicina1984. Ecuaciones Diferenciales Parciales1984. Ojo del huracán: publicación de una autobiografía, Mundo Científico.1985. Inteligencia Artificial1995. Ecuaciones Diferenciales Elementales modernas1997. Introducción a Análisis de matrices.

 

 

 

La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas, se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados.

Una subestructura óptima significa que se pueden usar soluciones óptimas de subproblemas para encontrar la solución óptima del problema en su conjunto. Por ejemplo, el camino más corto entre dos vértices se puede encontrar calculando primero el camino más corto al objetivo desde todos los vértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor camino de todos ellos.

 En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:

        1.     Dividir el problema en subproblemas más pequeños.

     2.   Resolver estos problemas de manera óptima usando        este proceso de tres pasos     recursivamente.

     3.    Usar estas soluciones óptimas para construir una solución óptima al problema original.

PROGRAMACION DINAMICA DETERMINISTICA

Ejercisios de programacion entera

PROBLEMAS

Problema 1

Se están considerando cuatro posibles inversiones. La primera de ellas se prevé que proporcione unos beneficios netos de

16.000 euros, la segunda, 22.000 euros, la tercera 12.000 euros, y la cuarta 8.000 euros. Cada una de las inversiones

requiere una cantidad de dinero en efectivo: 5.000, 7.000, 4.000 y 3.000 euros, respectivamente. Si solo se dispone de

14.000 euros para invertir. ¿Qué modelo de programación lineal entera permite obtener la combinación de inversiones que

prevea los máximos beneficios?

Solución

La declaración de variables enteras en OPL

del nombre de la variable y de la definición del rango de variación. El rango es

obligatorio y se compone de la palabra clave

se realiza con la palabra clave int seguidain seguida intervalo Variables de decisión

1 si se elige la inversión i

x i= 1 2 3 4

 

 

Modelo OPL

dvar int

x1 in 0..1;

del de variación:

extremo inferior

..extremo superior

Restricciones

i

0 si no se elije

1,2,3,4

 

dvar int x2 in 0..1;

dvar int

x3 in 0..1;

dvar int

x4 in 0..1;

maximize

16*x1+22*x2+12*x3+8*x4;

La suma de los costes de las inversiones no debe

rebasar la cantidad total disponible.

 

1 2 3 4

0,1 , 1, 2,3, 4

5 7 4 3 14i

x x x x

x i

   

 

Función objetivo

subject to

{

5*x1+7*x2+4*x3+3*x4 <= 14;

}

// solution (optimal) with objective 42

x1 = 0;

x2 = 1;

x3 = 1;

x4 = 1;

Hay que maximizar el beneficio total de todas las

inversiones

1 2 3 4

Maximizar z 16x  22x 12x  8x

Luego las inversiones segunda, tercera

y cuarta producen el máximo beneficio

Problema 2

Se desea ampliar una compañía con la instalación de una nueva factoría en Zaragoza o Sevilla o en ambas ciudades. También se piensa

construir a lo sumo un almacén en una ciudad donde se instale alguna factoría. En la siguiente tabla aparecen los beneficios estimados

de instalar una factoría y construir un almacén en Zaragoza y Sevilla, y el capital requerido para ello. Se dispone de un capital total para

la inversión de 39 M euros. El objetivo es tomar las decisiones que optimicen el beneficio de la inversión.

Decisiones Beneficio estimado Capital requerido

Instalar una factoría en Zaragoza 19 M euros 16 M euros

Instalar una factoría en Sevilla 15 M euros 13 M euros

Construir un almacén en Zaragoza 16 M euros 15 M euros

Construir un almacén en Sevilla 14 M euros 12 M euros



1 i l d i ió i í

Solución

Variables de decisión

1

I l f í S ill

x = Instalar una factoría en Zaragoza

dvar int

x1 in 0..1;

dvar int

x2 in 0..1;

dvar int

x3 in 0..1;

dvar int

x4 in 0..1;

Modelo OPL

i

si la decisión es sí

x =

0 si la decisión i es no



Restricciones

2

3

4

x = Instalar una factoría en Sevilla

x = Construir un almacén en Zaragoza

x = Construir un almacén en Sevilla

El de decisiones que se adopte no debe

maximize

19*x1+15*x2+16*x3+14*x4;

subject to

{

16*x1+13*x2+15*x3+12*x4 <= 29;

x3+x4

3 4

3 1

1 2 3 4

16 13 15 12 39

1

x x x x

x x

x x

   

 



conjunto rebasar el presupuesto de inversión disponible

Se debe construir a lo sumo un almacén

El almacén en Zaragoza sólo se puede construir si

se instala una factoría en Zaragoza

<= 1;

x3 <= x1;

x4 <= x2;

}

// solution (optimal) with objective 35

19 1 16 14

4 2

x  x

Función objetivo

El almacén en Sevilla sólo se puede construir si se

instala una factoría en Sevilla

Hay que maximizar el beneficio total de todas las

decisiones de inversión

x1 = 1;

x2 = 0;

x3 = 1;

x4 = 0;

Solución optima: construir una factoría

en Zaragoza y el almacén también en

Zaragoza, con un beneficio estimado de

35M euros.

1 2 3 4

 

Una compañía está considerando la fabricación de tres tipos nuevos de vehículos: T1, T2, y T3. Los recursos necesarios para su fabricación,

los recursos disponibles, y los beneficios esperados, para cada tipo de vehículo, se dan en la siguiente tabla:

Tipos T1 T2 T3 Disponibilidad

Material 1500 kilos 3000 kilos 5000 kilos 6000000 kilos

Trabajo 30 horas 25 horas 40 horas 60000 horas

Beneficios 2000 euros 3000 euros 4000 euros

La empresa quiere conocer qué tipo de vehículos debe fabricar y cuántos para maximizar los beneficios, teniendo en cuenta que un nuevo

modelo solo resulta económicamente viable si se fabrican al menos 1000 unidades.

Solución

d l ú d hí l d

Variables de decisión

,

i

i i

x número de vehículos a construir del tipo T i 1,2,3

y variable binaria auxiliar para expresar la disyunción

 



dvar float+

x1;

dvar float+

x2;

dvar float+

x3;

dvar int

y1 in 0..1;

dvar int

y2 in 0..1;

dvar int

y3 in 0..1;

Modelo OPL

Se podían haber

usado variables

int

2.400 es una cota del número de vehículos que se pueden

construir impuesta por las horas disponibles: 60.000/25 = 2.400 .

Los kilos disponibles imponen una cota menos restrictiva, 4.000

Restricciones

1 1

1 1

2400

1000 2400(1 )

2400

x y

x y

x y



  



maximize

2*x1+3*x2+4*x3;

subject to

{

x1 <= 2400 * y1;

1000 - x1 <= 2400 * (1 - y1);

x2 * y2;

Si

fabrican vehículos del tipo

y1 = 0 entonces x1 = 0, luego no seT1.

Igual ocurre para

i=2 y 3

Si

y1 = 1 entonces x1 >= 1000, luego se

2 2

2 2

3 3

3 3

1000 2400(1 )

2400

1000 2400(1 )

x y

x y

x y

  



  

<= 2400 1000 - x2 <= 2400 * (1 - y2);

x3 <= 2400 * y3;

1000 - x3 <= 2400 * (1 - y3);

1.5*x1+3*x2+5*x3 <= 6000;

30*x1+25*x2+40*x3 <= 60000;

}

Los kilos de material consumido no debe

sobrepasar disponibles

fabrican vehículos del tipo T

Igual ocurre para

1.i=2 y 3

Función de coste

1 2 3

1 2 3

1,5 3 5 6000

30 25 40 60000

x x x

x x x

  

  

// solution (optimal) with objective 6000

x1 = 0;

x2 = 2000;

x3 = 0;

y1 = 0;

Solución optima: construir 2000

hí l d ti T2

los kilos Las horas de trabajo consumidas no debe

sobrepasar los horas disponibles

Hay que maximizar el beneficio total

Problema 5

Maximizar Z 19x 15x 16x 14x

VARIABLE ENTERA

Max F(X) = 4x

1 + 3x2

s.a. 2x

3x

x

1 + x2 £ 21 + 4x2 £ 61 ³ 0 , x2 ³ 0 x1 , x2 Î {0,1}

(0,1) F=3

(1,0) F=4

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

EJERCICIO DE PROGRAMACION LINEAL ENTERA-BINARIA.

VARIABLES X1, X2, F;

*DECLARACION QUE LAS VARIABLES SON BINARIAS, 0-1.

BINARY

EQUATIONS OBJ, R1, R2;

OBJ.. F=E= 4*X1 + 3*X2;

R1.. 2*X1 + X2 =L= 2;

R2.. 3*X1 + 4*X2 =L= 6;

MODEL BIN01 /ALL/;

* PARA RESOLVER LOS PROBLEMAS ENTEROS HAY QUE USAR MIP

SOLVE BIN01 USING

VARIABLES X1, X2;MIP MAXIMIZING F;

La solución es:

Proven optimal solution.

MIP Solution : 4.000000 (1 iterations, 0 nodes)

Final LP : 4.000000 (0 iterations)

Best integer solution possible : 4.000000

Absolute gap : 0

Relative gap : 0

LOWER LEVEL UPPER MARGINAL

---- EQU OBJ . . . 1.000

---- EQU R1 -INF 2.000 2.000 .

---- EQU R2 -INF 3.000 6.000 .

LOWER LEVEL UPPER MARGINAL

---- VAR X1 . 1.000 1.000 4.000

---- VAR X2 . . 1.000 3.000

---- VAR F -INF 4.000 +INF .

**** REPORT SUMMARY : 0 NONOPT

0 INFEASIBLE

0 UNBOUNDED

Max F(X) = 8x

1 + 10x2

s.a. 4x

8x

x

1 + 6x2 £ 241 + 3x2 £ 241³0,x2³0, x1,x2ÎZ+

(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

(0,2) F=20 (1,2) F=28 (1,3) F=38

(0,3) F=30 (1,3) F=38

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

(0,4) F= 40

4x1+6x2 =24

8x1+3x2=24

F(x) = 8x1+10x2

* EJERCICIO DE PROGRAMACION LINEAL ENTERA

VARIABLES X1, X2, F;

*DECLARACION QUE LAS VARIABLES SON ENTERAS

INTEGER

EQUATIONS

OBJ, R1, R2;

OBJ.. F=E= 8*X1 + 10*X2;

R1.. 4*X1 + 6*X2 =L= 24;

R2.. 8*X1 + 3*X2 =L= 24;

MODEL ENT01 /ALL/;

SOLVE ENT01 USING

VARIABLES X1, X2;MIP MAXIMIZING F;

La solución es:

S O L V E S U M M A R Y

MODEL ENT01 OBJECTIVE F

TYPE MIP DIRECTION MAXIMIZE

SOLVER CPLEX FROM LINE 11

**** SOLVER STATUS 1 NORMAL COMPLETION

**** MODEL STATUS

8 INTEGER SOLUTION

**** OBJECTIVE VALUE

38.0000

RESOURCE USAGE, LIMIT 2.800 1000.000

ITERATION COUNT, LIMIT 4 10000

GAMS/Cplex Aug 7, 2000 WIN.CP.NA 19.4 016.015.038.WAT For Cplex 6.6

Cplex 6.6.1, GAMS Link 16, Using a GAMS/Cplex demo license installed at

runtime.

Solution satisfies tolerances

MIP Solution : 38.000000 (

Final LP : 38.000000 (0 iterations)

Best integer solution possible : 40.000000

Absolute gap : 2

Relative gap : 0.0526316

LOWER LEVEL UPPER MARGINAL

---- EQU OBJ . . . 1.000

---- EQU R1 -INF 22.000 24.000 .

---- EQU R2 -INF 17.000 24.000 .

LOWER LEVEL UPPER MARGINAL

---- VAR X1 . 1.000 100.000 8.000

---- VAR X2 . 3.000 100.000 10.000

---- VAR F -INF 38.000 +INF .

**** REPORT SUMMARY : 0 NONOPT

0 INFEASIBLE

0 UNBOUNDED

.4 iterations, 3 nodes)

Si observamos la solución que nos proporciona GAMS con el gráfico anterior,

podemos ver que la solución que ofrece GAMS no es la optima. Además GAMS ya nos

advierte que la solución es:

**** MODEL STATUS 8 INTEGER SOLUTION

Es decir, es solamente entera, pero no es optima. Fácilmente podemos advertir

que la solución optima es el punto (0,4) con una valor de 40.

Esto significa que GAMS no es capaz de encontrar la solución optima?. La

respuesta es

GAMS como todo programa de uso "profesional" incorpora la opción de

búsqueda de una solución "buena" en poco tiempo antes que la optima usando muchos

recursos, es decir, GAMS detiene el proceso de búsqueda en aquellas soluciones que

difieran menos de un 10 por ciento de la mejor solución.

NO.

Solution satisfies tolerances.

MIP Solution : 38.000000 (4 iterations, 3 nodes)

Final LP : 38.000000 (0 iterations)

Best integer solution possible : 40.000000

Absolute gap : 2

Relative gap : 0.0526316

Esto quiere decir que la mejor solución será 40, pero la solución actual (38)

difiere solamente un 5.26 por ciento (Relative gap) de la mejor solución. Como la

solución actual está dentro del margen de tolerancia, entonces GAMS detiene el

proceso.

Si se quiere encontrar el optimo, solamente hay que incorporar la opción de que

la tolerancia sea muy baja, por ejemplo un 0.00001 (0.001 por ciento).

Asi el fichero GMS será:

* EJERCICIO DE PROGRAMACION LINEAL ENTERA

*DECLARACION DE MARGEN DE TOLERANCIA

OPTION OPTCR=0.00001;

VARIABLES X1, X2, F;

*DECLARACION QUE LAS VARIABLES SON ENTERAS

INTEGER

EQUATIONS

OBJ, R1, R2;

OBJ.. F=E= 8*X1 + 10*X2;

R1.. 4*X1 + 6*X2 =L= 24;

R2.. 8*X1 + 3*X2 =L= 24;

MODEL ENT01 /ALL/;

SOLVE ENT01 USING

VARIABLES X1, X2;MIP MAXIMIZING F;

La solución que se obtiene es:

S O L V E S U M M A R Y

MODEL ENT01 OBJECTIVE F

TYPE MIP DIRECTION MAXIMIZE

SOLVER CPLEX FROM LINE 13

**** SOLVER STATUS 1 NORMAL COMPLETION

**** MODEL STATUS

1 OPTIMAL

**** OBJECTIVE VALUE 40.0000

RESOURCE USAGE, LIMIT 2.810 1000.000

ITERATION COUNT, LIMIT 5 10000

GAMS/Cplex Aug 7, 2000 WIN.CP.NA 19.4 016.015.038.WAT For Cplex 6.6

Cplex 6.6.1, GAMS Link 16, Using a GAMS/Cplex demo license installed at

runtime.

Proven optimal solution.

MIP Solution : 40.000000 (

Final LP : 40.000000 (0 iterations)

Best integer solution possible : 40.000000

Absolute gap : 0

Relative gap : 0

LOWER LEVEL UPPER MARGINAL

---- EQU OBJ . . . 1.000

---- EQU R1 -INF 24.000 24.000 2.000

---- EQU R2 -INF 12.000 24.000 .

LOWER LEVEL UPPER MARGINAL

---- VAR X1 . . 100.000 EPS

---- VAR X2 . 4.000 100.000 -2.000

---- VAR F -INF 40.000 +INF .

**** REPORT SUMMARY : 0 NONOPT

0 INFEASIBLE

0 UNBOUNDED

5 iterations, 3 nodes)

Como podemos observar ahora GAMS si que nos ha proporcionado la solución

optima, tal como indica el fichero LST

**** MODEL STATUS 1 OPTIMAL

En esta caso la diferencia está en que hace un mayor numero de iteraciones (4,

con la condición de tolerancia y 5, sin esa condición), es decir, un 20 por ciento más de

iteraciones.

No obstante las condiciones de "aceleración" y "desaceleración" son muchas y

de muy diferentes características, para ello puede verse el Manual del Usuario de

GAMS.

Ejemplo:

La empresa FERCA, S.A., se dedica al envasado de fertilizantes para el

suministro a sus clientes, debe determinar el plan de envasado de tres tipos de

fertilizantes (tipo 1, 2 y 3). Estos tipos de fertilizantes se envasan en cajas con peso

diferentes, a partir de tres componentes básicos (A, B y C). Los beneficios obtenidos

por cada tipo de fertilizante son de 25, 30 y 35 unidades monetarias, respectivamente.

Cada tipo de fertilizantes tiene una mezcla diferentes de componentes, así el tipo 1

requiere 10 kilos de componente A, 20 de la clase B y 18 de clase C. Para el tipo 2 los

requerimientos son de 13, 22 y 20 kilos de cada uno de los componentes, mientras que

para el tipo 3 los requerimientos son de 18, 20 y 24, respectivamente.

La empresa dispone en el almacén actualmente de 2324 kilos de componente A,

de 2550 de B y de 1568 de C.

Con estos datos determinar el numero de cajas de fertilizantes que la empresa

puede suministrar al mercado de forma que se maximice su beneficio.

El fichero GMS será el siguiente:

* FERCA, S.A.

VARIABLES X1, X2, X3, F;

INTEGER VARIABLES X1, X2, X3;

EQUATIONS

OBJ, R1, R2, R3;

OBJ.. F=E= 25*X1 + 30*X2 + 35*X3;

R1.. 10*X1 + 13*X2 + 18*X3 =L= 2324;

R2.. 20*X1 + 22*X2 + 20*X3 =L= 2550;

R3.. 18*X1 + 20*X2 + 24*X3 =L= 1568;

MODEL ENT11 /ALL/;

SOLVE ENT11 USING MIP MAXIMIZING F;

La solución que se obtiene es:

S O L V E S U M M A R Y

MODEL ENT11 OBJECTIVE F

TYPE MIP DIRECTION MAXIMIZE

SOLVER CPLEX FROM LINE 11

**** SOLVER STATUS 1 NORMAL COMPLETION

**** MODEL STATUS

8 INTEGER SOLUTION

**** OBJECTIVE VALUE 2340.0000

RESOURCE USAGE, LIMIT 2.690 1000.000

ITERATION COUNT, LIMIT 1 10000

GAMS/Cplex Aug 7, 2000 WIN.CP.NA 19.4 016.015.038.WAT For Cplex 6.6

Cplex 6.6.1, GAMS Link 16, Using a GAMS/Cplex demo license installed at

runtime.

Solution satisfies tolerances.

MIP Solution : 2340.000000 (

Final LP : 2340.000000 (0 iterations)

Best integer solution possible : 2351.111111

Absolute gap : 11.1111

Relative gap : 0.00474834

LOWER LEVEL UPPER MARGINAL

---- EQU OBJ . . . 1.000

---- EQU R1 -INF 1014.000 2324.000 .

---- EQU R2 -INF 1716.000 2550.000 .

---- EQU R3 -INF 1560.000 1568.000 .

LOWER LEVEL UPPER MARGINAL

---- VAR X1 . . 100.000 25.000

---- VAR X2 . 78.000 100.000 30.000

---- VAR X3 . . 100.000 35.000

---- VAR F -INF 2340.000 +INF .

**** REPORT SUMMARY : 0 NONOPT

0 INFEASIBLE

0 UNBOUNDED

1 iterations, 1 nodes)

El fichero de salida, ya nos advierte que la solución no es optima sino que

simplemente es entera con un máximo del 10 por ciento de diferencia respecto a la

mejor solución.

Para llegar a obtener la solución entera, debemos modificar la condición de

tolerancia, de forma que el fichero GMS será ahora:

* FERCA, S.A.

OPTION OPTCR = 0.00001;

VARIABLES X1, X2, X3, F;

INTEGER VARIABLES X1, X2, X3;

EQUATIONS

OBJ, R1, R2, R3;

OBJ.. F=E= 25*X1 + 30*X2 + 35*X3;

R1.. 10*X1 + 13*X2 + 18*X3 =L= 2324;

R2.. 20*X1 + 22*X2 + 20*X3 =L= 2550;

R3.. 18*X1 + 20*X2 + 24*X3 =L= 1568;

MODEL ENT12 /ALL/;

SOLVE ENT12 USING

MIP MAXIMIZING F;

La solución es :

S O L V E S U M M A R Y

MODEL ENT11 OBJECTIVE F

TYPE MIP DIRECTION MAXIMIZE

SOLVER CPLEX FROM LINE 12

**** SOLVER STATUS 1 NORMAL COMPLETION

**** MODEL STATUS

1 OPTIMAL

**** OBJECTIVE VALUE 2350.0000

RESOURCE USAGE, LIMIT 2.750 1000.000

ITERATION COUNT, LIMIT 4 10000

GAMS/Cplex Aug 7, 2000 WIN.CP.NA 19.4 016.015.038.WAT For Cplex 6.6

Cplex 6.6.1, GAMS Link 16, Using a GAMS/Cplex demo license installed at

runtime.

Proven optimal solution.

MIP Solution : 2350.000000 (

Final LP : 2350.000000 (0 iterations)

Best integer solution possible : 2350.000000

Absolute gap : 0

Relative gap : 0

LOWER LEVEL UPPER MARGINAL

---- EQU OBJ . . . 1.000

---- EQU R1 -INF 1024.000 2324.000 .

---- EQU R2 -INF 1712.000 2550.000 .

---- EQU R3 -INF 1568.000 1568.000 1.500

LOWER LEVEL UPPER MARGINAL

---- VAR X1 . . 100.000 -2.000

---- VAR X2 . 76.000 100.000 EPS

---- VAR X3 . 2.000 100.000 -1.000

---- VAR F -INF 2350.000 +INF .

**** REPORT SUMMARY : 0 NONOPT

0 INFEASIBLE

0 UNBOUNDED

4 iterations, 10 nodes)

Como puede observarse la solución es ahora optima, con un mejor valor de la

función objetivo.

Vamos a presentar un típico de programación entera(binaria) mixta, es decir, con

variables binarias y continuas:

con coste fijo.

problemas de localización de recursos o problemas

Este tipo de problemas vendría a representar una situación como la siguiente:

Consideremos un problema de distribución en que hay

estos clientes demandan se puede localizar o situar en

va a transportar el producto para satisfacer las demandas.

Supongamos que el cliente j tiene una demanda del producto que estima en

n clientes y que el producto quem almacenes desde los cuales sedj

unidades, y hay un coste asociado

localización del producto en el almacén

Además, hay un coste fijo

este es el caso, además cada almacén tiene unas disponibilidades de

problema que se plantea es: ¿Qué almacenes deben utilizar y que cantidad de producto

hay que enviar desde los almacenes a los clientes, de forma que se satisfaga la demanda

con un coste total mínimo?.

A la vista de la definición anterior del problema, deben ser dos los tipos de

variables a considerar. Por una parte, las correspondientes a las cantidades de producto

que hay que enviar desde los almacenes a los clientes que se indicaran como:

x

Estas variables se pueden considerar como variables continuas o enteras, según

las características del producto y del contexto del problema.

Por otra parte, debe considerarse la posibilidad de que se utilice o no un

determinado almacén

s

1 si se utiliza el almacen i

0 en otro caso

cij que incluye por unidad de producto, el coste dei y el envío del producto desde i al cliente j.Ci , que representa el coste de utilización del almacén i , siOi unidades. Elij = cantidad de producto enviada desde el almacén i al cliente j.i, de forma que definimos las variables:i =

ìíî

La función objetivo de este problema estará formada por dos sumandos, uno que

represente los costes de envío del almacén i al cliente j , y el otro sumando incorporará

los costes de utilización de los almacenes.

c

i = 1

m

j = 1

n

i = 1

m

ij x ij + Ci siå å å

Las restricciones serán:

a) La satisfacción de las demandas de los clientes. Consideraremos que se satisfacen

totalmente ( = ), aunque podemos sustituir esta restricción por (

x

i = 1

m

³ ):ij = d jå

b) Los envíos desde cada uno de los almacenes:

x s O

j = 1

n

ij i i

å

=

El significado de esta restricción lo podemos explicar que si la variables s

no será posible enviar productos desde ese almacén a cualquiera de los clientes, y en tal

caso x

i = 0,ij = 0

j = 1

n

å

y con ello x

j = 1

n

ij = 0. Sin embargo si si = 1, se verifica que x O ij i

å

=

para el almacén i, que son las disponibilidades de ese almacen..

En resumen, el modelo construido para este problema, es un programa de

programación entera mixta con variables binarias, y quedaría de la siguiente forma:

Min Z = c

i = 1

m

j = 1

n

i = 1

m

ij x ij + Ci siå å å

s.a:

x

i = 1

m

ij = d jå

j = 1, 2,..., n

x s O

j = 1

n

ij i i

å

x

s

Una variante de este problema, es cuando se pretende localizar un único almacén

con capacidad suficiente. En este caso la elección solo puede recaer un una variable

s

satisfacer el total de la demanda de los cliente. Con ello el problema seria casi idéntico

al anterior, con la salvedad que las oferta O

j = 1

n

= i = 1, 2,..., mij ³ 0 i = 1, 2,..., m j = 1, 2,..., ni Î { 0, 1 } i = 1, 2,..., mi =1, además debemos asegurar que el almacén elegido tenga la capacidad parai = d jå

Min Z = c

i = 1

m

j = 1

n

i = 1

m

ij x ij + Ci siå å å

s.a:

x

i = 1

m

ij = d jå

j = 1, 2,..., n

x s d

j = 1

n

j = 1

n

ij i j

å

x

s

Consideremos el siguiente ejemplo:

= å i = 1, 2,..., mij ³ 0 i = 1, 2,..., m j = 1, 2,..., ni Î { 0, 1 } i = 1, 2,..., m

Una empresa tiene que servir seis zonas comerciales, con un máximo de cuatro

fabricas. Las zonas comerciales y sus demandas (expresadas en unidades anuales de

producto) son las siguientes:

ZONA DEMANDA

CATALUNYA 480

NORTE 356

NOROESTE 251

LEVANTE 349

CENTRO 598

SUR 326

La empresa tiene en la actualidad dos fabricas en funcionamiento, una de ellas

esta situada en Barcelona y tiene una capacidad productiva de 500 unidades/año, la

segunda fabrica esta situada en Madrid y tiene una capacidad productiva de 700

unidades/año.

Las alternativas de inversión que se plantean en la empresa son las de ampliar

las dos fabricas existentes o bien construir nuevas plantas en Bilbao y/o Valencia. Los

costes variables de suministros cij, que comprenden tanto los costes de producción, de

transporte y los de distribución en las zonas de demanda son los siguientes:

Planta\Zona Cataluña Norte Noroeste Levante Centro Sur

Barcelona 10 62 110 35 62 100

Bilbao 62 10 63 63 40 83

Madrid 62 40 60 35 7 54

Valencia 35 63 96 10 35 67

Las diferentes fabricas tienen los costes anuales y los niveles de producción

siguientes:

CAPACIDAD AMPLIACIÓN COSTE

ACTUAL CAPACIDAD FIJO

BARNA 500 1000 100000

BILBAO 1000 100000

MADRID 700 1000 80000

VALENCIA 1000 100000

Cual ha de ser la decisión que tome la empresa de manera que se satisfagan las

demandas y el coste sea mínimo.

La modelización de este problema es muy similar a un problema de transporte,

excepto por la característica de incorporar la parte correspondiente al coste fijo de los

almacenes, así como las restricciones de producción y de capacidad máxima de cada

una de las plantas.

La construcción del fichero GMS con todas las variables (x y s) seria largo y

complicado, pero afortunadamente GAMS permite crear un fichero "casi" como se ha

escrito el modelo, simplemente definiendo previamente unos conjutnos de datos (SET,

PARAMETER, TABLE, etc.), como sigue:

$TITLE PROBLEMA DE LOCALIZACION

OPTION LIMROW=100;

OPTION LIMCOL =100;

OPTIONS OPTCR = 0.01;

SET

J ZONAS /CATAL, NORTE, NOROE, LEVAN, CENTR, SUR/

I FABRICAS /BARNA,BILBAO,MADRID,VALENC/

TABLE

CATAL NORTE NOROE LEVAN CENTR SUR

BARNA 10 62 110 35 62 100

BILBAO 62 10 63 63 40 86

MADRID 62 40 60 35 7 54

VALENC 35 63 96 10 35 67;

C(I,J) COSTES VARIABLES DE DISTRIBUCION Y TRANSPORTE

PARAMETER

/BARNA 100000

BILBAO 100000

MADRID 80000

VALENC 100000/;

F(I) COSTES FIJOS

PARAMETER

/CATAL 480

NORTE 356

NOROE 251

LEVAN 349

CENTR 598

SUR 326/;

D(J) DEMANDA DE LA ZONAS

PARAMETER

/BARNA 1000

BILBAO 1000

MADRID 1000

VALENC 1000/;

CA(I) CAPACIDAD DE LAS FABRICAS

PARAMETER

/BARNA 500

BILBAO 0

MADRID 700

VALENC 0/;

VARIABLES

FO

COFI

X(I,J)

Y(I);

POSITIVE VARIABLES X(I,J);

BINARY VARIABLES Y(I);

EQUATIONS

OBJ

COSTEFIJO

DEMANDA(J)

MAXPROD(I);

COSTEFIJO.. COFI =E= SUM(I, F(I)*Y(I));

OBJ.. FO =E= SUM((I,J), C(I,J)*X(I,J)) + COFI;

DEMANDA(J).. SUM(I,X(I,J)) =G= D(J);

MAXPROD(I).. SUM(J,X(I,J)) =L= CI(I) + (CA(I)*Y(I));

MODEL LOCALIZ /ALL/;

SOLVE LOCALIZ USING MIP MINIZING FO;

CI(I) CAPACIDAD INICIAL

DISPLAY

X.L,Y.L,DEMANDA.L, MAXPROD.L;

Vamos a observa en primer lugar las ecuaciones de este problema:

---- OBJ =E=

OBJ.. FO - COFI - 10*X(BARNA,CATAL) - 62*X(BARNA,NORTE) - 110*X(BARNA,NOROE)

- 35*X(BARNA,LEVAN) - 62*X(BARNA,CENTR) - 100*X(BARNA,SUR) -

62*X(BILBAO,CATAL) - 10*X(BILBAO,NORTE) - 63*X(BILBAO,NOROE) -

63*X(BILBAO,LEVAN) - 40*X(BILBAO,CENTR) - 86*X(BILBAO,SUR) -

62*X(MADRID,CATAL) - 40*X(MADRID,NORTE) - 60*X(MADRID,NOROE) -

35*X(MADRID,LEVAN) - 7*X(MADRID,CENTR) - 54*X(MADRID,SUR) - 35*X(VALENC,CATAL)

- 63*X(VALENC,NORTE) - 96*X(VALENC,NOROE) - 10*X(VALENC,LEVAN) -

35*X(VALENC,CENTR) - 67*X(VALENC,SUR) =E= 0 ; (LHS = 0)

---- COSTEFIJO =E=

COSTEFIJO.. COFI - 100000*Y(BARNA) - 100000*Y(BILBAO) - 80000*Y(MADRID) -

100000*Y(VALENC) =E= 0 ; (LHS = 0)

---- DEMANDA =G=

DEMANDA(CATAL).. X(BARNA,CATAL) + X(BILBAO,CATAL) + X(MADRID,CATAL)

+ X(VALENC,CATAL) =G= 480 ; (LHS = 0 ***)

DEMANDA(NORTE).. X(BARNA,NORTE) + X(BILBAO,NORTE) + X(MADRID,NORTE)

+ X(VALENC,NORTE) =G= 356 ; (LHS = 0 ***)

DEMANDA(NOROE).. X(BARNA,NOROE) + X(BILBAO,NOROE) + X(MADRID,NOROE)

+ X(VALENC,NOROE) =G= 251 ; (LHS = 0 ***)

DEMANDA(LEVAN).. X(BARNA,LEVAN) + X(BILBAO,LEVAN) + X(MADRID,LEVAN)

+ X(VALENC,LEVAN) =G= 349 ; (LHS = 0 ***)

DEMANDA(CENTR).. X(BARNA,CENTR) + X(BILBAO,CENTR) + X(MADRID,CENTR)

+ X(VALENC,CENTR) =G= 598 ; (LHS = 0 ***)

DEMANDA(SUR).. X(BARNA,SUR) + X(BILBAO,SUR) + X(MADRID,SUR) + X(VALENC,SUR)

=G= 326 ; (LHS = 0 ***)

---- MAXPROD =L=

MAXPROD(BARNA).. X(BARNA,CATAL) + X(BARNA,NORTE) + X(BARNA,NOROE)

+ X(BARNA,LEVAN) + X(BARNA,CENTR) + X(BARNA,SUR) - 1000*Y(BARNA) =L=

500 ; (LHS = 0)

MAXPROD(BILBAO).. X(BILBAO,CATAL) + X(BILBAO,NORTE) + X(BILBAO,NOROE)

+ X(BILBAO,LEVAN) + X(BILBAO,CENTR) + X(BILBAO,SUR) - 1000*Y(BILBAO)

=L= 0 ; (LHS = 0)

MAXPROD(MADRID).. X(MADRID,CATAL) + X(MADRID,NORTE) + X(MADRID,NOROE)

+ X(MADRID,LEVAN) + X(MADRID,CENTR) + X(MADRID,SUR) - 1000*Y(MADRID)

=L= 700 ; (LHS = 0)

MAXPROD(VALENC).. X(VALENC,CATAL) + X(VALENC,NORTE) + X(VALENC,NOROE)

+ X(VALENC,LEVAN) + X(VALENC,CENTR) + X(VALENC,SUR) - 1000*Y(VALENC)

=L= 0 ; (LHS = 0)

En las ecuaciones anteriores podemos observar el planteamiento formal de las

restricciones que afectan a cada una de las zonas y a cada una de las posibles

localizaciones.

Para obtener la solución de este problema usaremos solamente los resultados de

la opción DISPLAY. La solución a este problema es:

S O L V E S U M M A R Y

MODEL LOCALIZ OBJECTIVE FO

TYPE MIP DIRECTION MINIMIZE

SOLVER CPLEX FROM LINE 54

**** SOLVER STATUS 1 NORMAL COMPLETION

**** MODEL STATUS

1 OPTIMAL

**** OBJECTIVE VALUE 237425.0000

RESOURCE USAGE, LIMIT 2.800 1000.000

ITERATION COUNT, LIMIT 60 10000

GAMS/Cplex Aug 7, 2000 WIN.CP.NA 19.4 016.015.038.WAT For Cplex 6.6

Cplex 6.6.1, GAMS Link 16, Using a GAMS/Cplex demo license installed at

runtime.

Proven optimal solution.

MIP Solution : 237425.000000 (

Final LP : 237425.000000 (1 iterations)

Best integer solution possible : 237425.000000

Absolute gap : 0

Relative gap : 0

LOWER LEVEL UPPER MARGINAL

---- EQU OBJ . . . 1.000

---- EQU COSTEFIJO . . . 1.000

---- EQU DEMANDA

LOWER LEVEL UPPER MARGINAL

CATAL 480.000 480.000 +INF 10.000

NORTE 356.000 356.000 +INF 10.000

NOROE 251.000 251.000 +INF 60.000

LEVAN 349.000 349.000 +INF 35.000

CENTR 598.000 598.000 +INF 7.000

SUR 326.000 326.000 +INF 54.000

---- EQU MAXPROD

LOWER LEVEL UPPER MARGINAL

BARNA -INF 480.000 500.000 .

BILBAO -INF -644.000 . .

MADRID -INF 524.000 700.000 .

VALENC -INF . . -100.000

LOWER LEVEL UPPER MARGINAL

---- VAR FO -INF 2.3743E+5 +INF .

---- VAR COFI -INF 1.8000E+5 +INF .

---- VAR X

LOWER LEVEL UPPER MARGINAL

BARNA .CATAL . 480.000 +INF .

BARNA .NORTE . . +INF 52.000

BARNA .NOROE . . +INF 50.000

BARNA .LEVAN . . +INF EPS

BARNA .CENTR . . +INF 55.000

BARNA .SUR . . +INF 46.000

BILBAO.CATAL . . +INF 52.000

BILBAO.NORTE . 356.000 +INF .

BILBAO.NOROE . . +INF 3.000

BILBAO.LEVAN . . +INF 28.000

BILBAO.CENTR . . +INF 33.000

BILBAO.SUR . . +INF 32.000

MADRID.CATAL . . +INF 52.000

MADRID.NORTE . . +INF 30.000

MADRID.NOROE . 251.000 +INF .

MADRID.LEVAN . 349.000 +INF .

MADRID.CENTR . 598.000 +INF .

MADRID.SUR . 326.000 +INF .

VALENC.CATAL . . +INF 125.000

VALENC.NORTE . . +INF 153.000

VALENC.NOROE . . +INF 136.000

VALENC.LEVAN . . +INF 75.000

VALENC.CENTR . . +INF 128.000

VALENC.SUR . . +INF 113.000

---- VAR Y

LOWER LEVEL UPPER MARGINAL

BARNA . . 1.000 1.0000E+5

BILBAO . 1.000 1.000 1.0000E+5

MADRID . 1.000 1.000 80000.000

VALENC . . 1.000 EPS

**** REPORT SUMMARY : 0 NONOPT

0 INFEASIBLE

0 UNBOUNDED

E x e c u t i o n

60 iterations, 12 nodes)(DISPLAY)

---- 55 VARIABLE X.L

CATAL NORTE NOROE LEVAN CENTR SUR

BARNA 480.000

BILBAO 356.000

MADRID 251.000 349.000 598.000 326.000

---- 55 VARIABLE Y.L

BILBAO 1.000, MADRID 1.000

---- 55 EQUATION DEMANDA.L

CATAL 480.000, NORTE 356.000, NOROE 251.000, LEVAN 349.000

CENTR 598.000, SUR 326.000

---- 55 EQUATION MAXPROD.L

BARNA 480.000, BILBAO -644.000, MADRID 524.000

---- 55 VARIABLE FO.L = 237425.000

EXECUTION TIME = 0.220 SECONDS 1.4 Mb WIN194-116

La estrategia óptima es la de ampliar la planta de Madrid y construir una planta

en Bilbao. La nueva planta de Bilbao abastece a la zona Norte, mientras que la planta

actual de Barcelona abastece a Cataluña, y muy residualmente a Levante. El resto de la

demanda de la zona de Levante se abastece desde Madrid, así como a las restantes

zonas.