Programación lineal

Método para resolver algunos problemas de optimización

Para el retrónimo que se refiere a la transmisión de televisión, consulte Programación de transmisión .

Una representación pictórica de un programa lineal simple con dos variables y seis desigualdades. El conjunto de soluciones factibles se representa en amarillo y forma un polígono , un politopo bidimensional . La función de costo lineal está representada por la línea roja y la flecha: la línea roja es un conjunto de niveles de la función de costo y la flecha indica la dirección en la que estamos optimizando.

Una región factible cerrada de un problema con tres variables es un poliedro convexo . Las superficies que dan un valor fijo de la función objetivo son planos (no se muestran). El problema de la programación lineal es encontrar un punto en el poliedro que esté en el plano con el valor más alto posible.

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

${\displaystyle {\begin{aligned}&{\text{Find a vector}}&&\mathbf {x} \\&{\text{that maximizes}}&&\mathbf {c} ^{T}\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{and}}&&\mathbf {x} \geq \mathbf {0} .\end{aligned}}}$

Aquí, los componentes de x son las variables que se van a determinar, c y b son vectores dados (con lo que se indica que los coeficientes de c se utilizan como una matriz de una sola fila con el fin de formar el producto matricial) y A es una matriz dada. . 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 convexo${\displaystyle \mathbf {c} ^{T}}$${\displaystyle \mathbf {x} \mapsto \mathbf {c} ^{T}\mathbf {x} }$sobre 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.

Historia

Leonid Kantorovich

John von Neumann

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]

Usos

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. Por lo tanto, muchos temas se pueden caracterizar como problemas de programación lineal.

Forma estándar

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:

• Una función lineal para maximizar

p.ej ${\displaystyle f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}}$

• Restricciones del problema de la siguiente forma

p.ej

${\displaystyle {\begin{matrix}a_{11}x_{1}+a_{12}x_{2}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}&\leq b_{2}\\a_{31}x_{1}+a_{32}x_{2}&\leq b_{3}\\\end{matrix}}}$

• Variables no negativas

p.ej

${\displaystyle {\begin{matrix}x_{1}\geq 0\\x_{2}\geq 0\end{matrix}}}$

El problema generalmente se expresa en forma de matriz y luego se convierte en:

${\displaystyle \max\{\,\mathbf {c} ^{\mathrm {T} }\mathbf {x} \mid \mathbf {x} \in \mathbb {R} ^{n}\land A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\,\}}$

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.

Ejemplo

Suponga que un agricultor tiene un terreno de cultivo, digamos L km ² , 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 ₁ kilogramos de fertilizante y P ₁ kilogramos de pesticida, mientras que cada kilómetro cuadrado de cebada requiere F ₂ kilogramos de fertilizante y P ₂ kilogramos de pesticida. Sea S ₁ el precio de venta del trigo por kilómetro cuadrado y S ₂sea ​​el precio de venta de la cebada. Si denotamos el área de tierra sembrada con trigo y cebada por x ₁ y x ₂ respectivamente, entonces la ganancia puede maximizarse eligiendo valores óptimos para x ₁ y x ₂ . Este problema se puede expresar con el siguiente problema de programación lineal en la forma estándar:

Maximizar: ${\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}$		(maximizar los ingresos: los ingresos son la "función objetivo")
Sujeto a:	${\displaystyle x_{1}+x_{2}\leq L}$	(límite de área total)
	${\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F}$	(límite de fertilizante)
	${\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P}$	(límite de pesticidas)
	${\displaystyle x_{1}\geq 0,x_{2}\geq 0}$	(no se puede plantar un área negativa).

En forma de matriz, esto se convierte en:

maximizar ${\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}$

sujeto a ${\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq {\begin{bmatrix}0\\0\end{bmatrix}}.}$

Forma aumentada (forma floja)

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 :

Maximizar :${\displaystyle z}$

${\displaystyle {\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\0&\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}z\\\mathbf {x} \\\mathbf {s} \end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}}$

${\displaystyle \mathbf {x} \geq 0,\mathbf {s} \geq 0}$

donde están las variables de holgura recién introducidas, son las variables de decisión y es la variable a maximizar.${\displaystyle \mathbf {s} }$${\displaystyle \mathbf {x} }$${\displaystyle z}$

Ejemplo

El ejemplo anterior se convierte en la siguiente forma aumentada:

Maximizar: ${\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}$		(función objetiva)
sujeto a:	${\displaystyle x_{1}+x_{2}+x_{3}=L}$	(restricción aumentada)
	${\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}+x_{4}=F}$	(restricción aumentada)
	${\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}+x_{5}=P}$	(restricción aumentada)
	${\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0.}$

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.${\displaystyle x_{3},x_{4},x_{5}}$

En forma de matriz, esto se convierte en:

Maximizar :${\displaystyle z}$

${\displaystyle {\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\end{bmatrix}}{\begin{bmatrix}z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={\begin{bmatrix}0\\L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}\geq 0.}$

Dualidad

Artículo principal: programa lineal dual

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:

Maximizar c ^T x sujeto a A x ≤ b , x ≥ 0;

con el correspondiente problema dual simétrico ,

Minimizar b ^T y sujeto a A ^T y ≥ c , y ≥ 0.

Una fórmula primaria alternativa es:

Maximizar c ^T x sujeto a A x ≤ b ;

con el correspondiente problema dual asimétrico ,

Minimizar b ^T y sujeto a A ^T y = c , y ≥ 0.

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.

Variaciones

Cubrir / empacar dualidades

Pares de problema de cobertura / embalaje
Cubriendo problemas Problemas de empaque Cobertura mínima establecida Embalaje de conjunto máximo Cobertura de borde mínima Coincidencia máxima Cobertura mínima de vértice Conjunto máximo independiente Recubrimiento del contenedor Embalaje de contenedores Revestimiento poligonal Embalaje rectangular
v t mi

Un LP de cobertura es un programa lineal de la forma:

Minimizar: b ^T y ,

sujeto a: A ^T y ≥ c , y ≥ 0 ,

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:

Maximizar: c ^T x ,

sujeto a: A x ≤ b , x ≥ 0 ,

tal que la matriz A y los vectores b y c son no negativo.

Ejemplos

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 . ^[7] 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.

Holgura complementaria

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 ₁ ,  x ₂ , ...,  x _n ) es factible primordial y que y  = ( y ₁ ,  y ₂ , ...,  y _m ) es factible dual. Sea ( w ₁ ,  w ₂ , ...,  w _m ) las correspondientes variables primarias de holgura, y sea ( z ₁ ,  z ₂ , ...,  z _n ) las correspondientes variables duales de holgura. Entonces x y y son óptimos para sus respectivos problemas si y solo si

• x _j z _j  = 0, para j  = 1, 2, ...,  n , y
• w _yo y _yo  = 0, para yo  = 1, 2, ...,  m .

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").

Teoría

Existencia de soluciones óptimas

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.

Vértices (y rayos) óptimos de poliedros

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.

Algoritmos

Ver también: Lista de temas de análisis numérico § Programación lineal

En un problema de programación lineal, una serie de restricciones lineales produce una región factible convexa de valores posibles para esas variables. En el caso de dos variables, esta región tiene la forma de un polígono convexo simple .

Algoritmos de intercambio de bases

Algoritmo simplex de Dantzig

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. ^{[8] [9]} En raros problemas prácticos, las versiones habituales del algoritmo simplex pueden en realidad "ciclar". ^[9] Para evitar ciclos, los investigadores desarrollaron nuevas reglas de pivote. ^{[10] [11] [8] [9] [12] [13]}

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, ^[14] que es similar a su comportamiento en problemas prácticos. ^{[8] [15]}

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. ^{[8] [11] [12]} 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 .

Algoritmo entrecruzado

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 . ^{[13] [16]}

Punto interior

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.

Algoritmo elipsoide, siguiendo a Khachiyan

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.${\displaystyle O(n^{6}L)}$

Algoritmo proyectivo de Karmarkar

Artículo principal: algoritmo de Karmarkar

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. ^[17] Desde el descubrimiento de Karmarkar, se han propuesto y analizado muchos métodos de puntos interiores.${\displaystyle O(n^{3.5}L)}$

Algoritmo 87 de Vaidya

En 1987, Vaidya propuso un algoritmo que se ejecuta en el tiempo. ^[18]${\displaystyle O(n^{3})}$

Algoritmo 89 de Vaidya

En 1989, Vaidya desarrolló un algoritmo que se ejecuta en el tiempo. ^[19] 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.${\displaystyle O(n^{2.5})}$${\displaystyle O((n+d)^{1.5}nL)}$${\displaystyle d}$${\displaystyle n}$${\displaystyle L}$

Ingrese algoritmos de tiempo de dispersión

En 2015, Lee y Sidford demostraron que se puede resolver en el tiempo, ^[20] donde representa el número de elementos distintos de cero, y sigue siendo en el peor de los casos.${\displaystyle {\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)}$${\displaystyle nnz(A)}$${\displaystyle O(n^{2.5}L)}$

Algoritmo actual de tiempo de multiplicación de matrices

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 . ^[21] se define (aproximadamente) como el número más grande de modo que se pueda 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. ^[22] Estos dos algoritmos permanecen cuando y . El resultado debido a Jiang, Song, Weinstein y Zhang mejoró a . ^[23]${\displaystyle {\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)}$${\displaystyle \omega }$${\displaystyle \alpha }$ ${\displaystyle \alpha }$${\displaystyle n\times n}$${\displaystyle n\times n^{\alpha }}$${\displaystyle O(n^{2})}$${\displaystyle {\tilde {O}}(n^{2+1/6}L)}$${\displaystyle \omega =2}$${\displaystyle \alpha =1}$${\displaystyle {\tilde {O}}(n^{2+1/6}L)}$${\displaystyle {\tilde {O}}(n^{2+1/18}L)}$

Comparación de métodos de punto interior y algoritmos simplex

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 versus 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. ^[24]

Problemas abiertos y trabajo reciente

Problema no resuelto en informática :

¿Admite la programación lineal un algoritmo de tiempo fuertemente polinomial?

(más problemas sin resolver en informática)

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.

• ¿LP admite un algoritmo de tiempo fuertemente polinomial ?
• ¿LP admite un algoritmo de tiempo fuertemente polinomial para encontrar una solución estrictamente complementaria?
• ¿LP admite un algoritmo de tiempo polinomial en el modelo de cálculo de números reales (costo unitario)?

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 un 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 polinomial 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.

• ¿Existen reglas de pivote que conduzcan a variantes símplex en tiempo polinomial?
• ¿Todas las gráficas politopales tienen un diámetro acotado polinomialmente?

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. ^[13]

Enteros desconocidos

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:

• método del plano de corte
• Ramificar y enlazar
• Ramificar y cortar
• Sucursal y precio
• si el problema tiene alguna estructura adicional, puede ser posible aplicar la generación de columna retrasada .

Padberg y Beasley analizan estos algoritmos de programación de enteros .

Programas lineales integrales

Artículo principal: politopo integral

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.${\displaystyle P=\{x\mid Ax\geq 0\}}$${\displaystyle \{\max cx\mid x\in P\}}$${\displaystyle x^{*}}$${\displaystyle P}$${\displaystyle \{\max cx\mid x\in P\}}$

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:

• En un programa lineal de enteros, descrito en la sección anterior, las variables están forzosamente restringidas a ser enteros, y este problema es NP-difícil en general,
• En un programa lineal integral, descrito en esta sección, las variables no están limitadas a ser números enteros, sino que se ha demostrado de alguna manera que el problema continuo siempre tiene un valor óptimo integral (asumiendo que c es integral), y este valor óptimo se puede encontrar de manera eficiente ya que todos los programas lineales de tamaño polinomial se pueden resolver en tiempo polinomial.

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.

Solucionadores y lenguajes de scripting (programación)

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

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 ^[25] 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. [26] [27]
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 .

Ver también

