Desviaciones adicionales

Desviaciones adicionales

Les écarts complémentaires sont utilisable si le primal est réalisable et que la solution est bornée, le dual est réalisable et sa solution est aussi borné. Si les valeurs des solutions primale et duale sont égales, elles sont optimales pour leur programme linéaire, on parle de dualité forte. Parfois il n’est pas possible de trouver de solution, ou pas utile de la calculer. Le programme primal et dual étant lié, il est possible de déduire une solution du programme réciproque à l’aide des écarts complémentaires.

Proceso

L’un des principaux théorèmes de la théorie de la dualité en programación lineal est le théorème des écarts complémentaires. Ce théorème nous permet de trouver la solution optimale du problème dual lorsque nous connaissons la solution optimale du problème primal (et inversement) en résolvant un système d’équations formées par les variables de décision (primal et dual) et les contraintes (primal et dual modèle).

L’importance de ce théorème est qu’il facilite la résolution des modèles d’optimisation linéaire, ce qui vous permet de trouver le modèle le plus simple à traiter (du point de vue algorítmico). Le processus est le suivant:

  1. Encuentre una solución viable en el primario.
  2. Si este es el caso, observe las variables distintas de cero (esto implica que la restricción del dual está saturada) y las restricciones con juego (lo que implica que la variable del dual es cero).
  3. Resuelve el sistema de ecuaciones
  4. Verifique la dualidad fuerte, es decir, la solución del primario es idéntica a la del dual. En este caso, la solución factible es óptima.

Versión I. Sean x * e y * las soluciones del primario y el dual. Estas dos soluciones son óptimas si y solo si:

  • para cualquier j de 1 an
    • o la restricción j del dual está saturada
    • o x *j=0
    • o ambos
  • para todo i de 1 am
    • o la restricción i del primario está saturada
    • o y *I=0
    • o ambos

La segunda versión de las desviaciones complementarias permite comprender mejor cómo encontrar una solución en el programa recíproco. Para ello se debe asumir que las dos condiciones de la versión I son siempre verdaderas.

Versión II. Una solución x del primal es óptima si y solo si existe un vector y * tal que:

  • y * es elegible
  • si xj> 0 entonces la j-ésima restricción del dual está saturada
  • si la restricción i-ésima del primario no está saturada, entonces y *I=0.
  • ya la inversa entre lo dual y lo primario.

Así, una vez que se encuentra una solución en el programa recíproco, solo queda verificar la fuerte dualidad del sistema.

Ejemplo 1

Considere el siguiente modelo de programación lineal con 2 variables cuya solución óptima es X = 14/5 e Y = 8/5 con el valor óptimo V = 20,8.

método simplex holgura complementaria brechas complementarias

El modelo dual asociado con el modelo primario es:

método simplex holgura complementaria brechas complementarias

Entonces, el teorema de las desviaciones complementarias muestra las siguientes relaciones:

método simplex holgura complementaria brechas complementarias

Como sabemos, X = 14/5 e Y = 8/5 (solución óptima primaria). Si reemplazamos estos valores de X e Y en la tercera y cuarta ecuaciones (porque ambas restricciones del primario están saturadas y no podemos concluir nada sobre las ecuaciones 1 y 2), generamos un sistema de ecuaciones en términos de A y de B cuya solución corresponde a A = 6/5 y B = 2/5. Si luego evaluamos la función objetivo en el problema dual de esta solución, obtenemos: V = 12 (6/5) +16 (2/5) = 20.8, que es similar al valor óptimo del problema primario (dualidad fuerte ).

Ejemplo 2

Considere el siguiente problema:

método simplex holgura complementaria brechas complementarias

La solución a este problema es {42, 0, 10.4, 0, 0.4}. El problema dual es el siguiente:

método simplex holgura complementaria brechas complementarias

Test de faisabilité. La première contrainte est saturé, aucune conclusión pour y1. La deuxième contrainte n’est pas saturé, donc y2 = 0. La troisième contrainte est saturé, rien sur y3.

Variables positivas. x1 = 0, nada para concluir. x2> 0, la segunda restricción del dual está saturada. x3 = 0, nada para concluir. x4> 0, la cuarta restricción del dual está saturada.

Entonces, la solución de dual debe satisfacer: y2 = 0; y1 + y3 = 4; 4y1 + y3 = 1 con {1, 0, 3} como solución. Los valores de primal y dual son equivalentes, por lo que tenemos el óptimo.

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: