Ce document traite de la programmation linéaire d'un nombre entier. Il définit ce concept, donne des exemples d'applications et présente des méthodes pour formuler ce type de problèmes sous forme de programmes mathématiques.
0 évaluation0% ont trouvé ce document utile (0 vote)
888 vues27 pages
Ce document traite de la programmation linéaire d'un nombre entier. Il définit ce concept, donne des exemples d'applications et présente des méthodes pour formuler ce type de problèmes sous forme de programmes mathématiques.
Ce document traite de la programmation linéaire d'un nombre entier. Il définit ce concept, donne des exemples d'applications et présente des méthodes pour formuler ce type de problèmes sous forme de programmes mathématiques.
Ce document traite de la programmation linéaire d'un nombre entier. Il définit ce concept, donne des exemples d'applications et présente des méthodes pour formuler ce type de problèmes sous forme de programmes mathématiques.
La programmation mathmatique recouvre un ensemble de techniques doptimisation
sous contraintes qui permettent de dterminer dans quelles conditions on peut rendre maximum ou minimum une fonction objectif Z(Xj ) de n variables Xj lies par m relations ou contraintes Hi(Xj ) 0. De nombreux problmes de lentreprise peuvent sexprimer en termes doptimisation contrainte, aussi rencontre t-on de multiples applications de la programmation mathmatique et ceci dans pratiquement tous les domaines de la gestion.
La gestion de production est le domaine ou ces applications sont les plus nombreuses. On citera entre-autres :
Llaboration de plans de production et de stockage.
Le choix de techniques de production. Laffectation de moyens de production. La dtermination de la composition de produits.
Les applications sont galement nombreuses dans le domaine du marketing avec, en
particulier :
Le choix de plans-media. La dtermination de politiques de prix. La rpartition des efforts de la force de vente. La slection des caractristiques du produit.
On citera encore des applications en matire financire (choix de programmes
dinvestissements), en matire logistique (gestion des transports) et en matire de gestion des ressources humaines (affectation de personnel). Si les applications de la programmation mathmatique sont aussi nombreuses, on doit lattribuer en grande partie la souplesse de ses techniques en ce qui concerne leur formulation mais aussi la relative simplicit des mthodes de rsolution utilisables dans les cas les plus courants et pour lesquelles existent des programmes informatiques largement rpandus.
Parmi les techniques de programmation mathmatique la programmation linaire est la plus
classique.
[2] PROGRAMMATION LINEAIRE DUN NOMBRE ENTIER
I. DEFINITIONS ET EXEMPLES Programmation linaire dun nombre entier La programmation linaire dun nombre entier par dfinition est un Modle mathmatique dans lequel la fonction objectif et certaines (ou toutes les) variables sont restreintes des valeurs entires.
Applications
Choix dune solution optimale parmi un ensemble fini dalternatives. Peuvent gnralement se formuler comme des programmes en nombres entiers , cest ce quon appelle Optimisation combinatoire qui est Loptimisation de lusage de ressources limites dans les domaines militaire, industriel, agricole, conomique, ... Existence dalgorithmes trs efficaces pour rsoudre des problmes trs difficiles en pratique, mais solveurs de plus en plus performants.
Dans le cas ou les contraintes et les variables sont toutes deux entiers, on parle de programmation linaire en nombre entiers (ou simplement programmation en nombres entiers - IP en anglais). Dans le cas ou seulement un de ces aspects sexprime en nombre entiers, ou mme seulement certaines des variables, on parle de programmation linaire mixte (MP en anglais).
Exemple.1 (Slection de projets) : 5 projets doivent tre valus sur 3 ans. Etant donn le cot de chaque projet pour chaque anne et le profit obtenu par lexcution dun projet, dcider quels projets excuter sans dpasser le budget disponible pour chaque anne.
[3] Variables
Xj = 1 si le projet j est slectionn
0 sinon.
Formulation
Exemple.2 (Problme avec cots fixes) : 3 compagnies de tlphone offrent des tarifs diffrents pour les communications longue distance.
- Trouver le plan dabonnement optimal pour 200 minutes de communication / mois.
Variables
xi : minutes de communication avec la compagnie i
Yi = 1 si un abonnement est pris auprs de la compagnie i;
0 sinon.
Formulation
[4] Exemple.3 (Voyageur de commerce): Un reprsentant doit visiter n villes une et une seule fois, et revenir sa ville de dpart, en minimisant le cot total du trajet.
Le problme revient trouver un tour de cot minimum passant une et une seule fois par chacun des noeuds dun graphe. Le cot dutilisation de larc (i, j) est Cij .
Variables
Xij = 1 si larc (i, j) appartient au tour optimal,
0 sinon.
Contraintes
Problme : apparition possible de sous-tours
Formulation
[5] Contraintes disjonctives Dans un programme linaire, toutes les contraintes doivent tre satisfaites simultanment. Parfois, il est ncessaire de modliser le fait quune contrainte parmi un ensemble doit tre satisfaite. Si les contraintes de lensemble sont mutuellement incompatibles, on parle de contraintes disjonctives.
Exemple.4 (Contraintes disjonctives) :Une machine est utilise pour 3 tches diffrentes. Pour chaque tches i, une dure pi et une date limite di sont donnes, ainsi quune pnalit par jour de retard.
- Comment arranger les tches sur la machine pour minimiser la pnalit totale ? - Variables : xi : temps de fin de la tche i (xi pi). - Deux tches i et j ne peuvent tre excutes simultanment, donc xi xj + pi ou xj xi + pj .
Pour introduire ces contraintes disjonctives, nous faisons appel des variables binaires auxiliaires :
yij = 1 si i prcde j 0 si j prcde i
- Contrainte de date limite : introduction dune variable dcart non restreinte
xi + si = di . - Une pnalit apparat uniquement si si < 0. - Remplacement par deux variables non ngatives reprsentant les parties positive et ngative.
[6] Objectif : min z = 19 s 1 + 12 s 2 + 34 s
Formulation
II. Complexit des problmes et efficacit des algorithmes
La thorie de la complexit sattache classifier les problmes selon leur difficult.
Un problme est facile sil existe un algorithme efficace pour le rsoudre.
Exemples de problmes faciles : programmation linaire, affectation, plus courts chemins, . . . Un problme est difficile sil appartient la classe des problmes NP-complets, pour lesquels il est peu probable de trouver un jour un algorithme efficace. Exemple de problmes difficiles : programmes en nombres entiers, voyageur de commerce, . . .
Algorithmes efficaces et explosion combinatoire
Lefficacit dun algorithme est mesure par lordre de grandeur du nombre doprations lmentaires quil effectue en fonction de la taille des donnes ; Un algorithme sera efficace si le nombre doprations lmentaires est polynomial (i.e. born suprieurement par un polynme) en la taille de problme.
[7] Autre perspective : supposons que trois ordinateurs M1, M2 et M3 effectuent respectivement 10000, 20000 et 40000 oprations par seconde.
Quelle taille maximum de problme n peut-on rsoudre en une minute par des algorithmes effectuant respectivement n, n 2, n 3 et 2 n oprations ?
III. Problmes polynomiaux
1. Le problme daffectation
Cest un Exemple de problme combinatoire pour lequel il existe un algorithme efficace.par
dfinition :
La meilleure personne pour chaque tche.
n personnes doivent effectuer n tches. Un cot cij est associ laffectation de la personne i la tche j.
Formulation
- Proprit : la relaxation linaire du problme est toujours entire.
- Algorithme : mthode hongroise.
Exemple.5 (problme daffectation) : Un pre propose 3 travaux ses enfants : tondre la
pelouse, peindre le garage et laver la voiture. Il demande chaque enfant combien il voudrait tre pay pour chaque travail.
2. Soustraire ce prix de chaque ligne et slectionner le prix minimum dans chaque
colonne.
Tondre Peindre Laver
Med 6 1 0 9 Karim 0 6 1 9 Tarik 2 4 0 8 0 1 0
3. Soustraire ce prix de chaque colonne.
Tondre Peindre Laver
Med 6 0 0 9 Karim 0 6 1 9 Tarik 2 4 0 8 0 1 0
- Les "0" en bleu donnent une affectation admissible optimale.
- Loptimalit est assure par la valeur des variables duales (en rouge). - Nombre doprations : O(n 2 ). - Il arrive que les valeurs nulles du tableau ne permettent pas de trouver de solution admissible.
[9] 4. Slectionner un nombre minimum de lignes et colonnes couvrant tous les 0.
5. Slectionner le plus petit lment non couvert, le soustraire tous les lments non couverts et lajouter aux intersections.
6. Rpter jusqu trouver une solution admissible.
2. Modle de transport
Le modle de transport est un produit doit tre transport de sources (usines) vers des destinations (dpts, clients).
Lobjectif est de dterminer la quantit envoye de chaque source chaque
destination en minimisant les cots de transport. Les cots sont proportionnels aux quantits transportes. Les contraintes doffre sont limites aux sources et de demande satisfaire aux destinations.
Exemple.6 (modle de transport) : Une firme automobile a trois usines Alger, Oran et Bejaia, et deux centres de distribution Allemagne et France.
Les capacits des trois usines sont de 1000, 1500 et 1200 respectivement, et les demandes aux centres de distribution sont de 2300 et 1400 voitures.
[10] Cots : Allemagne France Alger 80 215 Oran 100 108 Bejaia 102 68
[11] Variantes Le modle de transport nest pas limit au transport de produits entre des sources et destinations gographiques.
Exemple .7 (Maintenance dquipements) : Une scierie prpare diffrents types de bois sur base dun plan hebdomadaire.
Pour satisfaire la demande, dpendant du type de bois, la scierie utilise un nombre donn de lames. Pour satisfaire la demande, deux possibilits : acheter une lame ($12) ; faire aiguiser la lame (service express : $6 en une nuit, sinon $3 en 2 jours). Demande :
Modle de transport
8 sources : achat de nouvelles lames (offre = demande totale), 7 jours de la semaine (offre = nombre de lames utilises). 8 destinations : 7 jours de la semaine (demande = nombre de lames utilises) + surplus de lames non achetes / Aiguises (demande = nombre total de lames).
[12] Algorithme pour le problme de transport
Bas sur lalgorithme du simplexe en tenant compte de la structure du problme.
1. Dtermination dune solution de base admissible. 2. Dtermination de la variable entrant en base. 3. Dtermination de la variable sortant de base.
Exemple.8 (Algorithme pour le problme de transport) :
1. Dtermination dune solution de base admissible
Heuristiques "gloutonnes", pas besoin de mthode des deux phases.
Variantes : a. Coin Nord-Ouest b. . Mthode des moindres cots c. . Approximation de Vogel (VAM)
a. Coin Nord-Ouest : Partir du coin suprieur gauche du tableau.
Allouer le plus possible la
cellule courante et ajuster loffre et la demande ; Se dplacer dune cellule vers la droite (demande nulle) ou le bas (offre nulle) ; Rpter jusquau moment o toute loffre est alloue.
b. Moindres cots : Slectionner la cellule de cot minimum.
Allouer le plus possible la cellule
courante et ajuster loffre et la demande ; Slectionner la cellule de cot minimum ayant une demande et une offre non nulles ; Rpter jusquau moment o toute loffre est alloue.
[13] c. Approximation de Vogel (VAM) :
Pour chaque ligne (colonne) avec une offre (demande) non-nulle, calculer une pnalit gale la diffrence Entre les deux cots les plus petits dans la ligne (colonne) ; Slectionner la ligne ou colonne avec la pnalit maximale et slectionner la cellule de cot minimum dans La ligne ou colonne ; Allouer le plus possible la cellule courante ; Lorsquil ne reste quune ligne ou colonne : moindre cots.
Formulation
Problme dual
Adaptation du simplexe
Critre doptimalit :
Complmentarit :
Trois tapes : 1. dtermination des variables duales (multiplicateurs) ; 2. vrification du critre doptimalit et dtermination de la variable entrante ; 3. dtermination de la variable sortante pour prserver ladmissibilit et pivotage.
[14] Dtermination des variables duales 1. m + n - 1 quations m + n inconnues : fixer u1 = 0. 2. Rsoudre rcursivement le systme
Exemple.9 (Dtermination des variables duales) :
2. Vrification du critre doptimalit et dtermination de la variable entrante
3. Dtermination de la variable sortante pour prserver ladmissibilit et pivotage
Objectifs : 1. loffre et la demande doivent continuer tre satisfaites ; 2. les quantits transportes doivent rester positives.
Mthode : 1. construction dun cycle parcourant des variables en base en partant de et revenant la variable entrante ; 2. dplacement le long de lignes et colonnes en alternant ajout et retrait dune mme quantit.
[15] Extension du modle de transport : il est parfois ncessaire (ou moins cher) dutiliser des noeuds intermdiaires pour le transport. Deux usines P1 et P2 servent 3 vendeurs D1, D2 et D3, via deux centres de transit T1 et T2.
[16] Noeuds de transbordement : arcs entrants et sortants. offre/demande = offre/demande originale + buffer Les noeuds de transbordement sont la fois sources et destinations pour le problme de transport. Buffer : quantit ncessaire pour transporter toute la demande travers le noeud de transbordement. Dans notre exemple : B = 2200.
IV. Mthodes de Branch-and-Bound
1. Branch-and-Bound pour les problmes en nombres entiers
Rsoudre un programme linaire consiste dterminer les valeurs des variables qui permettent doptimiser la fonction conomique. Il existe diverses techniques de rsolution parmi lesquelles les mthodes de Branch-and-Bound "Diviser pour rgner" qui sont des mthodes bases sur une numration "intelligente" des solutions admissibles dun problme doptimisation combinatoire, utilise toute la puissance de la programmation linaire pour dterminer de bonnes bornes.
Ide : prouver loptimalit dune solution en partitionnant lespace des solutions.
On appelle relaxation linaire dun programme linaire en nombres entiers le
programme linaire obtenu en supprimant les contraintes dintgralit sur les variables.
Programme en nombres entiers
Relaxation linaire
[17] Proprits de la relaxation linaire
La valeur de la solution optimale de LP est une borne suprieure sur la valeur de la
solution optimale de P. La valeur dune solution admissible de P fournit une borne infrieure sur la valeur de la solution optimale de P. Si la solution optimale de LP est entire (donc admissible pour P), elle est galement la solution optimale de P.
Branchement
Si la solution de LP nest pas entire, soit xi une variable prenant une valeur fractionnaire xi*dans la solution optimale de LP. Le problme peut tre divis en deux sous-problmes en imposant
xi [xi* ] ou xi [xi* ]+ 1
o x i* est le plus grand entier infrieur xi*.
La solution optimale de P est la meilleure des solutions optimales des deux
problmes
Exemple.10 (Branch-and-Bound) :
[18] La solution de LP1 est une solution admissible de P et donc z = 23 est une borne infrieure sur la valeur de la solution optimale de P. Le noeud correspondant peut tre limin vu quune solution entire optimale satisfaisant x1 3 a t trouve (solution de P1).
[19] - La valeur de la solution de LP, z = 23:75 est une borne suprieure sur la valeur de la solution optimale de P.
- Vu que tous les coefficients sont entiers, on peut en dduire que la valeur de la solution optimale de P est infrieure ou gale 23.
- La solution de P1 est donc optimale pour P.
Rgles de branchement
Il ny a pas de rgle gnrale pour le choix de la variable de branchement et de la branche
examiner en premier. Ce choix peut avoir un impact important sur le nombre de nuds examiner dans larbre de branch-and-bound. Exemple : branchement dabord du ct .
[20] 2. Branch-and-bound pour le voyageur de commerce
Formulation (rappel)
- Si on retire les contraintes dlimination de sous-tours, on obtient le problme
daffectation. - Cette relaxation a une solution entire qui peut tre obtenue par exemple avec la mthode hongroise. - Le branchement est effectu de manire liminer les sous-tours. - La valeur de la solution optimale du problme daffectation (AP) est une borne infrieure sur la valeur de la solution optimale du TSP. - Le cot dun tour fournit une borne suprieure sur la valeur de la solution optimale. - Si la solution optimale de AP est un tour (i.e. sans sous-tour), elle est galement la solution optimale du TSP.
[21] Si un sous-tour apparat :
Dans une solution admissible, un de ces arcs doit tre absent, donc
- Chacune de ces conditions va correspondre une branche de larbre de branch-and-
bound.
Exemple.11 (Voyageur de commerce) :
Solution du problme daffectation
[22] 3. Branch-and-bound pour les contraintes disjonctives
On peut utiliser une approche classique pour les problmes en nombres entiers en introduisant des variables supplmentaires (voir formulation en dbut de partie). On peut galement prendre comme relaxation le problme sans les contraintes disjonctives, et brancher sur les contraintes non satisfaites.
Exemple .12 (Contraintes disjonctives) : Une machine est utilise pour 3 tches diffrentes. Pour chaque tches i, une dure pi et une date limite di sont donnes, ainsi quune pnalit par jour de retard.
- Comment arranger les tches sur la machine pour minimiser la pnalit totale ?
Relaxation du problme
Branchement sur xi xj + pi ou xj xi + pj . Solution de la relaxation : ordonnancement au plus tt.
