Esta página aún no se ha traducido para esta versión. Puede ver la versión más reciente de esta página en inglés.

Algoritmos de programación lineal

Definición de programación lineal

La programación lineal es el problema de encontrar un vector que minimiza una función linealx FTX sujetos a restricciones lineales:

minxfTx

tal que uno o más de los siguientes retener:

≤ = ≤ ≤.A·xb
Aeq·xbeq
lxu

Algoritmo de punto interiorlinprog

El algoritmo es muy similar al.linprog'interior-point'Algoritmointerior-point-convexquadprog También comparte muchas características con el algoritmo.linprog'interior-point-legacy' Estos algoritmos tienen el mismo esquema general:

  1. PRESOLVE, lo que significa simplificación y conversión del problema a un formato estándar.

  2. Genere un punto inicial. La elección de un punto inicial es especialmente importante para resolver los algoritmos de punto interior de manera eficiente, y este paso puede llevar mucho tiempo.

  3. Iteraciones del corrector de predictores para resolver las ecuaciones de KKT. Este paso suele ser el que más tiempo consume.

PRESOLVE

El algoritmo comienza por intentar simplificar el problema eliminando redundancias y simplificando las restricciones. Las tareas realizadas durante el paso de PRESOLVE incluyen:

  • Compruebe si alguna variable tiene límites superiores e inferiores iguales. Si es así, Compruebe la viabilidad y, a continuación, corrija y quite las variables.

  • Compruebe si cualquier restricción de desigualdad lineal implica sólo una variable. Si es así, Compruebe la viabilidad y cambie la restricción lineal a un límite.

  • Compruebe si cualquier restricción de igualdad lineal implica solo una variable. Si es así, Compruebe la viabilidad y, a continuación, corrija y quite la variable.

  • Compruebe si alguna matriz de restricción lineal tiene cero filas. Si es así, Compruebe la viabilidad y elimine las filas.

  • Compruebe si los límites y las restricciones lineales son coherentes.

  • Compruebe si las variables aparecen sólo como términos lineales en la función objetiva y no aparecen en ninguna restricción lineal. Si es así, Compruebe la viabilidad y el rebote, y corrija las variables en sus límites apropiados.

  • Cambie las restricciones de desigualdad lineal a las restricciones de igualdad lineales agregando variables de holgura.

Si el algoritmo detecta un problema infactible o ilimitado, detiene y emite un mensaje de salida adecuado.

El algoritmo puede llegar a un único punto factible, que representa la solución.

Si el algoritmo no detecta un problema no factible o ilimitado en el paso de PRESOLVE, continúa, si es necesario, con los otros pasos. Al final, el algoritmo reconstruye el problema original, deshaciendo cualquier transformación PRESOLVE. Este paso final es el paso de postresolución.

Para simplificar, si el problema no se resuelve en el paso de PRESOLVE, el algoritmo desplaza todos los límites inferiores finitos a cero.

Generar punto inicial

Para establecer el punto inicial, el algoritmo hace lo siguiente.x0

  1. Initialize to, donde está el número de elementos del vector de función objetivo.x0ones(n,1)nf

  2. Convierta todos los componentes delimitados para que tengan un límite inferior de 0. Si el componente tiene un límite superior finito, entonces.iu(i)x0(i) = u/2

  3. Para los componentes que tienen solo un límite, modifique el componente si es necesario para que se encuentran estrictamente dentro del límite.

  4. Para poner cerca de la ruta central, tome un paso de corrector de predictores y, a continuación, modifique la posición resultante y las variables de holgura para que se encuentran bien dentro de los límites.x0 Para más detalles sobre la ruta central, véase Nocedal y Wright, Página 397.[7]

Predictor-corrector

Similar al, el algoritmo intenta encontrar un punto donde las condiciones se mantenga.fminconalgoritmo de punto interiorinterior-point-convexKarush-Kuhn-Tucker (KKT) Para describir estas ecuaciones para el problema de programación lineal, considere la forma estándar del problema de programación lineal después del preprocesamiento:

minxfTx subject to {A¯x=b¯x+t=ux,t0.

  • Supongamos por ahora que todas las variables tienen al menos un límite finito. Cambiando y negando componentes, si es necesario, esta suposición significa que todos los componentes tienen un límite inferior de 0.x

  • A¯ es la matriz lineal extendida que incluye tanto desigualdades lineales como ecualidades lineales. b¯ es el vector de igualdad lineal correspondiente. A¯ también incluye términos para extender el vector con variables de holgura que convierten las restricciones de desigualdad en restricciones de igualdad:xs

    A¯x=(Aeq0AI)(x0s),

    Dóndex0 significa el vector original.x

  • es el vector de los pantalones que convierten los límites superiores a las equalidades.t

El Lagrangio para este sistema involucra los siguientes vectores:

  • , Los multiplicadores de Lagrange asociados con las equalidades linealesy

  • , Multiplicadores de Lagrange asociados con el límite inferior (restricción positividad)v

  • , Los multiplicadores de Lagrange asociados con el límite superiorw

El Lagrangio es

L=fTxyT(A¯xb¯)vTxwT(uxt).

Por lo tanto, las condiciones KKT para este sistema son

fA¯Tyv+w=0A¯x=b¯x+t=uvixi=0witi=0(x,v,w,t)0.

El algoritmo predice primero un paso de la fórmula de Newton-Raphson y, a continuación, calcula un paso de corrector. El corrector intenta reducir el residuo en las ecuaciones de complementariedad no lineales sizi = 0. El paso de Newton-Raphson es

(0A¯T0IIA¯0000I0I00V00X000W0T)(ΔxΔyΔtΔvΔw)=(fA¯Tyv+wA¯xb¯uxtVXWT)=(rdrprubrvxrwt),(1)

donde,,, y son matrices diagonales que corresponden a los vectores,,, y respectivamente.XVWTxvwt Los vectores residuales en el lado derecho más lejano de la ecuación son:

  • Rd, el doble residuo

  • Rp, el residuo primigenio

  • Rub, el residuo de límite superior

  • Rvx, el residuo de complementariedad de menor límite

  • Rwt, el residuo de complementariedad de límite superior

La pantalla iterativa informa de estas cantidades:

Primal infeasibility=rp1+rub1Dual infeasibility=rd.

Para resolverlo, primero conviértalo a la forma de matriz simétricaEcuación 1

(DA¯TA¯0)(ΔxΔy)=(Rrp),(2)

Dónde

D=X1V+T1WR=rdX1rvx+T1rwt+T1Wrub.

Toda la matriz invierte en las definiciones de y son simples de calcular porque las matrices son diagonales.DR

Para derivar de, tenga en cuenta que la segunda fila de es la misma que la segunda fila de matriz de.Ecuación 2Ecuación 1Ecuación 2Ecuación 1 La primera fila viene de resolver las dos últimas filas de Δ y Δ, y luego resolver para Δ.Ecuación 2Ecuación 1vwt

es simétrico, pero no es positivo definitivo debido al término –.Ecuación 2D Por lo tanto, no se puede resolver utilizando una factorización Cholesky. Unos pocos pasos más conducen a una ecuación diferente que es positivo definitivo, y por lo tanto puede ser resuelto eficientemente por factorización Cholesky.

El segundo conjunto de filas de esEcuación 2

A¯Δx=rp

y el primer conjunto de filas es

DΔx+A¯TΔy=R.

Sustituyendo

Δx=D1A¯TΔy+D1R

Da

A¯D1A¯TΔy=A¯D1Rrp.(3)

Por lo general, la forma más eficiente de encontrar el paso de Newton es resolver para Δ usando la factorización de Cholesky.Ecuación 3y La factorización colesky es posible porque la matriz que multiplica Δ es obviamente simétrica y, en ausencia de degeneración, es positiva.y Después, para encontrar el paso de Newton, sustituto de espalda para encontrar Δ, Δ, Δ y Δ. Sin embargo, cuandoxtvw A¯ tiene una columna densa, puede ser más eficiente de resolver en su lugar.Ecuación 2 El algoritmo de punto interior elige el algoritmo de la solución en función de la densidad de las columnas.linprog

Para obtener más detalles del algoritmo, consulte Mehrotra.[6]

Después de calcular el paso de Newton corregido, el algoritmo realiza más cálculos para obtener un paso actual más largo, y para prepararse para mejores pasos posteriores. Estos cálculos de corrección múltiple pueden mejorar el rendimiento y la robustez. Para obtener más información, consulte Gondzio.[4]

El algoritmo de predictor-corrector es en gran parte el mismo que la versión completa, a excepción de los términos cuadráticos.quadprog'interior-point-convex' Ver.Full predictor-corrector

Condiciones de detención

El algoritmo de predictor-corrector recorre en iteración hasta que alcanza un punto que es factible (satisface las restricciones dentro de las tolerancias) y donde los tamaños de paso relativo son pequeños. En concreto, defina

ρ=max(1,A¯,f,b¯).

El algoritmo se detiene cuando se cumplen todas estas condiciones:

rp1+rub1ρTolConrdρTolFunrcTolFun,

Dónde

rc=maxi(min(|xivi|,|xi|,|vi|),min(|tiwi|,|ti|,|wi|)).

Rc mide esencialmente el tamaño de los residuos de complementariedad y, que son cada uno de los vectores de ceros en una solución.xvtw

Programación lineal de punto interior heredado

Introducción

El método de la herencia de punto interior predeterminado se basa en LIPSOL (), que es una variante de[52] El algoritmo de corrector predictor de Mehrotra (), un[47] método de punto interior primario-dual.

Algoritmo principal

El algoritmo comienza aplicando una serie de pasos de preprocesamiento (ver).Preprocesamiento Después del preprocesamiento, el problema tiene la forma

minxfTx such that {Ax=b0xu.(4)

Las restricciones de los límites superiores se incluyen implícitamente en la matriz de restricción.A Con la adición de variables de Slack primarias, se convierte ensEcuación 4

minxfTx such that {Ax=bx+s=ux0, s0.(5)

que se conoce como el problema: consiste en las variables primarias y consiste en las variables primarias de la holgura.primalxs El problema esdual

maxbTyuTw  such that  {ATyw+z=fz0, w0,(6)

donde y consisten en las variables duales y consiste en los dobles pantalones.yw z el condiciones de optimalidad para este programa lineal, es decir, el primitivo y el doble, sonEcuación 5Ecuación 6

F(x,y,z,s,w)=(Axbx+suATyw+zfxizisiwi)=0,                 x0, z0, s0, w0,(7)

Dónde XiZi Y siWi denotan la multiplicación por componentes.

Las ecuaciones cuadráticas xizi = 0 Y siwi = 0 se denominan los Complementariedad condiciones para el programa lineal; las otras ecuaciones (lineales) se denominan Condiciones.feasibility La cantidad

XTZ + sTW

es el brecha de dualidad, que mide el residuo de la porción de complementariedad de cuandoF (x,z,s,w) ≥ 0.

El algoritmo es un Algoritmo primal-dual, lo que significa que tanto los programas primarios como los duales se resuelven simultáneamente. Puede ser considerado como un método de Newton, aplicado al sistema lineal-cuadrático F(x,y,z,s,w) = 0 en, mientras que al mismo tiempo mantener los iterados,,, y positivo, por lo tanto el nombre del método de punto interior.Ecuación 7xzws (Los iterados se encuentran en la región estrictamente interior representada por las restricciones de desigualdad en.)Ecuación 5

El algoritmo es una variante del algoritmo de predictor-corrector propuesto por Mehrotra. Considere la posibilidad de iterar v = [x;y;z;s;w]Dónde [x;z;s;w] > 0 Primero calcule la llamada direcciónprediction

Δvp=(FT(v))1F(v),

que es la dirección de Newton; entonces la llamada direccióncorrector

Δvc=(FT(v))1F(v+Δvp)μe^,

Dónde μ > 0 se llama el Centrado parámetro y debe elegirse cuidadosamente. e^ es un vector cero-uno con los correspondientes a las ecuaciones cuadráticas en (), es decir, las perturbaciones sólo se aplican a las condiciones de complementariedad, que son todas cuadráticas, pero no a las condiciones de viabilidad, que son todas lineales.Fv Las dos direcciones se combinan con un parámetro de longitud de paso α > 0 y actualizar para obtener la nueva iteraciónvv+:

v+=v+α(Δvp+Δvc),

donde se elige el parámetro de longitud de paso para queα

V+ = [X+; y+; z+; s+; w+]

Satisface

[X+; z+; s+; w+] > 0.

Al resolver para las direcciones de predictor/corrector anteriores, el algoritmo calcula una factorización directa (dispersa) en una modificación de los factores de Cholesky de A·AT. Si tieneA columnas densas, en su lugar utiliza el Fórmula de Sherman-Morrison. Si esa solución no es adecuada (el residuo es demasiado grande), realiza una factorización de LDL de una forma de sistema aumentada de las ecuaciones de paso para encontrar una solución. (Consulte la página de referencia de la función.)Ejemplo 4 — la estructura de D (MATLAB)MATLAB®ldl

A continuación, el algoritmo se repite hasta que convergen los iterados. Los criterios de parada principales son uno estándar:

max(rbmax(1,b),rfmax(1,f),rumax(1,u),|fTxbTy+uTw|max(1,|fTx|,|bTyuTw|))tol,

Dónde

rb=Axbrf=ATyw+zfru={x}+su

son la viabilidad primaria residual, doble residual y de límite superior, respectivamente ({x} significa aquellos con límites superiores finitos), yx

fTxbTy+uTw

es la diferencia entre los valores de objetivos primarios y duales, y es cierta tolerancia.tol La suma de la los criterios de detención miden los errores relativos totales en las condiciones de optimalidad.Ecuación 7

La medida de la inviabilidad primordial es ||rb||, y la medida de la doble inviabilidad es ||rf||, donde la norma es la norma euclidiana.

Preprocesamiento

El algoritmo comienza por intentar simplificar el problema eliminando redundancias y simplificando las restricciones. Las tareas realizadas durante el paso de PRESOLVE incluyen:

  • Compruebe si alguna variable tiene límites superiores e inferiores iguales. Si es así, Compruebe la viabilidad y, a continuación, corrija y quite las variables.

  • Compruebe si cualquier restricción de desigualdad lineal implica sólo una variable. Si es así, Compruebe la viabilidad y cambie la restricción lineal a un límite.

  • Compruebe si cualquier restricción de igualdad lineal implica solo una variable. Si es así, Compruebe la viabilidad y, a continuación, corrija y quite la variable.

  • Compruebe si alguna matriz de restricción lineal tiene cero filas. Si es así, Compruebe la viabilidad y elimine las filas.

  • Compruebe si los límites y las restricciones lineales son coherentes.

  • Compruebe si las variables aparecen sólo como términos lineales en la función objetiva y no aparecen en ninguna restricción lineal. Si es así, Compruebe la viabilidad y el rebote, y corrija las variables en sus límites apropiados.

  • Cambie las restricciones de desigualdad lineal a las restricciones de igualdad lineales agregando variables de holgura.

Si el algoritmo detecta un problema infactible o ilimitado, detiene y emite un mensaje de salida adecuado.

El algoritmo puede llegar a un único punto factible, que representa la solución.

Si el algoritmo no detecta un problema no factible o ilimitado en el paso de PRESOLVE, continúa, si es necesario, con los otros pasos. Al final, el algoritmo reconstruye el problema original, deshaciendo cualquier transformación PRESOLVE. Este paso final es el paso de postresolución.

Para simplificar, el algoritmo desplaza todos los límites inferiores a cero.

Aunque estos pasos de preprocesamiento pueden hacer mucho para acelerar la parte iterativa del algoritmo, si el Los multiplicadores de Lagrange son obligatorios, los pasos de preprocesamiento deben deshacerse ya que los multiplicadores calculados durante el algoritmo son para el problema transformado, y no el original. Por lo tanto, si se solicitan los multiplicadores, esta transformación de nuevo no se calcula y puede ahorrar algún tiempo computacionalmente.not

Algoritmo dual-simplex

En un nivel alto, el algoritmo realiza esencialmente un algoritmo simplex en el.linprog'dual-simplex'problema dual

El algoritmo comienza por el preprocesamiento como se describe en.Preprocesamiento Para más detalles, véase Andersen y Andersen y Nocedal y Wright, capítulo 13.[1][7] Este preprocesamiento reduce el problema de programación lineal original a la forma de:Ecuación 4

minxfTx such that {Ax=b0xu.

y son versiones transformadas de las matrices de restricciones originales.Ab Este es el problema primigenio.

La viabilidad primigenia puede definirse en términos de la + Función

x+={xif x>00if x0.

La medida de la inviabilidad primordial es

Primal infeasibility=((lbx)+)2+((xub)+)2+((Axb)+)2+|Aeqxbeq|2.

Como se explica en, el doble problema es encontrar vectores y, y un vector variable de Slack que resuelvenEcuación 6ywz

maxbTyuTw  such that  {ATyw+z=fz0, w0.

La medida de la doble inviabilidad es

Dual infeasibility=ATy+zwf2.

Es bien sabido (por ejemplo, ver) que cualquier solución finita del doble problema da una solución al problema primigenio, y cualquier solución finita del problema primigenio da una solución al problema dual.[7] Además, si el problema primario o dual es ilimitado, entonces el otro problema es inviable. Y si el problema primario o dual es inviable, entonces el otro problema es inviable o ilimitado. Por lo tanto, los dos problemas son equivalentes en términos de obtener una solución finita, si existe uno. Debido a que los problemas primarios y duales son matemáticamente equivalentes, pero los pasos computacionales difieren, puede ser mejor resolver el problema primario resolviendo el problema dual.

Para ayudar a aliviar la degeneración (ver Nocedal y Wright, página 366), el algoritmo simplex doble comienza por perturbar la función objetiva.[7]

La fase 1 del algoritmo simplex dual es encontrar un punto dual factible. El algoritmo lo hace resolviendo un problema de programación lineal auxiliar.

 Fase 1 contorno

Durante la fase 2, el solucionador elige repetidamente una variable de entrada y una variable de salida. El algoritmo elige una variable de salida según una técnica sugerida por Forrest y Goldfarb llamada doble precio de borde más inclinado.[3] El algoritmo elige una variable de entrada utilizando la variación de la prueba de ratio de Harris sugerida por Koberstein.[5] Para ayudar a aliviar la degeneración, el algoritmo puede introducir perturbaciones adicionales durante la fase 2.

 Fase 2 contorno

El solucionador se repite, intentando mantener la doble viabilidad y reduciendo la infactibilidad primaria, hasta que la solución al problema reducido y perturbado es a la vez factible y dual factible. El algoritmo desenrolla las perturbaciones que introdujo. Si la solución (al problema perturbado) es dual inviable para el problema no perturbado (original), entonces el solucionador restaura la viabilidad dual usando los algoritmos Primal simplex o fase 1. Por último, el solucionador desenrolla los pasos de preprocesamiento para devolver la solución al problema original.

Variables básicas y no básicas

En esta sección se definen los términos y para un problema de programación lineal.basisnonbasisbasic feasible solutions La definición asume que el problema se da en el siguiente formulario estándar:

minxfTx such that {Ax=b,lbxub.

(Tenga en cuenta que y no son la matriz y Vector definiendo las desigualdades en el problema original.)Ab Supongamos que es una-por-matriz, de rangoAmn m < n, cuyas columnas son {a1,a2, ..., Unn}. Supongamos que {ai1,ai2,...,aim} es una base para el espacio de columna de, con index set = {ABi1,i2, ..., mem}, y que = {1, 2,..., n} \ es el complemento de.NBB La submatrizAB se llama a y la submatriz complementariabasisAN se llama a.nonbasis El vector de esbasic variablesxB y el vector de esnonbasic variablesxN. En cada iteración de la fase 2, el algoritmo reemplaza una columna de la base actual con una columna de la no base y actualiza las variablesxB YxN en consecuencia.

Si es una solución parax A·x = b y todas las variables no básicas enxN son iguales a sus límites inferior o superior, se llama a.xbasic solution Si, además, las variables básicas enxB satisfacer sus límites inferior y superior, por lo que es un punto factible, se llama a.xxbasic feasible solution

Referencias

[1] Andersen, E. D., and K. D. Andersen. Presolving in linear programming. Math. Programming 71, 1995, pp. 221–245.

[2] Applegate, D. L., R. E. Bixby, V. Chvátal and W. J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton University Press, 2007.

[3] Forrest, J. J., and D. Goldfarb. Steepest-edge simplex algorithms for linear programming. Math. Programming 57, 1992, pp. 341–374.

[4] Gondzio, J. “Multiple centrality corrections in a primal dual method for linear programming.” Computational Optimization and Applications, Volume 6, Number 2, 1996, pp. 137–156. Available at http://www.maths.ed.ac.uk/~gondzio/software/correctors.ps.

[5] Koberstein, A. Progress in the dual simplex algorithm for solving large scale LP problems: techniques for a fast and stable implementation. Computational Optim. and Application 41, 2008, pp. 185–204.

[6] Mehrotra, S. “On the Implementation of a Primal-Dual Interior Point Method.” SIAM Journal on Optimization, Vol. 2, 1992, pp 575–601.

[7] Nocedal, J., and S. J. Wright. Numerical Optimization, Second Edition. Springer Series in Operations Research, Springer-Verlag, 2006.