problemas de la semana

El tercer parcial.

1.- Resuelva (uno por persona) usando Programación Dinámica Determinística los problemas 1 y 3 de la semana 7, o el 7 de la semana 8 y 9 y el 3 de la semana 11.

2. - Resuelva (uno por persona) usando Programación Entera Binaria los problemas 3 de las semanas 7 y 11.

En todos los problemas se quiere que escriba el modelo del sistema como uno de Programación Entera o Programación Binaria.

2. Repita el problema anterior pero suponiendo que se contratan dos nuevos profesores cuyas preferencias son 5 y 6 en todas las asignaturas. Esto es, ahora tiene 7 profesores y sólo 5 asignaturas.

3. Un ladrón entra en un banco y se encuentra en la bóveda con 100 paquetes de 1 millón de XFAS, cada uno con un peso de 2 kilos. También se encuentra con 20 lingotes de oro con un peso de 15 kg y un valor en el mercado negro de 8 millones de XFAS y 50 lingotes de plata de 12 kg, con un valor en el mercado negro de 6 millones de XFAS. Si el ladrón sólo puede cargas con 30 kg. Formule el problema como uno de Programación Entera.

Solución de Nazario Evuy (pag.2-3). Lo ha planteado como un problema de Programación Lineal, pero le faltó decir que las variables x1, x2, x3 son variables enteras.

El segundo examen parcial.

1. Resuelva el problema 2 de la semana 4 y el 3 y 4 de la semana 3, por el método dual.

2. Para el problema de transporte que se muestra a continuación encuentre la solución de mínimo costo utilizando:

   1. 1. El problema dual

      2. El método de Stepping Stone

      3. El método de multilicadores

3. Suponga que el almacén de Boston se quema y sólo puede recibir 150 unidades de la producción. Calcule en nuevo óptimo en esta situación

4. Con el almacén de Boston en su consumo normal (300), ahora suponga que es la fábrica de Detroit la que tiene disminuir su producción a 50 und. Calcule el nuevo óptimo.

6. La presidenta de una compañía de la rama industrial altamente competitiva considera que un empleado de la compañía está proporcionado Información confidencial a la competencia. Ella está segura en un 90% que éste informante es el tesorero de la compañía, cuyos contactos han sido extremadamente valiosos para obtener financiamiento para la compañía. Si lo despide y es el informante, la compañía gana $100.000. Si lo despide pero no es el informante, la compañía pierde su experiencia y aún tiene a un informante en el equipo, con una pérdida para la compañía de $500.000.

Si ella no despide al tesorero, la compañía pierde $300.000, sea o no sea el informante, ya que en ambos casos el informante continúa en la compañía.

Antes de decidir la suerte del tesorero, la presidenta podría ordenar pruebas con un detector de mentiras. Para evitar posibles demandas, estas pruebas tendrían que administrarse a todos los empleados, con un costo total de $30.000. Otro problema es que las pruebas con el detector de mentiras no son definitivas. Si una persona está mintiendo, la prueba la revelara el 90% de las veces, pero si una persona no está mintiendo, la prueba lo indicará solo 70% de las veces.

7. Para el grafo no dirigido que se muestra en la figura, calcule el árbol de expansión de mínimo costo

8. Suponga ahora que el grafo es dirigido, que parte de (a) y llega a (g). Los arcos del grafo siempre van de izquierda a derecha o de abajo hacia arriba. Calcule el costo mínimo para llegar de a hasta g.

9. Si en el mismo gráfico anterior (dirigido) los números de los arcos los multiplicamos por 10 (todos) y se desea determnar el flujo máximo que puede enviarse desde a hasta g.

Respuesta problema 7 por Tomás Ndjé (pag. 9). Propone dos soluciones, cuando en realidad hay sólo una. El óptimo tampoco está bien.

P1: En la figura calcule el flujo máximo y las rutas que usaría para lograrlo, entre los nodos Source (s) y Sink (t). Observe que en todas las ramas se muestra i/j, donde la i indica el flujo que está circulando por esa rama y j indica la capacidad máxima de la tubería, por ejemplo del nodo 0 al 2 en la figura, en ese momento no está circulando nada y su capacidad máxima es 1. Observe además que las ramas tienen orientación, esto es, que el flujo sólo puede circular en el sentido mostrado.

P2: Para la figura, suponga que la red no está orientada y que en las ramas, i/j, la j indica el costo de ir de un nodo al otro, de los nodos que conecta esa rama, por ejemplo, del nodo 0 al nodo 1, el costo es 2. Calcule el costo mínimo para conectar directa o indirectamente todas las ciudades.

