LP: Soluciones y área factible

Dominio alcanzable

Se dice que una solución de un problema lineal es alcanzable si se satisfacen todas las restricciones. El dominio factible contiene todas las soluciones factibles al problema. La solución óptima es la "mejor" de las soluciones factibles.

Para saber si una solución es factible, basta con probar si se cumplen todas las restricciones, que se puede hacer a mano o en forma de matriz.

A mano :

programmation linéaire domaine de définition domaine réalisable

Comprobemos si la solución (3, 1) es factible.

La primera ecuación da 3 * 1/3 + 1 = 2, la restricción se cumple.
La segunda desigualdad da -2 * 3 + 5 * 1 = -1 ≤ 7, la restricción se cumple.
La tercera desigualdad da 3 + 1 = 4 ≤ 4, la restricción está satisfecha, decimos que está saturada.
Se satisfacen ambas restricciones de tipo.

La solución es alcanzable. El valor de la función objetivo es z = 3 - 1 = 2.

Desde un punto de vista matricial: debemos multiplicar la matriz del programa lineal por el vector solución y comparar el resultado con los miembros a la derecha del programa lineal

programmation linéaire domaine de définition domaine réalisable

Dominio alcanzable (o dominio de definición)

Cada restricción se puede comparar con una ecuación que divide el plano en dos. Por ejemplo, la ecuación aI* X1 + bI* X2 = cI divide el plano en dos semiplanos P1 y P2 ecuación:

programmation linéaire domaine de définition domaine réalisable

La restricción menor o igual determinará un semiplano, la restricción mayor o igual determinará el otro semiplano. Para saber en qué semiplano se encuentran las soluciones factibles de las restricciones, basta con probar un ejemplo simple y determinar si es factible o no.

Por ejemplo para la restricción: x1 + x2 ≤ 4, la solución (0,0) es factible, por lo que el origen está en el semiplano factible.

La intersección de todos los semiplanos factibles constituye el dominio factible. Este último puede ser acotado o ilimitado.

programmation linéaire domaine de définition domaine réalisable
Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: