La app de estudio todo en uno
4.8 • +11 mil reviews
Más de 3 millones de descargas
Free
La programación lineal es un método por el cual se optimiza un problema que se 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:
Si quieres saber para qué nos sirve la programación lineal, veamos el siguiente ejemplo:
Debes maximizar la cantidad de árboles que debes talar para producir \(X\) toneladas de madera al año. En este caso, necesitas una fórmula que contenga:
El encontrar el máximo de árboles que puedes talar dependiendo de cuantos plantas y cuantos maduran/sobreviven, es un ejemplo de un problema donde puedes usar 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 varias 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.\]
Ahora te describiremos, de manera general, cómo se resuelve un problema en programación lineal. Lo resolveremos paso por paso:
1. Supongamos, que se tienen dos objetos que se producen. Los objetos se representan por las variables \(x\) y \(y\).
2. Supongamos que estos objetos tienen cierto costo para ser producidos.
3. Además de esto cada producto puede ser producido en cierto tiempo.
4. Se tiene además un tiempo limitado para producir ambos \(t\) y un presupuesto limitado para la producción en este tiempo \(C\).
El problema anterior explicado paso por paso puede ser expresado de una manera sencilla. Esta manera es la forma estándar y se expresa así:
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.
Debido a que estos problemas son un caso aplicado de un sistema de ecuaciones lineales, tienen diversos tipos de soluciones, como:
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\]
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:
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.
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.
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.
La soluciones en un problemas de programación lineal pueden ser finitas; es decir, las podemos contar. Esas soluciones pueden ser:
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.
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.
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 un ejemplo:
Se tiene cierto número de fábricas \( (a,b) \). Estas fábricas deben abastecer un número de centros comerciales \((A, B, C)\). Y 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:
A | B | C | |
a | 2 | 3 | 1 |
b | 5 | 6 | 2 |
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\).
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\).
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\).
La programación lineal es el nombre que se le da a la optimización de un problema matemático, cuando el problema es expresado como funciones lineales.
Su finalidad es obtener resultados óptimos de problemas en matemáticas aplicadas.
La programación lineal se aplica cuando se busca resolver problemas de ingeniería, distribución, demanda económica y ciencias sociales.
Problemas que pueden ser expresados como ecuaciones lineales.
Un problema de programación lineal se constituye de:
de los usuarios no aprueban el cuestionario de Programación lineal... ¿Lo conseguirás tú?
Empezar cuestionarioSiempre preparado y a tiempo con planes de estudio individualizados.
Pon a prueba tus conocimientos con cuestionarios entretenidos.
Crea y encuentra fichas de repaso en tiempo récord.
Crea apuntes organizados más rápido que nunca.
Todos tus materiales de estudio en un solo lugar.
Sube todos los documentos que quieras y guárdalos online.
Identifica cuáles son tus puntos fuertes y débiles a la hora de estudiar.
Fíjate objetivos de estudio y gana puntos al alcanzarlos.
Deja de procrastinar con nuestros recordatorios de estudio.
Gana puntos, desbloquea insignias y sube de nivel mientras estudias.
Cree tarjetas didácticas o flashcards de forma automática.
Crea apuntes y resúmenes organizados con nuestras plantillas.
Regístrate para poder subrayar y tomar apuntes. Es 100% gratis.
Over 10 million students from across the world are already learning smarter.
Get Started for Free