Chapitre Un : Introduction à la recherche opérationnelle

La recherche opérationnelle (RO) a commencé juste avant la Seconde Guerre mondiale en Grande-Bretagne avec l'établissement

d'équipes de scientifiques pour étudier les problèmes stratégiques et tactiques liés à la militaire
opérations. L'objectif était de trouver l'utilisation la plus efficace des ressources militaires limitées.

ressources par l'utilisation de techniques quantitatives. Après la guerre, de nombreuses périodes de paix
des applications ont émergé, conduisant à l'utilisation de la RO et des sciences de la gestion dans de nombreuses industries

et occupations.
La recherche opérationnelle (RO) est l'étude de modèles mathématiques pour des organisations complexes.
L'optimisation des systèmes est une branche de la recherche opérationnelle qui utilise des techniques mathématiques telles que la programmation linéaire.

et la programmation non linéaire pour dériver des valeurs pour les variables du système qui optimiseront

performance. La science de la gestion ou la recherche opérationnelle utilise une approche logique pour résoudre des problèmes

résolution. Cette approche quantitative est largement utilisée dans les affaires. Domaines d'application
inclure la prévision, le budget d'investissement, la planification de la capacité, la gestion des horaires, la gestion des stocks.

gestion de projet et planification de la production.

Importance de la recherche opérationnelle

Il fournit un outil pour l'analyse scientifique et offre des solutions pour diverses entreprises.
problèmes.
Il permet un déploiement approprié et une allocation optimale des ressources rares.
Cela aide à minimiser les coûts d'attente et de service.
Cela permet à la direction de décider quand acheter et combien acheter grâce au
technique de planification des stocks.

Cela aide à évaluer les situations impliquant de l'incertitude.

Cela permet l'expérimentation avec des modèles, éliminant ainsi le coût de faire des erreurs.
tout en expérimentant avec la réalité.
Il permet un examen rapide et peu coûteux d'un grand nombre d'alternatives.
En général, la RO facilite et améliore le processus de prise de décision.
Domaines d'application
Contrôle des stocks
Conception des installations (décision de distribution)

Détermination du mélange de produits

Analyse de portefeuille
Allocation des ressources rares

1
 Décisions d'investissement

Gestion de projet.
CHAPITRE 2 : PROGRAMMATION LINÉAIRE (PL)

2.1. Concepts de base en PL

La programmation linéaire concerne l'optimisation (maximisation ou minimisation) d'un

fonction des variables connue sous le nom de fonction objectif, soumise à un ensemble d'équations linéaires et/ou
inégalités connues sous le nom de contraintes.

