Recherche Opérationnelle - Programmation Linéaire

Exercice 1 (modélisation)

1) Modèle maximisant le bénéfice

Nous devons définir les variables de décision. Le vendeur peut vendre deux types de lots. Soit x₁ le nombre de lots n°1 vendus, et x₂ le nombre de lots n°2 vendus.

La fonction économique à maximiser est le bénéfice total Z (en dinars) : Max Z = 6x₁ + 10x₂

Les contraintes sont liées aux stocks disponibles de guides et de cartes postales :

• Contrainte sur les guides : Chaque lot 1 et chaque lot 2 contient 1 guide. Le stock est de 20. x₁ + x₂ ≤ 20
• Contrainte sur les cartes postales : Le lot 1 en contient 10, le lot 2 en contient 50. Le stock est de 500. 10x₁ + 50x₂ ≤ 500
• Contraintes de non-négativité : x₁ ≥ 0, x₂ ≥ 0

2) Modèle sous forme standard

Pour passer à la forme standard, nous introduisons des variables d'écart positives (x₃ et x₄) pour transformer les inégalités "≤" en égalités. Max Z = 6x₁ + 10x₂ Sous contraintes : x₁ + x₂ + x₃ = 20 10x₁ + 50x₂ + x₄ = 500 x₁, x₂, x₃, x₄ ≥ 0

Exercice 2 (modélisation)

Formulation sous forme d'un programme linéaire

Définissons les variables de décision correspondant aux proportions de chaque produit brut pour composer une tonne d'aliment. Soit x₁ la quantité d'orge (en tonnes), x₂ la quantité d'arachides (en tonnes), et x₃ la quantité de sésame (en tonnes).

L'objectif est de minimiser le coût total Z pour une tonne : Min Z = 25x₁ + 41x₂ + 39x₃

Les contraintes sont :

• Contrainte de masse totale (pour 1 tonne d'aliment) : x₁ + x₂ + x₃ = 1
• Contrainte de pourcentage de protéines (au moins 22%) : 0,12x₁ + 0,52x₂ + 0,42x₃ ≥ 0,22
• Contrainte de pourcentage de graisses (au moins 3,6%) : 0,02x₁ + 0,02x₂ + 0,10x₃ ≥ 0,036
• Contraintes de non-négativité : x₁, x₂, x₃ ≥ 0

Exercice 3 (solution non bornée)

Note sur la transcription : Le document source présente des caractères endommagés (cid:0) qui masquent les signes. D'après le contexte classique d'un problème non borné et l'alignement des équations, nous reconstituons le problème ainsi : Min Z = -x₁ - x₂ Sous contraintes : -2x₁ + x₂ ≤ 2 (ou 2x₁ - x₂ ≥ -2) x₁ - 2x₂ ≤ 5 -x₁ + x₂ ≤ 1 x₁, x₂ ≥ 0

a- Représentation de l'ensemble des solutions admissibles

Pour représenter graphiquement, nous traçons les droites associées aux contraintes dans le plan (x₁, x₂) :

1. D₁ : -2x₁ + x₂ = 2 (passe par (0, 2) et (-1, 0)) ; la zone valide est vers le bas (x₂ ≤ 2x₁ + 2).
2. D₂ : x₁ - 2x₂ = 5 (passe par (5, 0) et (0, -2,5)) ; la zone valide est vers le haut (x₂ ≥ 0,5x₁ - 2,5).
3. D₃ : -x₁ + x₂ = 1 (passe par (0, 1) et (-1, 0)) ; la zone valide est vers le bas (x₂ ≤ x₁ + 1).

L'intersection avec le quadrant positif (x₁, x₂ ≥ 0) définit une région ouverte s'étendant indéfiniment vers le haut et la droite, car si l'on prend x₁ = x₂, toutes les contraintes sont satisfaites pour des valeurs infiniment grandes.

b- Localisation de toutes les solutions de base réalisables

Les solutions de base réalisables (SBR) correspondent aux sommets du polygone des contraintes dans la région admissible.

• Intersection des axes x₁=0, x₂=0 : Point O(0, 0). Vérifions les contraintes : 0 ≤ 2 (Vrai), 0 ≤ 5 (Vrai), 0 ≤ 1 (Vrai). C'est une SBR.
• Intersection de x₁=0 avec D₃ : Point A(0, 1). Vérifions D₂ : 0 - 2 ≤ 5 (Vrai) et D₁ : 1 ≤ 2 (Vrai). C'est une SBR.
• Intersection de x₂=0 avec D₂ : Point B(5, 0). Vérifions D₁ : -10 ≤ 2 (Vrai) et D₃ : -5 ≤ 1 (Vrai). C'est une SBR.

Toutes les autres intersections (ex: D₁ avec D₂) donnent des coordonnées négatives ou violent une contrainte. Les solutions de base réalisables sont donc O(0,0), A(0,1), et B(5,0).

c- Calcul de Z et solution optimale

Z(O) = -0 - 0 = 0 Z(A) = -0 - 1 = -1 Z(B) = -5 - 0 = -5 Le minimum parmi ces points est Z = -5 au point B(5,0). Cependant, l'énoncé indique que la solution est non bornée.

d- Détermination graphique de l'ensemble des solutions optimales

Si l'on déplace la droite de niveau Z = -x₁ - x₂ = k, pour k tendant vers -∞ (direction de la pente 1), la droite ne quitte jamais la zone réalisable (qui s'ouvre vers l'infini). La solution est donc infinie (non bornée). Il n'y a pas de minimum fini.

Exercice 4 (manipulation des bases)

a- Forme standard

On introduit les variables d'écart x₅ et x₆ : Max Z = 5x₁ + x₂ + 6x₃ + 24x₄ + 0x₅ + 0x₆ Sous contraintes : 4x₁ + 4x₂ + 4x₃ + x₄ + x₅ = 24 8x₁ + 6x₂ + 4x₃ + 3x₄ + x₆ = 36 x₁, ..., x₆ ≥ 0

b- La base B = (A₃, A₄) est-elle réalisable et optimale ?

Les vecteurs colonnes pour A₃ et A₄ sont A₃ = [4, 4]ᵀ et A₄ = [1, 3]ᵀ. La matrice de base est B = [[4, 1], [4, 3]]. Le déterminant de B = (4×3) - (1×4) = 12 - 4 = 8 ≠ 0. Il s'agit bien d'une base.

Calculons l'inverse B⁻¹ : B⁻¹ = 1/8 × [[3, -1], [-4, 4]]

Calculons la solution de base correspondante : X_B = B⁻¹ × b = 1/8 × [[3, -1], [-4, 4]] × [24, 36]ᵀ X_B = 1/8 × [(3×24 - 36), (-4×24 + 4×36)]ᵀ X_B = 1/8 × [(72 - 36), (-96 + 144)]ᵀ X_B = 1/8 × [36, 48]ᵀ = [4.5, 6]ᵀ Puisque x₃ = 4.5 ≥ 0 et x₄ = 6 ≥ 0, la base est réalisable.

Pour vérifier l'optimalité, nous calculons les coûts réduits (Cj - Zj) des variables hors base (x₁, x₂, x₅, x₆). Les coefficients dans la fonction objectif pour la base sont C_B = [6, 24]. Vecteur multiplicateur (variables duales) Y = C_B × B⁻¹ Y = [6, 24] × 1/8 × [[3, -1], [-4, 4]] Y = 1/8 × [(18 - 96), (-6 + 96)] = 1/8 × [-78, 90] = [-9.75, 11.25]

Calculons les coûts réduits (C'j = Cj - Y × Aj). Pour que la base soit optimale dans un problème de maximisation, il faut que tous les C'j ≤ 0 :

• Pour x₁ : C'₁ = 5 - ( -9.75×4 + 11.25×8 ) = 5 - (-39 + 90) = 5 - 51 = -46 ≤ 0
• Pour x₂ : C'₂ = 1 - ( -9.75×4 + 11.25×6 ) = 1 - (-39 + 67.5) = 1 - 28.5 = -27.5 ≤ 0
• Pour x₅ : C'₅ = 0 - ( -9.75×1 + 11.25×0 ) = 9.75 > 0

Puisque le coût réduit de x₅ est strictement positif (9.75), la base n'est pas optimale.

Exercice 5 (solution initiale)

a- Forme standard

Pour (PL1), on ajoute les variables d'écart x₄, x₅, x₆ ≥ 0 : Max Z = 2x₁ + x₂ + x₃ 2x₁ + x₂ + x₃ + x₄ = 2 x₁ + x₂ + x₅ = 10 2x₁ + 4x₂ + x₃ + x₆ = 8

Pour (PL2), on retranche des variables d'excédent x₄, x₅ ≥ 0 : Max Z = 3x₁ + 4x₂ + x₃ 8x₁ + 2x₂ + 2x₃ - x₄ = 3 7x₁ + 2x₂ + 3x₃ - x₅ = 3

b- Solutions initiales évidentes

• Pour (PL1) : Oui. En fixant les variables de décision x₁, x₂, x₃ à 0, on obtient directement x₄ = 2, x₅ = 10, x₆ = 8. Toutes ces valeurs sont positives, formant une base réalisable triviale (l'origine).
• Pour (PL2) : Non. Si on fixe x₁, x₂, x₃ à 0, on obtient x₄ = -3 et x₅ = -3, ce qui viole la contrainte de non-négativité. Il n'y a pas de solution de base évidente ; il faudra utiliser la méthode des deux phases ou la méthode du Grand M en ajoutant des variables artificielles.

Exercice 6 (solution intermédiaire)

1) Preuve que X est une solution de base réalisable

Soit le vecteur X = (0, 0, 230, 200, 0, 420). Remplaçons ces valeurs dans le système des contraintes (P.L) :

1. 0 + 2(0) + 230 + 200 = 430 (Vrai)
2. 3(0) + 2(230) + 0 = 460 (Vrai)
3. 0 + 4(0) + 420 = 420 (Vrai) Toutes les composantes de X sont positives (xj ≥ 0), la solution est donc admissible. Le nombre de variables strictement positives est 3 (x₃, x₄, x₆), ce qui correspond au nombre de contraintes. Le déterminant de leurs vecteurs colonnes est -2 (différent de 0), prouvant l'indépendance linéaire. C'est bien une solution de base réalisable.

2) Tableau du simplexe correspondant

Pour construire le tableau, exprimons les variables de base (x₃, x₄, x₆) en fonction des variables hors base (x₁, x₂, x₅). De la 2e équation : 2x₃ = 460 - 3x₁ - x₅ => x₃ = 230 - 1.5x₁ - 0.5x₅ Substituons x₃ dans la 1ère équation : x₁ + 2x₂ + (230 - 1.5x₁ - 0.5x₅) + x₄ = 430 -0.5x₁ + 2x₂ - 0.5x₅ + x₄ = 200 => x₄ = 200 + 0.5x₁ - 2x₂ + 0.5x₅ La 3e équation donne directement : x₆ = 420 - x₁ - 4x₂

Remplaçons dans la fonction objectif : Z = 3x₁ + 2x₂ + 5(230 - 1.5x₁ - 0.5x₅) = 1150 - 4.5x₁ + 2x₂ - 2.5x₅

Tableau correspondant (exprimé avec les coefficients de Cj - Zj pour la ligne d'évaluation) :

Base	x₁	x₂	x₃	x₄	x₅	x₆	RHS
x₄	-0.5	2	0	1	-0.5	0	200
x₃	1.5	0	1	0	0.5	0	230
x₆	1	4	0	0	0	1	420
Z	-4.5	2	0	0	-2.5	0	1150

3) Optimalité

Le tableau n'est pas optimal. La variable hors base x₂ a un coût réduit strictement positif (+2). L'introduire dans la base permettrait d'augmenter la valeur de Z.

Exercice 7 (méthode des deux phases ou méthode M)

Note : L'énoncé présente des erreurs typographiques de lecture, la forme la plus standard et mathématiquement valide pour ce système est restituée ici. Max Z = -2x₁ + x₂ 3x₁ + x₂ = 3 4x₁ + 3x₂ - x₃ = 6 (où x₃ est l'écart ≥ 0 de la contrainte ≥) x₁ + 2x₂ + x₄ = 3 (où x₄ est l'écart ≥ 0 de la contrainte ≤)

1) Méthode des deux phases

Phase 1 : On minimise la somme des variables artificielles a₁ et a₂ ajoutées aux contraintes 1 et 2. L'objectif de la Phase 1 est Max W' = -a₁ - a₂.

• a₁ = 3 - 3x₁ - x₂
• a₂ = 6 - 4x₁ - 3x₂ + x₃ Donc W' = 7x₁ + 4x₂ - x₃ - 9.

Base	x₁	x₂	x₃	x₄	a₁	a₂	RHS
a₁	3	1	0	0	1	0	3
a₂	4	3	-1	0	0	1	6
x₄	1	2	0	1	0	0	3
W'	7	4	-1	0	0	0	-9

Pivot 1 : Entrée de x₁ (plus grand coefficient positif dans W'), sortie de a₁ (min(3/3, 6/4, 3/1)).

Base	x₁	x₂	x₃	x₄	a₂	RHS
x₁	1	1/3	0	0	0	1
a₂	0	5/3	-1	0	1	2
x₄	0	5/3	0	1	0	2
W'	0	5/3	-1	0	0	-2

Pivot 2 : Entrée de x₂, sortie de a₂ (min(1/(1/3)=3, 2/(5/3)=1.2, 2/(5/3)=1.2)).

Base	x₁	x₂	x₃	x₄	RHS
x₁	1	0	1/5	0	0.6
x₂	0	1	-0.6	0	1.2
x₄	0	0	1	1	0
W'	0	0	0	0	0

Fin de la Phase 1 (W' = 0). La solution trouvée est x₁ = 0.6, x₂ = 1.2.

Phase 2 : On reprend Z = -2x₁ + x₂ et on substitue les variables de base (x₁, x₂). Z = -2(0.6 - 0.2x₃) + (1.2 + 0.6x₃) = x₃. Dans le tableau final, on observe que Z atteint un maximum de 0, et l'itération de Phase 2 permettrait de pivoter x₃ avec x₄ de manière dégénérée sans changer les valeurs (RHS de x₄ est 0). Solution optimale : x₁ = 3/5, x₂ = 6/5, Z = 0.

2) Résolution graphique et cheminement

Domaine admissible dans le plan (x₁, x₂) :

• 3x₁ + x₂ = 3 décrit un segment de droite.
• 4x₁ + 3x₂ ≥ 6 et x₁ + 2x₂ ≤ 3 encadrent ce segment. L'intersection de toutes ces contraintes ne définit qu'un seul point géométrique unique : (3/5, 6/5). Le domaine n'est pas une surface, c'est un point. Cheminement du simplexe : L'algorithme part de l'origine artificielle (0,0), se déplace le long de l'axe x₁ au point (1,0) (fin du Pivot 1), puis monte sur la contrainte d'égalité au point unique admissible (3/5, 6/5) (fin du Pivot 2).

Exercice 8 (programmation paramétrée)

1- Résolution graphique

Contraintes :

• D₁ : x₁ + x₂ ≤ 2
• D₂ : 2x₁ + 3x₂ ≤ 6 (Cette contrainte est redondante car x₁ + x₂ ≤ 2 implique que 2x₁ + 3x₂ = 2(x₁ + x₂) + x₂ ≤ 4 + 2 = 6).
• D₃ : x₁ - x₂ ≤ 0, soit x₁ ≤ x₂.

Le domaine est défini par les sommets :

• A(0, 0)
• B(1, 1) (intersection de x₁ = x₂ et x₁ + x₂ = 2)
• C(0, 2) (intersection de x₁ = 0 et x₁ + x₂ = 2)

Évaluons Z = 6x₁ + 5x₂ sur ces sommets :

• Z(A) = 0
• Z(B) = 6(1) + 5(1) = 11
• Z(C) = 6(0) + 5(2) = 10 La solution optimale est B(1, 1) avec Z = 11.

2- Étude paramétrée

Max Z = (6 - 2λ)x₁ + (5 + λ)x₂ Évaluons cette nouvelle fonction objectif aux trois sommets :

• Z(A) = 0
• Z(B) = (6 - 2λ) + (5 + λ) = 11 - λ
• Z(C) = (5 + λ)×2 = 10 + 2λ

a- Résolution selon les valeurs de λ : Le sommet B est optimal si Z(B) ≥ Z(C) et Z(B) ≥ Z(A).

• 11 - λ ≥ 10 + 2λ => 3λ ≤ 1 => λ ≤ 1/3.
• 11 - λ ≥ 0 => λ ≤ 11. Le sommet C est optimal si Z(C) ≥ Z(B) et Z(C) ≥ Z(A).
• λ ≥ 1/3 (d'après le calcul précédent inversé).
• 10 + 2λ ≥ 0 => λ ≥ -5. Conclusion :
• Pour λ < 1/3 : La solution optimale est (1, 1).
• Pour λ > 1/3 : La solution optimale est (0, 2).

b- Solutions jamais optimales : Le sommet A(0,0) nécessite que 0 ≥ 11 - λ (λ ≥ 11) ET que 0 ≥ 10 + 2λ (λ ≤ -5), ce qui est contradictoire. La solution (0,0) n'est jamais optimale.

c- Infinité de solutions optimales : Pour λ = 1/3, Z(B) = Z(C) = 32/3. La fonction objectif est parallèle à l'arête reliant B et C. Tous les points du segment [ (1, 1) ; (0, 2) ] sont des solutions optimales.

Exercice 9 (programme dual)

Premier Programme (P1)

On pose y₁ et y₂ les variables duales correspondant aux deux équations de contraintes. Min W = 60y₁ + 140y₂ Sous contraintes : 6y₁ + 2y₂ ≥ 15 10y₁ + 10y₂ ≥ 40 2y₁ + 6y₂ ≥ 12 y₁ ≥ 0, y₂ ≥ 0 (Puisque les contraintes d'origine intègrent des variables d'écart d'égalité de signe positif, les équations s'apparentent à des contraintes "≤" dans le primal de maximisation).

Second Programme (P2)

Min W = 16y₁ + 25y₂ Sous contraintes : y₁ + 7y₂ ≥ 4 y₁ + 5y₂ ≥ 5 2y₁ + 3y₂ ≥ 9 y₁ quelconque (car contrainte d'égalité dans le primal) y₂ ≥ 0 (car contrainte "≤" dans le primal de maximisation)

Exercice 10: (solution primal à partir du dual et inversement)

1- Programme dual de P.L.

Min Z (primal) devient Max W (dual). Max W = 8y₁ + 8y₂ + 47y₃ Sous contraintes : 4y₁ + y₂ + 7y₃ ≤ 2 y₁ + 4y₂ + 10y₃ ≤ 3 y₁, y₂, y₃ ≥ 0

3- Résolution du programme dual

Variables d'écart e₁, e₂. Tableau initial :

Base	y₁	y₂	y₃	e₁	e₂	RHS
e₁	4	1	7	1	0	2
e₂	1	4	10	0	1	3
-W	8	8	47	0	0	0

Itération 1 (Entrée de y₃, sortie de e₁) : Pivot 7. Itération 2 (Entrée de y₂, sortie de e₂) : Pivot 18/7. À l'issue des calculs (non détaillés ici pour concision, mais le déroulement suit l'algorithme standard), on obtient le tableau optimal :

Base	y₁	y₂	y₃	e₁	e₂	RHS
y₃	5/6	0	1	2/9	-1/18	5/18
y₂	-11/6	1	0	-5/9	7/18	1/18
-W	-16.5	0	0	-6	-0.5	-13.5

Valeur optimale du dual : W = 13.5.

4- Tableau optimal du primal

Les valeurs optimales des variables du primal (x₁ et x₂) se lisent directement dans la ligne des coûts réduits du tableau optimal dual (en valeur absolue), sous les colonnes des variables d'écart (e₁ et e₂).

• x₁ (associée à e₁) = 6
• x₂ (associée à e₂) = 0.5 (ou 1/2) La valeur optimale Z = 2(6) + 3(0.5) = 13.5, ce qui correspond bien à W.

Exercice 11 (théorème des écarts complémentaires)

1- Résolution graphique

Primal : Max Z = 3x₁ + 4x₂ Sous : (1) 2x₁ + x₂ ≤ 2 (2) x₁ + 2x₂ ≤ 6 (3) 3x₁ + 9x₂ ≤ 1 Remarque : Si 3x₁ + 9x₂ ≤ 1, alors x₁ ≤ 1/3 et x₂ ≤ 1/9. Dans ce cas, les contraintes (1) et (2) sont largement respectées (elles sont redondantes). Le domaine est le triangle de sommets (0,0), (1/3, 0), et (0, 1/9). Z(1/3, 0) = 1. Z(0, 1/9) = 4/9. La solution optimale est x₁ = 1/3, x₂ = 0, Z = 1.

2- Dual et écarts complémentaires

Dual : Min W = 2y₁ + 6y₂ + y₃ 2y₁ + y₂ + 3y₃ ≥ 3 y₁ + 2y₂ + 9y₃ ≥ 4 y₁, y₂, y₃ ≥ 0

D'après le théorème des écarts complémentaires :

• Dans le primal, x₁ = 1/3 > 0, donc la première contrainte du dual est serrée (égalité) : 2y₁ + y₂ + 3y₃ = 3.
• Les contraintes (1) et (2) du primal ont des variables d'écart strictement positives (2(1/3)+0 = 2/3 < 2, et 1/3+0 = 1/3 < 6). Par conséquent, les variables duales associées sont nulles : y₁ = 0, y₂ = 0. En substituant y₁ et y₂ dans la contrainte d'égalité duale : 2(0) + 0 + 3y₃ = 3 => 3y₃ = 3 => y₃ = 1. La solution du dual est y₁ = 0, y₂ = 0, y₃ = 1. W = 1. (Ce qui valide bien W = Z).

Exercice 12 (DS 2012-2013)

D'après la notation standard de ce problème : Max Z = 3x₁ + 3x₂ + x₃ Sous contraintes : -2x₁ + x₂ + x₃ ≤ 2 x₁ - x₃ ≤ 4 x₁ + x₂ + 2x₃ ≥ 4 x₁, x₂, x₃ ≥ 0

1. Résolution par la méthode des deux phases

On introduit les écarts (x₄, x₅, x₆) et une variable artificielle (a₁) sur la 3ème équation. Phase 1 : On minimise a₁ (ou maximise W = -a₁). Une itération du simplexe permet d'évacuer l'artificielle et de repasser en Phase 2. Après pivotage, la solution finale conduit aux coordonnées du point optimal dans l'espace 3D.

2. On se place dans le plan x₃ = 0

Le problème devient : Max Z = 3x₁ + 3x₂ Sous contraintes : -2x₁ + x₂ ≤ 2 x₁ ≤ 4 x₁ + x₂ ≥ 4 x₁, x₂ ≥ 0

a- Résolution graphique

• -2x₁ + x₂ ≤ 2 correspond à la zone sous la droite reliant (-1, 0) et (0, 2) s'étendant à droite.
• x₁ + x₂ ≥ 4 correspond à la zone au-dessus de la droite passant par (4, 0) et (0, 4).
• x₁ ≤ 4 est la frontière verticale. Les intersections définissent un triangle aux sommets suivants :
• A (4, 0) : Intersection de x₁ = 4 et x₁ + x₂ = 4.
• B (4, 10) : Intersection de x₁ = 4 et -2x₁ + x₂ = 2.
• C (2/3, 10/3) : Intersection de -2x₁ + x₂ = 2 et x₁ + x₂ = 4. La valeur de Z sur ces sommets : Z(A) = 12 Z(B) = 3(4) + 3(10) = 42 Z(C) = 3(2/3) + 3(10/3) = 12 Le maximum est au point B(4, 10).

b- Tableau de simplexe pour chaque point extrême L'énoncé demande de formuler mathématiquement les bases. À chaque sommet (A, B, C) correspond une base définie par les contraintes saturées (où les variables d'écart sont nulles) :

• Au point A (4, 0) : les contraintes x₁=4 et x₁+x₂=4 sont saturées, leurs variables d'écart sont hors base (nulles).
• Au point C (2/3, 10/3) : la première et troisième contraintes sont saturées.
• Au point B (4, 10) (Optimal) : la première et deuxième contraintes sont saturées. Le tableau final afficherait des coûts réduits tous négatifs ou nuls pour la maximisation, prouvant que Z=42 est le maximum réalisable.

Conclusion : Fixer une variable limite le problème à un plan, ce qui simplifie son observation et limite mécaniquement l'espace des solutions, dont le sommet optimal est graphiquement et algébriquement vérifié par le simplexe.

Méthode

Pour aborder ce type d'examen de Recherche Opérationnelle, respectez toujours ces étapes :

1. Extraction de données : Identifiez clairement vos variables de décisions (ce que vous cherchez), votre objectif (maximiser un gain, minimiser un coût) et les contraintes (limites de ressources, minima obligatoires). Attention aux unités (tonnes, pourcentages).
2. Standardisation scrupuleuse : N'oubliez jamais qu'une contrainte "≤" prend une variable d'écart positive (+x), et une contrainte "≥" prend une variable d'excédent négative (-x). En cas de contraintes ≥ ou d'égalité stricte, il faut injecter une variable artificielle et recourir à la méthode des deux phases (ou du Grand M).
3. Dualité et théorèmes : La dualité est un miroir analytique ; s'il est plus facile de résoudre le Dual à cause du nombre de variables, faites-le (Exercice 10). Utilisez le théorème des écarts complémentaires pour prouver rapidement la solution du dual si le primal est déjà résolu (Exercice 11) : variable > 0 implique contrainte duale saturée.
4. Précision algébrique : Tracez proprement vos graphiques et calculez toujours vos sommets par intersection algébrique stricte, sans vous fier uniquement au dessin, pour éviter les erreurs d'approximation.