P4 (problema para 3 estudiantes): Para el próximo semestre, el Decano de la Facultad dispone de 15 salones numerados del 1 al 15, los 5 primeros de 15 estudiantes, los 5 siguientes de 20 y los restantes de 30 estudiantes. El costo de limpieza de lo salones pequeños es de 3000 XFAS por día, los medianos 4000 y los grandes 5000. Los salones no usados no se limpian diariamente.

Asimismo, este semestre se están ofreciendo 60 cursos de 4 horas por semana en horarios desde las 8 am hasta las 6 pm, en bloques de 2 horas, esto es, de 8 a 10 am, de 10 a 12 m, y así sucesivamente. Ello implica que cada día en cada salón se pueden dictar hasta 5 cursos por salón. Las clases se dictan de lunes a viernes.

El número de estudiantes por salón es:

(11   22   10   13   20   18   10   27   24   19   14   29   25    8   18   26   19 24   23   15   23   10   15   13   22    8    8    8   13   18   14   27   12   17

 29   18   16   13   17   13   21   26   17   12   30   29   13   11   21   18   19 20   30   13   13   15   21   21   13   22)

Formule el problema de asignación de salones como uno de Programación Lineal Entera

Para el Problema de Transporte que se muestra a continuación, resuélvalo 

1. Por el método Simplex primal

2. Por el método Simplex dual

3. Por el Método del Stepping Stone

4. Por el método de Multiplicadores

Para los siguientes problemas resuelva el problema primal y el problema dual. Verifique que los valores óptimos de ambos son iguales y que los precios sombras de unos son las soluciones óptimas del otro.

1. Sistema primal:

min Z = 12x1 + 7x2

Sujeto a:

4x1 +2x2 ≥ 80

3x1 + 4x2 ≥ 90

x1, x2 ≥ 0

2. Sistema primal

min Z = 5x1 + 8x2 + x3

Sujeto a:

x1 + 4x2 + 6x3 ≥ 9

7x1 + 3x2 + 2x3 ≥ 7

x1,x2,x3 ≥ 0

3. El desarrollo de tres estrategias de un proceso administrativo de fondos de inversión a largo plazo causa costos de 1, 3 y 2 millones de pesos por año de procesamiento, respectivamente. Cada estrategia genera 10, 20 y 40 millones en beneficios por año, en el mismo orden, y se requiere un nivel mínimo de 800 millones en beneficios para que el negocio sea conveniente a los inversionistas. Por último se sabe que la diferencia entre el triple de la duración de la estrategia con costo de 3 millones menos la duración de la estrategia de 2 millones debe ser de por lo menos 10 años. ¿Cuál es la duración óptima de cada estrategia que garantiza los beneficios esperados y minimiza los costos de administración?

4. Para  el  eficiente  desempeño  de  las  actividades  de  una  empresa  comercializadora de  bienes  raíces,  se  han  cuantificado  para  los  departamentos  los  costos  de  ventas y administración en Xfas 10,500.00 y 12,000.00 respectivamente. Mientras que para una casa los mismos costos ascienden a Xfas 18,000.00 y 10,000.00, respectivamente. La utilidad que reporta cada departamento es de Xfas 150,000.00 y de 300,000.00 para cada casa. La empresa desea reducir al nivel mínimo posible el importe de sus costos totales manteniendo una utilidad de al menos Xfas 18,000,000.00, así como la necesidad de que la cantidad de departamentos vendidos a lo menos sea el doble de casas vendidas. ¿Cuál es la combinación óptima de departamentos y casas que se deben comercializar? y, ¿cuál es el importe de los costos totales con el nivel de ventas calculado?

Solución problema 1 Evangelina Nzang (pag. 6). Excelente uso del problema dual.

Solución problema 1 Angela Anguesomo (pag. 5). Buena solución.

Solución problema 4 Evangelina Nzang (pag. 3 y 4). Aunque en la página 4 en las líneas antes de la Tabla al final de la página hay unos errores, creemos que son errores de tipeo y está claro que la formulación es correcta. Hace un uso excelente de la solución dual.

Solución problema 3 Tomás Ndjá (pag. 5). Como no tiene punto inicial factible, ha utilizado el método de las dos fases pero de comienzo, se equivoca en la formulación de la primera parte, en los signos de las variables artificiales R.

El primer parcial.

1. Un comercio dispone de 60 unidades de un producto A por el que obtiene un beneficio por cada unidad que vende de 250 xfas. También dispone de 70 unidades de otro producto B por el que obtiene un beneficio por unidad vendida de 300 xfas. El comercio puede vender como máximo 100 unidades de sus productos. Utilizando técnicas de programación lineal, determina las unidades de los productos A y B que el comercio debe vender para que su beneficio sea máximo y calcula dicho beneficio. 

Sol: (30,70) Beneficio: 28.500 xfas

2. Una factoría fabrica dos tipos de artículos A y B. Para su elaboración se requieren dos máquinas M1 y M2. El artículo A necesita 1 hora de la máquina M1 y 2 horas de la máquina M2. El artículo B necesita 1 hora de cada una de las máquinas. Las máquinas M1 y M2 están en funcionamiento a lo sumo 40 y 50 horas a la semana, respectivamente. Hay que fabricar al menos 2 unidades de B. Por cada unidad del artículo A se obtiene un beneficio de 200€ y por cada uno de B 90€.

a) ¿Cuántas unidades de A y B deben fabricarse semanalmente para obtener el máximo beneficio?

b) Para obtener el máximo beneficio, ¿las dos máquinas han trabajado el máximo de horas semanales?

Sol: a) (24,2) b)No

3. Una empresa debe tener, como máximo, 140 trabajadores de dos tipos: transportistas y empleados de almacén. Por cada transportista debe haber como máximo 4 empleados de almacén y estos últimos deben ser, a lo sumo, 80. Por cada transportista, la empresa recibe una subvención de 1200€ y, por cada empleado de almacén, una subvención de 1800€.

a) ¿Se cumplen las condiciones anteriores con 30 transportistas y 70 empleados de almacén?

b) ¿Cuál es el número óptimo de transportistas y empleados de almacén para obtener la mayor subvención posible?

c) Si las subvenciones (transportistas y almacenistas) bajan a 1000€, calcule todas las posibles soluciones óptimas del problema.

Sol: a) Si b) (60,80) Subvención: 216000€  c) a*(60,80) + b*(140,0), a+b=1

************************************************************************************************************

Solución problema 1 (pag. 4) Angela Anguesomo. Buena solución gráfica. Le faltó evaluar un vértice, aunque en él no ocurre el óptimo.

Solución problema 2 (pag. 2) Angela Anguesomo. Excelente solución gráfica.

Solución problema 3 Nazario Evuy (pag. 1). En realidad sólo formuló el problema pero no resolvió nada. Ha debido usar Simplex o gráficos.

1. Una empresa está estudiando llevar a cabo una campaña publicitaria, para ello dispone de 1.000.000 de euros. Puede difundir sus anuncios en dos canales publicitarios distintos, el primero de ellos cobra 15.000 euros cada vez que emite un anuncio, mientras que el segundo cobra el doble. La probabilidad de que un anuncio del primer canal sea visto es del 30 %, mientras que del segundo es del 70 %. Como mínimo deben emitirse 26 anuncios en el primer canal y 13 en el segundo.  Determine el número de anuncios que debe lanzar en cada canal de manera que maximice la probabilidad de que se vea el anuncio de la empresa, teniendo en cuenta la restricción presupuestaria y las del número de anuncios. 

   1. Defina las variables y formule el modelo del sistema.

   2. Trabaje el problema usando el método Simplex paso a paso, para encontrar la solución óptima (maximizar que los anuncios se vean).

   3. Encuentre la nueva solución si se retira la segunda restricción (número mínimo de anuncios)

   4. Si se pudiera invertir más dinero, ¿en cuál de las cadenas lo invertiría? Justifique su respuesta

2. Considere el siguiente problema:

Max z = -x1 + 4x2

sujeto a:

-3x1 + x2 ≤  6

x1 + 2x2 ≤  4

x2 ≥ -3

x1 no está restringido

2. 1. Calcule la solución del problema usando el método gráfico

   2. Calcule la solución del problema usando el método del Simplex. Observe que x1  no está restringido y x2 tiene un límite inferior en -3.

3. Una empresa de transporte quiere organizar un viaje para 320 personas. Dispone de 4 autocares de 60 plazas y 5 autocares de 40 plazas. Si el costo de cada autocar de 60 plazas es igual a 320 euros y el costo de cada autocar de 40 plazas es de 230 euros:

   1. Plantear el problema que determina el número de autocares de cada tipo que se han de elegir para minimizar los costos globales. 

   2. Determinar la solución óptima y hallar el costo global mínimo usando Simplex.

 *********************************************************************************************************************************

Solución problema 2 de Nazario Evuy (pag. 2). En realidad no ha descrito la solución gráfica. Sólo dice que la hizo y obtuvo el resultado, pero no está bien. Ha debido incluir la gráfica. También, al tener una variable irrestricta ha debido escribir el problema de Programación Lineal que lo describe.

