Comment prouver que nous ne pouvons pas avoir X (j) + et X (j) - simultanément positif dans un LP?

Question

Comme nous le savons tous, dans un problème de programmation linéaire, toute variable x (j) voiture peut être remplacée par la différence entre 2 variables non négatives.

X (j) = X (j) + - X (j) -

Comment savons-nous que dans une solution de base, on ne peut jamais avoir X (j) + et X (j) - en même temps strictement positif?

Ai-je besoin de supposer un problème et de travailler dessus en divisant chaque variable en x + - x-? Mais cela ne me prouvera rien à la fin.

Answer 1

Tout d'abord, les manuels disent généralement que la méthode Simplex ne peut traiter que des variables non-négatives. C'est faux: les solveurs LP peuvent gérer directement les variables libres. Nous pouvons toujours utiliser la division variable dans certains cas de modélisation intéressants même si nous pouvons utiliser des variables libres.

Si l'objectif minimise |X| (à savoir qu'il minimise Xplus + Xmin) nous ne savons pas à la fois Xplus et Xmin peut être différente de zéro.

Il y a aussi un autre argument, plus exotique. Si les colonnes matricielles LP et Xmin sont identiques à l'exception du signe, elles ne peuvent apparaître dans la base (si elles le font, la matrice de base B serait singulière). Cet argument est bien sûr lié à la méthode Simplex.

Mais dans certains cas, Xplus et Xmin peuvent être différents de zéro. Ceci est parfois appelé non-convexity. Dans ce cas, on aurait besoin d'ajouter une variable binaire B avec:

Xplus <= M*B 
Xmin <= M*(1-B) 

Answer 2

Habituellement, il n'a pas d'importance: puisque vous êtes intéressé par la valeur de x, à la fois (5, 5) et (0, 0) pour exemple sont une représentation valide de la même solution x = 0.

Pourquoi avez-vous besoin que l'une des valeurs soit 0?