Programmation Linéaire

Recherche Opérationnelle (RO)

• Définition :
« Outil mathématique de l’aide à la décision qui
permet de trouver une solution optimale ou bien,
pour des problèmes NP-difficiles, une solution la
plus proche possible de l’optimum ».
 Recherche Opérationnelle (RO)

• Modélisation

Formulation Algorithme

Problème Modèle
Solution
réel mathématique

Programmation
Linéaire
 Recherche Opérationnelle (RO)

• Techniques de Modélisation :
– Programmation Linéaire
– Théorie des Graphes
– Théorie des Files d’Attente
– Simulation de Systèmes
– Théorie des Jeux
.
.
.
 Programmation Linéaire

• Gestion optimale de ressources

– Faire le mieux :
» coût minimum
» meilleur profit
– Avec les ressources disponibles :
» temps machine
» ressources humaines
» matière première
» postes de travail
.
.
.
 Programmation Linéaire

• Modèle linéaire 
– fonction linéaire, de plusieurs variables, à optimiser

– variables soumises à des contraintes :

» linéaires
» restrictions de non négativité
 Modèle Linéaire

• Exemple :
3 types de machines A, B et C
pour produire
4 produits différents I, II, III et IV.

Chaque produit doit être traité par

chacune des machines dans l’ordre
 Modèle Linéaire
• Exemple :
Caractéristiques des produits & machines
Disponibilité
Type de Produits hebdomadaire de
machine chaque machines
I II III IV
A 1,5 1 2,4 1 2000
B 1 5 1 3,5 8000
C 3 3,5 1
1,5 5000
Profit par unité 5,24 7,30 8,34 4,18
 Modèle Linéaire
• Exemple :
– But : établir la production hebdomadaire de chaque
produit de façon à maximiser le profit.

• Le modèle :
xj - production hebdomadaire du produit j.

but : trouver les valeurs de x1 , x2 , x3 et x4 qui

maximisent le profit, considérant la limite de temps
d’utilisation de chaque machine
 Modèle Linéaire

• Exemple :
– But : max z = 5,24 x1 + 7,30 x2 + 8,34 x3 + 4,18 x4

– Contraintes des machines :

A : 1,5 x1 + x2 + 2,4 x3 + x4  2000
B: x1 + 5 x2 + x3 + 3,5 x4  8000
C : 1,5 x1 + 3 x2 + 3,5 x3 + x4  5000

– Contraintes de non négativité :

x1 , x2 , x3 , x4  0
 Formulation

Forme générale :

max (ou min) z = c1 x1 + c2 x2 + ... + cr xr

Sous contraintes

ai 1 x1 + ai 2 x2 + ... + ai r xr   ,  ,   bi , i = 1,2, … , m

xj  0 ,  j = 1,2, … , r
 Remarques

max (ou min) z = c1 x1 + c2 x2 + ... + cr xr

sc
ai 1 x1 + ai 2 x2 + ... + ai r xr   ,  ,   bi , i = 1,2, … , m

xj  0 ,  j = 1,2, … , r contraintes de
non négativité
• xj - variables de décision
• z, fonction à optimiser - fonction objectif ( f. o. )
• cj , ai j et bi - constantes connues (expressions
linéaires)
 Résolution Graphique

• Problème à deux variables de décision

x1 et x2 :
– f. o. - droite dans  2
– contraintes - hemi-plans de  2

– P = (x1 , x2 ) - solution admissible (réalisable) si P satisfait

toutes les contraintes
– région admissible - l’ensemble des solutions admissibles
– solution optimale - solution admissible qui optimise la f.o.
 Exemple 1

x2 max z = 5 x1 + 3 x2
sc
3 x1 + 5 x2  15
5 x1 + 2 x2  10
x1 , x2  0

O x1
3x1 + 5x2 = 15

5x1 + 2x2 = 10
 Exemple 1

z1 x
A  z3 ;
z2 z 3 2 A  intersection des max z = 5 x1 + 3 x2
deux contraintes sc
3 x1 + 5 x2  15
z = 5x1 + 3x2 5 x1 + 2 x2  10
A x1 , x2  0

O x1  z
3x1 + 5x2 = 15
direction = - c1 / c2
= -5/3
5x1 + 2x2 = 10
 Exemple 1
z1
z2
x2 max z = 2,5 x1 + x2
AB z2 sc
3 x1 + 5 x2  15
z = 2,5x1 + x2 5 x1 + 2 x2  10
A x1 , x2  0

B x1
O
3x1 + 5x2 = 15
 z
direction = - c1 / c2
= -2,5
5x1 + 2x2 = 10
 Résumé

• Région admissible borné :

– polygone dont les côtés sont des segments des
droites représentant les contraintes linéaires du
problème
– un point P  à l ’intersection de 2 côtés du polygone
est un point extrême
– solution optimale:
» point extrême  solution optimale unique
» côté du polygone  infinité de solutions optimales
( la valeur de la f. o. est unique )
 Cas spéciaux

• Région admissible non borné

Une solution
contraintes :
unique
x2 x1  x2 =  1 z
max z = -3 x1 + 4 x2 3
z2  0,5x1 + x2 = 2
sc
x1 - x2  -1 z1
-0,5 x1 + x2  2
A
x1 , x2  0

x1
 Cas spéciaux

• Région admissible non borné

Une infinité
contraintes : de solutions
x2 x1  x2 =  1
max z = -x1 + 2 x2
z1  0,5x1 + x2 = 2
sc
x1 - x2  -1 z3
-0,5 x1 + x2  2 z2

x1 , x2  0

x1
 Cas spéciaux

• Région admissible non borné

contraintes : Pas de solution
finie
x2 x1  x2 =  1
max z = x1 + x2
sc z3  0,5x1 + x2 = 2
x1 - x2  -1 z2
-0,5 x1 + x2  2
z1
x1 , x2  0

x1
 Résumé

• Région admissible non borné :

– solution optimale:
» point extrême  solution optimale unique
» côté de la région admissible
 infinité de solutions optimales
( la valeur de la f. o. est unique )
» pas de solution optimale finie
 Un dernier cas spécial
• Région admissible vide 
contraintes incompatibles
er
1 cas :
x2  2x1 + 3x2 = 6  des hemi
x1 + x2 = 5 plans est vide
x1  x2 = 1 x1 + x2  5
- 2 x1 + 3 x2  6
x1 - x2  1
x1
x1 , x2  0
 Un dernier cas spécial
• Région admissible vide 
x contraintes incompatibles
2
ème
 x1 + x2 = 1 2 cas :
contrainte de
x1 + x2 =  1
non négativité
pas satisfaite
x1 + x2  -1
x1 - x + x  1
1 2

x1 , x2  0
 Généralisation

• Problème à r > 2 variables de décision 

solution graphique ?!?!
• Vocabulaire suggéré par la méthode
graphique :
1 - région admissible : région convexe d’un espace
de dimension r ( polyèdre convexe )
2 - un point P  à l’intersection de s  2 hyperplans
représentant les contraintes est un point extrême
du polyèdre
 Généralisation

• Problème à r > 2 variables de décision 

solution graphique ?!?!
• Vocabulaire suggéré par la méthode
graphique :
3 - solution optimale:
» unique  point extrême du polyèdre
» infinité de solutions optimales  frontière du polyèdre =
hyperplan de dimension < r ( la valeur de la f. o. est
unique )
 Résumé
• Région admissible :
– polyèdre convexe (polygone, dans 2) dont les
côtés représentent les contraintes linéaires du
problème
– borné ou non borné
– un point P  à l ’intersection de s  2 contraintes
est un point extrême
– solution optimale:

{{ » point extrême  solution optimale unique

» côté de la région admissible  infinité de solutions
optimales ( la valeur de la f. o. est unique )
» pas de solution optimale finie
 Méthode du Simplexe

• Méthode exacte et itérative

• Parcourt les points extrêmes jusqu’à
trouver la (les) solution(s) optimale(s), si
en existe
• Identification des cas de contraintes
incompatibles
• Basée sur l’algèbre des matrices
 Formulation

Forme générale :
max (ou min) z = c1 x1 + c2 x2 + ... + cr xr
sc
a1 1 x1 + a1 2 x2 + ... + a1 r xr   ,  ,   b1 ,
a2 1 x1 + a2 2 x2 + ... + a2 r xr   ,  ,   b2 ,
...
am 1 x1 + am 2 x2 + ... + am r xr   ,  ,   bm ,
xj  0 ,  j = 1,2, … , r
 Forme Canonique

Considérons toutes les contraintes du

type 
Vecteur ligne de taille r
r
max z =  cj xj max z = c x
j=1 Vecteur colonne de taille r
sc sc
r Matrice m x r
 ai j xj  bi ,  1  i  m Ax  b
j=1 Vecteur colonne de taille m
xj  0 ,  1  j  r x 0
 Forme Standard
Variable d’écart positif
r r
 ai j xj  bi   ai j xj + si = bi
j=1 j=1

max z ’ = c’ x ’ c’ = (c 0) x’ = x
sc ( s
(
où
A’ x ’ = b A’ = ( A | I )
x’  0 x  0, s  0
 Exemple

max z = 18 x1 + 12 x2 +
max z = 18 x1 + 12 x2
0 s1 + 0 s2 + 0 s3
sc
sc
4 x1 + 5 x2  20
4 x1 + 5 x2 + s1 = 20
2 x1 + x2  6
2 x1 + x2 + s2 = 6
x2  2
x2 + s3 = 2
x1 , x2  0
Ax x1 , x2 , s1 , s2 , s 3  0

si > 0  ai1 x1 + ai2 x2 < bi ; Is

si = 0  ai1 x1 + ai2 x2 = bi
 Fondements mathématiques

• A’ x’ = b
variables de décision
– m équations
– n = m + r variables

variables d’écart
– généralement rang A’ = m 
les m vecteurs lignes de A’ linéairement
indépendants ainsi que m des n vecteurs
colonnes de A’
 Fondements mathématiques
 a - ensemble des indices de colonnes de A’
 b  a avec |b | = m  j  b , { B j }  A
forment une matrice carrée B d’ordre m

 si B inversible  { B j } forment une base du

système

 i b  xi’ sont dénommées variables de base

 ib  a -b  xi’ sont dénommées variables
hors base
 Fondements mathématiques

xH
A’ x’ = b  (H | B ) ( xB
( =b

• On pose : xH = 0 et en multipliant les

deux termes par B-1  xB = B-1 b
• Or, Im est inversible. Ainsi,


solution
x (
= b  xH = x = 0
(A | I ) ( s
de base
réalisable
x = 0  origine et xB= s = b initiale
 Exemple
Forme canonique
max z = 18 x1 + 12 x2
sc
4 x1 + 5 x2  20
2 x1 + x2  6
x2  2

x1 , x2  0
 Exemple
Forme standard
max z = 18 x1 + 12 x2 + 0 s1 + 0 s2+ 0 s3
sc
4 x1 + 5 x 2 + s1 = 20
2 x1 + x2 + s2 = 6
x2 + s3 = 2

x 1 , x2 , s1 , s 2 , s3  0
 Exemple
x1
x2
max z = ( 18 12 0 0 0 ) S1
S2
sc
S3
x1
4 5 1 0 0 x2 20
2 1 0 1 0 S1 = 6
0 1 0 0 1 S2 2
S3

x , s 0
Ne définit pas une
solution de base Exemple max z = 18 x1 + 12 x2
x1 x2 s1 s2 s3 P réalisable sc
4x1 + 5x2 + s1 = 20
0 0 20 6 2 A
2x1 + x2 + s2 = 6
0 4 0 2 -2 B
x2 + s 3 = 2
0 6 -10 0 -4 C x2 x 1 , x2 , s1 , s2 , s3  0
0 2 10 4 0 D
5 0 0 -4 2 E C Points
2x1 + x2 = 6 extrêmes du
3 0 8 0 2 F
B polygone
0 0
5/3 8/3 0 0 -2/3 G G
D I H x2 = 2
5/2 2 0 -1 0 H
2 2 2 0 0 I E x1
A F
4x1 + 5x2 = 20
 Rappel : définitions et notations
• solution de base réalisable initiale :
– xB = variables d’écart - s  B = I 
– xN = variables de décision - x
{ xB = s = b
xN = x = 0

• but de la méthode du Simplexe

– Parcourir les points extrêmes jusqu’à trouver la
(les) solution(s) optimale(s), si en existe
• Théorème :
“Tous les points extrêmes de la région admissible
sont des solutions de base réalisables”
• changement de base  PIVOTAGE
 Pivotage
x2
max z = 18 x1 + 12 x2
sc
2x1 + x2 = 6
4 x1 + 5 x2  20
2 x1 + x2  6
x2  2 T1 = (0,2) T = (2,2) x2 = 2
2

x1 , x2  0
x1
T0= (0,0) T3 = (3,0)
4x1 + 5x2 = 20
 Tableau du Simplexe

• variable xj rentrante  variable qui

pourrait augmenter la f. o.
 inclure la f. o. dans le tableau de pivotage
max z = cN xN + cB xB
 max z
s. c.
z - (cN xN + cB xB ) = 0
N xN + x B = b
x  0 , z quelconque
 Tableau du Simplexe - Exemple

z xN xB xB = s ; xN = (x1 x2 )
z 1 zN- cN 0 cB = 0 ; cN = ( 18 12 )
z
xB 0 N I b zN - cN = cBN - cN = -cN
z = cBb = 0
z x1 x2 s1 s2 s3
z 1 -18 -12 0 0 0 0
s1 0 4 5 1 0 0 20
s2 0 2 1 0 1 0 6
s3 0 0 1 0 0 1 2
 Tableau du Simplexe
z xN xB
z 1 zN- cN 0 z
xB 0 N I b
• Choix de la colonne pivot :
N N N N N N
j telle que zj - cj = mink { (zk - ck ) ; (zk - ck ) < 0 }

• Choix de la ligne pivot :

i telle que bi / ai j = min l { bl / al j , al j > 0 }

 Tableau du Simplexe

• Condition d’arrêt :
– N N
si (zj - cj )  0,  j  z solution optimale finie

» N N
si (zj - cj ) > 0,  j  z solution unique

» N N
si  j tel que (zj - cj ) = 0  une infinité de solutions
optimales

– N N
si  j tel que (zj - cj ) < 0, avec ai j < 0,  i
 sans solution optimale finie
 Le problème de minimisation

• min z = cx  - max z’ = -cx

OU
• Condition d’arrêt :
N N
si (zj - cj )  0,  j

• Choix de la colonne pivot :

N N N N N N
j telle que zj - cj = maxk { (zk - ck ) ; (zk - ck )>0}

• Choix de la ligne pivot :

i telle que bi / ai j = min l { bl / al j , al j > 0 }
Méthode du simplexe – avec tableaux
• Nous allons utiliser des tableaux pour montrer les itérations de
l’algorithme du simplexe.

• Illustrons d’abord en complétant une itération du simplexe

sous cette forme pour le problème suivant.

min z = –8x – 6y min z

Sujet à Sujet à
5x + 3y + u =30 5x + 3y + u =30
2x + 3y + p =24 2x + 3y + p =24
1x + 3y + h = 18 1x + 3y + h = 18
x, y, u, p, h ≥ 0 –8x –6y –z = 0
x, y, u, p, h ≥ 0
 Tableau équivalent au système
min z = –8x – 6y min z
Sujet à Sujet à
5x + 3y + u =30 5x + 3y + u =30
2x + 3y + p =24 2x + 3y + p =24
1x + 3y + h = 18 1x + 3y + h = 18
x, y, u, p, h ≥ 0 –8x –6y –z = 0
x, y, u, p, h ≥ 0

u = 30 – 5x – 3y
p = 24 – 2x – 3y
h = 18 – 1x – 3y
z = 0 –8x – 6y
 u = 30 – 5x – 3y
p = 24 – 2x – 3y
h = 18 – 1x – 3y
z = 0 –8x – 6y

Étale 1: Critère d’entrée

Pour déterminer la variable d’entrée,
nous choisissons l’élément le plus
c s  min c j
1 j  n
  petit de la dernière ligne du tableau
min {–8, –6, 0, 0, 0} = –8.
x est donc la variable d’entrée
 u = 30 – 5x – 3y
p = 24 – 2x – 3y
h = 18 – 1x – 3y
z = 0 –8x – 6y

Étape 2: critère de sortie variable d’entrée

Pour identifier la variable de sortie
br  b i  déterminons le min des quotients des
xs   min  : a is  0
1i  m  a is 
a rs  termes de droite divisés par les
éléments correspondants dans la
colonne de la variable d’entrée
qui sont positifs:
 u = 30 – 5x – 3y
p = 24 – 2x – 3y
h = 18 – 1x – 3y
z = 0 –8x – 6y

Étape 2: critère de sortie variable d’entrée

br  b i  min {30/5, 24/2, 18} = 30/5 = 6

xs   min  : a is  0
1i  m  a is 
a rs 
La variable correspondante u
devient la variable de sortie
 u = 30 – 5x – 3y
p = 24 – 2x – 3y
h = 18 – 1x – 3y
z = 0 –8x – 6y

Variable de sortie variable d’entrée

Étape 3 : Pivot
Transformation du système ou
du tableau
• variable de sortie

variable d’entrée
RAPPEL: Nous utilisons l’équation où x et u apparaissent pour exprimer
x en fonction de u et y:
u = 30 – 5x – 3y => (5x = 30 – u – 3y) / 5
=> x = 6 – 1/5u – 3/5y
Ceci est équivalent à
5x + 3y + u =30
• variable de sortie

variable d’entrée
RAPPEL: Nous utilisons l’équation où x et u apparaissent pour exprimer
x en fonction de u et y:
u = 30 – 5x – 3y => (5x = 30 – u – 3y) / 5
=> x = 6 – 1/5u – 3/5y
Ceci est équivalent à
(5x + 3y + u =30) / 5
• variable de sortie

variable d’entrée
RAPPEL: Nous utilisons l’équation où x et u apparaissent pour exprimer
x en fonction de u et y:
u = 30 – 5x – 3y => (5x = 30 – u – 3y) / 5
=> x = 6 – 1/5u – 3/5y
Ceci est équivalent à
(5x + 3y + u =30) / 5 => x + 3/5y + 1/5u =6
• variable de sortie

variable d’entrée
Ceci est équivalent à
(5x + 3y + u =30) / 5 => x + 3/5y + 1/5u =6

En terme du tableau, ceci est équivalent à diviser la ligne de la variable de

sortie par le coefficient de la variable d’entrée dans cette ligne
 Divisons cette ligne par 5
• variable de sortie

variable d’entrée
Ceci est équivalent à
(5x + 3y + u =30) / 5 => x + 3/5y + 1/5u =6

En terme du tableau, ceci est équivalent à diviser la ligne de la variable de

sortie par le coefficient de la variable d’entrée dans cette ligne
 Divisons cette ligne par 5
variable de sortie

variable d’entrée

Le tableau qui en résulte est le suivant

x  3/ 5 y  1/ 5u  6
• Rappel: Nous substituons l’expression de x dans les autres équations
x = 6 – 1/5u – 3/5y
p = 24 – 2x – 3y
=> p = 24 – 2(6 – 1/5u – 3/5y) – 3y
Ceci est équivalent à : p = 24 – 2(6 – 1/5u – 3/5y) +2x – 2x – 3y
 2x + 3y + p – 2 (x + 3/5y +1/5u) = 24 – 2(6)
 deuxième ligne
moins
2(la première ligne)

Ceci est équivalent à : p = 24 – 2(6 – 1/5u – 3/5y) +2x – 2x – 3y

 2x + 3y + p – 2 (x +3/5y + 1/5u) = 24 – 2(6)
 2x + 3y + p = 24
– 2 (x +3/5y + 1/5u = 6)
0x + 9/5y –2/5u + p = 12
 deuxième ligne
moins
2(la première ligne)

Le tableau devient

0 x  9 / 5 y  2 / 5u  p  12
En répétant le processus pour les autres lignes du tableau
Itération typique

–
Étape 1: Choix de la variable d’entrée

• En se référant à la dernière ligne du tableau, soit c s  min c j

1 j  n
 
Variable d’entrée
Si c s ≥ 0, alors la solution
courante est optimale et
l’algorithme s’arrête

Si c s < 0, alors xs est la

variable d’entrée

–
Étape 2: Choix de la variable de sortie

Si a is  0  1  i  m
le problème n’est pas Variable d’entrée
borné et l’algo. s’arrête

Si i telque ais  0
alors la sol. demeure réalisable
  i tel que a is  0
bi
xi  b i  a is x s  0  x s 
a is
La variable d’entrée xs prend la valeur –
br  b i 
xs   min  : a is  0
1i  m  a is 
a rs 
Étape 2: Choix de la variable de sortie

Variable d’entrée

Variable de sortie

–
 Étape 3: Pivot
L’élément de pivot a rs est à l’intersection de la
colonne de la variable d’entrée xs et de la ligne
de la variable de sortie xr
Variable d’entrée

Variable de sortie

–
 Étape 3: Pivot
Divisons la ligne r par l’élément
de pivot a rs afin d’obtenir la
ligne r résultante
Variable d’entrée

Variable de sortie

1
a rs

–
 Étape 3: Pivot
Divisons la ligne r par l’élément
de pivot a rs afin d’obtenir la
ligne r résultante
Variable d’entrée

Variable de sortie

1 ar m1 arn br
1
ars ars ars ars

–
 Étape 3: Pivot
Multiplions la ligne r résultante
par a is pour la soustraire de la
ligne i du tableau. Ceci ramène le coefficient
de la variable d’entrée xs à 0.
Variable d’entrée

Variable de sortie

–
 Étape 3: Pivot
Multiplions la ligne r résultante
par a is pour la soustraire de la
ligne i du tableau. Ceci ramène le coefficient
de la variable d’entrée xs à 0.
Variable d’entrée

Variable de sortie

–
 Étape 3: Pivot
Multiplions la ligne r résultante
par a is pour la soustraire de la
ligne i du tableau. Ceci ramène le coefficient
de la variable d’entrée xs à 0.
Variable d’entrée

Variable de sortie

–
 Étape 3: Pivot
Multiplions la ligne r résultante
par c s pour la soustraire de la dernière
ligne du tableau. Ceci ramène le coefficient
de la variable d’entrée xs à 0.
Variable d’entrée

Variable de sortie

–
Tableau avant la prochaine itération

–
 Dualité

• À tout problème de PL on peut associer un autre problème PL,

son dual le primal

• Le problème dual permet de donner une autre interprétation

économique au problème primal
 Dualité

Exemple :

régime alimentaire :
– 6 produits alimentaires comme sources
de vitamines A et C

– but : minimiser le coût du régime tout en

satisfaisant la valeur nutritionnelle
minimale de chaque vitamine
 Dualité
Exemple :
Valeurs nutritionnelles & coût par produit

produit ( i ) Produits demande

(unités/kg) 1 2 3 4 5 6 (unité)

vitamine A 1 0 2 2 1 2 9
vitamine C 0 1 3 1 3 2 19

prix par kg 35 30 60 50 27 22
 Dualité

Le modèle :
xj = quantité consommée de chaque produit (en kg)
min z = 35 x1 + 30 x2 + 60 x3 + 50 x4 + 27 x5 + 22 x6
sc
x1 + 2 x3 + 2 x4 + x5 + 2 x6  9
x2 + 3 x 3 + x4 + 3 x5 + 2 x6  19

x1 , x2 , x 3 , x4 , x5 , x 6  0
 Dualité

Exemple : une autre vision du problème

producteur de cachets de vitamines synthétiques :
– 6 produits alimentaires contenant vitamines
A et C

– but : être compétitif tout en maximisant son

profit et en remplissant la demande
 Dualité
Exemple :
Prix maximum & composition de chaque produit

produit ( i ) Produits demande

(unité/kg) 1 2 3 4 5 6 (unité)

vitamine A 1 0 2 2 1 2 9
vitamine C 0 1 3 1 3 2 19

prix par kg 35 30 60 50 27 22
par exemple, prix compétitif du produit 5  inférieur ou égal à 27
 Dualité
Le modèle :
wi = prix d’une unité de chaque vitamine
produit 5 = 1 unité de vitamine A + 3 unités de vitamine C

 w1 + 3w2  27
max v = 9 w1 + 19 w2
sc
w1  35
w2  30
2 w1 + 3 w2  60
2 w1 + w2  50
w1 + 3 w2  27
2 w1 + 2 w2  22
w1 , w2  0
 Propriétés de la dualité
1 - Le dual du dual est le primal
2 - Pour toute paire de solutions réalisables x de P et w de D, on a cx  wb

x  0 et Ax  b  w (Ax)  wb
w  0 et wA  c  (wA) x  cx cx  (wA)x  wb

3 - Critère d’optimalité : cx* = w*b

sinon, cx’ < cx* = w*b < w’b ???

4 - Théorème Fondamental de la Dualité : si x* et w* sont les solutions

optimales finies de P et D, resp., alors z* = v*.
En effet z* = cx* = w*b = v*.
 A Two-Variable Problem
• Manufacture of chairs and tables:
– Resources available:
» Material: 400 boards of wood
» Labor: 450 man-hours
– Profit:
» Chair: $45
» Table: $80
– Resources needed:
» Chair
- 5 boards of wood
- 10 man-hours
» Table
- 20 boards of wood
- 15 man-hours
– Problem: How many chairs and how many tables should be
manufactured to maximize the total profit?
 Formulating Two-Variable Problem

• Manufacture x1 chairs and x2 tables to

maximize profit:
P = 45x1 + 80x2 dollars
• Subject to given resource constraints:
» 400 boards of wood, 5x1 + 20x2 ≤ 400 (1)
» 450 man-hours of labor, 10x1 + 15x2 ≤ 450 (2)
» x1 ≥ 0 (3)
» x2 ≥ 0 (4)
 Solution: Two-Variable Problem

40

30
Best solution: 24 chairs, 14 tables
20 Profit = 45×24 + 80×14 = 2200 dollars
Tables, x2

(1) 10
(24, 14)

(3)
(4)

0 10 20 30 40 50 60 70 80 90
Chairs, x1
increasing
(2)

decresing
 A Dual Problem
• Explore an alternative.
• Questions:
– Should we make tables and chairs?
– Or, auction off the available resources?
• To answer this question we need to know:
– What is the minimum price for the resources that will
provide us with same amount of revenue from sale as
the profits from tables and chairs?
– This is the dual of the original problem.
 Formulating the Dual Problem
• Revenue received by selling off
resources: Resources:
– For each board, w1 Material: 400 boards
Labor: 450 man-hrs
– For each man-hour, w2 Profit:
Chair: $45
• Minimize 400w1 + 450w2 Table: $80
Resources needed:
Chair
• Subject to constraints: 5 boards of wood
10 man-hours
Table
» 5w1 + 10w2 ≥ 45 20 boards of wood
15 man-hours
» 20w1 + 15w2 ≥ 80
» w1 ≥0
» w2 ≥0
 The Duality Theorem

• If the primal has a finite optimum solution,

so does the dual, and the optimum values
of the objective functions are equal.
 Primal-Dual Problems
• Primal problem • Dual Problem
– Fixed resources – Fixed profit
– Maximize profit – Minimize value
• Variables: • Variables:
» x1 (number of chairs) » w1 ($ value/board of wood)
» x2 (number of tables) » w2 ($ value/man-hour)
• Maximize profit 45x1+80x2 • Minimize value 400w1+450w2
• Subject to: • Subject to:
» 5x1 + 20x2 ≤ 400 » 5w1 + 10w2 ≥ 45
» 10x1 + 15x2 ≤ 450 » 20w1 + 15w2 ≥ 80
» x1 ≥0 » w1 ≥0
» x2 ≥0 » w2 ≥0
• Solution: • Solution:
» x1 = 24 chairs, x2 = 14 tables » w1 = $1, w2 = $4
» Profit = $2200 » value = $2200
 From Primal to Dual and inversely

X1 X2 X3 --- Xj --- Xn

Y1 a11 a12 a13 a1j a1n ≤ b1

Y2 ≤ b2
Y3 ≤ b3

Yi ai1 ai2 ai3 aij ain ≤ bi

Ym am1 am2 am3 amj amn ≤ bm

≥ ≥ ≥ ≥ ≥

C1 C2 C3 Cj Cn
 Solution: Primal-Dual
Variables primaires X1 X2 X3 X4 X5 X6 X7

Valeurs Primaires 100 0 250 0 0 560 140

|Couts marginaux| (Ci à la 0 200 0 160 500 0 0

fin du simplex)

Variables Duales Y4 Y5 Y6 Y7 Y1 Y2 Y3

Valeurs duales 0 200 0 160 500 0 0

|Couts marginaux| duales 100 0 250 0 0 560 140

(bi à la fin du simplex)