Exercici 5 - Viatjant de comerç · Matemática Discreta UAB Juny 2026
Tema: Optimització de rutes: carter xinès, viatjant de comerç i complexitat · Del examen Juny (2026)
Enunciado
Una empresa de repartiment ha de distribuir material a diverses poblacions d'una comarca. Cada dia, un vehicle surt del magatzem central, ha de visitar totes les poblacions exactament una vegada i tornar finalment al punt d'origen, intentant minimitzar la distància total recorreguda. Es disposa de les distàncies entre totes les poblacions i el magatzem central de l'empresa.
a.
(0,2 punts) Expliqueu com es pot modelitzar aquesta situació mitjançant un graf ponderat. Indiqueu què representen els vèrtexs, les arestes i els pesos de les arestes.
b.
(0,2 punts) Quin problema clàssic de teoria de grafs o optimització representa aquesta situació? Indiqueu les condicions que ha de satisfer una ruta vàlida en aquest problema.
Solución
Según los criterios oficiales de corrección
a. (0,2 punts) Expliqueu com es pot modelitzar aquesta situació mitjançant un graf ponderat. Indiqueu què representen els vèrtexs, les arestes i els pesos de les arestes.
Solución: La situació es modelitza amb un graf ponderat on: - Els vèrtexs () representen les poblacions i el magatzem central. - Les arestes () representen els trams de carretera o connexions directes viables entre parelles de localitzacions. - Els pesos () de les arestes representen les distàncies quilomètriques (o temps de viatge) entre elles.
b. Quin problema clàssic de teoria de grafs o optimització representa aquesta situació?
Solución: Problema del viatjant de comerç / TSP (Traveling Salesperson Problem)
Indiqueu les condicions que ha de satisfer una ruta vàlida en aquest problema.
Solución: Una ruta vàlida ha de satisfer: - Ser un cicle tancat que comenci i acabi al magatzem central. - Visitar cada vèrtex (cada població) exactament una vegada (cicle hamiltonià). - Minimitzar la suma total dels pesos de les arestes que componen el cicle.
La explicación paso a paso, hecha con IA, es Premium. Premium
Resuélvelo aquí mismo: corrección automática, pistas y solución paso a paso.
‹ Exercici 4 · Juny 2026 · Pregunta 3 (apartat d) - Problema del carter xinès · 2024 ›