Optimisation et programmation mathématique - publié le 16/11/2023

Thèmes abordés

Optimisation mathématique, programmation mathématique, algorithme du simplexe, inéquations, évaluation de l'optimalité, tableau simplexe

Résumé du document

Ce document est un ensemble de trois exercices corrigés de niveau licence portant sur l'optimisation et la programmation mathématique : algorithme du simplexe, formulation, système d'inéquations etc.

Extraits

[...] Résolution graphique, tableau simplexe associé à un sommet Soit x₁ le nombre de produits P1 Soit x₂ le nombre de produits P2 VARIABLES DE DECISION Produit 1 x₁ Produit 2 x₂ Type Saturation des machines CONTRAINTES Temps sur M 9900 Temps sur M 8400 Temps sur M 9600 Nous obtenons le système d'inéquation suivant, sans oublier les contraintes de bon sens : 11x₁ + 9x₂ 9900 x₁ 900 - 9/11x₂ 7x₁ +12x₂ 8400 x₁ 1200-12/17x₂ 6x₁ +16x₂ 9600 x₁, x₂ 0 x₁ 1600-16/6x₂ Les sommets du polyèdre des solutions réalisables sont des candidats à la solution optimum. Pour trouver la solution optimum, il faut rechercher la courbe de niveau de la fonction objectif la plus élevée en contact avec le polyèdre. Le gradient de la fonction objectif nous indique dans quel sens croit la fonction. [...]

[...] On en déduit la solution optimum : 630 produits P1 et 335 produits P2. Ce point respecte le système d'inéquations. Pour trouver le tableau simplexe associé au sommet optimum : x₂, e₃} vecteur hors bas β { e₁, e₂ } vecteur en base B ( ) B (barre) = ( ) B = ( 900 ) L'inverse de b : B⁻₁ = ( 0,174 - ) B⁻₁ (barre) = ( 0,174 - ) On en déduit le tableau simplexe associé au sommet optimum : x₁ x₂ e₁ e₂ e₃ x₁ - x₂ - e₃ - -55,6 - Ce₁ = 0 - = -55,6 Ce₂ = 0 - = -276 = 630,6 * 900 +335,7 * 1000 = 903240 Il est logique qu'on ne puisse produire qu'un nombre entier de produit, donc le réel profit est égal à 630 * 900 + 335*1000 = 902000 L'entreprise doit donc fabriquer 630 produits P1 et 335 produits P2 pour un profit de dinars. [...]

[...] La fonction objectif J x₂, x₃) = 12000*50/3 = 200000 L'exploitation agricole doit consacrer 16,6 hectares à la production de carottes pour maximiser son profit, qui sera de 200000 dinars. Formulation Soit x₁ le nombre d'oignons d'hiver Soit x₂ le nombre d'oignons d'été Soit y₁ le nombre de poireaux d'hiver Soit y₂ le nombre de poireaux d'été Soit t la somme totale de la production, soit la somme de x₁, x₂, y₁ et y₂ Nous effectuons un tableau variable-contrainte. Il faudra ensuite en déduire un système d'inéquations pour résoudre le problème. [...]

[...] Tableau simplexe initial relatif au problème : x₁ x₂ x₃ e₁ e₂ e₃ e₄ Point réalisable e₁ = 20 e₂ 800/40=20 e₃ 600/25=24 e₄ 100000/600 0=50/ J=0 Le second membre est positif donc le point réalisable Le pivot est situé à l'intersection entre x₁ et e₄ On fait entrer en base x₁ à la place de e₄ x₁ x₂ x₃ e₁ e₂ e₃ e₄ Point réalisable e₁ 0 1/6 - 1/6000 10/3 e₂ 0 -25/3 -1/150 400/3 e₃ 0 55/6 -1/240 1100/6 e₄ 1 5/6 1/6000 50/ J =200000 Le second membre est positif donc le point est réalisable. Il reste à évaluer l'optimalité. [...]