GRAU DE MATEMÀTIQUES

Treball final de grau

Introducción a la programación
lineal y entera: métodos del
Sı́mplex y de B&B

Autor: Arturo Elizalde Masiá

Director: Dra. Susana Romano Rodrı́guez

Realitzat a: Departament de Matemàtiques i Informàtica
(Matemàtiques i Informàtica)

Barcelona, 21 de junio de 2020

Abstract

Since Dantzig published the simplex method in 1949 for the solution of linear pro-
gramming problems (area of optimization) a great interest was sparked that allowed a
vast theoretical growth, opening the door to the development of new methods and algo-
rithms that are widely used today.
The main goal of this work is to address, at an introductory level, the simplex method
and the Branch and Bound method (or B&B). If x = (xB , xN ) is a basic feasible solution
of a linear programming problem min{f (x) | Ax = b, x ≥ 0} with no degenerate solutions,
throughout the iterative algorithm of the simplex it is determined through a finite quantity
of steps whether the problem is already within an optimal solution, whether a finite
optimal solution does not exist, or whether it determines the optimal solution.
The Branch and Bound method is used for solving linear programming problems in
which the solution (or part of it) must be an integer. The algorithm follows a binary tree
structure and under ideal conditions finishes in a finite quantity of steps.

Resumen

Desde que Dantzig publicó el método del sı́mplex en 1949 para la resolución de proble-
mas de programación lineal (área de la optimización) despertó un fuerte interés, y permitió
que se produjera un amplio crecimiento teórico dando pie al desarrollo de nuevos métodos
y algoritmos muy utilizados hoy en dı́a.
El objetivo principal del trabajo es abordar de manera introductoria el método del
sı́mplex y el método de Branch and Bound (o B&B). Si x = (xB , xN ) es una solución
básica factible de un problema de programación lineal mı́n{f (x) | Ax = b, x ≥ 0} sin
soluciones degeneradas, mediante el algoritmo iterativo del sı́mplex se determina en una
cantidad finita de pasos si el problema se encuentra ya en una solución óptima, si no
existe solución óptima finita o bien determina la solución óptima.
El método de Branch and Bound, se utiliza para resolver problemas de programación
lineal en donde la solución (o parte de esta), debe ser entera. El algoritmo sigue una
estructura de árbol binario y bajo condiciones ideales termina en una cantidad finita de
pasos.

2010 Mathematics Subject Classification. 90C05, 90C10, 90C11

i
Agradecimientos

A la Dra. Susana Romano por su ayuda, la paciencia y su tiempo.

A Joan y mi hermano Borja que me han ayudado siempre que lo he necesitado.

ii
Índice

1. Introducción 1

2. Programación Lineal 3
2.1. Representaciones equivalentes . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2. Soluciones básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3. Conjuntos convexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4. El método del sı́mplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4.1. Formulación general del método del sı́mplex. . . . . . . . . . . . . 10
2.4.2. Esquema general del método del sı́mplex . . . . . . . . . . . . . . . 11
2.4.3. Convergencia del método del sı́mplex . . . . . . . . . . . . . . . . . 12
2.4.4. La tabla del método del sı́mplex . . . . . . . . . . . . . . . . . . . 13
2.4.5. Construcción de una solución básica factible inicial . . . . . . . . . 16
2.4.6. Reglas de prevención de ciclo . . . . . . . . . . . . . . . . . . . . . 18
2.5. Dualidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5.1. Dualidad débil y dualidad fuerte . . . . . . . . . . . . . . . . . . . 20
2.5.2. Holguras complementarias . . . . . . . . . . . . . . . . . . . . . . . 22
2.5.3. Análisis de sensibilidad . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5.4. Formulación del algoritmo primal-dual . . . . . . . . . . . . . . . . 25
2.5.5. Algoritmo primal-dual . . . . . . . . . . . . . . . . . . . . . . . . . 27

3. Programación Entera 29
3.1. El método de Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.1. Descripción del método Branch and Bound . . . . . . . . . . . . . 30
3.1.2. Esquema general del método Branch and Bound . . . . . . . . . . 31
3.1.3. Convergencia del método Branch and Bound . . . . . . . . . . . . 32

4. Problemas aplicados 36
4.1. Ejemplos de problemas de programación lineal . . . . . . . . . . . . . . . 36
4.1.1. Problema de la dieta . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2. Relaciones lógicas con variables binarias . . . . . . . . . . . . . . . . . . . 37
4.2.1. Producción acotada . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2.2. Costes fijos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2.3. Variables con una cantidad finita de valores . . . . . . . . . . . . . 38
4.2.4. Restricciones sustitutas . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3. Ejemplos de problemas de programación Entera . . . . . . . . . . . . . . . 39
4.3.1. El problema de la mochila . . . . . . . . . . . . . . . . . . . . . . . 39

iii
 4.3.2. Problemas de localización . . . . . . . . . . . . . . . . . . . . . . . 40

5. Conclusiones 41

iv
1. Introducción

Si f : A −→ R es una función con A ⊂ Rn , mediante la optimización en general se

pretende encontrar y ∈ A de forma que f (x) ≤ f (y), o bien f (x) ≥ f (y) para todo y ∈ A.
La programación lineal es un campo de la optimización en el cual la función denominada
función objetivo, es lineal y respeta un conjunto de restricciones también lineales, de
igualdad o desigualdad.
La historia de la programación lineal data sus inicios sobre una publicación en 1823
del matemático y fı́sico Jean-Baptiste Joseph Fourier. No serı́a por eso hasta 1827 donde
se considera que está formulado el primer problema de programación lineal, planteado
como un sistema de inecuaciones a resolver junto al método de eliminación de Fourier ;
que de forma simplificada, es una extensión del método de eliminación de Gauss (usado
para sistemas de ecuaciones lineales).
La siguiente publicación conocida data en 1911 escrito por el ingeniero y matemático
Charles-Jean de La Vallée Poussin; Poussin diseño un método para la aproximación de
Chebyshev que consistı́a en minimizar kAx − bk∞ dada una matriz A y un vector b.
El matemático ruso Leonid Vitaliyevich Kantorovich publicó Métodos matemáticos para la
organización y la producción en el año 1939. Su obra fue archivada por razones ideológicas
en la URSS y no vio la luz hasta 1959.
Es por esto que es el matemático y fı́sico G. B. Dantzig quien es considerado el padre
de la programación lineal tal y como la conocemos hoy en dı́a, debido a sus trabajos en
1947, cuando trabajaba como asesor de las Fuerzas Áereas de los Estados Unidos en el
desarrollo de una herramienta para la automatización de la planificación de actividades
como despliegue de tropas, entrenamiento y demás logı́stica de las tropas aliadas entre
otros.
El nombre de programación lineal viene precisamente de su trabajo como asesor donde
cada una de estas planificaciones se denominaba “programación”(“program”, en inglés).
Por tanto, el nombre se refiere al diseño óptimo de programas, como recoge el tı́tulo de
la primera publicación de Dantzig sobre el tema: Programming in a linear structure. El
nombre final de programación lineal se le atribuye al economista y matemático americano,
aunque de origen holandés, T. C. Koopmans.
En 1949 Dantzig publicó el Método del Sı́mplex para resolver problemas de programa-
ción lineal, y que desde entonces ha sido el algoritmo de referencia para resolver este tipo
de problemas, independientemente de su tamaño. Según el propio Dantzig, la idea que le
llevo a creer que el Método del Sı́mplex serı́a una técnica de solución muy eficiente, fue
debida a que la geometrı́a usada para su tesis fue asociada con las columnas de una ma-
triz en lugar de sus filas. Desde su publicación la programación lineal creció en múltiples
direcciones, desde desarrollos teóricos hasta aspectos más puramente computacionales.
“La observación, en particular, de que varios sistemas económicos, industriales, fi-
nancieros y militares pueden ser modelados (o aproximados razonablemente) por sistemas
matemáticos de desigualdades y ecuaciones lineales ha dado lugar al desarrollo del campo
de programación lineal.”(Dantzig, 1997).

Los inicios de la programación lineal entera datan de 1958 con el trabajo de Ralph
E. Gomory quien introdujo el método de los planos de corte. El algoritmo Branch and
Bound (o B&B) fue propuesto por primera vez por A. H. Land y A. G. Doig en 1960
para la programación entera.

1
 Aunque la programación entera es NP-hard en general, algoritmos como el de Branch
and Bound han resultado ser de gran utilidad en la práctica. La investigación en esta área
es actualmente muy activa.

Estructura de la Memoria

Este trabajo recoge los principales resultados teóricos que ayudan a comprender y
desarrollar el método del sı́mplex desde un punto de vista tanto geométrico como alge-
braico.
En el capı́tulo 2 establecemos las bases de la programación lineal. Se define matemáti-
camente lo que es un programa lineal ası́ como sus representaciones equivalentes; se define
el conjunto de soluciones posibles que admite este tipo problema y que a su vez son solucio-
nes candidatas para optimizar el problema. Se darán condiciones necesarias y suficientes
para poder encontrar la solución óptima. Además se verán algunas relaciones importantes
entre las propiedades geométricas del conjunto de soluciones y el análisis convexo que nos
permitirá comprender la lógica usada en el método del sı́mplex. Completaremos la formu-
lación del método del sı́mplex con el uso de la tabla del método, que ayudará a organizar y
afrontar mejor un problema dado. Para finalizar el capı́tulo trataremos la dualidad, donde
podremos ver que todo programa lineal tiene asociado con otro programa lineal con el que
esta ampliamente relacionado y ofrecer ası́ una mayor perspectiva. Se tratará también el
algoritmo primal-dual, un método alternativo para resolver problemas de programación
lineal.
El capı́tulo 3 lo dedicaremos a la programación entera. Se analizará en detalle el método
de Branch and Bound. Para finalizar, en el capı́tulo 4 ejemplificaremos la formulación
de alguno de los problemas clásicos de la programación lineal y entera, y se establecen
algunas relaciones lógicas que ayudaran a comprender la modelización de problemas de
programación entera.

2
2. Programación Lineal

Las principales fuentes consultadas para este capı́tulo han sido, [1] y [2]. Se citaran
fuentes más concretas en alguno de los apartados.

Un problema de programación2 lineal es un problema de optimización en el cual tanto

la función (función objetivo) 3 como las restricciones son lineales. Cualquier programa
lineal se puede convertir a la siguiente forma estándar:

minimizar c1 x1 + c2 x2 + · · · + cn xn
sujeto a a11 x1 + a12 x2 + · · · + a1n xn = b1
a21 x1 + a22 x2 + · · · + a2n xn = b2
.. ..
. .
am1 x1 + am2 x2 + · · · + amn xn = bm
y xi ≥ 0, i ∈ {1, · · · , n}.

donde las bi , ci y aij son constantes reales fijas, y las xi son valores reales a determinar.

Podemos expresar el problema de forma más compacta como4

minimizar cT x
sujeto a Ax = b (2.1)
x≥0

donde x, c ∈ Rn , b ∈ Rm y A ∈ Mm×n (R), de rango m, con m ≤ n.

2.1. Representaciones equivalentes

En la siguiente tabla representamos dos formulaciones que son especialmente útiles.

Problema de minimización Problema de maximización

mı́n cT x máx cT x
Forma
sujeto a Ax = b sujeto a Ax = b
Estándar
x≥0 x≥0
mı́n cT x máx cT x
Forma
sujeto a Ax ≥ b sujeto a Ax ≤ b
Canónica
x≥0 x≥0

2
El uso de la palabra programación en este contexto se refiere a ”planifiación”.
3
f : Rn −→ R. Esta es la función que queremos minimizar o maximizar. Se suele expresar de la forma
c1 x1 + c2 x2 + · · · + cn xn donde los coeficientes c1 , c2 , . . . , cn son conocidos.
4
Si un vector es un vector fila (1 × n) o columna (n × 1) deberı́a quedar claro por contexto, pero para
evitar confusión, si x es un vector, se denotará:
x si representa un vector columna.
xT si representa un vector columna traspuesto, es decir un vector fila.

3
 Forma Canónica. En caso de que el problema sea de minimización, todas las
restricciones son de la forma ” ≥ ” y, si es de maximización, son de la forma ”≤”.
En ambos casos las variables han de ser no negativas.

Forma Estándar. todas las restricciones son de igualdad y todas las variables son
no negativas. En general nos centraremos en esta última.

Vamos a ver distintas transformaciones que se pueden hacer en los elementos que
componen un problema de programación lineal, y que nos permitirán pasar el problema
a la forma estándar si fuera necesario.
Función objetivo. Todo problema de minimización puede transformarse en un pro-
blema de maximización, y viceversa, ya que se verifica la siguiente relación:

n
X n
X
máx cj xj = -mı́n −cj xj .
j=1 j=1

Restricciones. Existen varias manipulaciones posibles:

Para pasar de una restricción ” ≤ ”(” ≥ ”) a una restricción ” ≥ ”(” ≤ ”), es

suficiente multiplicar todos los coeficientes por −1.

Si no queremos
Pn restricciones de igualdad, podemos reemplazar cada
Pn restricción de
la forma j=1 aij xj = bi por dos restricciones de desigualdad j=1 aij xj ≥ bi y
P n
j=1 aij xj ≤ bi .

Si solo queremos restriccionesPde igualdad, podemos remplazar cada restriccion de

la forma nj=1 aij xj ≤ bi por nj=1 aij xj + xsi+n = bi . A estas variables se las conoce
P
como variables P
de holgura y se suelen denotar con la letra s por slack. Si la restricción
es de la forma nj=1 aij xj ≥ bi , bastarı́a con restar la variable de holgura en vez de
sumarla. Estas variables se denominan variables excedentes.

No negatividad. Si tenemos una variable xj que puede tomar valores positivos y

negativos y queremos solo valores ≥ 0, podemos definir xj := uj − vj imponiendo uj ≥ 0
y vj ≥ 0.

Observación 2.1. En caso de pasar las restricciones de un programa lineal de la forma

Ax ≤ b (Ax ≥ b) mediante variables de holgura (excedentes) a restricciones de igualdad, la
matriz del programa lineal pasarı́a a ser de dimensión m × (n + m) de la forma [A, I]x = b,
siendo I la matriz identidad de dimensión m.

2.2. Soluciones básicas

Dado el sistema de ecuaciones

Ax = b,
con x ∈ Rn , b ∈ Rm y A ∈ Mm×n (R) de rango m, con m ≤ n, reordenamos la matriz de
manera que las m primeras columnas sean linealmente independientes.

4
Ahora, sea B ∈ Mm×m (R) la matriz determinada por estas m primeras columnas. Enton-
ces, B es una matriz invertible y xB ∈ Rm formado por las variables asociadas a B y xN
las demás, podemos escribir el sistema como

BxB + N xN = b.

A menos que se indique explı́citamente lo contrario, en este apartado se mantienen las

dimensiones de las matrices y vectores introducidos.

Definición 2.2. Dada cualquier submatriz B invertible formada por columnas de A,

x = (xB , xN ) es una solución básica de un programa lineal en la forma estándar, si xB
es solución de BxB = b y xN = 0. Las variables de xB se denominan variables básicas.

Definición 2.3. Si una, o más variables básicas son nulas, entonces la solución se dice
solución básica degenerada.

Consideremos ahora
Ax = b
(2.2)
x ≥ 0,
que representa las restricciones de un programa lineal en forma estándar.

Definición 2.4. Un vector x que satisfaga (2.2), se dice que es factible. Una solución
factible para (2.2) que también sea básica, se denomina solución básica factible.

Observación 2.5. Al conjunto de soluciones factibles, se le conoce como región factible

y se suele denotar por F . Es decir, F = {x | Ax = b, x ≥ 0}.

Definición 2.6. Una solución básica factible óptima és una solución básica factible que
optimiza el problema.

Observación 2.7. La solución básica factible óptima en caso de existir, puede ser única
o existir más de una.

Mediante el siguiente teorema se establece la importancia primordial de las solucio-

nes básicas factibles para resolver problemas de programación lineal. La demostración
representa el inicio del desarrollo del método del sı́mplex.

Teorema 2.8. Dado un programa lineal en la forma estándar (2.1), donde A es una
matriz de m × n de rango m,

1. si existe una solución factible, existe una solución básica factible;

2. si existe una solución factible óptima, existe una solución básica factible óptima.

Dem.: 1.) Sean a1 , a2 , . . . , an las columnas de A. Supongamos que xT = (x1 , x2 , . . . , xn )

es una solución factible. Entonces, en función de las columnas de A, esta solución satisface:

x1 a1 + x2 a2 + · · · + xn an = b.

Supongamos que exactamente p de las variables xi son mayores que cero, y por conve-
niencia, que sean las primeras p variables. Entonces,

x1 a1 + x2 a2 + · · · + xp ap = b. (2.3)

5
 Separamos en dos casos, dependiendo si el conjunto a1 , a2 , . . . , ap es linealmente inde-
pendiente o no:

Caso 1: Si tenemos a1 , a2 , . . . , ap linealmente independientes, entonces es evidente que

p ≤ m.

Si p = m, la solución es básica factible y por tanto hemos acabado.

Si p < m, como rang(A) = m, podemos completar con m − p vectores de los n − p

restantes por lo que el conjunto resultante de m vectores es linealmente indepen-
dientes. La asignación del valor cero a las m − p variables correspondientes da una
solución básica factible (degenerada).

Caso 2: Si a1 , a2 , . . . , ap linealmente dependientes, entonces existen λ1 , λ2 , . . . , λp ∈ R,

no todas nula y al menos una de ellas positiva tal que

λ1 a1 + λ2 a2 + · · · + λp ap = 0. (2.4)

Consideremos ahora α ∈ R, entonces, obtenemos

(x1 − αλ1 )a1 + (x2 − αλ2 )a2 + · · · + (xp − αλp )ap = b. (2.5)

como resultado de multiplicar (2.4) por α y restándola de (2.3). Observamos que para
todo α las componentes xi − αλi corresponden a una solución de las ecuaciones lineales,
pero la solución puede ser no factible (i.e, xj − αλj < 0 para algún j ∈ {1, . . . , p}).
Haciendo λT = (λ1 , λ2 , . . . , λp , 0, 0, . . . , 0), se observa que para cualquier α

x − αλ (2.6)

es una solución de las igualdades. Si α = 0 tenemos la solución factible original. Como

tenemos que al menos una de las λi es positiva, como mı́nimo una componente de x − αλ
decrecerá a medida que α crece. Incrementamos α hasta que una o más componentes son
cero. Especı́ficamente, seleccionamos α = ᾱ, donde
 
xi
ᾱ = mı́n : λi > 0 .
λi

Sea k un ı́ndice para el cual ᾱ = xk /λk , y consideramos

xj − ᾱλj (2.7)

Si λj ≤ 0, OK.

Si λj > 0, entonces xj − ᾱλj ≥ xj − (xj /λj )λj ≥ 0.

Acabamos de ver ası́ que la solución dada por (2.6) es factible y tiene a lo sumo p − 1
variables positivas.
Al repetir este proceso, en caso necesario, se podrı́an eliminar las variables positivas hasta
tener una solución factible con las columnas correspondientes que son linealmente inde-
pendientes. En este punto es aplicable el Caso 1.

6
 2.) Sea xT = (x1 , x2 , . . . , xn ) una solución factible óptima. Como en 1.) suponemos
que hay exactamente p variables positivas x1 , x2 , . . . , xp . De nuevo hay dos casos; el caso
1, correspondiente a la independencia lineal, es exactamente igual que antes. El caso
2 también se desarrolla igual que el anterior, pero además debemos demostrar que la
solución (2.6) es óptima.
Para α suficientemente pequeña la solución dada por (2.6) es una solución factible para
valores positivos o negativos de α5 . Consideremos entonces el valor de la solución (2.6):

cT x − αcT λ.

Veamos ahora que cT λ = 0. Puesto que si cT λ 6= 0, esto serı́a:

si cT λ > 0, para α = ᾱ, cT x − ᾱcT λ < cT x.

si cT λ < 0, podemos escoger α < 0 tal que, cT x − αcT λ < cT x.

Estarı́amos ası́ ante una contradicción por la hipótesis de optimalidad de x. Por tanto
necesariamente cT λ = 0.
Una vez establecido que la nueva solución factible con menos componentes positivos tam-
bién es óptima, el resto de la demostración se puede completar exactamente como en la
parte 1). 

Observación 2.9. De la demostración del teorema que acabamos de presentar, se deduce

que para buscar una solución óptima en un problema de programación lineal, es suficiente
con tener en cuenta las soluciones básicas factibles, puesto que en dicho tipo de solución
siempre se consigue el valor óptimo.

2.3. Conjuntos convexos

Hasta ahora, nos hemos basado en propiedades elementales de sistemas de ecuaciones

lineales. A continuación vamos a ver como interviene el análisis convexo 6 en la progra-
mación lineal. El vinculo principal entre las teorı́as algebraica y geométrica es la relación
formal existente entre las soluciones básicas factibles y los puntos extremos de los polie-
dros.

Definición 2.10. Se dice que un conjunto C ⊂ Rn es convexo si ∀x, y ∈ C, [x, y] ⊂ C

donde [x, y] = {λx + (1 − λ)y | 0 ≤ λ ≤ 1}.

Definición 2.11. x ∈ Rn es combinación

Pk lineal convexa
Pk de x1 , · · · , xk ∈ Rn si existen
λ1 , · · · , λk ∈ R no negativos con i=1 λi = 1 y x = i=1 λi xi .

Definición 2.12. Sea S ⊂ Rn . La envoltura convexa de S, conv(S), se define como el

conjunto de todas las combinaciones lineales convexas de puntos de S.
5
Para −ᾱ:
Si λj ≥ 0, OK.
Si λn
j < 0, entonces
o puede pasar que xj + ᾱλj < 0 . En ese caso seleccionarı́amos α =
xi
mı́n λi : λi < 0 . Volviendo a empezar el análisis, tenemos que si λj ≥ 0, OK. Si λj < 0, en-
tonces xj − αλj ≥ xj − (xj /λj )λj ≥ 0.
Hemos encontrado ası́ un α < 0 para el cual x − αλ es factible.
6
El análisis convexo es la rama de las matemáticas que se dedica al estudio de las funciones convexas
y de los conjuntos convexos.

7
Proposición 2.13. (La intersección de conjuntos convexos es convexa). Dada una colec-
ción de conjuntos convexos {Ci }i∈I , entonces el conjunto C ∗ = i∈I Ci es un conjunto
T
convexo

Dem.: Supongamos C ∗ 6= ∅ (en el caso contrario, ∅ es convexo por definición). Entonces,

sean x e y dos elementos de C ∗ y sea z = λx + (1 − λ)y con λ ∈ [0, 1]. Tenemos
T que ∀i ∈ I,
x ∈ Ci , y ∈ Ci , entonces, por la convexidad de Ci , z ∈ Ci . Por tanto, z ∈ i∈I Ci = C ∗ .


Definición 2.14. Dado un conjunto convexo C, Decimos que z ∈ C es un vértice o punto

extremo de C si no existen dos puntos distintos x, y en C tales que z = λx + (1 − λ)y
con λ ∈ (0, 1). En particular, z = x = y.

Definición 2.15. Un poliedro convexo es una intersección finita de semiespacios cerrados.

Observación 2.16. Es fácil de demostrar que, dada una matriz A ∈ Mm×n (R), b ∈ Rm ,
la región factible F = {x | Ax = b, x ≥ 0} de un problema de programación lineal, es un
poliedro convexo.

Definición 2.17. Se denomina politopo a la envoltura convexa de un número finito de

puntos.

Observación 2.18. Por definición, todo politopo es un conjunto acotado y es fácil de

demostrar que todo poliedro acotado es un politopo y viceversa.

Teorema 2.19. (Equivalencia de puntos extremos y soluciones básicas). Sea A una matriz
m × n de rango m, b ∈ Rm . Sea K el poliedro convexo formado por todos los vectores
x ∈ Rn que satisfacen
Ax = b
(2.8)
x ≥ 0.
Un vector x es un punto extremo de K si, y sólo si, x es una solución básica factible de
(2.8).

Dem.: Si xT = (x1 , x2 , . . . , xm , 0, 0, . . . , 0) una solución básica fatible de 2.8. Entonces,

x1 a1 + x2 a2 + · · · + xm am = b,

donde a1 , a2 , . . . , am , las m primeras columnas de A, son linealmente independientes.

Supongamos ahora que x puede formularse como una combinación convexa de dos puntos
distintos en K, por ejemplo, x = αy + (1 − α)z, 0 < α < 1, y 6= z. Como todas las
componentes de x, y, z son ≥ 0 y además 0 < α < 1, el resultado inmediato es que las
últimas n − m componentes de y y z son cero. Ası́, se tiene en especial

y1 a1 + y2 a2 + · · · + ym am = b

y
z1 a1 + z2 a2 + · · · + zm am = b.
Sin embargo, como los vectores a1 , a2 , . . . , am son linealmente independientes, se deduce
que x = y = z y, en consecuencia, x es un punto extremo de K.

8
 Recı́procamente, sea x un punto extremo de K. Supongamos que las componentes
distintas de cero de x son las p primeras componentes. Entonces,

x1 a1 + x2 a2 + · · · + xp ap = b,

con xi > 0, i = 1, 2, . . . , p.
Para demostrar que x es una solución básica factible, debe demostrarse que los vectores
a1 , a2 , . . . , ap son linealmente independientes.
Esto se hace por contradicción. Supongamos por tanto que a1 , a2 , . . . , ap son lineal-
mente dependientes. Entonces existe una combinación lineal no trivial igual a cero:

y1 a1 + y2 a2 + · · · + yp ap = 0.

Siendo y T = (y1 , y2 , . . . , yp , 0, 0, . . . , 0), y ∈ Rn . Como xi > 0, 1 ≤ i ≤ p, podemos

seleccionar  tal que
x + y ≥ 0, x − y ≥ 0.
Se tiene entonces que x = 21 (x + y) + 12 (x − y), que describe a x como una combinación
convexa de dos puntos distintos de K, lo que no puede ser, pues x es un punto extremo de
K. Ası́, a1 , a2 , . . . , ap son linealmente independientes y x es una solución básica factible.
(Aunque si p < m, es una solución básica factible degenerada.)


Corolario 2.20. Si existe una solución óptima finita en un problema de programación

lineal, existe una solución óptima en un punto extremo.

Dem.: En particular una solución óptima es una solución básica factible. 

Corolario 2.21. Si el conjunto convexo K correspondiente a (2.8) es no vacı́o, entonces

tiene al menos un punto extremo.

Dem.: Esto resulta de la primera parte del teorema (2.8) y del teorema de la equivalencia
anterior. 

Corolario 2.22. El conjunto K convexo correspondiente a (2.8) tiene a lo sumo un

número finito puntos extremos.

Dem.: Obviamente al seleccionar m vectores básicos de las n columnas de A, se obtiene

un número finito de soluciones básicas. Los vértices de K son un subconjunto de estas
soluciones básicas. 

2.4. El método del sı́mplex

Para la elaboración de este apartado principalmente se han seguido los capı́tulos 3 y 4

de [1]. Alguno de los subapartados se han completado con ideas extraı́das de [3], [4], [5],
[6] y [7].

El método del sı́mplex se basa en ir pasando de una solución básica factible (i.e un
punto extremo) a otra, hasta encontrar un punto extremo óptimo. Los resultados vistos
hasta ahora aseguran que para buscar una solución óptima es suficiente con considerar
sólo las soluciones básicas factibles.

9
Observación 2.23. Para un problema con n variables y m restricciones hay a lo sumo
 
n n!
=
m m!(n − m)!

soluciones básicas (que corresponden al número de formas de seleccionar m de n colum-

nas). Es por eso que dado un problema grande, una solución de búsqueda exhaustiva harı́a
el problema inabordable.

Por tanto, es conveniente buscar una forma más eficiente de movernos entre puntos
extremos de la región factible, o lo que es lo mismo, una forma eficiente de gestionar los
cambios de base. Esto es precisamente lo que intenta el método del sı́mplex.

2.4.1. Formulación general del método del sı́mplex.

consideremos el siguiente problema de programación lineal en forma estándar:

minimizar cT x
sujeto a Ax = b (2.9)
x≥0

donde x, c ∈ Rn , b ∈ Rm y A ∈ Mm×n (R) de rango m, con m ≤ n.

Dada una base B con una solución básica factible asociada x = (xB , xN ) = (B −1 b, 0) y
cuya función objetivo está dada por zB , donde
   −1 
T xB B b
T
zB = c x = c = (cB , cN ) = cTB B −1 b
xN 0

Denotemos por J al conjunto de los ı́ndices de las variables no básicas, es decir, las colum-
nas de A que no están en la base B, y para cada columna aj de A, definimos yj := B −1 aj .
Entonces, si ponemos aj como combinación lineal de las columnas de las base B, obtene-
mos que el coeficiente de la columna i de B es precisamente yij .
Dado que (xB , xN ) es una solución basica factible tenemos que xB ≥ 0, xN = 0 y
b = Ax = BxB + N xN . Despejando xB en la ecuación anterior obtenemos

xB =B −1 b − B −1 N xN
X
=B −1 b − B −1 aj xj
j∈J
X
=B −1 b − yj xj .
j∈J

Esta ecuación refleja como cambiará xB = B −1 b si alguna componente de xN pasa a ser

distinta de cero y al mismo tiempo queremos respetar las restricciones Ax = b. Además
si queremos encontrar una solución factible que mejore la función objetivo, también de-
beremos asegurar que respetamos las restricciones de no negatividad.

10
 Entonces, trasladando esto a la función objetivo y definiendo zj := cTB yj tenemos que,
dado x ∈ Rn cualquiera,

z = cT x =cTB xB + cTN xN
 
X X
=cTB B −1 b − yj xj  + cj xj
j∈J j∈J
X
cTB yj − cj xj


=zB −
j∈J
X
=zB − (zj − cj ) xj .
j∈J
P
Por tanto para que z = zB − j∈J (zj − cj ) xj sea menor que zB necesitamos que algún
(zj − cj ) > 0 7 . Es decir, dada una solución básica factible (xB , xN ), tenemos lo siguiente:

si zj − cj ≤ 0 para toda variable no básica j, entonces x = (xB , xN ) és una solución

óptima.

zj − cj > 0 para alguna variable no básica j, entonces la variable j es candidata a

entrar a formar parte de la base. En dicho caso, el vector yj = B −1 aj me permite
saber cómo varı́an las variables de la base actual a medida que aumento el valor de
xj .

El análisis que acabamos de desarrollar también nos permite identificar cuando estamos
ante un problema sin óptimo finito. Supongamos que tenemos una variable no básica
k ∈ J para la cual zk − ck > 0 y que, al mismo tiempo, el vector yk = B −1 ak tiene todas
sus componentes menores o iguales que cero. Esto nos estarı́a diciendo que, a medida que
aumentamos el valor de xk , el cambio inducido en las variables de la base (para mantener
factibilidad) es tal que ninguna de ellas reduce su valor (B −1 b − yk xk ≥ B −1 b ≥ 0).
Por tanto podemos aumentar xk indefinidamente sin perder factibilidad y mejorando la
función objetivo a cada paso.

2.4.2. Esquema general del método del sı́mplex

Presentamos el método del sı́mplex suponiendo que estamos ante un problema de

programación lineal en forma estándar.

Algoritmo (Sı́mplex).

Paso 0. En la forma estándard, determinamos una base B que tiene asociada una solución
básica factible x = (xB , xN ), con xB = B −1 b y xN = 0. Además, zB = cTB B −1 b.

Paso 1. Calculamos los valores zj − cj para todas las variables no básicas j ∈ J, donde
zj = cTB B −1 aj = cTB yj . Tenemos las siguientes posibilidades:

si zj − cj ≤ 0 ∀j, FIN. La solución básica factible x = (xB , xN ) és óptima.

7
En general, la cantidad cj −zj se denomina coste reducido de la variable j, pues en caso que zj −cj > 0
nos indica cuánto tendrı́a que reducirse el coste cj para que nos interesase que j entrase en la base

11
 Si ∃ j tal que zj − cj > 0. Sea k ∈ J el menor ı́ndice tal que zk − ck =
máxj∈J {zj − cj }. Ir al Paso 2 con k como variable de entrada.

Paso 2. Calculamos yk = B −1 ak . Tememos las siguientes posibilidades:

si yk ≤ 0, FIN. El problema no tiene óptimo finito.

Si yk 6≤ 0, entonces ak entra en la base y xk pasa a ser una variable básica.
Abandona la base la variable i con el ı́ndice menor:
 
(xB )i (xB )r
= mı́n : yrk > 0 .
yik 1≤r≤m yrk

Recalcular B, x = (xB , xN ), zB y los vectores yj . Volver al Paso 1.

2.4.3. Convergencia del método del sı́mplex

El estudio de la convergencia del método del sı́mplex está relacionada con la existencia
o no de soluciones básicas degeneradas. Cuando una de las variables básicas toma el valor
cero, implica que distintas bases representan al mismo punto extremo de la región factible
y por tanto cuando se aplica el algoritmo (sı́mplex) hay distintos cambios de base que
pueden no mejorar la función objetivo.

El siguiente resultado nos muestra la convergencia del método en ausencia de soluciones

degeneradas.8

Teorema 2.24. Dado un problema de programación lineal en forma estándar sin solu-
ciones básicas degeneradas, y dada una solución básica factible inicial , el método del
sı́mplex termina en una cantidad finita de pasos, bien encontrando una solución óptima
o concluyendo que no tiene solución óptima finita.

Dem.: En cada iteración del algoritmo pueden suceder tres cosas:

Si zj − cj ≤ 0 ∀j, el algoritmo termina pues estamos en una solución básica factible

óptima.

Si existe k tal que zk − ck > 0 y, además, yk ≤ 0, entonces el algoritmo termina

concluyendo que no existe solución óptima finita.

si existe k tal que zk − ck > 0 y, además, yk 6≤ 0, se genera una nueva solu-

ción básica factible xT = (xB , xN ) con xB = B −1 b y xN = 0 siendo B la nueva
base resultante de la entrada de ak y la salida de xB i . En ausencia de degenera-
ción xB tiene
n todas sus componentes
o estrictamente mayores que cero, y por tanto,
(xB )r
mı́n1≤r≤m yrk : yrk > 0 > 0. Esta desigualdad, combinada con zk − ck > 0, im-
plica que la función objetivo decrece estrictamente en cada iteración y por tanto las
soluciones básicas factibles obtenidas por el algoritmo son todas distintas entre sı́.
Como el número total de dichas soluciones es finito el algoritmo terminará en una
cantidad finita de iteraciones.


8
En el apartado 2.4.6, se explica que se puede hacer bajo la presencia de soluciones degeneradas.

12
Observación 2.25. Si x ∈ Rn es una solución degenerada de un problema de programa-
ción lineal con las condiciones habituales y, x tiene p < m componentes positivas, entonces
n−p


podrı́an haber m−p soluciones básicas factibles diferentes correspondientes a x.

2.4.4. La tabla del método del sı́mplex

Vamos ahora a ilustrar un ejemplo del método del sı́mplex. Para hacerlo usaremos la
tabla del método del sı́mplex. La idea consiste en guardar en una tabla toda la informa-
ción relevante de cada iteración a modo de facilitar la actualización de la misma. Veamos
primero cómo funciona la tabla.

Supongamos que partimos de un problema en la forma estándar con una solución

básica factible asociada x = (xB , xN ). Además, para facilitar la exposición, si A = [B, N ]
supongamos que las m columnas de B se corresponden con las primeras m variables.
Recordamos que N denota la matriz formada por las columnas de las variables no básicas.
Por comodidad B −1 b = b. Entonces representaremos la tabla del sı́mplex de la siguiente
forma:

xB xN z
zj − cj 0 cTB B −1 N − cN cTB b

xB cB Im×m B −1 N b

Observamos que tenemos la información necesaria para realizar una iteración del méto-
do del sı́mplex. En forma menos compacta, tenemos

xB1 ··· xBr ··· xBm ··· xi ··· xk ··· z

zj − cj 0 ··· 0 ··· 0 ··· zi − ci · · · zk − ck · · · cTB b

xB1 cB1 1 ··· 0 ··· 0 ··· y1i ··· y1k ··· b1

.. .. .. .. .. .. .. ..
. . . . . . . .
xBr cBr 0 ··· 1 ··· 0 ··· yri ··· yrk ··· br
.. .. .. .. .. .. .. ..
. . . . . . . .
xBm cBm 0 ··· 0 ··· 1 ··· ymi ··· ymk ··· bm

Supongamos entonces que decidimos que la variable xk debe entrar en la base y la va-
riable xBr debe salir de la misma. Se asocia la nueva base a B̃. Las operaciones a realizar
sobre la tabla actual, deberı́an de ser las siguientes:

13
 se actualiza el vector cB , y los valores b de las variables básicas xB .
Se actualizan las columnas yi y la matriz Im×m pasa a ser B̃ −1 .
se actualizan los valores zj − cj y el valor de la función objetivo cTB b.

Obtendrı́amos de este modo la tabla asociada a la base B̃, y poder ası́ iterar el algoritmo
en caso de ser necesario.

veamos ahora un ejemplo del funcionamiento del algoritmo del sı́mplex mediante la
tabla.
Ejemplo 2.26. Consideremos el siguiente problema de programación lineal:
minimizar −4x1 − 2x2 + 6x3
sujeto a −x1 + x2 + 2x3 ≤ 8
6x1 + x2 + 7x3 ≤ 6
−5x1 + 6x3 ≤ 1
x≥0
el primer paso debe ser pasar el problema a forma estándar, lo que resulta en el problema:

minimizar −4x1 − 2x2 + 6x3

sujeto a −x1 + x2 + 2x3 + xs4 =8
+6x1 + x2 + 7x3 + xs5 =6
−5x1 + 6x3 + xs6 =1
x≥0

Paso 0. (Inicialización).
Determinamos B = (a4 , a5 , a6 ) = Im×m . x = (xB , xN )T es xB = B −1 b = (8, 6, 1)T y
xTN = (0, 0, 0), siendo x una solución básica factible.
Se calcula además el valor de la función objetivo zB = cTB xB = (0, 0, 0)xB = 0.

Iteración 1. Paso 1 . (Criterio de entrada). Calculamos los zj − cj :

B −1 a1 = y1 = (−1, 6, −5)T . Por tanto, z1 − c1 = cTB y1 − c1 = 0 − (−4) = 4 > 0.

B −1 a2 = y2 = (1, 1, 0)T . Por tanto, z2 − c2 = cTB y2 − c2 = 0 − (−2) = 2 > 0.
B −1 a3 = y3 = (2, 7, 6)T . Por tanto, z3 − c3 = cTB y3 − c3 = 0 − (6) = −6 < 0.

Entonces la tabla quedarı́a de la siguiente forma:

[Tabla 1](entra x1 , sale xs5 )

x1 x2 x3 xs4 xs5 xs6 z
zj − cj +4 +2 −6 0 0 0 0
cB xB
xs4 0 −1 1 2 1 0 0 8
xs5 0 6 1 7 0 1 0 6
xs6 0 −5 0 6 0 0 1 1

14
 El máximo se alcanza para k = 1 y es 4 > 0. Por tanto, tenemos que x1 es la candidata
a entrar en la base.

Paso 2 . (criterio de salida). como el vector y1 = (−1, 6, −5)T tiene una única com-
ponente positiva, que esta asociada con la variable xs5 , entonces esta sale de la base. La
columna a1 entra en la base y x1 pasa a ser una variable básica.
La nueva base es B1 = (a4 , a1 , a6 ), con lo que tenemos:
   
1 −1 0 1 0.17 0
B1 = 0 6 0 y B1−1 = 0 0.17 0 ,
0 −5 1 0 0.83 1

y entonces xB = B1−1 b = (9, 1, 6)T , xN = (0, 0, 0)T y zB1 = cB1 xB = (0, −4, 0)T xB =
−4.

Iteración 2. Paso 1 . (Criterio de entrada). Calculamos los zj − cj :

B1−1 a2 = y2 = (1.17, 0.17, 0.83)T y z2 − c2 = cTB y2 − c2 = −0.67 − (−2) = 1.33 > 0.

B1−1 a3 = y3 = (3.17, 1.17, 11.83)T y z3 − c3 = cTB y3 − c3 = −4.67 − (−6) = −10.67 <
0.
B1−1 a5 = y5 = (0.17, 0.17, 0.83)T y z5 − c5 = cTB y5 − c5 = −0.67 − (0) = −0.67 < 0.

La tabla quedarı́a de la siguiente forma:

[Tabla 2](entra x2 , sale x1 )

x1 x2 x3 xs4 xs5 xs6 z
zj − cj 0 +1.33 −10.67 0 −0.67 0 −4
cB xB
xs4 0 0 1.17 3.17 1 0.17 0 9
x1 −4 1 0.17 1.17 0 0.17 0 1
xs6 0 0 0.83 11.83 0 0.83 1 6

El máximo se alcanza para k = 2 y es 1.33 > 0. Por tanto, tenemos que x2 es la

candidata a entrar en la base.

Paso 2.(criterio de salida). como el vector y2 = (1.17, 0.17, 0.83)T tiene todas las com-
ponente positivas, tenemos que mı́n{ 1.917 , 0.117 , 0.683 } = 0.117 . Por tanto x1 sale de la base.
La nueva base es B2 = (a4 , a2 , a6 ), con lo que tenemos:
   
1 1 0 1 −1 0
B2 = 0 1 0 y B2−1 = 0 1 0 ,
0 0 1 0 0 1

y entonces xB = B2−1 b = (2, 6, 1)T , xN = (0, 0, 0)T y zB2 = cTB2 xB = (0, −2, 0)T xB =
−12.

15
 Iteración 3. Paso 1. (Criterio de entrada). Calculamos los zj − cj :

B2−1 a1 = y1 = (−7, 6, −5)T . Por tanto, z1 − c2 = cTB y1 − c1 = −12 − (−4) = −8 < 0.

B2−1 a3 = y3 = (−5, 7, 6)T . Por tanto, z3 − c3 = cTB y3 − c3 = −14 − (−6) = −20 < 0.

B2−1 a5 = y5 = (−1, 1, 0)T . Por tanto, z5 − c5 = cTB y5 − c5 = 2 − (0) = −2 < 0.

Entonces la tabla quedarı́a de la siguiente forma:

[Tabla 3](óptima)

x1 x2 x3 xs4 xs5 xs6 z

zj − cj −8 0 −20 0 −2 0 −12
cB xB
xs4 0 −7 0 −5 1 −1 0 2
x2 −2 6 1 7 0 1 0 6
xs6 0 −5 0 6 0 0 1 1

El máximo se alcanza para k = 5 y es −2 < 0. Por tanto, estamos ante una solución
óptima.
La solución óptima, expresada únicamente con las variables del problema original, viene
dada por (0, 6, 0) con valor óptimo −12.

2.4.5. Construcción de una solución básica factible inicial

Pasamos a ver ahora como generar una solución básica factible dado un programa
lineal. Si las condiciones del problema son de la forma Ax = b, x ≥ 0, con b ≥ 0 para
cada una de sus componentes, y la matriz de restricciones A contiene la matriz identidad
Im×m entonces el problema de encontrar una solución básica factible x = (xB , xN ) es
inmediato. Basta con seleccionar las columnas asociadas a dicha submatriz identidad y la
solución inicial será entonces xB = B −1 b = b ≥ 0 y xN = 0.

Observación 2.27. Si las condiciones del problema son Ax ≤ b y x ≥ 0, si pasamos

el problema a la forma estándar añadiendo variables de holgura como hemos visto en
la sección 2.1, entonces estarı́amos ante el mismo caso, siendo [A, I]x = b el problema
equivalente en forma estándar y xTB = (xsn+1 , · · · , xsn+m ).

Suponiendo que no estamos ante las condiciones anteriores, podemos usar el llamado
método de la M grande (o ”Big-M ”).
En la forma estándar, la idea del método consiste en añadir variables artificiales en tan-
tas restricciones como sea necesario para que la nueva matriz de restricciones contenga
la matriz identidad como submatriz, lo que nos pone nuevamente en las condiciones del
caso anterior. En la función objetivo se añade además una penalización de las variables
artificiales dado por una constante M suficientemente grande.

16
 consideremos el problema en la forma estándar
minimizar cT x
sujeto a Ax = b (2.10)
x ≥ 0,

donde para simplificar y sin perdida de generalidad, suponemos b ≥ 0, y le añadimos un

vector de variables artificiales xa y una penalización M a la función objetivo, de manera
que
Pn Pm
minimizar i=1 ci xi + M j=n+1 xaj
sujeto a Ax + xa = b (2.11)
x, xa ≥ 0.
Una vez introducida la penalización, mediante el método del sı́mplex, buscamos una
solución óptima para (2.11). Si el algoritmo termina y alguna de las variables artificiales
tienes valor positivo en la solución óptima, entonces sabremos que el problema original
(2.10) no tenı́a soluciones factibles.
Observación 2.28. Las variables artificiales aumentan el conjunto de soluciones factibles
del problema original. De hecho, toda solución factible del problema original se puede
representar como una solución factible del problema ampliado en el que todas las variables
artificiales valen 0.

Veamos a continuación un ejemplo de como encontrar una solución básica factible

usando el método de la M grande.
Ejemplo 2.29. Supongamos que tenemos el siguiente problema de programación lineal

minimizar 3x1 − 3x2 + 3x3 − 4x4

sujeto a −x1 + x2 − 6x3 ≥1
5x1 + 2x2 + 2x3 − x4 ≥7
−x1 + 3x2 − x3 + 2x4 ≤7
x ≥ 0.
Si lo pasamos a forma estándar, obtenemos

minimizar 3x1 − 3x2 + 3x3 − 4x4

sujeto a −x1 + x2 − 6x3 −xs5 =1
5x1 + 2x2 + 2x3 − x4 −xs6 =7
−x1 + 3x2 − x3 + 2x4 +xs7 =7
x ≥ 0.

Si consideramos la matriz de coeficientes A = (a1 , · · · , a7 ), observamos que la columna

a7 se corresponde con el vector (0, 0, 1), pero todavı́a nos faltan las columnas (1, 0, 0) y
(0, 1, 0) para que se cumpla que la matriz identidad es una submatriz de A. Siguiendo el
método de la M grande, añadiendo las variables artificiales xa8 y xa9 nos queda el problema

minimizar 3x1 − 3x2 + 3x3 − 4x4 +M xa8 +M xa9

sujeto a −x1 + x2 − 6x3 −xs5 +xa8 =1
5x1 + 2x2 + 2x3 − x4 s
−x6 +xa9 =7
−x1 + 3x2 − x3 + 2x4 s
+x7 =7
x ≥ 0.

17
 De este modo podrı́amos tomar como base inicial B = (a7 , a8 , a9 ) con solución asocia-
da xTB = (7, 1, 7) y xN = 0.
Llegados ha este punto, habrı́a que iterar el método del sı́mplex y ver si en la solución ópti-
ma todas las variables artificiales se han hecho cero o no para decidir si se ha encontrado
una solución óptima del problema original o éste no tenia soluciones factibles.

2.4.6. Reglas de prevención de ciclo

Hasta ahora hemos podido ver la convergencia del método del sı́mplex bajo condiciones
de no degeneración. Ante la presencia de soluciones básicas degeneradas, existen métodos
diversos para evitar un posible ciclo durante el desarrollo del sı́mplex, garantizando ası́
la convergencia del método. En este apartado nos centraremos en la regla lexicográfica;
consiste en establecer un criterio para escoger la variable de salida de la base en cada ite-
ración del método del sı́mplex, asegurando que no exista la posibilidad de repetir ninguna
base a lo largo del proceso.

Sea x = (xB , xN ) una solución básica factible con base B asociada. supongamos que
xk es la variable escogida para entrar en la base. Entonces, para determinar la variable
que abandona la base calculan los ı́ndices de las variables candidatas con el criterio ya
expuesto en el Paso 2. del algoritmo (sı́mplex):
  
(xB )i (xB )r
I0 = i : = mı́n : yrk > 0 .
yik 1≤r≤m yrk

Si de aquı́ se deduce que solo hay una variable candidata, se elige ésta. En caso de
existir más de una candidata, se calculan los ı́ndices:
  
yi1 yr1
I1 = i : = mı́n .
yik r∈I0 yrk

De nuevo, si podemos deducir que solo hay una variable candidata, se elige esta. De
otra forma, se repite el proceso. Generalizando tenemos
  
yij yrj
Ij = i : = mı́n ,
yik r∈Ij−1 yrk

con j ≤ m. Llegando a un único ı́ndice para alguno de los Ij .

Nos asegurarı́amos ası́ de no repetir ninguna base en el desarrollo del sı́mplex . No
vamos a ha hacer una demostración formal de este hecho.

18
2.5. Dualidad

A todo problema de programación lineal le podemos asociar un nuevo problema de

programación lineal, conocido como problema dual. Este nuevo problema tiene importan-
tes propiedades. En particular, puede ser usado para resolver el problema original, que
llamaremos primal durante esta sección.
Empezamos presentando la formulación dual de un problema de programación lineal en
forma estándar

Primal Dual
minimizar cT x maximizar λT b
(2.12)
sujeto a Ax = b sujeto a λT A ≤ cT
x≥0
Donde x, c ∈ Rn , b, λ ∈ Rm y A ∈ Mm×n (R), con m ≤ n. x es la variable del problema
primal y λ es la variable del problema dual.

En esta sección no se supone que A sea de rango completo. Veamos a continuación

algunas relaciones entre el problema primal y su dual:

Si el primal es un problema de minimización, entonces el dual lo es de maximización

(y viceversa).

La matriz del problema dual es la matriz traspuesta AT del problema primal.

(λT A = cT es equivalente a AT λ = c).

Cada variable del primal corresponde con una restricción del dual.

Cada restricción del primal se corresponde con una variable del dual.

El vector b de términos independientes del primal pasa a ser el vector de coeficientes

de la función objetivo del dual.

El vector c de coeficientes de la función objetivo del primal pasa a ser el vector de

términos independientes del dual.

Restricciones de igualdad pasan a variables no restringidas y restricciones de mayor

o igual pasan a variables no negativas.

La siguiente tabla resume las principales relaciones entre el primal y el dual:

P rimal Dual
≥0 ←→ ≤
Variables ≤0 ←→ ≥ Restricciones
no restr. ←→ =
≥ ←→ ≥0
Restricciones ≤ ←→ ≤0 Variables
= ←→ no restr.

