Estudiante de preescolar

´
´
TECNICAS DE OPTIMIZACION
COMBINATORIAL
´
PRIMERA EDICION

´
´
RAMON ALFONSO GALLEGO RENDON
ANTONIO ESCOBAR ZULUAGA
Universidad Tecnol´gica de Pereira
o
Pereira - Risaralda - Colombia

´
RUBEN AUGUSTO ROMERO LAZARO
UNESP
Ilha Solteira - SP- Brasil

´
GRUPO DE PLANEAMIENTO EN SISTEMAS ELECTRICOS (GP)
´
GRUPO DE DESARROLLO EN INVESTIGACION OPERATIVA (DINOP)
´
UNIVERSIDADTECNOLOGICA DE PEREIRA

´
´
TECNICAS DE OPTIMIZACION COMBINATORIAL
Textos universitarios
Primera edici´n: Pereira, abril de 2006.
o
ISBN: 958-8272-04-1

Libro resultado de investigaci´n del proyecto:
o
´
NOVEDOSAS TECNICAS COMBINATORIALES
´
APLICADAS AL PROBLEMA DE ASIGNACION
GENERALIZADA Y FLUJO DE REDES APLICADO
AL PROBLEMA DE TRANSPORTE.
C´digo de Investigaci´n: UTP 6-05-5o
o

Impreso y hecho en Colombia
Esta obra se imprimi´ en el
o
Taller de Publicaciones de la
Universidad Tecnol´gica de Pereira
o
Se imprimieron 100 ejemplares

A mis Alfonsos Padre e hijo, a
la memoria de mi madre Ana
Emilia, a mi esposa Eliana y a
mis hermanos.
Ram´n Alfonso
o

A mi esposa Suany, a mis hijos
Laura, David y Juan Pablo que
son mi fuente de inspiraci´n
opermanente.
Antonio

A mi querida hija Ruth Raquel
por darnos la alegria de tenerla
formando parte de nuestra
familia.
Rub´n Augusto
e

AGRADECIMIENTOS
Este texto es el resultado de la investigaci´n Novedosas T´cnicas Combinatoriales Aplicadas
o
e
al problema de Asignaci´n Generalizada y Flujo en Redes Aplicado al Problema de Transporte,
o
investigaci´n apoyada por la UniversidadTecnol´gica de Pereira. A servido como texto gu´
o
o
ıa
en el curso de T´cnicas de Optimizaci´n Combinatorial, dictado por los autores en el programa
e
o
de maestr´ en Ingenier´ El´ctrica, en el programa de maestr´ en Ingenier´ Industrial y en
ıa
ıa e
ıa
ıa
el programa de maestr´ en Ense˜ anza de las matem´ticas, en la Universidad Tecnol´gica de
ıa
n
a
o
Pereira. Los cap´
ıtulos hansido revisados y complementados continuamente. Dentro de esta
tarea han tomado parte activa los estudiantes de los programas, a quienes les agradecemos sus
comentarios.
Un especial agradecimiento por sus aportes y consejos (in memoriam) al Ph.D. Jos´ Alcir
e
Monticelli, quien fuera profesor de la Universidad Estadual de Campinas (UNICAMP-Brasil),
quien contribuy´ con su experiencia en lasaplicaciones de las t´cnicas de optimizaci´n combio
e
o
natorial a los sistemas el´ctricos de potencia y a otras areas del conocimiento. A los profesores
e
´
Ph.D. Secundino Soares y Ph.D. Hermano Tavares, de la UNICAMP y a los profesores Ph.D.
Sergio Azevedo De Oliveira y Ph.D. Jos´ Roberto Sanchez Mantovani, de la Universidad del
e
Estado de S˜o Paulo (UNESP-Brasil), con los cuales hemosmantenido una estrecha relaci´n
a
o
acad´mica y que hacen parte de un selecto grupo de investigadores de la optimizaci´n aplicada.
e
o
Agradecimientos especiales al vicerrector acad´mico actual de la Universidad Tecnol´gica
e
o
de Pereira, Ingeniero Jos´ German L´pez Quintero por toda la colaboraci´n prestada.
e
o
o

LOS AUTORES

PREFACIO
En las ciencias aplicadas al igual que enel conocimiento te´rico, existen problemas de opo
timizaci´n lineal o no lineal que involucran al mismo tiempo variables continuas y enteras, deo
nominados PLEM (Problemas de Programaci´n Lineal Entera Mixta) o PNLEM (problemas de
o
Programaci´n No Lineal Entera Mixta). Cuando las dimensiones y la complejidad matem´tica
o
a
del problema son grandes, aparece el fen´meno denominado explosi´ncombinatorial, debido a
o
o
la gran cantidad de soluciones factibles e infactibles que aparecen. La soluci´n del problema es
o
aquella que tiene mejor funci´n objetivo y que cumple todas las restricciones. Una forma de
o
determinar ´sta soluci´n, denominada soluci´n optima, consiste en evaluar expl´
e
o
o ´
ıcitamente todas
las alternativas existentes, lo cual requiere de tiempos de...