Solución de Problemas de programación Lineal

...

[pic 17]

Figura 2. Proceso iterativo del Método Simplex

La trayectoria del algoritmo es ABC. Lo que significa que cada iteración del método simplex está asociada a un punto. Además, este método se mueve por los bordes, lo que significa que no se puede ir del punto A al C.[pic 18][pic 19]

Para ver la aplicación del método simplex, se aplicará a un ejemplo tomado de (3).

Reddy Mikks produce pinturas para interiores y exteriores con dos materias primas, y . La tabla siguiente proporciona los datos básicos del problema.[pic 20][pic 21]

[pic 22]

Una encuesta de mercado indica que la demanda diaria de pintura para interiores no puede exceder la de pintura para exteriores en más de una tonelada. Asimismo, que la demanda diaria máxima de pintura para interiores es de dos toneladas.

Reddy Mikks se propone determinar la (mejor) combinación óptima de pinturas para interiores y exteriores que maximice la utilidad diaria total.

El modelo completo de Reddy Mikks es

Maximizar [pic 23]

Sujeto a

[pic 24]

[pic 25]

[pic 26]

[pic 27]

[pic 28]

Primero hay que convertir las restricciones en ecuaciones con el uso de unas variables denominadas de holgura y exceso. Estas suelen estar representadas por la letra , se suman si la restricción es de signo y se restan si la restricción es de signo .[pic 29][pic 30][pic 31]

Maximizar [pic 32]

Sujeto a

[pic 33]

[pic 34]

[pic 35]

[pic 36]

[pic 37]

A continuación, se escribe la ecuación objetivo como

[pic 38]

Así, se puede representar la tabla simplex inicial como

[pic 39]

Figura 3. Tabla inicial Simplex

La tabla da la solución inicial que se inicia en el origen , por lo que se definen como las variables no básicas y como las variables básicas. La variable objetivo y las variables básicas aparecen en la columna “Básica”. En la columna “Solución” se dan sus valores; es decir, , , , , . [pic 40][pic 41][pic 42][pic 43][pic 44][pic 45][pic 46][pic 47][pic 48]

La función objetivo puede mejorarse si se incrementa una de sus variables. En la tabla simplex donde la ecuación aparece como , se selecciona la variable no básica con el coeficiente más negativo en la ecuación objetivo, . Esto se conoce como la condición de optimalidad simplex. La variable se conoce como la variable de entrada.[pic 49][pic 50][pic 51]

Si es la variable de entrada, una de las variables básicas actuales debe salir. La mecánica para determinar la variable de salida implica calcular las relaciones del lado derecho de las ecuaciones (columna Solución) con los coeficientes de restricción estrictamente positivos bajo la variable de entrada, , como se muestra [pic 52][pic 53]

[pic 54]

Figura 4. Determinación de la variable de salida

Se elige la variable básica con la relación positiva menor, la cual viene a ser la intersección no negativa mínima con el eje . Esta regla se conoce como condición de factibilidad simplex[pic 55]

El proceso de intercambio se basa en las operaciones de filas de Gauss-Jordan. Identifica la columna de la variable de entrada como columna pivote y la fila de la variable de salida como fila pivote. La intersección de la columna pivote y la fila pivote se conoce como elemento pivote.

[pic 56]

Figura 5. Fila y columna pivote

Los cálculos de Gauss-Jordan necesarios para obtener la nueva solución básica son de dos tipos. Para la fila pivote, se reemplaza la variable de salida en la columna Básica con la variable de entrada. Luego, se hace Nueva fila pivote Fila pivote actual Elemento pivote. Para todas las demás filas, incluyendo z; nueva fila = (Fila actual) (Coeficiente de la columna pivote) (Nueva fila pivote). Al aplicar estas operaciones se tiene:[pic 57][pic 58][pic 59][pic 60]

[pic 61]

Figura 6. Nueva solución básica

Los coeficientes de las restricciones de la variable básica forman una matriz de identidad. Por consiguiente, la columna Solución de forma automática da la nueva solución. En la última tabla, la condición de optimalidad muestra que es la variable de entrada. La condición de factibilidad produce la siguiente información:[pic 62]

[pic 63]

Figura 7. Segunda variable de salida

Al aplicar las operaciones de Gauss-Jordan a esta nueva tabla se obtiene la siguiente solución.

[pic 64]

Figura 8. Solución optima

Aquí se cumple la condición de optimalidad, ya que ninguno de los coeficientes de la fila son negativos. Los resultados de la tabla simplex se pueden interpretar como sigue[pic 65]

[pic 66]

Figura 9. Interpretación de resultados.

El valor de las variables de holgura asociadas a cada recurso da el estado del mismo. Si el valor es 0, el recurso se designa como escaso, ya que dicho recurso se ha consumido por completo. En cambio, si la holgura es positiva, el recurso es abundante. Para este modelo se tiene:

[pic 67]

Figura 10. Estado de los recursos

3.4. Modelo de transporte

El modelo de transporte es una técnica de programación lineal ideada para minimizar costos relacionados