Tema iii método gráfico y simplex

Ing. José Gregorio Díaz Landaeta

MÉTODO GRÁFICOAspectos Básicos

•Consiste en graficar las soluciones factibles, o el espacio de soluciones (espacio factible), que satisfaga todas las restricciones simultaneamente.

•Es una manera “simple” de resolver un problema de programación lineal que tenga solamente dos variables de decisión.•Es útil para encontrar la solución óptima e información adicional sobre cuan susceptible es esa solución con respecto a los datos del problema.

•Aun cuando para modelos con tres o más variables, este método es impráctico o imposible, proporciona un buen fundamento para el uso de la P.L. en el mundo real.


MÉTODO GRÁFICOMetodología

•Graficar las soluciones factibles (espacio encerrado por todas las restricciones del modelo).–Reemplazar el signo de desigualdad con un signo de igualdad.

–Grafique la igualdad (línea recta).–Identificar el lado factible de la recta: Seleccione un punto cualquiera (a,b) que no pertenezca a la recta y verifique si satisface la restricción. Si así es, entonces ese punto está en el lado factible; si no es así, el lado factible está en el lado opuesto al punto seleccionado.

El área del gráfico que satisface todas las restricciones, se denomina REGIÓN FACTIBLE (ESPACIO FACTIBLE) y cualquier punto dentro de esta región es una SOLUCIÓN FACTIBLE.


MÉTODO GRÁFICOMetodología

•Determinar la solución óptima.–Método I:•Graficar la función (línea) objetivo. Efectúe Z=0.•Localizar su mejor lado. Grafique Z≠ 0.

•“Mover” la línea de la función objetivo paralela a si misma en la dirección de mejora.

El punto final de corte entre la Región Factible y la función objetivo es la SOLUCIÓN ÓPTIMA.–Método II:•Identifique y determine los puntos de intersección entre las restricciones.•Sustituya estos puntos en la Función objetivo.

El punto que optimiza (minimiza o maximiza) la función objetivo es la SOLUCIÓN ÓPTIMA.


MÉTODO GRÁFICOConclusiones Importantes

•Puntos Extremos: Son los puntos esquina de una región factible. Representan las intersecciones entre las restricciones.•Línea de Función Objetivo: Gráfica donde todos los puntos sobre la línea tienen el mismo valor de función objetivo (Isocostos, Isoutilidades).•Solución Óptima: Punto en la región factible que tiene el mejor valor de la función objetivo. Representan los valores óptimos de las variables de decisión. Pueden existir infinitas soluciones óptimas.

•Valor óptimo: Valor de la función objetivo evaluada en la solución óptima.


MÉTODO GRÁFICOConclusiones Importantes

•Restricción Activa: Aquella que pasa por la solución óptima. Evaluada en la solución óptima, los términos de la restricción son iguales.•Restricción inactiva: Aquella que no pasa por la solución óptima. Evaluada en la solución óptima, los términos de la restricción son diferentes. Posee un excedente o una holgura.•Excedente: Es la diferencia entre el primer miembro y el lado derecho en una restricción ≥ evaluada en la solución óptima.

•Holgura: Es la diferencia entre el lado derecho y el primer miembro de una resstricción ≤ evaluada en la solución óptima.


MÉTODO SIMPLEXAspectos Básicos

•Es un procedimiento de cálculo iterativo que nos permite resolver cualquier problema de programación lineal.•Es un método algebraico sistemático que examina las esquinas (vértices o puntos extremos) de un conjunto factible de P.L. en busca de una solución óptima.•El fundamento del método se sustenta sobre la siguiente relación: Puntos extremos = Soluciones básicas.

•La base del método es el traslado de la definición geométrica del punto extremo a una definición algebraica.


MÉTODO SIMPLEXAspectos Básicos

•Consiste en identificar una solución inicial (Fase I) y luego “moverse” sistemáticamente a otras soluciones básicas que tengan el potencial de mejorar el valor de la función objetivo. Una vez identificada la solución óptima (Fase II), termina el proceso de cálculo.•El método está diseñado de manera que la función objetivo no disminuya (o aumente) en un modelo de maximización (o minimización) y generalmente aumentará (o disminuirá) en cada iteración.•Si el problema es no acotado o incosistente, el algoritmo lo descubrirá durante su ejecución.


MÉTODO SIMPLEXMetodología

•Fase I: Determinar la solución inicial.–Transformar el modelo a la FORMA ESTÁNDAR del modelo de P.L.–Identificar una Solución Inicial Básica Factible.Si el problema es “Inconsistente”, esta fase lo descubrirá.

•Fase II: Determinar la solución óptima.–Seleccionar una variable entrante (Condición de optimidad).–Seleccionar una variable saliente (Condición de factibilidad).–Determinar los valores de las nuevas variables.–Si la solución no es óptima, reinicie la Fase II.Si el problema es “no acotado”, esta fase lo identificará.


MÉTODO SIMPLEXForma Estándar del Modelo de P.L.

•Todas las restricciones son ecuaciones.

•Los segundos miembros de las ecuaciones son no negativos.

•Todas las variables son no negativas.

•La función objetivo puede ser de maximización o de minimización.

La propiedad de no negatividad de las variables, es sumamente importante en el desarrollo del método simplex.



•Transformación de restricciónes en ecuaciones.–Una restricción del tipo ≤ puede convertirse en una ecuación mediante la suma de una variable de holgura al primer miembro de la restricción. Sustituyendo el signo ≤ por =.

–Una restricción del tipo ≥ puede convertirse en una ecuación mediante la sustracción de una variable de exceso al primer miembro de la restricción. Sustituyendo el signo ≥ por =.

•Si el segundo miembro de la restricción es negativo, se multiplican ambos lados por -1.



•No negatividad de las variables.–Si el problema presenta una VARIABLE IRRESTRICTA (no restringida en signo), esta debe expresarse en términos de dos variables no negativas mediante el uso de una sustitución.

Y irrestricta

Se sustituye por

Y = Y1 – Y2

Y1, Y2 ≥ 0

La sustitución debe hacerse en todas las restricciones y en la función objetivo.



•No negatividad de las variables.–Si el problema presenta una VARIABLE NO POSITIVA (≤ 0), esta debe sustituirse por el negativo de una nueva variable no negativa, cuyo símbolo se escoge arbitrariamente.

Y ≤ 0

Se sustituye por

Y = -Y1

Y1 ≥ 0

La sustitución debe hacerse en todas las restricciones y en la función objetivo.



•Función Objetivo.Aunque el modelo estándar puede ser utilizado para resolver problemas del tipo de maximización o de minimización, algunas veces conviene convertir una forma a la otra.

La maximización de una función equivale a la minimización del negativo de la misma función y viceversa.

Maximizar Z = Minimizar –Z.

Esto significa que para el mismo conjunto de restricciones, los valores óptimos de las variables de decisión son lo mismos en ambos casos.


MÉTODO SIMPLEXSolución Inicial Básica Factible

•La forma Estándar de un Modelo de Programación Lineal genera un sistema de M ecuaciones con N incógnitas. Donde N ≥M.

•Una solución básica se determina igualando N-M variables a cero y resolviendo las M ecuaciones con las restantes M variables, siempre que la solución resultante exista y sea única.•La N-M variables que se igualan a cero, son las “Variables no básicas”. Las M variables restantes se conocen como “Variables básicas”.•Con la solución básica (variables básicas y no básicas) se construye la tabla inicial.


MÉTODO SIMPLEXFase II: Solución Óptima

•Seleccionar la variable entrante (Condición de optimidad):

–CASO MAXIMIZACIÓN: Variable no básica con el coeficiente mas negativo en la ecuación Z objetivo. La Solución Óptima se alcanza cuando todos los coeficientes no básicos en la ecuación Z son no negativos.–CASO MINIMIZACIÓN: Variable no básica con el coeficiente mas positivo en la ecuación Z objetivo. La Solución Óptima se alcanza cuando todos los coeficientes no básicos en la ecuación Z son no positivos.

Un empate se rompe arbitrariamente.


MÉTODO SIMPLEXFase II: Solución Óptima

•Seleccionar la variable saliente (Condición de factibilidad):

–Variable básica con la menor intersección (razón mínima con denominador estrictamente positivo) en la dirección de la variable entrante.

–La variable saliente es aquella variable básica que posea la menor razón resultante de dividir la columna “solución” entre los valores positivos (> 0) correspondientes a la “variable entrante”.–Esta condición se aplica tanto a problemas de MAXIMIZACIÓN como de MINIMIZACIÓN.

Un empate se rompe arbitrariamente.


MÉTODO SIMPLEX Fase II: Solución Óptima

•Determinar los valores de las nuevas variables: Método Gauss-Jordan.

–Columna de entrada: Columna debajo de la variable entrante.–Ecuación pivote: Renglón asociado con la variable saliente.–Elemento pivote: Intersección entre la columna de entrada y la ecuación pivote.

•Se realizan las siguientes dos operaciones de cálculo:

–Nueva Ecuación pivote:ecuación pivote/elemento pivote.

–Las demás ecuaciones (incluyendo Z):Ecuación anterior-coeficiente de la columna

entrante*nueva ecuación pivote.


MÉTODO SIMPLEX Regla de detención

•Determinar si la solución básica factible presente es óptima:

–CASO MAXIMIZACIÓN: Si todos las variables tienen coeficientes positivos en la ecuación Z de la tabla simplex.

–CASO MINIMIZACIÓN: Si todas las variables tienen coeficientes negativos en la ecuación Z de la tabla simplex.


MÉTODO SIMPLEXSolución Inicial Básica Factible

Condiciones Básicas

•Cada ecuación debe tener una “variable de holgura”: Variable no negativa con coeficiente +1.

•Cada variable de holgura debe aparecer solo en una restricción.

•Los segundos miembros de las ecuaciones son no negativos.

Si se cumplen estas condiciones se tendrá una solución básica factible con lo que se podrá construir la tabla inicial.


MÉTODO SIMPLEXLa Técnica M

•Se utiliza cuando la “Forma estandar del modelo de P.L.” no permite obtener facilmente una Solución Inicial Básica Factible.

•Procedimiento: –Sumar una variable artificial a aquellas ecuaciones estandarizadas que no posean “variables de holgura”.

–Restar la variable artificial, penalizada, a la función objetivo a maximizar (multiplicada por una constante M, de valor muy grande). Sumar si es minimización.

–Encontrar los coeficientes de la función objetivo modificada: Despejar la variable artificial en la ecuación correspondiente y sustituirla en la función objetivo.

–Aplicar el algoritmo simplex.



•Otro procedimiento: –Sumar una variable artificial a aquellas ecuaciones estandarizadas que no posean “variables de holgura”.–Restar la variable artificial, penalizada, a la función objetivo a maximizar (multiplicada por una constante M, de valor muy grande). Sumar si es minimización.–Construir normalmente la tabla simplex inicial.



•Otro procedimiento: –Transformar la tabla simplex:

•Caso Maximización: Multiplicar por –M los coeficientes de toda ecuación que contenga una variable artificial. Sumar a los coeficientes de la función objetivo.•Caso Minimización: Multiplicar por +M los coeficientes de toda ecuación que contenga una variable artificial. Sumar a los coeficientes de la función objetivo.

–Aplicar el algoritmo simplex.


MÉTODO SIMPLEXCasos Especiales

•Soluciones degeneradas: Ocurre cuando la tabla

presenta un cero (0) en la columna valor. En este caso,

el cálculo no generará variación en el valor de la

función objetivo. La degeneración ocurre cuando una

de las restricciones del modelo es redundante.

•Soluciones infactibles: Ocurre cuando al menos una

“Variable Artificial” es positiva en la iteración óptima.


MÉTODO SIMPLEXCasos Especiales

•Solución no acotada: Ocurre cuando los coeficientes

de las restricciones de una variable no básica (candidata

a entrar) son no positivos.

•Soluciones óptimas múltiples: Ocurre cuando se

encuentra en la iteración óptima, una variable no básica

con coeficiente cero en la función objetivo.

Documents

Tema iii método gráfico y simplex