[PDF] [PDF] Exercice de recherche opérationnelle Probl`eme de transf`erement

[PDF] Recherche opérationnelle - LMPA

On admettra que ces résultats se généralisent `a un programme linéaire `a n variables 1 3 6 Exercices § ¦ ¤ ¥ Exercice 1

[PDF] Modélisation

20 avr 2007 · Exercice 0 1 Exercice 0 1 cf : Recherche opérationnelle pour ingénieurs I (de Werra, Liebling, Hêche) ; page 33 Un fabricant doit produire 

[PDF] Recherche opérationnelle et applications

Une solution optimale est une solution admissible qui optimise la fonction objectif Définition 3 (Modèle de recherche opérationnelle) Maximiser ou minimiser ( 

[PDF] Exercice de recherche opérationnelle Probl`eme de transf`erement

Exercice de recherche opérationnelle Probl`eme Comme cela a déj`a été indiqué, l'algorithme du simplexe démarre par la recherche d'une solution de base 

[PDF] 174 EXERCICES SUPPLÉMENTAIRES — PARTIE II

Exercice 4 3 1 [PL équivalent] Considérez le problème minx }Ax ´ y}1 a) Reformulez-le L'algorithme du simplexe recherche itérativement une telle partition en 

[PDF] - Exercices de TD - 1 Modélisation - LIRMM

Le but de cet exercice est la recherche d'une stratégie mixte optimale pour le jeu de Morra 2 Page 3 FLIN606 Prog linéaire 2011/2012 1 MOD ÉLISATION

[PDF] Modèles de Recherche Opérationnelle - Département d

Département d'Informatique et de Recherche Opérationnelle 4 5 Exercices Si la recherche opérationnelle, en abrégé RO, est aujourd'hui présente dans la 

[PDF] Programmation linéaire et recherche opérationnelle Recherche

Recherche opérationnelle Tentative de définition Ensemble de méthodes ( algorithmiques, mathématiques, modélisation) afin de prendre des décisions 

[PDF] exercices récurrence terminale s pdf

[PDF] exercices réflexion et réfraction de la lumière seconde

[PDF] exercices reflexion miroir

[PDF] exercices regime transitoire mpsi

[PDF] exercices repérage dans le plan 5ème

[PDF] exercices représentation des forces

[PDF] exercices reproduction humaine terminale

[PDF] exercices reproduction humaine terminale pdf

[PDF] exercices resolues de cinetique chimique

[PDF] exercices résolus d'électrostatique

[PDF] exercices resolus de mecanique des fluides

[PDF] exercices résolus en macroeconomie

[PDF] exercices résolus sur atomistiques

[PDF] exercices saut en hauteur

[PDF] exercices saut en longueur primaire

Exercice de recherche op

´erationnelle

Probl `eme de transf`erement

Marc Roelens

Corrig

´e

1 Rappel du probl

`eme

Une mati

`ere premi`ere se trouv´ee stock´ee dans 5 d´epˆots situ´es`a Dunkerque (50 tonnes disponibles),

au Havre (70 tonnes disponibles), `a Bordeaux (40 tonnes disponibles),`a S`ete (60 tonnes disponibles) et`a

Mulhouse (80 tonnes disponibles).

On souhaite approvisionner

`a moindre coˆut 4 points de vente situ´es`a Chˆateauroux (60 tonnes de- mand

´ees), Bourges (80 tonnes demand´ees), Clermont-Ferrand (50 tonnes demand´ees) et Lyon (70 tonnes

demand

´ees).

On suppose que les seuls co

ˆuts`a prendre en compte pour l"optimisation sont les coˆuts de transports : ceux-ci sont proportionnels `a la quantit´e transf´er´ee et`a la distance parcourue. Voici les distances entre les diff

´erentes villes :StockCh

ˆateaurouxBourgesClermontLyon

50Dunkerque567502696736

70Le Havre406448594682

40Bordeaux345410369548

60S
`ete568574380325

80Mulhouse688623519340

Demande (t)60805070

D

´eterminer l"approvisionnement optimal.

2 Premi

`eres r´eflexions

2.1 Un probl

`eme de transport/flot

Ce probl

`eme fait partie de la grande famille des probl`emes de flot optimal dans un r´eseau de transport.

Il pr

´esente les particularit´es suivantes :

- le r

´eseau de transport est ditdirect: les sources du flot (les d´epˆots) sont directement connect´ees aux

puits du flot (les points de vente), sans passage par des points interm

´ediaires du r´eseau;

- les capacit ´es de transport des arcs connectant les sources aux puits sont infinies.

On pourrait ainsi tout

`a fait le traiter en mod´elisant le graphe de transport (graphe biparti) et en utilisant les algorithmes classiques de calcul de flot optimal (Ford-Fulkerson, am

´eliorations d"Edmonds-Karp).

2.2 Un probl

`eme de programmation lin´eaire

Si l"on note :

-Nle nombre de d´epˆots; -Ple nombre de points de vente; -Dila quantit´e disponible au d´epˆoti? {1..N}; -djla quantit´e demand´ee au point de ventej? {1..P}; 1 -cijle coˆut de transport unitaire (par tonne) du d´epˆotiau point de ventej; -qijla quantit´e transf´er´ee du d´epˆotiau point de ventej; Alors, trouver l"approvisionnement optimal consiste `a minimiser la fonction de coˆut :

F((qij)) =?

i,jc ijqij en respectant les contraintes : ?i? {1..N}?P ?j? {1..P}?N i=1qij≥dj la premi

`ere s´erie de contraintes traduisant le fait que la quantit´e livr´ee`a partir du d´epˆotidoitˆetre inf´erieure

a la quantit´e disponible, la seconde s´erie de contraintes traduisant le fait que la quantit´e livr´ee au point de

ventejdoitˆetre sup´erieure`a la quantit´e demand´ee.

On se trouve donc bien dans un probl

`eme d"optimisation d"une fonction lin´eaire des variables(qij)en respectant des contraintes

´egalement lin´eaires.

2.3 Condition n

´ecessaire et suffisante d"existence d"une solution

Une condition n

´ecessaire pour l"existence d"une solution (et donc l"existence d"une solution optimale) est le fait que la quantit ´eglobalementdisponible doitˆetre sup´erieure`a la quantit´eglobalementdemand´ee : N i=1D i≥N? i=1P j=1q ij=P? j=1N i=1q ij≥P? j=1d j

De plus, vu que la capacit

´e des arcs est infinie, cette condition est aussi clairement suffisante.

Exemple :la quantit´e disponible est de50 + 70 + 40 + 60 + 80 = 300tonnes, la quantit´e demand´ee est

de60 + 80 + 50 + 70 = 260tonnes, il existe donc une solution optimale au probl`eme.

2.4 Satisfaction au plus juste de la demande

Si le co

ˆut de transport unitaire est positif pour tous les arcs (ce qui est bien sˆur le cas dans le probl`eme

trait

´e o`u le coˆut est simplement la distance entre d´epˆot et point de vente), alors la solution optimale satisfait

exactementla demande de chaque point de vente : en effet, il coˆuterait plus cher d"apporter de la mati`ere

premi `ere en exc`es`a un point de vente! Ainsi, dans la seconde famille de contraintes, on peut remplacer les in

´egalit´es par des´egalit´es, ce qui

revient

`a dire que les variables d"´ecart correspondantes sont forc´ement nulles (hors base optimale).

2.5 Forme particuli

`ere de la matrice de contrainte On ajoute traditionnellement aux variables initiales des variables d"

´ecartyipour lesNpremi`eres

contraintes, qui repr

´esentent donc les quantit´es disponibles dans chaque d´epˆot et non transf´er´ees : on

pr

´ef`ere parfois ajouter unpoint de vente fictifdont la demande est pr´ecis´ement la diff´erence entre offre et

demande dans le probl `eme initial, qui permet d"´equilibrer demande et offre dans ce nouveau probl`eme. Le co

ˆut unitaire de transfert de n"importe quel d´epˆot vers ce point de vente fictif est une constante, en g´en´eral

egale`a z´ero. Il n"est pas n´ecessaire d"ajouter la contrainte li´ee`a ce point de vente fictif, car l"´equation

correspondante peut ˆetre obtenue`a partir des autres´equations! Ensuite, si l"on ordonne les variablesqijpar ordre lexicographique sur(i,j)puis les variablesyipar

ordre suri, la matrice de contraintes prend une forme tr`es particuli`ere (ci-dessous le cas d"exemple o`u l"on

2 a num

´erot´e les d´epˆots 1=Dunkerque, 2=Le Havre, 3=Bordeaux, 4=S`ete, 5=Mulhouse, et les points de vente

1=Ch

ˆateauroux, 2=Bourges, 3=Clermont, 4=Lyon) :q

11 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 050

y

20 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 070

y

30 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 040

y

40 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 060

y

50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 180

1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 060

0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 080

0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 050

0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 070

567502696736406448594682345410369548568574380325688623519340 0 0 0 0 0F

Noter au passage que cette matrice n"est pas sous la forme habituelle et ne correspond donc pas `a une solu-

