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)

Método simplex

El Método Simplex supone que las variables son continuas por lo tanto puede dar soluciones no discretas. Sin embargo se puede tener casos prácticos donde la variable tenga un sentido real, si solo toma valores enteros.

Ejemplo explicativo para método simplex:

Maximizar Z = f(x,y) = 3x + 2y

sujeto a: 2x + y ≤ 18

2x + 3y ≤ 42

3x + y ≤ 24

x ≥ 0 , y ≥ 0

Se consideran las siguientes fases:

1. Convertir las desigualdades en igualdades

Se introduce una variable de holgura por cada una de las restricciones del tipo ≤, para convertirlas en igualdades, resultando el sistema de ecuaciones lineales:

2x + y + r = 18

2x + 3y + s = 42

3x +y + t = 24

2. Igualar la función objetivo a cero

-3x - 2y + Z = 0

3. Escribir la tabla inicial simplex

En las columnas aparecerán todas las variables básicas del problema y las variables de holgura/exceso. En las filas se observan, para cada restricción las variables de holgura con sus coeficientes de las igualdades obtenidas, y la última fila con los valores resultantes de sustituir el valor de cada variable en la función objetivo, y de operar tal como se explicó en la teoría para obtener el resto de valores de la fila:

Tabla 1

4. Condición de parada

Cuando en la fila Z no existe ningún valor negativo, se ha alcanzado la solución óptima del problema. En tal caso, se ha llegado al final del algoritmo. De no ser así, se ejecutan los siguientes pasos.

5. Condición de entrada y salida de la base

A. Primero debemos saber la variable que entra en la base. Para ello escogemos la columna de aquel valor que en la fila Z sea el menor de los negativos. En este caso sería la variable x (P1) de coeficiente - 3.

Si existiesen dos o más coeficientes iguales que cumplan la condición anterior (caso de empate), entonces se optará por aquella variable que sea básica.

La columna de la variable que entra en la base se llama columna pivote (En color verde).

B. Una vez obtenida la variable que entra en la base, estamos en condiciones de deducir cual será la variable que sale. Para ello se divide cada término independiente (P0) entre el elemento correspondiente de la columna pivote, siempre que el resultado sea mayor que cero, y se escoge el mínimo de ellos.

En este caso:

18/2 [=9], 42/2 [=21] y 24/3 [=8]

Si hubiera algún elemento menor o igual a cero no se realiza dicho cociente, y caso de que todos los elementos de la columna pivote fueran de ésta condición tendríamos una solución no acotada y terminaríamos el problema.

El término de la columna pivote que en la división anterior dé lugar al menor cociente positivo, el 3, ya que

...