جاهعــة عبد الحويد ابن باديس
UNIVERSITE ABDELHAMID IBN BADIS MOSTAGANEM
هستغانن
FACULTE DES SCIENCES EXACTES ET DE L’INFORMATIQU كلية العلوم الدقيقة و األعالم األلي
DEPARTEMENT DE MATHEMATIQUES ET INFORMATIQUE قسن الرياضيات و األعالم األلي
L3 : Informatique
Responsable de la matière :BAHNES NACERA
[Link]@[Link]
Chapitre 1 : Introduction et propriétés de la programmation linéaire
Chapitre 2 : Méthodes de résolution
Résolution graphique
Méthode de simplexe
Méthode des 2 phases
Méthode de grand M (big M )
Méthode révisé du simplexe
Chapitre 3 : Dualité en programmation linéaire
Forme dual
Règles de passages du primal au dual
Principaux théorèmes dualité forte, théorème des écarts complémentaires
Interprétation économique
Algorithme dual du simplexe
Chapitre 4 : Problème du transport et d’affectation
2 @mail: [Link]@[Link] 2020/2021
Introduction
Modélisation d’un problème d’optimisation
Formes de PL
Exemples
3 @mail: [Link]@[Link] 2020/2021
• La programmation linéaire s’inscrit dans le domaine de la recherche opérationnelle
(RO), qui consiste à la résolution de problèmes complexes visant à obtenir le
meilleur résultats possible en tenant compte de certaines contraintes.
• La programmation linéaire est une technique mathématique d’optimisation de
fonction objective sous des contraintes ayant la forme d’inéquations linéaires.
Un outil qui permet de : * modéliser
* résoudre
toute une classe de problèmes d’optimisation.
4 @mail: [Link]@[Link] 2020/2021
La programmation linéaire traite de manière générale d'un problème
d'allocation de ressources limitées parmi des activités concurrentes
et ce d'une façon optimale.
La programmation linéaire emploie un modèle mathématique qui
décrit le problème réel.
L'adjectif "linéaire" indique que toutes les fonctions mathématiques
de modèle sont linéaires (de degré 1)
tandis que le terme "programmation" signifie essentiellement planification.
@mail: [Link]@[Link] 2020/2021 5
Modéliser un problème consiste à identifier :
- Les variables de décision (inconnues)
- Les contraintes (conditions)
- L’objectif à atteindre (optimisation)
Dans un problème de programmation linéaire, les contraintes
et l'objectif sont des fonctions linéaires des variables.
6 @mail: [Link]@[Link] 2020/2021
• Une usine fabrique 2 pièces P1 et P2 usinées dans deux ateliers A1 et A2.
Les temps d'usinage sont :
pour P1: de 3 heures dans l'atelier A1 et de 6 heures dans l'atelier A2
pour P2: de 4 heures dans l'atelier A1 et de 3 heures dans l'atelier A2.
Le temps de disponibilité hebdomadaire de l'atelier A1 est de 160
heures et celui de l'atelier A2 de 180 heures.
La marge bénéficiaire est de 1200 DA pour une pièce P1 et 1000 DA pour
une pièce P2.
Quelle production de chaque type doit-on fabriquer pour maximiser la
marge hebdomadaire?
7 @mail: [Link]@[Link] 2020/2021
• Modéliser sous forme de programme linéaire
1- Variables de décision (Inconnus):
X1 : quantité de pièces P1 à fabriquer
X2 : quantité de pièces P2 à fabriquer
2- Contraintes économiques :
3x1 + 4x2 ≤ 160 (contrainte due à l’atelier A1)
6x1 + 3x2 ≤ 180 (contrainte due à l’atelier A2)
3- Contraintes de signe :
x1 ≥ 0 , x2 ≥ 0
4- Fonction économique (objectif) :
Z = 1200x1 + 1000x2 (à optimiser, dans notre cas, maximiser)
8 @mail: [Link]@[Link] 2020/2021
9 @mail: [Link]@[Link] 2020/2021
La programme linéaire (PL) comme étant un modèle admet des hypothèses (des
conditions) que le décideur doit valider avant de pouvoir les utiliser pour modéliser
son problème. Ces hypothèses sont:
Les variables de décision du problème sont positives
Le critère de sélection de la meilleure décision est décrit par une fonction linéaire de ces
variables, c’est à dire, que la fonction ne peut pas contenir par exemple un produit croisé de deux
de ces variables. La fonction qui représente le critère de sélection est dite fonction objectif (ou
fonction économique).
Les restrictions relatives aux variables de décision (exemple: limitations des ressources) peuvent
être exprimées par un ensemble d’équations et inégalités linéaires. Ces équations forment
l’ensemble des contraintes.
Les paramètres du problème en dehors des variables de décisions ont une valeur connue avec
certitude.
10 @mail: [Link]@[Link] 2020/2021
Identifier les variables du problème à valeur non connues (variable de
décision) et les représenter sous forme symbolique (exp. x1, y1 ).
Identifier les restrictions ( les contraintes ) du problème et les
exprimer par un ensemble d’inégalités et d’équations linéaires.
Identifier l’objectif (ou le critère de sélection) est le représenter sous
une forme linéaire en fonction des variables de décision. Spécifier si le
critère de sélection est à maximiser ou à minimiser.
11 @mail: [Link]@[Link] 2020/2021
MAX (ou MIN) Z= c1X1 + c2X2 + … + cnXn
Sujet à: a11X1 + a12X2 + … + a1nXn ≤ b1
:
ak1X1 + ak2X2 + … + aknXn ≤ bk
:
am1X1 + am2X2 + … + amnXn ≤ bm
xj ≥ 0 j=1..n
12 @mail: [Link]@[Link] 2020/2021
Forme standard
n
Min (ou max) Z = cj xj
j=1
n
Sujet à: aijxj = bj, i = 1, 2, ..., m
j=1
xj ≥ 0, j = 1, 2, ..., n.
Représentation matricielle
Min (ou Max Z) = Ct * X
s. c AX=b
X≥0
𝐀 𝛜 𝑹𝒎∗𝒏 𝐗, 𝐂 𝛜 𝑹𝒏 𝐞𝐭 𝐛𝛜 𝑹𝒎
@mail: [Link]@[Link] 2020/2021 13
Forme canonique
n
Max Z = cj xj
j=1
n
Sujet à: aijxj ≤ bj, i = 1, 2, ..., m
j=1
xj ≥ 0, j = 1, 2, ..., n.
n
Min Z = cj xj
j=1
n
Sujet à: aijxj ≥ bj, i = 1, 2, ..., m
j=1
xj ≥ 0, j = 1, 2, ..., n.
@mail: [Link]@[Link] 2020/2021 14
Opérations à effectuer pour passer d’une forme à l’autre
1ère opération : min f(X) = - max (-f(X)) (f : fonction linéaire)
2ème opération: on peut remplacer chaque variable par une différence de
variables positives.
Xj = X’j - X’’j où X’j ≥ 0 et X’’j ≥ 0.
3ième opération: chaque équation ( ai1 X1 + ai2 X2 + .......... + ainXn = bi )
peut être remplacée par deux inéquations :
ai1 X1 + ai2 X2 + .......... + ainXn ≥ bi
ai1 X1 + ai2 X2 + .......... + ainXn ≤ bi
ou par les inéquations équivalentes:
ai1 X1 + ai2 X2 + .......... + ainXn ≥ bi
-ai1 X1 - ai2 X2 - .......... - ainXn ≥ - bi
@mail: [Link]@[Link] 2020/2021 15
Opérations à effectuer pour passer d’une forme à l’autre
4ième opération:
Toute inéquation ( ai1 X1 + ai2 X2 + .......... + ainXn ≤ bi )
(ou ai1 X1 + ai2 X2 + ........ + ainXn ≥ bi )
peut être remplacée par les équations :
i1 X1 + ai2 X2 + .......... + ainXn + Xn+i = bi , avec Xn+i ≥ 0
(ou ai1 X1 + ai2 X2 + .......... + ainXn - Xn+i = bi , avec Xn+i ≥ 0)
Xn+i est appelée une variable d'écart qu'on peut introduire dans
le problème et qui est affecté d'un coefficient nul dans la
fonction à optimiser.
@mail: [Link]@[Link] 2020/2021 16
Quiz
Le PL suivant est déjà sous forme canonique :
Min Z = 2x1 + 3x2 – x3
sous les contraintes:
2x1 + x2 - x3 ≥ 100
x1 + x2 + x3 ≥ 80
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0,
Ecrire le PL sous la forme standard
Ecrire le PL suivant sous la forme standard et la forme canonique
Max Z= 6x1 + 14x2 + 13x3
sujet à ½ x1 + 2x2 + x3 ≤ 24
x1 + 2x2 + 4x3 ≤ 60
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
@mail: [Link]@[Link] 2020/2021 17
Quiz
- Ecrire le PL suivant sous la forme
1) Canonique
2) Standard
Max Z = 6x1 - 3x2 + x3
sous les contraintes:
4x1 + 2x2 + x3 ≤ 65
x1 + x2 - x3 ≥ 5
x1 + x2 = 10
x1≥ 0, x2 ≤ 0,
@mail: [Link]@[Link] 2020/2021 18
Un agriculteur veut allouer 150 hectares de surface irrigable
entre culture de tomates et celles de piments. Il dispose de
480 heures de main d’œuvre et de 500 m3 d’eau. Un hectare
de tomates demande 2 heure de main d’œuvre, 4 m3 d’eau et
donne un bénéfice net de 1000 dinars. Un hectare de piments
demande 4 heures de main d’œuvre, 2 m3 d’eau et donne un
bénéfice net de 2000 dinars.
Quelle est la meilleure allocation de ses ressources ?
19 @mail: [Link]@[Link] 2020/2021
Une compagnie de taxi dispose de quatre véhicules libres et doit
transporter quatre clients. Le but de la compagnie est d'assigner un taxi
par client en minimisant la somme des distances parcourues.
Les distances respectives (en kilomètres) entre les taxis et les voyageurs
sont données par le tableau ci-contre.
Distance(cij) Client1 Client2 Client3 Client4
Taxi1 6 4 5 4
Taxi2 3 5 6 4
Taxi3 4 4 6 3
Taxi4 5 6 7 5
Donner un modèle mathématique de ce problème.
20 @mail: [Link]@[Link] 2020/2021
Une usine a reçu des plaques de métal d’une largeur de 200 cm et
d’une longueur de 500 cm. Il faut en fabriquer au moins 30
plaques de largeur de 110 cm , 40 plaques de largeur de 75 cm et
15 plaques de largeur de 60 cm. Donner le modèle mathématique
pour que les déchets soient les plus petits possibles .
Donner le modèle mathématique de ce problème.
21 @mail: [Link]@[Link] 2020/2021
Une plaque de 200 cm de largeur peut être découpée de cinq façons :
Une plaque de 75 cm et deux plaques de 60 cm. Les déchets seront de 05 cm.
Une plaque de 110 cm et une plaque de 75 cm. Les déchets seront de 15 cm.
Une plaque de 110 cm et une plaque de 60 cm. Les déchets seront de 30 cm.
Trois plaques de 60 cm. Les déchets seront de 20 cm.
Deux plaques de 75 cm. Les déchets seront de 50 cm.
Inconnus :
Soit xi : le nombre de plaques à découper par la façon i, le problème s’écrit :
22 @mail: [Link]@[Link] 2020/2021
On se propose de fournir quotidiennement et à chaque individu d'une
population d'animaux dans une ferme un minimum de : Protéines calories calcium fer
•70 g de protéines A 10 300 50 4
B 30 1800 400 4
•3000 cal
C 35 800 450 4
•800 mg de calcium D 20 1500 750 4
E 25 300 120 15
•12 mg de fer
Les différentes quantités de protéines (en g), de calories (en cal), de
calcium (en mg) et de fer (en mg) sont données par le tableau.
On dispose de cinq aliments A, B, C, D et E. les prix d'achats, pour
100g, respectifs de ces aliments sont respectivement de: 3, 7, 7, 5, 5.
Le problème est de constituer, au moindre frais, des rations
journalières respectant les exigences de départ.
Donner un modèle mathématique de ce problème.
23 @mail: [Link]@[Link] 2020/2021
Exemple : unité de production
• Proposer un programme ?
• Décisions (Variables de décision) [X1, X2, … Xn]
Qu’est-ce qu’on cherche à établir?
• Contraintes
Définir l’ensemble des solutions possibles.
• Objectif
Maximisation / Minimisation (objectif)
•Linéaire : formules polynômiales de degré 1
1 1 1
24
a 1X 1 a 2 X 2
a nX n
@mail: [Link]@[Link] 2020/2021
Chapitre suivant : Méthodes de résolution d’u PL
Cours suivant : Résolution graphique