• Programación convexa
• Programación dinámica
• Déficit esperado § Optimización del déficit esperado
• Modelo de insumo-producto
• Programación del taller de trabajo
• Juego de producción lineal
• Programación lineal-fraccionaria (LFP)
• Problema de tipo LP
• Programación matemática
• Programación no lineal
• Matroide orientado
• Programación cuadrática , un superconjunto de programación lineal
• Programación semidefinida
• Precio sombra
• Algoritmo simplex , utilizado para resolver problemas de LP

Notas

1. Gerard Sierksma; Yori Zwols (2015). Optimización lineal y entera: teoría y práctica (3ª ed.). Prensa CRC. pag. 1. ISBN 978-1498710169.
2. Alexander Schrijver (1998). Teoría de la programación lineal y entera . John Wiley e hijos. págs. 221–222. ISBN 978-0-471-98232-6.
3. George B. Dantzig (abril de 1982). "Reminiscencias sobre los orígenes de la programación lineal" . Cartas de investigación operativa . 1 (2): 43–48. doi : 10.1016 / 0167-6377 (82) 90043-8 .
4. Dantzig, George B .; Thapa, Mukund Narain (1997). Programación lineal . Nueva York: Springer. pag. xxvii. ISBN 0387948333. OCLC  35318475 .
5. Leonid Khachiyan (1979). "Un algoritmo polinomial para la programación lineal". Doklady Akademii Nauk SSSR . 224 (5): 1093–1096.
6. Narendra Karmarkar (1984). "Un nuevo algoritmo de tiempo polinomial para la programación lineal". Combinatorica . 4 (4): 373–395. doi : 10.1007 / BF02579150 . S2CID 7257867 . 
7. Vazirani (2001 , p. 112)
8. Dantzig y Thapa (2003) harvtxt error: no target: CITEREFDantzigThapa2003 (help)
9. Padberg (1999) harvtxt error: no target: CITEREFPadberg1999 (help)
10. Soso (1977)
11. Murty (1983)
12. Papadimitriou y Steiglitz harvtxt error: no target: CITEREFPapadimitriouSteiglitz (help)
13. Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Métodos entrecruzados: una nueva visión de los algoritmos de pivote". Programación Matemática, Serie B . 79 (1-3): 369-395. CiteSeerX 10.1.1.36.9373 . doi : 10.1007 / BF02614325 . Señor 1464775 . S2CID 2794181 .   
14. Borgwardt (1987) harvtxt error: no target: CITEREFBorgwardt1987 (help)
15. Todd (2002) harvtxt error: no target: CITEREFTodd2002 (help)
16. Roos, C. (1990). "Un ejemplo exponencial de la regla pivotante de Terlaky para el método simplex cruzado". Programación matemática . Serie A. 46 (1): 79–84. doi : 10.1007 / BF01585729 . Señor 1045573 . S2CID 33463483 .  
17. Strang, Gilbert (1 de junio de 1987). "El algoritmo de Karmarkar y su lugar en las matemáticas aplicadas". El inteligente matemático . 9 (2): 4–10. doi : 10.1007 / BF03025891 . ISSN 0343-6993 . Señor 0883185 . S2CID 123541868 .   
18. Vaidya, Pravin M. (1987). Un algoritmo para programación lineal que requiere operaciones aritméticas . 28º Simposio Anual del IEEE sobre Fundamentos de las Ciencias de la Computación. FOCS.${\displaystyle {O}(((m+n)n^{2}+(m+n)^{1.5}n)L)}$
19. Vaidya, Pravin M. (1989). Aceleración de la programación lineal mediante la multiplicación rápida de matrices . 30º Simposio Anual sobre Fundamentos de la Informática. FOCS. doi : 10.1109 / SFCS.1989.63499 .
20. Lee, Yin-Tat; Sidford, Aaron (2015). Mantenimiento inverso eficiente y algoritmos más rápidos para programación lineal . FOCS '15 Fundamentos de la informática. arXiv : 1503.01752 .
21. Cohen, Michael B .; Lee, Yin-Tat; Canción, Zhao (2018). Resolución de programas lineales en el tiempo de multiplicación de matrices actual . 51º Simposio Anual de ACM sobre Teoría de la Computación. STOC'19. arXiv : 1810.07896 .
22. Lee, Yin-Tat; Song, Zhao; Zhang, Qiuyi (2019). Resolver la minimización de riesgos empíricos en el tiempo de multiplicación de la matriz actual . Jornada de Teoría del Aprendizaje. COLT'19. arXiv : 1905.04447 .
23. Jiang, Shunhua; Song, Zhao; Weinstein, Omri; Zhang, Hengjie (2020). Matriz dinámica inversa más rápida para LP más rápidos . arXiv : 2004.07470 .
24. Illés, Tibor; Terlaky, Tamás (2002). "Métodos de pivote versus punto interior: pros y contras" . Revista europea de investigación operativa . 140 (2): 170. CiteSeerX 10.1.1.646.3539 . doi : 10.1016 / S0377-2217 (02) 00061-9 . 
25. "COR @ L - Investigación de optimización computacional en Lehigh" . lehigh.edu .
26. http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf OptimJ utilizado en un modelo de optimización para líneas de montaje de modelos mixtos, Universidad de Münster
27. http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 OptimJ utilizado en una técnica aproximada de cálculo de equilibrio perfecto en subjuegos para juegos repetidos

