Algoritmos-heursticos-y-exactos-para-el-problema-de-la-mochila

Vista previa del material en texto

UNIVERSIDAD NACIONAL AUTÓNOMA
DE MÉXICO
ANA LILIA ANAYA MUÑOZ
DIRECTOR DE TESIS:
M. en I. O. MARÍA DEL CARMEN HERNÁNDEZ AYUSO
FACULTAD DE CIENCIAS
ALGORITMOS HEURÍSTICOS Y EXACTOS PARA EL
PROBLEMA DE LA MOCHILA
T E S I S
QUE PARA OBTENER EL TÍTULO DE:
M A T E M Á T I C A
P R E S E N T A :
Cd. Universitaria, D.F. 2016
 
UNAM – Dirección General de Bibliotecas 
Tesis Digitales 
Restricciones de uso 
 
DERECHOS RESERVADOS © 
PROHIBIDA SU REPRODUCCIÓN TOTAL O PARCIAL 
 
Todo el material contenido en esta tesis esta protegido por la Ley Federal 
del Derecho de Autor (LFDA) de los Estados Unidos Mexicanos (México). 
El uso de imágenes, fragmentos de videos, y demás material que sea 
objeto de protección de los derechos de autor, será exclusivamente para 
fines educativos e informativos y deberá citar la fuente donde la obtuvo 
mencionando el autor o autores. Cualquier uso distinto como el lucro, 
reproducción, edición o modificación, será perseguido y sancionado por el 
respectivo titular de los Derechos de Autor. 
 
 
 
Hoja de datos del jurado
1.- Datos del alumno 4.- Datos del sinodal 2.
Anaya Mat.
Muñoz Adrián
Ana Lilia Girard
15570138 Islas
Universidad Nacional Autónoma 5.- Datos del sinodal 3.
de México Mat.
Facultad de Ciencias Laura
Matemáticas Pastrana
095348021 Ramírez
2.- Datos del tutor 6.- Datos del sinodal 4.
M. en I. O. Act.
María del Carmen Germán
Hernández Valle
Ayuso Trujillo
3.- Datos del sinodal 1. 7.- Datos del trabajo escrito
Dra. Algoritmos heurísticos y exactos
Hortensia para el problema de la mochila
Galeana 158p
Sánchez 2016
Contenido
Introducción v
1 Programación entera 1
1.1 De�niciones de Programación Lineal . . . . . . . . . . . . . . . . . . 2
1.2 Problema de la mochila . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.1 Problema de la mochila general . . . . . . . . . . . . . . . . . 12
1.2.2 Problema de la mochila general acotado . . . . . . . . . . . . 13
1.2.3 Problema change-making . . . . . . . . . . . . . . . . . . . . . 13
1.2.4 Problema de la mochila binario . . . . . . . . . . . . . . . . . 13
1.2.5 Problema subset-sum . . . . . . . . . . . . . . . . . . . . . . . 14
2 Rami�cación y acotamiento 15
2.1 Método de rami�cación y acotamiento . . . . . . . . . . . . . . . . . 16
2.1.1 Técnica de rami�car y acotar . . . . . . . . . . . . . . . . . . 17
2.1.2 Aspectos claves del método de rami�cación y acotamiento . . 20
5
2.1.3 Algoritmo de Dakin . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Método de rami�cación y acotamiento para el problema de la mochila
(Un método para obtener una cota superior). . . . . . . . . . . . . . . 27
2.2.1 Problema general . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.2 Problema Acotado . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.3 Problema Binario . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3 Algoritmo de rami�cación y acotamiento para el problema de la mochila 30
2.3.1 Algoritmo de Dakin ( problema general) . . . . . . . . . . . . 30
2.3.2 Algoritmo para el problema acotado . . . . . . . . . . . . . . . 37
2.3.3 Algoritmo de Balas (Para el Problema Binario de la Mochila) 43
2.3.4 Algoritmo para el problema binario . . . . . . . . . . . . . . . 49
3 Programación dinámica 63
3.1 Elementos de un problema de programación dinámica . . . . . . . . . 64
3.2 Problema de programación dinámica . . . . . . . . . . . . . . . . . . 65
3.3 Programación dinámica aplicada al problema de la mochila . . . . . . 71
3.3.1 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.3.2 Análisis de sensibilidad . . . . . . . . . . . . . . . . . . . . . . 82
4 NP Completez y métodos heurísticos 83
4.1 Complejidad computacional . . . . . . . . . . . . . . . . . . . . . . . 84
4.2 Reducciones polinomiales . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.2.1 Problema del SAT / Problema 3-acoplamiento. . . . . . . . . 89
4.2.2 Problema 3-acoplamiento / Problema 3-recubrimiento. . . . . 96
4.2.3 Problema 3-recubrimiento / Problema de la mochila binario. . 98
4.2.4 Problema de la mochila binario / Problema de la
mochila general. . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.3 Métodos heurísticos. . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.3.1 Algoritmo heurístico glotón para el problema binario . . . . . 105
4.3.2 Algoritmo heurístico glotón para el problema general . . . . . 108
4.3.3 Algoritmo heurístico truncado para el problema binario. . . . 111
4.3.4 Algoritmo heurístico truncado para el problema
general. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.3.5 Algoritmo reversible para el problema binario . . . . . . . . . 111
5 Programa 115
5.1 Función principal (menú) . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.1.1 Descripción de las variables principales . . . . . . . . . . . . . 116
5.1.2 Descripción de la función principal. . . . . . . . . . . . . . . . 116
5.2 Función rami�cación y acotamiento . . . . . . . . . . . . . . . . . . . 118
5.2.1 Función ramaco . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.2.2 Función aco1(n,b,a,c); . . . . . . . . . . . . . . . . . . . . . . 120
5.2.3 Función compara . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.2.4 Función crea . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.2.5 Función expandir . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.3 Función progdin() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.3.1 Descripción de las variables. . . . . . . . . . . . . . . . . . . . 124
5.3.2 Función Progdin1() . . . . . . . . . . . . . . . . . . . . . . . . 125
5.4 Función heurist( ); . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5.4.1 Descripción de las variables . . . . . . . . . . . . . . . . . . . 129
5.4.2 Descripción del programa . . . . . . . . . . . . . . . . . . . . 129
5.4.3 Función heu(n,b,a,c); . . . . . . . . . . . . . . . . . . . . . . . 130
5.4.4 Función compara1 . . . . . . . . . . . . . . . . . . . . . . . . 132
6 Manual de Usuario 133
6.1 Rami�cación y Acotamiento . . . . . . . . . . . . . . . . . . . . . . . 134
6.2 Programación Dinámica . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.3 Programación Heurística . . . . . . . . . . . . . . . . . . . . . . . . . 148
Apéndice A
Teoría de grá�cas 153
Conclusión 155
Bibliografía 157
Dedicatoria
A mis papás Juana Muñoz y Seferino Anaya porque siempre hicieron hasta lo imposi-
ble para que pudiera lograr mis metas y me motivaron para ser una persona respon-
sable. Con todo mi cariño y amor se las dedico.
A mis hermanas Gaby, Mary y Ara que con sus consejos no dejaron que me
perdiera en el camino.
A mi directora de tesis, M. en I. O. María del Carmen Hernández Ayuso; por la
paciencia que me tuvo y gracias a todas sus recomendaciones este trabajo se pudo
lograr.
i
Agradecimientos
Agradezco a Dios por haberme permitido estudiar la carrera de matemáticas que me
ha dado muchas satisfaciones.
Le doy gracias a mis papás: Juana Muñoz y Seferino Anaya por el amor y con-
�anza que me han dado ya que gracias a eso pude superar muchas de las pruebas
que se me han presentado en la vida; su ejemplo de entrega y dedicación me han
motivado a terminar la carrera.
A mis hermanas por todos sus consejos y apoyo que me han dado a lo largo de
mi vida.
A mi directora de tesis, M. en I. O. María del Carmen Hernández Ayuso por el
tiempo que dedicó a guiarme para desarrollar este trabajo, por el apoyo y con�anza
que me brindó en todo este tiempo, por el sin �n de revisiones y correcciones que
enriquecieron esta tesis hasta llegar a su �n.
A mis compañeros y amigos de la facultad, que gracias a su apoyo hicieron más
ligeras las tareas y exámenes durante la carrera,
A mis sinodales: Dra. Hortensia Galeana Sánchez, Mat. AdriánGirard Islas,
Mat. Laura Pastrana Ramírez y Act. Germán Valle Trujillo. Por el tiempo que
dedicaron a leer mi tesis, por sus sugerencias y correcciones
iii
A mis profesores ya que gracias a ellos tuve una formación profesional que ahora
aplico a la docencia.
Y por último, pero no menos importante, a la Univesidad Nacional Autónoma de
México que ha sido un segundo hogar para mi.
iv
Introducción
La teoría de la programación lineal entera ha sido una de las áreas de investigación
de operaciones que se ha desarrollado rápidamente, desde los primeros trabajos de
Ralph Gomory en los años cincuentas.
Esta tesis tiene como �nalidad el estudio del problema de la mochila modelado
como un problema de programación lineal entera, el cual ha sido estudiado sobre
todo en los últimos 25 años; éste resulta interesante porque está constituido por una
estructura sencilla, ya que el modelo matemático cuenta con una sola restricción.
A este problema le han encontrado muchas aplicaciones tales como: inventarios,
cargamentos de diferentes artículos, inversiones y situaciones industriales.
A pesar de la sencillez de su formulación; el problema de la mochila entero se cata-
loga como un problema difícil de resolver (NP-completo), es decir, es un problema
que no cuenta con algún algoritmo e�ciente para resolverlo. Existen algoritmos que
pueden resolverlo, pero éstos requieren de una cantidad exponencial de pasos para
llegar a la solución, si ésta existe, la cantidad de pasos va en función del tamaño del
problema, es decir, el número de variables.
Se podría pensar que para resolver el problema de la mochila entero se tendrían
que analizar todas las posibles soluciones y escoger la mejor, pero este camino es
exhaustivo. En este trabajo se enuncian algunos algoritmos que evitan explorar
todas las soluciones posibles, ya que con algunas condiciones se pueden descartar
v
algunas que no llevarían a la óptima.
En este trabajo también se desarrolló un programa en el lenguaje C++ que re-
suelve el problema de la mochila utilizando algunos algoritmos que se tratarán en los
capítulos 2, 3 y 4.
En el primer capítulo se dan algunas de�niciones elementales de la programación
lineal y programación lineal entera. Un concepto importante es la relajación PL y
los resultados que se derivan de éste; ya que para resolver algunos problemas enteros
se parte de la solución óptima de la relajación PL.
En el segundo capítulo se estudia el método de rami�cación y acotamiento que es
un procedimiento con un desarrollo largo, ya que partimos de una solución óptima
(solución de problema relajado) pero no factible (no cumple la restricción de que
las variables sean enteras) y se tienen que probar muchas posibles combinaciones
de variables enteras factibles para escoger la mejor solución. Con ayuda de algunas
condiciones el número de posibles soluciones se reduce.
En el capítulo tres se da una pequeña introducción a la programación dinámica;
después de dar algunas de�niciones elementales, se aplica un algoritmo especí�co
para el problema de la mochila.
En el capítulo cuatro se de�nen los problemas NP-Completos. Dado que el proble-
ma de la mochila pertenece a esta clase, se hace la reducción polinomial del problema
del SAT al problema de la mochila (un caso especial), después se da una introdu-
cción a los algoritmos heurísticos, que son una alternativa para obtener una "buena�
solución en un tiempo razonable.
En el capítulo cinco se muestran los diagramas de �ujo y el funcionamiento de las
rutinas más importantes que contiene el programa que se desarrolló en el lenguaje
C++: Este programa resuelve el problema de la mochila binario con rami�cación y
acotamiento, así como un algoritmo heurístico. También resuelve el problema de la
vi
mochila general con programación dinámica.
Por último, el capítulo 6 contiene el manual de usuario del programa �MOCHILA�
desarrollado en el lenguaje C++:
vii
Capítulo 1
Programación entera
Este capítulo contiene de�niciones básicas de programación lineal y programación
lineal entera así como algunas propiedades que se cumplen en este tipo de modelos
que son la base de los métodos de solución revisados en este trabajo.
Los problemas de programación lineal entera son en general más complicados de
resolver que los de programación lineal, por lo que en muchos de los casos se resuelve
la relajación PL del problema entero (el cual es de programación lineal) como primer
paso. En otros casos se aplica por la �losofía �divide y vencerás� conocida en la
bibliografía como técnica de rami�cación y acotamiento.
El objetivo de este capítulo es presentar la técnica de rami�cación y acotamiento,
así como formular el problema de la mochila mediante un modelo matemático lineal
entero.
1
1.1 De�niciones de Programación Lineal
De�nición 1: Un problema de programación lineal (PL), es un problema de opti-
mización, para el cual:
1. El objetivo es maximizar o minimizar una función lineal de variables de decisión
que llamaremos x1; x2; :::; xn; dicha función es llamada función objetivo.
2. Los valores que toman las variables de decisión tienen que satisfacer un con-
junto de restricciones, donde cada restricción debe ser una ecuación lineal o
una desigualdad lineal.
3. Hay restricciones de signo para cada variable xi, por ejemplo xi debe ser no
negativa, es decir, xi � 0 o no tiene restricción de signo, es decir, SRS).
En general un problema de programación lineal (PL) es de la siguiente forma:
Max (Min) z = c1x1 + c2x2 + :::+ cnxn
s:a: a11 x1 + a12 x2+ :::+ a1n xn � (�) (=) b1
a21 x1 + a22 x2+ :::+ a2n xn � (�) (=) b2
.
.
.
am1x1 + am2x2 + :::+ amnxn � (�) (=) bm
xi � 0 i = 1; :::n:
Un ejemplo de un problema de programación lineal es el siguiente:
Ejemplo 1: Una compañía quiere programar su producción de cerveza, la cual
puede ser clara u oscura. Los requerimientos laborales y monetarios en miles de pesos
2
por semana se expresan en la siguiente tabla (por cada 1000 litros)
Obreros requeridos Costo Precio al mayoreo
Clara 3 5 50
Oscura 5 2 30
Disponibilidad por semana 15 10
Las variables de decisión para este problema son las siguientes:
x1 = miles de litros de cerveza clara a producir semanalmente.
x2 = miles de litros de cerveza oscura a producir semanalmente.
Para construir las restricciones consideremos lo siguiente:
El número de obreros requeridos para producir cerveza clara u oscura por semana
no debe exceder de 15 y la cantidad necesaria para producir 1000 litros de cerveza
clara u oscura es de 3 y 5 respectivamente, por lo que la restricción referente a esto,
se expresa de la siguiente manera:
3x1 + 5x2 � 15
El costo de producción semanalmente no debe ser mayor a 10 mil pesos, por lo que
la restricción es:
5x1 + 2x2 � 10
La función objetivo describe la ganancia en miles de pesos de un plan de producción.
Entonces es:
z = 50x1 + 30x2
Esta función debe maximizarse, por lo que el modelo �nalmente es:
max z = 50x1 + 30x2
s:a: 3x1 + 5x2 � 15
5x1 + 2x2 � 10
x1; x2 � 0
3
De�nición 2: Un punto X = (x1; x2; :::; xn) es una solución factible si satisface
todas las restricciones del problema. La región factible de un problema de PL es el
conjunto de todas las soluciones factibles y se denota por Fp.
Ejemplo 2: La región factible del ejemplo anterior se obtiene gra�cando las dos
restricciones las cuales de�nen dos subespacios, posteriormente se analiza qué puntos
del plano satisfacen las desigualdades como se muestra en las �guras:
Los puntos que satisfacen la primera restricción son:
1 2 3
4
5
3
2
1
3
x 1
+5
 x
