Programación llinial

La programación llinial ye'l campu de la optimización matemática dedicáu a maximizar o embrivir (optimizar) una función llinial, denomada función oxetivu, de tala forma que les variables de dicha función tean suxetes a una serie de restricciones espresaes por aciu un sistema d'ecuaciones o inecuaciones tamién lliniales. El métodu tradicionalmente usáu pa resolver problemes de programación llinial ye'l Métodu Simplex.

Historia de la programación llinial

**Cronoloxía**^[1]
Añu	Acontecimientu
1826	Joseph Fourier antemana la programación llinial. Carl Friedrich Gauss resuelve ecuaciones lliniales por eliminación "gaussiana".
1902	Gyula Farkas concibe un métodu pa resolver sistemes de inecuaciones.
1947	George Dantzig publica'l algoritmu simplex y John von Neumann desenvolvió la teoría de la dualidá. Sábese que Leonid Kantoróvich tamién formuló la teoría en forma independiente.
1984	Narendra Karmarkar introduz el métodu del puntu interior pa resolver problemes de programación llinial.

El problema de la resolución d'un sistema llinial de inecuaciones remóntase, siquier, a Joseph Fourier, dempués de quien naz el métodu d'eliminación de Fourier-Motzkin. La programación llinial plantégase como un modelu matemáticu desenvueltu mientres la Segunda Guerra Mundial pa planiar los gastos y les tornes, con cuenta d'amenorgar los costos al exércitu y aumentar les perdes del enemigu. Caltúvose de callao hasta 1947. Na posguerra, munches industries usáronlo na so planificación diaria.

Los fundadores de la téunica son George Dantzig, quien publicó'l algoritmu simplex, en 1947, John von Neumann, que desenvolvió la teoría de la dualidá nel mesmu añu, y Leonid Kantoróvich, un matemáticu d'orixe rusu, qu'utiliza téuniques similares na economía antes de Dantzig y ganó'l premiu Nobel n'economía en 1975. En 1979, otru matemáticu rusu, Leonid Khachiyan, diseñó'l llamáu Algoritmu del elipsoide, al traviés del cual demostró que'l problema de la programación llinial ye resoluble de manera eficiente, esto ye, en tiempu polinomial.^[2] Más tarde, en 1984, Narendra Karmarkar introduz un nuevu métodu del puntu interior pa resolver problemes de programación llinial, lo que constituyiría una enorme meyora nos principios teóricos y práuticos nel área.

L'exemplu orixinal de Dantzig de la busca de la meyor asignación de 70 persones a 70 puestos de trabayu ye un exemplu de la utilidá de la programación llinial. La potencia de computación necesaria pa esaminar toles permutaciones con cuenta d'escoyer la meyor asignación ye inmensa (factorial de 70, 70!) ; el númberu de posibles configuraciones entepasa al númberu de partícules nel universu. Sicasí, toma namái un momentu atopar la solución óptima por aciu el planteamientu del problema como una programación llinial y l'aplicación del algoritmu simplex. La teoría de la programación llinial amenorga drásticamente el númberu de posibles soluciones facederes que tienen de ser revisaes.

Variables

Les variables son númberos reales mayores o iguales a cero. $X_{i}\geq 0$

En casu que se riquir que'l valor resultante de les variables sía un númberu enteru, el procedimientu de resolución denominar Programación entera.

Restricciones

Les restricciones pueden ser de la forma:

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

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

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

Onde:

A = valor conocíu a ser respetáu puramente;
B = valor conocíu que tien de ser respetáu o puede ser superáu;
C = valor conocíu que nun tien de ser superáu;
j = númberu de la ecuación, variable de 1 a M (númberu total de restricciones);
a; b; y, c = coeficientes téunicos conocíos;
X = Incógnites, de 1 a N;
i = númberu de la incógnita, variable de 1 a N.

Polo xeneral nun hai restricciones tocantes a los valores de N y M. Puede ser N = M; N > M; ó, N < M.

Sicasí si les restricciones del Tipu 1 son N, el problema puede ser determináu, y puede nun tener sentíu una optimización.

Los trés tipos de restricciones pueden dase simultáneamente nel mesmu problema.

Función Oxetivu

La función oxetivu pue ser:

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

o

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

Onde:

$f_{i}$ = coeficientes

Esistencia de soluciones óptimas

Geométricamente, les restricciones lliniales definen la rexón facedera, que ye un poliedru convexu. Una función llinial ye una función convexa, polo qu'un mínimu local ye un mínimu global; una función llinial ye tamién una función cóncava, asina que tou máximu local ye tamién un máximu global.

Como les funciones lliniales nun son nin puramente convexes nin puramente cóncaves, les soluciones óptimas nun son necesariamente úniques.

Si la rexón facedera ye acutada y non vacida, entós va esistir siquier una solución óptima, yá que una función llinial ye continua y polo tanto algama un máximu en cualquier rexón zarrada y acutada. Sicasí, puede nun esistir una solución óptima en dos situaciones. De primeres, si la rexón facedera ye vacida, esto ye, si nengún puntu verifica toles restricciones, entós el problema ye invidable. De segundes, si la rexón facedera nun ta acutada na direición del gradiente de la función oxetivu, el problema ye non acutáu, y pueden atopase puntos que verifiquen toles restricciones y con un valor tan alto como queramos de la función oxetivu.

