PROGRAMMATION LINÉAIRE

La programmation linéaire est le domaine de l'optimisation mathématique dédié à la maximisation ou

minimiser (optimiser) une fonction linéaire, appelée fonction objectif, de manière à ce que les
les variables de cette fonction soient soumises à une série de restrictions exprimées par un
système d'équations ou d'inéquations également linéaires. La méthode traditionnellement utilisée pour
Résoudre des problèmes de programmation linéaire est la méthode du Simplex.
Le problème de la résolution d'un système linéaire d'inéquations remonte, au moins, à Joseph
Fourier, après qui naît la méthode d'élimination de Fourier-Motzkin. La programmation
le linéaire se présente comme un modèle mathématique développé pendant la Seconde Guerre mondiale
pour planifier les dépenses et les retours, afin de réduire les coûts pour l'armée et d'augmenter les
pertes de l'ennemi. Cela est resté secret jusqu'en 1947. Dans l'après-guerre, de nombreuses industries l'ont
utilisé dans leur planification quotidienne.

Les fondateurs de la technique sont George Dantzig, qui a publié l'algorithme du simplex en 1947.
John von Neumann, qui a développé la théorie de la dualité la même année, et Leonid
Kantoróvich, un mathématicien d'origine russe, qui utilise des techniques similaires en économie auparavant
de Dantzig et a remporté le prix Nobel d'économie en 1975. En 1979, un autre mathématicien russe, Leonid
Khachiyan a conçu ce qu'on appelle l'Algorithme de l'ellipsoïde, à travers lequel il a démontré que le
Le problème de la programmation linéaire est résoluble de manière efficace, c'est-à-dire en temps.
polinomial.2 Plus tard, en 1984, Narendra Karmarkar introduit une nouvelle méthode du point
intérieur pour résoudre des problèmes de programmation linéaire, ce qui constituerait une avancée énorme dans
les principes théoriques et pratiques dans le domaine.

L'exemple original de Dantzig de la recherche de la meilleure affectation de 70 personnes à 70 postes

de travail est un exemple de l'utilité de la programmation linéaire. La puissance de calcul
nécessaire pour examiner toutes les permutations afin de sélectionner la meilleure affectation est
inmense (factorielle de 70, 70!) ; le nombre de configurations possibles dépasse le nombre de
particules dans l'univers. Cependant, il ne faut qu'un moment pour trouver la solution optimale
par le biais de la formulation du problème comme une programmation linéaire et l'application de
algorithme simplexe. La théorie de la programmation linéaire réduit de manière drastique le nombre de
solutions possibles réalisables qui doivent être révisées.

Existence de solutions optimales

Géométriquement, les contraintes linéaires définissent la région faisable, qui est un polyèdre.
convexe. Une fonction linéaire est une fonction convexe, donc un minimum local est un minimum
global ; une fonction linéaire est aussi une fonction concave, donc tout maximum local est aussi
un maximum global.

Comme les fonctions linéaires ne sont ni strictement convexes ni strictement concaves, les
les solutions optimales ne sont pas nécessairement uniques.

Si la région faisable est bornée et non vide, alors il existera au moins une solution optimale, puisque
qu'une fonction linéaire est continue et donc atteint un maximum dans toute région fermée
y acotée. Cependant, il se peut qu'il n'existe pas de solution optimale dans deux situations. Dans un premier
lieu, si la région faisable est vide, c'est-à-dire si aucun point ne vérifie toutes les contraintes,
Alors le problème est inviable. Deuxièmement, si la région faisable n'est pas bornée dans le
direction du gradient de la fonction objectif, le problème est non borné, et on peut trouver
points qui vérifient toutes les restrictions et avec une valeur aussi élevée que nous le souhaitons de la fonction
objectif.

Programmation entière
Dans certains cas, il est nécessaire que la solution optimale soit composée de valeurs entières pour certaines
des variables. La résolution de ce problème seobtient en analysant les alternatives possibles de
valeurs entières de ces variables dans un environnement autour de la solution obtenue en considérant
les variables réelles. Souvent, la solution du programme linéaire tronqué est loin d'être le
entier optimal, il est donc nécessaire d'utiliser un algorithme pour trouver cette solution de
forme exacte. Le plus célèbre est la méthode de 'Branch and Bound' ou Ébrancher et Borné par son
nombre en anglais. La méthode de Branch and Bound fait partie de l'ajout de nouvelles contraintes
pour chaque variable de décision (limiter) qui, lorsqu'elle est évaluée indépendamment (diviser), mène
à l'entier optimal.

LA FONCTION OBJECTIF
La fonction objective est étroitement liée à la question générale à laquelle on souhaite répondre. Si
Dans un modèle, différentes questions peuvent résulter, la fonction objectif serait liée à la question.
du niveau supérieur, c'est-à-dire, la question fondamentale. Ainsi, par exemple, si dans une situation on
désirent minimiser lescoûts, il est très probable que la question de niveau supérieur soit celle qui se
relier à augmenter l'utilité au lieu d'un interrogatoire qui cherche à trouver le moyen de
réduire les coûts.

LES VARIABLES DE DÉCISION

Similaire à la relation qui existe entre les objectifs spécifiques et l'objectif général, se comportent les
variables de décision concernant la fonction objective, car elles sont identifiées à partir de
une série de questions dérivées de la question fondamentale. Les variables de décision, sont en
théorie, facteurs contrôlables du système qui est en cours de modélisation, et en tant que tel, ceux-ci peuvent prendre
diverses valeurs possibles, dont il est nécessaire de connaître la valeur optimale, qui contribue à
réalisation de l'objectif de la fonction générale du problème.
LES RESTRICTIONS
Quand nous parlons des restrictions dans un problème de programmation linéaire, nous faisons référence à
tout ce qui limite la liberté des valeurs que peuvent prendre les variables de décision.
La meilleure façon de les trouver consiste à penser à un cas hypothétique dans lequel nous déciderions
donner une valeur infinie à nos variables de décision, par exemple, que se passerait-il si dans un
problème qui doit maximiser ses utilités dans un système de production de chaussures
décidions de produire une quantité infinie de chaussures ? Certainement, cela nous poserait maintenant
multiples interrogations, comme par exemple :

De quelle quantité de matières premières dispose-t-on pour les produire ?

De combien de main-d'œuvre disposez-vous pour les fabriquer ?
Est-ce que les installations de mon entreprise peuvent accueillir une telle quantité de produit ?
Ma force de marketing pourrait-elle vendre toutes les chaussures ?
Puis-je financer une telle entreprise ?
Eh bien, alors nous aurions découvert que notre système présente une série de limites,
tant physiques que contextuels, de telle sorte que les valeurs qui à un moment donné pourraient
nos variables de décision sont conditionnées par une série de restrictions.

EXEMPLE DE RÉSOLUTION D'UN PROBLÈME DE PROGRAMMATION LINÉAIRE

EL PROBLEMA
La fabrique de fils et tissus "SALAZAR" nécessite de fabriquer deux tissus de qualité différente T
y T’; on dispose de 500 kg de fil a, 300 kg de fil b et 108 kg de fil c. Pour obtenir un mètre
Pour produire un mètre de T’, il faut quotidiennement 125 g de a, 150 g de b et 72 g de c.
Par jour, il faut 200 g de a, 100 g de b et 27 g de c.

Le T se vend à 4000 $ le mètre et le T’ se vend à 5000 $ le mètre. S'il faut obtenir le maximum.
bénéfice, combien de mètres de T et T’ doivent être fabriqués ?
Le problème est recommandé à lire plus d'une fois pour faciliter la reconnaissance de
les variables, de plus il est fortement recommandé d'élaborer des tableaux ou des matrices qui facilitent
une plus grande compréhension de celui-ci.
ÉTAPE 1 : "FORMULER LE PROBLÈME"
Pour réaliser cette étape, nous partons de la question centrale du problème.
Et la formulation est :

Déterminer la quantité de mètres quotidiens de tissu type T et T' à fabriquer en tenant compte de la
bénéfice optimal par rapport à l'utilité.
ÉTAPE 2 : DÉTERMINER LES VARIABLES DE DÉCISION
En nous basant sur la formulation du problème, nos variables de décision sont :

XT : Quantité de mètres de tissu type T à fabriquer par jour

XT : Quantité de mètres quotidiens de tissu type T' à fabriquer
PASO 3: DETERMINAR LAS RESTRICCIONES DEL PROBLEMA
À cette étape, nous déterminons les fonctions qui limitent le problème, celles-ci sont données par
capacité, disponibilité, proportion, non-négativité entre autres.

2. MODÈLE DE PL
sont largement utilisés comme outil d'aide à la prise de décision tant par leurs
propriétés qui facilitent sa résolution, ainsi que sa pertinence à différents problèmes de
nature réelle. Ci-dessous, quelques exemples résumés en complexité avec le
objectif de montrer quelques applications typiques.
Applications de la Programmation Linéaire
Problème d'investissement : Considérez que vous disposez d'un capital de 21 000 dollars à investir
à la bourse. Un ami vous recommande 2 actions qui ont récemment été à
alza : Action A et Action B. L'Action A a un rendement de 10 % par an et l'Action B de
8% annuel. Son ami lui conseille d'avoir un portefeuille équilibré et diversifié et donc lui recommande
investir un maximum de 13 000 dollars dans l'Action A et au minimum 6 000 dollars dans l'Action B
B. De plus, l'investissement dans l'Action A doit être inférieur ou égal au double de l'investissement.
destinée à l'Action B. Vous souhaitez formuler et résoudre un modèle de Programmation Linéaire qui
permet d'obtenir la politique d'investissement qui permet d'obtenir le maximum de rentabilité (intérêt)
annuel.
Variables de Décision :
x = dollars invertis en Action A.
y = dollars invested in Action B.
Función Objetivo: Se busca maximizar la rentabilidad anual que resulta de invertir en los 2 tipos
de actions.
Maximiser 0.1x + 0.08y
Restricciones: Considera las recomendaciones de su amigo.
x + y≤21.000 On peut investir au maximum 21 000 dollars au total

x ≤13.000 Investir au maximum 13 000 dollars dans l'Action A

y≥6.000 Investir un minimum de 6.000 dollars dans l'Action B

x L'investissement dans A doit être inférieur ou égal au double de l'investissement dans

 2y≤0 B

x≥0, y≥0 Pas de négativité

