PLNE

Exercice 0 - Modélisation et Résolution

Énoncé et analyse des données

Le texte source pour cet exercice a subi une corruption majeure lors de son extraction (les équations apparaissent sous la forme de suites de chiffres incohérentes telles que 013108122 ou 212121ixxxxxxxZMax).

Par conséquent, les coefficients exacts de la fonction objectif à maximiser et des contraintes ne sont pas identifiables avec certitude. La question demande de vérifier des solutions optimales (réelles puis entières), mais comme il manque les paramètres d'entrée, cet exercice est techniquement impossible à résoudre sans inventer des données.

Cependant, l'objectif pédagogique de l'exercice est clair : il s'agit de démontrer que la solution optimale d'un Programme Linéaire (PL) en nombres réels n'est généralement pas égale à la solution du Programme Linéaire en Nombres Entiers (PLNE) et qu'un simple arrondissement ne fonctionne pas.

Exercice 1 - Problème du sac à dos

Modélisation générale

Le randonneur doit choisir des objets pour maximiser la valeur sans dépasser le volume B.## Exercice 0

L'extraction de cet exercice est sévèrement endommagée. Les coefficients de la fonction objectif et des contraintes sont illisibles (les nombres sont fusionnés sous la forme "13108122", "2121", etc.). Par conséquent, le calcul numérique exact est impossible car les données d'entrée sont manquantes.

Toutefois, l'énoncé demande de démontrer deux résultats à partir d'un programme linéaire :

1. Si les variables x sont des réels, la solution optimale continue est x1 = 22/9 et x2 = 4.
2. Si les variables x sont des entiers, la solution optimale entière donne une valeur différente (la valeur Z = 21 est mentionnée dans le texte).

Méthode de résolution attendue : Pour vérifier la première affirmation, il faudrait résoudre le système d'équations formé par les contraintes saturées du programme continu, ce qui donnerait le point d'intersection (22/9, 4). Pour vérifier la seconde affirmation, on appliquerait l'algorithme de séparation et d'évaluation (Branch and Bound). Puisque x1 = 22/9 ≈ 2.44 est fractionnaire, on créerait deux sous-problèmes en ajoutant les contraintes x1 ≤ 2 pour la première branche et x1 ≥ 3 pour la seconde, jusqu'à isoler la solution entière optimale.

Exercice 1 - Problème du sac à dos

Formulation mathématique

Le problème du sac à dos (Knapsack) consiste à choisir des objets pour maximiser la valeur totale sans dépasser le volume disponible B. Les variables de décision sont : xi = 1 si l'objet i est emporté, et 0 sinon.

Objectif : Maximiser Z = Σ ci xi (pour i de 1 à n) Sous contrainte : Σ ai xi ≤ B Avec : xi ∈ {0, 1}

Résolution par séparation et évaluation

L'énoncé précise une heuristique classique : les objets sont triés par ordre décroissant du ratio de rentabilité ci/ai. D'après les traces de l'arbre de résolution fournies dans le texte :

• La relaxation continue donne au sommet S0 la solution x* = (1, 1, 1/3, 0, 0, 0).
• La variable x3 étant fractionnaire (1/3), on sépare (branche) sur cette variable en créant un nœud où x3 = 0 et un nœud où x3 = 1.
• L'algorithme évalue ensuite les sommets. Par exemple, un sommet S2 est évalué avec une borne de Z = 24, qui correspond à une solution entière valide.
• Le sommet ayant la meilleure évaluation sert de point de départ pour continuer la recherche. Si l'évaluation d'un sommet est inférieure à la meilleure solution entière trouvée (la borne inférieure), ce sommet est élagué.

Exercice 2 - Problèmes d'affectation

Formulation classique (n tâches, n personnes)

On introduit les variables booléennes : xij = 1 si la tâche i est affectée à la personne j, et xij = 0 sinon.

Objectif : Maximiser le rendement total, soit Maximiser Z = Σ (pour i de 1 à n) Σ (pour j de 1 à n) Cij xij

Contraintes :

1. Chaque tâche i est affectée une et une seule fois : Σ (pour j de 1 à n) xij = 1
2. Chaque personne j se voit affecter une et une seule tâche : Σ (pour i de 1 à n) xij = 1

Formulation étendue (m tâches, n personnes, avec m < n)

Si le nombre de tâches (m) est strictement inférieur au nombre de personnes (n), certaines personnes n'auront aucune tâche. Le modèle s'adapte ainsi :

Objectif : Maximiser Z = Σ (pour i de 1 à m) Σ (pour j de 1 à n) Cij xij

Contraintes :

1. La somme des personnes affectées à la tâche i est 1 (chaque tâche est faite) : Σ (pour j de 1 à n) xij = 1 (pour tout i de 1 à m)
2. La somme des tâches affectées à la personne j est au maximum 1 (une personne fait au plus une tâche) : Σ (pour i de 1 à m) xij ≤ 1 (pour tout j de 1 à n)

Exercice 3 - Problème de recouvrement

Modélisation

On introduit les variables booléennes : xi = 1 s'il y a un hôpital construit dans l'arrondissement i, et xi = 0 sinon. L'objectif est de minimiser le nombre total d'hôpitaux : Minimiser Z = Σ xi

Les contraintes imposent que chaque arrondissement soit couvert par un hôpital situé soit chez lui, soit dans un arrondissement voisin immédiat. En lisant les données extraites, nous obtenons les inégalités suivantes :

1. x1 + x2 + x3 + x4 + x5 ≥ 1
2. x1 + x2 + x3 + x4 + x5 + x6 ≥ 1
3. x1 + x3 + x4 + x6 + x7 ≥ 1
4. x2 + x3 + x4 + x5 + x6 + x8 ≥ 1
5. x3 + x4 + x5 + x6 + x7 + x8 + x9 ≥ 1
6. x4 + x5 + x6 + x7 + x8 ≥ 1
7. x5 + x6 + x7 + x8 + x9 + x10 ≥ 1
8. x6 + x7 + x8 + x9 + x10 + x11 ≥ 1
9. x8 + x9 + x10 + x11 ≥ 1
10. x9 + x10 + x11 ≥ 1

Solution optimale

D'après le document, la solution optimale est obtenue en construisant des hôpitaux dans les arrondissements 3, 8 et 9. Les variables prennent donc les valeurs : x3 = 1, x8 = 1, x9 = 1, et toutes les autres xi = 0. Le nombre minimum d'hôpitaux à construire est Z = 3.

Exercice 4 - Problème Dos-à-Sac

Question 1 - L'arrondi de la solution continue

L'énoncé indique que la solution optimale de la relaxation continue (R) est x1 = 5.9 et x2 = 0, avec une valeur Z = 9.5 (ou -9.5 selon le sens de l'objectif). La question pose l'hypothèse d'une solution x1 = 6, x2 = 0 obtenue par arrondissement.

L'arrondi d'une solution continue n'est presque jamais la solution optimale en programmation linéaire en nombres entiers (PLNE), et n'est souvent même pas admissible. Dans ce cas, passer de x1 = 5.9 à x1 = 6 risque fort de violer l'une des contraintes du type "≤" qui limitait x1 à 5.9 dans le polyèdre continu. Si le point (6, 0) ne respecte pas toutes les contraintes, il n'est pas une solution valide pour (P).

Question 2 - Méthode des coupes

La question demande de montrer que la solution optimale entière est x1 = 1, x2 = 4 à l'aide d'une méthode de coupes. Bien que les équations initiales soient illisibles, le principe mathématique consiste à générer une coupe de Gomory. Puisque x1 = 5.9 est fractionnaire, on utilise la ligne du dictionnaire final du simplexe correspondant à x1 pour déduire une inégalité stricte sur les parties fractionnaires. Cette nouvelle contrainte (la coupe) est ajoutée au programme linéaire continu, ce qui rend le point (5.9, 0) irréalisable sans exclure aucune solution entière. Le problème est ensuite résolu itérativement par l'algorithme du simplexe dual jusqu'à obtenir les valeurs entières (1, 4).

Exercices 5, 6 et 7

Le texte source de ces trois exercices est irrémédiablement corrompu. Les équations ont été compressées en suites de chiffres inexploitables (comme 4559658212121S.C(P)). Il manque les coefficients de la fonction objectif et les valeurs du second membre des contraintes. Il est donc impossible de fournir une solution numérique pour ces exercices.

Néanmoins, les méthodes à appliquer selon les titres lisibles sont :

• Exercice 5 : Algorithme de séparation et d'évaluation (Branch and Bound).
• Exercice 6 : Méthode des plans sécants (Coupes de Gomory pour forcer l'intégrité).
• Exercice 7 : Résolution par Branch and Bound.

Méthode

Comment aborder une épreuve de Programmation Linéaire en Nombres Entiers (PLNE) :

1. Modélisation formelle : C'est toujours la première étape. Définissez clairement vos variables de décision (sont-elles binaires ? entières positives ? mixtes ?), la fonction objectif (Min ou Max), et exprimez chaque contrainte logique ou physique sous forme d'inégalité ou d'égalité mathématique.
2. Relaxation continue : Pour résoudre un PLNE à la main ou via un algorithme, on commence systématiquement par résoudre le problème en relâchant la contrainte d'intégrité (on permet aux variables d'être des nombres réels). Cette étape donne une borne fondamentale.
3. Méfiance envers l'arrondi : Ne supposez jamais que l'arrondi de la solution continue donnera la solution entière optimale. L'arrondi peut vous sortir du domaine des solutions réalisables.
4. Séparation et Évaluation (Branch and Bound) : Si la solution de la relaxation continue est fractionnaire, choisissez une variable fractionnaire (ex: x = 2.4). Séparez le problème en deux branches exhaustives (x ≤ 2 et x ≥ 3). Résolvez les relaxations continues de ces sous-problèmes et utilisez leurs valeurs pour élaguer l'arbre de recherche.
5. Coupes (Plans sécants) : Si la méthode des coupes est exigée, exprimez la ligne du tableau du simplexe correspondant à votre variable de base fractionnaire, puis isolez la partie fractionnaire des coefficients pour générer la coupe de Gomory. Ajoutez cette coupe géométrique au tableau et ré-optimisez via le simplexe dual.