Solución Algebraica de un Problema de Programación Lineal

PROGRAMACIÓN LINEAL

Es un enfoque de solución de problemas elaborado para ayudar a tomar decisiones. Es un modelo matemático con una función objetivo lineal, un conjunto de restricciones lineales variables no negativas. En el ambiente de negocios actual, pueden encontrarse gran cantidad de aplicaciones.

La función objetivo define la cantidad que se va a maximizar o minimizar en un modelo de programación lineal. Las restricciones limitan o reducen el grado en que puede perseguirse el objetivo. Las variables son las entradas controlables en el problema.

Para resolver un problema de programación lineal es recomendable seguir ciertos pasos que son: 1. Entender el problema a fondo. 2. Describir el objetivo. 3. Describir cada restricción. 4. Definir las variables de decisión. 5. Escribir el objetivo en función de las variables de decisión. 6. Escribir las restricciones en función de las variables de decisión. 7. Agregar las restricciones de no negatividad.

TÉRMINOS CLAVE

Modelo Matemático Representación de un problema donde el objetivo y todas las condiciones de restricción se describen con expresiones matemáticas. Restricciones de no negatividad Conjunto de restricciones que requiere que todas las variables sean no negativas. Solución Factible Solución que satisface simultáneamente todas las restricciones. Región Factible Conjunto de todas las soluciones factibles. Variable de holgura Variable agregada al lado izquierdo de una restricción de "menos o igual que" para convertir la restricción en una igualdad. El valor de esta variable comúnmente puede interpretarse como la cantidad de recurso no usado. Forma Estándar Programación lineal en el que todas las restricciones están escritas como igualdades. La solución óptima de la forma estándar de un programa lineal es la misma que la solución óptima de la formulación original del programa lineal. Punto Extremo Desde el punto de vista gráfico, los puntos extremos son los puntos de solución factible que ocurren en los vértices o "esquinas" de la región factible. Con problemas de dos variables, los puntos extremos están determinados por la intersección de las líneas de restricción. Variable de Excedente Variable restada del lado izquierdo de una restricción de "mayor o igual que" para convertir dicha restricción en una igualdad. Generalmente el valor de esta variable puede interpretarse como la cantidad por encima de algún nivel mínimo requerido.

EJEMPLO DE UN PROBLEMA DE MAXIMIZACIÓN MÉTODO GRÁFICO Y ALGEBRAICO

RMC es una pequeña empresa que fabrica una variedad de productos basados en sustancias químicas. En un proceso de producción particular, se emplean tres materias primas para producir dos productos: un aditivo para combustible y una base para solvente. El aditivo para combustible se vende a compañías petroleras y se usa en la producción de gasolina y combustibles relacionados. La base para solvente se vende a una variedad de empresas químicas y se emplea en productos para limpieza en el hogar e industriales. Las tres materias primas se mezclan para fabricar el aditivo para combustible y la base para el solvente, tal como se muestra a continuación:

Ésta nos muestra que una tonelada de aditivo para combustible es una mezcla de 0.4 toneladas del material 1 y 0.6 toneladas del material 3. Una tonelada de la base para solvente es una mezcla de 0.5 toneladas del material 1, 0.2 toneladas del material 2 y 0.3 toneladas del material 3. La producción de RMC esta restringida por una disponibilidad limitada de las tres materias primas. Para el periodo de producción actual,RMC tiene disponibles las siguientes cantidades de materia prima:

Debido a los desechos y a la naturaleza del proceso de producción, los materiales que no se lleguen a usar en una corrida de producción no se pueden almacenar para las subsiguientes, son inútiles y deben desecharse. El departamento de contabilidad analizó las cifras de producción, asignó todos los costos relevantes y llegó a precios que, para ambos productos, producirían una contribución a la utilidad de $ 40 por cada tonelada de aditivo para combustible producida y $ 30 para cada tonelada producida de base para solvente. Ahora usaremos la programación lineal para determinar la cantidad de aditivo para combustible y la cantidad de base para solvente para producir a fin de maximizar la contribución a la ganancia total.

MÉTODO GRÁFICO

PASOS 1. Trasladar la información relevante del problema a una tabla

