Scribd
Importer
51 vues2 pages

Bierlaire SessionTwo Enonce

Le document présente trois questions sur l'optimisation linéaire. La première question décrit un domaine de solutions admissibles et demande de déterminer les contraintes et la solution optimale. La deuxième question présente un problème d'optimisation à reformuler avec moins de contraintes. La troisième question analyse l'impact d'une nouvelle contrainte sur la solution optimale d'un problème graphique.

Transféré par

lovebooks
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
51 vues2 pages

Bierlaire SessionTwo Enonce

Le document présente trois questions sur l'optimisation linéaire. La première question décrit un domaine de solutions admissibles et demande de déterminer les contraintes et la solution optimale. La deuxième question présente un problème d'optimisation à reformuler avec moins de contraintes. La troisième question analyse l'impact d'une nouvelle contrainte sur la solution optimale d'un problème graphique.

Transféré par

lovebooks
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Introduction

à l’optimisation
Fall 2014 - 2015
Enseignant: M. Bierlaire
Session 2: Optimisation linéaire : analyse des con-
traintes

Question 1: (À résoudre sur le tableau par le chargé de cours)

Soit le domaine des solutions admissibles représenté par la partie ombragée sur la figure
suivante.

a) Donner toutes les contraintes qui définissent le domaine des solutions admissibles.
(format canonique)

b) Si c1 x1 +x2 est la fonction d’objective qu’il faut maximiser, quelle(s) valeur(s) doit-on
donner à c1 pour que P (1, 3) soit la solution optimale unique?

c) Si c1 = 2 et qu’il en coûte un montant fixe de 6$ pour remplacer la première con-


trainte par x1 − x2 ≤ 4 et la fonction objectif montre le profit ($), est-il avantageux
de remplacer cette contrainte? Quel est le gain ou la perte?

Question 2: (À résoudre par les étudiants en classe)

Consider the problem

min −3x − 2y
s.c. x − y ≥ −2
2x + y ≤ 8
x + y ≤ 5
x + 2y ≤ 10
x ≥ 0
y ≥ 0

1
a) Reformulate this problem with minimum number of constraints. Call this new math-
ematical model D.

b) Draw the domain D of the feasible solutions of the problem. Enumerate the vertices
of D.

c) Resolve the problem D graphically.

d) Express the linear program of D in canonical form and standard form.

Question 3: (À résoudre par les étudiants en classe s’il y a le temps, sinon à résoudre
à la maison )

Soit le domaine des solutions admissibles représenté par la partie ombragée sur la figure
suivante

Le programme linéaire associé à ce domaine est:

max 4x1 + x2
s.c. 3x1 + x2 ≥ 3
3x1 + 4x2 ≤ 16
x1 − x2 ≤ 3
x 1 , x2 ≥ 0

1. Si on ajoute la contrainte x1 − 2x2 ≤ 1, quelle est la solution optimale du problème?


Résoudre par la méthode graphique et donner les valeurs des variables et celle de la
fonction objectif.

2. Est-ce que P pourrait être le point optimal ? Quelles sont les situation des points
C et E ?

3. Si la fonction objectif est max(c1 x1 + c2 x2 ), quelle(s) valeur(s) faut-il imposer à c1


et c2 pour que le point P (2, 2.5) soit une solution optimale?

Vous aimerez peut-être aussi