Practica Examen.docx

Ejercicios de repaso Verdadero-Falso

1. V F Existe la seguridad de que los algoritmos heurísticos, al finalizar el proceso, proporcionarán un porcentaje específico de optimalidad. 2. V F La solución óptima para un modelo de optimización combinatoria se puede encontrar, en principio, por medio de la enumeración completa. 3. V F Una heurística alternativa, en el modelo de programación con recursos limitados, consiste en desplazar hacia adelante la actividad que más contribuye a la sobrecarga (es decir, la que requiere la participación del mayor número de personas). 4. V F La programación por metas es la única técnica cuantitativa creada para emplearse en modelos con objetivos múltiples. 5. V F Cada paso de la programación por metas con prioridades absolutas introduce una nueva meta y elimina de cualquier consideración ulterior a todas las candidatas actuales que no sean capaces de satisfacer también, en la medida de lo posible, esa nueva meta. 6. V F Considere la restricción de la meta 12x1_ 3x2 _ u1 _ v1 _ 100. Suponga que, por la presencia de otras restricciones del modelo, esa meta no pueda ser alcanzada. Si u1 es positiva, la meta se alcanzará con un margen excedente. 7. V F Una forma de establecer prioridades entre diversas metas consiste en aplicar ponderaciones a las variables de desviación. 8. V F Considere la restricción del intervalo de la meta 180 _4x1 _ 12x2 _ 250. Una formulación correcta de la meta es 4x1 _ 12x2 _ v1 _ 250 4x1 _ 12x2 _ u1 _ 180 9. V F Si una restricción del intervalo de la meta no puede alcanzarse (satisfacerse con exactitud), entonces una variable de desviación tiene que ser positiva, y la restricción a la cual se aplica dicha variable será activa. 10. V F En la programación por metas no se permite que ninguna restricción del sistema sea violada. 11. V F Nunca un modelo de programación por metas puede ser no factible.

Opción múltiple

12. Si el tiempo requerido para el ajuste inicial a fin de realizar n trabajos en una sola máquina depende de la secuencia, entonces el problema de minimizar el tiempo total de ajuste inicial requiere de la inspección de a. n secuencias b. 1 secuencia c. n! secuencias d. secuencias 13. La noción intuitivamente atractiva que sirve de motivación para un algoritmo codicioso es a. aproximarse lo más posible a la solución óptima b. conseguir el mejor resultado posible en el paso actual c. minimizar el número requerido de pasos d. ninguna de las afirmaciones anteriores 14. En el modelo de la programación de recursos, la operación de restar a los demás elementos de una columna el tiempo de ajuste inicial mínimo correspondiente a la misma a. es un procedimiento heurístico basado en la idea de que importante son los costos relativos b. garantiza la obtención de una solución óptima si se aplica el algoritmo codicioso c. hace que el algoritmo codicioso no resulte útil d. ninguna de las afirmaciones anteriores.

15. Si un modelo de programación por metas incluye la restricción g1(x1, . . . , xn) _ u1 _ v1 _ b1 y el término 6u1 _ 2v1 en la función objetivo, entonces la persona que está a cargo de la toma de decisiones a. prefiere que g1(x1, . . . , xn) sea mayor que b1 no menor b. prefiere que g1(x1, . . . , xn) sea menor que b1 no mayor c. le es indiferente que g1(x1, . . . , xn) sea mayor o menor que b1 16. Los modelos con objetivos múltiples a. son difíciles porque con frecuencia es verdad que al mejorar un objetivo se perjudica otro b. son difíciles porque los objetivos pueden estar expresados en medidas incongruentes entre sí (es decir, como el problema de “combinar manzanas y naranjas”)

