Previous Up Next

6.54.5  Passage de la forme standard à la forme canonique

La forme standard d’un problème d’optimisation linéaire est analogue à la forme canonique, mais en remplacant Axb par Ax=b avec b≥ 0 et où on cherche x≥ 0 (on peut s’y ramener si nécessaire en changeant le signe d’une ligne).

Le problème pour appliquer l’algorithme précédent est qu’on ne peut pas ajouter de variables d’écarts et donc qu’on n’a pas de valeur x évidente dans le domaine de maximisation (dit autrement on n’a pas de sous-matrice identité dans la formulation matricielle du problème et il n’y a pas d’opération de lignes évidente qui permette de le faire).

On va se ramener à des problèmes sous forme "canonique" par la méthode dite en 2 phases. Soit m le nombre de lignes de A (nombre de conditions dans Ax=b). On ajoute des variables artificielles y1,...,ym et on maximise −∑yi sous condition Ax=b, x ≥ 0, y ≥ 0 en partant de la valeur initiale 0 pour les variables non artificielles et b pour y (on appelle donc simplex_reduce avec un argument matrice obtenue en augmentant A par l’identité, b inchangé et un c artificiel formé de 0 au début et de 1 en dessous de l’identité (que simplex_reduce va commencer par annuler)). Si le maximum existe et est 0, on obtiendra une sous-matrice identité dans les colonnes correspondants à x, et on pourra éliminer les variables artificielles (dont la valeur sera 0 pour atteindre l’optimum). Il restera à appliquer à nouveau l’algorithme du simplexe mais avec le c original (comme les coefficients de c correspondant à l’identité n’ont pas de raison d’être nuls, on doit commencer par les rendre nuls, ce que simplex_reduce fait si on permute les colonnes pour placer la sous-matrice identité à droite).

Exemple : on cherche le minimum de 2x+3yz+t avec les x,y,z,t≥ 0 et :



xy+t=1
yz+t=3

Ceci revient à calculer l’opposé du maximum de −(2x+3yz+t). On ajoute donc deux variables artificielles y1 et y2, on tape directement la matrice de l’algorithme

simplex_reduce([[-1,-1,0,1,1,0,1],
[0,1,-1,1,0,1,3],
[0,0,0,0,1,1,0]])

On obtient comme optimum 0, avec 0 comme valeurs pour les variables artificielles, et la matrice




−1/20−1/211/21/2
1/21−1/20−1/21/2
0000110



Ceci signifie aussi qu’une valeur initiale dans le domaine est (0,1,0,2). Il nous reste à optimiser le problème de départ en remplacant les lignes de Ax=b par les 2 premières lignes de la matrice réponse ci-dessus dont on enlève les variables artificielles et en ajoutant la ligne de la fonction à optimiser. On prend donc la matrice

simplex_reduce([[-1/2,0,-1/2,1,2],
[1/2,1,-1/2,0,1],[2,3,-1,1,0]])

On obtient comme maximum -5, donc le minimum de l’opposé est 5, obtenu pour (0,1,0,2) soit après replacement des colonnes t=2 et y=1, les autres nuls.

Pour plus de détails, chercher sur google simplex algorithm ou dans une bibliothèque Ciarlet “Introduction à l’analyse matricielle et à l’optimisation”.

Back to the general case.
The standard form of a linear programming problem is similar to the simplest case above, but with Ax=b (instead of Axb) under the conditions x≥ 0. We may further assume that b≥ 0 (if not, one can change the sign of the corresponding line).

Pour plus de details, chercher sur google : algorithme du simplex.


Previous Up Next