La fonction objective peut être le profit, le coût, la capacité de production ou toute autre mesure.
de l'efficacité qui doit être obtenue de la manière la meilleure ou optimale possible
Les contraintes peuvent être imposées par différentes ressources telles que la demande du marché,
processus de production et équipements, capacité de stockage, disponibilité des matières premières, etc.
Par linéarité, on entend une expression mathématique dans laquelle les expressions entre les
les variables sont linéaires.
Définition :
La programmation linéaire est une technique de modélisation mathématique utile pour l'allocation économique de la "rare" ou
"ressources limitées" (telles que la main-d'œuvre, le matériel, la machine, le temps, l'entrepôt, l'espace, le capital, etc.) à
plusieurs activités concurrentes (telles que des produits, services, emplois, nouveaux équipements, projets, etc.)
sur la base d'un critère donné d'optimalité. Toutes les organisations, grandes ou petites, ont à leur
disposition, hommes, machines, argent et matériaux, dont l'approvisionnement peut être limité. Approvisionnement de
les ressources étant limitées, la direction doit trouver la meilleure allocation des ressources afin de
maximiser le profit ou minimiser la perte ou utiliser la capacité de production au maximum
étendue.

Étapes dans la formulation d'un modèle de PL :

1. Identifier les activités (variables de décision clés).

2. Identifier la fonction objective comme une fonction linéaire de ses variables décisionnelles.
3. Énoncez toutes les limitations de ressources sous forme d'équations linéaires ou d'inéquations de ses variables décisionnelles.
4. Ajouter des contraintes non négatives en tenant compte des valeurs négatives de la
les variables de décision n'ont aucune interprétation physique valable.
5. Utilisez des techniques mathématiques pour trouver tous les ensembles possibles de valeurs des variables.
(inconnus) satisfaisant toutes les fonctions
6. Sélectionnez l'ensemble particulier de valeurs des variables obtenu à l'étape cinq qui conduit à la
réalisation de la fonction objectif.

Le résultat des quatre premières étapes s'appelle la programmation linéaire. L'ensemble des solutions
obtenue à l'étape cinq est connue sous le nom d'ensemble des solutions faisables et la solution finale
sélectionné à l'étape six est appelé solution optimale (meilleure) du problème de PL.

Un programme linéaire typique a deux étapes

La fonction objective
Les contraintes
. Contrainte technique, et
. La contrainte de non-négativité

2
La fonction objective : est une représentation mathématique de l'objectif global du
l'organisation exprimée comme une fonction linéaire de ses variables de décision (Xj) optimiser le critère
d'optimalité.
Il est également appelé la mesure de performance telle que le profit, le coût, le revenu, etc.

La forme générale de la fonction objective est exprimée comme :

Optimiser (Maximiser ou Minimiser) Z= C j X j
Où : Z est la mesure de la variable de performance (profit/coût), qui est la fonction de X1, X2,
…,Xn(Quantités d'activités)
Cj (C1, C2…C n) (les paramètres ou coefficients) représentent la contribution d'une unité de la
variables respectives X1, X2, …,Xnà la mesure de la performance Z (la fonction objective).

Les contraintes : les contraintes doivent être exprimées sous forme d'égalités ou d'inégalités linéaires.
variables de décision.
La forme générale des fonctions de contraintes est exprimée comme suit :

unijx j (<, >, ≤, =, ≥) bje

un11X1+a12X2+…+a1nXn(&lt;, &gt;, ≤, =, ≥) b1
a21X1+a22X2+…+a2nXn(<,>, ≤, =, ≥) b2
. . .
. . .
. . .
Am1Xm+am2X2+…+amnXn(<,>, ≤, =, ≥) bn

aijs'appellent coefficients techniques et mesurent la consommation par unité de

ressources pour exécuter une unité de variable inconnue (activités) Xj.
aij„speut être positif, négatif ou zéro dans les contraintes données.

Le bjereprésente la disponibilité totale de l'ithressource.

On suppose que bje≥ 0 pour tout i. Cependant, si b quelconqueje< 0, alors les deux côtés de la
la contrainte que je peux être multiplié par 1 pour faire bje> 0 et inverser l'inégalité de
la contrainte.

Exigences pour un problème de programmation linéaire : En termes généraux, la PL peut être utilisée pour
problèmes d'optimisation si les conditions suivantes sont remplies.

1. Il doit y avoir une fonction objective bien définie qui doit être soit maximisée soit
minimisé et qui peut être exprimé comme une fonction linéaire des variables de décision
2. Il devrait y avoir des contraintes sur la quantité ou l'étendue de l'atteinte de l'objectif et
ces contraintes doivent être capables d'être exprimées sous forme d'équations linéaires ou d'inéquations
en termes de variables.
3. Il doit y avoir des alternatives d'action. Par exemple, un produit donné peut être
traité par deux machines différentes et le problème peut être de savoir combien de
produit à attribuer à quelle machine.
4. Les variables de décision doivent être interrelations et non négatives.
5. La ressource devrait être en quantité limitée.

2.2. Hypothèses de la Programmation Linéaire

3
 Un modèle de programmation linéaire est basé sur les hypothèses suivantes :

1. Hypothèse de proportionalité : Une hypothèse de base de la programmation linéaire est que la proportionalité existe.
dans la fonction objectif et les contraintes. Il déclare que la contribution de chacun
l'activité par rapport à la valeur de la fonction objective Z est proportionnelle au niveau de la
activité Xj, tel que représenté par le CjXjterme dans la fonction objective. De même, le
la consommation de ressources de chaque activité dans chaque contrainte fonctionnelle est proportionnelle à
le niveau de l'activité Xj, comme représenté par le aijXjterme dans la contrainte.
Que se passe-t-il lorsque l'hypothèse de proportionnalité ne tient pas ? Dans la plupart des cas, nous
utiliser la programmation non linéaire.

2. Hypothèse d'additivité : Indique que chaque fonction dans un modèle de programmation linéaire
(que ce soit la fonction objective ou le côté gauche d'une contrainte fonctionnelle) est
la somme des contributions individuelles des activités respectives.
Que se passe-t-il lorsque l'hypothèse d'additivité ne tient pas ? Dans la plupart des cas, nous utilisons
programmation non linéaire.

3. Hypothèse de divisibilité : Indique que les variables de décision dans un modèle de programmation linéaire
sont autorisés à avoir des valeurs, y compris des valeurs non entières, qui satisfont le
contraintes fonctionnelles et de non-négativité. Ainsi, puisque chaque variable de décision
représente le niveau de certaine activité, on suppose que les activités peuvent être exécutées
à des niveaux fractionnaires.
Dans certaines situations, l'hypothèse de divisibilité ne tient pas car certains ou tous
les variables de décision doivent être restreintes à des valeurs entières. Pour ces restrictions entières
un modèle de programmation sera utilisé.

4. Hypothèse de certitude : Cette hypothèse stipule que les différents paramètres (à savoir,
les coefficients de la fonction objective, les coefficients dans les contraintes fonctionnelles aijet
valeurs des ressources dans les contraintes bjesont certainement et précisément connus et que leur
les valeurs ne changent pas avec le temps. Cependant, dans les applications réelles, la certitude
l'hypothèse est rarement satisfaite précisément. Pour cette raison, il est généralement important de
effectuer une analyse de sensibilité après qu'une solution a été trouvée qui est optimale sous les hypothèses
valeurs des paramètres.

5. Finitude : Un modèle de PL suppose qu'il existe un nombre fini (limité) de choix.

(des alternatives) sont disponibles pour le décideur et que les variables de décision sont
interdépendante et non négative. La condition de non-négativité montre que la PL traite de
situations de la vie réelle car il n'est pas possible de produire/utiliser des quantités négatives.
6. Optimalité : Dans la PL, la solution optimale se situe toujours au point extrême de l'ensemble de
solutions réalisables.

Définitions Importantes

Solution : L'ensemble des valeurs des variables de décision Xje(i=1, 2, ….,n) qui satisfont le
Les contraintes d'un problème de programmation linéaire sont considérées comme constituant la solution à ce problème de programmation linéaire.

Solutions réalisables : L'ensemble des valeurs des variables de décision Xje(i=1, 2… n) qui
satisfaire toutes les contraintes et les conditions de non-négativité d'un PL simultanément.
Solution infaisable : L'ensemble des valeurs des variables de décision qui ne satisfont pas toutes les
contraintes et conditions de non-négativité d'un PL simultanément.

4
 Solution optimale : Une solution faisable qui optimise (maximise ou minimise)
La valeur de la fonction objective du problème de LP donné est appelée un optimisateur de base.
solution faisable.
Solution non bornée : Une solution qui peut augmenter ou diminuer la valeur du
La fonction objective d'un problème de programmation linéaire indéfinie est appelée solution non bornée.

2.3. Méthodes de résolution des problèmes de programmation linéaire

Un problème de programmation linéaire peut être résolu par la méthode graphique ou en appliquant l'algèbre.
méthode, appelée la méthode du simplexe.

1. Méthode graphique : elle peut être utilisée lorsque seules deux variables sont impliquées. Cette méthode
se compose des étapes suivantes :
i. Représenter le problème donné sous forme mathématique.
ii. Tracer chacune des contraintes sur le graphique.
iii. Identifiez la région réalisable (ou espace de solutions) qui satisfait toutes les contraintes
simultanément. Tout point sur ou à l'intérieur de la zone ombrée représente une solution réalisable
solution au problème donné.
iv. Localiser les points de solution (identifier les points d'angle de l'espace de solution).
v. Déterminer la solution optimale. Une solution qui optimise la fonction objective.
vi. Interpréter les résultats
a) Problème de Maximisation : Il s'agit du cas de Maximiser Z avec des inégalités de contraintes dans
<form. Considérez deux modèles de téléviseurs couleur ; Modèle A et B, qui sont produits par une entreprise.
pour maximiser le profit. Le profit réalisé est de 300 $ de A et de 250 $ de l'ensemble B. Les limitations
sont
a. Disponibilité de seulement 40 heures de travail chaque jour dans le département de production,

b. Une disponibilité quotidienne de seulement 45 heures sur le temps machine, et

c. Capacité à vendre 12 ensembles du modèle A.

Combien de séries de chaque modèle seront produites chaque jour afin que le profit total soit de
aussi grand que possible ?
Ressources utilisées par unité
Contraintes Maximum disponible
Modèle A Modèle B Heures
(x1) (x2)
Heures de travail 2 1 40

Heures de machine 1 3 45
Heures de marketing 1 0 12

Profit 300 $ 250 $

5
Solution :
1. Formulation du modèle mathématique de PPL
Max Z=300X1+250X2
St:
2X1+X2< 40
X1+3X2< 45 Modèle de Programmation Linéaire
X1 < 12
X1, X2>0
2. Convertir les inégalités des contraintes en égalités
2X1+X2= 40
X1+3X2= 45
X1 = 12
3. Tracez le graphique en trouvant les intercepts x et y
2X1+X2= 40 ==> (0, 40) et (20, 0)
X1+3X2= 45 ==> (0, 15) et (45, 0)
X1 = 12 ==> (12, 0)
X1,X2= 0

X2
X1=0
40 X112

B
15

Faisable C (12, 11)

Région X2=0
X1
D
Un 12 20 45

4. Identifier la zone feasible de la solution qui satisfait toutes les contraintes. La région ombragée
dans le graphique ci-dessus satisfait à toutes les contraintes et il est appelé Région Faisable.
5. Identifiez les points d'angle dans la région réalisable. En vous référant au graphique ci-dessus, le coin
les points sont dans ce cas :
(0, 0)
6. Identifiez le point optimal.

Coins Coordonnées Max Z = 300 X1+250X2

A (0, 0) 0$

B (0, 15) 3750 $

C (12, 11) $ 6350 (Optimal)

D (12, 0) 3600 $

6
 7. Interprétez le résultat. En conséquence, le résultat mis en évidence dans le tableau ci-dessus implique que 12
des unités du Modèle A et 11 unités du Modèle B de téléviseurs devraient être produites afin que le total

le profit sera de 6350 $.

b) Problème de minimisation : Dans ce cas, nous traitons de Minimiser Z avec des inégalités de
contraintes dans>form. Supposons qu'un atelier de mécanique dispose de deux types différents de machines ;
Machine 1 et Machine 2, qui peuvent être utilisées pour fabriquer un produit unique. Ces machines varient
dans la quantité de produit fabriqué par heure, dans la quantité de travail utilisée et dans le coût de
opération. Supposons qu'une certaine quantité de produit doit être produite et que nous
Nous aimerions utiliser au moins la main-d'œuvre régulière. Combien devrions-nous utiliser sur chacun ?
machine afin d'utiliser les coûts totaux et de respecter toujours les exigences ?

Ressource utilisée Heures minimales requises

Articles
Machine 1 (X1) Machine 2 (X2)

Produit produit/heure 20 15 100

Travail/heure 2 3 15
Coût d'exploitation 25 $ 30 $

Solution :
1. Le modèle de programmation linéaire :

Min.Z 25X 13  0X 2
St:
20X 11  5X 2 100
Modèle de PL
2 X 13 X 2 15
X 1 ,X2 0
Cher étudiant, pouvez-vous tracer les contraintes ci-dessus ? Voir l'étape 2 ci-dessous.
2. Le graphique des équations de contrainte :

20X1+15X2=100 ==> (0, 20/3) et (5, 0)

2X1+ 3X2=15 ==> (0, 5) et (7.5, 0)
X1, X2= 0

X2
X1=0
A (0, 20/3)

Zone faisable

B(2,5, 3,33)
X2=0

X1
5 C (7,5, 0)

7
3. Les coins et la solution réalisable :

Coordonnées des coins Z min = 25 X1+ 30X2

A (0, 20/3) 200

B (2.5, 3.33) 162,5 (Optimal)
C (7.5, 0) 187,5

Puisque notre objectif est de minimiser les coûts, le montant minimum (162,5) sera sélectionné.
X1= 2,5
X2= 3,33 et
Min Z= 162,5
Remarque :
-Dans les problèmes de maximisation, notre point d'intérêt est de rechercher le point le plus éloigné de la

origine (Valeur maximale de Z).

-Dans les problèmes de minimisation, notre point d'intérêt est de trouver le point le plus proche de l'origine

(Valeur minimale de Z).

Exemple3. Une entreprise fabrique deux produits A et B sur lesquels les bénéfices réalisés par unité
sont respectivement de 3 Birr et 4 Birr. Chaque produit est traité sur deux machines M1et M2.
Le produit A nécessite une minute de temps de traitement sur M1et deux minutes sur M2, pendant que B
demande une minute sur M1et une minute sur M2. Machine M1est disponible pour pas plus de
7 heures 30 minutes, tandis que la machine M2est disponible pendant 10 heures chaque jour ouvrable. Trouvez le
nombre d'unités des produits A et B à fabriquer pour obtenir un maximum de profit.

Solution
Formulation du modèle LPP
Laisse x1et x2dénote le nombre d'unités des produits A et B à produire par jour.
L'objectif est de maximiser le profit.
c'est-à-dire. Maximiser Z = 3x1+ 4x2
Les contraintes portent sur le temps disponible pour les machines M.1et M2
c'est-à-dire,
pour la machine M1, 1x1+ 1x2≤ 450
pour la machine M2, 2x1+ 1x2≤ 600 Réponse : x1=0, x2=450 et Zmax=Birr 1800
Où x1, x2≥ 0.

Exemple 4 : Le poids standard d'une brique à usage spécial est de 5 kg et elle contient deux éléments de base.
ingrédients B1et B2. B1coûte 5 Birr/kg et B2coûts 8 Birr/kg. Considérations de résistance
indiquez que la brique ne contient pas plus de 4 kg de B1et un minimum de 2 kg de B2. Puisque le
la demande pour le produit est susceptible d'être liée au prix de la brique, trouvez graphiquement le
coût minimum de la brique satisfaisant aux conditions ci-dessus.

Solution
Formulation du modèle LPP
Soit les quantités en kg des ingrédients B1 et B2 à utiliser pour fabriquer les briques égales à x1
et x2 resp.
L'objectif est de minimiser le coût de la brique.
c'est-à-dire, Minimiser Z = 5x1+ 8x2 Réponse : x1=3kg, x2= 2kg, Zmin31 Birr

8
 Les contraintes sont
Concernant la quantité de l'ingrédient B1: x1≤ 4,
Sur la quantité de l'ingrédient B2: x2≥ 2,
Sur le poids de la brique x1+ x2= 5
Où x1, x2≥ 0.

2.4. Quelques cas particuliers de la programmation linéaire

Il existe certains cas particuliers dans les problèmes de programmation linéaire. Certains de ces cas sont
résulté des violations des hypothèses de base de la PL. Celles-ci incluent :

1. Solutions optimales multiples : C'est la situation où il existe plus d'une solution optimale.
se produit. Cela se produira chaque fois que l'équation de la fonction objectif représente une ligne parallèle
à une certaine limite de l'espace de solution délimité.
Résoudre les problèmes suivants graphiquement

110x1+110x2,
Objet à :
x1+ x2≤ 9,
x1≥ 2
20x1+ 50x2≤ 360,
x2≥ 3
x1, x2≥ 0.

[Link] non bornée : elle existe lorsqu'un problème de PL n'a aucune limite sur les contraintes c'est-à-dire que le
la région faisable n'est limitée en aucun respect. Théoriquement, la valeur de la décision
la variable augmente indéfiniment sans violer la faisabilité et la valeur de l'objectif
la fonction peut augmenter à l'infini. Cette situation se produit principalement lorsque l'hypothèse de
la finitude est violente.

Résolvez les problèmes suivants graphiquement

Max Z = 30x1+50x2
Soumis à :
3x1+x2≥ 9,
x1+ 2x2≥12,
x1+ 2x2≥9,
x1, x2≥ 0.
3. Solution non faisable : l'infaisabilité est une condition qui existe lorsqu'il n'y a pas de solution à
un problème de PL qui satisfait toutes les contraintes et les restrictions de non-négativité. Il
signifie que les contraintes dans le problème sont conflictuelles et incohérentes. Infeasibilité
dépend uniquement des contraintes et n'a rien à voir avec la fonction objective

Résoudre les problèmes suivants graphiquement

Max Z = 3x1+2x2
Objet à :
-2x1+ 3x2≤ 9,
3x1- 2x2≤-20
x1, x2≥ 0.

9
Contraintes Liantes et Non Liantes (Ressources)

Une fois que la solution optimale à un PPL est obtenue, nous pouvons classer les contraintes comme étant
liant et ou non-liant. Une contrainte est qualifiée de liant si le côté gauche et le
le côté droit de la fonction de contrainte s'égale lorsque les valeurs optimales de la décision
les variables sont substituées dans la contrainte. D'autre part, si les substitutions des
la valeur des variables de décision ne conduit pas à l'égalité entre le côté gauche et le côté droit
de la contrainte, il a été dit qu'elle n'est pas contraignante.

Contraintes redondantes : Si la contrainte, lorsqu'elle est tracée, ne fait pas partie de la frontière
marquant la région réalisable du problème, il est dit qu'elle est redondante. L'inclusion ou le
l'exclusion d'une contrainte redondante n'affecte évidemment pas la solution optimale à la
problème.

Exercices : Résoudre les LLP suivants à l'aide de la méthode graphique

1. a) Min Z = 2x1+x2
b) Max Z = 2x1+3x2 Réponse : a) x1=0, x2=2, Zmin=2, b) Non borné
Objet à :
x1- 3x2≤6,
2x1+ 4x2≥8,
x1- 3x2≥-6,
x1, x2≥ 0.

2. Max Z = 4x1+5x2 Solution non bornée

Sous réserve de :
x1+ x2≥1,
-2x1+ x2≤1,
4x1- x2≥ 1
x1, x2≥ 0.

2.5. La méthode du Simplex

Lorsqu'un certain nombre de variables dans un programme linéaire sont plus de deux, la méthode graphique
ne peut pas être utilisé en raison de la difficulté à représenter précisément les variables en utilisant plus d'un
plan bidimensionnel. Cela signifie qu'il est impossible de représenter ces variables dans le graphique
et évaluer les points extrêmes. Dans de tels cas, il existe une méthode complète pour résoudre un
problème de programmation linéaire appelé méthode du simplexe (algorithme du simplexe).

L'algorithme est un processus où une procédure systématique est répétée (itérée) sur et
encore et encore jusqu'à obtenir le résultat souhaité.

La méthode du simplexe (algorithme) est une procédure itérative qui consiste à passer d'une solution de base à une autre.
réalisable à un autre de telle sorte que les valeurs de la fonction objectif ne diminuent pas (dans
cas de problème de maximisation) et n'augmente pas (dans le cas de problème de minimisation).

Le processus se poursuit jusqu'à ce qu'une solution optimale soit atteinte, si elle existe, sinon, le
le problème peut être non borné ou non réalisable et la méthode du simplexe ne peut pas trouver le
solution.

