Universidad de Chile MA3701-1 2014/03Facultad de Cs. Fsicas y Matematicas Profesor: Mauricio Soto, Natacha AstromujoffDepartamento de Ingeniera Matematica

1. Problemas de modelacion

1.1. El problema de la dieta

En una granja de cerdos, un granjero tiene diferentes cuatro tipos de alimentos con diferentes aportes denutrientes. Los precios diarios y los requerimientos mnimos se muestran en la tabla siguiente:

Maiz Alfalfa Avena Frijones requeridoProteina 1.5 2.0 1.0 4.1 4.0Calorias 1.0 3.1 0 2.0 8.0

Grasa 4.2 1.5 5.6 1.1 9.5Costo 5 7 7 9

Que cantidades de cada alimento debe comprar el granjero de tal manera de minimizar el costo y satisfacer lasnecesidades nutricionales de los cerdos?

1.2. Problema de la mochila (Knapsack)

Se intenta llenar una mochila de volumen fijo V con n items cada uno de volumen vi y donde a cada item sele asocia un factor de valor ai , es decir, si ai > aj significa que el tem i-esimo es mas valioso que el j-esimo.Calcule la seleccion de mayor valor para los siguientes tems suponiendo que puede cargar hasta 170 litros en lamochila y que es posible transportar una fraccion de un tem. Como cambia su solucion si los tems no puedendividirse?

Volumen 41 50 49 59 55 57 60Valor 442 525 511 593 546 564 617

Suponga que es posible transportar una fraccion de un tem. Plantee el problema para maximizar la cantidadde items necesarios (pueden haber uno o mas items del mismo tipo y no pueden haber trozos de algun item).

1.3. Programacion de horarios

Un hospital debe planear los horarios nocturnos semanales para las enfermeras. Cada enfermera puede trabajar5 das seguidos. Encuentre el numero mnimo de enfermeras que se necesita contratar si las demandas por nocheson las que se muestran en la tabla siguiente.

Da Lun Mar Mie Jue Vie Sab DomDemanda 15 12 20 25 30 15 10

1.4. Problema de transporte

Se tienen m plantas productoras y n bodegas. La planta i-eesima genera una cantidad si de productos y labodega j-esima puede almacenar dj productos. El costo de transportar un producto desde la planta i hastala bodega j es de cij . Encontrar el numero de productos que se deben enviar a cada bodega, de modo que seminimize el costo de transporte.

1.5. Planificacion energetica

El gobierno del pas Lechi le ha pedido realizar el plan energetico para los proximos T anos. Los expertos delgobierno afirman (con mucha seguridad) que la demanda de electricidad de dt megawatts durante los anost = 1, ..., T . La capacidad existente, basada en plantas de carbon no puede ser retirada por motivos que usteddesconoce con un valor de et megawatts para el ano t. Existen dos alternativas para expandir la capacidad:plantas hidroelectricas y plantas nucleares. El costo anual por megawatt para las plantas hidroelectricas quecomenzaron a operar en el ano t es de ct millones de dolares; mientras que el mismo costo para las plantasnucleares es de nt millones de dolares. Por razones ambientales, se ha decidido que no mas del 20 % de lacapacidad energetica total debe ser de origen nuclear. Una planta hidroelectrica opera por 20 anos, mientrasque una planta nuclear puede operar por 15 anos. Modele el problema que permita obtener un plan de expansionenergetica de costo mnimo.

The first step in formulating this problem as a linear programming problem is to define the decision variables.Let xt and yt be the amount of coal respectively, nuclear capacity brought on line at the beginning of year t. Letwt and zt be the total coal respectively, nuclear capacity available in year t. The cost of a capacity expansionplan is therefore,

Tt=1

ctxt + ntyt.

Since coal-fired plants last for 20 years, we have

wt =

ts=max{1,t19}

xs t = 1, . . . , T.

Similarly, for nuclear power plants,

zt =

ts=max{1,t14}

ys t = 1, . . . , T.

Since the available capacity must meet the forecasted demand, we require

wt + zt + et dt t = 1, ..., T.

Finally, since no more than 20 % of the total capacity should ever be nuclear,

ztwt + zt + et

0,2

1.6. Cutting Stock Problem

A manufacturer of metal sheets produces rolls of standard fixed width w and of standard length `. A large orderis placed by a customer who needs sheets of width w and varying lengths. In particular, bt sheets with length`i and width w for i = 1, ...,m are ordered. The manufacturer would like to cut the standard rolls in such away as to satisfy the order and to minimize the waste. Because scrap pieces are useless to the manufacturer,the objective is to minimize the number of rolls needed to satisfy the order. Given a standard sheet of length`, there are many ways of cutting it. Each such way is called a cutting pattern. The jth cutting pattern ischaracterized by the column vector aj where the ith component of aj namely aij , is a nonnegative integerdenoting the number of sheets of length `i in they jth pattern. For instance, suppose that the standard sheetshave length ` = 10 meters and that sheets of lengths 1.5, 2.5, 3.0, and 4.0 meters are needed. The following aretypical cutting patterns:

a1 = (3, 2, 0, 0)t

a2 = (0, 4, 0, 0)t

a3 = (0, 0, 3, 0)t . . .

Note that the vector a represents a cutting pattern if and only if

i aij ` and each aij is a nonnegativeinteger. The number of cutting patterns n is finite. If we let xj be the number of standard rolls cut accordingto theyth pattern, the problem can be formulated as follows: Minimize

mn

nj=1

xj

subject to

nj=1

aijxj bi,

xj 0 j = 1, . . . , n,xj N j = 1, . . . , n.