Introduccin a GLPK en

Optimizacin de Problemas de Produccin

Pedro Pieyro - Luis Stbile - Carlos Testuri
Colaboran: Hctor Cancela - Antonio Mauttone
Depto. Investigacin Operativa. Instituto de Computacin. Facultad de Ingeniera, UdelaR

2015

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

1 / 41

GNU Linear Programming Kit (GLPK)

Paquete informtico para la resolucin de problemas de programacin

lineal (LP) y programacin lineal entera mixta (MIP)
Ofrece un lenguaje de modelado algebraico (GMPL: GNU Math
Programming Language)

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

2 / 41

Problemas en GMPL

Los problemas se escriben en un archivo de texto plano utilizando los

elementos del lenguaje
Descripcin del modelo: Formado por una secuencia de sentencias
Datos del modelo: Formado por una secuencia de bloques de datos

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

3 / 41

Descripcin del modelo (Sentencias)

Las sentencias son la la unidad bsica del lenguaje

Toda sentencia finaliza con un punto y coma (;)
Sentencias Declarativas: Sirven para definir objetos del modelo
Sentencias Funcionales: Para realizar acciones especficas
(No las veremos en el curso)

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

4 / 41

Descripcin del modelo (Objetos)

Es definido mediante un nombre simblico que lo identifica

Los objetos pueden ser: escalares o N-dimensionados (N 1)
Objetos Escalares: Los referenciamos por medio del nombre; por
ejemplo t
Objetos Vectoriales: Los referenciamos por medio del nombre y un
subndice entre corchetes; por ejemplo: nutriente[i]
Objetos N-Dimensionados: Los referenciamos por medio del nombre y
N subndices entre corchetes; por ejemplo para N=2 (matriz),
contenido[i,j]

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

5 / 41

Descripcin del modelo (Conjuntos, Parmetros y Variables)

Los conjuntos definen el dominio de los ndices utilizados en el modelo

Los parmetros representan datos de la realidad
Las variables representan magnitudes que estn bajo el control de quin
toma las decisiones
Definicin y Sintxis
Conjuntos
set nombre;
Parmetros
param nombre dominio;
Variables de Decisin
var nombre dominio expresin;

Ejemplo
set alimento;
param precio{i in alimento};
var x{i in alimento} >= 0;

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

6 / 41

Descripcin del modelo (Restricciones)

Las restricciones representan exigencias que debe cumplir la solucin

que buscamos
Definicin y Sintxis
Restricciones
s.t. nombre dominio : expresin = expresin;
s.t. nombre dominio : expresin < expresin;
s.t. nombre dominio : expresin > expresin;
s.t. nombre dominio : expresin expresin;
s.t. nombre dominio : expresin expresin;
Ejemplo
s.t. demanda{j in nutriente} :
sum{i in alimento} x[i] * contenido[i,j] >= requisito[j];

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

7 / 41

Descripcin del modelo (Funcin Objetivo)

La funcin objetivo representa la expresin que queremos optimizar

Definicin y Sintxis
Funcin Objetivo
maximize nombre dominio :
expresin;
minimize nombre dominio :
expresin;

Ejemplo

minimize costo :
sum{i in alimento} precio[i] * x[i];

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

8 / 41

Descripcin del modelo (Comentarios)

Es una construccin muy til al momento de documentar nuestros

modelos
Sirven para hacer anotaciones legibles
Estas anotaciones son ignoradas por el intrprete que procesa el modelo
Comentarios de lnea: El caracter numeral (#) comenta todo lo que se
encuentre a su derecha
Comentarios de bloque: La secuencia barra asterisco (/*) comenta todo
lo que se encuentra entre los caracteres /* y */.

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

9 / 41

Datos del modelo

La primera forma de proporcionarle datos al modelo es por medio del

operador de asignacin := (dos puntos igual) en la declaracin
(definicin) del objeto. Por ejemplo:
set alimento := Leche Carne Arroz Papa Tomate;
La segunda es por medio de bloques de datos en la seccin de datos del
modelo

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

10 / 41

Datos del modelo (Seccin de datos)

La seccin de datos del modelo puede estar definida en el mismo archivo

que la descripcin del modelo, luego de la sentencia data;
En esta seccin las expresiones no estn permitidas
Por medio de bloques de datos se asignan valores a los Conjuntos y a
los Parmetros
sentencia;
. . .
sentencia;
data;
bloque de datos;
. . .
bloque de datos;
end;

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

11 / 41

Datos del modelo (Seccin de datos) (2)

Aunque por lo general vamos a querer tener los datos del modelo en un
archivo diferente, de modo de poder instanciar un mismo modelo con
distintos juegos de datos
sentencia;
sentencia;
. . .
sentencia;
end;

data;
bloque de datos;
bloque de datos;
. . .
bloque de datos;
end;

Archivo del modelo

Archivo de datos

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

12 / 41

Datos del modelo (Bloques de datos)

Bloque de datos
Ejemplo
Conjuntos
set nombre := t1 , . . . ,tn ;
set alimento := Leche Carne Arroz Papa Tomate;
Parmetros (Escalar)
param nombre := v;
param T := 4;
Parmetros (Vector)
param nombre := t1 , v1 ,
param precio := Leche 24
t2 , v 2 ,
Carne 190
...
Arroz 32
tn1 , vn1 ,
Papa 25
tn , v n ;
Tomate 50;

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

13 / 41

Datos del modelo (Bloques de datos)

Bloque de datos
Parmetros (Matriz)
param nombre : c1
r1 a11
r2 a21
. . .
rm am1
Ejemplo
Parmetros (Matriz)
param contenido
:
Leche
Carne
Arroz
Papa
Tomate

c2
a12
a22
. . .
am2

...
cn :=
. . . a1n
. . . a2n
. . .
. . . amn ;

Gr Pr Ca :=
20 34 49
250 180 0
2,5 67 780
1
21 170
2
11 47;

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

14 / 41

Problema de la dieta
El problema trata de la seleccin de alimentos que satisfacen requisitos
nutricionales a costo mnimo. Dado un conjunto de alimentos, con su
informacin nutricional y precio, el objetivo es seleccionar las cantidades de
alimentos a adquirir de forma de minimizar el costo de la dieta, mientras se
cumple con requisitos nutricionales. Estos requisitos se establecen como cotas
mnimas de algunos componentes nutricionales.
Cuadro: Contenido de nutrientes y precios por alimento

Alimento
Leche (L)
Carne (Kg)
Arroz (Kg)
Papa (Kg)
Tomate (Kg)
Requisitos (/da)

Grasas(g)
20
250
2.5
1
2
60

Protenas(g)
34
180
67
21
11
120

Carbohidratos(g)
49
0
780
170
47
280

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

Precio($)
24
190
32
25
50

2015

15 / 41

Problema de la dieta (Formulacin)

El objetivo es determinar la cantidad diaria de cada alimento a adquirir

mediante las variables xL , xC , xA , xP , xT .
Para cada nutriente existe una restriccin de cantidad mnima.

min 24xL + 190xC + 32xA + 25xP + 50xT

s.a.
20xL + 250xC + 2,5xA + xP + 2xT 60,
(Grasas)

34xL + 180xC + 67xA + 21xP + 11xT 120, (Proteinas)

49xL + 780xA + 170xP + 47xT 280,

(Carbohidratos)

xL , xC , xA , xP , xT 0.

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

16 / 41

Implementacin del Problema de la dieta (Conjuntos y Parmetros)

1
2

# PROBLEMA DE LA DIETA
#

3
4
5

set alimento ;
/ Alimentos /

6
7
8

10

11

set nutriente ;
/ Nutrientes /

param p r e c i o { i i n a l i m e n t o } ;
/ Precio por alimento /

12

13

14

param r e q u i s i t o { j i n n u t r i e n t e } ;
/ Requisitos n u t r i c i o n a l e s d i a r i o s /

15

16

17

param c o n t e n i d o { i i n a l i m e n t o , j i n n u t r i e n t e } ;
/ Contenido n u t r i c i o n a l j por alimento i /

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

17 / 41

19

20

22

23

25

26

Implementacin del Problema de la dieta (Variables, restricciones y

objetivo)

v a r x { i i n a l i m e n t o } >= 0 ;
/ Cantidades a ser adquiridas /

m i n i m i z e c o s t : sum{ i i n a l i m e n t o } p r e c i o [ i ] x [ i ] ;
/ C o s t o minimo /

s . t . demanda { j i n n u t r i e n t e } : sum{ i i n a l i m e n t o } x [ i ]
c o n t e n i d o [ i , j ] >= r e q u i s i t o [ j ] ;
/ Satisfaga los r e q u i s i t o s d i a r i o s para el n u t r i e n t e i /

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

18 / 41

28

Implementacin del Problema de la dieta (Bloques de datos)

data ;

29

30

s e t a l i m e n t o : = Leche C a r n e A r r o z Papa Tomate ;

31

32

s e t n u t r i e n t e := Grasas P r o t e i n a s Carbohidratos ;

33

34

35

36

37

38

param p r e c i o : = Leche
Carne
Arroz
Papa
Tomate

24 / ( $ p o r l i t r o ) /
190 / ( $ p o r Kg ) /
32 / ( $ p o r Kg ) /
25 / ( $ p o r Kg ) /
5 0 ; / ( $ p o r Kg ) /

39

40

41

42

param r e q u i s i t o : = G r a s a s
60
/ ( g d i a r i o s ) /
Proteinas
120 / ( g d i a r i o s ) /
Carbohidratos 280; / ( g d i a r i o s ) /

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

19 / 41

44

45

46

47

48

49

50

51

Implementacin del Problema de la dieta (Bloques de datos) (2)

param c o n t e n i d o :
Grasas P r o t e i n a s Carbohidratos :=
#
(g)
(g)
(g)
Leche
20
34
49
C a r n e 250
180
0
Arroz 2.5
67
780
Papa
1
21
170
Tomate
2
11
47;
end ;

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

20 / 41

Resolucin

El programa glpsol es ejecutado desde la lnea de comandos. Para indicarle al

intrprete que el archivo de entrada corresponde a una descripcin de un
modelo, utilizamos la opcin model. Por medio de la opcin output indicamos
el archivo en donde se almacenar el resultado. Las opciones son antecedidas
por dos guiones o signo de menos.
C:\> glpsol --model [Link] --output [Link]

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

21 / 41

Interpretacin de los resultados (Informacin sobre el problema)

Problem:
Rows:
Columns:
Non-zeros:
Status:
Objective:

dieta
4
5
19
OPTIMAL
cost = 80.3187251 (MINimum)

El solver ha encontrado un valor ptimo (mnimo en este caso) al problema

dieta y vale $ 80.31.

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

22 / 41

Interpretacin de los resultados

(Informacin sobre el estado de la funcin objetivo y las restricciones)

No.
Row name
St
Activity
Lower bound
Upper bound
Marginal
------ ------------ -- ------------- ------------- ------------- ------------1 cost
B
80.3187
2 demanda[Grasas]
NL
60
60
0.414343
3 demanda[Proteinas]
NL
120
120
0.462151
4 demanda[Carbohidratos]
B
368.988
280

Analizando la tabla vemos que el estado (Columna St) de los requisitos

nutricionales en Grasas esta acotado inferiormente (NL). Su valor marginal
(valor dual o precio sombra) vale $ 0.4143 por lo que si la restriccin fuera
relajada, la funcin objetivo mejorara ese valor. Con los requisitos de
Protenas sucede algo similar. Sin embargo los requisitos nutricionales en
Carbohidratos no estn acotados (St es B) por lo que la restriccin esta
inactiva. Relajarla no mejorar el valor objetivo. Su valor dual es 0.
Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin
Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

23 / 41

Interpretacin de los resultados (Informacin de la solucin)

No.
-----1
2
3
4
5

Column name
-----------x[Leche]
x[Carne]
x[Arroz]
x[Papa]
x[Tomate]

St
Activity
Lower bound
Upper bound
Marginal
-- ------------- ------------- ------------- ------------B
2.96414
0
NL
0
0
3.22709
B
0.286853
0
NL
0
0
14.8805
NL
0
0
44.0876

Vemos en la columna Activity la solucin ptima del problema. Las que

presentan estado B son las variables bsicas. La solucin es entonces Leche =
2.96414 litros y Arroz 0.286853 Kg. Deberamos adquirir esas cantidades
diriamente para minimizar los costos y cumplir con los requisitos
nutricionales. La columna Marginal indica los costos reducidos de las
variables no bsicas por lo que podemos deducir fcilmente que se ha
alcanzado el mnimo.

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

24 / 41

Problema de distribucin

El objetivo es encontrar un programa de envos de menor costo que satisfaga

los requerimientos del mercado y los suministros de las plantas. Supongamos
que contamos con tres plantas de productos enlatados ubicados en en Portland
(Maine), Seattle y San Diego. Las plantas pueden llenar 250, 500 y 750 latas
de conserva por da, respectivamente. El distribuidor opera con cinco
almacenes ubicados en New York, Chicago, Topeka (Kansas City), Dallas y
San Francisco. Cada uno de los almacenes puede vender 300 latas
diariamente. El distribuidor desea determinar el nmero de latas de conserva a
ser entregadas de las tres plantas a los cincos almacenes de modo que cada
almacen debera obtener tantas latas como pueda vender diariamente a costo
de transporte mnimo.

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

25 / 41

Problema de distribucin (2)

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

26 / 41

Problema de distribucin (3)

Para simplificar el modelo vamos a suponer que contamos con dos plantas
(Seattle y San Diego) y tres almacenes (New York, Chicago y Topeka).
En el cuadro mostramos los costos de envo (en dlares americanos) por
unidad desde las plantas a los almacenes.
Cuadro: Costos de distribucin (dlares por lata)

Almacenes
Plantas
Seattle
San Diego

New York

Chicago

Topeka

2.5
2.5

1.7
1.8

1.8
1.4

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

27 / 41

Problema de distribucin (Decisiones y objetivo)

Decisiones:
xSeattleNew York
xSeattleChicago
xSeattleTopeka
xSan DiegoNew York
xSan DiegoChicago
xSan DiegoTopeka
Objetivo:
min

Cantidad de latas de Seattle a New York

Cantidad de latas de Seattle a Chicago
Cantidad de latas de Seattle a Topeka
Cantidad de latas de San Diego a New York
Cantidad de latas de San Diego a Chicago
Cantidad de latas de San Diego a Topeka

transporte[i, j] x[i, j]

i{Seattle,SanDiego} j{NewYork,Chicago,Topeka}

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

28 / 41

Problema de distribucin (Restricciones)

Para cada planta, la cantidad de conservas distribuidas debe ser menor o

igual a la cantidad producida.
xSeattleNew York + xSeattleChicago + xSeattleTopeka
500
xSan DiegoNew York + xSan DiegoChicago + xSan DiegoTopeka 750
Debemos satisfacer la demanda de los almacenes.
xSeattleNew York + xSan DiegoNew York 300
xSeattleChicago + xSan DiegoChicago
300
xSeattleTopeka + xSan DiegoTopeka
300
No negatividad de las variables de decisin:
xSeattleNew York 0, xSeattleChicago 0, xSeattleTopeka 0,
xSan DiegoNew York 0, xSan DiegoChicago 0, xSan DiegoTopeka 0

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

29 / 41

Problema de distribucin (Formulacin)

P
P

min

i{Seattle,SanDiego}
j{NewYork,Chicago,Topeka} transporte[i, j] x[i, j]

s.a.
x
500

Pj{New York,Chicago,Topeka} Seattlej

x
750

Pj{New York,Chicago,Topeka} San Diegoj

x

300
Pi{Seattle,San Diego} iNew York

x
300

Pi{Seattle,San Diego} iChicago

i{Seattle,San Diego} xiTopeka 300

xi,j 0 con i {Seattle, San Diego} y j {New York, Chicago, Topeka}

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

30 / 41

Implementacin del Problema de distribucin (Conjuntos y Parmetros)

1
2

# PROBLEMA DE TRANSPORTE
#

3
4
5

set planta ;
/ Plantas /

6
7
8

10

11

s e t almacen ;
/ Almacenes /

param c a p a c i d a d { i i n p l a n t a } ;
/ C a p a c i d a d de l a p l a n t a i /

12

13

14

param demand { j i n a l m a c e n } ;
/ Demanda d e l mercado j /

15

16

17

param t r a n s p o r t e { i i n p l a n t a , j i n a l m a c e n } ;
/ C o s t o de t r a n s p o r t e p o r l a t a de c o n s e r v a /

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

31 / 41

19

20

22

23

25

26

Implementacin del Problema de distribucin (Variables, restricciones y

objetivo)
v a r x { i i n p l a n t a , j i n a l m a c e n } >= 0 ;
/ Cantidades a ser d i s t r i b u i d a s /

m i n i m i z e c o s t : sum{ i i n p l a n t a , j i n a l m a c e n } t r a n s p o r t e [ i , j ]
x[ i , j ];
/ C o s t o s t o t a l e s de t r a n s p o r t e /

s . t . s u p p l y { i i n p l a n t a } : sum{ j i n a l m a c e n } x [ i , j ] <= c a p a c i d a d
[ i ];
/ S u j e t o a l o s l i m i t e s de l a p l a n t a i /

27

28

29

s . t . demand { j i n a l m a c e n } : sum{ i i n p l a n t a } x [ i , j ] >= demanda [ j

];
/ S a t i s f a g a l a demanda d e l mercado j /

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

32 / 41

31

Implementacin del Problema de distribucin (Bloques de datos)

data ;

32

33

s e t p l a n t a : = S e a t t l e SanDiego ;

34

35

s e t a l m a c e n : = NewYork C h i c a g o Topeka ;

36

37

38

param c a p a c i d a d : = S e a t t l e
SanDiego

500
750;

39

40

41

42

param demand : = NewYork

Chicago
Topeka

300
300
300;

43

44

45

46

param t r a n s p o r t e :
NewYork
Seattle
2.5
SanDiego
2.5

Chicago
1.7
1.8

Topeka : =
1.8
1.4 ;

47

48

end ;

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

33 / 41

Interpretacin de los resultados

(Informacin sobre el estado de la funcin objetivo y las restricciones)

No.
Row name
St
Activity
Lower bound
Upper bound
Marginal
------ ------------ -- ------------- ------------- ------------- ------------1 cost
B
1680
2 supply[Seattle]
NU
500
500
< eps
3 supply[San-Diego]
B
400
750
4 demand[New-York]
NL
300
300
2.5
5 demand[Chicago]
NL
300
300
1.7
6 demand[Topeka]
NL
300
300
1.4

Si bien la restriccin supply[Seattle] acota la funcin objetivo superiormente,

el valor marginal esta muy prximo a 0 (, con  0).
Por otro lado, las restricciones de mercado nos indican que si pudieramos
elegir un mercado para reducir su demanda (relajar la restriccin), nos
convendra elegir el de New York, dado que cada unidad decrementara los
costos 2.5 puntos en el valor ptimo.
Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin
Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

34 / 41

Interpretacin de los resultados (Informacin de la solucin)

No. Column name St

Activity
Lower bound
Upper bound
Marginal
------ ------------ -- ------------- ------------- ------------- ------------1 x[Seattle,New-York]
B
200
0
2 x[Seattle,Chicago]
B
300
0
3 x[Seattle,Topeka]
NL
0
0
0.4
4 x[San-Diego,New-York]
B
100
0
5 x[San-Diego,Chicago]
NL
0
0
0.1
6 x[San-Diego,Topeka]
B
300
0

Analizando la segunda tabla vemos que el programa de envo de menor costo

es aquel que enva desde Seattle 200 latas a New York, y 300 a Chicago; y
desde San Diego 100 a New York y 300 a Topeka cumpliendo los lmites de
las plantas y las demandas de los mercados. A su vez indica que enviar latas
desde Seattle a Topeka o de San Diego a Chicago aumenta el costo por lata en
dlares en 0.4 y 0.1 unidades respectivamente.
Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin
Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

35 / 41

Problema de determinacin de lotes no capacitada

El problema de determinacin de lotes no capacitada puede ser descrito como

sigue. Hay un horizonte de n perodos donde, para cada perodo t
(t {1, . . . , n}), hay costos fijos de produccin (ft ), costos unitarios de
produccin (pt ), una demanada a satisfacer (dt 0) y costos de depsito ht
para el almacenamiento de la produccin no vendida al finalizar cada uno de
los perodos.

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

36 / 41

Problema de determinacin de lotes no capacitada (Decisiones y objetivo)

Variables de Decisin
xt es la cantidad producida en el perodo t,
st es el inventario al final del perodo t,
yt = 1 si se produce en el perodo t, yt = 0 en otro caso.
Restricciones
equilibrio de inventario segn perodos:
st1 + xt = dt + st , t = 1, . . . , n,
s0 = 0
,
activacin de produccin
Dado que no hay una cota de produccin se asume un valor grande M
para la activacin de los costos fijos
xt Myt , t = 1, . . . , n,
Funcin Objetivo
minimizar

Pn

t=1 (pt xt

+ ht st + ft yt )

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

37 / 41

Problema de determinacin de lotes no capacitada (Formulacin)

Pn

min

t=1 (pt xt + ht st + ft yt )

s.a.
s

t1 + xt = dt + st , t = 1, . . . , n

xt Myt , t = 1, . . . , n

s0 = 0,

xt 0, t = 1, . . . , n

st 0, t = 1, . . . , n

yt {0, 1}, t = 1, . . . , n

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

38 / 41

Implementacin del Problema de determinacin de lotes no capacitada

(Conjuntos y Parmetros)
1
2

# PROBLEMA DE DETERMINACION DE LOTES NO CAPACITADA

#

3
4
5

set periodo ;
/ Periodos /

6
7

param M;

8
9

10

param f { i i n p e r i o d o } ;
/ C o s t o f i j o de p r o d u c i r en e l p e r i o d o t /

11

12

13

param p { i i n p e r i o d o } ;
/ C o s t o u n i t a r i o de p r o d u c c i o n en e l p e r i o d o t , /

14

15

16

param h { i i n p e r i o d o } ;
/ c o s t o u n i t a r i o de a l m a c e n a m i e n t o en e l p e r i o d o t /

17

18

19

param d { i i n p e r i o d o } ;
/ demanda en e l p e r i o d o t /

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

39 / 41

21

22

Implementacin del Problema de determinacin de lotes no capacitada

(Variables y objetivo)

v a r x { i i n p e r i o d o } >= 0 ;
/ C a n t i d a d e s a p r o d u c i r s e en e l p e r i o d o t /

23

24

25

v a r s { i i n ( p e r i o d o u n i o n { 0 } ) } >= 0 ;
/ i n v en t a r io al f i n a l del periodo t /

26

27

28

30

31

var y{ i in p e r i o d o } , b i n a r y ;
/ 1 s i s e p r o d u c e en e l p e r i o d o t , 0 en o t r o c a s o /

m i n i m i z e c o s t o : sum{ i i n p e r i o d o } p [ i ] x [ i ] + h [ i ] s [ i ] +
f [ i ] y[ i ];
/ C o s t o minimo /

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

40 / 41

33

34

Implementacin del Problema de determinacin de lotes no capacitada

(Restricciones)

s . t . e q u i l i b r o { i i n p e r i o d o } : s [ i 1] + x [ i ] = d [ i ] + s [ i ] ;
/ E q u i l i b r i o de i n v e n t a r i o /

35

36

37

s . t . a c t i v { i i n p e r i o d o } : x [ i ] <= M y [ i ] ;
/ A c t i v a c i o n de l a p r o d u c c i o n /

38

39

40

s . t . i n i c i a l : s [0] = 0;
/ Inventario i n i c i a l /

Facultad de Ingeniera. UdelaR (Depto. Investigacin Optimizacin

Operativa. Instituto
de Problemas
de Computacin.
de Produccin
Facultad de Ingeniera)

2015

41 / 41