Programación lineal

Representación pictórica de un simple programa lineal con dos variables y seis desigualdades. El conjunto de soluciones factibles se representa en amarillo y forma un polígono, un politopo de 2 dimensiones. El óptimo de la función de coste lineal es donde la línea roja interseca el polígono. La línea roja es un conjunto de nivel de la función de coste, 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 objetiva son planos (no se muestran). El problema de programación lineal es encontrar un punto en el poliedro que está en el plano con el valor más alto posible.

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 la menor coste) 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 función afín (lineal) de valor real 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 se pueden expresar en forma canónica como

Encontrar un vectorxque maximizacTxsujeto aAx≤ ≤ byx≥ ≥ 0.{displaystyle {begin{aligned} tarde{text{Find a vector}} {mathbf {x}\\ccfnMicrosoft {f}}}mátbf {c}mathbf {x}\mcH00{text{ subject to}}} {f}}} Amathbf {x} leq mathbf {b}\cH00{text{and} {x} geq mathbf {0}end{aligned}}}

Aquí los componentes x son las variables a determinar, c y b se dan vectores (con cT{displaystyle mathbf {c} indicando que los coeficientes de c son utilizados como una matriz de una sola hoja con el propósito de formar el producto de la matriz), y A es una matriz dada. La función cuyo valor debe ser maximizado o minimizado (x↦ ↦ cTx{displaystyle mathbf {x} mapsto mathbf {c}Mathbf {x} en este caso) se llama la función objetiva. Las desigualdades Ax≤b y x ≥ 0 son las limitaciones que especifican un politopo convexo sobre el cual se debe optimizar la función objetiva. En este contexto, dos vectores son comparables cuando tienen las mismas dimensiones. Si cada entrada en el primero es menor o igual a la entrada correspondiente en el segundo, entonces se puede decir que el primer vector es menor o igual al 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 algunos problemas de ingeniería. Las industrias que usan modelos de programación lineal incluyen transporte, energía, telecomunicaciones y manufactura. Ha demostrado ser útil en el modelado de diversos tipos de problemas en la planificación, enrutamiento, programación, asignación y diseño.

Historia

Leonid Kantorovich

John von Neumann

El problema de resolver un sistema de desigualdades lineales se remonta al menos a Fourier, quien en 1827 publicó un método para resolverlas, 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. Es una forma que desarrolló, durante la Segunda Guerra Mundial, para planificar gastos y ganancias con el fin de reducir los costos del ejército y aumentar las pérdidas impuestas al enemigo. El trabajo de Kantorovich fue inicialmente descuidado en la URSS. Casi al mismo tiempo que Kantorovich, el economista holandés-estadounidense T. C. Koopmans formuló los problemas económicos clásicos como programas lineales. Kantorovich y Koopmans luego compartieron el premio Nobel de economía de 1975. 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. Hitchcock había muerto en 1957 y el premio Nobel no se otorga a título póstumo.

Desde 1946 hasta 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 EE. UU. En 1947, Dantzig también inventó el método simplex que, por primera vez de manera eficiente, abordó el problema de la programación lineal en la mayoría de los casos. 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 en el que había estado trabajando en la teoría de juegos era equivalente. Dantzig proporcionó una prueba formal en un informe inédito "A Theorem on Linear Inequalities" el 5 de enero de 1948. 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 era encontrar la mejor asignación de 70 personas para 70 trabajos. El poder de cómputo requerido para probar todas las permutaciones para 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 símplex. La teoría detrás de la programación lineal reduce drásticamente la cantidad de posibles soluciones que deben verificarse.

El problema de programación lineal se demostró por primera vez que se podía resolver en tiempo polinomial por Leonid Khachiyan en 1979, 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 problemas de programación lineal. problemas.

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. Ciertos casos especiales de programación lineal, como los problemas de flujo de red y los problemas de flujo de múltiples productos, se consideran lo suficientemente importantes como para tener mucha investigación sobre algoritmos especializados. Varios algoritmos para otros tipos de problemas de optimización funcionan resolviendo problemas de programación lineal 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. Asimismo, la programación lineal se usó mucho en la formación inicial de la microeconomía y actualmente se utiliza en la gestión de empresas, como la planificación, la producción, el transporte y la tecnología. Aunque los problemas de la administració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 también usa programación lineal para estabilizar videos de YouTube.

Forma estándar

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:

• A función lineal para maximizar

Por ejemplo. f()x1,x2)=c1x1+c2x2{displaystyle f(x_{1},x_{2})=c_{1}x_{2}x_{2}

• Problemas de la siguiente forma

Por ejemplo.

a11x1+a12x2≤ ≤ b1a21x1+a22x2≤ ≤ b2a31x1+a32x2≤ ≤ b3{displaystyle {begin{matrix}a_{11}x_{1}+a_{12}x_{2} b_{1}a_{21}x_{1}+a_{22}x_{2} b_{2}a_{31}x_{1}+a_{32}x_{2} ¿Qué?

• Variables no negativas

Por ejemplo.

x1≥ ≥ 0x2≥ ≥ 0{displaystyle {begin{matrix}x_{1}gq 0x_{2}gq 0end{matrix}}

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

max{}cTx▪ ▪ x▪ ▪ Rn∧ ∧ Ax≤ ≤ b∧ ∧ x≥ ≥ 0}{displaystyle max{,mathbf {c} {mathrm}mathbf {x} mid mathbf {x} in mathbb [R] ^{n}land Amathbf {x} leq mathbf {b} land mathbf {x} geq 0,}}

Otras formas, como problemas de minimización, problemas con restricciones en formas alternativas y problemas que involucran variables negativas siempre se pueden reescribir en un problema equivalente en forma estándar.

Ejemplo

Supongamos que un agricultor tiene un terreno de cultivo, digamos L km², para sembrar trigo o cebada o alguna 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₂ el precio de venta de la cebada. Si denotamos el área de tierra sembrada con trigo y cebada por x₁ y x₂ respectivamente, entonces el beneficio se puede maximizar 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: S1⋅ ⋅ x1+S2⋅ ⋅ x2{displaystyle S_{1}cdot x_{1}+S_{2}cdot x_{2}}		(maximizar los ingresos (las ventas totales de trigo más las ventas totales de cebada) – los ingresos son la "función objetiva")
Sujeto a:	x1+x2≤ ≤ L{displaystyle x_{1}+x_{2}leq L.	(limitado en el área total)
	F1⋅ ⋅ x1+F2⋅ ⋅ x2≤ ≤ F{displaystyle F_{1}cdot x_{1}+F_{2}cdot x_{2}leq F.	(limitado en fertilizante)
	P1⋅ ⋅ x1+P2⋅ ⋅ x2≤ ≤ P{displaystyle P_{1}cdot x_{1}+P_{2}cdot x_{2}leq P}	(limitado en plaguicida)
	x1≥ ≥ 0,x2≥ ≥ 0{displaystyle x_{1}gq 0,x_{2}geq 0}	(no puede plantar un área negativa).

En forma matricial esto se convierte en:

maximizar [S1S2][x1x2]{begin{2}begin{bmatrix}s_{1}end{bmatrix}{begin{bmatrix}x_{1}x_{2}end{bmatrix}}}}} {cH}}} {}}}}}} {c}}}}}}}}}}}}}}}}}} {c}}}}}}}}}}}}}}}}}}} {c}}}}}}}}}}}}}}}}}}} {c}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {c}}}}}}}}}}} {p}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

sujeto a [11F1F2P1P2][x1x2]≤ ≤ [LFP],[x1x2]≥ ≥ [00].{displaystyle {begin{bmatrix}1 {\f_{1}\p_{1}p_{2}end{bmatrix} {begin{bmatrix}x_{1}x_{2}end{bmatrix}}}leq {begin{bmatrix}LF\end{bmatrix},{begin{bmatrix}x_{1}x_{2}end{bmatrix}geq {begin{bmatrix}0end{bmatrix}}}

Forma aumentada (forma floja)

Los problemas de programación lineal se pueden convertir a una forma aumentada para aplicar la forma común del algoritmo simplex. Este formulario introduce variables de holgura no negativas para reemplazar las desigualdades con igualdades en las restricciones. Los problemas se pueden escribir en la siguiente forma de matriz de bloques:

Maximizar z{displaystyle z}:

[1− − cT00AI][zxs]=[0b]{displaystyle {begin{bmatrix}1⁄4mathbf {c} } {c} {c} {c} {c} {c}c}cH0}} {I} end{bmatrix} {begin{bmatrix}z\\mathbf {x}\\mathbf {s}end{bmatrix}={begin{bmatrix}0\Mathbf {b} end{bmatrix}}

x≥ ≥ 0,s≥ ≥ 0{displaystyle mathbf {x} geq 0,mathbf {s} geq 0}

Donde s{displaystyle mathbf {s} son las variables slack recién introducidas, x{displaystyle mathbf {x} son las variables de decisión, y z{displaystyle z} es la variable a maximizar.

Ejemplo

El ejemplo anterior se convierte en la siguiente forma aumentada:

Maximizar: S1⋅ ⋅ x1+S2⋅ ⋅ x2{displaystyle S_{1}cdot x_{1}+S_{2}cdot x_{2}}		(función objetiva)
sujeto a:	x1+x2+x3=L{displaystyle x_{1}+x_{2}+x_{3}=L}	(constricción aumentada)
	F1⋅ ⋅ x1+F2⋅ ⋅ x2+x4=F{displaystyle F_{1}cdot x_{1}+F_{2}cdot x_{2}+x_{4}=F}	(constricción aumentada)
	P1⋅ ⋅ x1+P2⋅ ⋅ x2+x5=P{displaystyle P_{1}cdot x_{1}+P_{2}cdot x_{2}+x_{5}=P}	(constricción aumentada)
	x1,x2,x3,x4,x5≥ ≥ 0.{displaystyle x_{1},x_{2},x_{3},x_{4},x_{5}geq 0.}

Donde x3,x4,x5{displaystyle x_{3},x_{4},x_{5} son (no negativo) variables de holgura, que representan en este ejemplo el área no utilizada, la cantidad de fertilizante no utilizado, y la cantidad de plaguicida no utilizado.

En forma matricial esto se convierte en:

Maximizar z{displaystyle z}:

[1− − S1− − S20000111000F1F20100P1P2001][zx1x2x3x4x5]=[0LFP],[x1x2x3x4x5]≥ ≥ 0.{xb} {cH00}cH00}cH00}cH00}cH00}cH0}b} {cH0} {ccH0}cH0}cH0}cH0} {cH0cH0} {cH0}cH0cH0}bcH0cH0cH00}cH0cH0}cH00cH0cH00}cH0cH00}cH0cH00cH0cH0cH0cH00}cH0cH0cH0cH0cH0cH0cH0cH00}cH00}cH00cH00cH00}cH00}cH0cH00cH00cH00cH0cH00cH00}cH00}c 0.}

Dualidad

Cada problema de programación lineal, denominado problema principal, se puede convertir en un problema dual, que proporciona un límite superior al valor óptimo del problema principal. En forma matricial, podemos expresar el problema primal como:

Maximizar c^Tx sujeto a Ax ≤ b, x ≥ 0;

con el correspondiente simétrica doble problema,

Minimize b^TSí. sujeto a A^TSí. ≥ c, Sí. ≥ 0.

Una formulación primaria alternativa es:

Maximizar c^Tx sujeto a Ax ≤ b;

con el correspondiente asimétrica doble problema,

Minimize b^TSí. sujeto a A^TSí. = c, Sí. ≥ 0.

Hay dos ideas fundamentales en 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 siempre es mayor o igual que el valor de la función objetivo del primal en cualquier solución factible. El teorema de la dualidad fuerte establece que si el primal tiene una solución óptima, x^*, entonces el dual también tiene una solución óptima, y^*, y c^Tx^*=b^Ty^*.

Un programa lineal también puede ser ilimitado o inviable. La teoría de la dualidad nos dice que si el primal no está acotado, entonces el dual es inviable por el teorema de la dualidad débil. Asimismo, si el dual es ilimitado, entonces el primal debe ser inviable. Sin embargo, es posible que tanto el dual como el primario sean inviables. Ver programa lineal dual para más detalles y varios ejemplos más.

Variaciones

Dualidades de cobertura/embalaje

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

Minimizar: b^TSí.,

sujeto a: A^TSí. ≥ c, Sí. ≥ 0,

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

El dual de un LP de cobertura es un LP de empaque, un programa lineal de la forma:

Maximizar: c^Tx,

sujeto a: Ax ≤ b, x ≥ 0,

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

Ejemplos

Los LP de cobertura y empaquetamiento comúnmente surgen como una relajación de programación lineal de un problema combinatorio y son importantes en el estudio de algoritmos de aproximación. Por ejemplo, las relajaciones LP del problema de empaquetamiento de conjuntos, el problema de conjuntos independientes y el problema de coincidencia son PL de empaquetamiento. Las relajaciones de PL del problema de cobertura de conjuntos, el problema de cobertura de vértices y el problema de conjuntos dominantes también cubren PL.

Encontrar una coloración fraccionaria de un gráfico 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.

Laxitud complementaria

Es posible obtener una solución óptima del dual cuando solo se conoce una solución óptima del primal utilizando el teorema de la holgura complementaria. El teorema establece:

Suponga que x = (x₁, x₂,..., x_n) es primal factible y que y = (y ₁, y₂,..., y_m) es factible dual. Sea (w₁, w₂,..., w_m) denota las correspondientes variables primarias de holgura y deja (z₁, z₂,..., z_n) indican las variables de holgura dual correspondientes. 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_i Sí._i= 0, para i= 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. Del mismo modo, si la variable de holgura j-ésima del dual no es cero, entonces la variable j-ésima 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 "sobrantes"), entonces las cantidades adicionales de ese recurso no deben tener valor. Del mismo modo, 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 (sin '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 y x ≤ 1 no se pueden satisfacer conjuntamente; en este caso, decimos que el LP es inviable. En segundo lugar, cuando el politopo es ilimitado 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 del 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 factibles básicas. La razón de esta elección de nombre es la siguiente. Sea d el número de variables. Entonces el teorema fundamental de las desigualdades lineales implica (para problemas factibles) que por cada vértice x^* de la región factible LP, existe un conjunto de d (o menos) restricciones de desigualdad del PL tales que, cuando tratamos esas restricciones d como igualdades, la solución única 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 las soluciones de LP. Este principio subyace al algoritmo simplex para resolver programas lineales.

Algoritmos

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

Algoritmos de intercambio de bases

Algoritmo simplex de Dantzig

El algoritmo simplex, desarrollado por George Dantzig en 1947, resuelve problemas de PL construyendo una solución factible en un vértice del politopo y luego recorriendo un camino en los bordes del politopo hacia los vértices con valores no decrecientes del objetivo función hasta que se alcance un óptimo seguro. En muchos problemas prácticos, "estancamiento" Ocurre: muchos pivotes se hacen sin aumento en la función objetivo. En problemas prácticos raros, las versiones habituales del algoritmo símplex pueden en realidad "ciclo". Para evitar ciclos, los investigadores desarrollaron nuevas reglas pivotantes.

En la práctica, el algoritmo simplex es bastante eficiente y se puede garantizar que encuentre el óptimo global si se toman ciertas precauciones contra los ciclos. Se ha demostrado que el algoritmo simplex resuelve problemas "aleatorios" problemas de manera eficiente, es decir, en un número cúbico de pasos, lo que es similar a su comportamiento en problemas prácticos.

Sin embargo, el algoritmo simplex tiene un comportamiento deficiente 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 cantidad de pasos exponenciales en el tamaño del problema. De hecho, durante algún tiempo no se supo si el problema de programación lineal era resoluble en tiempo polinomial, es decir, de clase de complejidad P.

Algoritmo cruzado

Al igual que el algoritmo simplex de Dantzig, el algoritmo entrecruzado es un algoritmo de intercambio de bases que gira entre bases. Sin embargo, el algoritmo entrecruzado no necesita mantener la viabilidad, sino que puede pasar de una base factible a una base no factible. El algoritmo entrecruzado no tiene complejidad de tiempo polinomial para la programación lineal. Ambos algoritmos visitan todos los vértices 2^D de un cubo (perturbado) de dimensión D, el cubo de Klee-Minty, en el peor de los casos.

Punto interior

A diferencia del algoritmo símplex, que encuentra una solución óptima al atravesar los bordes entre los vértices de un conjunto poliédrico, los métodos de punto interior se mueven por el interior de la región factible.

Algoritmo elipsoide, siguiendo a Khachiyan

Este es el primer algoritmo polinomio peor encontrado para la programación lineal. Para resolver un problema que tiene n variables y se pueden codificar en L bits de entrada, este algoritmo se ejecuta en O()n6L){displaystyle O(n^{6}L)} tiempo. Leonid Khachiyan resolvió este largo problema de complejidad en 1979 con la introducción del método ellipsoide. El análisis de convergencia tiene (número real) predecesores, en particular los métodos iterativos desarrollados por Naum Z. Shor y los algoritmos de aproximación de Arkadi Nemirovski y D. Yudin.

