Casos de Estudio

Universidad de los Andes-CODENSA

Programacin Lineal

Problema del Transporte

Cierto producto debe enviarse en determinadas cantidades u1,,um, desde cada uno de m orgenes, orgenes y recibirse en cantidades v ,,v vn, en cada uno de los n destinos. destinos Determine las cantidades xij, que deben enviarse desde el origen i al destino j, para conseguir minimizar el coste de envo.
1

1. Datos

m: el nmero de orgenes n: el nmero de destinos ui: la cantidad que debe enviarse desde el origen i vj: la cantidad que debe ser recibida en el destino j cij: el coste de envo de una cantidad de producto desde el origen i al destino j
2. Variables

xij: la cantidad que se enva desde el origen i al destino j. Se supone que las variables deben ser no negativas.

xij 0; i = 1,..., m; j = 1,..., n

(1)

3 Restricciones: Las restricciones del problema son: 3.

x ij = u i ; i = 1,..., m
j=1 m i =1

1 n x ij = v j ; j = 1,...,

(2)

El primer conjunto de condiciones indica que la cantidad del producto que parte del origen i debe coincidir con la suma de las cantidades que parten de ese origen hasta los distintos destinos j=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 g 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 p de todas las unidades). ) Es decir, se debe minimizar: los costos de transporte
Z = cij xij
i =1 j =1 m n

(3)

Ejemplo El Problema del Transporte:

Considrese el problema de transporte mostrado en la figura 1, 1 donde m=3 3 orgenes, n=3 destinos, u1=2, u2=3, u3=4, v1=5, v2=2, v3=2.

Figura 1. Esquema del problema de transporte.

En este caso el sistema es

1 0 0 CX = 1 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0

xij 0; i, j = 1,2,3

x11 x12 0 2 x13 0 3 x21 1 4 x22 = 0 5 x23 0 2 x31 1 2 x32 x33

Las tres primeras ecuaciones establecen la conservacin del producto en los tres orgenes g y las tres ltimas igualdades, g , la conservacin del p producto en los tres destinos. Si se concretan los valores particulares:
1 2 3 c = 2 1 2 3 2 1

Para los costos de envo, el problema consiste en minimizar:

Z = x11 + 2 x12 + 3 x13 + 2 x21 + x22 + 2 x23 + 3 x31 + 2 x32 + x33

El mnimo de la funcin objetivo es 14, que corresponde a:

2 0 0 X = 1 2 0 2 0 2

Problema de la Planificacin de la P d i Produccin

Un productor fabrica una pieza, cuya demanda vara en el tiempo, de acuerdo con la siguiente figura. figura

Figura 2. Grfico de la demanda en funcin del tiempo.

El productor d t debe d b atender t d la l demanda d d mensual l siempre. i En general E l cualquier l i problema de planificacin admitir diversas posibilidades que aseguren que la demanda es convenientemente atendida:

a)

Produccin variable: El fabricante puede producir cada mes el nmero exacto de unidades q que le solicitan. Produccin Constante: El fabricante que debe atender una demanda que cambia con el tiempo puede producir por encima de dicho nivel en periodos de baja demanda y almacenar la sobreproduccin para los periodos de demanda mayor.

b)

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 smax: la l capacidad id d mxima i de d almacenamiento l i t at: el precio de venta en el mes t

bt: el costo de produccin en el mes t ct: el costo de almacenamiento en el mes 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

st 1 + xt dt = st ; t = 1, 2,..., n st st , xt s max ; t = 1, 2,..., n 0

La demanda dt en el mes t debe coincidir con el cambio en el almacenamiento , st-1st, ms la produccin xt en el mes t; la capacidad de almacenamiento no puede excederse; y la demanda dt, almacenamiento st, y produccin xt deben ser no negativas.

4. Funcin a Optimizar

Una posibilidad consiste en maximizar el ingreso despus de descontar los costes de la variacin de la produccin y los inventarios.
Z = ( at dt bt xt ct st )
t =1 n

Otra posibilidad consiste en minimizar los costos de almacenamiento:

Z = ct st
t =1 n

Ejemplo El Problema de la Planificacin de la Produccin:

Considrese la funcin de demanda en funcin del tiempo mostrada en la siguiente tabla:

Tabla 1. Demanda en funcin del tiempo.