2
< 
15
Puntos que satisfacen la
desigualdad
3 x1+ 5 x2= 15
4 51 2 3
4
5
3
2
1
3
x 1
+5
 x
2
< 
15
Puntos que satisfacen la
desigualdad
3 x1+ 5 x2= 15
4 5
4
Los puntos que satisfacen la segunda restricción son:
5 x1+ 2 x2= 10
6
Puntos que satisfacen la
desigualdad
5x1+ 2x2 < 10
1 2 3 4 5
4
5
3
2
1
La intersección de estos semiespacios, junto con la restricción deno negatividad
es la región factible del problema de PL como se muestra en la �gura.
1 2 3
4
5
3
2
1
3 x1+5 x2 < 15
3 x1+ 5 x2= 15
4 5
5 x1+ 2 x2= 10
5 x1+ 2 x2 < 10
1 2 3 4 5
4
5
3
2
1
Puntos que satisfacen las dos
restricciones y la no negatividad
5
1 
_\--r-
-\ 
:::; ¡-
a - r' ~ 
--\ 
- b 
=-
-:\ 
-~ 
~ 
=1. 
--\ ...1 ...1 ..1 ...J. .... 
. . . . 
-
De�nición 3: Un vector X 0 que satisface las restricciones es una solución factible
y un vector X� que además de satisfacer las restricciones, optimiza la función objetivo
es una solución óptima.
Ejemplo 3: En el ejemplo anterior la solución óptima del problema es el punto
A =
�
20
19
; 45
20
�
y el valor de la función objetivo es z = 2350
19
:
1 2 3
4
5
3
2
1
4 51 2 3 4 5
4
5
3
2
1
A
De�nición 4: Un problema de PL P es un problema de programación lineal
entera (PLE), si alguna(s) variable(s) de decisión (x1; x2; :::; xn) de P tiene(n) la
restricción de ser entera.
Existen tres tipos de problemas en PLE.
Sean P un problema de PLE y X = (x1; x2; :::; xn) el vector de variables de
decisión de P :
� P es un problema de PLE mixto si alguna(s) componente(s) de X tienen la
restricción de ser entera(s) y alguna(s) no.
6
� P es un problema de PLE puro si todas las componentes de X tienen la res-
tricción de ser enteras.
� P es un problema de PLE binario si cada una de las componentes de X tiene
la restricción de tomar solamente los valores 0 ó 1:
Ejemplo 4: Un ejemplo de problema de PLE mixto es el siguiente: Se desea
armar una despensa con diferentes tipos de artículos (Leche en polvo, aceite, frijol,
azúcar, café, arroz), cada uno de ellos se llevan por empaque, con excepción del arroz
ya que éste es a granel; cada artículo tiene cierto bene�cio y éstos se acomodarán
en cajas con capacidad de 14kg cada una. El peso y bene�cio de cada artículo se
muestra en la siguiente tabla:
Artículo Kg por empaque Bene�cio
1. Leche en polvo 1.7 9
2. Aceite 0.9 5
3. Frijol 1 8
4. Azúcar 1 4
5. Café 0.5 4
6. Arroz a granel 8 por kg
Las variables de decisión son:
xi = Número de paquetes del tipo i, incluidos en la despensa para i = 1,2,...,5.
x6 = Cantidad de arroz a incluir en la despensa.
El modelo matemático para este problema es:
max z = 9x1 + 5x2 + 8x3 + 4x4 + 4x5 + 8x6
s. a. 1:7x1 + 0:9x2 + x3 + x4 + 0:5x5 + x6 � 14
xi � 0 i = 1; :::6 xi enteros para i = 1; :::; 5:
7
En este ejemplo las variables xi para i =1,..,5 tienen la restricción de ser enteras no
negativas y x6 puede tomar cualquier valor real no negativo.
Ejemplo 5: Un problema de PLE entera puro es el siguiente: Un camión de
SEDESOL con capacidad de 2.5 toneladas debe de ser llenado con los siguientes
artículos: maíz, frijol, azúcar y café (la unidad de medida es por sacos). Como
parte de un programa social, éstos serán transportados a poblados y vendidos a un
precio preferencial, esto es, si una persona compra el producto al camión en vez de
a cualquier otro distribuidor obtendrá un ahorró, en el siguiente cuadro se especi�ca
el peso de cada artículo y el ahorro por saco al consumidor:
Kilogramos por saco Ahorro por saco al consumidor
Maíz 10 10
Frijol 8 15
Azúcar 12 10
Café 5 7
Determinaremos con cuáles y cuántos artículos debe ser llenado el camión de tal
manera que se maximice el ahorro al consumidor. Éste es un problema de PLE puro,
ya que los sacos se cuentan por unidad (no se puede contar fracciones de saco), por
lo que se plantea de la siguiente manera:
Las variables de decisión son las siguientes:
x1 = número de sacos de maíz incluidos en el camión.
x2 = número de sacos de frijol incluidos en el camión.
x3 = número de sacos de azúcar incluidos en el camión.
x4 = número de sacos de café incluidos en el camión.
La restricción debe especi�car que el número de sacos no debe exceder la capacidad
de carga del camión; además las variables de decisión deben ser no negativas y enteras
8
ya que los sacos se cuentan por unidad, por lo que las restricciones del problema son
las siguientes,
10x1 + 8x2 + 12x3 + 5x4 � 2500
xi � 0; xi enteros para i = 1; :::; 4
La función objetivo describe el ahorro del consumidor por artículo comprado. En-
tonces es:
z = 10x1 + 15x2 + 10x3 + 7x4
Esta función se desea maximizar, por lo tanto el problema planteado como un pro-
blema de programación lineal entera es el siguiente:
max z = 10x1 + 15x2 + 10x3 + 7x4
s. a 10x1 + 8x2 + 12x3 + 5x4 � 2500
xi � 0 y xi entero para i = 1; :::; 4:
En este caso todas las variables del problema tienen la restricción de ser enteras.
Ejemplo 6: El siguiente problema es uno binario. Cinco proyectos están siendo
evaluados para un horizonte de 3 años de planeación, la siguiente tabla proporciona
las ganancias esperadas de cada proyecto y los respectivos costos anuales.
Costo en millones de pesos
Proyecto 1er año 2� año 3eraño Ganancias en millones $
1 5 1 8 20
2 4 7 10 40
3 3 9 2 20
4 7 4 1 15
5 8 6 10 30
El presupuesto disponible para invertir será de 25 millones de pesos cada año.
9
Las variables de decisión son las siguientes:
xi =
8<: 1 si el proyecto i es aceptado0 en otro caso
9=; parai = 1; 2; :::; 5:
Por lo que el problema se plantea como sigue:
max z = 20x1 + 40x2 + 20x3 + 15x4 + 30x5
s:a 5x1 + 4x2 + 3x3 + 7x4 + 8x5 � 25
x1 + 7x2 + 9x3 + 4x4 + 6x5 � 25
8x1 + 10x2 + 2x3 + x4 + 10x5 � 25
xi = 0 o 1 (i = 1; 2; :::; 5) :
De�nición 5: La relajación PL de un problema de PLE es el problema de PL que
resulta al omitir todas las restricciones enteras para las variables de decisión.
Observación 1: La región factible de un Problema de PLE está contenida en la
región factible de la relajación PL del problema entero.
Ejemplo 7: Sea
P
8>>>>>>>><>>>>>>>>:
max z = 4x1 + 3x2
s:a 3x1 + x2 � 12
x1 + x2 � 5
x1; x2 � 0
x1 y x2 enteros:
9>>>>>>>>=>>>>>>>>;
P es un problema de PLE puro, la relajación PL de P es:
P1
8>>>>><>>>>>:
max z = 4x1 + 3x2
s:a 3x1 + x2 � 12
x1 + x2 � 5
x1; x2 � 0:
9>>>>>=>>>>>;
grá�camente las regiones factibles de P y P1 se pueden observar en la siguiente
�gura:
10
2
Región Factible de P 1
1 3 5
10
8
6
4
2
12
1
3
5
Región Factible de P
4
3x1 + x2 ≤ 12
x1 + x2 ≤ 5
Observación 2: La relajación PL del problema entero es sencilla de resolver, ya
que si no se toma en cuenta la restricción de que las variables deben ser enteras, éste
se reduce a uno de PL y existen muchos métodos e�caces para obtener la solución
óptima.
Observación 3: Si se resuelve la relajación PL de un problema de PLE y se
obtiene una solución en la cual todas las variables son enteras, entonces la solución
óptima de la relajación PL será también la solución óptima del problema de PLE.
Este caso en pocas ocasiones ocurre, es por eso que existen algoritmos para llegar a
la solución óptima o una aproximación de la misma.
Observación 4. Si el problema de PL es no factible también lo es el entero.
11
• 
ITIIJ 
1.2 Problema de la mochila
El problema de la mochila es un problema de programación lineal entera y se caracte-
riza por tener sólo una restricción. Éste se re�ere a la siguiente situación: Suponga-
mos que un excursionista debe llenar una mochila de capacidad b con n artículos
diferentes, cada artículo i tiene un peso ai y un bene�cio ci. La mochila debe ser
llenada de tal manera que se maximice el bene�cio de los artículos incluidos, sujeto
a la restricción de capacidad.
Las variables de decisión son: xi que representan el número de artículos del tipo
i incluidos en la mochila para i = 1; ::; n:
Existen varias clases de problemas tipo mochila como son: �problema de la
mochila general�, �problema de la mochila general acotado� ,� problema de la
mochila binario�, �problema subset-sum� y �problema change-making�, los mode-
los matemáticos asociados a cada uno de los problemas los veremos en las siguientes
secciones.
1.2.1 Problema de la mochila general
El problema general de la mochila se expresa de la siguiente forma:
max z =
nX
i=1
cixi
s:a
nX
i=1
aixi � b
xi �0 y xi entero para i = 1; :::; n:
12
1.2.2 Problema de la mochila general acotado
El problema anterior se puede plantear de la siguiente forma: si para cada artículo i
existe una cota di; la cual nos indica que del artículo i se pueden llevar como máximo
di unidades, entonces el modelo matemático para este problema es:
max z =
nX
i=1
cixi
s:a
nX
i=1
aixi � b
0 � xi � di y xi entero para i = 1; :::; n
1.2.3 Problema change-making
Es un caso especial del problema de la mochila general acotado y surge de la condición
ci = 1 para i = 1; 2; :::; n: Por lo que el planteamiento del problema es:
max z =
nX
i=1
xi
s:a
nX
i=1
aixi � b
0 � xi � di y xi entero para i = 1; :::; n:
1.2.4 Problema de la mochila binario
Al problema de la mochila también se le pueden adicionar otras restricciones tales
que, todas las variables de decisión xi pueden tomar sólo los valores 0 ó 1, es decir,
si xi = 1 el artículo i es incluido en la mochila y si xi = 0 no es incluido. A este
planteamiento se le conoce como el problema de la mochila binario y se representa
13
de la siguiente manera:
max z =
nX
i=1
cixi
s:a
nX
i=1
aixi � b
xi =
8<: 01
9=; para i = 1; :::; n:
1.2.5 Problema subset-sum
Es un caso particular del problema de la mochila binario ya que las variables xi sólo
pueden tomar los valores 0 ó 1, la diferencia entre ambos es que ci = ai, por lo que
el modelo matemático de este problema es:
max z =
nX
i=1
aixi
s:a
nX
i=1
aixi � b
xi =
8<: 01
9=; para i = 1; :::; n:
14
Capítulo 2
Rami�cación y acotamiento
En este capítulo se tratará de un método general para resolver problemas enteros,
rami�cación y acotamiento. Este método necesita una cota superior, que es el valor
óptimo de la relajación PL del problema entero; en esta primera sección se explicará
el método de rami�car y acotar, más adelante se explicará el algoritmo para un
problema de programación lineal y en la siguiente sección se explicarán los procedi-
mientos para encontrar una cota superior de los problemas tipo mochila: general,
acotado y binario. Y en la última sección se darán algunos algoritmos de solución
para cada uno de estos problemas.
Podría pensarse que una manera natural de resolver un problema entero, sería
el redondeo, si se utiliza este método con la solución óptima de la relajación del
problema entero se presentan dos casos:
Sea Xi la solución del subproblema i y xj una componente que no tiene un valor
entero; sea [xj] la parte entera de xj.
� Si se redondea al siguiente entero, es decir, que xj = [xj]+1; y todas las demás
15
componentes de Xi se quedan iguales, la solución no sería factible ya que ésta
sería mejor que Xi; y como lo dijimos anteriormente esta es una cota superior,
por lo que implicaría que es una solución no factible.
� Si se redondea al entero anterior, es decir, xj = [xj], la solución si sería factible
pero no necesariamente óptima ya que en muchos casos por medio de diferentes
métodos se puede mejorar la solución.
Podemos concluir que el redondeo no es una técnica que sea útil para obtener
la solución óptima de un problema de PLE, es útil sólo si queremos encontrar una
solución factible y se da el caso.
2.1 Método de rami�cación y acotamiento
La técnica de Rami�cación y Acotamiento permite resolver problemas �difíciles�
aplicando métodos de solución que se han dado para problemas �fáciles�.
En la práctica, muchos de los problemas de PLE se resuelven mediante este
método, el cual encuentra la solución óptima mediante la enumeración e�ciente de
los puntos de la región factible del problema.
16
2.1.1 Técnica de rami�car y acotar
Se utilizará un ejemplo para describir la técnica de rami�cación y acotamiento. Sea
P un problema entero de la siguiente forma:
P
8>>>>>>>>>>><>>>>>>>>>>>:
max z = c1x1 + c2x2 + :::+ cnxn
s:a a11 x1 + a12 x2 + :::+ a1n xn � b1 ����R1
a21 x1 + a22 x2 + :::+ a2n xn � b2 ����R2
:::
am1x1 + am2x2 + :::+ amnxn � bm ����Rm
xi > 0 y xi enteros para i = 1; 2; :::; n:
9>>>>>>>>>>>=>>>>>>>>>>>;
La operación de rami�car procede de la siguiente manera:
Primero se obtiene la relajación PL de P , sea P1 y sea F1 la región factible de
P1, como se muestra en la �gura:
F1 Región Factible de la relajación PL
del problema entero
R1
R2
Se resuelve P1; si la solución encontrada X1 no es entera, se crean dos subproblemas
de P1, sean P2 y P3 con sus respectivas regiones factibles F2 y F3; cada subproblema
17
Pj tiene una nueva restricción (restricción de rami�cación):
xi � [xi], para P2
xi � [xi] + 1, para P3
donde [xi] es la parte entera de xi.
Esto se muestra en la siguiente �gura.
F1 Región factible de la relajación PL
del problema entero
R1
R2
F2 Región factible del problema P2
F3 Región factible del problema P3
[x1 ] [x1 ] + 1
Observación 5: La región que sólo está sombreada de la siguiente manera
corresponde a las soluciones descartadas, ya que son factibles para la relajación
PL, pero no para el problema entero, ya que tiene valores fraccionales, por lo que no
afecta eliminarlos de consideración.
Después se selecciona uno de los dos subproblemas, digamos P2 y se obtiene la
solución óptima de éste X2. A continuación se examina P3; éste también se resuelve
18
para obtener la solución óptima X3. Si las soluciones encontradas X2 y X3 no son
enteras entonces se escoge uno de los subproblemas P2 o P3 para proceder de la misma
manera que con P1, este procedimiento continúa hasta encontrar una solución óptima
para el problema P .
Todos los subproblemas Pi0s tienen la misma función objetivo que P y la misma
restricción (desigualdad lineal), la diferencia es que a los Pi0s se les aumentan algunas
restricciones de rami�cación.
Observemos que el valor óptimo de cada problema es una cota superior del valor
óptimo de los subproblemas generados a partir de él, pues la región factible de éstos
está contenida en la del primero.
Análogamente para problemas de minimización, el valor óptimo de P constituye
una cota inferior.
Todos los pasos de la rami�cación se ilustran con el siguiente árbol, en donde P1
es representado por el primer nodo y se va rami�cando de tal manera que cada rama
incide en un subproblema diferente, ya que éste tiene una restricción de rami�cación
distinta.
P1
P2 P3
P5P4 P7
P6
Pt+2Pt+1
19
2.1.2 Aspectos claves del método de rami�cación y aco-
tamiento
Si utilizamos el método de rami�cación y acotamiento, podemos �eliminar�algunos
nodos en donde ya se llegó o no llegaríamos a la solución óptima y de esta manera
se reduce el número de subproblemas a resolver.
No es necesario rami�car con respecto a un subproblema cuando:
1. El subproblema no es factible, es decir, que no cumpla la restricción de capaci-
dad.
2. El subproblema proporciona una solución en la cual todas la variables tienen
valores enteros, es decir, es una solución candidata para obtener la solución
óptima del problema entero.
3. El valor óptimo del subproblema es menor al valor óptimo en algún nodo cuya
solución es entera, es decir, el mejor candidato para z hasta este momento.
Con estos puntos se reduce el número de nodos en el árbol.
2.1.3 Algoritmo de Dakin
Dakin desarrolló un algoritmo de rami�cación y acotamiento para resolver problemas
de optimización, este algoritmo crea 2 nodos por cada nodo pendiente, es decir, si la
solución de un nodo Xl tiene una componente xj que no es entera, al primer nodo
que se crea se le asigna la restricción xj 6 [xj] y al segundo xj > [xj] + 1; cada
problema es resuelto. El procedimiento termina cuando la lista de nodos pendientes
sin etiquetar es vacía. El algoritmo de Dakin se enuncia como sigue:
20
Paso 1) Solución del problema relajado
Se resuelve la relajación PL del problema entero y obtenemos X1 y z1 = z (X1),
si xj 2 Z 8j terminamos, la solución encontrada es óptima, si no, ir al paso 2.
Paso 2) Rami�cación
Si Xi tiene una componente no entera, digamos xj, se crean dos nodos; al pro-
blema correspondiente al nodo l+1 se le agregala restricción xj � [xj] y al problema
del segundo nodo l+ 2 se le agrega la restricción xj � [xj] + 1; donde l es el número
del último nodo. Como se observa en la �gura:
i
l+1 l+2
xj ≤ [xj ] xj ≥ [xj ] + 1
Una vez resueltos los problemas de dichos nodos ir al paso 3:
Paso 3) Etiquetado
1. Si la solución encontrada es entera dicho nodo es etiquetado como �solución
candidata�.
2. Si existen nodos no etiquetados con cota menor que z(Xk); para algún nodo
Xk etiquetado como �solución candidata�, serán etiquetados como �nodo
no prometedor�.
3. Si la solución encontrada no es factible (ya que no cumple con la restricción de
capacidad) a este nodo se le asignará la etiqueta de �solución no factible�.
21
Después de haber etiquetado todos los nodos posibles ir al paso 4)
Paso 4) Inspección de nodos
1. Si todos los nodos están etiquetados y no existe alguno que tenga la etiqueta
de �solución candidata�entonces terminamos, el problema entero no tiene
solución.
2. Si todos los nodos están etiquetados y existen alguno o algunos nodos etique-
tados con �solución candidata�ir al paso 5).
3. Si existen nodos sin etiquetar, esto quiere decir que se puede seguir iterando
de estos nodos, ir al paso 2).
Paso 5) Solución óptima
El valor óptimo de la función objetivo es z(X�) = maxfz (Xi) j Xi es un nodo
etiquetado con solución candidatag la solución óptima es X�.
Ejemplo 8: Resolveremos el siguiente problema con el método de rami�cación y
acotamiento de Dakin:
P
8>>>>><>>>>>:
max z = 5x1 + 2x2
s:a 3x1 + x2 � 12
x1 + x2 � 5
x1; x2 � 0 y x1; x2 enteros.
9>>>>>=>>>>>;
Primero resolvemos la relajación PL de P que es:
P1
8>>>>><>>>>>:
max z = 5x1 + 2x2
s:a 3x1 + x2 � 12
x1 + x2 � 5
x1; x2 � 0:
9>>>>>=>>>>>;
22
La solución óptima de P1 es X1 = (72 ;
3
2
) = (3:5; 1:5) y el valor de la función objetivo
es z(X1) = 412 = 20:5: Grá�camente la región factible del problema es
1 2 3 4 5
10
8
6
4
2
12
3 x1+ x2 ≤ 12
x1 + x2 ≤ 5
F1 Región factible del
problema relajado P1
X1
X1 Solución óptima de P1
Iteración 1: Como los valores de X1 no son enteros se crean dos nodos con dos
subproblemas P2 y P3: P2 es P1 más una restricción de rami�cación
P2
8>>>>>>>><>>>>>>>>:
max z = 5x1 + 2x2
s:a 3x1 + x2 � 12
x1 + x2 � 5
x2 � 1
x1; x2 � 0:
9>>>>>>>>=>>>>>>>>;
La solución de P2 es X2 =
�
11
3
; 1
�
= (3:66; 1) ya que si x2 = 1 =) x1 = 113 y
z(X2) =
61
3
= 20:33
23
P3 es P1 más una restricción de rami�cación:
P3
8>>>>>>>><>>>>>>>>:
max z = 5x1 + 2x2
s:a 3x1 + x2 � 12
x1 + x2 � 5
x2 � 2
x1; x2 � 0:
9>>>>>>>>=>>>>>>>>;
La solución de P3 es X3 = (3; 2) y z(X3) = 19. Como todas las variables son enteras,
a este nodo se le pondrá la etiqueta de solución candidata.
Grá�camente las regiones factibles de P2 y P3 se muestran en la siguiente �gura
21 3 5
10
8
6
4
2
12
1
3
5
F1 Región Factible de P1
4
3 x1 + x2 ≤ 12
x1 + x2 ≤ 5
X1
F2 Región factible de P2
F3 Región factible de P3
Iteración 2: Como el valor de z en el nodo 2 es mayor al valor de z en el nodo
3 que es una solución candidata seguimos iterando del nodo 2 del cual saldrán
los subproblemas P4 y P5.
24
P4 es P2 más una restricción de rami�cación
P4
8>>>>>>>>>>><>>>>>>>>>>>:
max z = 5x1 + 2x2
s:a 3x1 + x2 � 12
x1 + x2 � 5
x2 � 1
x1 � 3
x1; x2 � 0:
9>>>>>>>>>>>=>>>>>>>>>>>;
De P4 obtenemos la siguiente solución X4 = (3; 1) ya que si x1 = 3, entonces,
x2 = 1 y el valor de z(X4) = 17 la solución de este nodo es entera por lo que a este
nodo se le pondrá la etiqueta de solución candidata.
P5 es P2 más una restricción de rami�cación:
P5
8>>>>>>>>>>><>>>>>>>>>>>:
max z = 5x1 + 2x2
s:a 3x1 + x2 � 12
x1 + x2 � 5
x2 � 1
x1 � 4
x1; x2 � 0:
9>>>>>>>>>>>=>>>>>>>>>>>;
La solución de este problema es X5 = (4; 0) ya que si x1 = 4, entonces, x2 = 0
y z(X5) = 20 como las variables tienen valores enteros, a este nodo lo etiquetamos
como solución candidata.
Gra�camente las regiones factibles de P4 y P5 se observan en la siguiente �gura:
25
21 3 5
10
8
6
4
2
12
1
3
5
F1 Región Factible de P1
4
3 x1 + x2 ≤ 12
x1 + x2 ≤ 5
X1
F2 Región factible de P2
F3 Región factible de P3
F5 Región factible de P5
F4 Región factible de P4
El árbol asociado a este problema es:
X1 = ( 3.5 , 1.5)
Z(X1) = 20.5
1
32
x2 ≤ 1 x2 ≥ 2
X2 = ( 3.66 , 1)
Z(X2) = 20.33
X3 = ( 3 , 2)
Z(X3) = 19
Solución candidata
4 5
x1 ≤ 3 x1 ≥ 4
X5 = ( 4 , 0)
Z(X5) = 20X4 = ( 3 , 1)
Z(X4) = 17
Solución candidataSolución candidata
Como todos los nodos estan etiquetados y existen tres nodos etiquetados como solu-
ción candidata, entonces tomamos el nodo que tiene el valor máximo de z, es
decir, z�(X�) = max f19; 17; 20g = 20, por lo tanto podemos concluir que la solución
óptima del problema es X� = (4; 0) con z�(X�) = 20:
26
• 
2.2 Método de rami�cación y acotamiento para
el problema de la mochila (Un método para
obtener una cota superior).
2.2.1 Problema general
Sea Pm un problema tipo mochila general
Pm
8>>>>>><>>>>>>:
max z =
nX
i=1
cixi
s:a
nX
i=1
aixi � b
xi � 0 y xi entero para i = 1; :::; n:
9>>>>>>=>>>>>>;
Como lo mencionamos anteriormente cuando tenemos un problema de maximización
se inicia con la solución óptima de la relajación PL de Pm, y ésta se obtiene de la
siguiente manera:
Procedimiento solución óptima Se calcula el cociente ci
ai
; i = 1; 2; :::; n; el cual
es el bene�cio por unidad incluida del artículo i y se ordena de mayor a menor, es
decir, c10
a10
� c20
a20
� ::: � cn0
an0
se tiene que el artículo 10 es del que se obtiene mayor
bene�cio, por lo que la solución óptima es x10 =
b
a10
y xi0 = 0 8i0 6= 10; donde x10 es el
número de unidades que se deben incluir del artículo 10; ya que b es la capacidad de
la mochila y a10 es el peso del artículo 10. Se puede concluir que la solución óptima
de la relajación PL de Pm es:
X =
�
0; 0; :::;
b
a10
; 0; 0; :::; 0
�
(1)
Y el valor de la función objetivo es : z(X) = c10 � ba10 :
27
2.2.2 Problema Acotado
Si Pm es un problema tipo mochila general acotado entonces Pm es de la siguiente
forma:
Pm
8>>>>>><>>>>>>:
max z =
nX
i=1
cixi
s:a
nX
i=1
aixi � b
0 � xi � di y xi entero para i = 1; :::; n:
9>>>>>>=>>>>>>;
La solución de la relajación PL del problema entero se obtiene de la siguiente manera:
Primero se realiza el procedimiento solución óptima con la salvedad de que como x10
tiene la restricción x10 6 d10, donde d10 es la cantidad máxima de unidades que se
pueden incluir del artículo 10, se tienen dos casos:
� Caso 1.- Si b
a10
� d10 ; entonces la solución óptima de la relajación PL de Pm es
x10 =
b
a10
y xi0 = 0; para i0 6= 10, es decir, la solución de la relajación PL de Pm
es X =
�
b
a
1
0
; 0; 0; ; :::; 0
�
:
Y el valor de la función objetivo es : z = c10 � ba10 :
� Caso 2.- Si b
a10
> d10, entonces x10 = d10 y b�(a10 � d10) es la capacidad marginal
de la mochila, por lo cual x20 (siguiente artículo con mejor bene�cio) tiene el
valor x20 =
b�(a10�d10 )
a20
: Si x20 6 d20 para obtener el valor de x20 se tienen 2 casos:
1. Si b�(a10�d10 )
a20
� d20 entonces la solución óptima de la relajación PL de Pm
es x10 = d10, x20 =
b�(a10�d10 )
a20
y xi0 = 0: para i0 6= 10; 20, es decir,
X =
�
d10 ;
b� (a10 � d10)
a20
; 0; :::; 0
�
y el valor de la función objetivo es :
z = c10 � d10 + c20 �
�
b� (a10 � d10)
a20
�
:
28
2. Si b�(a10�d10 )
a20
> d20 los valores óptimos de x10 y x20 son x10 = d10, x20 = d20,
y (b � [(a10 � d10) + (a20 � d20)]) es la capacidad marginal de la mochila,
por lo cual x30 (siguiente artículo con mejor bene�cio) tiene el valor x30 =
(b�[(a10�d10 )+(a20�d20 )])
a30
si x30 6 d30 ; se vuelven a tener 2 casos:
Este procedimiento se repite hasta que
24 tX
i0=1
ai0 � xi0
35 = b, donde t es el índice
más pequeño (1 < t � n) el cual satisface la expresión anterior, es decir, hasta que
se llene la mochila.
Con lo anterior se puede concluir que la solución óptima de la relajación PL de
Pm es:
X =
�
b
a10
; 0; 0; :::; 0
�
cuando a10 � d10 � b:
X =
0@d10 ; d20; :::; dt0 ; � 1a
t+1
0
�24b� tX
i0=1
ai0 � di0
35 ; 0; 0; :::; 0
1A en otro caso. (2)
2.2.3 Problema Binario
En el caso binario de la expresión (2) se tiene que di = 1 ya que di es una cota
superior de xi por lo que la solución del problema relajado de la mochila binario es:
X =
�
b
a10
; 0; 0; :::; 0
�
cuando a10 � b:
X =
0@1; 1; :::; 1; h 1
at+1
i24b� tX
i0=1
ai
35 ; 0; 0; :::; 0
1A en otro caso, (3)
donde t es el índice más pequeño (1 < t � n) el cual satisface
tX
i0=1
aj � b
29
2.3 Algoritmo de rami�cación y acotamiento para
el problema de la mochila
Una vez obtenida la cota superior del primer nodo, es decir, la cota superior para el
valor de z, se empieza a rami�car y a cada nodo se le asocia una cota superior que
es la función objetivo evaluada en la solución encontrada en él.
2.3.1 Algoritmo de Dakin ( problema general)
Dakin desarrolló un algoritmo de rami�cación y acotamiento para resolver problemas
de optimización, este algoritmo genera un árbol que inicia con un nodo asociado al
problema relajado del cual saldrán dos ramas correspondientes a los subproblemas
que tienen las restricciones xj 6 [xj] y xj > [xj]+ 1, donde xj es una componente no
entera de la solución; cada problema es resuelto. El procedimiento termina cuando la
lista de nodos sin sucesores sin etiquetar es vacía. El algoritmo de Dakin se enuncia
como sigue:
Paso 1) Solución del problema relajado
La solución óptima de la relajación PL del problema entero está dado en (1) y
obtenemos X1 y z1 = z (X1), si xj 2 Z 8j terminamos, la solución encontrada es
óptima, si no ir al paso 2.
Paso 2) Rami�cación
Sea l el nodo pendiente del cual se va a seguir iterando, sea Xl la solución de
dicho nodo; si ésta tiene una componente no entera, digamos xj, se crean dos nodos;
al problema correspondiente al nodo l + 1 se le aumenta la restricción xj � [xj] y
al problema del segundo nodo l + 2 se le agrega la restricción xj � [xj] + 1. En la
�gura se muestra lo anterior:
30
i
l+1 l+2
xj ≤ [xj ] xj ≥ [xj ] + 1
Una vez resuleto el problema de cada nodo ir al paso 3:
Paso 3) Etiquetado
Caso 1) Si la solución encontrada es entera dicho nodo es etiquetado como �solu-
ción candidata�.
Caso 2) Si existen nodos no etiquetados con cota menor que z(Xk); para algún
nodo Xk etiquetado como �solución candidata�, serán etiquetados como �nodo
no prometedor�.
Caso 3) Si la solución encontrada no es factible a este nodo se le asignará la
etiqueta de �solución no factible�.
Después de haber etiquetado todos los nodos posibles ir al paso 4).
Paso 4) Inspección de nodos
Caso 1) Si todos los nodos están etiquetados y no existe alguno que tenga la
etiqueta de �solución candidata� entonces terminamos, el problema entero no
tiene solución.
Caso 2) Si todos los nodos están etiquetados y existen alguno o algunos nodos
etiquetados con �solución candidata�entonces ir al paso 5).
Caso 3 ) Si existen nodos sin etiquetar, esto quiere decir que de esos nodos se
puede seguir iterando (rami�cando), ir al paso 2).
31
Paso 5) Solución óptima
El valor óptimo de la función objetivo es z�(X�) = maxfz (Xi) j Xi es un nodo
etiquetado con solución candidatag y la solución óptima es X�:
Ejemplo 9: Este procedimiento se ilustra con el siguiente ejemplo:
P
8>>><>>>:
max z = 6x1 + 16x2 + 10x3 + 20x4
s.a 6x1 + 14x2 + 9x3 + 17x4 � 40
xi � 0 y xi 2 Z para i = 1; 2; :::; 4:
9>>>=>>>;
El primer paso es resolver el problema relajado, que es el siguiente:
P1
8>>><>>>:
max z = 6x1 + 16x2 + 10x3 + 20x4
s.a 6x1 + 14x2 + 9x3 + 17x4 � 40
x1; x2; x3; x4 � 0.
9>>>=>>>;
Primero se ordenan las variables de tal manera que cumplan:
c10
a10
� c2
0
a20
� ::: � cn
0
an0
Los cocientes ordenados son
c1
a1
6
6
= 1 4�
c40
a40
c2
a2
16
14
� 1:14 2� c20
a20
c3
a3
10
9
� 1:11 3� c30
a30
c4
a4
40
17
� 2:352 1� c10
a10
y de acuerdo al nuevo orden se les asignarán valores a las variables.
Nodo 1 Buscamos la solución óptima del problema relajado P1:
Se procede como en (1) y la solución óptima de P1 es ba10 =
40
17
= 2:35 = x4 y
xi = 0 para i 6= 4, es decir, X1 =
�
0; 0; 0; 40
17
�
= (0; 0; 0; 2:35) y el valor de la función
objetivo es z(X1) = 80017 = 47:05; como x4 es un número no entero, entonces del nodo
1 saldrán dos nodos, nodo 2 y nodo 3.
32
Nodo 2 En este nodo tenemos el siguiente problema:
P2
8>>>>><>>>>>:
max z = 6x1 + 16x2 + 10x3 + 20x4
s.a 6x1 + 14x2 + 9x3 + 17x4 � 40
x4 � 2
x1; x2; x3; x4 � 0.
9>>>>>=>>>>>;
del cual obtenemos la siguiente solución:
X2 = (0; 0:42; 0; 2) y z(X2) = 46:72:
Nodo 3 Ahora el problema que debemos de resolver es el siguiente:
P3
8>>>>><>>>>>:
max z = 6x1 + 16x2 + 10x3 + 20x4
s.a 6x1 + 14x2 + 9x3 + 17x4 � 40
x4 � 3
x1; x2; x3; x4 � 0.
9>>>>>=>>>>>;
con esta nueva restricción la solución al problema no es factible ya que si x4 = 3
ya no satisface la restricción de capacidad. Por lo que este subproblema queda eli-
minado, es decir, este nodo se etiquetará como �solución no factible� y ya no se
rami�ca.
1
2
3
x4 ≥ 3
x4 ≤ 2
X1=(0,0,0,2.352) z1=47.05
X2=(0,0.42,0,2) z(X2)=46.72 X3=(0,0,0,3)
Solución no factible
Como en la solución del nodo 2 existe una componente no entera se continua rami-
�cando, es decir, del nodo 2 saldrán dos ramas que son nodo 4 y nodo 5.
33
Nodo 4 En este nodo tenemos el siguiente problema:
P4
8>>>>>>>><>>>>>>>>:
max z = 6x1 + 16x2 + 10x3 + 20x4
s.a 6x1 + 14x2 + 9x3 + 17x4 � 40
x4 � 2
x2 = 0
x1; x2; x3; x4 � 0.
9>>>>>>>>=>>>>>>>>;
La solución de P4 es X4 = (0; 0; 23 ; 2) = (0; 0; 0:66; 2) y z(X4) =
140
3
= 46:6:
Nodo 5 En este nodo tenemos el problema:
P5
8>>>>>>>><>>>>>>>>:
max z = 6x1 + 16x2 + 10x3 + 20x4
s.a 6x1 + 14x2 + 9x3 + 17x4 � 40
x4 � 2
x2 � 1
x1; x2; x3; x4 � 0:
9>>>>>>>>=>>>>>>>>;
del cual tenemos la solución X5 = (0; 1; 0; 2617) = (0; 1; 0; 1:52) y z(X5) =
792
17
= 46:58:
El árbol correspondiente hasta el nodo 5 se muestra en la siguiente �gura:
x2 ≥ 1
4 5
x2 = 0
X5=(0,1,0,1.52) z( X5 )=46.4
1
2
3
x4 ≥ 3
x4 ≤ 2
X1=(0,0,0,2.352) z1=47.05
X2=(0,0.42,0,2) z(X2)=46.72 X3=(0,0,0,3)
Solución no factible
X4=(0,0,0.66, 2) z( X4 )= 46.6
Como los nodos 4 y 5 tienen una componente no entera, entonces, de estos salen
dos ramas. En la siguiente iteración se rami�cará del nodo 4 ya que el valor de z
es mayor que la del nodo 5.
34
Nodo 6 Tenemos el siguiente problema:
P6
8>>>>>>>>>>><>>>>>>>>>>>:
max z = 6x1 + 16x2 + 10x3 + 20x4
s.a 6x1 + 14x2 + 9x3 + 17x4 � 40
x4 � 2
x2 = 0
x3 = 0
x1; x2; x3; x4 � 0.
9>>>>>>>>>>>=>>>>>>>>>>>;
del cual tenemos la solución X6 = (1; 0; 0; 2) y z(X6) = 46; como todas las compo-
nentes de X son enteras este nodo se etiquetará como �solución candidata�.
Nodo 7 Tenemos el siguiente problema:
P7
8>>>>>>>>>>><>>>>>>>>>>>:
max z = 6x1 + 16x2 + 10x3 + 20x4
s.a 6x1 + 14x2 + 9x3 + 17x4 � 40
x4 � 2
x2 = 0
x3 � 1
x1; x2; x3; x4 � 0.
9>>>>>>>>>>>=>>>>>>>>>>>;
del cual obtenemos la siguiente solución X7 =
�
0; 0; 1; 31
17
�
= (0; 0; 1; 1:823) y
z(X7) = 46
8
17
= 46:47:
El árbol correspondiente hasta esta iteración se muestra en la siguiente �gura:
6 7
x3 ≥ 1x3 =0
x2 ≥ 1
4 5
x2 = 0
X5=(0,1,0,1.52) z( X5 )=46.4
1
2
3
x4 ≥ 3
x4 ≤ 2
X1=(0,0,0,2.352) z1=47.05
X2=(0,0.42,0,2) z(X2)=46.72 X3=(0,0,0,3)
Solución no factible
X4=(0,0,0.66, 2) z( X4 )= 46.6
X6 =(1,0,0,2) z( X6 )=46
Sol. Candidata
X7=(0,0,1,1.823)
z( X7 )=46.47
Nodo no prometedor
35
A partir de esta �gura se puede concluir que la solución óptima es la que está asociada
con el nodo 6 que es X6 = (1; 0; 0; 2) y z(X6) = 46 ya que la función objetivo de
los dos nodos restantes es de 46.588 (nodo 5) y 46.47 (nodo 7), esto quiere decir
que si de alguno de estos dos nodos obtenemos otra solución candidata el valor
máximo de z será 46. Pues los coe�cientes de las variables en z son enteros.
Si lo que se desea es obtener todas las soluciones óptimas, entonces se sigue rami-
�cando, obteniendo el siguiente árbol del cual obtenemos las siguientes soluciones:
X6 = (1; 0; 0; 2) con z(X6) = 46 (nodo6) y X12 = (0; 1; 1; 1) con z(X12) = 46
(nodo 12).
6 7
x3 ≥ 1x3 =0
x2 ≥ 1
4 5
x2 = 0
X5=(0,1,0,1.52) z( X5 )=46.4
1
2
3
x4 ≥ 3
x4 ≤ 2
X1=(0,0,0,2.352) z1=47.05
X2=(0,0.42,0,2) z(X2)=46.72 X3=(0,0,0,3)
Solución no factible
X4=(0,0,0.66, 2) z( X4 )= 46.6
X6 =(1,0,0,2) z( X6 )=46
Sol. Candidata
X7=(0,0,1,1.823)
z( X7 )=46.47
10 11
8
9
x4 ≥ 2
x4 ≤ 1
x4 ≥ 2
x4 ≤ 1
X8=(0,1.642,0,1) z(X8)=46.27
X10=(0,0,2.55,1)
z(X10)=45.5
Sol. No prometedora
x2 ≥ 2
x2 ≤ 1
12
13
X12=(0,1,1,1) z(X12)=46
Sol. Candidata
X9=(0,1,0,2)
Solución no factible
X11=(0,0,1,2)
Solución no factible
X13=(0,2,0,0.705) z(X13)=46.11
14
15
x4 ≥ 1
X15=(0,2,0,1)
Sol. No Factible
x4 = 0
X14=(0,2,1.333,0) z(X14)=45.333
Sol. No prometedora
36
2.3.2 Algoritmo para el problema acotado
Para el caso en que las variables sean acotadas, se resuelve de la siguiente manera.
Paso 1) Solución del problema relajado
Se resuelve la relajación PL del problema entero como en (2) y llegamos a la
solución X1 y z1 = z (X1), si xj 2 Z 8j terminamos, la solución encontrada es
óptima, si no ir al paso 2.
Paso 2) Rami�cación
Sea l el nodo pendiente del cual se va a seguir iterando, sean Xl la solución de
dicho nodo y xj una componente no entera de dicha solución, se crean d+ 1 nodos:
l + 1; l + 2;...l + d + 1 (donde d es la cota de xj), a cada nodo se le agrega una
restricción diferente, al problema del nodo l + 1 se le asigna la restricción xj = 0;
al nodo l + 2 la restricción xj = 1; al nodo l + 3 la restricción xj = 2 y al nodo
l + (d+ 1) la restricción xj = d. Esto se muestra en la �gura.
i
l+1
l+(d+1)
xj =d
xj =0
l+2
l+k
xj =k-1xj=1
. . .
. . 
.
i
l+1
l+(d+1)
xj =d
xj =0
l+2
l+k
xj =k-1xj=1
. . .
. . 
.
Los problemas de estos nodos son resueltos como en (2) después ir al paso 3).
Los Pasos 3, 4 y 5) son los mismos que en el algoritmo anterior.
37
Ejemplo 10: Este procedimiento se ilustra con el siguiente ejercicio:
P
8>>>>><>>>>>:
max z = 18x1 + 14x2 + 8x3 + 4x4
s.a 15x1 + 12x2 + 7x3 + 4x4 � 33
x1 � 1 x2 � 2 x3 � 3 x4 � 2
xi � 0 y enteros para i = 1; 2; :::; 4:
9>>>>>=>>>>>;
Nodo 1 La relajación del problema P es:
P1
8>>>>><>>>>>:
max z = 18x1 + 14x2 + 8x3 + 4x4
s.a 15x1 + 12x2 + 7x3 + 4x4 � 33
x1 � 1 x2 � 2 x3 � 3 x4 � 2
xi � 0 para i = 1; 2; :::; 4:
9>>>>>=>>>>>;
Se procede como en (2), primero se ordenan las variables de tal manera que cumplan:
c10
a10
� c2
0
a20
� ::: � cn
0
an0
:
Los cocientes ordenados son:
c1
a1
18
15
= 1:2 1�
c10
a10
c2
a2
14
12
� 1:16 2� c20
a20
c3
a3
8
7
� 1:14 3� c30
a30
c4
a4
4
4
= 1 4�
c40
a40
y la solución óptima de P1 es X1 = (1; 1:5; 0; 0) con z(X1) = 39, como no es entera
se rami�cará de este nodo.
Nodo 2 Al subproblema P2 le corresponde la restricción x2 = 0; por lo que el
problema se expresa como sigue:
P2
8>>>>>>>><>>>>>>>>:
max z = 18x1 + 14x2 + 8x3 + 4x4
s.a 15x1 + 12x2 + 7x3 + 4x4 � 33
x1 � 1 x2 � 2 x3 � 3 x4 � 2
x2 = 0
xi � 0 para i = 1; 2; :::; 4:
9>>>>>>>>=>>>>>>>>;
38
la solución es X2 = (1; 0; 187 ; 0) = (1; 0; 2:571; 0) con z(X2) = 38
4
7
= 38:571:
Nodo 3 El subproblema P3 tiene la siguiente restricción x2 = 1; por lo que el
problema se expresa como sigue:
P3
8>>>>>>>><>>>>>>>>:
max z = 18x1 + 14x2 + 8x3 + 4x4
s.a 15x1 + 12x2 + 7x3 + 4x4 � 33
x1 � 1 x2 � 2 x3 � 3 x4 � 2
x2 = 1
xi � 0 para i = 1; 2; :::; 4:
9>>>>>>>>=>>>>>>>>;
la solución de P3 es X3 =
�
1; 1; 6
7
; 0
�
= (1; 1; 0:857; 0) con z(X3) = 3867 = 38:857:
Nodo 4 El subproblema P4 tendrá la restricción x2 = 2; por lo que el problema
se expresa como sigue:
P4
8>>>>>>>><>>>>>>>>:
max z = 18x1 + 14x2 + 8x3 + 4x4
s.a 15x1 + 12x2 + 7x3 + 4x4 � 33
x1 � 1 x2 � 2 x3 � 3 x4 � 2
x2 = 2
xi � 0 para i = 1; 2; :::; 4:
9>>>>>>>>=>>>>>>>>;
la solución es X4 =
�
9
15
; 2; 0; 0
�
= (0:6; 2; 0; 0) con z(X4) = 3845 = 38:8. Estas
rami�caciones se ilustran con el siguiente árbol :
1
2
4
X1 = (1, 1.5, 0, 0)
z (X1) = 39X 2= (1, 0, 2.571, 0)
z (X 2) =3 8.57
x2 =0
3
x2 =2
x2 =1
X 3 = (1, 1, 0.857, 0)
z (X 3) = 38.85
X4 = (0.6, 2, 0, 0)
z (X4) = 38.8
Se rami�cará del nodo 3 ya que este tiene la mejor cota, como x3 es la variable que
no es entera se le dan los valores de x3 = 0, x3 = 1, x3 = 2 y x3 = 3 para los nodos
5, 6, 7 y 8 respectivamemte.
39
Nodo 5 El subproblema P5 tiene la siguiente restricción x3 = 0; por lo que el
problema se expresa como sigue:
P5
8>>>>>>>>>>><>>>>>>>>>>>:
max z = 18x1 + 14x2 + 8x3 + 4x4
s.a 15x1 + 12x2 + 7x3 + 4x4 � 33
x1 � 1 x2 � 2 x3 � 3 x4 � 2
x2 = 1
x3 = 0
xi � 0 para i = 1; 2; :::; 4:
9>>>>>>>>>>>=>>>>>>>>>>>;
la solución es X5 =
�
1; 1; 0; 6
4
�
= (1; 1; 0; 1:5) con z(X5) = 38.
Nodo 6 El subproblema P6 tiene la siguiente restricción x3 = 1; por lo que el
problema se expresa como sigue:
P6
8>>>>>>>>>>>>>>>>><>>>>>>>>>>>>>>>>>:
max z = 18x1 + 14x2 + 8x3 + 4x4
s.a
15x1 + 12x2 + 7x3 + 4x4 � 33
x1 � 1 x2 � 2 x3 � 3 x4 � 2
x2 = 1
x3 = 1
xi � 0
para i = 1; 2; :::; 4
9>>>>>>>>>>>>>>>>>=>>>>>>>>>>>>>>>>>;
la solución es X6 =
�
14
15
; 1; 1; 0
�
= (0:933; 1; 1; 0) con z(X6) = 38:8.
Nodo 7 El subproblema P7 tiene la siguiente restricción x3 = 2; por lo que el
40
problema se expresa como sigue:
P7
8>>>>>>>>>>><>>>>>>>>>>>:
max z = 18x1 + 14x2 + 8x3 + 4x4
s.a 15x1 + 12x2 + 7x3 + 4x4 � 33
x1 � 1 x2 � 2 x3 � 3 x4 � 2
x2 = 1
x3 = 2
xi � 0 para i = 1; 2; :::; 4
9>>>>>>>>>>>=>>>>>>>>>>>;
la solución es X7 =
�
7
15
; 1; 2; 0
�
= (0:466; 1; 2; 0) con z(X7) = 38:4.
Nodo 8 El subproblema P8 tiene la siguiente restricción x3 = 3; por lo que el
problema se expresa como sigue:
P8
8>>>>>>>>>>><>>>>>>>>>>>:
max z = 18x1 + 14x2 + 8x3 + 4x4
s.a 15x1 + 12x2 + 7x3 + 4x4 � 33
x1 � 1 x2 � 2 x3 � 3 x4 � 2
x2 = 1
x3 = 3
xi � 0 para i = 1; 2; :::; 4:
9>>>>>>>>>>>=>>>>>>>>>>>;
la solución es X8 = (0; 1; 3; 0) con z(X8) = 38, la cual es entera por lo que se
etiquetará este nodo como solución candidata, se puede observar que todos lo nodos
colgantes tienen como cota 38.57 (nodo 2), 38 (nodo 5), 38.79 (nodo 6), 38.39
(nodo 7) y 38.8 (nodo 4); esto quiere decir que de estos nodos no se obtendrá un
mejor valor para la función objetivo, ya que los coe�cientes son enteros, por esta
razón se concluye que la solución óptima para el problema es: X8 = (0; 1; 3; 0) con
z(X8) = 38:
41
1
2
4
X1 = (1, 1.5, 0, 0)
z (X1) = 39X 2= (1, 0, 2.571, 0)
z (X 2) =3 8.57
Nodo no
prometedor
x2 =0
3
x2 =2
x2 =1
X 3 = (1, 1, 0.857, 0)
z (X 3) = 38.85
X4 = (0.6, 2, 0, 0)
z (X4) = 38.8
Nodo no
prometedor
8
7
6
5
X5=(1, 1, 0, 1.5)
z(X5)=38
Nodo no
prometedor
X8=(0, 1, 3, 0)
z(X8)=38
Solución
Candidata
x3 =0
x3 =1
x3 =2
x3 =3
X6=(0.933, 1, 1, 0)
z(X6)=38.8
Nodo no
prometedor
X7=(0.466, 1, 2, 0)
z(X7)=38.4 Nodo
no prometedor
Si lo que se desea es obtener todas las soluciones óptimas para el problema se procede
análogamente con los demás nodos y el árbol �nal es:
X16=(0.8, 0, 3,0)
z(X16)=38.4
14
13
15
18
x1 =0
9
10
x1 =0
x1 =1
X10=(1, 2, 0, 0)
Solución no
factible
X9=(0, 2, 1.285, 0)
z(X9)=38.28
x3 =1
1
2
4
X1 = (1, 1.5, 0, 0)
z (X1) = 39X 2= (1, 0, 2.571, 0)
z (X 2) =3 8.57
x2 =0
3
x2 =2
x2 =1
X 3 = (1, 1, 0.857, 0)
z (X 3) = 38.85
X4 = (0.6, 2, 0, 0)
z (X4) = 38.8
8
7
6
5
X5=(1, 1, 0, 1.5)
z(X5)=38
Nodo no
prometedor
X8=(0, 1, 3, 0)
z(X8)=38
Solución
Candidata
x3 =0
x3 =1
x3 =2
x3 =3
X6=(0.933, 1, 1, 0)
z(X6)=38.8
X7=(0.466, 1, 2, 0)
z(X7)=38.4
x3 =0
16
x3 =1
x3 =2
x3 =3
X13=(1, 0, 0, 2)
z(X13)=26
Solución
Candidata
X14=(1, 0, 1, 2)
z(X14)=34
Solución
Candidata
X15=(1, 0, 2, 1)
z(X15)=38
Solución
Candidata
17
X17=(0, 0, 3, 2)
z(X17)=32
Nodo no
prometedor
X18=(1, 0, 3, 0)
Solución no
factible
x1 =0
x1 =1
11
12
x1 = 1X11=(0, 1, 1, 2)
z(X11)=30
Nodo no
prometedor
X12=(1, 1, 1, 0)
Solución no
factible
19 20
x1 =0
x1 = 1
X19=(0, 1, 2, 1.75)
z(X19)=37
Nodo no
prometedor
X20=(1, 1, 2, 0)
Solución no
factible
21
X21=(0, 2, 0, 2)
z(X21)=36
Nodo no
prometedor
x3 =0
22
23
X23=(0, 2, 2, 0)
Solución no
factible
24
X24=(0, 2, 3, 0)
Soluciónno
factiblex3 =2
x3 =3
X22=(0, 2, 1, 0.5 )
z(X22)=38
Nodo no prometedor
42
Se observa que existen 5 nodos con etiqueta de solución candidata, por lo que
z�(X�) = max f26; 34; 38; 32; 38g = 38; como hay dos nodos con ese valor podemos
concluir que existen dos soluciones óptimas y son las correspondientes a los nodos
8 y 15, es decir, X8 = (0; 1; 3; 0) y X15 = (1; 0; 2; 1) con z�(X�) = 38:
2.3.3 Algoritmo de Balas (Para el Problema Binario de la
Mochila)
Egon Balas desarrolló un método para resolver problemas de optimización binarios
(0 - 1), el cual sólo se aplica a problemas con coe�cientes no negativos, sin embargo
cualquier problema binario puede convertirse a uno de esta forma ya que basta con
cambiar la(s) variable(s) xi con ci < 0 por xi0 = 1 � xi. Este método utiliza rami-
�cación y acotamiento para obtener la solución óptima del problema, la diferencia
con los métodos anteriores es que todos los nodos (subproblemas) tienen una solución
entera aunque no sea factible, esto es por que se le asigna el valor de 1 a todas las
variables del problema, siempre y cuando se trate de un problema de maximización
(es decir, mete todo en la mochila), si esta solución es factible, entonces, es la óptima,
en otro caso, se procede a rami�car quitando el artículo del cual se obtiene menos
rendimiento y así hasta llegar a una solución factible, es decir, se parte de una solución
óptima que en muchos casos no es factible y con �rami�cación y acotamiento� se
intenta obtener la factibilidad. Las variables del problema por ser binarias, sólo
tienen el valor de 0 y 1, éstas son asignadas a los conjuntos W (variables �jas con
valor uno), V (variables �jas con valor cero) y un tercer conjunto F que tendrá a
las variables libres, que en un principio todas valen uno, es decir, los conjuntos V y
W son los que guardan las modi�caciones que se les vayan haciendo a las variables
para hacer factible la solución óptima obtenida en cada nodo (en cada asignación
de W). Cada nodo tiene una partición diferente de los conjuntos anteriores, también
tiene dos cotas, una para la función objetivo � y otra para la capacidad �. Todo el
43
procedimiento se desarrolla con el siguiente algoritmo:
Algoritmo:
Inicialización: Se de�nen tres conjuntos para el primer nodo W, V y F de la
siguiente manera:
Conjunto de variables �jas con valor 1: W = fxi j xi = 1 para i = 1; 2; :::; ng.
Conjunto de variables �jas con valor 0: V = fxi j xi = 0 para i = 1; 2; :::; ng.
Conjunto de variables libres, con valor 1 temporalmente.:
F = fxi j xi es variable libre i = 1; 2; :::; ng
Por ser un problema de maximización todas las variables son asignadas al conjunto
F con el valor de uno (X0 = (1; 1; :::; 1)) y los conjuntos W y V no tienen elementos,
es decir,
W = ;
V = ;
F = fx1;x2; :::; xng :
Si X0 es factible, entonces es la solución óptima, pues ci � 0 para i = 1; :::; n y el
valor óptimo de la función objetivo es z(X0) =
nX
i=1
ci. En otro caso, como la solución
encontrada no es factible, se crea una variable r la cual tendrá asignado el número
del nodo generado.
r = 1, ir al paso 1.
Paso 2) Cotas
Se generan dos nodos para los cuales se obtienen dos cotas para cada uno, una
que involucra el valor de la función objetivo y la otra la capacidad marginal de la
mochila, se procede de la siguiente manera:
44
Si cm = min fcij xi 2 F para i = 1; :::ng ; entonces la cota superior del valor de la
función objetivo es � =
 X