Programación entera

En dellos casos ríquese que la solución óptima componer de valores enteros pa delles de les variables. La resolución d'esti problema llógrase analizando les posibles alternatives de valores enteros d'eses variables nuna redolada alredor de la solución llograda considerando les variables reales. Munches vegaes la solución del programa llinial truncáu ta lloñe de ser el óptimo enteru, polo que se fai necesariu usar dalgún algoritmu pa topar esta solución de forma exacta. El más famosu ye'l métodu de 'Ramificar y Acutar' o Branch and Bound pol so nome n'inglés. El métodu de Ramificar y Acutar parte de la adición de nueves restricciones pa cada variable de decisión (acutar) que al ser evaluáu independientemente (ramificar) lleva al óptimo enteru.

Aplicaciones

La programación llinial constitúi un importante campu de la optimización por delles razones, munchos problemes práuticos de la investigación d'operaciones pueden plantegase como problemes de programación llinial. Dellos casos especiales de programación llinial, tales como los problemes de fluxu de redes y problemes de fluxu de mercancíes considerar nel desenvolvimientu de les matemátiques lo suficientemente importantes como pa xenerar por si mesmos muncha investigación sobre algoritmos especializaos na so solución. Una serie d'algoritmos diseñaos pa resolver otros tipos de problemes de optimización constitúin casos particulares de la más amplia téunica de la programación llinial. Históricamente, les idees de programación llinial inspiraron munchos de los conceutos centrales de la teoría de optimización tales como la dualidá, la descomposición y la importancia de la convexidá y les sos xeneralizaciones. De la mesma, la programación llinial ye bien usada na microeconomía y l'alministración d'empreses, yá sía p'aumentar al máximu los ingresos o amenorgar al mínimu los costos d'un sistema de producción. Dellos exemplos son l'amiestu d'alimentos, la xestión d'inventarios, la cartera y la xestión de les finances, la asignación de recursos humanos y recursos de máquines, la planificación de campañes de publicidá, etc.

Otros son:

Optimización de la combinación de cifres comerciales nuna rede llinial de distribución d'agua.

Aprovechamientu óptimo de los recursos d'una cuenca hidrográfica, pa un añu con arribaciones caracterizaes por corresponder a una determinada frecuencia.

Soporte para toma de decisión en tiempu real, pa operación d'un sistema d'obres hidráuliques;

Solución de problemes de tresporte.

Exemplu

Esti ye un casu interesáu, con solu 6 variables (un casu real de problema de tresporte puede tener fácilmente más de 1.000 variables) nel cual apréciase la utilidá d'esti procedimientu de cálculu.

Esisten trés mines de carbón que la so producción diaria ye:

La mina "a" produz 40 tonelaes de carbón per día;
La mina "b" produz 40 t/día; y, *

La mina "c" produz 20 t/día. Na zona hai dos centrales termoeléctriques que peracaben:

La central "d" consume 40 t/día de carbón; y, *

La central "y" consume 60 t/día Los costos de mercáu, de tresporte per tonelada son:

De "a" a "d" = 2 monedes
De "a" a "y" = 11 monedes
De "b" a "d" = 12 monedes
De "b" a "y" = 24 monedes
De "c" a "d" = 13 monedes
De "c" a "y" = 18 monedes

Si preguntar a los pobladores de la zona cómo entamar el tresporte, seique la mayoría cuntaría que tien d'aprovechase'l preciu ufiertáu pol tresportista que va de "a" a "d", porque ye más conveniente que los otros, por cuenta de que ye'l de más so preciu.

Nesti casu, el costu total del tresporte ye:

Tresporte de 40 t de "a" a "d" = 80 monedes
Tresporte de 20 t de "c" a "y" = 360 monedes
Tresporte de 40 t de "b" a "y" = 960 monedes
Total 1.400 monedes.

Sicasí, formulando'l problema pa ser resueltu pola programación llinial tiénense les siguientes ecuaciones:

Restricciones de la producción:

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

Restricciones del consumu:

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

La función oxetivu va ser:

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

La solución de costu mínimu de tresporte diariu resulta ser:

X_b-d = 40 resultando un costu de 12 x 40 = 480 monedes
X_a-y = 40 resultando un costu de 11 x 40 = 440 monedes
X_c-y = 20 resultando un costu de 18 x 20 = 360 monedes
Total 1.280 monedes.

120 monedes menos qu'antes.

Ver tamién

Referencies

↑ Crilly, 2011.
↑ Khachiyan, 1979, páxs. 191-194.

Bibliografía

Crilly, Tony (2011). 50 coses qu'hai que saber sobre matemátiques. Ed. 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, New York, 1964
Universidá Peruana Unión - Biblioteca Central - llibro númberu 0.001245/f12 Programación llinial.

[FOOTNOTECrilly2011{{{c}}}-1] Crilly, 2011.

[FOOTNOTEKhachiyan1979{{{c}}}191-194-2] Khachiyan, 1979, páxs. 191-194.

[1]

[2]