INVESTIGACION DE OPERACIONES

UNITÉ I : MODÈLES D'OPTIMISATION.

SESIÓN 7: HOJA DE TRABAJO

Problème de Transport : (Référence : Hitchcock, 1941 ; Kantorovich, 1942 ; Koopmans 1947).

Le problème consiste à décider combien d'unités déplacer depuis certains points d'origine (plantes,
villes, etc) à certains points de destination (centres de distribution, villes, etc) de manière à
minimiser les coûts de transport, étant donné l'offre et la demande à ces points. On suppose qu'ils sont connus.
les coûts unitaires de transport, les exigences de demande et l'offre disponible.

Par exemple, supposons qu'une entreprise possède deux usines qui fabriquent un certain produit en
quantités de 250 et 400 unités par jour, respectivement. Ces unités doivent être transférées à
trois centres de distribution avec des demandes quotidiennes de 200, 200 et 250 unités, respectivement.
Les coûts de transport (en $/unité) sont :

[Link]. 1 [Link].2 [Link].3

Plante 1 21 25 15
Plante 2 28 13 19

Il est nécessaire de formuler un modèle de programmation linéaire qui permette de satisfaire les exigences de
demande au coût minimal.

Solution :

Variables de Decisión:Xij: Unidades transportadas desde la planta i (i=1, 2) hasta el centro de

distribution j (j=1, 2, 3)

Fonction Objectif : Minimiser le coût de transport donné par la fonction : 21X11 + 25X12 + 15X13
+ 28X21 + 13X22 + 19X23

Restrictions :

Satisfaire les exigences de la demande :

X11 + X21 = 200

X12 + X22 = 200

X13 + X23 = 250

Sujeto à l'Offre des plantes :

X11 + X12 + X13 = 250

X21 + X22+ X23 = 400

Pas de négativité : Xij >= 0

Le diagramme suivant permet une visualisation de la situation précédente :

PAULO CESAR OLIVARES TAIPE

 INVESTIGACION DE OPERACIONES

Le premier ensemble de contraintes stipule que la somme des envois depuis une source ne peut pas être
plus que son offre ; de manière analogique, le deuxième ensemble exige que la somme des envois soit...
destin satisfait votre demande.

Le modèle qui vient d'être écrit implique que l'offre totaleSi=1AI doitm être au moins
égal à la demande totaleSj=1bj.n Lorsque l'offre totale est égale à la demande totale, la formulation
la résultante est appelée modèle de transport équilibré. Celui-ci diffère du modèle uniquement en
hecho de que todas las restricciones son ecuaciones, es decir:

SXje j = ai, i=1,2,..., m

SXje j = bj, j=1,2,..., n

Dans le monde réel, l'offre ne doit pas nécessairement être égale à la demande ou supérieure à celle-ci. Sans
embargo, un modèle de transport peut toujours s'équilibrer. L'équilibre, en plus de son utilité dans
La représentation à travers des modèles de certaines situations pratiques est importante pour le développement.
du méthode de solution qui exploite complètement la structure spéciale du modèle de transport.
Les deux exemples suivants présentent l'idée d'équilibre et également ses implications pratiques.

Comme les modèles doivent être équilibrés (les quantités offertes doivent être égales aux quantités
demandées) nous pouvons exprimer les inéquations comme des équations (=). Ces modèles peuvent
résoudre en appliquant le simplexe, mais en définissant les inégalités comme des équations (=) nous les résumons toutes
les données dans un tableau de transport sur lesquelles nous appliquons la méthode ou la technique sélectionnée pour
obtener una solución factible inicial. Siempre esta solución debe proporcionar m+n-1 variables
de base.

Pour déterminer une solution réalisable initiale, nous avons trois méthodes :

1) Méthode du coin nord-ouest

2) Méthode de Coût minimum
3) Méthode d'approximation de Vogel ou pénalités.

1) La méthode du coin nord-ouest commence par l'attribution de la quantité maximale

admissible à travers l'offre et la demande de la variable x11 (celle de l'angle nord-ouest du tableau).
Ensuite, on barre la colonne (ligne) satisfaite, ce qui indique que les variables restantes de la
columna (renglón) tachada son iguales a cero. Si se satisfacen una columna y un renglón al mismo
temps, seul un (une ou l'autre) peut être rayé. (Cette condition garantit l'emplacement
automatique de variables de base zéro, s'il y en a). Après avoir ajusté les quantités d'offre et

PAULO CESAR OLIVARES TAIPE

 INVESTIGACION DE OPERACIONES

demande de toutes les lignes et colonnes non barrées, la quantité maximale réalisable est attribuée au
premier élément non barré de la nouvelle colonne (ligne). Le processus est terminé lorsqu'on laisse
sans rayer exactement une ligne ou une colonne.

SOLUTION INITIALE AMÉLIORÉE

2) MODÈLE DU COÛT MINIMAL

Attribuez la plus grande valeur possible à la variable avec le coût unitaire le plus bas de tout le tableau.
Rayer la ligne ou la colonne satisfaite. Après avoir ajusté l'offre et la demande de tous les
rangs et colonnes non barrés, répétez le processus en attribuant la valeur la plus élevée possible à la
variable avec le coût unitaire non barré le plus bas. La procédure est complète lorsque
il reste exactement une ligne ou bien une colonne sans rayer.

3) MÉTHODE D'APPROCHE DE VOGEL (VAM)

Cette méthode est heuristique et produit généralement une meilleure solution initiale que les deux méthodes précédentes.
décrits. En fait, le VAM produit généralement une solution initiale optimale, ou proche du niveau optimal. Les
Les étapes de la procédure sont les suivantes :

Étape 1 : Évaluez une pénalité pour chaque ligne en soustrayant le plus petit élément du coût de
r té de l'élément de coût inférieur suivant dans la même ligne.

Paso2: Identifique el renglón o columna con la mayor penalización, rompiendo empates en forma
arbitraire. Attribuez la valeur maximale possible à la variable avec le coût le plus bas de la ligne ou de la colonne
sélectionné. Ajustez l'offre et la demande et rayer la ligne ou la colonne satisfaite. Si une ligne ou
la colonne sont satisfaites en même temps, seul l'un d'eux est rayé et le reste de la ligne se voit attribuer
une offre zéro. Toute ligne ou colonne avec une offre ou une demande zéro ne doit pas être utilisée pour
calculer des pénalités futures.

Étape 3 :

a.-si seulement il y a une ligne ou une colonne non rayée, arrêtez-vous.

b.-s'il n'y a qu'une seule ligne avec une offre positive non barrée, déterminez les variables de base du
ligne par la méthode du coût minimum.

c.-Si toutes les lignes et colonnes non barrées ont une offre ou une demande zéro assignée,
déterminez les variables de base nul par la méthode du coût minimum. Arrêtez-vous.

d.- Sinon, calcule les pénalités des lignes et des colonnes non barrées et ensuite
dirigez-vous à l'étape 2.

Exemple 1 (Modèle de transport standard)

La société MG Auto possède des usines à Los Angeles, Detroit et La Nouvelle-Orléans. Ses centres de
les principaux points de distribution sont Denver et Miami. Les capacités des usines pendant le trimestre
Les demandes trimestrielles dans les deux centres sont de 1 000, 1 500 et 1 200 automobiles.
La distribution est de 2 300 et 1 400 véhicules. Le coût du transport d'une voiture par train est de 8
centavos par mile. Le diagramme des distances parcourues entre les usines et les centres de
la distribution est :

PAULO CESAR OLIVARES TAIPE

 INVESTIGACION DE OPERACIONES

Denver Miami
1 000 1 690
Los Angeles
Détroit 1 250 1 350
1 275 850
La Nouvelle-Orléans

Cela produit un coût par voiture à raison de 8 cents par mile parcouru. Produit les coûts
suivants (arrondis à des entiers), qui représentent Cje j du modèle original :

Denver Miami
80 215
Los Angeles
Détroit 100 108
102 68
Par l'utilisation La Nouvelle-Orléans de
codes
représente le
numériques qui représentent les plantes et les centres de distribution, nous faisons que X j j
nombre de voitures transportées de la source à la destination. Comme l'offre totale (= 1 000 + 1
500 + 1 200 = 3 700) est égal à la demande ( = 2 300 + 1 400 = 3 700), le modèle de transport
la résultante est équilibrée. Par conséquent, le modèle suivant de PL qui représente le problème a
toutes les restrictions d'égalité.

Minimiser Z = 80X11+ 215X12+ 100X21+ 108X22+ 102X31 + 68X32

Sujeto a:

X 11 X12 = 1 000
X21 X22 = 1 500
X31 X32 = 1 200
X11 X21 X31 = 2 300
X12 X22 X32 = 1 400

Xje j pour toutes lesiyj

Une méthode plus résumé pour représenter le modèle de transport consiste à utiliser ce que l'on
table de transport. C'est une forme de matrice où ses lignes représentent les sources et
ses colonnes les destinations. Les éléments de coût C sont
j j résumés dans le coin nord-ouest de la cellule
de la matrice (i, j). Par conséquent, le modèle de MG peut être résumé dans le tableau suivant :

PAULO CESAR OLIVARES TAIPE

 INVESTIGACION DE OPERACIONES

Exemple 2 (Modèle de transport avec équilibre)

Dans l'exemple précédent, supposez que la capacité de l'usine de Detroit est de 1 300 automobiles.
(au lieu de 1 500). On dit que la situation est déséquilibrée parce que l'offre totale (=3 500) ne
est égal à la demande totale (=3 700). Notre objectif est de reformuler le modèle de
transporte de manière à répartir la quantité manquante (=3 700 – 3 500 = 200) de manière optimale entre
les centres de distribution.

Comme la demande est supérieure à l'offre, on peut ajouter une plante fictive avec une capacité
de 200. Il est permis que cette usine, dans des conditions normales, envoie sa "production" à tous les
centres de distribution. Physiquement, la quantité d'unités envoyées à une destination depuis une usine
ficticia représentera la quantité manquante à cette destination.

La seule information qui manque pour compléter le modèle ce sont les "coûts de transport" unitaires
de l'usine fictive aux destinations. Comme l'usine n'existe pas, il n'y aura aucun envoi physique et le coût
le transport unitaire est nul. Cependant, nous pouvons aborder la situation sous un autre angle en disant
qui entraîne un coût de pénalité pour chaque unité de demande insatisfaite dans les centres de
distribution. Dans ce cas, les coûts de transport unitaires seront égaux aux coûts de pénalisation.
unitaires dans les différentes destinations.

Denver Miami
Los Angeles 80 215 1 000
Détroit 100 108 1 300
La Nouvelle-Orléans 102 68 1 200
Plante fictive 0 0 200

De manière analogue, si l'offre est supérieure à la demande, nous pouvons ajouter une destination fictive.
il réglera la différence. Par exemple, supposons que la demande à Denver diminue à 1
900tout automobile envoyé d'une usine à un centre de distribution fictif représente
un excédent dans l'usine.

Denver Miami Destin

Fictif
Los Angeles 80 215 0 1 000
Détroit 100 108 0 1 500
La Nouvelle-Orléans 102 68 0 1 200

L'application du modèle de transport ne se limite pas au problème de "transport".

L'exemple suivant illustre l'utilisation du modèle de transport dans d'autres domaines.

