observa la escena siguiente y encuentra las posibles soluciones
jueves, 16 de octubre de 2008
Ejemplos
Para aplicar la programación lineal en la elaboración de las raciones para vacas lecheras, partimos de una ración hipotética en la cual intervienen los siguientes datos:- Dos alimentos : un Concentrado (X1) y un Forraje (X2)- Tres nutrientes : Proteína Cruda PC Energía Neta de lactancia ENI Fibra Cruda FC- El precio por Kilogramo de cada uno de los alimentos- Necesidades nutritivas de las vacas lecheras.
ALIMENTOS
VARIABLES
PC
ENl
FC
PRECIO
( gr )
( Mcal )
( gr )
( $ )
concentrado
X1
120
2.0
100
100
forraje
X2
200
1.3
280
50
NECESIDADES
PC ( gr )
Enl ( Mcal )
FC ( gr )
MAXIMO
2000
MINIMO
1500
16.5
1300
Nuestro propósito es el de optimizar una ración de Mínimo Costo, aplicando la programación lineal por el método gráfico. El modelo de programación lineal es el siguiente:
(1) MIN 110 X1 + 50 X2
SUJETO A LAS SIGUIENTES RESTRICCIONES
(2) 120 X1 + 200 X2 >= 1500
(3) 2.0 X1 + 1.3 X2 >= 16.5
(4) 100 X1 + 280 X2 <= 2000
(5) 100 X1 + 280 X2 >= 1300
La ecuación (1) corresponde a la FUNCION OBJETIVO, que se trata de Minimizar, la restricción (2) es de la Proteina Cruda PC, que como mínimo debe tener 1500 gramos, la restricción (3) es de la Energía Neta de lactancia ENI, que como mínimo debe tener 16.5 Mcal., la restricción (4) es de la Fibra Cruda, FCmax que como máximo debe tener 2000 gramos, la restricción (5) es también de la Fibra Cruda FCmin, pero en este caso debe tener un mínimo de 1300 gramos.
Se va a determinar por graficación, cuantos Kilogramos de Concentrado (X1) y cuantos Kilogramos de Forraje (X2) se calcularan para que la ración sea al mínimo costo posible y cubra los requerimientos nutritivos.
Para pensar en una interpretación geométrica de nuestro problema, se transforman las inecuaciones 2, 3, 4 y 5 como ecuaciones :
120 X1 + 200 X2 = 1500
2.0 X1 + 1.3 X2 = 16.5
100 X1 + 280 X2 = 2000
100 X1 + 280 X2 = 1300
Se trazan las gráficas de dichas ecuaciones, que no son otra cosa que líneas rectas, en los ejes cartesianos, tomando coma eje de las Xs el Concentrado (X1) y en el eje de las Ys el Forraje (X2).
En el área factible de solución (rayada) tenemos dos vértices, el Punto A, donde se intersectan las líneas de FCmax con ENI y el Punto B donde se intersectan las líneas de ENl con PC; encontrando las coordenadas de estos puntos :
PUNTO A
FCmax 100 X1 + 280 X2 = 2000
Enl 2.0 X1 + 1.3 X2 = 16.5
Donde :
X1 = 4.7 X2 = 5.47
PUNTO B
ENl 2.0 X1 + 1.3 X2 = 16. 5
PC 120 X1 + 200 X2 = 1500
Donde :
X1 = 5.53 X2 = 4.18
Sustituyendo los valores de estos puntos en la ecuación del COSTO.
110 X1 + 50 X2
Para el Punto A (4.7 , 5.47)
110(4.7) + 50(5.47) = 790.5
Que son los valores para el MINIMO COSTO.
Para el Punto B (5.53 , 4.18)
110(5.53) + 50(4.18) = 817.62
La ecuación FCmin 100X1 + 280 X2 = 1300
está fuera del área factible de solución, por lo tanto, no participa en la solución del problema de optimización.
LA SOLUCION ES :
CONCENTRADO (X1) = 4.70 Kg.
FORRAJE (X2) = 5.47 Kg.
MINIMO COSTO = $ 790.50
APORTE DE NUTRIENTES POR LA RACION :
Proteina Cruda PC 120(4.7) + 200(5.47) = 1658 gr., que es poco más del mínimo impuesta por la restricción de 1500 gr.
Energía Neta de lactancia ENI 2.0(4.7) + 1.3(5.47) = 16.5 Mcal., que es el mínimo requerido e impuesto por la restricción.
Fibra Cruda FC 100(4.7) + 280(5.47) = 2000 gr., que es limite máximo requerido e impuesto por la restricción 1300 - 2000 gr. detalles graficos en:http://orbita.starmedia.com/~arivera/lineal.htm
ALIMENTOS
VARIABLES
PC
ENl
FC
PRECIO
( gr )
( Mcal )
( gr )
( $ )
concentrado
X1
120
2.0
100
100
forraje
X2
200
1.3
280
50
NECESIDADES
PC ( gr )
Enl ( Mcal )
FC ( gr )
MAXIMO
2000
MINIMO
1500
16.5
1300
Nuestro propósito es el de optimizar una ración de Mínimo Costo, aplicando la programación lineal por el método gráfico. El modelo de programación lineal es el siguiente:
(1) MIN 110 X1 + 50 X2
SUJETO A LAS SIGUIENTES RESTRICCIONES
(2) 120 X1 + 200 X2 >= 1500
(3) 2.0 X1 + 1.3 X2 >= 16.5
(4) 100 X1 + 280 X2 <= 2000
(5) 100 X1 + 280 X2 >= 1300
La ecuación (1) corresponde a la FUNCION OBJETIVO, que se trata de Minimizar, la restricción (2) es de la Proteina Cruda PC, que como mínimo debe tener 1500 gramos, la restricción (3) es de la Energía Neta de lactancia ENI, que como mínimo debe tener 16.5 Mcal., la restricción (4) es de la Fibra Cruda, FCmax que como máximo debe tener 2000 gramos, la restricción (5) es también de la Fibra Cruda FCmin, pero en este caso debe tener un mínimo de 1300 gramos.
Se va a determinar por graficación, cuantos Kilogramos de Concentrado (X1) y cuantos Kilogramos de Forraje (X2) se calcularan para que la ración sea al mínimo costo posible y cubra los requerimientos nutritivos.
Para pensar en una interpretación geométrica de nuestro problema, se transforman las inecuaciones 2, 3, 4 y 5 como ecuaciones :
120 X1 + 200 X2 = 1500
2.0 X1 + 1.3 X2 = 16.5
100 X1 + 280 X2 = 2000
100 X1 + 280 X2 = 1300
Se trazan las gráficas de dichas ecuaciones, que no son otra cosa que líneas rectas, en los ejes cartesianos, tomando coma eje de las Xs el Concentrado (X1) y en el eje de las Ys el Forraje (X2).
En el área factible de solución (rayada) tenemos dos vértices, el Punto A, donde se intersectan las líneas de FCmax con ENI y el Punto B donde se intersectan las líneas de ENl con PC; encontrando las coordenadas de estos puntos :
PUNTO A
FCmax 100 X1 + 280 X2 = 2000
Enl 2.0 X1 + 1.3 X2 = 16.5
Donde :
X1 = 4.7 X2 = 5.47
PUNTO B
ENl 2.0 X1 + 1.3 X2 = 16. 5
PC 120 X1 + 200 X2 = 1500
Donde :
X1 = 5.53 X2 = 4.18
Sustituyendo los valores de estos puntos en la ecuación del COSTO.
110 X1 + 50 X2
Para el Punto A (4.7 , 5.47)
110(4.7) + 50(5.47) = 790.5
Que son los valores para el MINIMO COSTO.
Para el Punto B (5.53 , 4.18)
110(5.53) + 50(4.18) = 817.62
La ecuación FCmin 100X1 + 280 X2 = 1300
está fuera del área factible de solución, por lo tanto, no participa en la solución del problema de optimización.
LA SOLUCION ES :
CONCENTRADO (X1) = 4.70 Kg.
FORRAJE (X2) = 5.47 Kg.
MINIMO COSTO = $ 790.50
APORTE DE NUTRIENTES POR LA RACION :
Proteina Cruda PC 120(4.7) + 200(5.47) = 1658 gr., que es poco más del mínimo impuesta por la restricción de 1500 gr.
Energía Neta de lactancia ENI 2.0(4.7) + 1.3(5.47) = 16.5 Mcal., que es el mínimo requerido e impuesto por la restricción.
Fibra Cruda FC 100(4.7) + 280(5.47) = 2000 gr., que es limite máximo requerido e impuesto por la restricción 1300 - 2000 gr. detalles graficos en:http://orbita.starmedia.com/~arivera/lineal.htm
Aplicaciones
Aplicaciones
La programación lineal constituye un importante campo de la optimización por varias razones, muchos problemas prácticos de la investigación de operaciones pueden plantearse como problemas de programación lineal. Algunos casos especiales de programación lineal, tales como los problemas de flujo de redes y problemas de flujo de mercancías se consideraron en el desarrollo de las matemáticas lo suficientemente importantes como para generar por si mismos mucha investigación sobre algoritmos especializados en su solución. Una serie de algoritmos diseñados para resolver otros tipos de problemas de optimización constituyen casos particulares de la más amplia técnica de la programación lineal. Históricamente, las ideas de programación lineal han inspirado muchos de los conceptos centrales de la teoría de optimización tales como la dualidad, la descomposición y la importancia de la convexidad y sus generalizaciones. Del mismo modo, la programación lineal es muy usada en la microeconomía y la administración de empresas, ya sea para aumentar al máximo los ingresos o reducir al mínimo los costos de un sistema de producción. Algunos ejemplos son la mezcla de alimentos, la gestión de inventarios, la cartera y la gestión de las finanzas, la asignación de recursos humanos y recursos de máquinas, la planificación de campañas de publicidad, etc.
Otros son:
Optimización de la combinación de diámetros comerciales en una red ramificada de distribución de agua.
Aprovechamiento óptimo de los recursos de una cuenca hidrográfica, para un año con afluencias caracterizadas por corresponder a una determinada frecuencia.
Soporte para toma de decisión en tiempo real, para operación de un sistema de obras hidráulicas;
Solución de problemas de transporte.
La programación lineal constituye un importante campo de la optimización por varias razones, muchos problemas prácticos de la investigación de operaciones pueden plantearse como problemas de programación lineal. Algunos casos especiales de programación lineal, tales como los problemas de flujo de redes y problemas de flujo de mercancías se consideraron en el desarrollo de las matemáticas lo suficientemente importantes como para generar por si mismos mucha investigación sobre algoritmos especializados en su solución. Una serie de algoritmos diseñados para resolver otros tipos de problemas de optimización constituyen casos particulares de la más amplia técnica de la programación lineal. Históricamente, las ideas de programación lineal han inspirado muchos de los conceptos centrales de la teoría de optimización tales como la dualidad, la descomposición y la importancia de la convexidad y sus generalizaciones. Del mismo modo, la programación lineal es muy usada en la microeconomía y la administración de empresas, ya sea para aumentar al máximo los ingresos o reducir al mínimo los costos de un sistema de producción. Algunos ejemplos son la mezcla de alimentos, la gestión de inventarios, la cartera y la gestión de las finanzas, la asignación de recursos humanos y recursos de máquinas, la planificación de campañas de publicidad, etc.
Otros son:
Optimización de la combinación de diámetros comerciales en una red ramificada de distribución de agua.
Aprovechamiento óptimo de los recursos de una cuenca hidrográfica, para un año con afluencias caracterizadas por corresponder a una determinada frecuencia.
Soporte para toma de decisión en tiempo real, para operación de un sistema de obras hidráulicas;
Solución de problemas de transporte.
Programacion Lineal
Concepto.-La Programación Lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal.
Consiste en optimizar (minimizar o maximizar) una función lineal, que denominaremos función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.
Consiste en optimizar (minimizar o maximizar) una función lineal, que denominaremos función objetivo, de tal forma que las variables de dicha función estén sujetas a una serie de restricciones que expresamos mediante un sistema de inecuaciones lineales.
Historia
El problema de la resolución de un sistema lineal de inecuaciones se remonta, al menos, a Fourier, después de quien nace el método de eliminación de Fourier-Motzkin. La programación lineal se plantea como un modelo matemático desarrollado durante la Segunda Guerra Mundial para planificar los gastos y los retornos, a fin de reducir los costos al ejército y aumentar las pérdidas del enemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas industrias lo usaron en su planificación diaria.
Los fundadores de la técnica son George Dantzig, quien publicó el algoritmo simplex, en 1947, John von Neumann, que desarrolló la teoría de la dualidad en el mismo año, y Leonid Kantorovich, un matemático ruso, que utiliza técnicas similares en la economía antes de Dantzig y ganó el premio Nobel en economía en 1975. Leonid Khachiyan en 1979 fue el primero en demostrar que el problema de la programación lineal se solucionaba en tiempo polinomial, sin embargo, el mejor avance en los principios teóricos y prácticos en el campo se produjo en 1984, cuando Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal.
El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70 personas a 70 puestos de trabajo es un ejemplo de la utilidad de la programación lineal. La potencia de computación necesaria para examinar todas las permutaciones a fin de seleccionar la mejor asignación es inmensa; el número de posibles configuraciones excede al número de partículas en el universo. Sin embargo, toma sólo un momento encontrar la solución óptima mediante el planteamiento del problema como una programación lineal y la aplicación del algoritmo simplex. La teoría de la programación lineal reduce drásticamente el número de posibles soluciones óptimas que deberán ser revisadas
Los fundadores de la técnica son George Dantzig, quien publicó el algoritmo simplex, en 1947, John von Neumann, que desarrolló la teoría de la dualidad en el mismo año, y Leonid Kantorovich, un matemático ruso, que utiliza técnicas similares en la economía antes de Dantzig y ganó el premio Nobel en economía en 1975. Leonid Khachiyan en 1979 fue el primero en demostrar que el problema de la programación lineal se solucionaba en tiempo polinomial, sin embargo, el mejor avance en los principios teóricos y prácticos en el campo se produjo en 1984, cuando Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal.
El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70 personas a 70 puestos de trabajo es un ejemplo de la utilidad de la programación lineal. La potencia de computación necesaria para examinar todas las permutaciones a fin de seleccionar la mejor asignación es inmensa; el número de posibles configuraciones excede al número de partículas en el universo. Sin embargo, toma sólo un momento encontrar la solución óptima mediante el planteamiento del problema como una programación lineal y la aplicación del algoritmo simplex. La teoría de la programación lineal reduce drásticamente el número de posibles soluciones óptimas que deberán ser revisadas
la fotografia es una gentileza del bloger del colega Rafael Amanqui.
Para Tu Envidia
Hola colegas en este blog encontraras informacion multiple en el transcurso de la semana estare colgando mas informacion.
Suscribirse a:
Entradas (Atom)