26/01/2014

1

RCP104

Optimisation en Informatique

2013 – 2014

Dr. Nazih OUWAYEDnazih.ouwayed@gmail.com

http://nouwayed.yolasite.com

TD 4 : Méthodes des coupes

Exercice 1 (1/6)

Janvier 2014RCP104 – Optimisation en Informatique2

� Soit le PLNE suivant :Max Z = 5x1 + 8x2

S. C :

x1 + x2 ≤ 6

5 x1 + 9 x2 ≤ 45

x1, x2 ≥ 0 et entier

26/01/2014

2

Exercice 1 (2/6)

Janvier 2014RCP104 – Optimisation en Informatique3

� Voici la nouvelle forme du PLNE après l’ajout desvariables d’écart :Max Z = 5x1 + 8x2

S. C :

x1 + x2 + x3 = 6

5 x1 + 9 x2 + x4 = 45

x1, x2 ≥ 0 et entier

Le tableau du simplexe du PL est le suivant :

Exercice 1 (3/6)

Janvier 2014RCP104 – Optimisation en Informatique4

� Résolvez graphiquement le problème (Il n’est pasnécessaire de trouver une solution entière) ?

� Calculez la coupe de Gomory à partir de la deuxièmeligne de tableau du simplexe ?

� Tracez graphiquement la nouvelle contrainte et montrerque la solution obtenue est entière ?

26/01/2014

3

Exercice 1 (4/6)

Janvier 2014RCP104 – Optimisation en Informatique5

� Résolvez graphiquement le problème (Il n’est pasnécessaire de trouver une solution entière) ?

(2.25, 3.75)

x1 + x2 ≤≤≤≤ 6

5 x1 + 9 x2 ≤≤≤≤ 45

Exercice 1 (5/6)

Janvier 2014RCP104 – Optimisation en Informatique6

� Calculez la coupe de Gomory à partir de la première lignede tableau du simplex ?

0x1 + x2 - 1.25x3 + 0.25x4 = 3.75

� 0x1 + 0x2 + 0.75x3 + 0.25x4 ≥ 0.75

Ce qui donne la nouvelle contrainte

en x1 et x2 : 8x1 + 12x2 ≤ 60 Détails dans Annex A

26/01/2014

4

Exercice 1 (6/6)

Janvier 2014RCP104 – Optimisation en Informatique7

� Tracez graphiquement la nouvelle contrainte et montrerque la solution obtenue est entière ?

(0, 5)

x1 + x2 ≤≤≤≤ 6

5 x1 + 9 x2 ≤≤≤≤ 45

8x1 + 12x2 ≤≤≤≤ 60

Exercice 2 (1/5)

Janvier 2014RCP104 – Optimisation en Informatique8

� Une compagnie procède à la fabrication de trois produits, P1,P2 et P3, en utilisant successivement trois types de machinesdifférentes, M1, M2 et M3. Les données du problème sontreprésentées dans le tableau suivant, qui indique :� Pour chaque produit et chaque type de machine, le nombre d’heures

de traitement requises pour fabriquer une unité du produit;

� Pour chaque type de machine, la capacité, soit le nombre d’heures parsemaine pouvant être consacrées à la fabrication machines de chaquetype);

� Pour chaque produit, le profit par unité (en €);

Le problème consiste à déterminer combien d’unités de chaqueproduit doivent être fabriquées de façon à maximiser le profittotal.

26/01/2014

5

Exercice 2 (2/5)

Janvier 2014RCP104 – Optimisation en Informatique9

� Formulez ce problème à l’aide d’un modèle deprogrammation linéaire ?

� Formulez le dual de ce problème et proposez uneinterprétation des variables duales ?

� La solution optimale du dual W= 2937,5 avecy1 =5; y2

=1,25; y3=0. Déduisez la solution du primal Z ?

Exercice 2 (3/5)

Janvier 2014RCP104 – Optimisation en Informatique10

� Formulez ce problème à l’aide d’un modèle deprogrammation linéaire ?

� Variablesxi = nombre d’unités fabriquées du produit Pi

� ObjectifMax Z = 50x1 + 20x2 + 25x3

� Contraintes 9x1 + 3x2 + 5x3 ≤ 5005x1 + 4x2 ≤ 3503x1 + 2x3 ≤ 150x1 , x2 , x3 ≥ 0

26/01/2014

6

Exercice 2 (4/5)

Janvier 2014RCP104 – Optimisation en Informatique11

� Formulez le dual de ce problème et proposez uneinterprétation des variables duales ?

� Variablesyj = prix (€/heure) pour louer une machine j à l’usine

� ObjectifMin W= 500y1 + 350y2 + 150y3

� Contraintes9y1 + 5y2 + 3y3 ≥ 503y1 + 4y2 ≥ 205y1 + 2y3 ≥ 25y1 , y2 , y3 ≥ 0

Exercice 2 (5/5)

Janvier 2014RCP104 – Optimisation en Informatique12

� La solution optimale du dual W= 2937,5 avecy1 =5; y2

=1,25; y3=0. Déduisez la solution du primal Z ?

� La solution optimale du primal Z = 2937,5 avecx1 =0; x2

=87,5; x3=47,5

26/01/2014

7

Annexe A

Janvier 2014RCP104 – Optimisation en Informatique13

Références

Janvier 2014RCP104 – Optimisation en Informatique14

� Méthodes de coupe de Gomory - Moshe Sniedovich’s, Université de Melbourne

� Modèles de recherche opérationnelle - Bernard Gendron, Université de montréal