2. Describir el objetivo del problema, formular las restricciones y nombrar las variables Objetivo: Maximizar la contribución total a la ganancia. Restricciones: Material 1 <= 20 Material 2 <= 5 Material 3 <= 21 F = Cantidad de toneladas para aditivo para combustible por producir. S = Cantidad de toneladas para aditivo para solvente por producir 3. Formular la función objetivo MAX = 40F + 30S 4. Realizar el modelo matemático MAX = 40F +30S sujeto a: 0.4F+0.5S <= 20 Ecuación 1 0.2S <= 5 Ecuación 2 0.6F+0.3S <= 21 Ecuación 3 F,S >= 0 5. Reemplazar por 0 los valores de F y S en cada una de las ecuaciones En ecuación 1 Si F=0 entonces: 0.5S = 20 S = 20/0.5 S = 40 (F=0,S=40) Si S=0 entonces 0.4F = 20 F = 20/0.4 F = 50 (F=50,S=0) En ecuación 2 S = 5/0.2 S = 25 (F=0,S=25) En ecuación 3 Si F=0 entonces 0.3S = 21 S = 21/0.3 S = 70 (F=0,S=70) Si S=0 entonces 0.6F = 21 F = 21/0.6 F = 35 (F=35,S=0) 6. Graficar los puntos encontrados Para realizar la gráfica es necesario tomar en cuenta las siguientes recomendaciones: 1.Preparar una gráfica para cada restricción que muestre las soluciones que satisfagan la restricción. 2.Determinar la región factible identificando las soluciones que satisfacen simultáneamente todas las restricciones. 3.Trazar líneas de función objetivo que muestren los valores de las variables de decisión que producen valores especificados para la misma. 4.Mover líneas de función objetivo paralelas hacia valores mayores de la función objetivo hasta que un mayor movimiento sacaría a la línea por completo de la región factible. 5.Cualquier solución factible en la línea de función objetivo con el valor máximo encontrado por el procedimiento anterior es una solución óptima.

Del anterior gráfico podemos deducir que las lineas celestes representan cada una de las restricciones del problema, la línea roja es la función objetivo, la parte de la gráfica sombreada con puntos rojos respresenta el área factible y el punto blanco la solución óptima, a continuación veremos como llegamos a cada una de dichas conclusiones.

MÉTODO ALGEBRAICO

1. Obtener la solución óptima a. Se usan las ecuaciones 1 y 3 del problema: 0.4F+0.5S = 20 Ecuación 4 0.6F+0.3S = 21 Ecuación 5 b. Se despeja F de la ecuación 4 0.4F+0.5S = 20 0.4F = 20-0.5S F = 50-1.25S Ecaución 6 c. Se sustituye F en la ecuación 5 0.6F+0.3S = 21 0.6(50-1.25S)+0.3S = 21 30-0.75S+0.3S = 21 -0.45S = 21-30 -0.45S = -9 S = -9/-0.45 S = 20 d. Se sustituye S en la ecuación 6 F = 50-1.25S F = 50-1.25(20) F = 50-25 F = 25 Se puede observar en la gráfica que estos dos valores están representados por el punto blanco, lo cual quiere decir que esta es la solución óptima del problema. e. Sustituir los valores en la función objetivo MAX = 40F+30S MAX = 40(25)+30(20) MAX = 1,000 + 600 MAX = $ 1,600 En conclusión se deben producir 25 toneladas de combustible y 20 toneladas de base para aditivo para obtener una utilidad máxima de $ 1,600 Para encontrar la línea que atraviesa la solución factible (punto blanco) se iguala a 0 F y S en la función objetivo y se encuentran los valores: 40F+30S = 1,600 Si F es 0 entonces: 30S = 1,600 S = 1,600/30 S = 53.33 (F=0,S=53.33) SI S es 0 entonces: 40F = 1,600 F = 1,600/40 F = 40 (F=40,S=0) Como se puede observar estos puntos estan representados por la línea celeste C3 y es la que atraviesa la solución óptima.

MÉTODO SIMPLEX

El algoritmo simplex está diseñado para localizar la solución óptima concentrándose en un número seleccionado de las soluciones básicas factibles del problema. Siempre empieza en una solución básica factible y después trata de encontrar otra solución básica factible que mejorará el valor del objetivo. Los cálculos para producir la nueva solución básica incluyen dos tipos: 1. Renglón pivote: Nuevo renglón pivote = renglón pivote actual / elemento pivote 2. Todos los demás renglones, incluyendo z: Nuevo renglón = (renglón actual) – (su coeficiente de la columna pivote) x (nuevo renglón pivote)

EJEMPLO DE MAXIMIZACIÓN UTILIZANDO EL MÉTODO SIMPLEX

Continuando con el problema anterior los pasos para resolver el problema por el método simplex son: 1. Expresar el problema en forma estándar Max 40F + 30S + S1 + S2 + S3 0.4F +0.5S + S1 = 20 0.2S + S2 = 5 0.6F +0.3S +S3 = 21 F,S,S1,S2,S3 >= 0 2. Obtener el renglón z que consiste en convertir al función objetivo en valores negativos. Max z = 40F+30S+S1+S2+S3 z = -40F-30S = O 3. Resumir la forma estándar en una tabla simplex

