LP: resolución gráfica

Resolución de gráficos

Es posible resolver los problemas con dos variables (o dos restricciones para un problema dual) directamente mediante una resolución gráfica. El proceso de resolución se desarrolla en tres etapas:

  1. Dominio alcanzable
  2. Grafica la función objetivo
  3. Determine la solución óptima

Dominio alcanzable

Para eso, representamos cada restricción en el gráfico, sombreando o coloreando el lado que no satisface la restricción.
Así, destacamos un dominio de definición o dominio realizable, cualquier punto del dominio de definición satisface todas las restricciones del modelo matemático.

Considere el siguiente programa lineal:

Resolución de gráficos

Dibujemos el dominio de la definición:

Agregar la primera restricción y el tipo de variables

Resolución de gráficos

Adición de la segunda restricción

Resolución de gráficos

Adición de la tercera restricción

Resolución de gráficos

Grafica la función objetivo

Para resolver el problema, representamos la función objetivo en el punto (100,0) luego en varios puntos (siguiendo el gradiente de la función objetivo) hasta que la función objetivo tenga solo un punto o una faceta del campo de definición.

Resolución de gráficos

El gradiente de la función objetivo es (350,300). Por lo tanto, el valor z aumenta cuando la función objetivo se mueve en la misma dirección que el vector (350,300), por lo tanto, se mueve hacia la esquina noreste. Podemos ver claramente en la siguiente figura que el valor de z ha aumentado tomando otra línea de la función objetivo.

Resolución de gráficos

Luego obtenemos las soluciones globales óptimas. Si trazamos la función objetivo nuevamente siguiendo el gradiente, la línea estará fuera del dominio de definición.

Soluciones óptimas

Las soluciones óptimas son los últimos puntos antes de que la línea de la función objetivo abandone el dominio de definición.

Resolución de gráficos

La solución óptima se encuentra en la intersección de la primera y la segunda restricción, por lo que satisface ambas restricciones. El vector solución es la solución del sistema:

Resolución de gráficos

La solución de este sistema es (122,78) que da z = 66100.

Las cuatro posibilidades de solución óptima

Hay cuatro posibilidades:

  • o existe una solución única (un punto);
  • ya sea una infinidad de soluciones (una faceta);
  • o la solución no está acotada, la línea de la función objetivo siempre estará en el dominio de definición siguiendo el gradiente;
  • o no hay solución, por ejemplo si el dominio está vacío.
Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: