Programación Lineal: El Método Simplex y sus cálculos de Gauss-Jordan

Programación Lineal

Metodo Simplex Curso: Investigación de Operaciones Ing. Javier Villatoro fjvillatoro.wordpress.com

Método Simplex

El método simplex es un método iterativo y analítico para la solución de problemas de programación lineal capaz de resolver modelos más complejos que los resueltos por el método grafico sin restricción en el número de variables.

OD -> 1D 2D -> 3D 1D -> 2D 3D -> 4D

Este método permite ir mejorando la solución a cada paso. La razón matemática de esta mejora radica en que el método consiste en caminar de vértice a vértice de manera de ir optimizando la función objetivo.

Fue desarrollado alrededor de 1947 por el norteamericano George Dantzig con el objetivo de crear un algoritmo capaz de solucionar de problemas de m restricciones y n variables.

Tipo de Optimización

• Maximizar: Obtener el valor optimo mayor
• Minimizar: Obtener el valor optimo menor

Condiciones del modelo

• El objetivo consistirá en maximizar o minimizar el valor de la función objetivo
• Todas las restricciones deben ser ecuaciones de igualdad (identidad)
• Todas las variables X, deben tener valor positivo o nulo
• Los términos independientes b; de cada ecuación debe ser no negativo

Preparación para el método simplex

• El procedimiento algebraico se basa en la solución de ecuaciones, por lo tanto, el primer paso para preparar el método simplex es convertir las restricciones funcionales de desigualdad en restricciones de igualdad equivalentes (de Inecuaciones a Ecuaciones), esto a través de variables de holgura.

Variables de Holgura

• (Cantidad no utilizada del recurso) Es aquella que se introduce en las restricciones identificadas en la formulación del modelo con el propósito de convertir las desigualdades de la restricción en igualdades o ecuaciones para el correcto funcionamiento del método. Se representan como Sn, donde n corresponde al número de variable de holgura.
• Estas variables suelen estar representadas por la letra "S", se suman si la restricción es de signo " <= " y se restan si la restricción es de signo ">=".

Restricciones

Tipo de Restricción

Mayor o igual ">=" (-) holgura (+) artificial Igual (+) artificial Menor o igual " <= " (+) holgura

Inecuaciones modeladas mediante programación lineal

2X1 + 3X2 + 1X3 ≤ 500 3X1 + 1X2 + 1X3 ≤ 700 4×1 + 2X2 + 2X3 ≤ 800

Inecuaciones transformadas en ecuaciones

2X1 + 3X2 + 1X3 +[1S1 + 0S2 + 0S3]=500 3X1 + 1X2 + 1X3 + OS1 + 1S2 + 0S3 = 700 4X1 + 2X2 + 2X3 + OS1 + 0S2 + 1S3 =800 Matriz Identidad

Condición de Optimalidad

• El método simplex asegura a través de cada iteración que encuentra una solución más óptima al punto de solución actual.
• El criterio de la variable de entrada consiste en:
• Elegir en maximización a la variable que tiene el mayor coeficiente negativo de la ecuación X. (función objetivo).
• En minimización el criterio a elegir es el más positivo.
• De acuerdo a esta condición, se llega al óptimo cuando: todos los coeficientes del lado izquierdo de la ecuación X. son no negativos en maximización
• o bien no positivos en minimización.
• Un empate entre las variables se rompe arbitrariamente.

Condición de Factibilidad

• El método asegura que partiendo de una solución básica factible, únicamente se encontraran soluciones básicas factibles.
• Relacionada a esta condición se encuentra asociado el criterio de la variable de salida que consiste en
• Elegir la variable correspondiente al cociente más pequeño positivo de los valores actuales de la solución entre los coeficientes positivos de las restricciones de la variable que entra.
• El criterio para seleccionar la variable de salida es el mismo independientemente si el objetivo es de tipo maximización o minimización.
• Un empate se rompe arbitrariamente.

Cálculos de Gauss-Jordan

• Fila Pivote
• Reemplace la variable de salida en la columna básica con la variable de entrada
• Nueva Fila Pivote = Fila Pivote Actual / Elemento pivote
• Todas las demás filas, incluyendo Z
• Nueva Fila = (Fila Actual) - (Coeficiente de la columna Pivote) x (Nueva fila Pivote)

Pasos en el método simplex

1. Determine la solución factible básica inicial
2. Determine la variable de Entrada utilizando la condición de optimalidad
3. Seleccione la variable de salida utilizando la condición de factibilidad
4. Aplique los pasos de cálculo de Gauss-Jordan para determinar la nueva solución básica. Vaya al paso 1.

Ejemplo de Programación Lineal

X2 6 Maximizar z = 5x1 + 4x2 sujeto a: 6x1+ 4x2+ $1 = 24 1 5 X1 + 2x2 + $2 = 6 2 $1 = 0 1 -X1 + x2 + 53 = 1 3 4 3 X2 + 54= 2 4 S3 =0 x1, X2≥ 0 3 2 $2 = 0 4 2 S4 = 0 C 1 A I B 5 -2 -1 0 1 2 3 4 5 6 24 6 -1 == ₹=4 =- 1 T = 6

Ejemplo: Reddy Mikks

Reddy Mikks produce pinturas para interiores y exteriores con dos materias primas, M1 y M2. La tabla siguiente proporciona los datos básicos del problema.

Toneladas de materia prima por tonelada de Pintura para exteriores Pintura para interiores Disponibilidad diaria máxima (toneladas) Materia prima, M1 6 4 24 Materia prima, M2 1 2 6 Utilidad por tonelada ($1000) 5 4

Una encuesta de mercado indica que la demanda diaria de pintura para interiores no puede exceder la de pintura para exteriores en más de una tonelada (Limite del mercado). Asimismo, que la demanda diaria máxima de pintura para interiores es de dos toneladas (límite de la demanda). Reddy Mikks se propone determinar la (mejor) combinación óptima de pinturas para interiores y exteriores que maximice la utilidad diaria total.

Solución del Problema

Tabla Básica

Maximizar z = 5x1 + 4x2 + 0$1 + 0s2 + 0s3 + 054 sujeto a = 24 (materia prima M1) 6×1 + 4x2 + $1 x1 + 2x2 + $2 = 6 (materia prima M2) - x1 + x2 + 53 = 1 (Límite del mercado) X2 +$4 = 2 (Límite de la demanda) x1,X2,51,52,53, 54 ≥0 Las variables $1, $2, S3 y S4 son las holguras asociadas con las restricciones respectivas. A continuación escribimos la ecuación objetivo como z - 5x1 - 4x2 = 0

Básica Z x1 X2 S1 S2 S3 S4 Solución Z 1 -5 -4 0 0 0 0 0 Fila z S1 0 6 4 1 0 0 0 24 Fila s1 S2 0 1 2 0 1 0 0 6 Fila s2 S3 0 -1 1 0 0 1 0 1 Fila S3 S4 0 0 1 0 0 0 1 2 Fila S4

Solución: Variable Entrante y Saliente

Según la condición de optimalidad (la variable más negativa), la variable entrante es X y la variable saliente es S1 (coeficiente más pequeño positivo).

Básica ×1 entrante Solución Relación (o intersección) S1 6 24 x1 = 24 = 4 - mínimo S2 1 6 ×1 = f = 6 S3 -1 1 ×1 = - = - 1 (denominador negativo, ignorar) S4 0 2 x1 = § = oo (denominador cero, ignorar) Conclusión: x1 entra (en el nivel 4) y x2 sale (en el nivel cero)

Entra 1 Básica Z X1 X2 S1 S2 S3 S4 Solución Z 1 -5 -4 0 0 0 0 0 Sale < S1 0 6 4 1 0 0 0 24 Fila pivote S2 0 1 2 0 1 0 0 6 S3 0 -1 1 0 0 1 0 1 S4 0 0 1 0 0 0 1 2 Columna pivote

Solución: Nueva Tabla y Condición de Optimalidad

La nueva tabla es

1 Básica Z x1 X2 $1 S2 S3 S4 Solución Z 1 0 -3 6 0 0 0 20 x1 0 1 2 1 6 0 0 0 4 1 S2 0 0 3 9. 1 0 0 2 S3 0 0 5 1 0 1 0 5 S4 0 0 1 0 0 0 1 2

En la última tabla, la condición de optimalidad muestra que x2 es la variable de entrada. La condición de factibilidad produce la siguiente información:

Básica Entrante X2 Solución Relación x1 Nim than inim - 4 X2 = 4 + 2 = 6 S2 2 x2 = 2 + 4 = 1.5 (mínima) S3 5 x2 = 5 + 5 = 3 S4 2 x2 = 2 +1=2 1 - 3 6 5

Solución Final

Estos cálculos producen la siguiente tabla:

Según la condición de optimalidad, ninguno de los coeficientes de la fila z son negativos. De ahí que la última tabla sea óptima.

Básica Z x1 X2 51 S2 S3 54 Solución Z 1 0 0 3 1 0 0 21 x1 0 1 0 4 -3 0 0 3 X2 0 0 1 8 4 0 0 5 S3 0 0 0 8 4 1 0 SA 0 0 0 1 3 0 1

Inecuación FONa regfac : (6 x + 4 y ≤ 24) Número ValorFO = 21 5 Punto O A = (1,2) B = (2,2) 4 ..... C = (3, 1.5) D = (4, 0) E = (0, 1) 3 Recta ..... FO: 5x + 4y = 21 A B ـحـ d C c: - x + y = 1 d: y = 2 10 0 -4 -3 -2 -1 0 1 -N 3 4 5 6 ValorFO = 21 -1- -2- < > C 1 1 1 3 3 5 - - 4 0 Da: 3x + 2y = 12 b: x + 2y = 6 D 4

Solución Óptima

La solución óptima puede leerse en la tabla simplex de la siguiente manera. Los valores óptimos de las variables en la columna Basic aparecen en la columna Solución del lado derecho y se interpretan como sigue:

Variable de decisión y Valor óptimo

Variable de decisión Valor óptimo Recomendación x1 3 Producir 3 toneladas diarias de pintura para exteriores x2 Producir 1.5 toneladas diarias de pintura para interiores Z 21 La utilidad diaria es de $21,000

La solución también da el estado de los recursos. Un recurso se designa como escaso si la variable de holgura asociada es cero, es decir, las actividades (variables) del modelo consumieron el recurso por completo. De lo contrario, si la holgura es positiva, entonces el recurso es abundante.

Clasificación de Restricciones

La siguiente tabla clasifica las restricciones del modelo:

Recurso Valor de holgura Estado Materia prima, M1 $1= 0 Escaso Materia prima, M2 $2 = 0 Escaso Límite del mercado S3 =2 Abundante Límite de la demanda 54 = 1 Abundante

Ejercicio en Clase

Una escuela prepara una excursión para 400 alumnos. La empresa de transportes tiene 8 buses pequeños con una capacidad de 40 personas y 10 buses grandes con capacidad de 50 personas, pero solo dispone de 9 conductores. El alquiler de un bus grande cuesta $80 y el de uno pequeño $60. Calcular cuantos de cada tipo hay que utilizar para que la excursión resulte lo mas económica posible para la escuela. R. 620