Cours d’initiation a la recherche operationnelle et applications de la programmation lineaire

Première partie

Un premier problème

Exemple 1 (Achat de billets d’avion).

–  Un homme d’affaires doit effectuer 5 voyages entre Fayetteville (FYV) à Denver (DEN), en partant le lundi de FYV et revenant le mercredi de DEN à FYV.

–  Billet aller-retour : $400.

–  Réduction de 20 % si un weekend est inclus. – Aller simple : 75 % du prix aller-retour.

Question

Comment acheter les billets pour les 5 semaines (à prix minimum)?

Aide à la décision

Problème d’aide à la décision

1. Quelles sont les alternatives possibles?
2. Quelles sont les restrictions à cette décision?
3. Quel est l’objectif utilisé pour évaluer les alternatives?

Restrictions

FYV-DEN le lundi et DEN-FYV le mercredi de la même semaine.

Evaluation des alternatives

Alternatives

–  Acheter 5 FYV-DEN-FYV normaux. 5 x $400 = $2000

–  Acheter un FYV-DEN, 4 DEN-FYV-DEN comprenant un weekend et un DEN-FYV. 0.75 x $400 + 4 x 0.8 x $400 + 0.75 x $400 = $1880

–  Acheter un FYV-DEN-FYV pour le lundi de la première semaine et le mercredi de la dernière semaine, et 4

DEN-FYV-DEN comprenant un weekend pour les autres voyages. 5 x 0.8 x 400 =1600 La troisième alternative est la meilleure.

Modèle de recherche opérationnelle

Ingrédients principaux

–  Alternatives (variables, inconnues du problème).

–  Restrictions (contraintes).

–  Fonction objectif à optimiser (minimiser ou maximiser).

Définition 1 (Solution admissible). Une solution admissible est un ensemble de valeurs données aux variables qui satisfait toutes les contraintes.

Définition 2 (Solution optimale). Une solution optimale est une solution admissible qui optimise la fonction objectif.

Définition 3 (Modèle de recherche opérationnelle). Maximiser ou minimiser (fonction objectif) Sujet à { contraintes }

Variables : continues (réelles), entières, booléennes (0/1),

Objectif : linéaire / non-linéaire, concave / convexe,

Contraintes : linéaire / non-linéaire, concave / convexe, égalités / inégalités,

Paramètres : connus avec certitude (modèles déterministes) / incertains (modèles stochastiques)

Exemple 2 (Maximisation de la surface d’un rectangle). Supposons que l’on veut plier un fil de fer de longueur L en rectangle de manière à maximiser la surface du rectangle.

Formulation

Solution –

–  Solution optimale :

Méthodes de résolution

–  Dans l’exemple, solution analytique au problème.

–  La plupart des problèmes pratiques sont trop grands ou trop complexes pour être résolus analytiquement.

Méthodes itératives

Déplacement de solution en solution pour atteindre l’optimum (méthodes exactes) ou une "bonne" solution

(heuristiques).

–  Importance des algorithmes et des solutions informatiques.

Recherche opérationnelle

La recherche opérationnelle est une technique d’aide à la décision.

Etapes pratiques

1. Définition du problème
2. Construction d’un modèle
3. Solution du modèle
4. Validation du modèle
5. Implémentation de la solution

Méthodologie

–  Les étapes les plus importantes sont la définition du problème (suppose un dialogue avec le décideur) et la construction du modèle (prendre conscience des hypothèses simplificatrices et de leur impact).

–  La phase de validation doit permettre de remettre en cause la validité du modèle.

–  Une approche globale nécessite donc un aller-retour constant entre le modèle et les attentes du décideur.

Techniques principales

–  Programmation linéaire

–  Programmation en nombres entiers

–  Optimisation dans les réseaux

–  Programmation non linéaire

–  "Optimisation" multi-critères

–  Programmation dynamique

–  Modèles stochastiques

–  Simulation

Deuxième partie

Programmation linéaire

Définition 4 (Programme linéaire). Modèle mathématique dans lequel la fonction objectif et les contraintes sont linéaires en les variables.

Applications

Optimisation de l’usage de ressources limitées dans les domaines militaire, industriel, agricole, économique,

Existence d’algorithmes très efficaces pour résoudre des problèmes de très grande taille (simplexe, points intérieurs)

Exemple 3 (Production de peinture). Une société produit de la peinture d’intérieur et d’extérieur à partir de deux produits de base M1 et M2.

Données

	Quantité utilisée par tonne Extérieure  Intérieure	Quantité disponible par jour
M1	6  4	24
M2	1  2	6
Profit par tonne	5  4

Contraintes supplémentaires

–  Demande maximum en peinture d’intérieur : 2 tonnes / jour.

–  La production en peinture d’intérieur ne dépasser que d’une tonne celle d’extérieur.

Formulation (Production de peinture) Alternatives (variables, inconnues du problème)

  x₁  =  tonnes de peinture d’extérieur

produites par jour

  x₂  =  tonnes de peinture

d’intérieur produites par jour

Fonction objectif à optimiser

maxz = 5x₁ + 4x₂

Restrictions (contraintes)

6x1 + 4x2	≤	24
x1 + 2x2	≤	6
x2	≤	2
x2 − x1	≤	1
x1,x2 Solutions et méthodes de résolution – Solution admissible : satisfait toutes les contraintes.	≥	0

x₁ = 3, x₂ = 1 (⇒ z = 19)

–  Nous voulons trouver la solution (admissible) optimale. – Infinité de solutions admissibles!

Méthodes pour trouver l’optimum

–  Méthode graphique

–  Simplexe

–  ( Ellipsoide, points intérieurs )

Exemple 4 (Diet problem). – On désire déterminer la composition, à coût minimal, d’un aliment pour bétail qui est obtenu en mélangeant au plus trois produits bruts : orge et arachide.

–  La quantité nécessaire par portion est de 400g.

–  L’aliment ainsi fabriqué devra comporter au moins 30% de protéines et au plus 5% de fibres.

Données

  Quantité par gramme d’aliment  Coût

Aliment	Protéines  Fibres  (EUR / kg)
Orge	0.09  0.02  1.5
Arachide Formulation (Diet problem) Variables	0.60  0.06  4.5
x1  =	grammes d’orge par portion
x2  =	grammes d’arachide par portion

Objectif

minz = 0.0015x₁ + 0.0045x₂

Contraintes

Quantité totale : x₁ + x₂ ≥ 400

Protéines : 0.09x₁ + 0.6x₂ ≥ 0.3(x₁ + x₂)

Fibres : 0.02x₁ + 0.06x₂ ≤ 0.05(x₁ + x₂)

Non-négativité : x₁,x₂ ≥ 0

Forme standard

Définition 5 (Forme standard). Un programme linéaire est sous forme standard lorsque toutes ses contraintes sont des égalités et toutes ses variables sont non-négatives. Représentation matricielle

  max  c^Tx

s.c.  Ax = b x ≥ 0

n variables, m contraintes, m < n, c,x ∈ Rⁿ,  b ∈ R^m,  A ∈ R^m×n.

Forme canonique

Définition 6 (Forme canonique). Un programme linéaire est sous forme canonique lorsque toutes ses contraintes sont des inégalités et toutes ses variables sont non-négatives. Représentation matricielle

  max  c^Tx

s.t.  Ax ≤ b x ≥ 0

n variables, m contraintes, c,x ∈ Rⁿ,  b ∈ R^m,  A ∈ R^m×n.

Théorème 1 (Equivalence des formes standard et canonique). Tout programme linéaire peut s’écrire sous forme standard et sous forme canonique.

Démonstration.

–  Une containte d’inégalité a^Tx ≤ b peut être transformée en égalité par l’introduction d’une variable d’écart :

a^Tx + s = b, s ≥ 0.

–  Une contrainte d’égalité a^Tx = b peut être remplacée par deux inégalités :

a^Tx ≤ b −a^Tx ≤ −b

–  a^Tx ≥ b ⇔ −a^Tx ≤ −b.

–  minc^Tx = −max−c^Tx.

–  Variable x non restreinte : substitution par deux variables (partie positive et négative)

x = x⁺ − x⁻x⁺,x⁻ ≥ 0.

Il existe toujours une solution optimale telle que x⁺ = 0 ou x⁻ = 0.

Forme standard du problème de production de peinture

maxz = 5x₁ + 4x₂

	s.c.6x1 + 4x2  ≤	24
	x1 + 2x2  ≤	6
	x2  ≤	2
	x2 − x1  ≤	1
Forme standard	x1,x2  ≥	0
maxz =	5x1 +4x2
s.c.	6x1 +4x2 +s1		= 24
	x1 +2x2  +s2		= 6
Forme matricielle	x2  +s3		= 2
	−x1 +x2 +s4 = 1 x1, x2, s1, s2, s3, s4 ≥ 0

  max  c^Tx

s.t.  Ax = b x ≥ 0

Variables pouvant prendre des valeurs négatives

Exemple 5 (Vente de hamburgers).

–  Un fast-food vend des hamburgers et des cheeseburgers. Un hamburger utilise 125 g. de viande alors qu’un cheeseburger n’en utilise que 100 g.

–  Le fast-food démarre chaque journée avec 10 kg de viande mais peut commander de la viande supplémentaire avec un coût additionnel de 2 EUR par kg pour la livraison.

–  Le profit est de 0.02 EUR pour un hamburger et 0.015 EUR pour un cheeseburger.

–  La demande ne dépasse pas 900 sandwiches / jour, et les surplus de viande sont donnés au Restos du Coeur.

Combien le fast-food doit-il produire de sandwiches de chaque type par jour?

Variables x₁ = nombre de hamburgers / jour x₂ = nombre de cheeseburgers / jour

Contraintes

–  Commande de viande supplémentaire :

  125x₁ + 100x₂ + x₃ = 10000,  x₃non restreint

–  Le coût pour la viande supplémentaire apparaît seulement si x₃< 0.

–  Substitution de x3 par 2 variables non-négatives :

x3 = x+3 − x−3 , x+3 ,x−3 ≥ 0 125x₁ + 100x₂ + x⁺₃ − x⁻₃ = 10000

–  Borne supérieure sur les ventes : x₁ + x₂ ≤ 900.

Modèle complet

s.c.		= 10000
	x1 + x2	≤ 900
		≥ 0

Remarque : Il existe une solution optimale telle que.

Représentation graphique

Production de peinture

maxz = 5x₁ + 4x₂

sous les contraintes :

6x₁ + 4x₂  ≤  24  (1) x₁ + 2x₂  ≤  6  (2) x₂  ≤  2  (3) x₂ − x₁  ≤  1  (4) x₁  ≥  0  (5) x₂  ≥  0  (6) Géométrie des solutions

Ensemble des solutions admissibles

Polyèdre (ABCDEF)

Courbes de niveaux de l’objectif

Ensemble de solutions ayant un profit (valeur de l’objectif) donné : intersection entre une droite et le polyèdre.

Amélioration de la solution

Recherche d’une direction dans laquelle le profit z augmente.

Résolution graphique (Production de peinture)

Recherche de la solution optimale

–  La droite mobile doit garder une intersection avec l’ensemble des solutions admissibles.

–  Solution optimale : x₁ = 3, x₂ = 1.5 (E)

–  La solution optimale est un sommet du polyèdre.

–  Cette observation est la base de l’algorithme du simplexe.

Résolution graphique (Diet problem)

Diet problem

minz = 0.0015x₁ + 0.0045x₂

