Programación linear

A programación linear é o campo da optimización matemática dedicado a maximizar ou minimizar (optimizar) unha función linear, denominada función obxectivo, de tal xeito que as variables desa función estean suxeitas a unha serie de restricións expresadas mediante un sistema de inecuacións tamén lineares. Os métodos máis empregados para resolver problemas de programación linear son algoritmos de pivote, en particular os algoritmos simplex.

O problema da resolución dun sistema linear de inecuacións remóntase, polo menos, a Joseph Fourier, a partir do que nace o método de eliminación de Fourier-Motzkin. A programación linear formúlase como un modelo matemático desenvolvido durante a segunda guerra mundial para planificar os gastos e os retornos, coa finalidade de reducir os custos ao exército e aumentar as perdas do inimigo. Mantívose en segredo ata 1947. Na posguerra, moitas industrias o empregaron na súa planificación diaria.

Os fundadores da técnica son George Dantzig, que publicou o algoritmo simplex, en 1947, John von Neumann, que desenvolveu a teoría da dualidade no mesmo ano, e Leonid Kantoróvich, un matemático de orixe rusa, que emprega técnicas similares na economía antes de Dantzig e gañou o Premio Nobel de Economía en 1975. En 1979, outro matemático ruso, Leonid Khachiyan, deseñou o chamado algoritmo do elipsoide, a través do que demostrou que o problema da programación linear é resoluble de xeito eficiente, é dicir, en tempo polinomial.^[2] Máis tarde, en 1984, Narendra Karmarkar introduce un novo método do punto interior para resolver problemas de programación linear, o que constituiría un enorme avance nos principios teóricos e prácticos na área.

O exemplo orixinal de Dantzig da busca da mellor asignación de 70 persoas a 70 postos de traballo é un exemplo da utilidade da programación linear. A potencia de computación necesaria para examinar todas as permutacións para seleccionar a mellor asignación é inmensa (factorial de 70, 70!) ; o número de posibles configuracións excede ao número de partículas no universo. Non obstante, leva só un momento atopar a solución óptima mediante a formulación do problema como unha programación linear e a aplicación do algoritmo simplex. A teoría da programación linear reduce drasticamente o número de posibles solucións factibles que deben ser revisadas.

As variables son números reais maiores ou iguais a cero. ${\displaystyle X_{i}\geq 0}$

No caso de que se requira que o valor resultante das variables sexa un número enteiro, o procedemento de resolución denomínase programación enteira.

As restricións poden ser da forma:

Tipo 1: ${\displaystyle A_{j}=\sum _{i=1}^{N}a_{i,j}\times X_{i}}$

Tipo 2: ${\displaystyle B_{j}\leq \sum _{i=1}^{N}b_{i,j}\times X_{i}}$

Tipo 3: ${\displaystyle C_{j}\geq \sum _{i=1}^{N}c_{i,j}\times X_{i}}$

Onde:

• A = valor coñecido que ten que ser respectado estritamente;
• B = valor coñecido que debe ser respectado ou pode ser superado;
• C = valor coñecido que non debe ser superado;
• j = número da ecuación, variable de 1 a M (número total de restricións);
• a; b; e c = coeficientes técnicos coñecidos;
• X = Incógnitas, de 1 a N;
• i = número da incógnita, variable de 1 a N.

En xeral non hai restricións en canto aos valores de N e M. Pode ser N = M; N > M; ou N < M.

Non obstante se as restricións do Tipo 1 son N, o problema pode ser determinado, e pode non ter sentido unha optimización.

Os tres tipos de restricións poden darse simultaneamente no mesmo problema.

A función obxectivo pode ser:

${\displaystyle Max!=\sum _{i=1}^{N}f_{i}\times X_{i}}$

ou

${\displaystyle Min!=\sum _{i=1}^{N}f_{i}\times X_{i}}$

Onde:

• ${\displaystyle f_{i}}$ = coeficientes son relativamente iguais a cero.

Nalgúns casos requírese que a solución óptima se compoña de valores enteiros para algunhas das variables. A resolución deste problema se obtense analizando as posibles alternativas de valores enteiros desas variables nunha veciñanza arredor da solución obtida considerando as variables reais.

Moitas veces a solución do programa linear truncado esta lonxe de ser o óptimo enteiro, polo que se fai necesario empregar algún algoritmo para conseguir esta solución de forma exacta. O máis famoso é o método de ramificar e limitar (en inglés, Branch and Bound). Este método parte da adición de novas restricións para cada variable de decisión (limitar) que ao ser avaliada independentemente (ramificar) leva ao óptimo enteiro.

