Metodo Simplex

TEMA 2. PROGRAMACIÓN LINEAL. MÉTODO SIMPLEX. RESUMEN

MÉTODO SIMPLEX. PROCEDIMIENTO PARA CONVERTIR EL PROBLEMA ORIGINAL EN SU FORMA ESTÁNDAR El método gráfico es útil cuando se tienen 2 variables en el problema. Si este número aumenta es necesario emplear el método simplex. Un problema de programación lineal está en su forma estándar si todas las restricciones son igualdades y si se conoce unasolución factible. Para lograr esto, es necesario utilizar las siguientes reglas. PASO 1. CONVERTIR LAS RESTRICCIONES (CON LADOS DERECHOS NO NEGATIVOS) EN IGUALDADES. 1. VARIABLE DE HOLGURA. Son variables no negativas que se agregan al lado izquierdo de la desigualdad cuando es del tipo para convertirla en una ecuación. Representan el recurso que se tiene pero no es empleado. 2. VARIABLESUPERFLUA. Son variables no negativas que se restan al lado izquierdo de la desigualdad cuando es del tipo y la convierten en ecuación. Representan los excedentes por encima del requerido. PASO 2. AGREGAR VARIABLES ARTIFICIALES A CADA RESTRICCIÓN QUE NO CONTENGA UNA VARIABLE DE HOLGURA. 1. VARIABLE ARTIFICIAL. Son variables que se agregan a todas las restricciones que no tienen variables de holgura. PASO3. DETERMINAR UNA SOLUCIÓN INICIAL AL SISTEMA. 1. Cada variable de holgura y cada artificial se igualan al lado derecho de la ecuación en la que aparecen. 2. Todas las demás variables, incluidas las superfluas, se igualan a cero. PASO 4. INTRODUCIR COSTOS DE PENALIZACIÓN. 1. Todas las variables de holgura y superfluas se introducen en la función objetivo con coeficientes CERO. 2. Todas lasvariables artificiales se agregan a la función objetivo con coeficiente M para problemas de minimización y –M para problemas de maximización. En ambos casos el valor de M es muy grande ( 4 veces mayor al estar trabajando en la computadora)

MÉTODO SIMPLEX. NOTACIÓN MATRICIAL DE LA FORMA ESTÁNDAR Función objetivo:

Con la condición:

Con

Donde , incluyendo todas las variables de holgura,superfluas y artificiales.

Se llena una tabla como la siguiente

EJEMPLO. Convertir el siguiente conjunto de restricciones en ecuaciones ------ (1) -------(2) ------(3) Solución. Paso 1. Agregar variables de holgura. Solo se usan en la primera desigualdad ----(4) Paso 2. Variables superfluas. Se utilizan en la segunda desigualdad -----(5) Paso 3. Variables artificiales. Usarlas en (5) y (3) ----(6)---- (7)

Y las restricciones iniciales quedan (agregamos todas las variables a las ecuaciones resultantes (4), (6) y (7) )

Paso 4. Determinar solución inicial

EJEMPLO. Póngase el siguiente programa en su forma estándar. Maximizar Con las condiciones ------ (1) -------(2) Con

Solución. Paso 1. Agregar variables de holgura. Solo se usan en la primera desigualdad ----(3) Paso 2.Variables superfluas. No Se utilizan porque no hay desigualdades del tipo “mayor o igual que” Paso 3. Variables artificiales. Usarlas en (2) ----(4) Y las restricciones iniciales quedan (agregamos todas las variables a las ecuaciones resultantes (3), y (4) )

Paso 4. Determinar solución inicial

Paso 5. Costos de penalización Como se agregaron variables artificiales y estamos maximizando, la funciónobjetivo queda

EJEMPLO. Póngase el siguiente problema en forma estándar. Maximizar

Con las condiciones ------ (1) -------(2) ------(3) Con

Solución. Paso 1. Agregar variables de holgura. No se utilizan Paso 2. Agregar variables superfluas. Se utilizan en las 3 desigualdades ----(4) ----(5) ----(6) Paso 3. Variables artificiales. Usarlas en (4), (5) y (6) ----(7) ----(8) ----(9) Y lasrestricciones iniciales quedan (agregamos todas las variables a las ecuaciones resultantes (7), , (8) y (9) ) ----(10) ----(11) ----(12) Paso 4. Determinar solución inicial

Paso 5. Costos de penalización Como se agregaron variables artificiales y estamos maximizando, la función objetivo queda

EJEMPLO. Para el ejemplo resuelto por el método gráfico indicado, resolverlo ahora utilizando el...