Referencias

• Kantorovich, LV (1940). "Об одном эффективном методе решения некоторых классов экстремальных проблем" [Un nuevo método para resolver algunas clases de problemas extremos]. Doklady Akad Sci SSSR . 28 : 211-214.
• FL Hitchcock: La distribución de un producto de varias fuentes a numerosas localidades , Journal of Mathematics and Physics, 20, 1941, 224-230.
• GB Dantzig: Maximización de una función lineal de variables sujetas a desigualdades lineales , 1947. Publicado pp. 339–347 en TC Koopmans (ed.): Activity Analysis of Production and Allocation , Nueva York-Londres 1951 (Wiley & Chapman-Hall)
• JE Beasley, editor. Avances en programación lineal y entera . Oxford Science, 1996. (Colección de encuestas)
• Bland, Robert G. (1977). "Nuevas reglas de pivote finito para el método simplex". Matemáticas de la investigación operativa . 2 (2): 103–107. doi : 10.1287 / moor.2.2.103 . JSTOR  3689647 .
• Karl-Heinz Borgwardt, The Simplex Algorithm: A Probabilistic Analysis , Algorithms and Combinatorics, Volume 1, Springer-Verlag, 1987 (Comportamiento promedio en problemas aleatorios)
• Richard W. Cottle, ed. El George B. Dantzig básico . Stanford Business Books, Stanford University Press, Stanford, California, 2003. (Artículos seleccionados por George B. Dantzig )
• George B. Dantzig y Mukund N. Thapa. 1997. Programación lineal 1: Introducción . Springer-Verlag.
• George B. Dantzig y Mukund N. Thapa. 2003. Programación Lineal 2: Teoría y Extensiones . Springer-Verlag. (Completo, que cubre, por ejemplo , algoritmos de pivote y de punto interior, problemas a gran escala, descomposición siguiendo Dantzig-Wolfe y Benders , e introduciendo la programación estocástica ).
• Edmonds, Jack; Giles, Rick (1977). "Una relación Min-Max para funciones submodulares en gráficos". Estudios en Programación de Enteros . Annals of Discrete Mathematics. 1 . págs. 185-204. doi : 10.1016 / S0167-5060 (08) 70734-9 . ISBN 978-0-7204-0765-5.
• Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Métodos entrecruzados: una nueva visión de los algoritmos de pivote". Programación Matemática, Serie B . 79 (1-3): 369-395. CiteSeerX  10.1.1.36.9373 . doi : 10.1007 / BF02614325 . Señor  1464775 . S2CID  2794181 .
• Gondzio, Jacek; Terlaky, Tamás (1996). "3 Una vista computacional de los métodos de puntos interiores" . En JE Beasley (ed.). Avances en programación lineal y entera . Serie de conferencias de Oxford sobre matemáticas y sus aplicaciones. 4 . Nueva York: Oxford University Press. págs. 103-144. Señor  1438311 . Archivo PostScript en el sitio web de Gondzio y en el sitio web de Terlaky de la Universidad McMaster .
• Murty, Katta G. (1983). Programación lineal . Nueva York: John Wiley & Sons, Inc. págs. Xix + 482. ISBN 978-0-471-09725-9. Señor  0720547 . (referencia completa a los enfoques clásicos).
• Evar D. Nering y Albert W. Tucker , 1993, Programas lineales y problemas relacionados , Academic Press. (elemental)
• M. Padberg, Linear Optimization and Extensions , Second Edition, Springer-Verlag, 1999. (relato cuidadosamente escrito de los algoritmos primarios y doble simplex y los algoritmos proyectivos, con una introducción a la programación lineal de enteros, que presenta el problema del viajante de comercio para Ulises ).
• Christos H. Papadimitriou y Kenneth Steiglitz, Optimización combinatoria: algoritmos y complejidad , Reedición corregida con un nuevo prefacio, Dover. (Ciencias de la Computación)
• Michael J. Todd (febrero de 2002). "Las múltiples facetas de la programación lineal". Programación matemática . 91 (3): 417–436. doi : 10.1007 / s101070100261 . S2CID  6464735 . (Encuesta invitada, del Simposio Internacional de Programación Matemática).
• Vanderbei, Robert J. (2001). Programación lineal: fundamentos y ampliaciones . Springer Verlag.
• Vazirani, Vijay V. (2001). Algoritmos de aproximación . Springer-Verlag. ISBN 978-3-540-65367-7. (Ciencias de la Computación)

Lectura adicional

Recursos de la biblioteca sobre programación lineal

Recursos en su biblioteca

• Dmitris Alevras y Manfred W. Padberg, Optimización lineal y extensiones: problemas y soluciones , Universitext, Springer-Verlag, 2001. (Problemas de Padberg con soluciones).
• Mark de Berg, Marc van Kreveld, Mark Overmars y Otfried Schwarzkopf (2000). Geometría computacional (2ª ed. Revisada). Springer-Verlag . ISBN 978-3-540-65620-3.Capítulo 4: Programación lineal: págs. 63–94. Describe un algoritmo de intersección de semiplano aleatorizado para programación lineal.
• Michael R. Garey y David S. Johnson (1979). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . WH Freeman. ISBN 978-0-7167-1045-5.A6: MP1: PROGRAMACIÓN INTEGER, pág.245. (informática, teoría de la complejidad)
• Gärtner, Bernd; Matoušek, Jiří (2006). Comprensión y uso de la programación lineal . Berlín: Springer. ISBN 3-540-30697-8. (introducción elemental para matemáticos e informáticos)
• Cornelis Roos, Tamás Terlaky, Jean-Philippe Vial, Métodos de puntos interiores para optimización lineal , Segunda edición, Springer-Verlag, 2006. (Nivel de posgrado)
• Alexander Schrijver (2003). Optimización combinatoria: poliedros y eficiencia . Saltador.
• Alexander Schrijver, Teoría de la programación lineal y entera . John Wiley & sons, 1998, ISBN 0-471-98232-6 (matemático) 
• Gerard Sierksma; Yori Zwols (2015). Optimización lineal y entera: teoría y práctica . Prensa CRC. ISBN 978-1-498-71016-9.
• Gerard Sierksma; Diptesh Ghosh (2010). Redes en acción; Ejercicios de texto e informática en optimización de redes . Saltador. ISBN 978-1-4419-5512-8. (modelado de optimización lineal)
• HP Williams, Model Building in Mathematical Programming , Quinta edición, 2013. (Modelado)
• Stephen J. Wright, 1997, Métodos primarios de punto interior dual , SIAM. (Nivel de posgrado)
• Yinyu Ye , 1997, Algoritmos de puntos interiores: teoría y análisis , Wiley. (Nivel avanzado de posgrado)
• Ziegler, Günter M. , Capítulos 1-3 y 6-7 en Lectures on Polytopes , Springer-Verlag, Nueva York, 1994. (Geometría)

Enlaces externos

Wikimedia Commons tiene medios relacionados con la programación lineal .

• Orientación sobre la formulación de problemas de LP
• Glosario de programación matemática
• Preguntas frecuentes sobre programación lineal
• Puntos de referencia para software de optimización