Les TD Algo Line Simplexe PDF

North American Private University AU: 2014-2015
IIT: International Institute of Section: Génie Télécom 1

Technology
Département de Génie Télécommunication
Travaux dirigés 1
Recherche opérationnelle (Programmation linéaire)
Exercice 1
Une compagnie téléphonique nouvellement installée désire déterminer le nombre de standardistes à recruter qui
minimisera ses coûts quotidiens tout en assurant un service répondant à des normes rigoureuses. Les besoins
minimaux en standardistes pour une journée typique sont donnés par le tableau suivant:
Heures 0-3 3-6 6-9 9-12 12-15 15-18 18-21 21-24

Besoins 6 4 12 20 20 24 14 14
Chaque standardiste assurera 3 périodes consécutives de 3 heures de travail, et recevra un salaire quotidien
de 25D. L’entreprise verse une prime de 5D aux standardistes qui prennent leur service à 18h ou à21h. Cette
prime est portée à 11D pour ceux qui commencent à minuit, à 3h ou à 6h.
Formuler le programme linéaire qui répond aux objectifs de la société.
Exercice 2
La figure ci-dessous représente un réseau IP où on considère un seul sens de transmission indiqué par les flèches.
Le nombre figurant sur chaque lien indique la durée nécessaire (en secondes) pour transférer un paquet IP en
empruntant ce lien.
Formuler le programme linéaire qui donne le chemin le plus rapide pour effectuer le transfert du
routeur A vers le routeur G.
1
Exercice 3
Au cours des manoeuvres militaires, un officier doit choisir les membres d’une patrouille de taille minimale parmi
les différents soldats qui sont sous ses ordres et dont les compétences sont décrites par le tableau ci-dessous:
Soldat Radio Camouflage Tireur Endurance physique Sous-officier

A x x 6 5 x
B x 8 7
C x x 7 7
D x 4 9
E x 7 9 x
F x 8 6
L’officier doit respecter les conditions suivantes:

• Il faut un et un seul sous-officier.
• Il faut au moins 1 opérateur radio et au moins 1 spécialiste du camouflage.

• Au moins deux opérateurs radio ne feront pas partie de la patrouille afin de rester disponibles pour
d’autres missions.
• Les membres de la patrouille doivent posséder une note moyenne d’au moins 7 au tir et d’au moins 7.5
en endurance physique.
• Si A fait partie de la patrouille, alors ni B ni C ne doivent en faire partie.
Écrire un programme linéaire qui traduit l’objectif et les contraintes de l’officier.
Exercice 4
Le directeur d’un service hospitalier est chargé d’organiser le planning des infirmières. Une journée de travail
est divisée en douze tranches de deux heures chacune. Les besoins de personnel varient d’une tranche horaire à
l’autre. Par exemple, peu d’infirmières sont nécessaires pendant la nuit, par contre l’effectif doit être renforcé
le matin pour assurer les soins aux patients. Le tableau suivant donne les besoins de personnel pour chacune
des tranches horaires:
Tranche horaire Nombre minimal d’infirmières

06h-08h 35
08h-10h 40
10h-12h 40
12h-14h 35
14h-16h 30
16h-18h 30
18h-20h 35
20h-22h 30
22h-00h 20
00h-02h 15
02h-04h 15
04h-06h 15
Écrire un programme linéaire en vue de déterminer le nombre minimal d’infirmières néces-

saires pour couvrir tous les besoins, sachant qu’une infirmière travaille huit heures par jour et
qu’elle a droit à une pause de deux heures au bout de quatre heures de travail.
2
Exercice 5
Un manufacture produit un type particulier de poutres d’acier de quatre grosseurs différentes : petites, médium,
grosses et très grosses. Ces poutres peuvent être manufacturées à l’aide de l’une quelconque des trois machines
A, B, C. Le tableau suivant donne en cm la longueur des poutres que chaque machine peut produire à l’heure:
Machines A B C
Petites 300 600 800
Médiums 250 400 700
Grosses 200 350 600
Trés grosses 100 200 300
Supposons que chaque machine peut être utilisée au plus 50 heures par semaine et que les coûts horaires
respectifs de ces machines sont 30, 50, 80. De plus, une étude du marché assure que la demande hebdomadaire
pour ces différentes grosseurs de poutres sera (respectivement) de 10000 cm, 8000 cm, 6000 cm, 6000 cm.
Écrire un programme linéaire de cette production.
Exercice 6
Une entreprise fabrique deux types d’interrupteurs électriques A et B. Les bénéfices nets sont respectivement
de 0,5 et 0,4 dt par unité. Une pièce de type A nécessite 2 minutes de travail dans l’usine; les interrupteurs de
type B nécessitent 1,5 minutes par pièce.
L’usine fonctionne 10 heures par jour. L’approvisionnement en fil de laiton ne permet la fabrication jour-
nalière que de 600 interrupteurs de tout type. En plus, le type A nécessite un isolant de céramique spécial
disponible en quantité suffisante pour fabriquer 400 interrupteurs par jour ; de même, un isolant différent est
utilisé pour B, la quantité disponible par jour permet de fabriquer au maximum 350 interrupteurs.
Un client potentiel de cette société exige d’avoir chaque jour 50 interrupteurs de type A.
Formuler ce problème sous forme d’un programme linéaire.
Exercice 7
Un étudiant doit assister à 20 séances de formation (anglais, français et informatique) et il est face aux con-
traintes suivantes:
• il doit assister au moins à 5 séances d’anglais et au moins 3 séances d’informatique,
• il ne faut pas que le nombre de séances d’anglais dépasse le double du nombre des séances de français,
• le centre formation exige un paiement total minimal de 300dt,
• l’étudiant possède un budget de 350 dinars,
Le prix d’une séance d’anglais est de 10dt, d’une séance de français est de 17dt et d’une séance d’informatique
est de 25dt.
Formuler ce problème sous forme d’un programme linéaire qui minimise le budget de formation
de cet étudiant.
Exercice 8
L’office du tourisme d’une ville décide de renouveler le mobilier d’un jardin public. Pour cela, il est nécessaire
d’acheter au moins 30 tables de pique-nique, 40 bancs publics et 90 poubelles. Les deux fournisseurs contactés
proposent chacun un type de lot :
Lot Tables Bancs Poubelles coût d’un lot

A 1 3 4 2000 dt
B 3 2 6 3600 dt
L’office de tourisme cherche à déterminer les nombres des lots à acheter, de chaque fournisseur, afin de
minimiser ses dépenses sachant qu’il possède un budget maximal de 50000dt.
3
Exercice 9
L’entreprise BoisMode fabrique des bureaux (B), des tables (T) et des chaises (C). La fabrication de chaque
type de ces meubles requière du bois et deux types de main-d’oeuvre qualifiée: menuiserie et peinture. Le
tableau suivant résume les quantités de chaque ressource nécessaire pour produire une pièce de chaque meuble.
Ressource Quantité nécessaire de la ressource Disponibilité
hebdomadaire
B T C
Bois a 8 6 1 48
Menuiserie b 4 2 1,5 20
Peinture c 2 1,5 0,5 8
a (en nombre de planches)
b (en heures de main-d’oeuvre)
c (en heures de main-d’oeuvre)
Le prix de vente d’un bureau est de 180DT , celui d’une table est de 60DT , et celui d’une chaise est de 40DT .
Le carnet des commandes impose la production d’au moins 5 tables par semaine. BoisMode réalise qu’il faut
produire au moins quatre chaises pour chaque table produite. La demande des tables et chaise est illimitée,
tandis que celle des bureaux est limitée à 10 par semaine.
Formuler un programme linéaire afin de maximiser le chiffre d’affaire hebdomadaire de BoisMode.
Exercice 10
Une usine produit des barres d’aciers de longueur 10 cm. Elle a reçue quatre commandes de barreaux de
différentes longueurs. Cette commande se présente comme suit:
Commandes A B C D
Longueur (cm) 3 4 5 7
Nombre d’unités 52 46 15 32
Pour satisfaire cette commande, le directeur de l’usine décide le découpage des barres de longueur 10 cm en
barreaux de longueur, 3 cm, 4 cm, 5 cm et 7 cm. Aussi le directeur veut minimiser le total des chutes, c’est-à-dire
la longueur totale de barres inutilisables, tout en satisfaisant les demandes.
4
Travaux dirigés 1
Recherche Opérationnelle
Programmation Linéaire
(Correction)
Exercice 1
Les besoins minimaux en standardistes pour une journée typique sont donnés par le tableau suivant:
Variables de décision :
= Le nombre de standardistes dans la période entre 0h et 3h
Fonction objectif :
Sous contraintes (s.c) :
Enseignant : Boukthir HADDAR ~1~ A.U : 2014-2015

Exercice 2
De même nous définissons : , , , , , , et
Fonction objectif :
+ + + + +
On doit partir de A :
Si on arrive à B on doit en partir :
Si alors
Si on n’arrive pas à B alors on n’en repart pas : 
Si alors
De même pour :
, , , , , , , { } Contrainte d’intégrité

Exercice 3
De même nous définissons , , , .
Fonction objectif :
(il faut un et un seul sous-officier).
(Il faut au moins 1 opérateur radio).
(Il faut au moins 1 spécialiste du camouflage).
(Il faut Au moins deux opérateurs radio ne feront pas partie de la patrouille)
𝑥𝐴 𝑥𝐵 𝑥𝐷 𝑥𝐹
(Les membres de la patrouille doivent posséder une note moyenne d’au moins 7 au tir)
. . 𝑥𝐴 . 𝑥𝐵 . 𝑥𝐶 . 𝑥𝐷 . 𝑥𝐸 . 𝑥𝐹
(Les membres de la patrouille doivent posséder une note moyenne d’au moins 7.5 en endurance physique).
(Si A fait partie de la patrouille, alors B ne doit pas en faire partie).
(Si A fait partie de la patrouille, alors C ne doit pas en faire partie).
, , , { } (Contraintes d’intégrité)

Exercice 4
Pour satisfaire la période entre 6h et 8h il faut compter le nombre d’infermière dans la période entre 6h et 8h,
ceux dans la période entre 4h et 6h, prendre en considération une pause de 2h à 4h, compter ceux dans la
période entre 0h et 2h et enfin compter ceux dans la période entre 22h et 0h. De même pour les autres
périodes.
= Nombre des infermières dans la période entre 0h et 2h

……
……
……
Fonction objectif :
(Contraintes d’intégrité)

Exercice 5
= Nombre d’heures travaillées par semaine sur la machine pour fabriquer la poutre de type avec :
=1 : machine A =1 : poutres petites

=2 : machine B =2 : poutres médiums
=3 : machine C =3 : poutres grosses
=4 : poutres très grosse
Fonction objectif :
Disponibilité de chaque machine
Satisfaction de la demande du marché
Exercice 6
variables de décisions:
: Nombre d’interrupteur de type A
: Nombre d’interrupteur de type B
Fonction Objectif:
Sous contraintes:

Exercice 7
: Nombre de séances d’anglais
: Nombre de séances de français
: Nombre de séances d’informatique
Fonction Objectif:
Sous contraintes:
Exercice 8
Nombre de lots A
Nombre de lots B
Fonction Objectif:
Sous contraintes:

Exercice 9
Nombre d’unités produites du meuble B.
Nombre d’unités produites du meuble T.
Nombre d’unités produites du meuble C.
Fonction Objectif:
Sous contraintes:
Exercice 10
Il faut tout d’abord faire la liste des combinaisons possibles :
Variables de décisions: Fonction Objectif:

: Nombre de barreaux pour la combinaison 1 𝑀𝑖𝑛 𝑍 𝑥 𝑥 𝑥 𝑥
: Nombre de barreaux pour la combinaison 2 Sous contraintes:
: Nombre de barreaux pour la combinaison 3 𝑥 𝑥 𝑥 𝑥
: Nombre de barreaux pour la combinaison 4 𝑥 𝑥 𝑥
: Nombre de barreaux pour la combinaison 5 𝑥 𝑥 𝑥7
: Nombre de barreaux pour la combinaison 6 𝑥
7 : Nombre de barreaux pour la combinaison 7 𝑥 𝑥 𝑥 𝑥 𝑥 𝑥 𝑥7 (Contraintes d’intégrité)
Technology
Travaux dirigés 2
Recherche Opérationnelle
Résolution graphique
Exercice 1
On considère le programme linéaire suivant:
M axZ
 = x1 + x2

 x1 + 2x2 ≤ 4
2x1 + x2 ≤ 3

s.c

 x2 ≥ 1
x1 , x2 ≥ 0

1. Vérifier que ( 23 , 53 )est une solution réalisable.

2. Montrer que pour toute solution réalisable (x1 , x2 ) on a la relation suivante x1 + x2 ≤ 37 .
3. En déduire que ( 23 , 53 ) est une solution optimale.
Exercice 2
Une usine fabrique deux produits P1 et P2 qui rapportent respectivement un profit de 1700 et 3200 dinars.
Chacun de ces produits demande pour son usinage des heures de fabrications unitaires sur les machines comme
indiqué dans le tableau suivant:
Machine A B C D E
P1 0 1.5 2 3 3
P1 3 4 3 2 0
Disponibilité 39 60 57 70 57
Donner les quantités optimales à produire de chaque type de produit en résolvant graphiquement le programme
linéaire adéquat.
Exercice 3
Résoudre graphiquement les programmes linéaires suivants:
MinZ = −x1 + x2 M inZ = −x1 M inZ = −2x1 − x2

−2x1 + x2 ≤ 2  
 3x1 + 4x2 ≤ 12  3x1 + 4x2 ≤ 12


x1 − 2x2 ≤ 2

s.c s.c −2x1 − x2 ≥ −6 s.c −2x1 − x2 ≥ −6
x1 + x2 ≤ 5
x1 , x2 ≥ 0 x1 , x2 ≥ 0

  
x1 , x2 ≥ 0

MaxZ = 3x1 + 4x2 MaxZ = −x1 − x2 MinZ = −x1 − x2
 3x1 + 4x2 ≤ 12  3x1 + 4x2 ≥ 12  3x1 + 4x2 ≥ 12
s.c 2x1 + x2 ≤ 3 s.c 2x1 + x2 ≥ 4 s.c 2x1 + x2 ≥ 4
x1 , x2 ≥ 0 x1 , x2 ≥ 0 x1 , x2 ≥ 0
  
M axZ = 6x1 − 3x2 + 5x3 + 2x4
 x1 + 5x2 ≤ 120
s.c x3 − 2x4 ≤ −40
x1 , x2 , x3 , x4 ≥ 0

1
Correction TD 2
Recherche Opérationnelle
(Résolution graphique)
Exercice 1
1) , vérifient toutes les contraintes donc c’est une solution réalisable pour le
programme linéaire ci-dessus

2) Montrons que une solution réalisable :
(1) + (2)  d’où si on divise le tous sur 3 on trouve : .
3) D’après la question 2) on a : , or ( est une solution réalisable qui donne
(le maximum possible). Donc ( est l’unique solution optimale.
Exercice 2
: La quantité à produire du produit
: La quantité à produire du produit
Fonction objectif :
Les contraintes :
Contraintes de disponibilité des machines
(Contrainte d’intégrité)

Le programme linéaire résultant est le suivant :
PL :
Remarque : Si on enlève la contrainte (4), l’espace des solutions réalisables ne change pas.
On dit que la contrainte (4) est redondante.
Pour déterminer le sens selon lequel on maximise , il suffit de tracer deux droites de la
fonction objectif qui correspondent à deux valeurs de choisis arbitrairement.
On choisit par exemple :
: (0, 0) et (10, -5.32)
: (0, 3.1) et (10, -2.1)
On translate par la suite la droite de la fonction objectif selon le sens d’optimisation. Le point
le plus loin est le point D qui correspond à l’intersection de la droite de la contrainte (2) avec
celle de la contrainte (3).
 Solution optimale : , ,

Exercice 3
PL1 :
Traçage des droites :
Pour déterminer le sens selon lequel on minimise , il suffit de tracer deux droites de la
: (1, 1) et (2, 2)
: (1, 2) et (2, 3)
le plus loin est le point C qui correspond à l’intersection de la droite de la contrainte (2) avec

PL2 :
le plus loin est le point C qui correspond à l’intersection de la droite de la contrainte (2) avec
celle de la contrainte .

PL 3 :
: (1, -2) et (0, 0)
: (0, -1) et (1, -3)
le plus loin est le point B qui correspond à l’intersection de la droite de la contrainte (1) avec

PL 4 :

: (0, 0) et (2, - )
: (1, -0.5) et (0, 0.25)
le plus loin est le point A qui correspond à l’intersection de la droite de la contrainte (1) avec

PL 5 :
RQ : Nous somme dans le cas d’un espace de solution réalisable non borné.
: (0, 0) et (1, -1)
: (1, -2) et (0, -1)
le plus loin est le point B qui correspond à l’intersection de la droite de la contrainte (1) avec

PL 6 : (même droites)
Si on change la fonction objectif par
Le sens d’optimisation (de minimisation) indique aussi que nous somme dans le cas d’un PL
non borné.  Pas de Solution réalisable pour ce PL.
PL7 :
Les variables de décisions ( et ( ) sont indépendants (il n’y a aucune contrainte

qui les relie). Donc on peut séparer le PL en deux : PL1 et PL2.
(PL1) 𝑀𝑎𝑥 𝑧 𝑥 𝑥 (PL2) 𝑀𝑎𝑥 𝑧 𝑥 𝑥

𝑥 𝑥 𝑥 𝑥
𝑆𝑐 𝑆 𝑐
𝑥 𝑥 𝑥 𝑥

Pour tracer la droite de : (0, 0) et (1, 2)
Pour tracer la droite de : (2, 3.66) et (7, 7.66)
PL2 est non borné donc PL est aussi non borné  pas de solution réalisable.

Technology
Travaux dirigés 3
Recherche Opérationnelle
Méthode de Simplexe
Exercice 1
Résoudre chacun des programme linéaires suivants en utilisant l’algorithme du simplexe:
M ax Z = 2x1 + 3x2 + 4x3 + 5x4  M ax Z = 3x1 + 4x2 + 2x3
x1 + x2 + x3 ≤ 56
 x1 + 2x2 + 3x3 + 4x4 ≤ 256


−2x1 + x3 ≤ −9
 

(P L1 ) x1 + 2x2 + 2x3 + 3x4 ≤ 128 (P L2 )
 
s.c s.c 3x1 + 2x2 + 4x3 ≥ 5
 x1 + 2x2 + x3 + 2x4 ≤ 96
 
 x2 ≥ −3
x1 , x2 , x3 , x4 ≥ 0
 

x1 , x2 , x3 de signes quelconques

Exercice 2
Résoudre chacun des programme linéaires suivants en utilisant l’algorithme du simplexe:
M inZ = −0.75x1 + 20x2 − 0.5x3 + 6x4 M in Z = 2x1 − 4x2 − 3x3 + x4

 0.25x 1 − 8x 2 − x 3 + 9x 4 ≤ 0 
 3x1 − x2 + 4x3 + x4 ≥ 15
(P L1 ) 0.5x1 − 12x2 − 0.5x3 + 3x4 ≤ 0 (P L2 ) x1 + 3x2 − x4 ≤ 10
 
s.c s.c

 x 3 ≤ 1 
 2x1 + x2 + x3 = 12
x1 , x2 , x3 , x4 ≥ 0 x1 , x2 , x3 , x4 ≥ 0
 
Exercice 3
Trouvez 3 solutions optimales du programme linéaire suivant:
Max Z = x1 + 3x2 + 5x3
 3x1 + x2 + x3 ≤ 6
s.c 6x1 + 3x2 + 5x3 ≤ 15
x1 , x2 , x3 ≥ 0

Exercice 4
Le tableau du simplexe représenté ci-dessous correspond à un programme linéaire dont l’objectif est la max-
imisation de Z = ax1 + bx2 .
Coef V B x1 x2 e1 e2 e3 V aleur
− 23 0 f 0 1
6 46
5
-18 0 0 1 2 k
c 1 g i − 61 4
cj d e h j − 12 Z=m
1. Donner les variables de base de ce tableau.
2. Certains paramètres de ce tableau ne peuvent prendre qu’une valeur unique et précise. Déterminer la
valeur de chacun de ces paramètres.
3. Sous quelles conditions la solution de base associée à ce tableau est l’unique solution optimale ?
4. Sous quelles conditions le programme linéaire admet une infinité de solutions optimales ?
5. Sous quelles conditions le programme linéaire n’est pas borné ?
6. Sous quelles conditions la solution de base associée à ce tableau est dégénérée ?
1
Correction TD 3
Exercice 1
Résoudre le PL suivant avec la méthode de Simplexe
Ecriture du PL sous la forme standard :
SBR0=(0, 0, 0, 256, 128, 96)
Construction du tableau 0 associé à SBR0
Coef VB Valeur Ratio

0 1 2 3 4 1 0 0 256 256/4
0 1 2 2 3 0 1 0 128 128/3
0 1 2 1 2 0 0 1 96 96/2
2 3 4 5 0 0 0 Z0 0
Construction du tableau 1

0 -1/3 -2/3 1/3 0 1 -4/3 0 256/3 256
5 1/3 2/3 2/3 1 0 1/3 0 128/3 64
0 1/3 2/3 -1/3 0 0 -2/3 1 32/3 -32
1/3 -1/3 2/3 0 0 -5/3 0 Z1 640/3
Construction du tableau 2

0 -1/2 -1 0 -1/2 1 -3/2 0 192/3
4 1/2 1 1 3/2 0 1/2 0 64
0 1/2 2 0 2 0 0 1 288/3
0 -1 0 -1 0 -2 0 Z2 256
Tous les Cj sont donc S=(0, 0, 64, 0) est une solution optimale por PL avec z*=256.
Remarque : il existe plusieurs solutions optimales on peut continuer puisqu’il y a des VHB
qui ont des Cj =0. On peut choisir une VHB d’entre eux et la faire entrer dans la base pour
chercher d’autres solutions optimales bien sur qui ont la même valeur de z*=256 telles que
S=(64, 0, 32, 0) ;
2)
{ {
On pose , et on obtient :
SBR0=(0, 0, 0, 0, 0, 0, 56, 0, 0, 3, 9, 5)
sont les VB donc il faut les exprimer en fonction des VHB
Coef VB valeur Ratio

0 1 -1 1 -1 1 -1 1 0 0 0 0 0 56 56
0 0 0 0 0 -1 1 0 0 0 1 0 0 3 ∞
2 -2 0 0 -1 1 0 -1 0 0 1 0 9
3 -3 2 -2 4 -4 0 0 -1 0 0 1 5
Cj -3-5M 0 0 0 0 Z0=
0 0 0 - - 1 0 0 0 - -163
0 0 0 0 0 -1 1 0 0 0 1 0 0 3 3
0 0 - - 0 -1 0 1 -
1 -1 - - 0 0 - 0 0 -
Cj 0 0 0 0 0 Z1=
0 0 0 - 0 0 1 0 - -
0 0 0 - 0 0 0 - 1 -
0 0 - -1 1 0 - 0 -
1 -1 - 0 - - 0
Cj 0 0 0 0 0 0 Z2=
Coe
VB valeur Ratio
f
0 0 0 0 - 0 0 1 - - -
4 0 0 1 -1 0 0 0 - - 4
0 0 0 0 -1 1 0 0 1 0 0 ∞
1 -1 0 - 0 - - ∞
Cj 0 0 0 0 0 0 0 Z3=
0 0 0 0 - 0 0 2 - 1 - -1 102
4 0 56
0
0
Cj Z4= 227
Solution optimale :
Exercice 2
{
SBR0=(0, 0, 0, 0, 0, 0, 1)
Nous somme dans le cas d’une SBR dégénérée (voir cours) car il y a 2 VB et qui sont
nulles. Dans ce cas, il faut choisir (au cours des itérations de Simplexe) la variable sortante
qui nous offre pivot positif, (bien sûr dans le cas où il y a égalité du ratio entre deux VB.
Lorsqu’on rencontre un cycle il faut prendre le critère de la 1ère VHB qui a le lors du
choix de la VHB entrante.
TAB0 :

0 0.25 -8 -1 9 1 0 0 0 0
0 0.5 -12 -0.5 3 0 1 0 0 0
0 0 0 1 0 0 0 1 1 ∞
Cj 0.75 -20 0.5 -6 0 0 0 Z=0
TAB1 : 0

0.75 1 -32 -4 36 4 0 0 0 0
0 0 4 1.5 -15 -2 1 0 0 0
0 0 0 1 0 0 0 1 1 ∞
Cj 0 4 3.5 -33 -3 0 0 Z=0
TAB2 : 0

0.75 1 0 8 - 84 - 12 0 0 0 0
-20 0 1 - - 0 0
0 0 0 1 0 0 0 1 1 1
Cj 0 0 2 -18 -1 -1 0 Z=0
TAB3 : 0
0.5 0 1 - - 0 0 0 0
-20 - 1 0 0 0 0
0 - 0 0 0 1 1 ∞
Cj - 0 0 3 2 -1 0 Z= 0
TAB4 :
0.5 - 56 1 0 2 14 0 0 0
-6 - 0 1 0 0 0
0 -56 0 0 -2 -14 1 1 0.4
Cj -16 0 0 1 -5 0 Z=0
0
TAB5 :
0 - 28 0 1 7 0 0 0
-6 -4 - 1 0 -1 0 0 0
0 0 1 0 0 0 1 1 ∞
Cj - 44 - 0 0 -12 0 Z=0
0
TAB6 :
0 0 -2 - 1 - 0 0 0
0.75 1 - 24 -1 6 0 -6 0 0 0
0 0 0 1 0 0 0 1 1 1
Cj 0 -2 - 0 - 0 Z=0
0
TAB7 :
0 0 0 1
0.75 1 0 0 1
0.5 0 0 1 0 0 0 1 1
Cj 0 -2 0 - 0 - - Z = 1.25
1.25
Tous les Cj 0 donc c’est le tableau optimal. Donc la solution optimale est :
, , , Avec .
2)
SBR0=(0, 0, 0, 0, 0, 10, 15, 12)

VB=(
VHB=(
{
On remplace de la FO avec les deux expressions précédentes :
TAB0 :
-M 3 -1 4 1 -1 0 1 0 15 15/4
0 1 3 0 -1 0 1 0 0 10 ∞
-M 2 1 1 0 0 0 0 1 12 12
Cj 4 -M 0 0 0 Z= - 27M
TAB1 :
3 3/4 -1/4 1 1/4 -1/4 0 1/4 0 15/4 -15
0 1 3 0 -1 0 1 0 0 10 10/3
-M 5/4 5/4 0 -1/4 1/4 0 -1/4 1 33/4 33/5
Cj 0 0 0 Z=- +45/4
TAB2 :
3 5/6 0 1 1/6 -1/4 1/2 1/4 0 55/12 11/2
4 1/3 1 0 -1/3 0 1/3 0 0 10/3 10
-M 5/6 0 0 1/6 1/4 -5/12 -1/4 1 49/12 49/10
Cj 0 0 0 Z=- +325/12
TAB3 :
3 0 0 1 0 -1/2 11/12 1/2 -1 1/2
4 0 1 0 -2/5 -1/10 1/2 1/10 -2/5 51/30
-2 1 0 0 1/5 3/10 -1/2 -3/10 6/5 49/10 49/3
Cj 0 0 0 0 Z=-
TAB4 :
3 0 1 0 26/3
4 1 0 0 10/3
0 0 0 1 49/3
Cj -25/3 0 0 -5/3
Tous les Cj 0 donc c’est le tableau optimal. Donc la solution optimale est :
, , , Avec .
Exercice 4
Coef VB x1 x2 e1 e2 e3 Valeur
0 e1 0 f=1 0 46
0 e2 -18 0 0 1 k
b= ? x2 c 1 g=0 i=0 4
cj d e=0 h=0 j=0 Z=m= ?
1) Le (PL) admet 3 contraintes, donc on a 3 VB. Puisque la colonne relative à une VB est
composée par un élément égale à 1 et tous les autres éléments sont égaux à 0 donc les
VB ne peuvent être que x2, e1 et e2 car les colonnes de x1 et e3 contiennent des éléments
de 0.
2) Les VB ont des cj = 0 donc . De plus l’élément d’intersection de la
ligne te la colonne d’une VB est égale à 1 donc .
3) Il faut avoir d < 0.
4) Il faut avoir d > 0.
5) Il faut avoir d > 0 et .
L’algorithme du Simplexe identifie un PL non borné si dans un tableau on n’a aucune

variable de base sortante. Autrement dit Si une variable admet un c j > 0 et les
éléments de sa colonne sont tous négatifs ou nul dans un tableau de simplexe alors on
peut conclure que le PL est non borné même si cette variable n’a pas le plus grand c j
> 0.
Une SBR est dite dégénérée si une VB a pour valeur 0. Alors pour que la solution de
base de ce tableau soit dégénérée il faut avoir .

Les TD Algo Line Simplexe PDF

Transféré par

Droits d'auteur :

Formats disponibles

Les TD Algo Line Simplexe PDF

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Les TD Algo Line Simplexe PDF

Transféré par

Droits d'auteur :

Formats disponibles

North American Private University AU: 2014-2015

IIT: International Institute of Section: Génie Télécom 1

Heures 0-3 3-6 6-9 9-12 12-15 15-18 18-21 21-24

Soldat Radio Camouflage Tireur Endurance physique Sous-officier

L’officier doit respecter les conditions suivantes:

• Il faut au moins 1 opérateur radio et au moins 1 spécialiste du camouflage.

Tranche horaire Nombre minimal d’infirmières

Écrire un programme linéaire en vue de déterminer le nombre minimal d’infirmières néces-

Lot Tables Bancs Poubelles coût d’un lot

Sous contraintes (s.c) :

Enseignant : Boukthir HADDAR ~1~ A.U : 2014-2015

De même nous définissons : , , , , , , et

Si on arrive à B on doit en partir :

Si on n’arrive pas à B alors on n’en repart pas : 

Enseignant : Boukthir HADDAR ~2~ A.U : 2014-2015

De même nous définissons , , , .

Sous contraintes (s.c) :

(il faut un et un seul sous-officier).

(Il faut au moins 1 opérateur radio).

(Il faut au moins 1 spécialiste du camouflage).

(Si A fait partie de la patrouille, alors B ne doit pas en faire partie).

(Si A fait partie de la patrouille, alors C ne doit pas en faire partie).

Enseignant : Boukthir HADDAR ~3~ A.U : 2014-2015

= Nombre des infermières dans la période entre 0h et 2h

= Nombre des infermières dans la période entre 22h et 0h

Sous contraintes (s.c) :

Enseignant : Boukthir HADDAR ~4~ A.U : 2014-2015

=1 : machine A =1 : poutres petites

Sous contraintes (s.c) :

Disponibilité de chaque machine

Satisfaction de la demande du marché

Enseignant : Boukthir HADDAR ~5~ A.U : 2014-2015

: Nombre de séances de français

: Nombre de séances d’informatique

Enseignant : Boukthir HADDAR ~6~ A.U : 2014-2015

Variables de décisions: Fonction Objectif:

1. Vérifier que ( 23 , 53 )est une solution réalisable.

MinZ = −x1 + x2 M inZ = −x1 M inZ = −2x1 − x2

programme linéaire ci-dessus

(1) + (2)  d’où si on divise le tous sur 3 on trouve : .

3) D’après la question 2) on a : , or ( est une solution réalisable qui donne

(le maximum possible). Donc ( est l’unique solution optimale.

Contraintes de disponibilité des machines

Enseignant : Boukthir HADDAR ~1~ A.U : 2014-2015

Enseignant : Boukthir HADDAR ~2~ A.U : 2014-2015

Traçage des droites :

On choisit par exemple :

Enseignant : Boukthir HADDAR ~3~ A.U : 2014-2015

Traçage des droites :

On choisit par exemple :

Enseignant : Boukthir HADDAR ~4~ A.U : 2014-2015

Traçage des droites :

On choisit par exemple :

: (1, -2) et (0, 0)

: (0, -1) et (1, -3)

Enseignant : Boukthir HADDAR ~5~ A.U : 2014-2015

Traçage des droites :

On choisit par exemple :

: (1, -0.5) et (0, 0.25)