Apuntes

de

Investigación

Operativa
 Apuntes
de
Investigación
Operativa
(10 de enero de 2011)

Autor:
M. Muñoz Márquez
Copyright 2011
c Universidad de Cádiz. Se concede permiso para copiar, distribuir y/o modificar
este documento bajo los términos de la Licencia de Documentación Libre de GNU, Versión 1.2 o
cualquier otra versión posterior publicada por la Free Software Foundation. Una traducción de la
licencia está incluida en la sección titulada “Licencia de Documentación Libre de GNU”.

Copyright 2011
c Universidad de Cádiz. Permission is granted to copy, distribute and/or modify
this document under the terms of the GNU Free Documentation License, Version 1.2 or any later
version published by the Free Software Foundation. A copy of the license is included in the section
entitled “GNU Free Documentation License”.
Capı́tulo 1

Problema de asignación

Algoritmo Húngaro de Asignación

1. Hacer ceros
a) Restar a cada fila su mı́nimo.
b) Restar a cada columna su mı́nimo.
2. Encuadrar ceros
a) En la fila o columna con menor número de ceros libres, encuadrar
uno.
b) Tachar los ceros de la fila y columna del cero encuadrado.
c) Repetir los dos pasos anteriores mientras queden ceros libres.
d ) Si se ha encuadrado un cero en cada fila y columna se tiene la asig-
nación óptima.
3. Tachar ceros con el menor número de lı́neas
a) Marcar las filas sin ceros encuadrados.
b) Marcar las columnas con cero tachado en fila marcada.
c) Marcar las filas con cero encuadrado en columna marcada.
d ) Repetir los dos pasos anteriores mientras se realicen nuevas marcas.

V
VI CAPÍTULO 1. PROBLEMA DE ASIGNACIÓN

e) Rayar las filas no marcadas y las columnas marcadas.

4. Mover ceros
a) Calcular el mı́nimo de los elementos no rayados.
b) Restar dicho mı́nimo a los elementos no rayados.
c) Sumar dicho mı́nimo a los elementos rayados dos veces.
d ) Repetir desde el paso Encuadrar ceros.
Capı́tulo 2

Programación entera

2.1. Introducción

Definición 2.1.1 Un problema de programación lineal entera es un problema

de programación lineal en el que alguna de las variables están sujeta a restric-
ciones de integridad, es decir, únicamente puede tomar valores enteros.

Suponiendo las primeras k variables están sujetas a condición de integri-

dad, un problema de programación lineal entera se puede escribir de la forma:

mı́n c0 x
(P E) s.a. Ax = b
x≥0
x1 , . . . , xk ∈ Z

Los problemas de programación lineal se clasifican en dos tipos:

Puros : Los problemas de programación lineal entera puros son aquellos en que
todas la variables están sometidas a restricciones de integridad y todos
los coeficientes del problema, matriz A y vectores c y b, tienen valores
enteros.

VII
VIII CAPÍTULO 2. PROGRAMACIÓN ENTERA

Mixtos : Un problema de programación lineal entera se dice mixto si no es un

problema de programación lineal puro.

Definición 2.1.2 Dado un problema de programación lineal, (P E), se define

su problema relajado, (P R), como:

mı́n c0 x
(P R) s.a. Ax = b
x≥0

El problema relajado de un problema de programación lineal entera es,

por tanto, el que se obtiene suprimiendo las condiciones de integridad sobre las
variables.

En un principio podrı́a parecer que la resolución del problema de pro-

gramación lineal entera se puede reducir a redondear la solución obtenida re-
solviendo el problema relajado, pero esto en general produce puntos no factible
y en ocasiones alejados de la solución del problema de programación entera.

2.2. Entero vs. relajado

Las relaciones existentes entre las soluciones del problema de programa-

ción lineal entera y su correspondiente relajado no son las que en un principio
podrı́an esperarse.

Las primeras relaciones entre ambos problemas se pueden deducir deri-

van de la definición del problema problema relajado. Dado que la región factible
de (P R) contiene a la de (P E) se tiene:

Lema 1 El problema (P R) tiene un valor objetivo óptimo mejor o igual que

(P E).

Lema 2 Si una solución óptima de (P R) es factible para (P E) entonces tam-

bién es solución óptima de (P E).
2.3. MÉTODO DE RAMIFICACIÓN Y ACOTACIÓN IX

Atendiendo al tipo de solución son posibles las siguientes comibinaciones:

(P E) (P R)
Infactible Infactible
Solución óptima Solución óptima
Infactible Solución óptima
Infactible Ilimitado
Solución óptima Ilimitado
Ilimitado Ilimitado

Considérese el siguiente problema:

máx x1 + x2
√
s.a. − 2x1 + x2 = α
x1 , x2 ≥ 0

Para cualquier valor de α se tiene que el problema relajado es imilitado,

en cambio, tomando α = 0, el único punto factible del problema entero es el
cero, por lo que el problema entero tiene solución óptima finita.

Para α = 1 el problema de programación entera es infactible.

El caso tercero se puede ilustrar considerando α = 1 y el problema de

minimizar.

2.3. Método de ramificación y acotación

El método de ramificación y acotación consiste en la división sucesiva

de un problema en varios subproblemas, generalmente dos, de forma que ca-
da subproblema sea más fácil de resolver que el problema original. La mejor
solución obtenida durante el proceso será la solución del problema de partida.

El siguiente ejemplo ilustra el método de ramificación y acotación para

la resolución de problemas de programación lineal entera.
X CAPÍTULO 2. PROGRAMACIÓN ENTERA

Ejemplo 2.3.1 Considérese el problema de programación lineal entera:

máx 4x + 2y
(P E) s.a. 9x + 6y ≤ 30
4x + 7y ≤ 18
x, y ≥ 0
x, y ∈ Z

En primer lugar se considera su correspondiente problema relajado

máx 4x + 2y
(P R) s.a. 9x + 6y ≤ 30
4x + 7y ≤ 18
x, y ≥ 0

y se resuelve utilizando el procedimiento habitual. La primera tabla sı́mplex

después de pasar el problema a formato estándar quedarı́a

x y s1 s2 b
s1 9 6 1 0 30
s2 4 7 0 1 18
z −4 −2 0 0 0

Por tanto, debe entrar x y salir s1

x y s1 s2 b
2 1 10
x 1 3 9 0 3
s2 0 13
3 − 49 1 14
3
2 4 40
z 0 3 9 0 3

Obteniéndose la tabla sı́mplex óptima correspondiente a la solución del

problema relajado.
La solución óptima de (P R) es x = 10/3 e y = 0, con valor objetivo
z = 40/3. Ningún valor para x en el intervalo (3, 4) es solución de (P E)
al no cumplir la condición de integridad, pudiéndose eliminar dicha franja
del conjunto de puntos factibles. Si se considera (P E) restringido a cada
una de las partes en que dicha banda divide a la región factible se obtienen
dos subproblemas: (P E1) con la restricción adicional x ≤ 3 y (P E2) con
2.3. MÉTODO DE RAMIFICACIÓN Y ACOTACIÓN XI

la restricción adicional x ≥ 4. La solución de (P E) será la mejor de las

soluciones de ambos subproblemas.
Para la resolución de (P E1) se añade la restricción x ≤ 3 a la tabla
óptimia de (P R):

x y s1 s2 s3 b
2 1 10
x 1 3 9 0 0 3
s2 0 13
3 − 49 1 0 14
3
s3 1 0 0 0 1 3
2 4 40
z 0 3 9 0 0 3

Siendo necesario pivotar sobre la fila 1 y la columna 1 para recuperar la

base.
x y s1 s2 s3 b
2 1 10
x 1 3 9 0 0 3
s2 0 13
3 − 49 1 0 14
3
s3 0 − 23 − 19 0 1 − 13
2 4 40
z 0 3 9 0 0 3

Aplicando sı́mplex dual se obtiene la tabla óptima:

x y s1 s2 s3 b
x 1 0 0 0 1 3
s2 0 0 − 76 1 13
2
5
2
y 0 1 1
6 0 − 23 1
2
1
z 0 0 3 0 1 13

La solución óptima de (P R1), es decir, el problema relajado de (P E1),

es x = 3 e y = 1/2, con valor objetivo z1 = 13.
Análogamente se harı́a para (P E2) pero incorporando la restricción x ≥
4:
x y s1 s2 s3 b
2 1 10
x 1 3 9 0 0 3
s2 0 13
3 − 49 1 0 14
3
s3 −1 0 0 0 1 −4
2 4 40
z 0 3 9 0 0 3
XII CAPÍTULO 2. PROGRAMACIÓN ENTERA

x y s1 s2 s3 b
2 1 10
x 1 3 9 0 0 3
s2 0 13
3 − 49 1 0 14
3
s3 0 2
3
1
9 0 1 − 23
2 4 40
z 0 3 9 0 0 3

Quedando un problema infactible.

Dado que la solución obtenida para (P R1) no es entera, y = 1/2, se debe

continuar el proceso, añadiendo los cortes y ≤ 0 e y ≥ 1.

x y s1 s2 s3 s4 b
x 1 0 0 0 1 0 3
s2 0 0 − 76 1 13
2 0 5
2
y 0 1 1
6 0 − 32 0 1
2
s4 0 1 0 0 0 1 0
1
z 0 0 3 0 1 0 13

x y s1 s2 s3 s4 b
x 1 0 0 0 1 0 3
s2 0 0 − 76 1 13
2 0 5
2
y 0 1 1
6 0 − 32 0 1
2
s4 0 0 − 16 0 3
2 1 − 12
1
z 0 0 3 0 1 0 13

x y s1 s2 s3 s4 b
x 1 0 0 0 1 0 3
s2 0 0 0 1 −4 −7 6
y 0 1 0 0 0 1 0
s1 0 0 1 0 −9 −6 3
z 0 0 0 0 4 2 12

La solución óptima al problema (P R11) es x = 3 e y = 0 con valor

z11 = 12.

Falta por explorar (P R12), es decir, la rama que se obtiene añadiendo la

2.3. MÉTODO DE RAMIFICACIÓN Y ACOTACIÓN XIII

restricción y ≥ 1 a (P R1):

x y s1 s2 s3 s4 b
x 1 0 0 0 1 0 3
s2 0 0 − 76 1 13
2 0 5
2
y 0 1 1
6 0 − 32 0 1
2
s4 0 −1 0 0 0 1 −1
1
z 0 0 3 0 1 0 13

x y s1 s2 s3 s4 b
x 1 0 0 0 1 0 3
s2 0 0 − 67 1 13
2 0 5
2
y 0 1 6
1
0 − 32 0 1
2
s4 0 0 6
1
0 − 32 1 − 12
1
z 0 0 3 0 1 0 13

x y s1 s2 s3 s4 b
1 2 8
x 1 0 9 0 0 3 3
s2 0 0 − 49 1 0 13
3
1
3
y 0 1 0 0 0 −1 1
s3 0 0 − 19 0 1 − 32 1
3
4 2 38
z 0 0 9 0 0 3 3

La solución obtenida para (P R12) tiene valor objetivo z = 37/3, si se

sigue buscando a partir de ella lo mejor que puede ocurrir, dado que los
coeficientes de la función objetivo son enteros, es que se obtenga otra
solución con valor 12, que iguaları́a a la solución ya obtenida. Por tanto,
la búsqueda en esta rama se puede acabar en este nodo.
Al haber acabado la exploración de todas las ramas la búsqueda ha con-
cluido y la solución buscada es la mejor, y en este caso la única, obtenida
x = 3 e y = 0, con valor objetivo z = 12.

Como muestra el ejemplo, el método de ramificación y acotación comien-

za resolviendo el problema relajado correspondiente. Si la solución es entera se
ha resuelto el problema entero. En caso contrario, se elige una variable con
valor no entero y se ramifica construyendo dos subproblemas.
XIV CAPÍTULO 2. PROGRAMACIÓN ENTERA

En cada una de las sucesivas iteraciones, se procede eligiendo un nodo no

terminal y resolviendo el problema relajado correspondiente. Si dicho problema
es infactible el nodo se marca como terminal. Si la solución es entera se actualiza
el valor z0 como el valor objetivo de la mejos solución entera obtenida y se
marca el nodo como terminal. Se marcan como nodos terminales todos los que
su correspondiente valor objetivo sea peor que z0 .

La búsqueda acaba cuando todos los nodos del árbol de búsqueda se han
marcado como terminales. La solución al problema entero es la mejor de las
soluciones enteras obtenidas, en caso de haber encontrado alguna.

Ejemplo 2.3.2 El árbol de búsqueda asociado a la resolución del problema

anterior es:
(P R)
x = 10
3 ,y = 0
z = 40
 XXXXX
3
 

9
 XXX z
(P R1)
(P R2)
(x ≤ 3)
(x ≥ 4)
x = 3, y = 12
Infactible
z = 13
 P
 PP
)
 PP
q
(P R11) (P R12)
(y ≤ 0) (y ≥ 1)
x = 3, y = 0 x = 38 , y = 1
38
z = 12 z= 3