Solution optimale : X = 13.000 Y = 8.000. Valeur optimale V(P) = 1.940 dollars. Il est recommandé
vérifier ces résultats à travers lerésolution graphiquey/o utilisantSolver d'Excel.
Problème de Processus de Production : Une entreprise produit trois types de meubles (A, B et C), chaque
l'un d'eux se vend à 200 $, 150 $ et 120 $ respectivement. Pour la production de ceux-ci
Muebles, l'entreprise dispose de 315 heures disponibles dans un atelier de découpe de bois, 110 heures.
disponibles dans un atelier de ponçage et 50 heures dans un atelier de peinture. Il a été estimé que le meuble
Un nécessite par unité 15 heures de travail dans l'atelier de découpe, 2 heures dans l'atelier de ponçage et 1
heure dans l'atelier de peinture (ces mêmes valeurs pour les meubles B et C sont 7,5:3:1 et 5:2:1,
respectivement). Il est nécessaire de formuler et de résoudre un modèle de Programmation Linéaire qui permet
trouver la quantité à fabriquer et à vendre de ces meubles de manière à ce que l'entreprise obtienne le
principal avantage.
Variables de Decisión:
X = Unités un élaborer y vendre supprimermeuble A.
Y = Unités a élaborer y vendre del meuble B.
Z = Unités à élaborer et vendre du meuble C.
De cette manière, le modèle d'optimisation qui permet de trouver le plan de production optimal est
le suivant

Ceci est le modèle utilisé pour exemplifier l'utilisation deSolveur d'Excel où l'on peut
trouver les résultats.
Problème de mélange de produits : Il y a 2 ingrédients pour fabriquer des bonbons, dont
La saveur variera en fonction de la proportion dans laquelle chacun des ingrédients intervient. Le
primer ingrediente se compra a $10 por kg. y el segundo a $20 por kg. El proceso de elaboración
suppose un coût de 5 $ par kg fabriqué, dont la quantité totale correspond simplement à la somme
des kg utilisés dans le mélange. La demande maximale pour un mois est chiffrée à 100 kg et le
precio de venta $50 kg. A la empresa no le interesa producir más de los que puede vender en el
Enfin, la composition de la masse doit contenir une proportion qui ne dépasse pas 50 %.
du premier ingrédient et 80 % du deuxième ingrédient. Il est nécessaire de déterminer combien de kg.
les bonbons doivent être fabriqués par mois et les proportions dans lesquelles ils doivent être utilisés
ingrédients pour obtenir un bénéfice maximal.
Variables de Décision :
X1: Kg a utiliser del ingrédient 1 en un mois
X2 : Kg à utiliser de l'ingrédient 2 en un mois
Fonction Objectif : Obtenir le maximum de profit de la vente des bonbons en déduisant les
coûts de production
Maximiser 50*(X1 + X2)–10*X1–20*X2 - 5*(X1 + X2) = 35*X1 + 25*X2
Restricciones:
Demande Maxima : X1 + X2 <= 100
Composición: X1/(X1 + X2) <= 50% o 0,5*X1–0,5*X2 <= 0
Composición: X2/(X1 + X2) <= 80% o -0,8*X1 + 0,2*X2 <= 0
Pas de négativité : X1,X2>=0

2. FORME CANONIQUE ET STANDARD DE LA PL

Un problème de programmation linéaire est dit écrit en « forme standard » si toutes les
Les restrictions du problème sont des équations linéaires et toutes les variables sont non négatives.
Nous dirons qu'un problème de programmation linéaire de minimisation est écrit en "forme
canónica" si toutes les variables sont non négatives et toutes les contraintes sont de type ≥.
Nous dirons qu'un problème de programmation linéaire de maximisation est écrit en "forme
canónica" si toutes les variables sont non négatives et toutes les contraintes sont du type ≤.
Observation: La méthode du simplexe, qui est une méthode pour résoudre des problèmes de programmation
linéaire, il est conçu pour être appliqué seulement après que le problème ait été écrit sous forme
standard.
Forme standard.
C'est l'égalisation des contraintes du modèle proposé, ainsi que l'augmentation des variables de
holgura, ou bien la resta de variables de excès.
Maintenant, on peut formuler le modèle mathématique pour ce problème général d'affectation de
ressources aux activités. Dans les données nécessaires pour un modèle de programmation linéaire qui gère
l'attribution de ressources à des activités particulières, ce modèle consiste à choisir des valeurs de
x1,x2,....,xn pour :

Optimizar (maximizar o minimizar) Z = c1x1 + c2x2 +....+ cnxn,

sous réserve des restrictions :
C11x1 + C12x2 +....+ C1nxn (≥,≤,=) cn1
C1x1 + C22x2 +....+ C2nxn (≥,≤,=) cn2
X1≥ 0, X2 ≥ 0, ......, Xn≥0

Exemple 1
Fonction objectif
Maximiser z=X1 + X2

5X1 + 3X2 ≤ 15
3X1 + 5x2 ≤ 15
xj ≥0; j=1,2

Étapes pour passer un problème de programmation linéaire au FORMAT STANDARD, se

considérant les phases suivantes :

1. Convertir les inégalités en égalités

On introduit une variable d'écart pour chacune des contraintes, afin de les convertir en
égalités, résultant du système d'équations linéaires :
Variable de holgure.
Il est utilisé pour convertir une inégalité de type "≤" en égalité. L'égalité est obtenue en ajoutant
sur le côté gauche de l'inégalité, une variable non négative, qui représente la valeur qu'il
il manque à gauche pour être identique au côté droit. Cela est connu sous le nom de variable de
holgura, et dans le cas particulier où les restrictions de type ≤ se réfèrent à la consommation
maximum d'une ressource, la variable ajoutée quantifie la quantité restante de ressource (quantité
non utilisée) en exécutant la solution optimale.

Tout problème de programmation linéaire formulé sous la forme de maximisation, avec toutes ses
les restrictions ≤ et avec la condition de non-négativité est appelée forme standard ou forme normale.
Ici, comme dans la méthode algébrique, nous devons obtenir une solution de base réalisable,
appliquant les variables de slack ou artificielles : le système d'équations restant ainsi :

Maximiser z=x1+x2
5X1+ 3X2 +X3=15
3X1 + 5X2 + X4 = 15
Xj ≥0; j=1,2,3,4
Les variables de base sont X3 et X4 et bien sûr dans la fonction objective Z.
2. Égaler la fonction objective à zéro
Nous avons besoin que la fonction objectif soit toujours une minimisation et que toutes les autres
restrictions soient des égalités.
Ce problème de programmation linéaire n'est pas encore sous forme standard. Donc, la prochaine étape à suivre
que nous devons réaliser est :
1. changer de maximisation à minimisation : multiplier la fonction objectif par -1.
Dans ce cas, la fonction objectif sera. Minimiser Z-X1-X2=0 Sujeta à :
5X1+ 3X2 +X3=15 31 + 5X2 + X4 = 15
 2e semaine :
FORMULATION OU ÉNONCÉ DE MODÈLES PL
Éléments de base d'unmodèleo mathématicien
Un modèle mathématique estproduitde l'abstraction d'unsystèmeréel, éliminant les
complexités et en faisant des hypothèses pertinentes ; une technique est appliquéemathématiqueset on obtient
une représentation symbolique de celui-ci.
Un modèle mathématique se compose d'au moins trois éléments ou conditions de base :
LesVariablesde décision, laFonctionObjectifet les restrictions.
Variables de décision et paramètres
Las variables de decisión son incógnitas que deben ser determinadas a partir de la solución del
modèle. Les paramètres représententles valeursconnus du système ou qui peuvent être contrôlés.
Les variables de décision sont représentées par : X1, X2, X3,…, Xn ou Xi, i = 1, 2, 3,…, n.
Fonction Objectif
La fonction objectif est une relation mathématique entre les variables de décision, les paramètres et une
magnitude qui représente l'objectif ou le produit du système. C'est lamesurede l'efficacité du
Modèle formulé en fonction des variables. Détermine ce qui va être optimisé (Maximiser ou
Minimiser).
La solution OPTIMA est obtenue lorsque levaleurde la Fonction Objectif est optimal (valeur
maximum ou minimum), pour un ensemble de valeursfactibles des variables. C'est-à-dire qu'il faut
remplacer les variables obtenues X1, X2, X3,…, Xn; dans la Fonction Objectif Z = f (C1X1,
C2X2, C3X3,…, CnXn) soumis aux restrictions du modèle mathématique.
Por ejemplo, si el objetivo es minimizar los coûtsde l'opération, la fonction objective doit
exprimer la relation entre lecoûtet les variables de décision, le résultat étant le coût le plus bas
de lessolutionsfactibles obtenues.
Restrictions
Les restrictions sont des relations entre les variables de décision et lesressourcesdisponibles. Les
les contraintes du modèle limitent la valeur des variables de décision. Elles se produisent lorsque les
les ressources disponibles sont limitées.
Dans le Modèle, en plus des contraintes, la Contrainte de Non
Négativité des variables de décision, c'est-à-dire : Xi = 0.
Par exemple, si l'une des variables de décision représente le nombre d'employés d'un atelier,
la valeur de cette variable ne peut pas être négative. Ou aussi, si l'une des variables est la quantité de
mesas à fabriquer, sa valeur ne pourra être égale à zéro ou supérieure à zéro, c'est-à-dire positive;
absurde d'obtenir comme résultat qu'on va fabriquer –4 tables.
La programmation linéaire est l'interrelation des composants d'un système, dans
termesmathématiciensque ce soit sous forme deéquationsdes inéquations linéaires appelées Modèle
deProgrammationLinéaire. C'est une technique utilisée pour développermodèlesmathématiques, conçue
pour optimiser l'utilisation des ressources limitées dansune entrepriseuorganisation.
Le Modèle deProgrammation Linéaire c'est une représentation symbolique de la réalité qui se
étudie, ou du problème qui va être résolu. Il se compose d'expressions logiquesmathématiques
contenan des termes qui signifient contributions : à lautilité(au maximum) ou au coût (avec
(minimum) in the Objective Function of the model. And toconsommationde ressources disponibles (avec
des égalités = ó = et égalités =) dans les restrictions.
Dans le présenttextenous développerons des Modèles Mathématiques de Programmation Linéaire de :
Maximisation et minimisation, qui seront indiquées dans la fonction objectif du modèle.
 Problèmes d'application pour formuler un modèle
1). [Link] usine produit deux types deproductos: M y N, les coûts
deproductionLes deux produits coûtent 3 $ pour le produit M et 5 $ pour le produit N.
Letempsle total de production est limité à 500 heures ; et les temps de production sont de 8
heures/unité pour le produit M et de 4 heures/unité pour le produit N. Formulez le Modèle
mathématique permettant de déterminer la quantité de produits M et N à produire, et qui optimise le
Coût total de production des deux produits.
Formulation du Modèle
Dans la formulation du modèle, nous pouvons nous aider de la représentation du Problème par
un organisateur graphique ou schéma :

Définition des Variables

On souhaite formuler un modèle mathématique pour déterminer la quantité qui doit être produite par
Chaque produit (M et N), nous aurons donc deux variables, représentées par : x1, x2.
Si étant : x1 = Quantité à produire du produit M,
x2= Quantité à produire du produit N
Fonction Objectif
Comment on ainformationdes coûts de production des produits M et N, l'objectif sera
les minimiser

Ensuite, la Fonction Objectif sera de Minimiser "C" égal au Coût total de production du produit M
plus le coût total de production du produit N.
Mathématiquement, la Fonction Objectif est :

Définition des Restrictions

 Le type de ressource dans le problème est le temps (cela peut être des heures)hommeu
heures machine).
Nous formulons la contrainte, en plaçant sur le côté gauche de l'inéquation la consommation unitaire
des produits M et N, et sur le côté droit la quantité disponible de la ressource (500 heures).

En résumé, nous avons le modèle mathématique de programmation linéaire du problème (un

modèle avec deux variables et une contrainte, prêt à appliquer unméthodede solution :

2). Lignes de Production.-Un entrepreneuril a 80 kg deaciery 120 kg dealuminiumet veut

fabriquer deux modèles de vélos : vélos de ville et vélos de montagne, pour les vendre à
lemarché200 S/. et 150 S/. respectivement pour chaque modèle, afin d'obtenir le maximum
bénéfice. Pour le vélo de promenade, il utilisera 1 kg d'acier et 3 kg d'aluminium, et pour le vélo
de montagne utilisera 2 kg des deuxmé[Link] le modèle mathématique de programmation
linéaire, qui permet de déterminer la quantité optimale de vélos à produire, pour obtenir le plus grand
bénéfice économique.
Formulation du Modèle
Representamos el Problema mediante un organizador gráfico o esquema

Définition des variables :

On souhaite déterminer la quantité de vélos à produire par modèle (promenade et montagne), par
Nous aurons donc deux variables.
Sean:x1= Cantidad de bicicletas de paseo a fabricar
x2= Cantidad de bicicletas de montaña a fabricar
Fonction Objectif
 L'objectif du problème est de maximiser les bénéfices économiques totaux (Z) des modèles de
vélos que fabriquera l'entrepreneur.
Prix deventede la bicicleta de paseo = 200 S/
Precio de venta de la bicicleta de montaña = S/. 150
Beneficio económico = Prixde vente unitaire x quantité à fabriquer
Bénéfice économique total de vélo de promenade = 200 x1
Bénéfice économique total de la bicyclette tout terrain = 150 x2
Ensuite, la fonction objectif sera : Maximiser : Z = 200 x1 + 150 x2
Définition des Restrictions
Nous avons élaboré un tableau dematière première consommée (Acier et Aluminium) par chaque modèle de
bicicleta (paseo y montaña) y su disponibilidad:
Modèle de vélo Acier Aluminium
Promenade 1 kg. 3 kg.
Montagne 2 kg. 2 kg.
Disponibilité dematièreprima 80 kg. 120 kg.
Restriction de la consommation d'acier dans la fabrication de bicyclettes :
1 x1 + 2 x2 < 80
Restriction de la consommation d'aluminium dans la fabrication de vélos :
3 x1 + 2 x2 < 120
Observation :
Le côté droit des contraintes, 80 et 120 représente la disponibilité en kg d'acier.
aluminium respectivement (matière première).
Le côté gauche dans les contraintes indique la consommation unitaire de matière première par chaque
modèle de vélo.
Condition de non-négativité : La production de chaque modèle de vélos peut être zéro (0)
ou supérieur à zéro, c'est-à-dire : x1, x2 = 0
Ensuite, le Modèle mathématique de Programmation Linéaire (avec deux variables et deux contraintes)
sera :

3). Cas deprise de dé[Link] avec lesdonnéesdu problème 2), précédent, si le

Un entrepreneur, en raison de contraintes économiques, décide de ne fabriquer qu'un seul modèle de vélo. Quel modèle ?
doit choisir ? Pourquoi ?
Les alternatives de fabrication se développent dans les contraintes du modèle mathématique ; et
La prise de décision se détermine en évaluant les alternatives obtenues dans la fonction objectif.
La décision à prendre, en raison d'une contrainte économique, est de produire un seul modèle de vélo qui
genere mayor beneficio al empresario. Luego desarrollamos las alternativas evaluando en las
restricciones del modelo:
La prise de décision s'effectue en évaluant dans la fonction objectif les alternatives de fabrication
obtenues par modèle de vélo. À suivreéchantillonleprocédureà réaliser.

Prise de décision :
Comme la fonction objective est de maximiser le bénéfice économique généré par leventes
nous avons pris la décision de ne fabriquer que des vélos de ville, car c'est le modèle qui va générer
plus grand gain, équivalent à S/. 8 000.
Observation :
Nous avons démontré l'importance de formuler un modèle mathématique approprié, car une erreur
dans la formulation du Modèle, cela peut nous amener à prendre une décision erronée qui peut
générer de graves conséquences pourl'entreprisevotre organisation.
 4. SOLUTION GRAPHIQUE
Le méthode graphique de solution de problèmes de programmation linéaire (PL) ne s'applique qu'à des problèmes
avec deux variables de décision ; cependant, elle illustre correctement les concepts qui nous
permettra de comprendre la nature du problème PL et par conséquent de comprendre les méthodes de solution
algébriques.
Tout d'abord, nous tracerons la région réalisable. Ensuite, nous illustrerons le comportement de
fonctions linéaires pour comprendre comment déterminer les points optimaux.

Exemple 1
Supposons que vous souhaitiez résoudre le problème PL :

Max z = 3 x + 2 y

sujet à

2x+y≤ 100R5
x + y ≤ 80R4
x ≤ 40R3
x ≥ 0 R1
y≥ 0 R2

Notre premier objectif est de tracer sur le plan la région réalisable ; c'est-à-dire de tracer l'ensemble de
points du plan qui satisfont aux contraintes. Notons que les contraintes doivent être respectées
simultanément. C'est-à-dire que les points doivent satisfaire la contrainte R1, la contrainte R2, et
ainsi de suite jusqu'à la contrainte R5. Du point de vue de la théorie basique des ensembles,
la région faisable est l'intersection des ensembles qui satisfont séparément chacun des
restrictions. Pour avancer vers notre objectif, nous devons savoir comment déterminer les points du plan
qui satisfont une inégalité linéaire. Nous distinguons deux cas :

Lorsque dans l'inégalité n'apparaît qu'une seule variable de décision (c'est-à-dire que l'autre variable a)
coefficient zéro

Lorsque dans l'inégalité apparaissent les deux variables de décision (c'est-à-dire que les deux ont
coefficient différents de zéro dans cette inégalité

L'analyse graphique est une alternative efficace pour faire face à la résolution de modèles de
Programmation Linéaire en 2 variables, où le domaine des points faisables (s'il existe) se
vous le trouverez dans le premier quadrant, comme produit de l'intersection des différentes contraintes
du problème linéaire.

Une des propriétés fondamentales d'un modèle de Programmation Linéaire qui admet une solution est
que celle-ci se trouvera au sommet ou à la frontière (tronçon) du domaine des points réalisables. Autrement dit, si
après avoir tracé le domaine et évalué les différents sommets pour choisir "le meilleur"
 candidat selon notre cas (la valeur de la fonction objectif sera celle qui nous permettra
discriminer lequel est le meilleur candidat en fonction de si nous maximisons ou minimisons.
Considérons un exemple introductif en 2 variables :
D) MIN 8X + 6Y
S.A. 2X + Y >= 10
...... .2X + 2Y >= 16
..... ..X>= 0, Y>= 0
Comentario:Nótese que corresponde alProblème Dual deP)cuya résolution se présente en
notre site en tant qu'exemple introductif à l'utilisation de Solver de MS Excel. Pour voir le
détail de la résolution graphique de P) il est recommandé à l'utilisateur de saisirICI.
Pour résoudre le problème D) nous traçons le domaine des points faisables et les courbes de niveau
associées à la fonction objectif :

La zone hachurée en vert représente le domaine des points réalisables du problème D), c'est
dire, ce sont les différentes combinaisons de valeurs que peuvent adopter les variables de décision qui
satisfont les contraintes du problème. Il convient de noter que cela correspond à un domaine non
Acoté, ce qui n'implique pas que le problème n'ait pas de solution.
D'autre part, nous savons que l'optimum d'un problème linéaire se trouve à un sommet ou sur la frontière.
du domaine des points réalisables. Dans ce cas, nous avons 3 sommets candidats pour l'optimal.
sont signalés par une flèche blanche et bleue. Le sommet(X,Y)= (0,10) avecV(P)=60;
(X,Y)=(2,6) avec V(P)=52 et (X,Y)=(8,0) avec V(P)=64. La valeur minimale pour la fonction objectif
se atteint en (X,Y)=(2,6) avec V(P)=52, qui se révèle être la Solution Optimale de D). Sans
embargo, une forme plus efficace d'obtenir l'optimal qui n'implique pas d'évaluer chaque sommet dans
La fonction objective déplace les courbes de niveau de la fonction objective dans la direction de
máximo decrecimiento (en el caso de un problema de minimización). Para un problema de
minimisation, le plus grand décroissement est atteint dans la direction du vecteur " - Gradient
F(X,Y)
Ensuite, l'optimum est atteint au dernier point où les courbes de niveau intersectent le domaine
de points réalisables dans la direction du maximum de décroissance, dont la solution est évidemment
correspond à (X,Y)=(2,6) avec V(P)=52.

ANALYSE DE SENSIBILITÉ GRAPHIQUE POUR 2 RESTRICTIONS

Une fois qu'un modèle de Programmation Linéaire est résolu, il est utile de faire une analyse de sensibilité.
qui permet d'identifier comment les variations dans les résultats du problème affectent
paramètres de celui-ci, sans que cela nécessite de résoudre à nouveau le problème.
1. Variation des Coefficients de la Fonction Objectif : La question à laquelle nous cherchons à répondre
quel est l'intervalle de variation pour les coefficients de la fonction objectif (chaque coefficient
se analyse séparément) qui maintient la Solution Optimale actuelle.
Une première approche consiste à considérer les pentes des contraintes actives au point optimal, c'est
dire, ces restrictions qui sont respectées à égalité (dans notre cas contrainte 1 et 2). La
la contrainte 1 (2X + Y >=10) a une pente de -2. La contrainte 2 (2X + 2Y >=16) a une pente de -
D'autre part, la pente de la fonction objectif étant C1=8 et C2=6 est -4/3.
En conséquence, la solution optimale actuelle est maintenue si la pente de la fonction objectif
(courbes de niveau) varient dans l'intervalle des pentes des restrictions actives actuelles. Cela
es:
-2 <= -C1/C2 <= -1 (Nous multiplions par -1)
2 >= C1/C2 >= 1
Si nous fixons C2=6.
2 >= C1/6 >= 1
12 >= C1 >= 6 (Garantit la solution optimale actuelle avec C2 fixe)
Si nous fixons C1=8.
2 >= 8/C2 >= 1
8 >= C2 >= 4 (Garantit la solution optimale actuelle avec C1 fixe)
Notez qu'aux extrémités des intervalles, en plus d'inclure la solution optimale actuelle, il y a aussi
considérant de nouvelles combinaisons du domaine qui maintiennent la Valeur Optimale et qui sont également
Solution optimale de D). Cette situation détermine que le problème a des solutions infinies.
optimales.

2. Variation des côtés droits des restrictions(calcul du "prix ombre")Une

Une question courante dans l'analyse de sensibilité est de voir l'impact qu'elle a sur la valeur optimale.
une variation marginale du côté droit de l'une de ses contraintes (tant augmentation ou
décroissance). L'impact sur la valeur optimale par unité de variation du côté droit d'une
la restriction (en maintenant le reste constant) est le prix ombre associé à cette restriction. Dans
dans notre exemple, considérez que le côté droit de la contrainte 1 (actuellement b1=10)
correspond à une ressource rare (exemple : heures homme, argent, temps, etc). Si nous savons que le
valeur optimale actuelle V(P)=52, nous aimerions savoir par exemple, combien augmenterait la valeur optimale
si nous disposions d'une unité supplémentaire de la ressource rare (c'est-à-dire, en passant ab1*=11).
Une forme équivalente soulève souvent cette inquiétude comme : Quel est le maximum que l'on peut...
serait-il disposé à payer par unité supplémentaire de la ressource associée à la première contrainte ? Ce
la valeur correspond au prix ombre.

Prix Sombra Restriction 1 : D'abord, on considère le déplacement parallèle de la Restriction

1 (tant dans le sens de croissance ou de décroissance du côté droit), de sorte que la Solution
Optimum continue à se trouver avec les restrictions actuelles actives (dans notre cas R1 et R2).
exemple, déplaçant R1 dans la direction de son décroissement, le dernier point où ils s'intersectent
R1 avec R2 serait dans la paire ordonnée (X,Y) = (0,8). L'utilisateur est invité à calculer le maximum.
variación pour R1 qui se produit en (X,Y)=(8,0).
 En conséquence, le Prix Ombre associé à la Restriction 1 est donné par :

Un Prix Ombre égal à 2 indique par exemple que si le côté droit augmente de 1 unité, le
le bénéfice supplémentaire (augmentation de la valeur optimale) est de 2 unités. De plus, un
la question fréquente consiste à identifier l'intervalle de variation où le prix sombra
calculé est valide. La valeur maximale que peut prendre le côté droit de R1 est b1*, de
modo que la nueva solución se siga encontrando con R1 et R2 actives. La valeur de b1* est obtenue
en évaluant(X,Y)=(8,0) dans la Restriction 1:2*(8) + 1*(0)=16. Suivant un raisonnement similaire le
le minimum que peut atteindre le côté droit de R1 est b1, évalué en (X,Y)=(0,8) en
R1 se obtient : 2*(0) + 1*(8) = 8.
Il est recommandé à l'utilisateur de calculer le Prix Ombre pour la Restriction 2, lequel
correspond à 2. Si vous souhaitez consulter un nouvel exemple, accédez àRésolution Graphique en
Programmation Linéaire. (Sitio: Recherche Opérationnelle

ANALYSE DE SENSIBILITÉ GRAPHIQUE POUR 3 RESTRICTIONS

La méthodologie et les concepts présentés pour le cas de 2 restrictions ne diffèrent pas, cependant,
il faut avoir un soin particulier à la manière dont l'inclusion d'une troisième contrainte affecte l'analyse.
Voyons l'exemple suivant :
P) MAX 4X + 3Y
S.A. 6X + 2Y <= 120
...... .1X + 4Y <= 100
........5X + 5Y <= 150
..... ..X>= 0, Y>= 0
La résolution graphique de cet exemple permet d'obtenir la solution optimale X=15, Y=15 avec valeur
óptimoV(P)=105, tel que l'on peut observer dans le graphique ci-dessous :

Avant de procéder à l'analyse de sensibilité, il est conseillé de vérifier si les actuelles

les contraintes du problème sont actives à l'optimum, c'est-à-dire si elles sont satisfaites par l'égalité :
R1 : 6*(15) + 2*(15) = 120 => R1 est une contrainte active
R2 : 1*(15) + 4*(15) < 100 => R2 n'est pas une contrainte active
R3 : 5*(15) + 5*(15) = 150 => R3 est une contrainte active
Dans le cas où le côté droit de la contrainte est une ressource, il est logique d'avoir une
disposition à payer par unité supplémentaire dans la mesure où cette ressource est utilisée à
capacité maximale. En conséquence, une contrainte non active a par définition un prix
ombre égale à zéro (cas du R2) car une augmentation du côté droit n'augmentera pas la valeur
optimum actuel V(P)=150. Cependant, ce n'est que dans des cas très particuliers que nous pouvons trouver
restrictions actives avec un prix ombre (ou coût réduit) égal à zéro, ce qui est plus
exception qui confirme la règle.
Luego de esta introducción veamos el cálculo del precio sombra o costo reducido para la
restriction 1 (R1). Tout d'abord, nous devons déplacer parallèlement la restriction 1 jusqu'au point
maximum où la solution optimale continue d'être trouvée avec les contraintes actuelles.
R1 et R3. Ce point est (X,Y)=(30,0). Par la suite, nous déplaçons en forme parallèle la
restriction 1 (R1) jusqu'au point minimal où la solution optimale est toujours trouvée avec les
restrictions actives actuelles R1 et R3. Notez que ce déplacement est limité jusqu'à
point où la contrainte 2 (R2) devient active, ce qui correspond au point (X,Y)=(6,666
23,333) comme indiqué dans le graphique suivant :

Par conséquent, le prix ombre associé à la contrainte 1 est donné par :

En suivant une procédure similaire, il est possible d'obtenir les prix ombres associés à la
restrictions restantes. Ci-dessous se présente un tableau résumé de l'analyse de sensibilité
obtenu avec Solver d'Excel :
3e semaine
MÉTHODE SIMPLEXE ET SES VARIANTES
La méthode du simplexe est une méthode analytique de solution de problèmes deprogrammation
linéairecapable de résoudre des modèles plus complexes que ceux résolus par leméthode
graphiquesans restriction sur le nombre de variables.

La méthode du simplexe est une méthode itérative qui permet d'améliorer la solution à chaque étape.
La raison mathématique de cette amélioration réside dans le fait que la méthode consiste à marcher depuis le sommet de
un polyèdre a un sommet voisin de manière à augmenter ou diminuer (selon le contexte de la
fonction objectif, soit maximiser ou minimiser), étant donné que le nombre de sommets que présente un
la solution polédrique est toujours finie, il y aura toujours une solution.
Cette méthode populaire a été créée en 1947 par un AméricainGeorge Bernard
Dantziget le Russe Leonid Vitalievich Kantorovich, dans le but de créer un algorithme capable de
résoudre des problèmes de m contraintes et n variables.

Qu'est-ce qu'une matrice identité ?

Une matrice peut être définie comme un agencement rectangulaire d'éléments, (ou une liste finie de
éléments), qui peuvent être des nombres réels ou complexes, disposés sous forme de lignes et de
columnas.

La matrice identité ou identité est une matrice carrée (qui possède le même nombre de
colonnes comme de rangées) d'ordre n qui ont tous les éléments diagonaux égaux à un (1) et
tous les autres composants égaux à zéro (0), est appelé matrice identique ou identité de
ordre n, et il est noté par :

L'importance de la théorie des matrices dans la méthode du simplexe est fondamentale, étant donné que le
l'algorithme se base sur cette théorie pour la résolution de ses problèmes.

OBSERVATIONS IMPORTANTES LORS DE L'UTILISATION DE LA MÉTHODE SIMPLEX

VARIABLES DE HOLGURA Y EXCÈS
La méthode du Simplexe fonctionne en se basant sur des équations et les restrictions initiales qui sont modélisées.
par programmation linéaire ne le sont pas, pour cela il faut convertir ces inéquations en
équations utilisant des variables appelées de slack et d'excès liées à le
ressource à laquelle se réfère la contrainte et qui dans le tableau final représente le "Slack ou
surplus" auquel font référence les célèbres programmes de résolution de recherche de
opérations, ces variables acquièrent une grande valeur dans l'analyse de sensibilité et jouent un rôle
fondamental dans la création de la matrice identité de base du Simplex.

Ces variables sont généralement représentées par la lettre "S", elles s'additionnent si la contrainte est de signe.
<= " y se restan si la restricción es de signo ">=.
Par exemple :

VARIABLE ARTIFICIELLE / MÉTHODE DE LA "M"

Une variable artificielle est un truc mathématique pour convertir des inéquations ">=" en équations, ou
lorsqu'il y a des égalités dans le problème original, la caractéristique principale de ces variables
Ils ne doivent pas faire partie de la solution, car ils ne représentent pas des ressources. L'objectif
fondamental de ces variables est la formation de la matrice identité.

Ces variables sont représentées par la lettre "A", elles s'ajoutent toujours aux contraintes, leur coefficient
es M (por esto se le denomina Méthode de la M grande, donde M significa un número demasiado
grand très peu attrayant pour la fonction objective), et le signe dans la fonction objective va dans
contre le sens de celle-ci, c’est-à-dire, dans les problèmes de maximisation, son signe est moins (-) et
en problèmes de minimisation, son signe est (+), nous répétons avec l'objectif que sa valeur dans la
la solution soit zéro (0).
4ème semaine
DÉFINITION DE DUALITÉ
Du latin dualitas, le terme dualité désigne l'existence de deux phénomènes ou caractères.
différents en une même personne ou dans un même état de choses. Dans le domaine de la philosophie et la
La théologie, on appelle dualisme la doctrine qui postule l'existence de deux principes.
supérieurs indépendants, antagonistes et irréductibles.

Dualité
Dans ce sens, les notions du bien et du mal sont un exemple de dualité. Les deux peuvent
se définir par opposition et font référence à deux essences complètement distinctes. Matière-
esprit et réalisme-idéalisme sont d'autres exemples de concepts qui forment une dualité.

Dans ce cas, l'ensemble de doctrines dualistes existantes et qui, comme nous l'avons mentionné,
partent de cette différenciation entre le Bien et le Mal ont une série de traits en commun. Ainsi, par
exemple, nous nous trouvons face au fait que le Bien est toujours identifié avec la lumière et aussi
avec l'esprit. De son côté, le Mal s'associe en tout temps à l'obscurité, avec ce qui est le
partie corporelle et aussi avec le diable lui-même.

De cette manière, nous pouvons parfaitement voir cette dualité dont nous parlons dans l'un de
les personnages littéraires les plus importants de toute l'histoire. Nous faisons référence à
protagoniste de l'œuvre « L'étrange cas du docteur Jekyll et de M. Hyde », qui en 1886
créé par l'écrivain écossais Robert Louis Stevenson.

En concret, il s'agit d'un scientifique qui a été capable de créer une potion qui lui permet de
changer physiquement et personnellement. Ainsi, lorsqu'il se transforme en Hyde, il devient un homme violent
capable de mettre fin à la vie d'un autre être humain. Ainsi, nous assistons aux deux faces qui
n'importe qui peut avoir, le docteur représente le Bien et Hyde le visage le plus caché, sinistre
et violente du genre humain.

La philosophie chinoise fait appel à la notion de yin et yang pour résumer la dualité de tout ce qui
existe dans l'univers. Cette idée peut s'appliquer à n'importe quelle situation ou objet, car elle pourrait
s'expliquer sur la prémisse qui soutient que dans tout le bon il y a quelque chose de mauvais et vice versa.

Néanmoins, au cours de l'histoire, d'autres dualismes importants ont existé. Dans le cas de la
filosofie nous rencontrons, par exemple, le penseur prussien Immanuel Kant qui a établi
la dualité suivante : la raison pratique et la raison pure.

Le dualisme théologique repose sur l'existence d'un principe divin du bien (associé à la Lumière)
en contraposición à un principe divin du mal (les Ténèbres). Dieu est désigné comme
responsable de la création du bien, tandis que le mal est attribué au diable. Le dualisme, par ...
Ainsi, il libère l'homme de la responsabilité de l'existence du mal dans le monde.

L'Église catholique s'oppose à cette dualité car elle défend un Dieu omnipotent et infini, sans
que puisse exister un mal qui limite son potentiel. Tout ce qui existe a été créé par Dieu, rien de
Ce qui est créé par Dieu peut être mauvais.
 6.1 RELATION ENTRE LE PRIMAL ET LE DUAL
Les relations primal-dual sont :
[Link] un problème primal a une solution faisable, le dual aura une solution faisable et
viceversa.
[Link] le problème primal a une solution faisable et une fonction objective non bornée, alors
le dual n'aura pas de solution réalisable et vice versa.
[Link] le primal n'a pas de solutions faisables, le dual n'a pas de solution faisable ou la fonction
objetivo es no acotada.
Souvent, en recherche opérationnelle, pour formuler un problème dual, on se présente de
selon le tableau [Link]
Primal standard Problème dual
Problème objectif Objectif Tipo de restricción Signe de la
variable
Maximisation Minimisation ≥ Non restreinte
Minimisation Maximisation ≤ Non restreint
Tableau 3.2.1
La relation entre un problème primal et son dual est présentée à l'aide des tableaux optimaux pour les deux.
En pratique, il est observé qu'il n'est pas nécessaire de résoudre les deux, en résolvant un (mieux
convenant), on peut donner la solution à l'autre.
Supposez l'exemple 3.2.1

Primordial
0= 1+ 2 2
.
2 1+ 8 2 ≤ 16
1 + 2≤5
1, 2≥ 0
Double
0 = 16 1+ 5 2

1 Hamdy Taha, Recherche Opérationnelle, 6ème Éd. Éditions Prentice Hall

 .
2 1+ 2≥1
8 1+ 2≥ 2
1, 2 ≥ 0

Tableau optimal 3.2.2 (résolu par la méthode du simplexe)

2 1 2
1
0 0 0 1/6 2/3 6
2 0 1 1/6 -1/3 1
1 0 -1/6 4/3 4
1

Tableau optimal dual 3.2.3 (par double phase)

Solution optimale
=6
1= 4

2= 1
1= 0
2= 0

1 2 1 2 1 2

0 0 0 -4 -1 — — 6

2 0 1 -4/3 1/3 4/3 -1/3 2/3

1 1 0 1/6 -1/6 -1/6 1/6 1/6

Solution optimale :
=6
1=1/6 2= 2/3 1= 0 2= 0 1= 0 2 =0
Remarquez que dans les deux tableaux 3.2.2 et 3.2.3, nous avons la même solution optimale.
UnAnalyse. Pour le primal=le6dual
, 6
propriété qui=uandouna c
maximisez l'autre, minimisez, parfois ne donne pas la même valeur, cela se produit lorsque le
la propriété de dualité est faible. Dans ce cas 0 0<, pour le problème qui est analysé
la dualité est forte 0 0considérant
= que les deux problèmes sont optimaux.
UnAnalyse. Observons sdans le primals f
ce tes r en anglais
que coi d'icien , les 0
coefficients de 1 2y(variables de début) correspondent à la solution d'un
problème dual comme sont 1= 1/6 y 2= 2/3, ces résultats sont comparés dans la
tableau 3.2.3 et nous remarquons qu'ils correspondent aux variables duales 1= 1/6 y 2 =
2/3

En résumé, les valeurs optimales pour un problème dual seront données par les variables
de augmentation (de départ) dans ce cas les variables de marge 1y 2.
Il en va de même si nous observons la ligne 0dans le tableau 3.2.3 (dual), la solution
optimale pour le primal sont les coefficients qui sont en dessous 1y 2qui correspondent en
ordre à 1= 4 y 2 = 1; notez que le négatif est omis, cela parce que le dual se
change to mminimiser et connaître s la propiedad de 0− (− ). 0

De la même manière, à partir du tableau optimal 3.2.2, on obtient les variables d'augmentation pour le
dual, elles se trouvent dans la ligne 0sous les variables réelles 1y 2; pour le
donc, les variables de marge 1= 0 2= 0.
De même, les variables d'augmentation pour le primal se trouvent dans la ligne 0sous les
variables duales 1y 2, pour notre exemple 1= 0 2= 0.
5ème semaine :
MODELOS DE TRANSPORTE
Le problème du transport ou de la distribution est unproblème de réseaux spécial
enprogrammation linéaireque se fonde
dans le besoin d'apporter des unités de
un point spécifique
appel source vers un autre
point spécifique appelé destination.
Les principaux objectifs d'un
le modèle de transport est la
satisfaction de tous les
exigences établies par les
destinations, et bien sûr, la minimisation
des coûts liés au plan
déterminé par les itinéraires choisis.
Le contexte dans lequel s'applique le
le modèle de transport est vaste et
peut générer des solutions pertinentes au
zone d'opérations, inventaire et
attribution des éléments.
Le processus de résolution d'un
Le modèle de transport peut être emporté
un câble parprogrammation linéaire communeCependant, sa structure permet la création
de multiples alternatives de solution telles que lastructure d'attributionou les méthodes
heuristiques les plus populaires commeOiseauCoin Nord-OuestoCoûts minimaux.

Les problèmes de transport ou de distribution sont l'un des plus appliqués en économie
actuel, laissant comme prévu de multiples cas de succès à l'échelle mondiale qui stimulent la
appréhension des mêmes.

PROBLÈME DE TRANSPORT PAR PROGRAMMATION LINÉAIRE

Comme mentionné précédemment, laprogrammation linéaire peut être utilisée pour la
résolution de modèles de transport, bien qu'il ne soit pas raisonnable de résoudre les modèles par
el Méthode du Simplexsi cela peut être d'une grande utilité, la phase de modélisation, la programmation
manque de praticité des méthodes d'attribution, mais peut être d'une grande importance
en fonction de la complexité des restrictions supplémentaires qui peuvent être présentes
problème particulier.
 MÉTHODE D'APPROCHE DE VOGEL (MAV)

Elmétodo de aproximación de Vogeles un método heurístico de resolución deproblèmes

de transport capable d'atteindre une solution de base non artificielle au départ, ce modèle
nécessite généralement un plus grand nombre d'itérations que les autres
méthodes heuristiques existantes à cet effet, cependant cela produit de meilleurs résultats
initiales que les mêmes.

ALGORITHME DE VOGEL

La méthode consiste en la réalisation d'un algorithme qui comprend 3 étapes fondamentales et

1 de plus qui garantit le cycle jusqu'à l'achèvement de la méthode.
PASO 1
Déterminer pour chaque ligne et colonne une mesure de pénalité en soustrayant les deux coûts
mineurs en rangées et colonnes.

