Método karmarkar – investigación de operaciones

MÉTODO KARMARKAR – INVESTIGACIÓN DE OPERACIONES

KARMARKAR METHOD

Aguirre Castellanos Rosa Guadalupe1, Díaz Utrera Jimena Mairyn2, Javier Flores Santiago3, Rodríguez de la Rosa Luis Fernando4, Segura Contreras María de Jesús5, Solorzano Ramírez Ángel del Carmen6.

UNIVERSIDAD VASCONCELOS DE TABASCO

RESUMEN

Mediante este artículo se busca exponer los aspectos más importantes que acompañan al método karmarkar. En efecto la programación lineal es una pieza esencial en el campo de la optimización, ya que en cuanto a los problemas prácticos referentes a la investigación operativa pueden plantearse como un problema de este tipo. En cuanto a la relación con la resolución de los problemas de programación lineal la importancia del método simplex no pasa desapercibida debido a que es el más utilizado para resolver este tipo de problemas. Aunque este método no es del todo eficaz en algunas ocasiones es por ello por lo que surge la necesidad de implementar el método karmarkar o método del punto interior para la resolución de problemas debido a que este se comporta de una manera más razonable en los casos en los que el método simplex es insuficiente.

PALABRAS CLAVE: Algoritmo, Certidumbre, Optimización, Programación lineal, Sistema de números.

INTRODUCCIÓN

La programación lineal se ocupa de la animación de una función lineal, por lo tanto, cumple un conjunto de restricciones. El nombre de programación lineal nace en 1947, cuando Dantzig trabajaba como asesor en las fuerzas aéreas de los estados unidos con el desarrollo de una herramienta capaz de planificar actividades armamentísticas ya que cada planificación se le denominaba “program” (programación)

Mayormente, los problemas de la vida real suelen ser descritos por medio de un modelo matemático seleccionando adecuadamente las variables de decisión planteando la función objetivo y las restricciones del problema. Este método de karmarkar tiene la capacidad de tener resultado diferente a un punto extremo. Es por eso que en este proyecto se da un enfoque ciertamente novedoso sobre lo que se llamaba el método de karmarkar, tratando así de dar aquí una mejor versión de este algoritmo que permita una Fácil implementación, ya que el algoritmo de karmarkar y las modificaciones realizadas en su método han dado lugar al algoritmo de punto intermedio de programación lineal, punto importante del algoritmo karmarkar es que en lugar de reconocer los vértices del poliedro determinado por 5 como en el simplex, evoluciona en el interior relativo 50 como en los métodos de programación no lineal, siendo este un método de punto interior, para finalizar conocemos que el avance karmarkar revitalizo el estudio de los métodos de punto interior y los problemas de barrera mostrándose.

[pic 1][pic 2][pic 3][pic 4][pic 5][pic 6][pic 7][pic 8][pic 9][pic 10]

[pic 11]

[pic 12][pic 13]

[pic 14][pic 15][pic 16][pic 17]

[pic 18][pic 19][pic 20][pic 21][pic 22]

        [pic 23]

[pic 24]

Como una innovación destacable en los años ochenta aparece un nuevo y poderoso algoritmo para la resolución de programas lineales: en 1984, Narendra Karmarkar un matemático indio establecido en Estados Unidos, diseñó una importante modificación del método del simplex. Puestos nuevamente, como ejemplo, la hormiga y tu poliedro, alcanzar la cima del poliedro aplicando esta modificación supondría que la hormiga podría ascender por el interior del poliedro abandonando las aristas por las que, según el método del simplex, debía subir. Con ello, escogiendo las rutas de ascenso adecuadamente, se podría colocar más rápidamente en la cima. Dicho artículo de Karmarkar no describe totalmente el método resolutorio y, además, afirma que es mucho más rápido que el simplex para problemas de gran dimensión. El intento de descubrimiento de un remedo de dicho método puso a toda la comunidad científica en pie de búsqueda.

Pasaron cuatro años hasta que se logró un conocimiento general del método y su distribución comercial.

Al principio, el método de Karmarkar fue acogido con cierto escepticismo. Unos años antes, el matemático soviético L. G. Khachian había desarrollado un método, basado en otro llamado del elipsoide, que, si bien teóricamente parecía superior al del simplex, resultó ser menos eficiente desde el punto de vista práctico.

Pero 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. Se cree que el problema hubiera necesitado semanas enteras de trabajo de ordenador mediante el método del simplex.

Sin embargo, el tratamiento de sistemas moderadamente grandes, el método del simplex parece, todavía, preferible.[pic 25][pic 26]

 [pic 27]

[pic 28]

[pic 29]

[pic 30]

1. Variables de decisión, x ∈ Rn: Representan las decisiones para las cuales buscamos una configuración de valores optima.

1. Función objetivo, f: Rn −→ R: Esta es la función que queremos maximizar o minimizar y representa el coste o beneficio asociado a cada combinación de variables de decisión.

1. Restricciones: Representan la viabilidad de los valores de las variables. Existen de dos tipos:

• Desigualdad: gi(x) ≤ 0, i ∈ {1,...,m}.

• Igualdad: hj(x) = 0, i ∈ {1,...,l}.

1. Proporcionalidad: Dada una variable cualquiera xj , su contribución al coste final es cjxj y su contribución a la restricción i es aijxj . Esto no permite modelar, por ejemplo, las siguientes situaciones:

• Economías de escala: Situaciones en las que cuanto más compremos más barata nos saldrá cada unidad. La proporcionalidad “obliga” a que el coste por unidad sea el mismo independientemente del número de unidades que compremos.

• Costes fijos: Como por ejemplo el coste de una llamada telefónica, si xj es la duración de la llamada, el coste asociado será de la forma cjxj + fj si xj > 0 y 0 si xj = 0.

1. Actividad: La contribución total al valor de la función es la suma de las contribuciones de cada una de las variables consideradas.

1. Certidumbre: Se conoce con exactitud cada dato del problema.

1. Solución no factible: Cuando al menos una restricción se incumple.

1. Solución factible: Cuando se satisfacen todas las restricciones. El objetivo de la programación lineal es encontrar una solución factible que sea la mejor, es decir, que tenga el mejor valor de la función objetivo del modelo.

1. Región factible: Conjunto de todas las soluciones factibles.

1. Solución básica: Es un punto de intersección de las restricciones. Estas pueden ser soluciones factibles o no factibles. Las soluciones básicas factibles coinciden con los puntos extremos de la región factible.

1. Solución óptima: Solución factible que proporciona el valor más favorable de la función objetivo.

1. Aditivita: El coste total es la suma de los costes asociados a cada una de las variables, esto no permite, por ejemplo, considerar interacciones entre las variables, como la efectividad de un medicamento de que depende de la cantidad de alcohol que se tome.

1. Divisibilidad: Las variables pueden tomar cualquier valor fraccionario. Esto no permitirá modelar problemas cuyas variables representen entidades indivisibles como por ejemplo personas, animales o coches.

[pic 31][pic 32]

1. Determinismo: Se supone en estos problemas que los valores A, b y c se conocen de manera totalmente precisa. Esto puede suponer problemas cuando estos parámetros representan por ejemplo precios y demandas, que en general están sujetos a cierta incertidumbre.

1. Variables de decisión: Se corresponden con la cantidad de megabytes que enviamos entre cada servidor i y cada cliente j, xij .

1. Función objetivo: Queremos minimizar el tiempo empleado por los servidores para enviar dicha información.

[pic 33][pic 34][pic 35]

[pic 36]

https://linuxtut.com/en/

[pic 37]

[pic 38]

[pic 39]

[pic 40]

El método de karmarkar puede dividirse en 3 fases claramente delimitadas:

• (fase I) convertir el problema a la FEK
• (Fase II) hallar una solución factible y satisfactoria para el problema de programación lineal dado en la forma estándar de karmarkar
• (Fase III) En la fase II se obtiene una solución x factible pero no necesariamente es un culto extremo del poliedro respectivo. Se debe emplear aquí algún mecanismo para encontrar la solución de punto extrema

Fase I: Convirtiendo un programa lineal a la forma de karmarkar

En esta fase se convierte un programa lineal dado en la forma estándar.

Maximixar {[pic 41]

(1) A la forma estándar de karmarkar  (FEK)

...