LP: Soluciones y área factible

Dominio alcanzable

Una solución de uno problema lineal Se dice que es factible si se cumplen todas las restricciones. El dominio factible contiene todas las soluciones factibles del problema. La solución óptima es la solución o soluciones factibles “mejores”.

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 :

programación lineal dominio de definición dominio realizable

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 de la programa lineal por el vector solución y compare el resultado con los miembros correctos del programa lineal

programación lineal dominio de definición dominio realizable

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:

programación lineal dominio de definición dominio realizable

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.

programación lineal dominio de definición dominio realizable
Compartir, repartir