La programación lineal es un método por el cual se optimiza un problema que puede ser expresado usando inecuaciones lineales. En estos problemas se tiene una función objetivo y diversas restricciones. Usando la programación lineal se puede encontrar el máximo o mínimo de la función a optimizar.
- Aquí te hablaremos de:
- Qué es la programación lineal.
- Sistemas de ecuaciones lineales y programación lineal.
- Problemas de los que se ocupa la programación lineal.
Ejemplo de un problema de programación lineal
Si quieres saber para qué nos sirve la programación lineal, mira el siguiente ejemplo:
Quieres saber cuánto puedes producir de madera en una plantación forestal. - Plantas cierta cantidad de árboles cada año.
- De cada año anterior, solo puedes talar ciertos árboles.
- Además de los árboles que plantas, solo algunos árboles maduran, para poder ser talados.
Debes maximizar la cantidad de árboles que puedes talar para producir \(X\) toneladas de madera al año. En este caso, necesitas una fórmula que contenga:
- Los árboles que se plantaron.
- Los que sobreviven.
- Los que crecen lo suficiente para ser talados.
Este problema —que implica encontrar el máximo de árboles que puedes talar, dependiendo de cuántos plantas y cuántos maduran/sobreviven— es un ejemplo de caso en el que puedes usar la programación lineal para resolverlo.
Introducción a la programación lineal
Como ya te mencionamos, la programación lineal es una herramienta usada para maximizar o minimizar cantidades en problemas matemáticos aplicados.
En estos problemas hay varias inecuaciones lineales. Podemos ver algunas en el ejemplo siguiente:
\[\left\{\begin{array}\, a_{11}x+a_{12}y+a_{13}z\geq b_1\\a_{21}x+a_{22}y+a_{23}z \leq b_2 \\ a_{31}x+a_{32}y+a_{33}z\geq b_3\end{array}\right.\]
En este caso, el problema tiene las siguientes características:
- Está compuesto de tres inecuaciones.
- Tiene tres incógnitas \((x, y, z)\).
- Hay cantidades \(b_1, b_2, b_3\) que deben ser mayores, menores o iguales que las ecuaciones lineales que contienen las variables \(x, y, z\).
Pasos para resolver un problema de programación lineal
Ahora te describiremos, de manera general, cómo se resuelve un problema en programación lineal. Lo haremos paso por paso:
1. Pensemos en que se tienen dos objetos que se producen. Los objetos se representan por las variables \(x\) y \(y\).
2. Supongamos que estos objetos implican cierto costo para ser producidos:
3. Además de esto, cada producto puede tardarse cierto tiempo en ser producido:
4. Se tiene, además, un tiempo limitado para producir ambos \(t\) y un presupuesto limitado para la producción en este tiempo \(C\).
Forma estándar
El problema anterior, explicado paso por paso, puede ser expresado de una manera sencilla. Esta manera es la forma estándar:
Optimiza: \(a_1x + b_1 y = P_t\)
Sujeto a:
\[a_1 (x) + b_1( y) \leq C\]\[a_1 (x) + b_1( y) \leq t\]
Aquí, optimizar puede ser minimizar o maximizar, dependiendo del caso.
Tipos de soluciones
Debido a que estos problemas son un caso aplicado de un sistema de ecuaciones lineales, tienen diversos tipos de soluciones, como:
- Soluciones únicas.
- Soluciones infinitas.
- Sin soluciones.
Resolución de problemas de programación lineal
Para solucionar un problema de programación lineal, se debe resolver el sistema de ecuaciones. Una vez que se tienen expresados los coeficientes y las restricciones, se procede a resolver el sistema. Sin embargo esto no es tan sencillo como en álgebra lineal.
Por ejemplo, en nuestro sistema de ecuaciones anterior, si usáramos igualdades, las soluciones serían:
\[x=20,y=-5\]
Pero, esto no puede ser posible, ya que la cantidad de objetos debe ser positiva.
Esto se debe a que, cuando se buscan soluciones de sistemas lineales, se necesita averiguar la intersección de ambas ecuaciones. En programación lineal, buscamos el área donde ambas funciones existen al mismo tiempo. Esto significa que las áreas se sobreponen una sobre la otra.
Si observamos la gráfica de ambas ecuaciones, tendríamos lo siguiente:
Fig. 1. Imagen de dos funciones lineales, su solución y el área donde se sobreponen.
Podemos observar varias cosas:
- La solución, si fueran igualdades, da como resultado un número negativo para \(y\). Como ya vimos, un número negativo no es posible, ya que tanto \(x\) como \(y\) deben ser positivos, porque ambos representan cantidades de algo.
- Las áreas se intersectan en un pequeño segmento cercano \((x=0;y=0)\).
- En esta superposición existen las soluciones al problema.
- Las soluciones solo pueden ser números enteros, ya que no hay medias cantidades de \(x\) o \(y\).
El óptimo, entonces, debe ser alguno de los puntos que se ve en la figura a continuación:
Fig. 2. Imagen de dos funciones lineales que representan un problema de programación lineal. El área donde se sobreponen y sus soluciones factibles que son los puntos magenta.
Explorando soluciones
Podemos explorar las soluciones que vemos en la figura 2:
Veamos el punto \(x=0, y=5\).
Si sustituimos estos valores en las ecuaciones originales, tenemos:
\[3·0+2·5 \leq 50\Rightarrow 10 \leq 50\]
\[2·0+4·5 \leq 20\Rightarrow 20 \leq 20\]
Si, además, la nueva constricción es que los valores son positivos o cero: \(x \leq 0 y \leq 0\).
Este punto es una solución, aunque aún no sabemos si es óptima.
Exploremos el otro límite de la solución, que es el punto \(x=10 y y=0\).
Al sustituir estos valores en las ecuaciones originales, tenemos:
\[3·10+2·0 \leq 50\Rightarrow 30 \leq 50\]
\[2·10+4·0 \leq 20\Rightarrow 20 \leq 20\]
Nuevamente, se cumplen las constricciones; pero, seguimos sin saber si esta solución es óptima.
A las soluciones que cumplen con las restricciones se les denomina soluciones factibles.
Soluciones óptimas
Ya que tenemos dos tipos de restricciones, nos queda introducir la tercera, que es la optimización. Aquí usamos lo que se denomina la función objetivo; esta función es: \(z=50x+20y\).
El óptimo, o solución óptima, es la solución para la cual el valor de \(z\) es el mismo que el valor que toma sobre la razón de soluciones factibles.
- Por ejemplo: si se busca minimizar la función objetivo, el valor que haga a la función objetivo igual que el valor mínimo que puede tomar en el área factible será el óptimo.
- Por ejemplo, si se busca maximizar función objetivo, el valor que haga a la función objetivo igual que el valor máximo que puede tomar en el área factible será el óptimo.
Número de soluciones
La soluciones en un problemas de programación lineal pueden ser finitas; es decir, las podemos contar. Esas soluciones pueden ser:
- Básicas.
- Factibles.
- Óptimas.
Ya te hemos hablado de las soluciones factibles y las óptimas. Entonces, ¿cuáles son las soluciones básicas?
Las soluciones básicas son aquellas que se encuentran en los vértices de las áreas donde se solapan las funciones.
Por ejemplo, las soluciones que exploramos \(x=10, y=0\) y \(x=0, y=5\) son soluciones básicas.
Problemas en programación lineal
Los problemas en programación lineal son, básicamente, de dos tipos: maximizar o minimizar cantidades. Para poder ver más sobre estos problemas, empezaremos con secciones dedicadas a los problemas clásicos que se abordan en programación lineal.
Ejemplo del problema de transporte
En el problema del transporte se tiene una función que debe optimizar el transporte de ciertos productos a ciertos puntos; en estos puntos existe una demanda de los productos.
Veamos cómo desarrollamos otro ejemplo de la misma manera:
Se tiene cierto número de fábricas \( (a,b) \). Estas fábricas deben abastecer un número de centros comerciales \((A, B, C)\). El transporte de los productos tiene cierto precio fijo entre la fábrica y los centros comerciales. Además de esto, cada centro comercial \((A,B,C)\) tiene cierta demanda del producto \(x\).Entonces: El costo de transportar el producto de la fábrica \(a\) a los centros comerciales \((A, B, C)\) es \((2, 3, 1)\). Mientras que el costo de transportar el producto \(x\) desde \(b\) hasta los centros comerciales \((A, B, C)\) es \((5, 6, 2)\). Aquí la función a minimizar ( también conocida como función objetivo) es el coste total:\[z=2x_{11} + 3x_{12} + 1x_{13}+ 5x_{21}+6x_{22}+2x_{23}\]Esta función se expresa de este modo, ya que la suma del costo es el costo total de enviar \(x\) desde \(a\) y \(b\) hasta los centros comerciales \((A, B, C)\).Esto lo podemos ver en la siguiente tabla:
Tabla 1. Costos de envío del producto \(x\) a cada uno de los centro comerciales.
Ahora, podemos poner algunas restricciones.
Primero, la demanda de \(x\) en todas las tiendas es \(200, 700, 250\) para \((A, B, C)\).
Segundo, la demanda es igual a la producción. Aquí \(a\) produce \( 600\) unidades y \(b\) produce \(650\) unidades.Lo siguiente es una restricción matemática, que significa que las soluciones deben ser positivas; no podemos tener un precio de envío negativo, por ejemplo.\[x_{ij}>0\]Las siguientes restricciones son acerca de la demanda y la oferta. En este caso, lo que se consume y envía a cada centro comercial no puede sobrepasar lo que se consume en los centros comerciales:\[x_{11}+ x_{12} + x_{13} \leq 600 \]\[ x_{21}+x_{22}+x_{23} \leq 650 \]Las últimas restricciones son aquellas de los productos vendidos en cada centro comercial. Por ejemplo: El centro comercial \(A\) debe de ser \(x_{11}+x_{12}=200\). El centro comercial \(B\) debe de ser \(x_{11}+x_{12}=700\). El centro comercial \(C\) debe de ser \(x_{11}+x_{12}=250\).De este modo, se tiene un problema en el que las restricciones están expresadas en forma de ecuaciones lineales. En este caso, lo que se puede buscar es minimizar el costo o los valores para los cuales:La función objetivo: \(z=2x_{11} + 3x_{12} + 1x_{13}+ 5x_{21}+6x_{22}+2x_{23}\) es mínima, dadas las restricciones:\[x_{ij}>0\]\[x_{11}+ x_{12} + x_{13} \leq 600 \]\[ x_{21}+x_{22}+x_{23} \leq 650 \] Venta en el centro comercial \(A\) debe de ser \(x_{11}+x_{12}=200\). Venta en el centro comercial \(B\) debe de ser \(x_{11}+x_{12}=700\). Venta en el centro comercial \(C\) debe de ser \(x_{11}+x_{12}=250\).
Problema de la producción
Otro problema clásico es el problema de la producción. En este, lo que se requiere es que se minimice el precio de la producción, de un producto \(x\) dadas ciertas restricciones.
Una importante restricción, nuevamente, es que los valores de \(x_{ij}\) deben ser positivos. Veamos como desarrollamos un ejemplo asi.
Una compañía automotriz decide producir tres nuevos modelos de coches. Se tienen dos plantas en el país \(A\) y \(B\). Sin embargo la corporación decide que cada planta debe producir sólo dos productos.
En este caso, se tiene para la planta \(A\) los productos \(x, y\) y para la planta \(B\) los productos \(y, z\).
Además de esto, se sabe lo siguiente:
Se tiene un tiempo limitado de producción en cada planta de \(T_1\) para \(A\) y \(T_2\) para \(B\). Además los tiempos de producción de cada coche son \(t_1=a\), \(t_2=b\) y \(t_3=c\).
Los costos de producción para cada nuevo coche son \(x=P_1\), \(y=P_2\) y \(z=P_3\) y el presupuesto total es \(P_t\)
Los coches tienen ganancias de \(G_1\) para \(x\), \(G_2\) para \(y\) y \(G_3\) para \(z\).
En este caso se tienen las siguientes ecuaciones:
El tiempo total para que se produzcan todos los coches es \(a_1(t_1)(x)+b_1(t_2)(y)\leq T_1\) en planta \(A\) y \(b_2(t_2)(x)+c_1(t_3)(z)\leq T_2\) en planta \(B\).
Los costos totales son \(a_1(P_1)(x)+b_1(P_2)(y)+b_2(P_2)(y)+c_1(P_3)(z) \leq P_t\)
La función a optimizar son las ganancias \(a_1(G_1)(x)+b_1(G_2)(y)+b_2(G_2)(y) G_3(c_1)(z) \leq G_T\)
Aquí los coeficientes \(a_1\), \(b_1\), \(b_2\) y \(c_1\) son el número de coches a producir en plantas \(A\) y \(B\).
Problema de la dieta
Otro problema muy común es el problema de la dieta de una persona.
Este se trata de maximizar los nutrientes que una persona consume, dados los ingredientes \((a, b, c, d,...)\) y las cantidades de carbohidratos, vitaminas, grasas y proteínas que estos contienen \((A, B, C, D…)\)
A este problema también se le asocia el costo de los ingredientes. Este costo es la función objetivo.
Aquí, nuevamente se tiene la restricción de que los valores deben ser positivos \(x_{ij}>0\).
Programación lineal - Puntos clave
- La programación lineal es un método a través del cual podemos resolver problemas de optimización.
- Los problemas se expresan en forma de funciones lineales y restricciones.
- Los problemas pueden tener diversas soluciones –también llamadas soluciones finitas–.
- Las soluciones pueden ser factibles, básicas u óptimas:
- Las soluciones factibles son aquellas que satisfacen las ecuaciones.
- Las soluciones básicas son aquellas que se encuentran en los vértices de las áreas que definen las funciones solapadas, una sobre la otra.
- Las soluciones óptimas son aquellas que maximizan o minimizan la función, usando las restricciones dadas.
Résumenes 
Exámenes 
Magazine 
Formacion Profesional 
