Dualité en programmation linéaire

François Schwarzentruber
18 janvier 2023

1 Certificat d’optimalité ?
Exemple 1 Considérons le programme linéaire suivant :
maximiser
 1 3x1 + 4x2
 2 x1 + 2x2 ≤ 30 (1)
3x1 + x2 ≤ 25 (2)
x1 , x2 ≥ 0


6 × (1) : 3x1 + 4x2 ≤ 3x1 + 12x2 ≤ 180

4 × (2) : 3x1 + 4x2 ≤ 12x1 + 4x2 ≤ 100
2 × (1) + 1 × (2) : 3x1 + 4x2 ≤ 4x1 + 5x2 ≤ 85
y1 × (1) + y2 × (2) : 3x1 + 4x2 ≤ ( 12 x1 + 2x2 )y1 + (3x1 + x2 )y2 = ( 21 y1 + 3y2 )x1 + (2y1 + y2 )x2 ≤ 30y1 + 25y2

minimiser
 1 30y1 + 25y2
 2 y1 + 3y2 ≥ 3
2y1 + y2 ≥ 4
y1 , y2 ≥ 0


Exemple 2 Considérons le programme linéaire suivant :

maximiser
 x1 + 6x2

 x1 ≤ 200 (1)
x2 ≤ 300 (2)


 x1 + x2 ≤ 400 (3)
x1 + x2 ≥ 0


Question. (x1 , x2 ) = (100, 300) est une solution optimale avec un objectif de 1900. Me croyez-vous ?
Vous pouvez me croire que c’est une solution : on remplace et on vérifie que (100, 300) vérifie les contraintes
et que l’objectif vaut 1900. Mais comment être sûr que c’est optimal ? En fait, on peut des fois (on verra que...
toujours !) en essayant de majorer l’objectif en sommant les contraintes.
Réponse.
• On a : (1) + 6(2) donne x1 + 6x2 ≤ 200 + 300 × 6 = 2000.
• Mieux : 0(1) + 5(2) + 1(3) donne x1 +6x2 ≤ 5×300+400 = 1900. Cela me certifie que 1900 est l’optimum.

Idée de généralisation. S’occuper de minimiser 200y1 + 300y2 + 400y3 sous la contrainte

(y1 + y3 )x1 + (y2 + y3 )x2 ≤ x1 y1 + x2 y2 + (x1 + x2 )y3 ≤ 200y1 + 300y2 + 400y3

| {z }
≥x1 +6x2 ?

Quid de considérer
minimiser
 200y1 + 300y2 + 400y3
 y1 + y3 ≥ 1
y2 + y3 ≥ 6 ?
y1 , y2 , y3 ≥ 0


2 Exemple d’une usine de meubles

On considère une usine de meubles.

1
 bureau table temps libre
menuiserie 1h 2h 20h
assemblage 2h 1h 22h
vernissage 1h 1h 12h
profit 300e 200e
Le programme primal consiste à calculer combien va-t-on construire de bureaux et de tables. Soit x1 le nombre
de bureaux construits, et x2 le nombre de tables construits. On souhaite maximiser le profit, mais en respectant
les contraintes de temps libres.
maximiser
 300x1 + 200x2

 x 1 + 2x 2 ≤ 20 (1)
2x1 + x2 ≤ 22 (2)


 x1 + x2 ≤ 12 (3)
x1 , x2 ≥ 0


300 × (1) : 300x1 + 200x2 ≤ 300x1 + 400x2 ≤ 6000

200 × (2) : 300x1 + 200x2 ≤ 400x1 + 200x2 ≤ 4400
300 × (3) 300x1 + 200x2 ≤ 300x1 + 300x2 ≤ 3600
100(2) + 100(3) : 300x1 + 200x2 ≤ 300x1 + 300x2 ≤ 3400
y1 (1) + y2 (2) + y3 (3) : 300x1 + 200x2 ≤ (y1 + 2y2 + y3 )x1 + (2y1 + y2 + y3 )x2 ≤ 20y1 + 22y2 + 12y3
On obtient donc :
minimiser
 20y1 + 22y2 + 12y3
 y1 + 2y2 + y3 ≥ 300
2y1 + y2 + y3 ≥ 200
y1 , y2 , y3 ≥ 0


Le programme dual s’explique aussi en changeant de point de vue. Supposons que l’on souhaite vendre à un
client tous le temps libre. On note y1 le prix d’1h de menuiserie, y2 le prix d’1h d’assemblage, y3 le prix d’1h
de vernissage. Le client va vouloir minimiser le prix de vente qui est de 20y1 + 22y2 + 12y3 . Mais nous, nous
ne voulons pas être perdant par rapport à une utilisation directe des ressources. Nous souhaitons que le revenu
gagné par exemple en vendant les ressources pour faire un bureau (à savoir y1 + 2y2 + y3 ) soit plus grand que ce
qu’on aurait gagné en vendant le bureau directement (300).

3 Motivation
1. Comprendre que le lien entre deux problèmes algorithmiques (par exemple : flot max et coupe min)
2. Construire des algorithmes spécialisés efficaces : transportation simplex method, l’algorithme hongrois
(pour couplage pondéré dans un graphe biparti), network simplex method
3. Analyser comment un programme est sensible aux modifications (ajout d’une contrainte, etc.).
4. Parfois, trouver une solution faisable est plus facile dans le dual que dans le primal
5. Démontrer des résultats théoriques de manière élégante
6. Interprétation en économie etc.
7. Parfois le dual est plus simple à résoudre que le primal.

4 Problème dual
Définition 3 (programme dual) A tout programme linéaire, appelé programme primal, on associe un pro-
gramme linéaire, appelé le programme dual, en utilisant cette recette de cuisine :
Programme primal Programme dual
Variables x1 , . . . , x n y1 , . . . , y m
Matrice A At
Vecteur de droite b c
Fonction objectif maximiser ct x minimiser bt y
Constraintes la i-ème contrainte a ≤ yi ≥ 0
la i-ème contrainte a ≥ yi ≤ 0
la i-ème contrainte a = yi ∈ R
xj ≥ 0 j-ème contrainte a ≥
xj ≤ 0 j-ème contrainte a ≤
xj ∈ R j-ème contrainte a =

2
Proposition 4 Le dual du dual de P est P .

Exercice 1 Donner le programme dual de

maximiser
 5x + 3y

 −5x + 2y ≤0
x+y ≤7


 x≤5
x, y ≥ 0


5 Plus court chemin : dualité et système physique

Définition 5 Problème d’un plus court chemin d’une source à une destination
entrée : graphe G = (S, A, poids) pondéré positivement, deux sommets s, t ∈ S
sortie : le poids d’un plus court chemin depuis s vers t ; +∞ sinon.

2
B D
4 4

A 1 3 1

2 3
C E
5

Proposition 6 Le problème d’un plus court chemin d’une source à une destination se réduit à la programmation
linéaire réelle. Pour trouver un plus court chemin de s à t dans G = (S, A, poids), on peut résoudre l’un des
programmes suivants
Programme primal
P
minimiser e∈A xe poids(e)
 P P

 P e partant de s xe − P e sortant de s xe =1
x − x = −1

Pe partant de t e Pe sortant de t e

 x
e partant de u e − e sortant de u xe = 0 pour tout sommet u 6∈ {s, t}
xe ≥ 0 pour tout arc e


Programme dual
maximiser dt − ds

dv − du 6 poids(u, v) pour tout arc u → v
du ∈ R pour tout sommet u
Démonstration. Ces programme sont [Link] verra que le théorème de dualité forte s’y applique,
mais on ne sait pas si les optimums sont atteints pour des solutions entières pour le programme primal. On verra
la matrice de ces problèmes est totalement unimodulaire. Et donc les optimums sont atteints par des solutions
entières. 

3
6 Sac à dos fractionnaire
6.1 Aucune limite sur la quantité de matière
c = (c1 , . . . , cn ) où ci = valeur d’une quantité de matière i
a = (a1 , . . . , an ) où ai = poids d’une quantité de matière i
b = poids maximal
On suppose ac11 ≥ ... ≥ acnn .

Programme dual D
Programme primal P minimiser by
maximiser ct x 
ay ≥ c
at x ≤ b

y≥0
x≥0
y (e/ kg) = variation de la valeur
x = (x1 , . . . , xn ) où xi est la
maximale gagnée quand b aug-
quantité de matière i prise
mente de 1kg
i.e
minimiser
 by
a 1 y ≥ c1
maximiser c1 x1 + · · · + cn xn



 ..

a1 x1 + · · · + an xn ≤ b .
x≥0 a y ≥ cn
 n


b

Une solution du primal : x1 = a1 , x2 = ... = xn = 0. y≥0
c1
La solution du dual : y = a1 .

6.2 Limite sur la quantité de matière

Programme dual D
minimiser by + z1 · · · + zn


 a1 y + z1 ≥ c1
 .
 ..


Programme primal P
maximiser
 t ct x  an y + zn ≥ cn
a x ≤ b



 

 x1 ≤ 1 y ≥ 0, z ≥ 0

 

..
 .

x ≤1 Une solution optimale du dual
 n



x≥0 est :
y = ackk
Une solution optimale du primal est de la forme :
x1 = . . .P
xk−1 = 1
b− k−1
a
zi = ci − ai ackk pour tout
i
xk = i=1
ak i = 1..k − 1
xk+1 = · · · = xn = 0
zk+1 = 0
..
.
zn = 0

7 Théorèmes de dualité
Programme primal P Programme dual D
maximiser ct x
 minimiser
 t bt y
Ax ≤ b Ay≥c
x≥0 y≥0

Théorème 7 (de dualité faible) Pour toute solution x de P , pour toute solution y de D, ct x ≤ bt y.

Démonstration. Pn
ct x = j=1 cj xj
Pn Pm
≤ j=1 ( i=1 aij yi ) xj par At y ≥ c
Pm Pm
= i=1 j=1 aij xj yi
Pm
≤ i=1 bi yi par Ax ≤ b
= bt y


4
Théorème 8 (de dualité forte) On est dans l’une des quatre situations suivantes :
1. P et D n’admettent pas de solutions ;
2. P est non borné et D n’admet pas de solutions ;
3. P n’admet pas de solutions et D est non borné ;
4. P possède une solution optimale x∗ , D possède une solution optimale y ∗ et ct x∗ = bt y ∗ .

Démonstration.
On se ramène à ces quatre cas via le théorème de dualité faible. Par exemple, le cas P non borné et D possède
une solution optimale est impossible. Il ne reste plus qu’à montrer le quatrième cas. Supposons que P possède
une solution optimale x∗ , montrer que D possède une solution optimale y ∗ et que ct x∗ = bt y ∗ .
maximiser 5x + 3y


 −5x + 2y ≤ 0
x+y ≤7

Exemple 9 Considérons le programme primal suivant :

 x≤5
x, y ≥ 0


Considérons l’exécution de l’algorithme du simplexe sur le problème primal P . L’algorithme commence par mettre
sous forme équationnelle :
maximiser
 c̄t x̄
Āx̄ = b où c̄ = (c, 0, . . . , 0), Ā = (A Idm ).
x̄ ≥ 0

maximiser 5x + 3y


 −5x + 2y + α = 0
x+y+β =7

Exemple 10 Voici le programme équationnel :

 x+γ =5
x, y, α, β, γ ≥ 0


L’algorithme considère alors le tableau associé, puis exécute des pivotages. On considère une exécution qui
termine, par exemple celle obtenue via règle de Bland. On atteint donc un tableau final de base B :
maximiser obj + c0t x̄N

x̄B = p − Qx̄N où les coordonnées du vecteur c0 sont négatives.
x̄ ≥ 0

maximiser
 31 − 2γ − 3β
 x=5−γ
Exemple 11 Le tableau final de base B = {x, y, α} est y =2+γ−β
α = 21 − 7γ + 2β


La solution basique x̄∗ de ce dernier tableau est telle que les n premières coordonnées x∗ de x̄∗ forment une
solution optimale du primal. On rappelle que x̄∗B = p = Ā−1 ∗ 0 t −1 t
B b et x̄N = 0 ; aussi c = c̄N − (c̄B ĀB ĀN ) ; (voir
cours sur l’algorithme du simplexe).

Exemple 12 x∗ = (5, 2) et x̄∗ = (5, 2, 21, 0, 0). x̄∗B = (5, 2, 21).

Posons y ∗ = (c̄tB Ā−1 t

B ) .
 
−5 2 1
Exemple 13 Ici, c̄tB = (5, 3, 0). La matrice ĀB = 1 1 0. Son inverse est Ā−1
B =
1 0 0
   
0 0 1 0
0 1 −1. On trouve y ∗ = 3.
1 −2 7 2

5
 Fait 14 ct x∗ = bt y ∗ .

Démonstration. ct x∗ = c̄t x̄∗ = c̄tB x̄∗B + c̄tN x̄∗N = c̄tB (Ā−1 t −1 ∗ t t ∗

B b) = (c̄B ĀB )b = (y ) b = b y . 
|{z}
0

Fait 15 y ∗ est une solution du dual (et donc est une solution minimale).

Démonstration. Il suffit de montrer les conditions de faisabilité At y ∗ ≥ c et y ∗ ≥ 0, que l’on peut résumer
par Āt y ∗ ≥ c̄. Posons w := Āt y ∗ = Āt (c̄tB Ā−1 t t −1 t
B ) = (c̄B ĀB Ā) . Regardons maintenant les coordonnées de w
selon que c’est une coordonnée dans la base du tableau final ou non :
wB = (c̄tB Ā−1 t
B ĀB ) = c̄B .
−1
wN = (c̄B ĀB ĀN )t = c̄N − c0 ≥ c̄N car c0 est un vecteur négatif. 
t

8 Interprétation physique
Programme primal P Programme dual D
maximiser
 ct x minimiser
 t bt y
Ax ≤ b Ay≥c
x≥0 y≥0

Afin d’être plus concret, considérons que x est de dimension 2 ou 3, et que x est la position d’une bille à
l’intérieur du polyèdre défini par Ax ≤ b. On suppose que c est le vecteur correspondant à la force de gravité.

Ainsi maximiser ct x revient à laisser agir la gravité. La bille tombe. Une solution optimale x∗ est la position
de la bille une fois tombée dans un creux (généralement, intersection de 3 faces, même si elle peut aussi rester en
plein milieu d’une face si elle est horizontale).
Soit N les indices des faces que la bille touche. Soit i ∈ N . Comme la bille touche la face i, la variable d’écart
correspondante est nulle. Dit autrement, voici la i-ème ligne-contrainte du programme primal : (Ax∗ )i = bi pour
tout i ∈ N . La ligne Ai. sont les coefficients de la face. Si on le considère comme un vecteur (colonne, autrement
dit on transpose), ce vecteur est normal à la face. Autrement dit, le vecteur Ati. est normal à la face i.
Faisons maintenant un peu de physique. La force de gravité F , proportionnelle à c. Elle se décompose sur
les vecteurs normaux des faces touchées par la bille. De même pour Pm c. Il existe donc y ∗ (la notation n’est pas
hasardeuse, on verra que c’est un optimum du dual) telle que c = i=1 yi (Ati. ) avec yi∗ = 0 pour i 6∈ N (bah oui,
∗

une face non touchée ne participe pas à la force). Autrement dit, c = At y ∗ . Montrons que

ct x∗ = bt y ∗ .

On a :
m
X X X X X
ct x∗ = (y ∗ )t Ax∗ = (y ∗ )i (Ax∗ )i = (y ∗ )i (Ax∗ )i + (y ∗ )i (Ax∗ )i = (y ∗ )i bi + (y ∗ )i bi = bt y ∗ .
| {z } | {z }
i=1 i∈N i6∈N i∈N i6∈N
0 0

9 Correspondance entre solutions primal/dual

Théorème 16 (coefficients magiques) Voici une solution optimale du problème dual :

6
 exécuter l’algorithme du simplexe dans le problème primal
soit c0 le vecteur des coefficients dans l’objectif du tableau final
y ∗ := opposés des coefficients dans c0 des variables d’écart (coefficient nul si dans la base)

Démonstration. Avant de lancer le simplexe, nous avons mis le problème primal sous forme équationnel,
puis nous avons introduire une variable d’écart par contraintes. N’oublions pas qu’il y a une variable dans le
problème dual pour chaque contrainte du problème primal. Donc il y a autant de variables d’écart que de
variables dans le problème dual. Donc le typage dans y ∗ := ... (dernière ligne de l’algo) est bon.
Considérons une variable d’écart d’indice i. La i-ème colonne de la matrice Ā, la matrice dans le problème
équationnel, que l’on note Āi est le i-ème vecteur unité, puisque la variable d’écart numéro i n’apparait que sur
la contrainte numéro i avec un coefficient 1.
Considérons maintenant la base B du dernière tableau de l’exécution de l’algorithme du simplexe :
maximiser obj + c0t x̄N

x̄B = p − Qx̄N où les coordonnées du vecteur c0 sont négatives.
x̄ ≥ 0

Reprenons les notations de la démonstration du théorème de dualité forte : w := Āt y ∗ = Āt (c̄tB Ā−1 t
B ) =
(c̄tB Ā−1 t
B Ā) .
t ∗ t ∗
Comme w := Ā y , on a wi = Āi y = yi . ∗

Comme i est une variable d’écart, c̄i = 0 (les variables d’écart n’apparaı̂ssent pas dans l’objectif de départ).
Ainsi, si on lit les équations de wB et wN donné en fin de la démonstration de la dualité on a :
• Si la variable d’écart i est dans B, alors wi = c̄i = 0 ;
• Si une variable d’écart i est dans N , alors wi = 0 − c0i = −c0i .
Conclusion :
• Si la variable d’écart i est dans B, alors yi∗ = 0 ;
• Si une variable d’écart i est dans N , alors yi∗ = −c0i .


Théorème 17 (des écarts complémentaires) Soit x une solution du primal P et y une solution du dual D.

x et y sont solutions P
1. pour tout indice i de contraintes de P , yi × (bi − j aij xj ) = 0 ;
optimales de ssi P
respectivement P et D 2. et pour tout indice j de contraintes de D, xj ×( i aij yi −cj ) = 0.

Démonstration.

x et y solutions optimales de leurs programmes respectifs

m
ct x = bt y (dualité forte)
m
ct x = y t Ax = bt y (voir démo du th. de dualité faible)
m
(ct − y t A)t x = 0 et y t (b − Ax) = 0 (réécriture algébrique)
m
points
P 1 et 2
(car les coordonnées des vecteurs sont positives et nombres positifs = 0 implique que ces nombres = 0)

10 Matrices totalement unimodulaires

Cas où un programme linéaire réel à coefficients entiers admet une solution optimale entière

Définition 18 (matrice totalement unimodulaire) Une matrice est totalement unimodulaire si toute sous-
matrice (en supprimant quelques lignes et/ou colonnes) carrée est de déterminant -1, 0 ou 1.

Proposition 19 Une matrice totalement unimodulaire ne contient que des -1, 0 ou 1.

 
1 −1 0
Exemple 1 est totalement unimodulaire.
−1 1 1
   
42 −1 1 −1
Exemple 2 et ne sont pas totalement unimodulaires.
−1 0 1 1

7
Proposition 20 Soit A une matrice totalement unimodulaire. La matrice Ā obtenue en ajoutant un vecteur
unité ei en dernière colonne est aussi totalement unimodulaire.

Démonstration. Calculer le déterminant d’une sous-matrice carrée en faisant un développement de

Laplace selon la dernière colonne. 
 
1 −1 0 1
Exemple 3 est totalement unimodulaire.
−1 1 1 0

maximiser ct x

Théorème 21 Considérons un programme linéaire Ax ≤ b où b ∈ Zm et A totalement unimodulaire.
x≥0
Si le programme admet une solution optimale, alors il admet une solution optimale entière x∗ ∈ Zn .
maximiser x + 3y − 5z

 x−y ≤ 30
Exemple 4 Si −x + y + z ≤ 42 est borné, alors il admet une solution maximale entière.
x, y, z ≥ 0


Démonstration. Étudions l’exécution de l’algorithme du simplexe. Il travaille d’abord sur un programme

équationnel où les contraintes sont Āx̄ = b avec Ā = (A | Idm ) et x̄ ∈ Rn+m . L’algorithme du simplexe trouve
une base B ∈ {1, . . . , n + m} telle que la solution basique associée x̄∗ soit définie par :

x̄∗B = Ā−1
B b
x̄∗N =0
Les coefficients de Ā−1
B s’écrivent, via les règles de Cramer, comme des fractions d’entiers avec au dénominateur
det(ĀB ). Comme A est totalement unimodulaire, Ā l’est aussi par la proposition 20. Ainsi, det(ĀB ) ∈ {−1, 0, 1}
(la valeur 0 est impossible car la matrice est inversible). 
Proposition 22 Soit A une matrice contenant seulement les éléments 0, 1 ou -1 et qui satisfait les 2 conditions
suivantes :
1. Chaque colonne contient au plus 2 éléments non nuls ;
2. Les lignes de A peuvent être partitionnées en 2 sous-ensembles S1 et S2 tel que pour chaque colonne
contenant 2 éléments non nuls :
• Si les 2 éléments non nuls ont le même signe, alors l’un est dans S1 et l’autre dans S2 ;
• Si les 2 éléments non nuls sont de signe différents, alors ils sont tous deux dans S1 , ou tous deux
dans S2 .
Alors A est totalement unimodulaire.

Démonstration. On pose

P(`) : le déterminant de toute sous-matrice de taille ` × ` de A est dans {−1, 0, 1}.

que l’on va démontrer par récurrence. Le cas de base P(1) est ok par définition de A. Supposons que P(` − 1).
Montrons P(`). Considérons une sous-matrice Q de taille ` × `. Par la condition 1, chaque colonne de A contient
au plus deux éléments non nuls. Ainsi, il en est de même pour chaque colonne de Q. S’il y a une colonne avec
que des 0, det(Q) = 0. S’il y a une colonne avec un seul élément non nul, on se ramène, à signe près, au calcul
du déterminant d’une sous-matrice de A de taille (` − 1) × (` − 1), qui est par récurrence de déterminant dans
{−1, 0, 1}. Enfin, toutes les colonnes de Q contiennent deux éléments non nuls, alors on montre que det(Q) = 0.
En effet, les lignes sont dépendantes.
1. En sommant toutes les lignes d’indices S1 , on obtient un certain vecteur ;
2. Et en sommant les lignes d’indices S2 on obtient le vecteur opposé, vu la condition 2.


11 Théorème de König
TODO: mettre la motivation SWERC

Théorème 23 Dans un graphe biparti,

cardinal d’un couplage maximal = cardinal d’une couverture minimal de sommets.

8
a 1 a 1

b 2 b 2
c 3 c 3
4 4

Démonstration. Quitte à renommer les objets, on note {1, . . . , n} l’ensemble des sommets,
et {1, . . . , m} l’ensemble des arêtes.

1) Programme linéaire pour le couplage maximal

Pm
maximiser j=1 xj
 P
 j incident à i xj ≤ 1 pour tout sommet i = 1..n
x≥0
x ∈ Zm


1 si l’arc j incidente au sommet i
En posant A ∈ Rn×m par aij = , ce programme se réécrit en :
0 sinon.
Pm
maximiser j=1 xj

 Ax ≤ 1
x≥0
x ∈ Zm


2) Programme linéaire pour la couverture minimal

Pn
minimiser
 P i=1 yi
 j incident à i yi ≥ 1 pour toute arête j = 1..m
y≥0
y ∈ Zn


que l’on peut réécrire en

Pn
minimiser i=1 yi

 At y ≥ 1
y≥0
y ∈ Zn


Si on avait “∈ Rm ” et “∈ Rn ” à la place “∈ Zm ” et “∈ Zn ”, les programmes seraient duaux l’un de l’autre

et cela conclurait la démonstration. Ici, on ne peut pas conclure car il n’y a pas de théorème de dualité pour la
programmation linéaire entière. Mais heureusement, la proposition 22 conclut la démonstration ! En effet :
1. Chaque colonne (arête) est incidente à deux sommets ;
2. Les paquets S1 et S2 sont pile poil les deux patates de sommets du graphe biparti.

Exercice 24 Montrer que la matrice d’incidence signée du problème du plus court chemin (et aussi du problème
de flots) est totalement unimodulaire. On notera qu’il n’y a pas besoin ici que le graphe soit biparti.

Notes bibliographiques
La dualité est évoquée dans [DPV08] et [CLRS09]. L’explication avec le certificat provient de [DPV08]. Les
démonstrations et les applications proviennent essentiellement de [GM07].

Références
[CLRS09] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to
Algorithms, 3rd Edition. MIT Press, 2009.
[DPV08] Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani. Algorithms. McGraw-Hill, 2008.
[GM07] Bernd Gärtner and Jirı́ Matousek. Understanding and using linear programming. Universitext. Sprin-
ger, 2007.