Programacion Lineal
Páginas: 18 (4433 palabras)
Publicado: 1 de octubre de 2012
PROGRAMACION LINEAL: METODO SIMPLEX
Un modelo de Programación Lineal (PL) considera que las variables de decisión tienen un comportamiento lineal, tanto en la función objetivo como restricciones del problema. En este sentido, la Programación Lineal es una de las herramientas más utilizadas en la Investigación Operativa debido a que por su naturaleza se facilitan los cálculos y en generalpermite una buena aproximación de la realidad.
Los Modelos Matemáticos se dividen básicamente en Modelos Determistas (MD) o Modelos Estocásticos (ME). En el primer caso (MD) se considera que los parámetros asociados al modelo son conocidos con certeza absoluta, a diferencia de los Modelos Estocásticos, donde la totalidad o un subconjunto de los parámetros tienen una distribución de probabilidadasociada. Los cursos introductorios a la Investigación Operativa generalmente se enfocan sólo en Modelos Determistas.
METODO SIMPLEX
El método simplex está basado fundamentalmente en este concepto. Careciendo de la ventaja visual asociada con la representación gráfica del espacio de soluciones, el método simplex emplea un proceso iterativo que principia en un punto extremo factible,normalmente el origen, y se desplaza sistemáticamente de un punto extremo factible a otro, hasta que se llega por último al punto óptimo.
Existen reglas que rigen la selección del siguiente punto extremo del método simplex:
1. El siguiente punto extremo debe ser adyacente al actual.
2. La solución no puede regresar nunca a un punto extremo considerado con la anterioridad.
El algoritmosimplex da inicio en el origen, que suele llamarse solución inicial. Después se desplaza a un punto extremo adyacente. La elección específica de uno a otro punto depende de los coeficientes de la función objetivo hasta encontrar el punto óptimo.
Al aplicar la condición de optimidad a la tabla inicial seleccionamos a Xi como la variable que entra. En este punto la variable que sale debe ser unade las variables artificiales.
Los pasos del algoritmo simplex son:
1. Determinar una solución básica factible inicial.
2. Prueba de optimidad: determinar si la solución básica factible inicial es óptima y sólo si todos los coeficientes de la ecuación son no negativos ( >= 0 ). Si es así, el proceso termina; de otra manera se lleva a cabo otra interacción para obtener la nuevasolución básica factible inicial.
3. Condición de factibilidad.- Para todos los problemas de maximización y minimización, variable que sale es la variable básica que tiene la razón más pequeña (positiva). Una coincidencia se anula arbitrariamente.
4. Seleccionar las variables de holgura como las variables básicas de inicio.
5. Selecciona una variable que entra de entre las variables nobásicas actuales que, cuando se incrementan arriba de cero, pueden mejorar el valor de la función objetivo. Si no existe la solución básica es la óptima, si existe pasar al paso siguiente.
6. Realizar el paso iterativo.
a) Se determina la variable básica entrante mediante la elección de la variable con el coeficiente negativo que tiene el valor mayor valor absoluto en la ecuación. Se enmarcala columna correspondiente a este coeficiente y se le da el nombre de columna pivote.
b) Se determina la variable básica que sale; para esta, se toma cada coeficiente positivo (>0) de la columna enmarcada, se divide el lado derecho de cada renglón entre estos coeficientes, se identifica la ecuación con el menor cociente y se selecciona la variable básica para esta ecuación.
c) Sedetermina la nueva solución básica factible construyendo una nueva tabla en la forma apropiada de eliminación de Gauss, abajo de la que se tiene. Para cambiar el coeficiente de la nueva variable básica en el renglón pivote a 1, se divide todo el renglón entre el número pivote, entonces
renglón pivote nuevo = renglón pivote antiguo
número pivote ...
Un modelo de Programación Lineal (PL) considera que las variables de decisión tienen un comportamiento lineal, tanto en la función objetivo como restricciones del problema. En este sentido, la Programación Lineal es una de las herramientas más utilizadas en la Investigación Operativa debido a que por su naturaleza se facilitan los cálculos y en generalpermite una buena aproximación de la realidad.
Los Modelos Matemáticos se dividen básicamente en Modelos Determistas (MD) o Modelos Estocásticos (ME). En el primer caso (MD) se considera que los parámetros asociados al modelo son conocidos con certeza absoluta, a diferencia de los Modelos Estocásticos, donde la totalidad o un subconjunto de los parámetros tienen una distribución de probabilidadasociada. Los cursos introductorios a la Investigación Operativa generalmente se enfocan sólo en Modelos Determistas.
METODO SIMPLEX
El método simplex está basado fundamentalmente en este concepto. Careciendo de la ventaja visual asociada con la representación gráfica del espacio de soluciones, el método simplex emplea un proceso iterativo que principia en un punto extremo factible,normalmente el origen, y se desplaza sistemáticamente de un punto extremo factible a otro, hasta que se llega por último al punto óptimo.
Existen reglas que rigen la selección del siguiente punto extremo del método simplex:
1. El siguiente punto extremo debe ser adyacente al actual.
2. La solución no puede regresar nunca a un punto extremo considerado con la anterioridad.
El algoritmosimplex da inicio en el origen, que suele llamarse solución inicial. Después se desplaza a un punto extremo adyacente. La elección específica de uno a otro punto depende de los coeficientes de la función objetivo hasta encontrar el punto óptimo.
Al aplicar la condición de optimidad a la tabla inicial seleccionamos a Xi como la variable que entra. En este punto la variable que sale debe ser unade las variables artificiales.
Los pasos del algoritmo simplex son:
1. Determinar una solución básica factible inicial.
2. Prueba de optimidad: determinar si la solución básica factible inicial es óptima y sólo si todos los coeficientes de la ecuación son no negativos ( >= 0 ). Si es así, el proceso termina; de otra manera se lleva a cabo otra interacción para obtener la nuevasolución básica factible inicial.
3. Condición de factibilidad.- Para todos los problemas de maximización y minimización, variable que sale es la variable básica que tiene la razón más pequeña (positiva). Una coincidencia se anula arbitrariamente.
4. Seleccionar las variables de holgura como las variables básicas de inicio.
5. Selecciona una variable que entra de entre las variables nobásicas actuales que, cuando se incrementan arriba de cero, pueden mejorar el valor de la función objetivo. Si no existe la solución básica es la óptima, si existe pasar al paso siguiente.
6. Realizar el paso iterativo.
a) Se determina la variable básica entrante mediante la elección de la variable con el coeficiente negativo que tiene el valor mayor valor absoluto en la ecuación. Se enmarcala columna correspondiente a este coeficiente y se le da el nombre de columna pivote.
b) Se determina la variable básica que sale; para esta, se toma cada coeficiente positivo (>0) de la columna enmarcada, se divide el lado derecho de cada renglón entre estos coeficientes, se identifica la ecuación con el menor cociente y se selecciona la variable básica para esta ecuación.
c) Sedetermina la nueva solución básica factible construyendo una nueva tabla en la forma apropiada de eliminación de Gauss, abajo de la que se tiene. Para cambiar el coeficiente de la nueva variable básica en el renglón pivote a 1, se divide todo el renglón entre el número pivote, entonces
renglón pivote nuevo = renglón pivote antiguo
número pivote ...
Leer documento completo
Regístrate para leer el documento completo.