Exemple 3 (Modèle d'inventaire de production)

PAULO CESAR OLIVARES TAIPE

 INVESTIGACION DE OPERACIONES

Une entreprise construit une usine principale pour la production d'un article dans une période de
quatre mois. Les demandes au cours des quatre mois sont : 100, 200, 180 et 300 unités. Une demande
pour le mois en cours peut être satisfait par :

1. Production excessive d'un mois précédent stockée pour une consommation ultérieure.
2. Producción en el mes actual.
3. Production excessive dans un mois suivant pour couvrir les commandes des mois précédents.

Le coût de production variable par unité dans un mois donné est de 4,00 $. une unité produite
pour une consommation ultérieure, cela entraînera un coût de stockage de 0,50 $ par unité par mois.
D'autre part, les articles commandés dans les mois précédents entraînent un coût de pénalité de
2,00 $ par unité par mois. La capacité de production pour fabriquer le produit varie chaque mois. Les
Les calculs des quatre mois suivants sont 50, 180, 280 et 270 unités, respectivement.

L'objectif est de formuler le plan d'inventaire de production à coût minimum. Cela

Le problème peut être formulé comme un modèle de « transport ». L'équivalence entre les
Les éléments des systèmes de production et de transport sont établis de la manière suivante :

Système de Production
Système de Transport
Fuentei 1. Période de production
2. Destinoj 2. Période de demande
3. Offre à la source 3. Capacité de production de la période
4. Demande à la destination 4. Demande de la période
5. Costo de transporte de la fuenteial destino 5. Costo de producto e inventario del periodoialj
j

Dans le tableau ci-dessous, un résumé du problème est présenté sous forme de modèle de transport :

Période
1 2 3 4 Capacité
Demande 1 4 4,5 5 5,5 50
2 6 4 4.5 5 180
3 8 6 4 4,5 280
4 10 8 6 4 270
Demanda: 100 200 180 300

Le coût de transport unitaire du périodeialjes :

Coût de production eni, i=j

C je j = Coût de production eni / coût de stockage eniaji<j

Coût de production eni/ coût de pénalité eniaji>j

La définition de Cje jindique que la production dans la période ipour la même période (i = j) seulement
égale le coût unitaire de production. Si le péridoise produit pour des périodes futures j (i < j), se
entraîne un coût de stockage supplémentaire. De la même manière, la production est prévue pour couvrir
Les commandes faites antérieurement (i > j) entraînent un coût de pénalité supplémentaire.

PAULO CESAR OLIVARES TAIPE

 INVESTIGACION DE OPERACIONES

Exercices Modèle de transport.

La fabrique de verre dispose de 40 tonnes de sable de type A et de 20 tonnes de sable de type B pour
utiliser ce mois. Le sable est fondu pour fabriquer du verre optique, du verre pour emballages ou du verre pour
fenêtres. La société a des commandes pour 20 tonnes de verres optiques, 25 tonnes de verre pour
emballages et 25 tonnes de verre pour fenêtres. Les coûts de production d'une tonne de chaque type de
le verre à partir de chaque type de sable est ci-dessous.

Résolvez le problème en le formulant comme un problème de transport.

Type de verre Optique Emballages Fenêtres

Arenes A 12 3 5
Arène B 8 2 4

2. rta l'entreprise a deux usines et trois distributeurs. Dans le tableau suivant, les coûts sont montrés
transport de chaque plante à chaque centre de distribution, ainsi que les offres disponibles de chaque
plante et les exigences de chaque distributeur.

Résoudre le problème en le formulant comme un problème de transport.

Distributeur
Plante Un B C Offre
J 100 85 110 20
K 90 105 75 40
Demande 15 25 20

3. L'usine produit trois articles A, B et C, dans les trois usines qu'elle possède. La première et
Au deuxième étage, ils peuvent fabriquer les trois articles, mais au troisième, seuls les articles A et C.
La demande des articles A, B et C est respectivement de 600, 800 et 700 unités par jour.
primera como la tercera planta su producción es de 600 unidades diarias y la segunda planta es de 900
unités quotidiennes.
Le coût de fabrication $/unité est :

Articles
Plante A B C
1 5 8 6
2 6 8 5
3 7 X 5

Formuler et résoudre le problème comme un modèle de transport.

4. ces usines produisent un produit, qui est ensuite transporté à deux centres de consommation. Les coûts
de production, les coûts de transport depuis les usines jusqu'aux centres de consommation, ainsi que l'offre
et la demande se trouvent dans le tableau suivant :

Coût de Coût de Transport $/u

Plante Production $/u C. de consommation1 C. de consommation2 Offre
1 50 5 7 900
2 55 8 5 500

PAULO CESAR OLIVARES TAIPE

 INVESTIGACION DE OPERACIONES

3 53 6 6 600
Demande 1.200 700

Résoudre le problème comme un modèle de transport avec l'objectif de minimiser le coût total
interpréter les résultats.

5-Trois usines produisent un produit, qui est ensuite transporté vers deux centres de consommation. Les coûts
de production, les coûts de transport des usines vers les centres de consommation, comme les prix
de vente dans les centres de consommation ainsi que l'offre et la demande se trouvent dans le tableau suivant :

Costo de Transporte $/u

Coût de
Production $/u C. de consommation1 C. de consommation2
Plante Offre
1 50 5 7 800
2 55 8 5 500
3 53 7 6 500
Prix de V. 69 70
Demande 1.200 700

Résoudre le problème comme un modèle de transport avec pour objectif de maximiser le bénéfice total
et interpréter les résultats.

6- Trois centrales électriques d'une capacité de 20, 35 et 40 millions de kilowatts/heure,

fournissent de l'électricité à trois villes. La demande maximale dans les trois villes est estimée à 30,
35 et 25 millions de kilowattheures. Le tableau fournit le prix par million de kilowattheures en
les trois villes.

Villes
Plante 1 2 3
1 600 $ 700 $ 400 $
2 320 $ 300 $ $350
3 500 $ 480 $ 450 $

Au mois d'août, il y a une augmentation de 20 % de la demande dans chacune des trois villes.
que l'on peut satisfaire en achetant de l'électricité à un autre réseau, à un prix de 1000 $ par million de
kilowattheures. Cependant, ce réseau n'est pas connecté à la ville 1. La Société de Services
Públicos veut déterminer le plan le plus économique pour la distribution et l'achat d'énergie.
électrique supplémentaire.

Resuelva e interprete la solución óptima.

Une entreprise dispose de trois usines pour fabriquer quatre produits : A, B, C et D. L'offre de
La production des trois usines est : 900, 1200 et 700 respectivement, peu importe quel produit il s'agit.
usine. Les demandes sont de 500 unités de A, 700 unités de B, 900 unités de C et 900
unidades de D. La fábrica 3 no puede elaborar el producto B. Hay una penalización por demanda
insatisfaite d'un produit, qui est de 25 % de son coût le plus bas pour chaque produit
fabrication, mais le produit B doit satisfaire toute sa demande. Les coûts de fabrication sont donnés
dans le tableau suivant :

Produits

PAULO CESAR OLIVARES TAIPE

 INVESTIGACION DE OPERACIONES

Usines B C D
Un
1 4 3 2 3
2 5 4 4 2
3 4 5 4

Résolvez et interprétez la solution optimale avec l'objectif de minimiser le coût.

8- Trois raffineries avec des capacités maximales quotidiennes de 6, 5 et 6 millions de gallons d'essence
répartissent à trois zones de distribution avec des demandes quotidiennes de 5, 7 et 7 millions de gallons du
combustible. La gasolina se transporta a las tres áreas de distribución a través de una red de tubería.
Le coût de transport est calculé en fonction de la longueur du pipeline à un dollar pour 10 000 gallons.
par milla parcourue.
La tabla siguiente indica la distancia de la Refinería a las áreas de distribución en millas.

Zone de distribution
Raffinerie 1 2 3
1 120 180 80

2 300 100 90

3 200 250 120

De même, la zone de distribution 1 doit recevoir toute sa demande et toute pénurie dans les zones 2 et
3 entraînera une pénalité de dix dollars pour 10 000 gallons.
Trouver et interpréter la solution optimale.

Exercice : Il est nécessaire de traiter 4 tâches différentes pour celaOn

compte 4 machines. Pour
les différences technologiques le gaspillage produit dépend du type de tâche et de la machine
dans laquelle s'exécute, étant donné la matrice de déchets exprimée en pesos définir l'attribution
optimale.
MACHINES
TAREAS 1 2 3 4
Un 49 86 54 70
B 45 79 66 81
C 46 58 78 88
D 44 38 66 69

2. La société de fabrication "Jiménez et Associés" souhaite organiser une journée de maintenance

préventif à ses trois machines principales A, B et C. Le temps nécessaire pour réaliser le
la maintenance de chaque machine est de 1 jour, cependant, la journée de maintenance ne peut pas
durer plus d'un jour, en tenant compte du fait que l'entreprise dispose de trois fournisseurs de services
de maintenance doit être attribuée une équipe de maintenance à chaque machine afin de pouvoir
respecter la réalisation de la maintenance préventive. En tenant compte que selon le degré de

PAULO CESAR OLIVARES TAIPE

 INVESTIGACION DE OPERACIONES

la spécialisation de chaque équipe de prestataires de services de maintenance fait varier le coût de la tâche

Pour chaque machine en particulier, il faut attribuer l'équipement correct à la machine indiquée avec le
objectif de minimiser le coût total de la journée. Les coûts associés peuvent être observés dans la
tableau suivant :

3. Une compétition de relais de 400 mètres comprend quatre nageurs différents, qui
nagent successivement 100 mètres dos, brasse, papillon et libre. Un entraîneur a
six nageurs très rapides, dont les temps attendus (en secondes) dans les événements
les individus sont donnés ci-dessous :

Événement 1 Événement 2 Événement 3 Événement 4

(dos) (Nado de (Papillon) (Libre)
pecho)
Nageur 1 65 73 63 57
Nageur 2 67 70 65 58
Nageur 3 68 72 69 55
Nageur 4 67 75 70 59
Nageur 5 71 69 75 57
Nageur 6 69 71 66 59

Comment l'entraîneur doit-il assigner les nageurs aux relais afin de minimiser leurs
temps ?

4. Une chaîne de restaurants de restauration rapide souhaite construire quatre magasins dans le secteur de
Chicago. Auparavant, la société avait engagé quatre entrepreneurs et, étant satisfaite
avec toutes, elle les a invitées à concourir pour chaque travail. Les offres finales (en milliers de
dollars) sont ceux que montre le tableau.

Entreprises de construction

1 2 3 4
Magasin 1 85 88 87 82

PAULO CESAR OLIVARES TAIPE

 INVESTIGACION DE OPERACIONES

Magasin 2 78 77 77 76
Boutique 3 82 81 82 80
Tienda 4 84 84 86 83

Yaque la chaîne de restaurants souhaite avoir les nouveaux établissements prêts dès que possible.
comme cela est possible, accordera au maximum un travail à chaque constructeur. Quelle affectation donne
comme résultat un coût total minimum pour la chaîne de restaurants ?

5. Trouvez l'allocation à coût minimum pour le problème suivant d'assignation de 5

opérateurs à 5 machines :

3 8 2 10 3
8 7 2 9 7
6 4 2 7 5
8 4 2 3 5
9 10 6 9 10

6. La société avancée a trois travaux à réaliser sur trois machines différentes. Chaque travail
cela doit être fait sur une et une seule machine. Le coût de chaque travail sur chaque machine est donné
dans le tableau suivant. Donnez les affectations de travail qui minimisent les coûts.

Travail X Y Z
A 4 6 8
B 2 3 4
C 4 8 5

[Link] dispose de quatre ouvriers pour compléter quatre travaux.

Chaque ouvrier ne peut faire qu'un seul des travaux. Le temps requis
Chaque travailleur pour compléter chaque travail se remet dans le tableau

PAULO CESAR OLIVARES TAIPE

 INVESTIGACION DE OPERACIONES

PAULO CESAR OLIVARES TAIPE