Td6 programmation linéaire en nombres entiers -Programmation

Télécharger PDF

Exercice 1 : Optimisation de la production d'un ébéniste

Un ébéniste fabrique des armoires et des tables. Une armoire nécessite 1 heure de travail et 9 m² de bois. Une table nécessite 1 heure de travail et 5 m² de bois. On dispose d'un total de 6 heures de travail et de 45 m² de bois. Chaque armoire génère un profit de 8 €, et chaque table génère un profit de 5 €.

1. Formulation du problème (P)

L'objectif est de maximiser le profit total de l'ébéniste en respectant les contraintes de ressources.

Soit x1 le nombre d'armoires et x2 le nombre de tables.

Maximiser z = 8x1 + 5x2

Sous les contraintes :
x1 + x2 ≤ 6 (Temps de travail)
9x1 + 5x2 ≤ 45 (Quantité de bois)
x1, x2 ≥ 0 et x1, x2 ∈ ℕ (Variables entières)

2. Solution du problème à variables continues (Relaxation linéaire)

En résolvant le problème sans la contrainte d'intégrité, nous obtenons :
z = 165/4 = 41,25
x1 = 15/4 = 3,75
x2 = 9/4 = 2,25

Comme les résultats ne sont pas entiers, cette valeur de z constitue une borne supérieure pour le problème en nombres entiers.

3. Méthode de séparation et évaluation (Branch and Bound)

Pour choisir la variable de séparation :

Critère de la variable la plus distante : Les deux variables sont à une distance de 0,25 d'un entier.
Critère du meilleur coefficient de profit (cj) : On choisit x1 car son profit (8) est supérieur à celui de x2 (5).

Le parcours de l'arbre en profondeur mène aux étapes suivantes :

Séparation sur x1 : Sous-problème P2 (x1 ≥ 4) et P3 (x1 ≤ 3).
Pour P2 (x1 ≥ 4), la solution relaxée donne z = 41, x1 = 4, x2 = 1,8. On sépare sur x2.
On explore la branche x2 ≤ 1 (P5). On trouve z = 40,55 avec x1 = 4,44.
En continuant la séparation, on trouve une solution entière candidate : x1 = 5, x2 = 0 avec z = 40.
La branche P3 (x1 ≤ 3) donne z = 39 (x1=3, x2=3), ce qui est inférieur à 40.

Solution optimale entière : Fabriquer 5 armoires et 0 table pour un profit de 40 €.

Exercice 2 : Résolution d'un programme linéaire en nombres entiers

Soit le problème suivant :
Maximiser z = 4x1 + 3x2
Sous les contraintes :
3x1 + 4x2 ≤ 12
4x1 + 2x2 ≤ 9
10x1 ≤ 22
x1, x2 ∈ ℕ

1. Solution relaxée et processus de séparation

La solution du programme linéaire relaxé est : x1 = 1,2 et x2 = 2,1 pour un profit z = 11,1.

2. Étapes du Branch and Bound

Nœud S0 (Initial) : x = (1,2 ; 2,1), z = 11,1. On sépare sur x2.
Nœud S1 (x2 ≥ 3) : Infaisable au regard des contraintes.
Nœud S2 (x2 ≤ 2) : x = (1,25 ; 2), z = 11. On sépare sur x1.
Nœud S3 (x1 ≤ 1) : Solution entière x = (1 ; 2), z = 10.
Nœud S4 (x1 ≥ 2) : x = (2 ; 0,5), z = 9,5.

La meilleure solution entière est x1 = 1 et x2 = 2 avec z = 10.

Exercice 3 : Problème de recouvrement - Gestion des chauffeurs

Une entreprise de transport doit couvrir ses besoins quotidiens en chauffeurs. Chaque chauffeur travaille 5 jours consécutifs suivis de 2 jours de repos.

Besoins quotidiens

Modélisation mathématique

Soit xi le nombre de chauffeurs commençant leur cycle de 5 jours le jour i (1=Lundi, ..., 7=Dimanche).

Objectif : Minimiser z = x1 + x2 + x3 + x4 + x5 + x6 + x7

Contraintes (exemples) :
Lundi : x1 + x4 + x5 + x6 + x7 ≥ 13
Mardi : x1 + x2 + x5 + x6 + x7 ≥ 18
...
Samedi : x2 + x3 + x4 + x5 + x6 ≥ 25
Contraintes d'intégrité : xi ≥ 0 et entiers.

Exercice 4 : Problème de transport de fournitures horticoles

Une municipalité possède 3 serres (S1, S2, S3) pour approvisionner 4 parcs (P1, P2, P3, P4).

Données de capacités et de demandes

Capacités des serres : S1 = 3, S2 = 7, S3 = 5.
Demandes des parcs : P1 = 4, P2 = 3, P3 = 4, P4 = 4.

Matrice des coûts de transport (Cij)

[ 2, 2, 2, 1 ]
[ 10, 8, 5, 4 ]
[ 7, 6, 6, 8 ]

Formulation mathématique

Soit xij la quantité transportée de la serre i vers le parc j.

Minimiser la somme des coûts : Σ Σ Cij * xij

Sous les contraintes :
- La somme des envois de chaque serre i doit être égale à sa capacité Ci.
- La somme des réceptions de chaque parc j doit être égale à sa demande Dj.
- xij ≥ 0.

Foire Aux Questions (FAQ)

Qu'est-ce que la méthode de séparation et évaluation (Branch and Bound) ?

C'est un algorithme utilisé pour résoudre des problèmes d'optimisation en nombres entiers. Il divise le problème en sous-problèmes plus petits (séparation) et utilise des bornes pour éliminer les zones qui ne peuvent pas contenir la solution optimale (évaluation).

Pourquoi la relaxation linéaire est-elle importante ?

La relaxation linéaire consiste à ignorer la contrainte selon laquelle les variables doivent être des nombres entiers. Elle permet d'obtenir une borne théorique (optimale pour le continu) qui aide à guider la recherche de la solution entière.

Quelle est la différence entre un problème de transport et un problème de recouvrement ?

Le problème de transport cherche à acheminer des biens d'un point A à un point B au moindre coût. Le problème de recouvrement cherche à sélectionner un ensemble minimal d'éléments (comme des équipes de travail) pour satisfaire des exigences spécifiques de couverture (comme des besoins horaires).