Programación lineal

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 5 de mayo de 2022; las comprobaciones requieren 5 ediciones .

La programación lineal es una disciplina matemática dedicada a la teoría y los métodos para resolver problemas extremos en conjuntos de espacio vectorial -dimensional definidos por sistemas de ecuaciones lineales y desigualdades. $norte$

La programación lineal (PL) es un caso especial de programación convexa , que a su vez es un caso especial de programación matemática . Al mismo tiempo, es la base de varios métodos para resolver problemas de programación entera y no lineal . Una generalización de la programación lineal es la programación lineal fraccionaria .

Muchas propiedades de los problemas de programación lineal también se pueden interpretar como propiedades de los poliedros y, por lo tanto, se pueden formular y demostrar geométricamente.

Historia

Estudios matemáticos de problemas económicos individuales, la formalización matemática de material numérico se llevó a cabo ya en el siglo XIX . En el análisis matemático del proceso de producción ampliado se utilizaron relaciones algebraicas, su análisis se realizó mediante cálculo diferencial . Esto permitió tener una idea general del problema.

El desarrollo de la economía requería indicadores cuantitativos, y en la década de 1920 se creó un equilibrio intersectorial ( IOB ). Fue él quien sirvió de impulso en la creación y estudio de modelos matemáticos. El desarrollo de la MOB en 1924-1925 en la URSS influyó en el trabajo del economista y estadístico Vasily Vasilievich Leontiev . Desarrolló un modelo intersectorial de producción y distribución de productos.

En 1938, Leonid Vitalievich Kantorovich , en el curso de la consulta científica, comenzó a estudiar la tarea puramente práctica de elaborar el mejor plan para cargar máquinas peladoras (fideicomiso de madera contrachapada). Esta tarea no se prestaba a los métodos convencionales. Quedó claro que la tarea no era aleatoria. [una]

En 1939, Leonid Kantorovich publicó el trabajo "Métodos matemáticos de organización y planificación de la producción", en el que formuló una nueva clase de problemas extremos con restricciones y desarrolló un método eficaz para resolverlos, sentando así las bases de la programación lineal.

El estudio de tales problemas condujo a la creación de una nueva disciplina científica de programación lineal y abrió una nueva etapa en el desarrollo de métodos económicos y matemáticos.

En 1949, el matemático estadounidense George Bernard Dantzig desarrolló un método efectivo para resolver problemas de programación lineal (LPP): el método simplex . [una]

El término "programación" debe entenderse en el sentido de "planificación" (una de las traducciones del inglés programación ). Fue propuesto a mediados de la década de 1940 por George Danzig, uno de los fundadores de la programación lineal, antes de que las computadoras se usaran para resolver problemas de optimización lineal .

El método del punto interior fue mencionado por primera vez por I. I. Dikin en 1967 . [2] . Estos estudios continuaron, incluso por parte de científicos nacionales. En la década de 1970, V. G. Zhadan logró obtener los principales resultados y desarrollar un enfoque general para la construcción de métodos de puntos interiores para resolver problemas de programación lineal y no lineal, basados en la transformación de espacios; proponer métodos numéricos barrera-proyectivos y barrera-newtonianos.

Tareas

El problema general (estándar) de la programación lineal es el problema de encontrar el mínimo de una función objetivo lineal (forma lineal) de la forma [3] :

f(x)=\sum_{j=1}^{n}c_{j}x_{j}=c_{1}x_{1}+c_{2}x_{2}+\ldots + c_{n}x_{n}.

Un problema en el que aparecen restricciones en forma de desigualdades se denomina problema básico de programación lineal (BLP)

\sum _{j=1}^{n}a_{ij}x_{j}\geqslant b_{i},\quad (i=1,\;2,\;\ldots,\;m)

x_{j}\geqslant 0.\quad (j=1,\;2,\;\ldots,\;n)

El problema de programación lineal tendrá forma canónica si en el problema principal en lugar del primer sistema de desigualdades hay un sistema de ecuaciones con restricciones en forma de igualdad [4] :

\sum _{j=1}^{n}a_{ij}x_{j}=b_{i}.\quad (i=1,\;2,\;\ldots,\;m)

