Examen de recherche opérationnelle

Solution optimale identique mais avec une étape de moins. 9. Page 10. Exercice 1.2.3. Résoudre par la méthode du simplexe. Min x1 − x2+ x3 sous

TD 7 : Exercice corrigé Algorithme du simplexe Méthode des deux

a) Introduisez les variables artificielles et appliquer la méthode des deux phases. ( ). 1. 2. 3. 4. 5. 6. 7.

Recherche opérationnelle

2.2.6 Exercices récapitulatifs . Bien que tr`es efficace cette méthode connue sous le nom d'algorithme du simplexe

Examens avec Solutions Recherche opérationnelle

2 – Résoudre le problème par la méthode du simplexe interpréter les résultats obtenus. Corrigé de l'examen de la session normale. Recherche opérationnelle.

Introduction à loptimisation et la recherche opérationnelle (2017

Algorithme du simplexe – corrigé (20 octobre 2017). Solution de la Dans le cas de cet exercice il n'est pas possible d'utiliser la solution de départ ...

Chapitre 3 Méthode du simplexe

Donc nous avons trouver la solution optimale et l'algorithme se termine à cette étape. 2. Choix de la ligne de pivot. Quels sont les sommets adjacents de

RECHERCHE OPERATIONNELLE

Résoudre par la méthode du simplexe. 4. Expliquer les résultats (variables EXERCICE NUMERO 4 : SIMPLEXE – APPROFONDISSEMENT (à faire). Sujet 1. (D'après ...

SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual

Cela provient du fait que. Excel dans son algorithme du simplexe utilise une construction du dual directe sans passer par On cherche à établir le plan de ...

- Exercices de TD - 1 Modélisation.

Le but de cet exercice est la recherche d'une stratégie mixte optimale pour le jeu de Morra. 4 Simplexe en une phase. - Exercice 34 - Résoudre par la méthode ...

FSJES-AC RECHERCHE OPERATIONNELLE Semestre 6 Filière

La méthode du simplexe est un algorithme qui permet la recherche de la solution optimale d'un EXERCICE : N° 10 - Résolution graphique – résolution simplexe - ...

Recherche opérationnelle

2.2.5 Utilisation de la méthode du simplexe dans un probl`eme de minimisation . . . . . . . 61. 2.2.6 Exercices récapitulatifs .

1 Programmation linéaire

Méthodes Numériques. Document 4 : Corrigé des exercices d'optimisation linéaire Le tableau de départ pour la méthode du simplexe est donc :.

Exercice 1.2.1. Résoudre par le simplexe Max x1 + 2x2 sous ?3x1

2) Tableau du simplexe (forme canonique !) x1 x2 x3 x4 x5 Exercice 1.2.2. x1 x2 x3 x4 ... Exercice 1.2.3. Résoudre par la méthode du simplexe.

FSJES-AC RECHERCHE OPERATIONNELLE Semestre 6 Filière

La méthode du simplexe est un algorithme qui permet la recherche de la solution optimale d'un programme linéaire donné. Dans la partie précédente ( Partie

