Tabla 1 0 0 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P4 0 40 0.02 0.03 0.05 1 0
P5 0 40 0.05 0.02 0.04 0 1
Z 0 0 0 0 0 0
Hay infinitos valores de X1, X2, X3 para el valor óptimo Z = 0 , los cuales están contenidos en la porción del plano 0 X1 + 0 X2 + 0 X3 = 0 que cumple las restricciones del problema.
Una de ellas es:
X1 = 0
X2 = 0
X3 = 0
viernes, 24 de septiembre de 2010
otro punto
3.6.2. Ed Butler es el gerente de producción de Bilco Corporacitio, que produce tres tipos de refracciones para automóviles. La manufactura de cada parte requiere de procesamiento en dos maquinas, con los siguientes tiempos de procesados.
Maquina refracción
A B C
1 0.02 0.03 0.05
2 0.05 0.02 0.04
Cada máquina está disponible 40 horas al mescla ganancia unitaria de cada parte fabricada está dada por
REFRACCION
A B C
GANANCIA $50 $40 $30
Ed requiere determinar que mezclas de refacciones debe producir para maximizar la ganancia total
Formule un modelo de programación lineal.
Despliegue el modelo en una hoja de Excel.
Realice tres estimaciones de la solución óptima. Use la hoja de cálculo para verificar la factibilidad de cada una, y si es factible, encuentre el valor de la función objetivo. ¿qué estimación tiene el mejor valor de la función objetivo?
Utilice Excel Solver para resolver este modelo por el método simplex.
Z=50x_1+40x_2+30x_3 S. a
0,02x_1+0,03x_2+0,05x_3≤40
x_1≥0 ,x_2≥0 ,x_3≥0
0,02x_1+0,03x_2+0,05x_3≤40
Maquina Uso de recursos por unidad de cada actividad Horas disponibles
A B C
1 0,02 0,03 0,05 40
2 0,05 0,02 0,04 40
Ganancia $ 50 $ 40 $ 30 61.818,182
Solución 363,636364 1.090,90909 0
x_1,x_2,x_3
Valor
(350, 1100 ,0) 61.500 Factible Mejor valor
(400, 900, 50) 57.500 Factible
(400, 1000, 100) 63.000 No factible
Maquina refracción
A B C
1 0.02 0.03 0.05
2 0.05 0.02 0.04
Cada máquina está disponible 40 horas al mescla ganancia unitaria de cada parte fabricada está dada por
REFRACCION
A B C
GANANCIA $50 $40 $30
Ed requiere determinar que mezclas de refacciones debe producir para maximizar la ganancia total
Formule un modelo de programación lineal.
Despliegue el modelo en una hoja de Excel.
Realice tres estimaciones de la solución óptima. Use la hoja de cálculo para verificar la factibilidad de cada una, y si es factible, encuentre el valor de la función objetivo. ¿qué estimación tiene el mejor valor de la función objetivo?
Utilice Excel Solver para resolver este modelo por el método simplex.
Z=50x_1+40x_2+30x_3 S. a
0,02x_1+0,03x_2+0,05x_3≤40
x_1≥0 ,x_2≥0 ,x_3≥0
0,02x_1+0,03x_2+0,05x_3≤40
Maquina Uso de recursos por unidad de cada actividad Horas disponibles
A B C
1 0,02 0,03 0,05 40
2 0,05 0,02 0,04 40
Ganancia $ 50 $ 40 $ 30 61.818,182
Solución 363,636364 1.090,90909 0
x_1,x_2,x_3
Valor
(350, 1100 ,0) 61.500 Factible Mejor valor
(400, 900, 50) 57.500 Factible
(400, 1000, 100) 63.000 No factible
RESUMEN DEL CAPITULO
RESUMEN CAPITULO
EL MÉTODO SIMPLEX
“EL método simplex es un procedimiento algebraico. Sin embargo sus conceptos fundamentales son geométricos” (Pág. 109). Este método es un algoritmo que nos permite resolver problemas de programación lineal y hacer análisis posóptimos y se hace mucho más fácil de entender basándose en los conceptos geométricos como son: el análisis de las soluciones FEV, la aplicación de un procedimiento sistematizado, la toma de sus variables de decisión iguales a cero, el seguimiento de una trayectoria lo largo de las aristas de la región factible para hallar una solución óptima, identificación de la tasa de mejoramiento en Z que se mueve por la arista que más aumenta su valor y la verificación de sí la tasa de mejoramiento en Z es positiva o negativa para determinar si se mueve por esta o por su adyacente.
En programación lineal cualquier problema con n variables de decisión posee dos soluciones FEV adyacentes entre sí si comparten n-1 fronteras de restricción. Las soluciones FEV adyacentes se conectan mediante una recta ubicada en las fronteras de restricción compartida, a esta recta se le llama orilla o arista de la región factible.
Fases:
1. Convertir las desigualdades en igualdades
Se introduce una variable de holgura por cada una de las restricciones, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
2. Igualar la función objetivo a cero
3. Escribir la tabla inicial simplex
En las columnas aparecerán todas las variables del problema y, en las filas, los coeficientes de las igualdades obtenidas, una fila para cada restricción y la última fila con los coeficientes de la función objetivo:
4. Encontrar la variable de decisión que entra en la base y la variable de holgura que sale de la base
1. Para escoger la variable de decisión que entra en la base, nos fijamos en la última fila, la de los coeficientes de la función objetivo y escogemos la variable con el coeficiente negativo mayor (en valor absoluto).
Si existiesen dos o más coeficientes iguales que cumplan la condición anterior, entonces se elige uno cualquiera de ellos.
Si en la última fila no existiese ningún coeficiente negativo, significa que se ha alcanzado la solución óptima. Por tanto, lo que va a determinar el final del proceso de aplicación del método del simplex, es que en la última fila no haya elementos negativos.
La columna de la variable que entra en la base se llama columna pivote (En color azulado).
2. Para encontrar la variable de holgura que tiene que salir de la base, se divide cada término de la última columna (valores solución) por el término correspondiente de la columna pivote, siempre que estos últimos sean mayores que cero.
Si hubiese algún elemento menor o igual que cero no se hace dicho cociente. En el caso de que todos los elementos fuesen menores o iguales a cero, entonces tendríamos una solución no acotada y no se puede seguir.
Si al calcular los cocientes, dos o más son iguales, indica que cualquiera de las variables correspondientes puede salir de la base.
3. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote operacional
5. Encontrar los coeficientes de la nueva tabla.
Los nuevos coeficientes de x se obtienen dividiendo todos los coeficientes de la fila d por el pivote operacional, que es el que hay que convertir en 1.
A continuación mediante la reducción gaussiana hacemos ceros los restantes términos de su columna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de la función objetivo Z.
IDENTIFICANDO CASOS ANÓMALOS Y SOLUCIONES
Obtención de la solución: Cuando se ha dado la condición de parada, obtenemos el valor de las variables básicas que están en la base y el valor óptimo que toma la función que están en la base mirando la columna P0. En el caso de que estemos minimizando, se multiplicará por "-1" el valor óptimo.
Infinitas soluciones: Cumplida la condición de parada, si se observa que alguna variable que no está en la base, tiene un 0 en la fila Z, quiere decir que existe otra solución que da el mismo valor óptimo para la función objetivo. Si estamos ante este caso, estamos ante un problema que admite infinitas soluciones, todas ellas comprendidas dentro del segmento (o porción del plano, o región del espacio, dependiendo del número de variables del problema) que define Ax+By=Z0. Si se desea se puede hacer otra iteración haciendo entrar en la base a la variable que tiene el 0 en la fila Z, y se obtendrá otra solución.
Solución ilimitada: Si al intentar buscar la variable que debe abandonar la base, nos encontramos que toda la columna de la variable entrante tiene todos sus elementos negativos o nulos, estamos ante un problema que tiene solución ilimitada. No hay valor óptimo concreto, ya que al aumentar el valor de las variables se aumenta el valor de la función objetivo, y no viola ninguna restricción.
No existe solución: En el caso de que no exista solución, seguro que tendremos que realizar las dos fases, por lo que al término de la primera sabremos si estamos en tal situación.
Empate de variable entrante: Se puede optar por cualquiera de ellas, sin que afecte a la solución final, el inconveniente que presenta es que según por cual se opte se harán más o menos iteraciones. Se aconseja que se opte a favor de las variables básicas, ya que son aquellas las que quedarán en la base cuando se alcance la solución con estos métodos.
Empate de variable saliente: Se puede nuevamente optar por cualquiera de ellas, aunque se puede dar el caso degenerado y entrar en ciclos perpetuos. Para evitarlos en la medida de lo posible, discriminaremos a favor de las variables básicas haciendo que se queden en la base. Ante el caso de estar en la primera fase (del método de las Dos Fases), se optará por sacar en caso de empate las variables artificiales.
Curiosidad Fase 1: Al finalizar la fase 1, si el problema original tiene solución, todas las variables artificiales, en la fila Z deben tener el valor "1".
¿Pivote puede ser 0?: No, ya que siempre se realizan los cocientes entre valores no negativos y mayores que cero.
EJEMPLO DE METODO SIMPLEX
Resolver mediante el método simplex el siguiente problema:
Maximizar Z = f(x,y) = 3x + 2y
sujeto a: 2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24
x ≥ 0 , y ≥ 0
Se consideran las siguientes fases:
1. Convertir las desigualdades en igualdades
Se introduce una variable de holgura por cada una de las restricciones del tipo ≤, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
2x + y + r = 18
2x + 3y + s = 42
3x +y + t = 24
2. Igualar la función objetivo a cero
- 3x - 2y + Z = 0
3. Escribir la tabla inicial simplex
En las columnas aparecerán todas las variables básicas del problema y las variables de holgura/exceso. En las filas se observan, para cada restricción las variables de holgura con sus coeficientes de las igualdades obtenidas, y la última fila con los los valores resultantes de sustituir el valor de cada variable en la función objetivo, y de operar tal como se explicó en la teoría para obtener el resto de valores de la fila:
Tabla I . Iteración nº 1
3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P3 0 18 2 1 1 0 0
P4 0 42 2 3 0 1 0
P5 0 24 3 1 0 0 1
Z 0 -3 -2 0 0 0
4. Condición de parada
Cuando en la fila Z no existe ningún valor negativo, se ha alcanzado la solución óptima del problema. En tal caso, se ha llegado al final del algoritmo. De no ser así, se ejecutan los siguientes pasos.
5. Condición de entrada y salida de la base
1. Primero debemos saber la variable que entra en la base. Para ello escogemos la columna de aquel valor que en la fila Z sea el menor de los negativos. En este caso sería la variable x (P1) de coeficiente - 3.
Si existiesen dos o más coeficientes iguales que cumplan la condición anterior (caso de empate), entonces se se optará por aquella variable que sea básica.
La columna de la variable que entra en la base se llama columna pivote (En color verde).
2. Una vez obtenida la variable que entra en la base, estamos en condiciones de deducir cual será la variable que sale. Para ello se divide cada término independiente (P0) entre el elemento correspondiente de la columna pivote, siempre que el resultado sea mayor que cero, y se escoge el mínimo de ellos.
En nuestro caso: 18/2 [=9] , 42/2 [=21] y 24/3 [=8]
Si hubiera algún elemento menor o igual a cero no se realiza dicho cociente, y caso de que todos los elementos de la columna pivote fueran de ésta condición tendríamos una solución no acotada y terminaríamos el problema (Ver teoría del método Simplex).
El término de la columna pivote que en la división anterior dé lugar al menor cociente positivo, el 3, ya que 8 es el menor cociente, indica la fila de la variable de holgura que sale de la base, t (P5). Esta fila se llama fila pivote (En color verde).
Si al calcular los cocientes, dos o más son iguales (caso de empate), se escoge aquella que no sea variable básica (si es posible).
3. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote, 3.
6. Encontrar los coeficientes de la nueva tabla.
Los nuevos coeficientes de la fila pivote, t (P5), se obtienen dividiendo todos los coeficientes de dicha fila entre el elemento pivote, 3, que es el que hay que convertir en 1.
A continuación mediante la reducción gaussiana hacemos ceros los restantes términos de su columna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de la función objetivo Z.
También se puede hacer de la siguiente manera:
Fila del pivote:
Nueva fila del pivote = (Vieja fila del pivote) / (Pivote)
Resto de las filas:
Nueva fila = (Vieja fila) -(Coeficiente de la vieja fila en la columna de la variable entrante) x (Nueva fila del pivote)
Veámoslo con un ejemplo una vez calculada la fila del pivote (fila de x (P1) en la Tabla II):
Vieja fila de P4 42 2 3 0 1 0
- - - - - -
Coeficiente 2 2 2 2 2 2
x x x x x x
Nueva fila pivote 8 1 1/3 0 0 1/3
= = = = = =
Nueva fila de P4 26 0 7/3 0 1 -2/3
Tabla II . Iteración nº 2
3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P3 0 2 0 1/3 1 0 -2/3
P4 0 26 0 7/3 0 1 -2/3
P1 3 8 1 1/3 0 0 1/3
Z 24 0 -1 0 0 1
Se puede observar que no hemos alcanzado la condición de parada ya que en los elementos de la última fila, Z, hay uno negativo, -1. Hay que repetir el proceso:
1. La variable que entra en la base es y (P2), por ser la variable que corresponde a la columna donde se encuentra el coeficiente -1.
2. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote: 2 / 1/3 [=6] , 26 / 7/3 [=78/7] y 8 / 1/3 [=8]
y como el menor cociente positivo es 6, tenemos que la variable que sale es r (P3).
3. El elemento pivote, que ahora hay que hacer 1, es 1/3.
Operando de forma análoga a la anterior obtenemos la tabla:
Tabla III . Iteración nº 3
3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P2 2 6 0 1 3 0 -2
P4 0 12 0 0 -7 1 4
P1 3 6 1 0 -1 0 1
Z 30 0 0 3 0 -1
Como en los elementos de la fila Z hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:
1. La variable que entra en la base es t (P5), por ser la variable que corresponde al coeficiente -1.
2. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote: 6/(-2) [=-3] , 12/4 [=3], y 6/1 [=6]
y como el menor cociente positivo es 3, tenemos que la variable que sale es s (P4).
3. El elemento pivote, que ahora hay que hacer 1, es 4.
Obtenemos la tabla:
Tabla IV . Iteración nº 4
3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P2 2 12 0 1 -1/2 0 0
P5 0 3 0 0 -7/4 0 1
P1 3 3 1 0 -3/4 0 0
Z 33 0 0 5/4 0 0
Se observa que en la última fila todos los coeficientes son positivos, por lo tanto se cumple la condición de parada, obteniendo la solución óptima.
La solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33. En la misma columna se puede observar el punto donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base: (x,y) = (3,12)
Maximizar Z = f(x,y) = 3x + 2y
sujeto a: 2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24
x ≥ 0 , y ≥ 0
Se consideran las siguientes fases:
1. Convertir las desigualdades en igualdades
Se introduce una variable de holgura por cada una de las restricciones del tipo ≤, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
2x + y + r = 18
2x + 3y + s = 42
3x +y + t = 24
2. Igualar la función objetivo a cero
- 3x - 2y + Z = 0
3. Escribir la tabla inicial simplex
En las columnas aparecerán todas las variables básicas del problema y las variables de holgura/exceso. En las filas se observan, para cada restricción las variables de holgura con sus coeficientes de las igualdades obtenidas, y la última fila con los los valores resultantes de sustituir el valor de cada variable en la función objetivo, y de operar tal como se explicó en la teoría para obtener el resto de valores de la fila:
Tabla I . Iteración nº 1
3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P3 0 18 2 1 1 0 0
P4 0 42 2 3 0 1 0
P5 0 24 3 1 0 0 1
Z 0 -3 -2 0 0 0
4. Condición de parada
Cuando en la fila Z no existe ningún valor negativo, se ha alcanzado la solución óptima del problema. En tal caso, se ha llegado al final del algoritmo. De no ser así, se ejecutan los siguientes pasos.
5. Condición de entrada y salida de la base
1. Primero debemos saber la variable que entra en la base. Para ello escogemos la columna de aquel valor que en la fila Z sea el menor de los negativos. En este caso sería la variable x (P1) de coeficiente - 3.
Si existiesen dos o más coeficientes iguales que cumplan la condición anterior (caso de empate), entonces se se optará por aquella variable que sea básica.
La columna de la variable que entra en la base se llama columna pivote (En color verde).
2. Una vez obtenida la variable que entra en la base, estamos en condiciones de deducir cual será la variable que sale. Para ello se divide cada término independiente (P0) entre el elemento correspondiente de la columna pivote, siempre que el resultado sea mayor que cero, y se escoge el mínimo de ellos.
En nuestro caso: 18/2 [=9] , 42/2 [=21] y 24/3 [=8]
Si hubiera algún elemento menor o igual a cero no se realiza dicho cociente, y caso de que todos los elementos de la columna pivote fueran de ésta condición tendríamos una solución no acotada y terminaríamos el problema (Ver teoría del método Simplex).
El término de la columna pivote que en la división anterior dé lugar al menor cociente positivo, el 3, ya que 8 es el menor cociente, indica la fila de la variable de holgura que sale de la base, t (P5). Esta fila se llama fila pivote (En color verde).
Si al calcular los cocientes, dos o más son iguales (caso de empate), se escoge aquella que no sea variable básica (si es posible).
3. En la intersección de la fila pivote y columna pivote tenemos el elemento pivote, 3.
6. Encontrar los coeficientes de la nueva tabla.
Los nuevos coeficientes de la fila pivote, t (P5), se obtienen dividiendo todos los coeficientes de dicha fila entre el elemento pivote, 3, que es el que hay que convertir en 1.
A continuación mediante la reducción gaussiana hacemos ceros los restantes términos de su columna, con lo que obtenemos los nuevos coeficientes de las otras filas incluyendo los de la función objetivo Z.
También se puede hacer de la siguiente manera:
Fila del pivote:
Nueva fila del pivote = (Vieja fila del pivote) / (Pivote)
Resto de las filas:
Nueva fila = (Vieja fila) -(Coeficiente de la vieja fila en la columna de la variable entrante) x (Nueva fila del pivote)
Veámoslo con un ejemplo una vez calculada la fila del pivote (fila de x (P1) en la Tabla II):
Vieja fila de P4 42 2 3 0 1 0
- - - - - -
Coeficiente 2 2 2 2 2 2
x x x x x x
Nueva fila pivote 8 1 1/3 0 0 1/3
= = = = = =
Nueva fila de P4 26 0 7/3 0 1 -2/3
Tabla II . Iteración nº 2
3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P3 0 2 0 1/3 1 0 -2/3
P4 0 26 0 7/3 0 1 -2/3
P1 3 8 1 1/3 0 0 1/3
Z 24 0 -1 0 0 1
Se puede observar que no hemos alcanzado la condición de parada ya que en los elementos de la última fila, Z, hay uno negativo, -1. Hay que repetir el proceso:
1. La variable que entra en la base es y (P2), por ser la variable que corresponde a la columna donde se encuentra el coeficiente -1.
2. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote: 2 / 1/3 [=6] , 26 / 7/3 [=78/7] y 8 / 1/3 [=8]
y como el menor cociente positivo es 6, tenemos que la variable que sale es r (P3).
3. El elemento pivote, que ahora hay que hacer 1, es 1/3.
Operando de forma análoga a la anterior obtenemos la tabla:
Tabla III . Iteración nº 3
3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P2 2 6 0 1 3 0 -2
P4 0 12 0 0 -7 1 4
P1 3 6 1 0 -1 0 1
Z 30 0 0 3 0 -1
Como en los elementos de la fila Z hay uno negativo, -1, significa que no hemos llegado todavía a la solución óptima. Hay que repetir el proceso:
1. La variable que entra en la base es t (P5), por ser la variable que corresponde al coeficiente -1.
2. Para calcular la variable que sale, dividimos los términos de la última columna entre los términos correspondientes de la nueva columna pivote: 6/(-2) [=-3] , 12/4 [=3], y 6/1 [=6]
y como el menor cociente positivo es 3, tenemos que la variable que sale es s (P4).
3. El elemento pivote, que ahora hay que hacer 1, es 4.
Obtenemos la tabla:
Tabla IV . Iteración nº 4
3 2 0 0 0
Base Cb P0 P1 P2 P3 P4 P5
P2 2 12 0 1 -1/2 0 0
P5 0 3 0 0 -7/4 0 1
P1 3 3 1 0 -3/4 0 0
Z 33 0 0 5/4 0 0
Se observa que en la última fila todos los coeficientes son positivos, por lo tanto se cumple la condición de parada, obteniendo la solución óptima.
La solución óptima viene dada por el valor de Z en la columna de los valores solución, en nuestro caso: 33. En la misma columna se puede observar el punto donde se alcanza, observando las filas correspondientes a las variables de decisión que han entrado en la base: (x,y) = (3,12)
HISTORIA
Historia de la programación lineal
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 Kantoróvich, 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. En 1979, otro matemático ruso, Leonid Khachiyan, demostró que el problema de la programación lineal era resoluble en tiempo polinomial. Más tarde, en 1984, Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal, lo que constituiría un enorme avance en los principios teóricos y prácticos en el área.
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 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 cifras comerciales en una red lineal 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.
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 Kantoróvich, 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. En 1979, otro matemático ruso, Leonid Khachiyan, demostró que el problema de la programación lineal era resoluble en tiempo polinomial. Más tarde, en 1984, Narendra Karmarkar introduce un nuevo método del punto interior para resolver problemas de programación lineal, lo que constituiría un enorme avance en los principios teóricos y prácticos en el área.
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 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 cifras comerciales en una red lineal 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.
sábado, 18 de septiembre de 2010
Puntos de P.L
3.6-5. Maureen Laird es el director financiero de la Alba Electric Co., empresa importante en el medio oeste. La empresa ha programado la construcción de nuevas centrales hidroeléctricas a 5, 10, y 20 años, para satisfacer las necesidades de la creciente población en la región servida por la empresa. Para cubrir por lo menos los costos de construcción, Maureen tiene que invertir parte del dinero de la empresa para cubrir estas necesidades futuras de liquidez. Maureen Sólo puede comprar tres tipos de activos financieros, cada uno cuesta $ 1 millón por unidad. Unidades fraccionales pueden ser comprados. Los activos que produzcan ingresos de 5, 10 y 20 años a partir de ahora, y que los ingresos se necesitan para cubrir al menos el flujo de efectivo mínimo las necesidades de estos años. (Cualquier excedente de ingresos por encima del mínimo obligación de que cada período de tiempo se aprovechará para aumentar el pago de dividendos a los accionistas en lugar de guardarlo para ayudar a cumplir con el requisito mínimo de liquidez en el próximo período de tiempo.)La siguiente tabla muestra los ingresos generados por cada unidad de cada activo y el mínimo de ingresos necesarios para cada uno de los periodos futuros cuando una nueva central hidroeléctrica se construirá.
- Formule un modelo de programación lineal
- Despliegue el modelo en una hoja de calculo
- Utilice la hoja de cálculo para verificar la posibilidad de comprar 100 unidades de la acción 1, 100 de la acción 2 y 200 de la 3. ¿cuanto efectivo generara esta mezcla de inversiones dentro 5, 10 y 20 años?
- Utilice el enfoque de prueba error con hoja cálculo para obtener su mejor solución óptima. ¿cual es la inversión total para su solución?
- Use Excel Solver para el modelo por el método simplex.
SOLUCION:
Pasamos el problema a la forma estándar, añadiendo variables de exceso, holgura, y artificiales según corresponda.
.A.
MINIMIZAR: z= X1 + X2 + X3 MAXIMIZAR: z= -1 X1 -1 X2 -1 X3 + 0 X4 + 0 X5 +
0 X6 + 0 X7 + 0 X8 + 0 X9
2 X1 + 1 X2 + 0.5 X3 ≥ 400
0.5 X1 + 0.5 X2 + 1 X3 ≥ 100
0 X1 + 1.5 X2 + 2 X3 ≥ 300
X1, X2, X3 =0
MAXIMIZAR: z= -1 X1 -1 X2 -1 X3 + 0 X4 + 0 X5 +0 X6 + 0 X7 + 0 X8 + 0 X9
2 X1 + 1 X2 + 0.5 X3 -1 X4 + 1 X7 = 400
0.5 X1 + 0.5 X2 + 1 X3 -1 X5 + 1 X8 = 100
0 X1 + 1.5 X2 + 2 X3 -1 X6 + 1 X9 = 300
X1, X2, X3 ≥ 0 X1, X2, X3, X4, X5, X6, X7, X8, X9 ≥ 0
C.
(X1, x2, x3)= (100, 100,200) es una posible solución. Esto puede generar 400millones en 5 años, 300 en 10 años, y 550 millones en 20 años. La total inversión será 400 millones.
ANEXO TABLAS ESCANEADAS
B.
Solución por PHPsimplex:
Tabla 1 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | -1 | ||
Base | Cb | P0 | P1 | P2 | P3 | P4 | P5 | P6 | P7 | P8 | P9 |
P7 | -1 | 400 | 2 | 1 | 0.5 | -1 | 0 | 0 | 1 | 0 | 0 |
P8 | -1 | 100 | 0.5 | 0.5 | 1 | 0 | -1 | 0 | 0 | 1 | 0 |
P9 | -1 | 300 | 0 | 1.5 | 2 | 0 | 0 | -1 | 0 | 0 | 1 |
Z | -800 | -2.5 | -3 | -3.5 | 1 | 1 | 1 | 0 | 0 | 0 |
Tabla 2 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | -1 | ||
Base | Cb | P0 | P1 | P2 | P3 | P4 | P5 | P6 | P7 | P8 | P9 |
P7 | -1 | 350 | 1.75 | 0.75 | 0 | -1 | 0.5 | 0 | 1 | -0.5 | 0 |
P3 | 0 | 100 | 0.5 | 0.5 | 1 | 0 | -1 | 0 | 0 | 1 | 0 |
P9 | -1 | 100 | -1 | 0.5 | 0 | 0 | 2 | -1 | 0 | -2 | 1 |
Z | -450 | -0.75 | -1.25 | 0 | 1 | -2.5 | 1 | 0 | 3.5 | 0 |
Tabla 3 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | -1 | ||
Base | Cb | P0 | P1 | P2 | P3 | P4 | P5 | P6 | P7 | P8 | P9 |
P7 | -1 | 325 | 2 | 0.625 | 0 | -1 | 0 | 0.25 | 1 | 0 | -0.25 |
P3 | 0 | 150 | 0 | 0.75 | 1 | 0 | 0 | -0.5 | 0 | 0 | 0.5 |
P5 | 0 | 50 | -0.5 | 0.25 | 0 | 0 | 1 | -0.5 | 0 | -1 | 0.5 |
Z | -325 | -2 | -0.625 | 0 | 1 | 0 | -0.25 | 0 | 1 | 1.25 |
Tabla 4 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | -1 | ||
Base | Cb | P0 | P1 | P2 | P3 | P4 | P5 | P6 | P7 | P8 | P9 |
P1 | 0 | 162.5 | 1 | 0.3125 | 0 | -0.5 | 0 | 0.125 | 0.5 | 0 | -0.125 |
P3 | 0 | 150 | 0 | 0.75 | 1 | 0 | 0 | -0.5 | 0 | 0 | 0.5 |
P5 | 0 | 131.25 | 0 | 0.40625 | 0 | -0.25 | 1 | -0.4375 | 0.25 | -1 | 0.4375 |
Z | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
Existe alguna solución posible para el problema, por lo que podemos pasar a la Fase II para calcularla.
Tabla 1 | -1 | -1 | -1 | 0 | 0 | 0 | ||
Base | Cb | P0 | P1 | P2 | P3 | P4 | P5 | P6 |
P1 | -1 | 162.5 | 1 | 0.3125 | 0 | -0.5 | 0 | 0.125 |
P3 | -1 | 150 | 0 | 0.75 | 1 | 0 | 0 | -0.5 |
P5 | 0 | 131.25 | 0 | 0.40625 | 0 | -0.25 | 1 | -0.4375 |
Z | -312.5 | 0 | -0.0625 | 0 | 0.5 | 0 | 0.375 |
Tabla 2 | -1 | -1 | -1 | 0 | 0 | 0 | ||
Base | Cb | P0 | P1 | P2 | P3 | P4 | P5 | P6 |
P1 | -1 | 100 | 1 | 0 | -0.416666666667 | -0.5 | 0 | 0.333333333333 |
P2 | -1 | 200 | 0 | 1 | 1.33333333333 | 0 | 0 | -0.666666666667 |
P5 | 0 | 50 | 0 | 0 | -0.541666666667 | -0.25 | 1 | -0.166666666667 |
Z | -300 | 0 | 0 | 0.0833333333333 | 0.5 | 0 | 0.333333333333 |
La solución óptima es Z = 300
X1 = 100
X2 = 200
X3 = 0
X1 = 100
X2 = 200
X3 = 0
Suscribirse a:
Entradas (Atom)