3-Variantes del método simplex variables de excedente y artificiales. Minimización PDF

Preview

Summary

Download 3-Variantes del método simplex variables de excedente y artificiales. Minimización PDF

Description

3) VARIANTES DEL MÉTODO SIMPLEX: VARIABLES DE EXCEDENTE Y ARTIFICIALES. MINIMIZACIÓN

VARIABLES DE EXCEDENTE Recuerda que el primer paso para resolver un problema de programación lineal es convertir las desigualdades en igualdades utilizando variables de holgura siempre que las restricciones sean de menor o igual (=? Si la inecuación contiene el signo de >=, debe recurrirse a una va ria ble de e xce de nt e . Esta se resta al primer miembro de la inecuación. Ejemplo: Si las restricciones de un problema de programación lineal (PL) son:

1

La primera desigualdad se transforma en igualdad añadiendo una variable de holgura, que llamaremos s₁ (tal como vimos en la lectura anterior), con lo que nos queda la ecuación:

2

La segunda desigualdad se convierte en ecuación restando una variable de excedente, que denominamos s₂, y la ecuación queda:

3

La variable de excedente s₂ representa la diferencia entre: x₁ + 10x₂ y 80; si esta diferencia es cero, entonces: s₂ = 0, pero si esta diferencia es distinta a cero, será necesariamente positiva, por lo que s₂ > 0, pues la desigualdad es mayor que cero.

Tanto las variables de holgura como las de excedente son mayores o iguales a cero; en caso contrario, se violarían una o más desigualdades originales. En este modelo modificado, se tiene un sistema de ecuaciones con más variables que igualdades. Recuerda el análisis que hicimos en la lectura 1. El sistema sigue teniendo n - m variables no básicas. VARIABLES ARTICIALES Las variables artificiales se utilizan en el método simplex sólo como auxiliares para identificar una solución factible básica inicial para el problema. Estas variables son necesarias cuando un problema contiene restricciones de mayor que o igual a (>=) y de igualdad (=). Las variables artificiales se utilizan para completar la matriz identidad, y de esta manera permitir una solución inicial. (Davis y McKeown, 1995, p. 155).

Lo que debe quedar claro es que, al sumar variables de holgura, como el coeficiente de dicha variable es 1, siempre podemos encontrar una submatriz de identidad para poder calcular la solución factible básica inicial. Pero si restamos una variable de excedente, el coeficiente es -1, y, por esa razón, hay que agregar una variable artificial solamente para poder partir con el método simplex, ya que podremos encontrar, con el auxilio de las variables artificiales, una SFBI. Lo mismo ocurre en el caso de una igualdad. Para poder comprender mejor este tema, vamos a resolver un problema en el que tengamos que recurrir a variables de excedente y artificiales. UN CASO DE MINIMIZACIÓN Antes de introducir este tema, queremos aclarar que no solamente las variables de excedente y artificiales se utilizan en problemas de minimización; simplemente, en este tipo de problemas, se utilizan con mayor frecuencia. Por otro lado, tienes que tener en cuenta dos cuestiones para un problema de minimización: 1

La prueba de optimalidad cambia: el proceso de solución continúa hasta que todos los valores de la fila de los indicadores sean negativos.

2

La variable entrante que se elige es la que tiene el valor positivo más grande en la fila de los indicadores.

Para fijar conceptos, te proponemos resolver, mediante el método simplex, el mismo problema resuelto en el Módulo 1 pero empleando el método gráfico. ENUNCIADO DEL PROBLEMA Con base en los actuales niveles de inventario y de la demanda potencial para el siguiente mes, los administradores de una empresa láctea han especificado que la producción total combinada de los productos A y B deben ser, al menos, de 7700 litros. Por otro lado, se debe satisfacer también el pedido de un cliente de 2750 litros del producto A. El objetivo de los administradores de la empresa es satisfacer los requisitos anteriores incurriendo en un costo de producción mínimo. Los costos de producción son de $3 por litro de producto A y de $2 por litro para el producto B. PLANTEO DEL PROBLEMA

RESOLUCIÓN MEDIANTE EL MÉTODO SIMPLEX 1

Convertimos las desigualdades en igualdades. Como en las restricciones de >= restamos variables de excedente, a la vez, para poder encontrar una solución factible básica inicial, sumaremos simultáneamente variables artificiales que llamaremos A. (En el texto de la bibliografía básica, figura como R. Hay distintas notaciones en los textos consultados; en esta lectura adoptaremos A).

Obsérvese que la cantidad de variables de excedente serán tantas como inecuaciones del tipo >= haya. En el caso de las variables artificiales, serán la misma cantidad, pues, por cada variable de excedente que restamos, tenemos que sumar una artificial. Si se tratara de una igualdad, solo se agregaría la artificial para poder obtener la SFBI. Como el sistema tiene más variables que ecuaciones, sabemos que existen infinitas soluciones.

2

Planteamos ahora la función objetivo introduciendo las variables artificiales y las de excedente.

¡Importante! Cuando se introducen las variables de holgura o de excedente a la función objetivo, se lo hace con coeficientes cero. Por lo tanto, no afectan el valor de la función objetivo. Pero a las variables artificiales se las introduce con coeficientes grandes, justamente para que el mismo método las expulse, pues no tienen sentido en la función objetivo, ya que existen por una cuestión meramente algebraica. Esta inserción de las variables artificiales con coeficiente alto en la función objetivo crea un problema que, en su momento, estudiaremos como resolver. Generalmente, los coeficientes de las variables artificiales se calculan unas 100 veces más que el de las variables principales. Pero, para simplificar, podemos tomar el mismo valor para ambas variables, A₁ y A₂. El valor que tomaremos es 200 (se podría haber tomado otro; también podrían haberse tomado coeficientes distintos para ambas variables artificiales). Entonces la función objetivo nos queda: Z = 3x₁ + 2x₂ + 0s₁ + 0s₂ + 200A₁ + 200A₂. El coeficiente de las variables artificiales es positivo en los casos de minimización y es negativo en los casos de maximización. Recuerda que los sistemas de restricciones pueden tener restricciones de = o = tanto si se debe maximizar la función objetivo como si se debe minimizarla. 3

Obtengamos, ahora, la SFBI. Analicemos la cantidad de variables no básicas para poder obtener la SFBI (una de las infinitas soluciones del sistema, que es punto de partida para comenzar a optimizar con el método simplex). Tenemos 2 ecuaciones, por lo que m = 2. Y 6 variables, entonces n = 6. Por lo que la cantidad de variables no básicas es: n – m = 6 – 2 = 4. Observa que una posible SFBI es: x₁ = 0; x₂ = 0; s₁ = 0; s₂ = 0; A₁ = 7700; A₂ = 2750.

4

Igualamos a cero a la función objetivo: Z - 3x₁ - 2x₂ + 0s₁ + 0s₂ - 200A₁ - 200A₂ = 0.

5

Planteo de la tabla simplex inicial: Tabla 1: Tabla simplex inicial para el problema de minimización propuesto

Básica z

z

x

x

s

s

A

A

1

-3

-2

0

0

20

20

Solució 0

A 1

0

1

1

1

0

1

0

77 00

A

0

1

0

0

-

0

1

27

Antes de seguir, observemos que, en la última columna, Z = 0 no está en concordancia con lo que indica la función objetivo en esa misma tabla, pues: Z = 3x₁ + 2x₂ + 0s₁ + 0s₂ + 200A₁ + 200A₂;

Z = 3 x 0 + 2 x 0 + 0 x 0 + 0 x 0 + 200 x 7700 + 200 x 2750 = 2 090 000. Esta contradicción se debe a la incorporación de las variables artificiales en la función objetivo con coeficientes distintos de cero. Por lo tanto, habrá que acomodar la tabla para que podamos comenzar a aplicar el método simplex. La forma de hacerlo es anular los coeficientes de las variables artificiales y aplicar operaciones elementales por filas. Observa que, si multiplicamos la fila 2 de la tabla por 200, le sumamos la 1 y sustituimos la fila 1 por el resultado de esta operación, el coeficiente -200 queda en cero. Lo mismo hacemos con la fila 3 para anular el coeficiente de A₂. Así nos queda la tabla: sumamos, a la fila 1, la segunda previamente multiplicada por 200. Tabla 2: Tabla simplex: parte 1. Coherencia en la función objetivo

Básica

z

z

1

A 1

0

Básica

A

x 1 1 9

x 2 1 9

20

1

1

-1

z

x

x

0

1

0

s 1

s

s 2 0

A 1 0

A 2 2

0

1

0

s

0

A

-1

0

Solució n 154000 0 77 00 Solució

A

1

27

Sumamos a la fila 1, la tercera previamente multiplicada por 200.

Básica

z

x

x

s

s

A

A

Solución

z

1

3 9

1 9

20

20

0

0

2090000

A 1

0

1

1

-1

0

1

0

77

0

A

1

0

0

-1

0

1

27

Esta tabla está en concordancia con lo obtenido anteriormente en la función objetivo. Entonces podemos aplicar el método simplex buscando la variable de entrada y de salida. La columna que tiene el número positivo más alto es la correspondiente con x₁. Esta es entonces la variable de entrada. La variable de salida será el cociente positivo menor entre la columna solución y los coeficientes de x₁ en las ecuaciones (recuerda que, en este paso, no se tiene en cuenta la función objetivo). 7700/1 = 7700; 2750/1 = 2750. Y la variable que sale es A₂.

La tabla simplex queda (está marcado el pívot con una circunferencia y quedan anulados todos los coeficientes de la columna del pívot realizando operaciones elementales por filas): 1

a la fila 1, se le suma la 3 previamente multiplicada por -397;

2

a la fila 2, se le suma la 3 previamente multiplicada por -1.

De la lectura de esta tabla, obtenemos las siguientes soluciones: x₁ = 2750; x₂ = 0; s₁ = 0; s₂ = 0; A₁ = 0; A₂ = 2750.

Pero hay coeficientes positivos en la primera fila, lo que nos dice que la función objetivo puede mejorarse. Repetimos el método simplex buscando la variable de entrada, que será x₂, y la de salida, A₁. En una iteración más, la tabla nos queda como sigue.

Esta es la tabla simplex final: x₁ = 2750, x₂ = 4950. El costo mínimo será de $18 150. (Compara estos resultados con el problema resuelto en el Módulo 1 mediante el método gráfico)....