Scribd
Importer
86 vues1 page

Programmation linéaire en informatique

Le document présente trois exercices de mathématiques portant sur la programmation linéaire. L'exercice 1 concerne l'optimisation des bénéfices d'une entreprise produisant des sauces. L'exercice 2 traite de la résolution d'un problème d'optimisation linéaire. L'exercice 3 porte sur la résolution d'un problème d'optimisation linéaire et l'utilisation des conditions d'optimalité primal-dual.

Transféré par

Badreddine Essaidi
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
86 vues1 page

Programmation linéaire en informatique

Le document présente trois exercices de mathématiques portant sur la programmation linéaire. L'exercice 1 concerne l'optimisation des bénéfices d'une entreprise produisant des sauces. L'exercice 2 traite de la résolution d'un problème d'optimisation linéaire. L'exercice 3 porte sur la résolution d'un problème d'optimisation linéaire et l'utilisation des conditions d'optimalité primal-dual.

Transféré par

Badreddine Essaidi
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

Mathématiques pour l’informatique Université de Provence

Licence Informatique
Partiel. Durée 2 heures.
Année 2002-2003

Exercice 1 (10 pts) Une compagnie fabrique deux types de sauces : une sauce tomate et
une sauce aux légumes. Chacune est obtenue en mélangeant des légumes et du concentré de
tomates. Le concentré de tomates doit représenter au moins la moitié de la composition de
la sauce tomate. Les légumes doivent représenter au moins le tiers de la composition de la
sauce aux légumes. Chaque jour la compagnie peut acheter jusqu’à 4 tonnes de légumes à 5
euros le kg, et 3 tonnes de concentré de tomates à 3 euros le kg. La compagnie vend un kilo
de sauce tomate à 8 euros, et un kilo de sauce aux légumes à 7 euros. La capacité d’absorp-
tion du marché est illimitée. La compagnie cherche à réaliser le plus grand bénéfice possible.

1. Modéliser le problème en un problème de programmation linéaire (pas plus de quatre


variables). On le note (P).
2. Ecrire le problème (Q) dual de (P).
3. Trouver des bornes inférieures strictement positives pour deux des variables duales.
(On rappelle que les variables duales sont positives ou nulles).
4. En utilisant le théorème des écarts complémentaires, résoudre (P).
Exercice 2 (5 pts) On considère le problème
M in z = −3x1 + 2x2
−x1 − x2 + e1 = −4
2x1 + x2 ≤ 6
x1 , x2 ≥ 0, e1 ≤ 0
1. Transformer le problème en un problème en forme standard.
2. Résoudre le problème en forme standard par l’algorithme du simplexe.
3. En considérant que la variable e01 = −e1 est une variable d’écart rajoutée à un
problème en forme canonique, donner le problème canonique de départ et le résoudre
graphiquement.
4. Calculer le dual et en donner une solution. Est-elle unique ?
Exercice 3 (5 pts) On considère le problème :
M in w = 12x1 + 5x2
2x1 + x2 ≥ 4
3x1 + x2 ≥ 5
x1 + x 2 ≥ 0
x1 , x2 , x3 quelconques.
1. Calculer le problème dual (ne pas oublier que le dual du dual est le primal).
2. Résoudre le problème dual par le simplexe.
3. Que vaut la fonction objectif du problème initial à l’optimum ? Pour quelles valeurs
cet optimum est-il atteint (utiliser les conditions d’optimalité primal-dual) ?

Vous aimerez peut-être aussi