MÉTODO SIMPLEX EN PROBLEMAS DE MAXIMIZACIÓN Y MINIMIZACIÓN.pptx

MÉTODO SIMPLEX
Tabla inicial del método simplex -pasos para completar la tabla.
método simplex en problemas de maximización y minimización.

1. EL MÉTODO SIMPLEX PARA PROBLEMAS DE MAXIMIZACIÓN El algoritmo simplex para problemas de maximización en programación lineal se basa en las siguientes pasos: Paso1.- Se plantea el modelo de programación lineal en forma estándar, de tal manera que incluya una base (matriz identidad de orden m). Paso 2.- Se elabora una TABLA SIMPLEX (inicial) cuya estructura es la siguiente:

2. TABLA INICIAL DEL MÉTODO SIMPLEX     VARIABLES NO BASICAS INICIALES   VARIABLES BASICA INICIALES     C j → c 1 c 2 ... c n c n+1 c n+2 ... c n+m   CB i XB i X 1 X 2 ... X n X n+1 X n+2 ... X m+n b i CB 1 CB 2 . . . CB m XB 1 XB 2 . . . XB m a 11 a 12 ... a 1n a 21 a 22 ... a 2n .............................. ……...................... .............................. a m1 a m2 ... a mn 1 0 ... 0 0 1 ... 0 .................................. .................................. .................................. 0 0 ... 1 b 1 b 2 . . . b m   Z j Z 1 Z 2 ... Z n Z n+1 Z n+2 ... Z n+m Z   Z j - C j Z 1- c 1 Z 2- c 2 Z n- c n Z n+1- c n+1 Z n+2- c n +2 Z n+m- c n+m  

3. EL MÉTODO SIMPLEX PARA PROBLEMAS DE MAXIMIZACIÓN XB i y CB i denota la i- ésima variable básica y su respectivo coeficiente económico. m Z = Σ CB i b i , es el valor actual de la función objetivo i =1 m Z j = Σ CB i a ij ; j=1, 2,..., m+n i=1   La solución básica actual está dado por: variables básicas : XB i = b i , i=1, 2,...,m variables no básicas : Todas iguales a cero Valor de la función objetivo: Z Paso 3.- Si todo Z j -C j ≥ 0, entonces la solución básica actual es ÓPTIMA FACTIBLE y el procedimiento termina. En caso contrario se continúa con el paso 4

4. EL MÉTODO SIMPLEX PARA PROBLEMAS DE MAXIMIZACIÓN Paso 4.- Se selecciona la VARIABLE QUE ENTRA A LA BASE de acuerdo a la siguiente CONDICION DE OPTIMALIDAD: La variable que entra a la base es aquella variable no básica que corresponde al mínimo de Z j -C j . En caso de empate, éste se rompe arbitrariamente. Sea X k la variable seleccionada.   Paso 5.- Se selecciona la VARIABLE QUE SALE DE LA BASE de acuerdo a la siguiente CONDICION DE FACTIBILIDAD: La variable que sale es la r- ésima variable básica siempre que: b r /a rk = min(b i / a ik ), a ik >0, i =1, 2,...,m En caso de empate este se rompe arbitrariamente. Si todo a ik ≤0 entonces el problema no tiene solución óptima finita. El elemento a rk se llama ELEMENTO PIVOTE.

5. EL MÉTODO SIMPLEX PARA PROBLEMAS DE MAXIMIZACIÓN Paso 6.- Se ejecutan operaciones matriciales elementales y se elabora una nueva tabla simplex, logrando que el ELEMENTO PIVOTE se convierta en uno y los restantes elementos de su columna en cero, formando un vector unitario. Los nuevos valores de a ij y b i son:   â ij = a ij / a rk , para i=r, j=1, 2,..., m+n   â ij = a ij - ( a ik /a rk ) a rj para i ≠ r , j=1, 2,..., m+n   b' i = b i /a rk , para i =r   b' i = b i - ( a ik /a rk ) b r , para i ≠ r , j=1, 2,...,n   Con los cuales se calcula los nuevos valores de Z j y Z j -C j , j=1,2,..., m+n y se regresa al paso 3.

6. EJEMPLO La empresa TAKAMURA S.A. fabrica 3 productos a través de tres operaciones diferentes. Los tiempos en minutos requeridos para procesar cada unidad de producto, la capacidad diaria de las operaciones en minutos por día y la ganancia de cada unidad de producto en dólares se muestran en la siguiente tabla. Se requiere determinar el número de unidades de cada producto que debe ser fabricado por TAKAMURA S.A. a fin de maximizar su ganancia total.

7. TABLA   OPERACIÓN TIEMPO REQUERIDO POR UNIDAD CAPACIDAD DE OPERACIÓN PRODUCTO 1 PRODUCTO 2 PRODUCTO 3 A B C 2 6 2 4 -- 8 2 4 -- 500 600 640 GANANCIA 6 4 10  

8. SOLUCIÓN MODELO MATEMÁTICO VARIABLES DE DECISIÓN. x 1 : Número de unidades del producto 1 x 2 : Número de unidades del producto 2 x 3 : Número de unidades del producto 3 MAXIMIZAR Z = 6x 1 + 4x 2 + 10x 3 sujeto a: 2x 1 + 4x 2 + 2x 3 ≤ 500 6x 1 + 4x 3 ≤ 600 2x 1 + 8x 2 ≤ 640 x j ≥ 0, j =1, 2, 3

9. Paso 1 .- Forma estándar del modelo con matriz base: MAXIMIZAR Z = 6x 1 + 4x 2 + 10x 3 + 0s 1 + 0s 2 + 0s 3 sujeto a: 2x 1 + 4x 2 + 2x 3 + s 1 = 500 6x 1 + 4x 3 + s 2 = 600 2x 1 + 8x 2 + s 3 = 640 x j ≥ 0, j = 1, 2, 3 s i ≥ 0, i = 1, 2, 3 Las variables s 1 , s 2 y s 3 son variables de holgura .

10. Paso 2.- Tabla inicial del método simplex   CBi Cj → 6 4 10   bi XBi X1 X2 X3 S1 S2 S3 S1 S2 S3 2 6 2 4 8 2 4 1 1 1 500 600 640   Zj   Zj-Cj -6 -4 -10  

11. Solución básica inicial. Variables básicas : s 1 = 500, s 2 = 600, s 3 = 640 Variables no básicas : x 1 = x 2 = x 3 = 0 Valor función objetivo : Z = 0 Paso 3.- No todo Z j - C j ≥ 0, la solución básica actual no es óptima. Se continúa con el paso 4. Paso 4.- Se selecciona la variable no básica x 3 que entra a la base, por corresponder al min( Z j - C j ) Paso 5.- Se selecciona la variable básica s 2 para que salga de la base, por corresponder al mínimo cociente de los b i entre los respectivos coeficientes a i3 (es decir los coeficientes tecnológicos de la variable que entra) min(500/2, 600/4) = 600/4 = b 2 /a 23 El denominador con valor cero no se toma en cuenta (a 33 = 0) El elemento pivote es a 23 = 4

12. Paso 6.- Se ejecutan operaciones matriciales elementales para convertir el pivote en 1 y los restantes elementos de su columna en 0. la nueva tabla simplex es la siguiente.   CBi Cj → 6 4 10   Bi XBi X1 X2 X3 S1 S2 S3 10 S1 X3 S3 -1 3/2 2 4 8 1 1 -1/2 1/4 1 200 150 640   Zj 15 10 5/2 1500   Zj-Cj 9 -4 5/2  

13. Solución básica actual. Variables básicas : s 1 = 200, x 3 = 150, s 3 = 640 Variables no básicas : x 1 = x 2 = s 2 = 0 Valor función objetivo : 1500 Se regresa al paso 3. Paso 3 .- No todo Z j - C j ≥ 0. La solución actual no es óptima. Paso 4.- Variable que entra es x 2 Paso 5.- Variable que sale es s 1 Elemento pivote es a 12 = 4

14. Paso 6.- Nueva tabla simplex.   CBi Cj → 6 4 10   Bi XBi X1 X2 X3 S1 S2 S3 4 10 X2 X3 S3 -1/4 3/2 4 1 1 1/4 -2 -1/8 1/4 1 1 50 150 240   Zj 14 4 10 1 2 1700   Zj-Cj 8 1 2  

15. Solución básica actual. Variables básicas : x 2 = 50, x 3 = 150, s 3 = 240 Variables no básicas : x 1 = s 1 = s 2 = 0 Valor función objetivo : Z = 1700 Se regresa al paso 3 Paso 3.- Todo Z j - C j ≥ 0, la solución básica es ÓPTIMA FACTIBLE y el procedimiento termina.   La empresa TAKAMURA S. A. debe producir: x 2 = 50 unidades del producto 2 x 3 = 150 unidades del producto 3 Para obtener una ganancia total de Z = $ 1700   El producto 1 (x 1 ) no es rentable producirlo, por tanto la variable que lo representa permanece como variable no básica cuyo valor es cero.   En la operación C hay un excedente de capacidad de 240 minutos (s 3 ), que se interpreta como tiempo no utilizado.

16. SOLUCIÓN CON SOFTWARE POMforwin TABLA DE DATOS

17. TABLA DE RESULTADOS

18. EL MÉTODO SIMPLEX PARA PROBLEMAS DE MINIMIZACIÓN   TÉCNICA DE VARIABLES ARTIFICIALES Los problemas de minimización pueden ser resueltos como problemas de maximización usando la transformación: MINIMIZAR Z = MAXIMIZAR (-Z )   Si el problema tiene solución óptima finita, se verifica que: MINIMO Z = - [MAXIMO (-Z)]   Sin embargo, el método simplex puede ser aplicado directamente para resolver problemas de minimización, haciendo un cambio solamente en los pasos 3 y 4, permaneciendo los otros pasos sin ninguna modificación. Pasos 3 y 4 para problemas de minimización: Paso 3.- Si todo Z j -C j ≤ 0, entonces la solución básica actual es OPTIMA FACTIBLE y el procedimiento termina. En caso contrario se continúa con el paso 4 Paso 4.- Se selecciona la VARIABLE QUE ENTRA A LA BASE de acuerdo a la siguiente CONDICIÓN DE OPTIMALIDAD: La variable que entra a la base es aquella variable no básica que corresponde al máximo de Z j -C j . En caso de empate, éste se rompe arbitrariamente. Sea X k la variable seleccionada.

19. EJEMPLO El señor Felix Santa María desea preparar una dieta con dos alimentos A y B, estos alimentos consisten exclusivamente de dos nutrientes (I, II). El alimento A cuesta $ 3 el kilogramo y contiene 90% del nutriente I. El alimento B cuesta $ 6 el kilogramo y contiene 60% del nutriente I. ¿Qué cantidad de cada uno de estos alimentos proporciona al menos 4 kilogramos del nutriente I y 2 kilogramos del nutriente II a un costo mínimo?. MODELO MATEMÁTICO. x 1 : Kg. de alimento A x 2 : Kg. de alimento B MINIMIZAR Z = 3x 1 + 6x 2 sujeto a 0.9x 1 + 0.6x 2 ≥ 4 0.1x 1 + 0.4x 2 ≥ 2 x j ≥ 0, j =1, 2

20. PASO 1.- Forma estándar del modelo, incluye matriz base MINIMIZAR Z = 3x 1 + 6x 2 + 0s 1 + 0s 2 + MA 1 + MA 2 sujeto a 0.9x 1 + 0.6x 2 - s 1 + A 1 = 4 0.1x 1 + 0.4x 2 - s 2 + A 2 = 2 x j ≥ 0, j = 1, 2 s i ≥ 0, i = 1, 2 A i ≥ 0, i = 1, 2   Las variables s 1 y s 2 son variables superfluas. Las variables A 1 y A 2 son variables artificiales

21. Paso 2.- Tabla inicial del método simple   CBi Cj → 3 6 M M   bi XBi X1 X2 S1 S2 A1 A2 M M A1 A2 0.9 0.1 0.6 0.4 -1 -1 1 1 4 2   Zj M M -M -M M M 6M   Zj-Cj M-3 M-6 -M -M  

22. Solución básica inicial Variables básicas : A 1 = 4, A 2 = 2 Variables no básicas : x 1 = x 2 = s 1 = s 2 = 0 Valor función objetivo : Z = 6M   Paso 3.- No todo Z j - C j ≤ 0, la solución básica actual no es óptima. Se continúa con el paso 4. Paso 4.- Se selecciona la variable no básica x 1 para que entre a la base, por tener el max ( Z j - C j ). Paso 5.- Se selecciona la variable básica A 1 para que salga de la base, por tener el mínimo cociente de los b i entre los respectivos coeficientes a i1 (es decir los coeficientes tecnológicos de la variable que entra)   min(4/0.9, 2/0.1) = 4/0.9 = b 1 /a 11   El elemento pivote es a 11 = 0.9

23. Paso 6.- Se ejecutan operaciones matriciales elementales para convertir el pivote en 1 y los restantes elementos de su columna en 0. Se tiene la nueva tabla simplex.   CBi Cj → 3 6 M M   bi XBi X1 X2 S1 S2 A1 A2 3 M X1 A2 1 2/3 1/3 -10/9 1/9 -1 10/9 -1/9 1 40/9 14/9   Zj 3 (M+6)/3 (M-30)/9 -M (-M+30)/9 M (14M+120)/9   Zj-Cj (M-12)/3 (M-30)/9 -M (-10M+30)/9  

24. Solución básica actual Variables básicas : x 1 = 40/9, A 2 = 14/9 Variables no básicas : x 2 = s 1 = s 2 = A 1 = 0 Valor función objetivo : (14M + 120)/9 Se regresa al paso 3. Paso 3.- No todo Z j - C j ≤ 0. La solución actual no es óptima. Paso 4.- Variable que entra es x 2 Paso 5.- Variable que sale es A 2 Elemento pivote es a 22 = 1/3

25. Paso 6.- Nueva tabla simplex.   CBi Cj → 3 6 M M   bi XBi X1 X2 S1 S2 A1 A2 3 6 X1 X2 1 1 -12/9 1/3 2 -3 12/9 -1/3 -2 3 4/3 14/3   Zj 3 6 -2 -12 2 12 32   Zj-Cj -2 -12 2-M 12-M  

26. Solución básica actual Variables básicas : x 1 = 4/3, x 2 = 14/3 Variables no básicas : s 1 = s 2 = A 1 = A 2 = 0 Valor función objetivo : Z = 32 Se regresa al paso 3 Paso 3.- Todo Z j - C j ≤ 0, la solución básica es ÓPTIMA FACTIBLE y el procedimiento termina. El señor Félix Santa María debe utilizar 4/3 kilogramos del alimento A (x 1 ) y 14/3 kilogramos del alimento B (x 2 ) para preparar la dieta que cumpla con los requerimientos mínimos de los nutrientes I y II, el costo mínimo de esta dieta (Z) es $ 32

27. SOLUCIÓN CON SOFTWARE POMforwin

28. MÉTODO DE DOS FASES   FASE I Se expresa la función objetivo en función de las variables artificiales, se pone el modelo en forma estándar que incluya una matriz base y se minimiza independientemente si el problema es de minimización o maximización. Si la función objetivo en la solución óptima es igual a cero quiere decir que el problema tiene solución finita y se continua con la fase II.   FASE II En la tabla óptima del método simplex de la fase I se eliminan las columnas de las variables artificiales, se pone los coeficientes correspondientes a las variables del problema y se continua con el procedimiento del método simplex hasta determinar la solución óptima. EJEMPLO. Min Z = -2x 1 + 2x 2 Sujeto a. 2x 1 + 4x 2 ≥ 10 4x 1 + 2x 2 ≤ 8 2x 1 + 8x 2 ≥ 8 x j ≥ 0, para toda j SOLUCIÓN FASE I   Min A = A 1 + A 3 Sujeto a. 2x 1 + 4x 2 – s 1 + 0s 3 + A 1 + 0s 2 + 0A 3 = 10 4x 1 + 2x 2 + 0s 1 + 0s 3 + 0A 1 + s 2 + 0A 3 = 8 2x 1 + 8x 2 + 0s 1 - s 3 + 0A 1 + 0s 2 + A 3 = 8 x j ≥ 0, para toda j s i ≥ 0, para toda i A i ≥ 0, para toda i

29.   CBi   XBi 1 1   bi X1 X2 S1 S3 A1 S2 A3 1 1 A1 S2 A3 2 4 2 4 2 8 -1 -1 1 1 1 10 8 8 Zj 4 12 -1 -1 1 1 18 Zj - Cj 4 12 -1 -1   CBi   XBi 1 1   bi X1 X2 S1 S3 A1 S2 A3 1 A1 S2 X2 1 7/2 1/4 1 -1 1/2 1/4 -1/8 1 1 -1/2 -1/4 1/8 6 6 1 Zj 1 -1 1/2 1 -1/2 6 Zj - Cj 1 -1 1/2 -3/2   CBi   XBi 1 1   bi X1 X2 S1 S3 A1 S2 A3 1 A1 X1 X2 1 1 -1 3/7 1/14 - 1/7 1 -2/7 2/7 -1/14 -3/7 -1/14 1/7 30/7 12/7 4/7 Zj -1 3/7 1 -2/7 -3/7 30/7 Zj - Cj -1 3/7 -2/7 - 10/7 SOLUCIÓN ÓPTIMA   X1 = 1 X2 = 2 S3 = 10 Las demás variables son no básicas e iguales a 0 Z = 0   CBi   XBi 1 1   bi X1 X2 S1 S3 A1 S2 A3 S3 X1 X2 1 1 -7/3 1/6 -1/3 1 7/3 -1/6 1/3 -2/3 1/3 -1/6 -1 10 1 2 Zj Zj - Cj -1 -1

30. FASE II Se eliminan las columnas de las variables artificiales   CBi   XBi -2 2   bi X1 X2 S1 S3 S2 -2 2 S3 X1 X2 1 1 -7/3 1/6 -1/3 1 -2/3 1/3 -1/6 10 1 2 Zj -2 2 -1 -1 2 Zj - Cj -1 -1 SOLUCIÓN ÓPTIMA X1 = 1 X2 = 2 S3 = 10 S1 = S2 = A1 = A3 = 0 Z = 2