PROBLEMAS EL CAMINO MAS CORTO

? ? ? ? ? - + ? ? ? - + ? ? ? ? ? - + ?? 1 1 ? 2 2 ? - P3 = Min ( y3 ) Soluciones óptimas: Valor óptimo: 0 ? B s.a ?0.35 x1 = 210 ? ?0.25 x2 = 100 ?0.15 x1 + 0.25x2 = 115 ? ?0.4 x1 + 0.6 x2 - y+ + y- = 240 ? ? x1 = 0, x2 = 0 ? y1 = 0, y1 = 0 ? ? x1 - 2 x2 - y+ + y- = 0 ? y2 = 0, y2 = 0 ? + - ? x2 - y3 + y3 = 300 ? y3 = 0,y3 = 0 (1) (2) (3) (4) (5) (6) Solución óptima: (418.182, 209.091) Valor óptimo: 90.909 La solución óptima consiste en elaborar diariamente 418.182 kg de panintegral y 209.091 kg de pan de centeno. El beneficio diario es 292.73€ + - ( y1 = 52.7274, y1 = 0), la producción de pan integral es exactamente el doble que + - laproducción de pan de centeno ( y2 = 0, y2 = 0), y la producción de este último - + es aproximadamente 209kg diarios ( y3 = 90.909, y3 = 0). Se cumplen, por lo tanto, la1ª y la 2ª meta y no la 3ª. 15


3. a) a) Se considera el siguiente grafo: 3 2 5 9 1 a 7 1 4 4 2 7 1 4 3 2 6 6 4 (5 puntos) Si los valores de cada arco representandistancias, hallar razonadamente cómo debe ser a para que la ruta más corta del nodo 1 al 7 pase obligatoriamente por el nodo 2. Indicar esta ruta más corta. b) (5puntos) Si a = 5 y los valores de los arcos representan capacidades de flujo, calcular el valor del flujo máximo del nodo 1 al 7. Solución: Los caminos del nodo 1al nodo 7 pasan bien por el nodo 2, por el 3 o por el 4. Aplicando el método de la ruta más corta, calculamos los caminos más cortos desde cada uno de estos nodos alnodo 7. En el siguiente grafo se observa que el camino más corto del nodo 2 al nodo 7 es (2,4,6,7) cuyo valor es 8. 3 2 0 5 3 9 1 4 2 4 1 7 8 1 2 6 3 3 4 6 2 16