Ce document décrit les étapes de développement d'un algorithme du simplexe pour résoudre des programmes linéaires. Il présente les exercices à réaliser pour implémenter les fonctionnalités clés de l'algorithme telles que l'initialisation du dictionnaire, le choix de la variable pivot et l'opération de pivotage.
0 évaluation0% ont trouvé ce document utile (0 vote)
249 vues8 pages
Ce document décrit les étapes de développement d'un algorithme du simplexe pour résoudre des programmes linéaires. Il présente les exercices à réaliser pour implémenter les fonctionnalités clés de l'algorithme telles que l'initialisation du dictionnaire, le choix de la variable pivot et l'opération de pivotage.
Ce document décrit les étapes de développement d'un algorithme du simplexe pour résoudre des programmes linéaires. Il présente les exercices à réaliser pour implémenter les fonctionnalités clés de l'algorithme telles que l'initialisation du dictionnaire, le choix de la variable pivot et l'opération de pivotage.
Ce document décrit les étapes de développement d'un algorithme du simplexe pour résoudre des programmes linéaires. Il présente les exercices à réaliser pour implémenter les fonctionnalités clés de l'algorithme telles que l'initialisation du dictionnaire, le choix de la variable pivot et l'opération de pivotage.
Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
Télécharger au format pdf ou txt
Vous êtes sur la page 1/ 8
GLIN606 Programmation linéaire Année 2011-2012
- TP 1. Calculs sur les rationnels. -
Le but de ce TP est de se constituer une petite bibliothèque sur les rationnels. Elle nous servira tout au long de notre implémentation du simplexe dont les calculs ne s’exprimeront ni en entier, ni en float pour des raisons d’arrondis.
Langage. Votre programme en C++ pourra commencer par :
#include <cstdlib> #include <iostream>
using namespace std;
typedef struct {{ int p; int q;} rat;
Les rationnels seront donc des nombres de la forme a/b où a est un entier et b est un entier positif. Ecrire les fonctions suivantes :
rat convert(int a, int b) // Convertit un couple d’entiers en rationnels.
rat opposerat(rat z) // Retourne l’opposé de z. rat inverserat(rat z) // Retourne l’inverse de z. rat ratnull() // Retourne le rationnel nul. bool negatif(rat z) // Teste si un rationnel est négatif. bool negatifounul(rat z) // Teste si un rationnel est negatif ou nul. bool pluspetit(rat x, rat y) // Teste si x est plus petit que y. bool pluspetitouegal(rat x, rat y) // Teste si x est plus petit que y. rat produitrat(rat u, rat v) // Retourne le produit de u et v. rat sommerat(rat a, rat b) // Retourne la somme de a et b. void simplify(rat *z) // Réduit la fraction (Attention ! Utiliser un calcul de pgcd pas trop lent...). void afficherat(rat z) // Affiche le rationnel z. Par exemple 2/3 ou -2 ou encore -11/25. void afficheratsigne(rat z) // Affiche z avec son signe. Par exemple +2/3 ou -2 ou encore -11/25.
Le but de ce TP est d’afficher les programmes linéaires et les dictionnaires que le simplexe va engendrer. Dans un premier temps, on se contentera d’un affichage console. Pour le lecteur exigeant, ne pas hésiter à utiliser Latex, avec un exemple proposé sur la page : http://www.lirmm.fr/~bessy/PL/accueil.html (section Documents) Rappelons que le programme linéaire (P ) que l’on veut résoudre est de la forme :
Maximiser cP1 x 1 + · · · + cn x n n Sous j=1 aij xj ≤ bi i = 1, . . . , m x1 , . . . , x n ≥ 0 Tous les coefficients aij , bi et cj sont des rationnels. Le codage de l’entrée se fait par deux tableaux int objectif[2 ∗ n] et int contraintes[m][2 ∗ n + 2]. La correspondance se fait ainsi :
– Le coefficient ci est égal à objectif[2 ∗ i − 2]/objectif[2 ∗ i − 1].
– Le coefficient aij est égal à contraintes[i − 1][2 ∗ j − 2]/contraintes[i − 1][2 ∗ j − 1]. – Le coefficient bi est égal à contraintes[i − 1][2 ∗ n]/contraintes[i − 1][2 ∗ n + 1].
- Exercice 1 - Affichage du programme linéaire.
Ecrire une fonction void afficheprogramme(int contraintes[m][2*n+2], int objectif[2*n]) qui affiche le programme linéaire. Par exemple, pour les entrées : int objectif[6] = {2, 3, 3, 1, −1, 5}; int contraintes[2][8] = {{2, 1, 0, 1, 6, 1, 2, 3}, {7, 1, 8, 1, −2, 1, 1, 4}}; l’affichage sera de la forme : Maximiser 2/3x 1 +3x 2 -1/5x 3 Sous 2x 1 +6x 3 <= 2/3 7x 1 +8x 2 -2x 3 <= 1/4 x 1,x 2,x 3 positifs ou nuls
- Exercice 2 - Dictionnaires. L’algorithme du simplexe manipule des dictionnaires de la forme :
x3 = 2 +x4 −x2 +5/2x5
x1 = 3 −2/3x2 −1/3x5 z =4 −x4 −2x2 +3x5 Ils sont représentés par : – Un tableau de rationnels rat dico[m + 1][n + 1], ici rat dico[3][4] dont par exemple l’entrée dico[0][3] est le rationnel 5/2 et l’entrée dico[2][0] est le rationnel 4. – Un tableau int variables[n+m] qui énumère tout d’abord les indices des variables non basiques du dictionnaire (celles horizontales, ici x4 , x2 , x5 ), et ensuite les variables basiques (celles verticales, ici x3 , x1 ). Dans l’exemple, on aura variables[5] = {4, 2, 5, 3, 1}.
Ecrire une fonction d’affichage void affichedico(rat dico[m + 1][n + 1],int variables[m + n]).
Le but de ce TP est d’implémenter la première phase de l’algorithme du simplexe.
L’algorithme du simplexe transforme le programme (P ) en un dictionnaire initial, sur lequel des pivots sont itérés.
- Exercice 3 - Dictionnaire initial.
Ecrire une fonction
void initialisedico(int contraintes[m][2 ∗ n + 2], int objectif[2 ∗ n], rat dico[m + 1][n + 1], int variables[n + m])
qui initialise les tableaux dico et variables représentant le dictionnaire initial du programme linéaire (P) donné par les tableaux contraintes et objectif.
- Exercice 4 - Pivot entrant.
Ecrire une fonction int pivotentrant(rat dico[m+1][n+1]) qui retourne le numéro de colonne entre 1 et n qui correspond à une variable entrante. Si aucune variable ne convient, pivotentrant retourne 0.
- Exercice 5 - Pivot sortant.
Ecrire une fonction int pivotsortant(rat dico[m + 1][n + 1], int i) qui retourne le numéro de ligne entre 1 et m qui correspond à une variable sortante, et ceci lorsque i est la colonne de la variable entrante. Si aucune variable sortante ne convient, pivotsortant retourne 0.
- Exercice 6 - Pivoter. Ecrire une fonction void pivoter(rat dico[m + 1][n + 1], int variables[n + m], int sort, int entr) qui effectue un pivot de simplexe sur le dictionnaire pour la variable entrante entr et la variable sortante sort.
- Exercice 7 - Simplexe. Achever d’implémenter l’algorithme du simplexe en une phase. Votre algorithme devra retourner : – soit une solution admissible optimale. – soit le message : La fonction objectif n’est pas bornée. – soit le message : Le dictionnaire initial de (P ) n’est pas admissible.
Le but de ce TP est d’effectuer quelques calculs avec votre algorithme, ainsi que d’en définir les limites.
- Exercice 8 - Application du simplexe.
Appliquer votre algorithme : 1. Aux programmes linéaires des exercices 1,2 et 3 de la fiche de TD. 2. À des programmes linéaires à n variables et n contraintes dont les coefficients sont tirés au hasard entre 1 et 10. Jusqu’à quelles valeurs de n votre algorithme vous permet-il de résoudre un programme linéaire ? 3. Votre algorithme est-il plus sensible au nombre n de variables ou au nombre m de contraintes ? Faire des simulations.
- Exercice 9 - Règle de Bland.
Ecrire une fonction int pivotentrantbland(rat dico[m + 1][n + 1],int variables[m + n]) et int piv- otsortantbland(rat dico[m + 1][n + 1], int i,int variables[m + n]) qui choisit les pivots entrants et sortants de plus petit indice lorsqu’il y a plusieurs choix possibles.
- Exercice 10 - Un cas de cyclage.
Ecrire une fonction int pivotentrantmaxcoef(rat dico[m + 1][n + 1]) qui retourne, parmi les choix possibles de pivots entrants, celui qui a un coefficient maximum dans la fonction objectif. Utiliser les fonctions pivotentrantmaxcoef et pivotsortantbland afin de résoudre l’exercice 43 de la fiche de TD.
- Exercice 11 - Les exemples de Klee-Minty.
Résoudre le problème linéaire suivant en utilisant l’algorithme du simplexe. Le choix de la variable entrante se fera avec pivotentrantmaxcoef.
Maximiser 100x1 +10x2 +x3
Sous x1 ≤1 20x1 +x2 ≤ 100 200x1 +20x2 +x3 ≤ 10000 x1 , x2 , x3 ≥0 Généraliser cet exemple pour n variables. Quel est le nombre f (n) de pivots effectués ?
Le but de ce TP est de résoudre le problème d’affectation (Cf cours, étude de cas 6) de t agents à t tâches. On se donne un tableau de rationnels assign[t][t] dont chaque entrée assign[i][j] représente la performance pij de l’agent i à réaliser la tâche j. Le problème est d’assigner une tâche à chaque agent afin de maximiser la somme des performances des agents à réaliser leurs tâches respectives. La modélisation de ce problème se fait ainsi : Les variables de décision sont les xij qui représentent la part de la tâche j réalisée par l’agent i. La fonction à maximiser est la somme des pij xij . Les contraintes sont : – Pour chaque agent i fixé, la somme des xij est au plus 1. – Pour chaque tâche j fixée, la somme des xij est au plus 1.
Il y a donc n = t2 variables de décision et m = 2t contraintes, parmi lesquelles t proviennent des
agents et t autres proviennent des tâches. Les variables d’écart provenant des agents seront notées a1 , . . . , at et celles provenant des tâches seront notées t1 , . . . , tt . Le but est d’utiliser l’algorithme du simplexe en une phase afin de résoudre ce problème. Illus- trons sur le cas (facile !) suivant :
performance tâche 1 tâche 2
agent 1 3 2 agent 2 3 5
On voit clairement que la performance maximale sera obtenue en assignant l’agent 1 à la tâche 1 et l’agent 2 à la tâche 2. Mais on va faire le calcul en utilisant le simplexe. La principale difficulté est d’initialiser le dictionnaire correspondant au programme linéaire. On veut obtenir :
Le dictionnaire initial est :
a 1 = 1 -x 11 -x 12 a 2 = 1 -x 21 -x 22 t 1 = 1 -x 11 -x 21 t 2 = 1 -x 12 -x 22 z = 0 +3x 11 +2x 12 +3x 21 +5x 22
Ceci se fait par l’intermédiaire d’une fonction void dicoinitassign(rat assign[t][t], rat dico[m + 1][n + 1]) qui initialise dico comme dictionnaire initial du problème d’assignation. L’affichage des variables se fera avec une fonction void affichevar(int i) qui au lieu d’afficher simplement x i affichera x 11, x 12, x 21, x 22, a 1, a 2, t 1, t 2, pour i variant de 1 à n + m.
La suite ne pose pas de problème, il suffit d’exécuter le simplexe.
La variable entrante est x 11.
La variable sortante est a 1. x 11 = 1 -a 1 -x 12 a2 = 1 -x 21 -x 22 t 1 = 0 +a 1 +x 12 -x 21 t2 = 1 -x 12 -x 22 z = 3 -3a 1 -x 12 +3x 21 +5x 22 La variable entrante est x 22. La variable sortante est a 2.
x 11 = 1 -a 1 -x 12 x 22 = 1 -x 21 -a 2 t1 = 0 +a 1 +x 12 -x 21 t2 = 0 -x 12 +x 21 +a 2 z = 8 -3a 1 -x 12 -2x 21 -5a 2 La solution optimale est : x 11= 1 x 12= 0 x 21= 0 x 22= 1. La valeur de la fonction objectif en cette solution est : 8. Le nombre de pivots effectues est : 2.
Vous pourrez modifier la conclusion en :
L’assignation est 11, 22, qui réalise une performance de 8.
Le certificat d’optimalité est obtenu en affectant les poids suivants sur les agents aches: a 1=3, a 2=5, t 1=0, t 2=0. et les t^
Une fois votre algorithme réalisé, testez-le sur des valeurs aléatoires de assign[t][t]. Quelle taille t de problèmes peut-on atteindre ? Comparer avec le simplexe sur des programmes aléatoires.
Résoudre les questions c. et d. de l’exercice 5 de la fiche de TD.
- Exercice 13 - Le cas non borné.
Lorsque votre algorithme ne trouve pas de candidat pour le pivot sortant, le problème est non borné. Plutot qu’un simple message Problème non borné, retourner un ensemble de solutions dépendant d’un paramêtre t qui certifie bien que le problème est non borné. Par exemple dans le programme suivant
Maximiser x1 +x2 Sous x1 −x2 ≤1 −x1 +x2 ≤1 x1 , x2 ≥0 La solution pourrait être :
Problème non borné lorsque x1 = t et x2 = t, avec t >= 0
- Exercice 14 - Certificat d’optimalité.
Lorsque votre algorithme du simplexe trouve une solution optimale, vous pouvez justifier son opti- malité grace au dual, ou ce qui est équivalent par une combinaison linéaire de contraintes. En plus de la solution optimale, retourner cette combinaison. Par exemple :
Maximiser x1 +x2 Sous 2x1 +x2 ≤3 x1 +2x2 ≤2 x1 , x2 ≥0 La solution pourrait être :
La solution optimale est x1 = 4/3, x2 = 1/3 pour une valeur de 5/3.
Le certificat d’optimalité est : 1/3 contrainte 1 + 1/3 contrainte 2, pour un résultat de x1 + x2 ≤ 5/3
- Exercice 15 - Réseau de transport.
Modifier votre algorithme du TP3 sur le problème d’affectation afin de résoudre les problèmes de réseaux de transport.
