Varios
Páginas: 5 (1066 palabras)
Publicado: 6 de noviembre de 2013
TEMATICA:
El método consiste en partir de un vértice del conjunto de soluciones, o solución inicial y determinar si es óptima. Si no lo es, se pasa a partir de él a otro vértice adyacente (es decir, que difiera del anterior en el hecho de que una coordenada no nula del primero se anule en el segundo y viceversa), por un criterio semejante al del gradiente, en el que mejore el valor de lafunción objetivo o función económica, repitiéndose esta operación hasta que no sea posible mejorar la función objetivo, en cuyo caso ya se ha alcanzado el óptimo.
El número de iteraciones es finito y, según los casos, se encuentra entre n y 2n.
Programación lineal con variables enteras y binarias
En muchos casos la naturaleza de las variables que constituyen un programa lineal y lasunidades en que vienen medidas exigen que estas variables tomen valores enteros, ejemplo: Número de vehículos, personas, productos, máquinas, etc.
En tal caso una aproximación para resolver el problema consiste en tratarlo sin tener en cuenta el carácter entero de las variables. Si la solución obtenida por la aplicación del método SIMPLEX resultara entera habríamos terminado con el problema.
Si noes así, una alternativa es redondear la solución, comprobando que el punto así obtenido es realmente una solución, es decir, satisface al conjunto de restricciones, o bien tomar de cada variable su parte entera, realizando la misma comprobación.
Cuando los valores de la variable son de magnitud considerable, estas alternativas garantizan una excelente aproximación al punto óptimo. Cuando losvalores de las variables son pequeños el redondeo puede estar lejos de la solución óptima, Así, que tenga cuidado.
Hay varios métodos para abordar la solución de un programa lineal con variables enteras. El mas conocido es el de “Formas enteras de Gomory o métodos de los hiperplanos de corte” que, básicamente, consiste en introducir restricciones adicionales que sólo pueden satisfacer lassoluciones enteras y que reducen paulatinamente el conjunto inicial de soluciones. Su solución conduce a cálculos muy laboriosos, que ahora se resuelven en el computador.
Otra consideración que se debe tener en cuenta es que se pueden usar variables binarias, esto es, que sólo puede tomar valores de 0 y 1, en un modelo de programación lineal. Esto se usa generalmente en los problemas de asignación.III. SOLUCIONES DE MAXIMIZACION SIMPLEX
La mejor manera de aprender el método simplex es resolviendo problemas de programación lineal Para esto realicemos el siguiente ejercicio.
Una fábrica productora de embalajes plásticos, elabora dos tipos de containers de 3.750 c.c. y 4.000 c.c. Los datos de producción se presentan en la tabla adjunta. La persona encargada del termo-formado nopuede trabajar más de 40 horas a la semana y los recursos económicos de la fábrica no permiten inversiones mayores de US$1.000 de materiales por semana ¿cuántos containers de cada tipo debería fabricar la industria, para obtener la utilidad máxima?
TIPO DE TRABAJO POR COSTO POR UTILIDAD POR
CONTAINER CONTAINER CONTAINER CONTAINER
3750 (A) 6 HORAS $200 $240
4000 (B) 5HORAS $100 $160
PASO 1: Establezca el modelo:
Cómo es posible que haya más de dos variables, es usual representarlas como X1 X2 X3, etc.
Variables independientes
X1: Cantidad de container tipo A
X2: Cantidad de container tipo B
Restricciones
C1: 6X1 + 5X2 Restricción de tiempo
C2: 200X1 + 100X2 Restricción de dinero
C3: X1
C4: X2
Funciónobjetivo:
Z= 240X1 + 160X2 (Z es la utilidad)
PASO 2: Convierta las desigualdades de restricciones en ecuaciones
6X1+5X2=40
Observe que si el número total de horas es menor que 40, implica que algunas horas no se aprovecharon, esto significa que C1 se podría escribir como:
C1=6X1+5X2+S1=40
S1 corresponde a la cantidad de horas no utilizadas, S1
S1 se denomina variable...
El método consiste en partir de un vértice del conjunto de soluciones, o solución inicial y determinar si es óptima. Si no lo es, se pasa a partir de él a otro vértice adyacente (es decir, que difiera del anterior en el hecho de que una coordenada no nula del primero se anule en el segundo y viceversa), por un criterio semejante al del gradiente, en el que mejore el valor de lafunción objetivo o función económica, repitiéndose esta operación hasta que no sea posible mejorar la función objetivo, en cuyo caso ya se ha alcanzado el óptimo.
El número de iteraciones es finito y, según los casos, se encuentra entre n y 2n.
Programación lineal con variables enteras y binarias
En muchos casos la naturaleza de las variables que constituyen un programa lineal y lasunidades en que vienen medidas exigen que estas variables tomen valores enteros, ejemplo: Número de vehículos, personas, productos, máquinas, etc.
En tal caso una aproximación para resolver el problema consiste en tratarlo sin tener en cuenta el carácter entero de las variables. Si la solución obtenida por la aplicación del método SIMPLEX resultara entera habríamos terminado con el problema.
Si noes así, una alternativa es redondear la solución, comprobando que el punto así obtenido es realmente una solución, es decir, satisface al conjunto de restricciones, o bien tomar de cada variable su parte entera, realizando la misma comprobación.
Cuando los valores de la variable son de magnitud considerable, estas alternativas garantizan una excelente aproximación al punto óptimo. Cuando losvalores de las variables son pequeños el redondeo puede estar lejos de la solución óptima, Así, que tenga cuidado.
Hay varios métodos para abordar la solución de un programa lineal con variables enteras. El mas conocido es el de “Formas enteras de Gomory o métodos de los hiperplanos de corte” que, básicamente, consiste en introducir restricciones adicionales que sólo pueden satisfacer lassoluciones enteras y que reducen paulatinamente el conjunto inicial de soluciones. Su solución conduce a cálculos muy laboriosos, que ahora se resuelven en el computador.
Otra consideración que se debe tener en cuenta es que se pueden usar variables binarias, esto es, que sólo puede tomar valores de 0 y 1, en un modelo de programación lineal. Esto se usa generalmente en los problemas de asignación.III. SOLUCIONES DE MAXIMIZACION SIMPLEX
La mejor manera de aprender el método simplex es resolviendo problemas de programación lineal Para esto realicemos el siguiente ejercicio.
Una fábrica productora de embalajes plásticos, elabora dos tipos de containers de 3.750 c.c. y 4.000 c.c. Los datos de producción se presentan en la tabla adjunta. La persona encargada del termo-formado nopuede trabajar más de 40 horas a la semana y los recursos económicos de la fábrica no permiten inversiones mayores de US$1.000 de materiales por semana ¿cuántos containers de cada tipo debería fabricar la industria, para obtener la utilidad máxima?
TIPO DE TRABAJO POR COSTO POR UTILIDAD POR
CONTAINER CONTAINER CONTAINER CONTAINER
3750 (A) 6 HORAS $200 $240
4000 (B) 5HORAS $100 $160
PASO 1: Establezca el modelo:
Cómo es posible que haya más de dos variables, es usual representarlas como X1 X2 X3, etc.
Variables independientes
X1: Cantidad de container tipo A
X2: Cantidad de container tipo B
Restricciones
C1: 6X1 + 5X2 Restricción de tiempo
C2: 200X1 + 100X2 Restricción de dinero
C3: X1
C4: X2
Funciónobjetivo:
Z= 240X1 + 160X2 (Z es la utilidad)
PASO 2: Convierta las desigualdades de restricciones en ecuaciones
6X1+5X2=40
Observe que si el número total de horas es menor que 40, implica que algunas horas no se aprovecharon, esto significa que C1 se podría escribir como:
C1=6X1+5X2+S1=40
S1 corresponde a la cantidad de horas no utilizadas, S1
S1 se denomina variable...
Leer documento completo
Regístrate para leer el documento completo.