Document2: Programmationconvexeetquadratique
1 ConditionsdeKuhn-Tucker 1 2 Programmationquadratique 3 2.1 Coniques . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 3 2.2 Méthode de Beale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 Méthode de
Dantzig . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.4 Méthode de Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1 ConditionsdeKuhn-Tucker
Exercice 1 Pour chacun des programmes suivants, déterminer géométriquement le domaine
réalisableconstituéparlescontraintes.Résoudrecesprogrammesaumoyendesconditions de Kuhn-
Tucker. Max (x3 1 −3x2) x1 −x2 + 2 ≥ 0 2x1 +
x2 −2 ≥ 0 x1 + 2x2 −10 ≤ 0 7x1 + 2x2 −28 ≤ 0 x1 et x2 ≥ 0 Max (4x1 −3x2) x1
+ 2x2 ≤ 7 2x1 + 5x2 ≥ 8 x1 et x2 ≥ 0 Exercice 2-MéthodedeLagrange 2-1) Déterminer le rectangle de
plus grande surface inscrit dans l’ellipse d’équation x2 1 a2 + x2 2 b2 = 1. 2-2) Déterminer le
parallélépipède de plus grand volume inscrit dans l’ellipsoïde d’équation x2 1 a2 + x2 2 b2 + x2 3 c2 =
1.
Exercice 3 On considère une économie à deux biens : un bien de consommation et le travail. L’indice
1 désigne le bien de consommation, dont le prix est p1, tandis que l’indice 2 désigne le travail, de prix
p2 (salaire). Les préférences d’un agent économique, dont la seule ressource est la force de travail,
sont représentables par une fonction d’utilité : U(x1,x2) = 2lnx1 + ln(3−x2). On suppose qu’il existe un
minimum vital de consommation x1 ≥ 1 et un plafond de travail que l’agent économique ne peut pas
dépasser x2 ≤ 3. On veut déterminer la fonction de demande du bien de consommation et la fonction
d’offre du travail. Formuler le programme de maximisation, donner une représentation géométrique
du problème et le résoudre au moyen des conditions de Kuhn-Tucker. La solution estelle unique?
Pourquoi?
Exercice 4 4-1) Résoudre par la méthode de Kuhn-Tucker le programme d’optimisation
suivant,danslequel m estunnombreréelstrictementpositifsuivantlesvaleursduquelon sera amené à
discuter : Max(x1 −1)2 (6−x2)x1 ≥ 2 0 ≤ x2 ≤ 5 x1
−mx2 ≤ 0 x1 et x2 ≥ 0 4-2) LesconditionsdeKuhn-Tuckersont-ellesàlafoisnécessairesetsuffisantes?
Pourquoi?
Exercice 5 On considère le programme quadratique suivant : Min (3x2 1
−2x1x2 + 3x2 2 −22x1 −14x2) −x1 + 3x2 ≤ 1 −3x1 + 7x2 ≤ 0 x1 −x2 ≤ 4 x1 et x2 ≥ 0 5-1) Ecrire les
conditions de Kuhn-Tucker de ce programme. 5-2) La solution x1 = 7/2 et x2 = 3/2 est-elle réalisable?
Est-elle optimale? 5-3) Résoudre le programme au moyen des conditions de Kuhn-Tucker. 5-4)
Donner les valeurs des variables d’écart ainsi que des coefficients de KuhnTucker λ1 et λ2.
Exercice 6 Une ressource disponible en quantité d doit être affectée à trois activités en quantités x1,
x2 et x3 respectivement. L’allocation de xk unités de ressource à l’activité k procure une recette nette
évaluée par fk(xk) = 8xk −kx2 k.
2
6-1) Onsouhaitedéterminerquelleestl’allocationquiprocureraunerecettenette totale maximale, dans
les deux éventualités suivantes : 1. la quantité disponible d est complètement utilisée. 2. on peut
utiliser une quantité inférieure à d et l’excédent est revendu au prix p. Le premier cas sera traité par
la méthode de Lagrange et le second cas au moyen des conditions de Kuhn-Tucker. 6-2) En
confrontant les résultats obtenus, examiner si on a intérêt à utiliser com