xi2W
ci +
X
xi2F
ci
!
� cm y la cota de capacidad es � =
nX
i=1
ai
tal que xi = 1. Sea xm la variable correspondiente al coe�ciente cm, la partición de
los conjuntos W;V y F se de�ne como sigue:
� Nodo r + 1 : Al subproblema r+1 se le agrega la restricción xm = 1; entonces:
F = F � fxmg
W = W [ fxmg
V = V:
� Nodo r + 2 : Al subproblema r+2 se le agrega la restricción xm = 0; entonces:
F = F � fxmg
W = W
V = V [ fxmg
r = r + 2 (contador de nodos).
Paso 3) Etiquetado
Para etiquetar los nodos es necesario comparar las dos cotas de cada nodo con
las demás. Empezando por �:
� Si � 6 b, terminamos de rami�car de este nodo (ya que la solución correspon-
diente a este nodo, ya es factible), existen dos casos:
Caso 1) Si F 6= ;, es decir, V [W 6= fx1; x2; :::; xng entonces:
45
W = fW [ fxigj xi 2 Fg y V = V y este nodo es etiquetado como �solución
candidata�.
Caso 2) Si F = ; quiere decir que todas las variables han sido asignadas a los
conjuntosW y V , es decir, V [W = fx1; x2; :::; xng; por lo que también es etiquetado
como �solución candidata�.
� Si � > b; entonces se tienen tres casos:
Caso 1) Si existen nodos colgantes no etiquetados y � � z(Xk); donde Xk es el
nodo que tiene la cota más grande de todos los nodos etiquetados como �solución
candidata�, entonces serán etiquetados como �nodo no prometedor�.
Caso 2) Si existen nodos colgantes sin etiquetar y � > z(Xk), donde Xk es el
nodo que tiene la cota más grande de todos los nodos etiquetados como �solución
candidata�, se toma el que tiene la mejor cota para la función objetivo e ir al paso
2.
Caso 3) Si todos los nodos están etiquetados, entonces ir al paso 4.
Paso 4) Solución óptima
El valor óptimo de la función objetivo es z�(X�) = maxfz (Xi) j Xi es un nodo
etiquetado con solución candidatag y la solución óptima es X�:
Ejemplo 11: Este algoritmo se ilustra con el siguiente ejemplo:
max z = 80x1 + 48x2 + 14x3 + 18x4 + 10x5
s.a 8x1 + 6x2 + 2x3 + 3x4 + 2x5 � 11
xi = f0; 1g para i = 1; 2; 3; 4; 5:
Nodo 1 Inicialización: r = 1
F = fx1; x2; x3; x4; x5g
46
W = ?
V = ?
� =
 X
