jueves, 30 de septiembre de 2010
viernes, 24 de septiembre de 2010
trabajo final ( primera entrega)
Trabajo final PL Primera parte
TRABAJO FINAL PL
1. Justificación
La región se ve muy necesitada de nuevas ideas, y de personal capacitado en todas las área relacionadas con el mejoramiento de los procesos productivos, en el suroeste antioqueño podemos observar gran potencial, no solo en la parte agrícola, sino en la parte industrial y turística, y lo que le hace falta es quien formule proyectos y tenga ideas buenas para explotar este potencial.
Nuestra idea va orientada no solo al mejoramiento de los procesos productivos si no a aumentar la productividad y de paso la competitividad de la empresa en el mercado, por medio de la programación lineal.
En la planta de producción de tableros en madera “maderas de café”, ubicada en el municipio de Hispania, se vio la oportunidad de implementar un problema de programación lineal, para maximizar las ganancias.
Como beneficiarios directos de los resultados de este proyecto están los empleados, los caficultores y sus familias y la comunidad en general, gracias a la creación de nuevos empleos.
Oportunidades o potencialidades identificadas que animan a plantear la ejecución del proyecto.
Mejorar la producción y la reducción de desperdicios por medio de optimizar el material utilizado en la fabricación de tableros de madera.
Vinculación al Plan de Desarrollo municipal o departamental.
“La productividad no sólo tiene implicaciones sobre la economía, tiene también implicaciones sociales, y su fin último es mejorar la calidad de vida de las personas, ya que las mejoras de productividad generan mayores niveles de competitividad y por lo tanto beneficios generales a la población.”
Como se dijo anteriormente este trabajo aumentara el numero de empleados de la empresa, generando un gran crecimiento para la economía de la región.
2. Definición del problema o necesidad y alternativa de solución:
Se vería afectada de manera directa la empresa “Maderas de Café” y de forma secundaria agricultores y personas dedicadas a la ebanistería.
Problema principal:
Falta de optimización de recursos y de estudios de programación lineal en la empresa
Causas:
Falta de experiencia, falta de asesoría en el tema, falta de recursos, la reciente creación de la empresa.
Como alternativa de solución a la parte de la capacitación de los trabajadores que laboran en esta empresa, en caso de que la administradora de riesgos profesionales (ARP Sura) ya esté llevando a cabo capacitaciones al momento de la ejecución de proyecto, se complementará éstas con temas que no se cubran allí como la productividad y metodologías para la mejora continua así como también otros relacionados con salud ocupacional e higiene y seguridad industrial.
3. Descripción del proyecto:
En el municipio de Hispania ha estado funcionando, la planta de producción de tableros en madera “maderas de café”.
En esta planta se producen tableros de diferentes maderas en distintos calibres, estos tableros tienen un valor comercial, con el cual son distribuidos y comercializados, la idea es determinar cuál es la cantidad de tableros que deben de producir para maximizar las ganancias, teniendo en cuenta la cantidad de demanda de cada tablero, y la cantidad de materia prima disponible.
4. Objetivos, resultados e indicadores:
Objetivo General (O.G.):
Aprender a aplicar la programación lineal en la vida practica y mejorar la productividad en la planta.
Objetivo Específico (O.E.):
· Mejorar la productividad en la planta, y así contribuir al crecimiento de la empresa y al mejoramiento de la calidad de vida de sus empleado
· Maximizar las ganancias de la empresa de acuerdo a la cantidad de productos procesados.
· Aplicar e implementar un sistema de programación lineal que permita a la empresa saber cual es la relación costo-beneficio de los tableros y sus características.
·
Resultados o productos esperados del proyecto (R):
Formulación del problema en forma matemática.
Lograr la implementación del problema de PL.
Aumentar de forma significativa las ganancias de la planta.
Indicadores Objetivamente Verificables (IOV)
Del Objetivo Específico:
• Aumentar, al menos, en un 40% la productividad de la planta
• Aumentar, al menos, en un 60% las ganancias de la empresa
• Verificar si el problema está bien planteado (trabajo del docente)
De Resultados:
R1 Con ayuda del docente se describirá el proceso y se mirará su factibilidad
R2 Logrando el resultado anterior, con ayuda de los directivos de la compaña (esto depende de la disponibilidad que estos tengan frente al proyecto)
R3 Si se logran hacer los 2 anteriores, este será inmediato.
5. Plan de trabajo y cronograma de actividades:
Se incluye una descripción detallada de cada actividad emprendida para alcanzar los resultados.
Actividades
|
Semana
| |||||||||
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
| ||
Diagnóstico de las condiciones actuales de producción
|
X
| |||||||||
Planteamiento del problema de PL
|
X
| |||||||||
Definición de variables, restricciones y función objetivo
|
X
| |||||||||
Formulación del modelo matemático
|
X
|
X
| ||||||||
Adaptación al caso real del modelo
|
X
|
X
|
X
| |||||||
Verificación de resultados esperados
|
X
| |||||||||
6. Compromisos académicos relacionados con el proyecto:
Se socializarán los resultados del proyecto con los compañeros de clase y con la empresa donde se realiza el trabajo, además de información escrita que describa los pasos llevados a cabo.
7. Bibliografía: Investigación de operaciones – Hillier Lieberman
[1] Plan de desarrollo de Antioquia “Manos a la obra”, 2008-2011 pag. 166 numeral 3.4
tabla punto
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
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
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)