MATEMÁTICAS APLICADAS Y COMPUTACIÓN

MÉTODO SIMPLEX

EQUIPO:

FLORES VELASCO JANEHT

HERNÁNDEZ RODRÍGUEZ JOCELYN

GONZÁLEZ IÑIGUEZ OCTAVIO

INDICE

VARIABLE NO RESTRINGIDA.

SOLUCIÓN FACTIBLE

SOLUCIÓN FACTIBLE BÁSICA.

SOLUCIÓN FACTIBLE NO DEGENERADA.

SOLUCIÓN FACTIBLE BÁSICA DEGENERADA.

SOLUCIÓN NO ACOTADA

SOLUCIONES ÓPTIMAS MÚLTIPLES

VARIABLES DE HOLGURA Y EXCESO:

Variable de holgura:

Variable de exceso:

VARIABLES DE ENTRADA:

VARIABLE DE SALIDA:

FORMA ESTÁNDAR DEL MODELO:

VARIABLES BÁSICAS:

VARIABLES NO BÁSICAS:

CONDICIÓN DE OPTIMALIDAD:

CONDICIÓN DE FACTIBILIDAD:

EJEMPLO DE APLICACIÓN DEL MÉTODO SIMPLEX

PLANTEAMIENTO DEL MODELO

SOLUCIÓN

INTERPRETACIÓN:

BIBLIOGRAFIA

CONCEPTOS:

VARIABLE NO RESTRINGIDA.

Es aquella que puede tomar toda clase de valores positivos, cero y negativos puede escribirse como la diferencia de dos variables no-negativas.

Ejemplo:

Sea x1 una variable no restringida, entonces:

x1=x2-x3

donde x2>=0, Nótese que si x2>x3, eso implica que x1>0: si x2=x3, entonces x1=0: si x2<x3, se tiene que x1<0.

SOLUCIÓN FACTIBLE  

Una solución factible es aquel vector columna Xt = (x1,...xn) que satisface las restricciones,

Ax>=b

x>=0

Ejemplo:

SOLUCIÓN FACTIBLE BÁSICA.

 Una solución factible básica es aquella solución factible con no más de m componentes positivas.

SOLUCIÓN FACTIBLE NO DEGENERADA.

Es una solución factible básica donde exactamente m componentes del vector columna X son positivas.

SOLUCIÓN FACTIBLE BÁSICA DEGENERADA.

Es una solución factible básica donde hay menos de m componentes positivas del vector X.

SOLUCIÓN NO ACOTADA

En algunos modelos de Programación lineal, los valores de las variables se pueden incrementar indefinidamente sin violar ninguna de las restricciones, el espacio de la solución es no acotado por lo menos en una dirección. Como resultado el valor objetivo aumentará (caso de maximización) o disminuirá (caso de minimización) indefinidamente. En este caso, tanto el espacio de la solución como el valor objeto óptimo son no acotados.

La no acotación en un modelo solo indica un modelo mal construido.

Las irregularidades más probables en estos modelos son que no han tomado en cuanta una ó más restricciones no redundantes y que los parámetros (contantes) de algunas restricciones no se calcularon correctamente.

un ejemplo que nos muestra un problema con solución no acotada es el siguiente:

Max z =x1+x2

s.a.

-x1+x2<=2

x1-x2<=2

x1,x2>=0

La gráfica del siguiente modelo es:

Como observamos en la gráfica la región factible crece indefinidamente y z nunca va a salir de ella, esto significa que nuestro problema tiene una solución no acotada.

SOLUCIONES ÓPTIMAS MÚLTIPLES

Dado el programa lineal en forma canónica Max z = cx sujeto a Ax<=b, x>=0, si existe un vector aj que no esté en la base cuya correspondiente zj-cj sea igual a 0, el resto de las zj-cj>=0 y todas las yij >0, i= 1,…,m. entonces el programa lineal tiene soluciones óptimas múltiples y la base es óptima.

Ejemplo :

Max z+ 4x+2y

s.a.

4x+y<=4

x-y<=1

x,y<=0

La gráfica del problema es :

La cual nos muestra que se puede tener dos soluciones óptimas para nuestro problema.

VARIABLES DE HOLGURA Y EXCESO:

Son variables que se agregan a la restricción en el modelo de la forma ampliada, para que la relación de la restricción sea de igualdad (representa el valor que le hace falta al lado izquierdo para ser igual al lado derecho). Ambos tipos de variables están sujetas a las mismas consideraciones que las variables de decisión (divisibilidad y no negatividad), para que de esta manera, cada restricción se convierta en igualdad.

Variable de holgura:

Para cualquier solución factible dada, la diferencia entre los coeficientes del lado izquierdo y los parámetros del lado derecho,  de una restricción, se le denomina la cantidad de holgura en las desigualdades ≤. Mostrando de manera explícita la diferencia, introduciendo una variable adicional en cada restricción ≤.

Se suma al lado izquierdo de la restricción del tipo ≤.

6 x1 + 4 x2 ≤ 24

6 x1 + 4 x2 + h = 24

Variable de exceso:

Para cualquier solución factible dada, la diferencia entre los coeficientes del lado izquierdo y los parámetros del lado derecho,  de una restricción, se le denomina la cantidad de exceso en las desigualdades ≥. Mostrando de manera explícita la diferencia, introduciendo una variable adicional en cada restricción ≥.

Se resta al lado izquierdo de la restricción del tipo ≥.

2 x1 + 3x2 ≥ 24

2 x1 + 3 x2 - h = 24

VARIABLES DE ENTRADA:

Estas suelen encontrarse en un criterio que se conoce como “Condición de optimalidad”, en un modelo, ya sea de optimización o minimización, y se refiere a la variable no básica en el renglón “z” con el coeficiente más negativo, si se trata de una maximización, o el coeficiente mas positivo, si se trata de una minimización, la cual, en el la tabla de solución anterior, a excepción de la primer tabla, esta variable era una variable básica.

VARIABLE DE SALIDA:  

Esta variable es un punto extremo que se encuentra en un criterio conocido como “Condición de factibilidad”, en un modelo, ya sea de optimización o minimización, y se refiere a la variable básica asociada con la mínima razón no negativa con el coeficiente más negativo, si se trata de una maximización, o el coeficiente mas positivo, si se trata de una minimización, la cual, en el la tabla de solución siguiente, pasará a ser variable no básica.

FORMA ESTÁNDAR DEL MODELO:

 Para resolver un modelo de programación lineal por medio del método simplex, este se deberá poner en forma estándar aplicando los siguientes puntos:

1. Todas las restricciones son ecuaciones son un segundo miembro positivo.

2. Una restricción se convierte en ecuación adicionando una variable de holgura (ó restando una variable de exceso) al primer miembro de la ecuación. El segundo miembro de la ecuación, se puede hacer positivo multiplicando ambos miembros por -1.

3. Todas las variables son positivas.

4. En el caso de que una variable yi cualquiera sea irrestricta (no restringida), esta pudiera expresarse en términos de dos variables positivas mediante el uso de la sustitución yi=yi+1-yi+2 donde yi+1, yi+2 >= 0.

5. La función objetivo ´puede ser de maximización ó de minimización.

Un ejemplo sencillo para poder obtener un modelo de programación lineal en forma estándar es el siguiente:

Min z= 2x1+3x2

s.a

x1+x2=10

-2x1+3x2<=-5

7x1-4x2<=6

x1 no restringida

x2>=0

Haciendo uso de los puntos anteriores obtenemos el siguiente el siguiente modelo de programación lineal en  forma estándar:

Min z= 2x3-2x4+3x2

s.a

x3-x4+x2=10

2x3-2x4+3x2-s1=-5

7x3-7x4-4x2+s2=6

 xi>=0

si>=0

VARIABLES BÁSICAS:

Son las variables del modelo de programación lineal que se hacen igual a cero al inicio de la primera iteración del método Simplex.

La columna llamada básica indica indica a las variables básicas actuales, en cada iteración.

Ejemplo

Maximizar z = 3x1 +9x2

Sujeto a

x1 + 4x2 £ 8

x1 + 2x2 £ 4

x1,x2 <=0

VARIABLES NO BÁSICAS:

Son las variables del modelo de programación lineal que son diferentes de cero al inicio de la primera iteración del método Simplex.

CONDICIÓN DE OPTIMALIDAD:

En el caso de la maximización, si todas las variables no básicas tienen coeficientes positivos en la función objetivo, se ha encontrado la solución óptima. En caso contrario se selecciona a la variable con coeficiente más negativo como la variable de entrada.

Se hace uso de este criterio para seleccionar la variable de entrada.

CONDICIÓN DE FACTIBILIDAD:

 Se obtiene la mínima razón = solución/(coeficiente positivo) donde el coeficiente positivo es asociado a la variable de entrada, y no se toman en cuenta valores menores ó iguales a cero.

s.a

Se hace uso de este criterio para seleccionar la variable de salida.

EJEMPLO DE APLICACIÓN DEL MÉTODO SIMPLEX

La empresa AXUS S.A. desea conocer la cantidad de productos A, B y C a producir para maximizar el beneficio, si cada unidad vendida genera en utilidad $150, $210 y $130 por unidad respectivamente.

Cada producto pasa por 3 mesas de trabajo, restringiendo la cantidad de unidades producidas debido al tiempo disponible en cada una de ellas. La siguiente tabla muestra el tiempo requerido por unidad de cada producto en cada mesa y el tiempo total disponible semanalmente (tiempo dado en minutos):

Se supone que cada unidad producida es vendida automáticamente. Determinar la combinación de productos que maximicen la utilidad para la compañía.

Una vez analizado el enunciado el lector procederá a crear el modelo matemático.

PLANTEAMIENTO DEL MODELO

x1= unidades producto A

x2= unidades  producto B

x3= unidades producto C

Función Objetivo (F.O.):

Max. Z = $150X1 + $210X2 + $130X3

                                    S.A.:

10X1 + 15X2 + 7X3 <= 3300 Minutos

12X1 + 17X2 + 7X3 <= 3500 Minutos

8X1 + 9X2 + 8X3 <= 2900 Minutos

X1 , X2 , X3 >= 0

Explicación del modelo:

·         La función objetivo representa la utilidad obtenida por cada unidad de producto A,B y C.

·         La primera restricción nos indica que el tiempo requerido para los tres productos en la Mesa 1 debe ser menor a 3300 minutos.

·         La segunda restricción establece que el tiempo requerido para los tres productos en la Mesa 2 debe ser menor a 3500 minutos.

·         La tercera restricción nos indica que el tiempo requerido para los tres productos en la Mesa 3 debe ser menor a 2900 minutos.

SOLUCIÓN

Resolveremos este planteamiento a través del método Simplex. Nuestro primer paso será convertir nuestro modelo a la forma estándar, agregando variables de holgura en las restricciones donde sea necesario. El modelo queda de la siguiente manera:

Max. Z = 150 X1 + 210 X2 + 130 X3

                                     S.A.:

10 X1+ 15 X2 + 7 X3+X4= 3300

12 X1 + 17 X2 + 7 X3 +x5 = 3500

8 X1 + 9 X2 + 8 X3+x6 = 2900

Xi >= 0       i=1,6

Ahora tomamos nuestra función objetivo y la igualamos a cero, para identificar los zj-cj. Además, localizaremos la solución básica factible inicial, partiendo del hecho de que el método Simplex comienza en el origen.

z-150x1+210x2+130x3=0

Solución básica factible inicial:

x1=0

x2=0

x3=0

x4=3300

x5=3500

x6=2900

Con la información anterior podemos construir nuestra primera tabla, que queda de la siguiente manera:

En este caso nuestra variable de entraba va a hacer x2 ya que tiene el número más negativo de la tabla.

Después buscaremos nuestra variable de salida, la cual se elige calculando la razón. Esta se calcula dividiendo los valores de las soluciones entre los valores de la  columna de nuestra variable de entrada. La variable con la razón más pequeña corresponderá a la variable de salida. No se calcula la razón para valores negativos o iguales a cero.

Calculando las razones:

3300/15=220

3500/17=205.88

2900/9=322.22

El menor valor es el de x5, por lo tanto es nuestra variable de salida.

 El elemento que se encuentra en la intersección de la columna de la variable de entrada (columna pivote) , y el renglón de la variable de salida (renglón pivote), se conoce como elemento pivote. A partir del elemento pivote y con la ayuda de operaciones básicas de renglón (Gauss Jordan), trataremos que el elemento pivote se convierta en uno y los demás elementos de dicha columna sean ceros.

 Ahora nuestra tabla es la siguiente:

La variable de entrada será x3.

La variable de salida será x6.

Como observamos en nuestro zj-cj todos nuestros valores son positivos, esto significa que llegamos a nuestra solución óptima.

X1=0

X2=105.4795

X3=243.8656

X4=10.958

X5=0

X6=0

Z= 53849.32

INTERPRETACIÓN:

La solución nos indica que para alcanzar la ganancia óptima posible se tendrán que producir 105 unidades del producto B y 243 del producto C, el producto A no debe ser producido. Además tendremos que en la Mesa 1 habrá un sobrante de 10.958 minutos, y que en la Mesa 2 y 3 se utilizará el tiempo disponible en su totalidad.

BIBLIOGRAFIA

Prawda, Witenberg Juan. Metodos Y Modelos De Investigación De Operaciones. Tercera ed. Vol. 1. Medellín: Limusa Wiley, 1981.Pág.71,73109.

Daellenbach, Hans G., John A. George, and Donald C. McNickle. Introducción a Las Técnicas De Investigación De Operaciones. Tercera ed. México: CECSA, 1990. Pág. 62/711

"Conceptos Programacion Lineal." Upload & Share PowerPoint Presentations and Documents. Web. 13 Apr. 2012. <http://www.slideshare.net/coryd0306/conceptos-programacion-lineal>.

Taha,H. Investigación de operaciones, una introducción, Pearson, México, 1998. Pág 103.

"Universidad Autónoma Del Estado De Morelos." Universidad Autónoma Del Estado De Morelos. Web. 12 Apr. 2012. <http://www.uaem.mx/posgrado/mcruz/>.

"4.2 Casos Especiales En La Aplicación Del Método Simplex." 4.2 Casos Especiales En La Aplicación Del Método Simplex. Web. 17 Apr. 2012. <http://148.204.211.134/polilibros/portal/Polilibros/P_terminados/Investigacion_de_operaciones_chavez/DOCUMENTOS/UNIDAD4/UNIDAD42.htm>.