Programación lineal (método gráfico, simplex y variable artificial)

Programación lineal (método gráfico, simplex y variable artificial)

Método gráfico.

Mostramos un ejemplo de programación lineal en la cual se resuelve mediante el método gráfico con los pasos siguientes:

Una ensambladora de computadoras fabrica 2 tipos diferentes de modelos. El modelo económico requiere 1 hora de armado y seis centímetros cuadrados de plástico especial. El modelo de lujo requiere 2 horas de armado y cuatro centímetros cuadrados de plástico especial. Las ganancias que deja una computadora económica son 500 pesos, una computadora de lujo son 4000 pesos. Se venderán todas las unidades producidas, pero de acuerdo a la planificación de disponibilidad que son 8 horas diarias y 24 centímetros cuadrados de plástico especial. ¿Cuál será la producción que deja la mayor ganancia?

Paso 1. Colocar datos en tabla tabular

Paso 2. Restricciones.

1. No se pueden utilizar más de 8 horas.
2. No se pueden utilizar 24 centímetros cuadrados de plástico especial.
3. X y Y es decir el número de modelo económico y de lujo no deben ser negativos.

Paso 3. Ecuaciones con restricciones

          x + 2y ≤ 8

        6x + 4y ≤ 24

Paso 4. Procedimiento Método grafico

• Primera ecuación x + 2y = 8

Se obtiene el valor de y cuando x = 0

x + 2y = 8

0 + 2y = 8        despejo y = 8/2         y=4 se forma el primer par de puntos en términos de (x, y)                                 punto     A (0, 4)

Se obtiene el valor de x cuando y = 0

x + 2y = 8

x + 2(0) = 8        despejo x = 8                 x=8 se forma el segundo par de puntos en términos de (x, y)                                 punto     B (8, 0)

• Segunda ecuación 6x + 4y = 24

Se obtiene el valor de y cuando x = 0

6x + 4y = 24

6(0) + 4y = 24        despejo y = 24/4         y=6 se forma el primer par de puntos en términos de (x, y)                                 punto     C (0, 6)

Se obtiene el valor de x cuando y = 0

6x + 4y = 24

6x + 4(0) = 24        despejo x = 24/6         x=4 se forma el segundo par de puntos en términos de (x, y)                                 punto     D (4, 0)

Paso 5. Grafica

Se unen los puntos anteriores formando dos lineal punto A con B y punto C con D.

[pic 1]

[pic 2]

Paso 6. Conclusión

Observamos la intersección de las dos líneas se obtiene el par de puntos (2,3). Mostrando que para x = 2, y = 3 por lo tanto concluimos:

Que debemos de producir:

• 2 computadoras de modelo económico y
• 3 computadoras de modelo de lujo

Para sacar la ganancia máxima se sustituye en la ecuación:

Máxima G = 500x + 4000y

             G= 500(2) + 4000(3) = 1000 + 12000 = 13000 pesos.

Método simplex.

El método simplex es un procedimiento algebraico que determina una solución óptima de resultados a un planteamiento de un problema con las limitaciones o restricciones del mismo.

Una de las características principales en el método simplex es introducir las holguras en las diferentes restricciones para poder seguir un proceso en busca de una solución óptima al planteamiento de cada problema.

Este análisis del método simplex se especifica en el siguiente ejemplo, con el objetivo de analizar y resolver de manera efectiva cualquier problema de maximización o minimización.

Tomamos el mismo ejemplo del Método gráfico, se resuelve mediante el método simplex con los pasos siguientes:

Paso 1. Colocar datos en tabla tabular

Paso 2. Restricciones.

1. No se pueden utilizar más de 8 horas.
2. No se pueden utilizar 24 centímetros cuadrados de plástico especial.
3. X y Y es decir el número de modelo económico y de lujo no deben ser negativos.

Paso 3. Ecuaciones con restricciones

          x + 2y ≤ 8

        6x + 4y ≤ 24

Paso 4. Procedimiento Método Simplex

1. Se colocan las holguras en cada ecuación de las restricciones y ecuación de maximizar las ganancias, teniendo:

0z +    1x1 +      2x2 +  1x3 + 0x4=  8

0z +    6x1 +      4x2 +  0x3 + 1x4=24

1z -  500x1 - 4000x2 +  0x3 + 0x4=  0

1. Se coloca en tabla tabular solo coeficientes numéricos

1. Se observa columnas de x1 y x2 y se toma columna de menor valor en fila de z, la columna seria x2,   pero en este caso observamos que la columna x1 se tiene la unidad se tomará la columna x1. Y tomaremos la fila de dividir LD entre cada valor de la fila x3 y x4 se tiene 8/1 = 8 y 24/6 = 4, por lo tanto se toma la fila de menor valor y seria fila x4, pero en este caso observamos que la fila x3 se tiene la unidad se tomará la fila x3. Como se muestra en la siguiente tabla:

[pic 5]

...