UNIVERSIDAD DE CHILEFACULTAD DE ECONOMA Y NEGOCIOSDepartamento de Control de Gestin y Sistemas de Informacin

Gua #1 : Modelamiento Matemtico para la Programacin de Decisiones

La razn prncipal por la total falta de inters por optimizar antes de 1947, fue debido a la imposibilidad de hacergrandes clculos computacionales1

Lo que hoy se conoce como Programacin Lineal se inicia como una rama de la Optimizacin poco antes de1950 como resultado de los trabajos realizados por George Dantzig, en la Fuerza Area de los EE.UU. durantela Segunda Guerra Mundial. Dantzig desarroll mtodos para organizar y planificar horarios de entrenamiento,abastecimientos logsticos y otras necesidades militares. Este tipo de problemas, que se encuentran de formaabundante en la ingeniera, se clasifican dentro de una gran clase de problemas en los que el objetivo es elegirentre varias, y potencialmente infinitas, alternativas posibles aquella que permita obtener el mejor beneficioposible. El clculo de la mejor alternativa se conoce como Optimizacin Matemtica y es una herramientacontempornea que apoya eficazmente la Toma de Decisiones en los grandes sistemas de la ingeniera.

En este curso nos concentramos especficamente en una rama particularde la Optimizacin Matemtica, aquella que est definida por sistemaslineales. Previo a los trabajos realizados por Dantzig, existen algunasreferencias sobre sistemas de desigualdades lineales desarrolladas porFourier en 1823, Gauss en 1826, Pareto en 1906 y Valle Poussin en 1911,entre otras. Sin embargo los trabajos precursores de la ProgramacinLineal son aquellos de Leontief en 1936, sobre un modelo econmico; deKantorovich en 1939, relacionado con la asignacin ptima de recursosescasos; y el de Hitchcok en 1941 sobre problemas de transporte.Gracias a los desarrollos de Dantzig, como veremos en la siguientes guasde este curso, se logra resolver numricamente un tipo de problemas quedebido a su tamao y complejidad no haban sido abordados previamen-te. Figura 1: George Dantzig

El objetivo de esta gua es definir algunos conceptos bsicos y dar a conocer los conceptos iniciales, queaproximarn al lector a los fundamentos de la modelacin matemtica a travs de sistemas lineales.

Optimizacin Matemtica

Entendemos como Optimizacin al modelamiento conjunto de tres elementos:

1. un vector de variables de decisin x Rn, cuyo valor debe determinarse,2. un valor objetivo f(x) R que deseamos llevar a un valor ideal a travs de estas variables, y3. un conjunto o regin factible S Rn que describe los posibles valores de las variables de desicin.

Un problema de optimizacin se escribe como

(P)

mn f(x)

s.a

x So bien (Q)

max f(x)

s.a

x SEn estos ejemplos las letras (P) (Q) denotan el nombre que recibe el problema y se leen P corresponde aminimizar el valor f(x) sujeto a que x est en S y Q corresponde a maximizar el valor f(x) sujeto a que xest en S. Las variables de decisin son mudas2.

1George B Dantzig, History of Mathematical Programming.2No dependen de la letra que se use para denotarlas, como en las integrales.

1

Existe amplia literatura respecto a la resolucin de problemas de optimizacin dependiendo de las caracters-ticas de f y S. En este curso, slo nos preocuparemos de problemas en donde f es una funcin lineal y S sedescribe a travs de un sistema de inecuaciones lineales. Ms adelante revisaremos en detalle estos conceptos.A la rama de la matemtica que estudia este tipo particular de problemas se le conoce como ProgramacinLineal.

Un problema de optimizacin puede:

1. Ser infactible, cuando S =

2. Ser no acotado, cuando no es posible elegir la mejor alternativa, es decir

M R x S tal que f(x) M (mn) f(x) M (max)

Para cualquier nmero que elijamos, existe una decisin posible cuyo valor es mejor que aquel nmeroelegido. Si elegimos otro mejor an, el argumento se repite.

3. Tener una o infinitas soluciones. Una solucin es un vector x S que cumple

y S f(x) f(y) (mn) f(x) f(y) (max)

el vector x es solucin si cualquier otra decisin posible es peor o igual que l

A x le llamaremos ptimo y a f(x) le llamaremos valor ptimo. Est ltima alternativa indica quesi ya conocemos al menos dos soluciones para un problema, entonces debe tener infinitas soluciones.

Dada una regin factible S, llamaremos vector factible a cualquier vector x S, esta regin representa todoslos posibles valores que pueden tomar las variables de decisin. Como ya lo mencionamos, en esta oportunidadslo nos preocuparemos de regiones descritas por sistemas lineales de la forma Ax b. En cuanto a la funcinobjetivo, recordemos la siguiente definicin.

