Programación llineal

De Wikipedia
Saltar a navegación Saltar a la gueta

La programación llineal ye'l campu de la optimización matemática dedicáu a maximizar o embrivir (optimizar) una función llineal, 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 llineales. El métodu tradicionalmente usáu pa resolver problemes de programación llineal ye'l Métodu Simplex.

Historia de la programación llineal[editar | editar la fonte]

Cronoloxía[1]
Añu Acontecimientu
1826 Joseph Fourier antemana la programación llineal. Carl Friedrich Gauss
resuelve ecuaciones llineales 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 llineal.

El problema del resolución d'un sistema llineal 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 llineal 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.

El fundadores de la técnica 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écniques similares na economía antes de Dantzig y ganó el 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 llineal 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 llineal, lo que constituyiría una enorme meyora nos principios teóricos y prácticos na á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 llineal. 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 llineal y l'aplicación del algoritmu simplex. La teoría de la programación llineal amenorga drásticamente el númberu de posibles soluciones facederes que tienen de ser revisaes.

Variables[editar | editar la fonte]

Les variables son númberos reales mayores o iguales a cero.

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[editar | editar la fonte]

Les restricciones pueden ser de la forma:

Tipu 1:

Tipu 2:

Tipu 3:

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écnicos 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[editar | editar la fonte]

La función oxetivu pue ser:

o

Onde:

  • = coeficientes

Esistencia de soluciones óptimas[editar | editar la fonte]

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

Como les funciones llineales 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, cuidao que una función llineal 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[editar | editar la fonte]

En dellos casos ríquese que la solución óptima componer de valores enteros pa delles de les variables. El 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 llineal truncáu ta llueñe de ser el óptimo enteru, polo que se fai necesariu usar dalgún algoritmu pa topar esta solución de forma esacta. 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[editar | editar la fonte]

La programación llineal constitúi un importante campu de la optimización por delles razones, munchos problemes prácticos de la investigación d'operaciones pueden plantegase como problemes de programación llineal. Dellos casos especiales de programación llineal, 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écnica de la programación llineal. Históricamente, les idees de programación llineal inspiraron munchos de los conceutos centrales de la teoría de optimización tales como la dualidá, la descomposición y l'importancia de la convexidá y les sos xeneralizaciones. De la mesma, la programación llineal 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 llineal 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[editar | editar la fonte]

Progr Lineal.PNG

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 el de más so preciu.

Nesti casu, el costo 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 llineal tiénense les siguientes ecuaciones:

  • Restricciones de la producción:
  • Restricciones del consumu:
  • La función oxetivu va ser:

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

  • Xb-d = 40 resultando un costo de 12 x 40 = 480 monedes
  • Xa-y = 40 resultando un costo de 11 x 40 = 440 monedes
  • Xc-y = 20 resultando un costo de 18 x 20 = 360 monedes
  • Total 1.280 monedes.

120 monedes menos qu'antes.

Ver tamién[editar | editar la fonte]

Referencies[editar | editar la fonte]

Bibliografía[editar | editar la fonte]

  • 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 llineal.
Programación lineal