10
Conditions pour l'application de la méthode du simplexe

Il y a certaines conditions qui doivent être remplies pour l'application de la méthode du simplex. Celles-ci
sont :
Le côté droit de chacune des contraintes bi doit être non négatif.

Si le problème de programmation linéaire a une contrainte négative, nous devons le convertir en

positive en multipliant les deux côtés par -1. Par exemple, si l'une des contraintes est donnée par
2x1- 4x2≥-8, nous ne pouvons pas appliquer la méthode du simplexe telle quelle. Donc, nous devrions la convertir en positif
en multipliant les deux côtés par -1. c'est-à-dire, -2x1+4x2≤ 8

2. Chacune des variables de décision du problème doit être non négative. Si l'un des choix
les variables ne sont pas réalisables, la méthode du simplexe ne peut pas être appliquée. Par conséquent, la faisabilité est un
condition nécessaire à l'application de la méthode du simplexe.

3. Les contraintes d'inégalité des ressources ou de toute autre activité doivent être converties en
équations.

Étant donné que la méthode du simplexe ne peut pas être appliquée en cas d'inégalités, il est obligatoire que
ces inégalités doivent être transformées en équations. Il y a certaines variables qui nous aident à
convertissez ces inégalités en équations. Ces variables sont : les variables de marge et de surplus.
Les variables d'écart : ce sont des variables qui peuvent transformer les inégalités de type "moins que" en équations.

Les variables d'écart représentent la quantité non utilisée d'une ressource donnée par les activités ou le temps d'inactivité.
ressources. Par exemple, si l'une des contraintes est donnée comme :
. x1≤ 4 nous pouvons convertir ceci en équations en introduisant une variable d'ajustement.
. x1+S1=4. Les valeurs de S1variera de zéro à quatre. c'est-à-dire, si x1=0, S1=4 signifiant que
tous les ressources disponibles ne sont pas utilisées. Si x1=4, S1=0 signifiant que tout est disponible
La ressource est entièrement utilisée et il n'y a aucune ressource inutilisée restante.

Variables de surplus : si l'inéquation de contrainte est de type supérieur, alors nous pouvons la convertir.
dans l'équation en soustrayant une variable appelée variable excédentaire. Les variables excédentaires représentent
que la demande en ressources est supérieure à la disponibilité.

Les variables excédentaires sont le négatif des variables d'écart. Par exemple, si l'une des
la contrainte est donnée comme :
x2≥ 8, cette inégalité peut être convertie en équation en introduisant une variable excédentaire comme
x2–S1= 8.

Remarque : les variables de marge et de surplus entrent dans la fonction objective avec des coefficients nuls.

Procédures de la méthode du simplexe

Étape 1 : Exprimez le problème sous forme standard.

Le problème donné est dit être exprimé sous forme standard si les variables de décision ne sont pas
négatif, le membre de droite des contraintes est non négatif et les contraintes sont exprimées comme
Des variables de relaxation non négatives sont ajoutées au membre de gauche des contraintes pour convertir
les en équations.

11
Exemple : Max Z = 3x1+4x2
Objet à :
x1+ x2≤450
2x1+x2≤600,
Où x1, x2≥ 0.
La forme standard du modèle LP ci-dessus est :
Max Z = 3x1+4x2 +0S1+0S2,
Sous réserve de :
x1+ x2+ S1=450,
2x1+ x2+S2= 600,
Où x1, x2,S1, S2≥ 0

Étape 2 : Établir la solution initiale

Pour mettre en place la solution initiale, nous devons d'abord déterminer les éléments de base et non-
variables de base.
Les variables d'assouplissement dans le tableau initial deviennent des variables de base et les variables de décision sont non-
variables de base. Si nous avons n inconnues et m contraintes, alors m variables devraient être
les variables de base et les autres (n-m) doivent être non-basiques de sorte que leur valeur soit nulle.
Les variables de base sont celles dont les valeurs sont obtenues à partir de la solution de base.
alors que les variables non-basiques sont celles dont les valeurs sont supposées être nulles dans le basique
solution.

La solution initiale de la forme standard ci-dessus peut être exprimée dans le

tableau simplex suivant
3 4 0 0
Contribution/unité Cj Matrice corporelle Matrice identité
CB BV x1 x2 s1 s2 b
0 s1 1 1 1 0 450
0 s2 2 1 0 1 600
Interprétation :
1. La première ligne indique les coefficients Cj des variables dans la fonction objective et
ils restent inchangés dans les tableaux suivants.
2. La première colonne CBreprésente les coefficients des variables de base actuelles dans l'obj.
amusant. La deuxième colonne est la colonne de base et elle représente les variables de base de la
solution actuelle.
3. La matrice de corps (matrice des coefficients) représente les coefficients des contraintes.
Ces coefficients représentent la quantité de ressources nécessaires pour prendre une unité de décision
variable.
4. La matrice identité représente les coefficients des variables d'écarts dans les contraintes.
5. Les valeurs x de la colonne b/solutionBla colonne indique les quantités de la variable
ressources ou valeurs R.H.S des contraintes ou valeurs des variables de base, S1et S2dans
la solution de base initiale.

Étape 3 : Effectuer le test d'optimalité

Le test d'optimalité peut être basé sur le signe des membres de la ligne d'index.

12
 Contribution/unité Cj 3 4 0 0
Matrice corporelle matrice identité
CB BV x1 x2 s1 s2 b
0 S1 1 (1) 1 0 450 ligne clé
0 S2 2 1 0 1 600
Zj 0 0 0 0 0
∆j = Zj- Cj -3 -4 0 0
↑K
Où : Zj=∑CBiunijet Z=∑CBixBi
Valeurs dans le Zjreprésente la contribution perdue par unité des variables. c'est-à-dire, les montants
par quelle contribution serait réduite si l'une des variables correspondantes x1, x2…
a été ajouté.
∆jest également appelé la ligne d'index. Cette ligne détermine si la solution actuelle est ou non
est optimal. Les coefficients dans cette rangée représentent le profit net (ou la contribution nette ou le net
amélioration marginale) des valeurs de la fonction objective Z pour chaque unité de
variable de colonne respective introduite dans la solution. Par exemple, comme x1augmente de
une unité Z augmentera de 3 unités.
Un coefficient positif dans le Zj-Cjla ligne indique le montant par lequel l'objectif
la fonction sera diminuée si une unité de la variable correspondante est introduite dans le
solution tandis qu'un coefficient négatif indique le montant par lequel le profit sera
augmenté si une unité de la variable correspondante est introduite dans la solution. Ces
Les coefficients ou éléments sont connus sous le nom de prix de shadow ou de valeurs comptables ou imputées.
valeurs des ressources.
La solution est optimale si tous les éléments de la ligne d'index sont positifs et nuls. Si au moins
un des éléments de la ligne d'index est -ve, la solution donnée n'est pas optimale et va vers
la prochaine étape. La prochaine itération nous donnera la prochaine solution de base réalisable ajustée.

Étape 4 : Itérer vers la solution optimale

À chaque itération, la méthode du simplexe déplace la solution de base réalisable actuelle vers une solution améliorée.
solution basique faisable. Cela se fait en remplaçant une variable basique actuelle par une nouvelle variable non-
variable de base comme suit.

Colonne pivot : La colonne qui a la valeur négative maximale de Zj-Cj,est celui qui
devrait entrer la solution (en entrant la variable).

Ligne pivot : L'élément situé à l'intersection de la colonne clé et de la ligne clé est appelé clé.
élément pivot et est entouré de ( ). Cet élément pivot correspond à celui qui quitte
variables. Laisser variable= (xbje/aij, unij) <0.

Pour trouver la nouvelle solution :

Si l'élément clé (numéro pivot) est 1, alors la ligne reste la même dans le nouveau
tableau simplex

Si l'élément clé (nombre pivot) est différent de 1, alors divisez chaque élément dans le pivot
ligne (y compris les éléments dans x)bcolonne) par le numéro pivot, pour trouver les nouvelles valeurs de
la ligne dans le nouveau tableau du simplexe.

13
 Les nouvelles valeurs des éléments dans les lignes restantes pour le nouveau tableau simple peuvent
peut être obtenu en effectuant des opérations élémentaires sur toutes les lignes afin que tous les éléments
sauf que l'élément clé dans la colonne clé est zéro. c'est-à-dire,

Non. dans nouvelle ligne = Non. dans ancienne ligne ± (Non. au-dessus ou en dessous de l'élément clé) (correspondant
Non. dans l'ancienne rangée)

Si tous les rapports sont négatifs ou infinis, la solution est non bornée.
La prochaine solution ne sera réalisable que si la ligne contenant le minimum (non négatif)
le ratio est sélectionné comme ligne clé ; dans le cas où une ligne contenant un ratio plus élevé (non négatif) est
marqué comme ligne clé, la solution suivante deviendra infaisable et il y aura
certaines valeurs négatives dans la colonne b qui sont illogiques.

Contribution/unité 3 4 0 0
Cj Matrice corporelle Matrice d'identité
CB BV x1 x2 s1 s2 b
4 X2 1 1 1 0 450
0 S2 1 o -1 1 150
Zj 4 4 4 0 1800 2ndf. solution
∆j = Zj- Cj 1 0 4 0
Valeur de perte marginalePrix d'ombre

Étape 5 : Effectuer le test d'optimalité pour la deuxième solution réalisable

Si une valeur négative se trouve dans la ligne des indices, alors la solution donnée n'est pas optimale. Donc nous
procédez à l'étape 4 à nouveau. Cependant, les valeurs dans la ligne d'index ne sont pas négatives.
la solution est optimale. Par conséquent, la solution optimale est x1=0, x2= 450,Zmax=1800.

Remarques :

1. La solution optimale obtenue ci-dessus satisfait les restrictions de non-négativité. Elle indique
qu'aucun autre ensemble de valeurs de x1et x2donne une valeur Z aussi élevée.

Variable d'écart s1n'existe pas dans la colonne de base. Cela signifie que la première ressource est
pleinement utilisé. Cependant, s2existe dans la colonne de base et sa valeur est 150. Cela signifie 150
les unités de la deuxième ressource restent non utilisées.

3. Éléments dans le Zj- La ligne Cj sous les variables d'assouplissement indique le prix d'ombre (ou comptabilité
valeurs ou valeurs imputées) des ressources.
4 et 0 sont appelés les prix ombres de la première et de la deuxième ressource respectivement.
4 sous s1la colonne indique que si une unité de la première ressource est utilisée en plus, alors le
la valeur de Z augmentera de 4 unités. Par conséquent, si nous voulons augmenter Z, cela devrait
augmentez la première ressource.
La capacité de la deuxième ressource n'a pas été pleinement utilisée ; il n'y aura pas d'utilisation.
l'augmentant davantage.

14
Exercices : Résoudre les problèmes suivants par la méthode du simplexe et interpréter les résultats.

1. Max Z = 40x1+80x2
Sous réserve de : Réponse. x1=9 unités, x2=10 unités, Zmax=1160
2x1+ 3x2≤ 48,
x1≤ 15, s1=20, s2=0, s3=20
x1≤ 10,
x1, x2≥ 0.

2. Max Z = 2x1+5x2
Sous réserve de : Réponse. x1=0unités, x2=380/9 unités, x3=470/3 unités, Zmax=3200/3
x1+ 4x2≤ 24, s1=0, s2=0, s3=1970/9
3x1+ x2≤21,
x1+ x2≤ 9,
x1, x2≥ 0.

Technique des variables artificielles

Il existe de nombreux problèmes de programmation linéaire où les variables d'écart ne peuvent pas fournir un
solution. Dans ces problèmes, au moins une des contraintes est de type (≥) ou (=). Dans de tels cas
nous introduisons un autre type de variables appelées variables artificielles.

Les variables artificielles sont fictives et n'ont aucune signification physique ou économique.
considérer le rôle des variables d'écart lors de la première itération, pour n'être remplacées qu'à une étape ultérieure
itération.

Les variables artificielles ne sont qu'un dispositif pour obtenir la solution de base faisable de départ et ensuite
La procédure du simplexe habituelle sera adoptée jusqu'à ce que la solution optimale soit obtenue.

Les variables artificielles sont exprimées par la lettre majuscule "A" et utilisées pour le type "≥" de
inégalités et équations "=".

Les variables artificielles entrent dans la fonction objective avec un coefficient "M", c'est-à-dire qu'elles entrent dans
la fonction objective avec une valeur négative (-M) pour la maximisation et une valeur positive (+M) pour
minimisation, où M >0.

M désigne un énorme nombre positif (une pénalité très importante), pour cela l'entreprise manipule le
variables artificielles.

Étapes de l'algorithme de la méthode du grand M

Étape 1 : Exprimer le problème LP sous forme canonique en introduisant des variables d'écart.

Ces variables sont ajoutées au membre de gauche des contraintes de (≤) et soustraites de
les contraintes de type (≥).
Étape 2 : Ajouter une variable artificielle non négative (A) correspondant aux contraintes ayant « ≥ » et
équations « = ».

Étape 3 : Mettre en place la solution initiale

15
 Pour mettre en place la solution initiale, nous devons d'abord déterminer les éléments de base et non-
variables de base. Dans la solution initiale, les variables originales ont une valeur nulle, donc elles sont
variables non basiques.

Étape 4 : Résoudre le LPP modifié par la méthode du simplexe.

Lors des itérations, en utilisant la méthode du simplexe, l'un des trois cas suivants peut se produire
se lever

a. Si aucune variable artificielle ne reste dans la base et que la condition d'optimalité est satisfaite,
alors la solution est une solution réalisable optimale.
b. Si au moins une variable artificielle apparaît dans la base au niveau zéro et d'optimalité
la condition est satisfaite, alors la solution est une solution optimale faisable. Mais c'est un
solution dégénérée. Les contraintes sont cohérentes bien qu'il puisse y avoir de la redondance dans
eux. La redondance signifie que le problème a plus que le nombre requis de
contraintes.
c. S'il y a au moins une variable artificielle dans la base à un niveau non nul (avec +ve
valeur dans la colonne b) et la condition d'optimalité est satisfaite, alors l'original
le problème n'a pas de solution réalisable. Par conséquent, le problème original n'a pas
solution réalisable car elle contient une variable artificielle (une pénalité très élevée M).
Remarques :

1. Les variables d'écart sont ajoutées aux contraintes de type (≤) et soustraites de
contraintes de type (≥).
2. Des variables artificielles sont ajoutées aux contraintes de type (≥) et (=). Égalité
les contraintes n'exigent ni variables d'écart ni variables de surplus.
3. Les variables, autres que les variables artificielles, peuvent réapparaître lors des itérations, une fois éliminées.
dans une itération ultérieure.

Exemple :

Max Z = 3x1- x2
Sous réserve de :
2x1+ x2≤ 2,
x1+ 3x2≥3,
x2≤ 4,
x1, x2≥ 0.

Étape 1 : Formulez le problème sous forme standard

Max Z = 3x1- x2 +0s1+0s2+0s3-MA1,

Sous réserve de :
2x1+ x2+ s1= 2,
x1+ 3x2- s2+A1=3,
x2+ s3= 4,
x1, x2, s1, s2, s3, A1≥ 0.
Étape 2 : Trouver une solution de base réalisable initiale

Substituer x1=x2=s2=0, alors la b.f.s initiale obtenue est : s=2, A1=3, s3=4, Z=-3M

16
Étape 3 : effectuer un test d'optimalité
Depuis le Zj- Cj est -ve sous certaines colonnes de variables, la solution n'est pas optimale et peut être
amélioré

Étape 4 : Itérer vers la solution optimale

Les itérations successives donnent les tableaux suivants

Tableau 1.
3 -1 0 0 0 -M
Cj
CBBV x1 x2 s1 s2 S3 Un1 b r
0 s1 2 1 1 0 0 0 2 2
-M A1 1 (3) 0 -1 0 1 3 1
0 S3 0 1 0 0 1 0 4 4
Zj=∑ CBaij-M -3M 0 M 0 -M -3M i.s
∆j = Zj- Cj-M-3 -3M+1 0 M 0 0
↑K
Tableau 2.
Cj 3 -1 0 0 0
CB BV x1 x2 s1 s2 S3 b r
0 s1 (5/3) 0 1 1/3 0 1 3/5
-1 x2 1/3 1 0 -1/3 0 1 3
0 S3 -1/3 0 0 1/3 1 3 -9
Zj=∑ CBaij -1/3 -1 0 1/3 0 -1 2ndb.f.s
∆j = Zj- Cj -10/3 0 0 1/3 0
↑K
Tableau 3.
Cj 3 -1 0 0 0
CB BV x1 x2 s1 s2 S3 b
3 x1 1 0 3/5 1/5 0 3/5
-1 x2 0 1 -1/5 -2/5 0 4/5
0 S3 0 0 1/5 2/5 1 16/5
Zj=∑ CBaij 3 -1 2 1 0 1
∆j = Zj- Cj 0 0 2 1 0

Par conséquent, la solution optimale est donnée par :

X1=3/5, x2=4/5, Zmax=1
Exercice : résoudre le p.l.f. LPP
Max Z = x1+2x2+3x3- x4
Sous réserve de :
x1+2x2+3x3=15
2x1+x2+5x3=20
x1+2x2+x3+ x4=10
x1x2x3, x4≥0

Indice : la forme standard est :

Max Z = x1+2x2+3x3- x4-MA1-MA2-MA3,
Sous réserve de :
x1+2x2+3x3 +0x4+A1+0A2+0A3=15

17
 2x1+x2+5x3+0x4+0A1+A2+0A3=20
x1+2x2+x3+ x4 +0A1+0A2+A3=10
x1,x2x3, x4Un1, A2, A3≥0

Cas spéciaux dans l'application de la méthode du simplexe

1. Détermination des vainqueurs dans la méthode du simplexe

Lors de l'opération de l'itération simplex, un tirage au sort peut se produire et nous pouvons faire face à une indifférence dans
choisir la variable d'entrée ou la variable de sortie. Lorsque des égalités peuvent se produire, les éléments suivants sont importants à

faire:

Lier le choix des variables d'entrée : la variable non basique qui entre dans la base est le
celui qui donne la plus grande amélioration par unité dans la fonction objectif.
Variable ayant la valeur maximale négative dans un problème de maximisation et la valeur maximale positive
valeur dans le problème de minimisation dans Zj- La ligne Cj est la variable d'entrée. Une égalité dans le
L'entrée de variable existe lorsque plus d'une variable a la même valeur la plus grande (ou la plus petite).
Pour départager, l'un d'eux est sélectionné arbitrairement comme variable d'entrée.

Lier dans le choix de laisser des variables : C'est le cas lorsque le rapport est le même.
Cette égalité peut être résolue en choisissant arbitrairement l'une des variables.

2. Pas de variable de base sortante (fonction objective non bornée)

C'est le cas lorsque tous les éléments de la colonne pivot sont négatifs ou nuls, qu'aucune variable
qualifie pour être une variable de base sortante.
Dans ce cas, aucune solution finie ne peut être déterminée. Parce qu'une ou plusieurs des variables
peut être augmenté indéfiniment sans violer la faisabilité.
L'interprétation est que la fonction objective n'est pas contrainte ou la valeur de
la fonction objectif Z peut augmenter indéfiniment ou le modèle est mal construit.

3. Solutions optimales multiples

C'est le cas lorsque le PPL a plus d'une solution optimale.

Dans le tableau simplex si le Zj- La valeur Cj est zéro pour une variable non de base, cela indique que
l'existence de plus d'une solution optimale.

4. Solution infaisable

Si toutes les contraintes ne sont pas satisfaites simultanément, le modèle n'a pas de solution faisable.
solution.
Dans le cas de la méthode du grand M, si au moins une des variables artificielles a une valeur positive
et la solution est optimale, alors cela indique qu'il n'y a pas de solution faisable.

Cas de minimisation de la méthode du simplexe

Pour la plupart des parties de la recherche de solution pour le problème de minimisation en utilisant la méthode du simplexe sont
traité de la même manière que le problème de maximisation. Les trois exceptions clés sont :

Les coefficients des variables artificielles (M) ont un signe positif dans la fonction objectif.

18
 La sélection de la colonne pivot (variables entrantes) est basée sur le plus grand positif
nombre (valeur) dans l'index (∆j) rang.
La solution est optimale lorsque toutes les valeurs de l'indice (∆j) la rangée n'est pas positive.
L'autre méthode alternative pour résoudre un problème de minimisation est de le convertir en
maximisation. c'est-à-dire, Min Z=Max (-Z)

Exemple
12x1+20x2
Sous réserve de :
6x1+ 8x2≥100,
7x1+ 12x2≥120,
x1, x2≥ 0.

Forme standard :
Min Z = 12x1+20x2+0s1+0s2+MA1+MA2
Objet :
6x1+ 8x2 -s1+A1=100,
7x1+ 12x2–s2+A2=120
x1, x2, s1, s2, A1, A2≥ 0.

Cj 12 20 0 0 M M
CB BV x1 x2 s1 s2 A1Un2 b r
M A1 6 8 -1 0 1 0 100 25/2
M A2 7 (12) 0 -1 0 1 120 10
Zj=∑ CBaij13M 20M -M -M M M 220M↑I.S
∆j = Zj- Cj 13M-12 20M-20 -M -M 0 0
↑K

Cj 12 20 0 0 M M
CBBV x1 x2 s1 s2 Un1 Un2 b r
M Un1 4/3 0 -1 2/3 1 0 20 15
20 x2 7/12 1 0 -1/12 0 1 10 120/7
Zj=∑ CBunij -35/3+4/3M 20 -M -5/3+2/3M M M 200+20M
∆j = Zj- Cj 4/3M-1/3 0 -M 2/3M-5/3 0 0
↑K

Cj 12 20 0 0
CB BV x1 x2 s1 s2 b
12 x1 1 0 -3/4 1/2 15
20 x2 0 1 7/16 -3/4 5/4
Zj=∑ CBaij 12 20 -1/4 -9 205
∆j = Zj- Cj 0 0 -1/4 -9

2.6. Programmation par objectifs et entière

19
Programmation entière

Dans la PPL, toutes les variables de décision étaient autorisées à prendre n'importe quelle valeur non négative car c'est assez
il est possible et approprié d'avoir des valeurs fractionnaires dans de nombreuses situations. Cependant, il y a
plusieurs conditions dans les affaires et l'industrie qui mènent à des modèles de planification impliquant des entiers
variables valorisées. C'est-à-dire que de nombreux problèmes pratiques impliquent des variables de décision qui doivent être

valeur entière.
Il existe des cas où les valeurs fractionnaires des variables peuvent être dénuées de sens dans le contexte de
le problème de décision actuel. Par exemple :
En production, la fabrication est souvent planifiée en termes de quantités discrètes.
La production de bétail implique un nombre discret d'animaux
Les modèles de programmation entière nécessitent toutes les hypothèses implicites de la programmation linéaire.
modèles sauf que certaines variables spécifiques doivent être des valeurs entières.
Lorsque toutes les variables sont contraintes à être des entiers, on l'appelle un entier pur
modèle de programmation, et au cas où seules certaines des variables sont interdites d'avoir des valeurs entières
des valeurs, le problème est dit être un problème de programmation en nombres mixtes.
Il existe deux méthodes utilisées pour résoudre l'IPP, à savoir
i. La méthode de coupure fractionnaire de Gomory

ii. Méthode de branch and bound (méthode de recherche)

i.Méthode de coupe fractionnaire de Gomory (Algorithme)

Cette méthode consiste d'abord à résoudre le PPI comme un LPP ordinaire en ignorant la contrainte de
valeurs entières et ensuite en introduisant une nouvelle contrainte au problème de sorte que le nouvel ensemble de
La solution réalisable inclut toutes les solutions entières réalisables originales, mais n'inclut pas le
Une solution non entière optimale a été trouvée initialement. Cette nouvelle contrainte est appelée Coupure Fractionnaire ou
Contrainte gomorienne. Ensuite, le problème révisé est résolu par la méthode du simplexe jusqu'à obtenir un entier optimal.
la solution est obtenue.

La méthode de coupe fractionnaire de Gomory implique les étapes suivantes :

1. Résoudre le PPI comme un PL ordinaire en ignorant la restriction des valeurs entières
2. Tester l'intégralité de la solution optimale.
Si tous les Xbje≥ 0 et sont des entiers, une solution entière optimale est obtenue
S'il y a au moins un bjen'est pas un entier alors passez à l'étape suivante
3. Sélectionnez la ligne source
Si seulement un Xbjen'est pas entier, la ligne correspondant à la solution non entière sera
sois la ligne source

