Metodo simplex

EL ALGORITMO SIMPLEX. COMO TRANSFORMAR UN PL EN FORMA ESTÁNDAR. Un PL estándar puede tener restricciones en forma de igualdad o desigualdad, variables no negativas o variables que no pueden tener restricciones de signo. Para usar el algoritmo simplex debemos transformar el PL en un problema equivalente en las que todas las restricciones son ecuaciones y todas las variables no son negativas. Esasí como un PL está en su forma estándar. ESTUDIO SOBRE EL ALGORITMO SIMPLEX. Una vez transformado un PL con m restricciones en la forma estándar si se supone que la forma estándar contiene n variables (denominadas x1, x2,…xn para nuestra comodidad). La forma estándar para el PL sería lo siguiente:

Una solución de un sistema lineal se obtiene una solución básica de ax = b haciendo n –m variablesiguales a cero y se despeja las m variables que quedan, esto supone que hacer las m-n variables iguales a cero proporciona valores únicos para las m variables restantes o equivalentemente, las columnas de las m variables constantes son linealmente independientes. TEOREMA 1. La región factible para cualquier problema de programación lineal es un conjunto convexo, también si un PL tiene una soluciónóptima tendré que existir un punto extremo de la región factible que es óptimo. TEOREMA 2. Para cualquier PL existe un punto extremo único de la región factible del PL que corresponde a cada solución básica factible, también existe por lo menos una sbf que corresponde a cada punto extremo de la región factible. Para resolver un problema de maximización por el algoritmo simplex los pasos son: Paso1. Encontrar una sbf para el PL, sbf se le llama a la solución básica factible inicial. Paso 2. Verificar que la sbf actual es la solución óptima par el PL, sino se debe encontrar una sbf adyacente que tenga un mayor valor de z. Paso 3. Regresar al paso 2 usando la nueva sbf con la sbf actual. EL ALGORITMO SIMPLEX El algoritmo simplex para resolver un PL en las cuales la meta es maximizar lafunción objetivo, el algoritmo simplex es la siguiente:

Paso1. Transformar el PL. En la forma estándar. Paso 2. Obtener una sfb (si es posible) a partir de la forma estándar. Paso3. Se determina si la sfb es óptima. Paso 4. Cuando la sfb no es optima, por lo tanto se determina que variable no básica se debe transformar en una variable básica. Paso 5. Usar el OER para encontrar la nueva sfb con elmejor valor de la función objetivo y regresar al paso 3. EL MÉTODO SIMPLEX DE DOS FASES. Este método es utilizado cuando no es tan fácil encontrar una solución factible. Dentro de este método se añaden variables artificiales a las restricciones igual que al método de la M grande. Existen ciertos pasos que se tiene que seguir para encontrar una solución con este método. 1. A) Modificar lasrestricciones de tal forma que al lado derecho de cada restricción sea no negativo. B) Identificar cada restricción si es una igualdad o una desigualdad y se añadirán una variable artificial por cada restricción. 2. Se transforma cada restricción en forma de desigualdad en la forma estándar. 3. Si la restricción i es una restricción o una igualdad, se añade la variable a a la restricción i y también se añadela restricción de signo ai 0. 4. Se resuelve una PL cuya función objetivo es min w´. A esto se le llama el PL fase I. Como cada ai 0, la solución del PL fase 1 corresponderá a uno de los casos siguientes: Caso 1. El óptimo valor de w´ es mayor que cero. Por lo tanto el PL no tiene solución. Caso 2. El óptimo valor de w´ es igual a cero, y no hay variables artificiales. En este caso se omitentodas las columnas que corresponden a las variables artificiales. La solución óptima del PL fase II, es la solución óptima para el PL original. Caso 3. El óptimo valor de w´ es igual a cero, y por lo menos una variable artificial está en la base óptima de la fase I. REPRESENTACION DE CUADROS SIMPLEX En lugar de escribir cada variable en cada restricción usamos frecuentemente una representación...