tion de base admissible : seules les 5 (Ndans le cas g´en´eral) premi`eres lignes correspondent effectivement

a des colonnes unit´es (on a indiqu´e dans la colonne de gauche l"index de la colonne unit´e contenant un 1

dans cette ligne).

On rappelle

´egalement que le probl`eme est un probl`eme deminimisation: on a laiss´e l"expression de Fau lieu de-Fpour all´eger un peu le tableau... 3 R ´esolution du probl`eme r´eduit par la m´ethode du simplexe

Afin d"all

´eger le travail, on va r´eduire la taille du probl`eme en ne conservant dans un premier temps que

3 d

´epˆots (Dunkerque, Le Havre et Bordeaux) pour deux points de vente (Chˆateauroux et Bourges), toutes

les autres donn ´ees (distances, demandes, stocks disponibles) restant identiques.

On constate sur ce probl

`eme r´eduit que la condition d"existence d"une solution est v´erifi´ee : le stock global disponible est de 50+70+40=160 tonnes, alors que la demande globale est de 60+80=140 tonnes.

Voici le tableau du simplexe correspondant

`a cet exemple r´eduit (avec la mˆeme technique de num´erotation des variables) :q

11q12q21q22q31q32y1y2y3y

11 1 0 0 0 0 1 0 050

y

20 0 1 1 0 0 0 1 070

y

30 0 0 0 1 1 0 0 140

1 0 1 0 1 0 0 0 060

0 1 0 1 0 1 0 0 080

567502406448345410 0 0 0F

3.1 Calcul d"une premi

`ere solution (amorc¸age)

Comme cela a d

´ej`a´et´e indiqu´e, l"algorithme du simplexe d´emarre par la recherche d"une solution

de base admissible initiale : une fois cette premi `ere solution trouv´ee, l"algorithme permet de savoir si la solution est optimale; si oui, on a termin ´e, si non, on sait trouver une nouvelle solution de base admissible meilleure que la pr

´ec´edente.

Rappelons ce qu"est une solution de base admissible : -solutionindique que les contraintes sont v´erifi´ees; -admissibleindique que les variables sont toutes positives ou nulles; -de baseindique que le nombre de variables non nulles est minimal.

On sait que la solution optimale (si elle existe) est une solution de base admissible ou plus exactement,

qu"il existe forc ´ement une solution optimale qui est une solution de base admissible. Le nombre (minimal) de variables non nulles parmi toutes les variables (y compris les variables d"

´ecart,

soitN(P+ 1), soit 9 dans l"exemple r´eduit, 25 dans l"exemple complet) est d´etermin´e par le nombre de

contraintes : c"est iciN+P, soit dans notre exemple r´eduit 5 (9 dans l"exemple complet).

Il existe plusieurs m

´ethodes (ou heuristiques) pour trouver cette solution de base admissible initiale : 3 - la m

´ethode des variables artificielles;

- la m

´ethode dite ducoin nord-ouest;

- la m ´ethode dite descoˆuts minimaux successifs(ou heuristique de Houthakker); - la m ´ethode dite desregrets maximaux successifs(ou heuristique de Balas-Hammer).

Il est

`a noter que ces m´ethodes ne fournissent pas directement, dans le cas g´en´eral, la solution optimale!

3.1.1 La m

´ethode des variables artificielles

Cette m

´ethode est tout`a fait g´en´erale : elle consiste`a ajouter des variables qui sont initialement dans la

base, tout en leur attribuant un co ˆut tr`es important (10 fois sup´erieur`a tous les autres coˆuts, par exemple).

Ainsi, lors de l"algorithme du simplexe, ces variables vont naturellement sortir de la base et n"y rentreront

plus jamais : on peut alors les

´eliminer d`es leur sortie.

Dans le cas du probl

`eme de transf`erement, on ajoutePvariables artificielles que l"on note(zj), et l"on r

´ecrit les contraintes sous la forme :

?i? {1..N}?P j=1qij+yi=Di ?j? {1..P}?N i=1qij+zj=di

La base initiale est ainsi constitu

´ee des variables d"´ecart(yi)et des variables artificielles(zj), ce qui fait bienN+P= 5variablesdebasesurNP+N+P= 11variablesautotal,correspondantaux5contraintes.

Le syst

`eme lin´eaire peut alors s"´ecrire :q

11q12q21q22q31q32y1y2y3z1z2y

11 1 0 0 0 0 1 0 0 0 050

y

20 0 1 1 0 0 0 1 0 0 070

y

30 0 0 0 1 1 0 0 1 0 040

z

11 0 1 0 1 0 0 0 0 1 060

z

20 1 0 1 0 1 0 0 0 0 180

567502406448345410 0 0 0M MF

Dans ce tableau, la valeurMest le coˆut associ´e aux variables artificielles. L"expression de la"fonction

economique»(derni`ere ligne du tableau) est encore incorrecte, il faudrait lui appliquer 2 phases de pivo-

