BURHAN.

Programmation linéaire : Cours de Mathématiques TC Sciences, chapitre Équations, inéquations et systèmes

Programmation linéaire : notion du chapitre Équations, inéquations et systèmes du programme de maths Tronc commun Sciences, expliquée pas à pas, avec 2 exemples guidés. Pour les élèves de TC Sciences et Technologique, option française (BIOF).

Notions du cours (10)

Apprendre avec Burhan

Programmation linéaire simple

Étape 1 sur 4

Un atelier de menuiserie

Un atelier de menuiserie fabrique chaque jour xx tables et yy chaises. Une table demande 22 h d'assemblage et 11 h de vernissage. Une chaise demande 11 h d'assemblage et 22 h de vernissage. L'atelier dispose au plus de 1616 h d'assemblage et de 1414 h de vernissage par jour. Il gagne 200200 dirhams par table et 150150 dirhams par chaise. Que fabriquer pour gagner le plus ?

Devine : Le meilleur choix

Parmi ces productions, laquelle rapporte le plus en respectant les heures disponibles ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :88 tables, aucune chaise.

Faux.

Elle respecte les heures, mais rapporte seulement 16001600 dirhams.

Choix B :Aucune table, 77 chaises.

Faux.

Elle respecte les heures, mais rapporte seulement 10501050 dirhams.

Choix C :44 tables et 55 chaises.

Faux.

Elle respecte les heures, car 13≤1613 \leq 16 et 14≤1414 \leq 14. Mais elle rapporte 15501550 dirhams.

Choix D :66 tables et 44 chaises.

Juste.

Juste : elle utilise toutes les heures et rapporte 18001800 dirhams.

Voir la correction complète

Pour 66 tables et 44 chaises : 2×6+4=162 \times 6 + 4 = 16 h d'assemblage, et 6+2×4=146 + 2 \times 4 = 14 h de vernissage. Le gain vaut 200×6+150×4=1800200 \times 6 + 150 \times 4 = 1800 dirhams. La suite permet de vérifier, avec la propriété « Programmation linéaire : valeur extrême en un sommet », qu'aucune autre production ne fait mieux.

Méthodeun problème de programmation linéaire

  1. Nomme les inconnues, puis traduis chaque contrainte par une inéquation. N'oublie pas x≥0x \geq 0 et y≥0y \geq 0.
  2. Représente la région des solutions, puis calcule ses sommets en résolvant des systèmes.
  3. Écris la quantité à rendre la plus grande, ou la plus petite, sous la forme λx+μy\lambda x + \mu y, où λ\lambda et μ\mu sont deux nombres donnés (ici 200200 et 150150).
  4. Calcule sa valeur en chaque sommet, puis conclus dans le langage de la situation.

Continuer : La région des productions possibles →

Étape 2 sur 4

La région des productions possibles

Exemplemettre l'atelier en inéquations