c. pueden abordarse en algunas ocasiones con el método de la programación por metas d. todo lo anterior Las preguntas 17, 18, 19 corresponden al siguiente problema: 1. g1(x1, x2) _ b1 es una restricción del sistema 2. La máxima prioridad consiste en minimizar el faltante para el logro de g2(x1, x2) _ b2 3. La siguiente prioridad consiste en minimizar el excedente para el logro de g3(x1, x2) _ b3 17. El primer paso del procedimiento de resolución es a. Min u2, s.a. g1(x1, x2) _ b1; g2 _ u2 _ b2; x1, x2, u2 b. Min u2, s.a. g1(x1, x2) _ b1; g2 _ u2 _ b2; x1, x2, u2 _ 0 c. Min u2, s.a. g1(x1, x2) _ b1; g2 _ u2 _ b2; x1, x2, u2_ 0 18. Sea RF I la expresión que denota los puntos (x1, x2) obtenidos en el primer paso del procedimiento de resolución. El segundo paso es: a. Min u3 _ v3, s.a. (x1, x2) en RF I y g3(x1, x2) _ u3 _ v3 _ b3 b. Min u3, s.a. (x1, x2) en RF I y g3(x1, x2) _ u3 _ b3 c. Min v3, s.a. (x1, x2) en RF I y g3(x1, x2) _ v3 _ b3 19. En este modelo: a. será posible alcanzar por lo menos una de las metas b. si no se alcanza la primera meta, la segunda tampoco podrá alcanzarse c. ninguna de las dos 20. Considere un programa por metas con la siguiente restricción: g1(x1, . . . , xn) _ v1 _ b1, v1> 0 y con v1 en la función objetivo. En ese caso a. La meta consiste en minimizar el excedente del logro b. Si v* > 0 entonces la restricción será activa c. ninguna de las afirmaciones anteriores d. tanto a como b.

Problemas 9-5. Sam Hull es el gerente de mercadotecnia de una compañía farmacéutica. Tiene que asignar cinco visitadores médicos a cinco hospitales. La siguiente tabla muestra las ventas esperadas. (a) Aplique una heurística codiciosa para asignar cada uno de los visitadores médicos a cada hospital, de manera que se maximice el total de las ventas esperadas. (b) Utilice la heurística modificada de la sección 9.2 (es decir, después de transformar los datos restando las ventas máximas en cada columna a todos los demás elementos de dicha columna, aplique la heurística codiciosa) para encontrar una nueva solución. ¿En qué medida es mejor el desempeño de esta heurística que el de la utilizada en la parte (a)?

SOLUCION: a) utilizando la heurística codiciosa la asignación de vendedores será la siguiente: 1-A 2-B 3-D 4-C 5-D

Teniendo una venta total esperada de 110.

25 21 21 25 18 110

b) transformando datos de la tabla: 30 A 1 2 3 4 5

26 B

-5 -10 -7 0 -2

25 C

-8 -5 -7 0 -4

22 D

-2 -7 -5 0 -2

20 E

0 -7 -1 0 -2

-4 -8 0 0 -2

Utilizando la heurística modificada se tiene : 4A 3E 1D 5C 2B

30 20 22 23 21 116

Se tiene como ventas esperadas : 116. Por lo tanto este procedimiento modificado es mucho mejor que la heurística codiciosa ya que muestra un dato optimo máximo de ventas, aparte de ser más rápida y eficiente. 9-6. Tres trabajos —J1, J2 y J3— tendrán que ser realizados en un mismo torno. El costo de la preparación o ajuste inicial para cada trabajo depende del ajuste realizado para el trabajo anterior. El costo de esos cambios de trabajo se presenta en la tabla siguiente. En estos momentos, el torno no ha sido ajustado aún para algún trabajo. (a) Use la heurística codiciosa para programar los trabajos. El objetivo es minimizar el costo total de ajuste o preparación para los trabajos. (b) Use la heurística modificada en la sección 9.2 para programar los trabajos. (c) ¿Se obtiene siempre un resultado mejor con la heurística modificada que con la heurística codiciosa?

SOLUCION a) Utilizando la heurística codiciosa de tiene el siguiente resultado: 0-J2 J2-J3 J3-J1

35 30 35 100

Por lo tanto el costo minimo con este procedimiento es de $100. b) Transformando los datos: 35 J1

25 J2

S/A J1 J2 J3

15 6 0

30 J3

