Método Simplex.

Conceptos y Ejemplo.

Integrantes:

                                                         

                                   

Índice

Introducción

Conceptos

2.1 Forma estándar

2.2 Variable de holgura.

2.3 Variable de exceso

2.4 Variables básicas y no básicas.

2.4.1 Variables básicas.

2.4.2 Variables no básicas.

2.5 Solución básica

2.6 Solución básica factible

2.7 Solución básica no factible

2.8 Solución múltiple

2.9 Solución inexistente.

2.10 Variable de entrada

2.11 Variable de salida

2.12 Condición de optimalidad.

2.13 Condición de factibilidad

Ejemplo Práctico

3.1 Planteamiento

3.2 Solución e interpretación de resultados

4.1 Referencias

 

Introducción

El Método simplex es una herramienta de programación lineal desarrollado por George Dantzing.

El método consiste en buscar sistemáticamente a través de todas las posibles soluciones, la solución óptima a un problema. Es un método muy eficiente y permite el uso de muchas variables, tiene como punto de partida el origen, el cual  es la solución inicial (solución básica factible). La eficiencia del método se consigue debido a que se dirige la búsqueda haciendo cambios a una solución básica factible adyacente, que se distingue al tener m-1 variables básicas iguales; es decir, dos vértices adyacentes sólo difieren en una variable básica; seleccionando la ruta de mayor pendiente, para mejorar el valor de Z, o por lo menos conservarlo este método prueba todos los puntos extremos gráficos.

Para aplicar el método Simplex se requiere considerar:

-Las desigualdades deben ser igualdades

-Todas las bi ≥ 0

-El modelo debe tener unicamente variables de holgura.

Los pasos del método Simplex

1.- Utilizando la forma estándar determinar una solución básica factibe igualando las m-n variables a cero ( el origen).

2.- Seleccionar la variable de entrada que a incrementar su valor pueda mejorar el valor de la Función objetivo cuando no existe esta situación la solución actual es la óptima, si no ir al siguiente paso.

3.- Seleccionar la variable de salida

4.- Determinar la nueva solución básica factible al hacer la variable de entrada en básica.

En el método simplex se hacen diversos cálculos de álgebra de matrices, para facilitar estos cálculos se hace uso de  una estructura de tabla  en la cual es expresado el modelo.

Para poder expresar un modelo en forma de tabla en necesario.

Expresar la Función objetivo como Zj-Cj

Ubicar las variables básicas en la solución inicial.

Las restricciones deben estar en forma de igualdad

 

Conceptos

 2.1 Forma estándar

El empleo de las soluciones básicas para resolver un modelo general de programación lineal , requiere poner el problema en una forma estándar y estas propiedades son:

1. Todas las restricciones son ecuaciones con un lado derecho no negativo.

2. Todas las variables son no negativas.

3. La función objetivo puede ser de maximización o minimización.

Ejemplo:

Maximizar z = 2x1 + 3x2

S.a

x1+x2 ≥ -5

-6x1+7x2 ≤ 4

x1+x2 = 10

x1,x2 ≥ 0

Forma Estándar

Maximizar z = 2x1 + 3x2

S.a

-x1-x2 +x3 = 5 ----> Se agrega una variable de exceso, y se multiplica por (-1) para tener un lado derecho no negativo.

-6x1+7x2 +x4 = 4 -----> Se agregó una variable de holgura.

x1+x2 = 10   --> Como es una ecuación no se necesitan variables de holgura ni de exceso.

x1,x2 ,x3,x4≥ 0.

2.2 Variable de holgura.

La variable de holgura aparece en las restricciones ≤, esta se agrega sumando en la restricción para que la desigualdad se vuelva ecuación.

Ejemplo:

x1+2x2≤4

Equivale a:

x1 + 2x2 + x3 = 4

Donde la variable x3≥0

2.3 Variable de exceso

La variable de exceso aparece en las restricciones ≥, aparece restando  en la restricción para convertir la desigualdad en ecuación.

Ejemplo:

x1+2x2≥4

Equivale a:

x1 + 2x2 - x3 = 4

Donde la variable x3≥0

El lado derecho de una ecuación siempre se puede hacer no negativo, multiplicando la ecuación por -1, de ser necesario.

2.4 Variables básicas y no básicas.

Cuando el modelo de programación lineal esta expresado en su forma estándar hay m ecuaciones lineales por n incognitas con (m<n). Estas variables se dividen en 2 grupos

1. Las n-m variables a las cuales se les asigna un valor de cero.

2. Las restantes m variables se determina su valor resolviendo las m ecuaciones resultantes.

2.4.1 Variables básicas.

Si las m ecuaciones producen una solución única, entonces las m variables asociadas se llaman variables básicas.

 Ejemplo:

x1 + 4x2 = 8

4x1 + 2x2 = 4

Tiene solución única x1=0, x2=2. Tanto x1 como x2 son variables básicas.

2.4.2 Variables no básicas.

 Las n-m restantes variables se conocen como variables no básicas.

Ejemplo:

x1+2x2≥4

Equivale a:

x1 + 2x2 - x3 = 4

Las n-m variables son x1,x2 por lo tanto se vuelven variables no básicas..

 

2.5 Solución básica

Una solución es básica si al menos n-m variables valen cero.

El número máximo de posibles soluciones básicas para un modelo con  m ecuaciones  y n incógnitas es

      n      =         n              

      m            m!(n-m)!

2.6 Solución básica factible

Si todas las variables asumen valores no negativos, entonces la solución básica es factible. Los puntos extremos de la región factible son soluciones básicas factibles.

Ejemplo:

x1 + 4x2 = 8

4x1 + 2x2 = 4

Tiene solución única x1=0, x2=2.4 

 

2.7 Solución básica no factible

Una solución básica no factible tiene cero variables no básicas, es decir no hay restricciones con desigualdades por lo que no aparecen variables de holgura ni de exceso.

Ejemplo:

Ecuaciones:

x1+x2=8

4x1+2x2=4

Solución única con x1=-6, x2=14.

Solución básica no factible debido a que x1<0 y una variable de desición no puede ser <0.

2.8 Solución múltiple

No hay variables no básicas .

Ejemplo:

Ecuaciones:

4x1+2x2 = 8

2x1+x2 = 4

Como las ecuaciones son linealmente dependientes hay soluciones múltiples al resolver el sistema.

2.9 Solución inexistente.

No hay variables no básicas

Ejemplo:

Ecuaciones

x2 +3x5=8

2x2 + 6x5=4

Las ecuaciones son inconsistentes por lo tanto no existe una solución.

2.10 Variable de entrada

Una variable de entrada es una variable no básica en un punto extremo que en el siguiente punto extremo adyacente es variable básica.

2.11 Variable de salida

Una variable de salida es una variable básica en un punto extremo que en el siguiente punto extremo adyacente es variable no básica.

2.12 Condición de optimalidad.

La variable de entrada en un problema de maximización es la variable que tiene el coeficiente mas negativo en el renglón Zj-Cj y para el caso de minimización la variable de entrada corresponde al coeficiente mas positivo del renglón Zj - Cj. La optimalidad se logra cuando en el renglón Zj-Cj  ya no hay valores positivos (minimización) o negativos (maximización) según sea el caso.

Ejemplo de optimalidad en maximización:

Maximizar z = 3x1 + 2x2

S.a

2x1+x2≤18

2x1+3x2≤42

3x1+x2≤24

x,y ≥ 0

Tabla en modelo estándar.

x1

x2

x3

x4

x5

Sol

Zj-Cj

-3

-2

0

0

0

0

x3

2

1

1

0

0

18

x4

2

3

0

1

0

42

x5

3

1

0

0

0

24

En el renglón Zj-Cj todos los valores son positivos por lo tanto llegamos a la optimalidad de la tabla.

x1

x2

x3

x4

x5

Sol

Zj-Cj

0

0

1 ¼

¼

0

33

x2

0

1

- ½  

½

0

12

x5

0

0

-1 ¾

¼

1

3

x1

1

0

¾

0

3

2.13 Condición de factibilidad

La variable de salida tanto en minimización como en maximización  se elige a la variable básica que tiene la razón no negativa mas pequeña.

Ejemplo de factibilidad en maximización.

Maximizar z = 3x1 + 2x2

S.a

2x1+x2≤18

2x1+3x2≤42

3x1+x2≤24

x,y ≥ 0

Tabla en modelo estándar.

x1

x2

x3

x4

x5

Sol

Zj-Cj

-3

-2

0

0

0

0

x3

2

1

1

0

0

18

x4

2

3

0

1

0

42

x5

3

1

0

0

0

24

El criterio de factibilidad se cumple ya que todos los bi (la columna solución) tienen valor no negativo por tanto es una solución factible.

Ejemplo Práctico

3.1 Planteamiento