DEFINICIN. Funcin Lineal de Rn a R

Una funcin f : Rn R se dice lineal ssi f(x+ y) = f(x) + f(y) x, y Rn R

OBSERVACIN: Siempre podremos asumir3 que f(x) = cT x para algn c Rn.

Un problema de optimizacin tiene dos valores relevantes, su solucin x y el valor de su solucin f(x). Enrelacin a estos valores, es posible definir relaciones con otros problemas similares.

DEFINICIN. Igualdad y Equivalencia de Problemas Cuando dos problemas tienen la misma solucin,se dice que los problemas son equivalentes. Cuando tienen el mismo valor ptimo, se dice que son iguales. Enparticular, para problemas lineales podemos escribir C R y k > 0 las siguientes relaciones

max f(x)

s.a

x S

max kf(x) + C

s.a

x Smax f(x)

s.a

x S= 1

k

mn kf(x)s.a

x S3Este resultado se conoce como Teorema de Riesz.

2

1. Programacin Lineal

Consideremos la siguiente situacin. Un estudiante de FEN desea planificar el tiempo que usar en las dosactividades que debe realizar durante un da laboral, digamos que x1 y x2 representan las horas del da que elestudiante decide ocupar en la actividad 1 y 2 respectivamente, naturalmente se tiene que x1 0 y x2 0. Siel da laboral dura 8 horas y las actividades no se pueden realizar de forma simultnea, entonces x1 + x2 8representa dicha condicin4. Si adems el estudiante debe usar 2 horas ms en la actividad 1 que las destinadasa la actividad 2, entonces se debe cumplir que x1 x2 + 2.En los problemas que veremos en este curso, la regin factible est dada por un conjunto de condicionesdescritas por inecuaciones lineales de la forma Tx con Rn y R , que llamaremos restricciones.Escritas en esta forma vectorial, las posibles estrategias factibles para el estudiante son todos los vectores quecumplen simultaneamente:

(1 1)(x1x2

) 2 ; (1 1)(x1

x2

) 8 ; (1 0)(x1

x2

) 0 ; (0 1)(x1

x2

) 0

Las ltimas dos restricciones restringen los valores de x1 y x2 no por condiciones del problema en particular,sino que por condiciones propias a la naturaleza de los conceptos que se intentan describir. A este tipo derestricciones se le conoce como naturaleza de las variables. Para hacer la escritura ms eficiente, podemosescribir el sistema de desigualdades lineales de forma matricial, en nuestro ejemplo, esto queda:

(1 11 1

)(x1x2

)(2

8

); x 0

OBSERVACIN: Estamos notando al vector de variables como x =(x1x2

).

Formalmente escribimos S = {x R2/Ax b ; x 0} con A =(1 1

1 1

)y b =

(28

).

Si el beneficio que se obtiene al realizar una hora de la actividad 1 es c1 y una hora de la actividad 2 es c2,entonces c1x1 + c2x2 representa el beneficio total que obtiene el estudiante al realizar x1 horas de la actividad1 y x2 horas de la actividad 2. Esto, lo podemos notar vectorialmente como(

c1 c2)(x1

x2

)o bien cTx

A partir de esto, podramos escribir el problema de encontrar una estrategia de actividades que maximice elbeneficio total del estudiante, como un problema de programacin lineal. Se considera como ProgramacinLineal a todos los problemas de la forma

max cTx

s.a

Ax b

con A Mmn, b Rm, c Rn.OBSERVACIN: Comnmente se suele trabajar con variables positivas, as que el problema genrico de Optimizacin Linealpuede considerarse como

max cT xs.a

Ax bx 0

4Al acto de describir matemticamente una condicin de la realidad se le denomina modelar, accin que no tiene relacinalguna con caminar sobre una pasarela.

3

Cuando la naturaleza de las variables slo restringe el valor de las variables a un conjunto de R, se les dicevariables continuas. A c se le llama vector de costos, y a b, vector de recursos. En la literatura, A sueletener el nombre de matriz de coeficientes tecnolgicos.

Revisemos otros ejemplos.

EJEMPLO 1. Problema de Transporte

Consideremos una industria que tiene dos fbricas, una en Santiago y otra en Rancagua. Los productos queestas fbricas producen deben ser enviados a tres destinos: Un punto de venta en Santiago, otro punto de ventaen Via del Mar y a Valparaso para la exportacin de los productos. Se sabe que la demanda diaria de cadapunto de venta es de 5.000 unidades y que se exportan 8.000. Adems, diariamente Santiago puede despachar12.000 unidades y Rancagua 6.000.

El costo de transporte por unidad enviada entre la ciudad i {Santiago-fbrica, Rancagua} y el destinoj {Santiago-venta, Via del Mar, Valparaso} est dado por la cantidad cij conocida.Si se desean planificar los envios de modo tal de minimizar el costo total de transporte es posible modelar unproblema de optimizacin que respresente dicha situacin.

Variables de decisin: la cantidad enviada desde la ciudad i al destino j.

xij definida para todo par i, j posible

Funcin Objetivo: el costo total.mn

ij

cijxij

Restricciones:

Naturaleza de las Variables : xij 0 i, jOferta Santiago : xSfSv + xSfV i + xSfV a 12000Oferta Rancagua : xRSv + xRV i + xRV a 6000

Demanda Santiago : xSfSv + xRSv = 5000Demanda Via del Mar : xSfV i + xRV i = 5000

Demanda Valparaso : xSfV a + xRV a = 8000

EJEMPLO 2. Planificacin de la Produccin

Una fbrica necesita planificar la produccin mensual en el plazo de un ao y para ello considera una demandamensual estimada por dt con t {1, 2, . . . , 12}. La fbrica tiene una bodega que actualmente tiene un stock deb0 unidades.

Los costos de produccin por unidad en cada mes estn dados por ct y el costo de almacenaje A es fijo durantetodo el ao.

Si se desea planificar la produccin de modo tal de minimizar el costo de total de la operacin y manteniendoun stock final conocido b12 es posible modelar un problema de optimizacin que resuelva esta situacin.

Variables de decisin:

1. la cantidad producida en cada mes t.

xt definida para todo t {1, 2, . . . , 12}

4

2. la cantidad almacenada en cada mes t.

bt definida para todo t {1, 2, . . . , 12}

Funcin Objetivo: el costo total, dado por costo total de produccin + costo total de almacenaje.

mnt

ctxt +t

Abt

Restricciones:

Naturaleza de las Variables : xt, bt 0 tOperacin t = 1 : b0 + x1 = d1 + b1Operacin t = 2 : b1 + x2 = d2 + b2Operacin t = 3 : b2 + x3 = d3 + b3

...Operacin t = 11 : b10 + x11 = d11 + b11Operacin t = 12 : b11 + x12 = d12 + b12

Stock Final : b12 = b12

EJEMPLO 3. Problema de la Dieta

Un criador de cerdos necesita definir la cantidad de alimento diaro para cada cerdo, con el fin de satisfacer losrequerimientos nutricionales mnimos segn la regulacin del SAG. Un kilgramo de alimento debe contenercomo mnimo 200[g] de carbohidratos, 180[g] de protenas y 150[g] de vitaminas.

Adems el SAG entrega a los criadores la siguiente carta de nutrientes (en [g]/[Kg]) con los posibles ingre-dientes para el alimento de los cerdos.

NutrientesAlimentos carbohidratos protenas vitaminas

maz 90 30 10cebada 20 80 20alfalfa 40 60 60

El precio del kilo de maz, de cebada y de alfalfa es de $42, $36 y $30 respectivamente.

Si el granjero desea encontrar la receta ms econmica que cumpla con los requerimientos del SAG es posiblemodelar un problema de optimizacin que respresente esta situacin.

Variables de decisin:

1. la cantidad de maz, m.

2. la cantidad de cebada, c.

3. la cantidad de alfalfa, a.

Funcin Objetivo: el costo total,mn 42m+ 36c+ 30a

5

Restricciones:

Naturaleza de las Variables : m, c, a 0carbohidratos : 90m+ 20c+ 40a 200

protenas : 30m+ 80c+ 60a 180vitaminas : 10m+ 20c+ 60a 150

EJEMPLO 4. Problema de la Mochila

:::::Enunciado:::::

Variables de decisin: Volumen del gas i-simo,

xi definida para todo i {1, . . . , N}

Funcin Objetivo: la calidad de la mezcla,

maxi

bixi

Restricciones:

Naturaleza de las Variables : xi 0 iVolumen Mximo :

i

cixi C

2. Programacin Entera

Cuando es necesario tomar decisiones que son enteras, como por ejemplo el nmero de camiones que se debenenviar de un lugar a otro, el nmero de vacas que se deben adquirir para satisfacer la produccin de leche, o elnmero de colegios que se deben construir para poder educar a toda la poblacin, no basta con considerar quela naturaleza de las variables sea positiva, es necesario pedir que la variable sea un nmero entero. La ramade la Optimizacin que se encarga de estos modelos se conoce como Programacin Lineal Entera5.

Un problema genrico de Programacin Entera puede escribirse como

max cTx

s.a

Ax bx 0x Zn

