Método del punto interior de KARMARKAR

Los pasos que se dieron dif´ıcilmente definen un algoritmo en el sentido normal, pero ¡la

idea es interesante! Se necesitan ciertas modificaciones que garanticen que 1) los pasos

generados a lo largo del gradiente no “se pasen” del punto ´optimo en B, y 2) en el

caso general n dimensional, la direcci´on definida por el gradiente proyectado no cause

un “empantanamiento” del algoritmo en un punto no ´optimo. Esto es, b´asicamente,

lo que se logra con el algoritmo del punto interior de Karmarkar.

Figure 1: Ilustraci´on del concepto general del algoritmo de Karmarkar.

Algoritmo del punto interior

En las publicaciones se pueden encontrar algunas variantes del algoritmo de Karmarkar.

Nuestra explicaci´on se apega al algoritmo original. Karmarkar supone que la

programaci´on lineal es

Minimizar z = CX

sujeta a

AX = 0

1X = 1

X  0

Todas las restricciones son ecuaciones homogP ´eneas, a excepcio´n de la restriccio´n 1X = n

j=1 xj = 1, que define un s´ımplex n dimensional. La validez del algoritmo de

Karmarkar descansa en satisfacer dos condiciones:

2

1. X = ( 1

n, 1

n, . . . , 1

n), satisface AX = 0.

2. m´ın z = 0.

Karmarkar proporciona modificaciones que permiten resolver el problema cuando no

se satisface la segunda condici´on. No presentaremos aqu´ı esas modificaciones.

En el siguiente ejemplo se ilustra c´omo se puede poner una programaci´on lineal general

en la forma homog´enea AX = 0 con 1X = 1, con lo cual tambi´en se tiene a

X = ( 1

n, 1

n, . . . , 1

n) como soluci´on factible (condici´on 1). En un segundo ejemplo se

muestra c´omo se puede hacer que la transformaci´on satisfaga las dos condiciones,

aunque los c´alculos son tediosos.

Ejemplo 7.7-1

Se tiene el problema

Maximizar z = y1 + y2

sujeta a

y1 + 2y2  2

yk  0, 8k.

La restricci´on y1 + 2y2  2 se convierte en una ecuaci´on aumentando una variable de

holgura y3  0 y se tiene

y1 + 2y2 + y3 = 2

Ahora se define

y1 + y2 + y3  U

donde U es suficientemente grande para no eliminar algunos puntos factibles en el

espacio original de soluciones. En nuestro ejemplo U = 5 ser´a adecuado, lo que se

puede determinar con la ecuaci´on y1 + 2y2 + y3 = 2. Suponiendo una variable de

holgura y4  0, se obtiene

y1 + y2 + y3 + y4 = 5

Se puede homogenizar la restricci´on y1 + 2y2 + y3 = 2 multiplicando el lado derecho

por (y1 + y2 + y3 + y4)/5 porque esta fracci´on es igual a 1. Esto lleva, despu´es de la

simplificaci´on, a

3y1 + 8y2 + 3y3 − 2y4 = 0

Para convertir y1 + y2 + y3 + y4 = 5 en un s´ımplex, se define la nueva variable xi =

yi/5, 1  i  4, para obtener

Maximizar z = 5x1 + 5x2

sujeta a

3x1 + 8x2 + 3x3 − 2x4 = 0

x1 + x2 + x3 + x4 = 1

3

xj  0, 1  j  4.

Por ´ultimo se puede asegurar que el centro X = ( 1

n, 1

n, . . . , 1

n) del s´ımplex es un punto

factible para ecuaciones homog´eneas, restando, del lado izquierdo de cada ecuaci´on,

una variable artificial cuyo coeficiente sea igual a la suma algebraica de todos los coeficientes

de restricci´on en el lado izquierdo; esto es, 3+8+3−2 = 12. A continuaci´on se

suman las variables artificiales a la ecuaci´on s´ımplex y se penalizan en forma adecuada

en la funci´on objetivo. En nuestro ejemplo, se aumenta la variable artificial x5 como

sigue:

Maximizar z = 5x1 + 5x2 −Mx5

sujeta a

3x1 + 8x2 + 3x3 − 2x4 − 12x5 = 0

x1 + x2 + x3 + x4 + x5 = 1

xj  0, 1  j  5.

Para este sistema de ecuaciones, el nuevo centro s´ımplex X = ( 1

5 , 1

5 , . . . , 1

5 ) es factible

para la ecuaci´on homog´enea. El valor M en la funci´on objetivo se elige suficientemente

grande para forzar a x5 al valor cero (comp´arese con el m´etodo M).

Ejemplo 7.7-2

En este ejemplo se demuestra que cualquier programaci´on lineal puede satisfacer las

condiciones 1) y 2) que se requieren en el algoritmo de Karmarkar. Las transformaciones

son complicadas y, por tanto, no se recomiendan en la pr´actica. En lugar de

ello se aconseja usar una variaci´on del algoritmo que no requiere la condici´on 2).

Se tiene la misma programaci´on lineal del ejemplo 7.8-1, que es

Maximizar z = y1 + y2

sujeta a

y1 + 2y2  2

yk  0, 8 k.

Se comienza definiendo los problemas primal y dual de la programaci´on lineal:

Primal Dual

Maximizar y0 = y1 + y2 Minimizar w0 = 2w1

sujeta a sujeta a

y1 + 2y2  2 w1  1

2w1  1

y1, y2  0 w1  0

Las restricciones primal y dual se pueden poner en forma de ecuaci´on como sigue:

y1 + 2y2 + y3 = 2, y3  0 (1)

w1 − w2 = 1, w2  0

4

En el ´optimo y0 = w0, que produce

y1 + y2 − 2w1 = 0 (2)

Se selecciona M suficientemente grande, y se obtiene

y1 + y2 + y3 + w1 + w2  M (3)

Ahora se convierte (3) en una ecuaci´on, y se obtiene

y1 + y2 + y3 + w1 + w2 + s1 = M, s1  0 (4)

A continuaci´on se define una nueva variable s2. De acuerdo con (4), las dos ecuaciones

siguientes son v´alidas si, y s´olo si la condici´on s2 = 1 es v´alida:

y1 + y2 + y3 + w1 + w2 + s1 −Ms2 = 0

y1 + y2 + y3 + w1 + w2 + s1 + s2 = M + 1 (5)

Entonces, dado que s2 = 1 como se estipul´o en (5), las ecuaciones primal y dual (1) se

pueden escribir en la siguiente forma:

y1 + 2y2 + y3 − 2s2 = 0

w1 − w2 − 1s2 = 0 (6)

Ahora se definen

yj = (M + 1)xj , j = 1, 2, 3.

wj−3 = (M + 1)xj , j = 4, 5

s1 = (M + 1)x6

s2 = (M + 1)x7

La sustituci´on en las ecuaciones (2), (5) y (6) producir´a las siguientes ecuaciones:

x1 + x2 − 2x4 = 0

x1 + x2 + x3 + x4 + x5 + x6 − Mx7 = 0

x1 + x2 + x3 + x4 + x5 + x6 + x7 = 1

x1 + 2x2 + x3 − 2x7 = 0

x4 − x5 − x7 = 0

xk  0, 8 k.

En el paso final se debe aumentar la variable artificial x8 en el lado izquierdo de cada

ecuaci´on; la nueva funci´on objetivo pedir´a minimizar x8, cuyo valor m´ınimo debe ser

cero (suponiendo que el primal es factible). Sin embargo, n´otese que en el algoritmo

de Karmarkar se requiere que la soluci´on

X =



1

8,

1

8,

1

8,

1

8,

1

8,

1

8,

1

8,

1

8

T

5

sea factible para AX = 0. Eso ser´a cierto para las ecuaciones homog´eneas (con lado

derecho cero) si el coeficiente asociado de x8 artificial es igual a la suma (algebraica)

de todos los coeficientes en el lado izquierdo. As´ı, se ve que el programa lineal transformado

es:

Minimizar z = x8

sujeta a

x1 + x2 − 2x4 − 0x8 = 0

x1 + x2 + x3 + x4 + x5 + x6 − Mx7 − (6 −M)x8 = 0

x1 + 2x2 + x3 − 2x7 − 2x8 = 0

x4 − x5 − x7 + x8 = 0

x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 = 1

xk  0, 8 k.

N´otese que la soluci´on de este problema produce soluciones ´optimas de los problemas

primal y dual, en forma autom´atica, por sustituci´on.

Ahora presentaremos los pasos principales del algoritmo. La figura 2(a) muestra una

ilustraci´on t´ıpica del espacio de soluciones en tres dimensiones, donde el conjunto homog

´eneo AX = 0 est´a formado s´olo por una ecuaci´on. Por definici´on, el espacio de

soluciones formado por el segmento de recta AB queda enteramente en el s´ımplex bidimensional

1X = 1 y pasa por el punto interior factible ( 1

3 , 1

3 , 1

3 ). De forma parecida,

la figura 2(b) muestra una ilustraci´on del espacio de soluciones ABC en cuatro dimensiones,

con el conjunto homog´eneo formado de nuevo s´olo por una restricci´on. En este

caso, el centro del s´ımplex tridimensional es ( 1

4 , 1

4 , 1

4 , 1

4 ).

El algoritmo de Karmarkar se inicia en un punto interior representado por el centro del

s´ımplex y a continuaci´on avanza en la direcci´on del gradiente proyectado para determinar

un nuevo punto de soluci´on. Este nuevo punto debe ser estrictamente interior,

lo que quiere decir que todas sus coordenadas deben ser positivas. La validez del algoritmo

se basa en esta condici´on.

Para que el nuevo punto de soluci´on sea estrictamente interior, no debe estar en los

l´ımites del s´ımplex. (En t´erminos de la figura 2, se deben excluir los puntos A y B en

tres dimensiones, y las rectas AB, BC y AC en cuatro dimensiones.) Para garantizar

este resultado se inscribe una esfera con su centro coincidente con el del s´ımplex, en

forma justa, dentro del s´ımplex. En el caso n dimensional, el radio r de esta esfera es

igual a 1/

p

n(n − 1). Una esfera menor con radio r (0 <  < 1) ser´a un subconjunto

de la esfera, y cualquier punto en la intersecci´on de la esfera menor con el sistema

homog´eneo

...