Chapitre 1

Introduction à l'Optimisation

1.1 Quelques exemples de modèles mathématiques................................................................................8

1.2. Définition de la Recherche Opérationnelle RO................................................................................8
1.3 Enjeux de la RO....................................................................................................................................10
1.4 Formulation d’un problème d’optimisation......................................................................................10
1.4.1 Analyse ...............................................................................................................................................10
1.4.2 Modélisation.......................................................................................................................................10
1.4.3 Critère a optimisé ..............................................................................................................................11
1.4.4 Application a l'exemple ....................................................................................................................11
1.5 Solutions d’un problème .....................................................................................................................12
1.6 Exemples................................................................................................................................................12
1.6.1 Problème de production...................................................................................................................12
1.6.2 Réseaux de transport.........................................................................................................................13
1.7. Définitions mathématique..................................................................................................................15
1.7.1 Problème d’optimisation...................................................................................................................15
1.7.2 Critère .................................................................................................................................................15
1.7.3 Contraintes .........................................................................................................................................16
1.7.4 Non-négativité ...................................................................................................................................16
1.8 Complexité des Algorithmes...............................................................................................................16
1.8.1 Notion de Complexité .....................................................................................................................16
1.8.2 L'évaluation temporelle ....................................................................................................................17
 Chapitre 1 Introduction à l'Optimisation

Chapitre 1 : Introduction à l'Optimisation

1.1 Quelques exemples de modèles mathématiques

Exemple 1

Une entreprise fabrique des tables et des chaises à partir de deux matières : le bois et la
peinture, sachant que la réalisation d'une table nécessite 3 m de bois et 4 kg de peinture, la
réalisation d'une chaise nécessite 2 m de bois et 1 kg de peinture. Les moyens financiers
de l'entreprise acceptent un approvisionnement de 100 m de bois et 120 kg de peinture
par semaine. Les produits ainsi fabriqués fournissent un bénéfice de 500 DA par table et
300 DA par chaise vendue.

Question
À partir de la description donnée, plusieurs questions se révèlent :
• Quelle quantité de table et quelle quantité de chaise doit produire l'entreprise ?
• Quelles sont les ressources disponibles, les limites et les barrières à ne pas dépasser ?
• Quel est le but de l'entreprise ?

Dans ce cas plusieurs propositions intuitives peuvent avoir lieu par exemple :
• 32 tables et 0 chaise avec un bénéfice de 16000
• 20 tables et 20 chaises avec un bénéfice de 16000
• 0 table et 50 chaises avec un bénéfice de 15000
• etc.

Nous remarquons qu'il y a une infinité de solutions possibles. Parmi toutes les solutions
proposées, comment choisir la meilleure ? Existe-t-il une technique qui pointe
directement sur la solution optimale ? Pour répondre à ces questions plusieurs techniques
inspirées de la recherche Opérationnelle sont proposées.

1.2. Définition de la Recherche Opérationnelle RO

La recherche Opérationnelle est une discipline qui permet de formuler des problèmes par
des supports scientifiques, mathématiques et informatiques pour aider à mieux décider. La
Recherche Opérationnelle ( R.O.) est avant tout un outil d’aide à la décision.

8
 Chapitre 1 Introduction à l'Optimisation

Autrement définie, la Recherche Opérationnelle (RO) traduit des énoncés ou des cahiers
de charges liés à des problématiques spécifiques sous forme de méthodes et des
démarches à base d'équation mathématique, des algorithmes et des outils statistiques.

La Recherche Opérationnelle (RO) permet d'assurer la communication entre le milieu

industriel (les secteurs extérieurs) et les applications théoriques dans le but de proposer les
solutions les mieux adaptées à une situation donnée.
La procédure utilisée par la recherche Opérationnelle RO peut être schématisée comme
suit :

Problème concret

Modélisation

Résolution par une

méthode de R.O

Interprétation
des résultats

Prise de
décision

Figure 1.1 Schéma de procédure utilisée par la RO

La recherche opérationnelle (RO) est utilisée dans les domaines ou la prise de décision fait
appel à la résolution des problèmes d’optimisation telle que les problèmes de :

• Dimensionnement, localisation
• Gestion de ressources
• Rentabilisation des investissements
• Détection de dysfonctionnements : diagnostics, réparation, maintenance.
• Partage des ressources
• Etc.

9
 Chapitre 1 Introduction à l'Optimisation

1.3 Enjeux de la recherche opérationnelle RO

L'utilisation de la recherche opérationnelle devient de plus en plus sollicitée dans la vie

quotidienne et à différents niveaux puisqu'elle offre plusieurs avantages et traite plusieurs
points tels que :

 l'amélioration de la compétitivité des entreprises

 la préservation des emplois
 l'accession à l’innovation
 elle propose les meilleures décisions stratégiques
 fournit une meilleure gestion des ressources. Etc.

1.4 Formulation d’un problème d’optimisation

La modélisation du problème ou le passage du texte vers les équations mathématiques ne

se fait pas de manière aléatoire. Il doit vérifier certaines conditions et doit passer par
plusieurs étapes : l’analyse, la modélisation et le critère à optimiser décrit comme suit :
1.4.1 Analyse

Dans cette phase, on commence toujours par l'identification des données nécessaires à la
résolution du problème, les valeurs de consommations ou les fiches techniques des
articles, la quantité des ressources disponibles, les coûts de transport, la capacité de
production, les gains engendrés par chaque article ou les dépenses établies pour la
réalisation d'une action. Dans cette phase, on détermine les composantes, les enjeux et les
limites du problème. Toutes ces informations sont primordiales pour la formulation des
problèmes.
1.4.2 Modélisation
L’optimisation repose toujours sur des modèles mathématiques qui sont généralement
simples et partiels. Pour définir le modèle du système, on définit :

 Ses variables
Une fois l'analyse effectuée, on détermine les variables du Système qui représente les
décisions à prendre et qui doit répondre à un certain nombre de questions : que faut-il
réaliser et en quelle quantité ? Combien doit-on acheter ? Combien de classes à faire dans
une école ? Les variables représentent les inconnues du système.

10
 Chapitre 1 Introduction à l'Optimisation

 Les contraintes
Les objets mathématiques qui assurent l'interaction et la liaison des variables par rapport
aux ressources disponibles et aux données du problème sont appelées contraintes.

1.4.3 Critère a optimisé

Représente l’objectif ou le but attendu du problème. il peut être une fonction de
minimisation lorsqu'il s'agit d'une dépense, d'un investissement ou une fonction de
maximisation lorsqu'il s'agit d'un profit ou de gain.

1.4.4 Application a un l'exemple

Une entreprise fabrique des tables et des chaises à partir de deux matières : le bois et la
peinture, sachant que la réalisation d'une table nécessite 3 m de bois et 4 kg de peinture la
réalisation d'une chaise nécessitent 2 m de bois et 1 kg de peinture. Les moyens financiers
de l'entreprise acceptent un approvisionnement de 100 m de bois et 120 kg de peinture
par semaine. Les produits ainsi fabriqués fournissent un bénéfice de 500 DA par table et
300 DA par chaise vendu.

Question : formuler le problème

Solution : reprenons les données de l'exemple sur un tableau :

Table Chaise Stock

bois 3 2 100
peinture 4 1 120
Gain 500 300

 Les variables :

x1 : représente la quantité des tables ;

x2 : représente la quantité des chaises.

 Les contraintes :

Pour le bois : 3x1 + 2x2 ≤ 100 (1)

Pour la peinture : 4x1 + 5x2 ≤ 150 (2)

Pour soulever le problème de la non-négativité des variables, puisqu'on ne peut pas

produire moins deux tables ou moins vingt chaises nous supposons que les variables sont
positives, en ajoutons une contrainte supplémentaire au problème :

11
 Chapitre 1 Introduction à l'Optimisation

x1, x2  0 (3)

 Les contraintes : 3x1 + 2x2 ≤ 100 (1)

4x1 + 5x2 ≤ 150 (2)
x1, x2  0 (3)

 Fonction objective :

Le gain : z = 5x1 + 3x2  L’objectif : max z = 5x1 + 3x2

1.5 Solutions d’un problème

 Solution admissible
On appelle solution admissible (ou solution) d’un problème tout vecteur x ∈ S qui
satisfait toutes les contraintes du problème.

 Solution optimale
On appelle solution optimale x*, la solution parmi toutes les solutions admissibles qui
fournissent le meilleur résultat, c'est à dire de trouver le max pour un problème de
maximisation ou trouver le min pour un problème de minimisation.

1.6 Exemples d'applications

1.6.1 Problème de production.

Une usine fabrique 2 produits P1 et P2 en utilisant un certain nombre de ressources : post

opératoire (machine), main-d'œuvre et emballage. Ces besoins sont indiqués dans le
tableau ci-dessous. Par ailleurs, chaque ressource est disponible en quantités limitées (cf.
tableau).

P1 P2 Ressource disponible
Heure /machine 3 9 81
main d’œuvre 4 5 55
emballage 2 1 20

Les deux produits P1 et P2 rapportent à la vente respectivement des bénéfices de 600

DA et 400 DA par unité. Quelles quantités de produits P1 et P2, doit produire l’usine afin
de maximiser le bénéfice total venant de la vente des 2 produits ?

• Choix des variables (les inconnues)

x1 et x2 sont respectivement les quantités des produits P1 et P2 à fabriquer (x1, x2 ∈ N).

12
 Chapitre 1 Introduction à l'Optimisation

• Choix de la fonction objectif à maximiser

La fonction objective F correspond au bénéfice total. Elle vaut :

F(x1, x2) = 600x1 + 400x2.

Le problème se traduit donc par :
Max F= 600 x1 + 400 x2 .

• Détermination des contraintes

a) La disponibilité de chacune des ressources s'écrit sous la forme suivante :

3x1 + 9x2 ≤ 81
4x1 + 5x2 ≤55
2x1 + x2 ≤ 20

b) Positivité des variables : x1, x2 ≥ 0.

En résumé, le problème de production se modélise sous la forme

Max F= 600 x1 + 400 x2 .

3x1 + 9x2 ≤ 81
4x1 + 5x2 ≤55
2x1 + x2 ≤ 20
x1, x2 ≥ 0.

1.6.2 Réseaux de transport

On désire acheminer des marchandises de n dépôts à m points de vente

On connaît :
cij avec i = 1..n et j = 1..m, coût de transport (i, j),
Xi avec i = 1..n, stocks de dépôts,
Dj avec j = 1..m, niveaux de demande aux points de vente.
On recherche, pour chaque couple (i, j), la quantité (positive) wij à transporter du dépôt
Xi au point de vente Dj.

Question : formuler mathématiquement le problème

13
 Chapitre 1 Introduction à l'Optimisation

Solution : formulation mathématiquement du problème.

Pour la formulation de cet exemple nous nous avons choisit un réseau composé de 4
dépôts (n=4) et 6 points de vente (m=6).

Les variables :
w11, w12, w13, w14, w15, w16, w21, w22, w23, w24, w25, w26, w31, w32, w33, w34, w35, w36, w41, w42,
w43, w44, w45, w46  0

Les contraintes :

Contraintes de capacité des producteurs :

w11+ w12+ w13+ w14+ w15+ w16 = X1

w21+ w22+ w23+ w24+ w25+ w26 = X2

w31+ w32+ w33+ w34+ w35+ w36 = X3

w41+ w42+ w43+ w44+ w45+ w46 = X4

Contraintes de satisfaction de la demande :

w11 + w21 + w31 + w41 = D1

w12 + w22 + w32 + w42 = D2
w13 + w23 + w33 + w43 = D3
w14 + w24 + w34 + w44 = D4
w15 + w25 + w35 + w45 = D5
w16 + w26 + w36 + w46 = D6
Fonction objective:

Min Z = c11 w11+ c12w12+ c13w13+ c14w14+ c15w15+ c16 w16+ c21w21+ c22w22+ c23w23+
c24w24+ c25w25+ c26w26+ c31w31+ c32w32+ c33w33+ c34w34+ c35w35+ c36w36+ c41w41+
c42w42+ c43w43+ c44w44+ c45w45+ c46w46

Solution du problème de programmation linéaire :

n m
min  c w
i 1 j 1
ij ij

w
i 1
ij  DJ j  1,....m
m

w
j 1
ij  Xi i  1,....n

14
 Chapitre 1 Introduction à l'Optimisation

 Le critère représente le coût total de transport.

 Les contraintes expriment l’égalité de l’offre et de la demande pour chaque point
de vente et chaque dépôt.

Exemple :
Une organisation possède quatre centres de distribution : (Tlemcen, Alger, Constantine et
Béchar) de stocks de produits respectivement de : 120 kg, 100 kg, 100 kg et 100 kg, pour
lesquels elle a reçu des commandes de ses antennes d'Oran (80 kg), Bejaia (190 kg) et
Tamanrasset (150 kg).
Les coûts de transport d’un kilo de produits, suivant les liaisons routières considérées,
sont donnés par le tableau suivant :

Oran Bejaia Tamanrasset

Tlemcen 80DA 200DA -
Alger 100DA 100DA -
Constantine - 400DA 900DA
Bechar - 600DA 800DA

 Représenter le problème sur un graphique.

 Formuler mathématiquement le problème.

1.7. Définitions mathématique

1.7.1 Problème d’optimisation :

Un problème d’optimisation est un problème d’analyse fonctionnelle qui cherche
l’extremum d’une fonction de n variables sur un domaine appartenant à Rn:

Maximiser J = f (x)

sous les contraintes gi(x) ≤ 0 pour i = 1, .., m x ∈ S ⊂ Rn .

Les composantes x1, ..., xn de x sont les variables ou inconnues du problème.

1.7.2 Critère

Le critère représente la fonction objectif

Maximiser f (x) qui est équivalent à minimiser −f (x).

15
 Chapitre 1 Introduction à l'Optimisation

1.7.3 Contraintes

Chaque fonction gi définissant une contrainte est une fonction de Rn sur R

Toute contrainte égalité h(x) = 0 est équivalente à :

h(x) ≤ 0
h(x) = 0
h(x) ≥ 0
1.7.4 Non-négativité

Tout nombre, positif ou négatif, peut toujours être écrit comme la différence de deux
nombres non négatifs (par exemple, - 4 = 6 - 10). Il suffit donc de remplacer la variable
d'activité par la différence de deux nouvelles variables d'activité non négatives (le nombre
de variables d'activité augmente de 1).

1.8 Complexité Algorithmique

1.8.1 Notion de Complexité

La complexité algorithmique est une notion qui concerne l'évaluation des performances
des algorithmes réalisant les mêmes procédés ou les mêmes fonctionnalités et permettant
de comparer et de déterminer si un algorithme "a" est meilleur qu'un algorithme "b" et s'il
est optimal ou s'il ne doit pas être utilisé.

Le but principal pour tout algorithme d’optimisation globalement convergent est de

trouver une valeur très proche de la solution optimale au bout d'un certain nombre fini
d’itérations. Mais ce nombre peut être extrêmement grand. Dans ce contexte, l'étude de la
complexité algorithmique prend en considération le nombre d’opérations, plus
précisément le temps d’exécution nécessaire sur ordinateur et l’encombrement mémoire,
en fonction de la taille du problème à traiter à savoir le nombre de variables et le nombre
de contraintes du problème.

 Considérons l’exemple-1 suivant :

{Début}
S:= 0 ; I : =1 ; N:=10 {"1"}
while I <= N do {"2"}
S = S +K[I] {"3"}
I = I+1 {"4"}
end do; {End}

16
 Chapitre 1 Introduction à l'Optimisation

Le temps d’exécution nécessaire pour cet algorithme t(n), composé de plusieurs temps de
chaque instruction. Nous supposons que :

 t1 est le temps d’exécution entre le début et la lecture des différentes variables

d'initiation {"1"}
 t2 représente le temps d’exécution de la comparaison {"2"}
 t3 est le temps d’exécution de l’action {"3"}
 t4 est le temps d’exécution de l’action {"4"}

Sachant que le temps t2, t3, t4 sont bien définis et inchangés durant l'exécution de cette
ligne. Par ailleurs ces temps représentent une boucle qui se répète n fois. Donc le temps
nécessaire pour l'exécution de la boucle est donné par :

n*tb avec tb= t2 + t 3 + t 4

De ce fait, le temps d’exécution t(n) de cet algorithme s’écrit :

t(n) = t1+ t 2+n * tg

Ce qui signifie que le temps d’exécution dépend linéairement de la taille n.

1.8.2 Évaluation temporelle

L'évaluation temporelle d'un algorithme peut avoir plusieurs possibilités parmi elles
lorsqu'il s'agit d'une :

 Somme des temps exp : l'exécution de trois actions l'une après l'autre ou chaque
action demande un temps de traitement relatif,

Action 1 : Traitement 1(t1)

Action 2 : Traitement 2 (t2 ) temps d'exécution : tn = t1+ t2+ t3
Action 3 : Traitement 3 (t3)

 Maximum de temps exp : c'est dans le cas d'une boucle avec la condition si

si < condition est vérifiée > alors on effectue

Action 1 avec temps de traitement1 (t1)
sinon temps d'exécution : tn = Max (t1, t2)
Action 2 avec temps de traitement 2 (t2)

17
 Chapitre 1 Introduction à l'Optimisation

 Somme des temps de passages successifs exp:

tant que < condition est vérifiée > faire Traitement (t1)

Le temps d'exécution : tn = n* t1 avec n le nombre de tests à effectuer

Note : d'une manière générale, les performances asymptotiques des algorithmes

dépendent principalement du nombre de variables, n, et la taille du problème, en
négligeant les termes de degré inferieur par exemple :

y(n) = n3 + 3n2 + 4 n + 10 est une complexité d'ordre O(n3)

y(n) = n log n + 12 n + 17 est une complexité d'ordre O(n log n)

18
 Chapitre 2
Programmation Linéaire

2.1 Introduction...........................................................................................................................................20
2.2 Forme d’un programme linéaire.........................................................................................................20
2.2.1 Forme générale...................................................................................................................................20
2.2.2 Forme standard ou forme canonique d’un programme linéaire.................................................21
2.3 Résolution de programmes linéaires..................................................................................................22
2.3.1 Résolution graphique.........................................................................................................................22
2.3.2 Méthode de simplexe .......................................................................................................................26
2.3.3 Résolution par les Tableaux de simplexe ......................................................................................29
2.4 Dualité ...................................................................................................................................................33
2.4.1 Qu'est ce que la dualité ? .................................................................................................................34
2.4.2 Qu'elle est l'importance....................................................................................................................34
2.4.3 Comment trouver le dual ? .............................................................................................................34
2.4.4 Conditions d’optimalité primal-dual ..............................................................................................35
2.4.5 Exemple..............................................................................................................................................35
 Chapitre 2 : Programmation linéaire

Chapitre 2 : Programmation linéaire

2.1 Introduction

En mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes

d'optimisation où la fonction objective et les contraintes sont toutes linéaires.

2.2 Forme d’un programme linéaire

2.2.1 Forme générale

La forme générale d’un problème d’optimisation est la suivante :

Maximiser f (x) {ou Minimiser f(x)}

sous
gi(x) = 0 i ∈ I 0 contraintes égalité
gi(x) ≤ 0 i ∈ I − contraintes inégalité
gi(x) ≥ 0 i ∈ I + contraintes inégalité
x = [x1, ..., xn]T ≥ 0

D'une manière plus détaillée, un programme linéaire (PL) est dit sous forme générale s’il
s'écrit de la façon suivante :

max F  c1 x1  c2 x2  ........ cn xn
2.1
La fonction 2.1 peut s'exprimer par une sommation de n terme (variables) comme suit :
n
max F   c j x j
j
2.2
Sous les contraintes :
n

a x
j 1
rj j  br
ou
n

a x
j 1
ij j  bi
2.3
ou
n

a
j 1
kj x j  bk

20
 Chapitre 2 : Programmation linéaire

2.2.2 Forme standard ou forme canonique d’un programme linéaire

Un problème linéaire est sous forme standard si toutes les contraintes sont des contraintes
égalité. Pour transformer une contrainte d'inégalité en contrainte d'égalité, il faut ajouter
aux membres de gauche d’une contrainte, une quantité (une mesure) appelée variable
d'écart qui sert à absorber l'écart entre le membre gauche et le membre droit d'une
contrainte si l'écart existe, bien sûr, sinon cette variable vaut zéro.

La forme standard peut être donnée par la forme suivante :

max z  CX

sous 2.4

 AX  b α

 X 0 β

Cette forme standard est obtenue en introduisant des variables d'écart dans toutes les
contraintes d'inégalité(à) et que ces variables soient non négatives(β).

La forme canonique d'un programme linéaire peut être exprimée par un ensemble de
vecteurs comme suit :
X  ( x1 , x2 ,.....xn )  R n
2.5
c  (c1 , c2 ,.....,cn )  R n
b  (b1 , b2 ,.....,bm )  R n

Et la matrice A de taille m x n

 a11 a12  a1n  2.6

 
A    
a am 2  amn 
 m1
avec:
n = nombre de variables,
m = nombre de contraintes,
X = vecteur des variables de décision
A = matrice réelle m × n (matrice des contraintes)
c= [c1, ..., cn] =vecteur-ligne des couts,
b=[b1, ..., bm]T=vecteur-colonne des seconds membres

21
 Chapitre 2 : Programmation linéaire

Z= CX est la fonction objective, ou critère à minimiser.

Exemple :
Reprenons l’exemple du problème de production de l’introduction. Sous forme standard
(en introduisant des variables d'écart), le PL s'écrit :

max F  600 x1  400 x2

Sous contrainte
4 x1  5 x2  x3  55
x1  3 x2  x4  27
2 x1  x2  x5  20
x1 , x2 , x3 , x4 , x5  0

Pour cet exemple :

 Le vecteur des variables dans le système est : X  ( x1 , x2 , x3 , x4 x5 )

 Le vecteur des coefficients c est donné par c=(600 , 400 , 0 , 0 , 0) puisque max F
peut s'écrire comme suit :
max F  600 x1  400 x2  0 x3  0 x4  0 x5

 Le vecteur des coefficients b est donné par b=(55 , 27 , 20)

 La matrice A :  4 5 1 0 0
 
A   1 3 0 1 0
 2 1 0 0 1
 
2.3 Résolution de programmes linéaires

Il existe plusieurs techniques de résolution pour les programmes linéaires. Cela dit nous
présenterons dans cette section : la résolution graphique et la résolution analytique en
détaillant deux procédures : méthode Simplexe et tableaux Simplexe.

2.3.1 Résolution graphique

La résolution graphique d'un problème linéaire consiste à tracer la droite qui sépare les
demi-plans pour chaque contrainte tout en conservant le demi-plan acceptable, c'est-à-
dire le demi-plan des solutions réalisables pour la contrainte. L'intersection des différents
demi-plans de toutes les contraintes sans oublier les contraintes de positivité forme le
polygone des solutions, appelé aussi "région des solutions admissibles".

22
 Chapitre 2 : Programmation linéaire

Exemples : soit le problème suivant :

max Z  600 x1  400 x2
2.7
Sous contrainte :
4 x1  5 x2  55
x1  3 x2  27
2 x1  x2  20
2.8
x1 , x2  0
Le problème possède trois contraintes plus la contrainte de positivité. On commence à
tracer chaque contrainte séparément.
4 x1  5x2  55

On prend la première contrainte du système et on remplace l'inégalité par une égalité sans
l'ajout de variable d'écart, (cette façon de faire est applicable seulement pour la résolution
graphique). L'équation résultante correspond à une droite. Pour tracer une droite, il
faudrait déterminer deux points, ce qui donne pour la première contrainte notre exemple :

4 x1  5x2  55
 Si x1=0 x2=11 le premier point est (x1 , x 2) =(0 , 11)
 Si x2=0 x1=55/4 = 13.75 le deuxième point est (x1 , x 2) =(13.75 , 0)

À partir de ces points on trace la première droite et on conserve ce qui est en dessus de la
droite. On élimine ensuite la partie supérieure puisque la contrainte est une contrainte
d'infériorité.

x2

10

x1
5 10
4x1+5 x2 = 55
Figure. 2.1 – Représentation de la première contrainte
23
 Chapitre 2 : Programmation linéaire

Ainssi, on applique le même principe pour toutes les contraintes du système :

x1  3x2  27
 Si x1=0 x2=9 le premier point est (x1 , x 2) =(0 , 9)
 Si x2=0 x1=27 le deuxième point est (x1 , x 2) =(27 , 0)

2 x1  x2  20
 Si x1=0 x2=20 le premier point est (x1 , x 2) =(0 , 20)
 Si x2=0 x1=10 le deuxième point est (x1 , x 2) =(10 , 0)

Bien évidemment, il faut tracer aussi les contraintes de positivité. L'intersection de toutes
les contraintes forme le polygone de solutions tel qu'il est donné par la figure2.2.
x2

2x1+ x2 = 20

5
x1+3 x2 = 27

10 x1
4x1+5 x2 = 55

Figure. 2.2 – Représentation des différentes contraintes

La question qui se pose maintenant est : quel est le point qui donne la valeur optimale
pour ce problème ?

Pour répondre à cette question nous expliquerons la procédure à suivre pour déterminer
la valeur maximale pour ce problème qui consiste à tracer la droite qui correspond à la
fonction objective.

Tout d'abord, on prend l'équation de la fonction objective et on lui attribue la valeur de

zéro puisque c'est la plus petite valeur pour la fonction objective. Ce qui donne pour cet
exemple :

24
 Chapitre 2 : Programmation linéaire

400x1 + 600 x2 = 0,
6
4 x1 = - 6 x2 x1  x2 x1  1.5x2
4
Le coefficient directeur de cette fonction est (−1, 1.5). Il passe par l'origine (0, 0).
Une fois la droite tracée on effectue une translation parallèle à la direction de la droite du
bas vers le haut jusqu’à rencontrer le dernier point du polygone satisfaisant les contraintes.

x2

2x1+ x2 = 20

5
x1+3 x2 = 81

5 7.5 10 x1
4x1+5 x2 = 55

Figure. 2.3 – Résolution graphique du problème de production

Le maximum de Z sur cet ensemble de contraintes est alors atteint. On obtient ainsi le
point qui correspond à la solution optimale. Par la projection de ce point sur les axes x 1 et
x2 on obtient : x1=7.5 et x2 = 5, ce qui donne une valeur maximale Z = 6000.

La méthode graphique pour la résolution d'un problème linéaire à deux variables est très
facile à appliquer. Sa difficulté augmente par l'augmentation des variables dans le système.
Elle devient difficile pour trois variables et, voire impossible, au delà de trois inconnus
dans le système étudié.

Afin d'ôter cette difficulté, une méthode appelée méthode du simplexe a été proposée et
développée par Dantzig afin de résoudre des problèmes de programmation linéaire avec
plusieurs variables.

25
 Chapitre 2 : Programmation linéaire

2.3.2 La méthode du simplexe :

La méthodologie proposée pour cette technique consiste à visiter tous les états possibles
dans un système en partant d'un sommet vers un sommet adjacent de manière à réviser et
améliorer la fonction objective. Pour ce faire, nous procédons à l'exploration des
différentes démarches selon l'ordre de priorité donné ci dessous :

Démarche 1 : On démarre l'application de l'approche (méthode du simplexe) par la

transformation des contraintes d'inégalité en contraintes d'égalité en ajoutant les variables
d’écart.

Démarche 2 : Dans un second temps nous sélectionnons les variables originales comme
variables hors-base et les variables d'écarts comme variable basique. puis nous
effectuerons une permutation entre une variable hors-base de notre choix qui sera
remplacée par une variable de base (entrante). Le choix de la variable entrante repose sur
la variable dont le coefficient est le plus élevé dans la fonction objective.

Démarche 3 : La variable sortante est la première à s’annuler. On répète le processus

jusqu’à ce que tous les coefficients de fonction objective soient négatifs ou nuls. Dans ce
cas, on arrête et la solution optimale est trouvée.

Exemple : Considérons le problème suivant :

Max F = 40 y1 + 60 y2 2.9
Sous les contraintes
2y1 + y2 ≤ 70 2.10
y1 + y2 ≤ 40 2.11
y1 + 3y2 ≤ 90 2.12
y1 ≥ 0
y2 ≥ 0
Solution :

Soit y3, y4 et y5, les variables d’écart relatif respectivement aux contraintes 2.10, 2.11 et
2.12, qui permettent de transformer les contraintes d'inégalité pour obtenir les égalités
suivantes :
2y1 + y2 + y3 = 70 2.13
y1 + y2 + y4 = 40 2.14
y1 + 3y2 + y5 = 90 2.15

On commence à partir du point y1=0, y2=0 et on vérifie s'il est possible d'augmenter la
fonction objective sachant que notre système est un système de trois équations avec cinq

26
 Chapitre 2 : Programmation linéaire

inconnues. Pour trouver la solution on impose deux des variables à zéro et on déduit les
valeurs des trois variables restantes. Ce qui donne :
y1 = 0,
y2 = 0 ;
Pour les variables de base et :
y3 = 70
y4 = 40
y5 = 90
Pour les variables hors base.

Et la valeur de la fonction objective F = 40 y1 + 60 y2= 0,

La question qui se pose est : Est-il possible d'augmenter F ?

Pour répondre à cette question, on vérifie la fonction objective. Si les coefficients sont
positifs, ce qui est le cas, on a donc la possibilité d'augmenter F. On favorise
l'augmentation de la variable qui a le plus grand coefficient dans la fonction objective.
Donc on choisit y2 en maintenant y1 = 0.

On remplace y1=0 dans équation 2.13, 2.14, et 2.15

2y1 + y2 + y3 = 70 y2 + y3 = 70 2.16
y1 + y2 + y4 = 40 y2 + y4 = 40 2.17
y1 + 3y2 + y5 = 90 3y2 + y5 = 90 2.18

On réécrit les variables restantes en fonction d'y2 pour chaque équation. Ce qui nous
donne :

y3 = 70 - y2 ≥ 0 → y2 ≤ 70 2.19
y4 = 40 - y2 ≥ 0 → y2 ≤40 2.20
y5 = 90 - 3y2 ≥ 0 → y2 ≤ 30 2.21

On peut augmenter la valeur de y2 au maximum à 30 puisque c'est la valeur qui permet de

satisfaire les équations 2.19, 2.20 et 2.21.

Nouvelle solution admissible :

y1 = 0 ;
y2 = 30 ;
y3 = 40 ;
y4 = 10 ;
y5 = 0

27
 Chapitre 2 : Programmation linéaire

On remarque bien que y1=0 est toujours maintenu à zéro. Par ailleurs, y5 est passé de 90
a 0 et y2 est passé de 0 a 30 .Donc on déduit que pour cette étape la variable sortante de la
base est y2 et la variable entrante à la base est y5.

La nouvelle valeur de la fonction objective est : F = 40 y1 + 60y2 = 1800,

Les coefficients de la fonction objective sont positifs. Ce qui permet améliorer d'avantage
la solution obtenue. Dans ce cas on s'arrange pour exprimer toutes les équations en
fonction de y1 et y5. Pour ce faire on retire la valeur de y2 de la troisième équation et on
remplace son expression dans les deux premières. Il en est de même pour F, ce qui nous
donne dans cette étape les équations 2.22, 2.23 et 2.24

5/3 y1 + y3 - 1/3 y5 = 40 2.22

2/3 y1 + y4 - 1/3 y5 = 10 2.23
1/3 y1 + y2 + 1/3 y5 = 30 2.24

Nouvelle expression de la fonction objective F = 1800 + 20y1 - 20y5,

D'après l'expression de la fonction objective de l'étape précédente on choisit d’augmenter

y1 en gardant y5 =
5/3 y1 + y3 - 1/3 y5 = 40 y3 = 40 - 5/3 y1 ≥ 0 → y1 ≤ 24 2.25
2/3 y1 + y4 - 1/3 y5 = 10 y4 = 10 - 2/3 y1 ≥ 0 → y1 ≤ 15 2.26
1/3 y1 + y2 + 1/3 y5 = 30 y5 = 30 - 1/3 y1 ≥ 0 → y1 ≤ 90 2.27

La valeur maximale admissible pour y1 = 15.

Nouvelle solution admissible :
y1 = 15;
y2 = 25;
y3 = 15;
y4 = 0;
y5 = 0

Pour cette étape, la variable sortante de la base est y2 et la variable entrante à la base est
y4. L'expression de la nouvelle valeur du critère est : F = 2100 - 30y4 - 10y5,

Les coefficients de y4 et y5 dans la fonction objective de la dernière étape sont négatifs,

quelle que soient la valeur de y4 et y5 qui implique une diminution de la valeur du critère
F. Il n’existe donc plus d'augmentation et d’amélioration possible et la dernière solution
obtenue représente la solution optimale qui est égale à 2100.

28
 Chapitre 2 : Programmation linéaire

2.3.3 Résolution par Tableaux de simplexe

On commence par la transformation des contraintes d'inégalité en contraintes d'égalité en

introduisant des variables d’écart.

Étape 1
On construit un tableau à deux dimensions rxs où le nombre de colonnes r est égal au
nombre de variables (les variables de décision plus les variables d'écart) dans le système
plus une colonne de solution. Le nombre de lignes est égal au nombre d'équation dans le
système sans considération des contraintes de positivité.

A la première itération, on sélectionne la variable qui a le coefficient le plus élevé dans la

ligne objective (fonction objective). On encadrent la colonne de la variable entrante que
l’on appelle " colonne pivot".

Étape 2
On calcule le minimum du rapport du coefficient du membre de droite de chaque
contrainte sur le coefficient correspondant à la colonne. Dans le cas ou le coefficient dans
la colonne entrante est négatif ou infini, on ne le compte pas dans le calcul du minimum.
On encadre alors la ligne ou le minimum se produit. Cette ligne reçoit le nom de "ligne
pivot".

Le coefficient qui se trouve à l’intersection de la colonne pivot et de la ligne pivot est

appelé "élément pivot".

Étape 3
On reconstruit le tableau du simplexe (il faut conserver la même dimension du tableau).
On commence, d'abord, par construire la nouvelle ligne pivot qui se calcule de la manière
suivante :

Ancienne ligne pivot

Nouvelle ligne pivot 
Element pivot

Puis, on calcule les autres lignes par la formule suivante :

Toutes les autres lignes y compris z=

(Ligne actuelle)-(l'élément de sa colonne pivot) * (nouvelle ligne pivot)

29
 Chapitre 2 : Programmation linéaire

Exemple : Une entreprise disposant de 10 000 m2 de planches de bois en réserve

fabrique et commercialise 2 types de boîtes en bois. La fabrication d’une boîte en bois de
type 1 et de type 2 requiert, respectivement, 1 et 2 m2 de bois ainsi que 2 et 3 minutes de
temps d’assemblage. Seules 200 heures de travail sont disponibles pendant la semaine à
venir. Les boites sont clouées et, il faut quatre fois plus de clou pour une boîte du second
type que pour une du premier. Le stock de clous disponible permet d’assembler au
maximum 15 000 boîtes du premier type. Les boites sont vendues, respectivement, 3 et 5
du chiffre d’affaires.

Formulation du problème :
x1 : quantité de boîtes en bois de type 1
x2 : quantité de boîtes en bois de type 2

Max z = 3x1 + 5x2

Sous les contraintes :
x1 + 2x2 ≤ 10 000
2x1 + 3x2 ≤ 12 000
x1+4x2 ≤ 15 000 2.28
x1 ≥ 0 et x2 ≥ 0

Après avoir mis le programme linéaire sous sa forme standard

Max z = 3x1 + 5 x2

S.c. x1 + 2x2 + x3 = 10 000

2x1 + 3x2 + x4 = 12 000 2.29
x1 +4x2 + x5 = 15 000
x1 ≥ 0 et x2 ≥ 0

On peut réécrire le programme linéaire en fonction de toutes les variables du système

(variables de décision et variables d'écarts)

Max z = 3x1 + 5 x2 +0 x3 + 0 x4 +0 x5

x1 + 2x2 + x3 +0 x4 + 0x5 = 10 000

2x1 + 3x2 + 0 x3 + x4 +0 x5 = 12 000 2.30
x1 +4x2 +0 x3 +0 x4 + x5 = 15 000
x1 ≥ 0 , x2 ≥ 0, x3 ≥ 0 , x4 ≥ 0 et x5 ≥ 0

Puis, nous faisons juste une translation vers un tableau comme suit :

30
 Chapitre 2 : Programmation linéaire

Itération 1

z x1 x2 x3 x4 x5 sol
z -1 3 5 0 0 0 0
x3 0 1 2 1 0 0 10000
x4 0 2 3 0 1 0 12000
x5 0 1 4 0 0 1 15000

Dans ce tableau, nous allons définir la colonne pivot, la ligne pivot et l'élément pivot.
Nous commençons par la colonne pivot. Pour ce faire, nous sélectionnerons la variable
qui a le coefficient le plus élevé dans la ligne de la fonction objective qui est le 5 de la
variable x2. Donc la colonne pivot est la colonne du x2.

Ensuite, nous définirons la ligne pivot en divisant chaque solution par les éléments
correspondants dans la colonne pivot.
10000/2 = 5000

12000/3 = 4000

15000/4 = 3750

On choisit la plus petite valeur. Dans ce cas c'est la valeur de : 3750. Ce qui correspond à
la dernière ligne du tableau qui sera la ligne pivot.

Itération 1
Colonne
pivot

z x1 x2 x3 x4 x5 sol
z -1 3 5 0 0 0 0
x3 0 1 2 1 0 0 10000 5000
x4 0 2 3 0 1 0 12000 4000
x5 0 1 4 0 0 1 15000 3750

Ligne
Pivot Élément Pivot

L'intersection entre la colonne pivot et la ligne pivot, nous donne l'élément pivot qui est
égal à 4

31
 Chapitre 2 : Programmation linéaire

Itération 2

Une fois l'élément pivot déterminé, on calcule la nouvelle ligne pivot en divisant
l'ancienne ligne par l'élément pivot, ce qui donne :

0 1 4 0 0 1 15000
4 4 4 4 4 4 4

0 0.25 1 0 0 0.25 3750

On la place dans le nouveau tableau en conservant la même position que dans le premier
tableau sauf que la variable dans la colonne pivot prend la place de la variable de la ligne
pivot comme suit :
z x1 x2 x3 x4 x5 sol
z
x3
x4
x2 0 0,25 1 0 0 0,25 3750

Ensuite, on remplit toutes les autres lignes par la formule suivante :

(Ligne actuelle)-(l'élément de sa colonne pivot) * (nouvelle ligne pivot)

On applique le principe sur la ligne 3 (variable x4)

Ligne actuelle 0 2 3 0 1 0 12000
L'élément de sa colonne pivot : 3
Nouvelle ligne pivot : 0 0.25 1 0 0 0.25 3750
Résultats obtenus pour cette ligne :
0 1.25 0 0 1  0.75 750

Et de la même manière, on applique le même calcule pour les lignes de x3 et de z. On les

pace dans les zones appropriées dans le tableau de la deuxième itération.
z x1 x2 x3 x4 x5 sol
z -1 1,75 0 0 0 -1,25 -18750
x3 0 0,5 0 1 0 -0,5 2500 5000
x4 0 1,25 0 0 1 -0,75 750 600
x2 0 0,25 1 0 0 0,25 3750 15000

32
 Chapitre 2 : Programmation linéaire

À la fin de cette itération, on vérifie tous les coefficients de ligne z. S'ils sont négatifs ou
nuls on s'arrête. On a trouvé la solution optimale. Ce n'est pas le cas ici, la valeur de x1 est
positive. On construit donc une nouvelle itération et un nouveau tableau de la même
manière que pour l'itération2.

Itération 3
z x1 x2 x3 x4 x5 sol
z -1 0 0 0 -1,4 -0,2 -19800
x3 0 0 0 1 -0,4 -0,2 2200
x1 0 1 0 0 0,8 -0,6 600
x2 0 0 1 0 -0,2 0,4 3600

D'après le tableau de l'itération 3 on remarque que les coefficients de la ligne z, sont

négatifs ou nuls. Donc on s'arrête. On a trouvé la solution optimale avec :
x1 = 600
x2 = 3600
z = 19800

2.4 Dualité
2.4.1 Exemple : Problème de production.
Deux produits R1 et R2 sont fabriqués en quantité m1 et m2. La fabrication des deux
produits passe par trois machines afin de subir différents traitements. Bien évidemment le
but de l'entreprise est de maximiser son bénéfice total provenant de la vente des 2
produits. Le problème ainsi formulé est donné par le programme suivant :
Max F(x1; x2) = 6x1 + 4x2
Sous contraintes :
3x1 + 9x2 ≤81
4x1 + 5x2 ≤ 55 2.31
2x1 + x2 ≤ 20
x1; x2 ≥ 0

Pour certaines raisons, l'entreprise décide de vendre toutes ses ressources. Un acheteur se
présente et propose à l'entreprise les prix unitaires k1, k2, k3 pour chacune des ressources.
L'entreprise acceptera de lui vendre toutes ses ressources uniquement si le prix de vente
est au moins égal au profit qu'elle ferait en vendant ses produits. De son coté, l'acheteur
cherche à minimiser ses dépenses. Quels prix unitaires k1, k2, k3 l'acheteur doit-il
proposer à l'entreprise pour qu'elle accepte de vendre toutes ses ressources ?

33
 Chapitre 2 : Programmation linéaire

2.4.1 Qu'est ce que la dualité ?

La dualité est un programme linéaire qui reflète un programme linéaire d'un problème
donné par sa première de description (principale). Autrement dit, la dualité est une façon
de visualiser un problème donné sous un autre angle. La dualité d'un problème, peut-être
assimilé à l'effet miroir où on arrive à voir la même chose sauf que les coordonnées de la
base utilisée ne sont pas les mêmes.

La dualité est un concept important en recherche opérationnelle. Tout programme

linéaire admet un programme dual. Autrement dit, à tout problème de maximisation peut
être associé un problème de minimisation et à tout problème de minimisation peut être
associé un problème de maximisation. Le premier est appelé : primal, le second étant son
dual.

Programme linéaire primal Programme linéaire dual

max z  cT x min f  bT y 2.32

 Ax  b  AT y  c
 
 x  0  y  0

Le fait d'avoir un problème vu selon deux angles différents (primal - dual) liés d'une
certaine manière, met en évidence la dépendance des solutions entre primal - dual.
D'ailleurs on peut facilement trouver une solution de l'un à partir de la solution de l'autre.

2.4.2 Comment trouver le dual ?

Pour passer du primal au dual, certaines transformations doivent être considérées qui sont
définies comme suit :

a) Les termes du second membre des contraintes "bi" dans le problème primal deviennent
les coefficients de la nouvelle fonction objective du dual et les coefficients de la fonction
objective primal deviennent le second membre des contraintes du dual.

b) Les variables de décisions du problème primal deviennent des variables d'écarts dans le
problème dual et les variables d'écarts deviennent les variables de décisions.

c) Le problème de maximisation devient un problème de minimisation et le problème de

minimisation devient un problème de maximisation.

d) Les inégalités d'infériorité deviennent des inégalités de supériorité et inversement.

34
 Chapitre 2 : Programmation linéaire

e) La matrice A se transforme en sa transposée AT.( l'écriture en ligne devient l'écriture en

colonne).

Exemple : Reprenons l'exemple 2.31.

Max F(x1; x2) = 6x1 + 4x2

Sous contrainte :
3x1 + 9x2 ≤81
4x1 + 5x2 ≤ 55
2x1 + x2 ≤ 20
x1; x2 ≥ 0

A chaque contrainte, nous affecterons une variable appelée yi. La transformation est
donnée par le tableau A.

Problème primal Problème dual

Max F(x1; x2) = 6x1 + 4x2 Min k(y1; y2; y3) = 81 y1 + 55 y2 + 20 y3

S.C S.C
y1 x1 + 9 x2 ≤ 81 3 y1 + 4 y2 + 2 y3 ≥ 6
y2 4 x1 + 5 x2 ≤ 55 9 y1 + 5 y2 + 1 y3 ≥ 4
y3 2 x1 + 1 x2 ≤ 20 y1 ; y2 ; y3 ≥ 0
x1; x2 ≥ 0

Tableau A: Passage du primal vers le dual

2.4.4 Conditions d’optimalité primal-dual

L'ensemble primal-dual possède un certain nombre de conditions et de propriétés

indissociables raccordées l'une à l'autre, précisées comme suit : si le problème primal est
réalisable et possède une solution optimale donc, forcement, il existe une solution
optimale pour le dual qui est la même. Et si le problème primal est non réalisable, le
primal l'est non borné.

2.4.5 Exemple : le programme primal est

Max z  100 x1  200 x2
S.C x1  x2  150
4 x1  2 x2  440
x1  4 x2  480
x1  90
x1  0 , x2  0

35
 Chapitre 2 : Programmation linéaire

Donc le programme dual est :

Min w  150 y1  440 y 2  480 y3  90 y 4

S.C y1  4 y 2  y3  y 4  100
y1  2 y 2  4 y3  200
y1  0 , y 2  0

Nous proposons de résoudre ce système par les tableaux de simplexe.

On remarque bien que le problème dual est un problème de minimisation. Les tableaux
de Simplexe s'appliquent de la même manière expliquée dans la section 2.3.3. La seule
différence réside dans le choix de la colonne pivot qui se fait, en sélectionnant la variable
qui a le coefficient le plus bas(le plus petit) dans la ligne de la fonction objective.

Itération 1

z y1 y2 y3 y4 e1 e2 sol
z -1 150 440 480 90 0 0 0
e1 0 1 4 1 1 -1 0 100
e2 0 1 2 4 0 0 -1 200

Itération 2 :

z y1 y2 y3 y4 e1 e2 sol
z -1 60 80 390 0 90 0 -9000
y4 0 1 4 1 1 -1 0 100
e1 0 1 2 4 0 0 -1 200

Itération 3 :

z y1 y2 y3 y4 e1 e2 sol
z -1 0 -160 330 -60 150 0 -15000
y1 0 1 4 1 1 -1 0 100
e1 0 0 -2 3 -1 1 -1 100

Itération 4 :

z y1 y2 y3 y4 e1 e2 sol
z 1 0 -60 0 -50 -40 -110 -26000
y1 0 1 4,66667 0 1,33333 -1,3333 0,33333 66,6667
y3 0 0 -0,6667 1 -0,3333 0,33333 -0,3333 33,3333

36
 Chapitre 2 : Programmation linéaire

La solution optimale du dual peut être déduite du primal de la manière suivante :

y1 =0  S1 = 0
y2 = - 60  S2 = 60
y3 = 0  S3 = 0
y4 = - 50  S4 = 50
e1 = - 40  x1 = 40
e2 = -110  x2 = 110
w = - 26000  z = 26000

37
 TD N° 1
Formulation mathématique
 TD N° 1

TD N° 1 : Formulation mathématique

Pour chaque exercice, formuler le problème de programmation linéaire

Exercice 1 : Un atelier de couture fabrique en série deux modèles de tablier. Le premier

modèle nécessite 1 mètre de tissu, 4 heures de travail et rapporte 240 DA. Un tablier du
deuxième modèle exige 2 mètres de tissu, 2 heures de travail et rapporte 160 DA. Sachant
que l'atelier dispose quotidiennement de 150 mètres de tissu et de 400 heures de travail, et
qu'il peut vendre toute sa fabrication. Combien de tablier faut-il fabriquer pour obtenir un
bénéfice maximal ?

Exercice 2 : Une association culturelle organise une exposition, pendant cette exposition
des tasses de café au lait et des tasses de chocolat au lait sont vendues pour apporter une
aide aux orphelins. Un sponsor a permis de procurer 40 litres de lait, 4 kg de sucre et
assez de café et de chocolat pour faire 150 tasses de chaque boisson.
On prévoit de servir 2 sucres par tasse en moyenne ; chaque paquet d'un kilogramme de
sucre contient 120 morceaux ; il faut 1/4 de litre de lait pour une tasse de chocolat et
1/12 de litre de lait pour une tasse de café.
Le trésorier du club propose de vendre 50 DA chaque tasse de chocolat au lait et 40 DA
chaque tasse de café au lait.

Déterminez le nombre de tasses de chaque sorte à servir et calculez la recette maximale

collectée ?

Exercice 3 : Une entreprise disposant de 10 000 m2 de bois en réserve, fabrique et

commercialise 2 types de boîtes en bois. La fabrication d’une boîte en bois de type 1 et de
type 2 nécessite, respectivement, 1 et 2 m2 de carton ainsi que 20 et 30 minutes de temps
d’assemblage. Seules 200 heures de travail sont disponibles pendant la semaine à venir.
Les boites sont clouer et il faut quatre fois plus de clou pour une boîte du second type que
pour une du premier. Le stock de clous disponible permet d’assembler au maximum
15000 boîtes du premier type. Les boites sont vendues, respectivement, 300 DA et 500
DA. Déterminez le nombre de boite de chaque type pour avoir la recette maximale.

Exercice 4 : Une entreprise de cimenterie a 4 station (site) de production de [Link]

approvisionnement en matière première est fait principale à partir 6 carrière. La capacité

63
 TD N° 1

de production de chaque carrière les tailles des stocks (vides) disponibles aux différentes
stations à alimenter sont données dans les tableaux suivants :

Station Taille des stocks/tonne

1 50
2 60
3 20
4 90

Carrière Capacité carrière/tonne

1 40
2 40
3 60
4 20
5 40
6 20

Les coûts unitaires de transport d'un kilo de matière première de la carrière i à la station j
sont donnés par le tableau suivant :

1 2 3 4 5 6
1 9 12 9 6 9 10
2 7 3 7 7 5 5
3 6 5 9 11 3 11
4 4 6 11 2 2 10

1. L'offre et la demande sont elles réalisables ?

2. Formuler mathématiquement le problème
3. Donnez une représentation graphique du problème.

64
 TD N° 2
PL : résolution graphique
 TD N° 2

TD N° 2 : Programmation Linéaire résolution graphique

Pour chaque exercice, formuler le problème de programmation linéaire et le résoudre

graphiquement.

Exercice 1 : Un fabricant de basket fait un bénéfice de 800 DA sur chaque basket

ordinaire et de 1500 DA sur chaque basket professionnel. Pour satisfaire a la demande des
vendeurs, la production journalière de basket ordinaires devrait se situer entre 30 et 80, et
la production journalière de basket professionnel 10 et 30. Pour maintenir une bonne
qualité, le nombre de baskets produites ne devrait dépasser 80 par jour.
Combien de baskets de chaque type faudrait-il fabriquer pour réaliser un bénéfice
maximum ?

Exercice 2 : Une association culturelle organise une exposition, pendant cette exposition
des tasses de café au lait et des tasses de chocolat au lait sont vendues pour apporter une
aide aux orphelins. Un sponsor a permis de procurer 20 litres de lait, 2 kg de sucre et
assez de café et de chocolat pour faire 150 tasses de chaque boisson.
On prévoit de servir 2 sucres par tasse en moyenne ; chaque paquet de sucre contient 120
morceaux et le poids du paquet indiqué sur la boite est de 500 g ; il faut 1/4 de litre de lait
pour une tasse de chocolat et 1/12 de litre de lait pour une tasse de café. Le trésorier du
club propose de vendre 50 DA chaque tasse de chocolat au lait et 40 DA chaque tasse de
café au lait.

Déterminez le nombre de tasses de chaque sorte à servir et calculez la recette maximale

collectée ?

66
 TD N° 3
Algorithme des tableaux de simplexe
 TD N° 3

TD N° 3 : Algorithme des tableaux de simplexe.

Dans les exercices suivants, appliquer l’algorithme tableaux de simplexe pour trouver la
solution optimale de programmation linéaire.

Exercice 1 : Soit le problème d'optimisation suivant :

Maximiser z = 240 x1 +160 x2

Sous 1 x1 + 2 x2 ≤ 150
4 x1 + 2 x2 ≤ 400
avec x1 ; x2 ≥ 0

Exercice 2 : Soit le problème d'optimisation suivant :

Maximiser z = 3x1 + 5x2

Sous x1 + 2 x2 ≤ 10000
2x1 + 3 x2 ≤ 12000
x1 + 4 x2 ≤ 15000
avec x1 ; x2 ≥ 0

Exercice 3 : Soit le problème d'optimisation suivant :

Maximiser z = 3x1 + 4x2 + 2x3

Sous x1 + x2 - x3 ≤ 10
x1 - 2x2 + 3x3 ≤ 14
avec x1; x2; x3 ≥ 0

Exercice 4 : On veut résoudre le problème d'optimisation suivant :

Maximiser z = 4x1 + 6x2 + 3x3

Sous x1 + 6x2 + 2x3 ≤ 24
x1 + 3x2 - 2x3 ≤ 9
x1; x2; x3 ≥ 0

68
 TD N° 3

Exercice 5 : Soit le problème d'optimisation suivant :

Minimiser z = 10x1 + 6x2 + 8x3

Sous x1 + x2 +2x3 ≥ 2
5x1 + 3x2 + 2x3 ≥ 1
x1; x2; x3 ≥ 0

1. Formuler le problème dual du primal donné

2. Résoudre le problème dual par l'algorithme du simplexe

69