T E S I S: Programaci On Entera: El Problema de Localizaci On de Plantas

Universidad Nacional Autónoma de México
Facultad de Ciencias
Programación entera: El problema de

localización de plantas
T E S I S
QUE PARA OBTENER EL TÍTULO DE:
ACTUARIO
PRESENTA:
MAURICIO LECANDA BRICEÑO
DIRECTOR DE TESIS:
DR. RICARDO STRAUSZ SANTIAGO
2013
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.
i
1. Datos del alumno

Lecanda
Briceño
Mauricio
55 66 16 01
Universidad Nacional Autónoma de México
Facultad de Ciencias
302035195
2. Datos del tutor

Dr
Ricardo
Strausz
Santiago
3. Datos del Sinodal 1

Act
Germán
Valle
Trujillo

Act
Mauricio
Aguilar
González

M en C
Jesús Agustı́n
Cano
Garcés

M en I
Marı́a Isabel
Escalante
Membrillo
7. Datos del trabajo escrito

Programación Entera: Problema de localización de plantas
71 p
2013
Índice general
Agradecimientos VII
Introducción IX
1. Programación Lineal 1
1.1. Antecedentes Históricos . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Modelo de Programación Lineal . . . . . . . . . . . . . . . . . . . 2
1.3. Región de Soluciones Factibles . . . . . . . . . . . . . . . . . . . 5
1.3.1. Convexidad . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2. Puntos Extremos . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.3. Variables Básicas y no Básicas . . . . . . . . . . . . . . . 8
1.3.4. Variables básicas y puntos extremos . . . . . . . . . . . . 9
1.4. Método Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.1. Coeficientes de costo reducido . . . . . . . . . . . . . . . . 11
1.4.2. Criterios de optimalidad y de selección . . . . . . . . . . . 12
1.5. Dualidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
iii
iv ÍNDICE GENERAL
1.5.1. Relación entre los problemas primal y dual . . . . . . . . 15
2. Programación Entera 17
2.2. Programación Entera Lineal . . . . . . . . . . . . . . . . . . . . . 18
2.2.1. Modelo de Programación Entera Lineal . . . . . . . . . . 18
2.3. Técnica Branch & Bound . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1. Algoritmo de Dakin (Branch and Bound) . . . . . . . . . 19
2.3.2. Descripción del algoritmo . . . . . . . . . . . . . . . . . . 21
3. Compl. Alg. en la Prog. Entera 29
3.1. Definiciones Básicas . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.1. Tipos de Algoritmos . . . . . . . . . . . . . . . . . . . . . 29
3.1.2. Problemas de decisión . . . . . . . . . . . . . . . . . . . . 31
3.1.3. Tipos de problemas . . . . . . . . . . . . . . . . . . . . . 31
3.2. Ejemplos de problemas NP-Completos . . . . . . . . . . . . . . . 32
3.3. Problema de la mı́nima cubierta por conjuntos . . . . . . . . . . 34
3.4. Tiempos de ejecución . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.1. Algoritmo Merge-Sort . . . . . . . . . . . . . . . . . . . . 36
4. Problema de ubicación de plantas 39
4.2. Definición del problema . . . . . . . . . . . . . . . . . . . . . . . 40

ÍNDICE GENERAL v
4.3. Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.4. Algoritmos de aproximación . . . . . . . . . . . . . . . . . . . . . 44
4.4.1. Descripción del algoritmo de Jain-Vazirani . . . . . . . . . 45
4.4.2. Descripción del algoritmo de Ajuste Dual . . . . . . . . . 50
4.5. ¿Qué tanto se puede mejorar? . . . . . . . . . . . . . . . . . . . . 53
Conclusiones 61
Bibliografı́a 63
Agradecimientos
Esta tesis se la dedico con mucho amor a mis padres Mauricio Lecanda Terán
y Patricia Elizabeth Briceño Duarte por haberme apoyado a lo largo de toda
mi vida en los buenos y en los malos momentos, otorgándome dı́a a dı́a su gran
sabidurı́a y su excelente educación y de quienes estoy muy orgulloso de ser su
hijo, a mi hermano David Lecanda Briceño con el que compartı́ tantas cosas
maravillosas en la niñez y en la adolescencia y que siempre hemos estado juntos
para apoyarnos y a mi flaco Jorge Alberto Romero Mendoza que es el amor de
mi vida, que me salvó del abismo y que ha estado conmigo durante todo este
tiempo ayudándome con sus ánimos, su paciencia y su gran amor.
Agradezco a mis abuelitos Raúl, Fede, Yola y Pera que con amor crearon a
las mejores familias en la que pude nacer, a todos mis tı́os, tı́as y primos Lecanda
y Briseño que tanto quiero y de quienes he recibido ayuda y consejos en todo
momento y finalmente a mi suegra Betty Mendoza que me adoptó como un hijo
más y que gracias a ella ahora con gran honor formo parte también de la familia
Mendoza.
A mis queridos amigos Agustı́n, Daniel, Ángel, Zaira, Adriana y Hany con
los que pasé los mejores años de mi carrera y que ahora se han convertido en
mis hermanos.
Finalmente, quiero agradecer a mi asesor Ricardo Strausz Santiago, o mejor

conocido como Dino que me ayudó enormemente durante casi 3 años a terminar
mi tesis y a mis sinodales Germán Valle Trujillo, Agustı́n Cano Garcés, Mauricio
Aguilar González y Marı́a Isabel Escalante Membrillo que con sus conocimientos
y observaciones me ayudaron a enriquecer el contenido de la tesis.
vii
Introducción
Optimizar es un tema que siempre está presente en la vida cotidiana, y es

más necesario cuando se ve involucrado el dinero. Todos hemos escuchado de
alguien que quiere minimizar gastos o maximizar ingresos y utilidades.
Este texto introduce al lector en el interesante mundo de la optimización, defi-

niendo modelos y variables y mostrando los métodos existentes para optimizar,
también enseña las dificultades encontradas cuando el problema que se quiere
resolver obliga a utilizar variables enteras, tal es el caso del tema de la tesis Pro-
blema de Localización de Plantas, el cual busca la mejor manera de distribuir
plantas para satisfacer la demanda de los clientes y al mismo tiempo minimizar
los gastos generados.
El término planta se refiere a cualquier lugar que genere un producto, como

por ejemplo una fábrica, o una agencia automovilı́stica o bien también puede
tratarse de un almacén o centro de distribución que en vez de generar un bien
ofrece un servicio.
El cliente es cualquier persona, empresa o incluso una población que requiera

del servicio que la planta ofrece y que está dispuesto a pagar por ello.
Los gastos generados por construir cualquier planta en cierta zona geográfica y
por atender a cualquier cliente son los que se buscan reducir al mı́nimo sin dejar
de satisfacer la demanda.
El objetivo de la tesis es mostrar una de las técnicas que encuentran una solución
rápida del problema de localización de plantas aunque se incurra en un error,
práctica que se hace comúnmente cuando se utilizan variables enteras en el
modelo, pues hay ocasiones en las que el número de variables es tan grande
que encontrar la mejor solución se complica en cuanto al tiempo requerido para
resolver el problema.
ix
x INTRODUCCIÓN
En la primera parte de la tesis se incluye una base teórica de la programación

lineal, la programación entera y la complejidad algorı́tmica. El problema central
se define y se resuelve en la segunda parte de la tesis y es aquı́ donde con la
ayuda de un ejemplo práctico se aprecia la sencillez del algoritmo.
Capı́tulo 1
Programación Lineal
El modelo de programación lineal (LP) por sus siglas en inglés, es uno de los más
importantes en la investigación de operaciones y en las ciencias de la adminis-
tración. Muchas situaciones cotidianas que busquen obtener una mejorı́a pueden
ser resueltas o aproximadas por el LP; incluso en la programación entera, el LP
es usado como subrutina.
1.1. Antecedentes Históricos
Los modelos matemáticos se usan desde siempre para resolver problemas y expli-
car fenómenos naturales. En particular la programación matemática surgió alre-
dedor del siglo XVIII como una herramienta para modelar problemas en donde
se debı́a optimizar cierta función continua f (x) con x ∈ Rn . Los programas ma-
temáticos más primitivos fueron utilizados por el economista Quesnay alrededor
del año 1759. [32]
La investigación de operaciones, surgió con la revolución industrial y con la

segunda Guerra Mundial, entre 1939 y 1945, cuando Gran Bretaña reunió a va-
rios cientı́ficos de la época para idear estrategias de guerra con las que pudieran
optimizar los recursos disponibles.
Tras finalizar la guerra, Gran Bretaña y Estados Unidos, inspirados en los

excelentes resultados obtenidos en la milicia, empezaron a aplicar la investiga-
ción de operaciones también en los ámbitos industrial, laboral y gubernamental.
Para 1951 ya se habı́a introducido por completo en Gran Bretaña y estaba por
1
2 CAPÍTULO 1. PROGRAMACIÓN LINEAL
hacerlo en Estados Unidos.[30]
Al paso de los años, la investigación de operaciones fue evolucionando hasta

convertirse en lo que es hoy en dı́a: una de las disciplinas con más aplicaciones
en el mundo real y sus herramientas se desarrollaron, en su mayorı́a, entre las
décadas de 1950 y 1960; algunas de ellas son: la programación lineal (Dantzig
1947 [7]), la programación dinámica (Bellman 1953[27]), la programación no li-
neal (Kuhn y Tucker 1951 [20]), la programación entera (Gomory 1958 [12]),
las redes de optimización (Ford y Fulckerson 1956 [9]), la teorı́a de colas (Er-
lang 1909 [24]), la teorı́a de inventarios (Arrow, Karlin, Scarf 1962 [29]) y la
simulación (Montecarlo 1944 [33]).
1.2. Modelo de Programación Lineal
Un problema de programación lineal se puede definir como optimizar cierta

función lineal sujeta a un conjunto de restricciones (funciones afines) las cuales
pueden ser desigualdades o ecuaciones.
Dentro de un modelo de optimización se distinguen 3 partes: las variables,

las restricciones y la función objetivo, los cuales se detallan a continuación
Variables
En un modelo de programación lineal se asume que algunas variables son

no controlables, como la distancia entre dos lugares, el clima, la demanda, etc,
mientras que otras son controlables, por ejemplo: decidir la ruta a tomar para
viajar de un lado a otro, la época de siembra, el número de productos a fabricar,
etc. Las controlables reciben el nombre de variables de decisión, mientras que
las no controlables son valores estimados y dependiendo de qué tan realista se
requiera el modelo, pueden o no formar parte de él.
Ejemplo
Supóngase que se quiere viajar de la ciudad X a la Z; la distancia d, medida

en kilómetros, que existe entre X y Z es un ejemplo de variable no controlable
pues no se tiene ningún control sobre ella.
Sin embargo, existen i rutas diferentes entre ambas ciudades, unas más largas
que otras, lo que sugiere que la decisión es si conviene elegir la ruta i o no y esto
aplica para cada ruta, por lo tanto las variables de decisión son las siguientes:
1.2. MODELO DE PROGRAMACIÓN LINEAL 3
(
1 entonces se elige la ruta i
Si xi =
0 entonces no se elige la ruta i
Los valores que toman las variables de decisión varı́an dependiendo del pro-
blema, en este caso cada variable puede tomar solo dos valores (1 ó 0) pero en
otras situaciones, puede tomar valores enteros o racionales.
Función Objetivo
La función objetivo es una función lineal que depende de las variables de

decisión y que se utiliza para medir el beneficio obtenido de la decisión tomada.
Siguiendo con el mismo ejemplo, la gasolina que se gastarı́a a lo largo de la ruta
i tiene un costo ci .
El costo también es un ejemplo de variable no controlable y además sirve

para definir la función objetivo:
f (x) :D⊂R→R
f (x) = cx
en la cual x = (x1 , x2 , . . . , xn )t ∈ Rn es el vector columna de variables de

decisión, c = (c1 , c2 , . . . , cn ) ∈ Rn es el vector de costos o utilidades y D es
el dominio en el cual se puede optimizar y es conocido también como región
factible.
Restricciones
El dominio D o también llamado conjunto factible está constituido por las

restricciones del problema, las cuales limitan el rango de valores que pueden
tomar x.
En el ejemplo, la única restricción serı́a la siguiente:
X
xi = 1
i
ya que con esto se asegura que se debe elegir una y sólo una ruta para resolver
el problema.
También existen restricciones sobre el signo de x y sobre el conjunto de

valores permitidos (en el ejemplo x pertenece a un conjunto cuyos únicos valores
son 0 y 1).
xi ∈ {0, 1} para todo i
De forma general se representan mediante funciones lineales de la forma:
n
X
Ri (x) = aij xj ≤ bi
j=1
donde i y j son los ı́ndices que numeran a las restricciones y a las variables
respectivamente. Cabe aclarar que el signo ≤ puede ser reemplazado por el
signo ≥ o por el signo =.
La intersección de todas ellas, define al conjunto D. El vector columna b =

(b1 , b2 , . . . , bm )t ∈ Rm , es llamado vector de recursos.
Los coeficientes aij forman una matriz de la forma:
 
a11 a12 ... a1n
 a21 a22 ... a2n 
 
A= . .. .. .. 
 .. . . . 
am1 am2 ... amn
y con ella se puede definir el modelo de programación lineal:
maximizar f (x)=c1 x1 +c2 x2 + . . .+cn xn

sujeto a a11 x1 +a12 x2 + . . .+a1n xn ≤b1
..
. (1.1)
am1 x1 +am2 x2 + . . .+amn xn ≤bm
x1 x2 . . . xn ≥0
1.3. REGIÓN DE SOLUCIONES FACTIBLES 5
o bien en forma matricial
maximizar f (x) = cx
sujeto a Ax ≤ b
x ≥ 0
el cual se dice que está en forma canónica; también existe la forma estándar en
el que la única diferencia es que el término Ax ≤ b es reemplazado por Ax = b.
Con esto, se puede definir el modelo para el ejemplo que se utilizó anterior-
mente:
minimizar f (x)=c1 x1 +c2 x2 + . . .+cn xn

sujeto a x1 + x2 + . . .+ xn =1
x1 x2 . . . xn ∈{0, 1}
1.3. Región de Soluciones Factibles
Para resolver un modelo lineal, es necesario conocer las propiedades básicas de

D; para ello, se definirán algunos términos.
Se llamará solución factible a cualquier vector x ∈ Rn que cumpla con todas

las restricciones, o dicho de otro modo, es factible si x ∈ D.
El conjunto:
D = {x ∈ Rn |Ax ≤ b, x ≥ 0}
se llama región de soluciones factibles o conjunto factible para LP (cuando

está en forma canónica).
1.3.1. Convexidad
Sean x1 , x2 , . . . , xm un conjunto de puntos en Rn , la combinación lineal convexa

de estos puntos se define como:
m
X m
X
λk xk con λk = 1 y λk ≥ 0 para k = 1, . . . , m
k=1 k=1
Las dos propiedades más importantes de D son la convexidad y la existencia

de puntos extremos.
Un conjunto H 6= ∅ es convexo si cumple lo siguiente: Para cualesquiera dos

puntos x, y ∈ H, toda combinación lineal convexa de x y y, está totalmente
contenida en H; es decir, λx + (1 − λ)y ∈ H con 0 ≤ λ ≤ 1.
Se demostrará ahora que la región factible D es un conjunto convexo:
Teorema 1.1. Sea D = {x ∈ Rn |Ax ≤ b, x ≥ 0} el conjunto factible de

cualquier problema lineal, entonces D es un conjunto convexo.
Demostración: Sean x, y ∈ D.
Para que λx + (1 − λ)y esté contenida en D, deben cumplirse dos cosas:
A(λx + (1 − λ)y) ≤ b y λx + (1 − λ)y ≥ 0
Notemos que en el caso de que el conjunto D solo tenga un punto, entonces

la combinación lineal convexa de x y y también está en D, pues en este caso
x = y y λx + (1 − λ)y = x ∈ D. Por lo tanto nos enfocaremos al caso en que D
contenga al menos dos puntos diferentes.
Primero se probará que λx + (1 − λ)y ≥ 0:
Como x, y ∈ D , entonces x ≥ 0 y y ≥ 0, y considerando que 0 ≤ λ ≤ 1 entonces

ambos miembros de la suma son no negativos y por lo tanto la suma también
lo es.
Ahora se demostrará que A(λx + (1 − λ)y) ≤ b:

Se tiene que
A(λx + (1 − λ)y) = λAx + (1 − λ)(Ay) ≤ λb + (1 − λ)b = b
Por lo tanto queda demostrado que para cualesquiera 2 puntos de D, sus com-
binaciones lineales convexas también están en D, por lo que D es un conjunto
convexo.
1.3.2. Puntos Extremos
Los puntos extremos de un conjunto D se definen como aquellos que no

pueden ser expresados como una combinación lineal convexa de cualesquiera
otros dos puntos distintos pertenecientes al conjunto.
f (x) = 2x f (x) = 2x
(a) (b)
b
Máximo
x x
b
Óptimo no acotado Puntos Extremos
Figura 1.1: (a) D = R, (b) D = [−1, 1]
Para ver la utilidad de los puntos extremos véanse los incisos (a) y (b) de
la figura (1.1). En ambos incisos se intenta maximizar la función f (x) = 2x,
la diferencia es que en (a), D = R el cual no tiene puntos extremos y en (b),
D = [−1, 1] cuyos puntos extremos son -1 y 1.
Con esto se intuye que el óptimo de cualquier función lineal probablemente

se encuentre en alguno de los puntos extremos de D, es por esto que son tan
importantes en la teorı́a de la programación lineal.
1.3.3. Variables Básicas y no Básicas
Se trabajará con la forma estándar del LP.
maximizar f (x) = cx
sujeto a Ax = b
x ≥ 0
La matriz A tiene m renglones y n columnas, eso quiere decir que hay m

restricciones y n variables, se asumirá que m ≤ n.
Supóngase que todos los renglones de A son linealmente independientes,

entonces tomando m columnas linealmente independientes de A se obtiene B,
una submatriz de A de m × m a la que se llamará matriz base. Las n − m
columnas restantes de A forman a N, otra submatriz de A de (n − m) × m.
La siguiente expresión se utilizará para separar la matriz A en B y N su-

poniendo sin pérdida de generalidad, que las primeras m columnas de A son
linealmente independientes
A = (B, N)
La misma expresión se usará para separar el vector de costos c y el vector

de variables x.
x = (xB , xN )
c = (cB , cN )
donde B es el conjunto de ı́ndices correspondientes a las columnas de B y N es

el conjunto de ı́ndices correspondientes a las columnas de N.
Sustituyendo estas nuevas matrices en el modelo, éste queda de la siguiente

forma:
maximizar f (x) = cB xB + c N xN
sujeto a BxB + NxN = b (1.2)

xB xN ≥ 0
Por lo tanto, la factibilidad está en función de las variables básicas y no

básicas.
Una solución será básica factible si xN =0 y xB ≥ 0. La matriz B asociada

se llama base factible.
En el modelo (1.2) comúnmente se escribe z en lugar de f (x)
1.3.4. Variables básicas y puntos extremos
A continuación se tiene un ejemplo para visualizar todo lo anterior.
maximizar f (x)=3 x1 +4x2

sujeto a 2 x1 + x2 ≤6
2 x1 +3x2 ≤9
x1 , x2 ≥0
En la figura (1.2) se puede ver la región factible del problema anterior de

dos variables y dos restricciones, en él se distinguen algunos puntos, los cuales
corresponden a las intersecciones de las rectas y corresponden a las soluciones
básicas factibles y para identificarlas es necesario estandarizar el problema, esto
se hace añadiendo variables de holgura, las cuales no tienen ningún costo para
la función objetivo sirven para que una desigualdad se vuelva igualdad:
maximizar f (x)=3 x1 +4x2

sujeto a 2 x1 + x2 +x3 =6
2 x1 +3x2 +x4 =9
x1 , x2 , x3 , x4 ,≥0
x2
r2
D
b b x1
r1
Figura 1.2: Representación gráfica y región factible del problema
La matrices A y b son por tanto:

2 1 1 0 6
A= = a1 a2 a3 a4 b=
2 3 0 1 9
La base asociada de cualquier solución como por ejemplo (x1 , x2 , x3 , x4 ) =

(3, 0, 0, 3), se pude encontrar identificando las variables básicas y no básicas,
las cuales en el ejemplo son fáciles de localizar pues como sólo hay dos restric-
ciones entonces sólo hay dos básicas x1 = 3 y x4 = 3 que por definición no
pueden ser no básicas. Por lo tanto, la base B consta de las columnas a1 y a4
de A:

2 0 −1 1/2 0
B= = a1 a4 B =
2 1 −1 1
Haciendo el mismo análisis para todas las soluciones básicas de la región, se

pueden obtener sus bases asociadas:

1 0 2 0
xB1 = (0, 0, 6, 9) B1 = xB2 = (3, 0, 0, 3) B2 =
0 1 2 1
1.4. MÉTODO SIMPLEX 11

1 1 9 3 2 1
xB3 = (0, 3, 3, 0) B3 = xB4 = ( , , 0, 0) B4 =
3 0 4 2 2 3

1 0 9 2 1
xB5 = (0, 6, 0, −9) B5 = xB6 = ( , 0, −3, 0) B6 =
3 1 2 2 0
Como se puede ver, B5 y B6 son bases no factibles, pues sus respectivas solu-
ciones tienen elementos negativos.
1.4. Método Simplex
Ya se conocen todas la propiedades de la región factible, ahora sólo falta

encontrar el óptimo. La función f (x) = 3x1 + 4x2 encuentra su valor máximo
en algún punto extremo factible o solución básica factible, el cual en este caso
es xB4 = (x1 , x2 , x3 , x4 ) = ( 94 , 23 , 0, 0) con un valor en la función objetivo de
f (xB4 ) = 12.75.
La técnica para resolver cualquier problema lineal fue desarrollada por Geor-
ge B. Dantzig y se llama método simplex [7].
1.4.1. Coeficientes de costo reducido
El método simplex trabaja siempre con la forma estándar del problema y en

cada iteración calcula una nueva solución básica factible basada en los criterios
de optimalidad.
Recuérdese que en términos de variables básicas, el problema se ve de la

forma:
maximizar z = c B xB + c N xN
sujeto a xB = B−1 b − B−1 NxN (1.3)

xB , xN ≥ 0
Si se sutituye a xB en z, se obtiene la expresión:
z = cB (B−1 b − B−1 NxN ) + cN xN
Distribuyendo términos y factorizando:
z = cB B−1 b − (cB B−1 N − cN )xN (1.4)
Cuando se está en una solución básica factible, el valor de la función objetivo

es z = cB B−1 b pues xN = 0 y para fines prácticos, al término cB B−1 b se le
llamará z0 .
Sin embargo, el coeficiente de xN en (1.4), sirve de indicador para ver si la

solución actual es óptima.
Recordando que aj es la columna j de la matriz A entonces se puede hacer

lo siguiente:
X X X
(cB B−1 N−cN )xN = (cB B−1 aj − cj )xj = (cB yj − cj )xj = (zj − cj )xj
j∈N j∈N j∈N
Sustituyendo, se tendrı́a:
X
z = z0 − (zj − cj )xj
j∈N
El coeficiente zj − cj de la variable no básica xj es llamado coeficiente de

costo reducido e indica si la solución actual es la óptima, según el criterio de
optimalidad.
1.4.2. Criterios de optimalidad y de selección
CRITERIO DE OPTIMALIDAD
1.4. MÉTODO SIMPLEX 13
Si el problema es de minimización, se tendrá la solución óptima cuando

zj − cj ≤ 0 ∀j ∈ N .
Si el problema es de maximización: se obtendrá la solución óptima cuando

zj − cj ≥ 0 ∀j ∈ N .
CRITERIOS DE SELECCIÓN
Si la solución actual no cumple con el criterio de optimalidad, lo que se hace

es sustituir una de las variables básicas por una no básica, creando ası́ una nueva
solución básica y garantizando a la vez la factibilidad por medio de algunos
criterios de selección.
Selección de la variable no básica (caso de minimización)
Como primer paso, se selecciona la variable no básica cuyo coeficiente de

costo reducido zj − cj sea el mayor (positivo). Cabe aclarar que éste es sólo un
criterio y no garantiza que sea la forma más rápida de encontrar el óptimo.
Selección de la variable básica (caso de minimización)
Luego se debe seleccionar la variable básica que dejará de serlo, para esto se
define al vector b como sigue:
 
b1
 b2 
B−1 b = b =  . 
 
 .. 
bm
Supóngase, sin pérdida de generalidad, que las primeras m variables son

básicas y que xj con j > m es la candidata a ser básica; entonces se tiene:
B−1 N = [ym+1 , ym+2 , . . . , yj , . . . , yn ] j∈N
con
yj = (y1j , y2j , . . . , yij , . . . , ymj )t i∈B
la columna yj (relacionada con la variable xj ) es llamada columna pivote y de

ella se selecciona un elemento llamado pivote por medio de la siguiente expresión:

bk bi
= mı́n | con yij > 0
ykj 1≤i≤m yij
el pivote ykj indica que la variable básica que debe salir de la base es xk .
Una vez que se tenga la nueva base, se recalcula todo y el proceso se repite
hasta que se obtenga la solución óptima, o bien se concluya que la solución es
no acotada.
Si el problema a resolver tiene restricciones del tipo ≤ ó ≥, entonces se deben

convertir en igualdades, lo cual se logra sumándoles o restándoles la cantidad
necesaria para que se cumpla la igualdad. A dichas cantidades se les llama
variables de holgura.
Con base a todo lo anterior, el algoritmo es:
Algoritmo Simplex
Entrada : Una matriz A ∈ Rm×n , dos vectores columna c ∈ Rn y b ∈ Rm

y un conjunto de soluciones factibles D = {x ∈ Rn |Ax ≤ b, x ≥ 0}.
Salida : Una solución básica factible x tal que cx = máx{cx|x ∈ D} o bien

concluir que la solución es no acotada.
① Estandarizar el problema añadiendo variables de holgura.

Seleccionar un punto extremo factible x ∈ D
② Calcular B, N, B, N y los coeficientes de costo reducido asociados a x.
③ Si la solución actual cumple el criterio de optimalidad entonces regresar x
Terminar.
④ Seleccionar el ı́ndice j ∈ N de la variable no básica que es candidata a ser
básica según el criterio de selección.
Calcular el vector yj = B−1 aj
Si yj ≤ 0 entonces la solución es no acotada
Terminar.
⑤ Calcular el cociente mı́nimo según el criterio de selección.
Seleccionar el ı́ndice k ∈ B de la variable básica que dejará de ser básica.
⑥ Hacer N = N \{j} ∪ {k} y B = B\{k} ∪ {j}.
Ir al paso 2
1.5. DUALIDAD 15
1.5. Dualidad
Todos los problemas de optimización, llamados también primales, tienen

asociado un problema equivalente llamado dual el cual tiene muchas aplicaciones
dentro de la programación lineal.
La teorı́a de la dualidad fue desarrollada por el matemático John Von Neu-

mann en 1947, mismo año en el que Dantzig desarrollaba el algoritmo simplex.
[7]
Von Neumann propuso que el dual del problema primal:
maximizar z = cx
sujeto a Ax ≤ b
x ≥ 0
es el siguiente
minimizar ν = bt y
sujeto a yA ≥ c
y ≤ 0
1.5.1. Relación entre los problemas primal y dual
Existen varias relaciones entre un problema primal y el dual asociado:
El número de restricciones del primal es igual al número de variables del

dual.
El número de variables del primal es igual al número de restricciones del

dual.
El dual del dual es el problema primal.

Sea x∗ y y∗ las soluciones óptimas del primal y del dual respectivamente,

entonces las funciones objetivo de ambos problemas son iguales, es decir
z∗ = ν ∗.
Si el problema primal (dual) es no acotado, entonces el dual (primal) es

no factible.
Hay ocasiones en las que el dual es más fácil de resolver que el primal, por
esta razón se necesita saber una manera de encontrar el problema dual a partir
de un primal dado, lo cual se logra con la siguiente tabla:
Primal Dual
minimizar maximizar
≤ ≤0
Restricciones ≥ ≥0 Variables
= s.r.s.
≥0 ≤
Variables ≤0 ≥ Restricciones
s.r.s. =
Capı́tulo 2
Programación Entera
La programación entera o IP por sus siglas en inglés, surgió alrededor del año
1958 por la necesidad de resolver problemas de optimización en los que la so-
lución, además de cumplir con todas las restricciones, debe ser entera para al
menos una de sus variables.
Algunos de los eventos más relevantes que desarrollaron a la programación

entera, se citan a continuación:
1958 [12]: El matemático Ralph E. Gomory publica un artı́culo en el que se

habla por primera vez del método de planos de corte para resolver problemas
enteros.
1960 [21]: Land y Doig describen otro de los métodos más importantes de la
IP, el llamado método de ramificación y acotamiento.
17
18 CAPÍTULO 2. PROGRAMACIÓN ENTERA
2.2. Programación Entera Lineal
2.2.1. Modelo de Programación Entera Lineal
El algoritmo simplex funciona para resolver prácticamente cualquier LP, sin

embargo otros más interesantes se modelan usando la IP y el motivo por el que
no se puede usar el algoritmo simplex es que el conjunto de soluciones factibles
de cualquier IP es no convexo.
Existen diferentes clases de IP’s:
Problema entero puro. Cuando todas las variables son enteras.

Problema entero mixto. Cuando al menos una variable es entera y existe
otra que no lo es.
Problema entero lineal. Cuando todas las restricciones y la función obje-
tivo son lineales.
Problema entero no lineal. Cuando al menos una restricción es no lineal.
El modelo IP de la clase entero puro en su forma general es el siguiente:
minimizar z = cx
sujeto a
Ax ≤ b
x≥ 0
x ∈ Zn
El conjunto de soluciones factibles para IP se denotará por F :
F = {x ∈ Rn |Ax ≤ b, x ≥ 0, x ∈ Z n }
2.3. Técnica Branch & Bound
Las técnicas más famosas que existen para resolver IP’s se clasifican en dos
tipos: planos de corte o cutting plane y ramificación y acotamiento o branch and
2.3. TÉCNICA BRANCH & BOUND 19
bound. A continuación se explica brevemente uno de los algoritmos, basados en

ramificación y acotamiento, más representativos.
2.3.1. Algoritmo de Dakin (Branch and Bound)
El primer algoritmo de ramificación y acotamiento fue introducido en 1960

por Land y Doig [21], el cual consiste principalmente en dividir el problema
original en n subproblemas y resolverlos usando el algoritmo simplex. Una vez
resueltos, a todos aquellos cuya solución no fue entera se les aplica el mismo
proceso. Las soluciones óptimas enteras se conservan y al final se elije la mejor
de todas.
Posteriormente Dakin [6] propuso otro algoritmo de ramificación en el que

cada problema estudiado se divide solo en 2 subproblemas en cada iteración,
disminuyendo ası́ el número de problemas por analizar.
Para fines prácticos, el problema original se llamará P0 y su región factible

será F0 = F .
El primer paso en este algoritmo es relajar la integralidad (integralidad sig-

nifica que las variables son enteras) de P0 para volverlo un LP que se llamará P0′ .
La región factible de P0′ es D0 , con F0 ⊆ D0 , donde:
D0 = {x|Ax ≤ b, x ≥ 0}
P0′ se resuelve usando simplex. Si la solución óptima x0 cumple con la res-

tricción de integralidad, entonces x0 también es solución para P0 . Si no es ası́,
P0 debe ser separado en dos subproblemas (P1 y P2 ) de tal forma que x0 sea no
factible en ambos.
Supóngase que la j-ésima variable de x0 no es entera, entonces:
xj0 = [xj0 ] + fj con 0 < fj < 1
para lograr que x0 sea no factible para P1 y P2 entonces sus regiones factibles
son:
F1 = F ∩ {x|xj0 ≤ [xj0 ]}
F2 = F ∩ {x|xj0 ≥ [xj0 ] + 1}
el proceso anterior es lo que se conoce como ramificación y una vez concluido,

se procede a analizar a P1 y P2 de la misma manera que se hizo con P0 , y
este proceso se repite hasta que todos los subproblemas den como resultado una
solución óptima entero-factible.
Sin embargo, existen cotas que indican si conviene o no ramificar un subpro-

blema. Al proceso de calcular tales cotas se le conoce como acotamiento.
Para explicar como funciona el acotamiento, supóngase que el valor óptimo

de la función objetivo de P0′ es z0′ y el de P0 es z0∗ , entonces como F0 ⊆ D0 ,
z0∗ ≤ z0′ para el caso de maximización y z0∗ ≥ z0′ para el caso de minimización.
Para P0 , la cota superior es z0 = z0′ y la cota inferior se puede tomar como

z0 = f (x′ ) para cualquier x′ ∈ F0 .
La cota inferior de P0 sirve como criterio para saber si alguno de sus sub-
problemas debe ser ramificado o no. Por ejemplo, en el caso de maximización
si la cota superior de P1 es menor que la cota inferior de P0 entonces no tiene
sentido seguir ramificando hacia P1 pues jamás se obtendrá una mejor solución,
es entonces cuando P1 se vuelve no prometedor.
Se define a L como la lista de problemas pendientes por analizar. Un pro-

blema deja de pertenecer a L cuando: se ramificó en otros dos, cuando se con-
sideró no prometedor o bien cuando su solución es entero-factible.
Para ayudar a representar la ejecución del algoritmo, se utilizan árboles

en el que la raı́z representa al problema original y los vértices representan los
subproblemas del original, los cuales sólo tienen dos ramas y en cada una de
ellas se encuentra la restricción que se añadió. También se coloca al lado de
cada vértice una etiqueta con las cotas inferior y superior encontradas durante
el acotamiento [z, z].
2.3.2. Descripción del algoritmo
Algoritmo de Dakin
Entrada : Una instancia (F, c) de cualquier problema entero.
Salida : Una solución x∗ ∈ F tal que cx∗ es óptimo.
① Inicializar la cota z = −∞ y hacer L = {P0 }.
② Elegir aleatoriamente un problema Pn de L.

Relajar a Pn y nombrar al problema relajado como Pn′ , resolver Pn′ usando
el algoritmo simplex.
③ Si Pn′ es no factible, entonces: L = L\{Pn }, Ir al paso 5.

En otro caso:
zn = zn∗ , donde zn∗ es el valor objetivo óptimo de Pn′ .
Si la solución óptima de Pn′ es entero-factible entonces
Si zn > z entonces z = zn , etiquetar a la solución óptima x∗n de
Pn′ como solución candidata.
En otro caso L = L\{Pn }, Ir al paso 5.
④ Si zn ≤ z entonces L = L\{Pn }, Ir al paso 5.

En otro caso Seleccionar alguna variable xj que no sea entera de la
solución óptima de Pn′ y construir dos problemas Pk y Pk+1 con regiones
factibles Fk y Fk+1 como sigue:
Fk = Fn ∩ {x|xj ≤ [xj ]}
Fk+1 = Fn ∩ {x|xj ≥ [xj ] + 1}
Hacer L = L\{Pn } ∪ {Pk , Pk+1 }.
⑤ Si L 6= ∅, Ir al paso 2.
En oto caso La solución óptima entero-factible de P0 es x∗n y su valor
objetivo es z.
Para visualizar mejor la ejecución del algoritmo, se resolverá el siguiente

ejemplo:
maximizar 3x1 + 4x2

sujeto a 2x1 + x2 ≤6
2x1 + 3x2 ≤9
x1 x2 ∈ Z+
En las siguientes gráficas la región sombreada representa al conjunto de solu-

ciones factibles Dj del problema lineal Pj′ asociado a Pj , los puntos representan
el conjunto de soluciones enteras factibles Fj y la lı́nea punteada representa una
curva de nivel z = 0 de la función objetivo.
x2
r2
b b
b b
F0 b
b b b b x1
r1
z = 3x1 + 4x2 = 0
Figura 2.1: Región factible del problema
El algoritmo empieza con el único problema que pertenece a L, es decir P0 ,

e inicializando la cota inferior del problema como z = −∞.
En la figura 2.1 se encuentra el problema original, y sus dos regiones factibles

D0 y F0 .
Como siguiente paso, se debe resolver el problema lineal P0′ asociado a P0 ,

la cual puede apreciarse en la figura 2.1 que su solución óptima es x∗0 = ( 94 , 23 )
y su valor objetivo es z0∗ = z0 = 51
4 .
La solución no es entera, sin embargo como z0 > z, se debe ramificar a P0

en P1 y P2 tal como lo muestra la figura 2.2.
51
P0 [−∞, 4
]
x2 ≤ 1 x2 ≥ 2
P1 P2
Figura 2.2: Árbol asociado al primer paso del algoritmo
L se actualiza con los dos nuevos problemas, quedando como L = {P1 , P2 }.

Las regiones factibles de P1 y P2 se muestran en la figura 2.3.
x2
r2
F2
b b r4
b b b r3
F1
b b b b x1
r1
z = 3x1 + 4x2 = 0
Figura 2.3: Región factible de P1 y P2
De la lista L = {P1 , P2 } se elije para ramificar a P2 . Se resuelve su problema

lineal asociado P2′ , cuya solución óptima es x∗2 = ( 23 , 2) con cota superior z2 = 25
2 .
Como la solución no es entera y z2 > z, se procede a ramificar a P2 en

P3 y P4 , tal como lo muestra la figura 2.4. Se actualiza a L, quedando como
L = {P1 , P3 , P4 }
51
P0 [−∞, 4
]
x2 ≤ 1 x2 ≥ 2
25
P1 P2 [−∞, 2
]
x1 ≤ 1 x1 ≥ 2
P3 P4
Figura 2.4: Árbol generado tras ramificar a P2
Las regiones factibles F3 y F4 se encuentran en la figura (2.5) y como se

puede ver, F4 = ∅ y por lo tanto P4 sale de L, la cual queda actualizada como
L = {P1 , P3 }. Se elige arbitrariamente a P3 y se resuelve P3′ .
r2 F4 = ⊘
r5 r6
b
F3
b b r4
x1
r1
x2 z = 3x1 + 4x2 = 0
Figura 2.5: Regiones factibles de P3 y P4
La solución óptima de P3′ es x∗3 = (1, 37 ) y su cota superior es z 3 = z3∗ = 37

3 .
Como no es entera y z 3 > z entonces se ramifica P3 en P5 y P6 . En la figura 2.6
se encuentra el árbol asociado a este paso de algoritmo y las regiones factibles

asociadas son F5 = {(0, 2)(1, 2)} y F6 = {(0, 3)}.
51
P0 [−∞, 4
]
x2 ≤ 1 x2 ≥ 2
25
P1 P2 [−∞, 2
]
x1 ≤ 1 x1 ≥ 2
37
[−∞, 3
] P3 P4 [INFACTIBLE]
x2 ≤ 2 x2 ≥ 3
P5 P6
Figura 2.6: Árbol generado después de ramificar a P3
Por último, de la lista L = {P1 , P5 , P6 }, se elige a P6 ; su solución óptima es

x∗6 = (0, 3) y su valor objetivo es z6 = z6∗ = 12.
La solución x∗6 es entero-factible, por lo que la cota inferior del problema se

actualiza por z = z6 .
Como z1 = 8,5 < z, entonces el problema P1 se vuelve un problema no

prometedor y por consiguiente, la lista queda como L = {P5 }.
La solución óptima de P5′ es x∗5 = (1, 2) y la cota superior es z5 = z5∗ = 11,

sin embargo, también es no prometedor por lo que la lista queda vacı́a L = ∅ y
por tal motivo, la solución óptima es x∗ = (0, 3) con valor objetivo z ∗ = z = 12.
El último árbol asociado al algoritmo, se encuentra en la figura 2.7.
51
P0 [12, 4
]
x2 ≤ 1 x2 ≥ 2
25
[NO PROMETEDOR] P1 P2 [12, 2
]
x1 ≤ 1 x1 ≥ 2
37
[12, 3
] P3 P4 [INFACTIBLE]
x2 ≤ 2 x2 ≥ 3
[NO PROMETEDOR] P5 P6 [12, 12]
Figura 2.7: Árbol final

Capı́tulo 3
Complejidad Algorı́tmica en
la Programación Entera
La complejidad algorı́tmica es una herramienta para analizar algoritmos que

ayuda a calcular su rapidez y eficiencia al momento de usarlos para resolver
algún problema en particular.
Surgió en el año 1972 cuando el matemático Karp [18], basándose en un

artı́culo publicado por Cook en 1971 [5], introdujo las clases de problemas P
y N P y formuló la pregunta ¿P 6= N P ? la cual, hoy en dı́a, sigue sin tener
solución.
3.1. Definiciones Básicas
3.1.1. Tipos de Algoritmos
En cuanto al tiempo de ejecución, existen los algoritmos de tiempo polinomial

y los de tiempo no polinomial.
Algoritmos polinomiales y no polinomiales
En general, mientras más variables existan, mayor es el tiempo que tarda un

algoritmo en resolver el problema. Los algoritmos polinomiales son aquellos en
29
30 CAPÍTULO 3. COMPL. ALG. EN LA PROG. ENTERA
los que el tiempo que consumen al resolver algún problema puede ser acotado
por un polinomio. Por el contrario, los algoritmos no polinomiales carecen de
esa propiedad.
Con respecto a la exactitud, los algoritmos se clasifican en óptimos y apro-

ximados.
Algoritmos óptimos y aproximados
Al tratar de resolver problemas IP, los algoritmos clásicos como el algoritmo

de Dankin, aunque garantizan encontrar la solución óptima, son no polinomiales.
Sin embargo, hay situaciones prácticas en las que se necesita tener una respuesta
rápida aunque la solución no sea necesariamente la mejor.
Se definirá como instancia al conjunto de elementos necesarios para definir

algún problema.
Los algoritmos aproximados se acercan al óptimo de la siguiente forma:
Sea I la instancia de un problema de optimización, y sean OP T (I) la solución

óptima y A(I) la calculada por el algoritmo A entonces:
1
OP T (I) ≤ A(I) ≤ kOP T (I) con k ≥ 1
k
Al número k se le conoce como factor de aproximación pues nos indica que tan
lejos se está del óptimo.
Los algoritmos óptimos son aquellos en los que k = 1.
Algoritmos deterministas y no-deterministas
Hay otra clasificación de algoritmos relevante en la teorı́a de la complejidad,

los no-deterministas en los que en contraposición a los deterministas, se agrega
una fase previa que adivina la solución del problema (el componente que adivina
es llamado oráculo) para luego checar que efectivamente dicha adivinanza es
solución del problema.
3.1. DEFINICIONES BÁSICAS 31
3.1.2. Problemas de decisión
La complejidad algorı́tmica está basada principalmente en los problemas de

decisión, los cuales están formados por una instancia y una pregunta cuya res-
puesta sólo puede ser si o no, por ejemplo:
Factibilidad Entera
Instancia : Una matriz A ∈ Zm×n y un vector b ∈ Zm .
Pregunta : ¿Existe un vector x ∈ Zn tal que Ax ≤ b?.
formalmente se definen ası́:
Definición 3.1. Un problema de decisión P= (X, Y ) es un conjunto de instan-

cias X y un subconjunto Y ⊆ X que son aquellas que regresan si (las llamadas
si-instancias)
3.1.3. Tipos de problemas
Dentro de la complejidad algorı́tmica, también existe una clasificación de

problemas que sirve para identificar su dificultad al momento de resolverlos.
Las clasificaciones más importantes son: P, N P, N P − Completo y N P − Duro.
Clase P
La clase P contiene a todos aquellos problemas de decisión en los que verificar

que alguna instancia del conjunto X pertenece a Y , se puede realizar con un
algoritmo polinomial.
Clase NP
Se dice que un problema de decisión P= (X, Y ) pertenece a la clase N P

cuando se puede verificar que alguna instancia x pertenece a Y en tiempo poli-
nomial usando un algoritmo no-determinista.
Se sabe que P ⊆ N P , pero la pregunta que aún sigue abierta dentro de la

complejidad algorı́tmica es ¿P = N P ?.
Transformaciones de problemas
Sean P1 = (X1 , Y1 ) y P2 = (X2 , Y2 ) dos problemas de decisión. Se dice que

P1 se transforma polinomialmente en P2 si las instancias X1 se transformen en
instancias X2 y las sı́-instancias de P1 se transforman en sı́-instancias de P2 ,
usando un algoritmo polinomial.
Se sigue inmediatamente de la definición que:
Proposición 3.1. Sean dos problemas de decisión P1 y P2 , Si P1 se transforma

polinomialmente en P2 y existe un algoritmo polinomial para P2 , entonces existe
un algoritmo polinomial para P1 . [19]
Clase NP-Completo
Se dice que P ∈ N P pertenece a la clase N P − Completo si todos los

problemas de la clase N P se transforman polinomialmente en P.
La clase N P − Completo es muy importante, pues gracias a la proposición

anterior, si se encuentra que alguno de los problemas de esta clase tiene un
algoritmo polinomial, entonces todos los demás también lo tienen y por lo tanto,
P serı́a igual a N P .
Clase NP-Duro
Por otro lado, P pertenece a N P −Duro si todos los problemas de la clase N P

se transforman polinomialmente en P aunque P no necesariamente pertenezca
a NP.
La forma más fácil de demostrar que un problema de optimización pertene-

ce a la clase N P − Duro es encontrando su problema de decisión asociado y
demostrar que éste pertenece a la clase N P − Completo. [25]
3.2. Ejemplos de problemas NP-Completos
Gracias al matemático Cook [5], el primer problema que se demostró que per-
tenece a la clase N P − Completo es el de satisfacibilidad, el cual consta de un
número de variables binarias en las que 1 significa verdadero y 0 significa falso
y un conjunto de clausulas que son la unión da varias variables. Un ejemplo de
tres variables serı́a:
3.2. EJEMPLOS DE PROBLEMAS NP-COMPLETOS 33
C = {x1 ∨ x2 ∨ x3 }
Para que C sea válida es necesario que al menos una de las xi con i = 1, 2, 3
sea verdadera. Una familia Z de clausulas es la intersección de todas ellas:
Z = C1 ∧ C2 ∧ . . . ∧ Cn
una asignación de verdad es una función T tal que T (x) = verdadero si x = 1

y viceversa. Se define como x al complemento de x y x = 1 si y solo si x = 0.
Si existe una asignación de verdad que satisfaga todas las clausulas al mismo
tiempo entonces el problema es satisfacible.
Posterior al trabajo de Cook, el matemático Richard Karp utilizó el hecho

de que el problema de satisfacibilidad pertenecı́a a la clase N P − Completo
para demostrar que otros 21 problemas de decisión pertenecı́an a la misma clase
[18], entre los cuales destacan: el problema del clan, el del conjunto estable o
conjunto independiente y el de la cubierta por vértices.
Sea G = (V (G), E(G)) una gráfica en donde V (G) es el conjunto de vértices

y E(G) es el conjunto de aristas. Se define clan, estable y cubierta de vértices
como sigue:
Clan: Es un subconjunto X ⊆ V (G) tal que para cualesquiera dos elemen-

tos v, w ∈ X existe una arista que los conecta.
Estable: Al contrario del clan, es un subconjunto Y ⊆ V (G) tal que ningún
y ∈ Y está conectado.
Cubierta por vértices: es un conjunto S ⊆ V (G) tales que cada arista de
G tiene como extremo al menos un vértice de S.
Los últimos tres problemas son fáciles de relacionar gracias a la siguiente

proposición:
Proposición 3.2. Sea G una gráfica y X ⊆ V (G). Entonces los siguientes 3
enunciados son equivalentes [19]:
1. X es una cubierta por vértices en G.

2. V (G)\X es un conjunto estable de G.
3. V (G)\X es un clan en el complemento de G.
Problema del Clan
Instancia : Una gráfica G y un entero k.
Pregunta : ¿Existe un clan de cardinalidad k en G?.
Problema del Conjunto Estable
Pregunta : ¿Existe en G un conjunto estable de k vértices?.
Problema de la cubierta por vértices

Pregunta : ¿Existe una cubierta por vértices de cardinalidad k en G?.
El siguiente resultado se debe a Karp [18] pero los detalles de la demostración

se omitieron por no ser relevantes para la tesis.
Teorema 3.1. El problema del clan, el problema de la cobierta por vértices y
el problema del conjunto estable son problemas que pertenecen a la clase N P −
Completo [18]
3.3. Problema de la mı́nima cubierta por con-

juntos
Un problema importante que pertenece a la clase N P − Duro es el de la

cubierta por conjuntos con cardinalidad mı́nima o mejor conocido como el pro-
blema de la mı́nima cubierta por conjuntos.
Problema de la mı́nima cubierta por conjuntos

S
Instancia : Un sistema (U,S) tal que S∈S S = U .
S : Encontrar una cubierta con cardinalidad mı́nima R ⊆ S tal que

Objetivo
R∈R R = U .
3.4. TIEMPOS DE EJECUCIÓN 35
Suponiendo que para toda x ∈ U , |{S ∈ S : x ∈ S}| = 2 entonces éste se

transforma en el de la mı́nima cubierta por vértices en la siguiente forma:
Dada una gráfica G de una instancia de la mı́nima cubierta por vértices,

la instancia equivalente de la mı́nima cubierta por conjuntos se define como
U := E(G) y S = {δ(v) : v ∈ V (G)} para todo v ∈ V (G), donde δ(v) es el
conjunto de todos los vértices adyacentes a v.
Por el teorema 3.1, se sabe que el problema de la cubierta por vértices

pertenece a la clase N P − Completo, por lo tanto el de la mı́nima cubierta por
vértices pertenece a la clase N P − Duro y a su vez también el de la mı́nima
cubierta por conjuntos.
3.4. Tiempos de ejecución
Conocer la clasificación de los problemas en cuanto a su complejidad (P , N P ,

N P − Completo ó N P − Duro) es importante, sin embargo resulta útil conocer
el tiempo que utilizan en ejecutarse.
Se dice que cada vez que en el código de un algoritmo, se asigne un valor

a una variable, se comparen dos variables, se realicen operaciones aritméticas
básicas (suma, resta, multiplicación, división, raı́z cuadrada) o se ejecute una
condición (si-entonces) se utiliza una unidad de tiempo.
Para medir el tiempo de ejecución, se debe estimar el número de veces que

se ejecutarán cada uno de los pasos del algoritmo hasta obtener el resultado,
basándose en la unidad de medida definida anteriormente.
Aunque no se puede saber con exactitud el número de veces que se ejecu-

tará algún paso del algoritmo, existen enfoques como el pesimista que siempre
supone que se está en el peor caso o el optimista que supone lo contrario, y
esto ayuda a estimar el tiempo empleado por un algoritmo. El enfoque que se
utilizará es el pesimista, ya que es el que más se aplica en la realidad.
Sea A un algoritmo y n el número de variables del problema a resolver con

A, se utiliza la notación O(f (n)) para decir que el algoritmo se ejecuta en un
tiempo del orden de la función f (n). Se dice que el algoritmo se ejecuta en
tiempo constante cuando f (n) = 1.
A continuación unos ejemplos para explicar lo anterior:

Sea T (A(n)) el tiempo de ejecución de A.
1. T (A(n)) = 3n + 5, entonces su tiempo es del orden O(n).
2. T (A(n)) = 5, entonces su tiempo es del orden O(1).
3. T (A(n)) = n log2 (n) + 4n + 3, entonces es del orden O(n log2 (n)).
A continuación se muestra una tabla de tiempos de ejecución para instancias

de diferentes tamaños y algoritmos polinomiales y no polinomiales
Tamaño de n
Tiempos 10 20 30 40 50 60
O(n) 0.00001 0.00002 0.00003 0.00004 0.00005 0.00006
segs segs segs segs segs segs
O(n2 ) 0.0001 0.0004 0.0009 0.0016 0.0025 0.0036
O(n3 ) 0.001 0.008 0.027 0.064 0.125 0.216
O(n5 ) 0.1 3.2 24.3 1.7 5.2 13.0
segs segs segs mins mins mins
O(2n ) 0.001 1.0 seg 17.9 12.7 35.7 366.0
segs mins dı́as años siglos
O(3n ) 0.059 58.0 6.5 3855 2 ∗ 108 N/D
segs mins años siglos siglos
3.4.1. Algoritmo Merge-Sort
Uno de los problemas más importantes y con muchas aplicaciones es encontrar

el mejor método para ordenar una lista finita de números.
Aunque existen muchos algoritmos para resolverlo, existe uno que tiene un
tiempo de ejecución eficiente, el cual recibe el nombre de Algoritmo Merge-Sort.
A continuación se describirá el algoritmo y se demostrará que tiene un tiempo

de ejecución del orden O(n log2 (n)) donde n es el total de números de la lista.
3.4. TIEMPOS DE EJECUCIÓN 37
Algoritmo Merge-Sort
Entrada : Una lista a1 , . . . , an de números reales.
Salida : Una permutación π : {1, . . . , n} → {1, . . . , n} tal que para todo

i = 1, . . . , n, aπ(i) ≤ aπ(i+1) .
① Si n = 1 entonces, π(1) := 1 y detener (regresar π).

n
② Definir m := 2 .
ρ:=Merge-Sort(a1 , . . . , am ).
σ:=Merge-Sort(am+1 , . . . , an ).
③ Hacer k := 1, l = 1.
Mientras k ≤ m y l ≤ n − m, Hacer:
Si aρ(k) ≤ am+σ(1) entonces π(k + l − 1) := ρ(k) y k := k + 1
en otro caso π(k + l − 1) := m + σ(l) y l = l + 1.
Mientras k ≤ m hacer: π(k + l − 1) := ρ(k) y k := k + 1.
Mientras l ≤ n − m hacer: π(k + l − 1) := m + σ(l) y l := l + 1.
Teorema 3.2. El algoritmo Merge-Sort se ejecuta en un tiempo del orden

O(n log n).
Demostración. Se denota por T (n) al tiempo de ejecución que se necesita para

resolver instancias que constan de n números.
n n
n Obsérvese que T (1) = 1 y que nT (n) = T ( 2 ) + T( n 2 ) + 3n + 6, donde
2 es el entero menor o igual que 2 y por el contrario 2 es el mayor o igual
que n2 . (El término 3n + 6 depende de que tan exacto se quiera medir el tiempo,
pero para efectos prácticos no es importante).
Se propone ahora que T (n) ≤ 12n log n + 1. Como es fácil demostrarlo para
n = 1, se procederá vı́a inducción.
Para n ≥ 2, se asume que la desigualdad es verdadera para 1, . . . , n − 1, por

lo tanto:
jnk lnm
2 2
T (n) ≤ 12 n + 1 + 12
log log n + 1 + 3n + 6
2 3 2 3
= 12n(log n + 1 − log 3) + 3n + 8
13
≤ 12n log n − n + 3n + 8 ≤ 12n log n + 1
2
37
pues log 3 ≥ 24 .
Capı́tulo 4
Problema de ubicación de
plantas
Existen situaciones en donde las empresas deben de decidir en que lugar cons-
truir sus centros de servicio para satisfacer la demanda eficientemente. Algu-
nos ejemplos pueden ser: fábricas, bodegas, depósitos, centros de distribución,
centros de atención al cliente, o también pueden ser librerı́as, supermercados,
estaciones de bomberos, hospitales, escuelas, etc. Tales situaciones se pueden
resolver matemáticamente mediante un modelo de ubicación de plantas.
El problema de ubicación de plantas ha sido un tema interesante para los

investigadores desde los años 1960’s; ha sido estudiado desde la perspectiva del
peor caso, desde el punto de vista probabilı́stico, el combinatorio y el heurı́stico
(ver [11] y [26]).
A lo largo de todos estos años se han desarrollado diferentes algoritmos

de aproximación para resolver el problema. El primero de todos lo propuso la
investigadora Dorit S. Hochbaum [14] aproximadamente por los años 80’s para
resolver el caso general no métrico, el cual tenı́a un factor de aproximación de
O(log(n)).
El primer algoritmo con factor de aproximación constante para este problema

lo propusieron Shmoys, Tardos y Aardal en 1997 [8], ellos resolvieron el problema
con un factor de aproximación de 4, el cual posteriormente fue mejorado a 1.736
39
40 CAPÍTULO 4. PROBLEMA DE UBICACIÓN DE PLANTAS
por Chudak y Shmoys [4]y 1.582 por Svirindeko [15].
Recientemente el problema de localización de plantas se ha podido aplicar

también a problemas de diseño de redes para servidores, caches e información
digital. [1, 2, 13, 22]
4.2. Definición del problema
Problema de ubicación de plantas sin lı́mite de capacidad

(PUPsC)
Instancia : Un conjunto finito de ciudades denotado por D, un con-

junto finito de zonas denotado por F, un costo fijo fi ∈ R+ por
construir una planta en la zona i ∈ F y un costo de servicio
cij ∈ R+ por servir a la ciudad j ∈ D con una planta ubicada en
la zona i ∈ F.
Objetivo : Encontrar un subconjunto X ⊆ F de zonas en las que se

abrirán plantas y una asignación σ : D → X de ciudades con
plantas abiertas, tal que la suma de los costos de las plantas más
los costos de servicio
X X
fi + cσ(j)j
i∈X j∈D
sea mı́nima.
Comúnmente, los costos de servicio están estimados en proporción a las

distancias geométricas que existen entre las zonas donde se construirá una planta
y los clientes, por lo que si se seleccionan al azar 2 zonas i, i′ ∈ F y dos clientes
j, j ′ ∈ D se forma una figura de 4 lados (que representan las distancias entre las
zonas y los clientes) en la que siempre se cumple que la suma de 3 de sus lados
es mayor que el cuarto lado. Por esta razón, si los costos de servicio están en
proporción a las distancias geométricas de los clientes y las zonas, entonces se
cumple la siguiente restricción:
cij + ci′ j + ci′ j ′ ≥ cij ′ para todas i, i′ ∈ F y j, j ′ ∈ D (4.1)
Si esto se cumple, se dice que el problema de ubicación de plantas es métrico.

4.2. DEFINICIÓN DEL PROBLEMA 41
El problema métrico de ubicación de plantas pertenece a la clase N P −Duro

como se demuestra en el siguiente:
Teorema 4.1. El problema métrico de ubicación de plantas sin lı́mite de ca-
pacidad (PUPsC métrico) es un problema N P − Duro.
Demostración. Se demostrará que el problema de la mı́nima cubierta por con-

juntos, el cual pertenece a la clase N P − Duro, se transforma polinomialmente
en el PUPsC.
Sea (U, S) cualquier instancia del problema de cubierta por conjuntos de

peso mı́nimo, en particular y sin pérdida de generalidad, con pesos unitarios.
El conjunto U es el universo que se debe cubrir por un subconjunto R de

conjuntos de S.
Claramente D = U puesto que el objetivo del problema de la cubierta por

conjuntos es crear, a partir de S, una familia finita de conjuntos que cubra
en su totalidad al conjunto U y en el PUPsC métrico el objetivo es cubrir
la demanda de los clientes D con un conjunto finito de plantas ubicadas en el
conjunto de zonas F; de aquı́ mismo se ve que S = F pues ambos conjuntos
cumplen con la misma función. También los conjuntos X y R son equivalentes.
Los costos de ambos problemas, se comparan de la siguiente manera: para

todo S ∈ S,
fS = c(S) = 1
(
1 para j ∈ S
cSj = (4.2)
3 para j ∈ U \S
El costo cSj es igual a 3 para no violar la desigualdad 4.1, sin embargo puede
ser reemplazado por cualquier número entre 1 y 3.
Por último, los óptimos de ambos problemas deben coincidir y en el caso del
PUPsC métrico es:
X X
fi + cσ(j)j
i∈X j∈D
la primera suma es fácil de analizar pues si recordamos que fi = 1 para todo

i ∈ F entonces:
k
X z }| {
fi = 1 + 1 + . . . + 1 = k en donde k = |X|
i∈X
Por el término (4.1), cij = 1 para todos los clientes asignados, por lo tanto,
la suma total del costo del problema PUPsC métrico es |X| + |D|, el cual es
óptimo si |R| = |X|, pues |R| es el valor óptimo del problema de la mı́nima
cubierta de conjuntos con pesos unitarios.
4.3. Modelo
Como en cualquier problema de programación matemática, se necesitan identi-

ficar cuales son las variables de decisión, las restricciones y la función objetivo
del PUPsC.
Variables de decisión
En este problema hay dos tipos de decisiones, la primera es decidir en que zona
construir la planta y la otra es decidir que ciudades se atenderán con que plantas.
Por tal motivo, existen dos tipos de variables de decisión que se definen de
la siguiente manera:
(
1 entonces la ciudad j se asigna a la planta ubicada en la zona i
Si xij =
0 entonces j no se asigna a la planta en i
(
1 entonces se construye una planta en la zona i
Si yi =
0 entonces no se construye ninguna planta en i
para todo i ∈ F y para todo j ∈ D

4.3. MODELO 43
Restricciones
El primer tipo de restricciones viene en la definición del problema, pues a cada

ciudad se le asigna sólo una planta para satisfacer su demanda:
X
xij = 1 para todo j ∈ D
i∈F
El segundo tipo de restricción tiene que ver más con un aspecto lógico, ya
que no se puede asignar una ciudad a una planta que no se construirá, por tanto
se deben incluir |F||D| restricciones del siguiente tipo:
xij ≤ yi para todo i ∈ F, j ∈ D
El último tipo de restricciones, tiene que ver con los valores que pueden
tomar las variables:
xij ∈{0, 1} para todo i ∈ F, j ∈ D
yi ∈{0, 1} para todo i ∈ F
Función Objetivo
Tal cual lo muestra la definición, el objetivo del problema es minimizar los costos
totales de servicio y de construcción, por lo que la función objetivo serı́a:
XX X
minimizar z = cij xij + fi yi
i∈F j∈D i∈F
El modelo queda entonces ası́:
XX X
minimizar cij xij + fi yi
i∈F j∈D i∈F
sujeto a
X
i∈F
xij , yi ∈ {0, 1} para todo i ∈ F, j ∈ D
Una de las técnicas usadas para resolver cualquier problema entero, es relajar
la restricción de integralidad para que se vuelva lineal y ası́ obtener información
valiosa sobre el problema, por ejemplo una cota superior para el óptimo.
Después de relajar, el modelo queda ası́:
XX X
minimizar cij xij + fi yi
i∈F j∈D i∈F
sujeto a
X
i∈F
xij , yi ≥ 0 para todo i ∈ F, j ∈ D
El problema dual asociado, es el siguiente:
X
maximizar νj
j∈D
sujeto a
νj − wij ≤ cij para todo i ∈ F, j ∈ D
X
wij ≤ fi para todo i ∈ F
j∈D
wij ≥ 0 para todo i ∈ F, j ∈ D
La variable νj con j ∈ D se interpreta como el presupuesto de la ciudad j y

la variable wij con i ∈ F, j ∈ D representa la aportación que hace la ciudad j
para que se abra una planta en la zona i.
4.4. Algoritmos de aproximación
Aunque los algoritmos propuestos por Shmoys, Tardos, Chudak, Aardal y

Svirindeko alcanzaron un factor de aproximación de 1.582, son considerados
poco eficientes debido al excesivo uso de la programación lineal.
4.4. ALGORITMOS DE APROXIMACIÓN 45
Por otro lado, en el año 2001 [16], Jain y Vazirani propusieron un nuevo
algoritmo con un factor de aproximación de 3 y un tiempo de ejecución de
O(m log2 (m)). El algoritmo de Jain y Vazirani, de ahora en adelante nombrado
JV, calcula la solución primal y la dual al mismo tiempo.
4.4.1. Descripción del algoritmo de Jain-Vazirani
Se definen los siguientes conjuntos:
Y : que consta de todas las zonas que aún no están tentativamente selec-
cionadas para abrir un planta en ellas.
V : que contiene a todas aquellas zonas que sı́ están tentativamente selec-
cionadas.
U : formado por todas las ciudades que aún no han sido conectadas o
asignadas a ninguna planta.
nótese también que la variable wij puede verse como que es mayor o igual que
máx{0, νj − cij }, para todo i ∈ F, j ∈ D.
El algoritmo consiste principalmente en incrementar de manera constante

el valor de las variables duales (que inicialmente valen cero). La variable νj
y sus correspondientes variables wij se congelan cuando la ciudad j ∈ D es
tentativamente asignada a alguna planta, lo cual ocurre en alguna de las dos
situaciones:
1. νj = cij para i ∈ V y j ∈ U .
P
2. j∈D wij = fi para i ∈ Y
Si se cumple la primera, entonces σ(j) = i y se congela νj , y si se cumple la

otra entonces Y = Y \{i} y V = V ∪ {i} y para todos los ciudades j ∈ U que
cumplan con que νj ≥ cij se hace σ(j) := i y se congela νj .
Ahora sea E el conjunto de todas las parejas {i, i′ } con i 6= i′ e i, i′ ∈ V ,

tales que existe algún j con σ(j) ∈ V con wij > 0 y wi′ j > 0. Se escoge el
conjunto estable maximal X de la gráfica formada por los conjuntos V, E y por
último, se abren todas las plantas que pertenecen a X y a todas las ciudades
que no están asignadas a ninguna planta de X (σ(j) ∈ / X) se asignan a algún
vecino abierto de σ(j) en (V, E).
Algoritmo de Jain-Vazirani
Entrada : Una instancia (D, F, (fi )i∈F , (cij )i∈F ,j∈D ) del PUPsC.
Salida : Una solución X ⊆ F y σ : D → X.
① Inicializar X = ∅, U = D y Y = F.
② Definir t1 = mı́n{cij |i ∈ V, j ∈ U }.
Definir t2 = mı́n{τ |∃i ∈ Y |ω(i, τ ) = fi } donde
P P
ω(i, τ ) = j∈U máx{0, τ − cij } + j∈D\U máx{0, νj − cij } = fi .
Definir t = mı́n{t1 , t2 }
③ Para i ∈ Y con ω(i, t) = fi Hacer:

Y = Y \{i}
Si hay un i′ ∈ X y j ∈ D\U con νj > cij y νj > ci′ j
Entonces ϕ(i) = i′
En otro caso ϕ(i) = i y X = X ∪ {i}
Para j ∈ U con cij ≤ t Hacer:
σ(j) = ϕ(i), νj = t y U = U \{j}
④ Para i ∈ V , j ∈ U con cij = t Hacer:

σ(j) = ϕ(i), νj = t y U = U \{j}
⑤ Si U 6= ∅ entonces ir al paso 2.
Teorema 4.2. Para instancias métricas I, el algoritmo de JV resuelve el

problema con un factor de aproximación de 3 y puede ejecutarse para correr en
un tiempo de O(m log2 (m)), donde m = |F||D|.
Demostración: Para empezar, el algoritmo entrega una solución factible, por lo

tanto:
X
νj ≤ OP T (I)
j∈D
.
Por otro lado, los costos de servicio y de apertura de las plantas se definen
de la siguiente manera:
X X
cF (X) := fi y cS (X) := cσ(j)j
i∈X j∈D
.
Se demostrará entonces que:
cF (X) + cS (X) ≤ 3OP T (I)

,
o dicho de otra manera
X X
fi + cσ(j)j ≤ 3OP T (I) (4.3)
i∈X j∈D
Para cada zona i, todas las ciudades j con wij > 0, están conectadas a la
planta
Pconstruida en i, o dicho de otro modo, σ(j) = i, además se tiene que
fi = j∈D wij .
Entonces, la primera suma de la ecuación (4.3) queda:
X XX XX
fi = wij ≤ 3 wij
i∈X i∈X j∈D i∈X j∈D
Para la segunda suma de (4.3), se propone que el costo de servicio para cada
cliente j es a lo más 3(νj − wσ(j)j ), es decir:
X X X X
cσ(j)j ≤ 3(νj − wσ(j)j ) = 3 νj − 3 wσ(j)j
j∈D j∈D j∈D j∈D
Para demostrarlo, se analizarán dos casos. Si cσ(j)j = νj − wσ(j)j , es trivial.

Por otro lado, cσ(j)j > νj y wσ(j)j = 0, lo que significa que ϕ(i) 6= i cuando
j se conectó a ϕ(i) en el paso 3 o 4 del algoritmo, entonces hay una zona
i ∈ F\(Y ∪ X) que no tiene plantas con cij ≤ νj y un cliente j ′ con wij ′ > 0 y
wσ(j)j ′ > 0, y por lo tanto cij ′ = νj ′ − wij ′ < νj ′ y cσ(j)j ′ = νj ′ − wσ(j)j ′ < νj ′ .
Nótese que νj ′ ≤ νj , pues j ′ se conectó a σ(j) antes que j. Se concluye que:
cσ(j)j ≤ cσ(j)j ′ + cij ′ + cij < νj ′ + νj ′ + νj ≤ 3νj = 3(νj − wσ(j)j )
Sumando ahora los dos costos, de servicio y de apretura de plantas, se tiene:
X X
cF (X) + cS (X) = fi + cσ(j)j
i∈X j∈D
XX X
≤3 wij +3 (νj − wσ(j)j )
i∈X j∈D j∈D
X X
=3 wij +νj − wσ(j)j
j∈D i∈X
P
Luego, i∈X wij = wσ(j)j , puesto que wij = 0 siempre que el cliente j no
esté asignado a la planta construida en i (es decir i 6= σ(j)), por lo que se sigue
que:
X X X
3 wij + νj − wσ(j)j =3 wσ(j)j + νj − wσ(j)j
j∈D i∈X j∈D
X
=3 νj
j∈D
≤ 3OP T (I)
Para medir el tiempo de ejecución del algoritmo, se analizará por separado

cada uno de los pasos del algoritmo.
① Como se puede ver en el algoritmo, en este paso sólo se le asignan valor a

3 variables, lo cual se ejecuta en tiempo constante al que llamaremos c1 ,
por lo que el tiempo total del paso 1 es T1 = c1 .
② Este paso se compone de tres partes, en las cuales se calcula el valor de

t1 , t2 y t respectivamente:
t1 = mı́n{cij |i ∈ V, j ∈ U }, y la manera más rápida para calcularlo es

simplemente hacer a lo más m = |F||D| comparaciones para conser-
var en cada paso el valor más chico. Sin embargo por conveniencia,
se ordenan primero a las c′ij s de menor a mayor con el algoritmo

Merge-Sort, lo cual lleva un tiempo de ejecución de O(m log2 m), y
como encontrar el valor mı́nimo en un conjunto ordenado es constan-
te, entonces el tiempo total para calcular t1 es O(m log2 m).
t2 = mı́n{τ |∃i ∈ Y |ω(i, τ ) = fi }, sin embargo viéndolo de la siguiente
forma es más fácil calcularlo:

ti2
t2 = mı́n |i ∈ Y
|Ui |
en donde:
Ui = {j ∈ U |cij ≤ t}
X X
ti2 = fi + (cij − νj ) + cij
j∈D \U :νj >cij j∈U i
Una vez calculados, ti2 y Ui se mantienen igual en cada iteración,

lo que nos indica que t2 se mantiene igual hasta que alguno de sus
componentes cambie y esto sucede cuando algún cliente es conectado
o cuando t = cij para algún j ∈ U . Como esto se hace a lo más
para cada i ∈ Y y j ∈ U , entonces actualizar los valores de t2 , ti2 y
|Ui | lleva un tiempo de O(m). Sólo hay que notar que para que esto
sea posible, hay que cambiar la definición de t1 en el paso 2 como:
t1 = mı́n {cij |i ∈ Y, j ∈ U }.
Calcular el valor de t lleva tiempo constante.
El tiempo total de ejecución del paso 2 es por lo tanto:
T2 = O(m log2 (m))

.
③ El paso 3 se ejecuta sólo si t2 = t y la condición si-entonces se ejecuta en

O(|D|) ya que i′ ∈ X, j ∈ D\U y νj > ci′ j implica que σ(j) = i′ . Por lo
tanto el tiempo de ejecución del paso 4 es: T4 = O(|D|).
④ El paso 4 sólo se ejecuta si t1 = t por lo que su tiempo de ejecución es

constante T3 = c3 .
⑤ Finalmente, el paso 5 se ejecuta en tiempo constante:

T5 = O(1).
El tiempo estimado de ejecución del algoritmo es entonces:
T1 + T2 + T3 + T4 + T5 = O(m log2 (m))
4.4.2. Descripción del algoritmo de Ajuste Dual
En el año 2003, Jain, Mahdain, Markakais, Sabery y Vazirani [17] propusie-

ron un mejor algoritmo en cuanto al tiempo de ejecución, al cual se llamará al-
goritmo de Ajuste-Dual.
El algoritmo de Ajuste-Dual es prácticamente el mismo algoritmo JV pero

en este caso las aportaciones de las ciudades a las plantas difieren un poco del
algoritmo JV :
Si la ciudad j está asignada a alguna planta ubicada en la zona i′ , entonces

ofrecerá como aportación para la apertura de una planta en i (cerrada) lo
que se ahorrarı́a por cambiar de planta (máx{0, ci′ j − cij }).
Por el contrario, si la ciudad aún no ha sido asignada entonces aporta lo

mismo que en el algoritmo JV (máx{0, νj − cij }).
Inicialmente todas las ciudades están no asignadas (U = D) y todas las

plantas están cerradas (X = ∅) y el tiempo t y todas las variables duales valen
cero.
Luego mientras que U 6= ∅ se incrementa el valor νj para todo j ∈ U y el

valor de t al mismo tiempo y en la misma proporción; es decir, νj = t para todo
j ∈ U hasta que alguno de los siguiente eventos ocurra:
1. νj = cij para alguna j ∈ U y alguna i ∈ X. Si esto ocurre, se asigna j a i

y se congela el valor de νj .
2. La suma de las aportaciones de las ciudades asignadas y no asignadas para

alguna planta en i ∈ F cerrada es igual a su costo de apertura. Si esto
sucede se abre la planta en i y todas las ciudades asignadas y no asignadas
que tengan una aportación no negativa a esa planta son asignadas a ella.
Formalmente el algoritmo queda ası́:
Algoritmo de Ajuste-Dual
Entrada : Una instancia (D, F , (fi )i∈F , (cij )i∈F ,j∈D ) del PUPsC.
Salida : Una solución X ⊆ F y σ : D → X.
① Inicializar X = ∅, U = D.
② Definir t1 = mı́n{cij |i ∈ X, j ∈ U }.
Definir t2 = mı́n{τ |∃i ∈ F\X|ω(i, τ ) = fi } donde
P P
ω(i, τ ) = j∈U máx{0, τ − cij } + j∈D\U máx{0, cσ(j)j − cij } = fi .
Definir t = mı́n{t1 , t2 }
③ Para i ∈ F\X con ω(i, t) = fi Hacer:

X = X ∪ {i}.
Para j ∈ D\U con cij < cσ(j)j Hacer: σ(j) = i.
Para j ∈ U con cij < t Hacer: σ(j) := i.
④ Para i ∈ X, j ∈ U con cij ≤ t Hacer:

σ(j) = i, νj = t y U = U \{j}.
⑤ Si U 6= ∅ entonces ir al paso 2.
Teorema 4.3. El algoritmo de arriba calcula una solución dual y una solución
factible primal y puede ejecutarse en un tiempo de O(|F|2 |D|) [19]
Para entender como funciona el algoritmo se resolverá con él un ejemplo

numérico que consta de 4 zonas para construir plantas y 7 clientes que atender.
La matriz C de costos de asignación es la siguiente:
 
2 2 1 5
2,5 6 5,5 8
 
4 3,5 10 4
 
8
C= 3 7 3
4 7 3 2
 
5,5 5 5 9
7 1 4 4
y los costos de apertura de cada zona son:

F = 30 25 18 35
El primer paso del algoritmo es hacer t = 0, X = ∅ y D = U , luego como lo

indica el procedimiento, se necesita calcular el valor de t y para esto se necesitan
calcular, t1 y t2 :
t1 = mı́n{cij |i ∈ X, j ∈ U }
en este caso se asume que t1 = ∞ pues X = ∅.
Por otro lado, para t2 :
t2 = mı́n{τ |∃i ∈ F\X|ω(i, τ ) = fi }
donde
X X
ω(i, τ ) = máx{0, τ − cij } + máx{0, cσ(j)j − cij } = fi
j∈U j∈D \U
Al contrario de t1 , como X = ∅ entonces se tiene que encontrar al valor de

τ necesario para abrir una planta en cada una de las 4 zonas de F.
Para la zona 1, τ = 607 , para la segunda zona τ =7.5, en la tercera τ =7.25

y para la cuarta, τ =10. El valor mı́nimo de τ es 7.25, lo cual quiere decir que
t2 =7.25 y por lo tanto t = t2 .
El paso 3 del algoritmo indica que hay que abrir una planta en la zona 3, es
decir X = X ∪{3}. Además todos los clientes j ∈ U que hicieron una aportación
a la apertura de la planta 3 son asignados a ella, es decir todos aquellos clientes
tales que c3j < t.
Como se puede ver en la matriz de costos C, todos los costos de la columna

3 son menores a 7.25 a excepción de c33 = 10, por lo tanto:
4.5. ¿QUÉ TANTO SE PUEDE MEJORAR? 53
σ(j) = 3 para j ∈ {1, 2, 4, 5, 6, 7}
El paso 4 indica que νj = t =7.25 para j ∈ {1, 2, 4, 5, 6, 7} y que U =

U \{1, 2, 3, 4, 6, 7}.
Como lo indica el paso 5, U 6= ∅ por lo que se regresa al paso 2.
De nuevo en el paso 2, t1 = c33 = 10 y t2 es el mı́nimo valor de τ necesario

para abrir una planta en las zonas 1, 2 y 4.
Para la zona 1, τ = 29, para la zona 2, τ =21.5 y para la 3, τ = 34, por lo

que t2 =21.5 y por último t = mı́n{t1 , t2 } = 10.
El paso 3 no aplica y al paso 4 indica que σ(3) = 3, ν3 = 10 y U = U \{3}.
Como U = ∅ entonces el algoritmo concluye con que se debe abrir la planta

en la zona 3 y que todos los clientes deben ser asignados a ella.
La solución primal es entonces:
x31 = x32 = x33 = x34 = x35 = x36 = x37 = 1

y3 = 1
y todas las demás variables valen 0, la cual tiene un valor en la función objetivo
de:
c31 + c32 + c33 + c34 + c35 + c36 + c37 + f3 = 53,5
4.5. ¿Qué tanto se puede mejorar?
El algoritmo de Ajuste-Dual entrega una solución dual que por lo regular

no es factible, esto se debe a que al abrir una planta se dejan de considerar las
aportaciones de las ciudades a esa planta, lo que puede ocasionar que al final se
sobrepase el valor de apertura de la planta.
ν
Sin embargo en el año 2003, Jain et al, encontraron que el vector ( γj , j ∈ D)
resulta ser una solución dual factible y además demostraron que el número γ es
el factor de aproximación del algoritmo de Ajuste-Dual [17].
Para encontrar el valor de γ, se utilizará la siguiente definición:

Definición 4.1. Dado νj con j ∈ (1, . . . |D|), una planta en la zona i es llamada
a lo más limitada por γ si y sólo si:
X
máx{νj /γ − cij , 0} ≤ fi (4.4)
j
Usando la definición anterior, es fácil ver que la solución es factible si y sólo si

todas las plantas son a lo más limitadas por γ. Nótese que en la suma (4.4) sólo
se necesitan ciudades tales que νj /γ − cij > 0.
Gráficamente, una estrella es un conjunto de vértices, en los que existe un vértice

llamado centro tal que todos los demás vértices se conectan a él, pero los demás
vértices no se conectan entre sı́.
Considérese la estrella S que consta de alguna zona F con costo de apertura f ,

y d ciudades que cumplen con que νj /γ − cij > 0. Sea dj el costo de servicio
entre la zona F y la ciudad j, y νj el presupuesto de la ciudad j al final de la
ejecución del algoritmo que sin pérdida de generalidad cumplen con:
ν 1 ≤ ν2 ≤ . . . ≤ νd
.
Se necesitan más variables para poder representar la ejecución del algoritmo.

Para esto, se identificará la situación de cada ciudad k (1 ≤ k ≤ d) antes de ser
asignada por primera vez, es decir, cuando t = νk − ǫ para una ǫ muy pequeña.
Sea j < k para la ciudad j, hay dos situaciones posibles justo antes de que la
ciudad k sea asignada por primera vez:
1. La ciudad j ya estaba asignada a alguna planta con un costo de dj .

2. La ciudad j aún no ha sido asignada a ninguna planta, entonces νj = νk
Con esta información se puede definir una variable que nos indique la situación
de las ciudades 1, 2, . . . , j, . . . , k − 1 al tiempo t = νk − ǫ.
(
dj Si j ya estaba conectada a la planta construida en la zona F ∈ F
rj,k =
νk en otro caso, i.e. si νj = νk
Se describen ahora desigualdades válidas para esas variables. Primero, para

j = 1, . . . , d − 2,
rj,j+1 ≥ rj,j+2 ≥ . . . ≥ rj,d (4.5)
porque el costo de servicio decrece si los ciudades son re-conectados.
Luego en el tiempo t = νk − ǫ, la aportación que la ciudad j otorga para que la

planta se construya en F es igual a:
máx{rj,k − dj , 0} si j < k, y
máx{t − dj , 0} si j ≥ k.
Para obtener una solución factible, entonces se debe cumplir que:
k−1
X d
X
máx{0, rj,k − dj } + máx{0, νk − dj } ≤ f. (4.6)
j=1 l=k
Para que la instancia sea métrica, se considera las siguiente restricción:
rj,k + dj + dk ≥ νk para 1 ≤ j < k ≤ d. (4.7)
Por último, se necesita que:
d
X
νj /γ − dj ≤ f
j=1
Despejando γ se obtiene:
Pd
j=1 νj
γ≥ Pd .
f+ j=1 dj
Con lo anterior se puede generar el siguiente modelo llamado Programa Li-

neal revelador de factores de aproximación:
Pd
j=1 νj
maximizar Pd
f+ j=1 dj
sujeto a
νj ≤ νj+1 (1 ≤ j < d)
rj,k ≥ rj,k+1 (1 ≤ j < k < d)
rj,k + dj + dk ≥ νk (1 ≤ j < k ≤ d)
Pk−1
j=1 máx{0, rj,k − dj }+
d
X
máx{0, νk − dl } ≤ f (1 ≤ k ≤ d)
l=k
d
X
dj > 0
j=1
f≥ 0
ν j , dj ≥ 0 (1 ≤ j ≤ d)
rj,k ≥ 0 (1 ≤ j < k ≤ d)
El modelo puede ser fácilmente modificado para transformarlo en uno lineal,

añadiendo la siguiente restricción:
d
X
f+ dj ≤ 1
j=1
El valor de γ se calcula numéricamente utilizando diversos valores para d.

Jain y Vazirani aproximaron el valor de γ a 1.61.
Sin embargo, también se necesitan encontrar factores de aproximación para

diferentes valores de f y dj . Esto se logra con el siguiente modelo:
Pd
j=1 νj − γF f
maximizar Pd
j=1 dj
sujeto a
νj ≤ νj+1 (1 ≤ j < d)
rj,k ≥ rj,k+1 (1 ≤ j < k < d)
rj,k + dj + dk ≥ νk (1 ≤ j < k ≤ d)
Pk−1
j=1 máx{0, rj,k − dj }+
d
X
máx{0, νk − dl } ≤ f (1 ≤ k ≤ d)
l=k
d
X
dj > 0
j=1
f≥ 0
νj , dj ≥ 0 (1 ≤ j ≤ d)
rj,k ≥ 0 (1 ≤ j < k ≤ d)
El siguiente lema garantiza que la solución óptima del modelo es en realidad

el factor de aproximación del algoritmo Ajuste-Dual.
Lema 4.1. Sea γF ≥ 1 y sea γS el supremo de los valores óptimos del modelo de
arriba para todas las d ∈ N. Sea X ∗ ⊆ F cualquier solución de I una instancia
dada, entonces el costo de la solución generada por el algoritmo Ajuste-Dual en
la instancia I es a lo más γF cF (X ∗ ) + γS cS (X ∗ ) [31].
Utilizando el lema anterior, se encontraron tres valores para γS diferentes

dependiendo del valor de γF , dando lugar al siguiente lema:
Lema 4.2. Consideremos el problema lineal revelador de factores para alguna
d∈N
1. (Vygen 2005 [31]) Para γF = 1, γS = 2

2. (Jain 2003 [17]) Para γF =1.61, γS =1.61
3. (Mahdain, Ye y Zhang [23]) Para γF =1.11, γS =1.78
Mezclando los dos lemas anteriores, se obtiene el siguiente corolario:
Corolario 4.1. Sea (γF , γS ) ∈ {(1,2),(1.61,1.61),(1.11,1.78)}, sea I una ins-

tancia del problema métrico de ubicación de plantas sin lı́mite de capacidad y
sea X ∗ ⊆ F cualquier solución. Entonces el costo producido por el algoritmo de
Ajuste-Dual es a lo más γF cF (X ∗ ) + γS cS (X ∗ )
Ahora se definirán dos técnicas útiles para mejorar el factor de aproximación

de los algoritmos descritos arriba.
GREEDY AUGMENTATION
La técnica GA o Greedy Augmantation de un conjunto de zonas X ∈ F con-

siste en seleccionar iterativamente un elemento i ∈ F maximizando el cociente
gX (i)
fi y luego hacer X = X ∪ {i} hasta que gX (i) ≤ fi para toda i ∈ F. En
donde:
gX (i) = cS (X) − cS (X ∪ {i})
para una solución X ⊆ F y una planta i ∈ F.
SCALING
La técnica S o Scaling consiste en multiplicar todas las plantas i ∈ F por un

valor δ > 0 para luego aplicar el algoritmo en cuestión a la instancia modificada
y después multiplicar los costos por 1δ .
El siguiente lema y teorema servirán para mejorar el factor de aproximación

de los algoritmos mencionados en este capı́tulo.
Lema 4.3. (Charikar y Guha [3]) Sea ∅ 6= X, X ∗ ⊆ F. Aplicar la técnica GA
a X para obtener un conjunto Y ⊇ X. Entonces:
cF (Y )+cS (Y ) ≤

∗ cS (X) − cS (X ∗ )
cF (X) +cF (X ) ln máx 1, + cF (X ∗ ) + cS (X ∗ )
cF (X ∗ )
Teorema 4.4. Supóngase que existen constantes positivas β, γS , γF y un algo-

ritmo A, el cual para cada instancia calcula una solución X tal que:
βcF (X) + cS (X) ≤ γF cF (X ∗ ) + γS (X ∗ )
1
para cada ∅ 6= X ∗ ⊆ F y sea δ ≥ β.
Entonces, aplicar la técnica S con valor δ y luego aplicar la técnica GA al

resultado para obtener una solución con un costo a lo más de:

γF γS − 1
máx + ln (βδ), 1 +
β βδ
veces el óptimo
Usando el corolario 4.1 se puede aplicar el teorema 4.4 al algoritmo Ajuste-

Dual con β = γF = 1, γS = 2 y δ=1.76 obteniendo ası́ una factor de aproxima-
ción de 1.57. El siguiente corolario indica que puede mejorarse aún más:
Corolario 4.2. Si se aplican las técnicas GA y S con δ=1.504, β = 1, γF =1.11

y γS =1.78 al algoritmo Ajuste-Dual entonces el factor de aproximación es de
1.52 [23]
El factor de aproximación 1.52, es el mejor conocido hasta la fecha para el

problema métrico de ubicación de plantas sin lı́mite de capacidad, sin embargo
es interesante saber qué tanto se puede disminuir este factor.
Sea α la solución de la ecuación α + 1 = ln( α2 ), entonces α ≈ 0,46305, si

restringimos a que los costos de servicio estén en el intervalo [1,3] entonces los
siguientes teoremas sugieren que el problema PUPsC tiene un algoritmo con
factor de aproximación de 1 + α.
Teorema 4.5. Consideremos el problema PUPsC (no métrico) restringido a

costos de servicio en el intervalo [1,3] entonces el problema tiene un algoritmo
con factor de aproximación 1 + α + ǫ con 0 < ǫ < 1 [19]
Teorema 4.6. Si existe algún ǫ > 0 y un algoritmo de aproximación con factor

de 1 + α − ǫ para el PUPsC métrico entonces P=NP [31]
Conclusiones
El problema de localización de plantas, pertenece a la clase NP-Duro, lo

que quiere decir que si se requiere una solución exacta, los algoritmos existentes
tardarı́an mucho tiempo para instancias grandes, por lo que si se aplica a una
situación real la decisión debe ser tomada con mayor rapidez.
Para solucionar esta problemática, se cuenta con el algoritmo de ajuste dual

que tiene un margen de error de 1.52 y que además es el mejor conocido a la
fecha.
La pregunta es, ¿tiene sentido seguir investigando para encontrar un mejor

algoritmo?, la respuesta es sı́, ya que si en algún momento se encuentra uno
con un factor de aproximación menor a 1.49 entonces P = N P lo que incluso
implicarı́a que existe un algoritmo óptimo de tiempo polinomial para todos los
problemas N P − Duros.
61
Bibliografı́a
[1] M. Andrews and L. Zang. The access network design problem. In Procee-
dings of the 39th Annual IEEE Symposium on Foundations of Computer
Science, 1998.
[2] G. Italiano Deng X B. Li, M. Golin and K. Soharby. On the optimal place-
ment of web proxies in the internet. In Proceedings of IEEE INFOCOM’99,
págs 1282-1290, 1999.
[3] M. Charikar and S. Guha. Improved combinatorial algorithms for the faci-
lity location and k-median problems. SIAM Journal on Computing vol. 34,
págs 803-824, 2005.
[4] F.A. Chudak and D.B. Shmoys. Improved approximation algorithms for the
uncapacited facility location problem. SIAM Journal on Computing vol. 33,
págs 1-25, 2003.
[5] S.A. Cook. The complexity of theorem proving procedures. Proceedings

of the 3rd Annual ACM Symposium on the theory of Computing. págs
151-158, 1971.
[6] R.J. Dakin. A tree-search algorithm for mixed integer programming pro-
blems. Mathematical and Phisical Sciences, Computer Journal, Volume 8,
1965.
[7] G.B. Dantzig. Linear Programming and Extensions. Princeton University

Press, 1963.
[8] É. Tardos D.B. Shmoys and K. Aardal. On Approximation algorithms for
facility location problems. In Proceedings of the 29th annual ACM Sympo-
sium in theory of Computing, 1997, págs 265-274.
[9] L.R. Ford and Fulkerson D.R. Maximal flow though a network. Canadian
Journal of Mathematics 8, 1956.
[10] Robert S. Garfinkel. Integer Programming. Wiley-Interscience, 1972.
63
64 BIBLIOGRAFÍA
[11] Nemhauser G.L. and L.A. Wolsey. Integer and Combinatorial Optimization.
John Wiley and Sons Inc., 1990.
[12] R Gomory. An Algorithm for Integer Solutions to Lineal Programming.

Princeton IBM Mathematical Research Report, 1958.
[13] S. Guha and S. Khuller. Greedy strikes back: Improved facility locations
algorithms. Journal of algorithms vol. 31, págs 228-248, 1999.
[14] D.S. Houchbaum. Heuristics for the fixed cost median problem. Mathema-
tical Programming 22, págs 148-162, 1982.
[15] M. Svirindeko. On An improved approximation algorithm for the metric

uncapacited facility location problem. In Proceedings of 9th Internacional
IPCO Conference, 2002, págs 240-257.
[16] K. Jain and V.V. Vazirani. Approximation algorithms for metric facility
locations and k-median problems using primal-dual schema and Lagrangian
relaxation. Journal of the ACM 48, págs 274-296, 2001.
[17] Mahdian M. Markakis E. Saberi A. y Vazirani V.V. Jain, K. Greedy facility

location algorithms analized using dual fitting with factor-revealing LP. págs
795-824. Journal of the ACM 50, 2003.
[18] R.M. Karp. Reductibility among combinatorial problems. págs 85-103. Ple-
num Press, New York, 1972.
[19] Bernhard Korte and Jens Vygen. Combinatorial Optimization, Theory and
Algorithms. Number 21 in Algorithms and Combinatorics. Springer, págs
561-598, third edition, 2005.
[20] H.W. Kuhn and A.W. Tucker. In Proceedings of the Second Berkeley Sym-
posium on Mathematical Statistics and Probability, 1951.
[21] A.H. Land and Doig A.G. An automatic model of solving discrete program-
ming problems. Econometrica 28, 1960.
[22] Venkata N. Padmanabhan Lili Qiu and Geoffrey M. Volker. On the place-
ment of web servers replicas. In Proceedings of IEEE INFOCOM’01, 2001.
[23] Y. Ye M., Mahdian and J. Zhang. Approximation algorithms for metric

facility location problems. 2006.
[24] Plus Magazine. Agner Krauro Erlang (1878-1929), 30/04/1997,

http://plus.maths.org/content/os/issue2/erlang/index, (25/05/2012).
[25] Garey M.R. and D.S. Johnson. Computers and Intractability A guide to
the theory of NP-Completeness. 1979.
[26] G. Cornuejols G.L. Nemhauser and L.A. Wolsey. Discrete Location Theory.
págs 119-171. John Wiley and Sons Inc., 1990.
BIBLIOGRAFÍA 65
[27] Bellman R. and S. Dreyfus. Applied Dynamic Programming. Princeton

University Press, 1962.
[28] Harvey M. Salkin. Integer Programming. Addison-Wesley Publishing Com-

pany, 1975.
[29] K.J. Arrow Scarf, H.E. and S. Karlin. Approximation Solutions to a Simple
Multi-Echelon Inventory Problem. Standford University Press, 1962.
[30] Hamdy A. Taha. Integer Programming, Theory, Applications and Compu-
tations. Academic Press, 1975.
[31] Jens Vygen. Approximation Algorithms for Facility Location Problems.

Research Institute for Discrete Mathematics, 2005.
[32] Wikipedia. Francois Quesnay, 19/01/2007,

http://es.wikipedia.org/wiki/quesnay, (11/02/2013).
[33] Averill M. Law y W.David Keltan. Simulation modeling and analysis.

McGraw-Hill, Tuscon Arizona, 1991.

T E S I S: Programaci On Entera: El Problema de Localizaci On de Plantas

Cargado por

Copyright:

Formatos disponibles

T E S I S: Programaci On Entera: El Problema de Localizaci On de Plantas

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

T E S I S: Programaci On Entera: El Problema de Localizaci On de Plantas

Cargado por

Copyright:

Formatos disponibles

Universidad Nacional Autónoma de México

Programación entera: El problema de

El uso de imágenes, fragmentos de videos, y demás material que sea

1. Datos del alumno

2. Datos del tutor

3. Datos del Sinodal 1

4. Datos del Sinodal 2

5. Datos del Sinodal 3

6. Datos del Sinodal 4

7. Datos del trabajo escrito

1.1. Antecedentes Históricos . . . . . . . . . . . . . . . . . . . . . . . 1

1.2. Modelo de Programación Lineal . . . . . . . . . . . . . . . . . . . 2

1.3. Región de Soluciones Factibles . . . . . . . . . . . . . . . . . . . 5

1.3.2. Puntos Extremos . . . . . . . . . . . . . . . . . . . . . . . 7

1.3.3. Variables Básicas y no Básicas . . . . . . . . . . . . . . . 8

1.3.4. Variables básicas y puntos extremos . . . . . . . . . . . . 9

1.4. Método Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.4.1. Coeficientes de costo reducido . . . . . . . . . . . . . . . . 11

1.4.2. Criterios de optimalidad y de selección . . . . . . . . . . . 12

1.5.1. Relación entre los problemas primal y dual . . . . . . . . 15

2.1. Antecedentes Históricos . . . . . . . . . . . . . . . . . . . . . . . 17

2.2. Programación Entera Lineal . . . . . . . . . . . . . . . . . . . . . 18

2.2.1. Modelo de Programación Entera Lineal . . . . . . . . . . 18

2.3. Técnica Branch & Bound . . . . . . . . . . . . . . . . . . . . . . 18

2.3.1. Algoritmo de Dakin (Branch and Bound) . . . . . . . . . 19

2.3.2. Descripción del algoritmo . . . . . . . . . . . . . . . . . . 21

3. Compl. Alg. en la Prog. Entera 29

3.1. Definiciones Básicas . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.1.1. Tipos de Algoritmos . . . . . . . . . . . . . . . . . . . . . 29

3.1.2. Problemas de decisión . . . . . . . . . . . . . . . . . . . . 31

3.1.3. Tipos de problemas . . . . . . . . . . . . . . . . . . . . . 31

3.2. Ejemplos de problemas NP-Completos . . . . . . . . . . . . . . . 32

3.3. Problema de la mı́nima cubierta por conjuntos . . . . . . . . . . 34

3.4. Tiempos de ejecución . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.4.1. Algoritmo Merge-Sort . . . . . . . . . . . . . . . . . . . . 36

4. Problema de ubicación de plantas 39

4.1. Antecedentes Históricos . . . . . . . . . . . . . . . . . . . . . . . 39

4.2. Definición del problema . . . . . . . . . . . . . . . . . . . . . . . 40

4.4. Algoritmos de aproximación . . . . . . . . . . . . . . . . . . . . . 44

4.4.1. Descripción del algoritmo de Jain-Vazirani . . . . . . . . . 45

4.4.2. Descripción del algoritmo de Ajuste Dual . . . . . . . . . 50

4.5. ¿Qué tanto se puede mejorar? . . . . . . . . . . . . . . . . . . . . 53

Finalmente, quiero agradecer a mi asesor Ricardo Strausz Santiago, o mejor

Optimizar es un tema que siempre está presente en la vida cotidiana, y es

Este texto introduce al lector en el interesante mundo de la optimización, defi-

El término planta se refiere a cualquier lugar que genere un producto, como

El cliente es cualquier persona, empresa o incluso una población que requiera

En la primera parte de la tesis se incluye una base teórica de la programación

1.1. Antecedentes Históricos

La investigación de operaciones, surgió con la revolución industrial y con la

Tras finalizar la guerra, Gran Bretaña y Estados Unidos, inspirados en los

hacerlo en Estados Unidos.[30]

Al paso de los años, la investigación de operaciones fue evolucionando hasta

1.2. Modelo de Programación Lineal

Un problema de programación lineal se puede definir como optimizar cierta

Dentro de un modelo de optimización se distinguen 3 partes: las variables,

En un modelo de programación lineal se asume que algunas variables son

Supóngase que se quiere viajar de la ciudad X a la Z; la distancia d, medida

La función objetivo es una función lineal que depende de las variables de