Revista de Matema´tica: Teor´ıa y Aplicaciones 2(1): 45–55 (1995)
me´todo de karmarkar
Juan Fe´lix Avila Herrera1
Resumen
Este es el primero de una serie de dos art´ıculos en los que se estudia el algoritmo
de Karmarkar. En el presente se da un enfoque ciertamente novedoso sobre lo que se
llamara´ el me´todo de Karmarkar. Se trata aqu´ı de dar una versio´n de este algoritmo
que permita una fa´cil implementacio´n.
Abstract
This is the first of a series of two articles in wich we study the Karmarkar’s Algorithm.
In this article we present a new approach that will be called the Karmarkar’s method.
We intent to present a version of this algorithm that could be implemented easily.
Palabras clave: Algoritmo de Karmarkar, Me´todo de Karmarkar, proceso de Karmarkar,
transformaciones proyectivas, matrices ralas, esquema de purificacio´n.
1 Descripcio´n del me´todo de Karmarkar
El algoritmo de Karmarkar al igual que el s´ımplex no resuelve los programas lineales en su
forma inicial. Es necesario transformar el problema en otro equivalente, de suerte que este
u´ltimo se ajuste a los requerimientos que exige el algoritmo de Karmarkar. Llamaremos
me´todo de Karmarkar al proceso que toma un problema en forma cano´nica:
Maximizar : z =
n∑
j=1
cjxj,
sujeta a:


n∑
j=1
aijxj ≥ bi i = 1, · · ·m,
xj ≥ 0, j = 1, · · · n,
(1)
lo convierte y halla la solucio´n del problema original, o bien concluye sobre la vacuidad o
no unicidad de la solucio´n.
Definicio´n 1 Un programa lineal se dice que esta´ en la forma esta´ndar de Karmarkar
(FEK) si es de la forma:
Minimizar : z = cx, sujeta a: Ax = 0, Unx = 1, x ≥ 0, (2)
1Escuela de Informa´tica, Universidad Nacional
45
46 j. f. avila
donde A es m× n de rango m, n ≥ 2, c y A esta´n compuestos por nu´meros enteros, Un es
un vector con n unos, y cumple las siguientes condiciones (S1) el punto x0 =
(
1
n
, · · · , 1
n
)
,
es factible para (2), y (S2) el valor objetivo o´ptimo del problema (2) es cero.
El me´todo de Karmarkar puede dividirse en tres fases claramente delimitadas:
1. (Fase I) Convertir el problema (1), a la FEK (2).
2. (Fase II) Hallar una solucio´n factible y “satisfactoria” para el problema de progra-
macio´n lineal dado en la forma esta´ndar de Karmarkar.
3. (Fase III) En la fase II se obtiene una solucio´n x factible pero no necesariamente
es un punto extremo del poliedro respectivo. Se debe emplear aqu´ı algu´n mecanismo
(comu´nmente llamado esquema de purificacio´n) para encontrar la solucio´n de punto
extremo.
2 Fase I: Convirtiendo un programa lineal a la forma de Kar-
markar
Conside´rese el siguiente problema de programacio´n lineal2:
Maximizar { cx : Ax ≥ b, x ≥ 0 } , (3)
donde A es m × n de rango m y los datos son todos enteros. Desglosamos el proceso de
conversio´n en los siguientes pasos.
1. Por dualidad de programacio´n lineal, las condiciones de optimalidad para el prob-
lema (3) requieren una solucio´n, si existe alguna, para el sistema:
Ax ≥ b,
x ≥ 0,
ATu ≤ c,
u ≥ 0
y cx = bu,
en donde x = (x1, · · · , xn) , y u = (xm+n+1, · · · , x2m+n) .
2. Se agregan y = (xn+1, · · · , xm+n) , y v = (x2m+n+1, · · · , x2m+2n) (vectores de hol-
gura) al sistema anterior, y se obtiene:
Ax− y = b,
x, y ≥ 0,
ATu+ v = c,
u, v ≥ 0
y cx− bu = 0. (4)
3. Con el fin de crear un punto interior de partida a, se introduce una variable artificial
x2m+2n+1. Sean x0, y0, u0 y v0, vectores con componentes estrictamente positivos,
por ejemplo3
x0 = Un, y0 = Um, u0 = Um, v0 = Un. (5)
2El proceso que se explicara´, puede ser aplicado tambie´n sobre la forma esta´ndar de un programa lineal.
Sin embargo, el dual del problema esta´ndar ofrece algunas dificultades extra, como por ejemplo, variables
no restringidas en signo.
3La eleccio´n de x0, y0, u0 y v0, es bastante libre, se pide solamente que sean puntos estrictamente
interiores en P+ := {x : xi > 0, ∀i }. El lector puede perfectamente escogerlos de otra manera.
me´todo de karmarkar 47
Para dar al lector la libertad de escoger x0, y0, u0 y v0, de otra forma, en lo que sigue,
se brindara´n las fo´rmulas para el caso general, e inmediatamente la forma particular
que adoptan e´stas bajo el escogimiento que se ha hecho anteriormente.
Se construye, entonces, el punto a como a := (x0, y0, u0, v0, 1), o bien a = U2m+2n+1
bajo la eleccio´n (5). De esta forma, el programa lineal que se debe resolver es
Minimizar : z = x2m+2n+1
sujeta a:


Ax− y + (b+ y0 −Ax0)x2m+2n+1 = b,
ATu+ v + (c− v0 −A
Tu0)x2m+2n+1 = c,
cx− bu+ (bu0 − cx0)x2m+2n+1 = 0,
xi ≥ 0, con 1 ≤ i ≤ 2m+ 2n+ 1.
Obse´rvese que a := (x0, y0, u0, v0, 1), es una solucio´n factible para el problema an-
terior, y se toma como punto de partida. El valor mı´nimo de x2m+2n+1 es cero si y
solamente si el problema (4) es factible.
4. Para escribir el sistema anterior en forma matricial primero se definen Ik, como la
matriz identidad de taman˜o k × k, Zp×q, como la matriz nula de taman˜o p × q, los
vectores α y β como α = b+y0−Ax0, y β = c−v0−A
Tu0 que en el caso (5) toman la
forma α = b+ Um−AUn y β = c− Un−A
T Um, y el escalar γ como γ = bu0−cx0, que
en el caso particular (5) se convierte en γ =
m∑
i=1
bi −
n∑
i=1
ci. De esta forma el programa
se puede reescribir como:
Minimizar : z = x2m+2n+1, Hx = f, x ≥ 0, (6)
en donde f =

 bc
0

 , y H es una matriz de taman˜o (m+n+1)× (2m+2n+1), dada
por
H :=

 Am×n − Im Zm×(m+n) αm×1Zn×(m+n) ATn×m In βn×1
c1×n Z1×m −b1×m Z1×n γ

 .
5. Se define ahora la transformacio´n proyectiva T : IR2(m+n)+1 → IR2(m+n+1) dada por
T (x) = x′, en donde x′i :=
xi/ai
1 +
∑2(m+n)+1
j=1 (xj/aj)
, que en el caso (5) toma la forma
x′i :=
xi
1 +
∑2(m+n)+1
j=1 xj
, para i = 1, 2, · · · , 2(m+n)+1, y x′2(m+n+1) := 1−
2(m+n)+1∑
i=1
x′i.
Se definen tambie´n:
P+ :=
{
x ∈ IR2(m+n)+1 : x ≥ 0
}
, y
∆ := {x ∈ IR2(m+n+1) : x ≥ 0
2(m+n+1)∑
i=1
xi = 1}.
La transformacio´n T tiene las siguientes propiedades:
48 j. f. avila
(a) T (P+) ⊆ ∆, i.e. T lleva P+ en ∆.
(b) T es uno-a-uno y la transformacio´n inversa de T , esta´ dada por T−1(x′) = x, o
bien xi =
aix
′
i
x′2(m+n+1)
, que bajo la eleccio´n (5) se convierte en xi =
x′i
x′2(m+n+1)
,
para i = 1, 2, · · · , 2(m + n) + 1.
(c) La transformacio´n T asigna el centro del s´ımplex ∆ al punto a, esto quiere decir
en el caso (5) que T (a) = 12(m+n+1) U2(m+n+1).
(d) Si Hi es la i-e´sima columna de la matriz H, entonces la ecuacio´n Hx = f ,
se puede escribir como
2(m+n)+1∑
i=1
Hixi = f. La ecuacio´n anterior se convierte
(usando T ) en
2(m+n)+1∑
i=1
Hiaix
′
i − fx
′
2(m+n+1) = 0, que en el caso (5) toma la
forma
2(m+n)+1∑
i=1
Hix
′
i − fx
′
2(m+n+1) = 0. De esta forma, si se define la matriz
H ′ = [ a1H1 | a2H2 | · · · | a2(m+n)+1H2(m+n)+1 | − f ],
que en el caso (5) se reduce a H ′ := [H | −f ], la ecuacio´n Hx = f es convertida
en
2(m+n+1)∑
i=1
H ′ix
′
i = 0, o bien en H
′x′ = 0.
En resumen, para resolver el problema 3 utilizando la eleccio´n particular (5), se debe
hallar la solucio´n4 de:
Minimizar : z = x′2(m+n)+1
sujeta a:


H ′x′ = 0,
2(m+n+1)∑
i=1
x′i = 1,
x′i ≥ 0, para 1 ≤ i ≤ 2(m+ n+ 1),
(7)
donde:
H ′ :=

 Am×n − Im Zm×(m+n) αm×1 −bm×1Zn×(m+n) ATn×m In βn×1 −cn×1
c1×n Z1×m −b1×m Z1×n γ 0

 ,
con:
α = b+ Um −AUn,
β = c− Un −A
T Um,
γ =
∑m
i=1 bi −
∑n
i=1 ci.
Una vez que se resuelva el problema (7), la solucio´n de (3), esta´ dada por
xi =
x′i
x′2(m+n+1)
, para i = 1, 2, · · · , n.
4Observe que en virtud de esta transformacio´n podemos redefinir la FEK, pidiendo sencillamente que se
minimice la (n− 1)-e´sima variable de decisio´n.
me´todo de karmarkar 49
3 Fase II: El algoritmo proyectivo de Karmarkar
En esta seccio´n se explicara´ el algoritmo de Karmarkar. Esta es la fase a´lgida del me´todo.
Def´ınase ∆ como:
∆ := {x : x ≥ 0,
∑n
i=1 xi = 1 } . (8)
No´tese que bajo las suposiciones (S1) y (S2), el problema (2) es factible (x0 es una solucio´n)
y acotado (la solucio´n optimal se halla en el s´ımplex ∆) y por tanto, tiene un valor objetivo
o´ptimo. Si la restriccio´n x ∈ ∆, se pudiera reemplazar por x ∈ S, en donde S es una
esfera, el problema (como se vera´) se simplifica, pues el valor o´ptimo puede ser encontrado
resolviendo un sistema lineal de ecuaciones. Para lograr esta simplificacio´n se empleara´n
lo que se conoce como transformaciones proyectivas. Tales transformaciones convierten el
problema dado en la FEK, en otro ma´s simple. Una vez ah´ı, se considera una restriccio´n de
e´ste, utilizando una esfera con radio apropiado. Se halla el valor o´ptimo para este u´ltimo
problema, y dado que la transformacio´n proyectiva en cuestio´n posee inversa, se regresa
al problema original (el dado en la FEK) con un nuevo punto factible x1 (el primero era
x0) con quiza´s mejor valor objetivo. El proceso se repite hasta alcanzar un valor o´ptimo
apropiado (recue´rdese que, en virtud de la suposicio´n (S2), el valor objetivo optimal del
problema es 0). De acuerdo con [3] la sucesio´n (xk) que se genera tiende a cero conforme
k → +∞, aunque no necesariamente en forma monoto´nica. Por tanto, en la pra´ctica, el
algoritmo se puede detener cuando el valor objetivo este´ “bastante cerca” de cero.
3.1 Resumen del Algoritmo de Karmarkar
Antes de explicar la deduccio´n del algoritmo de Karmarkar, se expondra´ en forma al-
gor´ıtmica su funcionamiento5.
1. Iniciacio´n: (k = 0)
(a) Calcule el radio r = 1/
√
n(n− 1).
(b) Calcule L = d1+log(1+|cj max|)+log(|detmax |)e. Aqu´ı d·e, significa la parte entera
superior y log(·) denota logaritmo en base 2, adema´s, |cj max| = max
1≤j≤n
{ |cj | } , y
la cantidad |detmax | es:
|detmax | = max { |det(B)| : B es una base para el problema (2) } .
La constante L se llama la longitud de entrada del problema (2). El ca´lculo
directo de L es dif´ıcil y en la pra´ctica se puede evitar usando otros criterios. Una
forma de estimar L es utilizar L˜ en donde:
L˜ := d1 + log(1 + |cj max|) + log(1 +m) +
m∑
i=1
n∑
j=1
log(1 + |aij |)e, (9)
y se satisface que L ≤ L˜.
5La matriz de restricciones tecnolo´gicas obtenida en la Fase I es de taman˜o (m+ n+ 1)× 2(m+ n+ 1),
no obstante por comodidad en la notacio´n, se supondra´ en lo que sigue, que su taman˜o es m× n.
50 j. f. avila
(c) Calcule α = (n− 1)/3n.
(d) Coloque x0 = (1/n, · · · , 1/n).
2. Elegir Solucio´n: Si cxk < 2
−L, la solucio´n actual xk es factible y satisfactoria, en-
tonces parar el algoritmo. Dado que, en la pra´ctica 2−L es muy pequen˜o, el algoritmo
se puede detener si cxk < , en donde  > 0 es alguna tolerancia predefinida.
3. Paso principal: Se definen las siguientes cantidades matriciales:
(a) La matriz Dk = diag {xk1, . . . , xkn }, en donde xk = (xk1, . . . , xkn).
(b) La matriz P =
[
ADk
Un
]
.
(c) El vector c¯ = cDk.
Se calcula entonces x∗ como x∗ = x0 − αr
cp
||cp||
, con cp =
[
I − P T (PP T )−1P
]
c¯T .
De esta forma se obtiene xk+1 = (Dkx
∗)/(UnDkx
∗). Incremente k en uno y regrese
al paso Elegir Solucio´n.
Para el ca´lculo de cp se puede proceder resolviendo el sistema:
(PP T )x = P c¯T , (10)
mediante6 una descomposicio´n L–U, y calcular entonces cp por cp = c¯
T − P Tx.
3.2 Deduccio´n del algoritmo de Karmarkar
Se empieza con x0 = (1/n, . . . , 1/n) y k = 0, el algoritmo ejecuta el siguiente paso iterativo,
toda vez que se tenga una solucio´n factible xk > 0.
1. (Primera simplificacio´n)
Defina la transformacio´n proyectiva7 T : ∆→ ∆, en donde:
y = T (x) =
D−1k x
UnD
−1
k x
, (11)
y Dk es la matriz diagonal Dk = diag {xk1, . . . , xkn }, donde xk = (xk1, . . . , xkn), (∆
es el s´ımplex descrito en (8)). Es claro que las entradas de T esta´n dadas por:
yi =
xi/xki
n∑
j=1
xj/xkj
, para i = 1, · · · , n. (12)
6No´tese que esta es la ecuacio´n normal para el problema de “mı´nimos cuadrados”: hallar x que minimiza
||P Tx− c¯T ||, consu´ltese [5].
7Las transformaciones proyectivas de IRn son descritas por la fo´rmula T (x) =
Cx+ d
fTx+ g
, en donde C es
una matriz n× n con valores reales, d, f ∈ IRn, g ∈ IR y la matriz
[
C d
f
T
g
]
, es no-singular.
me´todo de karmarkar 51
No´tese tambie´n que
∑
yi = 1, y que y ≥ 0 cuando x ≥ 0, por tanto el codominio de
T es efectivamente ∆.
¿Que´ pasa con el problema (2) bajo la transformacio´n (11)? Veamos:
(a) T (xk) = x0. La demostracio´n de e´sto es trivial.
(b) T es invertible, de hecho:
T−1(x) =
Dkx
UnDkx
. (13)
En efecto, si se pone Z(x) = Dkx/UnDkx y se calcula (T ◦ Z)(x) =
x
Unx
= x,
ya que Unx = 1. De forma ana´loga (Z ◦ T )(x) = x, y por tanto Z = T
−1.
(c) El problema (2) se transforma en:
Minimizar
{
cDkx
UnDkx
: ADkx = 0, Unx = 1, x ≥ 0
}
. (14)
2. (Segunda simplificacio´n)
Se nota de (14), que aunque las restricciones permanecen lineales ya que Ax = 0 es
homoge´nea, la funcio´n objetivo se ha convertido en un cociente de funciones lineales.
No obstante debido al supuesto (S2), el valor objetivo o´ptimo en la ecuacio´n (14) es
cero. Por tanto, podemos minimizar equivalentemente el numerador en el problema,
ya que el denominador es positivo y acotado lejos de cero para todo x ∈ ∆. Se obtiene
as´ı el siguiente problema:
Minimizar { c¯x : Px = P0, x ≥ 0 } , (15)
donde c¯ = cDk, P =
[
ADk
Un
]
y P0 =
[
0
1
]
.
3. (Tercera simplificacio´n)
En lugar de resolver el problema (15), que es equivalente a resolver el problema orig-
inal, se tratara´ de optimizar una restriccio´n ma´s simple de este u´ltimo. Aunque al
resolver esta restriccio´n no se resuelve (indirectamente) el problema original (pues los
problemas no son equivalentes), s´ı se var´ıa (tal vez mejora) la solucio´n actual xk v´ıa
T−1. Para describir la restriccio´n, considere primero la bola S inscrita en el s´ımplex ∆,
es decir, B(x0, r) en donde el radio r = 1/
√
n(n− 1). Ahora, en lugar de restringir
el problema a S, se utilizara´ una bola ma´s pequen˜a, a saber, B(x0, αr), en donde
0 < α < 1, con α = (n − 1)/3n. La eleccio´n de α no es trivial, y el lector8 puede
consultar los detalles en [3].
La restriccio´n que se resolvera´ es entonces:
Minimizar
{
c¯x : Px = P0, (x− x0)
T (x− x0) ≤ α
2r2
}
. (16)
8Al final de esta seccio´n se discute un poco sobre la eleccio´n particular de α.
52 j. f. avila
Se nota, entonces, que la solucio´n para el problema (16) es obtenida proyectando el
gradiente negativo (pues se esta´ minimizando, consulte [2]) de la funcio´n objetivo −c¯T ,
centrado en y0, sobre el espacio nulo o la superficie determinada por la restriccio´n Px = P0
y movie´ndose desde y0 a lo largo de esta direccio´n proyectada hasta la frontera de la bolas
B(y0, αr). Observe que la simplicidad de este proceso de solucio´n es una consecuencia
del hecho de que estamos optimizando una funcio´n lineal sobre una bola, y que estamos
actualmente ubicados en el centro de e´sta, de manera que, la frontera esta´ siempre a la
misma distancia; sin importar la direccio´n que se adopte. Si denotamos la proyeccio´n del
vector gradiente9 c¯T por cp y la solucio´n o´ptima del problema (16) como x
∗, obtenemos:
x∗ = x0 − αr
cp
||cp||
. (17)
[Note que si cp = 0, entonces cualquier solucio´n factible es optimal,
10y se debe terminar con
xk como solucio´n o´ptima del problema (2).]
Proposicio´n 1 Se verifica cp = [I − P
T (PP T )−1P ]c¯T .
Demostracio´n: Consulte [3].
2
La solucio´n x∗ obtenida en (17), debe ser ahora transformada al problema original (2).
Para lograr e´sto se usa la inversa de la transformacio´n proyectiva, i.e. T−1. De esta forma
el correspondiente vector revisado xk+1 esta´ dado por
xk+1 =
Dkx
∗
UnDkx∗
. (18)
Observe que x∗ > 0, ya que pertenece al interior de la esfera (n−1) dimensional inscrita
en ∆. Por tanto, el xk+1 dado en (18) es positivo. Esto completa una iteracio´n. Este
paso puede ser repetido despue´s de incrementar k por uno. El proceso puede ser terminado
cuando el valor objetivo esta´ suficientemente cerca de cero.
Ya se ha dicho algo sobre la forma de detener el algoritmo de Karmarkar, no obstante
es pertinente hacer algunas observaciones adicionales. Cuando se indico´ (en la pa´g. 49) la
forma de detener el proceso, se introdujo la constante L, que proporciona un criterio en este
sentido. El resultado es como sigue.
Teorema 1 El algoritmo de Karmarkar produce una solucio´n xk para el problema (2) que
satisface cxk < 2
−L, en 10nL iteraciones, toda vez que α = (n− 1)/3n.
Demostracio´n: Consulte [3]. 2
9De esta forma, cp pertenece a la superficie Px = P0.
10Si cp = 0, entonces c¯ es perpendicular a la regio´n Py = P0 del problema proyectado, entonces c¯
T y = 0
para todo y en tal regio´n (i.e. se alcanza el costo o´ptimo).
me´todo de karmarkar 53
Sobre el ca´lculo de la constante L se insta al lector a consular [1, 3, 6], en donde se apunta
que en la pra´ctica es innecesario hacerlo. De hecho de 30 a 60 iteraciones son suficientes,
independientemente del taman˜o del problema. Por otro lado el mismo Karmarkar asegura
que en la pra´ctica L es mucho ma´s pequen˜o que n.
Ser´ıa imperdonable terminar esta seccio´n sin mencionar uno de los aspectos cruciales
en las ideas de Karmarkar: la funcio´n potencial, que tiene injerencia directa en la eleccio´n
del α mencionado en el teorema 1. Como se sabe, el algoritmo construye una sucesio´n de
puntos x0, x1, · · ·, xk, de suerte que e´stos van generando valores decrecientes en la funcio´n
objetivo, pero como se ha dicho antes, no en forma mono´tona. El problema es entonces:
¿Co´mo asegurar que la sucesio´n as´ı obtenida va convergiendo efectivamente hacia la solucio´n
o´ptima? Afortunadamente, existe una funcio´n que preserva monoton´ıa estricta (dado que
la funcio´n objetivo original no necesariamente lo hace) y por tanto asegura la convergencia
hacia la solucio´n o´ptima. Esta funcio´n es conocida como funcio´n potencial, y esta´ dada por:
f(x) =
n∑
j=1
ln
[
cx
xj
]
= n ln(cx)−
n∑
j=1
ln(xj).
Al aplicar esta funcio´n potencial a la funcio´n objetivo del problema (14), se concluye (por
supuesto no de forma trivial) que la sucesio´n generada por el algoritmo de Karmarkar
converge a la solucio´n o´ptima toda vez que el valor de α se escoja en la forma que establece
el teorema 1, consulte [3]. Es importante tambie´n mencionar que la eleccio´n particular de
α permite una velocidad de convergencia apropiada, de suerte que se aproxime la solucio´n
o´ptima en pocas iteraciones.
4 Fase III: Rutina de redondeo optimal
En la Fase II se mostro´ co´mo determinar una solucio´n xk apropiada, satisfaciendo cxk <
2−L. Sin embargo, xk no necesariamente es un punto extremo. Es por esto que se debe
“redondear” xk, de manera que se obtenga una solucio´n o´ptima con esta cualidad, y tal que
tenga tan buen valor objetivo como xk.
Antes es conveniente hacer una definicio´n.
Definicio´n 2 Sean c, x ∈ IRn y b ∈ IR. Se dice que u ∈ IRn satisface en forma activa la
desiguadad c · x ≤ b, si c · u = b. Ana´logamente u satisface en forma activa c · x ≥ b o´
c · x = b si c · u = b.
A continuacio´n se describe la rutina de redondeo expuesta en [3].
1. Elegir Solucio´n: Si al sustituir xk en el programa lineal (2), n restricciones lineal-
mente independientes esta´n siendo satisfechas en forma activa, se concluye entonces
que xk es una solucio´n ba´sica o´ptima. Parar.
Es importante aclarar que si m+ 1 < n, no basta con que Axk = b y Unx = 1, en el
problema (2). Si m+1 < n, adema´s de satisfacerse estas igualdades, se debe cumplir
tambie´n, que algunas entradas de xk (a saber n−m− 1), deben ser nulas.
54 j. f. avila
2. Calcular direccio´n: Si xk no es una solucio´n de punto extremo, existen varias
restricciones (digamos l < n) del problema (2) que xk satisface en forma activa.
Denotemos con A˜ la matriz formada a partir de esas restricciones, de la siguiente
forma:
(a) Si una restriccio´n de Ax = b se satisface en forma activa con xk, se incluye la fila
correspondiente de A en A˜.
(b) Si Unxk = 1, el vector Un = (1, 1, · · · , 1) se incluye en A˜.
(c) Si la entrada i-e´sima de xk es nula, se agrega ei = (0, 0, · · · , 1, · · · , 0) (con un
u´nico 1 en la i-e´sima posicio´n) a A˜.
La matriz A˜ resultante es, entonces, de taman˜o l × n con l < n. Considere ahora el
sistema A˜x = 0 y sea d una solucio´n no trivial de este sistema.
3. Actualizar solucio´n: Se obtiene una nueva solucio´n x∗k, movie´ndose a lo largo de la
direccio´n d si cd < 0 y a lo largo de −d en otro caso11, hasta que algunas restricciones
bloqueen cualquier movimiento adicional por consideraciones de factibilidad. As´ı:
(a) si cd < 0, y todas las entradas de d son no negativas, se concluye que la
solucio´n es no acotada. En el caso contrario: x∗k = xk + λ · d, en donde
λ = min1≤i≤n{−xki/di : di < 0}, xk = (xk1, xk2, · · · , xkn) y d = (d1, d2, · · · , dn).
(b) si cd ≥ 0, y todas las entradas de d son no positivas, se concluye que la solucio´n
es no acotada. En el caso contrario:
x∗k = xk − λ · d,
en donde:
λ = min
1≤i≤n
{xki/di : di > 0 } .
Se regresa entonces al paso Elegir Solucio´n.
De acuerdo con [3], siguiendo este procedimiento se obtiene una solucio´n ba´sica factible x¯
para el problema (2), con valor objetivo extrictamente menor que 2−L. Esto concluye la
fase III del me´todo de Karmarkar.
El esquema de purificacio´n tiene sus or´ıgenes en 1965 en el trabajo de Charnes, Kortanek
y Raike, consulte [4]. Posteriormente, en 1988, Kortanek y Jishan (consulte [7]), mostraron
co´mo usar este esquema para lograr una solucio´n ba´sica factible o´ptima. El lector interesado
en otros enfoques de este problema, puede consultar el trabajo de Ye, en el cual se explica
co´mo obtener una base o´ptima v´ıa el algoritmo de Karmarkar, ver [8].
5 Conclusiones
Las tres fases que componenen el me´todo de Karmarkar no son, de ninguna forma triviales.
En este art´ıculo se ha explicado en que´ consiste cada una de ellas. El enfoque elegido ha
11En virtud de la fase I, basta con considerar el signo de d[n− 1].
me´todo de karmarkar 55
sido en su mayor parte algor´ıtmico, esto permitira´ al lector interesado, una implementacio´n
sin mayores contratiempos. La fase I del me´todo de Karmarkar abre las puertas del pro´ximo
art´ıculo. En efecto, despue´s de convertir un programa lineal (1) en (2), la matriz resultante
tiene una estructura rala que dificulta una implementacio´n eficiente del me´todo de Kar-
markar tal cual. En el art´ıculo siguiente se estudiara´n algunos me´todos para manejar tales
matrices y de esta forma obtener una implementacio´n eficiente del algoritmo de Karmarkar.
Referencias
[1] Anstreicher, K.M. (1990) “Progress in interior point algorithms since 1984”, SIAM
News 3
[2] Apostol, T.M. (1977) Calculus. Reverte´, Barcelona, vol. II.
[3] Bazaraa, M.S.; Jarvis, J.J.; Sherali, H. (1990) Linear Programming and Network Flows,
2nd Edition. John Wiley & Sons, New York.
[4] Charnes, A.; Kortanek, K.O.; Raike, W. (1965) “Extreme point solution in mathemat-
ical programming: an opposite sign algorithm”, System Research Memorandum No.
129, Northwestern University, Evanston
[5] Golub, G.H.; Van Loan, C.F. (1989) Matrix Computations, 2nd Edition. The Johns
Hopkins University Press, Baltimore.
[6] Karmarkar, N. (1984) “A new polynomial-time algorithm for linear programming”,
Combinatorica 4
[7] Kortanek, K.O.; Jishan, Z. (1988) “New Purification algorithms for linear program-
ming”, Naval Research Logistics Quaterly 35
[8] Ye, Y. (1990) “Recovering optimal basic variables in Karmarkar polynomial algorithm
for linear programming”, Mathematics of Operation Research 3