Algoritmo proyectivo de Karmarkar

El algoritmo de Khachiyan fue de gran importancia para establecer la capacidad de resolución en tiempo polinomial de los programas lineales. El algoritmo no fue un gran avance computacional, ya que el método simplex es más eficiente para todos, excepto para las familias de programas lineales 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 de proyecto para la programación lineal. El algoritmo de Karmarkar mejoró en el límite polinomio peor de Khachiyan (dar O()n3.5L){displaystyle O(n^{3.5}L)}). Karmarkar afirmó que su algoritmo era mucho más rápido en el LP práctico que el método simplex, una afirmación que creó un gran interés en los métodos interior-punto. Desde el descubrimiento de Karmarkar, se han propuesto y analizado muchos métodos de interiorismo.

Algoritmo 87 de Vaidya

En 1987, Vaidya propuso un algoritmo O()n3){displaystyle O(n^{3}} tiempo.

Algoritmo 89 de Vaidya

En 1989, Vaidya desarrolló un algoritmo que funciona O()n2.5){displaystyle O(n^{2.5} tiempo. Hablando formalmente, el algoritmo toma O()()n+d)1,5nL){displaystyle O(n+d)^{1.5}nL)} operaciones aritméticas en el peor de los casos, donde d{displaystyle d} es el número de limitaciones, n{displaystyle n} es el número de variables, y L{displaystyle L. es el número de bits.

Algoritmos de tiempo de escasez de entrada

En 2015, Lee y Sidford demostraron que, puede ser resuelto en O~ ~ ()()nnz()A)+d2)dL){displaystyle {tilde {}(nnz(A)+d^{2}{sqrt {d}L)} tiempo, donde nnz()A){displaystyle nnz(A)} representa el número de elementos no cero, y sigue tomando O()n2.5L){displaystyle O(n^{2.5}L)} en el peor caso.

Algoritmo de tiempo de multiplicación de matriz actual

