Chapitre 1
Formulation d’un programme linéaire
1.1 Programmes linéaires
Définition 1.1.1 Un programme linéaire dans Rn est un problème qui consiste à déterminer :
1) le minimum ou maximum d’une application linéaire Z : Rn → R restreinte à un ensemble de
solutions d’un système d’équations et/ou d’inéquations linéaires dans Rn ;
2) les éléments s’ils existent qui réalisent ce minimum ou ce maximum.
∑
Si l’application linéaire est Z(x) = nj=1 cj xj et le système mixte d’équations et/ou d’inéquations
linéaires est :
∑n
∑j=1 aij xj ≥ bi , i = 1, · · · , m1
n
j=1 aij xj ≤ bi , i = m1 + 1, · · · , m2
∑n
j=1 aij xj = bi , i = m2 + 1, · · · , m
on le note symboliquement :
∑
min (max) Z(x) = nj=1 cj xj
∑n
∑j=1 aij xj ≥ bi , i = 1, · · · , m1
n
aij xj ≤ bi , i = m1 + 1, · · · , m2
∑j=1
n
j=1 aij xj = bi , i = m2 + 1, · · · , m
xj ∈ R, j = 1, · · · , n
La fonction Z est alors dite fonction-objectif du problème et les éléments qui vérifient le système
d’équations et/ou d’inéquations linéaires sont appelés solutions réalisables ou admissibles ou acceptables
du problème.
On peut supposer que ce programme est sous la forme suivante dite forme générale :
∑
min (max) Z(x) = nj=1 cj xj
∑n
∑j=1 aij xj ≥ bi , i = 1, · · · , m1
n
∑j=1 aij xj ≤ bi , i = m1 + 1, · · · , m2
n
j=1 aij xj = bi , i = m2 + 1, · · · , m
x ≥ 0, j = 1, · · · , n1
j
xj ≤ 0, j = n1 + 1, · · · , n2
xj ∈ R, j = n2 + 1, · · · , n.
On a les remarques suivantes :
2
Remarque 1.1.1 - Etant donné un programme linéaire, on peut toujours se ramener à un programme
linéaire où les variables sont astreintes à être non négatives. En effet si xj est une variable négative on
−
fait le changement de variable x′j = −xj . Si par contre xj est quelconque dans R on pose xj = x+ j − xj
−
avec x+ j , xj ≥ 0 car tout réel peut s’écrire comme la différence de deux réels positifs ou nuls.
- Dans un programme linéaire on peut ramener toutes les contraintes d’inégalité à des inégalités de
même type. il suffit de multiplier la contrainte par −1 le cas échéant.
Par convention les contraintes d’inégalité pour un problème de minimisation sont du type ” ≥ ” et les
contraintes d’inégalité pour un problème de maximisation sont du type ” ≤ ”
On peut dire alors qu’un programme linéaire est un programme mathématique de la forme
∑
min (max) Z(x) = nj=1 cj xj
∑n
∑j=1 aij xj ≥ (≤) bi , i = 1, · · · , m1
n
j=1 aij xj = bi , i = m1 + 1, · · · , m
xj ≥ 0, j = 1, · · · , n
Dans un programme linéaire on distingue deux types de contraintes : les contraintes relatives au signe
des variables, dites contraintes de restriction de signe ou de non-négativité et les autres dites ”vraies
contraintes” on dit aussi contraintes structurelles.
Si on note :
∑n
∑ j=1 aij xj ≥ (≤) bi , i = 1, · · · , m1
n
C = x ∈ Rn : j=1 aij xj = bi , i = m1 + 1, · · · , m ,
xj ≥ 0, j = 1, · · · , n
Comme déjà dit plus haut, les éléments de C sont appelés solutions réalisables, admissibles ou accep-
tables et la fonction Z est appelée fonction-objectif du problème.
1.2 Modélisation sous forme de programmes linéaires
1.2.1 Etapes de la modélisation
Pour modéliser un problème sous forme d’un programme linéaire, on peut procèder en quatre étapes :
le choix des variables, la détermination des contraintes, la détermination de la fonction-objectif et enfin
le résumé.
Etape 1 : choix des variables
Dans cette étape on choisit les variables de décision : en général elles permettent de définir la fonction-
objectif.
Etape 2 : détermination des contraintes
A ce niveau il faut d’abord signaler les contraintes de signe des variables qui ne sont indiquées dans le
texte. Les variables sont en génaral non négatives en tant que quantités de matière. Ensuite on détermine
les contraintes structurelles qui sont liées au texte. Il ne faut pas oublier d’indiquer les éléments du texte
qui engendrent les contraintes structurelles.
Etape 3 : détermination de la fonction-objectif
Dans cette partie, on définit la fonction-objectif qui est soit un bénéfice soit un coût de production.
Etape 4 : résumé
On termine la modélisation par un résumé qui signale le type de problème à résoudre. Pour un coût
de production il s’agira naturellement d’un programme linéaire de minimisation et pour un problème de
gain d’un programme linéaire de maximisation.
3
Remarque 1.2.1 (Hypothèse de linéarité) Pour modéliser un problème sous forme d’un programme
linéaire, on prend en compte les hypothèses de linéarité sur la fonction-objectif et les contraintes struc-
turelles. Cela signifie par exemple que, pour fabriquer une unité d’un produit donné, si on utilise une
matière première à la hauteur de α, alors pour en fabriquer x unités, on utilisera la matière première
à la hauteur de αx. En outre si la vente d’une unité de ce produit conduit à un bénéfice de c unités
monétaires, alors la vente de x unités de ce produit conduira à un bénéfice de cx unités monétaires.
Cette hypothèse de linéarité sera prise en compte automatiquement pour tous les cas de modélisation
en programmation linéaire.
1.2.2 Quelques exemples
Exemple 1 : Problème de production
Soient Mi (i = 1, · · · , m), m machines qui fabriquent en série n types de produits Pj (j = 1, · · · , n).
La machine Mi a une capacité maximum de bi unités de temps. La fabrication d’une unité du produit
Pj nécessite l’utilisation de la machine Mi durant aij unités de temps. Si cj représente le gain relatif à la
production d’une unité du produit Pj , quelle doit être la politique de production pour maximiser le gain
total ?
Exemple 2 : Problème de transport
Soient r centres de production d’un bien donné possédant des stocks disponibles en quantités respec-
tives q1 , · · · , qr . Dans s centres de consommation, la demande de ce bien est respectivement de d1 , · · · , ds .
Les frais de transport d’une unité de bien du centre de production i au centre de consommation j est cij
unités monétaires. Il s’agit de déterminer comment approvisionner les centres de consommation à partir
des centres de production de manière à minimiser le coût total de transport. Formuler ce problème sous
forme d’un programme linéaire.
Exemple 3 : Problème de la ration alimentaire
On dispose de n aliments Aj (j = 1, · · · , n) aux prix respectifs par unité de cj unités monétaires
(j = 1, · · · , n).
On considère m éléments nutritifs ei (i = 1, · · · , m). La quantité du ième élément nutritif contenue dans
une unité de l’aliment Aj est aij . Les besoins respectifs en les m éléments nutritifs sont bi (i = 1, · · · , m).
On se propose de déterminer la ration alimentaire qui tout en étant de meilleur marché possible
garantisse un apport suffisant en éléments nutritifs.
Exemple 4
Un ébéniste fabrique des bureaux sous deux modèles : le modèle ”luxe” et le modèle ”standard”.
Des études de marché ont montré que, pour l’année à venir, les possibilités de vente s’élèvent à 300
unités pour le modèle ”luxe” et à 400 unités pour le modèle ”standard”. L’approvisionnement en bois est
suffisant pour pouvoir fabriquer annuellement 500 bureaux quel que soit le type. Par ailleurs, le temps
de fabrication d’un bureau sous le modèle ”luxe” est double de celui d’un bureau de type ”standard” : la
capacité annuelle de fabrication est telle que, si tous les bureaux fabriqués étaient du type ”standard”,
on pourrait en fabriquer 700 au maximum.
La vente d’un bureau sous le modèle ”luxe” conduit à une marge unitaire sur coût variable égale à 7,
celle d’un bureau de type ”standard” : 5.
On se propose de rechercher le programme annuel de fabrication conduisant au profit global maximal.
Exemple 5
Le propriétaire d’une station d’essence qui vend du Super, de l’Ordinaire et du Gas-oil aux prix
respectifs de 415, 390 et 295 unités monétaires le litre, mais livrés par la station mère aux prix de 405,
375 et 270 unités monétaires.
Comme le propriétaire de la station est peu scrupuleux et qu’il veut s’enrichir rapidement, il se livre
au trafic suivant : se basant sur son expérience du métier, il sait qu’il peut vendre à la pompe ”Super”
4
un mélange des trois carburants à condition qu’il y ait au moins 70% de Super et pas plus de 10%
d’Ordinaire.
De même, à la pompe ”Ordinaire”, il peut vendre un mélange comportant au moins 15% de Super et
pas plus de 70% de Gas-oil.
Enfin, le mélange vendu à la pompe ”Gas-oil” doit contenir au moins 80% de Gas-oil.
D’autre part, le marché est tel que le propriétaire de la station ne peut vendre plus de 20 000 litres
de Super, 30 000 litres d’Ordinaire et 20 000 litres de Gas-oil.
Donner la formulation mathématique de ce problème.
Exemple 6
On désire déterminer la composition, à coût minimal, d’un aliment pour bétail qui est obtenu en
mélangeant au plus deux produits bruts : orge et arachide.
- la quantité nécessaire par portion est de 400g.
- l’aliment ainsi fabriqué devra comporter au moins 30% de protéı̈nes et au plus 5% de fibres.
On a les données suivantes :
quantité par gramme d’aliment
Aliment Protéı̈ne Fibres Coût (F/kg)
orge 0,09 0,02 450
arachide 0,60 0,06 500
Modéliser le problème sous forme d’un programme linéaire.
1.3 Forme standard, forme canonique
Dans cette partie on considère la relation suivante.
Pour u et v dans Rn on note
u ≤ v ⇔ ui ≤ vi ∀ i = 1, · · · , n.
Définition 1.3.1 Un programme linéaire est sous forme standard si les vraies contraintes sont des
égalités et les variables sont astreintes à être non négatives. En d’autres termes, le problème est sous
la forme
∑n
min
{ ∑ (max) Z = j=1 cj xj
n
j=1 aij xj = bi , i = 1, · · · , m
xj ≥ 0, j = 1, · · · , n
Si on pose A = (aij ) ∈ Mm,n (R), c = (cj ) ∈ M1,n (R), et
b = (bi ) ∈ Mm,1 (R), on a la notation matricielle
min(max)
{ Z = cx
Ax = b
x ∈ Rn , x ≥ 0
On a la proposition suivante.
Proposition 1.3.1 Tout programme linéaire peut se mettre sous forme standard
Preuve : Il suffit de transformer les contraintes d’inégalité en contraintes d’égalité en considérant les
équivalences suivantes :
∑n ∑n
aij xj ≥ bi ⇔ aij xj − si = bi , si ≥ 0
j=1 j=1
∑
n ∑
n
aij xj ≤ bi ⇔ aij xj + si = bi , si ≥ 0
j=1 j=1
5
Définition 1.3.2 La variable si introduite pour passer d’une contrainte d’inégalité à une contrainte
d’égalité est appelée variable d’écart.
Remarque 1.3.1 Le passage à la forme standard augmente le nombre de variables dans le programme
linéaire.
Définition 1.3.3 Un programme linéaire est sous forme canonique si les vraies contraintes sont des
inégalités et les variables sont astreintes à être non négatives. Pour les problèmes de minimisation on a
∑n
min Z =
{ j=1 cj xj
∑n
≥ bi , i = 1, · · · , m
j=1 aij xj
xj ≥ 0, j = 1, · · · , n
et pour les problèmes de maximisation on a
∑
max Z = nj=1 cj xj
{ ∑n
j=1 aij xj ≤ bi , i = 1, · · · , m
xj ≥ 0, j = 1, · · · , n
En considérant les mêmes notations que ci-dessus, on obtient respectivement pour la minimisation et
la maximisation la notation matricielle suivante :
min Z = cx
{ max
{ Z = cx
Ax ≥ b Ax ≤ b
x ∈ Rn , x ≥ 0 x ∈ Rn , x ≥ 0
Proposition 1.3.2 Tout programme linéaire peut se mettre sous forme canonique
Preuve : Il suffit de transformer les contraintes d’égalité en contraintes d’inégalité en considérant l’une
des équivalences suivantes :
∑
n { ∑n
j=1 aij xj ≥ bi ,
∑
aij xj = bi ⇔
− nj=1 aij xj ≥ −bi
j=1
ou
∑
n { ∑n
j=1 aij xj ≤ bi ,
∑
aij xj = bi ⇔
− nj=1 aij xj ≤ −bi
j=1
Remarque 1.3.2 Le passage à la forme canonique augmente le nombre de contraintes dans le programme
linéaire.