tage pour

´eliminer les coefficients des variables(zj). En fait, vue la forme particuli`ere de la matrice, on

obtiendrait pour la variableqijle coefficientcij-M. Pour choisir le premier pivot, on devrait donc choisir la valeur la plus n

´egative parmi ces coefficients,

ce qui revient

`a choisir la plus petite valeur descij, ce qui revient`a la m´ethode indiqu´ee plus loin descoˆuts

minimaux successifs.

3.1.2 La m

´ethode du coin nord-ouest

Cette m

´ethode consiste`a"faire entrer dans la base»les variables par ordre lexicographique croissant

(si c"est possible) sans faire"sortir de la base»les variables que l"on a fait entrer. Sur l"exemple, on obtient

ainsi les phases suivantes :

1. on commence par la variableq11; il y a deux coefficients 1 dans la colonne correspondante, on

calcule donc les ratios"valeur du second membre divis´ee par valeur du coefficient», ce qui revient`a

simplement consid ´erer la valeur du second membre, en l"occurrence 50 et 60; on retient le minimum (positif) de ces deux valeurs, qui est donc la valeur 50, correspondant `a la ligne dey1qui va sortir de la base; on peut retrouver la signification ´economique de ce r´esultat :q11repr´esente la quantit´e transf´er´ee du d

´epˆot de Dunkerque au point de vente de Chˆateauroux; on est limit´e par la demande`a Chˆateauroux

(60 tonnes) et le stock disponible `a Dunkerque (50) : la variable prend donc la valeur 50, la demande r

´esiduelle`a Chˆateauroux prend la valeur 10 et le stock r´esiduel`a Dunkerque est nul (ety1,q12sont

nulles et hors base); 4

2. la variable suivante est doncq21: on est limit´e par la demande r´esiduelle`a Chˆateauroux (10 tonnes)

et le stock au Havre (70 tonnes); la variable prend donc la valeur 10, le stock r

´esiduel au Havre est

de 60 tonnes, la demande r ´esiduelle`a Chˆateauroux est nulle (etq31est nulle et hors base);

3. la variable suivante est doncq22: on est limit´e par la demande`a Bourges (80 tonnes) et le stock

r

´esiduel au Havre (60 tonnes); la variable prend donc la valeur 60, la demande r´esiduelle`a Bourges

prend la valeur 20 et le stock r ´esiduel au Havre est nul (ety2est nulle et hors base);

4. la variable suivante est doncq32: on est limit´e par la demande r´esiduelle`a Bourges (20 tonnes) et le

stock `a Bordeaux (40 tonnes); la variable prend donc la valeur 20, le stock r´esiduel`a Bordeaux est de 20 tonnes. Les variables hors base sont doncq12,q31,y1ety2; les autres variables sont : ????q

11= 50

q

21= 10

q

22= 60

q

32= 20

y 3= 20 Le co

ˆut global de cette solution est de 67490. Comme cette m´ethode ne tient absolument pas compte des

co

ˆuts associ´es, on a toutes raisons de penser que la solution obtenue n"a que tr`es peu de chances d"ˆetre

optimale.

3.1.3 Amorc¸age par m

´ethode de Houthakker

Dans cette m

´ethode (´egalement appel´ee m´ethode des coˆuts minimaux successifs), on cherche`a faire

entrer les variables par ordre de co ˆut croissant (si elles n"ont pas d´ej`a´et´e class´ees comme´etant hors de la base). On obtient ainsi successivement :

1. la premi

`ere variable estq31(coˆut minimal de 345) : on est limit´e par la demande`a Chˆateauroux (60

tonnes) et le stock `a Bordeaux (40 tonnes); la variable prend donc la valeur 40, la demande r´esiduelle

a Chˆateauroux est de 20 tonnes, le stock r´esiduel`a Bordeaux est nul (q32,y3sont nulles et hors base);

