Programmation de la méthode simplexe en Matlab

Vous allez mettre en œuvre trois fonctions Matlab qui, ensemble, résolvent des programmes linéaires sous forme de :

Où A est une matrice m × n, x est un vecteur ligne de longueur n, et c est un vecteur colonne de longueur n.

Vous ne pouvez pas supposer que A a une forme particulière; En particulier, on ne doit pas supposer que A est une matrice de contraintes découlant de l'introduction de variables lentes de la .

En commençant par un problème de la forme (1), on introduit m nouvelles variables y1,. . . , ym et résoudre le problème auxiliaire

Il est clair que nous pouvons toujours trouver un vecteur facultatif pour le nouveau problème auxiliaire (en particulier, nous choisissons les variables de base yj et les colonnes correspondantes de la matrice de contraintes sont l'identité).

Le problème initial a un premier vecteur de base réalisable si et seulement si le problème (2) a une solution telle que y1 = y2 =. . . = Yn = 0.

Il y a cependant une complication. Si l'on arrive à une solution de (2) pour laquelle toutes les variables de base sont , on a alors un vecteur initialement réalisable pour le problème initial. Si, d'autre part, quelques-uns des  s sont fondamentalement réalisables pour notre solution de (2), alors nous devrions effectuer d'autres manipulations pour obtenir un vecteur faisable de base pour le problème initial. Nous ne nous occuperons pas de cela. Notre procédure d'initialisation tentera de trouver la solution au problème auxiliaire (2).

Si nous trouvons une telle solution et que les variables de base incluent les , nous allons simplement signaler que notre procédure d'initialisation a échoué.

La première étape

La première étape consiste à implémenter une fonction Matlab appelée simplexe_etape pour exécuter une seule étape de la méthode simplex révisée. Nous ferons le suivi du vecteur de base courant réalisable avec trois variables: iB, iN et xB. Le vecteur iB tiendra les indices de l'ensemble courant de variables de base, iN tiendra les indices de l'ensemble courant de variables non base, et xB tiendra les valeurs des variables de base.

La fonction simplexe_etape doit être placée dans un fichier simplexe_etape.m et elle doit avoir la séquence suivante:

function [istatus,iB,iN,xB] = simplexe_etape(A,b,c,iB,iN,xB,iregle)

%

% Prendre une seule méthode simplex pour le programme linéaire

%

% min: c*x

% ST: Ax=b

% x>=0,

%

% ou A est une matrice (m,n).

%                

%                   Paramètres d'entrée:

%

% A - (n, m) matrice de contraintes

% B - (m, 1) Vecteur POSITIF apparaissant dans l'équation de contrainte ci-dessus

% C - (1, n) vecteur donnant les coefficients de la fonction objective

% iB - (1, m) vecteur entier spécifiant les indices des variables de base au début de l'étape simplex

% iN - (1, n-m) vecteur entier représentant les indices de la non-base

% De variables au début de l'étape simplex

% xB - (m, 1) vecteur spécifiant les valeurs de la base

% De variables au début de l'étape simplex

%

% Iregle - paramètre entier spécifiant la règle de pivot à utiliser:

% iregle= 0 indique que la règle du coefficient le plus petit doit être utilisée

% Irelgle = 1 indique que la règle de Bland doit être utilisée%

%

% Paramètres de sortie:

%

% Istatus - paramètre entier rapportant la progression ou lac de celui-ci effectué par cette fonction

% Istatus = 0 indique l'étape normale de la méthode simple non dégénérée terminée

% Istatus = 16 indique que le programme est illimité

% Istatus = -1 indique qu'un vecteur optimal possible a été trouvé

%

% iB - vecteur entier spécifiant les m indices des variables de base après l'étape simplex

% iN - vecteur entier spécifiant les indices n-m des variables non basses après l'étape simplex

% xB - vecteur de longueur m spécifiant les valeurs des variables de base après l'étape simplex

%

Étape deux

La deuxième étape consiste à implémenter une fonction Matlab pour effectuer l'initialisation. La fonction doit être appelée simplexe_init et elle doit être placée dans le fichier simplexe_init.m. La séquence d'appel de cette fonction est:

function [istatus,iB,iN,xB] = simplexe_init(A,b,c)

%

% Tentative de trouver un vecteur facultatif de base pour le programme linéaire

%

% max: c*x

% ST: Ax=b

% x>=0,

%

% ou A est une  matrice (m,n).

%

% Paramètres d'entrée:

%

% A - (n, m) matrice de contraintes

% B - (m, 1) vecteur apparaissant dans l'équation de contrainte ci-dessus

% C - (1, n) vecteur donnant les coefficients de la fonction objective

%

% Paramètres de sortie:

%

% istatus - paramètre entier indiquant le résultat de la procédure d'initialisation

% istatus = 0 indique qu'un vecteur réalisable de base a été trouvé

% istatus = 4 indique que la procédure d'initialisation a échoué

% istatus = 16 indique que le problème est impossible

%

% iB - vecteur entier de longueur m spécifiant les indices des variables de base

% iN - vecteur entier de longueur n-m caractérisant les indices des variables non basses

% xB - vecteur de longueur m spécifiant les valeurs des variables de base

%

Troisième étape :

L'étape finale est la mise en œuvre d'une méthode simplex de fonction Matlab qui a utilisé les deux fonctions précédentes pour calculer une solution à un programme linéaire. La séquence de la méthode de la fonction simplexe, ce qui devrait se trouver dans le fichier simplexe_methode.m, est la suivante:

function [istatus,X,eta,iB,iN,xB] = simplexe_methode(A,b,c,iregle)

%

% Trouver une solution optimale de base pour le programme linéaire

%

% min: c*x

% ST: Ax=b

% x>=0,

%

% ou A est une  matrice (m,n).

%

% Paramètres d'entrée:

%

% A - (n, m) matrice de contraintes

% b - (m, 1) Vecteur POSITIF apparaissant dans l'équation de contrainte ci-dessus

% c - (1, n) vecteur donnant les coefficients de la fonction objective

%

% iregle - paramètre entier spécifiant la règle de pivot à utiliser:

% iregle = 0 indique que la règle du coefficient le plus petit doit être utilisée

% iregle = 1 indique que la règle de Bland doit être utilisée

%

% Paramètres de sortie:

%

% istatus - paramètre entier indiquant les résultats obtenus par cette fonction

% istatus = 0 indique une complète complète (c'est-à-dire qu'une solution a été trouvée et rapportée)

% istatus = 4 indique que le programme est impossible

% istatus = 16 indique que le programme est possible mais que notre procédure d'initialisation a échoué

% Istatus = 32 indique que le programme est illimité

%

% X vecteur de longueur n spécifiant la solution

% eta - la valeur minimale de la fonction objectif

% iB - vecteur entier spécifiant les m indices des variables de base après l'étape simplex

% iN - vecteur entier spécifiant les indices n-m des variables non basses après l'étape simplex

% xB - vecteur de longueur m spécifiant les valeurs des variables de base après l'étape simplex

%

En utilisant n'importe quelle technique que vous souhaitez, modifiez votre fonction simplexe_init , il marchera très biens à moins que le programme linéaire ne soit faisable.