La programación lineal ( LP , también llamada optimización lineal ) es un método para lograr el mejor resultado (como la máxima ganancia o el menor costo) en un modelo matemático cuyos requisitos están representados por relaciones lineales . La programación lineal es un caso especial de programación matemática (también conocida como optimización matemática ).
Más formalmente, la programación lineal es una técnica para la optimización de una función objetivo lineal , sujeta a restricciones de igualdad lineal y desigualdad lineal . Su región factible es un politopo convexo , que es un conjunto definido como la intersección de un número finito de medios espacios , cada uno de los cuales está definido por una desigualdad lineal. Su función objetivo es una verdadera -valued afín (lineal) la función definida en este poliedro. Un algoritmo de programación lineal encuentra un punto en el politopo donde esta función tiene el valor más pequeño (o más grande) si tal punto existe.
Los programas lineales son problemas que pueden expresarse en forma canónica como
Aquí los componentes de x son las variables que se determinen, c y b se dan vectores (con lo que indica que los coeficientes de c se utilizan como una matriz de una sola fila con el fin de formar el producto de la matriz), y A es un dado matriz . La función cuyo valor se va a maximizar o minimizar ( en este caso) se llama función objetivo . El desigualdades A x ≤ b y x ≥ 0 son las limitaciones que especifican un politopo convexosobre el cual se optimizará la función objetivo. En este contexto, dos vectores son comparables cuando tienen las mismas dimensiones. Si cada entrada en el primero es menor o igual que la entrada correspondiente en el segundo, entonces se puede decir que el primer vector es menor o igual que el segundo vector.
La programación lineal se puede aplicar a varios campos de estudio. Se usa ampliamente en matemáticas y, en menor medida, en negocios, economía y para algunos problemas de ingeniería. Las industrias que utilizan modelos de programación lineal incluyen transporte, energía, telecomunicaciones y manufactura. Ha demostrado ser útil para modelar diversos tipos de problemas en la planificación , el enrutamiento , la programación , la asignación y el diseño.
El problema de resolver un sistema de desigualdades lineales se remonta al menos hasta Fourier , quien en 1827 publicó un método para resolverlas, [1] y de quien se nombra el método de eliminación de Fourier-Motzkin .
En 1939, el matemático y economista soviético Leonid Kantorovich , quien también propuso un método para resolverlo, dio una formulación de programación lineal de un problema que es equivalente al problema general de programación lineal . [2] Es una forma que desarrolló, durante la Segunda Guerra Mundial , de planificar los gastos y las ganancias con el fin de reducir los costos del ejército y aumentar las pérdidas impuestas al enemigo. [ cita requerida ] El trabajo de Kantorovich fue inicialmente descuidado en la URSS . [3] Casi al mismo tiempo que Kantorovich, el economista holandés-estadounidense TC Koopmans formuló problemas económicos clásicos como programas lineales. Kantorovich y Koopmans luego compartieron el premio Nobel de economía de 1975 . [1] En 1941, Frank Lauren Hitchcock también formuló problemas de transporte como programas lineales y dio una solución muy similar al método símplex posterior . [2] Hitchcock había muerto en 1957 y el premio Nobel no se otorga póstumamente.
Durante 1946-1947, George B. Dantzig desarrolló de forma independiente una formulación de programación lineal general para usar en problemas de planificación en la Fuerza Aérea de los EE. UU. [4] En 1947, Dantzig también inventó el método simplex que, por primera vez, abordó de manera eficiente el problema de la programación lineal en la mayoría de los casos. [4] Cuando Dantzig organizó una reunión con John von Neumann para discutir su método simplex, Neumann inmediatamente conjeturó la teoría de la dualidad al darse cuenta de que el problema que había estado trabajando en la teoría de juegos era equivalente. [4] Dantzig proporcionó una prueba formal en un informe inédito "Un teorema sobre desigualdades lineales" el 5 de enero de 1948.[3] El trabajo de Dantzig se puso a disposición del público en 1951. En los años de la posguerra, muchas industrias lo aplicaron en su planificación diaria.
El ejemplo original de Dantzig fue encontrar la mejor asignación de 70 personas para 70 trabajos. La potencia informática necesaria para probar todas las permutaciones y seleccionar la mejor asignación es enorme; el número de configuraciones posibles excede el número de partículas en el universo observable . Sin embargo, solo lleva un momento encontrar la solución óptima planteando el problema como un programa lineal y aplicando el algoritmo simplex . La teoría detrás de la programación lineal reduce drásticamente el número de posibles soluciones que deben verificarse.
Leonid Khachiyan demostró por primera vez que el problema de programación lineal se podía resolver en tiempo polinomial en 1979, [5] pero un gran avance teórico y práctico en el campo se produjo en 1984 cuando Narendra Karmarkar introdujo un nuevo método de punto interior para resolver la programación lineal. problemas. [6]
La programación lineal es un campo de optimización ampliamente utilizado por varias razones. Muchos problemas prácticos en la investigación de operaciones pueden expresarse como problemas de programación lineal. [3] Ciertos casos especiales de programación lineal, como problemas de flujo de red y problemas de flujo de múltiples productos , se consideran lo suficientemente importantes como para haber generado mucha investigación sobre algoritmos especializados para su solución. Varios algoritmos para otros tipos de problemas de optimización funcionan resolviendo problemas de LP como subproblemas. Históricamente, las ideas de la programación lineal han inspirado muchos de los conceptos centrales de la teoría de la optimización, como la dualidad, la descomposición y la importancia de la convexidad.y sus generalizaciones. Del mismo modo, la programación lineal se utilizó mucho en la formación inicial de la microeconomía y actualmente se utiliza en la gestión de la empresa, como la planificación, la producción, el transporte, la tecnología y otros temas. Aunque los problemas de gestión moderna cambian constantemente, a la mayoría de las empresas les gustaría maximizar las ganancias y minimizar los costos con recursos limitados. Google usa programación lineal para estabilizar los videos de YouTube. [7] Por lo tanto, muchos temas pueden caracterizarse como problemas de programación lineal.
La forma estándar es la forma habitual y más intuitiva de describir un problema de programación lineal. Consta de las siguientes tres partes:
El problema generalmente se expresa en forma de matriz y luego se convierte en:
Otras formas, como problemas de minimización, problemas con restricciones en formas alternativas, así como problemas que involucran variables negativas , siempre se pueden reescribir en un problema equivalente en forma estándar.
Suponga que un agricultor tiene un terreno de cultivo, digamos L km 2 , para plantar trigo o cebada o una combinación de ambos. El agricultor tiene una cantidad limitada de fertilizante, F kilogramos y pesticida, P kilogramos. Cada kilómetro cuadrado de trigo requiere F 1 kilogramos de fertilizante y P 1 kilogramos de pesticida, mientras que cada kilómetro cuadrado de cebada requiere F 2 kilogramos de fertilizante y P 2 kilogramos de pesticida. Sea S 1 el precio de venta del trigo por kilómetro cuadrado y S 2sea el precio de venta de la cebada. Si denotamos el área de tierra sembrada con trigo y cebada por x 1 y x 2 respectivamente, entonces la ganancia puede maximizarse eligiendo valores óptimos para x 1 y x 2 . Este problema se puede expresar con el siguiente problema de programación lineal en la forma estándar:
Maximizar: | (maximizar los ingresos: los ingresos son la "función objetivo") | |
Sujeto a: | (límite de área total) | |
(límite de fertilizante) | ||
(límite de pesticidas) | ||
(no se puede plantar un área negativa). |
En forma de matriz, esto se convierte en:
Los problemas de programación lineal se pueden convertir en una forma aumentada para aplicar la forma común del algoritmo simplex . Este formulario introduce variables de holgura no negativas para reemplazar desigualdades con igualdades en las restricciones. Los problemas se pueden escribir en la siguiente forma de matriz de bloques :
donde están las variables de holgura recién introducidas, son las variables de decisión y es la variable a maximizar.
El ejemplo anterior se convierte en la siguiente forma aumentada:
Maximizar: | (función objetiva) | |
sujeto a: | (restricción aumentada) | |
(restricción aumentada) | ||
(restricción aumentada) | ||
donde están las variables de holgura (no negativas), que representan en este ejemplo el área no utilizada, la cantidad de fertilizante no utilizado y la cantidad de pesticida no utilizado.
En forma de matriz, esto se convierte en:
Cada problema de programación lineal, al que se hace referencia como problema primario , puede convertirse en un problema dual , que proporciona un límite superior al valor óptimo del problema primario. En forma de matriz, podemos expresar la primal problema como:
Una fórmula primaria alternativa es:
Hay dos ideas fundamentales para la teoría de la dualidad. Uno es el hecho de que (para el dual simétrico) el dual de un programa lineal dual es el programa lineal primario original. Además, cada solución factible para un programa lineal da un límite al valor óptimo de la función objetivo de su dual. El teorema de la dualidad débil establece que el valor de la función objetivo del dual en cualquier solución factible es siempre mayor o igual que el valor de la función objetivo del primario en cualquier solución factible. El teorema de la dualidad fuerte establece que si el primario tiene una solución óptima, x * , entonces el dual también tiene una solución óptima, y * , yc T x * =b T y * .
Un programa lineal también puede ser ilimitado o inviable. La teoría de la dualidad nos dice que si el primordial es ilimitado, el dual es inviable por el teorema de la dualidad débil. Asimismo, si el dual es ilimitado, entonces el primordial debe ser inviable. Sin embargo, es posible que tanto el dual como el primario sean inviables. Consulte el programa lineal dual para obtener detalles y varios ejemplos más.
Pares de problema de cobertura / embalaje | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||
Un LP de cobertura es un programa lineal de la forma:
tal que la matriz A y los vectores b y c son no negativo.
El doble de un LP de recubrimiento es un LP de empaque , un programa lineal de la forma:
tal que la matriz A y los vectores b y c son no negativo.
Los LP de cobertura y empaquetado surgen comúnmente como una relajación de programación lineal de un problema combinatorio y son importantes en el estudio de algoritmos de aproximación . [8] Por ejemplo, las relajaciones de LP del problema de empaquetado del conjunto , el problema del conjunto independiente y el problema de emparejamiento son los LP de empaquetado. Las relajaciones de LP del problema de la cobertura del conjunto , el problema de la cobertura del vértice y el problema del conjunto dominante también cubren los LP.
Encontrar una coloración fraccionaria de una gráfica es otro ejemplo de un LP de cobertura. En este caso, hay una restricción para cada vértice del gráfico y una variable para cada conjunto independiente del gráfico.
Es posible obtener una solución óptima para el dual cuando solo se conoce una solución óptima para el primario utilizando el teorema de la holgura complementaria. El teorema establece:
Suponga que x = ( x 1 , x 2 , ..., x n ) es factible primordial y que y = ( y 1 , y 2 , ..., y m ) es factible dual. Sea ( w 1 , w 2 , ..., w m ) las correspondientes variables primarias de holgura, y sea ( z 1 , z 2 , ..., z n ) las correspondientes variables duales de holgura. Entonces x y y son óptimos para sus respectivos problemas si y solo si
Entonces, si la i -ésima variable de holgura del primario no es cero, entonces la i -ésima variable del dual es igual a cero. Asimismo, si la j -ésima variable de holgura del dual no es cero, entonces la j -ésima variable del primario es igual a cero.
Esta condición necesaria para la optimización transmite un principio económico bastante simple. En forma estándar (cuando se maximiza), si hay holgura en un recurso primario restringido (es decir, hay "sobras"), entonces las cantidades adicionales de ese recurso no deben tener valor. Asimismo, si hay holgura en el requisito de restricción de no negatividad del precio dual (sombra), es decir, el precio no es cero, entonces debe haber suministros escasos (no "sobras").
Geométricamente, las restricciones lineales definen la región factible , que es un poliedro convexo . Una función lineal es una función convexa , lo que implica que todo mínimo local es un mínimo global ; de manera similar, una función lineal es una función cóncava , lo que implica que todo máximo local es un máximo global .
No es necesario que exista una solución óptima, por dos razones. Primero, si las restricciones son inconsistentes, entonces no existe una solución factible: por ejemplo, las restricciones x ≥ 2 yx ≤ 1 no pueden satisfacerse conjuntamente; en este caso, decimos que el LP es inviable . En segundo lugar, cuando el politopo no está acotado en la dirección del gradiente de la función objetivo (donde el gradiente de la función objetivo es el vector de los coeficientes de la función objetivo), no se alcanza ningún valor óptimo porque siempre es posible hacer mejor que cualquier valor finito de la función objetivo.
De lo contrario, si existe una solución factible y si el conjunto de restricciones está acotado, entonces el valor óptimo siempre se alcanza en el límite del conjunto de restricciones, por el principio máximo para funciones convexas (alternativamente, por el principio mínimo para funciones cóncavas) ya que las funciones lineales son tanto convexas como cóncavas. Sin embargo, algunos problemas tienen distintas soluciones óptimas; por ejemplo, el problema de encontrar una solución factible a un sistema de desigualdades lineales es un problema de programación lineal en el que la función objetivo es la función cero (es decir, la función constante que toma el valor cero en todas partes). Para este problema de factibilidad con la función cero para su función objetivo, si hay dos soluciones distintas, entonces cada combinación convexa de las soluciones es una solución.
Los vértices del politopo también se denominan soluciones básicas factibles . El motivo de esta elección de nombre es el siguiente. Sea d el número de variables. Entonces, el teorema fundamental de las desigualdades lineales implica (para problemas factibles) que para cada vértice x * de la región factible LP, existe un conjunto de restricciones de desigualdad d (o menos) de LP tales que, cuando tratamos esas restricciones d como igualdades, la única solución es x * . Por lo tanto, podemos estudiar estos vértices mediante la observación de ciertos subconjuntos del conjunto de todas las restricciones (un conjunto discreto), en lugar del continuo de soluciones LP. Este principio subyace a laalgoritmo simplex para la resolución de programas lineales.
El algoritmo simplex , desarrollado por George Dantzig en 1947, resuelve problemas de LP mediante la construcción de una solución factible en un vértice del politopo y luego caminando a lo largo de un camino en los bordes del politopo hacia los vértices con valores no decrecientes de la función objetivo hasta un el óptimo se alcanza con seguridad. En muchos problemas prácticos, se produce un " estancamiento ": se realizan muchos pivotes sin aumento de la función objetivo. [9] [10] En problemas prácticos raros, las versiones habituales del algoritmo simplex pueden en realidad "ciclar". [10] Para evitar ciclos, los investigadores desarrollaron nuevas reglas de pivote. [11] [12] [9] [10] [13][14]
En la práctica, el algoritmo simplex es bastante eficiente y se puede garantizar que encontrará el óptimo global si se toman ciertas precauciones contra los ciclos . Se ha demostrado que el algoritmo simplex resuelve problemas "aleatorios" de manera eficiente, es decir, en un número cúbico de pasos, [15] que es similar a su comportamiento en problemas prácticos. [9] [16]
Sin embargo, el algoritmo simplex tiene un comportamiento pobre en el peor de los casos: Klee y Minty construyeron una familia de problemas de programación lineal para los cuales el método simplex toma una serie de pasos exponenciales en el tamaño del problema. [9] [12] [13] De hecho, durante algún tiempo no se sabía si el problema de programación lineal era resoluble en tiempo polinómico , es decir, de clase de complejidad P .
Al igual que el algoritmo simplex de Dantzig, el algoritmo entrecruzado es un algoritmo de intercambio de bases que pivota entre bases. Sin embargo, el algoritmo entrecruzado no necesita mantener la viabilidad, sino que puede girar de una base factible a una inviable. El algoritmo entrecruzado no tiene complejidad de tiempo polinomial para la programación lineal. Ambos algoritmos visitan todas las esquinas 2 D de un cubo (perturbado) en la dimensión D , el cubo de Klee-Minty , en el peor de los casos . [14] [17]
En contraste con el algoritmo simplex, que encuentra una solución óptima al atravesar los bordes entre vértices en un conjunto poliédrico, los métodos de punto interior se mueven a través del interior de la región factible.
Este es el primer algoritmo de tiempo polinomial del peor de los casos que se haya encontrado para la programación lineal. Para resolver un problema que tiene n variables y se puede codificar en L bits de entrada, este algoritmo se ejecuta en el tiempo. [5] Leonid Khachiyan resolvió este problema de complejidad de larga data en 1979 con la introducción del método elipsoide . El análisis de convergencia tiene predecesores (de números reales), en particular los métodos iterativos desarrollados por Naum Z. Shor y los algoritmos de aproximación de Arkadi Nemirovski y D. Yudin.
El algoritmo de Khachiyan fue de gran importancia para establecer la solubilidad en tiempo polinómico de programas lineales. El algoritmo no fue un avance computacional, ya que el método simplex es más eficiente para todas las familias de programas lineales, excepto para las especialmente construidas.
Sin embargo, el algoritmo de Khachiyan inspiró nuevas líneas de investigación en programación lineal. En 1984, N. Karmarkar propuso un método proyectivo para la programación lineal. El algoritmo de Karmarkar [6] mejoró el límite polinómico del peor caso de Khachiyan [5] (dar ). Karmarkar afirmó que su algoritmo era mucho más rápido en la práctica LP que el método simplex, una afirmación que generó un gran interés en los métodos de punto interior. [18] Desde el descubrimiento de Karmarkar, se han propuesto y analizado muchos métodos de puntos interiores.
En 1987, Vaidya propuso un algoritmo que se ejecuta en el tiempo. [19]
En 1989, Vaidya desarrolló un algoritmo que se ejecuta en el tiempo. [20] Hablando formalmente, el algoritmo toma operaciones aritméticas en el peor de los casos, donde es el número de restricciones, es el número de variables y es el número de bits.
En 2015, Lee y Sidford demostraron que se puede resolver en el tiempo, [21] donde representa el número de elementos distintos de cero, y sigue siendo en el peor de los casos.
En 2019, Cohen, Lee y Song mejoraron la ejecución de vez en cuando, es el exponente de la multiplicación de matrices y es el exponente dual de la multiplicación de matrices . [22] se define (aproximadamente) como el número más grande tal que uno puede multiplicar una matriz por una matriz en el tiempo. En un trabajo de seguimiento de Lee, Song y Zhang, reproducen el mismo resultado a través de un método diferente. [23] Estos dos algoritmos permanecen cuando y . El resultado debido a Jiang, Song, Weinstein y Zhang mejoró a . [24]
La opinión actual es que las eficiencias de buenas implementaciones de métodos basados en simplex y métodos de punto interior son similares para aplicaciones rutinarias de programación lineal. Sin embargo, para tipos específicos de problemas de LP, puede ser que un tipo de solucionador sea mejor que otro (a veces mucho mejor), y que la estructura de las soluciones generadas por los métodos de punto interior frente a los métodos basados en símplex sean significativamente diferentes con el soporte el conjunto de variables activas es típicamente más pequeño para el último. [25]
¿Admite la programación lineal un algoritmo de tiempo fuertemente polinomial?
Hay varios problemas abiertos en la teoría de la programación lineal, cuya solución representaría avances fundamentales en matemáticas y avances potencialmente importantes en nuestra capacidad para resolver programas lineales a gran escala.
Este conjunto de problemas estrechamente relacionados ha sido citado por Stephen Smale como uno de los 18 problemas sin resolver más importantes del siglo XXI. En palabras de Smale, la tercera versión del problema "es el principal problema no resuelto de la teoría de la programación lineal". Si bien existen algoritmos para resolver la programación lineal en tiempo débilmente polinomial, como los métodos elipsoides y las técnicas de punto interior , todavía no se han encontrado algoritmos que permitan un rendimiento de tiempo fuertemente polinómico en el número de restricciones y el número de variables. El desarrollo de tales algoritmos sería de gran interés teórico y quizás también permitiría obtener beneficios prácticos en la resolución de grandes LP.
Aunque la conjetura de Hirsch fue refutada recientemente para dimensiones más altas, todavía deja abiertas las siguientes preguntas.
Estas preguntas se relacionan con el análisis de desempeño y el desarrollo de métodos similares a la simplex. La inmensa eficiencia del algoritmo simplex en la práctica a pesar de su rendimiento teórico de tiempo exponencial sugiere que puede haber variaciones de simplex que se ejecutan en tiempo polinomial o incluso fuertemente polinomial. Sería de gran importancia práctica y teórica saber si existen tales variantes, particularmente como un enfoque para decidir si LP puede resolverse en un tiempo fuertemente polinomial.
El algoritmo simplex y sus variantes pertenecen a la familia de algoritmos de seguimiento de bordes, llamados así porque resuelven problemas de programación lineal al moverse de vértice a vértice a lo largo de los bordes de un politopo. Esto significa que su rendimiento teórico está limitado por el número máximo de aristas entre dos vértices cualesquiera en el politopo LP. Por tanto, nos interesa conocer el diámetro máximo teórico-gráfico de los grafos politopales. Se ha demostrado que todos los politopos tienen un diámetro subexponencial. La reciente refutación de la conjetura de Hirsch es el primer paso para demostrar si algún politopo tiene un diámetro superpolinomial. Si existen tales politopos, entonces no se puede ejecutar ninguna variante de seguimiento de bordes en tiempo polinomial. Las preguntas sobre el diámetro de los politopos son de interés matemático independiente.
Los métodos de pivote simplex conservan la viabilidad primaria (o dual). Por otro lado, los métodos de pivote entrecruzados no preservan la viabilidad (primordial o dual); pueden visitar bases primarias factibles, duales factibles o primarias y duales no factibles en cualquier orden. Los métodos de pivote de este tipo se han estudiado desde la década de 1970. [ cita requerida ] Esencialmente, estos métodos intentan encontrar la ruta de pivote más corta en el politopo de arreglo bajo el problema de programación lineal. En contraste con los gráficos politopales, se sabe que los gráficos de los politopos de disposición tienen un diámetro pequeño, lo que permite la posibilidad de un algoritmo de pivote cruzado entrecruzado en tiempo polinomial fuerte sin resolver preguntas sobre el diámetro de los politopos generales. [14]
Si se requiere que todas las variables desconocidas sean números enteros, entonces el problema se llama un problema de programación de números enteros (IP) o de programación lineal de números enteros (ILP). En contraste con la programación lineal, que se puede resolver de manera eficiente en el peor de los casos, los problemas de programación de enteros son en muchas situaciones prácticas (aquellas con variables limitadas) NP-hard . La programación de enteros 0-1 o la programación de enteros binarios (BIP) es el caso especial de la programación de enteros donde se requiere que las variables sean 0 o 1 (en lugar de enteros arbitrarios). Este problema también se clasifica como NP-difícil y, de hecho, la versión de decisión fue uno de los 21 problemas NP-completos de Karp .
Si solo se requiere que algunas de las variables desconocidas sean números enteros, entonces el problema se denomina problema de programación de enteros mixtos (MIP). Por lo general, también son NP-hard porque son incluso más generales que los programas ILP.
Sin embargo, hay algunas subclases importantes de problemas de IP y MIP que se pueden resolver de manera eficiente, sobre todo los problemas en los que la matriz de restricciones es totalmente unimodular y los lados derechos de las restricciones son números enteros o, de manera más general, en los que el sistema tiene la integralidad dual total. (TDI) propiedad.
Los algoritmos avanzados para resolver programas lineales enteros incluyen:
Padberg y Beasley analizan estos algoritmos de programación de enteros .
Se dice que un programa lineal en variables reales es integral si tiene al menos una solución óptima que es integral. Asimismo, se dice que un poliedro es integral si para todas las funciones objetivas factibles acotadas c , el programa lineal tiene un óptimo con coordenadas enteras. Como lo observaron Edmonds y Giles en 1977, se puede decir de manera equivalente que el poliedro es integral si para cada función objetivo integral factible acotada c , el valor óptimo del programa lineal es un número entero.
Los programas lineales integrales son de importancia central en el aspecto poliédrico de la optimización combinatoria, ya que proporcionan una caracterización alternativa de un problema. En concreto, para cualquier problema, el casco convexo de las soluciones es un poliedro integral; si este poliedro tiene una descripción agradable / compacta, entonces podemos encontrar eficientemente la solución óptima factible bajo cualquier objetivo lineal. Por el contrario, si podemos probar que una relajación de programación lineal es integral, entonces es la descripción deseada del casco convexo de soluciones factibles (integrales).
La terminología no es coherente en toda la literatura, por lo que se debe tener cuidado de distinguir los siguientes dos conceptos:
Una forma común de probar que un poliedro es integral es demostrar que es totalmente unimodular . Hay otros métodos generales que incluyen la propiedad de descomposición entera y la integralidad dual total . Otros LP integrales específicos bien conocidos incluyen el politopo correspondiente, los poliedros de celosía, los poliedros de flujo submodular y la intersección de dos polimatroides / g -polimatroides generalizados; por ejemplo, ver Schrijver 2003.
Licencias permisivas :
Nombre | Licencia | Breve información |
---|---|---|
GLOP | Apache v2 | Solucionador de programación lineal de código abierto de Google |
Pyomo | BSD | Un lenguaje de modelado de código abierto para optimización lineal, mixta de enteros y no lineales a gran escala |
SuanShu | Apache v2 | un conjunto de algoritmos de optimización de código abierto para resolver LP, QP , SOCP , SDP , SQP en Java |
Licencias copyleft (recíprocas) :
Nombre | Licencia | Breve información |
---|---|---|
Solucionador de restricciones de casuario | LGPL | un conjunto de herramientas de resolución de restricciones incrementales que resuelve de manera eficiente sistemas de igualdades y desigualdades lineales |
CLP | CPL | un solucionador de LP de COIN-OR |
glpk | GPL | GNU Linear Programming Kit, un solucionador LP / MILP con una API C nativa y numerosos (15) contenedores de terceros para otros lenguajes. Soporte especializado para redes de flujo . Paquetes de la AMPL -como GNU MathProg Lenguaje de Modelado y traductor. |
Qoca | GPL | una biblioteca para resolver de forma incremental sistemas de ecuaciones lineales con varias funciones de objetivo |
Proyecto R | GPL | un lenguaje de programación y un entorno de software para computación estadística y gráficos |
MINTO (Mixed Integer Optimizer, un solucionador de programación de enteros que utiliza un algoritmo de bifurcación y enlace) tiene un código fuente disponible públicamente [26] pero no es de código abierto.
Licencias propietarias :
Nombre | Breve información |
---|---|
OBJETIVOS | Un lenguaje de modelado que permite modelar modelos de optimización lineales, enteros mixtos y no lineales. También ofrece una herramienta para la programación de restricciones. También se puede implementar el algoritmo, en forma de heurística o métodos exactos, como Generación de columnas o rama y corte. La herramienta llama a un solucionador apropiado como CPLEX, Gurobi o similar, para resolver el problema de optimización en cuestión. Las licencias académicas son gratuitas. |
AMPL | Un lenguaje de modelado popular para optimización lineal, mixta de enteros y no lineales a gran escala con una versión gratuita limitada para estudiantes disponible (500 variables y 500 restricciones). |
APMonitor | API para MATLAB y Python. Resuelva problemas de programación lineal (LP) de ejemplo a través de MATLAB, Python o una interfaz web. |
CPLEX | Solucionador popular con una API para varios lenguajes de programación, y también tiene un lenguaje de modelado y funciona con AIMMS, AMPL, GAMS , MPL, OpenOpt, OPL Development Studio y TOMLAB . Gratis para uso académico. |
Función Excel Solver | Un solucionador no lineal ajustado a hojas de cálculo en las que las evaluaciones de funciones se basan en las celdas de nuevo cálculo. Versión básica disponible como complemento estándar para Excel. |
FortMP | |
JUEGOS | |
Gurobi | Solucionador con algoritmos paralelos para programas lineales a gran escala, programas cuadráticos y programas de enteros mixtos. Gratis para uso académico. |
Bibliotecas numéricas IMSL | Colecciones de algoritmos matemáticos y estadísticos disponibles en C / C ++, Fortran, Java y C # / .NET. Las rutinas de optimización en las bibliotecas IMSL incluyen minimizaciones sin restricciones, con restricciones lineales y no lineales, y algoritmos de programación lineal. |
LINDO | Solucionador con API para la optimización a gran escala de programas lineales, enteros, cuadráticos, cónicos y no lineales generales con extensiones de programación estocástica. Ofrece un procedimiento de optimización global para encontrar una solución globalmente óptima garantizada para programas generales no lineales con variables continuas y discretas. También tiene una API de muestreo estadístico para integrar simulaciones de Monte-Carlo en un marco de optimización. Tiene un lenguaje de modelado algebraico ( LINGO ) y permite modelar dentro de una hoja de cálculo ( What'sBest ). |
Arce | Un lenguaje de programación de propósito general para computación simbólica y numérica. |
MATLAB | Un lenguaje de programación de propósito general y orientado a matrices para computación numérica. La programación lineal en MATLAB requiere Optimization Toolbox además del producto básico de MATLAB; las rutinas disponibles incluyen INTLINPROG y LINPROG |
Mathcad | Un editor de matemáticas WYSIWYG. Tiene funciones para resolver problemas de optimización lineales y no lineales. |
Mathematica | Un lenguaje de programación de propósito general para matemáticas, que incluye capacidades numéricas y simbólicas. |
MOSEK | Un solucionador de optimización a gran escala con API para varios lenguajes (C ++, java, .net, Matlab y python). |
Biblioteca numérica NAG | Una colección de rutinas matemáticas y estadísticas desarrolladas por Numerical Algorithms Group para múltiples lenguajes de programación (C, C ++, Fortran, Visual Basic, Java y C #) y paquetes (MATLAB, Excel, R, LabVIEW). El capítulo Optimización de la biblioteca NAG incluye rutinas para problemas de programación lineal con matrices de restricciones lineales dispersas y no dispersas, junto con rutinas para la optimización de sumas cuadráticas, no lineales de cuadrados de funciones lineales o no lineales con restricciones no lineales, limitadas o sin restricciones . La biblioteca NAG tiene rutinas para la optimización local y global, y para problemas continuos o enteros. |
OptimJ | Un lenguaje de modelado basado en Java para optimización con una versión gratuita disponible. [27] [28] |
SAS / OR | Un conjunto de solucionadores para optimización lineal, entera, no lineal, sin derivadas, de red, combinatoria y de restricciones; el lenguaje de modelado algebraico OPTMODEL ; y una variedad de soluciones verticales dirigidas a problemas / mercados específicos, todos los cuales están completamente integrados con el Sistema SAS . |
SCIP | Un solucionador de programación de enteros de restricciones de propósito general con énfasis en MIP. Compatible con el lenguaje de modelado Zimpl . Gratis para uso académico y disponible en código fuente. |
XPRESS | Solucionador de programas lineales a gran escala, programas cuadráticos, programas generales no lineales y de enteros mixtos. Tiene API para varios lenguajes de programación, también tiene un lenguaje de modelado Mosel y trabaja con AMPL, GAMS . Gratis para uso académico. |
VisSim | Un lenguaje de diagrama de bloques visual para la simulación de sistemas dinámicos . |
|title=
( ayuda )Recursos de la biblioteca sobre programación lineal |
|
Wikimedia Commons tiene medios relacionados con la programación lineal . |