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

...