Iniciar sesión Empieza a estudiar
La app de estudio todo en uno
4.8 • +11 mil reviews
Más de 3 millones de descargas
Free
|
|
Programación lineal

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:

Ejemplo de un problema de programacion lineal

Si quieres saber para qué nos sirve la programación lineal, veamos el siguiente ejemplo:

  1. Quieres saber cuánto puedes producir de madera en una plantación forestal.
  2. Plantas de cierta cantidad de árboles cada año.
  3. De cada año anterior solo puedes talar ciertos árboles.
  4. Además de los árboles que plantas, solo ciertos árboles maduran para poder ser talados.

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:

  • Los árboles que se plantaron.
  • Los que sobreviven.
  • Los que crecen lo suficiente para ser talados

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.

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 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.\]

  • 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\).

Problema general de programación lineal, por pasos

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.

  • \(x=P_1\) y \(y=P_2\)

3. Además de esto cada producto puede ser producido en cierto tiempo.

  • \(x=t_1\) y \(y=t_2\)

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 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.

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\]

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:

Programación lineal soluciones StudySmarter.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:

 Programación lineal tipos de soluciones StudySmarter.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 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\).

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.

Preguntas frecuentes sobre Programación lineal

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:

  • Una ecuación o función objetivo.
  • Una serie de restricciones.
  • Una serie de condiciones lógicas como valores siempre positivos, negativos, etc.

Cuestionario final de Programación lineal

Pregunta

¿Para que nos sirve la programación lineal?


Mostrar respuesta

Answer

Maximizar o minimizar problemas.

Show question

Pregunta

Si un problema está representado por dos inecuaciones lineales en programación lineal, ¿cuántas variables existen?

Mostrar respuesta

Answer

Existen más de tres variables.

Show question

Pregunta

¿Qué sistema representa un problema de programación lineal?

Mostrar respuesta

Answer

\(a_1x+b_1y-c_1z=k_0\)

\(a_2x-b_2y-c_2z=k_0\)

\(a_3x+b_3y+c_3z=k_0\).

Show question

Pregunta

¿Cuáles son los elementos que definen las desigualdades en un problema de programación lineal?

Mostrar respuesta

Answer

Restricciones.

Show question

Pregunta

Supongamos que somos una empresa que produce coches eléctricos, estos coches pueden ser ofrecidos a otra empresa ya que son coches de carga o servicio. Se tienen furgonetas \(x\) y camionetas de carga \(y\). 


Se ofrecen dos posibles paquetes que son:


\(4x+2y\)

\(2x+5y\)


Pero del primer paquete solo se pueden proveer cincuenta coches y del segundo solo cuarenta debido a restricciones. ¿Cómo expresas estas restricciones en un problema de programación lineal?

Mostrar respuesta

Answer

\(4x+2y \leq 50\)

\(2x+5y \leq 40\).

Show question

Pregunta

En el problema del transporte, ¿se puede tener una restricción que represente un valor mayor de ventas entre tiendas que la producción del producto que se transporta?

Mostrar respuesta

Answer

No, ya que la producción solo puede ser igual a los productos vendidos en cada tienda.

Show question

60%

de los usuarios no aprueban el cuestionario de Programación lineal... ¿Lo conseguirás tú?

Empezar cuestionario

Scopri i migliori contenuti per le tue materie

No hay necesidad de copiar si tienes todo lo necesario para triunfar. Todo en una sola app.

Plan de estudios

Siempre preparado y a tiempo con planes de estudio individualizados.

Cuestionarios

Pon a prueba tus conocimientos con cuestionarios entretenidos.

Flashcards

Crea y encuentra fichas de repaso en tiempo récord.

Apuntes

Crea apuntes organizados más rápido que nunca.

Sets de estudio

Todos tus materiales de estudio en un solo lugar.

Documentos

Sube todos los documentos que quieras y guárdalos online.

Análisis de estudio

Identifica cuáles son tus puntos fuertes y débiles a la hora de estudiar.

Objetivos semanales

Fíjate objetivos de estudio y gana puntos al alcanzarlos.

Recordatorios

Deja de procrastinar con nuestros recordatorios de estudio.

Premios

Gana puntos, desbloquea insignias y sube de nivel mientras estudias.

Magic Marker

Cree tarjetas didácticas o flashcards de forma automática.

Formato inteligente

Crea apuntes y resúmenes organizados con nuestras plantillas.

Regístrate para poder subrayar y tomar apuntes. Es 100% gratis.

Get FREE ACCESS to all of our study material, tailor-made!

Over 10 million students from across the world are already learning smarter.

Get Started for Free
Illustration