Programación Lineal

Saludos a todos mis estimados lectores, este espacio está destinado para dar conocimiento acerca de la Programación Lineal, desde un punto de vista reflexivo, introduciendo ejemplos, anécdotas, imágenes y vídeos para una fácil comprensión.

La Programación Lineal nació como disciplina independiente poco antes de 1950, y desde ese momento, ha contribuido en gran parte en la maximización de los procesos industriales, minimización de costos y al uso adecuado de los recursos en los servicios y en la administración.

Caracterizada por ser una de las pocas disciplinas modernas que incluye especialmente la matemática con un gran número de aplicaciones en el campo de la economía y administración.

Distintos profesionales, como ingenieros, economistas, políticos y militares, con frecuencia se afrontan a situaciones en las que se debe tomar decisiones con la finalidad crea una máxima utilidad de los recursos disponibles o, minimizar los daños si ocurren eventos inesperados, por lo que, la planificación de la producción de una empresa debe tener como mira fundamental, la mayor afluencia posibles de ingresos  para la misma, minimizando los costes que deben invertirse.

La toma de decisiones busca el máximo o el mínimo de una magnitud llamada "función objetivo", la cual depende de las variables de decisión, encargada de la medición de utilidad o pérdida asociada a cada posible decisión a través de las inecuaciones relativas a las variables recibiendo el nombre de restricciones de desigualdad, donde cada posible asignación de valores a las variables que satisfaga las restricciones, se convierte en una posible solución factible que suele llamarse programa de producción. La función objetivo permite la comparación de la utilidad  que reporta con cada una de las soluciones factibles.

Se puede decir que no existe en la actualidad una rama de la actividad económica en las sociedades contemporáneas que no se encuentre organizada mediante las técnicas de Programación Lineal, ya que es el sistema más efectivo que permite la optimización de problemas con millones de variables y centenares de restricciones.

Por lo que la Programación Lineal referencia a un modelo matemático compuesto de algoritmos por el cual se resuelven escenarios reales en las que se busca la identificación y resolución de problemas en el ambiente de negocios, para incrementar la productividad respecto a recursos (principalmente los limitados y costosos), aumentando los beneficios.

El objetivo vital de la Programación Lineal se encuentra en la optimización, es decir, maximizar o minimizar funciones lineales en varias variables reales con restricciones lineales (sistemas de inecuaciones lineales), optimizando una función objetivo también lineal.

• La función objetivo determina 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.

Los pasos para resolver los casos de programación lineal 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.

Dentro de la Programación Lineal encontraremos:

•   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 ámbito 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.

Los resultados y proceso de optimización se convierten en un respaldo cuantitativo de las decisiones frente al as situaciones planteadas, tomando en cuenta diversos criterios administrativos como:

•     Hechos.
•     Experiencias.
•     Intuición.
•     Autoridad.

Ejemplos de Programación Lineal:

1-" El Problema"

La fábrica de Hilados y Tejidos "SALAZAR" requiere fabricar dos tejidos de calidad diferente T y T’; se dispone de 500 Kg de hilo a, 300 Kg de hilo b y 108 Kg de hilo c. Para obtener un metro de T diariamente se necesitan 125 gr de a, 150 gr de b y 72 gr de c; para producir un metro de T’ por día se necesitan 200 gr de a, 100 gr de b y 27 gr de c.

El T se vende a $4000 el metro y el T’ se vende a $5000 el metro. Si se debe obtener el máximo beneficio, ¿cuántos metros de T y T’ se deben fabricar?

"El problema", se recomienda leer en más de una ocasión para facilitar el reconocimiento de las variables, además es muy recomendable la elaboración de tablas o matrices que faciliten una mayor comprensión del mismo.

PASO 1: "Formular el Problema"

Para realizar este paso partimos de la pregunta central del problema.

¿Cuántos Metros de T y T’ se Deben Fabricar?

Y la formulación es:

“Determinar la cantidad de metros diarios de tejido tipo T y T’ a fabricar teniendo en cuenta el óptimo beneficio respecto a la utilidad”.

PASO 2: "Determinar las Variables"

Basándonos en la formulación del problema nuestras variables de decisión son:

XT: Cantidad de metros diarios de tejido tipo T a fabricar

XT’: Cantidad de metros diarios de tejido tipo T’ a fabricar 

PASO 3: Determinar las Restricciones del Problema

En este paso determinamos las funciones que limitan el problema, estas están dadas por capacidad, disponibilidad, proporción, no negatividad entre otras.

De disponibilidad de materia prima:

0,12XT + 0,2XT’ <= 500              Hilo “a”

