La programación lineal es la forma más sencilla de optimizar un problema. A través de este método, podemos formular un problema del mundo real en un modelo matemático. Podemos resolver una gran variedad de problemas usando programación lineal en diferentes sectores, pero generalmente se usa para el problema en el que tenemos que maximizar ganancias, minimizar costos o minimizar el uso de recursos.
Tipos de problemas de programación lineal
Existen principalmente tres tipos de problemas basados en la programación lineal. Estos son los siguientes:
Problema de fabricación: en este tipo de problema, algunas restricciones como mano de obra, unidades de producción/hora, horas de máquina se dan en forma de ecuación lineal. Y tenemos que encontrar una solución óptima para obtener el máximo beneficio o el mínimo coste.
Problema de dieta: este tipo de problemas son generalmente fáciles de entender y tienen menos variables. Nuestro principal objetivo en este tipo de problema es minimizar el costo de la dieta y mantener una cantidad mínima de cada componente en la dieta.
Problema de transporte: en estos problemas, tenemos que encontrar la forma de transporte más económica eligiendo la ruta más corta/ruta optimizada.
Algunos términos comúnmente utilizados en problemas de programación lineal son:
Función objetivo: La función directa de forma Z = ax + by, donde a y b son constantes, que se reduce o aumenta se llama función objetivo. Por ejemplo, si Z = 10x + 7y. Las variables x e y se denominan variables de decisión.
Restricciones: Las restricciones que se aplican a una desigualdad lineal se denominan restricciones.
- Restricciones no negativas: x > 0, y > 0 etc.
- Restricciones generales: x + y > 40, 2x + 9y ≥ 40 etc.
Problema de optimización: Un problema que busca la maximización o minimización de variables de desigualdad lineal se denomina problema de optimización.
Región factible: una región común determinada por todos los problemas dados, incluida la restricción no negativa (x ≥ 0, y ≥ 0), se denomina región factible (o área de solución) del problema. La región distinta de la región factible se conoce como región no factible.
Soluciones factibles: estos puntos dentro o sobre la región límite representan soluciones factibles del problema. Cualquier punto fuera del escenario se denomina solución no factible.
Solución óptima (más factible): cualquier punto en la región emergente que proporcione la cantidad correcta (máxima o mínima) de la función objetivo se denomina solución óptima.
Teoremas del Problema de Programación Lineal
Teorema 1: Consideremos Y la región factible (polígono convexo) para un problema de programación lineal, es decir, Y = ax + by (función objetivo). Entonces, cuando Y tiene un valor óptimo (máximo o mínimo), donde x e y están sujetos a restricciones descritas por desigualdades lineales, entonces este valor óptimo ocurre en los puntos de esquina de la región factible, es decir, los vértices.
Teorema 2: Consideremos Y como la región factible de un problema de programación lineal, es decir, Y = ax + by (función objetivo). Si X está acotado, entonces la función objetivo Y tiene un valor máximo y mínimo en X y cada uno de estos ocurre en un punto de esquina de X.
NOTA:
- Si tenemos que encontrar la salida máxima, tenemos que considerar los puntos de intersección más internos de todas las ecuaciones.
- Si tenemos que encontrar la salida mínima, consideramos los puntos de intersección más externos de todas las ecuaciones.
- Si no hay un punto en común en la desigualdad lineal, entonces no hay una solución factible.
Solución gráfica de un problema de programación lineal
Podemos resolver problemas de programación lineal usando dos métodos diferentes:
- Punto de esquina
- Método de iso-coste
Punto de esquina
Para resolver el problema utilizando el método del punto de esquina, debe seguir los siguientes pasos:
Paso 1: Crea una formulación matemática a partir del problema dado. Si no se da.
Paso 2: Ahora traza la gráfica usando las restricciones dadas y encuentra la región factible.
Paso 3: encuentra las coordenadas de la región factible (vértices) que obtuvimos del paso 2.
Paso 4: Ahora evalúe la función objetivo en cada esquina de la región factible. Suponga que N y n denotan los valores mayor y menor de estos puntos.
Paso 5: si la región factible está acotada, entonces N y n son los valores máximo y mínimo de la función objetivo. O si la región factible es ilimitada entonces:
- N es el valor máximo de la función objetivo si el semiplano abierto se obtiene por el eje + por > N no tiene punto común a la región factible. De lo contrario, la función objetivo no tiene solución.
- n es el valor mínimo de la función objetivo si el semiplano abierto se obtiene por el eje + por < n no tiene punto común a la región factible. De lo contrario, la función objetivo no tiene solución.
Ejemplos:
Pregunta 1. Resuelva gráficamente los problemas de programación lineal dados:
Maximizar: Z = 8x + y
y las restricciones son:
x + y ≤ 40,
2x + y ≤ 60,
x ≥ 0, y ≥ 0
Solución:
Paso 1: Las restricciones son:
x + y ≤ 40,
2x + y ≤ 60,
x ≥ 0, y ≥ 0
Paso 2: Dibuje el gráfico usando estas restricciones.
Aquí ambas restricciones son menores o iguales, por lo que satisfacen la siguiente región (hacia el origen). Puede encontrar el vértice de la región factible por gráfico, o puede calcular usando las restricciones dadas:
x + y = 40 …(yo)
2x + y = 60 …(ii)
Ahora multiplique eq(i) por 2 y luego reste tanto eq(i) como (ii), obtenemos
y = 20
Ahora pon el valor de y en cualquiera de las ecuaciones, obtenemos
X = 20
Entonces el tercer punto de la región factible es (20, 20)
Paso 3: Encontrar el valor máximo de Z = 8x + y. Compare cada punto de intersección del gráfico para encontrar el valor máximo
Puntos Z = 8x + y (0, 0) 0 (0, 40) 40 (20, 20) 180 (30, 0) 240 Entonces el valor máximo de Z = 240 en el punto x = 30, y = 0.
Pregunta 2. Un tipo de pastel requiere 200 g de harina y 25 g de grasa, y otro tipo de pastel requiere 100 g de harina y 50 g de grasa Encuentra el número máximo de pasteles que se pueden hacer con 5 kg de harina y 1 kg de grasa suponiendo que no falten los demás ingredientes, utilizados en la elaboración de las tortas.
Solución:
Paso 1: cree una tabla como esta para facilitar la comprensión (no es necesario).
Piso (g) Grasa (g) Pastel de primer tipo (x) 200 25 Pastel de segundo tipo (y) 100 50 Disponibilidad 5000 1000 Paso 2: crea una ecuación lineal usando la desigualdad
- 200x + 100y ≤ 5000 o 2x + y ≤ 50
- 25x + 50y ≤ 1000 o x + 2y ≤ 40
- Además, x > 0 y y > 0
Paso 3: Cree un gráfico usando la desigualdad (recuerde solo tomar los ejes x e y positivos)
Paso 4: Encontrar el número máximo de tortas (Z) = x + y. Compara cada punto de intersección de la gráfica para encontrar el número máximo de pasteles que se pueden hornear.
X y Z(x+y) 0 20 20 20 10 30 25 0 25 Claramente, Z es máximo en la coordenada (20, 10). Entonces, la cantidad máxima de pasteles que se pueden hornear es Z = 20 + 10 = 30.
Método de iso-coste
El término método iso-costo o iso-beneficio proporciona la combinación de puntos que produce el mismo costo/beneficio que cualquier otra combinación en la misma línea. Esto se hace trazando líneas paralelas a la pendiente de la ecuación.
Para resolver el problema utilizando el método Iso-cost, debe seguir los siguientes pasos:
Paso 1: Crea una formulación matemática a partir del problema dado. Si no se da.
Paso 2: Ahora traza la gráfica usando las restricciones dadas y encuentra la región factible.
Paso 3: ahora encuentra las coordenadas de la región factible que obtuvimos del paso 2.
Paso 4: encuentre el valor conveniente de Z (función objetivo) y dibuje la línea de esta función objetivo.
Paso 5: si la función objetivo es de tipo máximo, dibuje una línea que sea paralela a la línea de la función objetivo y esta línea esté más alejada del origen y solo tenga un punto común a la región factible. O si la función objetivo es de tipo mínimo, dibuje una línea que sea paralela a la línea de la función objetivo y esta línea sea la más cercana al origen y tenga al menos un punto común a la región factible.
Paso 6: Ahora obtenga las coordenadas del punto común que encontramos en el paso 5. Ahora, este punto se usa para encontrar la solución óptima y el valor de la función objetivo.
Ejemplos:
Pregunta 1. Resuelva gráficamente los problemas de programación lineal dados:
Maximizar: Z = 50x + 15y
y las restricciones son:
5x + y ≤ 100,
x + y ≤ 50,
x ≥ 0, y ≥ 0
Solución:
Dado:
5x + y ≤ 100,
x + y ≤ 50,
x ≥ 0, y ≥ 0
Paso 1: Encontrar puntos
También podemos escribir como
5x + y = 100 ….(yo)
x + y = 50 ….(ii)
Ahora encontramos los puntos
entonces tomamos eq(i), ahora en esta ecuación
Cuando x = 0, y = 100
y cuando y = 0, x = 20
Entonces, los puntos son (0, 100) y (20, 0)
De manera similar, en la ecuación (ii)
Cuando x = 0, y = 50
Cuando y = 0, x = 50
Entonces, los puntos son (0, 50) y (50, 0)
Paso 2: ahora marca estos puntos en el gráfico y encuentra la región factible.
Paso 3: ahora encontramos el valor conveniente de Z (función objetivo)
Entonces, para encontrar el valor conveniente de Z, tenemos que tomar el mcm del coeficiente de 50x + 15y, es decir, 150. Entonces, el valor de Z es el múltiplo de 150, es decir, 300. Por lo tanto,
50x + 15y = 300
Ahora encontramos los puntos
Ponga x = 0, y = 20
Ponga y = 0, x = 6
dibuja la línea de esta función objetivo en el gráfico:
Paso 4: Como sabemos que la función objetivo es de tipo máximo, dibujamos una línea que es paralela a la línea de la función objetivo y está más alejada del origen y solo tiene un punto común a la región factible.
Paso 5: Tenemos un punto común que es (12.5, 37.5) con la región factible. Entonces, ahora encontramos la solución óptima de la función objetivo:
Z = 50x + 15y
Z = 50(12,5) + 15(37,5)
Z = 625 + 562,5
Z = 1187
Pregunta 2. Resuelva gráficamente los problemas de programación lineal dados:
Minimizar: Z = 20x + 10y
y las restricciones son:
x + 2y ≤ 40,
3x + y ≥ 30,
4x + 3y ≥ 60,
x ≥ 0, y ≥ 0
Solución:
Dado:
x + 2y ≤ 40,
3x + y ≥ 30,
4x + 3y ≥ 60,
x ≥ 0, y ≥ 0
Paso 1: Encontrar puntos
También podemos escribir como
l1 = x + 2y = 40 ….(yo)
l2 = 3x + y = 30 ….(ii)
l3 = 4x + 3y = 60 ….(iii)
Ahora encontramos los puntos
Así que tomamos eq(i), ahora en esta ecuación
Cuando x = 0, y = 20
y cuando y = 0, x = 40
Entonces, los puntos son (0, 20) y (40, 0)
De manera similar, en la ecuación (ii)
Cuando x = 0, y = 30
Cuando y = 0, x = 10
Entonces, los puntos son (0, 30) y (10, 0)
De manera similar, en la ecuación (iii)
Cuando x = 0, y = 20
Cuando y = 0, x = 15
Entonces, los puntos son (0, 20) y (15, 0)
Paso 2: ahora marca estos puntos en el gráfico y encuentra la región factible.
Paso 3: ahora encontramos el valor conveniente de Z (función objetivo)
Entonces supongamos que z = 0
20x + 10y = 0
x = -1/2y
dibuja la línea de esta función objetivo en el gráfico:
Paso 4: Como sabemos que la función objetivo es de tipo mínimo, dibujamos una línea que es paralela a la línea de la función objetivo y la más cercana al origen y tiene al menos un punto común a la región factible.
Esta línea paralela toca la región factible en el punto A. Así que ahora encontramos las coordenadas del punto A:
Como puede ver en el gráfico en el punto A, las líneas l2 y l3 se intersecan, por lo que encontramos la coordenada del punto A resolviendo estas ecuaciones:
l2 = 3x + y = 30 ….(iv)
l3 = 4x + 3y = 60 ….(v)
Ahora multiplique eq(iv) con 4 y eq(v) con 3, obtenemos
12x + 4y = 120
12x + 9y = 180
Ahora restamos ambas ecuaciones obtenemos las coordenadas (6, 12)
Paso 5: Tenemos un punto común que es (6, 12) con la región factible. Entonces, ahora encontramos la solución óptima de la función objetivo:
Z = 20x + 10y
Z = 20(6) + 10(12)
Z = 120 + 120
Z = 240