4. Se encuentran las intersecciones de la primera variable (la más negativa) para determinar el renglón pivote. En este caso se toma la columna donde se encuentra el -40 y cada uno de los valores de la solución se divide dentro de los valores de dicha columna, escogiendo el menor valor y toda esa fila se convertirá en la fila pivote como se puede observar en la siguiente tabla:

5. Se hacen los cálculos correspondientes a. La nueva fila pivote es la S3 el objetivo es convertir el valor de 0.6 en 1 para lo cual se divide toda la fila dentro de 0.6 y se coloca en la nueva tabla. b. El resto de valores que se encuentran arriba o abajo de 0.6 deben convertirse en 0. Para este caso se desea convertir el 0.4 en 0 por lo cual se convierte el 0.4 en negativo se multiplica por el valor correspondiente en la nueva fila pivote que es 1 y se le suma el valor de esa posición en la tabla antigua que en este caso es 0.4 en resumen (-0.4*1+0.4 = 0) y asi sucesivamente con cada una de las filas:

6. Como no se tienen todavía las variables de z en positivo, entonces hay que repetir los pasos 4 y 5 hasta que todos los valores de z sean positivos:

Como se puede observar en la tabla anterior todos los valores de z son positivos, lo cual quiere decir se ha llegado a encontrar la solución óptima del problema que es producir 20 toneladas de aditivo para combustible y 25 toneladas de base para solvente para obtener una ganancia máxima de $ 1,600*. * Si observa se obtuvieron los mismos resultados que el método gráfico y algebraico anteriormente descritos

EJEMPLO DE UN PROBLEMA DE MINIMIZACIÓN

M & D Chemicals produce dos productos que se venden como materias primas a compañías que fabrican jabones para baño y detergentes para ropa. Basado en un análisis de los niveles de inventario actuales y la demanda potencial para el mes siguiente, la gerencia de M & D ha especificado que la producción combinada para los productos A y B debe ser en total al menos 350 galoes. Por separado, también debe satisfacerse un pedido de un cliente importante de 125 galones del producto A. El producto A requiere dos horas de procesamiento por galón, mientras el producto B requiere una hora de procesamiento por galón, y para el siguiente mes se dispone de 600 horas de tiempo de procesamiento. El objetivo de M & D es satisfacer estos requerimientos con un costo total de producción mínimo. Los costos de producción son $2 por galón para el producto A y $3 por galón para el producto B. Para encontrar el calendario de producción de costo mínimo, formularemos el problema de M & D Chemicals como un programa lineal. Siguiendo un procedimiento parecido al usado para el problema RMC, primero definimos las variables de decisión y la función objetivo para el problema. Sea A = Cantidad de galones del producto A B = Cantidad de galones del producto B Debido a que los costos de producción son $ 2 por galón para el producto A y $ 3 por galón para el producto B, la función objetivo que corresponde a la minimización del costo total de producción puede escribirse como: Min 2A+3B A continuación consideramos las restricciones impuestas al problema de M & D Chemicals. Para satisfacer la demanda del cliente importante de 125 galones del producto A, sabemos que A debe ser al menos 125, Por tanto, escribimos la restricción 1A >= 125 Debido a que la producción combinada para ambos productos debe ser el total al menos 350 galones, podemos escribir la restricción 1A+1B >= 350 Por último, la limitación en el tiempo de procesamiento disponible de 600 horas significa que necesitamos agregar la restricción: 2A+1B <= 600 Después de agregar las restricciones de no negatividad, tenemos el siguiente programa lineal para el problema de M & D Chemicals: Min 2A+3B Sujeto a: 1A >= 125 1A + 1B >= 350 2A + 1B <= 600 A,B >= 0 Debido a que el modelo de programación lineal sólo tiene dos variables de decisión puede usarse el procedimiento de solución gráfica para encontrar las cantidades de producción óptimas. El método gráfico para este problema, como en el problema de RMC, requiere que primero tracemos la gráfica de las líneas de restricción para encontrar la región factible. Al trazar cada línea de restricción por separado y luego verificar los puntos en cada lado de la línea, pueden identificarse las soluciones que satisfacen cada restricción. Al combinar las soluciones que satisfacen cada restricción en la misma gráfica obtenemos la región factible.

MÉTODO GRÁFICO

PASOS 1. Trasladar la información relevante del problema a una tabla

