Si se refiere a una solución de LP numérica, el método Simplex es la mejor manera.
La teoría de los multiplicadores de Lagrange es importante (especialmente para derivar precios sombra y demás), pero como algoritmo, no creo que alguna vez se implemente en códigos LP (al menos, en códigos LP que no sean de juguete).
El método Simplex, por otro lado, continúa siendo competitivo después de casi 7 décadas desde que fue articulado por primera vez por George Dantzig. Claro, tiene una complejidad exponencial en el peor de los casos, pero en la práctica funciona muy bien en muchos LP.
Hay otra clase de algoritmos para resolver LPs llamados algoritmos de punto interior (o barrera) que tienen complejidad polinómica. A pesar de su mejor límite teórico, no siempre supera al simplex.
- ¿Se espera que todas las empresas nuevas resuelvan un problema para ser rentables y exitosas (tecnología, artículos comunes, industria de la moda)?
- ¿Cuál es el método de Newton-Rapson para encontrar una raíz cuadrada de un número entero? ¿Cómo se usa?
- Dado un flujo de alrededor de mil millones de números en una matriz, que tiene aproximadamente solo 1000 números únicos, ¿cómo puedo imprimir los números únicos? La complejidad debe ser menor que O (n).
- ¿Cuál es el programa más simple para encontrar números primos en C ++?
- ¿Cuál es la complejidad de [matemáticas] T (n) = 2T (n-1) + C? [/ Matemáticas]
Una ligera digresión …
La tecnología en solucionadores comerciales modernos (CPLEX, Gurobi … no GLPK) está tan avanzada hoy que la elección del algoritmo de optimización es casi de importancia secundaria. La solución exitosa / rápida de un LP depende de algo más que el algoritmo de optimización en bruto; está influenciado principalmente por factores como la heurística de un solucionador, sus bibliotecas de álgebra lineal y, puede sorprenderle saber, el azar.
Heurística : la heurística incorporada de un solucionador es un gran problema. Si sus suposiciones coinciden con las características de un problema, el solucionador puede evitar hacer una gran cantidad de trabajo innecesario. Nada es más rápido que una iteración de optimización no tomada.
Una fase previa a la resolución (común en todos los solucionadores principales, a veces implementada en un lenguaje de modelado) también puede ayudar a simplificar un problema y, en algunos casos, devolver una solución sin tomar una sola iteración simple.
Álgebra lineal : las bibliotecas de álgebra lineal personalizadas en solucionadores de LP comerciales suelen ser las mejores de su clase, porque el álgebra lineal eficiente es clave para soluciones de LP eficientes. Las bibliotecas utilizadas son típicamente tan buenas que en algunos productos de optimización de ingeniería comercial, los solucionadores LP se utilizan en lugar de solucionadores lineales especializados para resolver sistemas Ax = b muy grandes. Ahora, ¿por qué uno haría eso?
En primer lugar, si uno ya está incorporando un solucionador de LP para optimizar la ingeniería, ¿por qué no usarlo también para resolver sistemas lineales? Si bien el solucionador de LP, que es un solucionador disperso / denso de uso general, no puede vencer a un solucionador lineal a medida que reconoce patrones especiales en la matriz, como bandas, circulantes, etc., en general todavía hace un excelente trabajo. Por el precio de una pequeña pérdida de eficiencia, uno gana un montón de regalos como el manejo de mal acondicionamiento (los solucionadores de LP manejan muy bien las matrices mal acondicionadas, es su pan de cada día), la capacidad de imponer restricciones, etc. Esto evita que uno tenga que escriba un solucionador lineal a medida.
Oportunidad : finalmente, no descarte el papel de la casualidad. Si bien el azar juega un papel más importante en los programas de enteros mixtos (en los cuales una perturbación en la heurística puede cambiar drásticamente el camino de la solución, ver Fischetti acelera la optimización con aleatoriedad), hay un pequeño elemento de azar involucrado en la solución LP. El orden del conjunto de restricciones determina la matriz de restricciones inicial y, dependiendo del condicionamiento de su sistema, esto puede afectar la selección de heurísticas del solucionador y su secuencia de aplicación. Esto se debe al hecho de que los números flotantes son una aproximación discontinua y finita a una recta numérica real y son susceptibles a problemas como la cancelación catastrófica, etc.