El problema principal puede reducirse a uno canónico introduciendo variables adicionales.

Los problemas de programación lineal de la forma más general (problemas con restricciones mixtas: igualdades y desigualdades, presencia de variables libres de restricciones) pueden reducirse a cambios equivalentes (que tienen el mismo conjunto de soluciones) de variables y reemplazo de igualdades por un par de desigualdades [5] .

Es fácil ver que el problema de encontrar el máximo puede ser reemplazado por el problema de encontrar el mínimo tomando los coeficientes con el signo opuesto. $C$

Ejemplos de problemas

Coincidencia máxima

Considere el problema de coincidencia máxima en un gráfico bipartito : hay varios niños y niñas, y para cada niño y niña se sabe si se gustan. Es necesario casarse con el máximo número de parejas con simpatía mutua.

Introduzcamos variables que correspondan a la pareja del -ésimo niño y la -ésima niña y satisfagamos las restricciones: $x_{ij}$ $i$ $j$

0\leqslant x_{{ij}}\leqslant 1,

x_{1j}+x_{2j}+\ldots +x_{nj}\leqslant 1,

x_{{i1}}+x_{{i2}}+\ldots +x_{{im}}\leqslant 1,

con una función objetivo , donde son iguales a 1 o 0 dependiendo de si el -ésimo niño y la -ésima niña son amables entre sí. Se puede demostrar que entre las soluciones óptimas a este problema existe una solución entera. Variables iguales a 1 corresponderán a parejas que deberían estar casadas. ${\displaystyle f=c_{11}x_{11}+c_{12}x_{12}+\ldots +c_{nm}x_{nm))$ $c_{ij}$ $i$ $j$

Caudal máximo

Sea un gráfico (con aristas dirigidas) en el que para cada arista se indique su capacidad. Y se dan dos vértices: un sumidero y una fuente. Es necesario especificar para cada borde cuánto fluido fluirá a través de él (no más que su capacidad) para maximizar el flujo total desde la fuente hasta el sumidero (el fluido no puede aparecer ni desaparecer en todos los vértices excepto en la fuente y el sumidero, respectivamente).

Tomemos como variables la cantidad de fluido que circula por el borde. Después $x_{yo}$ $i$

0\leqslant x_{i}\leqslant c_{i},

donde es la capacidad de la arista th. Estas desigualdades deben complementarse con la igualdad de la cantidad de fluido entrante y saliente para cada vértice, excepto para el sumidero y la fuente. Como una función, es natural tomar la diferencia entre la cantidad de líquido que sale y entra en la fuente. $c_{yo}$ $i$ $F$

Una generalización del problema anterior es el flujo máximo de costo mínimo. En este problema se dan los costos para cada arista y es necesario elegir entre los flujos máximos el flujo con el costo mínimo. Esta tarea se reduce a dos problemas de programación lineal: primero, debe resolver el problema del flujo máximo y luego agregar a este problema la restricción , donde está el valor del flujo máximo, y resolver el problema con una nueva función : el costo del flujo. $f(x)\geqslant m$ $metro$ $f(x)$

Estos problemas se pueden resolver más rápido que los algoritmos generales para resolver problemas de programación lineal debido a la estructura especial de ecuaciones y desigualdades.

Problema de transporte

Hay cierta carga homogénea que necesita ser transportada de los almacenes a las fábricas. Para cada almacén , se sabe cuánta carga hay en él , y para cada planta, se conoce su necesidad de carga. El costo de transporte es proporcional a la distancia del almacén a la planta (todas las distancias del -ésimo almacén a la -ésima planta son conocidas). Se requiere elaborar el plan de transporte más económico. $norte$ $metro$ $i$ $ai}$ $b_{j}$ $c_{ij}$ $i$ $j$

Las variables decisivas en este caso son - la cantidad de carga transportada desde el -ésimo almacén a la -ésima planta. Cumplen las restricciones: $x_{ij}$ $i$ $j$

x_{{i1}}+x_{{i2}}+\ldots +x_{{im}}\leqslant a_{i},

x_{{1j}}+x_{{2j}}+\ldots +x_{{nj}}\geqslant b_{j}.