2. Describir el objetivo del problema, formular las restricciones y nombrar las variables Objetivo: Satisfacer los requerimientos con un costo mínimo. Restricciones: 1. Producir para el cliente 125 gal. de A 2. Producción combinada 350 gal. 3. 2 horas para producir A por cada B contando en total con 600 horas A = Cantidad de galones del producto A. B = Cantidad de galones del producto B. 3. Formular la función objetivo MIN = 2A + 3B 4. Realizar el modelo matemático MIN = 2A + 3B sujeto a: 1A >= 125 Ecuación 1 1A+1B >= 350 Ecuación 2 2A+1B <= 600 Ecuación 3 A,B >= 0 5. Reemplazar por 0 los valores de A y B en cada una de las ecuaciones En ecuación 1 Si B=0 entonces: (A=125,B=0) En ecuación 2 Si A es 0 1B = 350 (A=0,B=350) Si B es 0 1A = 350 (A=350,B=0) En ecuación 3 Si A=0 entonces 1B = 600 (A=0,B=600) Si B=0 entonces 2A = 600 A = 600/2 A = 300 (A=300,B=0) 6. Graficar los puntos encontrados Para realizar la gráfica es necesario tomar en cuenta las siguientes recomendaciones: 1.Preparar una gráfica para cada restricción que muestre las soluciones que satisfagan la restricción. 2.Determinar la región factible identificando las soluciones que satisfacen simultáneamente todas las restricciones. 3.Trazar líneas de función objetivo que muestren los valores de las variables de decisión que producen valores especificados para la misma. 4.Mover líneas de función objetivo paralelas hacia valores más pequeños de la función objetivo hasta que un movimiento mayor a la línea por completo de la región factible. 5.Cualquier solución factible en la línea de función objetivo con el valor más pequeño es una solución óptima.

Del anterior gráfico podemos deducir que las lineas celestes representan cada una de las restricciones del problema, la línea roja es la función objetivo, la parte de la gráfica sombreada con puntos rojos respresenta el área factible y el punto blanco la solución óptima, a continuación veremos como llegamos a cada una de dichas conclusiones.

MÉTODO ALGEBRAICO

1. Obtener la solución óptima a. Se usan las ecuaciones 2 y 3 del problema: 1A+1B = 350 Ecuación 4 2A+1B = 600 Ecuación 5 b. Se despeja A de la ecuación 4 1A=350-1B A=350-1B Ecuación 6 c. Se sustituye A en la ecuación 5 2(350-1B)+1B=600 700-2B+1B=600 -2B+1B=600-700 -1B=-100 B=-100/-1 B=100 d. Se sustituye B en la ecuación 6 A=350-1B A=350-1(100) A=350-100 A=250 Se puede observar en la gráfica que estos dos valores están representados por el punto blanco, lo cual quiere decir que esta es la solución óptima del problema. e. Sustituir los valores en la función objetivo MIN = 2A+3B MIN = 2(250)+3(100) MIN = 500+300 MIN = $800 En conclusión Se deben producir 250 galones del producto A y 100 galones del producto B para obtener un costo mínimo de $ 800 Para encontrar la línea que atraviesa la solución factible (punto blanco) se iguala a 0 A y B en la función objetivo y se encuentran los valores: 2A+3B = 800 Si A es 0 entonces: 3B=800 B=800/3 B=266.67 SI B es 0 entonces: 2A=800 A=800/2 A=400 Como se puede observar estos puntos estan representados por la línea celeste C3 y es la que atraviesa la solución óptima.

MÉTODO SIMPLEX

Se puede dividir el procedimiento del método simplex en dos fases: FASE I: Se expresa el problema en forma estándar y se añaden las variables artificiales necesarias a las restricciones. En seguida se encuentra una solución básica de las ecuaciones resultantes , por medio del método simplex, que minimice la suma de las variables artificiales. FASE II: Se utiliza la solución factible obtenida en la fase I como una solución factible inicial para el problema original, por medio del método simplex. Nuevo renglón Z= renglón Z anterior + A * Renglón A + B * Renglón B PASOS 1. Escribir el problema en forma estándar Si la restricción es mayor o igual los valores de S seran negativos por el contrario si la restricción es menor o igual serán positivos y por cada variable S se agrega una variable R positiva excepto en la tercera ecuación para este caso. Min 2A+3B+S1+S2+S3 1A -S1+R1 =125 1A+1B -S2+R2=350 2A+1B +S3=600 A,B,S1,S2,S3 >=0 2. Escribir el problema en una tabla simplex, usando el renglón r y no el z

3. Obtener el nuevo renglón r Nuevo renglón r = renglón actual + (+R1) * Renglón S1 + (+R2) * Renglón S2

4. Continuar con el simplex hasta obtener nuevamente el primer renglón r

5. Quitar las columnas R1 y R2 y agregar la función objetivo

6. Obtener el nuevo renglón z Nuevo renglón z = renglón anterior z +(+A) * renglón S1 +(+B)*renglón S2

7. Continuar con el simplex hasta que todos sean negativos

En conclusión se deben producir 250 galones del producto A y 100 galones del producto B para obtener un costo mínimo de $ 800*. Nótese que se llegaron a los mismos resultados que el método algebraico