Scribd
Importer
27 vues2 pages

CoursPontsRO 69 70

Le document traite du théorème fort de la dualité en programmation linéaire, démontrant que la solution optimale d'un programme primal peut être utilisée pour construire des solutions réalisables au programme dual. Il propose également une méthode pour tester la réalisabilité d'un système d'équations linéaires et montre comment cela peut être appliqué à des programmes linéaires. Enfin, il aborde des exemples pratiques, comme la modélisation d'un problème de diététique et la formulation du problème du sac à dos en tant que programme linéaire en nombres entiers.

Transféré par

lovebooks
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
27 vues2 pages

CoursPontsRO 69 70

Le document traite du théorème fort de la dualité en programmation linéaire, démontrant que la solution optimale d'un programme primal peut être utilisée pour construire des solutions réalisables au programme dual. Il propose également une méthode pour tester la réalisabilité d'un système d'équations linéaires et montre comment cela peut être appliqué à des programmes linéaires. Enfin, il aborde des exemples pratiques, comme la modélisation d'un problème de diététique et la formulation du problème du sac à dos en tant que programme linéaire en nombres entiers.

Transféré par

lovebooks
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

63 CHAPITRE 4.

PROGRAMMATION LINÉAIRE

4.6.4 Théorème fort de la dualité


En s’appuyant sur la caractérisation de l’optimalité de la solution retournée par l’algo-
rithme du simplexe, prouver le théorème fort de la dualité (Théorème 4.4). Plus précisément,
montrer que le programme (4.8) écrit dans la base optimale permet de construire des so-
lutions réalisables au dual (4.11) donnant le même coût à la fonction objectif. Expliquer
pourquoi cela permet de conclure.

4.6.5 Trouver une solution réalisable


Considérons le système suivant
Ax = b
(4.14)
x≥0
où b ∈ Rm et A est une m × n matrice réelle. L’objectif de l’exercice est de proposer une
méthode pour tester si un tel système a une solution réalisable, et s’il en existe, en trouver
une.
1. Montrer qu’on peut supposer que b ≥ 0.
Considérons maintenant le programme
Pm
Min i=1 yi
s.c. Ax + y = b
(4.15)
x≥0
y≥0

2. Montrer que le système (4.14) a une solution réalisable si et seulement si le programme (4.15)
a une valeur optimale = 0.
Par conséquent, l’algorithme du simplexe est une méthode pour résoudre un système de
la forme du système (4.14). En effet, le programme (4.15) a une solution basique réalisable
facile à identifier : y = b et x = 0. On peut alors dérouler l’algorithme du simplexe aisément
sur le programme (4.15) à partir de cette base initiale. Noter que s’il y a une solution au
système (4.14), cette méthode lui trouve une solution basique réalisable. C’est donc également
une méthode pour trouver une première solution réalisable à un programme linéaire pour
lequel il n’y en a pas d’évidente.
3. Réciproquement, montrer avec la théorie de la dualité que si on a une méthode pour trouver
une solution réalisable de n’importe quel système d’équations et d’inéquations linéaires, alors
on peut utiliser cette méthode pour résoudre les programmes linéaires.

4.6.6 Meilleure droite approximante


Soit (x1 , y1 ), (x2 , y2 ), . . . , (xn , yn ) des points dans le plan. On cherche la meilleure droite
approximante pour la norme sup, i.e. la droite du plan d’équation ax + b = y telle que
supi=1,...,n |axi + b − yi | soit le plus petit possible. Montrer que Pcela revient à résoudre un
programme linéaire. Même question en cherchant à minimiser ni=1 |axi + b − yi |.
CHAPITRE 4. PROGRAMMATION LINÉAIRE 64

4.6.7 Interprétation économique de la dualité


Un diététitien utilise six produits comme source de vitamines A et C. Il a une certaine
demande en vitamine A et en vitamine C. Il veut la satisfaire au moindre coût.

Produits (unités/kg) Demande


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

1. Modéliser ce problème comme un programme linéaire.


2. Ecrire le programme dual. Proposer une interprétation.

4.6.8 Programmation linéaire en nombres entiers


Un programme linéaire du type

Min cT x
s.c. Ax = b (4.16)
xj ∈ N j = 1, . . . , n

est appelé programme linéaire en nombres entiers.


Ecrire le problème du sac-à-dos comme un programme liénaire en nombre entiers.
Comme le problème du sac-à-dos est NP-difficile, cela prouve que la résolution des pro-
grammes linéaires en nombre entiers est également NP-difficile.

Vous aimerez peut-être aussi