xi2W
ci +
X
xi2F
ci
!
� cm = (0 + 170)� 10 = 160
� = 21
Nodo 2 Como la solución del nodo 1 no es factible y cm = c5 = 10 y xm = x5,
entonces a este nodo le corresponde la restricción x5 = 1 :
F = F � fx5g = fx1; x2; x3; x4g
W = W [ fx5g = fx5g
V = V = ?
� =
 X
xi2W
ci +
X
xi2F
ci
!
� cm = (10 + 160)� 14 = 156
� = 21:
Nodo 3 A este nodo le corresponde la restricción x5 = 0 :
F = F � fx5g = fx1; x2; x3; x4g
W = W = ?
V = V [ fx5g = fx5g
� =
 X
xi2W
ci +
X
xi2F
ci
!
� cm = 0 + 160� 14 = 146
� = 19.
Estas iteraciones se ilustran con el siguiente árbol:
47
1
[160]
α=21
32
[156] [146]
α=19α=21
x5=1
x5=0
W = ø
V = ø
W = {x5 }
V = ø W = ø
V = {x5 }
Si procedemos análogamente obtenemos el siguiente árbol:
W = {x5, x3, x4, x2 }
V = ø
1
W = ø
V = ø
[160]
α=21
32
[156] [146]
α=19α=21
W = ø
V = {x5 }
W = {x5 }
V = ø
54
[152] [138]
α=19α=21
W = {x5, x3 }
V = ø
W = {x5 }
V = {x3 }
6
[122]
α=21
W = {x5 , x3 , x4 }
V = ø
[108]
α=19
W = {x5, x4}
V = {x3 }
7
[104]
α=18
W = {x5, x3 }
V = { x4 }
13
[90] W = {x5 }
V = {x3 , x4}
α=16
1716
α=21 α=15
α=18 α=12
[90] [42]
[76] [24]
W = {x5, x3 }
V = {x4, x2 }
W = {x5, x3, x2 }
V = { x4 }
W = {x5, x3, x4 }
V = { x2}
x5=0
x5=1
x4=1
x3=1
x2=1
x4 =1
x2=1
x2=0 x2=0
x4 =0
x3=0
x4=0
Nodo no
prometedor
W = {x5 ,x4,x2}
V = {x3 }
W = {x5, x4}
V = {x3, x2}
12
20
21x2=1
x2=0
[21]
[76]
α=19
α=13
Nodo no
prometedor
Nodo no
prometedor
Nodo no
prometedor
Nodo no
prometedor
Nodo no
prometedor
Nodo no
prometedor
22 23
48
3
W = ø
V = {x5 }
[146]
α=19
9
8
[142] [128]
α=17
α=19
W = ø
V = {x5, x3 }
W = {x3 }
V = {x5 }
[112] [94]
α=16α=19
W = {x3, x4 }
V = {x5 }
W = {x3 }
V = {x5, x4 }
[80]
α=19
W = {x3 , x4 , x2 }
V = {x5 }
[98] α=14
W = {x4}
V = {x5 , x3}
[32]
W = {x3, x4 }
V = {x5 , x2 }
15
[80]
W = ø
V = {x5, x3, x4 }
α=17
α=13
x3 =0
x3 =1
x2=1
x4=1
x2=0
x4=0
Nodo no
prometedor
W = {x4,x2}
V = {x5, x3}
V = {x5, x3, x2 }
W = { x4 }
14
24
25x2 =1
x2=0
[18]
[66]
α=17
α=11
Solución Candidata
X = (1, 0, 0, 1, 0) y z = 98
Nodo no
prometedor
Nodo no
prometedor
Nodo no
prometedor
x4=1
x4 =0
Nodo no
prometedor
18
19
10 11
Finalmente podemos concluir que la solución óptima es: X = (1; 0; 0; 1; 0) con el
valor óptimo: z�(X) = 98 en el nodo 25.
2.3.4 Algoritmo para el problema binario
Si consideramos el problema en el cual cada variable xj sólo puede tomar los valores
de 0y 1, entonces las restricciones xj > 0 y xj 6 1 son equivalentes a xj = 0 y xj = 1
respectivamente.
Paso1) Solución del problema relajado
Se resuelve la relajación PL del problema entero como en la sección 2:1:3 y
llegamos a la solución X1 y z1 = z (X1), si xj = 0 o xj = 1 8j terminamos, la
solución encontrada es óptima, si no ir al paso 2.
Paso2) Rami�cación
Sean l el nodo pendiente del cual se va a seguir iterando, Xl la solución de dicho
nodo y xj una componente tal que 0 < xj < 1; donde i es el número de nodo y j es
49
el lugar de la componente que tiene el valor fraccional, se crean dos nodos, el primero
es el nodo l + 1 al que se le introduce la restricción xj = 0, y al segundo l + 2 se le
agrega la restricción xj = 1; como se muestra en la �gura.
i
l+1 l+2
xj = 1
xj = 0
El problema lineal de cada nodo se resuelve, después ir al paso 3:
Paso 3) Etiquetado
Caso1) Si la solución encontrada es una solución entera dicho nodo es etiquetado
como �solución candidata�.
Caso 2) Si existen nodos no etiquetados con cota menor que z(Xk); para algún
nodo Xk etiquetado como �solución candidata�, serán etiquetados como �nodo
no prometedor�.
Caso3) Si la solución encontrada no es factible, a este nodo se le asignará la
etiqueta de �solución no factible�.
Después de haber etiquetado todos los nodos posibles ir al paso 4).
Paso 4) Inspección de nodos
Caso1) Si todos los nodos están etiquetados y no existe alguno que tenga la
etiqueta de �solución candidata� entonces terminamos, el problema entero no
tiene solución.
Caso2) Si todos los nodos están etiquetados y existen alguno o algunos nodos
50
etiquetados con �solución candidata�ir al paso 5).
Caso3) Si existen nodos sin etiquetar, esto quiere decir que de ellos se puede
seguir iterando (rami�cando), ir al paso 2).
Paso 5) Solución óptima
El valor óptimo de la función objetivo es z�(X�) = maxfz (Xj) j Xj es un nodo
etiquetado con solución candidatag y la solución óptima es X�:
Ejemplo 12:
max z = 12x1 + 12x2 + 9x3 + 15x4 + 90x5 + 26x6 + 112x7
s.a 3x1 + 4x2 + 3x3 + 3x4 + 15x5 + 13x6 + 16x7 � 35
xi = f0; 1g 8i 2 f1; 2; :::; 7g :
Nodo 1 Resolvemos el problema relajado que es el siguiente:
max z = 12x1 + 12x2 + 9x3 + 15x4 + 90x5 + 26x6 + 112x7
s.a 3x1 + 4x2 + 3x3 + 3x4 + 15x5 + 13x6 + 16x7 � 35
xi � 0 y xi � 1 8i 2 f1; 2; :::; 7g :
La solución óptima para el problema relajado es:
X1 =
�
1
3
; 0; 0; 1; 1; 0; 1
�
= (0:333; 0; 0; 1; 1; 0; 1) y z(X1) = 221:
Como tenemos un valor en X 1 que es fraccional, debemos rami�car desde este
nodo.
Nodo 2 En este nodo tenemos el mismo problema que en el nodo 1 más una
restricción de rami�cación que es x1 = 0 y el problema queda de la siguiente manera:
max z = 12x1 + 12x2 + 9x3 + 15x4 + 90x5 + 26x6 + 112x7
s.a 3x1 + 4x2 + 3x3 + 3x4 + 15x5 + 13x6 + 16x7 � 35
x1 = 0
xi � 0 y xi � 1 i 2 f1; 2; :::; 7g :
51
del cual obtenemos la solución:
X2 =
�
1; 1
4
; 0; 1; 1; 0; 1
�
= (1; 0:25; 0; 1; 1; 0; 1) y z(X2) = 220:
Nodo 3 Al problema de este nodo se le agrega la restricción x1 = 1 :
max z = 12x1 + 12x2 + 9x3 + 15x4 + 90x5 + 26x6 + 112x7
s.a 3x1 + 4x2 + 3x3 + 3x4 + 15x5 + 13x6 + 16x7 � 35
x1 = 1
xi � 0 y xi � 1 i 2 f1; 2; :::; 7g :
del que obtenemos la solución X3 =
�
1; 0; 0; 1
3
; 1; 0; 1
�
= (1; 0; 0; 0:333; 1; 0; 1) y
z(X3) = 219:
Esto se ilustra con la siguiente �gura:
1
2
3
X1=(0.333, 0, 0, 1, 1, 0, 1)
z(X1)=221
X2=(0, 0.25, 0, 1, 1, 0, 1)
z(X2)=220 X3=(1, 0, 0, 0.333, 1, 0, 1)
z(X3)=219
x1 =0
x1=1
Rami�camos el nodo 2 porque tiene la cota mayor.
Nodo 4 En este nodo se tiene el mismo problema que en el 2 más una restri-
cción de rami�cación que es x2 = 0 por lo que el problema nos queda de la siguiente
manera:
max z = 12x1 + 12x2 + 9x3 + 15x4 + 90x5 + 26x6 + 112x7
s.a 3x1 + 4x2 + 3x3 + 3x4 + 15x5 + 13x6 + 16x7 � 35
x1 = 0
x2 = 0
xi � 0 y xi � 1 i 2 f1; 2; :::; 7g :
la solución es X4 =
�
0; 0; 1
3
; 1; 1; 0; 1
�
= (0; 0; 0:333; 1; 1; 0; 1) y z (X4) = 220.
52
Nodo 5 A este nodo se le agrega la restricción de x2 = 1 :
max z = 12x1 + 12x2 + 9x3 + 15x4 + 90x5 + 26x6 + 112x7
s.a 3x1 + 4x2 + 3x3 + 3x4 + 15x5 + 13x6 + 16x7 � 35
x1 = 0
x2 = 1
xi � 0 y xi � 1 i 2 f1; 2; :::; 7g :
del que obtenemos la solución X5 = (0; 1; 0; 0; 1; 0; 1) y z (X5) = 214; a este nodo
lo etiquetamos con �solución candidata�, porque todos los elementos de X son
enteros.
Como no existe algún nodo con etiqueta menor que la del nodo 5 implica que de
los nodos 4 y 3 es posible seguir rami�cando, ahora vemos qué nodo tiene la cota
máxima y es el nodo 4, por lo que se rami�cará a partir de éste.
4
5
X4=(0, 0, 0.333, 1, 1, 0, 1)
z(X4)=220
X5=(0, 1, 0, 0, 1, 0, 1)
z(X5)=214
Sol. Candidata
x2 =0 x2=1
1
2
3
X1=(0.333, 0, 0, 1, 1, 0, 1)
z(X1)=221
X2=(0, 0.25, 0, 1, 1, 0, 1)
z(X2)=220 X3=(1, 0, 0, 0.333, 1, 0, 1)
z(X3)=219
x1 =0
x1=1
Nodo 6 Es el mismo problema que el del nodo 4 más la restricción x3 = 0 :
max z = 12x1 + 12x2 + 9x3 + 15x4 + 90x5 + 26x6 + 112x7
s.a 3x1 + 4x2 + 3x3 + 3x4 + 15x5 + 13x6 + 16x7 � 35
x1 = 0
x2 = 0
x3 = 0
xi � 0 y xi � 1 i 2 f1; 2; :::; 7g :
53
obtenemos X6 =
�
0; 0; 0; 1; 1; 1
13
; 1
�
= (0; 0; 0; 1; 1; 0:076; 1) y z (X6) = 219:
Nodo 7 En este nodo tenemos el siguiente problema en el cual se ha agregado la
restricción x3 = 1 :
max z = 12x1 + 12x2 + 9x3 + 15x4 + 90x5 + 26x6 + 112x7
s:a
3x1 + 4x2 + 3x3 + 3x4 + 15x5 + 13x6 + 16x7 � 35
x1 = 0
x2 = 0
x3 = 1
xi � 0 y xi � 1 i 2 f1; 2; :::; 7g :
obtenemos X7 =
�
0; 0; 1; 1
3
; 1; 0; 1
�
= (0; 0; 1; 0:333; 1; 0; 1)) y z (X7) = 216:
El siguiente árbol ilustra las rami�caciones anteriores:
6
7
X8=(0, 0, 0, 1, 1, 0.076, 1)
z(X8)=219
X7=(0, 0, 1, 0.333, 1, 0, 1)
z(X7)=216
x3 =0
x3=1
4
5
X4=(0, 0, 0.333, 1, 1, 0, 1)
z(X4)=220
X5=(0, 1, 0, 0, 1, 0, 1)
z(X5)=214
Sol. Candidata
x2 =0 x2=1
1
2
3
X1=(0.333, 0, 0, 1, 1, 0, 1)
z(X1)=221
X2=(0, 0.25, 0, 1, 1, 0, 1)
z(X2)=220 X3=(1, 0, 0, 0.333, 1, 0, 1)
z(X3)=219
x1 =0
x1=1
Como los nodos 6 y 3 tienen la misma cota superior, rami�camos del nodos 3 .
Nodo 8 Se resolverá el mismo problema que en el nodos 3 más la restricción de
54
rami�cación x4 = 0:
max z = 12x1 + 12x2 + 9x3 + 15x4 + 90x5 + 26x6 + 112x7
s:a 3x1 + 4x2 + 3x3 + 3x4 + 15x5 + 13x6 + 16x7 � 35
x1 = 1
x4 = 0
xi � 0 y xi � 1 i 2 f1; 2; :::; 7g :
obtenemos X8 =
�
1; 1
4
; 0; 0; 1; 0; 1
�
= (1; 0:25; 0; 0; 1; 0; 1) y z (X8) = 217:
Nodo 9 La restricción de rami�cación de este nodo es x4 = 1; por lo que el
problema a resolver es:
max z = 12x1 + 12x2 + 9x3 + 15x4 + 90x5 + 26x6 + 112x7
s.a 3x1 + 4x2 + 3x3 + 3x4 + 15x5 + 13x6 + 16x7 � 35
x1 = 1
x4 = 1
xi � 0 y xi � 1 i 2 f1; 2; :::; 7g :
obtenemos X9 =
�
1; 0; 0; 1; 13
15
; 0; 1
�
= (1; 0; 0; 1; 0; 866; 0; 1) y z (X9) = 217:
9
8
X8=(1, 0.25, 0, 0, 1, 0, 1)
z(X8)=217
X9=(1, 0, 0, 1, 0.866, 0, 1)
z(X9) = 217
x4 = 0 x4=1
6
7
X8=(0, 0, 0, 1, 1, 0.076, 1)
z(X8)=219
X7=(0, 0, 1, 0.333, 1, 0, 1)
z(X7)=216
x3 =0
x3=1
4
5
X4=(0, 0, 0.333, 1, 1, 0, 1)
z(X4)=220
X5=(0, 1, 0, 0, 1, 0, 1)
z(X5)=214
Sol. Candidata
x2 =0 x2=1
1
2
3
X1=(0.333, 0, 0, 1, 1, 0, 1)
z(X1)=221
X2=(0, 0.25, 0, 1, 1, 0, 1)
z(X2)=220 X3=(1, 0, 0, 0.333, 1, 0, 1)
z(X3)=219
x1 =0
x1=1
Como la cota del nodo 6 es mayor a la de los nodos 7, 8 y 9 elegimos al nodo 6
para seguir rami�cando.
55
Nodo 10 En este nodo tenemos el mismo problema del nodo 6 más una restri-
cción de rami�cación x6 = 0 y el problema a resolver es:
max z = 12x1 + 12x2 + 9x3 + 15x4 + 90x5 + 26x6 + 112x7
s.a 3x1 + 4x2 + 3x3 + 3x4 + 15x5 + 13x6 + 16x7 � 35
x1 = 0
x2 = 0
x3 = 0
x6 = 0
xi � 0 y xi � 1 i 2 f1; 2; :::; 7g :
obtenemos X10 = (0; 0; 0; 1; 1; 0; 1) y z (X10) = 217; este nodo lo etiquetamos como
�solución candidata�.
Nodo 11 Le agregamos la restricción x6 = 1 :
max z = 12x1 + 12x2 + 9x3 + 15x4 + 90x5 + 26x6 + 112x7
s.a 3x1 + 4x2 + 3x3 + 3x4 + 15x5 + 13x6 + 16x7 � 35
x1 = 0
x2 = 0
x3 = 0
x6 = 1
xi � 0 y xi � 1 i 2 f1; 2; :::; 7g :
obtenemos X11 =
�
0; 0; 0; 0; 6
15
; 1; 1
�
= (0; 0; 0; 0; 0:4; 1; 1) y z (X11) = 174:
Como elvalor de la función objetivo del nodo 10 es entera y es mayor o igual a
la de los nodos sin etiquetar, esto quiere decir que la solución obtenida en este nodo
es óptima ya que si se sigue rami�cando se obtendrían soluciones cuyo valor de la
función objetivo sería menor a 217, ya que los coe�cientes son enteros. Por lo tanto
X� = (0; 0; 0; 1; 1; 0; 1) y z� (X�) = 217 es óptima. El árbol asociado a este problema
es el siguiente:
56
10 11
X10=(0, 0, 0, 1, 1, 0, 1)
z(X10)=217
Solución candidata
X11=(0, 0, 0, 0, 0.4, 1, 1)
z(X11)=174
Nodo no prometedor
x6 =0
x6=1
9
8
X8=(1, 0.25, 0, 0, 1, 0, 1)
z(X8)=217
X9=(1, 0, 0, 1, 0.866, 0, 1)
z(X9) = 217
x4 = 0 x4=1
6
7
X8=(0, 0, 0, 1, 1, 0.076, 1)
z(X8)=219
X7=(0, 0, 1, 0.333, 1, 0, 1)
z(X7)=216
x3 =0
x3=1
4
5
X4=(0, 0, 0.333, 1, 1, 0, 1)
z(X4)=220
X5=(0, 1, 0, 0, 1, 0, 1)
z(X5)=214
Sol. Candidata
x2 =0 x2=1
1
2
3
X1=(0.333, 0, 0, 1, 1, 0, 1)
z(X1)=221
X2=(0, 0.25, 0, 1, 1, 0, 1)
z(X2)=220 X3=(1, 0, 0, 0.333, 1, 0, 1)
z(X3)=219
x1 =0
x1=1
Consideremos otro ejemplo:
Ejemplo 13:
max z = 80x1 + 48x2 + 14x3 + 18x4 + 10x5
s.a 8x1 + 6x2 + 2x3 + 3x4 + 2x5 � 11
xi = 0; 1 para i = f1; 2; :::; 5g :
Nodo 1 Resolvemos el problema relajado que es el siguiente:
max z = 80x1 + 48x2 + 14x3 + 18x4 + 10x5
s.a 8x1 + 6x2 + 2x3 + 3x4 + 2x5 � 11
xi � 0 y xi � 1 i 2 f1; 2; :::; 5g :
La solución óptima para el problema relajado es X1 =
�
1; 1
2
; 0; 0; 0
�
y z(X1) = 104:
Como tenemos un valor en X 1 que es fraccional, debemos rami�car desde este
nodo.
57
Nodo 2 En este nodo tenemos el mismo problema que en el nodo 1 más una
restricción de rami�cación, ésta es x2 = 0; el problema queda de la siguiente manera:
max z = 80x1 + 48x2 + 14x3 + 18x4 + 10x5
s.a 8x1 + 6x2 + 2x3 + 3x4 + 2x5 � 11
x2 = 0
xi � 0 xi � 1 i 2 f1; 2; :::; 5g :
del cual obtenemos X2 = (1; 0; 1; :3333; 0) y z(X2) = 100:
Nodo 3 Al problema de este nodo se le agrega la restricción x2 = 1:
max z = 80x1 + 48x2 + 14x3 + 18x4 + 0x5
s.a 8x1 + 6x2 + 2x3 + 3x4 + 2x5 � 11
x2 = 1
xi � 0 y xi � 1 i 2 f1; 2; :::; 5g
del cual obtenemos la solución X3 = (0:625; 1; 0; 0; 0) y z(X3) = 98:
Esto se ilustra con la siguiente �gura:
x2 =0
X1=(1.0.5,0,0,0)
z(X1)=1041
2 3
X3=(0.625,1,0,0,0)
z(X2)=98
x2 =1X2=(1,0,1,0.33,0)
z(X1)=100
Se escoge el nodo 2 para rami�car.
Nodo 4 En este nodo se tiene el mismo problema que en el 2 más una restri-
cción de rami�cación, ésta es x4 = 0; por lo que el problema nos queda de la siguiente
58
manera:
max z = 80x1 + 48x2 + 14x3 + 18x4 + 10x5
s.a 8x1 + 6x2 + 2x3 + 3x4 + 2x5 � 11
x2 = 0
x4 = 0
xi � 0 y xi � 1 i 2 f1; 2; :::; 5g :
y obtenemos X4 = (1; 0; 1; 0; 0:5) y z (X4) = 99.
Nodo 5 A este nodo se le agrega la restricción de x4 = 1 :
max z = 80x1 + 48x2 + 14x3 + 18x4 + 10x5
s.a 8x1 + 6x2 + 2x3 + 3x4 + 2x5 � 11
x2 = 0
x4 = 1
xi � 0 y xi � 1 i 2 f1; 2; :::; 5g:
y obtenemos X4 = (1; 0; 0; 1; 0) y z (X4) = 98; a este nodo lo etiquetamos con �solu-
ción candidata�, porque todos los elementos de X son enteros.
x2 =0
X1=(1.0.5,0,0,0)
z(X1)=1041
2 3
X3=(0.625,1,0,0,0)
z(X2)=98
Nodo no prometedor
x2 =1X2=(1,0,1,0.33,0)
z(X1)=100
x4 =0
x4 =1
54
X5=(1,0,0,1,0)
z(X5)=98
Solución Candidata
X4=(1,0,1,0,0.5)
z(X4)=99
Ahora vemos qué nodo tiene la cota máxima de los nodos que no están etiquetados y
es el nodo 4, por lo que se rami�cará a partir de éste.
59
Nodo 6 Es el mismo problema que el del nodo 4 más una restricción:
max z = 80x1 + 48x2 + 14x3 + 18x4 + 10x5
s.a 8x1 + 6x2 + 2x3 + 3x4 + 2x5 � 11
x2 = 0
x4 = 1
x5 = 0
xi � 0 y xi � 1 i 2 f1; 2; :::; 5g :
obtenemos X6 = (1; 0; 1; 0; 0) y z (X6) = 94; a este nodo se le asignara la etiqueta de
�solución candidata�.
Nodo 7 En este nodo tenemos tenemos el siguiente problema agragando la res-
tricción x5 = 1:
max z = 80x1 + 48x2 + 14x3 + 18x4 + 10x5
s.a 8x1 + 6x2 + 2x3 + 3x4 + 2x5 � 11
x2 = 0
x4 = 1
x5 = 1
xi � 0 y xi � 1 i 2 f1; 2; :::; 5g :
obtenemos X7 = (1; 0; 0:5; 0; 1) y z (X7) = 97; a este nodo se le asignará la etiqueta
de �nodo no prometedor�.
El siguiente árbol ilustra las rami�caciones anteriores
x2 =0
X1=(1.0.5,0,0,0)
z(X1)=1041
2 3
X3=(0.625,1,0,0,0)
z(X2)=98
Nodo no prometedor
x2 =1X2=(1,0,1,0.33,0)
z(X1)=100
x4 =0
x4 =1
54
X5=(1,0,0,1,0)
z(X5)=98
Solución Candidata
X4=(1,0,1,0,0.5)
z(X4)=99
x5 =0
x5 =1
76
X6=(1,0,1,0,0)
z(X6)=94
Solución candidata
X4=(1,0,0.5,0,1)
z(X4)=97
Nodo no prometedor
60
Con lo anterior podemos concluir que la solución óptima para el problema está en el
nodo 5 y es X5 = (1; 0; 0; 1; 0) y z(X5) = 98:
Si comparamos el algoritmo de Balas con la especialización de Dakin para el
problema binario observamos que con el de Balas se tienen que desarrollar todas
las ramas del árbol y el método es largo y exaustivo, en cambio con el algoritmo
de Dakin descartamos varias soluciones que no nos llevarían a la óptima y el árbol
�nal es pequeño por lo que podemos concluir que en cuestión de rapidez es mejor
el algoritmo de Dakin que el algoritmo de Balas ya que en e�ciencia con ambos
algoritmos se llega al óptimo.
61
Capítulo 3
Programación dinámica
En este capítulo se darán las de�niciones básicas de Programación Dinámica, así
como las características que tiene un problema resuelto con esta técnica para después
aplicarla a los de tipo mochila.
La programación dinámica es utilizada para solucionar problemas de optimización
y está basada en la partición de los últimos en una serie de etapas. Es decir, en una
serie de subproblemas ligados entre sí; éstos son más sencillos de resolver ya que sólo
se requiere de una decisión por lo que al utilizar programación dinámica se podría
decir que se está utilizando un proceso de decisión en multietapas.
Los subproblemas se de�nen de tal manera que la respuesta global está constituida
por una combinación de las decisiones tomadas en cada una de las etapas.
La programación dinámica está basada en la teoría que desarrolló Richard Bell-
man a principios de 1950, la cual incluye el �Principio de Optimalidad�que dice:
�Dado el estado actual del sistema, la decisión óptima para cada una de las
etapas restantes no debe depender de estados previamente alcanzados o de decisiones
previamente tomadas�
63
Es decir, que las decisiones que se toman en cada una de las etapas son indepen-
dientes de las que se hayan tomado en etapas anteriores o de estados previamente
alcanzados.
A un problema de programación dinámica se le asocian dos tipos de variables: de
estado y de decisión.
� Variables de estado: Son la liga entre las etapas y se podría decir que son
una medida de las condiciones que existen al empezar alguna etapa.
� Variables de decisión: Son las variables que involucran las alternativas que
son posibles en cada una de las etapas del problema de optimización.
3.1 Elementos de un problema de programación
dinámica
En un problema de programación dinámica se observan cuatro elementos: etapas,
alternativas, estados del sistema y ecuaciones recursivas.
� Etapa es un subproblema del problema de optimización, en el cual se debe de
tomar una decisión.
� Alternativas son las variables de decisión de cada etapa, las cuales in�uyen
en la función de rendimiento de la misma.
� Estados del sistema son la liga o la relación que existe entre las etapas.
El estado del sistema debe contener toda la información necesaria para poder
tomar una decisión factible en la etapa actual. Cabe señalar que la de�nición
de estado deberá permitir que se tome una decisión factible para la etapa actual
sin necesidad de comprobar las decisiones realizadas en etapas anteriores.
64
� Ecuaciones recursivas contienen toda la información del rendimiento acu-
mulado durante las etapas anteriores, de tal manera que la ecuación recursiva
de la etapa i contiene toda la información necesaria para tomar una decisión en
la etapa i+1, por lo que en la última etapa se tiene el rendimiento óptimo total
(o viceversa: la ecuación de la etapa i contiene toda la información necesaria
para tomar una decisión