Si plus d'un Xbjeest non entier, choisissez la ligne ayant la plus grande fraction
partie (fje) comme une ligne source.
Dans ce cas, écrivez chaque Xbjeen tant que (Xbje= xbje+fJe): Où xbjeest la partie entière de Xbje
(solution) et fjeest la partie fractionnaire positive de Xbje. 0< fje<1
S'il y a une égalité lorsque deux lignes ou plus ont le même f positif plus grandje) sélectionnez
arbitrairement.
4. Trouvez la nouvelle contrainte (contrainte de Gomor) à partir de la ligne source.

20
 i.∑aijXj= Xbje
ii.∑((aij+fje)Xj= xbje+fje
iii.∑fjeXj≥ fje
iv.∑(-fje)Xj≤-fje
v.∑ (-fje)Xj+ Gje= -fje Contrainte gomorienne et G est le relâchement gomorien.

5. Ajoutez la nouvelle contrainte (gomorienne) au bas du tableau simplex obtenu à l'étape

1 et trouver la nouvelle solution réalisable.
Notez que les variables d'écart gomoriennes entrent dans la fonction objective avec un coefficient de zéro
6. Tester l'intégralité de la nouvelle solution
Encore si au moins un Xbje(solution) n'est pas un entier, allez à l'étape 3 et répétez le
procédure jusqu'à ce qu'une solution entière optimale soit obtenue.
Trouvez la solution entière optimale pour le LPP suivant

Max Z = x1+x2
Objet à :
3x1+ 2x2≤5,
x2≤ 2,
x1, x2≥ 0 et sont des entiers
Solution
1. Résoudre le PPI comme un PPL ordinaire en ignorant la restriction des valeurs entières.
Max Z = x1+x2+ 0s1+0s2
Objet :
3x1+ 2x2+s1= 5,
x2+s2= 2,
x1, x2s1, s2≥ 0 et sont des entiers
Cj 1 1 0 0
CB BV x1 x2 s1 s2 b r
0 s1 3 2 1 0 5
0 s2 0 1 0 1 2
Zj=∑ CBaij 0 0 0 0 0
∆j= Zj- Cj -1 -1 0 0

Cj 1 1 0 0
CB BV x1 x2 s1 s2 b r
1 x1 1 2/3 1/3 0 5/3
0 s2 0 1 0 1 2
Zj=∑ CBaij 1 2/3 1/3 0 5/3
∆j= Zj- Cj 0 -1/3 1/3 0

Cj 1 1 0 0
CB BV x1 x2 s1 s2 b r
1 x1 1 0 1/3 -2/3
1 x2 0 1 0 1 2
Zj=∑ CBunij 1 1 1/3 1/3 7/3
∆j= Zj- Cj 0 0 1/3 1/3

21
 2. Tester l'intégralité de la solution optimale.
La solution est x1=1/3, x2=2 et Z=7/3. Puisque x11/3 est une solution non entière donc
que la solution réalisable actuelle n'est pas une solution entière optimale.

3. Sélectionnez la ligne source. La ligne correspondant à une solution non entière.

x1+ 1/3s12/32= 1/3

4. Trouvez la nouvelle contrainte (contrainte gomorienne) à partir de la ligne source.
x1+ 1/3s1- 2/32= 1/3,
(1+0) x1+ (0+1/3) s1+ (-1 + 1/3) s2= 0+1/3, et éliminer la partie entière
1/3s1+1/3s2≥ 1/3
-1/3s1-1/3s2≤-1/3
-1/3s1-1/3s2+G1= -1/3 La contrainte gomorienne et G est le surplus gomorien.

5. Ajoutez la nouvelle contrainte (Gomorienne) au bas du tableau simplex obtenu dans

étape 1 et trouvez la nouvelle solution réalisable.

1Cj 1 0 0 0
CB BV x1 x2 s1 s2 G1 b
1 x1 1 0 1/3 -2/3 0 1/3
1 x2 0 1 0 1 0 2
0 G1 0 0 -1/3 -1/3 1 -1/3
Zj=∑ CBaij 1 1 1/3 1/3 0 7/3
∆j= Zj- Cj 0 0 1/3 1/3 0
La solution n'est pas réalisable car la solution (G1=-1/3) est négatif. Donc, G 1va partir
la base.
Sélectionnez la nouvelle contrainte comme ligne pivot. Afin de sélectionner la variable entrante,
utiliser :
j
Max(,aij 0)
aij
1 1
Max(,aij 0) Max(
Par conséquent,
j 3 , 3 ) (1,1)
aij 1 1
3 3

Choisissez arbitrairement (laissez s1est choisi comme variable d'entrée

Cj 1 1 0 0 0
CB BV x1 x2 s1 s2 G1 b
1 x1 1 0 0 -1 1 0
1 x2 0 1 0 1 0 2
0 s1 0 0 1 1 -3 1
Zj=∑ CBaij 1 1 0 0 1 2
∆j= Zj- Cj 0 0 0 0 1

22
Puisque tout ∆j≥ 0 et tous les Xbje≥ 0 et sont des entiers, la solution réalisable actuelle est un entier optimal
solution.
Par conséquent, la solution est x1=0, x2=2 et Z=2

Exercices :
1. Max Z = 4x1+3x2
Sujet à : Réponse : 1x=3, x2=0 et Z=12
x1+ 2x2≤ 4,
2x1+x2≤6,
x1, x2≥ 0 et sont des entiers

2. Max Z = 3x1+4x2
Objet : Réponse : 1x=1, x2=2 et Z=11
3x1+ 2x2≤8
x1+4x2≤ 10,
x1, x2≥ 0 et sont des entiers

ii. Méthode de branchement et de bornage (méthode de recherche)

Programmation par objectifs

Les entreprises ont généralement plus d'un objectif. Par exemple, maximiser le profit total, maximiser
part de marché, maintien de l'emploi total, fourniture d'une gestion écologique de qualité,
minimiser le niveau de bruit dans le voisinage, et répondre à de nombreux autres critères non économiques
objectifs. Il n'est pas possible pour le LP d'avoir plusieurs objectifs à moins qu'ils ne soient tous mesurés de la même manière
unités (telles que des dollars), une situation très inhabituelle. Une technique importante qui a été
développé pour compléter la PL est appelé programmation par objectifs.

La programmation par objectifs "satisfait", contrairement à la programmation linéaire qui essaie d'"optimiser". Satisfaire signifie

s'approcher le plus possible de l'atteinte des objectifs. La fonction objectif est la principale différence
entre la programmation par objectifs et la PL. Dans la programmation par objectifs, le but est de minimiser
variables de déviation, qui sont les seuls termes de la fonction objective.

Exemple de Programmation par Objectifs Harrison Electric Revu

ObjectifsLa direction de Harrison veut atteindre, chacun sur un pied d'égalité :
Objectif 1 : produire autant de bénéfices au-dessus de 30 $ que possible pendant la période de production.

Objectif 2 : utiliser pleinement les heures disponibles du département câblage.

Objectif 3 : éviter les heures supplémentaires dans le département d'assemblage.

Objectif 4 : respecter une exigence contractuelle pour produire au moins sept ventilateurs de plafond.

23