2. la variable suivante estq21(coˆut minimal de 406) : on est limit´e d"une part par la demande r´esiduelle

a Chˆateauroux (20 tonnes) et d"autre part par le stock au Havre (70 tonnes); la variable prend donc

la valeur 20, le stock r ´esiduel au Havre prend la valeur 50, la demande r´esiduelle`a Chˆateauroux est nulle (etq11est nulle et hors base);

3. la variable suivante est doncq22(coˆut minimal de 448) : on est limit´e par la demande`a Bourges (80

tonnes) et le stock r ´esiduel au Havre (50 tonnes); la variable prend donc la valeur 50, la demande r

´esiduelle`a Bourges prend la valeur 30, le stock r´esiduel au Havre est nul (ety2est nulle et hors

base);

4. la variable suivante est doncq12(coˆut minimal de 502) : on est limit´e par la demande r´esiduelle`a

Bourges (30 tonnes) et le stock

`a Dunkerque (50 tonnes); la variable prend donc la valeur 20, le stock r ´esiduel`a Dunkerque prend la valeur 20, la demande r´esiduelle`a Bourges est nulle. Les variables hors base sont doncq11,q32,y2ety3; les autres variables sont : ????q

12= 30

q

21= 20

q

22= 50

q

31= 40

y 1= 20 Le co

ˆut global de cette solution est de 59380.

5

3.1.4 Amorc¸age par m

´ethode de Balas-Hammer

Il semble naturel d"essayer d"approvisionner chaque point de vente `a partir du d´epˆot qui est le moins cher pour ce point de vente. Ne pas le faire va entra ˆıner un surcoˆut (puisque l"on va se fournir`a un d´epˆot plus cher), et c"est ce surco

ˆut que l"on nommeregret.

Dans la m

´ethode de Balas-Hammer (´egalement appel´ee m´ethode des regrets maximaux successifs), on

cherche

`a faire entrer les variables pour ordre de regret d´ecroissant (si elles n"ont pas d´ej`a´et´e class´ees

comme ´etant hors de la base). On obtient ainsi successivement :

1. calculons le regret associ

´e`a chaque point de vente :

- pour le point de vente `a Chˆateauroux, le d´epˆot le moins cher est Bordeaux`a un coˆut de 345, le suivant ´etant Le Havre`a un coˆut de 406, soit un regret de 61; - pour le point de vente `a Bourges, le d´epˆot le moins cher est Bordeaux`a un coˆut de 410, le suivant etant Le Havre`a un coˆut de 448, soit un regret de 38; le regret maximal correspond `a la variableq31(comme pour Houthakker); la variable prend donc la valeur 40, la demande r ´esiduelle`a Chˆateauroux est de 20 tonnes, le stock r´esiduel`a Bordeaux est nul (q32,y3sont nulles et hors base);

2. on recalcule les regrets :

- pour le point de vente `a Chˆateauroux, le d´epˆot le moins cher est Le Havre`a un coˆut de 406, le suivant ´etant Dunkerque`a un coˆut de 567, soit un regret de 161; - pour le point de vente `a Bourges, le d´epˆot le moins cher est Le Havre`a un coˆut de 448, le suivant etant Dunkerque`a un coˆut de 502, soit un regret de 54; le regret maximal correspond `a la variableq21(comme pour Houthakker); la variable prend donc la valeur 20, le stock r ´esiduel au Havre prend la valeur 50, la demande r´esiduelle`a Chˆateauroux est nulle (etq11est nulle et hors base);

3. il ne reste que le point de vente de Bourges, pour lequel le moins cher est Le Havre (50 tonnes encore

disponible) suivi de Dunkerque (30 tonnes utilis

´ees sur les 50 tonnes disponibles)

On retrouve donc exactement la m

ˆeme solution que pour Houthakker : ceci est uneco¨ıncidence!

3.2 Calcul du tableau du simplexe

On prend donc comme solution de base admissible la solution commune trouv

´ee par les deux m´ethodes.

On commence par faire entrerq31dans la base, c"esty3qui en sort (troisi`eme ligne du tableau) :q

11q12q21q22q31q32y1y2y3y

11 1 0 0 0 0 1 0 050

y

20 0 1 1 0 0 0 1 070

q

310 0 0 0 1 1 0 0 140

1 0 1 0 0-1 0 0-120

0 1 0 1 0 1 0 0 080

