Date post: | 04-Jun-2018 |
Category: |
Documents |
Upload: | guillermo-nevado-rojas |
View: | 217 times |
Download: | 0 times |
of 67
8/13/2019 Casos de Estudio de Programacin Lineal
1/67
Casos de Estudio
Universidad de los Andes-CODENSA
8/13/2019 Casos de Estudio de Programacin Lineal
2/67
Programacin Lineal
8/13/2019 Casos de Estudio de Programacin Lineal
3/67
Problema del Transporteroblema del TransporteCierto producto debe enviarse en determinadas cantidades u1,,um,desde cada
, 1,, n, .
Determine las cantidades xij, que deben enviarse desde el origen ial destinoj, paraconseguir minimizar el coste de envo.
1. Datos
m:el nmero de orgenes
n:el nmero de destinos
ui:la cantidad que debe enviarse desde el origen i
cij:el coste de envo de una cantidad de producto desde el origen ial destinoj
2. Variables
xij: la cantidad que se enva desde el origen i al destino j. Se supone que las
variables deben ser no negativas.
8/13/2019 Casos de Estudio de Programacin Lineal
4/67
(1)n1,...,jm;1,...,i;0 ==ijx
.
(2)
=
==
m
n
1jiij m1,...,i;ux
El primer conjunto de condiciones indica que la cantidad del producto que parte
del origen idebe coincidir con la suma de las cantidades que parten de ese origen
=1ijij ,...,
hasta los distintos destinosj=1,,n.
El segundo conjunto de condiciones asegura que el total recibido en el destino j
debe corresponder a la suma de todas las cantidades que llegan a ese destino y
parten de los distintos orgenes i=1,,m.
Los grupos de restricciones presentados en (1)y (2)muestran las restricciones de
las variables y del problema, respectivamente.
4. Funcin a maximizar
En el problema de transporte nos interesa minimizar los costos de envo (suma de
los costos de trans orte de todas las unidades). Es decir, se debe minimizar:
(3)
= ==
m
i
n
j ijijxcZ
1 1
8/13/2019 Casos de Estudio de Programacin Lineal
5/67
Ejemplo El Problema del Transporte:
=,orgenes, n=3 destinos, u1=2, u2=3, u3=4, v1=5, v2=2, v3=2.
Figura 1.Esquema del problema de transporte.
2000000111
13
12
11
x
x
x
=
=
2
5
4
010010010
001001001
111000000
23
22
21
x
xx
CX
2100100100
33
32
31
x
x
x
1,2,3ji,;0 =ijx
8/13/2019 Casos de Estudio de Programacin Lineal
6/67
Las tres primeras ecuaciones establecen la conservacin del producto en los tres
or enes las tres ltimas i ualdades, la conservacin del roducto en los tresdestinos.
Si se concretan los valores particulares:
=
123212c
Para los costos de envo, el problema consiste en minimizar:
El mnimo de la funcin ob etivo es 14 ue corres onde a:
333231232221131211 232232 xxxxxxxxxZ ++++++++=
= 021
002
X
8/13/2019 Casos de Estudio de Programacin Lineal
7/67
Problema de la Planificacin de laP d iroduccin
Un productor fabrica una pieza, cuya demanda vara en el tiempo, de acuerdo con
.
Figura 2.Grfico de la demanda en funcin del tiempo.
pro uctor e e aten er a eman a mensua s empre. n genera cua qu er
problema de planificacin admitir diversas posibilidades que aseguren que la
demanda es convenientemente atendida:
8/13/2019 Casos de Estudio de Programacin Lineal
8/67
a) Produccin variable:El fabricante puede producir cada mes el nmero
exacto de unidades ue le solicitan.
b) Produccin Constante:El fabricante que debe atender una demanda que
de baja demanda y almacenar la sobreproduccin para los periodos dedemanda mayor.
Los problemas de esta naturaleza ilustran las dificultades que surgen cuando
objetivos contrarios estn presentes en e un sistema dado.
1. Datos
n:el nmero de meses a considerar
s0:la cantidad almacenada disponible al principio del periodo considerado
dt:el nmero de unidades (demanda) que se solicita en el mes t
s : a capac a m x ma e a macenam en o
at:el precio de venta en el mes t
8/13/2019 Casos de Estudio de Programacin Lineal
9/67
bt:el costo de produccin en el mes t
t
2. Variables
xt:el nmero de unidades producidas en el mes t
st:el nmero de unidades almacenadas en el mes t
3. Restricciones
1 ; 1,2,...,t t t t s x d s t n + = =max ; 1,2,...,
, 0
t
t t
s s t n
s x
=
La demanda dt en el mes t debe coincidir con el cambio en el almacenamiento ,
st-1st, ms la produccin xten el mes t; la capacidad de almacenamiento no puede
t, t, tnegativas.
8/13/2019 Casos de Estudio de Programacin Lineal
10/67
4. Funcin a Optimizar
de la variacin de la produccin y los inventarios.
( )n
t t t t t t Z a d b x c s=
Otra posibilidad consiste en minimizar los costos de almacenamiento:
1t=
n
1t t
t
c s=
=
8/13/2019 Casos de Estudio de Programacin Lineal
11/67
Ejemplo El Problema de la Planificacin de la Produccin:
tabla:
Tabla 1.Demanda en funcin del tiempo.
Supngase que la cantidad almacenada inicialmente es s0=2. Entonces el sistema se
transforma en:
1
2
31 0 0 0 1 0 0 0 0
s
s
s
4
1
1 1 0 0 0 1 0 0 3; , ; 1,2,3,4
0 1 1 0 0 0 1 0 6
0 0 1 1 0 0 0 1 1
sCx st xt o t
x
x
= = =
3
4
x
x
8/13/2019 Casos de Estudio de Programacin Lineal
12/67
Donde el cero en la matriz de la derecha procede a restar la demanda para t=1del
almacenamiento inicial.Si se maximiza el beneficio despus de descontar los costos y los inventarios, y se
toma at=3, bt=1, ct=1, el problema de optimizacin se convierte en:
Maximizar 1 2 3 4 1 2 3 436Z x x x x s s s s=
Sujeto a las restricciones ya mencionadas.
Resolviendo este roblema encontramos ue el valor mximo es:
1 2 3 4 1 2 3 426 para ( , , , , , , , ) (0,0,0,0,0,3,6,1)TZ x s s s s x x x x= = =
Lo que implica ningn almacenamiento.
8/13/2019 Casos de Estudio de Programacin Lineal
13/67
Problema de la Dietaroblema de la DietaSe conocen los contenidos nutritivos de ciertos alimentos, sus precios y la cantidad
.
cantidad de cada alimento que debe comprarse para satisfacer los mnimosaconsejados y alcanzar un precio total mnimo.
1. Datos
m: el nmero de nutrientes.
n: el nmero de Alimentos.
aij: la cantidad del nutriente ien una unidad del alimentoj.
.
cj:el precio de una unidad del alimentoj.
8/13/2019 Casos de Estudio de Programacin Lineal
14/67
8/13/2019 Casos de Estudio de Programacin Lineal
15/67
Ejemplo El Problema de la Dieta:
nutrientes digeribles (DN), protenas digeribles (DP), calcio (Ca), y fsforo (Ph)
dados en la siguiente tabla:
Tabla 2.Contenidos nutritivos de cinco alimentos
Las restricciones se convierten en
178.6 70.1 80.1 67.2 77.0 74.2
x
2
3
4
6.50 9.40 8.80 13.7 30.4 14.7
0.02 0.09 0.03 0.14 0.41 0.14
xx
x
5
1 2 3 4 5
. . . . . .
, , , ,
x
x x x x x
0
8/13/2019 Casos de Estudio de Programacin Lineal
16/67
Supngase que los precios unitarios de los alimentos son:
De este modo se tiene el siguiente PPL:
1 2 3 4 51, 0.5, 2, 1.2, 3c c c c c= = = = =
Minimizar 1 2 3 4 50.5 2 1.2 3Z x x x x x= + + + +
Sujeto a las restricciones ya mencionadas.
Con la solucin de este sistema se obtiene la solucin
0.793 en el punto (0,1.530,0,0.023,0)Z=
8/13/2019 Casos de Estudio de Programacin Lineal
17/67
Problema del Flujo en un a Redroblema del Flujo en un a RedSupngase una red de transporte (conduccin hidrulica, ferrocarril, carreteras,
. , , ,
mensajes, etc.) de un conjunto de nodos de la red, llamados nodos fuente, a unconjunto de puntos de destino, llamados nodos sumideros.Adems de stos, la red
contiene nodos intermedios donde no tienen lu ar ni entradas ni salidas de
material. Sea xijel flujo que va del nodo ial nodoj(positiva en la direccin ij,y
negativa en otro caso).
1. Datos
g: el grafog=(N,A)que describe la red de transporte, donde Nes el conjunto de
, y x .n: el nmero de nudos en la red.
fi: el flujo entrante (positivo) o saliente (negativo) en el nudo i
mij: la capacidad mxima de flujo en la conexin entre el nudo iy elj
cij:el precio de mandar una unidad del bien desde el nudo i al nudoj.
8/13/2019 Casos de Estudio de Programacin Lineal
18/67
2. Variables
ij
3. Restricciones: Las restricciones del problema son:
Imponiendo la condicin de conservacin del flujo en todos los nudos, y las
restr cc ones so re a capac a e as neas o conex ones, se o t enen as
siguientes restricciones:Restricciones de conservacin del flujo
(4)
Restricciones de capacidad de las lneas o conexiones
(5)
n1,...,i;)( == ij jiij fxx
ji;
8/13/2019 Casos de Estudio de Programacin Lineal
19/67
Ejemplo El Problema de Flujo en Redes:
los valores positivos de las variables del flujo.
Figura 3.Esquema del problema de transporte.
En este caso el sistema es
(7)
=
3
2
1
14
13
10010
0100100111
f
ff
x
x
x
ji;
ji;
8/13/2019 Casos de Estudio de Programacin Lineal
20/67
Supngase adems que . El problema de optimizacin es minimizarji,;1=ijc
Sometido a (7). Mediante el software adecuado puede obtenerse la siguiente
solucin:
3424141312
40x
10;
0
4
1
)1(
4
4
3
puntoelen5
24
14
13
+
=
=
x
x
x
Z
Esta solucin indica que existe un conjunto de infinitas soluciones, todas ellas
ro orcionando el mismo valor timo Z=5.
2234 x
8/13/2019 Casos de Estudio de Programacin Lineal
21/67
Problema de la Cartera de Valoresroblema de la Cartera de ValoresUn inversor es propietario de participaciones de varios valores. Masconcretamente es dueo de bi participaciones de los valores burstiles Ai,i=1,2,..m. Los precios actuales de estos valores son vi. Considrese que se pueden
predecir los dividendos que se pagarn al final del ao que comienza y los preciosfinales de los diferentes valores burstiles, esto es,Aipagar diy tendr un nuevo
i.
El objetivo es ajustar la cartera, es decir, el nmero de participaciones en cadavalor, de modo que se maximicen los dividendos
1. Datos
m: el nmero de valores burstiles
i:e n mero ac ua e par c pac ones e va or ursvi: el precio actual del valor ipor participacin
di: el dividendo que se pagar al final del ao en el valor burstil i
wi:el nuevo precio del valor burstil i
8/13/2019 Casos de Estudio de Programacin Lineal
22/67
r: porcentaje mnimo rdel valor actual de toda la cartera que no debe superarse en
el a ustes:porcentaje mnimo del valor total actual que no debe superarse por el valor
futuro total de la cartera, para hacer frente a la inflacin
2. Variablesxi: el cambio en el nmero de participaciones del valor burstil i.
3. Restricciones
Se deben ase urar ciertas condiciones ue debe satisfacer una cartera bien
equilibrada:
El nmero de participaciones debe ser no negativo
Exigimos que el capital asociado a todo valor concreto, despus del ajuste,
represente al menos una cierta fraccin rdel capital total actual de la cartera
i ix
( ) ( );i i i j j ji
r v b x v b x j + +
8/13/2019 Casos de Estudio de Programacin Lineal
23/67
El capital total de la cartera no debe cambiar en el ajuste pues se supone que no se
invierte dinero adicional
0i ii
v x =
ara acer rente a a n ac n, e cap ta tota en e uturo e e ser a menos un
cierto porcentaje smayor que el capital invertido actualmente:
( ) (1 )i i i i iw b x s v b+ +
4. Funcin a optimizar
Nuestro ob etivo es maximizar los dividendos
i i
( )i i ii
Z d b x= +
La tarea se concreta al determinar el valor mximo de los dividendos sujeto a todaslas restricciones anteriores.
8/13/2019 Casos de Estudio de Programacin Lineal
24/67
Ejemplo El Problema de la Cartera deValores:
, , ,con precios 20, 20 y 100 dlares, respectivamente. Se dispone de la siguiente
informacin: A no pagar dividendos y alcanzar una nueva cotizacin de 18
dlares B a ar 3 dlares or artici acin la nueva cotizacin ser 23 dlares
y Cpagar 5 dlares por participacin con una nueva cotizacin de 102 dlares. Si
se toman los porcentajes rcomo 25 y s, 0.30, todas las restricciones se escriben
como:
75
100
A
B
x
x
[ ][ ]
35
0.25 20(75 ) 20(100 ) 100(35 ) 20(75 )
0.25 20(75 ) 20(100 ) 100(35 ) 20(100 )
C
A B C A
A B C B
x
x x x x
x x x x
+ + + + + +
+ + + + + +
[ ]0.25 20(75 ) 20(100 ) 100(35 ) 100(35 )20 20 100 0
18 75 23 100 102 35
A B C C
A B C
x x x x
x x x
x x
+ + + + + ++ + =
+ + + + 1.03 7000x+
8/13/2019 Casos de Estudio de Programacin Lineal
25/67
8/13/2019 Casos de Estudio de Programacin Lineal
26/67
P bl d Di t ib i d E groblema de Distribucin de EnergaLos generadores de energa, as como las demandas de la misma se sitan en unared energtica. El objetivo de este problema consiste en decidir la energa aproducir por cada generador de forma tal que se satisfagan las diferentes
condiciones tcnicas de la red y los generadores, as como las demandas, al mnimocoste.
a a nea e transm s n e una re e energ a transm te energ a e un us a otro.La energa transmitida es proporcional a la diferencia de los ngulos de estos buses(de forma similar a que el agua que fluye en una tubera que conecta dos tanques es
ro orcional a la diferencia de alturas del a ua en ambos . La constante deproporcionalidad tiene un nombre divertido susceptibilidad. La potenciatransmitida desde el bus ialja travs de la lnea i-jes por tanto
(8))( jiijB
donde Bijes la susceptibilidad de la lnea i-j, y y los ngulos de los buses iyj,respectivamente. Por razones fsicas, la cantidad de energa transmitida a travs deuna lnea tiene un lmite. Este lmite est relacionado con consideraciones trmicas
i j
. ,su lmite de transmisin no sea excedido.
8/13/2019 Casos de Estudio de Programacin Lineal
27/67
Esta condicin puede formularse como
9donde es la capacidad de transmisin de la lnea i-j.Debe notarse que la potencia
transmitida es proporcional a la diferencia de ngulos y no, a un ngulo dado. Por
tanto uede fi arse el valor de un n ulo arbitrario a 0 tomarlo como ori en. Es
ijjiijij
ijP
decir, para un bus arbitrario k:
(10)0=k
origen es que los ngulos son variables no restringidas en signo. La potencia
generada por un generador es una magnitud positiva limitada inferiormente,
debido a las condiciones de estabilidad (de forma similar a la de un automvil, ueno puede moverse a una velocidad inferior a un cierto lmite), y superiormente,
debido a lmites trmicos (similarmente a la de un automvil que no puede
moverse a ms de una cierta velocidad mxima). Las restricciones anteriores
conducen a:(11)
donde pi es la potencia producida por el generador i, y y son constantes
iii PpP
iPiP
positivas que representan, respectivamente, el mnimo y el mximo de las
potencias generadas por el generador i.
8/13/2019 Casos de Estudio de Programacin Lineal
28/67
En todo bus, la potencia que entra debe ser igual a la potencia que sale (ley de laconservacin de la energa), que puede escribirse como
(12)
donde es el conjunto de buses conectados a travs de las lneas al bus i y Di la
i;)( =+
iij
jiij DpBi
i
.
Como se ha indicado anteriormente, la potencia transmitida a travs de toda lnea eslimitada, por tanto
(13)
1. Datos
n:el nmero de eneradores.
,,jiij
: la mnima energa de salida asociada al generador i.
: la mxima energa de salida asociada al generador i.
B : la susce tancia de la lnea i- .
iP
iP
:la capacidad mxima de transmisin de la lnea i-j.
Ci:el coste de producir energa en el generador i.
ijP
.
Di: la demanda asociada al bus i.i
8/13/2019 Casos de Estudio de Programacin Lineal
29/67
2. Variables
: la ener a roducida or el enerador i.:el ngulo del bus i.
3. Restricciones: Las restricciones de este problema son
i
(14)
,...,2,1;jmax;)(max
,..,2,1i;)(
i =
==+
=
ijjiijij
jiijiij
k
niPBP
nDPBi
4. Funcin a minimizar: El objetivo es minimizar el precio total de la
n1,2,...,imax;min = ii PpiP
pro ucci n e potencia
(15)
donde Ci es el precio de la produccin del generador i, y n el nmero de
=
= n
iiipCZ
1
generadores.
8/13/2019 Casos de Estudio de Programacin Lineal
30/67
8/13/2019 Casos de Estudio de Programacin Lineal
31/67
Este problema puede escribirse como:
sometido a
21
03=
85.0)(0.3)(5.30)(5.2)(0.3
..
3231
22123
11213
=+=++
=++
p
p
3.0)(5.23.0
4.010.0
..
21
2
1
P
Las variables de optimizacin sonp1, p2, y .
5.0)(5.35.0
...
31
1 2
La solucin de este problema es:TT .117,0)(-0.143,-0,85)(0.565,0.2p,385.5 === Z
a so uc n p ma requ ere que e genera or pro uzca . y e genera or
produzca 0.285.
8/13/2019 Casos de Estudio de Programacin Lineal
32/67
Programacin Lineal Entera-Mixta
8/13/2019 Casos de Estudio de Programacin Lineal
33/67
Problema de Identificacin deSntomas Relevantesntomas Relevantes
Sea un conjunto conocido de posibles enfermedades.
Considrese ue los mdicos al identificar las enfermedades asociadas a un{ }1 2, ,..., nD D D D=
conjunto de pacientes, basan su decisin normalmente en un conjunto de sntomas
. Considrese que se requiere identificar un nmero mnimo de
sntomas de tal manera ue cada enfermedad uede distin uirse
{ }1 2, ,..., mS S S S =S S
perfectamente de las otras de acuerdo con los niveles de los sntomas en el
conjunto Sa. Determinar el nmero mnimo de sntomas es importante ya que da
lugar a un costo mnimo de diagnstico.
1. Datos
D: el con unto de enfermedades.
S:Conjunto de sntomas.
n:nmero de enfermedades
m:nmero de sntomas
8/13/2019 Casos de Estudio de Programacin Lineal
34/67
8/13/2019 Casos de Estudio de Programacin Lineal
35/67
incluidos en Sa, y a>0es el nivel de discrepancia deseado. Se debe tener en cuenta
ue a medida ue el valor dea
es ma or, ma or ser el nmero de sntomasrequeridos, entonces:
m
j ikjx d
coincide con el nmero de sntomas en S0 que toman distintos valores para las
enfermedades Di D, a es el nmero mnimo, ara cual uier ar (Di,D ) de
=
enfermedades, necesario para tener un subconjunto aceptable Sa, lo que quiere
decir que pueden desconocerse a-1sntomas.
4. Funcin a minimizar
El objetivo es minimizar el nmero de sntomas seleccionados:
Sin embargo, si las enfermedades han de identificarse con alguna carencia de
1
m
jZ x
==
informacin, el conjunto S0puede resultar inservible, por tanto, normalmente se
emplea un valor a>0.
8/13/2019 Casos de Estudio de Programacin Lineal
36/67
Para determinar los sntomas relevantes asociados a la enfermedad itenemos:
Minimizar1
m
j
Z x=
=
Sujeto a
De esta manera odemos determinar el subcon unto mnimo del con unto
{ }1
; 1, 2,..., ,j ikjj
x d a k n i k
=
>
S S
de manera que la enfermedad itenga sntomas diferentes comparada con el resto
de enfermedades.
8/13/2019 Casos de Estudio de Programacin Lineal
37/67
Ejemplo El Problema de Identificacin de Sntomas Relevantes:
Considrese el con unto de enfermedades el con unto de, , , ,D D D D D D=
sntomas . Considrese asimismo que los sntomas asociados a las
diferentes enfermedades y los sntomas relevantes para cada enfermedad son los
que aparecen en la siguientes tablas:
{ }1 2 8, ,...,S S S S =
Tabla 3.Sntomas asociados a todas las enfermedades.
Tabla 4.Sntomas relevantes a cada enfermedad, para a=1.
8/13/2019 Casos de Estudio de Programacin Lineal
38/67
Por tanto, minimizando la suma:
Sujeto a las restricciones mostradas anteriormente, y dos valores de a, se concluye
1j
Z x=
=
que e con unto e s ntomas
es un subconjunto mnimo y suficiente de sntomas que permite distinguir las
{ }2,5
cinco enfermedades. Sin embargo, si se emplea un nivel de discrepancia de a=3, el
conjunto mnimo requerido es
{ }1,2,4,5,7Hay que tener en cuenta, que en este caso es posible hacer un diagnstico correcto
an en la ausencia de dos sntomas.
8/13/2019 Casos de Estudio de Programacin Lineal
39/67
Problema del Horario Acadmicoroblema del Horario AcadmicoEl objetivo es asociar aulas y horas a las asignaturas de un programa acadmico
dividido en cursos. Se considera ue estn dis onibles n aulas n horas
respectivamente, para ensear nsasignaturas. Estas asignaturas estn agrupadas por:
(1) Cursos y (2) profesores. Los ndices s, c, h, i, y b indican respectivamenteasignatura, clase, hora, profesor y bloque.
1. Datos
n :nmero de aulas.
nh:nmero de horas.
ns:nmero de asignaturas.
ni
:n mero e asignatura que a e impartir e pro esor i.
nb:nmero de cursos.
: conjunto de todas las asi naturas.
i: conjunto de asignaturas que ha de impartir el profesor i.
b: conjunto de asignaturas del curso b.
8/13/2019 Casos de Estudio de Programacin Lineal
40/67
2. Variables
, ,ca la hora h, y 0 en otro caso.
3. Restricciones
a. Cada profesor imparte todas sus asignaturas:
n n
1 1
( , , ) ;i
is c h
v s c h n i = =
=
b. Cada profesor imparte mximo una asignatura cada hora:
1
( , , ) 1; ,c
i
n
s c
v s c h h i =
c. Cada asignatura se imparte una sola vez:
1 1
( , , ) 1;c hn n
c h
v s c h s= =
=
8/13/2019 Casos de Estudio de Programacin Lineal
41/67
d. En cada clase y hora se imparte mximo una sola asignatura:
( , , ) 1; ,s
v s c h c h
e. En cada hora, se ensea como mximo una asignatura en cada curso:
( , , ) 1; ,cn
v s c h h b=
4. Funcin a Optimizar
Hay diferentes opciones de funcin objetivo a minimizar. En este caso se escogi la
funcin objetivo que busca obtener un horario compacto:
c hn n
Minimizar 1 1, ,
s c h = =
.
penaliza el que las variables v(s,c,h)tomen el valor 1 para valores elevados de cy h.
Por tanto, su objetivo es compactar el horario.
8/13/2019 Casos de Estudio de Programacin Lineal
42/67
Ejemplo El Problema del Horario Acadmico
Considrese 3 aulas, 5 horas, 8 asi naturas, 2 rofesores, 2 cursos. El con unto de
todas las asignaturas es , el conjunto de las asignaturas del
profesor 1 es , el conjunto de las asignaturas del profesor 2 es
el con unto de asi naturas del curso 1 es
{ }1 2 8, ,...,S S S ={ }1 1 2 8, ,S S S =
S S S S S = S S S S =
Y el conjunto de las asignaturas del curso 2 es . Se debe tener en
cuenta que .{ }2 5 6 7 8, , ,S S S S =
1 2 1 2 1 2 1 2y , y y = = = =
La solucin se muestra en la siguiente tabla:
Tabla 5.Sntomas asociados a todas las enfermedades.
8/13/2019 Casos de Estudio de Programacin Lineal
43/67
El horario para el profesor 1 es:
El horario para el profesor 2 es:
8/13/2019 Casos de Estudio de Programacin Lineal
44/67
8/13/2019 Casos de Estudio de Programacin Lineal
45/67
Problema de Localizacin de PlantasProductivasroductivas
Se trata de elegir la localizacin de plantas entre un conjunto dado de posibles
localizaciones teniendo en cuenta las necesidades de los consumidores
optimizando algn criterio econmico. Normalmente, la construccin de una
planta origina un costo importante que no depende del nivel de produccin de esaplanta.
Figura 5.Localizacin de plantas con capacidad limitada.
8/13/2019 Casos de Estudio de Programacin Lineal
46/67
1. Datos
I: conjunto de nconsumidores.
J: conjunto de mlugares donde las plantas pueden ser construidas.
{ }1,...,n
{ }1,...,m
.
cij:beneficio unitario por venta al consumidor i, de bienes producidos en la plantajuj: la capacidad productiva de la planta localizada enj.
bi: la demanda del consumidor i.
2. Variables
yj:variable binaria que permite modelar la construccin de una planta productiva
en la localizacinj.
1 si se construye la planta productiva0 en otro caso
jjy =
xij: cantidad de producto enviada desde la plantajal consumidor i.
R i i
8/13/2019 Casos de Estudio de Programacin Lineal
47/67
3. Restricciones
Las restricciones de este roblema son las si uientes. Ha de satisfacerse la demanda
de cada consumidor:
;ij ij J
x b i I
=
Dado que al consumidor ino se le puede suministrar desdeja no ser que se hayaconstruido una central enj, tenemos que:
Dado quey =0implica que xi=0, y y =1da lugar a la restriccin ,
;ij j ji I
x u y j J
i ij ji Ix u que implica que la produccin de la planta j no puede exceder su capacidad
mxima.Adems, las restricciones sobre las variables son:
, ;
0; ,
j
ij
y
x i I j J
4. Funcin a Optimizar
maximizar ij ij j ji I j J j J
Z c x f y
=
Ej l El P bl d L li i d Pl t I d t i l
8/13/2019 Casos de Estudio de Programacin Lineal
48/67
Ejemplo El Problema de Localizacin de Plantas Industriales
Una em resa considera la construccin de lantas roductivas ara suministrar un
determinado producto a 7 ciudades. La demanda de cada una de esas ciudades
puede estimarse mediante factores demogrficos y sociales, como se muestra en la
siguiente tabla.
Tabla 6.Beneficios en funcin de las localizaciones.
Un determinado estudio estadstico ha identificado 6 posibles localizaciones paralas plantas industriales. Se supone que todas las plantas tienen las mismas
caractersticas. La capacidad mxima de produccin de cada planta es de 6
unidades. Se considera que el costo de recobrar la inversin a lo largo del
horizonte de estudio de una planta es 10 unidades monetarias.
El bj ti d t i l d l t l li i d f t l
8/13/2019 Casos de Estudio de Programacin Lineal
49/67
El objetivo es determinar el nmero de plantas y sus localizaciones, de forma tal
que se suministre la demanda de las ciudades y el beneficio obtenido sea mximo.
El proceso de optimizacin consiste en maximizar el beneficio total incluyendo
costos de amortizacin su eto a las restricciones ertinentes:
Maximizar7 6 6
1 1 1
10ij ij ji j j
Z c x y= = =
=
Sujeto a 6 61 2
1 1
1.5; 2.0j jj j
x x= =
= =
6 6
3 41 1
6 6
3.0; 4.0j jj j
x x= =
= =
5 6
1 16
71
. .
2.0
j j
j j
jj
x
= =
=
=
y 6
8/13/2019 Casos de Estudio de Programacin Lineal
50/67
y 6
1
6 ; 1,...,7ij ji
x y j=
=
{ }0,1 ; 1,...,6
0; 1,...,7; 1,...,6
j
ij
y j
x i j
=
= =
pr mer grupo e restr cc ones correspon e a as restr cc ones e eman a y e
segundo a las restricciones de capacidad productiva.
La solucin se muestra en la siguiente figura:
Figura 6.Solucin al ejemplo de localizacin de plantas con capacidad limitada.
La solucin consiste en emplazar 3 plantas industriales en las localizaciones L L y
8/13/2019 Casos de Estudio de Programacin Lineal
51/67
La solucin consiste en emplazar 3 plantas industriales en las localizaciones L2, L4y
L5. La distribucin de produccin por ciudades se muestra en la siguiente Tabla:
Tabla 7.Produccin de cada planta que se suministra a cada ciudad.
8/13/2019 Casos de Estudio de Programacin Lineal
52/67
Problema de Programacin deCentrales Termo Elctricasentrales Termo Elctricas
El costo de poner en funcionamiento una central trmica despus de haber estado
arada un ar de das es mu elevado or lo ue la lanificacin de los arran ues
paradas debe hacerse con cuidado.
El problema de programacin horaria de centrales trmicas consiste en
determinar ara un horizonte de lanificacin multi-horario el arran ue arada
de cada central, de tal forma que se suministre la demanda en cada hora, el costo se
minimice, y se satisfagan determinadas restricciones tcnicas y de seguridad.
Un tpico horizonte de planificacin es un da dividido en horas. Si los intervalos
horarios se denotan mediante k, el horizonte de planificacin consta de los
Donde Kes tpicamente igual a 24.
1,2,...,k K=
El costo de arranque de una central es una funcin exponencial del tiempo que la
central lleva parada, pero se considera constante (lo que es una simplificacin
razonable en la mayora de los casos).
Cada vez que una central se arranca se origina un gasto que se puede expresar de la
8/13/2019 Casos de Estudio de Programacin Lineal
53/67
Cada vez que una central se arranca se origina un gasto que se puede expresar de la
siguiente forma:
donde Cj es el costo de arranque de la central je yjkes una variable binaria que
toma el valor de 1 si la central se arranca al comienzo del eriodo k 0 en otro
j jkC y
caso.
El costo de parada puede expresarse de forma anloga al costo de arranque:
donde Ejes el costo de parada de la centraljy zjkes una variable binaria que toma
el valor de 1 si la centraljse para al comienzo del periodo k, y 0 en otro caso.
j jk
El costo de funcionamiento esta constituido por un costo fijo y un costo variable.
El costo fijo se puede expresar como:
dondeAjes el costo fijo de la centraljy vjkes una variable binaria que toma el valor
de 1 si la central esta en funcionamiento durante el eriodo k, 0 en otro caso.
jkv
El costo variable puede considerarse proporcional a la produccin en la central:
8/13/2019 Casos de Estudio de Programacin Lineal
54/67
El costo variable puede considerarse proporcional a la produccin en la central:
B
donde Bj es el costo variable de la central j y pjk la produccin de la central j
durante el periodo k.
Las centrales trmicas no pueden funcionar por debajo de una produccin mnimani por encima de una produccin mxima. Esta restriccin se puede escribir como:
donde son respectivamente las producciones mnima y mxima de la
j jk jk j jkv p P v
y Pcentralj.
,
incrementar su produccin por encima de un mximo, denominado rampa mximade subida de carga. Esta restriccin se puede expresar como:
donde Sjes la rampa mxima de subida de carga de la centralj.
1k jk jp p+
Para el primer periodo del horizonte de planificacin las restricciones previas
8/13/2019 Casos de Estudio de Programacin Lineal
55/67
p p p p
tienen la siguiente forma:
donde es la produccin de la central j en el periodo previo al comienzo del
horizonte de lanificacin.
1 j jp P S 0
j
Anlogamente, ninguna central puede bajar su produccin por encima de un
mximo, que se denomina rampa mxima de bajada de carga:
Donde Tjes la rampa mxima de bajada de la centralj.
Para el primer periodo del horizonte de planificacin la restriccin anterior toma
1jk jk j+
la forma:
Cualquier central que esta funcionando puede pararse pero no arrancarse y
0
1j j jp p T
cualquier central parada puede arrancarse pero no pararse. Esto se expresa de lasiguiente manera:
1k k k k y z v v =
Para el primer periodo la restriccin anterior se convierte en:
8/13/2019 Casos de Estudio de Programacin Lineal
56/67
p p0z v V =
donde es una variable binaria que toma el valor de 1 si la central jesta en
funcionamiento en el periodo anterior al primero del horizonte de planificacin, y
0 en otro caso.
0V
La demanda debe suministrarse en cada periodo, por lo tanto:
J
p D=
dondeJes el nmero de centrales y Dkla demanda en el periodo k.
1j=
Por razones de seguridad, la potencia total disponible en centrales en
funcionamiento debe ser mayor que la demanda en una determinada cantidad de
reserva, es decir:
1
J
j jk k kj
v D R=
+
on e kes a can a requer a e reserva por enc ma e a eman a en e
periodo k.
1. Datos
8/13/2019 Casos de Estudio de Programacin Lineal
57/67
K:nmero de eriodos de tiem o ue tiene el horizonte tem oral
Cj : costo de arranque de la centralj.
Ej: costo de parada de la centralj.
j: costo o e a centra j.
Bj: costo variable de la centralj.produccin mnima de la centralj.:
produccin mxima de la centralj.
Sj: rampa mxima de subida de carga de la centralj.
:j
0
de planificacin.
Tj: rampa mxima de bajada de carga de la centralj.
j
constante binaria que toma el valor de 1 si la centralj esta funcionando en el
periodo previo al comienzo del horizonte de planificacin, y 0 en otro caso.
J:nmero de centrales de produccin.
:jV
Dk:demanda en el periodo k.
Rk: reserva requerida en el periodo k.
2. Variables
8/13/2019 Casos de Estudio de Programacin Lineal
58/67
:variable binaria ue toma el valor 1, si la central se arranca al comienzo del
periodo k, y 0 en otro caso.
zjk : variable binaria que toma el valor 1, si la central j se para al comienzo del
eriodo k 0 en otro caso.
vjk: variable binaria que toma el valor 1, si la central j esta en funcionamiento
durante el periodo k, y 0 en otro caso.
k .
3. RestriccionesCualquier central debe funcionar por encima de su produccin mnima y por
debajo de su produccin mxima, por lo tanto:
Las restricciones de rampa de subida deben satisfacerse:
; ,j jk jk j jkv p v
donde .1 ; , 0,..., 1jk jk jp p S j k K+ =
0
0 jp P=
Las restricciones de rampa de bajada son:
8/13/2019 Casos de Estudio de Programacin Lineal
59/67
La lgica de cambio de estado (de arranque a parada y viceversa) ha de preservarse,
1 ; , 0,..., 1jk jk jp p T j K+ =
donde .
1; , 1,...,jk jk jk jky z v v j k K = =
0
0 ;j jv V j=
La demanda ha de satisfacerse en cada periodo, por lo tanto:
1
;J
jk kj
p D k=
=
Finalmente y por razones de seguridad, la reserva ha de mantenerse en todos los
periodos:
;J
k k kv D R k + 1j=
8/13/2019 Casos de Estudio de Programacin Lineal
60/67
Ejemplo El Problema de Programacin de Centrales Termo-
8/13/2019 Casos de Estudio de Programacin Lineal
61/67
Elctricas
Se considera un horizonte de planificacin de 3 horas. Las demandas en esas horasson respectivamente 150, 500 y 400. Las reservas son respectivamente 15, 50 y40. Se consideran 3 centrales de produccin de energa elctrica. Los datos de las
centrales se muestran en la siguiente tabla:
Tabla 8.Produccin de cada planta que se suministra a cada ciudad.
Se considera que todas las centrales estn paradas en el periodo previo al primero
del horizonte de planificacin.
La produccin ptima de cada central se muestra en la siguiente tabla:
8/13/2019 Casos de Estudio de Programacin Lineal
62/67
Tabla 9.Produccin de cada planta que se suministra a cada ciudad.
El costo mnimo de produccin es 191. La central 1 se arranca al comienzo de la
hora 1 ermanece aco lada durante 3 horas. La central 2 se arranca al comienzode la hora 2 y permanece acoplada durante las horas 2 y 3. La central 3 se arranca
al comienzo de la hora 2 y se para al comienzo de la hora 3.
8/13/2019 Casos de Estudio de Programacin Lineal
63/67
Programacin No-Lineal
8/13/2019 Casos de Estudio de Programacin Lineal
64/67
Problema del Paquete Postalroblema del Paquete PostalUn paquete postal es una caja de dimensiones x,y, y z(como la figura), que debe
La altura mas el permetro de la base no puede exceder 108 cm
Pues no son posibles las longitudes negativas.
2 2 108; , , 0z x y x y z+ +
Se buscan las tres dimensiones que maximizan el volumen
( , , )V x y z xyz =
8/13/2019 Casos de Estudio de Programacin Lineal
65/67
Como el ancho xdebe ser mayor que 0.5 y, de acuerdo con la teora de resistencia
de materiales la deformacin en el extremo libre viene dada por:
8/13/2019 Casos de Estudio de Programacin Lineal
66/67
de materiales, la deformacin en el extremo libre viene dada por:
3 / 3FL EI
,
3 /12I xy=
es el correspondiente momento de inercia de la seccin rectangular, se tiene que
minimizar W(x,y)bajo las restricciones:
3
0.5
SExy
x
, 0x y
8/13/2019 Casos de Estudio de Programacin Lineal
67/67
Bibliografaibliografa
Ciencia, Enrique Castillo, Antonio J. Conejo, Pablo Pedregal, Ricardo Garca, Natalia
Alguacil, 2002.