Supngase que la cantidad almacenada inicialmente es s0=2. Entonces el sistema se transforma en:
s1 s 2 0 s3 0 s 0 4 = 3 ; st , xt o; t = 1, 2,3, 4 0 x1 6 1 x2 1 x3 x 4

1 0 0 0 1 1 0 0 Cx = 0 1 1 0 0 0 1 1

1 0 0 0 1 0 1 0 0

0 0 0

Donde el cero en la matriz de la derecha procede a restar la demanda para t=1 del 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
Z = 36 x1 x2 x3 x4 s1 s2 s3 s4

Sujeto a las restricciones ya mencionadas. Resolviendo este problema encontramos que el valor mximo es:
Z = 26 para x = ( s1 , s2 , s3 , s4 , x1 , x2 , x3 , x4 ) = (0,0,0,0,0,3,6,1)T

Lo que implica ningn almacenamiento.

Problema de la Dieta
Se conocen los contenidos nutritivos de ciertos alimentos, sus precios y la cantidad mnima diaria de nutrientes aconsejada. aconsejada El problema consiste en determinar la cantidad de cada alimento que debe comprarse para satisfacer los mnimos aconsejados y alcanzar un precio total mnimo.
1. Datos

m: el nmero de nutrientes. n: el nmero de Alimentos. aij: la cantidad del nutriente i en una unidad del alimento j. bi: la cantidad mnima del nutriente i aconsejada. cj: el precio de una unidad del alimento j.

2. Variables

xj: la cantidad del alimento j que debe adquirirse. adquirirse

3. Restricciones

Como la cantidad total de un nutriente dado i es la suma de las cantidades de los nutrientes en todos los alimentos y las cantidades de alimentos deben ser no negativas, entonces tenemos:

aij x j bi ; i = 1,..., m
j =1

x j 0; j = 1,..., n
4. Funcin a Minimizar

En el problema de la dieta se esta interesado en minimizar el precio de la dieta: Minimizar

Z = cjxj
j =1 n

Donde cj es el precio unitario del alimento j.

Ejemplo El Problema de la Dieta:

Considere un caso con cinco nutrientes y con los mnimos aconsejados para los 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

78.6 6.50 0.02 0 27 0.27 70.1 9.40 0.09 0 0.34 34 80.1 8.80 0.03 0 0.30 30 67.2 13.7 0.14 1 1.29 29 x1 77.0 74.2 x2 30.4 14.7 x3 0.41 0.14 x4 0 0.86 86 0 0.55 55 x 5 x1, x2 , x3 , x4 , x5 0

Supngase que los precios unitarios de los alimentos son:

c1 = 1, c2 = 0.5, c3 = 2, c4 = 1.2, c5 = 3

De este modo se tiene el siguiente PPL: Minimizar

Z = x1 + 0.5 x2 + 2 x3 + 1.2 x4 + 3 x5

Sujeto a las restricciones ya mencionadas. Con la l solucin l de d este sistema se obtiene b l solucin la l
Z = 0.793 en el punto (0,1.530,0,0.023,0)

Problema del Flujo en un a Red

Supngase una red de transporte (conduccin hidrulica, ferrocarril, carreteras, etc ) a travs de la cual se desea enviar un cierto material (aceite, etc.) (aceite grano, grano vehculos, vehculos mensajes, etc.) de un conjunto de nodos de la red, llamados nodos fuente, a un conjunto de puntos de destino, llamados nodos sumideros. Adems de stos, la red contiene nodos intermedios, , donde no tienen lugar g ni entradas ni salidas de material. Sea xij el flujo que va del nodo i al nodo j (positiva en la direccin ij ,y negativa en otro caso).
1. Datos

g: el grafo g=(N,A) que describe la red de transporte, donde N es el conjunto de nudos y A es el conjunto de conexiones. nudos, cone iones 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 i y el j cij: el precio de mandar una unidad del bien desde el nudo i al nudo j.

2. Variables

xij: el flujo que va del nodo i al nodo j

3. Restricciones: Las restricciones del problema son:

Imponiendo la condicin de conservacin del flujo en todos los nudos, y las restricciones i i sobre b la l capacidad id d de d las l lneas l o conexiones, i se obtienen bi l las siguientes restricciones: Restricciones de conservacin del flujo
j ( xij x ji ) = f i ; i = 1,..., n
(4) (5)

Restricciones de capacidad de las lneas o conexiones

mijj xijj mijj ; i < j

donde i<j evita la posible duplicacin de restricciones.

4. Funcin a minimizar: El precio total es:
Z = cij xij
ij

(6)

As, debe minimizarse (6) bajo (4) y (5). Las redes d de d abastecimiento b d agua, los de l sistemas de d comunicaciones, y otros, conducen a problemas de redes de transporte como el descrito aqu.

Ejemplo El Problema de Flujo en Redes:

Considrese el problema de flujo en la red de la figura 3 donde las flechas indican los valores positivos de las variables del flujo.

Figura 3. Esquema del problema de transporte.

En este caso el sistema es

x12 1 1 1 0 0 x13 1 0 1 0 0 x14 = 0 1 0 0 1 0 0 1 1 1 x24 x34

f1 f2 f3 f4

xij mij ; i < j xij mij ; i < j

(7)

Donde se supone que mij = 4, i < j, y (f1 , f 2 , f 3 , f 4 ) = (7,-4,-1,-2)

Supngase adems que cij = 1; i, j. El problema de optimizacin es minimizar

Z = x12 + x13 + x14 + x24 + x34

Sometido a (7). Mediante el software adecuado puede obtenerse la siguiente solucin:

x12 0 4 x 3 13 1 Z = 5 en el punto x14 = 4 + (1 ) 4 ; 0 1 4 x24 0 x 2 2 34

Esta solucin indica que existe un conjunto de infinitas soluciones, todas ellas proporcionando el mismo valor ptimo, Z Z=5. 5.

Problema de la Cartera de Valores

Un inversor es propietario de participaciones de varios valores. Mas concretamente 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 precios finales de los diferentes valores burstiles, esto es, Ai pagar di y tendr un nuevo precio wi. El objetivo es ajustar la cartera, es decir, el nmero de participaciones en cada valor, de modo que se maximicen los dividendos
1. Datos

m: el nmero de valores burstiles bi: el l nmero actual t ld de participaciones ti i i d del l valor l b burstil til i vi: el precio actual del valor i por participacin di: el dividendo que se pagar al final del ao en el valor burstil i wi: el nuevo precio del valor burstil i

r: porcentaje mnimo r del valor actual de toda la cartera que no debe superarse en el ajuste j s: 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. Variables

xi: el cambio en el nmero de participaciones del valor burstil i.

3. Restricciones

Se deben asegurar ciertas condiciones que debe satisfacer una cartera bien equilibrada: El nmero de participaciones debe ser no negativo
xi bi

Exigimos que el capital asociado a todo valor concreto, despus del ajuste, represente al menos una cierta fraccin r del capital total actual de la cartera
r vi (bi + xi ) v j (b j + x j ); j i

El capital total de la cartera no debe cambiar en el ajuste pues se supone que no se invierte dinero adicional

vi xi = 0
i

Para hacer P h f frente a la l inflacin, i fl i el l capital i l total l en el l futuro f d b ser al debe l menos un cierto porcentaje s mayor que el capital invertido actualmente:

wi (bi + xi ) (1 + s) vibi
i i

4. Funcin a optimizar

Nuestro objetivo es maximizar los dividendos

Z = di (bi + xi )
i

La tarea se concreta al determinar el valor mximo de los dividendos sujeto a todas las restricciones anteriores.

Ejemplo El Problema de la Cartera de Valores:

Se tienen participaciones de tres valores burstiles, burstiles 75 de A, 100 de B y 35 de C, 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, ,Bp pagar g 3 dlares p por p participacin p y la nueva cotizacin ser 23 dlares, , y C pagar 5 dlares por participacin con una nueva cotizacin de 102 dlares. Si se toman los porcentajes r como 25 y s, 0.30, todas las restricciones se escriben como:
xA xB xC 0.25[ 20(75 + x A ) + 20(100 + xB ) + 100(35 + xC )] 0.25[ 20(75 + x A ) + 20(100 + xB ) + 100(35 + xC )] 0.25[ 20(75 + x A ) + 20(100 + xB ) + 100(35 + xC ) ] 20 x A + 20 xB + 100 xC 18(75 ( + x A ) + 23(100 ( + xB ) + 102(35 ( + xC ) 75 100 35 20(75 + x A ) 20(100 + xB ) 100(35 + xC ) = 0 1.03(7000) ( )

Despus de varias simplificaciones , las restricciones anteriores se transforman en:

xA xB xC 15 x A 5 xB 25 xC 5 x A + 15 xB 25 xC 5 x A 5 xB + 75 xC 20 x A + 20 xB + 100 xC 18 x A + 23 xB + 102 xC 75 100 35 250 250 1750 = 0 270

La solucin l obtenida b d es:

Z = 612.5 dlares y x A = 12.5, xB = 75, xC = 17.5

P bl Problema de d Di Distribucin t ib i de d E Energa g

Los generadores de energa, as como las demandas de la misma se sitan en una g El objetivo de este problema consiste en decidir la energa g a red energtica. producir por cada generador de forma tal que se satisfagan las diferentes condiciones tcnicas de la red y los generadores, as como las demandas, al mnimo coste. C d lnea Cada l de d transmisin i i de d una red d de d energa transmite i energa de d un bus b 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 proporcional p p a la diferencia de alturas del agua g en ambos). ) La constante de proporcionalidad tiene un nombre divertido susceptibilidad. La potencia transmitida desde el bus i al j a travs de la lnea i-j es por tanto donde Bij es la susceptibilidad de la lnea i-j, y i y j los ngulos de los buses i y j, respectivamente. Por razones fsicas, la cantidad de energa transmitida a travs de una lnea tiene un lmite. Este lmite est relacionado con consideraciones trmicas o de estabilidad. estabilidad Por tanto, tanto una lnea energtica debe ser operada de forma tal que su lmite de transmisin no sea excedido.
Bij ( i j )

(8)

Esta condicin puede formularse como

Pij Bij ( i j ) Pij

(9)

donde Pij 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, ,p puede fijarse j el valor de un ngulo g arbitrario a 0, , y tomarlo como origen. g . Es decir, para un bus arbitrario k:
k = 0
(10)

Una consecuencia que se deriva de esta posibilidad de fijar arbitrariamente un 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, ,q que no 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:
P i pi Pi

(11)

donde pi es la potencia producida por el generador i, y P i y P i son constantes positivas que representan, respectivamente, el mnimo y el mximo de las potencias generadas por el generador i.

En todo bus, la potencia que entra debe ser igual a la potencia que sale (ley de la conservacin de la energa), que puede escribirse como
j i

Bij ( i j ) + pi = Di ; i

(12)

donde i es el conjunto de buses conectados a travs de las lneas al bus i y Di la demanda asociada al bus i. Como se ha indicado anteriormente, la potencia transmitida a travs de toda lnea es limitada, por tanto
P ij Bij ( i j ) P ij , j i , i
(13)

1. Datos

n: el nmero de g generadores. P i: la mnima energa de salida asociada al generador i. P i: la mxima energa de salida asociada al generador i. Bij: la susceptancia p de la lnea i-j. j P ij : la capacidad mxima de transmisin de la lnea i-j. Ci: el coste de producir energa en el generador i. i i : el conjunto de buses conectados a travs de lneas al bus i. Di: la demanda asociada al bus i.

2. Variables

pi: la energa g p producida p por el g generador i.

i : el ngulo del bus i.

3. Restricciones: Las restricciones de este problema son

k = 0
j i

Bij ( i j ) + Pi = Di ; i = 1,2,.., n
Pi min pi Pi max; i = 1,2,..., n

(14)

Pijj max Bijj ( i j ) Pijj max; j i ; i = 1,2,..., n

4. Funcin a minimizar: El objetivo es minimizar el precio total de la

produccin d de d potencia

Z = Ci pi
i =1

(15)

donde Ci es el precio de la produccin del generador i, y n el nmero de generadores.

Ejemplo El Problema de Distribucin de Energa: Considrese el sistema de la figura 4.

Figura 4. Esquema del problema de Distribucin de Energa.

El generador del bus 1 produce un coste 6 y sus lmites inferiores y superiores son, respectivamente, 0.15 y 0.6. El coste de produccin del generador del bus 2 es 7 y sus lmites de potencia son, respectivamente, 0.1 y 0.4. La lnea 1-2 tiene una susceptancia 2.5 y un lmite de transmisin mximo de 0.3, la lnea 1-3 tiene una susceptancia de 3.5 y un lmite de transmisin de 0.5, y, finalmente, la lnea 23 tiene una susceptancia de 3.0 3 0 y un lmite de transmisin de 0.4. 0 4 Este sistema tiene una demanda simple localizada en el bus 3 con un valor de 0.85. Se considera un periodo de una hora, y se toma como origen el bus 3.

Este problema puede escribirse como: minimizar sometido a

6 p1 + 7 p2

3 = 0 3.5( 3 1 ) + 2.5( 2 1 ) + p1 = 0 3.0( 3 2 ) + 2.5(1 2 ) + p2 = 0 3.5(1 3 ) + 3.0( 2 3 ) = 0.85

0.15 P 1 0.6 0.10 P2 0.4

0.3 2.5(1 2 ) 0.3 0.4 3.0( 2 3 ) 0.4 0.5 3.5(1 3 ) 0.5

Las variables de optimizacin p son p1, p2, 1 y 2 . La solucin de este problema es:
Z = 5.385, p = (0.565,0.285) T , = (-0.143,-0.117,0) T

La solucin L l i ptima ti requiere i que el l generador d 1 produzca d 0 565 y el 0.565 l generador d 2 produzca 0.285.

Programacin Lineal Entera-Mixta

Problema de Identificacin de Sntomas Relevantes

S = {S1 , S2 ,..., Sm }. Considrese que se requiere identificar un nmero mnimo de sntomas S a S , de tal manera q que cada enfermedad p puede distinguirse g

Sea D = { D1 , D2 ,..., Dn } un conjunto conocido de posibles enfermedades. Considrese q que los mdicos, , al identificar las enfermedades asociadas a un conjunto de pacientes, basan su decisin normalmente en un conjunto de sntomas

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 g a un costo mnimo de diagnstico. g
1. Datos

D: el conjunto j de enfermedades. S: Conjunto de sntomas. n: nmero de enfermedades m: nmero de d sntomas

cij: el nivel del sntoma j asociado a la enfermedad i. dikj: nivel de discrepancia entre las enfermedades i y k debido al sntoma j. j a: nivel mnimo requerido de discrepancia.
2. Variables

1 si el sntoma j pertenece a Sa xj = 0 si no pertenece

3. Restricciones

El l subconjunto b d Sa debe de d b ser suficiente f para distinguir d claramente l todas d las l enfermedades:

x j dikj a; i, k {1, 2,..., n} , i k

j =1

Donde

1 si cij ckj dikj = i cij = ckj 0 si

mide la discrepancia entre las enfermedades Di y Dk en trminos de los sntomas

incluidos en Sa, y a>0 es el nivel de discrepancia deseado. Se debe tener en cuenta que a medida q q que el valor de a es mayor, y , mayor y ser el nmero de sntomas requeridos, entonces:

x j dikj
j =1

coincide con el nmero de sntomas en S0 que toman distintos valores para las enfermedades Di y Dk, y a es el nmero mnimo, p para cualquier q par (Di,Dk) de p enfermedades, necesario para tener un subconjunto aceptable Sa, lo que quiere decir que pueden desconocerse a-1 sntomas.
4. Funcin a minimizar

El objetivo es minimizar el nmero de sntomas seleccionados:

Z = xj
j =1 m

Sin embargo, si las enfermedades han de identificarse con alguna carencia de informacin, el conjunto S0 puede resultar inservible, por tanto, normalmente se emplea un valor a>0.

Para determinar los sntomas relevantes asociados a la enfermedad i tenemos: Minimizar Sujeto a
m

Z = xj
j =1

x j dikj > a; k {1, 2,..., n} , i k

j =1

S ai S De esta manera p podemos determinar el subconjunto j mnimo del conjunto j

de manera que la enfermedad i tenga sntomas diferentes comparada con el resto de enfermedades.

Ejemplo El Problema de Identificacin de Sntomas Relevantes:

Considrese el conjunto j de enfermedades D = { D1 , D2 , D3 , D4 , D5 } y el conjunto j de sntomas S = {S1 , S2 ,..., S8 }. 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:

Tabla 3. Sntomas asociados a todas las enfermedades.

Tabla 4. Sntomas relevantes a cada enfermedad, para a=1.

Por tanto, minimizando la suma:

Z = xj
j =1 m

Sujeto a las restricciones mostradas anteriormente, y dos valores de a, se concluye que el l conjunto j d sntomas de

{2,5}

es un subconjunto mnimo y suficiente de sntomas que permite distinguir las cinco enfermedades. Sin embargo, si se emplea un nivel de discrepancia de a=3, el conjunto mnimo requerido es

{1, 2, 4,5,7}

Hay que tener en cuenta, que en este caso es posible hacer un diagnstico correcto an en la ausencia de dos sntomas.

Problema del Horario Acadmico

El objetivo es asociar aulas y horas a las asignaturas de un programa acadmico dividido en cursos. Se considera q que estn disponibles p nc aulas y nh horas, , respectivamente, para ensear ns asignaturas. Estas asignaturas estn agrupadas por: (1) Cursos y (2) profesores. Los ndices s, c, h, i, y b indican respectivamente asignatura, clase, hora, profesor y bloque.
1. Datos

nc: nmero de aulas. nh: nmero de horas. ns: nmero de asignaturas. ni: nmero de d asignatura que h ha d de impartir el l profesor f i. nb: nmero de cursos. : conjunto de todas las asignaturas. g i: conjunto de asignaturas que ha de impartir el profesor i. b: conjunto de asignaturas del curso b.

2. Variables

v(s c h): variable binaria que toma el valor 1 si la asignatura s se imparte en el aula v(s,c,h): c a la hora h, y 0 en otro caso.
3. Restricciones a.

Cada profesor imparte todas sus asignaturas:

si c =1 h =1

v( s, c, h) = ni ; i

nc nh

b.

Cada d profesor f imparte mximo una asignatura cada d hora: h

si c =1

v( s, c, h) 1; h, i

nc

c.

Cada asignatura se imparte una sola vez:

v( s, c, h) = 1; s
c =1 h =1

nc nh

d.

En cada clase y hora se imparte mximo una sola asignatura:

s

v( s, c, h) 1; c, h

e.

En cada hora, se ensea como mximo una asignatura en cada curso:

sb c =1

v( s, c, h) 1; h, b

nc

4. Funcin a Optimizar

Hay diferentes df opciones de d funcin f objetivo b a minimizar. En este caso se escogi la l funcin objetivo que busca obtener un horario compacto: Minimizar
s c =1 h =1

(c + h ) v ( s , c, h )

nc nh

Sujeto a las restricciones ya mencionadas. mencionadas Se eligi esta funcin objetivo dado que penaliza el que las variables v(s,c,h) tomen el valor 1 para valores elevados de c y h. Por tanto, su objetivo es compactar el horario.

Ejemplo El Problema del Horario Acadmico

Considrese 3 aulas, , 5 horas, , 8 asignaturas, g ,2p profesores, , y 2 cursos. El conjunto j de todas las asignaturas es = {S1 , S2 ,..., S8 } , el conjunto de las asignaturas del profesor 1 es 1 = {S1 , S2 , S8 } , el conjunto de las asignaturas del profesor 2 es Y el conjunto de las asignaturas del curso 2 es 2 = {S5 , S6 , S7 , S8 } . Se debe tener en cuenta que 1 2 = y 1 2 = , y 12 = y 1 2 = . La solucin se muestra en la siguiente tabla: j de asignaturas g del curso 1 es 1 = {S1 , S2 , S3 , S4 }, 2 = {S3 , S4 , S5 , S6 , S7 }, el conjunto

Tabla 5. Sntomas asociados a todas las enfermedades.

El horario para el profesor 1 es:

El horario para el profesor 2 es:

El horario para el curso 1 es:

El horario para el curso 2 es:

Problema de Localizacin de Plantas Productivas

Se trata de elegir la localizacin de plantas entre un conjunto dado de posibles localizaciones, , teniendo en cuenta las necesidades de los consumidores y optimizando algn criterio econmico. Normalmente, la construccin de una planta origina un costo importante que no depende del nivel de produccin de esa planta.

Figura 5. Localizacin de plantas con capacidad limitada.

1. Datos

I: conjunto {1,..., n} de n consumidores. J: conjunto {1,..., m} de m lugares donde las plantas pueden ser construidas. fj: costo fijo de construccin de la planta localizada en j para j J. cij: beneficio unitario por venta al consumidor i, de bienes producidos en la planta j uj: la capacidad productiva de la planta localizada en j. bi: la demanda del consumidor i.
2. Variables

yj: variable binaria que permite modelar la construccin de una planta productiva en la localizacin j.
1 si se construye la planta productiva j yj = 0 en otro caso

xij: cantidad de producto enviada desde la planta j al consumidor i.

3. Restricciones

Las restricciones de este p problema son las siguientes. g Ha de satisfacerse la demanda de cada consumidor:

xij = bi ; i I
jJ

Dado que al consumidor i no se le puede suministrar desde j a no ser que se haya construido una central en j, tenemos que:

xij u j y j ; j J
iI

Dado que yj=0 implica que xijj=0,i y yj=1 da lugar g a la restriccin iI xij u j , que implica que la produccin de la planta j no puede exceder su capacidad mxima. Adems, las restricciones sobre las variables son:
y j {0,1 0 1} ; j J xij 0; i I , j J
4. Funcin a Optimizar

maximizar

Z = cij xij f j y j
iI jJ jJ

Ejemplo El Problema de Localizacin de Plantas Industriales

Una empresa p considera la construccin de p plantas p productivas p para 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 para las 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 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 sujeto j a las restricciones p pertinentes: Maximizar Sujeto a
Z = cij xij 10 y j
i =1 j =1 j =1
7 6 6

x1 j = 1.5; x2 j = 2.0
j =1 6 j =1 6

x3 j = 3.0; x4 j = 4.0
j =1 6 j =1 6

2 5; x6 j = 1.0 10 x5 j = 2.5;
j =1 6 j =1

x7 j = 2.0
j =1

xij 6 y j ; j = 1,...,7
i =1

y j {0,1} ; j = 1,...,6

xij 0; i = 1,...,7; j = 1,...,6

El primer i grupo de d restricciones i i corresponde d a las l restricciones i i d demanda de d d y el l 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 L2, L4 y 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.

Problema de Programacin de Centrales Termo-Elctricas

El costo de poner en funcionamiento una central trmica despus de haber estado parada un p p par de das es muy y elevado, ,p por lo q que la p planificacin de los arranques q y paradas debe hacerse con cuidado. El problema de programacin horaria de centrales trmicas consiste en determinar p para un horizonte de p planificacin multi-horario, , el arranque q yp parada 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 periodos:
k = 1, 2,..., K

Donde K es tpicamente igual a 24. 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 siguiente forma:
C j y jk

donde Cj es el costo de arranque de la central j e yjk es una variable binaria que toma el valor de 1 si la central j se arranca al comienzo del p periodo k y 0, , en otro caso. El costo de parada puede expresarse de forma anloga al costo de arranque:
E j z jk

donde Ej es el costo de parada de la central j y zjk es una variable binaria que toma el valor de 1 si la central j se para al comienzo del periodo k, y 0 en otro caso. El costo de funcionamiento esta constituido por un costo fijo y un costo variable. El costo fijo se puede expresar como:
A j v jk

donde Aj es el costo fijo de la central j y vjk es una variable binaria que toma el valor periodo k, y 0 en otro caso. de 1 si la central j esta en funcionamiento durante el p

El costo variable puede considerarse proporcional a la produccin en la central:

B j p jk

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 mnima ni por encima de una produccin mxima. Esta restriccin se puede escribir como:
Pj v jk p jk Pj v jk

donde Pj y Pj son respectivamente las producciones mnima y mxima de la central j. Al pasar de un periodo de tiempo al siguiente, cualquier central trmica no puede incrementar su produccin por encima de un mximo, denominado rampa mxima de subida de carga. Esta restriccin se puede expresar como:
p jk +1 p jk S j

donde Sj es la rampa mxima de subida de carga de la central j.

Para el primer periodo del horizonte de planificacin las restricciones previas tienen la siguiente forma:
p j1 Pj0 S j

donde Pj0 es la produccin de la central j en el periodo previo al comienzo del horizonte de p planificacin. Anlogamente, ninguna central puede bajar su produccin por encima de un mximo, que se denomina rampa mxima de bajada de carga:
p jk p jk +1 T j

Donde Tj es la rampa mxima de bajada de la central j. Para el primer periodo del horizonte de planificacin la restriccin anterior toma l forma: la f
p0 j p j1 T j

Cualquier q central q que esta funcionando p puede p pararse p pero no arrancarse y cualquier central parada puede arrancarse pero no pararse. Esto se expresa de la siguiente manera:
y jjk z jk j = v jk j v jk j 1

Para el primer periodo la restriccin anterior se convierte en:

y j1 z j1 = v j1 V j0

donde V j0 es una variable binaria que toma el valor de 1 si la central j esta en funcionamiento en el periodo anterior al primero del horizonte de planificacin, y 0 en otro caso. La demanda debe suministrarse en cada periodo, por lo tanto:

p jk = Dk
j =1

donde J es el nmero de centrales y Dk la demanda en el periodo k. 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:

Pj v jk Dk + Rk
j =1

Donde D d Rk es la l cantidad tid d requerida id de d reserva (por ( encima i de d la l demanda) d d ) en el l periodo k.

1. Datos

K: nmero de p periodos de tiempo p q que tiene el horizonte temporal p Cj : costo de arranque de la central j. Ej: costo de parada de la central j. Aj: costo fij fijo d de l la central l j. Bj: costo variable de la central j.
Pj : produccin mnima de la central j. Pj : produccin mxima de la central j.

Sj: rampa mxima de subida de carga de la central j.

Pj0 : produccin de la central j en el periodo anterior al del comienzo del horizonte

de planificacin.

Tj: rampa mxima de bajada de carga de la central j.

V j0 :constante binaria que toma el valor de 1 si la central j esta funcionando en el

periodo previo al comienzo del horizonte de planificacin, y 0 en otro caso.

J: nmero de centrales de produccin. Dk: demanda en el periodo k. Rk: reserva requerida en el periodo k.

2. Variables

yjk: variable binaria q que toma el valor 1, , si la central j 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 periodo k, y 0 en otro caso. p vjk: variable binaria que toma el valor 1, si la central j esta en funcionamiento durante el periodo k, y 0 en otro caso. pjk: produccin de la central j durante el periodo k. k
3. Restricciones

Cualquier central debe funcionar por encima de su produccin mnima y por debajo de su produccin mxima, por lo tanto:
Pj v jk p jk Pj v jk ; j , k

Las restricciones de rampa de subida deben satisfacerse:

0 donde p j 0 = Pj .

p jk +1 p jk S j ; j , k = 0,..., K 1

Las restricciones de rampa de bajada son:

p jk p jk +1 T j ; j , k = 0,..., 0 K 1

La lgica de cambio de estado (de arranque a parada y viceversa) ha de preservarse, por lo tanto:
y jk z jk = v jk v jk 1; j , k = 1,..., K
0 donde v j 0 = V j ; j.

La demanda ha de satisfacerse en cada periodo, por lo tanto:

p jk = Dk ; k
j =1

Finalmente y por razones de seguridad, la reserva ha de mantenerse en todos los periodos:

Pj v jk Dk + Rk ; k
j =1

4. Funcin a Optimizar

Minimizar

Z = A j v jk + B j p jk + C j y jk + E j z jk
k =1 j =1

Ejemplo El Problema de Programacin de Centrales TermoElctricas

Se considera un horizonte de planificacin de 3 horas. Las demandas en esas horas son respectivamente 150, 500 y 400. Las reservas son respectivamente 15, 50 y 40. 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:

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 1y yp permanece acoplada p durante 3 horas. La central 2 se arranca al comienzo de 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.

Programacin No-Lineal

Problema del Paquete Postal

Un paquete postal es una caja de dimensiones x, y, y z (como la figura), que debe verificar los siguientes requisitos para ser aceptado en la oficina de correos: La altura mas el permetro de la base no puede exceder 108 cm
z + 2 x + 2 y 108; x, y, z 0

Pues no son posibles las longitudes negativas. Se buscan las tres dimensiones que maximizan el volumen
V ( x, y, z ) = xyz

Problema del Cantilever

Se desea disear un cantilever de seccin rectangular y longitud dada para conseguir peso mnimo, mnimo y a la vez asegurar una deformacin mxima transversal bajo la accin de una carga vertical actuando en el extremo libre. El material para construirlo tiene un peso especfico conocido. Sean x e y el ancho y la altura que se buscan. Sean L, F, S, y , la longitud, la carga en el extremo libre, la deformacin mxima permitida, y el peso especfico, respectivamente es decir, respectivamente, decir el conjunto de datos del problema. problema El objetivo es minimizar el peso:
W ( x, y ) = Lxy

Como el ancho x debe ser mayor que 0.5 y, de acuerdo con la teora de resistencia de materiales, la deformacin en el extremo libre viene dada por:
FL3 / 3EI

donde E es el mdulo deYoung del material del cantilever, cantilever e

I = xy 3 / 12

es el correspondiente momento de inercia de la seccin rectangular, se tiene que minimizar W(x,y) bajo las restricciones:
4 FL3 Exy 3 x x, y
S 0.5 0

Bibliografa
Formulacin Formulacin y Resolucin de Modelos de Programacin Matemtica en Ingeniera y

Ciencia, Enrique Castillo, Antonio J. Conejo, Pablo Pedregal, Ricardo Garca, Natalia Alguacil, 2002.