sous les contraintes
x1 + x2	≥	400
0.21x1 − 0.30x2	≤	0
0.03x1 − 0.01x2	≥	0
x1	≥	0
x2	≥	0

Solution optimale

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 - système de m équations à n inconnues (m < n).

–  Identification algébrique des sommets : correspondance avec les bases d’un système d’équations.

Solutions de base

–  Système de m équations linéaires à n inconnues (m < n) : infinité de solutions.

–  Si on fixe à zéro n − m variables : système de m équations à m inconnues possédant une solution unique (si la matrice est inversible). C’est une solution de base.

Définition 7 (Solution de base). Une solution de base d’un programme linéaire est la solution unique du système de m équations à m inconnues obtenu en fixant à zéro n − m variables (pourvu que la matrice du système soit inversible).

Les variables fixées à zéro sont appelées variables hors base et les autres variables en base.

Exemple 6 (Production de peinture). Prenons B = {s₁,s₂,s₃,s₄}.

z =	0 +5x1 +4x2
s1 =	24 −6x1 −4x2
s2 =	6 −x1 −2x2
s3 =	2  −x2
s4 =	1 +x1 −x2

Si x₁ = x₂ = 0, alors s₁ = 24, s₂ = 6, s₃ = 2, s₄ = 1. Toutes ces valeurs sont non-négatives et la solution est réalisable.

Définition 8 (Solution de base réalisable). Une solution de base telle que toutes les variables prennent des valeurs non-négatives est appelée solution de base réalisable.

Géométrie des solutions de base

–  Prenons B = {s₁,s₂,s₃,s₄} ⇒ x₁ = x₂ = 0, s₁ = 24, s₂ = 6, s₃ = 2, s₄ = 1.

– Cette solution de base réalisable correspond au sommet (0,0).
Base  Solution  Objectif	Sommet
{s1,s2,s3,s4}  (0,0)  0	A
{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

Théorème 2. Toute solution de base réalisable correspond à un sommet du polyèdre.

Détermination de la solution de base optimale – Nombre maximum de solutions de base :

–  Algorithme "bête et méchant" : énumération de toutes les bases.

–  Méthode du simplexe : 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. – 3 etapes :

1. Détermination de la variable entrante.
2. Détermination de la variable sortante.
3. Pivotage.

L’algorithme du simplexe

Variable entrante

z =	0 +5x1 +4x2
s1 =	24 −6x1 −4x2
s2 =	6 −x1 −2x2
s3 =	2  −x2
s4 =	1 +x1 −x2

–  Si x₁ (ou x₂) augmente (entre en base), la valeur de la fonction objectif z augmente. – Quelle est la valeur maximale de x₁ ?

–  Contraintes : les autres variables doivent rester positives.

Variable sortante
	s1 =	24 −6x1 ≥ 0 → x1 ≤ 4
Pivotage	s2 = s3 = s4 =	6 −x1 ≥ 0 → x1 ≤ 6 2  ≥ 0 → 2 ≥ 0 1 +x1 ≥ 0 → x1 ≥ −1	toujours! toujours!	⇒ x1 ≤ 4
– Si x1 = 4, alors s1 = 0.

–  x₁entre en base, s₁sort de la base. – Substitution :

–  Nouveau système :

Equations du simplexe

–  B = indices des variables en base, N = indices des variables hors base. – Notation :

–  c_k : profit marginal ou coût réduit.

Règles de pivotage

Variable entrante

Choisir la variable k hors base avec le profit marginal maximum (maxz) ou le coût réduit minimum (minz).

  maxz  →  k = argmaxc_i

i∈N

minz

→

k = argminci i∈N

Si c_k ≤ 0 (max) ou c_k ≥ 0 (min) pour tout k ∈ N, solution optimale, STOP.

+5x1

z = 0+4x₂s₁ = 24 −6x₁ −4x₂

s2 = 6	−x1	−2x2
s3 = 2		−x2
s4 = 1	+x1	−x2

Variable sortante

Choisir la variable l en base telle que

Si a_lk ≤ 0 pour tout l ∈ B, problème non borné, STOP.

z = 0	+5x1 +4x2
s1 = 24	−6x1 −4x2
s2 = 6	−x1  −2x2
s3 = 2	−x2
s4 = 1	+x1  −x2

Pivotage

z = 0 +5x₁ +4x₂s₁ = 24 −6x₁ −4x₂s₂ = 6 −x₁ −2x₂

s₃ = 2 −x₂s₄ = 1 +x₁ −x₂z = 20 −56s1 +23x2 x1 = 4 −16s1 −23x2

s2 = 2 +16s1

s₃ = 2  −x₂

s4 = 5 −16s1 −53x2

Présentation en tableau

Présentation compacte pour effectuer les calculs sans répéter les systèmes d’équations.

Itération 1

Var. en base	z	x1	x2	s1	s2	s3	s4	Solution
z	−1	5	4	0	0	0	0
s1	0	6 1	4	1	0	0	0
s2	0		2	0	1	0	0
s3	0	0	1	0	0	1	0
s4	0	−1	1	0	0	0	1

Itération 2

Var. en base	z	x1	x2	s1	s2	s3	s4	Solution
z x1	−1 0	0 1	2 3		0 0	0 0	0 0
			2 3 4 3 1
s2	0	0			1	0	0
s3	0	0		0	0	1	0
s4	0	0	5 3		0	0	1

Itération 3

Var. en base	z	x1	x2	s1	s2	s3	s4	Solution
z	−1	0	0			0	0
x1	0	1	0			0	0
x2	0	0	1			0	0
s3	0	0	0			1	0
s4	0	0	0			0	1

Solution initiale artificielle

–  Une solution de base admissible n’est pas toujours connue a priori.

–  Certains problèmes n’admettent pas de solution admissible, donc il est impossible de trouver une base de départ.

–  La méthode des deux phases va permettre de déterminer une base admissible ou prouver que le problème est impossible.

Exemple 7 (Méthode des 2 phases).

	min	z =	4x1	+x2
	s.c.		3x1	+x2	=	3
			4x1	+3x2	≥	6
			x1	+2x2	≤	4
Introduction des variables d’écart			x1,	x2	≥ 0
min	z =	4x1	+x2
s.c.		3x1	+x2			=	3
		4x1	+3x2	−x3		=	6
		x1	+2x2		+x4	=	4
		x1,	x2,	x3,	x4	≥ 0

–  Pas de base admissible "triviale".

–  On voudrait voir apparaître une matrice identité.

– Introduction de variables artificielles. Introduction des variables artificielles
min  z =  4x1	+x2
min  r =			R1	+R2
min  r =  −7x1	−4x2	+x3					+9
s.c.  3x1	+x2		+R1			=	3
4x1	+3x2	−x3		+R2		=	6
x1	+2x2				+x4	=	4
x1,	x2,	x3,	R1,	R2,	x4	≥ 0

–  R₁, R₂ et x₄ peuvent être utilisées comme base de départ admissible.

–  Base pour le système de départ si R₁ = R₂ = 0 (hors base). – Réécrire l’objectif en fonction des variables hors base!

Solutions optimales multiples

–  Si la fonction objectif est parallèle à une contrainte active pour la solution optimale, la même valeur de l’objectif peut être prise par plusieurs solutions admissibles.

–  Il y a une infinité de solutions optimales dans ce cas (toutes les combinaisons convexes de sommets optimaux).

–  Cela se traduit par un profit marginal nul pour une ou plusieurs variables hors base.

Exemple 8 (Solutions optimales multiples).

	max		z =		2x1		+4x2
	s.c.				x1		+2x2		≤	5
					x1		+x2		≤	4
					x1,		x2		≥ 0
Var. en base		z		x1		x2		s1	s2	Solution
z		−1		2		4		0	0	0
s1		0		1		2		1	0	5
s2		0		1		1		0	1	4
z		−1		0		0		−2	0	−10
x2		0		1 2		1		1 2	0	5 2
s2		0		1 2		0			1	3 2
z		−1		0		0		−2	0	−10
x2		0		0		1		1	−1	1
x1		0		1		0		−1	2	3

Solution optimale :

Problèmes non bornés

–  Certains problèmes sont non bornés dans une direction donnée.

–  Si cette direction est une direction d’amélioration de la fonction objectif, celle-ci peut prendre une valeur arbitrairement grande!

Exemple 9 (Problèmes non bornés).

max	z =	2x1	+x2
s.c.		x1	−x2	≤	1
		2x1		≤	4

Var. en base	z	x1	x2	s1	s2	Solution
z	−1	2	1	0	0	0
s1	0	1	−1	1	0	1
s2	0	2	0	0	1	4

–  Tous les coefficients (sauf le profit maginal) dans la colonne de x₂ sont négatifs ou nuls.

–  Cela signifie que toutes les contraintes de non-négativité sont satisfaites quelle que soit la valeur de x₂.

–  L’objectif peut donc augmenter indéfiniment.

Problèmes impossibles

–  Le système de contraintes peut n’avoir aucune solution.

–  Généralement, provient d’une mauvaise formulation du problème.

Exemple 10 (Problèmes impossibles).

max	z =	3x1	+2x2
s.c.		2x1	+x2	≤	2
		3x1	+4x2	≥	12
		x1,	x2	≥ 0

Problème primal et problème dual Problème primal

  max  c^Tx

s.c.  Ax = b x ≥ 0

n variables, m contraintes, m < n, c,x ∈ Rⁿ, b ∈ R^m, A ∈ R^m×n. Problème dual

  min  b^Ty

  s.c.  A^Ty ≥ c

(y non restreint)

m variables, n contraintes, m < n, c ∈ Rn, b,y ∈ Rm, Exemple 11 (Problème primal et dual - forme standard).			A ∈ Rm×n.
Problème primal :
max	z =	x1	+x2
s.c.		2x1	+x2	= 5	(y1)
		3x1	−x2	= 6	(y2)
Problème dual :		x1,	x2	≥ 0
min	w =	5y1	+6y2
s.c		2y1	+3y2	≥ 1	(x1)
		y1	−y2	≥ 1	(x2)

Propriétés et règles de construction du dual

Théorème 3. Le problème dual du problème dual est le problème primal.

Règles de construction

	Problème max	Problème min
	Contrainte	Variable
	≤	≥ 0
	=	non restreinte
	Variable	Contrainte
≥ 0			≥
non restreinte Exemple 12 (Problème primal et dual - forme générale). Problème primal :			=
max  z =  5x1  +12x2			+4x3
s.c.  x1  +2x2			+x3	≤ 10		(y1)
2x1  −x2			+3x3	= 8		(y2)
x1,  x2,			x3	≥ 0

Problème dual :

min	w =	10y1	+8y2
s.c		y1	+2y2	≥ 5	(x1)
		2y1	−y2	≥ 12	(x2)
		y1	+3y2	≥ 4	(x3)
		y1		≥ 0

Théorème 4 (Dualité faible). Considérons la paire primale-duale :

  max  c^Tx

s.c. Ax = b x ≥ 0 min b^Ty

  s.c.  A^Ty ≥ c

–  Si x est une solution admissible du primal et y une solution admissible du dual, alors

c^Tx ≤ b^Ty

–  S’il y a égalité, alors x est une solution optimale du primal et y une solution optimale du dual.

Théorème 5 (Dualité forte). Considérons la paire primale-duale :

  max  c^Tx

s.c. Ax = b x ≥ 0 min b^Ty

  s.c.  A^Ty ≥ c

–  Si le primal et le dual admettent tous les deux une solution admissible, ils ont tous deux une solution optimale finie et la même valeur objectif optimale.

–  Si le primal (dual) est non borné, le dual (primal) n’admet pas de solution admissible.

Théorème 6 (Complémentarité). Considérons la paire primale-duale :

  max  c^Tx

s.c. Ax = b x ≥ 0 min b^Ty

  s.c.  A^Ty ≥ c

Si x est une solution optimale du primal et y une solution optimale du dual, alors

.

où a_i est la i-ème colonne de A.

En d’autres termes :

xi > 0	⇒	,
aTiy > ci	⇒	xi = 0.

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

max	z =	5x1	+12x2	+4x3
s.c.		x1	+2x2	+x3	≤ 10	(y1)
		2x1	−x2	+3x3	= 8	(y2)
		x1,	x2,	x3	≥ 0

Dual (D) :

Solution optimale de (P) : 

Solution optimale de (D) : 

–  La forme canonique d’un programme linéaire peut être interprétée comme un problème d’allocation de ressources.

–  Paire primale-duale :

  max  c^Tx

s.c.  Ax ≤ b x ≥ 0

  min  b^Ty

s.c.  A^Ty ≥ c y ≥ 0

–  Données : c_j : profit par unité d’activité j. b_i : disponibilité de la ressource i. a_ij : consommation de la ressource i par unité d’activité j.

–  Variables :

x_j : niveau de l’activité j. y_i : valeur d’une unité de la ressourcei.

Interprétation de la dualité faible z ≤ w : profit ≤ valeur des ressources

Interprétation de la dualité forte

Le profit maximal est atteint si les ressources ont été exploitées complètement, i.e. jusqu’à épuisement de leur valeur.

Exemple 14 (Dualité dans le problème de production de peinture).

4y₁ +2y₂ +y₃ +y₄ ≥ 4 y₁, y₂, y₃, y₄ ≥ 0

x₁ = 3, x₂ = 1.5, z = 21 y₁ = 0.75, y₂ = 0.5, y₃ = y₄ = 0, w = 21

–  Le profit augmente de 0.75 par augmentation d’une tonne de M1 et de 0.5 par tonne de M2. (Localement. Dans quelles limites? Voir analyse de sensibilité)

–  Les "ressources" 3 et 4 sont abondantes, augmenter ces ressources n’apporte aucun profit supplémentaire.

Exemple 15 (Production de jouets).

–  Une société de jouets produit des trains, des camions et des voitures, en utilisant 3 machines.

–  Les disponibilités quotidiennes des 3 machines sont 430, 460 et 420 minutes, et les profits par train, camion et voiture sont respectivement EUR 3, EUR 2 et EUR 5. – Les temps nécessaires sur chaque machine sont :

Machine	Train	Camion	Voiture
1	1	2	1
2	3	0	2
3	1	4	0

Base : B = {x₂,x₃,s₃}.

Solveurs

Logiciels pour résoudre des programmes linéaires :

–  Indépendants :

–  Commerciaux : CPLEX (), XPRESS-MP (), – Gratuits : PCx, lpsolve, glpk,

–  Tableurs : La plupart des tableurs intègrent un outil de résolution de programmes linéaires (Excel, Gnumeric,)

–  Langages de modélisation (ampl, GNU MathProg, mpl, OPL studio, mosel, ) : langages de haut niveau permettant la séparation modèle/données, se chargeant de l’interface avec un solveur.

NAME	toys
ROWS L R0001 L R0002 L R0003 N R0004 COLUMNS C0001	R0001	1
C0001	R0002	3
C0001	R0003	1
C0001	R0004	3
C0002	R0001	2
C0002	R0003	4
C0002	R0004	2
C0003	R0001	1
C0003	R0002	2
C0003	R0004	5
RHS B	R0001	430
B	R0002	460
B ENDATA	R0003	420

FIGURE 1 – Exemple de production de jouets au format MPS

Solveurs indépendants

Avantages

–  Puissance, efficacité

–  Intégrables dans des applications via des librairies

Désavantages

–  Formats de fichiers (MPS)

–  Pas de séparation modèle / données – Ré-utilisation difficile des modèles

Solveurs intégrés aux tableurs

Avantages

–  Disponibles sur (quasi) tous les ordinateurs

–  Interface facile d’utilisation

–  Présentation des données / résultats

Désavantages

–  Difficulté d’implémenter de grands modèles

–  Séparation modèle / données difficile

–  Solveurs moins efficaces (en général)

Langages de modélisation

Avantages

–  Séparation modèle / données

–  Ré-utilisabilité des modèles

–  Indépendance modèle / solveur

FIGURE 2 – Exemple de production de jouets au format AMPL (modèle)

Désavantages

–  Apprentissage du langage

–  Prix des versions commerciales

–  Limitation en taille des versions d’essai gratuites

–  Moindre efficacité (actuellement) des solveurs gratuits

FIGURE 3 – Exemple de production de jouets au format AMPL (données)

Troisième partie

Programmation en nombres entiers

–  Programmes linéaires dans lesquels certaines (ou toutes les) variables sont restreintes à des valeurs entières.

–  Si seulement une partie des variables doivent être entières, on parle de programme mixte (MILP).

–  Optimisation combinatoire : choix d’une solution optimale parmi un ensemble fini d’alternatives. Peuvent généralement se formuler comme des programmes en nombres entiers.

–  Problèmes très difficiles en pratique, mais solveurs de plus en plus performants.

Exemple 16 (Sélection de projets). 5 projets doivent être évalués sur 3 ans. Etant donné le coût de chaque projet pour chaque année et le profit obtenu par l’éxécution d’un projet, décider quels projets éxécuter sans dépasser le budget disponible pour chaque année.

	Coût par année		Profit
Projet	1  2	3
1	5  1	8	20
2	4  7	10	40
3	3  9	2	20
4	7  4	1	15
5	8  6	10	30
Budget	25  25	25

Variables si le projet j est sélectionné, sinon.

Formulation
	max z =	20x1	+40x2	+20x3	+15x4	+30x5
	s.c.	5x1	+4x2	+3x3	+7x4	+8x5	≤	25
		x1	+7x2	+9x3	+4x4	+6x5	≤	25
		8x1	+10x2	+2x3	+x4	+10x5	≤	25
		x1,	x2,	x3,	x4,	x5	∈	{0,1}

Exemple 17 (Problème avec coûts fixes).

–  3 compagnies de téléphone offrent des tarifs différents pour les communications longue distance.

  Compagnie  Abonnement  Prix / minute

–  Trouver le plan d’abonnement optimal pour 200 minutes de communication / mois.

Variables x_i : minutes de communication avec la compagnie i.

si un abonnement est pris auprès de la compagnie i,

Exemple 18 (Voyageur de commerce).

–  Un représentant doit visiter n villes une et une seule fois, et revenir à sa ville de départ, en minimisant le coût total du trajet.

–  Le problème revient à trouver un tour de coût minimum passant une et une seule fois par chacun des noeuds d’un graphe. Le coût d’utilisation de l’arc (i,j) est c_ij .

Variables si l’arc (i,j) appartient au tour optimal, sinon.

Contraintes

Problème : apparition possible de sous-tours

Formulation

min z = s.c.

Exemple 19 (Problème de couverture). Le département de sécurité d’un campus veut installer des téléphones d’urgence. Chaque rue doit être servie par un téléphone, le but étant de minimiser le nombre de téléphones à installer (installation aux carrefours).

Formulation

Contraintes disjonctives

–  Dans un programme linéaire, toutes les contraintes doivent être satisfaites simultanément.

–  Parfois, il est nécessaire de modéliser le fait qu’une contrainte parmi un ensemble doit être satisfaite. Si les contraintes de l’ensemble sont mutuellement incompatibles, on parle de contraintes disjonctives.

Exemple 20 (Contraintes disjonctives).

–  Une machine est utilisée pour 3 tâches différentes. Pour chaque tâches i, une durée p_i et une date limite d_i sont données, ainsi qu’une pénalité par jour de retard.

Tâche	Durée	Limite	Pénalité
1	5	25	19
2	20	22	12
3	15	35	34

–  Comment arranger les tâches sur la machine pour minimiser la pénalité totale?

–  Variables : x_i : temps de fin de la tâche i (x_i ≥ p_i).

–  Deux tâches i et j ne peuvent être éxécutées simultanément, donc

x_i ≥ x_j + p_ioux_j ≥ x_i + p_j.

–  Pour introduire ces contraintes disjonctives, nous faisons appel à des variables binaires auxiliaires :

si i précède j

xi − xj + Myij ≥ pix_j − x_i + M(1 − y_ij) ≥ p_j

–  Contrainte de date limite : introduction d’une variable d’écart non restreinte x_i + s_i = d_i.

–  Une pénalité apparaît uniquement si s_i < 0.

–  Remplacement par deux variables non négatives représentant les parties positive et négative.

Problèmes faciles et difficiles

–  La théorie de la complexité s’attache à classifier les problèmes selon leur difficulté.

–  Un problème est facile s’il existe un algorithme efficace pour le résoudre.

–  Exemples de problèmes “faciles” : programmation linéaire, affectation, plus courts chemins,

–  Un problème est difficile s’il appartient à la classe des problèmes NP-complets, pour lesquels il est peu probable de trouver un jour un algorithme efficace.

–  Exemple de problèmes “difficiles” : programmes en nombres entiers, voyageur de commerce,

Algorithmes efficaces et explosion combinatoire

–  L’efficacité d’un algorithme est mesurée par l’ordre de grandeur du nombre d’opérations élémentaires qu’il effectue en fonction de la taille des données.

–  Un algorithme sera efficace si le nombre d’opérations élémentaires est polynomial (i.e. borné supérieurement par un polynôme) en la taille de problème.

n	lnn + 1	n	n2	n3	2n
1	1.000	1	1	1	2
2	1.301	2	4	8	4
3	1.477	3	9	27	8
5	1.699	5	25	125	32
10	2.000	10	100	1000	1024
20	2.301	20	400	8000	1048576
50	2.699	50	2500	125000	1.12 × 1015
100	3.000	100	10000	1000000	1.27 × 1030

–  Autre perspective : supposons que trois ordinateurs M₁, M₂ et M₃ effectuent respectivement 10000, 20000 et 40000 opérations par seconde. opérations par seconde.

–  Quelle taille maximum de problème n peut on résoudre en une minute par des algorithmes effectuant respectivemet n, n², n³ et 2ⁿ opérations?

Ordinateur	n	n2	n3	2n
M1	600000	775	84	19
M2	1200000	1095	106	20
M3	2400000	1549	134	21

Le problème d’affectation

–  Exemple de problème combinatoire pour lequel il existe un algorithme efficace.

–  La meilleure personne pour chaque tâche.

–  n personnes doivent effectuer n tâches.

–  Un coût c_ij est associé à l’affectation de la personne i à la tâche j. Formulation du problème d’affectation

–  Propriété : la relaxation linéaire du problème est toujours entière. – Algorithme : méthode hongroise.

Exemple 21 (Problème d’affectation). Un père 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.

	Tondre	Peindre	Laver
John	15	10	9
Karen	9	15	10
Terri	10	12	8

Méthode hongroise

–  Sélectionner le prix minimum dans chaque ligne.

	Tondre	Peindre	Laver
John	15	10	9	9
Karen	9	15	10	9
Terri	10	12	8	8

–  Soustraire ce prix de chaque ligne et sélectionner le prix minimum dans chaque colonne.

	Tondre	Peindre	Laver
John	6	1	0	9
Karen	0	6	1	9
Terri	2	4	0	8
	0	1	0

–  Soustraire ce prix de chaque colonne.

	Tondre	Peindre	Laver
John	6	0	0	9
Karen	0	5	1	9
Terri	2	3	0	8
	0	1	0

–  Les "0" en bleu donnent une affectation admissible optimale.

–  L’optimalité est assurée par la valeur des variables duales (en rouge).

–  Nombre d’opérations : O(n²).

–  Il arrive que les valeurs nulles du tableau ne permettent pas de trouver de solution admissible.

0	3	2	2	1
2	0	0	2	7
0	1	4	3	4
3	2	0	0	5
0	0	3	0

  1  4  6  3

  9  7  10  9

  4  5  11  7

–  Sélectionner un nombre minimum de lignes et colonnes couvrant tous les 0.

–  Sélectionner le plus petit élément non couvert, le soustraire à tous les éléments non couverts et l’ajouter aux intersections.

0	2	1	1	2
3	0	0	2	7
0	0	3	2	5
4	2	0	0	5
-1	0	3	0

–  Répéter jusqu’à trouver une solution admissible.

–  Un produit doit être transporté de sources (usines) vers des destinations (dépôts, clients).

–  Objectif : déterminer la quantité envoyée de chaque source à chaque destination en minimisant les coûts de transport. Les coûts sont proportionnels aux quantités transportées.

–  Contraintes d’offre limitée aux sources et de demande à satisfaire au destinations.

  Sources  Destinations

Exemple 22 (Modèle de transport).

–  Une firme automobile a trois usines à Los Angeles, Detroit et New Orleans, et deux centres de distribution à Denver et Miami.

–  Les capacités des trois usines sont de 1000, 1500 et 1200 respectivement, et les demandes aux centres de distribution sont de 2300 et 1400 voitures. – Coûts :

	Denver	Miami
Los Angeles	80	215
Detroit	100	108
New Orleans	102	68

Formulation

minz = s.c.	80x11 +215x12 +100x21 +108x22 +102x31 +68x32
(Los Angeles)	x11	+x12					= 1000
(Detroit)			x21	+x22			= 1500
(New Orleans)					x31	+x32	= 1200
(Denver)	x11		+x21		+x31		= 2300
(Miami)		x12		+x22		+x32	= 1400
	x11,	x12,	x21,	x22,	x31,	x32	≥ 0

Représentation tableau

	Denver	Miami	Offre
Los Angeles	80 1000	215	1000
Detroit	100	108	1500
	1300	200
New Orleans	102	68 1200	1200
Demande	2300	1400

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.

Variantes

Le modèle de transport n’est pas limité au transport de produits entre des sources et destinations géographiques.

Exemple 23 (Modèle de production).

–  Une société fabrique des sacs à dos, pour lesquels la demande arrive de mars à juin et est de 100, 200, 180 et 300 unités, respectivement.

–  La production pour ces mois est de 50, 180, 280 et 270, respectivement.

–  La demande peut être satisfaite

1. par la production du mois courant ($40 / sac);
2. par la production d’un mois précédent (+ $0.5 / sac / mois pour le stockage);
3. par la production d’un mois suivant (+ $2 / sac / mois de pénalité de retard).

Correspondances avec le modèle de transport

Transport	Production - stocks
Source i	Période de production i
Destination j	Période de demande j
Offre à la source i	Capacité de production à la période i
Demande à la destination j	Demande pour la période j
Coût de transport de i à j	Coût unitaire (production + stock + pénalité) pour une production en période i pour la période j

Exemple 24 (Maintenance d’équipements).

–  Une scierie prépare différents types de bois sur base d’un plan hebdomadaire.

–  Pour satisfaire la demande, dépendant du type de bois, la scierie utilise un nombre donné de lames.

–  Pour satisfaire la demande, deux possibilités :

–  acheter une lame ($12);

–  faire aiguiser la lame (service express : $6 en une nuit, sinon $3 en 2 jours).

–  Demande :

Modèle de transport

8 sources : achat de nouvelles lames (offre = demande totale), 7 jours de la semaine (offre = nombre de lames utilisées).

8 destinations : 7 jours de la semaine (demande = nombre de lames utilisées) + surplus de lames non achetées / aiguisées (demande = nombre total de lames).

	Lun	Mar	Mer	Jeu	Ven	Sam	Dim	Surplus	Offre
Achat	12	12	12	12	12	12	12	0	124
Lun	10000	6	6	3	3	3	3	0	24
Mar	10000	10000	6	6	3	3	3	0	12
Mer	10000	10000	10000	6	6	3	3	0	14
Jeu	10000	10000	10000	10000	6	6	3	0	20
Ven	10000	10000	10000	10000	10000	6	6	0	18
Sam	10000	10000	10000	10000	10000	10000	6	0	14
Dim	10000	10000	10000	10000	10000	10000	10000	0	22
Demande	24	12	14	20	18	14	22	124

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.

Exemple 25 (Algorithme pour le problème de transport).

Détermination d’une solution de base admissible

–  Heuristiques "gloutonnes", pas besoin de méthode des deux phases. – Variantes :

1. Coin Nord-Ouest
2. Méthode des moindres coûts
3. Approximation de Vogel (VAM)

Coin Nord-Ouest

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);
2. répéter jusqu’au moment où toute l’offre est allouée.

Exemple 26 (Coin Nord-Ouest).

Coût : 520

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;
2. répéter jusqu’au moment où toute l’offre est allouée.

Exemple 27 (Moindres coûts).

Coût : 475

Approximation de Vogel (VAM)

1. pour chaque ligne (colonne) avec une offre (demande) non-nulle, calculer une pénalité égale à la différence entre les deux coûts les plus petits dans la ligne (colonne);
2. sélectionner la ligne ou colonne avec la pénalité maximale et sélectionner la cellule de coût minimum dans la ligne ou colonne;
3. allouer le plus possible à la cellule courante;
4. lorsqu’il ne reste qu’une ligne ou colonne : moindre coûts.

Exemple 28 (VAM).

Coût : 475

Formulation

Problème dual

Trois étapes :  1. détermination des variables duales (multiplicateurs);

2. vérification du critère d’optimalité et détermination de la variable entrante;
3. détermination de la variable sortante pour préserver l’admissibilité et pivotage.

Détermination des variables duales

1. m + n − 1 équations à m + n inconnues : fixer u₁ = 0.
2. Résoudre récursivement le système

u_i + v_j − c_ij = 0 pour tout x_ij > 0.

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é.

–  Extension du modèle de transport : il est parfois nécessaire (ou moins cher) d’utiliser des noeuds intermédiaires pour le transport.

–  Deux usines P1 et P2 servent 3 vendeurs D1, D2 et D3, via deux centres de transit T1 et T2.

Transformation en problème de transport – 3 types de noeuds :

Noeuds d’offre purs : arcs sortants uniquement. offre = offre originale

Noeuds de demande purs : arcs entrants uniquement. demande = demande originale

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 problème de transport.

–  Buffer : quantité nécessaire pour transporter toute la demande à travers le noeud de transbordement. – Dans notre exemple : B = 2200.

	T1	T2	D1	D2	D3	Offre
P1	3	4	M	M	M	1000
P2	2	5	M	M	M	1200
T1	0	7	8	6	M	2200
T2	M	0	M	4	9	2200
D1	M	M	0	5	M	2200
D2	M	M	M	0	3	2200
Demande	2200	2200	3000	3100	500

–  Les méthodes de branch-and-bound sont des méthodes basées sur une énumération "intelligente" des solutions admissibles d’un problème d’optimisation combinatoire.

–  Idée : prouver l’optimalité d’une solution en partitionant l’espace des solutions.

–  "Diviser pour régner"

–  Application à la programmation linéaire en nombres entiers : utilise toute la puissance de la programmation linéaire pour déterminer de bonnes bornes.

–  On appelle relaxation linéaire d’un programme linéaire en nombres entiers le programme linéaire obtenu en supprimant les contraintes d’intégralité sur les variables.

