Actividad 2. Solucin a problemas por los Mtodos: grfico y simplex

Universidad Abierta y a Distancia de Mxico15Actividad 2. Solucin a problemas por los Mtodos: grfico y simplexAsignatura: Investigacin de Operaciones Quinto Semestre Docente: Rafael Alvarado CoronoRoberto Nieto Morales Matricula: al13502595

Instrucciones: I. Lee cada ejercicio escrito al final de la actividad y resuelva segn el mtodo indicado. Para los ejercicios a resolver por el Mtodo grfico: 1. Grafica la regin factible y marca con un crculo las soluciones factibles en los vrtices (FEV). 2. En cada solucin FEV identifica el par de ecuaciones de fronteras de restriccin que satisface. 3. En cada solucin FEV, utiliza este par de ecuaciones de fronteras de restriccin para obtener la solucin algebraica de los valores de X1 y X2 en vrtice. 4. En cada solucin FEV, identifica sus soluciones FEV adyacentes. 5. En cada par de soluciones FEV adyacentes, identifica, en su ecuacin, la frontera de restriccin comn. 6. Escribe la solucin del ejercicio.

Para los ejercicios a resolver por el Mtodo simplex: 1.- Convierte el modelo de la forma original a la forma estndar. 2.- Crea la tabla simplex y compltala con la forma estndar. 3.- Define la columna pivote o columna de entrada. 4.- Determina la variable de salida. 5.- Completa la tabla simplex con la iteracin uno. 6.- Si no hay solucin, realiza la siguiente iteracin hasta encontrar la solucin factible.

Ejercicio 1. Resolver por el metodo grafico: Supon que X1 son muebles de madera y X2 son muebles de metal que se van a producir. Sea el modo lineal Z = 5X1 + 4X2 Sujeto a: 3X1 + 4X2 10 -4X1 + 3X2 6 3X1 + 1X2 7 Y X1, X2 0

Solucin: Como primer paso, es necesario determinar el conjunto de soluciones de cada una de las restricciones. Para obtener el conjunto de soluciones de una desigualdad en el plano cartesiano [R2], primero debemos considerarlo como una ecuacin con objeto de graficar la recta que limitara al semiplano correspondiente a la solucin de la desigualdad. Para la primera restriccin 3X1 + 4X2 10 Al quitar la desigualdad 3X1 =10 entonces X1= = 3.3 Al quitar la desigualdad 4X2 =10 entonces X2= = 2.5Para saber donde se ubica la regin factible debe tomarse un valor antes y uno despus del de X1, si es que existe, de no ser as, podemos tomar X2; es decir, si en este caso el valor de X1 es de 3.3, se toma el valor de 2.3 y 4.3 respectivamente, y se sustituyen en la restriccin 1. Restriccin 1 3X1 + 4X2 10Si X1 toma el valor de 2.3, debemos cuestionarnos lo siguiente:2.3 por el valor de X1 que es 3, es menor que 10? Al ser afirmativo, la regin factible de esta restriccin se encuentra hacia la izquierda

Para la segunda restriccin -4X1 + 3X2 6 Al quitar la desigualdad -4X1 = 6 entonces X1= = -1.5 Al quitar la desigualdad 3X2 =6 entonces X2= = 2Para saber donde se ubica la regin factible debe tomarse un valor antes y uno despus del de X1, si es que existe, de no ser as, podemos tomar X2; es decir, si en este caso el valor de X1 es de -1.5, se toma el valor de -2.5 y 0 respectivamente, y se sustituyen en la restriccin 2. Restriccin 2 -4X1 + 3X2 6Si X1 toma el valor de -2.5, debemos cuestionarnos lo siguiente:-2.5 por el valor de X1 que es -4, es menor que 6? Al ser negativo, la regin factible de esta restriccin se encuentra hacia la derecha.

Para la tercera restriccin 3X1 + 1X2 7 Al quitar la desigualdad 3X1 = 7 entonces X1= = 2.3 Al quitar la desigualdad 1X2 =7 entonces 1X2= = 7 Para saber donde se ubica la regin factible debe tomarse un valor antes y uno despus del de X1, si es que existe, de no ser as, podemos tomar X2; es decir, si en este caso el valor de X1 es de 2.3, se toma el valor de 1.3 y 3.3 respectivamente, y se sustituyen en la restriccin 3. Restriccin 3 3X1 + 1X2 7 Si X1 toma el valor de 2.3, de vemos cuestionarnos lo siguiente:1.3 por el valor de X1 que es 3, es menor que 7? Al ser afirmativo, la regin factible de esta restriccin se encuentra hacia la izquierda El siguiente paso es unir las tres graficas en una sola e identificar la regin factible que es la interseccin entre las tres reas.Para determinar en qu punto factible se alcanza el mejor valor de la funcin objetivo, nos apoyaremos en las curvas de nivel o frontera de la regin factible optima, para lo cual ser necesario evaluar los puntos de interseccin existentes dentro del cuadrante uno como se observa en la siguiente grafica.Al considerar el rea de solucin factible y sustituir los puntos de interseccin se generan los siguientes valores

Regin factible

Por lo tanto podemos deducir que Z alcanza un valor mximo en C, es decir cuando X1 = 2 X2 = 1 Ejercicio 2: Resuelve por el mtodo grafico. Sea el modelo lineal Maximizar Z = X1 + 2X2 Sujeto a: X1 + 2 X2 2 X1 + X2 3 Y X1, X2 0 Solucion:Graficando las siguientes desigualdades considerando X1 = XObtenemos las siguientes graficas

Al considerar el rea de solucin factible y sustituir los puntos de interseccin se generan los siguientes valores Z = X + 2Y C: Z = (0) +2 (2)=4 F: Z = (1) +2 (2)=5 I: Z = (2) +2 (1)=4 K: Z = (2) +2 (0)=2Por lo tanto podemos deducir que Z alcanza un valor mximo en I, es decir cuando X1 = 2 y X2 = 1 Ejercicio No 3. Formato original Maximizar Z = -X1 + X2 + X3

Sujeto a: X1 + 2X2 - X3 20 -2X1 + 4X2 + 2X3 60 2X1 + 3X2 + X3 50

y X1, X2, X3 0Considerando las desigualdades anteriores transformndolas a igualdades agregando variables de holgura, en virtud de que se tienen restricciones de tipo

Formato estndar Maximizar Z = - - X1 + 2X2 - X3 +20 Sujeto a: + + 60 + + 50 Y , , 0Primer paso.Tabla mtodo Simplex.Solucin

12-110020

-24201060

23100150

Z1-1-10000

Segundo paso encontrar el rengln de entrada y de salida Rengln de entrada

Solucin

12-110020 -10

-242010Rengln de salida60 30

23100150 50

Z1-1-1000

Pivote

Segundo paso

Solucin

-242010Rengln de salida60 30

= -= 2= 1 = 0 = = 0 = 30

Solucin Solucin

210030

Tercer pasoSolucin

12-110020

-1210030

A continuacin debe multiplicarse el rengln por el inverso de cada valor que se transformara en cero y sumarlo al rengln que se convertir.Solucin

12-110020

-2 10030

1*-1=-1+1=01*2=2+2=41*1=1+ [-1]=01*0=0+1=11* = +0 = 1*0=0+0=01*30= 30 +20=50

Solucin Solucin

0401050

-2 10030

Una vez que hemos resuelto el rengln , continuamos con el rengln . Ahora debemos multiplicar el rengln por -1 ya que es el inverso de 1.Solucin

23100150

-1210030

-1*-1 = 1+2=3-1*2=-2+3=1-1*1=-1+ [1]=0-1*0=0*0=0-1* = - + 0= - -1*0=0+1=1-1*30=-30 +50=20

Solucin

0401050

-2 10030

3100- 120

Ntese que la columna de entrada por el momento esta correcta, ahora solo nos falta definir a Z que se llevara a cabo multiplicando el inverso de -1 por sumando el resultado a la fila del objetivo Z.

Solucin

Z1-1-10000

0401050

-2 10030

3100- 120

1*-1=-1+1= 01*2=2+ [-1]=11*1=1+ [-1]=01*0=0+0=01* = +0= 1*0=0+0=01*30=30+0=30

Solucin

Z0100030

0401050

-2 10030

3100- 120

Notemos que la misin ha sido concluida.

Ejercicio No 4 Resolver por el mtodo simplex. Sea el modelo lineal: Formato original

Maximizar Z = 2X1 - X2 + X3

Sujeto a: 3X1 + X2 + X3 6 X1 - X2 + 2X3 1 X1 + X2 - X3 2 Y X1, X2, X3 0 Formato estndar Maximizar Z = -2X1 + X2 - X3

Sujeto a: 3X1 + X2 + X3 + = 6 X1 - X2 + 2X3 + =1 X1 + X2 - X3 + = 2 Y X1, X2, X3 0

Tabla modelo simplex

Z R

Z1-21 -10 000

031 11 0 062

0 1-1201 011

0 11-100122

Solucin

1-1 20 1 0 1

El rengln de salida se divide entre el pivote = 1 = -1 = 2 = 0 = 1 = 0 = 0 = 1

Queda de la siguiente manera: ntese que cambi al rengln Solucin

31110 06

1-1 20 1 0 1

Posteriormente se multiplica el inverso de 3, siendo este -3 por el rengln se suma con los valores de -3 * 1= -3 +3= 0-3 * -1= 3*1 = 4-3* 2= -6 +1= -5-3*0=0 +1= 1-3*1=-3 +0= -3-3 * 0=0 +0= 0

Y cambian los valores en , posteriormente continuamos con ser multiplicar -1 que es el inverso de 1 para obtener el resultado del rengln

Solucin

04-51-3 06

1-1 20 1 0 1

1 1 -10 0 12

Continuamos con -1* 1=-1 + 1= 0-1* -1 = 1 + 1 = 2-1*2= -2 + [-1]= -3-1*0 = 0+0= 0-1*1=-1+0= -1-1*0= 0+1= 1-1*1=-1+2=1Solucin

0-2301 -1-1

1-1 20 0 1 2

0 2 -30 -1 1 1

Ahora continuamos con ZSolucin

Z-21-100 00

1-1 20 0 1 2

-3*1 + [-2]=-5-3*-1+ [-1]=4-3*2+ [-1]=-7-3*0+0=0-3*0+0=0-3*1+0=-3-3*2+0= -6Se puede apreciar que siguen estando valores negativos en Z as que comencemos de nueva cuenta.Ntese el pivote y la columna de entrada y el rengln de salida

Solucin

Z-54-700-3-6

0-2301 -1-1

1-1 20 0 1 2

0 2 -30 -1 1 1

Dividimos el rengln de salida y el pivote para obtener uno en el mismo pivote= - = - = 1= 0= 0= = 1Solucin

Z-54-700-3-6

0-2301 -1-1

- 10 0 1

0 2 -30 -1 1 1

Ahora convertiremos al rengln multiplicando el valor inverso de 3, que viene siendo -3Solucin

0-2301 -1-1

- 10 0 1

-3* = - -3 * - = -3*1=-3+3= 0-3*0=0+0=0-3*0=0+1=1-3* = -3*1=-3+ [-1]=-4Entonces el rengln esta optimo con el valor cero en la columna de entrada.Solucin

- 001 -4

- 10 0 1

Solucin

02-30-1 11

- 10 0 1

De la misma forma obtendremos

3* = +0= 3*- = - +2=3*1=3+ [-3]=03*0=0+0=03*0=0+ [-1]=-13* = +1= 3*1=3+1=4Solucin

-00-1 4

- 10 0 1

Solucin

- 001 -4

- 10 0 1

- 00 -1 4

De nueva cuanta vamos con Z para tratar de encontrar puros valores positivosSolucin

Z-54-700 -3-6

- 10 0 1

-3*= + -5=- -3* - = +4= -3*1=-3+ [-7]=-10-3*0= 0+0=0-3*0+0= 0-3*+ [-3]=-3*1 + [-6]=-9

Solucin

- 001 -4

- 10 0 1

- 00 -1 4

Z--1000-9

/ = 1- / = -11/ = 20/ = 00/ = 0 / = 11/ = 2

Solucin

- 001 -4

1 -1 20 0 1 2

- 00 -1 4

Z--1000-9

Obtenemos los valores de Solucin

- 001 -4

1 -1 20 0 1 2

* 1 + - = 0*-1+ = 0 * 2+0= 3 * 0+0 =0 * 0+1= 1 * 1 + = 3 * 2 + [-4]= -1Solucin

00301 3-1

1 -1 20 0 1 2

-00-1 4

- * 1 + = 0- * -1 + [- ] =-2- * 2 +0= -3- *0 +0= 0- *0 + [-1]= -1- * 1+ = 1- * 2 +4= 1

Z--1000-9

1 -1 20 0 1 2

* 1 +- = -2 * -1 + = 4 * 2 + -10= -7 * 0 + 0 = 0 * 0 + 0 = 0 * 1 + = 6 * 2 + [-9]=

Solucin

Z-24-700 6

00301 3-1

1 -1 20 0 1 2

0-2-30-1 11

= = = 1 = 0 = 0= = 1

Solucin

Z-24-700 6

00301 3-1

10 0 1

0-2-30-1 11

Nota: Al estudiar el procedimiento para la solucin de este problema en el libro de Rodolfo Valentn Muos Castorena, Mara Beranrdett Ochoa Hernndez y Manuel Morales Garca, (por cierto aprend muy bien este procedimiento) en el mtodo simplex, no me dieron resultados satisfactorios y gaste mucho de mi tiempo en tratar de dar solucin a este problema.Tuve que orientarme con otro material y me dieron resultados satisfactorios con unos simples pasos, aqu est la solucin.

Maximizar Z = 2X1 - X2 + X3

Sujeto a: 3X1 + X2 + X3 6 X1 - X2 + 2X3 1 X1 + X2 - X3 2 Y X1, X2, X3 0 Formato estndar Maximizar Z = -2X1 + X2 - X3

Sujeto a: 3X1 + X2 + X3 + = 6 X1 - X2 + 2X3 + =1 X1 + X2 - X3 + = 2 Y X1, X2, X3 0

COLUMNA DE ENTRADAPIVOTERenglnSolucinoperaciones

Z -21-10000+ 2

-3111006-

1120101+ 1

11-10012- 2

RENGLON SALIENTE

Realizaremos las operaciones que tenemos al lado derecho de nuestra tabla:

-21-10000

+2+2+2+2+2+2+2

1120101

Z0332002

-3111116

+3+3+3+3+3+3+3

1120101

0471309

1120101

-1-1-1-1-1-1-1

1120101

0000000

z0332002

0471309

0000000

00-30001

1120101

Solucin al problema:Maximizar Z = 2X1 - X2 + X3 Z = 2; 2= 2 (1)- 1+1= 2 = 1; Youtube.com/watch?v=s2plb4uAub4

Pasos para resolver Prog. Lin. Por el mtodo simplex