Revista de Matemática: Teoría y Aplicaciones ISSN Impreso: 1409-2433 ISSN electrónico: 2215-3373

OAI: https://revistas.ucr.ac.cr/index.php/matematica/oai
Algoritmo de Karmarkar y matrices ralas
PDF

Palabras clave

método de Karmarkar

Cómo citar

Ávila Herrera, J. F. (1995). Algoritmo de Karmarkar y matrices ralas. Revista De Matemática: Teoría Y Aplicaciones, 2(2), 35–48. https://doi.org/10.15517/rmta.v2i2.117

Resumen

Este es el segundo de una serie de dos artículos en los que se estudia el método de Karmarkar. Se muestra cómo utilizar la teoría de matrices ralas para obtener una implementación eficiente del proceso de Karmarkar, presentado en el primer artículo. En la fase I del proceso de Karmarkar, se pone en evidencia la forma como se incrementa el tamaño de la matriz de resticciones tecnológicas. La nueva matriz sin embargo, posee una estructura peculiar bastante favorable, debido a la presencia de bloques de ceros que la hacen parte de una familia de matrices bastante conocida, a saber las matrices ralas. Se discute en este trabajo algunas técnicas para manejar este tipo de matrices, y finalmente el autor propone una variante del método del Karmarkar que aprovecha dicha situación.

https://doi.org/10.15517/rmta.v2i2.117
PDF

Citas

J. F. Avila Herrera (1993) Una implementación eficiente del algoritmo de Karmarkar. Tesis de Maestría ITCR, Cartago, C.R..

J. F. Avila Herrera (1995) “Método de Karmarkar”, Revista de Matemáticas 1

M. S. Bazaraa y J. J. Jarvis (1984) Programación Lineal y Flujo de Redes, 1era Edición. Limusa, México.

M. S. Bazaraa, J. J. Jarvis and H. Sherali (1990)Linear Programming and Network Flows, 2nd Edition. John Wiley & Sons, N.Y..

R. L. Burden y J. D. Douglas (1985) Análisis Numérico. Grupo Editorial Iberoamérica, México.

I. E. Duff and J. K. Reid (1989) Direct Methods for Sparse Matrices. Oxford Science Publications, Oxford.

P. E. Gill, W. Murray, M. A. Saunders and M. H. Wright (1986) Mantaining LU Factors of a General Sparse Matrix. Department of Operations Research, Stanford University, California.

G. H. Golub and C. F. Van Loan (1989) Matrix Computations, 2nd Edition. The Johns Hopkins University Press, USA.

N. Karmarkar (1984) “A new polynomial-time algorithm for Linear Programming”, Combinatorica 4

M. Nuñez y V. Kong (1992) El problema de la Mezcla de Alimentos. Reporte Técnico, ITCR.

Comentarios

Descargas

Los datos de descargas todavía no están disponibles.

Métricas

Cargando métricas ...