Método de Karmarkar

Método de Karmarkar.

La programación lineal se trata de un conjunto de técnicas matemáticas que intentan obtener el mayor provecho posible de sistemas económicos, sociales, tecnológicos, etc. Su problema básico de ésta es el de la maximización de una cierta expresión lineal, que se llama función objetivo, cuyas variables están sometidas a una serie de restricciones que vienen expresadas por ecuaciones lineales.

En 1762, un físico, matemático y astrónomo italiano, Lagrange, resuelve problemas de optimización con restricciones de igualdad.

En 1820 un matemático, astrónomo, geobotánico y físico alemán, Gauss, resuelve sistemas de ecuaciones lineales por el método "eliminación Gaussiana" para que, en 1866, un geodesista alemán, Wilhem Jordan mejorará está técnica y elaborará el método "Gauss-Jordan".

En los años 50 se realizó un gran avance con el algoritmo ideado por George Dantzing, en Estados Unidos, el algoritmo de Simplex.

En 1984, Narendra Karmarkar, un matemático de origen indio logró, un algoritmo que supera con mucho, en eficiencia, el algoritmo del simplex para el tratamiento de problemas con un gran número de variables y de restricciones.

Este método, también llamado algoritmo o proceso de Karmarkar, es igual que el método de Simplex, no resuelve los programas lineales en su forma inicial. Para poder resolver el problema se debe de transformar en otro equivalente de forma que se ajuste a los requerimientos que exige dicho algoritmo.

El algoritmo de Karmarkar ha demostrado una eficacia bastante mayor, sobre todo cuando se trabaja con sistemas de un número de variables y de inecuaciones verdaderamente grande. Un cierto problema reciente de programación lineal con 800000 variables fue resuelto con el algoritmo de Karmarkar tras 10 horas de trabajo de ordenador.

A continuación, se mencionan algunos de los aspectos más importantes sobre el método de Karmarkar. Este método permite resolver programas lineales en tiempo polinomial, mejorando en este sentido en el algoritmo del simplex.

El método de Karmarkar consiste en tres fases que se resumen a continuación:

Se tiene:

Maximizar z= Y1 + Y2

Sujeta a:

Y1 + 2Y2 ≤ 2

Yk ≥ 0, Ɐk

La restricción Y1 + 2Y2 ≤ 2 se convierte en una ecuación aumentando una variable de holgura Y3 ≥ 0 y se tiene:

Y1 + 2Y2 + Y3 = 2

Ahora se define

Y1 + 2Y2 + Y3 ≤ U

Donde U es suficientemente grande para no eliminar algunos puntos factibles en el espacio original de soluciones. En este ejemplo U=5 será adecuado, lo que se puede determinar con la ecuación Y1 + 2Y2 + Y3 = 2. Suponiendo una variable de holgura Y4 ≥ 0, se obtiene

Y1 + Y2 + Y3 + Y4 = 5

Se puede homogenizar la restricción Y1 + 2Y2 + Y3 = 2 multiplicando el lado derecho por (Y1 + Y2 + Y3 + Y4) /5 porque esta fracción es igual a 1. Esto lleva, después de la aplicación, a

3Y1 + 8Y2 + 3Y3 -2 Y4 = 0

Para convertir Y1 + Y2 + Y3 + Y4 = 5 en un simplex, se define la nueva variable Xi = Yi/5, ≤ i ≤ 4, para obtener Maximizar

Z = 5Xi + 5Xi2

Xj ≥ 0, 1 ≤ j ≤ 4

Por último, se puede asegurar que el centro X = (,,…,) del simplex es un punto factible para ecuaciones homogéneas, restando, del lado izquierdo de cada ecuación, una variable artificial cuyo coeficiente sea igual a la suma algebraica de todos los coeficientes de restricción en el lado izquierdo; esto es, 3 + 8 + 3 – 2 = 12. Lo que sigue es sumar las variables artificiales a la ecuación simplex y se penalizan en forma adecuada en la función objetivo. En este ejemplo, se aumenta la variable artificial X5 como sigue:[pic 1][pic 2][pic 3]

...