A programación linear constitúe un importante campo da optimización por varias razóns, moitos problemas prácticos da investigación de operacións poden formularse como problemas de programación linear. Algúns casos especiais de programación linear, tales como os problemas de fluxo de redes e problemas de fluxo de mercancías que se consideraron no desenvolvemento das matemáticas o suficientemente importantes como para xerar por eles mesmos moita investigación sobre algoritmos especializados na súa solución. Unha serie de algoritmos deseñados para resolver outros tipos de problemas de optimización constitúen casos particulares da máis ampla técnica da programación linear. Historicamente, as ideas de programación linear inspiraron moitos dos conceptos centrais da teoría de optimización como a dualidade, a descomposición e a importancia da convexidade e as súas xeneralizacións. Do mesmo xeito, a programación linear é moi empregada na microeconomía e na administración de empresas, para aumentar ao máximo os ingresos ou para reducir ao mínimo os custos dun sistema de produción. Algúns exemplos son a mestura de alimentos, a xestión de inventarios, a carteira e a xestión das finanzas, a asignación de recursos humanos e recursos de máquinas, a planificación de campañas de publicidade etc.

Outros son:

• Optimización da combinación de cifras comerciais nunha rede linear de distribución de auga.
• Aproveitamento óptimo dos recursos dunha cunca hidrográfica, para un ano con afluencias caracterizadas por corresponder a unha determinada frecuencia.
• Axuda para toma de decisións en tempo real, para operación dun sistema de obras hidráulicas;
• Solución de problemas de transporte.

Este é un caso curioso, con só 6 variables (un caso real de problema de transporte pode ter facilmente máis de 1000 variables) no que se aprecia a utilidade deste procedemento de cálculo.

Existen tres minas de carbón coa seguinte produción diaria:

• a mina "a" produce 40 toneladas de carbón por día;
• a mina "b" produce 40 t/día; e,
• a mina "c" produce 20 t/día.

Na zona hai dúas centrais termoeléctricas que consomen:

• a central "d" consome 40 t/día de carbón; e,
• a central "e" consome 60 t/día.

Os custos de mercado de transporte por tonelada son:

• De "a" a "d" = 2 moedas
• De "a" a "e" = 11 moedas
• De "b" a "d" = 12 moedas
• De "b" a "e" = 24 moedas
• De "c" a "d" = 13 moedas
• De "c" a "e" = 18 moedas

Se se preguntase aos habitantes da zona como organizar o transporte, talvez a maioría opinaría que debe aproveitarse o prezo ofrecido polo transportista que vai de "a" a "d", porque é máis conveniente cós outros, debido a que é o de prezo máis baixo.

Neste caso, o custo total do transporte é:

• Transporte de 40 t de "a" a "d" = 80 moedas
• Transporte de 20 t de "c" a "e" = 360 moedas
• Transporte de 40 t de "b" a "e" = 960 moedas
• Total 1400 moedas.

Non obstante, formulando o problema para ser resolto mediante a programación linear téñense as seguintes ecuacións:

• Restricións da produción:

${\displaystyle X_{a\to d}+X_{a\to e}\leq 40}$	${\displaystyle [{\mbox{T/dia}}]\,\!}$
${\displaystyle X_{b\to d}+X_{b\to e}\leq 40}$	${\displaystyle [{\mbox{T/dia}}]\,\!}$
${\displaystyle X_{c\to d}+X_{c\to e}\leq 20}$	${\displaystyle [{\mbox{T/dia}}]\,\!}$

• Restricións do consumo:

${\displaystyle X_{a\to d}+X_{b\to d}+X_{c\to d}\geq 40}$	${\displaystyle [{\mbox{T/dia}}]\,\!}$
${\displaystyle X_{a\to e}+X_{b\to e}+X_{c\to e}\geq 60}$	${\displaystyle [{\mbox{T/dia}}]\,\!}$

• A función obxectivo será:

${\displaystyle 2X_{a\to d}+11X_{a\to e}+12X_{b\to d}+24X_{b\to e}+13X_{c\to d}+18X_{c\to e}=Min!}$

A solución de custo mínimo de transporte diario resulta ser:

• X_b-d = 40 resultando un custo de 12 • 40 = 480 moedas
• X_a-e = 40 resultando un custo de 11 • 40 = 440 moedas
• X_c-e = 20 resultando un custo de 18 • 20 = 360 moedas
• Total 1280 moedas.

120 moedas menos que antes.

• Poliedro convexo
• Algoritmo de pivote
• Algoritmo simplex
• Conjetura de Hirsch
• Leonid Kantoróvich

• Crilly, Tony (2011). 50 cosas que hay que saber sobre matemáticas. Ariel. ISBN 978-987-1496-09-9. 
• Khachiyan, L. (1979). A polynomial algorithm in linear programming 20. Soviet Math. Doklady. 
• Loomba, N.P. Linear Programming: An introductory analysis. McGraw-Hill, Nova York, 1964