Solución problema 3 Evangelina Nzang (pag. 2). Excelente uso de la formulación dual.

Solución pregunta 1 por A. Ikako en : https://rebrand.ly/b8f96b

Solución pregunta 2 por D. Ntutumu: https://bit.ly/3JibFqm.

Solución pregunta 3 por S. Nsué: https://bit.ly/3qPN5a9

Solución por D. Ntutumu: https://bit.ly/3Narn8d.

P4. En la figura que se encuentra abajo, se muestran los costos por llevar mercancías de una ciudad a otra. (A) Encuentre la interconexión más barata que permita llegar directa o indirectamente a todas las ciudades. (B) ¿Qué puede hacer para asegurar que la conexión de LA a CH aparezca en la solución?

(P3) Una compañía que opera 10 horas al día, fabrica 3 productos con 3 procesos de acuerdo a la tabla que se muestra a continuación. Se desea que calcule el valor optimo (número de unidades del producto 1, 2 y 3, y función objetivo). Luego se quiere saber en cuál de los 3 procesos habria que invertir para producir más y mejor, use el precio dual para tomar esa decisión. Por último, si el precio de venta del producto 3 se baja a 3$, calcule el nuevo valor de la función objetivo sin tener que resolver de nuevo el problema. Los procesos 1, 2, 3 pueden operar simultáneamente.

(P4) En el siguiente problema determine la solución óptima y calcule los costos sombra. Determine en cuál elemento de la Disponibilidad Diaria se debe aumentar para mejorar más la función objetivo y cuáles son las nuevas variables óptimas. Asimismo, indique como resulta afectada la función objetivo si ocurre un cambio unitario en cualquiera de los precios de venta.

(P5) En el siguiente problema determine la solución óptima y calcule los costos sombra. Determine en cuál elemento de la Disponibilidad Diaria se debe aumentar para mejorar más la función objetivo y cuáles son las nuevas variables óptimas. Asimismo, indique como resulta afectada la función objetivo si ocurre un cambio unitario en cualquiera de los precios de venta.

(P6) En el siguiente problema determine la solución óptima y calcule los costos sombra. Determine en cuál elemento de la Disponibilidad Diaria se debe aumentar para mejorar más la función objetivo y cuáles son las nuevas variables óptimas. Asimismo, indique como resulta afectada la función objetivo si ocurre un cambio unitario en cualquiera de los precios de venta.

Solución S. Nsué: https://bit.ly/3qS8aAu

1. Una empresa está estudiando llevar a cabo una campaña publicitaria, para ello dispone de 1.000.000 de euros. Puede difundir sus anuncios en dos canales publicitarios distintos, el primero de ellos cobra 15.000 euros cada vez que emite un anuncio, mientras que el segundo cobra el doble. La probabilidad de que un anuncio del primer canal sea visto es del 30 %, mientras que del segundo es del 70 %. Como mínimo deben emitirse 26 anuncios en el primer canal y 13 en el segundo.  Determine el número de anuncios que debe lanzar en cada canal de manera que maximice la probabilidad de que se vea el anuncio de la empresa, teniendo en cuenta la restricción presupuestaria y las del número de anuncios. 

   1. Defina las variables y formule el modelo del sistema.

   2. Trabaje el problema usando el método Simplex paso a paso, para encontrar la solución óptima (maximizar que los anuncios se vean).

   3. Encuentre la nueva solución si se retira la segunda restricción (número mínimo de anuncios)

   4. Si se pudiera invertir más dinero, ¿en cuál de las cadenas lo invertiría? Justifique su respuesta

2. Considere el siguiente problema:

Min z = 5000x1  + 7000x2 

sujeto a:

-2x1  + x2  ≥  -5

x1  - x2  ≥  1

x1 , x2  ≥  0

2. 1. Calcule la solución usando Lingo con 5000 y 7000 en la función objetivo y con 5 y 7. ¿Obtuvo la misma solución --una multiplicada por 1000 da la otra--?

   2. Calcule la solución usando el método de las dos fases del Simplex, paso a paso, y (5,7) en la función objetivo. Identifique en la primera fase un punto factible y la solución óptima en la segunda fase

3. Considere el siguiente problema:

Max z = -x1 + 4x2

sujeto a:

-3x1 + x2 ≤  6

x1 + 2x2 ≤  4

x2 ≥ -3

x1 no está restringido

3. 1. Calcule la solución del problema usando el método gráfico

   2. Calcule la solución del problema usando el método del Simplex. Observe que x1  no está restringido y x2 tiene un límite inferior en -3.