• Aventures científiques
  • Experimenta
  • Notícies
  • Pregunta
  • Jocs i recursos educatius
  • Turisme científic
  • Cerca avançada
  • Aventures científiques
  • Experimenta
  • Notícies
  • Pregunta
  • Jocs i recursos educatius
  • Turisme científic
  • Cerca avançada
Inici16: Les moltes cares de l’optimització!
Tornar

16: Les moltes cares de l’optimització!

20 febrer, 2012

Gestionar el transport públic d’una gran ciutat és una tasca realment complicada en la qual s’han de resoldre múltiples problemes. Afortunadament, molts d’ells es poden escriure en el mateix “idioma”.

Fa uns dies ja vam parlar dels problemes relacionats amb la planificació del transport públic d’una gran ciutat. Escollir el traçat, la freqüència de pas i el tipus de vehicle que farà cada ruta tenint en compte les interaccions que es produeixen entre elles i amb la resta del trànsit és un problema que posa a prova a milers d’experts en investigació operativa.

Avui hem tornat a visitar la UPC perquè Francesc López  ens acabi d’explicar com poden resoldre tots aquests problemes fent servir eines d’àlgebra lineal.

De l’àlgebra a la investigació operativa passant per la geometria

Per resoldre molts dels problemes que tracta en la seva investigació, en  Francesc fa servir, entre d’altres, l’algorisme del Símplex. Aquest algorisme permet resoldre un tipus específic de models matemàtics així que el primer que cal fer és reescriure el problema en forma d’inequacions lineals.

Cada inequació lineal estarà associada a una restricció del nostre problema. Així, per exemple, hi haurà una que dirà que dues línies no poden passar pel mateix lloc a la vegada, hi haurà una altra que dirà que cada vehicle només podrà fer-se servir en una línia i que els usuaris que entren en un punt al metro n’han de sortir per un altre.

Com veieu, moltes d’aquestes restriccions són “de calaix” però cal recordar que per a l’ordinador només són inequacions i que som nosaltres, els qui les interpretem, els qui ens hem d’assegurar que tota solució “absurda” queda fora del nostre model. De fet, tot sovint expressar aquestes restriccions en forma d’inequació lineal no resulta gens senzill i bona part de la feina rau a trobar una bona combinació d’inequacions i demostrar que realment funciona.

Un cop reescrit el nostre model fent servir inequacions lineals l’algorisme del símplex l’interpreta com un poliedre en moltes dimensions. Així, cada inequació és un pla de tall que deixa fora algunes solucions “impossibles” i deixa dins tota la resta. Si anem afegint més inequacions el que passa és que cada cop queden menys solucions possibles dins del nostre model i com si fóssim escultors anem creant, cara a cara, el políedre de les solucions factibles.


                                        Políedre de dimensió 3.

Finalment a partir d’aquí l’algorisme del símplex cerca un vèrtex del nostre políedre i va resseguint les arestes fins a trobar la solució òptima.

Més dimensions = més problemes.

A la imatge podeu veure un exemple en 3 dimensions però els problemes amb els quals treballen els experts en planificació urbana poden arribar a tenir milions de variables i altres tantes dimensions. Com més dimensions i més cares té el poliedre associat al nostre problema més dificultats tindrà l’algorisme del símplex per a trobar la solució òptima.

Així, tot i que l’algorisme del símplex ens proporciona sempre una solució òptima i que els problemes escrits en forma de inequacions lineals tenen propietats matemàtiques que ens ajuden a resoldre’ls no sempre n’hi ha prou i de vegades cal fer servir tècniques encara més sofisticades.

Etiquetes: Matemàtiques, Matemàtiques a la vista!

Comparteix!
Tweet

Respondre Cancel·la les respostes

Equip Investigador

Carlos Luna

Pau Senra

Pura Fornals

Veure tot l'equip »

Diari de Recerca

El projecte »

18: Per a saber-ne més

17: Cloenda

16: Les moltes cares de l’optimització!

15: Un eixam de solucions possibles!

14: Més val prevenir que ensorrar!

13: L’atmosfera al descobert

12: Les poblacions arriben a bon port

11: Un bon model només és la meitat!

10: Hora punta!

9: Un bosc de paràmetres!

8: Baixa la ràdio… que no sento la tele!

7: Nous vents per a problemes antics

6: Poblacions en moviment

5: Modelització Matemàtica

4: Les Granotes

3: El Laberint Màgic

2: El joc dels Gratacels

1: Les Torres de Hanoi

Piulades recents

  • RT @AmgenSpain: ¿Conoces Amgen #TransferCiencia? Un apasionante proyecto educativo realizado en colaboración con @fundaciorecerca que prete…
  • RT @IESCamiloJCela: Charla clase on-line con la investigadora Marta Fierro Fernández, investigadora del @CSIC y del Centro Severo Ochoa @CB…
  • RT @claretbarcelona: L'alumnat de #batxillerat s'endinsa en la recerca en #genètica i #biotecnologia participant d'un taller formatiu a càr…
Amb el suport de:
Copyright © 2014 Design by FCRi.cat.
  • Qui som
  • Contacte
  • Avís legal
  • RSS
Atenció! Aquest lloc web utilitza cookies i tecnologies similars. Si no canvia la configuració del seu navegador, vostè n’accepta l’ús.
Veure política de privacitat i condicions d’ús
Acceptar