EJEMPLOS DESARROLLADOS

EJEMPLO 1

Maximizar Z= 5X1+4X2
Sujeto a: X1+X2 ≤ 20
2X1+X2 ≤ 35
-3X1+X2 ≤ 12
X1≥0, X2≥0
Este problema de programación lineal se ajusta a la forma normal. La tabla simplex
inicial es:

El indicador mas negativo, -5, aparece en la columna x1. Por ello, x1 es la variable
entrante. El menor cociente es 17.5, de modo que, S2 es la variable saliente. El
elemento pivote es 2. Utilizando operaciones elementales sobre los renglones para
obtener un 1 en la posición del pivote y 0 en las demás posiciones de esa columna,
se tienen:

Variable Entrante

Obsérvese que en el lado izquierdo, x1 reemplazó a S2. Ya que -3/2 es el indicador

más negativo se debe continuar con el proceso. La variable entrante es ahora x2. El

menor cociente es 5. De modo que S1 es la variable saliente y ½ es el elemento

pivote. Utilizando operaciones elementales sobre renglones, se tiene:

En donde x2 reemplazo a S1 en el lado izquierdo. Como todos los indicadores son

no negativos, el valor máximo de Z es 95 y aparece cuando x2=5 y x1=15 (y S3=52,

S1=0, S2=0).

PASOS PARA EL DESARROLLO DEL METODO SIMPLEX

1. Elaborar la tabla simplex inicial.

Existen cuatro variables de holgura, S1, S2, S3, y S4; una para cada restricción.

2. Si todos lo indicadores del último renglón son no negativos, entonces Z tiene un

máximo cuando X1=0, X2=0 y X3=0. El valor máximo es 0. Si existen indicadores

negativos, localizar la columna en la que aparezca el indicador más negativo.

Esta columna señala la variable entrante.

3. Dividir cada uno de los elementos de la columna de b que se encuentran por

encima de la recta punteada entre el correspondiente elemento de la columna de

la variable entrante. Se debe realizar esta división solo en los casos en los que el

elemento de la variable que entra sea positivo.

4. encerrar en un círculo el elemento de la columna de la variable entrante que

corresponde al menor cociente del paso 3. Este es un elemento pivote. La

variable saliente es la que se encuentra al lado izquierdo del renglón del elemento

pivote.

5. Utilizar operaciones elementales sobre renglones para transformar la tabla en

otra tabla equivalente que tenga un 1 en donde se encuentra el elemento pivote y

0 en las demás posiciones de esa columna.

6. la variable entrante debe reemplazar a la variable saliente en el lado izquierdo de

esta nueva tabla.

7. si todos los indicadores de la tabla nueva son no negativos, ya se tiene una

solución óptima. El valor máximo de Z es el elemento del último renglón y la

última columna. Ocurre esto cuando las variables se encuentran del lado

izquierdo de la tabla son iguales a lo elementos correspondiente de la última

columna. Todas las demás variables son ceros. Si cuando menos uno de los

indicadores es negativo, se debe repetir el mismo proceso con la nueva tabla,

comenzando con el paso 2.

CONCEPTO

El método simplex fue desarrollado por George dantzig (1947) y es un método

algebraico que se utiliza para resolver problemas de programación lineal en un

número finito de pasos en una computadora. Este método establece una solución

factible y luego prueba si es óptima o no. Si no lo es busca una mejor solución y si

esta no es optima entonces repite el proceso hasta hallar una solución óptima.

A) INTRODUCIÓN

En los capítulos 1 y 2 de esta unidad vimos como resolver problemas de programación lineal a través del método gráfico y el método algebraico, surgen grandes limitaciones a la hora de trabajar con estos dos métodos, es decir que no es posible darle óptima solución a un problema. Esto se debe a que el método grafico no resulta práctico cuando el número de variables se aumenta a tres, y con más variables resulta imposible de utilizar. Por otra parte el método algebraico tarda demasiado tiempo aun para problemas de pocas variables y restricciones.

El mejor método para resolver un problema de programación lineal es el método

Simplex, ya que es un método de fácil aplicación, de tipo algorítmico y conduce a una eficiente solución del problema.

PROBLEMA DE INGENIERÍA EN SISTEMAS

EL PROBLEMA

La empresa COMPU TOTAL  Ltda. Dedicada a la fabricación de mesas de computadoras, ha ampliado su producción en dos líneas más. Por lo tanto actualmente fabrica mesas, sillas, mesas para la impresora y bibliotecas. Cada mesa requiere de 2 piezas rectangulares de 8 pines, y 2 piezas cuadradas de 4 pines. Cada silla requiere de 1 pieza rectangular de 8 pines y 2 piezas cuadradas de 4 pines, cada mesas para la impresora  requiere de 1 pieza rectangular de 8 pines, 1 cuadrada de 4 pines y 2 bases trapezoidales de 2 pines y finalmente cada biblioteca requiere de 2 piezas rectangulares de 8 pines, 2 bases trapezoidales de 2 pines y 4 piezas rectangulares de 2 pines. Cada mesa cuesta producirla $10000 y se vende en $ 30000, cada silla cuesta producirla $ 8000 y se vende en $ 28000, cada mesas para la impresora cuesta producirla $ 20000 y se vende en $ 40000, cada biblioteca cuesta producirla $ 40000 y se vende en $ 60000. El objetivo de la fábrica es maximizar las utilidades.

PASO 1: MODELACIÓN MEDIANTE PROGRAMACIÓN LINEAL

Las variables:
 
X₁ = Cantidad de mesas a producir (unidades)
X₂ = Cantidad de sillas a producir (unidades)
X₃ = Cantidad de mesas para la impresora a producir (unidades)
X₄ = Cantidad de bibliotecas a producir (unidades)

as restricciones:

 

2X₁ + 1X₂ + 1X₃ + 2X₄ <= 24               

2X₁ + 2X₂ + 1X₃ <= 20                     

2X₃ + 2X₄ <= 20                            

4X₄ <= 16                          

 

La función Objetivo:

 

Z_MAX = 20000X₁ + 20000X₂ + 20000X₃ + 20000X₄

PASO 2: CONVERTIR LAS INECUACIONES EN ECUACIONES

En este paso el objetivo es asignar a cada recurso una variable de Holgura, dado que todas las restricciones son "<=".

 

2X₁ + 1X₂ + 1X₃ + 2X₄ + 1S₁ + 0S₂ + 0S₃ + 0S₄ = 24               

2X₁ + 2X₂ + 1X₃ + 0X₄ + 0S₁ + 1S₂ + 0S₃ + 0S₄ = 20                             

0X₁ + 0X₂ + 2X₃ + 2X₄ + 0S₁ + 0S₂ + 1S₃ + 0S₄ = 20

0X₁ + 0X₂ + 0X₃ + 4X₄ + 0S₁ + 0S₂ + 0S₃ + 1S₄ = 16

 

De esta manera podemos apreciar una matriz identidad (n = 4), formado por las variables de holgura las cuales solo tienen coeficiente 1 en su respectivo recurso, por el ejemplo la variable de holgura "S1" solo tiene coeficiente 1 en la restricción correspondiente a el recurso 1.

 

La función objetivo no sufre variaciones:

 

Z_MAX = 20000X₁ + 20000X₂ + 20000X₃ + 20000X₄

PASO 3: DEFINIR LA SOLUCIÓN BÁSICA INICIAL

El Método Simplex parte de una solución básica inicial para realizar todas sus iteraciones, esta solución básica inicial se forma con las variables de coeficiente diferente de cero (0) en la matriz identidad.

 

1S₁ = 24               

1S₂  = 20                              

1S₃ = 20

1S₄  = 16

PASO 4: DEFINIR LA TABLA SIMPLEX INICIAL

Solución: (segundo término)= En esta fila se consigna el segundo término de la solución, es decir las variables, lo más adecuado es que estas se consignen de manera ordenada, tal cual como se escribieron en la definición de restricciones.

Cj = La fila "Cj" hace referencia al coeficiente que tiene cada una de las variables de la fila "solución" en la función objetivo.

Variable Solución = En esta columna se consigna la solución básica inicial, y a partir de esta en cada iteración se van incluyendo las variables que formarán parte de la solución final.

Cb = En esta fila se consigna el valor que tiene la variable que se encuentra a su derecha "Variable solución" en la función objetivo.

Zj = En esta fila se consigna la contribución total, es decir la suma de los productos entre término y Cb.

Cj - Zj =  En esta fila se realiza la diferencia entre la fila Cj y la fila Zj, su significado es un "Shadow price", es decir, la utilidad que se deja de recibir por cada unidad de la variable correspondiente que no forme parte de la solución.

 

Solución inicial:

PASO 5: REALIZAR LAS ITERACIONES NECESARIAS

Este es el paso definitivo en la resolución por medio del Método Simplex, consiste en realizar intentos mientras el modelo va de un vértice del poliedro objetivo a otro.

 

El procedimiento a seguir es el siguiente:

 

1. Evaluar que variable entrará y cual saldrá de la solución óptima:

2. El hecho de que una variable distinta forme parte de las variables solución implica una serie de cambios en el tabulado Simplex, cambios que se explicarán a continuación.

 

- Lo primero es no olvidar el valor del "a" correspondiente a la variables a entrar, en este caso el "a = 4".

Lo siguiente es comenzar a rellenar el resto de la tabla, fila x fila.

Se repite este procedimiento con las dos filas restantes, ahora se harán los cálculos correspondientes en el resto de las celdas.

De esta manera se culmina la primera iteración, este paso se repetirá cuantas veces sea necesario y solo se dará por terminado el método según los siguientes criterios.

- Continuamos con las iteraciones para lo cual tenemos que repetir los pasos anteriores.

En esta última iteración podemos observar que se cumple con la consigna Cj - Zj <= 0, para ejercicios cuya función objetivo sea "Maximizar", por ende hemos llegado a la respuesta óptima.

 

X₁ = 3

X₂ = 4

X₃ = 6

X₄ = 4

Con una utilidad de: $ 340000