La programación lineal

PROGRAMACIÓN LINEAL

La programación lineal es una técnica matemática, que consiste en una serie de métodos y procedimientos que permiten optimizar (maximizar o minimizar), una función lineal, las que se encuentran sujetas a determinaciones las que son conocidas como restricciones y que se expresan mediante un sistema de inecuaciones lineales.

Al maximizar una función, esta nos llevará al resultado de determinar la producción, por ejemplo, que es lo que debemos fabricar y en qué cantidades para que se obtenga el máximo beneficio, considerando las limitaciones tanto técnicas como humanas. Por otra parte, cuando minimizamos una función, tendremos como resultado los costos mínimos para producir.

La programación lineal tiene como objetivo principal ayudar en la toma de decisiones de manera óptima.

Planteamiento

Como mencionamos anteriormente resolver un problema de Programación Lineal consiste en optimizar una función que se encuentra sujeta a restricciones, entendiendo que optimizar es encontrar un valor que maximice o minimice la función, según el caso.

Lo primero es conocer los conceptos claves de Programación lineal, que se detallan a continuación:

• Función objetivo: Define la cantidad que se va a maximizar o minimizar en un modelo de programación lineal. La cual tiene varias variables.

• Restricciones: Representan condiciones que es preciso satisfacer. Sistema de Igualdades y Desigualdades (≤ o ≥), estas limitan o reducen el grado en que puede perseguirse el objetivo.

Existen dos tipos de restricciones:

Restricciones de no negatividad: Son aquellas que garantizan que ninguna variable de decisión sea negativa.

Restricciones estructurales: Reflejan factores como la limitación de recursos y otras condiciones que impone la situación del problema.

Ejemplo explicativo para programación lineal:

Una maquina produce dos tipos de productos A y B, para fabricarlos se necesita un tiempo de producción en máquinas y un acabado a mano que realizan los operarios. La venta del modelo A necesita 2 horas en las máquinas y 1/2 hora de trabajo a mano y produce un beneficio de $50.000. la venta del modelo B necesita 3 horas en las máquinas y 1/4 de hora de trabajo a mano y origina un beneficio de $43.000.

Se dispone de un total de 300 horas de trabajo en máquinas y 60 horas de trabajo a mano. Entre los dos tipos de productos deben fabricarse por lo menos 90. ¿Qué cantidad de cada tipo de producto deben fabricarse para que el beneficio sea máximo?

Productos Trabajo máquina (hora) Trabajo mano

(hora) Beneficio (pesos)

A x

2 1/2 50.000

B y

3 1/4 43.000

Total: 90 300 60 B(x,y)

Tenemos los datos ordenados en una tabla de doble entrada.

Maximizar B(x,y)= 50.000X + 43.000Y

Sujeto a 2X + 3Y ≤ 300

½ X + ¼ Y ≤ 60

X + Y ≥ 90

X ≥ 0

Y ≥ 0

Luego representamos cada inecuación, en el plano cartesiano (lo que será explicado más detalladamente en el siguiente punto, “solución gráfica”) y posterior a esto debemos hallar los vértices de x e y.

Dichos vértices debemos reemplazarlo en la función objetivo, que recordamos que es:

B(x,y)= 50.000X + 43.000Y

B(0,90)= $3.870.000

B(0,100)= $4.300.000

B(90,0)= $ 4.500.000

B(120,0)= $6.000.000

B(105,30)= $6.540.000

Como nos solicitaban aquel resultado que maximiza el beneficio entonces debemos fabricar 105 productos tipo A y 30 productos tipo B para obtener el máximo beneficio que serían $6.540.000.

Solución gráfica

La solución gráfica solo aplica a problemas con dos variables de decisión y sin número de restricciones. Sin embargo, muestra adecuadamente los conceptos que nos ayudaran a entender claramente el problema de Programación Lineal.

A continuación mostraremos el comportamiento de las funciones lineales para entender como determinar los puntos óptimos.

Cambiamos el símbolo de desigualdad por el símbolo de igualdad y lo que obtenemos es una línea recta. Esta recta es fácil de graficar usando la técnica de intersección con los ejes: hacemos cero una de las variables y despejamos para la otra variable. De nuevo, la recta es la frontera de nuestro conjunto: por

Inspección, es fácil determinar el lado de dicha frontera que cumple la desigualdad.

Ejemplo explicativo para una solución gráfica:

Función objetivo

P= 3X + 2Y

Sujeto a

2X + Y ≤ 100

X + Y ≤ 80

X ≤ 40

X ≥ 0

Y ≥ 0

Cuando ya tenemos nuestro sistema de inecuaciones lo resolvemos, cada inecuación es una ecuación de una línea recta, en la primera representamos gráficamente 2x+y=100 y tomamos un punto en el plano cartesiano por ejemplo el (0,0) 2*0+0 es menor que 100, entonces sombreamos, el semiplano donde se encuentra el punto (0,0).

En el siguiente representamos la línea recta x+y=80, tomamos nuevamente el punto (0,0) y lo reemplazamos 0+0 es menos que 80 y lo representamos en el plano.

100 80

2x+y=100 x+y=80

50 80

2x+y≤100 x+y≤80

Región Factible

Se hace una intersección de los conjuntos de puntos que hemos encontrado (El punto C(20;60) se determina resolviendo el sistema 2x + y = 100 y x + y = 80; el punto D(20;60) se determina resolviendo el sistema 2x + y = 100 y x = 40).

E(0,80)

• D(20,60)

• C(40,20)

A(0,0) B(40,0)

...