Solución gráfica de problemas de programación lineal

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.

  1. Restricciones no negativas: x > 0, y > 0 etc.
  2. 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:

  1. Si tenemos que encontrar la salida máxima, tenemos que considerar los puntos de intersección más internos de todas las ecuaciones.
  2. Si tenemos que encontrar la salida mínima, consideramos los puntos de intersección más externos de todas las ecuaciones.
  3. 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:

  1. Punto de esquina
  2. 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

Publicación traducida automáticamente

Artículo escrito por ankitzm y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *