Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob.

du transport et d’affectation

Recherche opérationnelle
Z. Bahou, EMI

2019/2020

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Plan du cours:
▪ Introduction générale à la recherche opérationnelle.
▪ Programmation linéaire.
‐ Algorithme du simplexe.
‐ Dualité.
‐ Post-optimisation.
‐ Problème du transport.
‐ Problème d’affectation.
▪ Optimisation dans les réseaux.
‐ Notions élémentaires de la théorie des graphes.
‐ Problème de l’arbre de poids minimal.
‐ Problèmes de cheminements optimaux dans un réseau.
‐ Problème central d’ordonnancement. (MPM, PERT, CPM) Problèmes de flot.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

L’optimisation
• L'optimisation ou la recherche de l’optimum est un souci permanent au sain des organisations.
Plus les entreprises grandissent, plus les problèmes de gestion se multiplient et se compliquent : la
gestion de production, la gestion du stock, la gestion des flux financiers, la gestion des réseaux ou de
circulation des biens et de services...
• La résolution de ces problèmes nécessite des efforts tant au niveau de la recherche de la solution
optimale qu’au niveau de la modélisation .

►Le souci N° 1 au sain des firmes est souvent du comment maximiser le profit?, minimiser
les coûts?

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Recherche Opérationnelle
• « Outil mathématique de modélisation et d’optimisation. Il permet de trouver une solution
optimale ou bien une solution qui S’approche le plus possible de l’optimum »

• On peut définir la Recherche Opérationnelle (RO) comme l'ensemble des domaines

scientifiques, des outils et des problèmes touchant aux questions d'ordre décisionnel (dit aussi
stratégique) ou d'optimisation de systèmes complexes. L'expression systèmes complexes est à
prendre ici au sens le plus littéral du terme, c'est-à-dire difficile à comprendre pour un individu
sans l'aide d'un modèle ou d'un ordinateur.

• Les problèmes sont rendus complexes dans la RO par : leur dimension qui peut être
importante, mais surtout par leur structure qui peut-être par exemple combinatoire,
stochastique etc.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Recherche Opérationnelle
▪ On peut citer en exemple pertinent :
‐ la recherche d'un itinéraire sur une carte « Comment aller le plus vite
ou avec le moindre coût de Rabat à Berlin, en voiture? ».
‐ l'ordonnancement des tâches à accomplir en usine « Comment
ordonnancer les taches d’un projet en fonction de la main d’ œuvre, tout
en minimisant sa durée? ».
‐ la décision stratégique d'investissement d'une entreprise sur un
marché concurrentiel « Comment investir ses 10000 DH d’économie
afin de maximiser le profit obtenu après deux ans? » .

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

La RO en entreprise
‐ Pour l'entreprise, la RO constitue un outil informatique pour aider à la gestion de l'entreprise.
‐ La RO se retrouve donc sur une même ligne d'outils que les outils de comptabilité, de gestion de Base de données
ou de gestion des systèmes d'information.
‐ La RO utilise ces diverses sources de données pour aider aux décisions dans l’entreprise.
‐ Les grands groupes industriels ont quasiment toujours un département RO. Il est la plupart du temps intégré au
pôle R&D mais il est parfois intégré dans des pôles plus décisionnaires, comme les conseils de décisions
stratégiques.
Les grandes problématiques de la RO
- network design (conception de réseaux de télécommunication) - ordonnancement (domaine à la limite
- transport problématique/problème...)
- localisation (plant location) - optimisation financière
- micro-électronique (VLSI design) - chaîne logistique (supply chain) et création de lots (lot-
- bio-informatique, applications médicales sizing)
- productique (job-shop, flow-shop,...) - optimisation « durable »
- et de nouvelles problématiques se créent régulièrement.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Les domaines de la RO
Il est difficile de classer ou de lister exhaustivement tous les domaines de la RO. D'autant que ces domaines ont tous une
réalité par eux-mêmes et on peut se demander quelle partie de ces domaines est dans la RO ou pas.
▪ Aspect continu : ▪ Aspect discret ou combinatoire :
‐ Optimisation continue. ‐ Théorie des graphes
‐ PL. ‐ Algorithmique, algorithmique des graphes
‐ Théorie des jeux continues. ‐ Programmation dynamique
‐ Optimisation stochastique. ‐ Optimisation combinatoire exacte ou à garanti
‐ Programmation semi-définie. d'approximation
‐ Simulation continue. ‐ Optimisation combinatoire heuristique
‐ Processus markovien, la file d'attente,...
‐ Simulation discrète
‐ Ordonnancement
‐ PLNE, approches polyédrales
‐ Programmation quadratique
‐ Programmation par contraintes
‐ Théorie des jeux algorithmique

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Les outils de la RO
Il existe de nombreux outils logiciels disponibles commercialement ou libres pour résoudre des problèmes précis
ou des problèmes plus généraux.
▪ Logiciels d'optimisation (interactif ou modeleur)
‐ Solveur linéaire (cplex, xpress, glpk, gurobi, excel...)
‐ Solveur entier (cplex, xpress, glpk, gurobi,...)
‐ Solveur quadratique (cplex, xpress)
▪ Logiciel de simulation
‐ Système de file d'attente (qnap, simula,...)
‐ Système continu
▪ Logiciel d'aide à la décision :
‐ Outils à interface graphique de planification (SAP, produit ilog)...
‐ Outils d'analyse des problèmes (probas)...
▪ Des API (souvent C++ ou java) d'algorithmes et de Structures de données
‐ Des frameworks permettant d'utiliser les solveurs dans un processus algorithmiques plus complexes. Par
exemple les méthodes de coupes ou de générations de colonnes : Scip, Concert technology (d'ILOG),...

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

La pratique de la RO
• Découvrir le problème : En général, la découverte du sujet passe par des discussions orales, souvent contradictoires avec les
différents intervenants. Il s'agit de cerner la/les questions au cours de réunion et de discussion autour d'un texte qui devient
vite un cahier des charges du projet.
• Modéliser : est un aspect très important et primordial. Les problèmes que l’on traite émanant de situations concrètes. Il
s’agit alors de définir la situation en termes mathématiques et dans un souci d’efficacité de schématiser (modéliser) le problème.
• Evaluer la complexité: Etape évidemment nécessaire, il faut étudier la complexité du problème obtenu après modélisation. C'est
le moment de se rendre compte si le problème traité est difficile ou pas, si un outil classique est utilisable etc.
• Choisir un outil : Le choix de l'outil signifie à la fois choisir un algorithme théorique mais aussi rechercher
existe un outil informatique disponible : solveurs, architectures objets d'algorithmes, API d'algorithmes,...

• Expérimentation et retour d'expérience

• Intégration et vie logicielle : Etape nécessaire pour l'entreprise, il faut intégrer l'outil dans le cadre des outils de l'entreprise.
L'interfaçage avec les SI de l'entreprise n'est pas une chose simple, ni d'ailleurs l'obligation fréquente de permette une certaine
ergonomie de l'outil qui ne s'adresse pas à un public initié à la RO ou au math : prévoir un manuel d'utilisateur, des formations
etc.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Conclusion

La RO est un domaine transversal entre recherche et ingénierie, entre maths et

informatique, entre théorie pure et applications. On dit qu'elle traite les
problèmes de la société, ce qui la montre utile à tous : en effet, il est toujours
intéressant d'avoir un système mieux géré, plus économe sur les ressources, plus
écologique,... tout en respectant les contraintes naturelles du droit du travail et le
respect des conditions de travail.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Introduction à la programmation linéaire

Un outil qui permet de :
• Modéliser
• Résoudre
toute une classe de problèmes d’optimisation.
La programmation linéaire constitue l’origine de l’optimisation mathématique moderne. Son
étude a été menée par George Bernard Dantzig à partir de 1947. L’algorithme du simplexe « le
plus connu des méthodes de résolution », que nous présentons dans le prochain chapitre, est
considéré comme un des dix algorithmes les plus importants du vingtième siècle. C’est la
première fois qu’un problème avec contraintes d’inégalité a été résolu.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Introduction à la programmation linéaire

• La programmation linéaire est un outil très puissant de la recherche opérationnelle. C’est un
outil générique qui peut résoudre un grand nombre de problèmes. En effet, une fois un problème
modélisé sous la forme d’´équations linéaires, des méthodes assurent la résolution du problème
de manière exacte.

• On distingue dans la programmation linéaire, la programmation linéaire en nombres réels, pour

laquelle les variables des équations sont dans IR+ et la programmation en nombres entiers, pour
laquelle les variables sont dans IN. Bien entendu, il est possible d’avoir les deux en même
temps. Cependant, la résolution d’un problème avec des variables entières est nettement plus
compliquée qu’un problème en nombres réels.

• Un programme linéaire est la maximisation ou la minimisation d’une fonction linéaire

sous des contraintes linéaires.
Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]
Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Modélisation