Introduction à loptimisation et la recherche opérationnelle (2017

Algorithme du simplexe – corrigé (20 octobre 2017) exercice il n'est pas possible d'utiliser la solution de départ usuelle qui.

Examen de recherche opérationnelle – Corrigé

On va maintenant résoudre le probl`eme par la méthode du simplexe. On sait que par cette méthode on se déplace sur les sommets du polytope des solutions

TD 7 : Exercice corrigé Algorithme du simplexe Méthode des deux

a) Introduisez les variables artificielles et appliquer la méthode des deux phases. ( ). 1. 2. 3. 4. 5. 6. 7.

RECHERCHE OPERATIONNELLE

Programmation linéaire : résolution par l'algorithme du simplexe. Programmation linéaire : résolution par Application numéro 8 : EXERCICES AUTO CORRIGES ...

SOLUTIONNAIRE : DUAL EXERCICES 1 Formulation du dual

Cela provient du fait que. Excel dans son algorithme du simplexe utilise une construction du dual directe sans passer par la forme canonique. Il ne faut donc

- Exercices de TD - 1 Modélisation.

Maximiser le gain de l'année par la méthode du simplexe. Le but de cet exercice est la recherche d'une stratégie mixte optimale pour le jeu de Morra.

Examen de recherche op

´erationnelle - Corrig´e

Marc Roelens

´ecembre 2006

1 Ordonnancement de t

ˆaches

1.1

On dresse le tableau des contraintes de pr

´ec´edence :T

ˆacheABCDEFGHIJ

´ec.JHA, HA, BC, IDD, F

On d

´etermine successivement :

- les t

ˆaches de niveau 0 (celles qui n"ont pas d"ant´ec´edent) : ce sont C, D et F (que l"on peut num´eroter

dans cet ordre); - les t

ˆaches de niveau 1 (celles qui n"ont que des ant´ec´edents de niveau 0) : ce sont I et J (que l"on

num

´erote dans cet ordre);

- les t

ˆaches de niveau 2 (celles qui n"ont que des ant´ec´edents de niveau 0 ou 1) : ce sont A et H (que

l"on num

´erote dans cet ordre);

- les t

ˆaches de niveau 3 (celles qui n"ont que des ant´ec´edents de niveau 0, 1 ou 2) : ce sont B et E (que

l"on num

´erote dans cet ordre);

- les t

ˆaches de niveau 4 (celles qui n"ont que des ant´ec´edents de niveau 0, 1, 2 ou 3) : il ne reste plus

que G!

Voici donc le tableau des t

ˆaches avec niveau et num´ero d"ordre :T

ˆacheABCDEFGHIJ

´ec.JHA, HA, BC, IDD, F

Niv.2300304211

N o68129310745

Comme on a r

´eussi`a num´eroter tous les sommets, c"est que le graphe de pr´ec´edence est sans circuit, et la

num

´erotation des sommets constitue un tri topologique (si la tˆache X est avant la tˆache Y, alors le num´ero

de X est inf

´erieur au num´ero de Y).

Une repr

´esentation par niveau possible pour ce graphe est la suivante (on a ajout´e des tˆaches fictives

correspondant au d

´ebut et`a la fin des travaux) :niveau 4

CDF IJ AH E G

Déb

Fin niveau 0 niveau 2 niveau 3 niveau 1 B1 1.2

On porte sur chaque arc du graphe de pr

´ec´edence la dur´ee de la tˆache dont cet arc est issu, et on sait que l"on calcule la date de d ´ebut au plus tˆot en d´eterminant le chemin le plus long depuis le d´ebut des travaux; ceci permet de trouver la dur ´ee minimale d"ex´ecution qui est la date de d´ebut au plus tˆot de la tˆache fictive repr

´esentant la fin des travaux.

Ensuite, on d

´etermine la date de d´ebut au plus tard en calculant le chemin le plus long depuis chaque sommet jusqu" `a cette tˆache fictive de fin des travaux.

Comme le graphe est ordonn

´e par niveaux, ces calculs se font par niveaux croissants pour les dates de d

´ebut au plus tˆot, par niveaux d´ecroissants pour les dates de d´ebut au plus tard. Le r´esultat est r´esum´e sur

le graphe suivant :32,32C D F I JA H

EGDébFin

10108
4 5 5 1 2105
5 3

70,00,5

0,38,9

5,6

5,5 12,1213,1422,31 22,22

BLes dates de d

´ebut au plus tˆot et au plus tard sont indiqu´ees (s´epar´ees par des virgules) au dessus des tˆaches.

On obtient ainsi les r

´eponses :

- la dur ´ee minimale d"ex´ecution est de 32 unit´es; - le chemin critique est D 1.3

Le graphe PERT est d

´ecrit ci-apr`es : il comprend 8´etapes et deux tˆaches fictives (en pointill´es), de dur ´ees nulles, servant`a repr´esenter les contraintes de pr´ec´edence. [32,32]

H (5) B (8)

G (10)

A (10) E (1)J (7)C (4)

D (5)

F (2)I (3)

[12,12][8,9] [5,5] [0,0][13,14] [22,22][22,22]Pour chaque

´etape, on a indiqu´e la date au plus tˆot et la date au plus tard (entre crochets). Le chemin critique

est (heureusement!) le m ˆeme que celui calcul´e par le graphe de pr´ec´edence. On peut alors calculer les marges libres, totales et certaines, dont on rappelle la d

´efinition. Pour toute

etapeei, on notetila date au plus tˆot de cette´etape, ett?ila date au plus tard. Alors, pour une tˆacheXjde

dur ´eedj, comprise entre l"´etapek(avant) et l"´etapel(apr`es), on d´efinit : -MT(Xj) =t?l-tk-dj(marge totale deXj); -ML(Xj) =tl-tk-dj(marge libre deXj); -MC(Xj) =tl-t?k-dj(marge certaine deXj).

On obtient les r

´esultats suivants :T

ˆacheABCDEFGHIJ

T0150930110

L0140930000

C0040930000

2 1.4

On voit sur le tableau pr

´ec´edent que la marge totale de H est de 1 unit´e : donc, l"augmentation de 1 unit

´e de la dur´ee de H va r´esorber cette marge (sans pour autant d´ecaler la fin du projet). Si H augmente`a

nouveau de 1 unit ´e, alors on obtient un nouveau chemin critique D et la dur ´ee minimale d"ex´ecution du projet passe`a 33 unit´es de temps.

2 Allocation de ressources

2.1

On note doncxjla quantit´e de cageots plac´ee dans le magasinj. Ces variablesxjsont enti`eres, posi-

tives, inf ´erieures`a la valeurn. Le b´en´efice global (que l"on cherche`a maximiser) est donc :

F(x1,···,xm) =m?

j=1b(xj,j) en respectant bien s ˆur la contrainte que le nombre total de cageots estn, c"est-`a-dire : m j=1x j=n

C"est donc un probl

`eme de programmation dynamique. 2.2

On note alors, pour0≤i≤net0≤j≤m,P(i,j)le profit maximum obtenu en vendanticageots

dans lesjpremiers magasins. On a bien´evidemment : (?i? {0..n})(P(i,1) =b(i,1))

Ensuite, pourj≥2, pour placer optimalementicageots dans lesjpremiers magasins, on peut dire l"on

placexj≤icageots dans le magasinjeti-xjde fac¸on optimale dans lesj-1premiers magasins. On choisit bien s ˆur la valeur dexjqui maximise la somme des b´en´efices obtenus. En clair :

P(i,j) = max0≤xj≤ib(xj,j) +P(i-xj,j-1)

2.3quotesdbs_dbs2.pdfusesText_3

[PDF] Examen de recherche opérationnelle – Corrigé

Examen de recherche op

´erationnelle - Corrig´e

Marc Roelens

´ecembre 2006

1 Ordonnancement de t

ˆaches

On dresse le tableau des contraintes de pr

´ec´edence :T

ˆacheABCDEFGHIJ

´ec.JHA, HA, BC, IDD, F

´etermine successivement :

´erote dans cet ordre);

´erote dans cet ordre);

´erote dans cet ordre);

Voici donc le tableau des t

ˆaches avec niveau et num´ero d"ordre :T

ˆacheABCDEFGHIJ

´ec.JHA, HA, BC, IDD, F

Niv.2300304211

Comme on a r

´erieur au num´ero de Y).

Une repr

´ebut et`a la fin des travaux) :niveau 4

Déb

On porte sur chaque arc du graphe de pr

´esentant la fin des travaux.

Ensuite, on d

Comme le graphe est ordonn

EGDébFin

70,00,5

0,38,9

5,5 12,1213,1422,31 22,22

BLes dates de d

On obtient ainsi les r

´eponses :

Le graphe PERT est d

H (5) B (8)

G (10)

A (10) E (1)J (7)C (4)

F (2)I (3)

´efinition. Pour toute

On obtient les r

´esultats suivants :T

ˆacheABCDEFGHIJ

T0150930110

L0140930000

C0040930000

On voit sur le tableau pr

2 Allocation de ressources

F(x1,···,xm) =m?

C"est donc un probl

P(i,j) = max0≤xj≤ib(xj,j) +P(i-xj,j-1)