trabajo de io (1)

CASOS ESPECIALES DEL MÉTODO SIMPLEX

AGUILAR PRADA LISETH ALEJANDRA

SOLERA ROJAS CLAUDIA VERUSHKA

NELSON ZUÑIGA PORTILLO

Universidad del Atlántico

Facultad de Ingeniería

Ingenieria Química

3 de Noviembre de 2015

II

RESUMEN

En el presente trabajo se tiene como finalidad analizar cada uno de los casos especiales del método simplex, haciéndolos claros a través de ejemplos donde se pueda visualizar mejor el comportamiento presente.

Los casos especiales del método simplex son:

Degeneración Óptimos alternativos Solución no acotada Solución no factible

III

CASOS ESPECIALES DEL MÉTODO SIMPLEX

INTRODUCCIÓN

El método simplex es un procedimiento iterativo que permite mejorar la solución de la función objetivo en cada paso. El proceso concluye cuando no es posible continuar mejorado dicho valor, es decir, se ha alcanzado la solución óptima ya sea para minimización o maximización. La razón matemática de esta mejora radica en que el método consiste en caminar del vértice de un poliedro1 un vértice vecino de manera que aumente o disminuya (según el contexto de la función objetivo) dado que el número de vértices que representa un poliedro solución es finito siempre se hallara la solución.

1. DEGENERACIÓN

En este primer caso, cuando se empieza la primera iteración con la tablas características del método simplex, se puede presentar un empate en la parte del valor solución, es decir, va a haber una redundancia entonces se deberá escoger la fila pivote, que sería la variable de salida. 2Cuando esto sucede al menos una variable básica será cero en la siguiente iteración y se dice que la nueva solución esta degenerada; también puede hacer que las iteraciones ocurran de forma indefinida y que el algoritmo nunca se termine, a menos que se vaya de nuevo a la iteración donde se hizo la escogencia del valor repetido y se empiece de nuevo hasta cuando se encuentre una solución óptima.

EJEMPLO:

Función objetivo:

ZMAX=3 X1+9 X2

Restricciones:

X1+4 X2≤8

X1+2 X2≤4

1 Salazar,Bryan.Metodo Simplex.{En línea}.{1 Noviembre de 2015} disponible en (http://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/m%C3%A9todo-simplex/).2 Taha,Hamdy.Investigación de operaciones. Novena edición. Ciudad de México: Pearson Education,Inc.2012.824p

IV

X1 , X2≥0

Reformulando,

Función objetivo:

ZMAX=3 X1+9 X2+∅ S1+∅ S2

Restricciones:X1+4 X2+S1=8

X1+2 X2+S2=4

X1 , X2 , S1 , S2≥0

Se procede a resolver este primer caso con las iteraciones del método simplex

C j 3 9 0 0 VALORSOLUCIÓN

C j X1 X2 S1 S2

0 S1 1 4 1 0 8 84=2

0 S2 1 2 0 1 4 42=2

Z j 0 0 0 0 0Cj-Zj 3 9 0 0

Tabla 1. Coeficientes de las variables de la función objetivo y restricciones

La columna pivote escogida fue la de mayor valor por que es un caso de maximización y se procedió a dividir el valor solución entre los valores de la columna para poder decidir la fila pivote pero se ve que se repiten los valores por

V

lo que se llega a tomar la decisión de tomar la primera fila para seguir los la siguiente iteración.

Para la siguiente tabla se tomo el valor de la intercepción para dividirlo entre cada uno de los valores de la fila pivote y poder darle el valor a la variable de entrada de este caso que es X2 y se obtuvieron los resultados mostrados en la tabla 2. También se hicieron los siguientes cálculos:

Para X2:

14=14

44=1

14=14

04=0

84=2

Para S2:

1−(2× 14 )=122− (2×1 )=0

0−(2× 14 )=−12

1− (2×0 )=1

4− (2×2 )=0

La tabla quedaría de la siguiente manera:

VI


C j X1 X2 S1 S2

0 S1 14

1 14

0 2 2/(1 /4)=8

0 S212

0 −12

1 0 0 /(12)=0

Z j94

94

94

0 18

Cj-Zj 34

0 −94

0

Tabla 2. Coeficientes de las variables de la función objetivo y restricciones modificadas.

Aquí la columna pivote fue elegida por el numero positivo el cual no cumplía con la condición de maximización con la cual se está trabajando y la fila pivote se escogió con el número menor después de haber dividido con los respectivos números de la columna pivote, como aun no se ha encontrado la solución optima se procede con la tercera iteración.

En este caso la variable de entrada es X1 y la de salida es S2, es decir la columna y fila pivote respectivamente, los cálculos son:

Para X1 :

1212

=1

VII

012

=0

−1212

=−1

012

=0

Para X2:

14−( 14 ×1)=0

1−( 14 ×0)=114−( 14 × (−1 ))=120−( 14 ×2)=−1

2

2−( 14 ×0)=2

Estos valores en la tabla 3 se ven de la siguiente manera:

C j 3 9 0 0 VALORSOLUCIÓNC j X1 X2 S1 S2

9 X2 0 1 12

−12

2 2/(1 /4)=8

3 X11 0 −1 2 0 0 /(1

2)=0

Z j3 9 3/2 3/2 18

VIII

Cj-Zj 0 0 −3/2 −3/2

Tabla 3. Tabla de la solución optima.

Esta sería la tabla que concluye el ejercicio lo que indica que se tomo una buena decisión al empezar el ejercicio en cuanto a sacar a S1 y dejar entrar a X2

2. ÓPTIMOS ALTERNATIVOS

Este segundo caso se da cuando la función objetivo es paralela a una restricción del problema, es decir gráficamente tiene dos o más soluciones optimas.

Una de las características es que la función objetivo asume el valor de una solución básica factible óptima en donde al menos una de las variables no-básicas se convierte en básica, teniendo valor de cero en la solución final de la ecuación.

Esto quiere decir que si al realizar la primera iteración no queda ninguna variable no básica negativa se puede tomar como solución factible optima el valor que hay en Zj tomando el valor de la variable que salió para darle la solución y la variable no básica convertirla en básica y darle valor de cero en la solución. Como se puede observar en la tabla que es la solución numero uno.

Pero se puede encontrar otra solución repitiendo el procedimiento que dará la misma solución óptima para Zj y también se encontraran los valores de las variables básicas que serán diferentes en esta iteración, así se tienen dos soluciones pero depende de la exigencia del usuario la solución que se elija.

EJEMPLO:

Función objetivo:

ZMAX=X1+12X2

Restricciones:

2 X1+X2≤4

X1+2 X2≤3

X1 , X2≥0

Reformulando,

IX

Función objetivo:

ZMAX=X1+12X2+∅ S1+∅ S2

Restricciones:2 X1+X2+S1=4

X1+2 X2+S2=3

X1 , X2 , S1 , S2≥0

C j 3 9 0 0 VALORSOLUCIÓNC j X1 X2 S1 S2

0 S1 2 1 1 0 4 4 /2=2

0 S21 2 0 1 3 3/1=3

Z j0 0 0 0 0Cj-Zj 1 1/2 0 0

Tabla 4. Coeficientes de las variables de la función objetivo y restricciones

Para la columna pivote se toma el mayor valor positivo y para la fila pivote se dividen los valores solución entre los valores solución. Ahora se proceden a hacer los cálculos:

Para X1:

22=1

12=1/2

12=1/2

02=0

X

42=2

Para S2:

1− (1×1 )=0

2−(1× 12 )=320−(1× 12 )=−1

2

1− (1×0 )=1

3−(1×2 )=1


Tabla 5. Solución óptima 1.

En esta tabla ya se ve una solución óptima sin embargo si se toma la variable no básica para este caso que es X2se puede llegar a otra solución que se muestra en la siguiente tabla utilizando el mismo procedimiento mencionado anteriormente.

Para X2:


C j X1 X2 S1 S2

0 X1 1 1/2 1/2 0 2 2/(1 /2)=4 /3

0 S21 3/2 −1/2 1 1 1/(3 /2)=2/3

Z j0 0 1/2 0 2Cj-Zj 0 0 −1/2 0

XI

032

=0

3232

=1

−1232

=−13

132

=2/3

132

=2/3

Para X1:

1−(( 12 )×0)=112−( 12×1)=0

12−( 12∗(−13 ))=230−( 12× 23 )=−67

200

2−( 12× 23 )=333200

XII


Tabla 6. Solución Óptima 2.

3. SOLUCIÓN NO ACOTADA

Para saber si una solución es no acotada, se debe tener en cuenta que si en cualquier iteración los coeficientes de una variable en las restricciones de una variable no son positivos, entonces el espacio de soluciones no está acotado en esa dirección. Además, si el coeficiente de la función objetivo de esa variable es negativo en el caso de la maximización o positivo en el caso de la minimización, entonces el valor de la función objetivo tampoco está acotado3.

Este caso se puede dar debido a que está mal construido, ya sea que no se determinaron correctamente las variables o se omitieron algunas restricciones. Por ende, se puede ver que se produce ganancia infinita, lo cual es algo irracional.

EJEMPLO:

Función objetivo:

ZMAX=36 X1+30 X2−3 X3−4 X4

Restricciones:

X1+X 2−X3≤5

6 X1+5 X2−X4≤10

3 Anonimo. Casos especiales del método simplex.{En línea}.Disponible en: http://www.sites.upiicsa.ipn.mx/polilibros/portal/polilibros/p_terminados/InvOperChave/Documentos/Unidad4/UNIDAD42.htm

C j 1 1/2 0 0 VALORSOLUCIÓNC j X1 X2 S1 S2

0 X1 1 0 1/3 −67 /200 333200

½ X2 0 1 1/3 2/3 2/3

Z j0 1/2 33/200 0 2Cj-Zj 0 0 −33/200 0

XIII

X1 , X2 , X3 , X 4≥0

Reformulando,

Función objetivo:

ZMAX=−36 X1−30 X2+3 X3+4 X4+∅ S1+∅ S2

Restricciones:

X1+X 2−X3+S1=5

6 X1+5 X2−X4+S2=10

X1 , X2 , X3 , X 4 , S1 , S2≥0

Para ello, se hace la primera tabla del método Simplex (Tabla 7), donde se colocan los distintos coeficientes de las restricciones y función objetivo.

C j -36 -30 3 4 0 0 VALORSOLUCIÓN

C j X1 X2 X3 X 4 S1 S2

0 S1 1 1 -1 0 1 0 5 51=5

0 S2 6 5 0 -1 0 1 10 106

=1,7

Z j 0 0 0 0 0 0 0

C j−Z j -36 -30 3 4 0 0 0

Tabla 7. Coeficientes de las variables de la función objetivo y restricciones.

XIV

Para escoger la columna pivote, se elige el valor negativo más alejado del cero, el cual en este ejemplo, sería el valor de -36.

Luego, se escoge la fila que corresponde al menor valor del cociente del valor solución de cada fila de restricción con el valor que está encerrado en la columna pivote, así como se muestra en la Tabla 7.

Ahora, se realiza la segunda tabla del método Simplex, organizando los distintos valores (Tabla 8).


C j X1 X2 X3 X 4 S1 S2

0 S1 0 16

-1 16

1 −16

103

10316

=20

-36 X1 1 56

0 −16

0 16

106

106

−16

=−10

Z j -36 -30 0 6 0 -6 -60

C j−Z j 0 0 3 -2 0 6 60

XV


Para hallar los coeficientes de la tabla anterior, se realizó lo siguiente con los valores de la tabla 7:

Para S2:

66=1

56=56

06=0

−16

06=0

16=16

106

=106

Para S1:

1− (1×1 )=0

1−(1× 56 )=16−1− (1×0 )=−1

0−(1×−16 )=16

1− (1×0 )=1

XVI

0−(1× 16 )=−16

5−(1× 106 )=103Así como en la tabla anterior, se escogió la columna pivote y la fila. Y se procede a hacer las modificaciones respectivas.

Luego, se hace la nueva tabla del método Simplex (Tabla 9):


C j X1 X2 X3 X 4 S1 S2

4 X 4 0 1 -6 1 6 −1 20 10316

=20

-36 X1 1 1 -1 0 1 0 5 106

−16

=−10

Z j 0 2 -9 0 12 4 100


Donde los valores de la anterior tabla se calcularon así:

Para X 4:

016

=0

XVII

1616

=1

−116

=−6

1616

=1

116

=6

−1616

=−1

10316

=20

Para X1:

1−(−16 ×0)=0

1−(−16 ×1)=16−1−(−16 ×(−6))=−1

0−(−16 ×1)=16

XVIII

1−(−16 ×6)=1

0−(−16 ×−1)=−16

106

−(−16 ×20)=5Al tener los valores de la tabla 9, se puede ver que en la columna pivote se encuentran valores negativos, lo cual tiene una SOLUCIÓN NO ACOTADA.

4. SOLUCIÓN NO FACTIBLE:

El modelo no tiene solución factible cuando no se puede satisfacer las restricciones al mismo tiempo.

Al tener una solución no factible apunta a la posibilidad de que el modelo no se haya formulado correctamente haciendo que las restricciones estén en conflicto. También es posible que las restricciones no estén destinadas a cumplirse en forma simultánea.

EJEMPLO

Función objetivo:

ZMAX=3 X1+2 X2

Restricciones:

2 X1+X2≤2

3 X1+4 X2≥12

X1 , X2≥0

Reformulando,

Función objetivo:

XIX

ZMAX=3 X1+2 X2+∅ S1−∅ S2+M A1

Restricciones:

2 X1+X2+S1=2

3 X1+4 X2−S2+A1=12

X1 , X2 , S1 , S2 , A1≥0

Para ello, se hace la primera tabla del método Simplex (Tabla 10), donde se colocan los distintos coeficientes de las restricciones y función objetivo.

C j 3 2 0 0 M VALORSOLUCIÓN

C j X1 X2 S1 S2 A1

0 S1 2 1 1 0 0 2 2/1=2

M A1 3 4 0 -1 1 12 12/4=3

Z j 3M 4M 0 -M M 12M

C j−Z j 3-3M 2-4M 0 m 0 M=50

C j−Z j -147 -198 0 50 0 -600

Tabla 10. Coeficientes de las variables de la función objetivo y restricciones.

Para saber el valor de C j−Z j, se hace que:

XX

3−3M=0→M=1

2−4M=0→M=1/2

Por lo que el valor que se puede tomar de M sería de 50.

Para escoger la columna pivote, se elige el valor negativo más alejado del cero, el cual en este ejemplo, sería el valor de -198.

Luego, se escoge la fila que corresponde al menor valor del cociente del valor solución de cada fila de restricción con el valor que está encerrado en la columna pivote, así como se muestra en la Tabla 10.

Ahora, se realiza la segunda tabla del método Simplex, organizando los distintos valores (Tabla 11).

C j 3 2 0 0 M VALORSOLUCIÓNC j X1 X2 S1 S2 A1

2 X2 2 1 1 0 0 2

M A1 -5 0 -4 -1 1 4

Z j 4-5M 2 2-4M -M M 4+4M

C j−Z j 5M-1 0 4M-2 M 0

C j−Z j 249 0 198 50 0


Para hallar los coeficientes de la tabla anterior, se realizó lo siguiente con los valores de la tabla 10:

Para X2:

21=2

11=1

11=1

XXI

01=0

01=0

21=2

Para A1:

3−(4×2 )=−5

4− (4×1 )=0

0−(4×1 )=−4

−1− (4×0 )=−1

1− (4×0 )=1

12−(4×2 )=4

Así como en la tabla anterior, se escogió la columna pivote y la fila. Y se procede a hacer las modificaciones respectivas.

Al tener los valores de la tabla 11, se puede ver que se tiene una SOLUCIÓN NO FACTIBLE ya que las restricciones no se dan simultáneamente.

BIBLIOGRAFÍA

1. Salazar,Bryan.Metodo Simplex.{En línea}.{1 Noviembre de 2015} disponible en (http://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/m%C3%A9todo-simplex/).

2.Taha,Hamdy.Investigación de operaciones. Novena edición. Ciudad de México: Pearson Education,Inc.2012.824p

XXII

3. Anonimo. Casos especiales del método simplex.{En línea}.Disponible en: http://www.sites.upiicsa.ipn.mx/polilibros/portal/polilibros/p_terminados/InvOperChave/Documentos/Unidad4/UNIDAD42.htm

trabajo de io (1)

Documents