0,15XT + 0,1XT’ <= 300              Hilo “b”

0,072XT + 0,027XT’ <= 108        Hilo “c”

De no negatividad

XT,XT’ >= 0

PASO 4: Determinar la función Objetivo

En este paso es de vital importancia establecer el contexto operativo del problema para de esta forma determinar si es de Maximización o Minimización. En este caso abordamos el contexto de beneficio por ende lo ideal es Maximizar.

Función Objetivo

ZMAX = 4000XT + 5000XT’

2- Ejemplo de un Problema de  Maximización de P.L, utilizando el método algebraico, método gráfico y método simplex.

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 representa 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 están 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)

Aspectos Fundamentales Del Método Simplex

1. Encuentra una solución óptima
2. Es un método de cambio de bases
3. Requiere que la función objetivo sea expresada de tal forma que cada variable básica tenga como coeficiente 0
4. Requiere que cada variable básica aparezca en una y solamente una ecuación de restricción.

Dualidad

Asociado a cada problema de Programación Lineal existe un llamado dual, de hecho al de Programación Lineal se le llama primal. La forma general del problema dual es la siguiente:

Optimizar Z = b1Y1+ b1Y2 +….+ bn Yn). 

Función objetivo.

Sujeta a a11Y1+ a11Y2 +…..+ am1Y1) £ C1

a21Y1+ a22Y2 +…..+ am2Y2) £ C1

Restricciones

.

a1mY1+ a2mY2 +…..+ amnYm) £ Cn

Para facilitar la comprensión de lo anterior considérese el diagrama siguiente:

Primal	Dual
C1……. Cn (1) a11 b1 (2) (3) am1 bm	b1……. bm (3) (2) a11……. am1 C1 (1) C2
Variables X1……. Xn	Variables Y1……. Ym

El problema dual tiene las siguientes características:

• El el objetivo de la optimización es contrario al del primal.
• Las inecuaciones de restricción son inversas.
• La solución del dual es la misma que la del primal.

Desde el punto de vista económico, el significado de las variables duales es de gran interés para los gerentes, ya que representan el valor por unidad de recurso adicional, lo cuál permite tomar decisiones sobre donde invertir para incrementar las utilidades.

Análisis de Sensibilidad

El objetivo del análisis de sensibilidad es determinar la influencia de ciertos valores en la solución óptima, que nos permite la interpretación razonable de los resultados obtenidos. En muchos casos la información lograda por la aplicación del análisis de sensibilidad puede ser más importante y más informativa que simple resultado obtenido en la solución óptima.

El análisis deviene del resultado de los cambios en:

• Los coeficientes en la función objetivo.
• Los términos independientes en las restricciones.

Estableciendo una relación entre la programación lineal y experiencias previas, puedo decir que de cierta manera la he aplicado en mi trabajo como ayudante farmacéutico a través de la disminución de costos en la adquisición de materiales para la creación de formulas magistrales y el aumento de la productividad con un mínimo de recursos necesarios, ya que es importante encontrar materiales a bajo costos pero sin que los mismo afecten la calidad del producto y a su vez es de vital importancia el garantizar una máxima producción para poder satisfacer al público en generar y así aumentar las ganancias de la empresa en un linea temporal a medio y largo plazo, estableciendo metas claras. 

Todo lo anteriormente expuesto permite decir que la programación lineal es de vital importancia para la parte de maximización o minimización de costos, es decir, cumple un factor primordial en el mundo económico,  ya que busca la identificación y resolución de problemas en el ambiente de negocios, para incrementar la productividad respecto a recursos (principalmente los limitados y costosos), aumentando los beneficios.

Sin más que hacer referencia, quedo de uds hasta una nueva oportunidad.

Atentamente, De Jesús C, Daniel A.

Referencias Bibliográficas

• Anónimo. (2010). Origen de la Programación Lineal. Visitado : (17 de Julio de 2014) Disponible en: http://thales.cica.es/rd/Recursos/rd98/Matematicas/29/origen.html

• Dantzig, G.B. (1991), "Linear Programming", en History of Mathematical Programming (J. Lenstra et al., Eds.), North-Holland, pp. 19-31.

• Kantorovich, L.V. (1959), "Métodos Matemáticos de Planificación y Organización de la producción", en El uso de las Matemáticas en la Economía (V.S. Nemchinov, Ed.), Mezhkniga, en ruso. Traducción al español, Labor, 1973, pp. 273-380.

• Riveral, Olman. (2008). Origen de la Programación Lineal. Visitado : (17 de Julio de 2014) Disponible en: http://thales.cica.es/rd/Recursos/rd98/Matematicas/29/origen.html