Les heures disponibles donnent le système : {x≥0y≥02x+y≤16x+2y≤14\begin{cases} x \geq 0 \\ y \geq 0 \\ 2x + y \leq 16 \\ x + 2y \leq 14 \end{cases} Sa région est un quadrilatère de sommets O(0,0)O(0, 0), A(8,0)A(8, 0), B(6,4)B(6, 4) et C(0,7)C(0, 7). Le sommet BB est le point commun des droites 2x+y=162x + y = 16 et x+2y=14x + 2y = 14 : D=3D = 3, Dx=18D_x = 18 et Dy=12D_y = 12, donc B(6,4)B(6, 4). Le gain vaut 200x+150y200x + 150y dirhams.

Repère gradué, x pour les tables et y pour les chaises. La droite d'équation 2x + y = 16 descend fortement et passe par A(8, 0). La droite d'équation x + 2y = 14 descend doucement et passe par C(0, 7). Elles se coupent en B, de coordonnées (6, 4). Le quadrilatère de sommets O, A, B et C est teinté : ce sont les productions qui respectent les heures disponibles.

La région des productions possibles de l'atelier est le quadrilatère teinté OABC, limité par les axes et par les droites 2x + y = 16 et x + 2y = 14.

PropriétéProgrammation linéaire : valeur extrême en un sommet

Le plan est rapporté à un repère. Soit P\mathcal{P} une région du plan non vide, formée des points M(x,y)M(x, y) dont les coordonnées vérifient un système d'inéquations larges (≤\leq ou ≥\geq) du premier degré à deux inconnues, et limitée par un polygone, côtés compris. Soit λ\lambda et μ\mu deux réels.

Parmi les points M(x,y)M(x, y) de P\mathcal{P}, l'expression λx+μy\lambda x + \mu y prend sa plus grande valeur et sa plus petite valeur en des sommets du polygone.

Remarque

Ce résultat est admis. Sa démonstration demande des outils qui dépassent ce chapitre ; la suite l'illustre sur l'atelier.

← Étape précédenteContinuer : Les valeurs aux sommets →

Étape 3 sur 4

Les valeurs aux sommets

En clair. Fixe un gain, par exemple 12001200 dirhams. Les productions qui le donnent vérifient 200x+150y=1200200x + 150y = 1200 : c'est une droite, qui passe par (6,0)(6, 0) et (0,8)(0, 8). Pour un gain plus grand, la droite 200x+150y=k200x + 150y = k glisse parallèlement à elle-même, en s'éloignant de OO. Pour l'atelier, la dernière de ces droites qui touche encore la région passe par le sommet B(6,4)B(6, 4). Cette observation illustre la propriété précédente ; elle ne la démontre pas.

Repère gradué avec la région teintée OABC des productions possibles. Une droite en pointillés, d'équation 200x + 150y = 1200, passe par (6, 0) et (0, 8) et traverse la région. Une seconde droite, d'équation 200x + 150y = 1800, lui est parallèle, comme l'indique le même chevron, et passe par le sommet B(6, 4) sans entrer dans la région. Une flèche va de la première droite vers la seconde, en s'éloignant de O : c'est le sens où le gain augmente.

Deux droites de gain parallèles : celle de 1200 dirhams, en pointillés, traverse la région, celle de 1800 dirhams ne la touche plus qu'au sommet B ; la flèche montre le sens où le gain augmente.

Exemplecomparer les sommets

On calcule le gain 200x+150y200x + 150y en chaque sommet :

  • en O(0,0)O(0, 0) : 00 ;
  • en A(8,0)A(8, 0) : 16001600 ;
  • en B(6,4)B(6, 4) : 1200+600=18001200 + 600 = 1800 ;
  • en C(0,7)C(0, 7) : 10501050.

D'après la propriété « Programmation linéaire : valeur extrême en un sommet », le plus grand gain est atteint en BB. L'atelier fabrique 66 tables et 44 chaises par jour, pour 18001800 dirhams.

Avec une contrainte « au moins 33 meubles », soit x+y≥3x + y \geq 3, le point OO ne convient plus : 0≥30 \geq 3 est faux. On garde le demi-plan opposé à OO. Les sommets sont alors (3,0)(3, 0), AA, BB, CC et (0,3)(0, 3). Pour la plus petite valeur, on garde le sommet où la valeur est la plus petite : 450450 dirhams en (0,3)(0, 3).

Attentiontous les sommets, toutes les contraintes

✗ « On compare A(8,0)A(8, 0) et C(0,7)C(0, 7) : le meilleur gain vaut 16001600 dirhams. »

✓ Le sommet BB, point commun de deux contraintes, a été oublié. Liste tous les sommets de la région, y compris ceux des axes. N'oublie pas non plus x≥0x \geq 0 et y≥0y \geq 0 : un nombre de tables n'est jamais négatif.

← Étape précédenteContinuer : Un autre gain, puis à toi →

Étape 4 sur 4

Un autre gain, puis à toi

Vérifie : Si le gain change

Le gain par table passe à 400400 dirhams, celui par chaise reste 150150 dirhams. Les heures disponibles ne changent pas. Quel sommet donne le plus grand gain ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :Le sommet A(8,0)A(8, 0).

Juste.

Juste : 400×8=3200400 \times 8 = 3200 dépasse les autres valeurs.

Choix B :Le sommet B(6,4)B(6, 4).

Faux.

En BB, le gain vaut 2400+600=30002400 + 600 = 3000, moins qu'en AA.

Choix C :Le sommet C(0,7)C(0, 7).

Faux.

En CC, le gain vaut seulement 10501050.

Choix D :Le sommet O(0,0)O(0, 0).

Faux.

En OO, l'atelier ne fabrique rien : le gain est nul.

Voir la correction complète

On calcule 400x+150y400x + 150y aux sommets : 00 en OO, 32003200 en AA, 30003000 en BB, 10501050 en CC. Le plus grand gain est en AA : 88 tables, aucune chaise. La région ne change pas, mais le meilleur sommet change avec le gain.

À toi : Une semaine plus calme

Une autre semaine, l'atelier dispose au plus de 1010 h d'assemblage et de 88 h de vernissage par jour. Les gains restent 200200 dirhams par table et 150150 dirhams par chaise. Trouve la production qui rapporte le plus. Écris ta réponse sur ton cahier avant de dévoiler la correction.

Besoin d'aide ? Indice 1

Le système devient x≥0x \geq 0, y≥0y \geq 0, 2x+y≤102x + y \leq 10 et x+2y≤8x + 2y \leq 8.

Encore bloqué ? Indice 2

Les sommets sur les axes se lisent avec x=0x = 0 puis y=0y = 0 ; cherche le quatrième par un déterminant.

Encore bloqué ? Indice 3

Point délicat : compare les gains en tous les sommets, OO compris.

Voir la solution complète

Le quatrième sommet vérifie {2x+y=10x+2y=8\begin{cases} 2x + y = 10 \\ x + 2y = 8 \end{cases} : D=3D = 3, Dx=12D_x = 12 et Dy=6D_y = 6, donc c'est (4,2)(4, 2). Les gains valent 00 en OO, 10001000 en (5,0)(5, 0), 11001100 en (4,2)(4, 2) et 600600 en (0,4)(0, 4). L'atelier fabrique 44 tables et 22 chaises par jour, pour 11001100 dirhams.

RemarqueCoin devoir : rédiger la conclusion

En devoir, la conclusion revient à la situation. Pour l'atelier, écris : « La région des solutions a pour sommets O(0,0)O(0, 0), A(8,0)A(8, 0), B(6,4)B(6, 4) et C(0,7)C(0, 7). Le gain y vaut 00, 16001600, 18001800 et 10501050 dirhams. Le plus grand gain est atteint en BB : l'atelier doit fabriquer 66 tables et 44 chaises par jour. » Donne toujours les sommets, les valeurs, puis la réponse en mots.

← Étape précédenteFin de la notion

S'entraîner sur cette notion

Sources du cours

  • Référentiel BURHAN du chapitre « Équations, inéquations et systèmes » (tc · sciences · mathematiques)