En 2019, Cohen, Lee y Song mejoraron el tiempo de funcionamiento para O~ ~ ()()n⋅ ⋅ +n2.5− − α α /2+n2+1/6)L){displaystyle {tilde}(n^{omega) }+n^{2.5-alpha /2}+n^{2+1/6}L)} tiempo, ⋅ ⋅ {displaystyle omega } es el exponente de la multiplicación de matriz y α α {displaystyle alpha } es el doble exponente de la multiplicación de matriz. α α {displaystyle alpha } se define (aproximadamente) como el mayor número de tal manera que uno puede multiplicar n× × n{displaystyle ntimes n} matriz por n× × nα α {displaystyle ntimes n^{alpha } matriz O()n2){displaystyle O(n^{2}} tiempo. En un trabajo de seguimiento de Lee, Song y Zhang, reproducen el mismo resultado a través de un método diferente. Estos dos algoritmos permanecen O~ ~ ()n2+1/6L){displaystyle {tilde}(n^{2+1/6}L)} cuando ⋅ ⋅ =2{displaystyle omega =2} y α α =1{displaystyle alpha =1}. El resultado debido a Jiang, Song, Weinstein y Zhang mejoró O~ ~ ()n2+1/6L){displaystyle {tilde}(n^{2+1/6}L)} a O~ ~ ()n2+1/18L){displaystyle {tilde}(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 símplex y métodos de puntos interiores son similares para aplicaciones rutinarias de programación lineal. Sin embargo, para tipos específicos de problemas de PL, 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 apoyo conjunto de variables activas siendo típicamente más pequeño para el último.

Problemas abiertos y trabajos recientes

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.

• ¿El LP admite un algoritmo de tiempo polinomio fuerte?
• ¿El LP admite un algoritmo fuertemente polinomio-tiempo para encontrar una solución estrictamente complementaria?
• ¿El LP admite un algoritmo de tiempo polinomio en el número real (costo único) modelo de cálculo?

Este conjunto de problemas estrechamente relacionados ha sido citado por Stephen Smale como uno de los 18 mayores problemas sin resolver del siglo XXI. En palabras de Smale, la tercera versión del problema 'es el principal problema sin resolver de la teoría de la programación lineal'. Si bien existen algoritmos para resolver la programación lineal en tiempo polinomial débil, como los métodos elipsoidales y las técnicas de punto interior, aún no se han encontrado algoritmos que permitan un rendimiento de tiempo polinomial fuerte 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 tal vez también permitiría ganancias prácticas en la resolución de grandes PL.

Aunque la conjetura de Hirsch fue refutada recientemente para dimensiones más altas, aún deja abiertas las siguientes preguntas.

• ¿Hay reglas fundamentales que conducen a variantes simples de tiempo polinomio?
• ¿Todos los gráficos politopales tienen diámetro polinomial?

Estas preguntas se relacionan con el análisis de rendimiento y el desarrollo de métodos similares a símplex. La inmensa eficiencia del algoritmo simplex en la práctica, a pesar de su rendimiento teórico en tiempo exponencial, sugiere que puede haber variaciones de simplex que se ejecuten 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 se puede resolver en un tiempo fuertemente polinomial.

El algoritmo símplex y sus variantes pertenecen a la familia de algoritmos de seguimiento de aristas, llamados así porque resuelven problemas de programación lineal moviéndose de vértice a vértice a lo largo de las aristas de un politopo. Esto significa que su rendimiento teórico está limitado por el número máximo de aristas entre dos vértices en el politopo LP. Como resultado, nos interesa conocer el diámetro máximo teórico de grafos de los grafos politópicos. 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 probar si algún politopo tiene un diámetro superpolinomial. Si existen tales politopos, entonces ninguna variante de seguimiento de bordes puede ejecutarse en tiempo polinomial. Las preguntas sobre el diámetro del politopo 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 conservan la viabilidad (principal 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. 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. A diferencia de los gráficos politópicos, se sabe que los gráficos de politopos de disposición tienen un diámetro pequeño, lo que permite la posibilidad de un algoritmo de pivote entrecruzado de tiempo fuertemente polinomial sin resolver preguntas sobre el diámetro de los politopos generales.

Incógnitas enteras

Si se requiere que todas las variables desconocidas sean números enteros, entonces el problema se llama un problema de programación entera (IP) o programación lineal entera (ILP). A diferencia de la programación lineal, que puede resolverse eficientemente en el peor de los casos, los problemas de programación entera son en muchas situaciones prácticas (aquellas con variables acotadas) NP-difíciles. La programación de enteros 0-1 o programación de enteros binarios (BIP) es el caso especial de la programación de enteros donde las variables deben ser 0 o 1 (en lugar de números enteros arbitrarios). Este problema también se clasifica como NP-difícil y, de hecho, la versión de decisión era 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 llama un problema de programación de enteros mixtos (lineal) (MIP o MILP). 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 problemas en los que la matriz de restricciones es totalmente unimodular y los lados derechos de las restricciones son números enteros o, más en general, donde el sistema tiene la propiedad de integralidad dual total (TDI).

Los algoritmos avanzados para resolver programas lineales enteros incluyen:

• método cut-plane
• Subdivisión y límites
• Rama y corte
• Subdivisión y precio
• si el problema tiene alguna estructura extra, puede ser posible aplicar la generación de columna retardada.

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

Programas lineales integrales

Se dice que un programa lineal en variables reales integral si tiene al menos una solución óptima que es integral, es decir, hecha de sólo valores enteros. Del mismo modo, un poliedro P={}x▪ ▪ Ax≥ ≥ 0}{displaystyle P={xmid Axgeq 0} se dice que integral de todas las funciones objetivas c, el programa lineal {}maxcx▪ ▪ x▪ ▪ P}{displaystyle {max cxmid xin P} tiene un óptimo xAlternativa Alternativa {displaystyle x^{*} con coordenadas enteros. Como observó Edmonds y Giles en 1977, se puede decir equivalentemente que el poliedro P{displaystyle P} es integral si por cada función objetiva integral c, el óptimo valor del programa lineal {}maxcx▪ ▪ x▪ ▪ P}{displaystyle {max cxmid xin P} es un entero.

Los programas lineales integrales tienen una 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, la envolvente convexa de las soluciones es un poliedro integral; si este poliedro tiene una descripción agradable/compacta, entonces podemos encontrar eficientemente la solución factible óptima 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 consistente en toda la literatura, por lo que se debe tener cuidado de distinguir los siguientes dos conceptos,

• en una programa lineal entero, descritos en la sección anterior, las variables se limitan por la fuerza a ser enteros, y este problema es NP-hard en general,
• en una programa lineal integral, descrito en esta sección, las variables no se limitan a ser enteros, sino que se ha demostrado de alguna manera que el problema continuo siempre tiene un valor óptimo integral (asumiendo c es integral), y este valor óptimo se puede encontrar eficientemente ya que todos los programas lineales de tamaño polinomio se pueden resolver en el tiempo polinomio.

Una forma común de probar que un poliedro es integral es mostrar que es totalmente unimodular. Hay otros métodos generales que incluyen la propiedad de descomposición de enteros y la integralidad dual total. Otros LP integrales específicos bien conocidos incluyen el politopo coincidente, los poliedros de celosía, los poliedros de flujo submodular y la intersección de dos polimatroides/g generalizados, p. véase Schrijver 2003.

Lenguajes de resolución y scripting (programación)

Licencias permisivas:

Licencias copyleft (recíprocas):

MINTO (Mixed Integer Optimizer, un solucionador de programación de números enteros que utiliza un algoritmo de bifurcación y límite) tiene un código fuente disponible públicamente, pero no es de código abierto.

Licencias propietarias: