Algorithme

Dans cet algorithme nous allons utilisé la méthode du Simplexe afin de résoudre le programme linéaire. Nous utiliserons ces données qui sont générées automatiquement :

• p : le nombre des instances, p ϵ [500 ; 2000]
• n : le nombre de variables des décisions, n ϵ [1000 ; 100 000].
• m : le nombre des contraintes, m ϵ [50 ; 1000]

Le modèle de notre programme :

MAX   z = cx

     s.c. Ax ⩽ b

            x ⩾ 0

• b : chaque composante b varie dans l’intervalle réel [25 ; 250]
• c : chaque composante du vecteur profit c varie dans l’intervalle réel ϵ [0 ; 500]
• A : chaque composante de la matrice des A varie dans l’intervalle réel ϵ [0 ; 100]

Programme principal

package simplexe;

public class Main {

    public static void main(String[] args) {
        int nb_instance = rand(500, 2000);
        System.out.println("Nombre d'instances = " + nb_instance);
        for(int i=0; i<nb_instance; i++){
            try{
                //pour tester l'execution
                //System.out.println("i = " + i);
                //Simplexe p = new Simplexe(3, 2);
                Simplexe p = new Simplexe(rand(1000, 100000), rand(50, 1000));
            }catch(ConstraintsNumberException e){
                System.out.println("Nb constraintes > variables decisions.");
            }
        }
        System.out.println("Le nombre des instances = " + nb_instance);
    }
    
    public static int rand(int min, int max){
        return min + (int)Math.floor(Math.random()*(max-min));
    }
}

Dans le Main (programme principal) le nombre d’instance qui varie entre 500 et 200 est généré aléatoirement (dans notre exemple d’exécution p = nb_instance = 543).

Ensuite pour chaque instance on appelle notre fonction Simplexe qui prend en paramètre deux entier aléatoires, n et m.

Méthode du Simplexe

Définition : « L'algorithme du simplexe est un algorithme de résolution des problèmes d'optimisation linéaire. Données d’entrées : un tableau réalisable / Résultat : un tableau optimal ou non borné ».

    public Simplexe(int n, int m) throws ConstraintsNumberException{
        if(m>n){
            throw new ConstraintsNumberException();
        }
        this.c = new double[n+m];
        this.A = new double[m][n+m];
        this.b = new double[m];
        for(int i=n; i<c.length; i++){
            c[i] = 0;
        }
        for(int l=0; l<b.length; l++){
            for(int k=n; k<c.length; k++){
                A[l][k] = (k-n == l ? 1 : 0);
            }
        }
        for(int i=0; i<n; i++){
            c[i] = rand(500);
        }
        for(int l=0; l<b.length; l++){
            for(int k=0; k<n; k++){
                A[l][k] = rand(100);
            }
        }
        for(int i=0; i<b.length; i++){
            b[i] = randBase(25, 250);
        }
        
        c[0]=3;
        c[1]=5;
        c[2]=1;

        A[0][0]=8;
        A[0][1]=16;
        A[0][2]=19;
        A[1][0]=9;
        A[1][1]=25;
        A[1][2]=7;

        b[0]=17;
        b[1]=24;
        
        ExecuteProgramme();
        
        long debut_execution = System.currentTimeMillis();
        while(!opt){
            detPivot();
        }
        temps_execution = System.currentTimeMillis()-debut_execution;
        
        writeFile(n, m, temps_execution);
    }

Avons de commencer nos calculs nous avons rempli les variables et les matrices avec les réels qui conviennent ensuite on lance la fonction ExecuteProgramme()  qui permet d’afficher notre système linéaire dans la console.

Nous avons déclaré deux variables debut_execution et temps_execution qui permettent d’enregistrer les temps d’exécution de la fonction et dés qu’on trouve une solution optimale on stocke le temps d’exécution, la valeur de n et la valeur de m dans un fichier Excel.

Les étapes d'exécution

1/ choisir une colonne (variable) entrante :

Dans cette étape nous choisissons une colonne hors-base noté s ayant un coût (profit) positif,

            s ϵ { j ϵ { 1,….,n } tel que c_j  > 0 }

            on utilise la règle de Bland pour choisir la colonne qui convient.

2/ choisir une colonne (variable) sortante :

            On doit choisir une ligne r minimisant les quotients b_i / a_is suivants :

            r ϵ { i ϵ { 1,….,m } tel que b_i / a_is  = min{ b_k / a_ks  avec a_ks  > 0 } }

S’il n’existe pas de colonne entrante : sortir avec un tableau courant non borné

public void detPivot() {
    int idProfit = -1;
    double max = Double.MIN_VALUE;
    for (int i=0; i<c.length; i++){
        if(c[i] > 0 && c[i] > max){
            max = c[i];
            idProfit = i;
        }
    }
    if(idProfit == -1) {
        opt = true;
        //////
        System.out.println("La solution est optimale : z = " + -z);
    } else {
        opt = false;
        int idPivot = regleBland(idProfit);
        if(idPivot == -1){
            System.out.println("La solution est non bornée.");
        } else {
            double sol = -pivotage(idPivot, idProfit);
            System.out.println("Nouvelle solution : " + sol + "\n");
        }
    }
}

3/ mettre à jour la base courante et des valeurs du tableau

            Pivoter autour de a_rs et répéter à partir de l’étape 1.

public double pivotage(int idPivot, int idProfit) {
    double alpha = 0;
    for(int l=0; l<b.length; l++) {
        alpha = -A[l][idProfit]/A[idPivot][idProfit];
        if(l != idPivot){
            for(int k=0; k<c.length; k++){
                A[l][k] += alpha*A[idPivot][k];
            }
            b[l] += alpha*b[idPivot];
        }
    }
    
    //Fonction objectif
    alpha = -c[idProfit]/A[idPivot][idProfit];
    for(int i=0; i<c.length; i++) {
        c[i] += alpha*A[idPivot][i];
    }
    z += alpha*b[idPivot];
    
    //Ligne du pivot
    alpha = A[idPivot][idProfit];
    for(int i=0; i<c.length; i++) {
        A[idPivot][i] /= alpha;
    }
    b[idPivot] /= alpha;
    
    return z;
}

NB : La règle de Bland 

« Lorsque plusieurs candidats sont susceptibles d’entrer ou de sortir de la base, les départager en choisissant toujours la variable x_r ayant le plus petit index r.

public int regleBland(int idProfit) {
    int idPivot = -1;
    double min = Double.MAX_VALUE;
    for(int i=0; i<b.length; i++) {
        if(A[i][idProfit] > 0 && b[i]/A[i][idProfit]<min){
            min = b[i]/A[i][idProfit];
            idPivot = i;
        }
    }

    return idPivot;
}

Compilation

javac Main.java Simplexe.java ConstraintNumberException.java

Exécution

java simplex/Main

Vous pouvez télécharger le dossier .zip du projet qui contient tous les fichiers sources, en cliquant sur le lien ci-dessous.