Existen varias metodologas para resolver este tipo de poblemas, entre las ms populares esta el Algoritmo deBranch & Bounds y el procedimiento de planos cortantes de Gomory6.

Veamos algunos ejemplos.

EJEMPLO 5. Problema del Granjero

:::::Enunciado:::::5En ingls, Integer Programming.6Lamentablemente, por motivos de tiempo, este curso no alcanza a abarcar estos mtodos, y quedan pendientes para un

segundo curso de Optimizacin.

6

2.1. Programacin Binaria

Un caso especfico de la optimizacin con variables enteras, es la programacin binaria, esto es, cuando lasdecisiones slo tienen dos opciones, por ejemplo Si o No. Este tipo de decisiones se modela numricamentecon un parmetro que slo toma dos valores, el caso general es que tome valores en {0, 1}.La estructura general de problemas lineales con este tipo de variables es

(P)

max cTx

s.a

Ax bx {0, 1}n

En la ingeniera este tipo de variables tiene un gran nmero de aplicaciones, se utilizan en problemas detransporte, de localizacin, de asignacin, de construccin, de emparejamiento, etc. Veamos un par de ejemplos.

EJEMPLO 6. Problema de Localizacin

:::::Enunciado:::::

EJEMPLO 7. Problemas de Seguridad

:::::Enunciado:::::

3. Programacin Mixta

En este curso, nuestro uso de variables binarias, estar complementado con el uso de variables continuas,permitiendo una modelacin mucho ms flexible. A estos modelos combinados se les conoce como ProgramacinMixta7.

La estructura general de problemas lineales con este tipo de variables es

(P)

max cTx

s.a

Ax+By bx 0y Zn

Veamos un par de ejemplos.

EJEMPLO 8. Problema de Inversin

:::::Enunciado:::::

EJEMPLO 9. Problema de Transporte con varios Camiones

:::::Enunciado:::::

4. Problemas

1. Se desea enviar un producto desde Puerto Montt a Castro. Existen solo 3 empresas de transbordadores:Cruz del Sur y Transmar, que zarpan desde Pargua; y Queilen, que lo hace desde Chaitn. Hay un conveniocon cada una de estas empresas de transporte, de modo que solo se tarifa por el exceso de carga (segnuna capacidad preestablecida por cada empresa de transporte).7En ingls, Mixed Integer Programming

7

Por otro lado, en la isla exiten 4 puertos: Ancud y Chacao, a los cuales se puede llegar navegando desdePargua; y Quelln y Castro, a los que se llega desde Chaitn.

Hay dos limitaciones importantes a considerar:

No se puede acumular el producto en ninguna ciudad, es decir, todo lo que sale desde Puerto Monttdebe llegar a Castro.

Solo tenemos 10 millones de pesos para realizar este proyecto.

Se detallan a continuacin los costos (en millones) del envio de t toneladas del producto,

Transporte Terrestre

Castro Pargua ChaitenAncud 0,9tChacao (t 1)2Quelln 0,2

Puerto Montt 0,4t 0,6 + 0,1t

Transporte Martimo

Par-Anc Par-Chac Chai-Quell CastroCruz del Sur 0,3t+ 0,1 0,2tTransmar 0,3 0,2t+ 0,2Queilen 0,1t 0,6t

Recuerde que solo se tarifa cuando se usa un servicio y cuando hay exceso de carga (segn la siguientetabla).

Empresa CapacidadCruz del Sur 3Transmar 2.8Queilen(Chaiten-Quellon) 2Queilen(Chaiten-Castro) 0

Hacer un esquema (dibujo) de este problema y modelar el problema de maximizar el envo.

2. (con solucin, gracias a Roberto Cortez)

En una cierta fbrica se ha detectado que la actual asignacin de recursos humanos es ineficiente, por loque se le ha encargado a usted la tarea de re-asignar el personal disponible.

En el proceso productivo hay tres tareas:1. Mantencin y operacin de mquinas.2. Clasificacin de los productos.3. Embalaje de los productos.

Adems, el personal disponible se clasifica en tres grupos:1. Personas con capacitacin y experiencia.2. Personas con capacitacin pero sin experiencia.3. Personas sin capacitacin ni experiencia.

Las cantidades de unidades del producto que una persona produce al mes estn dadas por la siguientetabla:

8

tarea \ grupo grupo 1 grupo 2 grupo 3tarea 1 2.000 500 200tarea 2 1.200 1.500 800tarea 3 800 1.000 700

A una persona del grupo 1 se le pagan $1.000, a una del grupo 2 $700 y a una del grupo 3 $350 (al mes,dinero medido en miles de pesos). Adems usted dispone de 20 personas del grupo 1, 50 del grupo 2 y 80del grupo 3 y se le ha dado un presupuesto mensual de $75.000 (tambin medido en miles de pesos). Porltimo, en cada tarea la produccin no puede ser inferior a 40.000 unidades al mes, pues si no se detiene lacadena productiva.

Plantee el problema como uno de optimizacin en que se busca maximizar la produccin.

Solucin: Las variables de decisin son los nmeros de personas de cada grupo asignadas a cada tarea, esdecir:

xij = nmero de personas del grupo i asignadas a la tarea j

La suma de todas las personas asignadas de un mismo grupo no debe ser mayor que la cantidad de gentedisponible de dicho grupo, es decir:

3j=1

x1j 20 ;3

j=1

x2j 50 ;3

j=1

x3j 80

La suma de todas las personas asignadas de todos los grupos, ponderadas por su respectivo sueldo, no debesobrepasar el presupuesto disponible, es decir:

1,000

3j=1

x1j + 700

3j=1

x2j + 350

3j=1

x3j 75,000

La suma por tarea de las personas asignadas, ponderadas por su respectiva productividad, debe ser mayora 40.000, que es la produccin mnima para que no se detenga la cadena productiva, es decir:

2,000x11 + 500x21 + 200x31 40,0001,200x12 + 1,500x22 + 800x32 40,000

800x13 + 1,000x23 + 700x33 40,000No olvidemos imponer positividad de las variables:

xij 0 i, j = 1, 2, 3

La funcin a maximizar es la suma de las personas en cada grupo y en cada tarea, ponderada por laproductividad del segmento respectivo, es decir:

2,000x11 + 500x21 + 200x31 + 1,200x12 + 1,500x22 + 800x32 + 800x13 + 1,000x23 + 700x33

3. (con solucin) Un comerciante debe trasladar en su camioneta tres productos (A,B,C) desde la casa matrizde su negocio hacia una sucursal de venta pasa satisfacer necesidades minimas de stock. Como el fue alumnode Optimizacin, sabe que puede hacerlo de manera ptima respecto al gasto de combustible.

El sabe que el gasto de combustible es directamente proporcional a la carga que tenga la camioneta, pero elcomerciante no tienen ninguna balanza, por lo que decide considerar las densidades indicadas en la etiquetade las cajas.

Al momento de cargar se da cuenta que la camioneta puede alcanzar su capacidad maxima de 100 m3.Como los producto A y B son sustitutos, se necesita al menos 60 unidades entre los dos para la venta

9

en la sucursal. Adems el gobierno restringe viajes de productos orgnicos, por lo que el factor total deproductos de esa naturaleza debe ser de 20.

En la Tabla se indica la densidad de los productos, y el numero de unidades y el factor de elementosorganicos que vienen en una caja de 1 m3 de cada producto.

Producto A Producto B Producto CDensidades kgm3 3 9 12Unidades por caja unm3 2 3 4Factor Prod Organicos f.p.o.m3 0 1 4

Plantee el problema como uno de Optimizacin Lineal.

Solucin: Puesto que lo que queremos es minimizar el consumo de bencina, y este es directamente pro-porcional con el peso, el problema del comerciante es minimizar el peso total, dado por 3x1 + 9x2 + 12x3.

Para respetar la capacidad de la camioneta se debe cumplir que x1 + x2 + x3 100.Para satisfacer las necesidades de la sucursal se debe tener que 2x1 + 3x2 60.Para cumplir con la norma del gobierno se debe cumplir que x2 + 4x3 = 20.

El problema se escribe de la siguiente forma:

(P)

min 3x1 + 9x2 + 12x3s.a

x1 + x2 + x3 1002x1 + 3x2 60x2 + 4x3 = 20

xi 0 i = 1, 2, 3.

4. Se le asignado un monto de $10,000,000 para invertirlos en distintos instrumentos bancarios.

Como posibles instrumentos consideramos 2 tipos de inversiones en renta variable, fondos mutuos y acciones,los cuales rentan un 4% y 5% anualmente, respectivamente, y 1 tipo de inversin en renta fija, el cualrenta un 3%.

Para evitar perdidas inesperadas, causadas por los vaivenes del mercado, se le pide invertir en renta fija almenos un 20% del total invertido en renta variable.

Modele el problema de maximizar las ganancias asociadas a la inversin descrita anteriormente, medianteprogramacin lineal.

5. El ministerio de minera y energa desea realizar un estudio sobre la demanda elctrica de la zona centraldel pas, este tiene por fin el satisfacer las demandas de ese sector al menor costo posible.

Para esto, debe considerar las 4 plantas hidroelctricas ya existentes, llamadas en lo que sigue P1, P2, P3y P4, las cuales distribuyen directamente electricidad a las ciudades de Santiago, Valparaso, Via del Mary Rancagua. La informacin con que se cuenta se resume en la siguiente tabla:

Ciudades Santiago Via del Mar Valparaso RancaguaPlanta Oferta\Demanda 5 3 2 1P1 2 2 1 - -P2 3 1 3 2 -P3 2 2 - 4 3P4 4 4 3 2 1

donde los valores indicados entre una planta y una ciudad dada corresponden a los costos por un millnde Kilowatts/hora transportados ($/MkWh), mientras que las ofertas y demandas dadas se encuentras enmillones de Kilowatts/hora (MkWh).

Modele el problema anterior como un problema de transporte.

10

6. El suministro de gas en Sudamrica es muy complejo, debido a algunos problemas polticos que existen entrelos pases del cono sur, y por el deficit que tendr Argentina en lo aos venideros. Por esto, nuestro pas leha encargado realizar una propuesta para satisfacer nuestra demanda gasfera, al menor costo posible.

Ms precisamente, se le pide asignar la oferta (anual) Boliviana de 7 millones de metros cbicos (Mm3)para satisfacer la demanda de Chile y Argentina, que ascienden a 3 y 4 Mm3, respectivamente. Per, elcuarto pas implicado, produce lo justo para satisfacer su demanda interna, por lo que para nuestros efectosse considera como un nodo de paso (i.e. sin oferta ni demanda). Por razones polticas, no hay posibilidadde enviar gas directamente desde Bolivia a Chile, pero si a travs de Argentina o Per.

Finalmente, los costos ($/Mm3) y las cotas, inferiores y superiores (Mm3), asociados al transporte del gasentre los distintos pases se entregan en la siguiente tabla:

desde\hacia Per Argentina ChileBolivia (3,1,10) (10,0,7) -Per - (2,4,10) (6,0,5)Argentina - - (3,1,2)

Modele el problema anterior como un problema de flujo factible a costo mnimo. (minimizar el costo,cumpliendo con las restricciones).

7. Considere una fbrica con tres tipos de mquinas: A, B y C, que pueden producir cuatro productos: 1, 2, 3 y4. Cada producto debe pasar por alguna operacin en cada uno de los tres tipos de mquina. Suponga quela produccin es continua (i.e. se puede producir una cantidad no necesariamente entera de productos) yque cada producto debe pasar primero por una mquina A, luego por una B y finalmente por una C. Supongaadems que el tiempo requerido para ajustar las mquinas al cambiar de producto es despreciable. La tablasiguiente muestra:

Las horas requeridas en cada tipo de mquina por unidad de cada producto,

El tiempo total disponible por semana por mquina, y

La ganancia por la venta de una unidad de cada producto.

Mquina Prod. 1 Prod. 2 Prod. 3 Prod. 4 T disponibleA 1.5 1 2.4 1 2000B 1 5 1 3.5 8000C 1.5 3 3.5 1 5000

Ganancia 5.24 7.30 8.34 4.18

Se desea determinar la produccin semanal de cada producto que maximiza las ganancias. Plantee elproblema como un problema de programacin lineal.

8. Una fbrica tiene tres bodegas: B1, B2 y B3, donde tiene almacenadas b1, b2 y b3 sillas respectivamen-te. Se tienen adems cuatro puntos de venta: V1, V2, V3 y V4, donde se requieren v1, v2, v3 y v4 sillasrespectivamente. Suponga que es posible enviar sillas desde cualquier bodega a cualquier punto de venta.Considere que el costo de llevar una silla de la bodega Bi al punto de venta Vj es cij . Se desea satisfacer lasdemandas minimizando el costo de transporte. Plantee este problema como un problema de programacinlineal, haciendo las suposiciones que crea necesarias.

Suponga que por problemas con el sindicato de camioneros, no se puede llevar ms que dij sillas desdeBi hasta Vj . Agregue las restricciones correspondientes para incorporar esta situacin al planteamiento delproblema anterior, y deduzca en que pas est la fbrica.

9. Suponga que el productor de un artculo en particular conoce o es capaz de estimar la demanda de suproducto para los prximos n meses. Se desea programar la construccin a lo largo de dichos n meses demodo de minimizar los costos variables totales. Asumiremos que el producto puede ser almacenado durante

11

estos n meses. Habr un costo asociado a mantener una unidad de produccin en inventario durante unmes.

En algunas circunstancias, la sobreproduccin puede ser provechosa, y en otras debe ser evitada. porejemplo, podra ser que si se programa la produccin para satisfacer exactamente la demanda durantealgunos meses, se necesitara mucha sobreproduccin en ciertos meses de demanda especialmente alta. Porotro lado, ciertas cantidades de producto se pueden producir y almacenar en produccin normal durantemeses de baja demanda, para ser almacenados hasta que la demanda exceda la produccin. En otros casospodra ser mejor sobreproducir en ciertos meses e ir almacenando, incluso con una demanda baja, porqueel costo de produccin puede ser menor durante dichos meses, tal vez por cambios de precios de la materiaprima por temporadas u otras razones. El problema est en programar la produccin de modo de balancearlos costos de almacenaje contra los costos de sobreproduccin (horas extra, mquinas, etc), para minimizarel costo variable total.

Plantee el problema como uno de programacin lineal. Considere para estos efectos ci el costo de produciruna unidad en el mes i en jornada normal, el costo di de producir una unidad en el mes i en jornadaextraordinaria, y el costo fi de almacenar una unidad durante el mes i. Se tiene adems como datos ai, lacapacidad de produccin en jornada ordinaria en el mes i, ai, la capacidad de sobreproduccin en el mesi, y bj la cantidad de unidades requeridas en el mes j. El programa lineal debe determinar la produccinque minimize la suma de costos de produccin y almacenamiento. (HINT: Considere como variables xij , elnmero de unidades producidas en jornada ordinaria en el mes i y vendidas en el mes j, e yij , el nmerode unidades producidas en jornada extraordinaria en el mes i y vendidas en el mes j)

10. Escriba un modelo de programacin lineal para determinar una dieta que contenga al menos 0.5% de calciopero no ms de 1.2% del mismo, al menos 22% de protenas y al menos 5% de fibra cruda. Los ingredientesson caliza, maz y soya y los aportes (en Kg.), por cada Kg. de ingrediente son:

Ingrediente Calcio Protenas FibraCaliza 0.35 0 0Maz 0.001 0.09 0.02Soya 0.002 0.5 0.08

Existen dos escenarios posibles para los costos ($/Kg)

Caliza Maz SoyaEscenario A 0.016 0.046 0.125Escenario B 0.018 0.045 0.126

Se debe minimizar el costo por Kg, en el caso ms desfavorable.

11. Escriba un modelo de P.L. para el siguiente problema. La National Free Transportation Agency (NAFTA),debe decidir un programa de formacin y contratacin de nuevas azafatas para los prximos seis meses.

Las exigencias a respetar son expresadas en horas de vuelo de azafatas: 8.000 en enero, 9.000 en febrero,8.000 en marzo, 10.000 en abril, 9.000 en mayo y 12.000 en junio.

La formacin de una nueva azafata dura un mes. Esta formacin comprende 100 horas de vuelo en lneasde la compaia. Estas 100 horas se pueden deducir de exigencias que las azafatas deben cumplir, es decir,sirven para satisfacer las exigencias de horas de vuelo de azafatas de la compaia.

Cada azafata experimentada puede entregar hasta 150 horas de vuelo por mes. La compaia dispone de 60azafatas experimentadas al 1 de enero.

Cada azafata experimentada recibe un sueldo de US$800 por mes, independientemente del nmero de horasque preste servicio. Cada mes, el 10% de las azafatas experimentadas deja su trabajo por diversas razones.

Al cabo de un mes de formacin, que cuesta US$400 a la compaia, una azafata aprendiz se convierte enazafata experimentada.

12

12. Escriba un modelo de P.L. para el siguiente problema. Un granjero posee 100 hectreas (ha.) que puedenser utilizadas para el cultivo de trigo y maz. El rendimiento por ha. es de 60 quintales anuales de trigo yde 95 quintales de maz.

Cualquier fraccin de las 100 ha. puede ser destinada al cultivo de trigo o maz. El trabajo necesario esde 4 hrs. por ha. anuales, ms 0.15 hr. por quintal de trigo y 0.70 hr. por quintal de maz. El costo de lassemillas y abono es de $20 por quintal de trigo y $12 por quintal de maz.

El granjero puede vender su trigo a $175 el quintal y su maz a $95 el quintal. A la compra, le costaranrespectivemente $250 y $150. Puede tambin criar cerdos y pollos. Los vende cuando han alcanzado la edadde 12 meses. Un cerdo se vende a $4.000. Un ave se vende en trminos de cerdo-equivalente (el nmero depollos necesarios para obtener $4.000 al momento de la venta).

Un cerdo requiere 25 quintales de trigo o 20 quintales de maz, a como 25 hrs. de trabajo y 25 m2 deterreno. Un cerdo-equivalente de pollos requiere 25 quintales de maz o 10 quintales de trigo, as como 40hrs. de trabajo y 15 m2 de terreno.

El granjero dispone de 10.000 m2 de terreno para la crianza. Dispone tambin de 2.000 hrs. de trabajoanuales y puede poner a su familia a trabajar, disponiendo as de 2.000 hrs. suplementarias. Puede tambincontratar horas suplementarias de obreros agrcolas al costo de $150 la hora.

Cada hora de obrero agrcola demanda 0.15 hr. de trabajo de supervisin de parte del granjero.

Determine las superficies a destinar al cultivo de trigo y/o maz y las cantidades de cerdos y/o pollos aproducir, de manera de maximizar el beneficio.

Explicite los supuestos usados en la modelacin.

13. Una empresa de arriendo de autos, debe satisfacer la demanda de cuatro ciudades en un cierto da:

Ciudad Autos demandadosA 2B 3C 5D 7

La empresa tiene 3 garages donde guarda sus 18 autos:

Garage Autos disponibles1 62 23 10

Las distancias entre los garages y las ciudades estn dadas por la tabla:

Gar.Ciu. A B C D

1 7 11 3 22 1 6 0 13 9 15 8 5

Encuentre una asignacin de los automviles a las diferentes ciudades, de manera de minimizar la distanciatotal recorrida.

14. Un computador servidor (S) debe transferir 50 archivos a otro remoto (R), por medio de tres computadoresintermedios (1), (2) y (3), cuyos costos de transmisin unitarios y capacidades mximas estn dadas porla tabla siguiente:

13

Arco (S,1) (S,2) (S,3) (1,2) (1,3) (2,3) (1,R) (2,R) (3,R)Costo 1 2 3 5 1 6 8 5 4

Capacidad 20 10 + 10 50 50 + 10 40Plantee este problema como uno de programacin lineal.

15. Considere tres centros de oferta de un cierto producto, con ofertas respectivas de 5, 25 y 25 unidades, ytres centros de demanda, con demandas conocidas de 10, 20 y 15 respectivamente.

Suponga que la matriz de costos de transporte por unidad es:

(cij) =

6 2 14 7 23 1 2

Plantee el problema como un problema de transporte. Es factible? Agregue al problema un centro dedemanda adicional para reparar el problema. Qu puede representar ese centro de demanda? Entregueuna estrategia factible.

16. Suponga usted que juegan Colo-Colo y el grandioso equipo mgicoUniversidad de Chile. Como es inevitableen este tipo de compromisos, aparecen en el estadio los tipicos garreros, que como todo el mundo sabe (Porlo menos quien escribe esto y su novia lo saben) son delincuentes y lumpen por excelencia (Los de Abajo enel fondo son nios buenos). Dada esta situacin de inminente peligro a su seguridad personal, los vecinos delestadio aterrorizados ante esta horda de delincuentes organizan un encuentro con Carabineros a quienes lesplantean su problema: "Necesitamos seguridad para el da del encuentro". Carabineros de Chile entoncesse ve enfrentado al problema siguiente:

Minimizar el nmero de policas a la salida del estadio, considerando que cada cuadra debe ser vigiladadesde una esquina. Para ello contratan los servicios de un profesor de optimizacin de cuyo nombre no meacuerdo ahora, pero de marcadas tendencias azules quien le entrega el problema a unos de sus ayudantescon nombre de instrumento musical y obsesin con el nmero trece (un romntico viajero tambin), el cuala su vez, confiando ciegamente en la pericia de los alumnos lo incluye en una gua de ejercicios propuestos.(Notar la coincidencia).

Indicacin: Considerar el barrio aledao al estadio como un grafo (A,N) en que los nodos son las esquinasy los arcos son las cuadras en cuestin. Cmo cambia el modelo si las esquinas tienen costo es decir, hayque pagar ci por poner un polica en un nodo i y el nmero de policas est limitado por L?

Nota: Lo de carabineros es una historia falsa para hacer ms entretenido el cuento, lo que no quiere decirque el problema ande alejado de la realidad. Este problema se puede complicar ms an si consideramos queaparte de simples carabineros podemos contar con otro tipo de artefactos tales como guanacos, zorrillos,cucas, etc (que naturalmente tienen coberturas y costos distintos).

P.D. Estos problemas son una recopilacin de problemas de varios autores. Agradeciemientos a Hector Ramrez,Roberto Cortez y Charango. Los enunciados han sido escritos textuales del original, para preservar enunciadosmemorables. ,

No olvides que cuando desocupes esta guapuedes donarla en la Feria de Apuntes o

reciclarla.

14

7Esta gua es parte de un apunte (actualmente en borrador) que rene las principales materias del curso Investigacin Operativade la Facultad de Economa y Negocios de la Universidad de Chile. Se reciben comentarios y sugerencias a travs del correorlopezi@fen.uchile.cl. Los tildes an no han sido corregidos en esta versin.

15