ejerciciosprogramacionmatematica2004-05
TRANSCRIPT
1
PROGRAMACIÓN MATEMÁTICA
Licenciatura de Economía Dpto. de Economía Aplicada
Facultad de CC. EE. y Empresariales Universidad de La Laguna
Ejercicios Propuestos
Curso 2004-2005
En realidad todos los que se han esforzado conscientemente por uti-lizar las matemáticas en sus explicaciones han sido recompensados por descubrimientos brillantes... Conviene recordar que si se exami-na la historia del pensamiento económico se verifica que la mayor parte de los progresos importantes han sido realizados por econo-mistas poseedores de una formación matemática más o menos acaba-da. Maurice Allais (1954)
1. El arte de modelizar 1. Producción de mínimo coste Una empresa produce un único bien mediante tres factores pro-ductivos. Debe satisfacer una demanda mínima de su producto de 100 toneladas y tiene que afrontar un coste fijo de medio millón de euros. Los precios de los tres factores productivos son 10, 20 y 30 euros por kilo, respectivamente. La función de producción es de tipo Cobb-Douglas, y su expre-sión es 5.0
3221321 10),,( xxxxxxq = . Sabiendo que se desea minimizar costes, encontrar las cantidades de
los factores productivos que se deben emplear en el proceso de producción.
2. Utilidad del consumidor Supongamos que la función de utilidad de un consumidor en un perio-do de tiempo viene dada por 2121 ),( xxxxU = donde 21 xyx representan las cantidades consumidas de dos bienes 1 y 2 en dicho periodo de tiempo. Si el precio del primer bien es 11 04.05 xp −= y el del segundo es 22 01.04 xp −= , si la renta disponible para el consumidor es de 50 unidades monetarias, y si los precios son tales que 31 ≥p y 22 ≥p , se pide calcular las cantidades consumidas de cada bien cuando el objetivo del consumidor es maximizar su utilidad.
3. Producción y distribución Una empresa quiere maximizar la tasa de rentabilidad sobre los cos-tes que origina al realizar dos actividades distintas, la de producción y la de distribución de produc-tos. El coste variable por tonelada obtenida por el proceso de producción es de 40000 euros, mien-tras que el coste por tonelada distribuida es de 41000 euros. La empresa debe sufragar un coste fijo de 100000 euros, independientemente de la cantidad producida y/o comercializada. Por cada tone-lada producida obtiene un beneficio unitario de 18000 euros, mientras que por la distribución ob-tiene 19000 euros por tonelada. Dispone de dos recursos productivos para desarrollar esas dos acti-vidades, personal e instalaciones. Ha valorado su disponibilidad de recursos personales en 60000 euros y en 200000 sus recursos de instalaciones. Conoce que para producir una tonelada de produc-to requiere 15000 euros en personal y 30000 en concepto de usos de instalaciones, mientras que para distribuir una tonelada del mismo producto requiere 10000 en recursos personales y 40000 euros de instalaciones. Formular un modelo para encontrar la política óptima de producción y dis-tribución.
4. Planificación de la Producción (1) Una empresa fabrica puertas y ventanas de cristal, estructu-rándose su trabajo en varias plantas procesadoras según el siguiente plan:
Planta 1: Se fabrican los marcos y molduras de aluminio. Planta 2: Se fabrican los marcos de madera.
2
Planta 3: Se produce el vidrio y se ensamblan los productos.
Debido a que las ganancias se han reducido, se ha decidido dejar de fabricar algunos productos y dejar libre una parte de la capacidad de producción para fabricar dos productos nuevos que están teniendo mayor demanda: Puertas de vidrio con marco de aluminio de 0,70x2 m. (Ganancia por uni-dad=300 euros), y ventana con vidrio doble y marco de madera de 1,5x2 m. (G. u.=500 euros). La compañía llega a la conclusión de que todos los productos que fabrique los puede vender. Sin em-bargo, la capacidad de producción de cada planta es limitada, pudiéndose invertir la capacidad dispo-nible para la producción de cada uno de estos nuevos productos, según la siguiente tabla.
Capacidad usada por u. de producto Prod. 1 Prod. 2
Capacidad dispo-nible
Planta 1 1 0 4 Planta 2 0 2 12 Planta 3 3 2 18 Ganancia unitaria (100 €) 3 5
Formular un programa matemático que proporcione la combinación de los dos productos más ren-table para la empresa.
5. Producción de alimentos Cierto alimento se produce mediante refinado y mezcla de cinco ti-pos de sustancias de dos clases: vegetales (v1,v2) y no vegetales (n1,n2,n3). Cada sustancia puede adquirirse para reparto inmediato o futuro. Los precios de reparto (en euros por tonelada) de las sustancias para los próximos meses vienen dados en la siguiente tabla:
V1 V2 N1 N2 N3 Enero 110 120 130 110 115 Febrero 130 130 110 90 115 Marzo 110 140 130 100 95 Abril 120 110 120 120 125 Mayo 100 120 150 110 105 Junio 90 100 140 80 135
El precio de venta del producto es de 150 euros por tonelada.
Las sustancias vegetales y no vegetales requieren diferentes líneas de producción y refinamiento. En un mes cualquiera no es posible refinar más de 200 toneladas de sustancias vegetales y 250 to-neladas de las no vegetales. No hay pérdida de peso en el proceso de refinado y el coste del mismo es insignificante.
Por otra parte, se pueden almacenar hasta 1000 toneladas de cada uno de los dos tipos de sustancias para su uso posterior. El coste de almacenamiento para ambos es de 5 euros por tonelada y mes. Sin embargo, ni el producto final ni tampoco las sustancias refinadas pueden ser almacenadas.
Existe, por último, una restricción tecnológica sobre la calidad del producto final, que en las unida-des apropiadas de medida, debe estar entre 3 y 6. Se supone que la calidad de la mezcla es lineal respecto a las cantidades de las sustancias empleadas y sus respectivas calidades, que son:
V1 V2 N1 N2 N3 8.8 6.1 2 4.2 5
Se comienza con 500 toneladas de cada sustancia almacenada y se desea disponer de la misma can-tidad al final de Junio en el almacén.
Formular un modelo matemático para determinar la política óptima de adquisición de materias pri-mas y producción del alimento para maximizar el beneficio.
3
6. Producción de mezclas La empresa ZUMIBAN se dedica a la obtención de zumos de frutas exóticas. En el proceso de transformación se utiliza zumo puro, agua y otros aditivos que diferencian los zumos de la empresa respecto a los de la competencia. El zumo puro se obtiene exprimiendo las frutas y desechando las pieles y otros residuos sólidos.
ZUMIBAN fabrica tres tipos de zumo A, B y C combinando zumo puro, agua y aditivos en las si-guientes proporciones:
TIPO ZUMO ZUMO PURO AGUA ADITIVOS A 2 1 1 B 5 2 2 C 3 2 1
Se sabe que la función de ingresos de la empresa es zyx 22222 ++ donde x, y, z son los litros de los zumos A, B y C, y que los costes totales por litro son de 10 u.m. para el zumo A, 2 u.m. para el zu-mo B y 3 u.m. para el zumo C. También se conoce que por cada 10 Kg. De fruta se obtienen 7 litros de zumo puro y la empresa dispone de un stock de 20.000 Kg. De fruta en almacén. No existen lími-tes para el empleo de agua y aditivos. Además, por razones estratégicas se considera que no es con-veniente que la producción de un tipo de zumo supere el 40% del total.
Calcula cuántos litros de cada clase de zumo deberá producir ZUMIBAN para maximizar los bene-ficios.
7. Programación de turnos laborales (1) La empresa Seguritas necesita tener cada día de la se-mana al menos el siguiente número de empleados:
Lunes Martes Miércoles Jueves Viernes Sábado Domingo Empleados necesarios 16 15 16 19 14 12 18
Atendiendo a convenios laborales, cada empleado hará su semana laboral trabajando 5 días consecutivos comenzando cuando la empresa le diga. Por otra parte, cada contrato le supone a la empresa un costo de 500 euros por semana. Según esto, ¿cuántos empleados se necesitarán si se quiere minimizar los costos de contratación? ¿Cuántos trabajadores empezarán su turno de 5 días los miércoles?
8. Planificación de la producción (2) Chirility Company debe producir al menos 600000 torni-llos pequeños y 400000 tornillos grandes para satisfacer la demanda de las siguientes 4 semanas. Estos tornillos pueden producirse en dos máquinas distintas, cada una de las cuales está disponible 40 horas a la semana. Los requerimientos de costo y tiempo para producir cada tamaño de tornillo en cada máquina y el precio de venta de cada tamaño de tornillo se muestran a continuación: Tornillos pequeños Tornillos grandes Precio de venta (€/1000 u.) 27.5 32.5 Costo en la máquina 1 (€/1000 u.) 6.25 7.75 Costo en la máquina 2 (€/1000 u.) 8 9.25 Tiempo en la máquina 1 (min/libra) 1.5 1.75 Tiempo en la máquina 2 (min/libra) 1 1.25
En cada libra hay aproximadamente 60 tornillos pequeños y 40 grandes. El gerente quiere maximi-zar el beneficio y satisfacer la demanda con la disponibilidad limitada de tiempo de máquina en las siguientes 4 semanas. Formular un modelo que indique cómo llevar a cabo la producción.
4
9. Selección de personal El departamento de selección de personal de unos grandes almacenes ha preseleccionado a siete candidatos para ocupar cinco puestos de vendedores en la empresa. Estos puestos de vendedores corresponden a cinco secciones diferentes: Fotografía, Discos, Calzado, Juguetería y Librería. Para realizar la selección se ha probado a los siete candidatos en las cinco secciones en las mismas condiciones para todos. El número de ventas realizado por cada candidato en las cinco secciones viene dado por la siguiente tabla:
Candidatos Fotografía Discos Calzado Juguetería Librería Juan 8 9 2 4 1 Pedro 2 9 4 1 2 Andrés 8 7 3 9 1 Luisa 7 5 6 10 1 Catalina 8 9 6 9 3 Roberto 3 9 1 10 4 Isabel 8 7 6 3 4
Formular un modelo que permita determinar qué cinco trabajadores debe seleccionar la empresa y a qué secciones debe asignar a cada uno de los vendedores contratados.
10. Programación de turnos laborales (2) La principal sucursal del Burlington Bank en Vermont requiere de 8 a 15 cajeros de servicio, dependiendo de la hora del día, como se indica en la siguien-te tabla:
PERIODO NÚMERO MÍNIMO DE CAJEROS 8-10 8 10-12 10 12-14 15 14-16 12
Los cajeros a tiempo completo trabajan 8 horas consecutivas a 15$ la hora, comenzando a las 8 h. Los cajeros a tiempo parcial trabajan 4 horas consecutivas a 8$ la hora, comenzando a las 8 h., 10 h. o 12 h. Las regulaciones sindicales requieren que a toda hora al menos el 60% de los cajeros sean de tiempo completo. Como gerente del departamento de personal, haga una recomendación respec-to al número de empleados a tiempo completo y a tiempo parcial requeridos a lo largo del día para minimizar el costo diario total.
11. Localización de plantas productivas Cosmic Computer Company (CCC) acaba de darse a co-nocer y ha obtenido fondos para producir un nuevo ordenador. La compañía confidencialmente anti-cipa una demanda mensual de 1700 ordenadores de una tienda de ventas al detalle en San Diego, 1000 ordenadores de una tienda de Barstow, 1500 ordenadores de una tienda de Tucson y 1200 or-denadores de una tienda de Dallas. Para satisfacer esta demanda anticipada, la gerencia de CCC está considerando construir plantas de ensamblaje en San Francisco, Los Ángeles, Phoenix y/o Denver. Las capacidades de producción mensual y los costos fijos proyectados (que incluyen la operación de la planta, el pago de hipoteca, etc.) se muestran en la siguiente tabla:
Capacidades de las plantas y costos fijos UBICACIÓN CAPACIDAD MENSUAL COSTOS FIJOS MENSUALES San Francisco 1700 70000 Los Ángeles 2000 70000 Phoenix 1700 65000 Denver 2000 70000
El costo de embarque de un ordenador terminado desde cada planta hasta cada tienda detallista se da en la tabla siguiente:
5
Costos de embarque ($/ordenador) de las plantas a las tiendas TIENDAS PLANTAS San Diego Barstow Tucson Dallas San Francisco 5 3 2 6 Los Ángeles 4 7 8 10 Phoenix 6 5 3 8 Denver 9 8 6 5
Como gerente de la división de producción, se le ha pedido recomendar las plantas que se construi-rían para minimizar los costos totales de transporte mensual y los costos fijos.
12. Producción y almacenamiento National Steel Corporation (NSC) produce un acero especial usado en las industrias de aviación y aeroespaciales. El departamento de ventas de NSC ha recibido pedidos de 2400, 2200, 2700 y 2500 toneladas de acero para cada uno de los siguientes 4 meses. NSC puede satisfacer estas demandas produciendo el acero, extrayéndolo de su inventario o usando cualquier combinación de las dos alternativas.
Se proyecta que los costos de producción por tonelada de acero durante cada uno de los siguientes cuatro meses sean de 7400, 7500, 7600 y 7650 euros. Como los costos suben cada mes, debido a las presiones inflacionistas, tal vez sea mejor que NSC produzca más acero del que necesita en un mes determinado y que almacene el exceso. La capacidad de producción, sin embargo, no puede exceder las 4000 toneladas en ningún mes. La producción mensual se termina al final del mes, cuando la demanda se satisface. Cualquier acero remanente se almacena en inventario a un costo de 120 euros por tonelada por cada mes que permanece allí. Estos datos se resumen en la siguiente tabla:
Mes 1 2 3 4 Demanda (tons) 2400 2200 2700 2500 Costo de producción (€/ton) 7400 7500 7600 7650 Costo de inventario (€/ton/mes) 120 120 120 120
Si el nivel de producción se incrementa de un mes al siguiente, entonces la compañía incurre en un costo de 50€ por tonelada de producción incrementada para cubrir la mano de obra adicionales y/o el tiempo extra. Cada tonelada de producción disminuida incurre en un costo de 30€ para cubrir los beneficios de empleados no utilizados.
El nivel de producción durante el mes anterior fue de 1800 toneladas, y el inventario que comienza es de 1000 toneladas. El inventario al final del cuarto mes debe ser de al menos 1500 toneladas para cubrir la demanda anticipada.
Formule un plan de producción para NSC que minimice los costos totales en los siguientes cuatro meses.
13. Uso y urbanización de la tierra Birdeyes Real Estate Co. posee 800 acres de tierra de primera clase, pero no urbanizada, en un lago escénico en la parte central de Ozark Mountains. En el pasado, se aplicaba poca o ninguna regulación a nuevas urbanizaciones en torno al lago. Las orillas del lago ahora están alineadas con residencias vacacionales agrupadas. Debido a la falta de servicio de drena-je, o desagüe por alcantarillado, se utilizan muchos tanques sépticos, la mayoría instalados en forma inadecuada. Con el paso de los años, la infiltración de los tanques sépticos ha provocado un severo problema de contaminación del agua.
Para controlar la degradación más profunda en la calidad del agua, los funcionarios del municipio
6
presentaron y aprobaron algunos reglamentos estrictos aplicables a todas las urbanizaciones a futu-ro:
1. Sólo se pueden construir casas para una, dos y tres familias, donde las unifamiliares costituyen cuando menos el 50% del total.
2. Para limitar el número de tanques sépticos, se requieren tamaños de lote mínimos de 2, 3 y 4 acres para casas de una, dos y tres familias.
3. Se deben establecer áreas de recreo de 1 acre cada una a razón de un área por cada 200 familias.
4. Para preservar la ecología del lago, no se puede extraer agua del subsuelo para uso en la casa o el jardín.
El presidente de Birdeyes Real Estate estudia la posibilidad de urbanizar los 800 acres de la compa-ñía en el lago. La nueva urbanización incluirá casas para una, dos y tres familias. El estima que el 15% del terreno se utilizará en la apertura de calles y vías de acceso para servicios. También calcula que los siguientes serán sus ingresos derivados de la venta de las diversas unidades habitacionales:
Unidades habitacionales Sencilla Doble Triple Ingreso neto por unidad ($) 10000 15000 20000
El costo de conexión del servicio de agua al área es proporcional al número de unidades que se construyan. Sin embargo, la comunidad estipula que se deberá colectar un mínimo de 100000 $ para que el proyecto sea económicamente factible. Además, la expansión del sistema acuífero más allá de su capacidad actual está limitada a 200000 galones por día durante periodos de consumo máxi-mo, pico. Los datos que siguen resumen el costo de conexión del servicio de agua y también del consumo de agua suponiendo una familia de tamaño medio:
Unidades habitacionales Sencilla Doble Triple Recreo Costo del servicio de agua por unidad ($) 1000 1200 1400 800 Consumo de agua por unidad (galones/día) 400 600 840 450
2. Programación Lineal 14. Dibujar el conjunto de soluciones factibles y resolver por el método gráfico los siguientes pro-gramas lineales:
a)
0y x,
82y+x-
6y+ xa.s
3y+ xMax
≥≤
≤
b)
0y x,
72y+5x
4y+3x a.s
8y+6x Min
≥≥
≥
c)
0y x,
1y+x-
1y- xa.s
y-x- Min
≥≥
≥
d)
0y, x
32y
86y xs.a
2y3xMax
≥≤
≥++
7
15. Resolver los siguientes programas lineales utilizando el método Símplex:
a)
0x,x, x
8x2x4 x
12x4x32x
4xx xa.s
xx32x Max
321
321
321
321
321
≥
≤++≤++
≤++
++
b)
0x, x
5x22x
6x34x a.s
x26x Min
21
21
21
21
≥
≥+≤+
+
c)
0x, x
4x32x-
4x2x a.s
x3x Max
21
21
21
21
≥
≤+≥+
+
d)
0x, x
4x
2xx- a.s
x xMax
21
2
21
21
≥
≤≤+
+
16. Plantear el problema dual de cada uno de los Programas Lineales incluidos en los ejercicios 23 y 24 y resolverlos utilizando el método Símplex.
17. Dado el problema:
0y x,
4y+2x-
10y+ xa.s
2y+ xMax
≥≤
≤
a) Resolver el problema y su dual, ilustrando las soluciones gráficamente.
b) Cambiar la primera restricción por x+y≤11, y analizar el cambio en el óptimo de la función objetivo.
c) Idem si se cambia la primera restricción por x+2y≤10
18. Dado el programa
0x,x, x
2xx2x
1x6x xa.s
xx3x=z Max
321
321
321
321
≥≤++≤+−
−+
plantear su programa dual y las propiedades de holgura complementaria.
19. Decir si cada una de las siguientes afirmaciones es cierta o falsa, razonando la respuesta:
a) La regla del método Símplex para elegir la variable no básica entrante se usa porque siem-pre conduce a la mejor solución básica factible adyacente.
b) La regla del método Símplex para elegir la variable básica que sale se usa porque al hacer otra elección casi siempre se llega a una solución básica que no es factible.
c) Cuando un modelo de programación lineal tiene una restricción de igualdad, se introduce una variable artificial a esta restricción con el fin de iniciar el método Símplex con una solu-ción básica inicial que sea factible para el modelo original.
20. Una refinería de petróleo puede destilar dos tipos de crudo: Un crudo de Arabia ligero y un cru-do mexicano pesado (de alta densidad), cuyos precios respectivos son 11 y 9 dólares/barril. De cada uno de estos crudos se obtienen tres productos destilados: keroseno, gasolina y gas-oil, en las si-guientes proporciones:
8
Gasolina Keroseno Gas-oil Pérdidas
Arabia ligero 0,4 0,2 0,35 0,05
Mexico pesado 0,32 0,15 0,45 0,08
La empresa de refinamiento ha firmado un contrato con una empresa de distribución para suminis-trarle 1000000 de barriles de gasolina, 300000 de keroseno y 200000 de gas-oil. ¿Qué cantidad debe destilar de cada uno de los dos tipos de crudo para satisfacer sus compromisos con el mínimo coste? Resolverlo por el Dual.
21. Un inversor dispone de 50000 dólares para invertir en tres tipos de valores: bonos de bajo ries-go que proporcionan un interés del 5% anual; acciones de riesgo medio con un interés del 8% y obligaciones especulativas de alto riesgo con un 16%. Para tener en cuenta el factor riesgo, el in-versor decide no invertir más de 25000 dólares en las obligaciones especulativas y que la cantidad invertida entre los bonos y las obligaciones no supere los 30000 dólares. ¿Cuánto debe invertir en cada tipo de valores para maximizar sus intereses?
22. Un bodeguero dispone de tres tipos de vino en sus bodegas: tinto doble pasta (TDP), tinto (T) y clarete (C), y tiene la intención de embotellar y comercializar sus propias marcas de vino, distinguiendo tres calidades: Vino Extra (E), Vino Reserva (R) y Vino de Mesa (M). La elaboración de estas calidades se realiza combinando los tres tipos de vino de la siguiente forma:
Componentes (en litros)
Marca TDP T C AGUA
E 0,6 0,3 0,1 -
R 0,4 0,3 0,2 0,1
M 0,2 0,4 0,3 0,1
Los costes de los vinos a utilizar y las cantidades de que dispone son:
VINO Precio coste (u.m/l) Cantidad (litros)
TDP 100 120000
T 30 80000
C 20 50000
Agua - ilimitada
El precio de venta unitario de las botellas elaboradas (1 litro de capacidad) es: 110 u.m. las E, 80 u.m. las R y 50 u.m. las M. Si por cada botella de vino E ó R espera vender por lo menos 2 de M, ¿cuál debe ser la producción de cada una de las marcas que maximice el beneficio neto?
23. La empresa A se dedica al montaje de motocicletas de 500, 250, 125 y 50 centímetros cúbicos. Posee una planta que está estructurada en cuatro departamentos: fabricación de los chasis, pintura, montaje y el departamento O.K.-Line o verificación de calidad. Las horas de mano de obra que ne-cesita cada uno de los modelos de motocicletas en los diferentes departamentos son las siguientes:
9
Sección Fabricación de chasis
Pintura Montaje O.K.-Line
Mod. 500 8 6 8 4
Mod. 250 6 3 8 2
Mod. 125 4 2 6 2
Mod. 50 2 1 4 2
La distribución de los trabajadores es la siguiente: El departamento de fabricación de chasis dispone de 25 trabajadores, el de pintura de 18, el de montaje de 30 y el O.K.-Line de 10. Todos los trabaja-dores realizan una jornada laboral de 8 horas.
Si el margen de beneficio de cada uno de los modelos es de 200000, 140000, 80000 y 40000 u.m. respectivamente, ¿cuál ha de ser la combinación óptima de motocicletas a producir para que el be-neficio sea máximo?
Además, realizar un análisis postóptimo en los siguientes casos:
a) Se contrata un nuevo operario para la sección de verificación.
b) Se consigue reducir el número de horas empleadas en la construcción del chasis de las mo-tocicletas de 125 c.c. pasando de 4 horas a 3 horas.
c) En un nuevo avance tecnológico, la sección de construcción de chasis reduce el tiempo de fabricación unitario de las motocicletas de 125 c.c. de 4 a 2 horas.
d) ¿Interesaría fabricar motocicletas de 125 c.c. si su beneficio unitario fuese de 90000 u.m.?
e) El departamento de ventas informa que las motocicletas de 250 c.c. son invendibles al pre-cio actual y que para poder competir con las marcas rivales el precio debería descender, si-tuando el beneficio unitario en 120000 u.m. ¿Conviene modificar el proceso productivo?
24. Cierta empresa produce cuatro artículos diferentes utilizando los materiales A y B. Dada la dis-tancia existente entre el almacén proveedor y la empresa, el proveedor establece como condición para servir los materiales que el consumo mínimo mensual de A y B debe ser de 5600 y 8700 uni-dades. La estructura del proceso productivo es la siguiente:
Producto 1 Producto 2 Producto 3 Producto 4
Material A 200 150 100 45
Material B 300 250 180 82,5
El coste unitario de producción es, respectivamente, de 90, 80, 50, 24. ¿Cuál debe ser la distribu-ción de la producción para que los costes sean mínimos? Hacer un análisis de la sensibilidad de los diferentes parámetros del modelo.
25. Una empresa constructora tiene en cartera realizar una serie de proyectos de dos tipos (A y B) cuyo coste de desarrollo unitario es el mismo (lo suponemos igual a 1 para ambos). Las necesida-des de analistas, programadores y terminales de ordenador para cada tipo de proyecto vienen dadas por la siguiente tabla:
Tipo: Nº de prog. Nº de anal. Nº de term.
A 2 2 3
B 3 6 1
10
Estos proyectos pueden hacerse total o parcialmente, y el deseo de la empresa es minimizar el cos-te de desarrollo de los proyectos que se vayan a ejecutar. Sabiendo que los condicionantes para el desarrollo de estos proyectos son: al menos 9 programadores y 5 analistas deben estar ocupados en ellos, y se cuenta únicamente con 6 terminales de ordenador, se pide:
a) Formular el problema de Programación Matemática que permite modelizar esta situación.
b) Resolverlo por el método Símplex e interpretar económicamente la solución obtenida
c) Comprobar por el método gráfico el óptimo encontrado.
26. Sabiendo que las siguientes tablas Símplex representan la tabla inicial y la final de un problema de programación lineal en forma estándar de maximización con tres restricciones, la primera debida a materia prima, la segunda a trabajo, y la tercera de tipo técnico, y donde x4, x5, x6 son variables de holgura:
Tabla Inicial
Vb/f x1 x2 x3 x4 x5 x6 l d
X4 2 3 1 1 0 0 12 X5 2 4 -1 0 1 0 10
X6 1 1 1 0 0 1 4
Z -3 1 -2 0 0 0 0
Tabla Final
Vb/f x1 x2 x3 x4 x5 x6 l d
X4 0 1 -1 1 0 -2 4 X5 0 2 -3 0 1 -2 2
X1 1 1 1 0 0 1 4
Z 0 4 1 0 0 3 12
a) ¿Cuál es la nueva solución óptima si se dispone de 5 unidades del tercer recurso en lugar de las 4 originales?
b) Determinar la solución óptima si se decide que x2 debe tomar, al menos, el valor 1.
27. El departamento de producción de una empresa naviera recibe un contrato para producir un número de anclas que requieren el uso de un material tipo A cuyo coste por unidad es de 30 u.m., y de un material tipo B cuyo coste por unidad es de 80 u.m.. Para cada ancla puede usarse como máximo 12 unidades de material A y como mínimo 16 unidades de material B. Cada unidad de A pesa 4 kg., y cada unidad de B, 6 kg. Si el peso del ancla debe ser como mínimo de 120kg., y el deseo del departamento de producción es conocer la mezcla de materiales A y B que debe emplear para fabricar cada ancla minimizando costes, se pide:
a) Formular el problema de Programación Matemática que permite modelizar esta situación.
b) Resolverlo por el método Símplex e interpretar económicamente la solución obtenida
c) Comprobar por el método gráfico el óptimo encontrado.
28. Sabiendo que las siguientes tablas Símplex representan la tabla inicial y la final de un problema de programación lineal en forma estándar de maximización con tres restricciones, la primera debida a materia prima, la segunda a trabajo y la tercera de tipo técnico, donde x4, x5, x6 son variables de holgura:
11
Tabla Inicial
Vb/f x1 x2 x3 x4 x5 x6 L.D
X4 2 3 1 1 0 0 16 X5 2 4 -1 0 1 0 20
X6 0 1 1 0 0 1 4
Z -3 -4 -2 0 0 0 0
Tabla Final
Vb/f x1 x2 x3 x4 x5 x6 L.D
X1 1 1 0 1/2 0 -1/2 6 X5 0 3 0 -1 1 2 12
X3 0 1 1 0 0 1 4
Z 0 1 0 3/2 0 1/2 26
a) ¿Cuál es la nueva solución óptima si se dispone de 30 unidades del primer recurso en lugar de las 16 originales?
b) Determinar la solución óptima si cambia el beneficio unitario del segundo producto (coefi-ciente en la función objetivo) de 4 unidades a 2 unidades
29. Dado el siguiente problema: Max z= 2x1-x2+x3 s. a. 3x1+x2+x3≤60 x1-x2+2x3≤10 x1+x2-x3≤20 x1,x2,x3 ≥0
y después de introducir las variables de holgura y de realizar una iteración del método Símplex se obtiene la tabla Símplex:
x1 x2 x3 x4 X5 x6 L.D.
x4 0 4 -5 1 -3 0 30
x1 1 -1 2 0 1 0 10
x6 0 2 -3 0 -1 1 10
z 0 -1 3 0 2 0 20
a) Identificar la solución factible en un vértice obtenida en esta iteración.
b) Escribir la función objetivo contenida en la tabla y su valor en la solución factible implícita a ella.
c) Escribir las ecuaciones de restricción que definen la solución factible en un vértice obteni-da en esta iteración.
d) Continuar la aplicación de método Símplex hasta encontrar la solución óptima indicando en ese caso la solución óptima y el valor del objetivo en el óptimo.
30. Una empresa produce y distribuye 5 artículos diferentes y recibe como beneficio unitario por cada uno de ellos 2, 5, 3, 4 y 1 u.m. respectivamente. Además utiliza dos recursos para la produc-ción (recurso 1 y recurso 2) en las siguientes cantidades:
Artículo 1 Artículo 2 Artículo 3 Artículo 4 Artículo 5 Disponibilidad
máxima
Recurso 1 1 3 2 3 1 6
Recurso 2 4 6 5 7 1 15
Responder a las siguientes cuestiones, resolviendo, sin utilizar el método Símplex, a través de su programa dual:
a) Las cantidades a producir para maximizar los beneficios y el beneficio máximo alcanzado.
12
b) Los precios sombra imputados a cada recurso y las cantidades no utilizadas de los mismos.
c) El coste mínimo total imputado a los recursos.
d) Comprobar la solución anterior empleando el método Símplex en el problema primal.
31. Partiendo del problema anterior, analizar el efecto en la solución óptima de cada uno de los si-guientes cambios por separado y, en el caso de que ésta cambie, reoptimizar para encontrar la nueva solución óptima:
a) La cantidad del recurso 1 necesaria para producir el artículo 3 pasa a valer 0.
b) La disponibilidad máxima del recurso 2 pasa a valer 18.
32. Una compañía está dedicada a finalizar la fabricación de automóviles y camiones. Cada vehículo tiene que pasar por un taller de pintura y por un taller de montaje de la carrocería. Cada día tenemos disponibles 120 y 50 horas de trabajo en los talleres de pintura y de montaje de carrocería, respec-tivamente. Además, la pintura de cada automóvil lleva 2 horas de trabajo, mientras que la de un ca-mión lleva 3 horas. También, el montaje de la carrocería lleva 1 hora de trabajo para ambos tipos de vehículos. Sabiendo que la ganancia por cada camión finalizado es de 3 u.m. (u.m.=100.000 u.m.), mientras que por cada automóvil es de 2 u.m., se pide:
a) Formular el Problema de Programación Matemática que permite conocer qué cantidad de automóviles y camiones debe finalizar diariamente la empresa para maximizar sus beneficios, y clasificarlo.
b) Resolverlo gráficamente.
c) Comprobar la solución obtenida anteriormente empleando el método Símplex, indicando además la solución factible, el beneficio que le corresponde a esta, y las ecuaciones de res-tricción, implícitas en cada una de las tablas del Símplex.
d) ¿Qué ocurre con la solucion óptima si cada automóvil pasara a aportar 4 u.m. al beneficio? Hacer el estudio postóptimo ayudado del método Símplex revisado y comprobar gráficamente tu solución.
e) Plantear el problema dual del anterior (con los nuevos beneficios unitarios), interpretar los valores de las variables duales en el óptimo, escribir las relaciones entre todas las variables y comprobar el teorema fuerte de la dualidad.
3. Programación Entera 33. Resolver a mano, con ayuda del ordenador y gráficamente (sólo los de dos variables) los si-guientes problemas de programación entera.
a) Max z = 4x1 - 2x2 + 7x3 -x4 b) Max z = 4x1 + 5x2 c) Max z=3x1 + 2x2
s.a: x1 + 5x3 ≤ 10 s.a: x1 - x2 ≤ 1.75 (ó 2.25) s.a: x1 + 4x2 ≤ 8
x1 + x2 -x3 ≤ 1 x1 - x2 ≥ 1.25 -x1 + 4x2 ≥ 4
6x1 - 5x2 ≤ 0 x1≥ 2 x1≥0, x2≥0 y enteras
-x1 + 2x3 -2x4 ≤ 3 x1≥0, x2≥0 y enteras
xj≥0 para j=1,2,3,4 y entera para j=1,2,3
13
d) Max z = 3x1 + 2x2 +x3 e) Max z= 2x1 + 3x2 +x3 f) Max z= 4x1 + 5x2
s.a: x1 + x2 + x3 ≤ 4 s.a: x1 + x2 + x3 ≤ 5 s.a: 3x1 + 4x2 ≤ 20
2x1 - x2 - x3 ≤ 0 -x1 + 2x2 - x3 ≤ 0 4x1 + 2x2 ≤ 16
x1 + x2 - x3 ≤ 0 x1 + x2 - x3 ≤ 0 x2 ≥ 2
0≤x1, x2, x3 ≤2 y enteras x1≥0, x2≥0, x3≥0 y enteras x1≥0, x2≥0 y enteras
34. California Manufacturing Company ha decidido ampliarse mediante la construcción de una nue-va fábrica ya sea en Los Ángeles (LA) o/y San Francisco (SF). También está pensando en construir a lo sumo un nuevo almacén en aquella ciudad que se elija para la nueva fábrica. El valor presente neto (beneficio total que toma en cuenta el valor del dinero en el tiempo) de construir una fábrica en LA es de $9 millones, en SF $5 millones, el de un almacén en LA $6 millones y en SF $4 millones. El capital requerido para las respectivas inversiones es de $6, $3, $5 y $2 millones respectivamente, en donde el capital total disponible es de $10 millones. El objetivo es encontrar la combinación factible de alternativas que maximice el valor presente neto total.
35. High Tech, una compañía de inversión de capital riesgo, está considerando invertir hasta 1 mi-llón de dólares en una o más propuestas que ha recibido de diversos empresarios. Cada propuesta ha sido filtrada por el departamento de investigación, y seis han tenido una tasa esperada de retorno suficiente para justificar el riesgo implicado. La inversión única requerida y la tasa de rendimiento esperada asociada para cada proyecto son las siguientes: Proyecto: Bio-Tech Tale-Com Laser-Optics Compu-Wre Medi-Opti Sound-News Capital $ 200000 350000 150000 125000 375000 70000 Tasa de retorno 5.0 16.5 13.0 12.5 14.0 9.0 (esperada)
Como socio mayoritario se le ha pedido que haga recomendaciones respecto a los proyectos que deben respaldarse. Su meta es lograr la devolución esperada más alta sobre la inversión.
36. Spiral Paper, Inc. vende rollos de papel para computadoras y cajas registradoras a diversos ven-dedores al por menor. Sus rollos estándar tienen 20 pulgadas de ancho. Los vendedores al por me-nor han hecho pedidos de 1050 rollos de 3 pulgadas de ancho, 2050 rollos de 5 pulgadas de ancho y 4050 rollos de 8 pulgadas de ancho. Para producir estos rollos más pequeños, la máquina cortadora que tiene 8 montaduras diferentes corta rollos de 20 pulgadas, el número de rollos obtenidos de cada rollo de 20 pulgadas por cada montadura son los siguientes (nótese que la columna suma 20 pulgadas): Montadura 1 2 3 4 5 6 7 8 3 pulgadas 6 0 1 0 4 2 5 1 5 pulgadas 0 4 0 2 0 1 1 3 8 pulgadas 0 0 2 1 1 1 0 0 desperdicio 2 0 1 2 0 1 0 2
Estos son pedidos únicos. Cualquier rollo sobrante se vende con descuento, lo que provoca una pér-dida neta de $1 por cada rollo de 3 pulgadas, $1.50 por cada rollo de 5 pulgadas y $2 por cada rollo de 8 pulgadas. El desperdicio es reciclado a un costo neto de $0.50 por pulgada. Como gerente del departamento de producción, se le ha pedido determinar cómo usar las distintas monturas de la má-quina cortadora para satisfacer la demanda especificada para los rollos de tamaño para venta al por menor, a la vez que se minimiza el costo total.
37. BUDD ha obtenido una subvención federal de $5 millones para desarrollar edificios de depar-tamentos para personas de ingresos bajos y medianos en una extensión de 180000 pies cuadrados de terreno. Cada tipo de edificio requiere 20000 pies cuadrados. El costo estimado de cada edificio de
14
ingresos bajos es de $300000, y el costo estimado de cada edificio de ingresos medios es de $600000. Cada edificio de ingresos bajos proporciona 15 unidades, y cada edificio de ingresos me-dianos proporciona 12 unidades. Para mantener el vecindario bien equilibrado, el gobierno federal requiere que la proporción de los departamentos de ingresos medios con los de ingresos bajos sea de al menos 0.80. El director de BUDD desea determinar el mayor número de departamentos indi-viduales que pueden construirse en el terreno disponible con el presupuesto dado.
38. a) En la planta de Cleveland de Case Chemicals se producen dos disolventes CS-01 y CS-02. El departamento de mezclado de la planta actualmente tiene 5 empleados de tiempo completo, cada uno trabajando 40 horas a la semana y dos trabajadores de tiempo parcial, cada uno trabajando 15 horas a la semana. Estos empleados manejan máquinas que mezclan ciertos productos químicos para producir cada disolvente. Los productos, una vez mezclados, se refinan en el departamento de puri-ficación, que actualmente emplea seis trabajadores a tiempo completo a 40 horas a la semana cada uno y un trabajador a tiempo parcial que trabaja 10 horas a la semana. Las horas requeridas en los departamentos de mezclado y purificación para producir 1000 galones de cada uno de los productos son
CS-01 CS-02 Mezclado 2 1 Purificación 1 2
Case Chemicals tiene un suministro prácticamente ilimitado de las materias primas requeridas para producir los dos disolventes y puede vender cualquier cantidad de CS-01. La demanda para el pro-ducto más especializado, CS-02 está limitada a un máximo de 120000 galones a la semana. El de-partamento de contabilidad de la compañía estima una ganancia neta de $0.30 por galón de CS-01 y $0.50 por galón de CS-02.
Determinar la producción que maximice las ganancias.
b) Para incrementar ganancias, el presidente está considerando una expansión. Con las actuales ins-talaciones pueden contratarse hasta tres trabajadores más de tiempo completo en cada uno de los departamentos de mezclado y purificación a un costo semanal de $800 por empleado. La gerencia también puede considerar ampliar las instalaciones de producción a un costo estimado de $20000 a la semana. Esta expansión permitiría a la compañía contratar hasta ocho trabajadores adicionales en cada departamento, cinco más de los que se podrían contratar en cada departamento sin la expan-sión. Como gerente del departamento de producción, se le ha pedido que haga recomendaciones de contratación y expansión apropiadas.
4. Programación No Lineal 39. Realizar un esbozo gráfico para funciones de una o dos variables que se caractericen en su do-minio de optimización por:
a) No poseer máximos ni mínimos locales (ni globales por tanto).
b) Poseer máximos y mínimos locales pero no globales.
c) Poseer máximos y mínimos locales y máximos y mínimos globales únicos.
d) Poseer máximos y mínimos locales, máximo global único, y no existir mínimo global.
e) Poseer máximos y mínimos locales, mínimo global único, y no existir máximo global.
f) Poseer máximos locales y un máximo global único, pero no existir mínimos locales (ni
15
globales por tanto).
g) Poseer mínimos locales y un mínimo global único, pero no existir máximos locales (ni globales por tanto).
h) Poseer más de un (incluso infinitos) mínimos o máximos globales.
i) Poseer máximos o mínimos locales no detectables mediante la Programación Matemática Clásica por no ser la función diferenciable en estos puntos.
40. Dado el programa matemático:
0x-
0y- x
01-y+ xa.s
yx=y)f(x, Max 22
≤≤≤
+
a) Representar gráficamente el conjunto factible.
b) Representar curvas de nivel correspondientes a niveles de la función objetivo cada vez ma-yores.
c) Encontrar gráficamente un óptimo del problema.
41. Desde el punto de vista neoclásico, el problema de optimización que el consumidor habrá de resolver es:
0x,...,0 x
Mxp...xp a.s
)x,...,u(x Max
n1
nn11
n1
≥≥≤++
para p1,…,pn,M∈IR+ conocidos.
a) Representar gráficamente el conjunto factible para dos bienes.
b) Razonar porqué si la función de utilidad u verifica la propiedad de monotonía o insaciabili-dad (x0>x1⇒u(x0)>u(x1)), entonces el óptimo del problema se debe dar sobre la recta presu-puestaria, gastándose el consumidor toda la renta.
c) Como consecuencia del apartado anterior, el problema del consumidor en el caso de que se verifiquen las hipótesis usuales de la Teoría Económica se puede representar por:
Mxp...xp a.s
)x,...,u(x Max
nn11
n1
=++
siendo por tanto un problema tratable mediante Programación Clásica (imponiéndose a poste-riori que la solución sea no negativa). Resolver este problema mediante el método de los mul-tiplicadores de Lagrange obteniendo e interpretando las condiciones de primer orden necesa-rias de óptimo y escribiendo las condiciones suficientes de óptimo de segundo orden.
d) Interpretar económicamente el multiplicador de Lagrange en este problema (Ayuda: De-
mostrar que λ=∂∂
λ=∂∂ ∑
=
n
1i
ii
óptimo M
xp
Mu
(multiplicador de Lagrange)).
42. Dada la función de utilidad de un consumidor del tipo u(x1,x2)= x x11 2
21 2/ / , encontrar las funciones
de demanda del consumidor, así como las cantidades demandadas en el óptimo para
16
M=100.000 u.m., p1=5.000 u.m., y, p2=10.000 u.m. ¿Cómo varía la utilidad en esta última posición si M cambia a 105.000 u.m.?
43. Resolver el problema de producción:
factores) los de (Coste 68x42x a.s
n)(Producció x3x2x9060x=Q Max
21
22
2121
=+−−+
Interpretar a través del multiplicador de Lagrange, análogamente al ejercicio 3 y 4, qué le ocurre a la producción óptima si el coste total se fija en 69 u. m.
44. Razonar gráficamente si los siguientes conjuntos de IR n son convexos o no:
a) { }4yx,2yx/IR)y,x(M 21 ≤−≤+∈=
b) { }1y,1x,4yx/IR)y,x(M 2222 ≤≤≤+∈=
c) { }x23 ey/IR)y,x(M =∈=
45. Estudiar la convexidad o concavidad de las siguientes funciones:
a) f(x,y) = -ex+y b) f(x,y) = 3x2 + 5y2 - 2xy
c) f(x,y) = x2 + y2 + z3 d) f(x,y) = ln(xy) , x,y∈ IR +
46. Uno de los supuestos de la Teoría Económica en la formalización de las preferencias del con-sumidor es el de convexidad (estricta) de las preferencias: “Dada una combinación de bienes, el conjunto de las combinaciones al menos tan buenas como ella es (estrictamente) convexo”.
a) Interpretar esta hipótesis de convexidad desde el punto de vista económico.
b) Comprobar que esto equivale a que la función de utilidad que representa estas preferencias sea cuasicóncava (estrictamente, bajo ciertas condiciones que no veremos).
c) Interpretar económicamente el hecho de que u(x), función de utilidad que representa estas preferencias, sea cuasicóncava.
d) Ratificar los apartados anteriores con la función de utilidad u(x1,x2)=x1x2 .
47. Dado el problema:
0y
0)x2(y a .s
x)x(f Max3
≤−≤−−
=
Resolverlo gráficamente y comprobar que el óptimo no verifica las condiciones de Kuhn-Tucker. Obsérvese finalmente que en el óptimo no se verifica la condición de regularidad de la restricción.
48. Consideremos el problema:
0y-
1x
4y xa .s
8yx)y,x(f Max22
22
≤≤≤+
−+=
Comprobar que el punto A(1,0) verifica las condiciones de Kuhn-Tucker de óptimo pero no lo es.
17
49. Dado el problema:
0y
0x
4y xa .s
)2y(x)y,x(f Max2
22
≥≥≤+
−−−=
Comprobar que la función objetivo es cóncava y las restricciones convexas, con lo que las condi-ciones de Kuhn-Tucker son necesarias y suficientes para el óptimo del problema. Encontrar, si es posible, el óptimo de este programa.
50. Dado el problema:
0x
0x
3x2x a .s
x)1xln()x,x(f Max
2
1
21
2121
≥≥≤+
++=
Comprobar que es un problema de Programación Convexa y resolverlo a través de las condiciones de Kuhn-Tucker.
51. Dado el programa:
1zyx a s.
z2y3)z,y,x(f Max222 ≤++
+−=
Comprobar los puntos que verifican las condiciones de Kuhn-Tucker, y estúdiese si son óptimos.
52. Una empresa automovilística ha firmado un contrato por el que se compromete a entregar 50 coches al final de cada mes durante los próximos tres meses. El coste de producir x coches en un mes es igual al cuadrado del número de coches que se produce en ese mes, esto es c(x)=x2. El coste de almacenamiento para un coche que se fabrica en un mes determinado y se entrega al mes siguien-te es de 20 u. m. Suponemos que no existe stock inicial. Partiendo de esta información se pide:
a) Formular un programa que determine la política óptima de producción y almacenamiento a lo largo de los tres meses (para minimizar el coste total).
b) Determinar la solución del problema.
53. Las funciones de ingresos y costes de una empresa son, respectivamente:
I(Q) = 16Q - Q2
C(Q) = Q2 + 8Q -2
Suponiendo que desea maximizar sus ingresos sujetos a que el beneficio debe ser no inferior a 8 u.m. y la cantidad producida no negativa, hallar la producción óptima a través de las condiciones de Kuhn-Tucker y verificar que no es inferior a la producción para la que se obtiene el beneficio máximo (Img(Q)=CMg(Q)).
54. Dado el siguiente problema de Programación No Lineal
Min z = x2-2y
s.a x2+y2≤16
x+y≥4
18
a) Dibujar la región factible y decir si es convexa o no.
b) Estudiar las propiedades de convexidad o concavidad de la función objetivo y dibujar las curvas de nivel.
c) Calcular gráficamente la solución óptima.
d) Confirmar para dicha solución la regularidad del punto y las condiciones apropiadas de Kuhn-Tucker.
55. Dado el problema:
1 x
1y x s.a
zyx+y+x=z)y,f(x, Min22
222
≥≤+
++
comprobar que el objetivo y las restricciones vienen dados por funciones convexas. Véase geomé-tricamente que el punto (1,0,0) es mínimo global y compruébese que no verifica las condiciones de Kuhn-Tucker. Finalmente, obsérvese que en este punto no se satisface la condición de regularidad.
56. Para el programa
2yx,0
1yx a s.
y7x3)y,x(f Max
≤≤≥+
+=
comprobar si el punto A(2,2) verifica las condiciones de Kuhn-Tucker y deducir si es óptimo.
57. Analizar gráficamente y mediante las condiciones de K-T (de primer y segundo orden) los si-guientes problemas.
a) max x2 + y2 b) max z= y - x c) max x
s.a.: x +y -1 ≤ 0 s.a.: x2 + y2 ≤ 4 s.a.: x2 - y ≤ 0
x - y ≤ 0 -x2 + y = 0 x - y ≤ -1
-x ≤ 0 x ≥ 0, y ≥ 0
d) min (x-4)2 + (y-4)2 e) min x - 2y
s.a.: x-3 ≤ 0 s.a.: x2 + y2 ≤ 1
x - y -2 ≤ 0 y - x ≥ 0
x ≥ 0, y ≥ 0
58. Analizar mediante las condiciones de K-T (de primer y segundo orden) los siguientes problemas (sugerencia: analizar gráficamente para "intuir" los óptimos).
a) min x2 + y2 b) min x2 + (y-1)2 c) min x + 2y
s.a.: xy ≥ 4 s.a.: x + y ≤ 6 s.a.: xy ≥ 1
x ≥ 0 x + y ≥ 0 x - y ≤ 2
x ≥ 0
19
d) min 3x2 + 4y2 + 4xy e) max e--x f) min z=x2 - 2y
s.a.: x + 2y ≤ 1 s.a.: x ≥ 0 s.a.: x2 + y2 ≤ 16
x + y ≥ 4
59. Dado el problema: max xy
s.a.: x + y + z ≤ 5
x2 + y2 + z2 ≥ 4
x ≥ 0, y ≥ 0, z ≥ 0
a) Calcular cuánto tiene que valer a, para que el punto (5/2,5/2,a) sea candidato a máximo lo-cal.
b) Confirmar que el punto obtenido en el apartado anterior es máximo local del problema.
60. Un comerciante puede comprar hasta 17'25 kg. de un producto químico a 10 unidades moneta-rias (u.m.=mil u.m.) el kg. Se puede convertir cada kg. de este producto químico a un costo de 3 u.m./kg., en un kg. del producto 1, y a un costo de 5 u.m./kg, en un kg. del producto 2. Si se producen x1 kg. del producto 1, éste se venderá al precio de (30-x1) el kg., y si se producen x2 kg. del produc-to 2, éste se venderá al precio de (50-x2) el kg. Se pide:
a) Formular matemáticamente el Programa Matemático que permite maximizar las ganancias a este comerciante y clasificarlo.
b) Resolverlo, en caso de ser posible, a través de las condiciones de Kuhn-Tucker. ¿Es un pro-blema de Programación Convexa?
5. Problemas complementarios 61. Una empresa de productos alimenticios de temporada tiene una planta que produce helados que son servidos a una cadena de heladerías. Los distintos sabores de helado tienen el mismo coste aproximado de producción y se envasan en recipientes de 3 litros. La estimación de la demanda de helado durante cada uno de los próximos doce meses es la siguiente:
Mes En. Fe. Mar Ab. Ma. Ju. Jul. Ag. Se. Oc. No. Di.
NºRecip pedidos
75 80 85 95 120 140 175 190 175 130 110 90
La empresa dispone de un gran almacén frigorífico y, por tanto, puede producir excedentes cual-quier mes para servirlos en meses futuros, si le resulta rentable. Puede suceder, además, que le re-sulte interesante adelantar la producción a base de utilizar mano de obra en horas extraordinarias, para lo que se dispone de varias posibilidades. La capacidad de producción de la planta, por otro la-do, varía también debido a los cambios de demanda de mano de obra en las plantas que fabrican otros productos. La tabla siguiente resume las capacidades de producción y los costes:
20
Mes En. Fe. Mar Ab. Ma. Ju. Jul. Ag. Se. Oc. No. Di.
(1) 100 100 100 90 90 90 90 90 80 80 80 90
(2) 40 40 40 40 40 50 50 60 60 60 50 50
(3) 65 65 65 65 70 70 75 75 75 70 70 65
(4) 85 85 85 85 90 90 95 95 95 90 90 85
Siendo: (1)=Capacidad normal de producción (2)=Capacidad extra de producción (3)=Precio recipiente en tiempo normal(u.m.) (4)=Precio en tiempo extra(u.m.) Por cada mes que el helado se guarde en el almacén, hay un coste de 10 céntimos, por cada envase de 3 litros. ¿Cuántos recipientes debería producir cada mes para que el coste de producción total (producción+almacenaje) sea mínimo? (Resolver con LINDO).
62. Una compañía tiene tres plantas que fabrican cierto producto que debe mandarse a cuatro cen-tros de distribución. Las plantas 1, 2 y 3 producen 12, 17 y 11 cargas mensuales, respectivamente. Cada centro de distribución necesita recibir 10 cargas al mes. La distancia en millas desde cada planta a los respectivos centros de distribución es la siguiente:
Centro 1 Centro 2 Centro 3 Centro 4
Planta 1 800 1300 400 700
Planta 2 1100 1400 600 1000
Planta 3 600 1200 800 900
El coste del flete por cada carga es de 100 dólares más 0.50 dólares/milla. ¿Cuántas cargas deben mandarse desde cada planta a cada uno de los centros de distribución para minimizar el coste total de transporte?
63. Una Compañía Extractora de Carbón de Asturias opera con dos minas A y B. Extraer carbón en la mina A le cuesta a la compañía 3 Millones de u.m. diarios, mientras que en la B le cuesta 2 Mi-llones de u.m. De cada mina se obtiene carbón de alta, mediana, y baja calidad. La mina A produce 2 Toneladas de carbón de alta calidad, 1 Ton. de mediana calidad, y 0,5 Ton. de baja calidad diariamen-te, mientras que la mina B produce al día 1 Ton. de cada una de las calidades. Sabiendo que la com-pañía ha contratado con sus clientes el abastecer un mínimo de 14 Ton. de carbón de alta calidad, 10 Ton. de carbón de mediana calidad, y 6 Ton. de carbón de baja calidad al mes, se pide:
a) Formular el problema de Programación Matemática que permite conocer el número de días que esta empresa debe operar en cada mina para minimizar el coste al cual puede satisfacer sus obligaciones contractuales.
b) Clasificar el problema anterior (Programación estática o dinámica, Clásica o no, Lineal o No Lineal).
c) Comprobar que, desde la óptica de la Programación No Lineal, es un problema de Progra-mación Convexa, y comprobar que operar 4 días/mes en la mina A y 6 días/mes en la mina B satisface las condiciones de Kuhn-Tucker. ¿Se puede afirmar algo sobre la solución del pro-blema a partir de lo anterior?
21
d) Resolverlo gráficamente como un problema de Programación Lineal.
e) Escribir el problema dual asociado.
f) Resolver el problema dual por el método Símplex.
g) Establecer las relaciones entre las variables del primal y del dual y enumerar las conse-cuencias que se deducen del teorema de holgura complementaria.
h) Leer la solución óptima y el valor del objetivo del problema original (primal) en la tabla co-rrespondiente del Símplex para el dual.
i) Interpretar económicamente las soluciones óptimas de los problemas primal y dual.
64. Razonar la verdad o falsedad de cada una de las siguientes afirmaciones:
a) La región factible de un problema de programación matemática es siempre acotada y cerra-da.
b) Todo problema de programación matemática tiene una solución finita. En particular, si el problema es de programación lineal también se verifica este hecho.
c) La regla del método Símplex (en programación lineal) para elegir la variable básica que sale se usa porque al hacer otra elección se llega a una solución básica no factible.
d) Cuando un modelo de programación lineal tiene una restricción de igualdad, siempre es im-prescindible introducir una variable artificial para comenzar la resolución por el método Sím-plex.
e) Las variables de holgura se introducen para convertir un problema de Programación No Li-neal en uno de Programación Lineal Continua en forma estándar.
f) Todo Problema de Programación No Lineal se puede expresar como un problema de Pro-gramación Convexa para el cual las condiciones de Kuhn-Tucker son suficientes para determi-nar el óptimo.
g) Todo problema de Programación Lineal tiene asociado otro problema de Programación Li-neal llamado su dual, pudiéndose conocer la solución de uno de ellos a través de la resolución del otro.
h) Algunos modelos de Programación Lineal que tienen algunas restricciones de igualdad y otras de desigualdad, pueden resolverse por el método Símplex sin hacer uso de las variables artificiales.
i) En un problema de Programación No Lineal, un punto que sea óptimo verifica las condicio-nes de Kuhn-Tucker.
ii) Si un punto verifica las condiciones de Kuhn-Tucker y es óptimo, entonces es un punto regular de la región factible.
65. Considere el problema: Max z=4x1+5x2 Sujeto a: 3 x1 + 4 x2 ≤ 20 4 x1 +2 x2 ≤ 16 x2 ≥ 2 x1 ≥ 0, x2 ≥ 0
22
a) Plantear el Dual. b) Construir la primera tabla del Dual para resolverlo por el Símplex y llevar a cabo sólo una
iteración para calcular la segunda tabla. c) Sin hacer más cálculos, da la solución del Primal, sabiendo que la Tabla Final del Dual es
y1 y2 y3 h1 h2 a1 a2 y2 y1
0 1
1 0
3/10 -2/5
-2/5 1/5
3/10 -2/5
2/5 -1/5
-3/10 2/5
1/10 6/5
-w 0 0 1.2 2.4 3.2 -2.4+M -3.2+M -25.6
d) Si en al segunda restricción del primal hay un 17 en lugar de un 16, qué se te ocurre comentar utilizando los resultados de la tabla dada en c, sin hacer ningún cálculo más. e) Haz el análisis de sensibilidad para el coeficiente de y1 en la función objetivo. f) En el Primal, suponiendo que las variables son enteras y resolviéndolo por el método de
ramificación y acotación obtenemos el siguiente árbol: (0) (2.4 , 3.2 ; 25.6)
x1≤2 x1≥3 (2 , 3.5 ; 25.5) (1) (2) (3 , 2 ; 22) x2≤3 x2≥4 ¿? (3) (4) (1.33 , 4 ; 25.33) x1≤1 x1≥2 (1 , 4.25 ; 25.25) (5) (6) ¿? x2≤4 x2≥5 ¿? (7) (8) (0 , 5 ; 25)
f1) Plantea y resuelve de cabeza (razonando, sin apenas hacer cálculos) los problemas de los nodos 3, 6 y 7. f2) ¿Falta ramificar más alguno de lo nodos? Comenta los nodos 2, 3, 6, 7 y 8.
g) Resolverlo gráficamente suponiendo x1 entera y x2 continua.
66. La siguiente tabla de Símplex muestra la solución óptima de un problema de programación li-neal (de minimización con restricciones de ≥). Se sabe que x1 y x2 se eligieron como variables bási-cas iniciales.
x1 x2 x3 x4 x5 x6 x7
2/5 -3/10 0 1 3/10 -2/5 3/10 1/10 -1/5 2/5 1 0 -2/5 1/5 -2/5 6/5 -z 38/5 34/5 0 0 6/5 12/5 16/5 -128/5
a) Identifica las variables básicas y no básicas de la tabla actual, señalando sus valores así como el valor objetivo óptimo. b) Identifica B-1. c) Calcula B (sabiendo que BB-1=I) y utilízala para escribir el problema original sin varia-bles de holgura. d) Escribe el problema dual y resuélvelo gráficamente. Además, dibuja la región factible del dual suponiendo que la segunda variable es entera y di, justificándolo, cual es el óptimo de este nuevo problema. e) A partir de la tabla dada, escribe la tabla óptima dual (sin el interior). f) Encuentra las condiciones para b1 y b2 (términos independientes de las restricciones ini-ciales) que mantienen óptima la base actual. g) Encuentra la nueva solución óptima si b1=b2=2. h) Si en la última fila de la tabla dada en lugar de 6/5 apareciera 0 debajo de la x5 ¿cuál se-ría la solución final?