En Recherche Opérationnelle (RO), modéliser un problème consiste à identifier:

• les variables intrinsèques (inconnues)

• les différentes contraintes auxquelles sont soumises ces variables
• l'objectif visé (optimisation).

Dans un problème de programmation linéaire (PL) les contraintes et l'objectif sont

des fonctions linéaires des variables. On parle aussi de programme linéaire.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Problème de production
Un fabricant produit 2 types de yaourts à la fraise A et B à partir de Fraise, de Lait et de
Sucre. Chaque yaourt doit respecter les proportions suivantes de matières premières.
A B

Fraise 2 1
Lait 1 2
Sucre 0 1

On dispose de 800 Kg de Fraises, 700 Kg de Lait et 300 Kg de sucre.

La vente de 1 Kg de yaourts A et B rapporte respectivement 4 DH et 5 DH.
Le fabricant cherche à maximiser son profit.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Modélisation

• Surquelles quantités peut-on travailler ?

• Que cherche-t-on à optimiser ?
• Quelles sont les contraintes du problème?

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Modélisation

• Sur quelles quantités peut-on travailler ?

o les quantités de yaourts A et B produites
o On parle de variables de décision
o On les notera x et x
A B

• Que cherche-t-on à optimiser ?

• Quelles sont les contraintes du problème ?

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Modélisation
• Sur quelles quantités peut-on travailler ?
• Variables : xA et xB
• Que cherche-t-on à optimiser ?
o Le profit z
o Calculé à partir de xA et xB
o On parle de fonction objectif
o z = 4x + 5x
A B

• Quelles sont les contraintes du problème ?

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Modélisation
• Sur quelles quantités peut-on travailler ?
• Variables : xA et xB
• Que cherche-t-on à optimiser ?
• max z = 4xA + 5xB
• Quelles sont les contraintes du problème ?
o Première contrainte : 800 Kg de fraises disponibles
o la quantité utilisée dépend de la production : 2xA + xB
o 2xA + xB ≤800

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Modélisation
• Sur quelles quantités peut-on travailler ?
• Variables : xA et xB
• Que cherche-t-on à optimiser ?
• max z = 4 x A + 5x B
• Quelles sont les contraintes du problème ?
2xA+ xB ≤800 (fraises)
xA+ 2xB ≤ 700 (lait)
xB ≤ 300 (sucre)
xA, xB ≥ 0 positivité !

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Notre premier programme linéaire

max 4xA+ 5xB

2xA+ xB ≤ 800
xA+ 2xB ≤ 700
xB ≤ 300
xA, xB ≥0

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Problème de transport
Approvisionner au moindre coût les clients à partir des usines.
Usines (i Є I ) Rabat Tanger Agadir
Productions (pi ) 25 15 20

Clients (j Є J ) Casablanca Oujda Rabat Marrakech

Demandes (dj ) 20 12 9 14

Prix/unité (ci ,j ) Casablanca Oujda Rabat Marrakech

Rabat 26 19 0 4
Tanger 12 2 20 24
Agadir 19 30 24 28

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Modèle du problème de transport

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Mise en forme d’un programme linéaire

▪ Détecter et comprendre le problème (phase préscientifiques)
‐ que doit-on faire? Quel est le vrai problème à résoudre ?
▪ Identifier les variables de décision
‐ variables régissant la situation à modéliser
‐ variables réelles ( ou entières : Programmation linéaire entière)
▪ Préciser la fonction objectif
‐ fonction mathématique composée des variables de décision
‐ fonction linéaire
▪ Préciser les contraintes du problème
‐ paramètres limitant la réalisation du modèle
‐ équations ou inéquations composées des variables de décision
Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]
Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Conclusion
La programmation linéaire est la technique sans doute la plus connue et dont le succès a
largement contribué au succès initial de la recherche opérationnelle. Elle est la méthode de
référence pour les entreprises notamment dans le domaine bancaire, forestier, industriel, du
transport et de la télécommunication.
Un programme linéaire est un problème d’optimisation consistant à maximiser ou minimiser
une fonction « objectif » linéaire de plusieurs variables de décision (fonction économique)
soumise à un ensemble de contraintes exprimées sous forme d’équations linéaires et/ou
d’inéquations linéaires.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Exercices d’application « modélisation »:

Exercice 1

Un vendeur de matériel informatique a voulu liquider son stock des usb et des
souris sans fil, il a donc décidé de les grouper par lots de vente.
— Le premier lot contient 5 souris et 1 usb, et se vend à 4 dollars.
— Le deuxième lot contient 1 souris et 10 usb, et se vend à 6 dollars.
Il dispose au total de 60 souris et 110 usb.
Quelle est la répartition la plus avantageuse pour lui, entre les deux types de lots ?

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Exercices d’application « modélisation »:

Exercice 1 Correction

x1 = le nombre de lots du premier type

x2 = le nombre de lots du deuxième type

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Exercices d’application « modélisation »:

Exercice 2
On donne ci-après les caractéristiques de 3 gaz : A, B, C :

A B C
Teneur en souffre (g/m3) 6 2 4
Prix (Dh/m3) 10 25 15
Pouvoir calorifique (kcal/m3) 1 000 2 000 1 500

Réaliser le mélange qui donne le plus grand pouvoir calorifique en respectant les contraintes
suivantes :
• La teneur en souffre doit être au plus de 3 g/m3,
• Le prix ne doit pas dépasser 22 Dh/m3.
• Le volume du mélange ne doit pas dépasser 1m3

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Exercices d’application « modélisation »:

Exercice 2 Correction
Identification des variables :
Le pouvoir calorifique dépend des volumes de gaz utilisés pour produire le mélange. Appelons :
x1 = le volume de gaz A utilisé pour produire 1 m3 de mélange
x2 = le volume de gaz B utilisé pour produire 1 m3 de mélange
x3 = le volume de gaz C utilisé pour produire 1 m3 de mélange
L’objectif poursuivi consiste à choisir le mélange qui a le plus grand pouvoir calorifique z :
Max z = 1000x1 + 2000x2 + 1500x3
Contraintes :
Les ingrédients x1, x2 et x3 d’un mélange réalisable doivent vérifier les conditions suivantes :
— Teneur en soufre : elle doit être au plus de 3 g/m3 . Ce qui s’écrit : 6x1 + 2x2 + 4x3 ≤ 3
— Prix du mélange : il ne doit pas dépasser 22 Dh/m3. Ce qui s’écrit : 10x1 + 25x2 + 15x3 ≤ 22
— Volume du mélange : il est de 1 m3. Ce qui s’écrit : x1 + x2 + x3 = 1

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Exercices d’application « modélisation »:

Exercice 3
Un étudiant veut décider quel type d’aliments manger de manière à minimiser ses
dépenses, tout en conservant une nourriture équilibrée. 5 types d’aliments F1, . . . ,
F5 sont disponibles, chacun contenant une quantité donnée d’ énergie (kcal), de
protéines (g) et de calcium (mg). L’étudiant veut que le menu à établir contienne
une quantité minimum (donnée) d’énergie, une quantité minimum de protéines et
une quantité minimum de calcium. Le prix par gramme de chaque type d’aliment
est donné. De plus, on impose une borne supérieure sur la quantité qu’on mange
de chaque aliment. Formuler le problème comme un programme linéaire.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Exercices d’application « modélisation »:

Exercice 3 Correction
Notons :
‐ ei = l’énergie contenue dans l’aliment Fi
‐ pi = les protéines contenues dans l’aliment Fi
‐ ci = le calcium contenu dans l’aliment Fi
‐ E = quantité minimale d’énergie nécessaire
‐ P = quantité minimale de protéines nécessaire
‐ C = quantité minimale de calcium nécessaire
‐ Ui est la borne supérieure sur la quantité de
l’aliment Fi
‐ wi est le prix par gramme de l’aliment Fi
‐ Nous utilisons les variables suivantes :
xi = quantité de l’aliment Fi à manger

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Exercices d’application « modélisation »:

Exercice 4
Considérons le problème de transport suivant : une firme dispose de m entrepôts
et de n clients. Il faut livrer un certain produit des entrepôts vers les clients.
Notons Oi la quantité du produit stockée dans l’ entrepôt i, ∀ i = 1, . . . , m et dj
la quantité du produit demandée par le client j, ∀ j = 1, . . . , n. Le coût unitaire de
transport de l’ entrepôt i vers le client j est noté cij . La firme veut minimiser le
coût de transport total, en satisfaisant tous les clients. Donner une formulation de
ce problème sous forme de programme linéaire.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Exercices d’application « modélisation »:

Exercice 4 Correction

xij = quantité livrée au client j à partir de l’ entrepôt i

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Exercices d’application « modélisation »:

Exercice 5

Considérons le problème d’une commune au Maroc. Dans la commune, il y a I

quartiers, J écoles, et G classes dans chaque école (p.ex. 1ère – 6e primaire). Chaque
école j ∈ J à une capacité de Cjg étudiants pour la classe g ∈ G. Dans chaque
quartier i ∈ I, il y a Sig étudiants qui veulent aller en classe g ∈ G. La distance entre
le quartier i ∈ I et l’école j ∈ J est dij . Donner un programme linéaire, dont
l’objectif est d’envoyer tous les étudiants à la bonne classe, tout en minimisant la
distance totale parcourue par les étudiants.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Exercices d’application « modélisation »:

Exercice 5 Correction
xijg = nombre d’étudiants résidant dans le quartier i, qui vont à la classe g de l’école j.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Programmation linéaire
▪ Forme générale d’un programme linéaire. ▪ Formes matricielles classiques et convenions.
Notons par x = (x1, x2, ..., xn)T le vecteur des variables. b =
(b1, b2, ..., bm)T le second membre des contraintes, c = (c1, c2,
..., cn)T le vecteur coût ou profit associé aux variables et A la
matrice m × n des aij .

(1) : fonction objective.

(2) : m contraintes linéaires.
(3) : contraintes de positivité. La forme canonique avec des contraintes ≤ s’utilise dans la
représentation graphique, et la forme standard avec des
contraintes égalité s’utilise dans la résolution algébrique
Remarque : Ces formes ne servent qu’`a simplifier les représentations théoriques. Dans la réalité un problème linéaire peut
comporter des contraintes égalités ou inégalités.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Programmation linéaire Forme standard

Théorème (Equivalence des formes standard et
canonique). Tout programme linéaire peut s’écrire sous
forme standard et sous forme canonique.
Démonstration.– Une contrainte d’inégalité 𝒂𝒕 𝒙 ≤ 𝒃 peut
être transformée en égalité par l’introduction d’une
variable d’écart : 𝒂𝒕 𝒙 + 𝒔 = 𝒃 ; s ≥ 0
Forme matricielle
Exemple:
Forme canonique

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution graphique ❖ Interprétation graphique d'une contrainte

❖ Illustration sur un exemple Considérons la contrainte (1) : X + Y ≤ 200.

▪ La droite X + Y = 200 passe par les points (0,200) et (200,0) et
divise le plan en 3 parties :
– La partie au dessus de la droite correspond à l'ensemble des
points tels que X + Y > 200.
– La partie en dessous de la droite correspond à l'ensemble des
points tels que X + Y < 200.
– La partie sur la droite correspond à l'ensemble des points tels
que X + Y = 200.
❖
▪ La solution du problème sera en dessous ou sur la droite.
▪ Répéter ce raisonnement pour les 5 contraintes donne une
région convexe appelée un polyèdre. Cette région correspond à
l'ensemble des points réalisables.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire Polyèdre des contraintes

▪ Résolution graphique

❖ Interprétation graphique de l'objectif

Considérons l'ensemble des points

réalisables tels que :
350X + 300Y = 35000.
350X + 300Y = 52500.
350X + 300Y = 66100.
Ce sont les courbes de niveau de
l'objectif.
Jusqu'a quelle valeur peut-on aller ?

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire Courbes de niveau de l'objectif

▪ Résolution graphique

❖ Interprétation graphique de l'objectif

Considérons l'ensemble des points

réalisables tels que :
350X + 300Y = 35000.
350X + 300Y = 52500.
350X + 300Y = 66100.
Ce sont les courbes de niveau de
l'objectif.
Jusqu'a quelle valeur peut-on aller ?

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire Courbes de niveau de l'objectif

▪ Résolution graphique

❖ Interprétation graphique de l'objectif

Considérons l'ensemble des points

réalisables tels que :
350X + 300Y = 35000.
350X + 300Y = 52500.
350X + 300Y = 66100.
Ce sont les courbes de niveau de
l'objectif.
Jusqu'a quelle valeur peut-on aller ?

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire Courbes de niveau de l'objectif

▪ Résolution graphique

❖ Interprétation graphique de l'objectif

Considérons l'ensemble des points

réalisables tels que :
350X + 300Y = 35000.
350X + 300Y = 52500.
350X + 300Y = 66100.
Ce sont les courbes de niveau de
l'objectif.
Jusqu'a quelle valeur peut-on aller ?

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution graphique
❖ Détermination de la solution
‐ On déduit des courbes de niveau que la solution optimale est située dans un "coin" de la région
réalisable, a l'intersection de deux contraintes. Ce "coin" est appelé point extrême ou sommet.
‐ Si un problème a au moins une solution optimale, l'une d'entre-elles est un point extrême.
‐ Il est possible de trouver une solution optimale en énumérant tous les points extrêmes.
‐ Graphiquement, la solution est atteinte lorsque les contraintes (1) et (2) sont actives « saturés »
(i.e. satisfaites à l’égalité).
X + Y = 200
‐ Ceci donne le système à deux équations et deux inconnues suivant :ቊ
9X + 6Y = 1566
‐ Dont la solution est le point extrême (X*; Y *) = (122; 78).
‐ C'est la solution optimale du problème, qui donne la valeur optimale de 66100.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution graphique
❖ Remarque

Pour résoudre le problème linéaire dans le cas d’une minimisation, nous

allons appliquer une démarche équivalente, mais dans ce cas, nous
cherchons la droite (représentant la fonction économique) la plus
rapprochée de l’origine.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution graphique
❖ Plus d'une solution optimale
Si la fonction objectif avait été
300X + 300Y
Le point (122; 78) donne une valeur de 60000.
Le point (80; 120) donne une valeur de 60000.
Il n'y a pas de meilleur point et il y a en fait
beaucoup de points équivalents : (90; 110), (95;
105), (100; 100), . . . Il y en a une infinité !
Ceci arrive car les courbes de niveau sont
parallèles a la contrainte (1) « Active ». Toutes
les solutions optimales se retrouvent le long de
cette contrainte, entre deux points extrêmes.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Algorithme géométrique
1. Partir d’un point extrême x de la région réalisable
2. Déterminer une arête le long de laquelle l’objectif augmente.
S’il n’en existe pas, x est optimal, STOP
3. Se déplacer le long de l’arête jusqu’au point extrême y suivant.
S’il n’existe pas, le problème est
non borné, STOP
Sinon, poser x y et revenir
en 2

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Exercice résolution graphique
Exercice 1: Résoudre les problèmes suivants par la méthode graphique

(1) (2) (3)

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Exercice résolution graphique
Exercice 1: Correction

(1) (2) (3)

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Exercice résolution graphique
Exercice 2: On considère le programme linéaire suivant :

1◦ Tracer les contraintes et déterminer la région réalisable.

2◦ La région réalisable comporte combien de points extrêmes ?
3◦ Déterminer la solution optimale.
4◦ Quelles sont les contraintes qui sont satisfaites avec une stricte égalité ?
Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]
Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Exercice résolution graphique
Les contraintes qui sont satisfaites avec
Exercice 2: Correction une stricte égalité à l’optimum sont :

Ainsi, le point A vérifie

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Exercice résolution graphique
Exercice 3: On considère le programme linéaire suivant :

1◦ Déterminer la solution optimale avec la méthode graphique.

2◦ Est-ce que la solution optimale est unique ?

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Exercice résolution graphique
Exercice 3: Correction

Sur la figure, comme la droite z = 15 est tangente à la

deuxième contrainte, il n’y a pas de solution optimale
unique.
En effet, tout point situé sur cette droite entre les sommets
A et B est optimal.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Exercice résolution graphique
Exercice 4:
La direction d’une usine de meubles a constaté qu’il y a des temps morts dans chacun des départements de l’usine.
Pour remédier à cette situation, elle décide d’utiliser ces temps morts pour fabriquer deux nouveaux modèles de
bureaux, M1 et M2. Les temps de réalisation pour chacun de ces modèles dans les ateliers de sciage, d’assemblage et de
sablage ainsi que les temps libres dans chacun de ces ateliers sont donnés dans le tableau ci-dessous. Ces temps
représentent le nombre d’heures nécessaires à un homme pour effectuer le travail. Les profits que la compagnie peut
réaliser pour chacun de ces modèles sont de 300.DH pour M1 et de 200 DH pour M2.

La direction désire déterminer combien de bureaux de chaque modèle elle doit fabriquer pour maximiser son profit.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Exercice résolution graphique
Exercice 4: Correction
Posons x1 le nombre de bureaux du modèle M1 et x2
le nombre de bureaux du modèle M2. Les temps libres
de chaque département imposent des contraintes qu’il
faut respecter. La contrainte imposée par les temps
libres à l’atelier de sciage :𝑥1 + 2𝑥2 ≤ 20 les autres
2𝑥1 + 𝑥2 ≤ 22
contraintes sont :ቊ Il s’ajoute à ces
𝑥1 + 𝑥2 ≤ 12
contraintes des contraintes de non-négativité puisque 2𝑥1 + 𝑥2 = 22 𝑥1 = 10
le nombre de bureaux ne peut être négatif, on a donc : ቊ → ቊ
𝑥1 + 𝑥2 = 12 𝑥2 = 2
𝑥1 ≥ 0; 𝑥2 ≥ 0. La direction veut maximiser son
profit, c’est-à-dire maximiser la fonction :
𝑍 = 300𝑥1 + 200𝑥2
Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]
Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution graphique
Quelques définitions :

• Un polyèdre est un ensemble qui peut être décrit

comme P={x 𝝐 IR𝒏 | Ax ≥ b}
où A est une matrice m x n et b un vecteur de IR𝒎 .
• Note : l’ensemble admissible d’un programme
linéaire est un polyèdre.
• Un ensemble de la forme P={x 𝝐 IR𝒏 | Ax = b}
est un polyèdre en forme standard.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution graphique
Quelques définitions :
• Soient 𝑥1 ,…𝑥𝑘 des vecteurs de IR𝒏 , et
soient 𝜆1 ,…, 𝜆𝑘 des scalaires non négatifs
tels que σ𝒊,…𝝀 𝝀𝒊 =1; Le vecteur y=
σ𝒊,…𝝀 𝝀𝒊 𝒙𝒊 est une combinaison
convexe des vecteurs 𝑥1 ,…𝑥𝑘 .
• Soit P un polyèdre. Un vecteur x 𝝐 P est
un point extrême de P si on ne peut pas
l’exprimer comme combinaison convexe
de deux autres points de P.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution graphique
Quelques définitions :
• Une solution est dite réalisable si elle satisfait toutes les contraintes d’égalité et
que toutes les variables sont positives.
• Une solution optimale est une solution réalisable minimisant l’objectif.
• Si le polyèdre S est borné, tout point de S peut s’exprimer comme combinaison
linéaire convexe de points extrêmes.
• Si S est borné, il existe toujours une solution optimale qui est solution de base
réalisable.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Conclusion
Nous avons résolu des cas de programmes linéaires simples : deux variables et trois
ou cinq contraintes. Au fur et à mesure que le nombre des contraintes s’accroît, la
méthode graphique s’avère de plus en plus difficile à mettre en œuvre. Or, dans la
pratique, les programmes linéaires comportent plusieurs dizaines de variables et de
contraintes.
L’algorithme du simplexe est le plus utilisée des méthodes de résolution des
programmes linéaires. Il a été mis au point en 1948 par B. Dantzig. Depuis, cet
algorithme a fait l’objet de certaines d’articles scientifiques et a servi à la résolution
de nombreux modèles linéaires.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution algébrique « Simplexe »
Idées de base
– Solution optimale : sommet (point extrême).
– Idée fondamentale du simplexe : déplacement de sommet en sommet adjacent de manière à
améliorer la fonction objectif.
– Transformation des inégalités en égalités : forme standard du programme linéaire
– Les variables fixées à zéro sont appelées variables hors base et les autres variables en base.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire Base Solution Objectif Sommet

▪ Résolution algébrique « Simplexe » s1; s2; s3; s4 (0; 0) 0 A
Géométrie des solutions de base x1; s2; s3; s4 (4; 0) 20 F
s1; x1; s3; s4 (6; 0) -- Non réalisable
x1; x2; s3; s4 (3; 1.5) 21 E
Détermination de la solution de base optimale
– Partir d’une solution de base admissible et
passer à une solution de base voisine qui améliore
la valeur de l’objectif.
– Solution voisine : changement d’une variable en
base.
Prenons B = fs1; s2; s3; s4g ) x1 = x2 = 0; s1 = 24; s2 = 6; s3 – 3 étapes :
= 2; s4 = 1. 1. Détermination de la variable entrante.
– Cette solution de base réalisable correspond au 2. Détermination de la variable sortante.
sommet (0; 0).
3. Pivotage .
Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]
Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution algébrique « Simplexe »
Illustration sur un exemple

1. Le problème doit être mis sous forme standard.

Trois nouvelles variables (d‘écart), positives ou nulles
(une par contrainte) permettent d'obtenir des
contraintes égalité :

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire • Ce dictionnaire est une façon de représenter le point
▪ Résolution algébrique « Simplexe » réalisable x = (x1; x2; x3) = (0; 0; 0) avec f(x) = 0 et (e1;
Illustration sur un exemple e2; e3) = (5; 11; 8). Il s'agit d'un point extrême.
Dictionnaire initial • Les variables en base e1, e2, et e3 sont exprimées en
fonction des variables hors-base x1, x2, et x3.
• Dans le point courant, les variables hors-base sont
toujours nulles.
• z représente la valeur courante de l'objectif. Ses
coefficients (5,4, et 3) dans le dictionnaire sont appelés
les coûts réduits.
• S'il y a des coûts réduits positifs, on a intérêts à donner
une valeur positive aux variables hors-base associées afin
d'augmenter la valeur de z.
• Par exemple, ici, si on peut poser x1 = 1, alors z sera
augmenté de 5.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution algébrique « Simplexe » • Pour les trois contraintes, cela donne les inégalités
Illustration sur un exemple suivantes
Première itération

• La valeur maximale que peut prendre x1 est donc

qui correspond a la contrainte e1

• On décide d'augmenter la valeur de x1 et de laisser x2 • Donc si on pose x1 = 5/2 , alors on aura e1 = 0. x1 va

et x3 a zéro. Si on prend x1 trop grand, les variables en entrer en base et e1 va sortir de base.
base peuvent devenir négatives. Quelle valeur • Cette opération s'appelle un pivot et va mener au
maximale peut-on choisir ? second dictionnaire, et a un nouveau et meilleur
• On se sert des contraintes e1; e2; e3 ≥ 0 ou on isole x1 point extrême.
et on laisse x2 et x3 a zéro. Pour e1, cela donne :
Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]
Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire Première itération : Nouveau dictionnaire

▪ Résolution algébrique « Simplexe » Après avoir fait la même opération pour e3 et z, le pivot
Illustration sur un exemple est complété et on obtient le second dictionnaire
(première itération) :
Première itération : Pivot.
Il faut d'abord effectuer le pivot en exprimer la nouvelle
variable de base x1 en fonction de l'ancienne e1 :

Il faut ensuite écrire les autres lignes du dictionnaires

dans lesquelles on remplace x1 par sa nouvelle
expression. Pour e2, cela donne : qui correspond au point extrême x = (5/2; 0; 0) pour la
valeur courante de f(x) = 25=2, avec les écarts e = (0; 1;
1/2) (on a bien un point réalisable).

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire Deuxième itération

▪ Résolution algébrique « Simplexe »
Illustration sur un exemple
Première itération : Fin.
• Le coût réduit associe a la nouvelle
variable hors-base (e1) est forcément
négatif ou nul. Si on refaisait entrer cette
variable en base, on obtiendrait le point On fait entrer x3 en base. On a x3 = min (1; 5)
extrême précèdent. = 1. C'est e3 qui sort de base.
• Critère d‘ arrêt : Comme il reste des Le pivot donne x3 = 1 + x2 + 3e1 - 2e3.
coûts réduits positifs, cela signifie que l'on Ce qui permet d'obtenir le nouveau dictionnaire.
peut améliorer la valeur de f.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire Dégénérescence

▪ Résolution algébrique « Simplexe » Soit le dictionnaire
Illustration sur un exemple
Deuxième itération : Nouveau dictionnaire et fin

Si on choisit x3 comme variable entrante, alors on aura

𝟏 𝟏 𝟏 𝟏
x3 = min{ , , }= .Les trois variables de base sont
𝟐 𝟐 𝟐 𝟐
candidates à sortir. Si on sort x4, on obtient :
Ce dictionnaire correspond au point extrême x = (2; 0; 1)
avec les écarts e = (0; 1; 0) et f(x) = 13.
Tous les coûts réduits sont négatifs, donc on ne peut plus
augmenter la valeur de z. L'algorithme s‘ arête et on a la
garantie que x = (2; 0; 1) est la solution optimale, pour une Un point de base avec des variables de base à 0 est dit
valeur optimale de f(x) = 13. dégénéré.
Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]
Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution algébrique « Simplexe » Cyclage
• Il est possible que l'algorithme du simplexe cycle,
Illustration sur un exemple c'est-a-dire qu‘ après un certain nombre d‘ itérations,
Dégénérescence « suite » on retombe sur le dictionnaire d'une itération
Si on fait entrer x1 en base, on obtient : précédente. Ceci n'est possible qu'avec des points
dégénérés.
• Dans ce cas, si les règles pour les choix des variables
entrantes et sortantes ne changent pas, l'algorithme
répètera les mêmes itérations a l'infini.
• Des règles existent pour éviter ceci. Par exemple la
règle lexicographique de [Bland, 1977] qui consiste a
toujours considérer les plus petits indices pour l‘
• Le point est reste le même : x = (0,0,1/2,0,0) pour f(x) entrée et la sortie.
= 4. On a eu une itération dégénérée.
• D'autres pivots mèneront éventuellement à des points
non dégénères.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution algébrique « Simplexe »
Dégénérescence de 1ère espèce
● Coefficient d'une variable hors-base à 0 dans le dictionnaire
● On peut alors faire entrer cette variable dans la base (plus grand coefficient non négatif)
● La fonction objectif n'augmente alors pas
● Correspond au cas où la fonction économique est parallèle à l'hyperplan associé à une des contraintes
Dégénérescence de 2ème espèce
● Valeur nulle pour au moins l'une des variables de base.
● Correspond au cas où il passe, par un des sommets au moins, un ou plusieurs hyperplans supplémentaires.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire Etape Maximisation Minimisation

▪ Résolution algébrique « Simplexe » 1 Formuler un programme linéaire pour Formuler un programme linéaire pour
le problème réel. le problème réel.
Simplexe pour les problèmes de minimisation
2 Ecrire le programme linéaire sous une Ecrire le programme linéaire sous une
• Il y a deux manières de résoudre un problème de forme standard forme standard
minimisation en utilisant la méthode de simplexe. 3 Construire le premier tableau Construire le premier tableau
« dictionnaire » de simplexe « dictionnaire » de simplexe
La première méthode nécessite le changement de la
4 Choisir comme variable entrante dans Choisir comme variable entrante dans
règle de choix de la variable entrante. Dans un la base celle qui admet le plus grand la base celle qui admet le plus petit
problème de maximisation la règle est de choisir comme effet net positif effet net négatif .
variable entrante celle qui a le plus grand effet net 5 Choisir la variable sortante de la base Choisir la variable sortante de la base
positif non nul.. Pour un problème de minimisation, on celle qui admet le plus petit ratio celle qui admet le plus petit ratio
supérieur à zéro. supérieur à zéro.
va utiliser la règle inverse. C’est-à-dire la variable
6 Construire le nouveau tableau en Construire le nouveau tableau en
entrante est celle à laquelle on associe la plus petite utilisant la règle de pivot utilisant la règle de pivot
valeur négative non nulle.
7 Faire le test d’optimalité. Si Faire le test d’optimalité. Si
• Ceci va nous amener aussi à changer le test (cj-zj) ≤ 0 pour toutes les variables (cj-zj)≥ 0 pour toutes les variables
d’optimalité , tous les coûts réduit doivent être (hors base) donc la solution obtenue (hors base) donc la solution obtenue
est optimale. Sinon retourner à l’étape est optimale. Sinon retourner à l’étape
positifs « cout réduit ≥ 0 » 6. 6.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution algébrique « Simplexe » 𝐌𝐢𝐧 𝐱𝟏 + 𝐱𝟐
Simplexe pour les problèmes de minimisation Sc :
La deuxième méthode pour résoudre un 2𝑥1 + 𝑥2 ≥ 12
problème de se base sur le résultat suivant 5𝑥1 + 8𝑥2 ≥ 74
" Résoudre un problème min ctx sujet à un 𝑥1 + 6𝑥2 ≥ 24
ensemble de contraintes est équivalent à résoudre 𝑥1 ≥ 0; 𝑥2 ≥ 0
un problème max - ctx sujet au même ensemble
de contraintes ". Ces deux problèmes sont 𝐌𝐚𝐱 − 𝐱 𝟏 − 𝐱 𝟐
équivalents dans la mesure où ils donnent le Sc :
même vecteur des solutions optimales. La seule 2𝑥1 + 𝑥2 ≥ 12
différence est que la valeur de la solution max - 5𝑥1 + 8𝑥2 ≥ 74
ctx est l’opposé de la solution de min - 𝑥1 + 6𝑥2 ≥ 24
ctx (i.e. min ctx = - max -ctx). 𝑥1 ≥ 0; 𝑥2 ≥ 0

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution algébrique « Simplexe »
‘Coût réduit’

Le problème (P) s’´écrit alors sous la forme :

On partitionne A sous la forme suivante : A = [B N], on
partitionne de même les vecteurs x
Et c : x = (xB, xN)T et c = (cB, cN)T .

C’est la forme canonique par rapport à la base B.

x* est dite solution de base si elle vérifie

↔
Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]
Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution algébrique « Simplexe »

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution algébrique « Simplexe »
Algorithme du simplexe

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution algébrique « Simplexe »
Exercices 1
Résoudre le programme suivant en utilisant la méthode du simplexe

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution algébrique « Simplexe »
Exercices 1 : correction
La forme standard du programme est:

La solution obtenue x1 = 10, x2 = 10, x3 = 10, x4 = x5 = 0

est optimale, et la valeur maximale de z est 250.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution algébrique « Simplexe »
Exercices 2
Résoudre le programme suivant en utilisant la méthode du simplexe

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution algébrique « Simplexe »
Exercices 2 : Correction

la solution obtenue x1 = 5, x2 = 7, x3 = x4 = x5 = 0, x6 = 56
est optimale, et la valeur maximale de z est 1356.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Résolution d’un programme linéaire

▪ Résolution algébrique « Simplexe »
Exercices 3
Un ébéniste fabrique des bureaux sous forme standard ou Soit x1 le nombre de bureaux de type luxe, x2
luxe. Des études de marché ont montré que pour l’ année à le nombre de bureaux de type standard. Le
venir, les possibilités de vente s’ élèvent à 300 unités pour le programme linéaire est
modelé luxe et à 400 unités pour le modèle standard.
L’approvisionnement en bois est suffisant pour fabriquer
annuellement 500 bureaux quel que soit le type. Par ailleurs, le
temps de fabrication d’un modèle luxe est le double de celui
d’un bureau de modèle standard. La capacité annuelle de
fabrication est telle que, si tous les bureaux fabriqués étaient de
type standard, on pourrait en fabriquer 700 au maximum. La
vente d’un bureau sous le modèle luxe conduit à une marge
unitaire sur coût variable égale à 7, celle d’un bureau de type
Résoudre le programme suivant en utilisant la
standard égale à 5. On se propose de rechercher le programme méthode du simplexe et la méthode graphique.
annuel de fabrication conduisant au profit global maximum.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
La dualité est un concept fondamental en programmation linéaire et conduit à un résultat de
grande portée théorique et pratique.
Approche intuitive
Soit le problème d'optimisation linéaire suivant, de valeur optimale z* = 13500 :

Plutôt que de résoudre ce problème, essayons d'avoir une

estimation rapide de la valeur que peut prendre z.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
Approche intuitive
• Imaginons que nous multiplions la première contrainte par 20, la seconde contrainte par 40 et
la troisième par 100 et qu'on fasse la somme de ces trois nouvelles contraintes.

• Sachant que la fonction objectif est max z = 100x1 + 200x2, on peut alors affirmer à partir
de cette combinaison linéaire que

• Cette nouvelle contrainte fournit une borne supérieure sur la valeur de z.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
Approche intuitive
• Pouvons-nous trouver une combinaison linéaire qui offrira une meilleure borne sur la
valeur de z ?
• Multiplions la première par 0, la deuxième contrainte par 50 et la troisième par 150, on
obtient alors :

• Cette nouvelle combinaison linéaire donne une meilleure borne sur la valeur de
z. On sait maintenant que la valeur de z ne peut pas dépasser 14000.
• Est-ce la meilleure borne que l'on puisse trouver ?

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
Approche intuitive
• Afin d'obtenir la meilleure borne, prenons une combinaison linéaire quelconque avec les
quantités 𝜋1 , 𝜋2 et 𝜋3 non négatives :

• On peut affirmer que z ≤ 240 𝜋1 + 100 𝜋2 + 60 𝜋3 si et seulement si :

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
Approche intuitive
• Donc on cherche a attribuer des valeurs à 𝜋1 ,
𝜋2 et 𝜋3 qui minimiseront 240 𝜋1 + 100 𝜋2 +
60 𝜋3 . Ceci peut s'effectuer en résolvant le
problème d'optimisation linéaire suivant :

• Ce nouveau problème est appelé le dual du

problème linéaire original (qui est appelé le
primal).
Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]
Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
▪ un programme linéaire donné que nous appelons primal, l’opération de dualité associe un autre programme
linéaire dit son dual, qui ne sera défini qu’à l’aide des seules données du primal. La dualité présente un double
intérêt :
- d’une part, le programme dual à une interprétation économique importante : il constitue une autre vision du
programme initial, le primal.
‐ d’autre part, les propriétés liant le programme primal et son dual permettront de résoudre des problèmes de
minimisation en termes de maximisation, ce qui est souvent plus facile, et de développer de nouveaux
algorithmes qui se révéleront plus performants dans un grand nombre de situations. Considérons un
programme linéaire avec m=99 et n=9. Un dictionnaire du primal a 100 lignes alors qu'un dictionnaire
du dual a 10 lignes. Etant donné ce qui a été dit plus haut sur l'efficacité de l'algorithme du simplexe, à savoir que
le nombre d'itérations est proportionnel au nombre de lignes et quasi-insensible au nombre de variable, il serait
plus intéressant de passer par la résolution du dual et d'en déduire une solution optimale du primal à partir d'un
tableau optimal du dual. Il suffit alors d'y considérer les coefficients dans la fonction objective des variables d'écart
(en valeur absolue).
- Un autre intérêt de la dualité réside dans la certification d'optimalité d'une solution qu'elle soit de base
ou non.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité

Un programme linéaire est caractérise par le

tableau simplexe

Par définition, le problème dual est obtenu en

transposant ce tableau.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité ‘Exemple’
• A l'optimum, le primal et le dual sont liés par les règles suivantes:
- les fonctions objectifs z et w ont la même valeur optimale
- la valeur marginale d'une variable dans un programme est égale
à l'opposé de la valeur optimale de la variable associée dans l'autre
programme et réciproquement.
• les 2 variables de décision x1 et x2 du Primal sont associées 2
contraintes et donc 2 variables d'écart u1 et u2 dans le Dual.
De même aux 2 contraintes du Primal auxquelles
correspondent 2 variables d'écart t1 et t2, sont associées 2
variables de décision y1 et y2 dans le Dual.

• Le programme dual peut quelque fois apporter des

interprétations économiques intéressantes. D'un point de vue
mathématique, il peut permettre de résoudre certains
problèmes de minimisation.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
Règles de dualisation

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
Règles de dualisation
(𝜋1 )
(𝜋2 )
(𝜋3 )

(𝑥1 )
• Le problème dual du problème (𝑥2 )
dual est le problème primal (𝑥3 )

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
Relations primal/dual
Considérons la paire primale-duale :
Théorème:
Si (P) admet un optimum à valeur finie, soient 𝝅*
les multiplicateurs du simplexe associés à une Théorème de Dualité : Soit (P) et (D) deux problèmes un
solution optimale x*de (P). Alors 𝝅* est une Primal et son Dual
solution réalisable du problème dual et – Si x est une solution admissible du primal et y une solution
Cx* = 𝝅* b. (𝝅* est donc solution optimale du admissible du dual, alors:
dual). Z*= Max(P) ≤ Z* = Min (D)
– Si Z*= Max(P) = Min (D) , alors x est une solution
optimale du primal et y une solution optimale du dual.
– Si le primal (dual) est non borné, le dual (primal) n’admet pas
de solution admissible.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Exemple (Résolution du dual par les règles de complémentarité).

Dualité
Relations primal/dual
Théorème (Complémentarité). Considérons la
paire primale-duale :

Si x est une solution optimale du primal et y une

solution optimale du dual, alors

En d’autres termes :

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité « Exercices »
Exercice 1 :
Formuler le problème dual de chacun des programmes linéaires suivants :

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité « Exercices »
Exercice 1: Correction
Formuler le problème dual de chacun des programmes linéaires suivants :

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité « Exercices »
Exercice :
Appliquer le théorème des écarts complémentaires pour vérifier l’optimalité de la solution proposée.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité « Exercices »
Exercice : Correction
Le Dual
Comme y3 = 0, le système précédent devient

La troisième contrainte du problème primal n’est pas saturée. En résolvant ce système, on obtient : y1 = 1, y2 = 1, y4 =
Donc, la variable duale associée à cette contrainte est nulle : y3 = 0. 1 (y3 = 0) Cette solution ne satisfait pas la dernière
D’autre part, les variables x2, x3 et x4 sont strictement positives. contrainte du problème dual. Elle n’est donc pas
Ce qui implique que la deuxième, la troisième et la quatrième réalisable et par suite la solution primale proposée n’est
contraintes duales sont saturées. On obtient donc le système pas optimale.
suivant :

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité « Exercices »
Exercice :
Appliquer le théorème des écarts complémentaires pour vérifier l’optimalité de la solution proposée.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité « Exercices »
Exercice : Correction

Comme y3 = y4 = y6 = 0, le système précédent devient

En résolvant ce système, on obtient :

La troisième, quatrième et sixième contraintes du problème
primal ne sont pas saturées. Donc, les variables duales
associées à ces contraintes sont nulles : y3 = y4 = y6 = 0. Cette solution satisfait toutes les contraintes du
D’autre part, les variables x3, x4 et x6 sont strictement problème dual et z* = Max(P) = Min(D).. Elle est
positives. Ce qui implique que la troisième, la quatrième et donc réalisable et par suite la solution primale
la sixième contraintes duales sont saturées. On obtient donc proposée est optimale.
le système suivant :

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
Interprétation économique de la dualité:
La variable duale associée à une contrainte correspond au coût de cette contrainte dans la
solution courante. Si cette contrainte est saturée, ce coût est positif. Il est nul si cette
contrainte n'est pas saturée.
exemple
Monsieur Mohammed est un fabriquant des appareils électroménagères , il propose deux modèles à la vente, des
laves vaisselles et des petits réfrigérateurs. Les appareils de monsieur Mohammed sont tellement à la mode qu'il est
certain de vendre tout ce qu'il parvient à produire, au moins au prix catalogue actuel de 16000 DH pour les laves
vaisselles , et 10000 DH pour les petits réfrigérateurs. Son problème vient de l'approvisionnement limité en
deux matières premières, le caoutchouc et l'acier. La construction d'un petit réfrigérateur nécessite l'emploi d'une
unité de caoutchouc et d'une unité d'acier, tandis que celle d'une lave vaisselle nécessite une unité de caoutchouc
mais deux unités d'acier. Sachant que son stock de caoutchouc est de 400 unités et son stock d'acier de 600 unités,
combien doit-il produire de petits réfrigérateur et de laves vaisselles au moyen de ces stocks afin de maximiser son
chiffre d'affaire ?

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
Interprétation économique de la dualité:
exemple
Nous appellerons x le nombre des laves vaisselles produites, y le nombre
des petits réfrigérateurs produits, et z le chiffre d'affaire résultant. Le
problème se traduit alors sous la forme∶
𝒎𝒂𝒙𝒊𝒎𝒊𝒔𝒆𝒓 𝒛 = 𝟏𝟔𝟎𝟎𝟎 𝒙 + 𝟏𝟎𝟎𝟎𝟎
𝒔𝒐𝒖𝒔 𝒍𝒆𝒔 𝒄𝒐𝒏𝒕𝒓𝒂𝒊𝒏𝒕𝒆𝒔 𝒙 + 𝒚 ≤ 𝟒𝟎𝟎
𝟐𝒙 + 𝒚 ≤ 𝟔𝟎𝟎
𝒙 ≥ 𝟎; 𝒚 ≥ 𝟎

Un tel système, parce qu'il ne fait intervenir que deux variables, peu se
résoudre assez facilement de manière graphique. On obtient ainsi la
solution optimale x = 200 et y = 200,qui correspond a z = 5200000: Elle
est unique dans ce cas précis, et correspond a un sommet de la zone de
contraintes.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
Interprétation économique de la dualité:
exemple « Le problème dual du concurrent »

Supposons maintenant que monsieur Mohammed possède un concurrent madame Nouhaila qui,
pour honorer des commandes en trop grand nombre, se propose de lui racheter tous ses stocks. Ce
dernier doit faire une offre de prix (disons u) pour chaque unité de caoutchouc et une offre de prix
(disons v) pour chaque unité d'acier. Pour que l'offre soit acceptée, il faut que le prix payé par
madame Nouhaila soit au moins égal a ce que monsieur Mohammed pourrait en tirer en produisant
des appareils électroménagères .

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
Interprétation économique de la dualité:
exemple « Le problème dual du concurrent »

Le problème du concurrent s‘écrit ainsi :

𝒎𝒊𝒏𝒊𝒎𝒊𝒔𝒆𝒓 𝒑 = 𝟒𝟎𝟎 𝒖 + 𝟔𝟎𝟎 𝒗

𝒔𝒐𝒖𝒔 𝒍𝒆𝒔 𝒄𝒐𝒏𝒕𝒓𝒂𝒊𝒏𝒕𝒆𝒔 𝒖 + 𝒗 ≥ 𝟏𝟎𝟎𝟎𝟎
𝒖 + 𝟐𝒗 ≥ 𝟏𝟔𝟎𝟎𝟎
𝒖 ≥ 𝟎; 𝒗 ≥ 𝟎

Une analyse graphique fournit la solution optimale u = 4000 et v = 6000, ce qui correspond à un prix global
p = 5200000. On remarque que la solution optimale du problème du concurrent (on parlera de problème
dual, par opposition au problème primal du fabriquant) correspond aux prix marginaux du problème du
fabricant, et que le prix minimal que puisse proposer le concurrent est égal au chiffre d'affaire maximal
du fabricant.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
Algorithmes primal et dual du simplexe ▪ La matrice B induit une solution dite de base
Considérons la paire primale-duale : :𝒙𝒃 = 𝑩−𝟏 𝒃 ; 𝒙𝑵 = 𝟎.
▪ La solution de base est primale réalisable (𝑥
≥ 0) si et seulement si 𝑩−𝟏 𝒃 ≥ 𝟎 .
▪ La matrice B induit une solution 𝒚 = 𝒄𝑩 𝑩−𝟏
duale réalisable si et seulement si
𝒄𝑵 − 𝒄𝑩 𝑩−𝟏 𝑵 ≥ 𝟎 (coûts réduits ≥ 0).
On partitionne A en une matrice carrée B inversible et une matrice
N A=(B N) ▪ - Pour cette solution de base et cette solution
On partitionne de façon identique le vecteur x et le vecteur c y, les objectifs du primal et du dual ont la
même valeur = 𝒄𝑩 𝑩−𝟏 𝒃.
𝑐𝐵 est le vecteur extrait de 𝑐 , correspondant aux colonnes de la
▪ Pour être dual réalisable , on doit avoir pour
matrice 𝐵; 𝑐𝑁 est le vecteur extrait de 𝑐 , correspondant aux une minimisation 𝑐𝑁 ≥ 0 , et pour une
colonnes de la matrice 𝐵 .Même chose pour le vecteur x maximisation 𝑐𝑁 ≤ 0

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
Algorithme Simplexe dual
▪ On considère un programme linéaire primal (P) « Maximisation »
‐ Notons que les coefficients dans la fonction objective sont tous non positifs 𝒄𝑵 − 𝒄𝑩 𝑩−𝟏 𝑵 ≤
𝟎 . On dit dans ce cas que la base est "dual-réalisable".
‐ Notons également que le second membre 𝑩−𝟏 𝒃 n'est pas positif ou nul. On dit que la base n'est pas
" primal-réalisable ".

Algorithme primal
On passe de solution de base primale réalisable en solution de base primale réalisable. Et on stoppe dès
que l’on a atteint une base B qui est duale réalisable (coûts réduits ≥ 0)
Algorithme dual
On passe de base duale réalisable en base duale réalisable. Et on stoppe dès que l’on a atteint une solution
de base primale réalisable (𝑩−𝟏 𝒃 ≥ 𝟎 )

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
L’Algorithme dual du Simplexe

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
L’Algorithme dual du Simplexe : Exemple d’illustration
résoudre le problème par l’algorithme dual du simplexe

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
L’Algorithme dual du Simplexe : Exemple d’illustration
résoudre le problème par l’algorithme dual du simplexe

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

Dualité
L’Algorithme dual du Simplexe : Exemple d’illustration
résoudre le problème suivant et résoudre son dual , comparer.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème du transport
le problème du transport peut être formulé à l’aide d’un graphe simple où il n’y a pas de sommets intermédiaires,
seulement un ensemble de sommets source S, et un ensemble de sommets puits P.

• Chaque origine est représentée par un

sommet Oi,
• chaque destination par un sommet Dj,
• chaque route de l’origine i à la destination j
par un arc orienté de Oi vers Dj.

Le mot transport provient de la considération des sommets dans S comme des usines et de ceux dans P comme des
clients. Il s’agit de transporter les unités de disponibilité à partir des sources jusqu’aux clients à coût de transport total
minimum.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème du transport
Énoncé général du problème de transport

Où ai  la quantité de biens à acheminer de la source i

aux n destinations,
bj  la quantité de biens nécessaire pour satisfaire à la
demande à la destination j,
cij  coût unitaire de transport entre une source i et une
destination j,
xij  la qté transportée de l’origine i à la destination j.

m origines,
n destinations

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème du transport
Remarque: Une condition nécessaire et suffisante pour que le problème de transport admet une solution optimale
est que

Problèmes non balancés

– Si l’offre n’est pas égale à la demande : modèle non balancé.
– Introduction d’une source ou destination artificielle.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème du transport
Algorithme pour le problème de transport
Basé sur l’algorithme du simplexe en tenant compte de la structure du problème.
1. Détermination d’une solution de base admissible.
2. Détermination de la variable entrant en base.
3. Détermination de la variable sortant de base.
Illustration par un exemple

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème du transport
Algorithme pour le problème de transport
1. Détermination d’une solution de base admissible.
A. Méthode du coin nord-ouest Démarche :
Partir du coin supérieur gauche du tableau.
1. allouer le plus possible à la cellule courante et
ajuster l’offre et la demande ;
2. se déplacer d’une cellule vers la droite
(demande nulle) ou le bas (offre nulle) ;
3. répéter jusqu’au moment où toute l’offre est
allouée.

Remarque : méthode facile, ne tient pas compte des coûts de transport, loin de la solution optimale, la moins efficace.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème du transport
Algorithme pour le problème de transport
1. Détermination d’une solution de base admissible.
A. Méthode des Moindres coûts:
Sélectionner la cellule de coût minimum.
1. allouer le plus possible à la cellule courante et
ajuster l’offre et la demande ;
2. sélectionner la cellule de coût minimum ayant
une demande et une offre non nulles ;
3. répéter jusqu’au moment où toute l’offre est
allouée.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème du transport
Algorithme pour le problème de transport
2. Détermination de la variable entrant en base.
Nous allons utiliser la technique des coûts duaux. Etant donné une solution de base x, la
méthode consiste à déterminer une décomposition des coefficients cij (les coûts de transport) de
la forme cij = ui + vj pour les indices correspondants à ceux de la solution de base. Il y a m + n
− 1 équations pour m + n inconnues. Dans la pratique, on pose u1 = 0 et on résout pour les
autres variables.
Critère d’optimalité :
ui + vj – cij ≤ 0 ou cij – ui - vj ≥ 0
Complémentarité :
xij > 0 ► ui + vj – cij = 0

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème du transport
Algorithme pour le problème de transport
Exemple d’illustration: ❖ Vérification du critère d’optimalité et détermination de la variable entrante

❖ Détermination de la variable sortante pour préserver l’admissibilité et

pivotage
Objectifs : 1. l’offre et la demande doivent continuer à être satisfaites ;
2. les quantités transportées doivent rester positives.
Méthode : 1. construction d’un cycle parcourant des variables en base en partant de
et revenant à la variable entrante ;
2. déplacement le long de lignes et colonnes en alternant ajout et retrait
d’une même quantité.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème du transport
Algorithme pour le problème de transport
Exemple d’illustration:

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème du transport
Algorithme pour le problème de transport
Exemple d’illustration:

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème du transport
Algorithme pour le problème de transport
Exemple d’illustration:

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème du transport
Algorithme pour le problème de transport
Exercice: Résoudre le problème de transport suivant :

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème du transport
Algorithme pour le problème de transport
Exercice: Correction b) La case (1, 3) « variable X13 »entre dans la
base. On doit trouver celle qui quitte.
a) On démarre avec la solution du coin nord-
ouest et on évalue les coûts duaux.

Donc θ = 10 ce qui conduit à la solution de base

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème du transport
Algorithme pour le problème de transport
Exercice: Correction c) La case (2, 1) entre dans la base. On doit
Les coûts duaux trouver celle qui quitte.

Donc θ = 20 ce qui conduit à la solution de base

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème du transport
Algorithme pour le problème de transport
Exercice: Correction
Les coûts duaux

Ce tableau est optimal et la valeur de z = 1480.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème du transport
Exercice:
Une entreprise expédie un produit vers cinq magasins à partir de trois entrepôts. Le but est de trouver un programme
d’expédition des produits qui minimise le coût de transport total des entrepôts vers les magasins. Pour simplifier, on
nomme les entrepôts E1, E2, et E3 et les magasins M1, M2, M3, M4, et M5. Les disponibilités dans les entrepôts et les
demandes sont représentées dans le tableau ci-après ainsi que les coûts de transport. On suppose que les demandes sont
fermes (i.e. l’entreprise doit assurer exactement les quantités demandées).

1. Donner une solution réalisable par la méthode nord-ouest

2. Donner une solution réalisable par la méthode de moindre coût
3. Trouver une solution optimale du problème par la méthode des coûts duaux en partant de l’une des deux solutions réalisables
trouvées

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème d’affectation
Le problème d’affectation consiste à affecter les éléments d’un ensemble à ceux d’un autre
ensemble selon une approche biunivoque (un à un) de sorte que la somme des coûts des
affectations soit minimale.
Exemple: Répartir les ouvriers sur les machines ; assigner des véhicules aux trajets; affecter des
chauffeurs aux véhicules ; allocation des fréquences …de la façon la plus efficace sont des
problèmes d'affectation.

▪ Soit n unités à affecter à n tâches; une unité ne peut être affectée qu'à une tâche et une
tâche ne peut employer qu'une unité.
▪ L'unité i exécute la tâche j avec un coût ou un profit cij.

Comment doit-on affecter chaque unité à une seule tâche pour que le cout soit optimale?

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème d’affectation
Algorithme pour le problème d’affectation
Énumération de toutes les solutions possibles.
Adaptation de la méthode du simplexe
n=5 120 solutions réalisables.
Les propriétés de la matrice des contraintes nous
permettent d’utiliser le simplexe pour résoudre ce n = 20 Une calculatrice analysant une affectation par
problème de programmation linéaire en nombres entiers. microseconde travaillant 8 heures par jour et
365 jours par année, exigerait 2500 siècles pour
Inconvénients : ce travail.
• Cela conduit à des tableaux très grands (d’ordre n).
Technique spéciale tenant compte de la structure particulière
• La solution est fortement dégénérée. du problème d’affectation.
• Certaines itérations n’ont aucune incidence sur la
solution réalisable courante. Seul la base change Méthode hongroise « algorithme du Kuhn »
« dégénérescence » développée par le mathématicien Kuhn.

Kuhn, H. W. "The Hungarian Method for the Assignment Problem ". Naval Research Logistics Quarterly, Vol. 2, pp. 83-97, 1955.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème d’affectation
Algorithme pour le problème d’affectation
Description de la méthode hongroise sous une forme qui permet de faire tous les calculs dans la matrice des données du problème :
1. Soustraire l'élément minimum de la rangée i de chaque élément de la rangée i, pour tout i = 1, 2, ..., n.
2. Soustraire l'élément minimum de la colonne j de chaque élément de la colonne j, pour tout j = 1, 2, ..., n.
3. Examiner les rangées à partir de la première. S'il existe une rangée ne contenant qu'un seul zéro non marqué, alors marquer
ce zéro en l’encadrant pour dénoter une affectation. Éliminer les autres zéros de la même colonne en les marquant (cases grises).
• Répéter ce processus jusqu'à ce que toutes les rangées ne contiennent aucun zéro non marqué ou au moins deux zéros non
marqués.
4. Examiner les colonnes à partir de la première. S'il existe une colonne avec un seul zéro non marqué, alors marquer ce zéro
en l’encadrant pour dénoter une affectation. Éliminer les autres zéros non marqués de la même rangée en les marquant (cases grises).
Répéter ce processus jusqu'à ce que toutes les colonnes ne contiennent aucun zéro non marqué ou au moins deux zéros non marqués.
5. Répéter les étapes 3 et 4 successivement jusqu'à ce qu'une des trois conditions soit obtenue.
(a) Chaque rangée possède une affectation; alors cette affectation est optimale. L'algorithme prend fin.
(b) Il y a au moins deux zéros non marqués dans chaque rangée et chaque colonne; alors faire une affectation
arbitraire à un de ces zéros en l’encadrant et éliminer tous les autres zéros de la même rangée et de la même colonne en les marquant
(cases grises) puis aller à 3.
(c) Il n'y a aucun zéro non marqué et une affectation complète n'a pas été faite; alors passer à l'étape 6.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème d’affectation
Algorithme pour le problème d’affectation

6. Cocher () toutes les rangées pour lesquelles des affectations n'ont pas été faites.
7. Cocher () toutes les colonnes pas encore cochées et qui ont un zéro dans des rangées cochées.
8. Cocher () toutes les rangées pas encore cochées et qui ont des affectations dans des colonnes cochées.
9. Répéter les étapes 7 et 8 jusqu'à ce qu'il ne soit plus possible de cocher.
10. Tracer une ligne à travers toutes les rangées non cochées et toutes les colonnes cochées.
11. Parmi tous les éléments de la matrice qui ne sont pas couverts par une ligne, choisir l'élément le plus petit et le
soustraire de chaque élément non couvert et l'ajouter à chaque élément doublement couvert (par une ligne
verticale et horizontale). Retourner à l'étape 3.

Les conditions d’optimalité du problème d’affectation sont :

xij = 1  le coût réduit cij = 0.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème d’affectation
Algorithme pour le problème d’affectation
Prenons un exemple simple afin de montrer le processus de l’algorithme. Soient 5 machines (ligne) et 5 tâches (colonne)
donnant la table de coûts suivants :

17 15 9 5 12 5
16 16 10 5 10 5
12 15 14 11 5 5
4 8 14 17 13 4
13 9 8 12 17 8

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème d’affectation
Algorithme pour le problème d’affectation
Étape 1 : réduction du tableau initial
On soustrait à chaque ligne le plus petit élément de la ligne. Plus on soustrait à chaque colonne le plus petit élément de la
colonne.
12 9 4 0 7
11 10 5 0 5
7 9 9 6 0
0 3 10 13 9
5 0 0 4 9
0 0 0 0 0
Cette normalisation des coûts machines et des tâches permet d’avoir au moins un zéro par ligne et par colonne
la case (i, j) est admissible si cij = cij – ui – vj = 0 sinon elle est inadmissible.
– L’optimalité est assurée par la valeur des variables duales ui ; vj

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème d’affectation
Algorithme pour le problème d’affectation
Étape 2 : rechercher une solution réalisable
On cherche la ligne comportant le moins de zéros non barrés. En cas d’égalité on prendra la ligne la plus haute.
1.On encadre un des zéros de cette ligne (arbitrairement celui le plus à gauche).
2.On barre tous les zéros se trouvant sur la même ligne et colonne que celui sélectionné.
3.On recommence jusqu’à ce que tous les zéros sont encadrés ou barrés.
Si on a encadré un zéro par ligne et par colonne, nous avons une solution optimale. Sinon on passe à l’étape 3.

12 9 4 0 7
11 10 5 -0- 5
7 9 9 6 0
0 3 10 13 9
5 0 -0- 4 9

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème d’affectation
Algorithme pour le problème d’affectation
Étape 3 : création des pivots
Le sous-tableau permet par retranchement de posséder une configuration permettant de trouver une solution optimale. La
construction des pivots se fait ainsi :
1.On marque toute ligne ne contenant aucun zéro encadré.
2.On marque toute colonne ayant un zéro barré sur une ligne marquée.
3.On marque toute ligne ayant un zéro encadré dans une colonne marquée.
4.Répéter 2 et 3 jusqu’à ne plus avoir de modification.
On trace alors un trait sur toute ligne non marquée et sur toute colonne marquée. Dans notre exemple, la ligne 1 et 2 sont marqués,
ainsi que la colonne 4. Les éléments deux fois marqués sont accompagnés d’une étoile.

12 9 4 -0- 7
11 10 5 -0- 5
-7- -9- -9- *-6-* -0-
-0- -3- -10- *-13-* -9-
-5- -0- -0- *-4-* -9-

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème d’affectation
Algorithme pour le problème d’affectation
Étape 4 : modification du tableau
Les cases non traversées par un trait constituent un tableau partiel.
1.On retranche à toutes les cases de ce tableau le plus petit élément de celui-ci.
2.On ajoute cet élément à toutes les cases du tableau barrées dans les deux sens (accompagnées d’une étoile).
On recommence les étapes 2 à 4 jusqu’à obtenir un résultat optimal. Dans notre exemple, nous obtenons un résultat optimal
après la première itération.

8 5 0 0 3
7 6 1 0 1
7 9 9 10 0
0 3 10 17 9
5 0 0 8 9
L’affectation minimale se calcule à partir du tableau initial : 9+5+5+4+9 = 32.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]

Introduction Résolution Graphique Simplexe Analyse de la sensibilité Dualité Prob. du transport et d’affectation

problème d’affectation
Algorithme pour le problème d’affectation
Exercice On veut affecter 5 tâches à 5 ingénieurs informaticien. Les coûts des affectations sont données par le tableau
suivant:
Ingénieur 1 Ingénieur 2 Ingénieur 3 Ingénieur 4 Ingénieur 5
Tâche 1 15 40 5 20 20
Tâche 2 22 33 9 16 20
Tâche 3 40 6 28 0 26
Tâche 4 8 0 7 25 60
Tâche 5 10 10 60 15 5

Rechercher une affectation conduisant à un coût minimum en utilisant l’algorithme hongrois.

Chapitre 1: Programmation linéaire Ziyad Bahou : [email protected]