Méthode du simplexe pour problèmes de programmation linéaire

Cette macro trouve la solution optimale d'un programme linéaire à l'aide de la forme révisée du simplexe. La programmation linéaire (PL) concerne une fonction d'objectif avec uniquement des termes linéaires et elle suppose qu'il n'existe que des contraintes linéaires.

De manière générale, si le nombre de contraintes est très supérieur au nombre de variables de décision, la forme d'origine du simplexe n'est pas efficace.

La fonction d'objectif peut servir à maximiser ou à minimiser une fonction mathématique, telle que la représentation d'un bénéfice ou d'un coût. L'optimisation comporte le plus souvent une contrainte, ce qui signifie que la solution optimale doit être trouvée dans certaines limites qui sont en général définies par la quantité de ressources ou le budget disponible pour un projet.

Télécharger la macro

Assurez-vous que Minitab connaît l'emplacement de la macro que vous avez téléchargée. Sélectionnez Outils > Options > Général. Sous Emplacement de la macro, accédez à l'emplacement où vous avez enregistré les fichiers de macro.

Important

Si vous utilisez un ancien navigateur Web, lorsque vous cliquez sur le bouton Télécharger, il est possible que le fichier s'ouvre dans Quicktime, qui partage l'extension de fichier .mac avec les macros de Minitab. Pour enregistrer la macro, cliquez avec le bouton droit de la souris sur le bouton Télécharger, puis sélectionnez Enregistrer la cible sous.

Entrées requises

  • Une colonne contenant les coefficients de la fonction d'objectif.
  • Les colonnes correspondant à chacun des éléments de la fonction d'objectif, y compris les variables, le symbole d'égalité et le résultat. Chaque ligne de cet ensemble de colonnes identifie une contrainte sur l'optimisation.

L'exemple suivant, extrait de l'ouvrage de Hillier et Lieberman, illustre la fabrication de deux produits (x1 et x2) pour la société Wyndor Glass Co. Les trois contraintes représentent la capacité de chacune des trois usines de la société à utiliser les ressources pour la production du produit 1 (x1) et du produit 2 (x2).

MAXIMIZE Bénéfice = 3x1 + 5x2 (Fonction d'objectif)

SUBJECT TO:

x1   <= 4 (Usine 1)
  2x2 <= 12 (Usine 2)
3x1 +2x2 <= 18 (Usine 3)

x1 ≥ 0, x2 ≥ 0 (Contraintes de non-négativité)

Les coefficients, les signes d'égalité et les résultats doivent être saisis dans une feuille de travail Minitab comme suit :

C1 C2 C3 C4 C5
x1 x2 inégalité résultats objectif
1 0 <= 4 3
0 2 <= 12 5
3 2 <= 18  

Entrées facultatives

MIN
Par défaut, la macro résout un problème de maximisation. Si vous souhaitez minimiser la fonction d'objectif, insérez un point-virgule après la commande principale et, dans la seconde ligne, utilisez la commande MIN et un point ("."), marquant la fin de la commande.

Exécution de la macro

Supposons que vos données soient organisées comme ci-dessus. Pour exécuter la macro, sélectionnez Edition > Editeur de ligne de commande et saisissez :

%SIMPLEX C1-C2 C4 C5; 
INEQ C3.

Cliquez sur Soumettre les commandes.

Informations supplémentaires

En général, n + 2 colonnes sont spécifiées pour formuler le problème. L'argument final saisi dans la commande principale correspond à la colonne contenant les coefficients de la fonction d'objectif. L'avant-dernier argument requiert une colonne spécifiant le côté droit de toutes les inégalités dans le problème (à l'exception de la non-négativité, puisqu'elle est supposée par défaut). Les premières n colonnes spécifient les coefficients (a11, a12,..., a1n) de toutes les contraintes linéaires de type a11*x1 + a12*x2 + ...  + a1n*xn.

Enfin, si toutes les inégalités sont de type "<=", aucune opération de votre part n'est nécessaire ; sinon indiquez les symboles pour toutes les contraintes dans une colonne. Vous pouvez saisir l'un des symboles suivants : >=, >, ≥, ≤, <=, <, =.

Pour obtenir des informations plus techniques sur l'algorithme reportez-vous à l'ouvrage suivant :

Bazaraa, M.S., Jarvis, J.J. et Sherali, H.D. "Linear Programming and Network Flows", 4e édition. John Wiley & Sons, New Jersey, 2010.

En utilisant ce site, vous acceptez l'utilisation de cookies à des fins d'analyse et de personnalisation du contenu.  Lisez notre politique