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.

Historia da programación linear

Cronoloxía

Ano	Acontecemento
1826	Joseph Fourier anticipa a programación linear. Carl Friedrich Gauss resolve ecuacións lineares por eliminación "gaussiana".
1902	Gyula Farkas concibe un método para resolver sistemas de inecuacións.
1947	George Dantzig publica o algoritmo simplex e John von Neumann desenvolveu a teoría da dualidade. Sábese que Leonid Kantoróvich tamén formulou a teoría de xeito independente.
1984	Narendra Karmarkar introduce o método do punto interior para resolver problemas de programación linear.

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

Variables

As variables son números reais maiores ou iguais a cero. $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.

Restricións

As restricións poden ser da forma:

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

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

Tipo 3: $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.

Función Obxectivo

A función obxectivo pode ser:

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

ou

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

Onde:

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

Programación enteira

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.

Aplicacións

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.

Exemplo

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:

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

• Restricións do consumo:

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

• A función obxectivo será:

$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.

Véxase tamén

Outros artigos

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

Bibliografía

• 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