Embed Size (px)
Citation preview
1
Lecon 1
Programmation lineaire
Xavier Goaoc
1
Lecon 1
Programmation lineaire
Xavier Goaoc
2
Developpee tardivement (Kantorovitch 1939, Dantzig 1947, ...)
impact difficile a surevaluer, en theorie et en pratique.
La programmation lineaire est la theorie des systemes d’inegalites lineaires.
systeme lineaire, sous-espace affine, pivot de Gauss
→ programme lineaire, polyedre, algorithme du simplexe
3
Premiers exemples
de programmes lineaires
4
Un programme lineaire (PL) est un probleme qui consiste a maximiser sur Rd
une fonction lineaire sous des contraintes lineaires.
max x1 + x2
t.q. x1 ≥ 02x2 − x1 ≤ 2
x2 − 2x1 ≥ −4x1 + x2 ≥ 0
4
Un programme lineaire (PL) est un probleme qui consiste a maximiser sur Rd
une fonction lineaire sous des contraintes lineaires.
max x1 + x2
t.q. x1 ≥ 02x2 − x1 ≤ 2
x2 − 2x1 ≥ −4x1 + x2 ≥ 0
x2
x1
4
Un programme lineaire (PL) est un probleme qui consiste a maximiser sur Rd
une fonction lineaire sous des contraintes lineaires.
max x1 + x2
t.q. x1 ≥ 02x2 − x1 ≤ 2
x2 − 2x1 ≥ −4x1 + x2 ≥ 0
x2
x1
4
Un programme lineaire (PL) est un probleme qui consiste a maximiser sur Rd
une fonction lineaire sous des contraintes lineaires.
max x1 + x2
t.q. x1 ≥ 02x2 − x1 ≤ 2
x2 − 2x1 ≥ −4x1 + x2 ≥ 0
x2
x1
4
Un programme lineaire (PL) est un probleme qui consiste a maximiser sur Rd
une fonction lineaire sous des contraintes lineaires.
max x1 + x2
t.q. x1 ≥ 02x2 − x1 ≤ 2
x2 − 2x1 ≥ −4x1 + x2 ≥ 0
x2
x1
4
Un programme lineaire (PL) est un probleme qui consiste a maximiser sur Rd
une fonction lineaire sous des contraintes lineaires.
max x1 + x2
t.q. x1 ≥ 02x2 − x1 ≤ 2
x2 − 2x1 ≥ −4x1 + x2 ≥ 0
x2
x1
4
Un programme lineaire (PL) est un probleme qui consiste a maximiser sur Rd
une fonction lineaire sous des contraintes lineaires.
max x1 + x2
t.q. x1 ≥ 02x2 − x1 ≤ 2
x2 − 2x1 ≥ −4x1 + x2 ≥ 0
x2
x1
4
Un programme lineaire (PL) est un probleme qui consiste a maximiser sur Rd
une fonction lineaire sous des contraintes lineaires.
max x1 + x2
t.q. x1 ≥ 02x2 − x1 ≤ 2
x2 − 2x1 ≥ −4x1 + x2 ≥ 0
x2
x1
4
Un programme lineaire (PL) est un probleme qui consiste a maximiser sur Rd
une fonction lineaire sous des contraintes lineaires.
max x1 + x2
t.q. x1 ≥ 02x2 − x1 ≤ 2
x2 − 2x1 ≥ −4x1 + x2 ≥ 0
Une forme generale
max cTx
t.q. Ax ≤ b
x ∈ Rd, A ∈ Rn×d, b ∈ Rn
x2
x1
4
Un programme lineaire (PL) est un probleme qui consiste a maximiser sur Rd
une fonction lineaire sous des contraintes lineaires.
max x1 + x2
t.q. x1 ≥ 02x2 − x1 ≤ 2
x2 − 2x1 ≥ −4x1 + x2 ≥ 0
Une forme generale
max cTx
t.q. Ax ≤ b
x ∈ Rd, A ∈ Rn×d, b ∈ Rn c =
(11
), A =
−1 0−1 2−1 −12 −1
, b =
0204
x2
x1
5
Valeur d’ un PL = valeur maximale dans [−∞,+∞] atteinte par la fonction a optimiser
Resoudre un programme lineaire = determiner un vecteur x optimal
ou qu’aucun x ne satisfait toutes les contraintes.
5
Algorithmes du simplexe, methode de l’ellipsoide, methodes de point interieur,algorithmes primal-dual, methodes par echantillonnage, . . .
Valeur d’ un PL = valeur maximale dans [−∞,+∞] atteinte par la fonction a optimiser
Resoudre un programme lineaire = determiner un vecteur x optimal
ou qu’aucun x ne satisfait toutes les contraintes.
5
On sait resoudre les programmes lineaires efficacement
Algorithmes du simplexe, methode de l’ellipsoide, methodes de point interieur,algorithmes primal-dual, methodes par echantillonnage, . . .
en pratique : algorithmes du simplexe, implantation efficaces, . . .
plusieurs milliers de variables et de contraintes.
Valeur d’ un PL = valeur maximale dans [−∞,+∞] atteinte par la fonction a optimiser
Resoudre un programme lineaire = determiner un vecteur x optimal
ou qu’aucun x ne satisfait toutes les contraintes.
5
On sait resoudre les programmes lineaires efficacement
Algorithmes du simplexe, methode de l’ellipsoide, methodes de point interieur,algorithmes primal-dual, methodes par echantillonnage, . . .
en theorie : algorithmes polynomiaux en la representation du PL.
(On cherche encore un algorithme polynomial en n et d. . . )
en pratique : algorithmes du simplexe, implantation efficaces, . . .
plusieurs milliers de variables et de contraintes.
Valeur d’ un PL = valeur maximale dans [−∞,+∞] atteinte par la fonction a optimiser
Resoudre un programme lineaire = determiner un vecteur x optimal
ou qu’aucun x ne satisfait toutes les contraintes.
5
On sait resoudre les programmes lineaires efficacement
Algorithmes du simplexe, methode de l’ellipsoide, methodes de point interieur,algorithmes primal-dual, methodes par echantillonnage, . . .
en theorie : algorithmes polynomiaux en la representation du PL.
(On cherche encore un algorithme polynomial en n et d. . . )
en pratique : algorithmes du simplexe, implantation efficaces, . . .
plusieurs milliers de variables et de contraintes.
Reduire une question a un (ou plusieurs) PL est une bonne nouvelle !
Valeur d’ un PL = valeur maximale dans [−∞,+∞] atteinte par la fonction a optimiser
Resoudre un programme lineaire = determiner un vecteur x optimal
ou qu’aucun x ne satisfait toutes les contraintes.
6
Exemple 1 : optimisation logistique
Une patisserie industrielle possede deux sites de production, a Quimper et a Vannes.Elle expedie sa production vers Rouen, Paris et Bordeau. La capacite maximalede production de Quimper est de 350 caisses/semaine et celle de Vannes est de650 caisses par semaine. La demande a satisfaire a chaque destination est de 300caisses par semaine. Les quantites de CO2 emises pour transporter une caisse d’unsite de production vers un site de consommation sont :
Paris Rouen BordeauQuimper 25 17 18Vannes 25 18 14
On cherche a determiner le plan de production et de transport qui satisfait lesdemandes en degageant le moins de CO2 possible.
6
Exemple 1 : optimisation logistique
Une patisserie industrielle possede deux sites de production, a Quimper et a Vannes.Elle expedie sa production vers Rouen, Paris et Bordeau. La capacite maximalede production de Quimper est de 350 caisses/semaine et celle de Vannes est de650 caisses par semaine. La demande a satisfaire a chaque destination est de 300caisses par semaine. Les quantites de CO2 emises pour transporter une caisse d’unsite de production vers un site de consommation sont :
Paris Rouen BordeauQuimper 25 17 18Vannes 25 18 14
On cherche a determiner le plan de production et de transport qui satisfait lesdemandes en degageant le moins de CO2 possible.
min 25xPQ + 25xPV + 17xRQ + 18xRV + 18xBQ + 14xBV
t.q. xPQ + xPV ≥ 300
xRQ + xRV ≥ 300
xBQ + xBV ≥ 300
xPQ + xRQ + xBQ ≤ 350
xPV + xRV + xBV ≤ 650
xPQ, . . . , xBV ≥ 0
6
Exemple 1 : optimisation logistique
Une patisserie industrielle possede deux sites de production, a Quimper et a Vannes.Elle expedie sa production vers Rouen, Paris et Bordeau. La capacite maximalede production de Quimper est de 350 caisses/semaine et celle de Vannes est de650 caisses par semaine. La demande a satisfaire a chaque destination est de 300caisses par semaine. Les quantites de CO2 emises pour transporter une caisse d’unsite de production vers un site de consommation sont :
Paris Rouen BordeauQuimper 25 17 18Vannes 25 18 14
On cherche a determiner le plan de production et de transport qui satisfait lesdemandes en degageant le moins de CO2 possible.
t.q.
max − (25xPQ + 25xPV + 17xRQ + 18xRV + 18xBQ + 14xBV )
xPQ + xPV ≥ 300
xRQ + xRV ≥ 300
xBQ + xBV ≥ 300
xPQ + xRQ + xBQ ≤ 350
xPV + xRV + xBV ≤ 650
xPQ, . . . , xBV ≥ 0
6
Exemple 1 : optimisation logistique
Une patisserie industrielle possede deux sites de production, a Quimper et a Vannes.Elle expedie sa production vers Rouen, Paris et Bordeau. La capacite maximalede production de Quimper est de 350 caisses/semaine et celle de Vannes est de650 caisses par semaine. La demande a satisfaire a chaque destination est de 300caisses par semaine. Les quantites de CO2 emises pour transporter une caisse d’unsite de production vers un site de consommation sont :
Paris Rouen BordeauQuimper 25 17 18Vannes 25 18 14
On cherche a determiner le plan de production et de transport qui satisfait lesdemandes en degageant le moins de CO2 possible.
t.q.
max − (25xPQ + 25xPV + 17xRQ + 18xRV + 18xBQ + 14xBV )
Une imprimerie fonctionne 45 heures par semaine. En une heure elle peut imprimeret decouper 25 jeux de tarot, 50 jeux de 54 cartes ou 75 jeux de 32 cartes. Lemarche hebdomadaire est de 500 jeux de tarot, 1000 jeux de 54 cartes et 1500jeux de 32 cartes. Les expeditions ont lieu une fois par semaine, donc le local destockage doit etre capable de contenir la totalite de la production hebdomadaire.Il contient au plus 2000 jeux de tarot ou 4000 jeux de 54 cartes ou 7500 jeux de32 cartes (ou toute combinaison, par exemple 1000 jeux de tarot et 2000 jeux de54 cartes). Le profit realise est de 1 euro par jeu de tarot, 30 centimes par jeu de54 cartes et 25 centime par jeu de 32 cartes. L’entreprise cherche la productionqui maximise son profit...
xPQ + xPV ≥ 300
xRQ + xRV ≥ 300
xBQ + xBV ≥ 300
xPQ + xRQ + xBQ ≤ 350
xPV + xRV + xBV ≤ 650
xPQ, . . . , xBV ≥ 0
6
Exemple 1 : optimisation logistique
Une patisserie industrielle possede deux sites de production, a Quimper et a Vannes.Elle expedie sa production vers Rouen, Paris et Bordeau. La capacite maximalede production de Quimper est de 350 caisses/semaine et celle de Vannes est de650 caisses par semaine. La demande a satisfaire a chaque destination est de 300caisses par semaine. Les quantites de CO2 emises pour transporter une caisse d’unsite de production vers un site de consommation sont :
Paris Rouen BordeauQuimper 25 17 18Vannes 25 18 14
On cherche a determiner le plan de production et de transport qui satisfait lesdemandes en degageant le moins de CO2 possible.
t.q.
max − (25xPQ + 25xPV + 17xRQ + 18xRV + 18xBQ + 14xBV )
Une imprimerie fonctionne 45 heures par semaine. En une heure elle peut imprimeret decouper 25 jeux de tarot, 50 jeux de 54 cartes ou 75 jeux de 32 cartes. Lemarche hebdomadaire est de 500 jeux de tarot, 1000 jeux de 54 cartes et 1500jeux de 32 cartes. Les expeditions ont lieu une fois par semaine, donc le local destockage doit etre capable de contenir la totalite de la production hebdomadaire.Il contient au plus 2000 jeux de tarot ou 4000 jeux de 54 cartes ou 7500 jeux de32 cartes (ou toute combinaison, par exemple 1000 jeux de tarot et 2000 jeux de54 cartes). Le profit realise est de 1 euro par jeu de tarot, 30 centimes par jeu de54 cartes et 25 centime par jeu de 32 cartes. L’entreprise cherche la productionqui maximise son profit...
xPQ + xPV ≥ 300
xRQ + xRV ≥ 300
xBQ + xBV ≥ 300
xPQ + xRQ + xBQ ≤ 350
xPV + xRV + xBV ≤ 650
xPQ, . . . , xBV ≥ 0
Un restaurateur dispose de 880 oursins et de 720 huıtres. Ilpropose a sa clientele deux types d’assiette : assiette a 20euros (4 oursins, 1 huıtre) ou assiette a 15 euros (2 oursins,3 huıtre). Quelle recette maximum est envisageable par cerestaurateur ?
7
Exemple 2 : flot dans un graphe
1
2 3
4 5 6
7 8 9
1500
11
00
16
00
850
700
22
00
4000
1300
1180
2100
17
50920
14
00
3630
Un reseau (informatique, routier, . . . )
Chaque arete a une capacite
= flot maximal (de donnees, de voitures, . . . )sur cette arete par unite de temps
7
Exemple 2 : flot dans un graphe
1
2 3
4 5 6
7 8 9
1500
11
00
16
00
850
700
22
00
4000
1300
1180
2100
17
50920
14
00
3630
Un reseau (informatique, routier, . . . )
Le flot maximum possible entre deux sommetsdonne est donne par un PL.
Chaque arete a une capacite
= flot maximal (de donnees, de voitures, . . . )sur cette arete par unite de temps
7
Exemple 2 : flot dans un graphe
1
2 3
4 5 6
7 8 9
1500
11
00
16
00
850
700
22
00
4000
1300
1180
2100
17
50920
14
00
3630
Un reseau (informatique, routier, . . . )
Le flot maximum possible entre deux sommetsdonne est donne par un PL.
Chaque arete a une capacite
= flot maximal (de donnees, de voitures, . . . )sur cette arete par unite de temps
une variable par arete
ecrire les lois de Kirchhoff
(sauf aux deux sommets en question)
maximiser le flot en un des sommets speciaux
8
Exemple 3 : regression lineaire `1
(x1
y1
),
(x2
y2
), . . . ,
(xn
yn
)des points de donnees dans R2.
8
Exemple 3 : regression lineaire `1
(x1
y1
),
(x2
y2
), . . . ,
(xn
yn
)des points de donnees dans R2.
Comment trouver la droite minimisant lasomme des distance `1 a ces points ?
8
Exemple 3 : regression lineaire `1
(x1
y1
),
(x2
y2
), . . . ,
(xn
yn
)des points de donnees dans R2.
Comment trouver la droite minimisant lasomme des distance `1 a ces points ?
min∑n
i=1 |axi + b− yi|
Idee : introduire deux variables a, bet chercher
8
Exemple 3 : regression lineaire `1
(x1
y1
),
(x2
y2
), . . . ,
(xn
yn
)des points de donnees dans R2.
Comment trouver la droite minimisant lasomme des distance `1 a ces points ?
min∑n
i=1 |axi + b− yi|
pas PL...
Idee : introduire deux variables a, bet chercher
8
Exemple 3 : regression lineaire `1
(x1
y1
),
(x2
y2
), . . . ,
(xn
yn
)des points de donnees dans R2.
Comment trouver la droite minimisant lasomme des distance `1 a ces points ?
min∑n
i=1 |axi + b− yi|
pas PL...
Idee : introduire deux variables a, bet chercher
min e1 + e2 + . . .+ en
Meilleure idee : introduire 2+n variables a, b, e1, e2, . . . , enet chercher
t.q. ei ≥ axi + b− yiei ≥ − (axi + b− yi)
pour i = 1, 2, . . . , n
9
Methode du simplexe
Intuition geometrique
10
x ∈ Rd, A ∈ Rn×d, b ∈ Rn
Ax ≤ b = intersection de demi-espaces de Rd
= polyedre convexe (event. vide)(P)
max cTx
t.q. Ax ≤ b
x2
x1
+animation
+ reduction a un sommet
10
x ∈ Rd, A ∈ Rn×d, b ∈ Rn
Ax ≤ b = intersection de demi-espaces de Rd
= polyedre convexe (event. vide)(P)
max cTx
t.q. Ax ≤ b
Les lignes de niveau de cTx sont des hyperplans
x2
x1
+animation
+ reduction a un sommet
c
10
x ∈ Rd, A ∈ Rn×d, b ∈ Rn
Ax ≤ b = intersection de demi-espaces de Rd
= polyedre convexe (event. vide)(P)
max cTx
t.q. Ax ≤ b
Les lignes de niveau de cTx sont des hyperplans
x2
x1
+animation
+ reduction a un sommet
c
On cherche un point d’appuide l’hyperplan support a Ax ≤ bdans la direction c.
10
x ∈ Rd, A ∈ Rn×d, b ∈ Rn
Ax ≤ b = intersection de demi-espaces de Rd
= polyedre convexe (event. vide)(P)
max cTx
t.q. Ax ≤ b
Les lignes de niveau de cTx sont des hyperplans
x2
x1
+animation
+ reduction a un sommet
c
On cherche un point d’appuide l’hyperplan support a Ax ≤ bdans la direction c.
On peut restreindre la rechercheaux sommets de Ax ≤ b.
11
max cTx
t.q. Ax ≤ bn’a pas de solution si et seulement si
Ax ≤ b est vide ou cTx est non borneesur Ax ≤ b
11
max cTx
t.q. Ax ≤ bn’a pas de solution si et seulement si
Ax ≤ b est vide ou cTx est non borneesur Ax ≤ b
11
max cTx
t.q. Ax ≤ bn’a pas de solution si et seulement si
Ax ≤ b est vide ou cTx est non borneesur Ax ≤ b
11
max cTx
t.q. Ax ≤ bn’a pas de solution si et seulement si
Ax ≤ b est vide ou
Dans les autres cas, le probleme est fini : enumerer les sommets du polyhedre
cTx est non borneesur Ax ≤ b
11
max cTx
t.q. Ax ≤ bn’a pas de solution si et seulement si
Ax ≤ b est vide ou
Intersections borneesd’un nombre fini de
demi-espaces(H-representation)
Enveloppes convexesd’ensembles finis de
points(V -representation)
=
=
polytopes convexes
Dans les autres cas, le probleme est fini : enumerer les sommets du polyhedre
cTx est non borneesur Ax ≤ b
11
max cTx
t.q. Ax ≤ bn’a pas de solution si et seulement si
Ax ≤ b est vide ou
Intersections borneesd’un nombre fini de
demi-espaces(H-representation)
Enveloppes convexesd’ensembles finis de
points(V -representation)
=
=
polytopes convexes
Upper bound theorem : un polytope a n sommets
dans Rd a au plus(n−b d+1
2c
b d2c
)+(n−b d+2
2c
b d−12c
)facettes.
Dans les autres cas, le probleme est fini : enumerer les sommets du polyhedre
cTx est non borneesur Ax ≤ b
11
max cTx
t.q. Ax ≤ bn’a pas de solution si et seulement si
Ax ≤ b est vide ou
Intersections borneesd’un nombre fini de
demi-espaces(H-representation)
Enveloppes convexesd’ensembles finis de
points(V -representation)
=
=
polytopes convexes 1
Upper bound theorem : un polytope a n sommets
dans Rd a au plus(n−b d+1
2c
b d2c
)+(n−b d+2
2c
b d−12c
)facettes.
Si P est un polytope contenant l’origine,
P ? = {y ∈ Rd : ∀x ∈ P y · x ≤ 1} est son polaire.
Dans les autres cas, le probleme est fini : enumerer les sommets du polyhedre
cTx est non borneesur Ax ≤ b
11
max cTx
t.q. Ax ≤ bn’a pas de solution si et seulement si
Ax ≤ b est vide ou
Intersections borneesd’un nombre fini de
demi-espaces(H-representation)
Enveloppes convexesd’ensembles finis de
points(V -representation)
=
=
polytopes convexes 1
Upper bound theorem : un polytope a n sommets
dans Rd a au plus(n−b d+1
2c
b d2c
)+(n−b d+2
2c
b d−12c
)facettes.
Si P est un polytope contenant l’origine,
P ? = {y ∈ Rd : ∀x ∈ P y · x ≤ 1} est son polaire.
Dans les autres cas, le probleme est fini : enumerer les sommets du polyhedre
cTx est non borneesur Ax ≤ b
11
max cTx
t.q. Ax ≤ bn’a pas de solution si et seulement si
Ax ≤ b est vide ou
Intersections borneesd’un nombre fini de
demi-espaces(H-representation)
Enveloppes convexesd’ensembles finis de
points(V -representation)
=
=
polytopes convexes 1
Upper bound theorem : un polytope a n sommets
dans Rd a au plus(n−b d+1
2c
b d2c
)+(n−b d+2
2c
b d−12c
)facettes.
Si P est un polytope contenant l’origine,
P ? = {y ∈ Rd : ∀x ∈ P y · x ≤ 1} est son polaire.
Dans les autres cas, le probleme est fini : enumerer les sommets du polyhedre
cTx est non borneesur Ax ≤ b
Bijection entre
les faces de P de dimension k, et
les faces de P ? de dimension d− 1− k
12
Si on sait...
12
Si on sait...
trouver un premier sommet,
12
Si on sait...
trouver un premier sommet,
etant donne un sommet, construire ses voisins,
12
marcher en optimisant localement conduit a l’optimum global.
Si on sait...
trouver un premier sommet,
etant donne un sommet, construire ses voisins,
12
La methode du simplexe marche ainsi, mais manipule les sommets symboliquement.
marcher en optimisant localement conduit a l’optimum global.
Si on sait...
trouver un premier sommet,
etant donne un sommet, construire ses voisins,
12
La methode du simplexe marche ainsi, mais manipule les sommets symboliquement.
marcher en optimisant localement conduit a l’optimum global.
Si on sait...
trouver un premier sommet,
etant donne un sommet, construire ses voisins,
12
La methode du simplexe marche ainsi, mais manipule les sommets symboliquement.
marcher en optimisant localement conduit a l’optimum global.
Si on sait...
trouver un premier sommet,
etant donne un sommet, construire ses voisins,
sommet ' d contraintes saturees
12
La methode du simplexe marche ainsi, mais manipule les sommets symboliquement.
marcher en optimisant localement conduit a l’optimum global.
Si on sait...
trouver un premier sommet,
etant donne un sommet, construire ses voisins,
sommet ' d contraintes saturees
relaxer une contrainte
donne un degre de liberte
' une arete incidente au sommet.
12
La methode du simplexe marche ainsi, mais manipule les sommets symboliquement.
marcher en optimisant localement conduit a l’optimum global.
Si on sait...
trouver un premier sommet,
etant donne un sommet, construire ses voisins,
sommet ' d contraintes saturees
relaxer une contrainte
donne un degre de liberte
' une arete incidente au sommet.
on trouve le voisin quand
une premiere nouvelle contrainte sature.
Quand on s’eloigne sur cette arete,
13
Methode du simplexe
Presentation algebrique
14
Ax=b
(A : n lignes et d colonnes)
Tout PL peut s’ecrire sous forme equationnelle :
(P)max cTx
t.q. Ax = bx ≥ 0
14
Ax=b
Idee : introduire des variables d’ecart.
3x1 − x2 ≤ 2 →{
3x1 − x2 + e = 2e ≥ 0
(A : n lignes et d colonnes)
Tout PL peut s’ecrire sous forme equationnelle :
(P)max cTx
t.q. Ax = bx ≥ 0
14
Ax=b
Idee : introduire des variables d’ecart.
3x1 − x2 ≤ 2 →{
3x1 − x2 + e = 2e ≥ 0
(A : n lignes et d colonnes)
Tout PL peut s’ecrire sous forme equationnelle :
(P)max cTx
t.q. Ax = bx ≥ 0
max x1 + x2
t.q. x1 ≥ 0
2x2 − x1 ≤ 2
x2 − 2x1 ≥ −4x1 + x2 ≥ 0
max x1 + x2
t.q. x1 ≥ 0
14
Ax=b
Idee : introduire des variables d’ecart.
3x1 − x2 ≤ 2 →{
3x1 − x2 + e = 2e ≥ 0
(A : n lignes et d colonnes)
Tout PL peut s’ecrire sous forme equationnelle :
(P)max cTx
t.q. Ax = bx ≥ 0
max x1 + x2
t.q. x1 ≥ 0
2x2 − x1 ≤ 2
x2 − 2x1 ≥ −4x1 + x2 ≥ 0
max x1 + x2
t.q. x1 ≥ 0
2x2 − x1 − e1 = 2
14
Ax=b
Idee : introduire des variables d’ecart.
3x1 − x2 ≤ 2 →{
3x1 − x2 + e = 2e ≥ 0
(A : n lignes et d colonnes)
Tout PL peut s’ecrire sous forme equationnelle :
(P)max cTx
t.q. Ax = bx ≥ 0
max x1 + x2
t.q. x1 ≥ 0
2x2 − x1 ≤ 2
x2 − 2x1 ≥ −4x1 + x2 ≥ 0
max x1 + x2
t.q. x1 ≥ 0
2x2 − x1 − e1 = 2
x1 + x2 + e2 = 0
14
Ax=b
Idee : introduire des variables d’ecart.
3x1 − x2 ≤ 2 →{
3x1 − x2 + e = 2e ≥ 0
(A : n lignes et d colonnes)
Tout PL peut s’ecrire sous forme equationnelle :
(P)max cTx
t.q. Ax = bx ≥ 0
max x1 + x2
t.q. x1 ≥ 0
2x2 − x1 ≤ 2
x2 − 2x1 ≥ −4x1 + x2 ≥ 0
max x1 + x2
t.q. x1 ≥ 0
2x2 − x1 − e1 = 2
x2 − 2x1 + e3 = −4x1 + x2 + e2 = 0
14
Ax=b
Idee : introduire des variables d’ecart.
3x1 − x2 ≤ 2 →{
3x1 − x2 + e = 2e ≥ 0
(A : n lignes et d colonnes)
Tout PL peut s’ecrire sous forme equationnelle :
(P)max cTx
t.q. Ax = bx ≥ 0
max x1 + x2
t.q. x1 ≥ 0
2x2 − x1 ≤ 2
x2 − 2x1 ≥ −4x1 + x2 ≥ 0
max x1 + x2
t.q. x1 ≥ 0
2x2 − x1 − e1 = 2
x2 − 2x1 + e3 = −4x1 + x2 + e2 = 0
e1, e2, e3 ≥ 0
14
Ax=b
Idee : introduire des variables d’ecart.
3x1 − x2 ≤ 2 →{
3x1 − x2 + e = 2e ≥ 0
On suppose les lignes de A lineairement independantes.
(A : n lignes et d colonnes)
Tout PL peut s’ecrire sous forme equationnelle :
(P)max cTx
t.q. Ax = bx ≥ 0
max x1 + x2
t.q. x1 ≥ 0
2x2 − x1 ≤ 2
x2 − 2x1 ≥ −4x1 + x2 ≥ 0
max x1 + x2
t.q. x1 ≥ 0
2x2 − x1 − e1 = 2
x2 − 2x1 + e3 = −4x1 + x2 + e2 = 0
e1, e2, e3 ≥ 0
15
La methode du simplexe marche sur les bases faisable.A =
−1 1 1 0 01 0 0 1 00 1 0 0 1
b =
132
c =
11000
Les sommets de Ax = b, x ≥ 0 sont les solutions faisables de support minimal.
max cTx
t.q. Ax = bx ≥ 0
15
La methode du simplexe marche sur les bases faisable.A =
−1 1 1 0 01 0 0 1 00 1 0 0 1
b =
132
c =
11000
Les sommets de Ax = b, x ≥ 0 sont les solutions faisables de support minimal.
max cTx
t.q. Ax = bx ≥ 0
Theoreme (Caratheodory). Toute combinaison positive d’un ensemble Ade vecteurs est combinaison positive d’au plus rkA de ces vecteurs.
15
La methode du simplexe marche sur les bases faisable.A =
−1 1 1 0 01 0 0 1 00 1 0 0 1
b =
132
c =
11000
Les sommets de Ax = b, x ≥ 0 sont les solutions faisables de support minimal.
max cTx
t.q. Ax = bx ≥ 0
Theoreme (Caratheodory). Toute combinaison positive d’un ensemble Ade vecteurs est combinaison positive d’au plus rkA de ces vecteurs.
Preuve. Soit b = Ax avec x ≥ 0 une combinaison positive.
Restreignons A au support de x et supposons ce support de taille > rk(A).
15
La methode du simplexe marche sur les bases faisable.A =
−1 1 1 0 01 0 0 1 00 1 0 0 1
b =
132
c =
11000
Les sommets de Ax = b, x ≥ 0 sont les solutions faisables de support minimal.
max cTx
t.q. Ax = bx ≥ 0
Theoreme (Caratheodory). Toute combinaison positive d’un ensemble Ade vecteurs est combinaison positive d’au plus rkA de ces vecteurs.
Preuve. Soit b = Ax avec x ≥ 0 une combinaison positive.
Restreignons A au support de x et supposons ce support de taille > rk(A).
Le support de x+ tz est contenu dans le support de x.
Alors il existe z ∈ kerA non trivial et b = A(x+ tz) pour tout t ∈ R.
15
La methode du simplexe marche sur les bases faisable.A =
−1 1 1 0 01 0 0 1 00 1 0 0 1
b =
132
c =
11000
Les sommets de Ax = b, x ≥ 0 sont les solutions faisables de support minimal.
max cTx
t.q. Ax = bx ≥ 0
Theoreme (Caratheodory). Toute combinaison positive d’un ensemble Ade vecteurs est combinaison positive d’au plus rkA de ces vecteurs.
Preuve. Soit b = Ax avec x ≥ 0 une combinaison positive.
Restreignons A au support de x et supposons ce support de taille > rk(A).
Le support de x+ tz est contenu dans le support de x.
Faire varier t permet de reduire le support.
Alors il existe z ∈ kerA non trivial et b = A(x+ tz) pour tout t ∈ R.
15
La methode du simplexe marche sur les bases faisable.A =
−1 1 1 0 01 0 0 1 00 1 0 0 1
b =
132
c =
11000
Les sommets de Ax = b, x ≥ 0 sont les solutions faisables de support minimal.
max cTx
t.q. Ax = bx ≥ 0
Theoreme (Caratheodory). Toute combinaison positive d’un ensemble Ade vecteurs est combinaison positive d’au plus rkA de ces vecteurs.
Preuve. Soit b = Ax avec x ≥ 0 une combinaison positive.
Restreignons A au support de x et supposons ce support de taille > rk(A).
Le support de x+ tz est contenu dans le support de x.
Faire varier t permet de reduire le support.
Alors il existe z ∈ kerA non trivial et b = A(x+ tz) pour tout t ∈ R.
15
La methode du simplexe marche sur les bases faisable.A =
−1 1 1 0 01 0 0 1 00 1 0 0 1
b =
132
c =
11000
Les sommets de Ax = b, x ≥ 0 sont les solutions faisables de support minimal.
max cTx
t.q. Ax = bx ≥ 0
Theoreme (Caratheodory). Toute combinaison positive d’un ensemble Ade vecteurs est combinaison positive d’au plus rkA de ces vecteurs.
Preuve. Soit b = Ax avec x ≥ 0 une combinaison positive.
Restreignons A au support de x et supposons ce support de taille > rk(A).
Le support de x+ tz est contenu dans le support de x.
Faire varier t permet de reduire le support.
Alors il existe z ∈ kerA non trivial et b = A(x+ tz) pour tout t ∈ R.
15
La methode du simplexe marche sur les bases faisable.A =
−1 1 1 0 01 0 0 1 00 1 0 0 1
b =
132
c =
11000
Les sommets de Ax = b, x ≥ 0 sont les solutions faisables de support minimal.
max cTx
t.q. Ax = bx ≥ 0
Theoreme (Caratheodory). Toute combinaison positive d’un ensemble Ade vecteurs est combinaison positive d’au plus rkA de ces vecteurs.
Preuve. Soit b = Ax avec x ≥ 0 une combinaison positive.
Restreignons A au support de x et supposons ce support de taille > rk(A).
Le support de x+ tz est contenu dans le support de x.
Faire varier t permet de reduire le support.
Alors il existe z ∈ kerA non trivial et b = A(x+ tz) pour tout t ∈ R.
15
La methode du simplexe marche sur les bases faisable.A =
−1 1 1 0 01 0 0 1 00 1 0 0 1
b =
132
c =
11000
Les sommets de Ax = b, x ≥ 0 sont les solutions faisables de support minimal.
La methode du simplexe utilise les supports pour representer les sommets et marcher.
max cTx
t.q. Ax = bx ≥ 0
Theoreme (Caratheodory). Toute combinaison positive d’un ensemble Ade vecteurs est combinaison positive d’au plus rkA de ces vecteurs.
Preuve. Soit b = Ax avec x ≥ 0 une combinaison positive.
Restreignons A au support de x et supposons ce support de taille > rk(A).
Le support de x+ tz est contenu dans le support de x.
Faire varier t permet de reduire le support.
Alors il existe z ∈ kerA non trivial et b = A(x+ tz) pour tout t ∈ R.
15
La methode du simplexe marche sur les bases faisable.
Regardons cela sur un exemple...
A =
−1 1 1 0 01 0 0 1 00 1 0 0 1
b =
132
c =
11000
Les sommets de Ax = b, x ≥ 0 sont les solutions faisables de support minimal.
La methode du simplexe utilise les supports pour representer les sommets et marcher.
max x1 + x2
x1 ≤ 3
x1, x2 ≥ 0x2 ≤ 2
t.q. −x1 + x2 ≤ 1
max cTx
t.q. Ax = bx ≥ 0
Theoreme (Caratheodory). Toute combinaison positive d’un ensemble Ade vecteurs est combinaison positive d’au plus rkA de ces vecteurs.
Preuve. Soit b = Ax avec x ≥ 0 une combinaison positive.
Restreignons A au support de x et supposons ce support de taille > rk(A).
Le support de x+ tz est contenu dans le support de x.
Faire varier t permet de reduire le support.
Alors il existe z ∈ kerA non trivial et b = A(x+ tz) pour tout t ∈ R.
15
La methode du simplexe marche sur les bases faisable.
Regardons cela sur un exemple...
A =
−1 1 1 0 01 0 0 1 00 1 0 0 1
b =
132
c =
11000
Les sommets de Ax = b, x ≥ 0 sont les solutions faisables de support minimal.
La methode du simplexe utilise les supports pour representer les sommets et marcher.
max x1 + x2
x1 ≤ 3
x1, x2 ≥ 0x2 ≤ 2
t.q. −x1 + x2 ≤ 1max x1 + x2
x1 + x4 = 3
x1, . . . , x5 ≥ 0x2 + x5 = 2
t.q. −x1 + x2 + x3 = 1
max cTx
t.q. Ax = bx ≥ 0
Theoreme (Caratheodory). Toute combinaison positive d’un ensemble Ade vecteurs est combinaison positive d’au plus rkA de ces vecteurs.
Preuve. Soit b = Ax avec x ≥ 0 une combinaison positive.
Restreignons A au support de x et supposons ce support de taille > rk(A).
Le support de x+ tz est contenu dans le support de x.
Faire varier t permet de reduire le support.
Alors il existe z ∈ kerA non trivial et b = A(x+ tz) pour tout t ∈ R.
16
On part d’une solution faisable de support minimal, e.g.
00132
max x1 + x2
x1 + x4 = 3
x1, . . . , x5 ≥ 0x2 + x5 = 2
t.q. −x1 + x2 + x3 = 1
16
On part d’une solution faisable de support minimal, e.g.
00132
On exprime objectif et variables du supporten les variables hors-support.
x3 = 1 + x1 − x2
x4 = 3− x1
x5 = 2− x2
obj = x1 + x2
max x1 + x2
x1 + x4 = 3
x1, . . . , x5 ≥ 0x2 + x5 = 2
t.q. −x1 + x2 + x3 = 1
00132
16
On part d’une solution faisable de support minimal, e.g.
00132
On exprime objectif et variables du supporten les variables hors-support.
x3 = 1 + x1 − x2
x4 = 3− x1
x5 = 2− x2
obj = x1 + x2
Augmenter x1 ou x2 ameliore l’objectif et reste faisable !
max x1 + x2
x1 + x4 = 3
x1, . . . , x5 ≥ 0x2 + x5 = 2
t.q. −x1 + x2 + x3 = 1
00132
16
On part d’une solution faisable de support minimal, e.g.
00132
On exprime objectif et variables du supporten les variables hors-support.
x3 = 1 + x1 − x2
x4 = 3− x1
x5 = 2− x2
obj = x1 + x2
x2 = 1 + x1 − x3
x4 = 3− x1
x5 = 1− x1 + x3
obj = 1 + 2x1 − x3
On augmente (au choix) x2 jusqu’a unesolution faisable de support minimal.
x3 s’annule. pour x2 = 1.
Augmenter x1 ou x2 ameliore l’objectif et reste faisable !
max x1 + x2
x1 + x4 = 3
x1, . . . , x5 ≥ 0x2 + x5 = 2
t.q. −x1 + x2 + x3 = 1
00132
01031
16
On part d’une solution faisable de support minimal, e.g.
00132
On exprime objectif et variables du supporten les variables hors-support.
x3 = 1 + x1 − x2
x4 = 3− x1
x5 = 2− x2
obj = x1 + x2
x2 = 1 + x1 − x3
x4 = 3− x1
x5 = 1− x1 + x3
obj = 1 + 2x1 − x3
On augmente (au choix) x2 jusqu’a unesolution faisable de support minimal.
x3 s’annule. pour x2 = 1.
x2 = 2− x5
x4 = 2 + x5 − x3
x1 = 1− x5 + x3
obj = 3− 2x5 + x3
On peut encore augmenter x1...
Augmenter x1 ou x2 ameliore l’objectif et reste faisable !
max x1 + x2
x1 + x4 = 3
x1, . . . , x5 ≥ 0x2 + x5 = 2
t.q. −x1 + x2 + x3 = 1
00132
01031
12020
16
On part d’une solution faisable de support minimal, e.g.
00132
On exprime objectif et variables du supporten les variables hors-support.
x3 = 1 + x1 − x2
x4 = 3− x1
x5 = 2− x2
obj = x1 + x2
x2 = 1 + x1 − x3
x4 = 3− x1
x5 = 1− x1 + x3
obj = 1 + 2x1 − x3
On augmente (au choix) x2 jusqu’a unesolution faisable de support minimal.
x3 s’annule. pour x2 = 1.
x2 = 2− x5
x4 = 2 + x5 − x3
x1 = 1− x5 + x3
obj = 3− 2x5 + x3
On peut encore augmenter x1...
puis x3...x2 = 2− x5
x3 = 2 + x5 − x4
x1 = 3− x4
obj = 5− x5 − x4
Augmenter x1 ou x2 ameliore l’objectif et reste faisable !
max x1 + x2
x1 + x4 = 3
x1, . . . , x5 ≥ 0x2 + x5 = 2
t.q. −x1 + x2 + x3 = 1
00132
01031
12020
32200
16
On part d’une solution faisable de support minimal, e.g.
00132
On exprime objectif et variables du supporten les variables hors-support.
x3 = 1 + x1 − x2
x4 = 3− x1
x5 = 2− x2
obj = x1 + x2
x2 = 1 + x1 − x3
x4 = 3− x1
x5 = 1− x1 + x3
obj = 1 + 2x1 − x3
On augmente (au choix) x2 jusqu’a unesolution faisable de support minimal.
x3 s’annule. pour x2 = 1.
x2 = 2− x5
x4 = 2 + x5 − x3
x1 = 1− x5 + x3
obj = 3− 2x5 + x3
On peut encore augmenter x1...
puis x3...
pour arriver a l’optimum
32200
.
x2 = 2− x5
x3 = 2 + x5 − x4
x1 = 3− x4
obj = 5− x5 − x4
Augmenter x1 ou x2 ameliore l’objectif et reste faisable !
max x1 + x2
x1 + x4 = 3
x1, . . . , x5 ≥ 0x2 + x5 = 2
t.q. −x1 + x2 + x3 = 1
00132
01031
12020
32200
17
En general :
Il faut se donner une regle de pivot en cas de choix multiples.
Meme principe, solutions representees par leur support.
base = support d’une solution de support minimal
17
En detail...
En general :
Il faut se donner une regle de pivot en cas de choix multiples.
Meme principe, solutions representees par leur support.
base = support d’une solution de support minimal
Construire une solution faisable initiale.
Resoudre un LP... de solution initiale triviale.
17
En detail...
En general :
Il faut se donner une regle de pivot en cas de choix multiples.
Meme principe, solutions representees par leur support.
base = support d’une solution de support minimal
Construire une solution faisable initiale.
Resoudre un LP... de solution initiale triviale.
Detecter que cTx n’est pas borne sur Ax = b, x ≥ 0.
Lors d’un pivot, aucune variable ne s’annule.
17
En detail...
En general :
Il faut se donner une regle de pivot en cas de choix multiples.
Meme principe, solutions representees par leur support.
base = support d’une solution de support minimal
Construire une solution faisable initiale.
Resoudre un LP... de solution initiale triviale.
Detecter que cTx n’est pas borne sur Ax = b, x ≥ 0.
Lors d’un pivot, aucune variable ne s’annule.
Gerer les degenerescences sans cycler.
Des pivots n’augmentant pas l’objectif peuvent etre necessaires.
18
Largest coefficient
Steepest edge : suivre l’arete la mieux alignee avec c.
La regle de pivot determine, la variable choisie pour augmenter l’objectif.
Largest increase
Bland’s rule : privilegie la variable d’indice minimum.
...
Devex : heuristique approximant Steepest edge.
Shadow vertex
18
Largest coefficient
Steepest edge : suivre l’arete la mieux alignee avec c.
La regle de pivot determine, la variable choisie pour augmenter l’objectif.
Largest increase
Bland’s rule : privilegie la variable d’indice minimum.
...
Devex : heuristique approximant Steepest edge.
Shadow vertex
Ne cycle pasnaturellement
tres efficaceen pratique
18
Largest coefficient
Steepest edge : suivre l’arete la mieux alignee avec c.
La regle de pivot determine, la variable choisie pour augmenter l’objectif.
Largest increase
Bland’s rule : privilegie la variable d’indice minimum.
...
Devex : heuristique approximant Steepest edge.
Shadow vertex
Ne cycle pasnaturellement
tres efficaceen pratique
Exemples exponentiels, diametre d’un polytope, complexite lissee, . . .
18
Largest coefficient
Steepest edge : suivre l’arete la mieux alignee avec c.
La regle de pivot determine, la variable choisie pour augmenter l’objectif.
Largest increase
Bland’s rule : privilegie la variable d’indice minimum.
Random Edge : choisir aleatoirement uniformement... ou pas.
...
Devex : heuristique approximant Steepest edge.
Shadow vertex
Ne cycle pasnaturellement
tres efficaceen pratique
Exemples exponentiels, diametre d’un polytope, complexite lissee, . . .
19
Programmation mixte et entiere
20
Un programme mixte est un PL dans lequel certaines variables sont contraintes a prendredes valeurs entieres.
max cTx
t.q. Ax ≤ b
x ∈ Zk × Rd−k
Modelise des ressourcesnon fractionnables.
20
Un programme mixte est un PL dans lequel certaines variables sont contraintes a prendredes valeurs entieres.
max cTx
t.q. Ax ≤ b
x ∈ Zk × Rd−k
Modelise des ressourcesnon fractionnables.
20
Un programme mixte est un PL dans lequel certaines variables sont contraintes a prendredes valeurs entieres.
Toutes les variables dans Z (k = d) : programmation entiere.
max cTx
t.q. Ax ≤ b
x ∈ Zk × Rd−k
Modelise des ressourcesnon fractionnables.
20
Un programme mixte est un PL dans lequel certaines variables sont contraintes a prendredes valeurs entieres.
Toutes les variables dans Z (k = d) : programmation entiere.
max cTx
t.q. Ax ≤ b
x ∈ Zk × Rd−k
Modelise des ressourcesnon fractionnables.
Resoudre un programme mixte general est theoriquement difficile.
Decider la faisabilite est NP-difficile deja avec toutes les variables dans {0, 1}.
Des methodes pratiques peuvent marcher, meme si des instances inabordables existent(http://miplib.zib.de/miplib2010.php)
Cutting planes, branch-and-bound, . . .
21
Si on ignore les contraintes d’integralite,
Relaxation...
- le probleme devient facile a resoudre (c’est un PL),
- la solution au PL borne inferieurement la solution du programme mixte/entier,
21
Si on ignore les contraintes d’integralite,
Relaxation...
- le probleme devient facile a resoudre (c’est un PL),
- la solution au PL borne inferieurement la solution du programme mixte/entier,
21
On va regarder 3 exemples issus de problemes d’optimisation sur des graphes.
Si on ignore les contraintes d’integralite,
et on peut parfois borner superieurement l’ecart entre les deux solutions !
Relaxation...
- le probleme devient facile a resoudre (c’est un PL),
- la solution au PL borne inferieurement la solution du programme mixte/entier,
22
4
5
9
4
5
9
6 3
78
1
2
236
Couplage parfait de poids maximum (maximum weight matching).
22
4
5
9
4
5
9
6 3
78
1
2
236
Couplage parfait de poids maximum (maximum weight matching).
arete entre i et j
variable xi,j , poids pi,j(xi,j = xj,i)
22
4
5
9
4
5
9
6 3
78
1
2
236
Couplage parfait de poids maximum (maximum weight matching).
max∑
i,j pi,jxi,j
t.q. xi,j ∈ Z0 ≤ xi,j ≤ 1
∀i,∑
j xi,j = 1
arete entre i et j
variable xi,j , poids pi,j(xi,j = xj,i)
22
4
5
9
4
5
9
6 3
78
1
2
236
Couplage parfait de poids maximum (maximum weight matching).
(R)
max∑
i,j pi,jxi,j
t.q. xi,j ∈ Z0 ≤ xi,j ≤ 1
∀i,∑
j xi,j = 1
arete entre i et j
variable xi,j , poids pi,j(xi,j = xj,i)
22
4
5
9
4
5
9
6 3
78
1
2
236
Couplage parfait de poids maximum (maximum weight matching).
Theoreme. Si le graphe est biparti et le PL (R) est faisable, ila au moins une solution optimale ou tous les xi,j sont entiers.
(R)
max∑
i,j pi,jxi,j
t.q. xi,j ∈ Z0 ≤ xi,j ≤ 1
∀i,∑
j xi,j = 1
arete entre i et j
variable xi,j , poids pi,j(xi,j = xj,i)
22
4
5
9
4
5
9
6 3
78
1
2
236
Couplage parfait de poids maximum (maximum weight matching).
Preuve : On part d’une solution x∗ au PL.
Supposons que x∗i,j n’est pas entier.
Theoreme. Si le graphe est biparti et le PL (R) est faisable, ila au moins une solution optimale ou tous les xi,j sont entiers.
(R)
max∑
i,j pi,jxi,j
t.q. xi,j ∈ Z0 ≤ xi,j ≤ 1
∀i,∑
j xi,j = 1
arete entre i et j
variable xi,j , poids pi,j(xi,j = xj,i)
22
4
5
9
4
5
9
6 3
78
1
2
236
Couplage parfait de poids maximum (maximum weight matching).
Preuve : On part d’une solution x∗ au PL.
Supposons que x∗i,j n’est pas entier.
Theoreme. Si le graphe est biparti et le PL (R) est faisable, ila au moins une solution optimale ou tous les xi,j sont entiers.
(R)
max∑
i,j pi,jxi,j
t.q. xi,j ∈ Z0 ≤ xi,j ≤ 1
∀i,∑
j xi,j = 1
Il existe x∗j,k qui est aussi non-entier. (Car∑
i x∗i,j = 1.)
arete entre i et j
variable xi,j , poids pi,j(xi,j = xj,i)
22
4
5
9
4
5
9
6 3
78
1
2
236
Couplage parfait de poids maximum (maximum weight matching).
Preuve : On part d’une solution x∗ au PL.
Supposons que x∗i,j n’est pas entier.
Theoreme. Si le graphe est biparti et le PL (R) est faisable, ila au moins une solution optimale ou tous les xi,j sont entiers.
(R)
max∑
i,j pi,jxi,j
t.q. xi,j ∈ Z0 ≤ xi,j ≤ 1
∀i,∑
j xi,j = 1
Il existe x∗j,k qui est aussi non-entier. (Car∑
i x∗i,j = 1.)
arete entre i et j
variable xi,j , poids pi,j(xi,j = xj,i)
22
4
5
9
4
5
9
6 3
78
1
2
236
Couplage parfait de poids maximum (maximum weight matching).
Preuve : On part d’une solution x∗ au PL.
Supposons que x∗i,j n’est pas entier.
Theoreme. Si le graphe est biparti et le PL (R) est faisable, ila au moins une solution optimale ou tous les xi,j sont entiers.
(R)
max∑
i,j pi,jxi,j
t.q. xi,j ∈ Z0 ≤ xi,j ≤ 1
∀i,∑
j xi,j = 1
Il existe x∗j,k qui est aussi non-entier. (Car∑
i x∗i,j = 1.)
arete entre i et j
variable xi,j , poids pi,j(xi,j = xj,i)
22
4
5
9
4
5
9
6 3
78
1
2
236
Couplage parfait de poids maximum (maximum weight matching).
Preuve : On part d’une solution x∗ au PL.
Supposons que x∗i,j n’est pas entier.
Theoreme. Si le graphe est biparti et le PL (R) est faisable, ila au moins une solution optimale ou tous les xi,j sont entiers.
(R)
max∑
i,j pi,jxi,j
t.q. xi,j ∈ Z0 ≤ xi,j ≤ 1
∀i,∑
j xi,j = 1
Il existe x∗j,k qui est aussi non-entier. (Car∑
i x∗i,j = 1.)
arete entre i et j
variable xi,j , poids pi,j(xi,j = xj,i)
22
4
5
9
4
5
9
6 3
78
1
2
236
Couplage parfait de poids maximum (maximum weight matching).
Preuve : On part d’une solution x∗ au PL.
Supposons que x∗i,j n’est pas entier.
et on peut former ainsi... un cycle... de longueur paire.
Theoreme. Si le graphe est biparti et le PL (R) est faisable, ila au moins une solution optimale ou tous les xi,j sont entiers.
(R)
max∑
i,j pi,jxi,j
t.q. xi,j ∈ Z0 ≤ xi,j ≤ 1
∀i,∑
j xi,j = 1
Il existe x∗j,k qui est aussi non-entier. (Car∑
i x∗i,j = 1.)
arete entre i et j
variable xi,j , poids pi,j(xi,j = xj,i)
22
4
5
9
4
5
9
6 3
78
1
2
236
Couplage parfait de poids maximum (maximum weight matching).
Preuve : On part d’une solution x∗ au PL.
Supposons que x∗i,j n’est pas entier.
et on peut former ainsi... un cycle... de longueur paire.
Theoreme. Si le graphe est biparti et le PL (R) est faisable, ila au moins une solution optimale ou tous les xi,j sont entiers.
(R)
max∑
i,j pi,jxi,j
t.q. xi,j ∈ Z0 ≤ xi,j ≤ 1
∀i,∑
j xi,j = 1
+t
+t
+t+t
−t −
t
−t−t
On decale de ±t les x∗i,j du cycle
Il existe x∗j,k qui est aussi non-entier. (Car∑
i x∗i,j = 1.)
arete entre i et j
variable xi,j , poids pi,j(xi,j = xj,i)
22
4
5
9
4
5
9
6 3
78
1
2
236
Couplage parfait de poids maximum (maximum weight matching).
Preuve : On part d’une solution x∗ au PL.
Supposons que x∗i,j n’est pas entier.
et on peut former ainsi... un cycle... de longueur paire.
Theoreme. Si le graphe est biparti et le PL (R) est faisable, ila au moins une solution optimale ou tous les xi,j sont entiers.
(R)
max∑
i,j pi,jxi,j
t.q. xi,j ∈ Z0 ≤ xi,j ≤ 1
∀i,∑
j xi,j = 1
+t
+t
+t+t
−t −
t
−t−t
On decale de ±t les x∗i,j du cycle
on fait varier t partant de 0 (↗ ou ↘ selon pi,j)
jusqu’a rendre une variable entiere.
Il existe x∗j,k qui est aussi non-entier. (Car∑
i x∗i,j = 1.)
arete entre i et j
variable xi,j , poids pi,j(xi,j = xj,i)
22
4
5
9
4
5
9
6 3
78
1
2
236
Couplage parfait de poids maximum (maximum weight matching).
Preuve : On part d’une solution x∗ au PL.
Supposons que x∗i,j n’est pas entier.
et on peut former ainsi... un cycle... de longueur paire.
Theoreme. Si le graphe est biparti et le PL (R) est faisable, ila au moins une solution optimale ou tous les xi,j sont entiers.
(R)
max∑
i,j pi,jxi,j
t.q. xi,j ∈ Z0 ≤ xi,j ≤ 1
∀i,∑
j xi,j = 1
+t
+t
+t+t
−t −
t
−t−t
On decale de ±t les x∗i,j du cycle
on fait varier t partant de 0 (↗ ou ↘ selon pi,j)
jusqu’a rendre une variable entiere.
et on recommence.
Il existe x∗j,k qui est aussi non-entier. (Car∑
i x∗i,j = 1.)
arete entre i et j
variable xi,j , poids pi,j(xi,j = xj,i)
23
Couverture par sommets minimale (minimum vertex cover).
23
Couverture par sommets minimale (minimum vertex cover).
min∑
i xi
t.q. xi ∈ Z0 ≤ xi ≤ 1
∀ arete ij, xi + xj ≥ 1
sommet i
variable xi
23
Couverture par sommets minimale (minimum vertex cover).
min∑
i xi
t.q. xi ∈ Z0 ≤ xi ≤ 1
∀ arete ij, xi + xj ≥ 1
sommet i
variable xi
Decider si le MVC comporte au moins k sommets est NP-difficile.
23
Couverture par sommets minimale (minimum vertex cover).
min∑
i xi
t.q. xi ∈ Z0 ≤ xi ≤ 1
∀ arete ij, xi + xj ≥ 1
sommet i
variable xi
Decider si le MVC comporte au moins k sommets est NP-difficile.
Mais on peut calculer une solution faisable pas trop mauvaise en
calculant une solution x∗ au PL obtenu par relaxation,
arrondissant x∗ en x par xi = 1 si x∗i ≥ 1
2 et xi = 0 sinon.
23
Couverture par sommets minimale (minimum vertex cover).
min∑
i xi
t.q. xi ∈ Z0 ≤ xi ≤ 1
∀ arete ij, xi + xj ≥ 1
sommet i
variable xi
Decider si le MVC comporte au moins k sommets est NP-difficile.
Mais on peut calculer une solution faisable pas trop mauvaise en
calculant une solution x∗ au PL obtenu par relaxation,
arrondissant x∗ en x par xi = 1 si x∗i ≥ 1
2 et xi = 0 sinon.
Pour tout graphe, si xopt est l’optimal du programme entier, on a∑i x
∗i ≤
∑i x
opti ≤
∑i xi ≤ 2
∑i x
∗i
23
Couverture par sommets minimale (minimum vertex cover).
min∑
i xi
t.q. xi ∈ Z0 ≤ xi ≤ 1
∀ arete ij, xi + xj ≥ 1
sommet i
variable xi
Decider si le MVC comporte au moins k sommets est NP-difficile.
On peut donc calculer une 2-approximation efficacement.
en particulier∑
i xi ≤ 2∑
i xopti
Mais on peut calculer une solution faisable pas trop mauvaise en
calculant une solution x∗ au PL obtenu par relaxation,
arrondissant x∗ en x par xi = 1 si x∗i ≥ 1
2 et xi = 0 sinon.
Pour tout graphe, si xopt est l’optimal du programme entier, on a∑i x
∗i ≤
∑i x
opti ≤
∑i xi ≤ 2
∑i x
∗i
24
Ensemble independant maximum (maximum independent set).
24
max∑
i xi
t.q. xi ∈ Z0 ≤ xi ≤ 1
∀ arete ij, xi + xj ≤ 1
sommet i
variable xi
Ensemble independant maximum (maximum independent set).
24
max∑
i xi
t.q. xi ∈ Z0 ≤ xi ≤ 1
∀ arete ij, xi + xj ≤ 1
sommet i
variable xi
Decider si le MIS comporte au moins k sommets est NP-difficile.
Ensemble independant maximum (maximum independent set).
24
max∑
i xi
t.q. xi ∈ Z0 ≤ xi ≤ 1
∀ arete ij, xi + xj ≤ 1
sommet i
variable xi
Decider si le MIS comporte au moins k sommets est NP-difficile.
Ensemble independant maximum (maximum independent set).
L’ecart entre la solution de la relaxation est l’optimal est non-borne (Kn).
La relaxation a une solution ou chaque xi =12 .
24
max∑
i xi
t.q. xi ∈ Z0 ≤ xi ≤ 1
∀ arete ij, xi + xj ≤ 1
sommet i
variable xi
Decider si le MIS comporte au moins k sommets est NP-difficile.
Ensemble independant maximum (maximum independent set).
L’ecart entre la solution de la relaxation est l’optimal est non-borne (Kn).
La relaxation a une solution ou chaque xi =12 .
En fait, approximation efficace impossible si P 6= NP .
25
Dualite
26
Essayons de commenter la valeur de...
max 2x1 + 3x2
t.q. 4x1 + 8x2 ≤ 12
2x1 + x2 ≤ 3
3x1 + 2x2 ≤ 4
x1, x2 ≥ 0
26
Essayons de commenter la valeur de...
max 2x1 + 3x2
t.q. 4x1 + 8x2 ≤ 12
2x1 + x2 ≤ 3
3x1 + 2x2 ≤ 4
x1, x2 ≥ 0
x1, x2 ≥ 0 donc 2x1 + 3x2 ≤ 4x1 + 8x2 ≤ 12
26
Essayons de commenter la valeur de...
max 2x1 + 3x2
t.q. 4x1 + 8x2 ≤ 12
2x1 + x2 ≤ 3
3x1 + 2x2 ≤ 4
x1, x2 ≥ 0
x1, x2 ≥ 0 donc 2x1 + 3x2 ≤ 4x1 + 8x2 ≤ 12
mieux... 2x1 + 3x2 ≤ 12(4x1 + 8x2) ≤ 6
26
Essayons de commenter la valeur de...
max 2x1 + 3x2
t.q. 4x1 + 8x2 ≤ 12
2x1 + x2 ≤ 3
3x1 + 2x2 ≤ 4
x1, x2 ≥ 0
x1, x2 ≥ 0 donc 2x1 + 3x2 ≤ 4x1 + 8x2 ≤ 12
mieux... 2x1 + 3x2 ≤ 12(4x1 + 8x2) ≤ 6
encore mieux... 2x1 + 3x2 = 13((4x1 + 8x2) + (2x1 + x2)) ≤ 5
26
Essayons de commenter la valeur de...
max 2x1 + 3x2
t.q. 4x1 + 8x2 ≤ 12
2x1 + x2 ≤ 3
3x1 + 2x2 ≤ 4
x1, x2 ≥ 0
x1, x2 ≥ 0 donc 2x1 + 3x2 ≤ 4x1 + 8x2 ≤ 12
mieux... 2x1 + 3x2 ≤ 12(4x1 + 8x2) ≤ 6
encore mieux... 2x1 + 3x2 = 13((4x1 + 8x2) + (2x1 + x2)) ≤ 5
En multipliant la ieme contrainte par yi on obtient...
max 2x1 + 3x2
t.q. 4x1 + 8x2 ≤ 12
2x1 + x2 ≤ 3
3x1 + 2x2 ≤ 4
x1, x2 ≥ 0
≤min 12y1 + 3y2 + 4y3t.q. 4y1 + 2y2 + 3y3 ≥ 2
8y1 + y2 + 2y3 ≥ 3
y1, y2, y3 ≥ 0
26
Essayons de commenter la valeur de...
max 2x1 + 3x2
t.q. 4x1 + 8x2 ≤ 12
2x1 + x2 ≤ 3
3x1 + 2x2 ≤ 4
x1, x2 ≥ 0
x1, x2 ≥ 0 donc 2x1 + 3x2 ≤ 4x1 + 8x2 ≤ 12
mieux... 2x1 + 3x2 ≤ 12(4x1 + 8x2) ≤ 6
encore mieux... 2x1 + 3x2 = 13((4x1 + 8x2) + (2x1 + x2)) ≤ 5
En multipliant la ieme contrainte par yi on obtient...
max 2x1 + 3x2
t.q. 4x1 + 8x2 ≤ 12
2x1 + x2 ≤ 3
3x1 + 2x2 ≤ 4
x1, x2 ≥ 0
≤min 12y1 + 3y2 + 4y3t.q. 4y1 + 2y2 + 3y3 ≥ 2
8y1 + y2 + 2y3 ≥ 3
y1, y2, y3 ≥ 0
26
Essayons de commenter la valeur de...
max 2x1 + 3x2
t.q. 4x1 + 8x2 ≤ 12
2x1 + x2 ≤ 3
3x1 + 2x2 ≤ 4
x1, x2 ≥ 0
x1, x2 ≥ 0 donc 2x1 + 3x2 ≤ 4x1 + 8x2 ≤ 12
mieux... 2x1 + 3x2 ≤ 12(4x1 + 8x2) ≤ 6
encore mieux... 2x1 + 3x2 = 13((4x1 + 8x2) + (2x1 + x2)) ≤ 5
En multipliant la ieme contrainte par yi on obtient...
max 2x1 + 3x2
t.q. 4x1 + 8x2 ≤ 12
2x1 + x2 ≤ 3
3x1 + 2x2 ≤ 4
x1, x2 ≥ 0
≤min 12y1 + 3y2 + 4y3t.q. 4y1 + 2y2 + 3y3 ≥ 2
8y1 + y2 + 2y3 ≥ 3
y1, y2, y3 ≥ 0
26
Essayons de commenter la valeur de...
max 2x1 + 3x2
t.q. 4x1 + 8x2 ≤ 12
2x1 + x2 ≤ 3
3x1 + 2x2 ≤ 4
x1, x2 ≥ 0
x1, x2 ≥ 0 donc 2x1 + 3x2 ≤ 4x1 + 8x2 ≤ 12
mieux... 2x1 + 3x2 ≤ 12(4x1 + 8x2) ≤ 6
encore mieux... 2x1 + 3x2 = 13((4x1 + 8x2) + (2x1 + x2)) ≤ 5
En multipliant la ieme contrainte par yi on obtient...
max 2x1 + 3x2
t.q. 4x1 + 8x2 ≤ 12
2x1 + x2 ≤ 3
3x1 + 2x2 ≤ 4
x1, x2 ≥ 0
≤min 12y1 + 3y2 + 4y3t.q. 4y1 + 2y2 + 3y3 ≥ 2
8y1 + y2 + 2y3 ≥ 3
y1, y2, y3 ≥ 0
26
Essayons de commenter la valeur de...
max 2x1 + 3x2
t.q. 4x1 + 8x2 ≤ 12
2x1 + x2 ≤ 3
3x1 + 2x2 ≤ 4
x1, x2 ≥ 0
x1, x2 ≥ 0 donc 2x1 + 3x2 ≤ 4x1 + 8x2 ≤ 12
mieux... 2x1 + 3x2 ≤ 12(4x1 + 8x2) ≤ 6
encore mieux... 2x1 + 3x2 = 13((4x1 + 8x2) + (2x1 + x2)) ≤ 5
En multipliant la ieme contrainte par yi on obtient...
max 2x1 + 3x2
t.q. 4x1 + 8x2 ≤ 12
2x1 + x2 ≤ 3
3x1 + 2x2 ≤ 4
x1, x2 ≥ 0
≤min 12y1 + 3y2 + 4y3t.q. 4y1 + 2y2 + 3y3 ≥ 2
8y1 + y2 + 2y3 ≥ 3
y1, y2, y3 ≥ 0
Plus generalement, ≤max cTxt.q. Ax ≤ b
x ≥ 0
min bT y
t.q. AT y ≥ cy ≥ 0
27
max cTxt.q. Ax ≤ b
x ≥ 0
27
associer yi a la iemeligne de A
max cTxt.q. Ax ≤ b
x ≥ 0 y ≥ 0
min bT y
t.q. AT y ≥ c
27
=
associer yi a la iemeligne de A
max cTxt.q. Ax ≤ b
x ≥ 0 y ≥ 0
min bT y
t.q. AT y ≥ c
y ≥ 0
max −bT yt.q. −AT y ≤ −c
27
=
associer xi a la iemeligne de −AT
associer yi a la iemeligne de A
x ≥ 0
min −cTxt.q. −(AT )Tx ≥ −b
max cTxt.q. Ax ≤ b
x ≥ 0 y ≥ 0
min bT y
t.q. AT y ≥ c
y ≥ 0
max −bT yt.q. −AT y ≤ −c
27
==
associer xi a la iemeligne de −AT
associer yi a la iemeligne de A
x ≥ 0
min −cTxt.q. −(AT )Tx ≥ −b
max cTxt.q. Ax ≤ b
x ≥ 0 y ≥ 0
min bT y
t.q. AT y ≥ c
y ≥ 0
max −bT yt.q. −AT y ≤ −c
27
==
associer xi a la iemeligne de −AT
associer yi a la iemeligne de A
primal
x ≥ 0
min −cTxt.q. −(AT )Tx ≥ −b
max cTxt.q. Ax ≤ b
x ≥ 0 y ≥ 0
min bT y
t.q. AT y ≥ c
y ≥ 0
max −bT yt.q. −AT y ≤ −c
dual
27
PL primal PL dual
variables x1, x2, . . . , xn y1, y2, . . . , ymmatrice A AT
terme de droite b c
fonction max cTx min bT y
contraintes ieme inegalite est ≤ yi ≥ 0ieme inegalite est ≥ yi ≤ 0ieme inegalite est = yi ∈ R
xi ≥ 0 ieme inegalite est ≤. . . . . .
On peut dualiser un PLsous forme quelconque.
==
associer xi a la iemeligne de −AT
associer yi a la iemeligne de A
primal
x ≥ 0
min −cTxt.q. −(AT )Tx ≥ −b
max cTxt.q. Ax ≤ b
x ≥ 0 y ≥ 0
min bT y
t.q. AT y ≥ c
y ≥ 0
max −bT yt.q. −AT y ≤ −c
dual
28
La valeur d’un PL ”maximisant” est toujours majoree par la valeur de son dual.
Theoreme de dualite faible.
28
La valeur d’un PL ”maximisant” est toujours majoree par la valeur de son dual.
Theoreme de dualite faible.
infaisable faisable faisablenon-borne borne
infaisable
faisablenon-borne
faisableborne
primal
dual
28
La valeur d’un PL ”maximisant” est toujours majoree par la valeur de son dual.
Theoreme de dualite faible.
Dualite faibleprimal non-borne ⇒ dual infaisable
infaisable faisable faisablenon-borne borne
infaisable
faisablenon-borne
faisableborne
primal
dual
28
La valeur d’un PL ”maximisant” est toujours majoree par la valeur de son dual.
Theoreme de dualite faible.
Theoreme (dualite forte). Un PL et son dual sontsoit tous deux infaisables,soit l’un infaisable et l’autre faisable non borne,soit tous deux faisables bornes et de meme valeur.
Dualite faibleprimal non-borne ⇒ dual infaisable
A prouver=
infaisable faisable faisablenon-borne borne
infaisable
faisablenon-borne
faisableborne
primal
dual
=
primal faisable borne⇒ dual faisable et de meme valeur
28
La valeur d’un PL ”maximisant” est toujours majoree par la valeur de son dual.
Theoreme de dualite faible.
Preuve classique via lemme de Farkas.
Theoreme (dualite forte). Un PL et son dual sontsoit tous deux infaisables,soit l’un infaisable et l’autre faisable non borne,soit tous deux faisables bornes et de meme valeur.
Dualite faibleprimal non-borne ⇒ dual infaisable
A prouver=
Ax = b a une solution ≥ 0
a1
a3
b
infaisable faisable faisablenon-borne borne
infaisable
faisablenon-borne
faisableborne
primal
dual
=
a2
primal faisable borne⇒ dual faisable et de meme valeur
28
La valeur d’un PL ”maximisant” est toujours majoree par la valeur de son dual.
Theoreme de dualite faible.
Preuve classique via lemme de Farkas.
Theoreme (dualite forte). Un PL et son dual sontsoit tous deux infaisables,soit l’un infaisable et l’autre faisable non borne,soit tous deux faisables bornes et de meme valeur.
Dualite faibleprimal non-borne ⇒ dual infaisable
A prouver=
Ax = b a une solution ≥ 0
∃y tq yTA ≥ 0 et yT b < 0
xor
a1
a3
by
infaisable faisable faisablenon-borne borne
infaisable
faisablenon-borne
faisableborne
primal
dual
=
a2
primal faisable borne⇒ dual faisable et de meme valeur
29
Prop. Si un PL est faisable et borne, alors son dual est faisable et de meme valeur.
Preuve. on part de max cTx t.q. Ax ≤ b, x ≥ 0.
forme equationnelle : max cTx t.q. Ax ≤ b, x ≥ 0.
29
Prop. Si un PL est faisable et borne, alors son dual est faisable et de meme valeur.
Preuve. on part de max cTx t.q. Ax ≤ b, x ≥ 0.
forme equationnelle : max cTx t.q. Ax ≤ b, x ≥ 0.
A =(A Im
)et xT = (x xn+1, xn+2, . . . , xn+m)
variables d’ecart
{
29
Prop. Si un PL est faisable et borne, alors son dual est faisable et de meme valeur.
Preuve. on part de max cTx t.q. Ax ≤ b, x ≥ 0.
on applique l’algorithme du simplexe jusqu’a trouver une solution x∗ de support B
forme equationnelle : max cTx t.q. Ax ≤ b, x ≥ 0.
A =(A Im
)et xT = (x xn+1, xn+2, . . . , xn+m)
variables d’ecart
{
on pose y∗ = (cTBA−1B )T et on montre que c’est une solution faisable du dual,
29
Prop. Si un PL est faisable et borne, alors son dual est faisable et de meme valeur.
Preuve. on part de max cTx t.q. Ax ≤ b, x ≥ 0.
on applique l’algorithme du simplexe jusqu’a trouver une solution x∗ de support B
forme equationnelle : max cTx t.q. Ax ≤ b, x ≥ 0.
A =(A Im
)et xT = (x xn+1, xn+2, . . . , xn+m)
variables d’ecart
{
on pose y∗ = (cTBA−1B )T et on montre que c’est une solution faisable du dual,
revient a ATy∗ ≥ c ou encore A
T(cTBA
−1B )T = A
T(A−1
B )T cB ≥ c
29
Prop. Si un PL est faisable et borne, alors son dual est faisable et de meme valeur.
Preuve. on part de max cTx t.q. Ax ≤ b, x ≥ 0.
on applique l’algorithme du simplexe jusqu’a trouver une solution x∗ de support B
forme equationnelle : max cTx t.q. Ax ≤ b, x ≥ 0.
A =(A Im
)et xT = (x xn+1, xn+2, . . . , xn+m)
variables d’ecart
{
on pose y∗ = (cTBA−1B )T et on montre que c’est une solution faisable du dual,
revient a ATy∗ ≥ c ou encore A
T(cTBA
−1B )T = A
T(A−1
B )T cB ≥ c
Dans le support,(A
T)B(A−1
B )T cB = cB ≥ cB
29
Prop. Si un PL est faisable et borne, alors son dual est faisable et de meme valeur.
Preuve. on part de max cTx t.q. Ax ≤ b, x ≥ 0.
on applique l’algorithme du simplexe jusqu’a trouver une solution x∗ de support B
forme equationnelle : max cTx t.q. Ax ≤ b, x ≥ 0.
A =(A Im
)et xT = (x xn+1, xn+2, . . . , xn+m)
variables d’ecart
{
on pose y∗ = (cTBA−1B )T et on montre que c’est une solution faisable du dual,
revient a ATy∗ ≥ c ou encore A
T(cTBA
−1B )T = A
T(A−1
B )T cB ≥ c
Dans le support,(A
T)B(A−1
B )T cB = cB ≥ cB
Hors-support,(A
T(A−1
B )T cB)H
= cH − r ou r est le vecteur des gains, donc ≤ 0.
29
Prop. Si un PL est faisable et borne, alors son dual est faisable et de meme valeur.
Preuve. on part de max cTx t.q. Ax ≤ b, x ≥ 0.
on applique l’algorithme du simplexe jusqu’a trouver une solution x∗ de support B
cTx∗ = cTx∗ = cTBx∗B = cTB
(A−1B b)=(cTBA
−1B
)b = (y∗)T b = bT y∗
forme equationnelle : max cTx t.q. Ax ≤ b, x ≥ 0.
A =(A Im
)et xT = (x xn+1, xn+2, . . . , xn+m)
variables d’ecart
{
on pose y∗ = (cTBA−1B )T et on montre que c’est une solution faisable du dual,
revient a ATy∗ ≥ c ou encore A
T(cTBA
−1B )T = A
T(A−1
B )T cB ≥ c
Dans le support,(A
T)B(A−1
B )T cB = cB ≥ cB
Hors-support,(A
T(A−1
B )T cB)H
= cH − r ou r est le vecteur des gains, donc ≤ 0.
29
Prop. Si un PL est faisable et borne, alors son dual est faisable et de meme valeur.
Preuve. on part de max cTx t.q. Ax ≤ b, x ≥ 0.
on applique l’algorithme du simplexe jusqu’a trouver une solution x∗ de support B
cTx∗ = cTx∗ = cTBx∗B = cTB
(A−1B b)=(cTBA
−1B
)b = (y∗)T b = bT y∗
forme equationnelle : max cTx t.q. Ax ≤ b, x ≥ 0.
A =(A Im
)et xT = (x xn+1, xn+2, . . . , xn+m)
variables d’ecart
{
on pose y∗ = (cTBA−1B )T et on montre que c’est une solution faisable du dual,
revient a ATy∗ ≥ c ou encore A
T(cTBA
−1B )T = A
T(A−1
B )T cB ≥ c
Dans le support,(A
T)B(A−1
B )T cB = cB ≥ cB
Hors-support,(A
T(A−1
B )T cB)H
= cH − r ou r est le vecteur des gains, donc ≤ 0.
30
Soient (P ) un PL, (D) son dual,x∗ une solution faisable de (P ) et y∗ une solution faisable de (D).
x∗ et y∗ sont complementaires ssi ∀i,x∗i = 0 ou y∗ sature la ieme contrainte de (D),
y∗i = 0 ou x∗ sature la ieme contrainte de (P ).
30
Theoreme (complementarite). x∗ et y∗ sont optimaux ssi ils sont complementaires.
Soient (P ) un PL, (D) son dual,x∗ une solution faisable de (P ) et y∗ une solution faisable de (D).
x∗ et y∗ sont complementaires ssi ∀i,x∗i = 0 ou y∗ sature la ieme contrainte de (D),
y∗i = 0 ou x∗ sature la ieme contrainte de (P ).
30
Theoreme (complementarite). x∗ et y∗ sont optimaux ssi ils sont complementaires.
Verifier une solution x∗ a un PL est facile quand son support est minimal.
On verifie que x∗ est faisable et on construit une solution y∗ du dual.
y∗ sature les contraintes associees au support de x∗ ⇒ resolution d’un systeme.
x∗ est optimal ssi x∗ et y∗ ont meme valeurs.
Soient (P ) un PL, (D) son dual,x∗ une solution faisable de (P ) et y∗ une solution faisable de (D).
x∗ et y∗ sont complementaires ssi ∀i,x∗i = 0 ou y∗ sature la ieme contrainte de (D),
y∗i = 0 ou x∗ sature la ieme contrainte de (P ).
31
C’est tout pour aujourd’hui...