ÉTAPE 2
Choisir la ligne ou la colonne avec la plus grande pénalité, c'est-à-dire celle résultant de la soustraction effectuée dans le
Étape 1, il faut choisir le plus grand nombre. En cas d'égalité, il faut choisir
arbitrairement (à l'appréciation personnelle).

ÉTAPE 3
De la fila o colonne de plus grande pénalité déterminée à l'étape précédente, nous devons
choisir la cellule avec le coût le plus bas, et y attribuer la quantité maximale possible de
unités. Une fois cette étape franchie, une offre ou une demande sera satisfaite, donc elle
tachera la rangée ou la colonne, en cas d'égalité, seule 1 sera rayée, l'autre restera avec
offre ou demande égale à zéro (0).

PASO 4: DE CICLO Y EXCEPCIONES

- Si une ligne ou une colonne sans aucune offre ou demande est laissée non barrée, s'arrêter.

- S'il reste une ligne ou une colonne non barrée avec une offre ou une demande positive, déterminez les
variables de base dans la ligne ou la colonne avec la méthode des coûts minimaux, s'arrêter.

Si toutes les lignes et colonnes qui ne sont pas barrées ont une offre et une demande nulles, déterminez
les variables de base zéro par la méthode du coût minimum, arrêter.

- Si aucun des cas précédents ne se présente, revenez à l'étape 1 jusqu'à ce que les offres et
les demandes ont été épuisées.

EXEMPLE DE LA MÉTHODE D'APPROCHE DE VOGEL

Par ce procédé, nous résoudrons l'exercice de transport résolu en modules.
antérieurs parprogrammation linéaire.

LE PROBLÈME
Une entreprise énergétique colombienne dispose de quatre centrales de génération pour satisfaire
la demande quotidienne d'électricité dans quatre villes, Cali, Bogotá, Medellín et Barranquilla. Les
plantas 1,2,3 y 4 pueden satisfacer 80, 30, 60 y 45 millones de KW al día respectivamente.
Les besoins des villes de Cali, Bogotá, Medellín et Barranquilla sont de 70, 40, 70
y 35 millions de Kw par jour respectivement.

Les coûts associés à l'envoi de fourniture énergétique par million de KW entre chaque
plante et chaque ville sont enregistrés dans le tableau suivant.

Formule un modèle de programmation linéaire qui permette de satisfaire les besoins de tous
les villes tout en minimisant les coûts associés au transport.

SOLUCIÓN ÉTAPE PAR ÉTAPE

La première étape consiste à déterminer les mesures de pénalité et à les consigner dans le tableau de
coûts, comme indiqué ci-dessous.

L'étape suivante consiste à choisir la plus grande pénalité, de cette manière :

L'étape suivante consiste à choisir de cette colonne la plus petite valeur, et dans un tableau parallèle, on lui
assignez le plus grand nombre possible d'unités, nous pouvons observer comment le coût le plus bas est
"2" et à cette cellule, on peut attribuer au maximum 60 unités "qui est la capacité
de la plante 3".
Étant donné que la ligne de la "Plante 3" a déjà attribué toute sa capacité (60 unités), celle-ci doit
disparaître.

On en est arrivé à la fin du cycle, donc le processus se répète.

Nous entamons une nouvelle itération

Nous continuons avec les itérations,
 2. MÉTHODE DU BANQUET
La solution obtenue par les méthodes précédentes est la solution initiale de la méthode de
banquillo. La façon de vérifier si la solution actuelle peut être améliorée est d'examiner les
variables non basiques actuelles à la recherche d'améliorations potentielles dans la valeur de la fonction
objectif. S'il existe une telle variable, ce sera la variable qui entre dans ce cas une des
les variables b{asicas actuelles doivent laisser la solution (comme dans la méthode simplex).
Afin de déterminer la variable qui entre et celle qui sort, un circuit fermé est identifié pour
chaque variable non de base. Le circuit commence et se termine par la variable non de base désignée.
Un circuit consiste en des segments horizontaux et verticaux successifs (connectés) dont
Les points extrêmes doivent être des variables de base, sauf pour les 2 segments de départ et
terminaison dans la variable non basique.
Le circuit est utilisé pour vérifier si la valeur de la fonction objective peut être améliorée.
lorsque la variable non basique est augmentée au-dessus de sa valeur actuelle de zéro.
La procédure consiste à trouver l'augmentation ou la diminution du coût de transport
comme résultat d'augmenter les unités dans la variable non basique étudiée.

Cette valeur est obtenue en assignant des signes positifs et négatifs alternés aux coûts.
associés aux variables qui forment le circuit, en commençant par le coût de la variable non
de base. La somme des coûts du circuit peut être effectuée dans le sens des aiguilles d'une montre.
horloge ou dans le sens inverse.

Le résultat obtenu dans la somme des coûts du circuit peut être positif ou négatif. Si
il est positif indique que l'assignation d'unités à la variable considérée augmente le
coût total de transport. Mais si cette valeur est négative, la solution peut être améliorée
assigné à la variable non de base la plus petite valeur des variables qui doivent réduire leur
valeur dans le circuit qui est considéré.

La procédure se termine lorsque toutes les variables non de base ont une valeur positive dans la
somme des coûts du circuit.

Exemple :
Encuentre la solución óptima del problema de la compañía de renta de autos utilizando una
solution initiale par la méthode du coût minimum et en utilisant la méthode de l'utilisation de
banc de touche
Comment attribuer ?
Soustraire 3 unités aux négatifs et ajouter 3 unités aux positifs.

De nouveaux critères ou chemins sont établis

8e semaine
MÉTHODE DES MULTIPLICATEURS
Cette méthode reproduit exactement les mêmes itérations que la méthode de banc.
la principale différence se situe dans la façon dont les variables non basiques sont évaluées à chaque
iteración. Asociados a cada renglón i de la tabla existen multiplicadores Ujesimilairement se
associe un multiplicateur Vja cada columna de la tabla j. Para cada variable básica Xijde la
solution actuelle, on écrit l'équation Uje+Vj= Cij. Ces équations fournissent m+n-1
relations avec m+n inconnues.
Les valeurs des multiplicateurs peuvent être déterminées à partir des équations
en supposant une valeur arbitraire pour l'un des multiplicateurs (généralement on)
établit U1=0) et en résolvant le système d'équations pour trouver les multiplicateurs
inconnus. Une fois cela fait, l'évaluation de chaque variable non de base Xpqest
dada comme :

Le critère utilisé pour sélectionner la variable qui entre est le même que la méthode de
banquillo (la plus grande négative).

Exemple :
Une entreprise envisage une demande de 5 clients utilisant des articles qui ont
disponibles dans 2 entrepôts. Les entrepôts comptent 800 et 1000 unités
respectivement. Les clients ont besoin de 200, 150, 200, 180 et 500 unités respectivement.
Les coûts d'expédition par article des entrepôts des clients sont :

Résolvez le modèle de transport en utilisant.

a) Une solution initiale par la méthode d'approximation de Vogel.
b) La solution optimale par la méthode des multiplicateurs.
DESTINO FICTICIO = 570 ARTÍCULOS

Pour trouver la valeur des multiplicateurs

On s'habitue :

Pour trouver des coûts :

9ème semaine
MODELO DE ASIGNACIÓN
Le modèle d'affectation est un type spécial de problème de programmation linéaire dans lequel
les assignés sont des ressources qui sont destinées à la réalisation de tâches. Par exemple, les
Les assignés peuvent être des employés à qui il faut donner du travail. L'affectation de
l'attribution de personnes à des travaux est une application courante du problème d'affectation. Cependant, les
Les éléments assignés ne doivent pas nécessairement être des personnes. Ils peuvent également être des machines, des véhicules ou des plantes, ou
y compris les périodes auxquelles des tâches sont assignées.
"La meilleure personne pour le poste" est une bonne description du modèle de
assignation.
L'objectif du modèle est de déterminer l'allocation optimale (à coût minimum) de
travailleurs à des postes.
Le modèle général d'affectation avec n travailleurs et n postes est représenté dans le tableau
suivant :

Pour s'ajuster à la
définition d'un problème de
assignation, il est nécessaire que cela soit
type d'applications se formule de
manière à ce que les
hypothèses suivantes :
1. Le nombre d'assignés est
égal au nombre de tâches. (Ce
numéro se denote par n.)
2. À chaque assigné, une seule tâche est attribuée.
3. Chaque tâche doit être effectuée par un seul assigné.
4. Il existe un coût cij associé à l'attribut i (i = 1, 2, . . . , n) qui effectue la tâche j (j =
2, . . . , n).
5. L'objectif est de déterminer comment les n attributions doivent être effectuées pour minimiser les
coûts totaux.
Le modèle d'affectation peut être résolu directement comme un modèle normal de
transport. Cependant, le fait que toutes les offres et les demandes soient égales à 1,
a conduit au développement d'un algorithme simple de solution appelé méthode hongroise.

MÉTHODE HONGROISE
La méthode hongroise est une méthode d'optimisation des problèmes d'affectation, connue
Comme tel, merci au fait que les premières contributions à la méthode classique définitive ont été de Dénes.
König et Jenő Egerváry, deux mathématiciens hongrois. L'algorithme tel qu'il sera détaillé à
La suite est conçue uniquement pour la résolution de problèmes de minimisation.
Il est important de souligner que la méthode hongroise fonctionne sur une matrice de coûts n*m (dans ce
cas connu sous le nom de matrice m*m, étant donné que le nombre de lignes est égal au nombre de
colonnes n = m).
Pour résoudre des problèmes d'affectation en appliquant la méthode hongroise, il est nécessaire de suivre les
étapes ou algorithmes suivants :
Étape 1
Dans la matrice de coût originale, identifier le minimum de chaque ligne et le soustraire de tous les
éléments de la ligne.
Étape 2
Dans la matrice résultant de l'étape 1, identifier le minimum de chaque colonne et le soustraire de
tous les éléments de la colonne.

Étape 2.1
S'il n'est pas possible d'assurer une affectation faisable (avec tous les éléments zéro) avec les
étapes 1 et 2
a). Tracer la quantité minimale de lignes horizontales et verticales dans la dernière matrice
réduite que couvrent tous les éléments zéro.
b). Sélectionner l'élément minimum non couvert, le soustraire de chaque élément non couvert et
ensuite l'ajouter à tout élément dans l'intersection de deux lignes.
c). S'il n'est pas possible de trouver une affectation réalisable entre les éléments zéro que
resultat, répéter l'étape 2.1. Dans le cas contraire, passer à l'étape 3 pour déterminer la
attribution optimale.

Étape 3
Identifier la solution optimale comme l'affectation réalisable associée aux éléments zéro
de la matrice obtenue à l'étape 2.

EXEMPLE #1
Une équipe de 3 mécaniciens doit être affectée à l'exécution de 3 tâches, où chaque
le mécanicien doit effectuer une tâche. Il est nécessaire de trouver l'affectation du coût minimum pour cela.
quels sont les coûts associés à ce que le mécanicien i réalise la tâche j.

SOLUCIÓN
ÉTAPE 1 : Dans la matrice de coût d'origine, identifier le minimum de chaque ligne et le soustraire de
tous les éléments de la ligne.

PASO 2: En la matriz que resulte del paso 1, identificar el mínimo de cada columna, y
soustraire tous les éléments de la colonne.
ÉTAPE 3 : Identifier la solution optimale comme l'affectation feasible associée aux
éléments nuls de la matrice obtenue à l'étape 2.

Les cellules avec une valeur de zéro et de couleur marron sont la solution optimale. En conséquence le
mecánico 1 realiza la tarea 2, el mecánico 2 asuma la tarea 1 y el mecánico 3 la tarea 3.
Chaque mécanicien effectue exactement une tâche et le coût total de cette affectation (valeur
óptimo) est deQ9+Q10+Q8=Q27.
10ma. Semana
1. DÉFINITIONS DES PROJETS
PROBABILISTIQUES ET DÉTERMINISTES
Projets probabilistiques
Le modèle probabilistico-statistique est la forme que peuvent prendre un ensemble de données.
obtenus deéchantillonnagesde données avec un comportement qui est supposéaléatoire.
Un modèle statistique est un type demodèle mathématiqueque usa laprobabilitéet quoi
inclut un ensemble d'assumptions sur la génération d'algdes données échantillonnairesde tel
façon qu'ils ressemblent aux données d'une population plus grande.
Les hypothèses ou suppositions d'un modèle statistique décrivent un ensemble de
distributions de probabilité, qui sont capables d'approcher de manière adéquate un
ensemble de données. Les distributions de probabilité inhérentes des modèles
les statistiques sont ce qui distingue les modèles des autres modèles mathématiques
déterministes.
Un modèle statistique est spécifié par un ensemble d'équations qui relient
diverses variables aléatoires, et dans lesquelles d'autres variables non aléatoires peuvent apparaître.
En tant que tel, "un modèle est une représentation formelle d'une théorie""1
Tous les tests d'hypothèses statistiques et tous lesestimators statistiquesprocèdent de
modèles statistiques. En fait, les modèles statistiques sont une partie fondamentalement
del'inférence statistique.

Modèles basés sur des distributions

Ils peuvent être des modèles probabilistiques discrets ou continus. Les premiers, pour la plupart se
basées sur des répétitions de tests de Bernoulli. Les plus utilisés sont :
Modèle de Bernoulli
Modèle Binomial.
Modèle géométrique.
Modèle Binomial négatif.
Modèle hypergéométrique.
Modèle de Poisson.
D'autre part, comme cela a été mentionné précédemment, il existe des modèles probabilistes continus,
parmi eux, nous soulignons :
Distribución Normal: usada largement dans des échantillons supérieurs à 30 données.
Distribution Chi Carré : utiliséeen petites quantités.
Distribution exponentielle : utiliséeen durée ou là où intervient le passage du temps.
Distribution Fla distribution F de Snedecor : utilisée pour contrôler lavariancede 2
distributions.
Modèle de récupération de l'indépendance binaire
Le modèle probabiliste en tant que modèle de récupération d'indépendance binaire a été
développé par Robertson et Spark Jones. Ce modèle affirme qu'ils peuvent être caractérisés
les documents d'une collection par l'utilisation de termes d'indexation. Évidemment
il existe un sous-ensemble idéal de documents qui contient uniquement les documents
pertinents à un besoin d'information pour lequel une pondération est effectuée sur les
termes qui composent la requête effectuée par l'utilisateur. Ensuite, le système
calculez la similarité entre chaque document de la collection et la requête et présentez les
résultats classés par degré de probabilité de pertinence par rapport à la requête.
Ce modèle évite la comparaison exacte (existence ou non d'un terme de la requête dans
le document) et permet à l'utilisateur de réaliser un processus de rétroaction en évaluant le
pertinence des documents récupérés afin que le système puisse calculer le
probabilité lors de futures consultations que les documents récupérés soient ou non
pertinents en fonction des termes utilisés dans la requête qu'ils soient ou non pertinents.
Modèles de régression
Un modèle statistique de régression est une expression symbolique sous forme d'égalité ou
équation utilisée dans tous les conceptions expérimentales et dans la régression pour indiquer
les différents facteurs qui modifient la variable de réponse. Le modèle statistique le plus
simple est utilisé dans les conceptions complètesles essais randomisés(DCA). Son modèle est :

