AplicacionDeLaTeoriaDeLaComplejidadEnOptimizacion

NARRACIONES DE LA CIENCIA Y LA TECNOLOGÍA

Aplicación de la teoría de la complejidad
en optimización combinatoria
Marco Antonio Cruz Chávez
Pedro Moreno Bernal
Jesús del Carmen Peralta Abarca

H

oy en día, a pesar de que las computa-

de recorridos sería tan grande que no alcanzaría a

doras han evolucionado rápidamente

resolverse ni siquiera en varios meses.

y de que son capaces de procesaruna

Otro problema de optimización es el de la mo-

gran cantidad de operaciones por segundo, exis-

chila. En este se plantea llenar una mochila cuya

ten problemas cuya solución puede tardar años

restricción principal es no soportar más que un pe-

en obtenerse. Un ejemplo de este tipo de proble-

so determinado al cargar una parte de un conjunto

ma es el del “agente viajero” —conocido comoTSP

de objetos, cada uno de ellos con un peso y valor

(traveling sales problem), por sus siglas en inglés.

determinados. Debe maximizarse la carga de obje-

Trata de un vendedor que debe visitar cierto nú-

tos en la mochila sin exceder el peso permitido. Su

mero de ciudades. Partiendo de su ciudad de ori-

formulación es sencilla, pero la forma de resolverlo

gen, debe visitar una vez cadaciudad y regresar

es muy compleja. Este problema se presenta como

al punto de partida. El objetivo es encontrar una

aplicación real en las empresas que requieren al-

ruta que reduzca la distancia recorrida. La figura 1

macenar una gran cantidad de productos.

muestra el caso en que el agente tiene que pasar

Se dice que un problema es fácil de resolver

por cuatro ciudades, cada una representadapor

cuando es posible encontrar un algoritmo (méto-

un nodo, así como la distancia respectiva entre

do de solución) cuyo tiempo de ejecución en una

ellas. Este problema tiene aplicación real en em-

computadora crezca de forma “razonable” o mode-

presas que necesitan reducir costos de transporte

rada de acuerdo con el tamaño del problema. Por

y presenta las tres posibles rutas que puedetomar

el contrario, es difícil cuando el algoritmo que lo

el agente viajero. La mejor es la del orden C1, C2,

resuelve tiene un tiempo de ejecución que crece

C4, C3, dado que la distancia de 27 es la más corta.

exponencialmente con el tamaño del problema.

Una forma de resolver este problema sería

Bajo algunas condiciones, el uso de un algorit-

evaluar todas las posibles combinaciones de reco-mo computacional para resolver un problema que

rridos y escoger la de menor costo; pero tan solo

sea adecuado a sus características es suficiente,

para doce ciudades hay 19 958 400 rutas posibles,

pero para otras circunstancias se tienen que dise-

así que sería casi imposible evaluar manualmente

ñar algoritmos computacionales muy específicos

cada recorrido para escoger el mejor. Si elnúmero

para las condiciones dadas, que resuelvan la pro-

de ciudades a visitar fuera de cincuenta, el número

blemática presentada de manera eficaz y eficiente.

Profesor e investigador, Centro de Investigaciones en Ingeniería y Ciencias Aplicadas (Ciicap), UAEM
Doctorado en Ingeniería y Ciencias Aplicadas, Centro de Investigaciones en Ingeniería y Ciencias Aplicadas (Ciicap), UAEM
Profesora einvestigadora, Facultad de Ciencias Químicas e Ingeniería (FCQeI), UAEM

inventio 3 5

Figura 1. Tres posibles rutas para el agente viajero
C1

9

10

C1

5

5
9

10

C3
6

C1

C3

C3
3

C2

6

3
C4

C2

9

C4

C2

3
9

C4

Fuente: autores

Se puede afirmar que para todos los proble-

ra en que se ejecute. Además, conocer el tiempo

mas, existe al menos un algoritmo de solución; sin

exacto que tardaráun programa de cómputo en

embargo, generalmente se tienen o proponen va-

dar resultados es una tarea difícil de determinar.

rios algoritmos para tratar de resolver un proble-

En su lugar, es mejor calcular la cantidad de ope-

ma. Una forma de escoger el mejor es mediante la

raciones que se realizan de acuerdo con los datos

comparación de la eficiencia, que permite evaluar

de entrada...