Programme en nombres entiers

  (P)  max  c^Tx

s.c.  Ax ≤ b x ≥ 0, entier.

Relaxation linéaire

  (LP)  max  c^Tx

s.c.  Ax ≤ b x ≥ 0.

Propriétés de la relaxation linéaire

–  La valeur de la solution optimale de LP est une borne supérieure sur la valeur de la solution optimale de P.

–  La valeur d’une solution admissible de P fournit une borne inférieure sur la valeur de la solution optimale de P.

–  Si la solution optimale de LP est entière (donc admissible pour P), elle est également la solution optimale de P.

Branchement

–  Si la solution de LP n’est pas entière, soit x_i une variable prenant une valeur fractionnaire x^∗_i dans la solution optimale de LP.

–  Le problème peut être divisé en deux sous-problèmes en imposant

où  est le plus grand entier inférieur à.

–  La solution optimale de P est la meilleure des solutions optimales des deux problèmes

z = 23.75

–  La solution de LP₁ est une solution admissible de P et donc z = 23 est une borne inférieure sur la valeur de la solution optimale de P.

–  Le noeud correspondant peut être éliminé vu qu’une solution entière optimale satisfaisant x₁ ≤ 3 a été trouvée (solution de P₁).

–  La valeur de la solution de LP, z = 23.75 est une borne supérieure sur la valeur de la solution optimale de P. – Vu que tout les coefficients sont entiers, on peut en déduire que la valeur de la solution optimale de P est inférieure ou égale à 23.

–  La solution de P₁ est donc optimale pour P.

Règles de branchement

–  Il n’y a pas de règle générale 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 noeuds à examiner dans l’arbre de branch-and-bound.

–  Exemple : branchement d’abord du côté ≥.

Formulation (rappel)

–  Si on retire les contraintes d’élimination de sous-tours, on obtient le problème d’affectation.

–  Cette relaxation a une solution entière qui peut être obtenue par exemple avec la méthode hongroise.

–  Le branchement est effectué de manière à éliminer les sous-tours.

–  La valeur de la solution optimale du problème d’affectation (AP) est une borne inférieure sur la valeur de la solution optimale du TSP.

–  Le coût d’un tour fournit une borne supérieure 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.

–  Si un sous-tour apparaît :

xi1i2 = xi2i3 = xi3i4 = ··· = xik−1ik = xiki1 = 1.

–  Dans une solution admissible, un de ces arcs doit être absent, donc

x_i1i₂ = 0 ou x_i2i₃ = 0 ou ou x_ik−1i_k = 0 ou x_iki₁ = 0.

–  Chacune de ces conditions va correspondre à une branche de l’arbre de branch-and-bound.

	1	2	3	4	5
1	∞	8	2	10	3
2	9	∞	20	9	7
3	6	40	∞	7	5
4	8	4	2	∞	5
5	9	10	6	9	∞

Exemple 31 (Voyageur de commerce).

Solution du problème d’affectation

  [153][24]  z = 28

–  On peut utiliser une approche classique pour les problèmes en nombres entiers en introduisant des variables supplémentaires (voir formulation en début de partie).

–  On peut également prendre comme relaxation le problème sans les contraintes disjonctives, et brancher sur les contraintes non satisfaites.

Exemple 32 (Contraintes disjonctives).

–  Une machine est utilisée pour 3 tâches différentes. Pour chaque tâches i, une durée p_i et une date limite d_i sont données, ainsi qu’une pénalité par jour de retard.