____________________________________________________________________________ IUT de Saint-Etienne – Département TC –J.F.Ferraris – Math – S1 – CalcAn – CoursEx – Rev2014 – page 33 sur 69

4 1er

degré : introduction à la programmation linéaire

Programmation linéaire :

Recherche du maximum ou du minimum d'une fonction (économique le plus souvent) compte

tenu de certaines contraintes représentées par des équations ou des inéquations du premier

degré.

Nous travaillerons ici exclusivement sur des problèmes linéaires et à deux variables (cas plus

complexes traités en deuxième année et – heureusement - sur tableur). Malgré la simplicité (non

apparente) de ce que nous traiterons au-dessous, la méthodologie que nous allons suivre est très

générale : c’est celle de la mise en équation d’un problème, quel qu’il soit.

Progressons par étapes, en suivant un exemple "fil rouge".

Exemple fil rouge :

Une société met en bouteille de l'eau minérale, suivant deux conditionnements :

* par bouteilles d'un litre et demi, vendues 80 € le lot de cent bouteilles,

* par bouteilles d'un demi litre, vendues 30 € le lot de cent bouteilles.

Pour être produite, chaque bouteille doit passer par 3 ateliers :

atelier 1 : remplissage ; durée maximale de travail hebdomadaire : 68 h,

atelier 2 : sertissage, étiquetage ; durée maximale de travail hebdomadaire : 88 h,

atelier 3 : emballage, conditionnement ; durée maximale de travail hebdomadaire : 76 h.

Le tableau ci-dessous indique les temps nécessaires, en heures, à prévoir dans chaque atelier pour

chaque lot de 100 bouteilles à produire (les données sont volontairement simplistes, voire

irréalistes, pour faciliter les calculs dans le cadre de cet exemple) :

atelier 1 atelier 2 atelier 3

1,5 L 3 h 3 h 1 h

0,5 L 1 h 2 h 2 h

Combien doit-on produire (et vendre) de chaque type de lot pour optimiser le chiffre d'affaires ?

4.1 Mise en équation des contraintes

Les temps maximum passés dans chaque atelier ne permettent pas de produire à l'infini…

TD4.1 : Système de contraintes

a. Que sont ici les variables ?

____________________________________________________________________________ IUT de Saint-Etienne – Département TC –J.F.Ferraris – Math – S1 – CalcAn – CoursEx – Rev2014 – page 34 sur 69

b. Sur quelles grandeurs l’énoncé pose-t-il des contraintes ?

c. Pour ces quantités produites variables x et y, comment exprimer le temps passé dans

l'atelier 1 ?

d. Faire de même pour les ateliers 2 et 3

e. Récapituler l'ensemble des contraintes imposées aux quantités x et y dans un système

unique, où chaque inéquation sera écrite sous sa forme réduite.

4.2 Représentation graphique - polygone des contraintes

Une inéquation linéaire du premier degré à deux inconnues a pour forme cartésienne :

Ax + By + C < 0 , et pour forme réduite : y < ax + b ou y > ax + b ou x < c ou x > c.

Ses solutions sont les couples (x, y) correspondant aux points d'un demi-plan délimité par la

droite d'équation y = ax + b ou d'équation x = c.

Les solutions d'un système composé de telles inéquations sont les couples (x, y)

correspondant aux points communs aux demi-plans solutions de chaque équation.

On pratique là un régionnement du plan.

____________________________________________________________________________ IUT de Saint-Etienne – Département TC –J.F.Ferraris – Math – S1 – CalcAn – CoursEx – Rev2014 – page 35 sur 69

TD4.2 : Polygone des contraintes

a. Représenter ci-dessous, dans un repère orthogonal, les droites issues des inéquations du

système de contraintes obtenu au TD1 : on légendera correctement les axes du repère ainsi

que les droites tracées

Mettre en évidence la région du plan solution du système.

Marquer en gras le polygone des contraintes, frontière de cette région.

____________________________________________________________________________ IUT de Saint-Etienne – Département TC –J.F.Ferraris – Math – S1 – CalcAn – CoursEx – Rev2014 – page 36 sur 69

b. Donner les coordonnées des sommets de ce polygone.

c. L'entreprise peut-elle produire 5 lots de 100 bouteilles de 1,5 L et 15 lots de 0,5 L ?

d. L'entreprise peut-elle produire 20 lots de 100 bouteilles de 1,5 L et 20 lots de 0,5 L ?

____________________________________________________________________________ IUT de Saint-Etienne – Département TC –J.F.Ferraris – Math – S1 – CalcAn – CoursEx – Rev2014 – page 37 sur 69

4.3 Droites d'iso-profit (ou iso-coût), optimisation

Une équation du type C = ax + by reliant deux variables x et y se traduit par une droite du plan.

Si b est différent de 0, son équation réduite s'exprime ainsi : y = -(a/b)x + C/b.

-(a/b) est son coefficient directeur, ou pente ;

C/b est son ordonnée à l'origine, ordonnée du point d'intersection entre la droite et l'axe (Oy).

Supposons a et b fixés, et gardons la possibilité de faire varier C.

A chaque valeur de C correspond une droite ; on peut donc créer une famille de droites.

Les droites de cette famille ont toutes la même pente (-a/b) : elles sont parallèles entre elles.

Leurs ordonnées à l'origine, C/b, sont proportionnelles à C.

TD4.3 : Fonction objectif, droites d'iso-profit

On appelle C(x, y) le chiffre d'affaires réalisé par la vente de x lots de 100 bouteilles de 1,5 L

et de y lots de 100 bouteilles de 0,5 L.

C sera à optimiser : c'est notre fonction objectif.

a. Calculer C(5, 15) puis C(20, 20).

b. Pour en simplifier l'écriture, on notera C le chiffre d'affaires défini ci-dessus.

Exprimer C en fonction de x et y.

Mettre cette expression sous la forme de l'équation réduite d'une droite DC.

c. Tracer sur le graphique du TD4.2, les droites D1200 et D2400.

____________________________________________________________________________ IUT de Saint-Etienne – Département TC –J.F.Ferraris – Math – S1 – CalcAn – CoursEx – Rev2014 – page 38 sur 69

d. Répondre graphiquement aux questions suivantes :

Existe-t-il des productions réalisables - couples (x, y) - donnant un chiffre d'affaires de 1200 € ?

Existe-t-il des productions réalisables - couples (x, y) - donnant un chiffre d'affaires de 2400 € ?

e. La droite d'iso-profit maximisant le chiffre d'affaires est celle qui, tout en possédant au

moins un point commun avec l'intérieur du polygone des contraintes ou avec le polygone lui-

même, possède la plus grande ordonnée à l'origine possible. Trouver cette droite,

graphiquement.

f. Récapituler :

Le chiffre d'affaires maximum possible correspond à la production (…… ; ……) et vaut …………€.

____________________________________________________________________________ IUT de Saint-Etienne – Département TC –J.F.Ferraris – Math – S1 – CalcAn – CoursEx – Rev2014 – page 39 sur 69

4.4 Exercices

4.4.1

Une entreprise fabrique deux produits A et B. Le produit A nécessite 2 heures de travail sur la

machine M, 3 heures de main d'œuvre et 3 kg de matière première. Le produit B nécessite 1 heure

de travail sur la machine M, 1 heure de main d'œuvre et 3 kg de matière première. Le produit A

rapporte un bénéfice de 80 euros, le produit B de 40 euros.

Sachant que l'entreprise ne dispose que de 800 heures de la machine M par mois, 900 heures de

main d'œuvre et 1500 kg de matière première, déterminer les quantités des produits A et B qu'elle

doit fabriquer par mois afin de réaliser un bénéfice mensuel maximum.

Quel est alors ce bénéfice ?

4.4.2

Pour fleurir un parc, il faut au minimum : 1200 jacinthes, 3200 tulipes et 3000 narcisses.

Deux pépiniéristes proposent :

* l'un le lot A : 30 jacinthes, 40 tulipes et 30 narcisses, pour 75 €

* l'autre le lot B : 10 jacinthes, 40 tulipes et 50 narcisses, pour 60 €

Combien de lots A et de lots B doit-on acheter pour que la dépense soit minimale ?

Quelle est alors cette dépense ?

4.4.3

La société DevS1 commercialise deux types de coffres métalliques, qu'elle doit faire transporter

par camion de son site de production vers son site de vente. Un coffre de type A a un volume de

0,2 m³ et pèse 80kg ; un coffre de type B a un volume de 0,5 m³ et pèse 120kg. Un camion du

transporteur a une capacité de 20 m³ et de 6,24 tonnes.

Ce transporteur facture à DevS1 10€ par coffre A et 15€ par coffre B transporté, alors qu'un coffre

A vendu rapporte 35€ à DevS1 et qu'un coffre B lui rapporte 55€.

L'objectif est ici de connaître les nombres de coffres A et B à charger dans un camion pour que le

bénéfice réalisé par DevS1 soit optimisé.

1) Contraintes

a. Exprimer en fonction des nombres de coffres x et y la contrainte de volume d'un camion.

b. Exprimer en fonction des nombres de coffres x et y la contrainte de charge d'un camion.

c. Montrer que ces deux contraintes peuvent se résumer au système suivant :

,0 4 40

252

3

y x

y x

≤ − + < − +

d. Que sait-on de plus sur la nature des nombres x et y ?

e. Représenter graphiquement les solutions (zone hachurée) de ce système.

échelles : 1 cm pour 10 coffres A, 1 cm pour 5 coffres B.

____________________________________________________________________________ IUT de Saint-Etienne – Département TC –J.F.Ferraris – Math – S1 – CalcAn – CoursEx – Rev2014 – page 40 sur 69

2) Fonction objectif : le bénéfice

a. Exprimer le bénéfice B réalisé par DevS1 lors du transport de x coffres A et y coffres B.

b. Montrer que, sous forme réduite, l'expression devient : ,B

y x= − +0 62540

c. Tracer sur votre graphique la droite correspondant à un bénéfice de 800€.

d. La droite de bénéfice optimale est-elle la plus haute ou la plus basse possible ? Pourquoi ?

e. Tracer cette droite, donnant le meilleur bénéfice possible. Expliquer.

f. Combien de coffres de chaque type faut-il placer dans un camion pour optimiser le

bénéfice ?

g. Que vaut alors ce bénéfice ?

h. Vérifier que cette valeur concorde avec l'ordonnée à l'origine de votre droite.