10 5

9 4 0

0

Con la heurística modificada se tiene los siguientes datos : S/A-J3 J3-J2 J2-J1

39 25 41 105

S/A-J3 J3-J1 J1-J2

39 35 30 104

c) no se cumple la teoría de la heurística modificada por que en este caso se incurren a mayores costos en los distintos caminos para proceder con la operación del torno: $105 y $104. Por tanto el método codicioso refleja un costo mucho menor que es de $ 100. 9-11. Considere el siguiente modelo de programación por metas Min P1v1 +P2v2 + P3u3 + P4(u4+v4) s.a. x2 + u1 -v1 = 100 x1+ x2 +u2- v2 = 80 x2 +u3 = 40 x1 +2x2 +u4 - v4 = 160 x1, x2, u1, u2, u3, u4, v1, v2, v3, v4 ≥0 (a) Use el método gráfico para resolver el modelo. (b) Interprete la tercera meta x2+ u3 = 40. (c) Sustituya x2 + u3=40 con x2 + u3 ≥ 40. ¿Cuál será la nueva interpretación? (d) Aplique el método gráfico para resolver el modelo con la sustitución propuesta en (c).

SOLUCION: a) graficando las restricciones se tiene:

 

Notese que no todas las restricciones son activas por lo tanto no existe solución en el modelo. No existe región de factibilidad. .

b) interpretando la tercera meta : x2+ u3 = 40, teniendo igualdad se dice entonces que u3≥0 y v3 es cero y satisfacen la meta , y que en esta restricción la decisión de un faltante es permitida ya que la variable de desviación de excedente ya es cero. c) cambiando la restricción a : x2+ u3 ≥ 40 si la u optima es positiva , esta restricción será activa ,porque de lo contrario u3* podría hacerse más pequeña. La v3* por lo tanto tendrá en valor de cero y no aparecerá en la función objetivo. La decisión de una faltante será permitida.

d)graficando :



.

9-12. Considere el siguiente modelo de programación por metas Min P1v1 + P2v2 + P3v3 + P4(u4 + v4) s.a. x2 + u1 - v1 = 100 x1 + x2 + u2 - v2 = 80 x1 - v3 = 40 x1 + 2x2 + u4 - v4 = 160 x1, x2, u1, u2, u3, u4, v1, v2, v3, v4 ≥0

(a) Utilice el método gráfico para resolver el modelo. (b) Interprete la tercera meta x1 -v3 =40. (c) Sustituya x1 - v3 = 40 por x1 - v3 ≤40. ¿Cuál será la nueva interpretación? (d) Aplique el método gráfico para resolver el modelo con la sustitución propuesta en (c). SOLUCION: a)

b) interpretando la tercera meta : x1-v3 = 40, teniendo igualdad se dice entonces que u3=0 y v3 ≥0 y satisfacen la meta , y que en esta restricción la decisión de un excedente es permitida para llegar a la meta ya que la variable de desviación de faltante ya es cero. c) sustituyendo la restricción por x1 - v3 ≤40 entonces será una restricción de un modelo de prioridades absolutas en donde la variable u3* =0 y que es permitible que un v3* sea aumentada para llegar a la meta .

d) graficando:



.

9-13. Considere el siguiente programa por metas:

Min P1u2 + P2v1 + P3u3 s.a. x1 + x2 + u1 - v1 = 80 x1 + u2 - v2 = 100 x2 + u3 ≥45 x1, x2, u1, v1, u2, v2, u3 ≥0

(a) Resuélvalo por medio del método gráfico.

(b) ¿Se ha alcanzado la meta correspondiente a la primera prioridad? R: Si se ha alcanzado a la meta ya sea con estos resultados:  X1=80,X2=0------------- X2=80,X1=0 Teniendo intersección a su vez con la 3era restricción (c) ¿Y qué podemos decir de la segunda y tercera prioridades?

para llegar a las cantidades precisas de las metas X1=35,X2=45 se debe añadir u2*=65 y v2*=0 en la restricción 2 para asi tener las metas precisas.