Où
Y = est la variable de réponse d'intérêt.
μ= moyenne générale de la population sur laquelle on travaille
t = la variation qui est attribuée aux niveaux du facteur qui est en cours d'évaluation
(effet des traitements).
ξ= est la variation des facteurs non contrôlés (l'erreur expérimentale)
i=i-ème traitement
j = j-ème répétition de chaque traitement
j(i) = est la variation des unités expérimentales imbriquées dans les traitements.
Les modèles statistiques peuvent être linéaires ou non linéaires.

DÉTERMINISTIQUES
Un modèle déterministe est un modèle mathématique où les mêmes entrées ou
les conditions initiales produiront invariablement les mêmes sorties ou résultats, non
contemplant l'existence du hasard, ou de l'incertitude dans le processus modélisé par
dudit modèle.
Está estrechamente relacionado con la creación de entornos simulados a través de
simulateurs pour l'étude de situations hypothétiques, ou pour créer des systèmes de gestion qui
permettant de réduire la propagation des erreurs. Les modèles déterministes ne peuvent être que
adecués pour des systèmes déterministes non chaotiques, pour des systèmes aléatoires (non-
determinista) y caóticos (determinista inpredictible a largo plazo) los modelos deterministas
ils ne peuvent pas prédire correctement la plupart de leurs caractéristiques.
L'inclusion d'une plus grande complexité dans les relations avec un plus grand nombre de variables et
Des éléments étrangers au modèle déterministe permettront à celui-ci de s'approcher d'un modèle
probabilistique ou de méthode stochastique.
Par exemple, la planification d'une ligne de production, dans tout processus industriel, est
posible realizarla con la implementación de un sistema de gestión de procesos que incluya
un modèle déterministe dans lequel les matières premières, le travail, sont quantifiés
les délais de production et les produits finis associés à chaque processus.
Un ensemble d'équations différentielles d'un système physique macroscopique constitue un
modèle déterministe qui peut prédire l'évolution déterministe dans le temps d'un bien
nombre de magnitudes caractéristiques du système.

2. DIAGRAMME DE FLÈCHES (RÉSEAU) CPM, PERT

Le Diagramme de Flèches indique l'ordre dans lequel les activités doivent être exécutées.
projet, permettant de planifier et de contrôler son développement,
en identifiant les activités qui le composent et en déterminant son
chemin critique, par une représentation en réseau.
Le diagramme de flèches :

Muestra en un sólo documento el recorrido de un proyecto.

Rendez possibles les activités correspondant à un projet
déterminé, sa séquence et sa durée, soient connues.
Facilite le contrôle du projet, permettant de répondre face aux
difficultés qui peuvent surgir au cours de son développement.
Les plans irréalistes se mettent en évidence, offrant la possibilité de les ajuster.
Le diagramme en flèches est également connu sous d'autres noms, tels que : activité
diagramme de réseau, diagramme de réseau, réseau d'activités, diagramme de nœud, ou méthode de la
ruta crítica (CPM–méthode critique chemin).
Elle est fondée sur l'application de la méthodologie du chemin critique. Cela suppose une
simplification de l'outil de planification PERT (Évaluation et Révision du Programme)
Technique). Cette méthode a été développée par la Marine des États-Unis, pour soutenir le
projet du sous-marin nucléaire Polaris. Son objectif était de faciliter la planification et
programmation de projets de grande complexité et d'ampleur. Le diagramme de flèches
constitue une simplification de la méthode PERT.
Dans un projet, le travail est décomposé en un ensemble d'activités interdépendantes.
dont l'ordre doit être respecté. Mais dans la séquence des activités, certaines d'entre elles peuvent
être exécutées simultanément. Le diagramme de flèches permet que des séries de
les activités parallèles se manifestent, permettant l'ajustement de la programmation du
projet et facilitant sa réalisation dans les plus brefs délais.
De cette manière, le diagramme de flèches fournit la "chemin critique" du projet, qui est le
flux des activités décisives, où les retards affecteront le calendrier de la totalité
du projet. Elle met également en évidence quelles activités peuvent accélérer le projet.

Élaboration du Diagramme de Flèches

1. Identifier les activités. Tout d'abord, pour la confection du diagramme de

flèches, on procède à l'identification des activités qui composeront le projet à
planifier. Les activités sont enregistrées sur des cartes. Celles-ci peuvent être collées sur un panneau, ou
situées sur une surface de travail
2.Déterminer la première activité du projet. Par la suite, et listées les
activités, il est établi laquelle est la première dans l'exécution du projet.
3.Démarrer le classement des activités. À partir de la première activité, on demande
s'il y a des activités simultanées ainsi que quelle activité succède à l'initiale.
[Link] le classement des activités. Ensuite, le processus décrit se
se déroule jusqu'à ce que le reste des activités soit situé en séquence ou en parallèle.
5. Connecter les activités et assigner des temps. Une fois les cartes triées, on
numérotent et un temps réaliste est attribué à chaque activité pour son accomplissement.
6. Spécifier la trajectoire fondamentale. Enfin, on identifie le parcours principal.
La méthode la plus simple pour calculer le temps total nécessaire pour compléter le
projet, c'est celui de la trajectoire cumulative la plus longue. Pour cela, on additionne chaque
trajectoire des activités connectées de manière à ce que la trajectoire cumulative plus
Long représente le temps de développement du projet le plus rapide possible. À cette
La trajectoire est appelée trajectoire fondamentale du projet.

Diagramme de Flèches – Final. Appuyer pour augmenter

DIAGRAMA CPM
est fréquemment utilisé dans le développement et le contrôle de projets. L'objectif principal est
déterminer la durée d'un projet, le comprenant comme une séquence d'activités
liées entre elles, où chacune des activités a une durée estimée.
Dans ce sens, le principal postulat de CPM est que les activités et leurs temps de
la durée est connue, c'est-à-dire qu'il n'y a pas d'incertitude. Cette hypothèse simplificatrice fait
que cette méthodologie soit facile à utiliser et dans la mesure où l'on souhaite voir l'impact de la
incertitude sur la durée d'un projet, une méthode complémentaire peut être utilisée
comme c'est le casPERT.
Un parcours est une trajectoire du début à la fin d'un projet. Dans ce sens, la
La longueur de la trajectoire critique est égale au chemin le plus long du projet. Il convient de noter que
que la durée d'un projet est égale au chemin critique.
Étapes de CPM
Pour utiliser la méthode CPM ou de chemin critique, il faut suivre les étapes suivantes :
1. Définir le projet avec toutes ses activités ou parties principales.
2. Établir des relations entre les activités. Décider laquelle doit commencer en premier et laquelle doit.
suivre après
3. Dessiner un diagramme reliant les différentes activités en fonction de leurs relations de
précedence.
4. Définir coûts y temps estimé pour chaque activité.
5. Identifier le chemin le plus long du projet, celui qui déterminera la
durée du projet (Chemin Critique).
6. Utilisez le diagramme comme aide pour planifier, superviser et contrôler le projet.
Pour des raisons de simplicité et pour faciliter la représentation de chaque activité, il est fréquent de
utilise la notation suivante :

Où :

IC : Début le plus proche, c'est-à-dire le plus tôt que l'activité peut commencer.

TC : Terme le plus proche, c'est-à-dire le plus tôt où l'activité peut se terminer.

IL : Début le plus lointain, c'est-à-dire le plus tard que l'on peut commencer l'activité sans retarder le
terme du projet.

TL : Terme le plus éloigné, c'est-à-dire le plus tard que l'activité peut se terminer sans retard.
la fin du projet.
De plus, le terme Holgura est défini pour chaque activité qui consiste en le temps
maximum que l'on peut retarder le début d'une activité sans que cela ne retarde la
achèvement du projet. Le flottement d'une activité peut être obtenu avec ce qui suit
formule :
Holgura = IL - IC = TL - TC
EXEMPLE : Ci-dessous se présente un résumé des activités requises par un
projet à compléter. La durée de chaque activité en semaines est fixe. Il
demandez d'estimer la durée totale du projet par la méthode CPM.
Actividad Duración (sem) Actividad Predecesora
A 6 -
B 8 -
C 12 A,B
D 4 C
 E 6 C
F 15 D,E
G 12 E
H 8 F,G
En considération des étapes de la méthode CPM définies précédemment, dans ce cas, on
il doit développer l'étape 3 et 5. Dans ce sens, il est nécessaire de construire le diagramme
identifiant les relations entre les activités et afin de résumer la
la méthodologie intégrera immédiatement le calcul de la marge, IC, TC, IL, TL pour
chaque activité, avec l'identification du chemin critique.

Tout d'abord, le diagramme est construit en identifiant chaque

actividad en un nodo (círculo) con su nombre respectivo y
entre parenthèses le temps estimé. Les flèches entre
Les activités signalent les relations de prédécence, par
exemple, l'activité F ne peut commencer qu'une fois
terminées les activités D et E.
Ensuite, pour chaque activité, les indicateurs IC sont identifiés.
y TC. Por ejemplo, para la actividad C el inicio más
cercano est 8 (cela parce que C ne peut commencer qu'une fois
terminée A et B, B étant celle qui prend le plus de temps et termine
en 8) y le terme le plus proche est 20 (étant donné que l'activité
C prend 12 semaines).
Par la suite, on obtient l'IL et le TL pour chaque activité.
Con esta información el cálculo de la holgura de cada actividad es simple. Para obtener el
Il y a TL de chaque activité nous "nous déplaçons" du fin jusqu'au début. Dans ce cas, la
l'activité qui se termine le plus tard est H (49 sem) et donc nous nous demandons quand elle est lo
plus tard que je pourrais terminer H sans retarder le projet (TL), cela est clairement 49.
tant que le plus tard que H peut se terminer est 49, le plus tard que H peut commencer pour
Respecter ce temps est 41 (étant donné que H dure 8 sem). Ensuite, la marge de H est nulle. Noter
Les activités avec une marge égale à zéro correspondent aux activités du chemin.
critique. De plus, un projet peut avoir plus d'une voie critique.

DIAGRAMME PERT
Un diagramme de PERT permet d'établir des relations à partir des dépendances de l
activités d'un projet. Si le livrable d'une activité est nécessaire pour commencer le
suivant, nous situerons ensuite la deuxième tâche. Aucune activité ne peut être réalisée
avant, cela dépend de la fin d'une autre qui est planifiée plus tard. De cette manière, plus
simple, nous expliquons ce qu'est le diagramme de PERT et comment utiliser PERT dans leprocessus de
planificationde ton travail.

Dans le monde de la gestion et de la direction de projets, la technique PERT est très populaire et
s'applique pour connaître les itinéraires de travail optimaux. Par exemple, si pour réaliser la tâche C
Il est nécessaire d'avoir le livrable de l'activité A, PERT nous avisera que nous devons terminer A
avant que nous mettions en marche C. Pure logique qui a priori ne doit pas avoir plus
complication. Cependant, la situation se complique lorsque l'exécution d'une seule activité
affecte de nombreuses activités.
Les initiales du diagramme de PERT signifient Technique de Révision et d'Évaluation de
Programmes, et il peut s'appliquer à l'ensemble du projet ou uniquement à des phases déterminées de la
planification critiques.

PERT est souvent utilisé avec des techniques CPM (Critical Path Method) pour détecter ces
‘goulots d'étranglement’ qui peuvent mettre en danger l'ensemble du projet. Avec PERT et
CPM nous permettra de connaître le chemin critique de nos projets et de réaliser un meilleur contrôle de
qualité des résultats de celui-ci.
Ainsi, ce concept est directement lié à la date de fin du projet. Pour que
cela se réalise dans les délais, la première chose à développer est le chemin critique. C'est pourquoi,
il est impératif d'identifier le chemin critique lors de la phase de planification, à
à travers une autre technique très similaire à la méthode PERT, nous parlons du CPM (Chemin Critique)
Méthode).
Grâce aux dépendances entre les activités extraites, nous obtiendrons le flux de travail le plus
optimal. C'est seulement ainsi que nous pourrons éviter un retard qui
paralyse notre projet. Les activités qui ne
se rapportent à lachemin critiqueils ont un
maire holgura pour ce qu'ils peuvent être
susceptibles de modifications ultérieures sans
que affecte la date de fin du projet.
Ainsi, tandis que PERT considère les
ressources nécessaires pour compléter les
activités sur une durée déterminée, la
la logique du CPM détecte le chemin critique et les éventuels 'goulets d'étranglement' du projet.

Rouge PERT
Les techniques PERT et CPM nous aident à planifier un projet avec le coût
minimum et la durée la plus adaptée, comme le fait Sinnaps. Avec les deux techniques,
Le chef de projet pourra trouver unecompensation de l'effort dans votre projet.
Compte tenu des activités qui ne sont pas dans le chemin critique, l'équipe
il travaillera sur ces tâches lorsque les ressources seront disponibles, les mettant au service de la
activités critiques dans les phases les plus compliquées du processus.

L'ORIGINE DE PERT

Il s'agit d'une technique appliquée à d'importants projets de notre histoire contemporaine.

La Marine des États-Unis a commencé à l'utiliser en 1958 pour la planification
déprojet Polaris, un missile balistique lancé par sous-marin, construit avec des armes
nucléaires pendant la guerre froide. On dit que grâce à la logique de PERT, cela a été avancé de deux
ans la date d'achèvement de sa construction. Tout un avantage si nous traitons un contexte
bélisme. Le programme Apollo, par exemple, a également été programmé en suivant la méthode
PERT.
Actuellement, PERT est utilisé tant pour des projets gouvernementaux que pour des projets liés à la
industrie. En effet, certains gouvernements, comme le gouvernement américain ou des institutions publiques
comme la NASA, exigent aux entreprises privées un travail basé sur la logique de PERT.

À QUOI SERT LE DIAGRAMME DE PERT ?

Le Diagramme de PERT est utilisé par les entreprises depuis le milieu du siècle dernier. Ses
les fonctionnalités sont multiples, car parmi les plus remarquables, la technique PERT nous
aide à savoir quelle sera la fin du projet. C'est-à-dire, la date minimale à laquelle
nous terminerons notre travail. Cela nous permet d'établir une communication plus
effective with the project owner or client.

On pourrait dire que la méthode PERT remplit des aspects primordiaux.

Cela fonctionne à travers un réseau de relations d'origine des éléments qui

composent les activités, concernant l'ordre dans lequel elles doivent être exécutées.
Sa caractéristique fondamentale est la durée des activités
Cherche à respecter des dates de livraison spécifiques
—Évaluez l'impact des changements au cours de l'exécution du projet. Lessimulations
ils peuvent mieux gérer l'incertitude. S'il y a des écarts par rapport à ce qui était prévu, on
il vérifiera comment ce changement affecte le projet dans son ensemble. Nous pouvons l'obtenir
automatiquement avec des applications avancées de gestion.
De plus, tout cela peut être représenté dans undiagramme de Gantt, tel que le fait
l'application Sinnaps.
PERT sert également à beaucoup d'autres choses. Nous avons rassemblé une série d'avantages et
inconvénients du diagramme de PERT.

Ventajas

Organiser des activités.

Calculer des itinéraires de travail optimisés.
Prend en compte les dépendances entre les tâches.
Planifications plus efficaces et réalistes.
Il prend en compte chaque activité de manière individuelle et sa relation avec les autres.
tâches.
Permet d'identifier les goulets d'étranglement ou les nœuds critiques dans le parcours de travail.
Aide à respecter les délais et les budgets estimés.
Améliore la prise de décision anticipée et efficace.
Meilleure intégration et présentation des données aux parties prenantes du projet.

Inconvénients

Ne favorise pas la planification flexible. Il est compliqué de replanifier si tu appliques des techniques.
de PERT dans la gestion de projets. Heureusement, il existe des applications comme
Sinnaps qui dépassent cette limite pour adapter les méthodes PERT et CPM au monde si
versatile dans lequel nous vivons aujourd'hui.
 Nous ne disposons pas de données suffisantes lors de la création du diagramme PERT en ligne. Quand
nous réalisons la première planification ou estimation du projet, nous n'en avons pas encore une
informations exhaustives et complètes à son sujet. Comment connaître l'estimation exacte de
coûts ou délais ? D'où la nécessité de re-planifier et cela nous amène à la
première barrière de PERT : son statisme.
Cela suppose un énorme effort de créer par nous-mêmes un réseau PERT de
projet moyen. Les itinéraires de travail contiennent souvent plusieurs activités, avec plusieurs
dépendances entre elles. Nous devons prendre en compte différents et multiples liens
Le seul paramètre est le facteur temps. Si une donnée sur les durées échoue de
activités, changements de dates, délais ou toute autre variation dans lagestion des ressourcestoute
le réseau PERT s'effondrerait. D'où l'importance d'utiliser des applications qui ont en
énumérer ces inconvénients du diagramme de PERT, et qui permettent des planifications
flexibles, comme c'est le cas de Sinnaps.
Ce n'est pas une méthode agile. Pour tout ce que nous avons mentionné précédemment, la technique
Le PERT est prédictif mais n'est pas agile. Il ne permet pas une réévaluation constante de la
planification, s'éloignant ainsi d'une gestion réaliste. Oui, il prédit ce qui se passera dans
projets avec un niveau d'incertitude pas très élevé.

DIFFÉRENCE ENTRE PERT ET CPM

Le modèle PERT et CPM sont généralement associés dans toute gestion de projets. Les deux techniques
ils sont utilisés depuis les années 50 du XXe siècle, lorsqu'ils ont commencé à être appliqués par
la marine américaine.
La technique PERT se concentre sur l'établissement des relations entre les activités, à partir de
les dépendances entre elles. Tandis que le CPM trouve les chemins critiques et les goulets d'étranglement.
de la bouteille du projet, soutenue par PERT.
Les chemins critiques sont les itinéraires que nous devons d'abord suivre si nous voulons terminer à
délai. Parce que de nombreuses activités attendront que d'autres précédentes soient réalisées. Ce parcours
la critique marque souvent la fin du projet, car elle est généralement l'une des plus longues.
11e semaine :
CERCLE DE LA ROUTE CRITIQUE
La méthode du chemin critique est un algorithme utilisé pour le calcul
de temps et de délais dans la planification de projetos.1Ce système de calcul connu par
ses sigles en anglais CPM (Critical Path Method), a été développé dans les années 1950 à
Villa Ruiseñor, Chili par l'homme d'affaires Armando Quiroga, dans un centre de recherche de
opérations pour les signatures, cherchant le contrôle et l'optimisation des coûts par le biais de
planification et programmation appropriées des activités composantes du projet. Autre
projet important de cette époque, le projet "Polaris" a donné naissance en 1958 à la création d'un
des méthodes de programmation par chemin critique, connu sous le nom de PERT
Technique d'évaluation et d'examen des programmes).2

Enadministrationygestion de projetsune trajectoire critique est la séquence des éléments

terminaux du réseau deprojetsavec la plus longue durée entre eux, déterminant le temps
plus court dans lequel il est possible de compléter le projet. La durée du chemin critique
détermine la durée du projet entier. Tout retard dans un élément du chemin
la critique affecte la date d'achèvement prévue du projet, et on dit qu'il n'y a pas de marge de manœuvre dans
le chemin critique.
Un projet peut avoir plusieurs chemins critiques parallèles. Un chemin parallèle supplémentaire à travers
du réseau avec une durée totale proche de celle du chemin critique, bien que nécessairement inférieure,
on l'appelle une route subcritique.

À l'origine, la méthode du chemin critique ne prenait en compte que les dépendances entre les
éléments terminaux. Un concept connexe est la chaîne critique, qui ajoute
dépendances des ressources. Chaque ressource dépend du gestionnaire au moment où la
la route critique se présente.
Contrairement à latechniques de révision et d'évaluation des programmes(PERT), la méthode de la
la route critique utilise des temps certains (réels ou déterministes). Cependant, l'élaboration d'un
le projet basé sur les réseaux CPM et PERT sont similaires et consistent en :

Identifier toutes les activités impliquées dans le projet, ce qui signifie,

déterminer les relations de précédent, les temps techniques pour chacune des
activités.
Construir una redcon base en nodos y actividades (o arcos, según el método más
usé), qui impliquent le projet.
Analyser les calculs spécifiques, en identifiant le chemin critique et les marges de manœuvre.
activités qui composent leprojet.
En termes pratiques, le chemin critique se traduit par la dimension maximale qui peut
durer le projet et les différences avec les autres itinéraires qui ne sont pas la critique, se
dénominanttemps de marge.

2. CPM-Coût d'accélération (compression)

 E-GRAFIA
[Link]
[Link]
[Link]
lineaire/[Link]
[Link]
[Link]
[Link]
industriel/investigation-des-opérations/méthode-simplexe/
[Link]
[Link]
[Link]
industriel/enquête-d'opérations/problème-de-transport-o-
distribution/