Pauta C3 1s2024 ICN344

Gestión de Operaciones II - ICN344
CERTAMEN 3 1s 2024
GESTIÓN DE OPERACIONES II - ICN344
Profesores : Mónica López C. - Cristian Álvarez C.

Ayudantes : Esteban Fernández, Isaı́as Puelles, Alejandro Quiroga, Lucı́a Saavedra
PARTE 1: CONCEPTOS (40 pts)
1. Considere el problema de encontrar la ruta de costo mı́nimo (SPP) para ir desde 1 a N , donde cada
arco que conecta nodos i, j ∈ {1, ..., N } tiene un costo de cij ∈ Z+ . La formulación dual de este
problema es la siguiente:
max d1 − dN
di + cij ≤ dj ∀i, j ∈ 1, ..., N
Responda lo siguiente (10 pts):
• Al resolver este problema, ¿qué interpretación tiene el valor de las variables di , ∀i ∈ {1, ..., N }?
• ¿Qué representa el valor óptimo de la función objetivo del problema dual?
• ¿Qué rol cumple la restricción en los algoritmos revisados?
Al resolver el dual, di ∀i ∈ N representa el costo óptimo para llegar a i ∈ N (3 pts). El valor óptimo
de la función objetivo es equivalente a min dN y representa el costo de la ruta mı́nima (3 pts). La
restricción del dual se utiliza en los algoritmos para asegurar el cumplimiento de las condiciones de
holgura complementaria, de forma que si di + cij < dj entonces conviene activar el arco (i, j), es
decir, xij = 1. En caso contrario, no hay beneficio por utilizar el arco (i, j) y xij = 0 (4 pts).
2. Suponga que debe enviar un paquete desde el nodo 1 hasta el nodo N , a través de una red logı́stica
representada por un grafo dirigido. En lugar de representar costos, el parámetro cij representa la
probabilidad de éxito del envı́o de paquete desde i a j. ¿Qué cambios deberı́amos considerar en el
modelo SPP para tomar en consideración maximizar las probabilidades de éxito del envı́o? (10 pts).
Todas las restricciones se mantienen igual, Qpero debemos cambiar la función objetivo a maximización
(3 pts). La función quedarı́a como max i,j cij xij siendo xij la variable binaria que toma valor 1 si
se activa el arco (i, j) y 0 en otro caso. El problema queda no lineal. (7 pts).
3. En el contexto del problema del vendedor viajero (TSP), para una red sobre un conjunto N de nodos,
que incluye al nodo origen, analice la siguiente restricción:
XX
Xij ≥ 1
i∈Q j∈Q̂
donde Q ⊂ N , Q̂ ⊂ N , Q ∩ Q̂ ≡ ∅ y además Q ∪ Q̂ ≡ N . ¿Qué implica esta restricción en el TSP?

(10 pts).
La restricción nos dice que para cualquier par de subconjuntos Q y Q̂ debe haber al menos un arco
que los conecte (5 pts). Esto en el contexto de TSP implica que no pueden haber subtours (5 pts).
Departamento de Industrias. 1 Universidad Técnica Federico Santa Marı́a

4. En los problemas revisados, se minimiza una función de costos totales sujeta a una serie de restric-
ciones que entrega como resultado una o varias rutas de transporte. ¿Qué otros aspectos competitivos
en transporte pueden no estar siendo considerados al buscar minimizar costos? ¿cómo podrı́amos
considerarlos? (10 pts)
Al mininmizar costos se dejan de priorizar aspectos como los riesgos asociados al transporte, la uti-
lización de flota, el nivel de servicio que podrı́a estar medido con los tiempos de entrega, la confiabili-
dad de la entrega, entre otros (8 pts). Mediante la obtención de los parámetros relacionados se podrı́an
formular nuevas restricciones y variables para incorporar estos aspectos y asegurar que se cumplirá
cierto estándar (2 pts).

CERTAMEN 3 1s 2024
GESTIÓN DE OPERACIONES II - ICN344
Profesores : Mónica López C. - Cristian Álvarez C.

Ayudantes : Esteban Fernández, Isaı́as Puelles, Alejandro Quiroga, Lucı́a Saavedra
PARTE 2: PROBLEMA (60 pts.)
1. Considere el siguiente grafo, en el que se tienen 3 nodos con sus respectivas ofertas y 2 nodos con
sus respectivas demandas. Sobre cada arco en itálica aparecen los costos unitarios de transporte.
a) Encuentre la asignacion óptima de transporte tal que satisfaga ofertas y demandas al mı́nimo costo,
utilizando el algoritmo de Hitchcock. Inicie con la regla de esquina noroeste. (25 pts)
b) Exprese la solución como un grafo y calcule el mı́nimo costo total (5 pts).
c) ¿Es posible aplicar en la práctica la solución óptima encontrada? Explique a detalle (5 pts).
2. Considere la siguiente modificación sobre el grafo anterior: ahora se tiene además, UN NODO DE
TRANSFERENCIA entre orı́genes y destinos. TODOS los arcos desde y hacia el nodo de transferencia
tienen costo 3.
d) Elabore el tableau correspondiente y obtenga una solución inicial en el mismo mediante esquina noroeste
(25 pts).

PAUTA PROBLEMA
a). Debemos crear un nodo oferta ficticio (4) con arcos a costo 0 para balancear el problema. Con la
regla de esquina noroeste la tabla queda ası́:
1 2 Oferta
1 20 0 20
2 20 0 20
3 X 40 40
4 10 10 20
Demanda 50 50 100
Chequeamos degenerancia para comprobar que #{Xij } = 5 = 4 + 2 − 1. Por lo tanto podemos revisar
condiciones de HC:
Para Xij > 0, con µ1 = 0 entonces cij = µi + vj :
(1, 1): c11 = µ1 + v 1 → v1 = 10
(2, 1): c21 = µ2 + v 1 → µ2 = −2
(3, 2): c32 = µ3 + v 2 → µ3 = 5
(4, 1): c41 = µ4 + v 1 → µ4 = −10
(4, 2): c42 = µ4 + v 2 → v2 = 10
Para Xij = 0, cij − µi − vj > 0
(1, 2): c12 − µ1 − v2 = 12 − 0 − 10 = 2 > 0
(2, 2): c22 − µ2 − v2 = 4 − (−2) − 10 = −4 < 0
Por lo tanto, el pivote será (2, 2), y vamos a generar un ciclo +(2, 2) → −(2, 1) → +(4, 1) → −(4, 2).
Esto da como máximo para redistribuir θ = 10. La nueva tabla es la siguiente:
1 2 Oferta
1 20 0 20
2 10 10 20
3 X 40 40
4 20 0 20
Demanda 50 50 100
Se mantiene que #{Xij } = 5.

Para Xij > 0, con µ1 = 0 entonces cij = µi + vj :
(1, 1): c11 = µ1 + v 1 → v1 = 10
(2, 1): c21 = µ2 + v 1 → µ2 = −2
(2, 2): c22 = µ2 + v 2 → v2 = 6
(3, 2): c32 = µ3 + v 2 → µ3 = 9
(4, 1): c41 = µ4 + v 1 → µ4 = −10
Para Xij = 0, cij − µi − vj > 0

(1, 2): c12 − µ1 − v2 = 12 − 0 − 6 = 6 > 0

(4, 2): c42 − µ4 − v2 = 0 − (−10) − 6 = 4 > 0
Por lo tanto encontramos la solución óptima.
b) La solución óptima equivale a X11 = 20, X21 = 10, X22 = 10, X32 = 40, con todas las demás variables
en 0 y con la falta de oferta impactando al cliente 1 X41 = 20. El costo total es $920.
c) En la práctica no es posible implementar la solución tal como la arroja el algoritmo pues esta incluye
un nodo ficticio. Sin embargo la solución encontrada es la óptima a implementar aún con las condiciones
iniciales del problema.
d)
1f 2f 3f 4f 7t 1s 2s Oferta
1f 100 X X X 20 0 0 120
2f X 100 X X 20 0 0 120
3f X X 100 X 40 X 0 140
4f X X X 100 20 0 0 120
7t X X X X 0 50 50 100
1s X X X X X 100 X 100
2s X X X X X X 100 100
Demanda 100 100 100 100 100 150 150 800

Pauta C3 1s2024 ICN344

Cargado por

Copyright:

Formatos disponibles

Pauta C3 1s2024 ICN344

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Pauta C3 1s2024 ICN344

Cargado por

Copyright:

Formatos disponibles

Gestión de Operaciones II - ICN344

Profesores : Mónica López C. - Cristian Álvarez C.

PARTE 1: CONCEPTOS (40 pts)

donde Q ⊂ N , Q̂ ⊂ N , Q ∩ Q̂ ≡ ∅ y además Q ∪ Q̂ ≡ N . ¿Qué implica esta restricción en el TSP?

Departamento de Industrias. 1 Universidad Técnica Federico Santa Marı́a

Departamento de Industrias. 2 Universidad Técnica Federico Santa Marı́a

Profesores : Mónica López C. - Cristian Álvarez C.

PARTE 2: PROBLEMA (60 pts.)

b) Exprese la solución como un grafo y calcule el mı́nimo costo total (5 pts).

Departamento de Industrias. 3 Universidad Técnica Federico Santa Marı́a

Se mantiene que #{Xij } = 5.

Departamento de Industrias. 4 Universidad Técnica Federico Santa Marı́a

(1, 2): c12 − µ1 − v2 = 12 − 0 − 6 = 6 > 0

Departamento de Industrias. 5 Universidad Técnica Federico Santa Marı́a

También podría gustarte