19
Proposición 2.30. El dual del dual coincide con el primal.

Dem.: Sea el dual de un problema de programación lineal en forma estándar, es decir:

máx λT b
sujeto a λT A ≤ cT
Se expresa de forma equivalente

−mı́n −bT (u − v)
sujeto a −AT (u − v) ≥ −c
u≥0
v≥0
donde hemos considerado que λ = u − v. Además podemos expresar
 
T T T

u
−b (u − v) = −b , b
v
y  
T

u T T
−A (u − v) = −A , A
v
Entonces, el dual correspondiente es

−máx −y T c
sujeto a y T (−AT , AT ) ≤ (−bT , bT )
y ≥ 0,
que a su vez es equivalente a
mı́n cT y
sujeto a Ay = b
y≥0
que efectivamente coincide con el primal en su forma estándar. 

Para facilitar la exposición presentaremos siempre el problema primal como un pro-

blema de minimización y el dual como un problema de maximización.

2.5.1. Dualidad débil y dualidad fuerte

Empezamos este apartado presentando otra relación importante entre el primal y el

dual. Supongamos sin pérdida de generalidad, que tenemos la formulación dual de un
problema primal expresado en forma estándar como en (2.12).
Proposición 2.31 (Dualidad débil). Sean x, λ factibles para el problema primal y dual
respectivamente de (2.12), entonces se verifica cT x ≥ λT b.

Dem.: Se tiene
λT b = λT Ax ≤ cT x,
siendo válida la última desigualdad, porque x ≥ 0 y λT A ≤ cT . 

20
 Este resultado tiene varias implicaciones prácticas. La primera de ellas es que un vector
factible para uno de los problemas da lugar a una cota en el valor del otro. Los valores
asociados al primal son mayores que los asociados al dual.
De esta proposición se deriva de forma inmediata el siguiente corolario.
Corolario 2.32. Si x∗ y λ∗ son soluciones factibles del primal y del dual tales que cT x∗ =
(λ∗ )T b, entonces x∗ y λ∗ son soluciones optimas del primal y dual, respectivamente.

A continuación vamos a ver la demostración del teorema de dualidad fuerte, utilizando

las caracterı́sticas del método del sı́mplex.

Teorema 2.33 (Dualidad fuerte). Dada la formulación dual de un problema de pro-

gramación lineal en forma estándar, Si uno de los problemas primal o dual tiene una
solución optima finita, también la tiene el otro, y los valores correspondientes de las fun-
ciones objetivo coinciden.
Si la función objetivo de uno de ellos es no acotada, el otro no tiene soluciones factible.

Dem.: Observemos que el segundo enunciado es una consecuencia directa de la dualidad

débil, ya que si el primal no está acotado y λ es factible para el dual, se debe tener
λT b ≤ −M para una M arbitrariamente grande, lo cual evidentemente, es imposible.
Supongamos ahora, que para el programa lineal en forma estándar

minimizar cT x
sujeto a Ax = b (2.13)
x ≥ 0,

se tiene la solución óptima x∗ = (xB , 0) con la base B correspondiente.

Entonces, queremos determinar una solución del problema dual

maximizar λT b
(2.14)
sujeto a λT A ≤ cT

en función de B.
Se divide A como A = [B, N ]. Como la solución básica factible xB = B −1 b es óptima,
entonces de la sección (2.4.1) sabemos que zj − cj ≤ 0 para toda variable no básica j, que,
es equivalente a cTB B −1 aj − cj ≤ 0 y por tanto resulta cTB B −1 N ≤ cTN .

Ahora, definimos λT = cTB B −1 . Demostramos que esta elección de λ resuelve el pro-

blema dual. Tenemos

λT A = λT B, λT N = cTB , cTB B −1 N ≤ cTB , cTN = cT .

     

Ası́, como λT A ≤ cT , λ es factible para el dual. Por otro lado,

λT b = cTB B −1 b = cTB xB ,

y el valor de la función objetivo dual para esta λ es igual al valor del problema primal.
Por tanto por la dualidad débil, queda establecida la optimalidad de λ para el dual.


De este teorema, se deriva de forma inmediata el siguiente corolario:

21
Corolario 2.34. Sea x∗ solución óptima con base B asociada de un programa lineal en
forma estándar como el de (2.12), entonces

λT = cTB B −1

es una solución óptima del problema dual.

Observación 2.35. De la demostración del teorema de dualidad fuerte, se deduce que

si una solución cumple las condiciones de optimalidad del primal (i.e, zj − cj ≤ 0), au-
tomáticamente es factible en el dual (sea factible o no para el primal).

2.5.2. Holguras complementarias

Pasamos a ver ahora la relación existente entre las soluciones óptimas de los problemas
primal y dual. Presentamos entonces el teorema de holguras complementarias, ofreciendo
ası́ una caracterización de las soluciones óptimas de dichos problemas.
Para el teorema nos basaremos la formulación canónica de un problema de programación
lineal y su dual, es decir en el par:

Primal Dual
minimizar cT x maximizar λT b
(2.15)
sujeto a Ax ≥ b sujeto a λT A ≤ cT
x≥0 λT ≥ 0.

Teorema 2.36. (Teorema de las holguras complementarias). Sean x y λ soluciones fac-

tibles de un problema de programación lineal en forma canónica y su formulación dual
(como por ej. (2.15)) , respectivamente. Entonces, x y λ forman un par de soluciones
óptimas si y sólo si

λi (a(i) x − bi ) = 0 ∀i ∈ {1, . . . , m}, 9 (2.16)

(cj − λT aj )xj = 0 ∀j ∈ {1, . . . , n}. (2.17)

Dem.: Definimos,
ui := λi (a(i) x − bi ) ∀i ∈ {1, . . . , m},
y
vj := (cj − λT aj )xj ∀j ∈ {1, . . . , n}.

Claramente de las relaciones entre el primal y el dual tenemos que ∀i ∈ {1, . . . , m}

ui ≥ 0 y ∀j ∈ {1, . . . , n}
Pvmj ≥ 0.
Definimos ahora U := i=1 ui y V := ni=1 vi . Entonces, U = V = 0 si y sólo se cumplen
P
(2.16) y (2.17). Además,
m
X n
X
U +V = ui + vi = cT x + λT Ax − λT Ax − λT b = cT x − λT b.
i=1 i=1

Finalmente, se verifican (2.16) y (2.17) si y sólo si U + V = 0 (⇔ cT x = λT b), que, por

el corolario (2.32), sabemos que es una condición necesaria y suficiente tales que tanto x
como λ sean soluciones óptimas del primal y dual, respectivamente. 
9 (i)
a representa la fila i de la matriz Am×n .

22
Observación 2.37. El resultado que acabamos de ver, implica que dadas un par de solu-
ciones óptimas x y λ, si una restricción del dual no se satura10 , entonces la correspondiente
variable del primal es 0 (i.e cj − λT aj > 0 ⇒ xj = 0).

2.5.3. Análisis de sensibilidad

El análisis de sensibilidad nos permite estudiar como variaciones en los parámetros

del problema de partida se traducen en variaciones sobre la solución óptima y función
objetivo del problema asociado.
Supongamos que dado el problema (2.15), conocemos una base óptima B del problema
primal. Además, para facilitar la exposición, asumiremos que la solución básica óptima
asociada, x es no degenerada. Del corolario (2.34) sabemos que λT = cTB B −1 es una solu-
ción óptima del dual. Si denotamos J como el conjunto de variables no básicas, sabemos
también de la sección (2.4.1) que
X X
z = cTB B −1 b − (zj − cj ) xj = λT b − (zj − cj ) xj .
j∈J j∈J

Como estamos asumiendo que la solución es no degenerada, tenemos que xB = B −1 b > 0,

con lo que si perturbásemos ligeramente el vector b, seguirı́amos teniendo una solución
básica factible asociada a la base B. Para ver el cambio de dicha perturbación en b, si
definimos z̄ = λT b = cTB B −1 b, tenemos que

∂ z̄
= λi .
∂bi

Es decir, λi nos da la tasa de variación de la función objetivo ante una perturbación

en bi . Como λi > 0, aumentando el valor de bi la función objetivo empeora (aumenta), y
análogamente mejora si reducimos bi .
Relacionando la presentación que acabamos de hacer con el teorema de holguras com-
plementarias, podemos interpretar que cuando una restricción no se satura, no tenemos
nada que ganar y por eso la variable dual asociada es 0.

El estudio de las perturbaciones sobre el vector c es similar a la exposición que aca-

bamos de ver; de hecho el vector c en el dual se comporta como el vector b en el primal.
Por lo general si perturbamos c en el primal podemos tener pérdida de optimalidad, pero
nunca a pérdida de factibilidad. Una manera de ver como ha cambiado el valor óptimo
cT x después de perturbar el vector c, serı́a iterando el método del sı́mplex en el propio
primal a partir de la solución óptima anterior.

Aunque no vamos a ofrecer un análisis detallado, supongamos ahora que quisiéramos

realizar alguna perturbación sobre la matriz A de restricciones. Distinguimos dos casos:

Cambios en una columna no básica. Si perturbamos una de las columnas no

básicas de la matriz A, por ejemplo cambiando ai por âj , solamente se verı́a afectada
10
Decimos que una restricción esta saturada en x, si se cumple a(i) x = bi donde x ∈ F con F la región
factible de un programa lineal.

23
 la columna correspondiente de la tabla11 incluyendo el zj − cj correspondiente. Para
este caso serı́a suficiente con recalcular la columna B −1 âj y obtener ẑj − cj =
CBT B −1 â − c . Si ẑ − c ≤ 0 mantenemos optimalidad y nada cambia. En caso
j j j j
contrario habrı́a que iterar el método del s´simplex hasta recuperar optimalidad (la
columna j entrarı́a en la base).

Cambios en una columna básica. El cambió sobre una columna básica, puede
implicar que tengamos dependencia de la matriz B, y por tanto dejemos de tener
una base. Pero aun sin perder la independencia de la base, cambiarı́a B −1 y eso
podrı́a provocar que cambien todas las columnas de la tabla del sı́mplex.

Ilustramos con un ejemplo simple los cambios que se producen en un programa lineal
tras aplicar alguna perturbación en el vector b:
Ejemplo 2.38. Consideremos el problema

minimizar −2x1 − 3x2 − 4x3

sujeto a x1 + 2x2 + 3x3 ≤ 11
2x1 + 3x2 + 2x3 ≤ 10
x ≥ 0.

Si lo resolviendo mediante la tabla del sı́mplex, obtendremos la tabla óptima:

[Tabla](óptima)

x1 x2 x3 xs4 xs5 z
zj − cj 0 − 12 0 −1 − 21 −16
cB xB
1 1
x3 −4 0 4 1 2 − 41 3
5
x1 −2 1 4 0 − 21 3
4 2

con xB = (3, 2) y valor óptimo z = −16.

De forma general, supongamos que perturbamos una de las componentes del vector b
de forma que b̂ = b + (0, . . . , 0, ∆bi , 0, . . . , 0)T . Si Bi−1 es la columna i de B −1 , queremos
encontrar las condiciones que nos aseguren,

x̂B = B −1 b̂ = B −1 b + Bi−1 ∆bi ≥ 0.

Es decir que mantenemos la factibilidad y, por lo tanto, como los zj − cj no cambian,

mantenemos también optimalidad.
Veamos ahora entonces qué pasa si en el problema dado realizamos cambios en b1 :
1 −1
!
2 4
de la tabla, tenemos que B −1 = −1 3
, y por lo tanto
2 4

3 + ∆b1 /2 ≥ 0 ⇒ ∆b1 ≥ −6
B −1
b+ Bi−1 ∆bi = (3, 2) + (1/2, −1/2)∆b1 ≥ 0 ⇒
2 − ∆b1 /2 ≥ 0 ⇒ ∆b1 ≤ 4.
11
Nos referimos a la tabla del método del sı́mplex; se puede encontrar información mas detallada en la
sección 2.4.4.

24
Es decir, si ∆b1 ∈ [−6, 4] se mantiene la factibilidad para x̂B . Equivalentemente, podemos
variar b1 en el intervalo [11 − 6, 11 + 4] = [5, 15].
Observamos además, si λT es una solución óptima del dual, entonces

λT = cTB B −1 = (−4, −2)B −1 = (−1, −1/2).

Por cada unidad en que aumentemos b1 dentro de [5, 15], la función objetivo se verá
reducida en λ1 = −1 unidad; si por ejemplo tenemos b̂ = (12, 10), entonces el valor
óptimo de la función objetivo pasa a ser ẑ = −17.
Realizando el mismo análisis para b2 , la tasa de variación de la función objetivo serı́a
λ2 = −1/2.12

2.5.4. Formulación del algoritmo primal-dual

El algoritmo primal-dual es una variante del método del sı́mplex, que consiste en resol-
ver un problema de programación lineal operando de forma simultanea en los problemas
primal y dual.
Consideremos un problema de programación lineal en forma estándar y su formulación
dual como el que sigue, con las condiciones habituales:

Primal Dual
minimizar cT x maximizar λT b
sujeto a Ax = b sujeto a λT A ≤ cT
x≥0

Para facilitar la exposición nos referiremos a los problemas primal y dual como P y
D respectivamente. En el algoritmo primal-dual, primero es necesario disponer de una
solución factible λ para D, que se puede obtener del siguiente modo:

Si c ≥ 0, entonces λ = 0 solución factible de D.

Si ∃j con cj < 0, entonces añadimos al problema P una variable xn+1 junto a la

restricción x1 + x2 + · · · + xn + xn+1 = bm+1 ; donde bm+1 > máx1≤i≤n {xi } para
cualquier posible valor de las variables x1 , . . . , xn .13
El nuevo problema dual tendrá una variable λm+1 y se formulará de la siguiente
forma:
maximizar λT b + λm+1 bm+1
sujeto a λT aj + λm+1 ≤ cj (j ∈ {1, . . . , n + 1})
λm+1 ≤ 0.
Escogiendo λ = (0, 0, . . . , 0, ĉ)T con ĉ = mı́n {ci | ci < 0}, tenemos que λ es una
solución factible de este problema (pues ĉ < 0).

Supongamos entonces que disponemos de una solución λ factible para D. Si encontra-

mos una solución x factible14 de P, tal que xj = 0 ∀j con cj − λT aj > 0, por el teorema
de las holguras complementarias, tanto x como λ serı́an óptimos15 .
12
Los zj − cj asociados a las variables de holgura coinciden con la solución óptima del problema dual,
pues zj = cTB B −1 ej y cj = 0.
13
una cota para este valor se puede encontrar fácilmente a partir de la matriz A.
14
Obsérvese que si x es factible para P, automáticamente se cumplirı́a la ecuación λi (a(i) x − bi ) = 0 del
teorema de las holguras complementarias.
15
El algoritmo primal-dual, se basa precisamente buscar una solución x que cumpla dichas condiciones.

25
En este caso, para nuestra solución λ tendremos que algunas de las restricciones de la
forma λT ai ≤ ci estarán saturadas. Definimos el conjunto

KA := {k ∈ N | λT ak = ck }, para N = {1, . . . , n}.

Entonces una solución factible x de P será óptima si y sólo si para todo k ∈

/ KA , xk = 0.
Por tanto, sera suficiente encontrar una solución factible verificando

X
ak xk = b
k∈kA (2.18)
xk ≥ 0 k ∈ KA
xj = 0 j∈/ KA .
Nos referiremos a KA como el conjunto de columnas activas 16 . Para buscar una solución
de (2.18) consideremos una versión restringida de P que llamaremos RP, y que es de la
forma:

m
X
minimizar xai
i=1
X
sujeto a ak xk + xa = b
k∈KA
xk ≥ 0 k ∈ KA
xj = 0 j∈/ KA
xai ≥ 0 i ∈ {1, . . . , m}.

En el cual se ha introducido un vector de variables artificiales xa = (xa1 , . . . , xam ), de

dimensión m. Una componente en cada restricción de P. Partiendo de xai = bi optimiza-
mos.

Si el valor óptimo de RP es 0, entonces x verifica (2.18) y consecuentemente x es

solución óptima de P.

Si el valor óptimo de RP es mayor que 0, en este caso no existe solución en el primal

que verifique las condiciones de holguras complementarias, y es necesario cambiar
λ. se procede del siguiente modo con la formulación del dual de RP, que llamaremos
DRP. Entonces DRP será:
maximizar λT b
sujeto a λT ak ≤ 0 k ∈ KA
λi ≤ 1 i ∈ {1, . . . , m}.

Denotemos por µ el óptimo de DRP. Entonces se repite el procedimiento, pero

modificando λ por una combinación lineal de µ con el propio λ, esto es:

λ̄ = λ + ωµ.

Queremos ω que nos mantenga factibilidad en D, y que además mejore el valor

objetivo, λ̄T b = λT b + ωµT b. Como RP y RPD son un par primal-dual, tenemos
16
Observamos que las igualdades usan sólo columnas de A correspondientes con elementos de KA , que
provienen de las restricciones saturadas en D (para la solución λ).

26
 que µT b > 0 (ya que ha de coincidir con el óptimo de RP ). Entonces, si ω > 0 el
valor objetivo en D mejora.
Por otro lado para que λ̄ sea factible, necesariamente ∀i ∈ {1, . . . , n},

λ̄T ai = λT ai + ωµT ai ≤ ci .

Observamos que si ∀i ∈ {1, . . . , n}, µT ai ≤ 0, entonces podemos aumentar ω inde-

finidamente, y por tanto como D serı́a no acotado, consecuentemente P no tendrá
solución factible.
En otro caso, seleccionamos ω = ω̂ donde

ci − λT ai
 
ω̂ = mı́n .
/ A ,µT ai >0
i∈K µT ai

Se reemplaza λ por λ̄ y ası́ sucesivamente hasta que lleguemos a un problema en el

que el óptimo de RP es 0 o que nos permita asegurar que P no tiene soluciones factibles.

Observación 2.39. Bajo las condiciones del algoritmo primal-dual, se mantiene cons-
tantemente la factibilidad de λ en el dual.

2.5.5. Algoritmo primal-dual

El Algoritmo primal-dual, resulta de gran utilidad para situaciones en las que no

disponemos de una solución básica factible en el primal.
Para finalizar esta sección y teniendo en cuenta la exposición anterior, presentamos el
algoritmo primal-dual y posteriormente un breve análisis de la convergencia del mismo
seguido por un ejemplo.
Algoritmo (Primal-Dual).

Paso 1. Disponer de una solución factible λ del problema dual D.

Paso 2. Se define el conjunto KA asociado a λ y se resuelve el problema relajado primal

RP.

(i) Si el valor óptimo de RP es 0, la solución correspondiente x es óptima para

el problema primal P.
/ KA , µT aj ≤ 0, P no tiene soluciones
(ii) Si el valor óptimo de RP > 0 y, ∀j ∈
factibles.
(iii) En otro caso, λ pasa a ser λ̄, y se vuelve a empezar el Paso 2.

El método descrito converge puesto que si k̂ es el ı́ndice que determina la selección

de ω̂, entonces, tendremos que la columna k̂ pasará a ser activa puesto que λ̄T ak = ck̂ .
Suponiendo además ausencia de degeneración17 , el problema dual va mejorando a cada
iteración, con lo que eventualmente, se recorrerán todas las posibles combinaciones de
columnas activas y no activas.

Ilustramos el algoritmo con el siguiente ejemplo:

17
En caso de degeneración se podrı́a aplicar alguna regla que asegure que no se repite ninguna base
como ya se ha visto para el sı́mplex.

27
Ejemplo 2.40. Dado el problema (P ):

minimizar 2x1 + x2 + 4x3

sujeto a x1 + x2 + 2x3 = 3
2x1 + x2 − 3x3 = 5
x ≥ 0.

Iteración 1.
Lo primero que necesitamos es una solución factible del problema dual. Como tenemos
que c = (2, 1, 4)T ≥ 0, podemos considerar λ = (0, 0)T .
Paso 2.

KA = ∅. Para la versión restringida RP 1 , tenemos que la solución óptima es x =

(0, 0, 0, 3, 5)T con valor óptimo zRP 1 = 8 > 0.

La solución factible de DRP es µ = (1, 1)T . como se cumple ∃j ∈ / KA , µT aj > 0,

seguimos.
ω = mı́n{ 23 , 21 } = 1/2 ⇒ λ̄ = (0, 0)T + 21 (1, 1)T = ( 12 , 12 )T .

Actualizamos λ = ( 12 , 21 )T . Volvemos a iterar el Paso 2.

Iteración 2.
Paso 2.

KA = {2}. Para la versión restringida RP 2 , tenemos que la solución óptima es

x = (0, x2 , 0, xa1 , xa1 )T con valor óptimo zRP 2 > 0.

La solución factible de DRP es µ = (−1, 1)T . como se cumple ∃j ∈ / KA , µT aj > 0,

seguimos.
ω = mı́n{ 12 , 23 } = 1/2 ⇒ λ̄ = ( 12 , 12 )T + 12 (−1, 1)T = (0, 1)T .

Actualizamos λ = (0, 1)T . Volvemos a iterar el Paso 2.

Iteración 3.
Paso 2.

KA = {1, 2}. Para la versión restringida RP 3 , tenemos que la solución óptima

es x = (2, 1, 0, 0, 0)T con valor óptimo zRP 3 = 0. Se termina; la solución óptima
correspondiente al primal es x∗ = (2, 1, 0)T .

28
3. Programación Entera

Las principales fuentes consultadas para este capı́tulo han sido [8] y [9].

Hasta ahora hemos visto modelos de programación lineal donde las variables podı́an
tomar cualquier valor real.
Vamos a considerar ahora, el problema de la forma:

minimizar cT x
sujeto a Ax = b
(3.1)
x≥0
x ∈ Zn

donde c ∈ Rn , b ∈ Rm y A ∈ Mm×n (R) de rango m, con m ≤ n.

A diferencia de un problema de programación lineal, las variables se restringen a valores
enteros. Este tipo de problemas se conocen como problemas de programación (lineal)
entera. Cuando algunas variables están restringidas a valores enteros y otras no, hablamos
de problemas de programación entera mixta.

Observación 3.1. La región factible de un problema de programación entera, es no

convexa.

Observación 3.2. Se podrı́a pensar en resolver el problema lineal asociado resultante

de relajar/eliminar la condición de que las variables sean enteras, para posteriormente
redondear la solución obtenida. Pero esta técnica rara vez ofrece buenos resultados.

Ilustramos la observación en el siguiente ejemplo:

Ejemplo 3.3.
minimizar −5x1 − 8x2
sujeto a x1 + x2 ≤ 6
5x1 + 9x2 ≤ 45
x≥0
x ∈ Z2

La solución óptima del problema relajado es x∗r = (2.25, 3.75) con valor objetivo zr =
−41.25. La solución óptima entera es x∗ = (0, 5), con valor objetivo z = −40. En este caso,
si intentásemos buscar una solución entera a partir de la solución óptima x∗r podrı́amos
probar de redondear la solución, obteniendo ası́ el punto (2, 4), que no es factible pues
2 · 5 + 9 · 4 = 46 > 45.

3.1. El método de Branch and Bound

El método Branch and Bound o Ramificación y Acotación, consiste en subdividir su-

cesivamente la región factible del problema de partida y resolver las versiones relajadas de
los problemas resultantes, hasta encontrar la solución óptima del problema. La subdivisión
se realiza de forma que sigue una estructura de árbol binario 18 .
18
De la teorı́a de grafos, sabemos que: Un árbol binario es un árbol no dirigido tal que el grado de cada
vértice es menor o igual a 3. Intuitivamente, es una estructura de datos formada por un nodo inicial, y
en la cual cada nodo puede tener hasta ”dos hijos”, que pasarı́an a ser dos nodos más.

29
3.1.1. Descripción del método Branch and Bound

Consideremos el siguiente problema de programación entera mixta:

minimizar cT x + dT y
sujeto a Ax + Gy = b
(3.2)
x, y ≥ 0
x ∈ Zn

donde d, y ∈ Rp , b ∈ Rm , c ∈ Rn , A ∈ Mm×n (R) y G ∈ Mm×p (R) ambas de rango m,

con m ≤ n. Para facilitar la exposición, vamos a denotar el problema como MILP (Mixed
Integer Linear Program),

MILP : mı́n cT x + dT y | (x, y) ∈ S



con S = (x, y) ∈ Zn+ × Rp+ | Ax + Gy = b .



Supongamos que el problema MILP dado admite la solución óptima (x∗ , y ∗ ) con valor
óptimo z ∗ .
Consideremos entonces la relajación del problema MILP, es decir

LP0 : mı́n cT x + dT y | (x, y) ∈ P0



con P0 = (x, y) ∈ Rn+ × Rp+ | Ax + Gy = b y supongamos que LP0 admite una solución


óptima (x, y) con valor óptimo z0 .

Como S ⊆ P0 , inmediatamente tenemos z∗ ≥ z0 . Además, si x es un vector entero,
entonces (x, y) ∈ S y por tanto z ∗ = z0 ; en este caso quedarı́a resuelto el MILP.
De no ser ası́, y siendo xT = (x1 , · · · , xn ) al menos una de las variables xj con j ∈
{1, · · · , n} serı́a no entera. Seleccionamos xj = f la variable no entera con j mı́nimo de
mejor potencial19 . Definimos entonces los conjuntos

S1 := S ∩ {(x, y) | xj ≤ bf c} , S2 := S ∩ {(x, y) | xj ≥ df e}

donde bf c denota al mayor entero menor o igual que f y df e denota al menor entero
mayor o igual que f . Tenemos que (S1 , S2 ) es una partición de S.
Consideramos ahora los dos siguientes problemas enteros mixtos basados en esta partición,

MILP1 : mı́n cT x + dT y | (x, y) ∈ S1 , MILP2 : mı́n cT x + dT y | (x, y) ∈ S2 .

 

La solución original del problema se ha reducido a resolver estos dos nuevos subproblemas.
Denotamos por P1 , P2 las relajaciones resultantes de S1 y S2 respectivamente. Esto es

P1 := P0 ∩ {(x, y) | xj ≤ bf c} , P2 := P0 ∩ {(x, y) | xj ≥ df e} ,

y consideramos,

LP1 : mı́n cT x + dT y | (x, y) ∈ P1 , LP2 : mı́n cT x + dT y | (x, y) ∈ P2 .

 

(i) Si uno de los LPi es infactible, i.e., Pi = ∅, entonces también tenemos Si = ∅ ya que
Si ⊆ Pi . Y por tanto como MILPi es infactible no lo necesitamos considerar más.
Decimos que el problema queda podado por infactibilidad.
19
Cconsideramos que xj tiene mejor potencial, si se cumple que cj f es mı́nimo)

30
 (ii) Sea (xi , y i ) una solución óptima de LPi con valor óptimo zi , para i = 1, 2.

(iia) Si xi es un vector entero, entonces (xi , y i ) es una solución óptima del problema
MILPi y una solución factible del problema MILP. El problema MILPi queda
solucionado, y decimos que queda podado por optimalidad. Como Si ⊆ S, le
sigue que zi ≥ z ∗ , esto es, zi es una cota superior del valor de MILP.
(iib) Si xi no es un vector entero, y zi es mayor o igual que el valor de la mejor cota
superior conocida del MILP, entonces Si no puede contener una solución mejor
y el problema queda podado por acotación.
(iic) Si xi no es un vector entero y zi es menor que el valor de la mejor cota superior
conocida, entonces Si aun puede contener una mejor solución óptima para el
MILP. Sea xij , la componente no entera de la solución xi tal que cj xij es
mı́nimo. Se define fi := xij y los conjuntos Si1 := Si ∩ {(x, y) | xij ≤ bfi c},
Si2 := S2 ∩ {(x, y) | xij ≥ dfi e} y se repite el proceso.

3.1.2. Esquema general del método Branch and Bound

El metodo de Branch and Bound que presentamos a continuación es para problemas

de minimización con región factible no vacı́a y acotada20 .
Cada Programa Lineal relajado, corresponde con un nodo del árbol de binario. Para un
nodo Nij 21 , se le asocia el valor óptimo zij del programa lineal LPij .
Denotaremos como L la lista de nodos que deban resolverse.

Algoritmo (Branch and Bound).

Paso 0. INICIALIZACIÓN.
Definimos L := {N0 }, la cota superior U B := +∞

Paso 1. PRINCIPAL.

Selecciona un nodo Nij en L y eliminarlo (L → L \ Nij ).

Resolver LPij . Si es infactible ir al Paso 2. De otro modo, sea (xi , y i ) la
solución óptima de LPij con valor óptimo zij .
Si x no es entera y U B ≤ zij descartamos nodo por acotación. Ir al Paso
2.
Si (xi , y i ) es factible para MILP y zij < U B definimos:

U B := zij

(x∗ , y ∗ ) := (xi , y i ).
Ir al Paso 2.
Desde LPi se construyen los dos problemas lineales LPkj , LPkj+1 y se añaden
a L los nodos Nkj y Nkj+1 correspondientes, donde k = i + 1. Ir al paso 1.
20
En caso de no tener región factible no vacı́a y acotada, el método puede no converger. Esto se puede
ver en el ejemplo (3.8).
21
El ı́ndice i representa cada nivel del árbol binario, mientras j representa la posición. Para cada nivel
i ≥ 0, pueden haber 2i nodos distintos.

31
Paso 2. CONTROL

Si L =
6 ∅ ir al Paso 1.
Si L = ∅, la solución (x∗ , y ∗ ) es óptima. Se termina.

Observación 3.4. En el Paso 1. la selección del nodo Ni queda abierta. Lo mas reco-
mendado es tomar aquel con mayor potencial, es decir aquel donde el valor óptimo del
nodo zi sea mı́nimo.

3.1.3. Convergencia del método Branch and Bound

Teorema 3.5. (Convergencia del Algorimo). Sea MILP un problema de programación

entera mixta en donde la región factible es no vacı́a y acotada, entonces el algoritmo de
Branch and Bound descrito anteriormente encuentra la solución óptima en una cantidad
finita de pasos.

Dem.: Presentamos la idea de la demostración.

Como la región factible es acotada, el número total de ramificaciones es finito. Esto, unido
a que el algoritmo no repite dos veces la misma ramificación, asegura la convergencia finita
del mismo (se puede ramificar varias veces sobre la misma variable, pero nunca será una
ramificación ya hecha).
Por otro lado, para ver que la convergencia se produce a un óptimo del problema entero, es
importante notar que los pasos de ramificación dividen la región factible del subproblema
actual de tal manera que solo se dejan fuera soluciones no enteras: xi en el intervalo
(bxic, dxi e). Por tanto nunca dejamos fuera soluciones factibles del MILP original. El
algoritmo termina cuando todo subproblema Nij creados en el transcurso del mismo está
en alguna de las siguientes situaciones:

(I) El subproblema LPij asociado a Nij ha sido resuelto y se ha encontrado el óptimo

entero del mismo.

(II) El potencial zij del subproblema asociado a Nij es tal que U B < zij con lo que
ninguna solución factible de Nij puede mejorar el valor U B obtenido.

Esto asegura que, entre las regiones factibles de todos los subproblemas explorados,
no hay ninguna solución que pueda mejorar U B. Lo cual, unido a que ninguna solución
factible del problema entero queda fuera de la unión de las regiones factibles de estos
subproblemas, asegura la optimalidad de U B. 

Observación 3.6. A pesar de tener garantizada la convergencia finita del algoritmo, se

trata de un algoritmo exponencial, y eso puede elevar considerablemente el tiempo de
resolución.
Si consideramos LB la cota mı́nima encontrada en un problema relajado, podemos tener
controlado en todo momento el porcentaje máximo de desviación con respecto al óptimo
mediante el cociente (U B − LB)/LB.

Veamos a continuación como se resolverı́a el problema del ejemplo (3.3) con el algoritmo
de Branch and Bound.

32
Ejemplo 3.7.
minimizar −5x1 − 8x2
sujeto a x1 + x2 ≤ 6
5x1 + 9x2 ≤ 45
x≥0
x ∈ Z2

Paso 0 . Inicialización.
Definimos L = {N0 }, LB = −∞, U B = +∞.

Iteración 1 Paso 1 . Principal.

L → L \ N0 (L = ∅).

Al resolver LP0 , obtenemos (x1 , x2 ) = (2.25, 3.75)T y z0 = −41.25 < U B = +∞.

Como c2 x2 = −30 < c1 x1 = −11.25, construimos los dos problemas correspon-

dientes LP11 y LP12 añadiendo las restricciones x2 ≤ 3 y x2 ≥ 4 respectivamente.
Actualizamos L = {N11 , N12 }.

Iteración 2 Paso 1 . Principal. Como el potencial de N11 y N12 es el mismo (−41.11).

Escogemos N11 por ser el de ı́ndice más bajo.

L → L \ N11 (L = {N12 }).

Al resolver LP11 , obtenemos (x1 , x2 ) = (2, 3)T y z11 = −34 < U B = +∞. Actuali-
zamos U B = −34.

Paso 2 . Control.

como L =
6 ∅, volvemos al Paso 1.

Iteración 3 Paso 1 . Principal.

L → L \ N12 (L = ∅).

Al resolver LP12 , obtenemos (x1 , x2 ) = (1.8, 4)T y z12 = −41 < U B = −34.

construimos los dos problemas correspondientes LP23 y LP24 añadiendo las restric-
ciones x1 ≤ 1 y x1 ≥ 2 respectivamente.. Actualizamos L = {N23 , N24 }.

Iteración 4 Paso 1 . Principal. Como el potencial de N23 y N24 es el mismo (−41).

Escogemos N23 por ser el de ı́ndice más bajo.

L → L \ N23 (L = {N24 }).

Al resolver LP23 , obtenemos (x1 , x2 ) = (1, 4.44)T y z23 = −40.56 < U B = −34.

33
 construimos los dos problemas correspondientes LP35 y LP36 añadiendo las restric-
ciones x2 ≤ 4 y x2 ≥ 5 respectivamente.. Actualizamos L = {N24 , N35 , N36 }.

Iteración 5 Paso 1 . Principal. Escogemos N24 por ser el nodo de mejor potencial
(−41).

L → L \ N24 (L = {N35 , N36 }).

Al resolver LP24 , obtenemos que el problema es infactible.

Paso 2 . Control.

como L =
6 ∅, volvemos al Paso 1.

Iteración 6 Paso 1 . Principal. Como el potencial de N35 y N36 es el mismo (−40.56).

Escogemos N35 por ser el de ı́ndice más bajo.

L → L \ N35 (L = {N36 }).

Al resolver LP35 , obtenemos (x1 , x2 ) = (1, 4)T y z35 = −37 < U B = −34. Actuali-
zamos U B = −34.

Paso 2 . Control.

como L =
6 ∅, volvemos al Paso 1.

Iteración 7 Paso 1 . Principal.

L → L \ N36 (L = ∅).

Al resolver LP36 , obtenemos (x1 , x2 ) = (0, 5)T y z36 = −40 < U B = −37. Actuali-
zamos U B = −40.

Paso 2 . Control.

como L = ∅, la solución (x∗1 , y2∗ ) = (0, 5)T es óptima. Fin

El siguiente diagrama muestra la evolución de los distintos nodos del algoritmo:

34
 N0

x2 ≤ 3 x2 ≥ 4

N11 N12

x1 ≤ 1 x1 ≥ 2

N23 N24

x2 ≤ 4 x2 ≥ 5

N35 N36

Figura 1: esquema del algoritmo Branch and Bound del ejemplo 3.7

Para finalizar esta sección vamos a ver un ejemplo donde la región factible del problema
relajado no cumple las condiciones del teorema (3.5) y entonces el algoritmo no converge.
Ejemplo 3.8. Consideremos el siguiente problema de programación entera.

minimizar x1 + x2
sujeto a 3x1 − 3x2 ≤ 2
3x1 − 3x2 ≥ 1 (3.3)
x ≥0
∈ Z2

Si aplicamos el algoritmo, obtenemos que la solución del problema relajado LP0 , es

(x1 , x2 ) = ( 13 , 0)T con z0 = 31 . Posteriormente se derivan los problemas LP11 y LP12
resultantes de añadir las restricciones x1 ≤ 0 y x1 ≥ 1 respectivamente.

LP11 es infactible por ser x1 ≤ −1.

Para LP12 , la solución óptima del problema es (x1 , x2 ) = (1, 31 )T con z12 = 34 .

Si seguimos iterando, se derivan los problemas LP23 y LP24 resultantes de añadir las
restricciones x2 ≤ 0 y x2 ≥ 1 respectivamente.

LP23 es infactible.
Para LP24 ,la solución óptima del problema es (x1 , x2 ) = ( 43 , 1)T con z24 = 73 .

A medida que vayamos iterando, iremos obteniendo soluciones de la forma (n + 13 , n) y

(n+1, n+ 13 ) para los problemas relajados, con valor creciente para la función objetivo, pero
sin que el algoritmo pueda identificar que la región factible es vacı́a; consecuentemente
podrı́amos seguir iterando el algoritmo indefinidamente.

35
4. Problemas aplicados

Las principales fuentes consultadas para este capı́tulo han sido [8] y [9].

En esta sección vamos a mostrar algunos ejemplos de problemas clásicos cuya mo-
delización matemática dan pie a la formulación de problemas de programación lineal y
programación entera.

4.1. Ejemplos de problemas de programación lineal

4.1.1. Problema de la dieta

Una de las primeras aplicaciones conocidas del algoritmo del Simplex fue la determi-
nación de una dieta adecuada que fuera de menor coste. El problema de la dieta consiste
en determinar la dieta más económica que satisfaga las necesidades nutritivas mı́nimas
básicas para una persona o un grupo de personas.
Ejemplo 4.1. Supongamos que disponemos de n alimentos distintos con un precio ci
la unidad del alimento i-ésimo. Además hay m ingredientes nutritivos básicos y, para
conseguir una dieta equilibrada, cada persona debe recibir al menos bj unidades del j-
ésimo elemento nutritivo por dı́a. Finalmente, se supone que cada unidad del alimento i
contiene aji unidades del j-ésimo elemento nutritivo. Entonces, denominamos xi al número
de unidades del alimento i de la dieta. El problema consistirá en seleccionar las xi para
minimizar el coste total. Esto es:
si,
aji = Cantidad del nutriente j en el alimento i, para j ∈ {1, . . . , m}, i ∈ {1, . . . , n}
bj = Cantidad necesaria del nutriente j, para j ∈ {1, . . . , m}
ci = Coste unitario del alimento i, para i ∈ {1, . . . , n}
xi = número de unidades del alimento i, para i ∈ {1, . . . , n}.

Entonces el problema a resolver se corresponde con el programa lineal,

minimizar c1 x1 + c2 x2 + · · · + cn xn
sujeto a a11 x1 + a12 x2 + · · · + a1n xn ≥ b1
a21 x1 + a22 x2 + · · · + a2n xn ≥ b2
.. ..
. .
am1 x1 + am2 x2 + · · · + amn xn ≥ bm
y xi ≥ 0, i ∈ {1, . . . , n}.

El problema de la dieta tiene su particular interpretación en el dual. Si consideramos el

problema que acabamos de describir como el primal, es decir con las restricciones Ax ≥ b
y x ≥ 0, el dual de este problema serı́a:
máx λT b
sujeto a λT A ≤ cT
λ ≥ 0.
Este problema se corresponde por ejemplo, en el caso en que un farmacéutico que dispone
de m complementos vitamı́nicos distintos y una cantidad bj de cada complemento.

36
El precio unitario del nutriente j es λj . El farmacéutico quiere maximizar los beneficios
asociados a la venta de complementos vitamı́nicos, pero debe asegurarse que los precios
sean competitivos con el de los alimentos que contienen al nutriente. PEs decir, para cada
alimento i, el precio en complementos vitamı́nicos de sus nutrientes, j∈{1,...,m} λj aji no
puede ser superior al coste del alimento, ci .
Observación 4.2. Además podrı́amos dar una interpretación del teorema de holguras
complementarias. Supongamos por ejemplo que tenemos un par de óptimos x, λT del pri-
mal y dual respectivamente; entonces, si en el primal hay un nutriente que se produce por
encima de su nivel mı́nimo (a(j) x > bj ), entonces el precio del complemento correspon-
diente en el dual será 0. Se podrı́a interpretar como que ese nutriente se consigue ”gratis”.
De modo similar, si un complemento vitamı́nico tiene un precio > 0, la restricción en el
primal se verificará con igualdad ya que no puede ser que haya un exceso de nutriente en
el primal (el dual nos dice que ”no es gratis”).
Por otro lado, si compramos un alimento en el primal, no puede ser que en el dual lo ”pro-
duzcamos más baratoçon los complementos; ası́ pues, si en el dual replicamosün alimento
por debajo de su coste primal, entonces en el primal no será óptimo comprarlo.

4.2. Relaciones lógicas con variables binarias

Antes de presentar alguno de los problemas clásicos de la programación entera vamos a

introducir el uso de variables binarias, a fin de modelar muchos tipos de relaciones lógicas
entre variables y restricciones.

4.2.1. Producción acotada

Supongamos que tenemos que decidir la cantidad a fabricar de un producto xj . Pode-

mos decidir si fabricarlo o no. En caso de hacerlo queremos que la cantidad este entre lj
y uj , con 0 < lj < uj . Una manera de modelar esto serı́a considerando la variable binaria
yj ∈ {0, 1} tal que:

1 si se fabrica el producto j
yj =
0 si no se fabrica el producto j.

Las restricciones de producción vendrán dadas por

lj yj ≤ xj
xj ≤ uj yj .

Entonces si yj = 0, xj = 0. Si yj = 1 se cumple lj ≤ xj ≤ uj .

4.2.2. Costes fijos

Supongamos que tenemos una actividad xj que podemos realizar o no y que en caso
de realizar-la tiene un coste fijo fj y un coste variable cj . Por lo tanto el coste asociado
a xj es 0 si xj = 0 y fj + cj xj si xj > 0. De nuevo una manera de modelar esto seria
considerando la variable binaria yj ∈ {0, 1} tal que:

1 si se realiza la actividad j
yj =
0 si no se realiza la actividad j.

37
 Entonces el sumando correspondiente de la función objetivo serı́a fj yj + cj xj .
Observación 4.3. Hay que evitar soluciones en las que yj = 0 y xj > 0. Para eso se
puede añadir la restricción xj ≤ M yj , para M suficientemente grande. De esta forma nos
aseguramos que si yj = 1, xj no tenga ninguna restricción adicional, y que si yj = 0,
entonces se impondrá xj = 0

4.2.3. Variables con una cantidad finita de valores

Supongamos que tenemos una variable xj que puede tomar una cantidad finita de
valores {v1 , · · · , vl }. Entonces consideramos yij variables binarias, con i ∈ {1, · · · , l} tales
que 
1 si xj = vi
yij =
0 si xj 6= vi .

como xj sólo puede tomar uno de estos valores tendremos

l
X
yij = 1.
i=1

Por último, la variable xj vendrá dada por

l
X
xj = vi yij
i=1

4.2.4. Restricciones sustitutas

Supongamos ahora que tenemos un problema en el que ha de cumplirse al menos una

de las dos siguientes restricciones
Pn
a1j xj ≤ b1
Pj=1
n
j=1 a2j xj ≤ b2

Esto se puede modelar a través de una variable binaria y tal que


0 si imponemos que se cumpla la primera restricción
y=
1 si imponemos que se cumpla la segunda restricción,

y se introducen en el problema las siguientes dos restricciones:

Pn
a1j xj ≤ b1 + M y
Pj=1
n
j=1 a2j xj ≤ b2 + M (1 − y),

donde M > 0 es una constante lo suficientemente grande.

Veamos ahora el caso que dadas m restricciones queremos que se cumplan al menos k.
La formulación pasarı́a por introducir m variables binarias yi , donde

0 si imponemos que se cumpla la i-ésima restricción
yi =
1 si imponemos que se cumpla la i-ésima restricción,

38
 En el problema habrı́a que introducir las siguientes m restricciones
Pn
a x ≤ b1 + M y1
Pnj=1 1j j
a x
j=1 2j j ≤ b2 + M y2
.. .. ..
Pn . . .
j=1 amj xj ≤ bm + M ym ,

acompañada de la restricción
m
X
yi = m − k.
i=1

4.3. Ejemplos de problemas de programación Entera

4.3.1. El problema de la mochila

El problema de la mochila se puede formular como sigue:

Un excursionista debe decidir que cosas incluir en su mochila. Tiene n objetos entre los que
elegir y cada objeto tiene un peso pj y una utilidad uj . El excursionista quiere maximizar
la utilidad de la mochila que se encuentras sujeta a una restricción, el peso de la mochila
P ≥ 0. Se expresa el problema, de la forma que sigue:

n
X
maximizar uj xj
j=1
Xn
sujeto a p j xj ≤ P
j=1
x ∈ {0, 1}n

xj es una variable binaria que indica si el objeto entra en la mochila o no.

Observación 4.4. Existen problemas relevantes de programación entera que resultan ser
(casi) equivalente al problema de la mochila, como por ejemplo el problema de la suma
de subconjuntos. Dicho problema plantea la siguiente cuestión:
Dado un conjunto de números S = {a1 , a2 , . . . , an } y otro número b, ¿existe algún sub-
conjunto de S cuyos números sumen exactamente b? Por ejemplo, si S = {2, 5, 16, 4, 7, 28}
y b = 29, la respuesta és afirmativa puesto que 16 + 7 + 4 + 2 = 29. La formulación del
problema es como sigue:

n
X
maximizar aj xj
j=1
n
X
sujeto a aj xj ≤ b
j=1
x ∈ {0, 1}n

Por tanto la equivalencia es casi inmediata22 , y existirá dicho subconjunto de S cuyos

elementos sumen b si y sólo si la solución óptima del problema toma el valor b.
22
Es suficiente considerar que los valores de los números representan tanto su peso como su utilidad y
que la mochila admite un peso b.

39
4.3.2. Problemas de localización

Uno de los problemas clásicos de la programación entera, es el problema de localización.

Su desarrollo a lo largo del tiempo ha sido tal, que existen múltiples versiones de este
problema. Presentamos a continuación un ejemplo.

Ejemplo 4.5. Supongamos que disponemos de una empresa con m potenciales ubicacio-
nes distintas en donde situar un almacén de distribución para atender las demandas de
n clientes. El problema que se plantea, es decidir qué almacenes deberı́an abrirse y qué
cantidad de mercancı́as se deben enviar desde cada almacén a cada cliente.
Usando las variables binarias vistas en el apartado 4.2.2, tenemos:

1 se abre el almacen de distribución j
yj =
0 si no se abre el almacen de distribución j.

Por otro lado xij denota la cantidad de mercancı́as enviadas del almacén i al cliente
j, y cij es el coste asociado a enviar una unidad de mercancı́a de i a j, y fi , el coste fijo
por abrir el almacén i.
Además, se debe tener en cuenta, que para cada cliente j, su demanda dj debe ser
realizada y no se pueden hacer envı́os desde almacenes no abiertos. Ası́ pues, con todo lo
descrito anteriormente, la formulación del problema es la siguiente:

m X
X n m
X
minimizar cij xij + fi yi
i=1 j=1 i=1

m
X
sujeto a xij = dj j ∈ {1, . . . , n}
i=1
 
n
X n
X
xij − yi  dj  ≤ 0 i ∈ {1, . . . , m}
j=1 j=1
xij ≥ 0 j ∈ {1, . . . , m}, j ∈ {1, . . . , n}
yi ∈ {0, 1} i ∈ {1, . . . , m}

La función objetivo a minimizar contempla tanto los costes fijos asociados a los alma-
cenes
Pm abiertos como los costes de transporte entre almacén y cliente. Con la restricción
i=0 xij = dj , se impone la demanda del cliente dj . Veamos ahora que pasa con las
variables vinarias:
Pn
Si yi = 0, el almacén i no abre, y entonces j=1 xij ≤ 0, no se envı́a nada desde el
almacén i.

Si yi = 1, la restricción establece que desde el almacén i no se enviarán más que la

suma de todas las demandas.

40
5. Conclusiones

Una de las motivaciones principales que me ha llevado a realizar este trabajo es la

inmediata conexión entre lo práctico y teórico.
La profunda comprensión de la naturaleza algebraica del problema que plantea la
programación lineal, ha permitido idear métodos para una resolución muy eficiente en
general. El método del sı́mplex es un claro ejemplo de ello, y que además a dı́a de hoy
sigue siendo el gran referente para abordar este tipo de problemas no solo por su gran
utilidad sino por que también proporciona mucha información adicional relativa a la
solución encontrada. Con el método del sı́mplex se ha podido demostrar el teorema de
dualidad fuerte, que nos ha servido en gran medida para demostrar el teorema de las
holguras complementarias, y para el análisis de sensibilidad con el cual se ha visto como
pueden afectar las distintas variaciones de un problema de programación lineal.
La importancia de disponer de un método como el del sı́mplex, también se ha visto
reflejada en la programación entera, ya que como hemos podido comprobar el método de
Branch and Bound resuelve versiones relajadas del problema inicial.
Este trabajo, de manera introductoria, alcanza el objetivo de establecer una base
rigurosa de conocimientos sobre la programación lineal y entera a partir de la cual poder
seguir profundizando a nivel teórico o desarrollar y implementar en la práctica.

41
Referencias

[1] Bazaraa, M., Jarvis, J. and Sherali, H., 2013. Linear Programming And Network Flows.
Hoboken: Wiley.

[2] Luenberger, D. and López Mateos, M., 1989. Programación lineal y no lineal. Wil-
mington, Del.: Addison-Wesley Iberoamericana.

[3] Dantzig, G. and Thapa, M., 1997. Linear Programming, 1:Introduction. New York:
Springer.

[4] Fuente O’Connor, J., 1998. Técnicas De Cálculo Para Sistemas De Ecuaciones, Pro-
gramación Lineal Y Programación Entera. 2nd ed. Barcelona: Reverté.

[5] Basart i Muñoz, J., 1998. Programació Lineal. Bellaterra: Universitat Autònoma de
Barcelona, Servei de Publicacions.

[6] Pan, P., 2014. Linear Programming Computation. Berlin: Springer.

[7] Matousek, J. and Gärtner, B., 2007. Understanding And Using Linear Programming.
Berlin: Springer.

[8] Conforti, M., Cornuejols, G. and Zambelli, G., 2014. Integer Programming. Springer.

[9] Bradley, S., Hax, A. and Magnanti, T., 1992. Applied Mathematical Programming.
Reading, Mass: Addison-Wesley.

42