problemas de la semana
Problemas de la Semana 8. 23 al 27 de abril
Resuelva el problema 2 de la semana 4 y el 3 y 4 de la semana 3, por el método dual.
Para el problema de transporte que se muestra a continuación encuentre la solución de mínimo costo utilizando:
El problema dual
El método de Stepping Stone
El método de multilicadores
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
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.
5. Para el problema de Asignación que se muestra a continuación, encuentre la aignación óptima de cada depósito (1,2,3,4) a cada almacén (A, B, C, D).
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.
Problemas de la Semana 7. 16 al 20 de abril
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
Problemas de la Semana 6. 09 al 13 de abril
Para el Problema de Transporte que se muestra a continuación, resuélvalo
Por el método Simplex primal
Por el método Simplex dual
Por el Método del Stepping Stone
Por el método de Multiplicadores
Problemas de la Semana 5. 02 al 05 de abril
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.
Sistema primal:
min Z = 12x1 + 7x2
Sujeto a:
4x1 +2x2 ≥ 80
3x1 + 4x2 ≥ 90
x1, x2 ≥ 0
Sistema primal
min Z = 5x1 + 8x2 + x3
Sujeto a:
x1 + 4x2 + 6x3 ≥ 9
7x1 + 3x2 + 2x3 ≥ 7
x1,x2,x3 ≥ 0
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?
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?
Problemas de la Semana 4. 18 al 21 de marzo
Problemas de la Semana 3. 11 al 15 de marzo
Para todos los problemas a continuación se desea que calcule el óptimo usando Simplex. En el último problema se desea que calcule todos los posibles óptimos en el apartado (c). Las regiones factibles de cada problema se recogen a continuación de los enunciados.
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
Fig. 1. Región factible problema 1
Fig. 2. Región factible problema 2
Fig. 3. Región factible problema 3
Problemas de la Semana 2. 4 al 8 de marzo
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.
Defina las variables y formule el modelo del sistema.
Trabaje el problema usando el método Simplex paso a paso, para encontrar la solución óptima (maximizar que los anuncios se vean).
Encuentre la nueva solución si se retira la segunda restricción (número mínimo de anuncios)
Si se pudiera invertir más dinero, ¿en cuál de las cadenas lo invertiría? Justifique su respuesta
Considere el siguiente problema:
Max z = -x1 + 4x2
sujeto a:
-3x1 + x2 ≤ 6
x1 + 2x2 ≤ 4
x2 ≥ -3
x1 no está restringido
Calcule la solución del problema usando el método gráfico
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.
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:
Plantear el problema que determina el número de autocares de cada tipo que se han de elegir para minimizar los costos globales.
Determinar la solución óptima y hallar el costo global mínimo usando Simplex.
Problemas de Cursos Anteriores
Problema semana 11 (13 de junio): El tercer parcial https://bit.ly/3CwX6vt.
Solución pregunta 1 por A. Ikako en : https://rebrand.ly/b8f96b
Problemas semana 8 (12 de mayo): El segundo examen en https://bit.ly/41BArrW
Solución pregunta 2 por D. Ntutumu: https://bit.ly/3JibFqm.
Solución pregunta 3 por S. Nsué: https://bit.ly/3qPN5a9
Problemas de la semana 7 (05 de mayo):
P1 (3 personas): Un famoso artista guineano va a comenzar este verano un tour donde visitará 10 ciudades y quiere hacerlo al menor costo posible, pasando por por cada ciudad sólo una vez. No importa de que ciudad salga, tiene que volver a la misma ciudad cuando haya terminado. Los costos de visita entre ciudad y ciudad se muestra a continuación. Formule el problema como uno de TSP y calcule la solución usando Lindo. Si obtiene 2 o más subtours, eso no es solución válida. luego aplique el algoritmo de B & B para obtener una solución que en un sólo recorrido pase por todas las ciudades una vez.
Solución S. Nsué, A. Milam, A. Ikako en: http://rb.gy/iu5u9
Problemas de la semana 6 (28 de abril):
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 2. 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 2, 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
Problemas de la semana 5 (21 de abril): En el problema 4 (el mapa) encuentre el Árbol de Mínima Expansión
Solución por D. Ntutumu: https://bit.ly/3Narn8d.
Solución por C. Belarmino https://bit.ly/3opHSoH.
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?
Solución problema 2, semana 5: por C. Belarmino en https://bit.ly/3opHSoH
Semana 4 (14 de abril): Resuelva el examen que puede bajar de https://bit.ly/3H6SxdU
Solución del problema A por C. Belarmino: https://bit.ly/3Iu3Ygj
Solución de problema B por A. Ikako en https://bit.ly/450215b
Semana 3 (30 de marzo):
(P1) Para el siguiente problema de optimización, calcule el valor óptimo, los valores de x1 y x2, los precios duales y el nuevo valor de la función objetivo si se cambian los coeficientes de z. Observe que el (0,0) NO es un punto factible, por lo que tiene que conseguir uno por el método de las dos fases.
(P2) Para el siguiente problema de optimización, calcule el valor óptimo, los valores de x1 y x2, los precios duales y el nuevo valor de la función objetivo si se cambian los coeficientes de z. Observe que el (0,0) NO es un punto factible, por lo que tiene que conseguir uno por el método de las dos fases.
(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.
Solución Problema 4: Hecha por C. Belarmino. En https://bit.ly/42fCvac
(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
Semana 2 (24 de marzo):
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.
Defina las variables y formule el modelo del sistema.
Trabaje el problema usando el método Simplex paso a paso, para encontrar la solución óptima (maximizar que los anuncios se vean).
Encuentre la nueva solución si se retira la segunda restricción (número mínimo de anuncios)
Si se pudiera invertir más dinero, ¿en cuál de las cadenas lo invertiría? Justifique su respuesta
Considere el siguiente problema:
Min z = 5000x1 + 7000x2
sujeto a:
-2x1 + x2 ≥ -5
x1 - x2 ≥ 1
x1 , x2 ≥ 0
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--?
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
Considere el siguiente problema:
Max z = -x1 + 4x2
sujeto a:
-3x1 + x2 ≤ 6
x1 + 2x2 ≤ 4
x2 ≥ -3
x1 no está restringido
Calcule la solución del problema usando el método gráfico
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.
Solución Problema 1 Semana 2: Hecho por D. Ntutumu. En https://bit.ly/3nzVaP0