Metodo Simplex Ejemplo

Problema

La Industria DACAR fabrica baterías para sus distribuidores lo que cuenta con un medio de transporte que es el tráiler de carga el cual lleva un contenedor, este contenedor tiene 2 espacios el cual en cada uno se le asigna un tipo de palet (base para depositar las baterías para su posterior traslado) y un límite de baterías que puede soportar que se muestra a continuación, el espacio de este contenedor esta dado de acuerdo al número de baterías que puede contener.

ESPACIOS POR PALET CANTIDAD DE BATERÍAS

Mitad de un Palet 200

Palet Grande 2000

Existen ofertas por parte de diferentes clientes de una misma ciudad el cual se dan a continuación.

CLIENTE NÚMERO DE BATERÍAS GANANCIA POR BATERÍA

1 150 $ 88

2 250 $ 176

3 200 $ 152

4 100 $ 132

5 800 $ 144

6 500 $ 116

7 240 $ 178

8 50 $ 120

La Industria DACAR desea saber qué cantidad de baterías en cada espacio se necesita para maximizar la ganancia de transporte.

Aplicación

Formulación de la Función Objetivo

X1 = NUMERO DE BATERÍAS DEL CLIENTE 1 EN LA PALETA 1/2

X2 = NUMERO DE BATERÍAS DEL CLIENTE 2 EN LA PALETA 1/2

X3 = NUMERO DE BATERÍAS DEL CLIENTE 3 EN LA PALETA 1/2

X4 = NUMERO DE BATERÍAS DEL CLIENTE 4 EN LA PALETA 1/2

X5 = NUMERO DE BATERÍAS DEL CLIENTE 5 EN LA PALETA 1/2

X6 = NUMERO DE BATERÍAS DEL CLIENTE 6 EN LA PALETA 1/2

X7 = NUMERO DE BATERÍAS DEL CLIENTE 7 EN LA PALETA 1/2

X8 = NUMERO DE BATERÍAS DEL CLIENTE 8 EN LA PALETA 1/2

X9 = NUMERO DE BATERÍAS DEL CLIENTE 1 EN LA PALETA GRANDE

X10 = NUMERO DE BATERÍAS DEL CLIENTE 2 EN LA PALETA GRANDE

X11= NUMERO DE BATERÍAS DEL CLIENTE 3 EN LA PALETA GRANDE

X12 = NUMERO DE BATERÍAS DEL CLIENTE 4 EN LA PALETA GRANDE

X13 = NUMERO DE BATERÍAS DEL CLIENTE 5 EN LA PALETA GRANDE

X14 = NUMERO DE BATERÍAS DEL CLIENTE 6 EN LA PALETA GRANDE

X15 = NUMERO DE BATERÍAS DEL CLIENTE 7 EN LA PALETA GRANDE

X16 = NUMERO DE BATERÍAS DEL CLIENTE 8 EN LA PALETA GRANDE

Max Z = 88(X1 + X9) + 176(X2 + X10) + 152(X3 + X11) + 132(X4 + X12) + 144(X5 + X13) + 116(X6 + X14) + 178(X7 + X15) + 120(X8 + X16)

SUJETA A:

X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8 ≤ 200

X9 + X10 + X11 + X12 + X13 + X14 + X15 + X16 ≤ 2000

X1 + X9 ≤ 150

X2 + X10 ≤ 250

X3 + X11 ≤ 200

X4 + X12 ≤ 100

X5 + X13 ≤ 800

X6 + X14 ≤ 500

X7 + X15 ≤ 240

X8 + X16 ≤ 50

Xi ≥ 0, i = 1 – 16

Método Simplex

El Método Simplex es un procedimiento de cálculo algebraico, iterativo, para resolver Modelos Lineales de cualquier tamaño.

El algoritmo Simplex requiere que el Modelo Lineal, para ser solucionado, cumpla las condiciones de Forma Estándar y Sistema Canónico.

La Forma Estándar incluye:

a) una Función Objetivo a optimizar

b) lado derecho de las restricciones con valor positivo

c) variables de decisión no negativas

d) las restricciones deben ser expresadas como igualdades.

Para transformar las restricciones en igualdades se deben incorporar las llamadas variables de holgura.

Una variable de holgura tiene coeficiente cero en la Función Objetivo. Se suman en restricciones del Tipo ≤ y se restan en restricciones del Tipo ≥. En términos matemáticos, expresan la diferencia entre el lado izquierdo y el lado derecho de las restricciones. Al igual que las variables de decisión deben ser mayores o iguales a cero.

En términos del modelo representan la cantidad de recurso no utilizado con relación a un máximo disponible

(Parte ociosa de los recursos).

Cuando la restricción es de una condición o requerimiento, representan la cantidad de esa condición o requerimiento que se obtiene por encima de un mínimo o que se deja de tener con relación a un máximo.

El Sistema Canónico en un Modelo Lineal significa que debe existir una variable básica en cada restricción.

Esto permite obtener una primera solución posible que satisface todas las restricciones.

Una variable básica tiene coeficiente 1 positivo en una restricción y no existe en las demás.

Las variables de decisión (estructurales) del modelo y las variables de holgura pueden ser variables básicas. Cuando ninguna de ellas cumple con la condición de ser básica, se incorpora una variable como artificio matemático, para cumplir con el sistema canónico y a esa variable se le llama variable artificial.

Una variable artificial debe tener incorporado un coeficiente muy alto en la Función Objetivo, con signo negativo en maximización y con signo positivo en minimización. Con esto se logra que el procedimiento Simplex las elimine de la solución en las primeras iteraciones. Estas variables deben valer cero en la solución óptima del modelo.

Una Tabla Simplex es un resumen detallado de toda la información del modelo para trabajar más fácilmente con él. La siguiente tabla expresa cómo deben ser recogidos los datos para resolver el problema de programación lineal por el Método Simplex.

Procedimiento para solucionar un modelo de Programación Lineal con el Método Simplex y de la M.

FASE I: Preparar el modelo inicial para construir la tabla:

1) Transformar los términos independientes en positivos (multiplicando por -1).

2) Si en alguna restricción, hay un solo proceso que está contenida en ella sola, lo convertiremos en unitario (dividiendo por su coeficiente) y si no lo hago meteré una variable de holgura.

3) En las inecuaciones en las que encontramos ≤ introducimos una variable de holgura sumando.

4) En las inecuaciones en las que encontramos ≥ introducimos una variable de holgura restando y además una variable artificial sumando para que en dicha restricción haya un proceso unitario positivo.

5) En las igualdades se introduce una variable artificial sumando si en la misma no existe una variable unitaria positiva.

6) En toda restricción debe haber una variable unitaria positiva.

7) Las variables de holgura, a la hora de introducirlas en la función objetivo lo haremos siempre con coeficiente cero, y las variables artificiales se introducen con el coeficiente –m si estamos maximizando 0 m si estamos minimizando.

8) Igualar a cero la función objetivo

FASE II: Construir la tabla y resolver el algoritmo.

Paso 1: Construir la tabla del método Simplex y rellenamos la tabla con los coeficientes.

...