567502406448 0 65 0 0-345F-13800C"est ensuiteq21qui entre dans la base (quatri`eme ligne du tableau) :q

11q12q21q22q31q32y1y2y3y

11 1 0 0 0 0 1 0 050

y

2-1 0 0 1 0 1 0 1 150

q

310 0 0 0 1 1 0 0 140

q

211 0 1 0 0-1 0 0-120

0 1 0 1 0 1 0 0 080

161502 0 448 0 471 0 0 61F-219206

C"est ensuiteq22qui entre dans la base alors quey2en sort (deuxi`eme ligne du tableau) :q

11q12q21q22q31q32y1y2y3y

11 1 0 0 0 0 1 0 050

q

22-1 0 0 1 0 1 0 1 150

q

310 0 0 0 1 1 0 0 140

q

211 0 1 0 0-1 0 0-120

1 1 0 0 0 0 0-1-130

609502 0 0 0 23 0-448-387F-44320Et pour terminer, c"estq12qui entre dans la base (cinqui`eme ligne du tableau) :q

11q12q21q22q31q32y1y2y3y

10 0 0 0 0 0 1 1 120

q

22-1 0 0 1 0 1 0 1 150

q

310 0 0 0 1 1 0 0 140

q

211 0 1 0 0-1 0 0-120

q

121 1 0 0 0 0 0-1-130

107 0 0 0 0 23 0 54 115F-59380Onacettefoisunesolutiondebaseadmissibledeco

Qui plus est, on constate que les coefficients de la fonction ´economique sont tous positifs : on est donc par- venu

`a l"optimum! Ceci, est-il encore besoin de le rappeler, est une co¨ıncidence : la m´ethode de Houthakker

ou celle de Balas-Hammer ne sont cens ´ees donner qu"une"bonne»solution, pas forc´ement la meilleure.

3.3 Quelques constatations

Dans toutes les manipulations de l"algorithme du simplexe que l"on a r

´ealis´ees, on constate que les

coefficients de la matrice ne sont que des 0, des 1 ou des -1 : ceci n"est pas un hasard mais peut

ˆetre

proprement d

´emontr´e (on peut retrouver`a l"intuition ce r´esultat si l"on songe`a la mod´elisation par flots).

On a

´egalement une autre propri´et´e : le nombre de 1 dans chaque colonne est toujours´egal au nombre

de -1 plus une unit ´e! L`a encore, ce r´esultat n"est pas le fruit du hasard.

Enfin, consid

´erons une variable hors base,q11par exemple qui repr´esente la quantit´e transf´er´ee de

Dunkerque

`a Chˆateauroux. Si l"on voulait la faire entrer dans la base - lui donner une valeur +1 par exemple

- il faudrait, afin de respecter la contrainte de ne pas d ´epasser 50 tonnes transf´er´ees`a partir de Dunkerque, diminuer de -1 la quantit ´e transf´er´ee`a Bourges (c"est le seul point de vente approvisionn´e). Comme on doit respecter la quantit

´e transf´er´ee`a Bourges, il faut augmenter de +1 la quantit´e livr´ee depuis un autre

d

´epˆot : si l"on ne veut pas rendre non nulle une autre variable (lors d"un changement de base, une et une

seule variable sort, une et une seule variable entre), on ne peut augmenter que le transfert depuis Le Havre.

Mais pour cela (respect du stock disponible au Havre), on doit diminuer la quantit

´e transf´er´ee du Havre`a

Ch ˆateauroux...et la boucle (ou plus exactement le cycle) est boucl´ee!

Calculons le co

ˆut de ce transfert (toujours pour une tonne transf´er´ee) : il faut compter en plus la distance

de Dunkerque `a Chˆateauroux (567) et la distance du Havre`a Bourges (448), en moins la distance de

Dunkerque

`a Bourges (502) et la distance du Havre`a Chˆateauroux (406), soit un total de567 + 448-

502-406 = 107: c"est pr´ecis´ement la valeur du coefficient dans la fonction´economique deq11.

En fait, on rappelle que le tableau final (primal) permet de donner une expression des variables dans

la base et de la fonction ´economique en fonction des variables hors base, cette expression´etant valable

au voisinage de la solution de base admissible correspondante. Si l"on souhaite exprimer la variation de la

solution par rapport `a la variableq11(par exemple, si une nouvelle contrainte commerciale nous imposait de livrer Ch ??????y 1= 20quotesdbs_dbs19.pdfusesText_25