La compañia Reddy Mikks produce pinturas tanto para interiores como para exteriores, a partir de dos materias primas M1 y M2. En la tabla se muestran los datos pertinentes.

Toneladas de materia prima por tonelada de:

Pintura para exteriores

Pintura para interiores

Disponibilidad máxima diaria (toneladas)

Materia prima M1

6

4

24

Materia prima M2

1

2

6

Utilidad por tonelada (1000 dólares)

5

4

Una encuesta de mercado restringe la demanda máxima diaria de pintura para interiores a  2 toneladas. Además, la demanda diaria de pintura para interiores no puede exceder a la de pintura para exteriores por más de 1 tonelada. Reddy Mikks quiere determinar la mezcla de producto óptima de pinturas para interiores y para exteriores que maximize la utilidad total diaria.

Los elementos básicos del modelo son:

1.-Variables de decisión que se tratan de determinar

2.-Objetivo (meta) que se trata de optimizar

3.-Restricciones que necesita satisfacer

La definición apropiada de variables de decisión  es el primer paso para el desarrollo del modelo. Una vez definidas las variables de decisión habrá que construir la Función objetivo y las restricciones

Para el problema necesitamos determinar las cantidades que se van a producir de pinturas para interiores y exteriores.

Las variables del modelo se definirian como :

x1= Toneladas diarias producidas de pintura para exteriores.

x2= Toneladas diarias producidas de pintura para interiores.

El siguiente paso  es plantear la función objetivo, en el caso de la compañia su objetivo es incrementar la utilidad total diaria de la pintura , tanto para exteriores como para interiores.

La función objetivo quedaría planteada de la siguiente manera.

Maximizar= 5x1+4x2.

Debido a que las disponibilidades diarias de la materia prima M1 y M2 están limitadas a 24 y 6 toneladas respectivamente, las restricciones se expresarian como:

6x1 + 4x2 ≤24   (Materia prima M1)

x1 + 2x2 ≤ 6  (Materia prima M2)

Hay 2 tipos de restricciones de la demanda, la primera es que la demanda máxima de pintura para para interiores debe limitarse a dos toneladas, la segunda plantea que el exceso de la producción diaria de pintura para exteriores sobre la pintura para exteriores es cuando mucho de una tonelada.

La primera restricción se expresa como:

x2≤2

La segunda restricción se expresa como

x2-x1≤1

La restricción final es una restricción implícita sobre el modelo, que dice que las variables x1 y x2 deben ser >= 0.

El modelo completo de Reddy Mikks es planteado como:

Maximizar z= 5x1+4x2

Sujeto a

6x1+4x2≤24

x1+2x2≤6

-x1+x2≤1

x2≤2

x1,x2≥0

3.2 Solución e interpretación de resultados

Para resolver el problema primero lo pondremos en su forma estándar.

Maximizar z= 5x1+4x2 +x3+x4+x5+x6

Sujeto a

6x1+4x2+ x3                        = 24

x1+2x2         +  x4                = 6

-x1+x2                   +x5         = 1

x2                                  + x6 = 2

x1,x2,x3,x4,x5,x6≥0

La forma estándar se resume en forma de una tabla simplex como:

Solución básica               factible

z

x1     x2    x3    x4    x5    x6

Solución

z

1

-5     -4     0      0      0     0

    0

x3

x4

x5

x6

0

0

0

0

 6       4     1      0     0     0

 1       2     0      1     0     0

-1       1     0      0     1     0

 0       1     0      0     0     1

24

6

1

2

Cada uno de los cuatro renglones inferiores representa una ecuación  cuyo lado derecho  se da en  la columna de solución. El renglón -z se obtiene de  z-5x1-4x2=0. Las variables de holgura x3,x4,x5,x6 proporcionan una solución básica factible inicial, debido a que una vez que les asignamos valores de cero a las variables no básicas x1 y x2, la columna de solución proporciona los valores de las holguras, es decir x3=24, x4=6, x5=1 y x6=2.

En la tabla del renglón z elegiremos a la variable mas negativa como nuestra variable de entrada ya que estamos hablando de un caso de maximización. La variable mas negativa es -5 que corresponde a x1.

Teniendo la variable de entrada procedemos a encontrar la variable de salida que es la variable cuya razón se asocia con la mas pequeña no negativa que en este caso es la variable x3, el remplazo de la variable de entrada con la variable de salida producirá la nueva solución básica (x1,x4,x5,x6).

Solución basica factible

z

  x1   

  x2    x3    x4   x5    x6

 Solución

z

1

-5

  -4     0      0     0      0

      0

x3

0

 6

    4    1       0     0      0

       24

x4

x5

x6

0

0

0

 1

-1

 0 

  2     0       1      0      0

  1     0       0      1      0

  1     0       0      0      1

       6

       1

       2

Para producir la nueva solución básica se incluyen los siguientes pasos.

1.- Primero el nuevo renglón pivote = renglón pivote actual / elemento pivote.

2.- Después todos los demás renglones incluyendo z serán modificados de la siguiente manera.

Nuevo renglón = (renglón actual) - (su coeficiente de la columna pivote) x (nuevo renglón pivote)

Por tanto el nuevo cuadro símplex correspondiente a la nueva solución básica es (x1,x4,x5,x6).

Solución básica factible

z

x1    x2     x3    x4    x5    x6

Solución

z

1

0    -⅔      ⅚      0      0     0  

20

x1

x4

x5

x6

0

0

0

0

1            ⅙     0      0     0

0    1⅓     -⅙    1       0     0

0    1 ⅔     ⅙     0      1     0

0      1        0     0       0     1  

4

2

5

2

Nuevamente elegimos a nuestra variable de entrada que seria la variable mas negativa, en nuestra tabla solo queda una variable negativa por tanto es la única que puede ser nuestra variable de entrada, para elegir la variable de salida elegimos a la que tenga la razón no negativa mas pequeña, es decir dividimos los elementos de la columna de solución entre la columna de la variable de entrada.

Por tanto la variable de entrada es x2 y la variable de salida es x4. Ahora repetimos los pasos anteriores para encontrar la nueva solución básica. Por tanto el nuevo cuadro símplex correspondiente a la nueva solución básica es (x1,x2,x5,x6).

Solución básica factible

z

x1   x2   x3    x4     x5   x6

Solución

 z

1

0     0     ¾    ½      0     0

21

x1

x2

x5

x6

0

0

0

0

1     0    ¼    -½      0     0

0     1    -⅛    ¾      0     0

0     0     ⅜   -1 ¼   1     0

0     0     ⅛    -¾     0     1

3

1 ½

2 ½

½

Puesto que ninguno de los coeficientes del renglón z asociados con las variables no básicas x3 y x4 es negativo, la última tabla simplex es óptima.

La solución óptima se puede leer en la tabla simplex de la siguiente manera. Los valores óptimos de las variables en  la columna “básica” se dan en la columna derecha de la “solución” y se interpretan como:

Variable de decisión

Valor óptimo

Recomendaciones

x1

x2

z

3

1.5

21

Producir diariamente 3 toneladas de pintura para exteriores

Producir diariamente 1.5 toneladas de pintura para interiores

La utilidad diaria es de 21000 dólares

A partir de la tabla simplex óptima es posible determinar la situación de los recursos.

 La situación de los recursos está designada como escasa o abundante dependiendo, respectivamente , de si las actividades (variables) del modelo utilizan totalmente o no la cantidad  del recurso. Esta información se obtiene de la tabla simplex óptima, verificando el valor de la variable de holgura asociada con la con la restricción que representa al recurso. Si el valor de la holgura es cero, el recurso se utiliza completamente y se clasifica como escaso. De lo contrario, una holgura positiva indica que el recurso es  abundante.

Para este modelo las cuatro restricciones se clasifican:

Recursos

Valor de holgura

Solución

Materia prima, M1

x3=0

Escaso

Materia prima, M2

X4=0

Escaso

Límite de la demanda 1

x5=1

Abundante

Límite de la demanda 2

x6=2

Abundante

La situación de los recursos indica que  está garantizado un incremento en la disponibilidad de las materias primas M1 y M2, debido a que ambos recursos son escasos.

4.1 Referencias

     

      * Hamdy A. Taha. (1998). Investigación de Operaciones (Sexta edición.). Prentice Hall.

     Imágenes extraidas de:

      * Imagen2.jpg (JPEG Imagen, 1158x696 pixels) - Escalado (10%). (s. f.). Recuperado abril 14, 2012, a partir de http://gauss.acatlan.unam.mx/file.php/1/Imagen2.jpg

      * acatlan.png (PNG Imagen, 1024x244 pixels) - Escalado (31%). (s. f.). Recuperado abril 14, 2012, a partir de http://www.tutor.unam.mx/images/acatlan.png

   

                                                                                        Página  de