Download Trabajo Dirigido #1 - U

FACULTAD CS. FÍSICAS Y MATEMÁTICAS
UNIVERSIDAD DE CHILE
MA37A Optimización. Semestre Otoño 2008
Profesor: Héctor Ramı́rez C. Auxiliares: Omar Larre, Oscar Peredo.
Trabajo Dirigido #1
P1. (Problema de la Mochila (o Knapsack)) Se intenta llenar una mochila de volumen fijo V con n items cada
uno de volumen vi y donde a cada item se le asocia un factor de necesidad ai , es decir, si ai > aj significa
que el item i-ésimo es más necesario que el j-ésimo. Plantee el problema para maximizar la cantidad de items
necesarios (pueden haber uno o mas items del mismo tipo y no pueden haber ”trozos”de algun item).
P2. (Sumar N primeros números) Se tienen N números c1 , ..., cN cuyo orden es cσ(1) ≤ ... ≤ cσ(N ) . Encontrar el
K
X
valor de
cσ(i) , con K ≤ N .
i=1
P3. (Carga transportada en un container) Se desea maximizar la carga transportada dentro de un container.
Tenemos cinco tipos de materiales distintos (A,B,C,D y E), cuyos pesos y volúmenes totales son los siguientes:
tipo
A
B
C
D
E
peso [kg]
1
2
8
2
5
volumen [m3 ]
3
3
4
4
2
Debe saber que la principal restricción concierne la capacidad del container dada por 7m3 .
¿ Que fracción del total de cada material irá en el container?
P4. (Programación de horarios)Un hospital planea hacer horarios nocturnos semanales para las enfermeras. Cada
dı́a se requieren Di enfermeras y cada enfermera puede trabajar 5 dias seguidos. Encuentre el número mı́nimo
de enfermeras que se necesita contratar.
P5. (Planificación Minera) Una mina de cobre esta compuesta por N secciones. Cada sección tiene un peso total de
Wi y un peso wi de cobre dentro de la sección (con i el ı́ndice de la sección). La cantidad total (en toneladas de
peso) que se puede extraer de la mina es Ct (W ) (de peso total) y Ct (w) (de peso en cobre) en cada perı́odo t.
Además, se sabe el beneficio bi (en millones de pesos) de cada seccion. Plantee un modelo lineal para calcular
la extracción de las secciones en T perı́odos, maximizando el beneficio total.
P6. (Problema de Producción)Considere una fábrica con 3 tipos de maquinas A,B y C que pueden producir 4
productos (cada producto debe pasar por las 3 maquinas, y ellas funcionan en forma continua). Suponga
además que el tiempo para ajustar las maquinas entre cambios de productos es despreciable.
Debe tener en cuenta la cantidad de productos generados por cada maquina, las ganancias y los tiempos de
uso siguientes::
Tipo de máquina
A
B
C
$
P1
1,5
1
1,5
5,24
P2
1
5
3
7,3
P3
2,4
1
3,5
8,34
1
P4
1
3,5
1
4,18
Tiempo total disponible (horas)
2000
8000
5000
Plantee el problema de producción semanal que maximiza ganacias.
P7. Computadores Bell produce dos tipos de productos: notebooks y desktops. Con el fin de maximizar las ganancias
de la empresa, computadores Bell le pide a usted que planifique la producción de este mes de la compañia usando
programación lineal.
El proceso productivo es bastante complejo, para simplificarlo sólo consideraremos las siguientes restricciones:
(i) Cada computador requiere un chip procesador, y se cuenta con sólo 10000 chips de este tipo.
(ii) Cada computador requiere memoria RAM. Esta viene en chips de 512MB. Un notebook se vende con
512MB de memoria RAM instalada (es decir un sólo chip), mientras que un desktop se vende con 1024MB
de memoria RAM (es decir dos chips). Gracias a un excelente negocio se cuenta con un stock de 15000
chips.
(iii) Cada computador requiere cierto tiempo para su armado. Dadas sus arquitecturas, un notebook necesita
4 minutos mientras que un desktop necesita 3 minutos de armado. Computadores Bell cuenta con 25000
minutos disponibles para armado durante el próximo mes.
Finalmente, dada las actuales condiciones del mercado, cada notebook producido genera una ganancia de
$300000, mientras que cada desktop producido genera una ganancia de $400000.
Resuelva este problema usando resolución gráfica y responda: ¿Cuántos notebooks y desktops se producirán en
el mes? ¿Cuál es la ganancia máxima que puede tener computadores Bell?
P8. Resuelva gráficamente el siguiente problema lineal:
máx x + 2y sujeto a x + y ≤ 10, 3x + y ≤ 20, x − y ≥ 4, x ≥ 0, y ≥ 0
2