Recherche opérationelle IFT2505.

Question1:

a) Le problème de transport tel que présenté présente une matrice A remplie de 1

A= dont le nombre de ligne est égal n+m (puisqu'on a m contrainte de quantités a et n contraintes de demandes  ) le rang d'une telle matrice rang(A)=1[pic 1]

or pour qu'un system de contraintes soit non redondante il faut que le rang de A soi égal au nombre des contraintes (n+m dans notre cas) ce qui n'est pas le cas ici donc les contraintes décrites dans ce problème ne sont pas linéairement indépendante

b) soit le problème primal suivant:

min CT X

t.q    A .X=b

xi ≥0 ∀i=1..n

considérant la contrainte n redondante le système deviendra

min CT X

[pic 2]

[pic 3]

.

.

.

.

[pic 4]

xi ≥0 ∀i=1..n

si on écrit le dual des deux problèmes on aura [pic 5][pic 6]

soit λ* la solution du dual (I) et λ'* celle du dual (II) et x* la solution du primal

sous la dualité forte on a
[pic 7]

donc       d'où  et comme bm ≥0 donc  donc la variable duale associé a la contrainte redondante est nulle [pic 8][pic 9][pic 10]

et si on sélectionne une a une chaque contrainte comme contrainte redondante on remarque que la variable dual associé a cette contrainte s'annule ainsi les variables duales qui composent la solution optimal du dual ne sont pas unique en effet dépendant du choix de la  contrainte redondante du primal a éliminé  la solution du dual correspondant sera différente ( annulation de la variable duale correspondante)

Question2:  Application de l'algorithme du nord-Ouest

 a=(10,15,7,8)   b=(8,6,9,12,15)

solution(X11=8, X12=2, X22=4, X23=9, X24=2, X34=7, X44=3, X45=5)

a=(2,3,4,5,6)   b=(6,5,4,3,2)

solution(X11=2, X21=3, X31=1, X32=3, X42=2, X43=3, X53=1, X54=3, X55=2)

...