La función objetivo tiene la forma: , que debe minimizarse. $f(x)=x_{{11}}c_{{11}}+x_{{12}}c_{{12}}+\ldots +x_{{nm}}c_{{nm}}$

Juego de suma cero

Hay una matriz de tamaño . El primer jugador elige un número del 1 al , el segundo - del 1 al . Luego verifican los números y el primer jugador obtiene puntos, y el segundo obtiene puntos ( - el número elegido por el primer jugador - el segundo). Necesitamos encontrar la estrategia óptima para el primer jugador. $A$ $n\veces m$ $norte$ $metro$ $a_{{ij}}$ $(-a_{{ij}})$ $i$ $j$

Deje en la estrategia óptima, por ejemplo, el primer jugador, el número debe elegirse con probabilidad . Entonces la estrategia óptima es una solución al siguiente problema de programación lineal: $i$ $Pi}$

0\leqslant p_{i}\leqslant 1,

p_{1}+\ldots +p_{n}=1,

a_{1i}p_{1}+a_{2i}p_{2}+\ldots +a_{ni}p_{n}\geqslant c\quad (i=1,\;\ldots,\;m ),

en el que se quiere maximizar la función . El valor en la solución óptima será la expectativa del peor de los casos del pago del primer jugador. $f(p_{1},\;\ldots,\;p_{n},\;c)=c$ $C$

Algoritmos de solución

El más famoso y ampliamente utilizado en la práctica para resolver el problema general de la programación lineal (LP) es el método simplex . A pesar de que el método simplex es un algoritmo bastante eficiente que ha mostrado buenos resultados en la resolución de problemas de PL aplicados, se trata de un algoritmo con complejidad exponencial . La razón de esto es la naturaleza combinatoria del método simplex, que enumera sucesivamente los vértices del poliedro de soluciones admisibles mientras busca la solución óptima.

El primer algoritmo polinomial , el método del elipsoide , fue propuesto en 1979 por el matemático soviético L. Khachiyan , resolviendo así un problema que llevaba mucho tiempo sin resolver. El método del elipsoide tiene una naturaleza no combinatoria completamente diferente a la del método símplex. Sin embargo, en términos computacionales, este método resultó ser poco prometedor. Sin embargo, el hecho mismo de la complejidad polinomial de los problemas condujo a la creación de toda una clase de algoritmos de LP efectivos: métodos de puntos interiores , el primero de los cuales fue el algoritmo de N. Karmarkar propuesto en 1984 . Algoritmos de este tipo utilizan una interpretación continua del problema de PL, cuando en lugar de enumerar los vértices del politopo de soluciones al problema de PL, se realiza una búsqueda a lo largo de trayectorias en el espacio de variables del problema que no pasan por los vértices. del politopo. El método de punto interior, que, a diferencia del método simplex, pasa por alto los puntos del interior del rango de tolerancia, utiliza métodos de función de barrera logarítmica de programación no lineal desarrollados en la década de 1960 por Fiacco y McCormick.

Otro método para resolver el PL es usando el algoritmo de Seidel:

El LP se da en forma canónica con variables y restricciones que componen el conjunto . $d$ $metro$ $H$
Si o , obtenga la solución básica óptima . ${\ estilo de visualización d = 1}$ $metro=0$ $H$
De lo contrario, elija una restricción aleatoria y calcule recursivamente la solución básica óptima para . $h\en H$ ${\displaystyle H\setminus \{h\))$
Si la solución básica óptima para no viola la restricción , devuélvela. ${\displaystyle H\setminus \{h\))$ $h$
De lo contrario, calcule la intersección del poliedro LP con el hiperplano y resuelva recursivamente el LP resultante con una variable. $h$ $d-1$

Este método tiene complejidad asintótica . $O(m\cdot d!)$

Problemas de programación lineal dual

Cada problema de programación lineal [6] de la forma

\sum _{j=1}^{n}a_{ij}x_{j}\leqslant c_{i},\;i={\overline {1,\;m));

x_{j}\geqslant 0,\;j={\overline {1,\;n));

F(x)=\sum _{j=1}^{n}b_{j}x_{j}\to \max

es posible en cierto modo comparar algún otro problema de programación lineal, llamado dual o conjugado con respecto al original o directo. La conexión entre los problemas original y dual radica principalmente en que la solución de uno de ellos puede obtenerse directamente de la solución del otro. Definamos el problema dual con respecto al problema original de programación lineal

Tarea inicial	Doble problema
$\sum _{j=1}^{n}a_{ij}x_{j}\leqslant c_{i},\;i={\overline {1,\;m))$	$y_{i}\geqslant 0,\;i={\overline {1,\;m))$
$x_{j}\geqslant 0,\;j={\overline {1,\;n))$	$\sum _{i=1}^{m}a_{ij}y_{i}\geqslant b_{j},\;j={\overline {1,\;n))$
$F(x)=\sum _{j=1}^{n}b_{j}x_{j}\to \max$	$T(y)=\sum_{i=1}^{m}c_{i}y_{i}\to \min$

Si los vectores y son soluciones admisibles de los problemas primal y dual, entonces , y la igualdad se logra si y sólo si y son soluciones óptimas. Si la función objetivo de uno de los dos problemas duales no está limitada (desde arriba para el original, desde abajo para el dual), entonces el área de soluciones factibles del otro problema está vacía. $X$ $y$ $F(x)\leqslant T(y)$ $X$ $y$

Si los vectores y son las soluciones óptimas de los problemas directo y dual, respectivamente, entonces se cumplen las siguientes igualdades $x^{*}$ $y^{*}$

x_{j}^{*}(\sum _{i=1}^{m}a_{ij}y_{i}^{*}-b_{j})=0,\;j={ \sobrelínea {1,\;n}};

y_{i}^{*}(\sum _{j=1}^{n}a_{ij}x_{j}^{*}-c_{i})=0,\;i={ \overline {1,\;m}}.

Es decir, para soluciones óptimas a los problemas primal y dual, las restricciones no tensas (se satisface la desigualdad estricta) corresponden a variables cero, y las variables distintas de cero (incluidas en el plan de soporte) corresponden a restricciones estrictas (se implementa la desigualdad no estricta). como igualdad) restricciones. Pero puede haber cero variables correspondientes a restricciones estrictas.

Estas propiedades de las soluciones duales pueden reducir significativamente el tiempo de solución si tiene que resolver un problema con una cantidad de restricciones mucho mayor que la cantidad de variables. Entonces es posible, habiendo resuelto el problema dual, encontrar su plan de soporte, luego de lo cual, habiendo seleccionado en el problema directo solo las restricciones correspondientes al plan de soporte (todas estas restricciones deben ser deformadas), resolver el sistema habitual de ecuaciones lineales para ellos.

Teorema. El problema dual del LP dual es el problema LP primario.

Prueba: Considere un LP directo de la forma bajo la condición . Asociemos el LP dual con él y obtengamos bajo la condición . Llevémoslo a otra forma, equivalente en significado: bajo la condición . Comparemos nuevamente el LP dual con él y obtengamos bajo la condición . Lo llevamos a una forma equivalente y obtenemos un LP idéntico al original: bajo la condición . ${\ estilo de visualización \ max c ^ {T}}$ $Ax\leqslant b,x\geqslant 0$ ${\ estilo de visualización \ min b ^ {T} y}$ $A^{T}y\geqslant c,y\geqslant 0$ $\max-b^{T}y$ $-A^{T}y\leqslant -c,y\geqslant 0$ ${\ estilo de visualización \ min -c^{T}x}$ $-Ax\geqslant -b,x\geqslant 0$ ${\ estilo de visualización \ max c ^ {T}}$ $Ax\leqslant b,x\geqslant 0$

Software

lp_solve es un software de código abierto (LGPL GNU GNU General Public License for Libraries ) para resolver ecuaciones lineales. LpSolve tiene un IDE , una API C nativa y muchas otras API para Java, AMPL, MATLAB, Wolfram Mathematica, O-Matrix, Sysquake, Scilab, Octave, FreeMat, Euler, Python, Sage, PHP, R y Microsoft Solver Foundation. .

Véase también

Notas

↑ 1 2 Fuente: Biblioteca Científica Universal Regional de Altai. V. Ya. Shishkova (AKUNB) Archivado el 5 de marzo de 2022 en Wayback Machine . Métodos de optimización: Proc. tolerancia. Brazovskaya NV; Universidad Técnica Estatal de Altai I. I. Polzunova, [Centro de Distancia. aprendizaje]. - Barnaul: Editorial AltGTU, 2000. - 120 p. - ISBN 5-BNV-MOr.9.00 - UDC/LBC 22.183.4 B871.
↑ Dikin I. I. Solución iterativa de problemas de programación lineal y cuadrática // Dokl. Academia de Ciencias de la URSS. - 1967. - T. 174 , N º 4 . - S. 747-748 .
↑ Karmanov, 1986 , pág. 63.
↑ Karmanov, 1986 , pág. 80.
↑ Karmanov, 1986 , pág. 77.
↑ Libro de texto electrónico "Métodos económicos y matemáticos". Dualidad en la programación lineal Archivado el 17 de junio de 2016 en Wayback Machine .

Literatura

Abramov L. M., Kapustin V. F. Programación matemática. - Tutorial. - L. : LGU, 1981. - 328 p.
Akof R., Sasieni M. Fundamentos de la investigación de operaciones. — Por. De inglés. V. Ya. Altaeva., ed. I. A. Ushakova. — M .: Mir, 1971. — 551 p.
Akulich I. L. Capítulo 1. Problemas de programación lineal, Capítulo 2. Problemas especiales de programación lineal // Programación matemática en ejemplos y problemas. - M. : Escuela Superior, 1986. - 319 p. — ISBN 5-06-002663-9 .
Astafiev NN Sistemas infinitos de desigualdades lineales en programación matemática. - M. : Nauka, 1991. - 134 p.
Ashmanov S. A., Timokhov A. V. Teoría de optimización en tareas y ejercicios. - M. : Nauka, 1991. - 446 p.
Gass S. Programación lineal. - M. : Literatura físico-matemática, 1961. - 300 p.
Davydov E. G. Investigación de operaciones. - M. : Escuela Superior, 1990. - 382 p.
Degtyarev Yu. I. Investigación de operaciones. — Libro de texto para universidades. - M. : Escuela Superior, 1986. - 320 p.
Zukhovitsky S. I., Avdeeva L. I. Programación lineal y convexa. — M .: Nauka, 1966. — 348 p.
Karmanov VG Programación matemática. — 3ra edición. — M .: Nauka, 1986. — 288 p.
Kuznetsov A. V., Sakovich V. A., Kholod N. I. Matemáticas superiores. Programación matemática. - Minsk.: Escuela Superior, 1994. - 286 p.
Thomas H. Kormen y otros Capítulo 29. Programación lineal // Algoritmos: Construcción y análisis = Introducción a los algoritmos. - 2ª ed. - M .: "Williams" , 2006. - S. 1296. - ISBN 5-8459-0857-4 .
Yudin D. B. , Holstein E. G. Programación lineal. — M .: Nauka, 1969. — 424 p.
Dantzig JB Memorias del comienzo de la programación lineal.
Gabasov R., Kirillova F. M. Métodos de programación lineal. - Minsk: BGU, 1977. - 176 p.

Enlaces

Solucionador de programa lineal (LiPS) : un paquete de optimización gratuito para resolver problemas de programación lineal, entera y de destino.
Vershik A. M. O L. V. Kantorovich y la programación lineal
Diapositivas de programación lineal
Bolshakova I. V., Kuralenko M. V. Programación lineal. Material didáctico para el trabajo de control . (enlace descendente desde el 13-05-2013 [3461 días])
Barsov A. S. ¿Qué es la programación lineal? // Conferencias populares sobre matemáticas , Gostekhizdat, 1959.
Vyalyi MN Desigualdades lineales y combinatoria . —MTsNMO , 2003.

diccionarios y enciclopedias

En catálogos bibliográficos
BNF : 119415380 TIERRA : 4035816-1 J9U : 987007555765405171 LCCN : sh85082127 NDL : 00570683 NKC : ph122356

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock Método Powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial