Faculté des Sciences de Tunis Année universitaire : 2023/2024

Dép. des Sciences de l'Informatique Section : IGL 3 & ICE 3

Programmation Linéaire
Feuille d'exercices N° 1
Programmes Linéaires : Définitions, Notations

EXERCICE N° 1:

Soit le programme linéaire :

X1 + 2X2 - X3 = 1
2X1 - X2 - 5X3 ≤ 2 X 1, X 2 ≥ 0
X1 + 3X2 - 5X3 ≥ 1
X1 + 2X2 + 3X3 = Z (Max)

a) Mettre ce programme sous forme canonique, sous forme standard.

b) Le problème étant mis sous la forme standard on a :
m = 3, n = 6.
Ecrire A2, A3, A4
Posant I= {1, 3}, J = {2, 4, 5}.
Ecrire bI, CJ, AI, AJ, AIJ.

EXERCICE N° 2:

Un industriel veut fabriquer un alliage dont la composition est 30% de cuivre, 30% de Zinc et 40% de Fer.
Il trouve disponible sur le marché 9 sortes d'alliages dont les compositions et les prix sont donnés par le
tableau suivant :

Alliage 1 2 3 4 5 6 7 8 9
Cuivre 10 10 40 60 30 30 30 50 20
Zinc 10 30 50 30 30 40 20 40 30
Fer 80 60 10 10 40 30 50 10 50
Coût 4 5 6 6 8 8 7 6 7

Sachant que le coût de l'opération du mélange est indépendant des alliages utilisés, l'industriel se demande quels
alliages il doit acheter et dans quelles proportions pour minimiser son coût de production ? Formuler ce
problème comme un programme linéaire.

EXERCICE N° 3

Une ferme comporte deux parcelles A et B de 20 et 40 hectares respectivement. Six sortes de céréales peuvent
être cultivées sur ces parcelles I, II, III, IV, V, VI. Le profit par quintal de chaque céréale est donné ci-dessous.

Céréales I II III IV V VI
Profit / quintal 24 31 14 18 61 47

Pour cultiver un quintal de chaque céréale, on a besoin des surfaces (en hectares) et des quantités d'eau (en m3)
suivantes :
 Céréales I II III IV V VI
Parcelle A 0.01 0.015 0.01 0.008 0.025 0.02
Parcelle B 0.01 0.017 0.012 0.01 0.03 0.017
Eau 60 80 50 70 107 90

Le volume total d'eau disponible est de 400.000m3. Noter que pour faire pousser, par exemple, un quintal de
céréale II, on a besoin de 0,015 hectares de parcelle A ou de 0,017 hectares de parcelle B. On cherche à rendre
maximum le profit total tout en respectant les diverses contraintes. Formuler ce problème comme un
programme linéaire (on définira avec soin les variables du problème et on donnera l'interprétation physique des
contraintes).

EXERCICE N°4:

Deux types de pétroles légers PL1 et PL2 sont produits dans une raffinerie en quantités respectives de 40 et 70
tonnes par jour. PL1 a un taux d'octane de 104 et PL2 un taux d'octane de 94. Ces pétroles légers peuvent être
mélangés dans n'importe quelles proportions, le taux d'octane du mélange obtenu varie linéairement avec les
taux d'octanes des parties constituant le mélange, c'est à dire que le produit obtenu à partir de 2 tonnes de PL1 et
3 tonnes de PL2, par exemple, pèsera 5 tonnes et aura un taux d'octane de : (2*104 + 3*94) / 5 = 98.
De tels mélanges peuvent être vendus sur le marché sous le nom de Kérosène si le taux d'octane est supérieur ou
égal à 102 et sous le nom de Super si le taux d'octane est supérieur ou égal à 96 (les demandes de Kérosène et
de Super sont illimitées). La vente d'une tonne de Kérosène procure un profit de 16D. Celle du Super donne un
profit de 10D.
Le problème consiste à déterminer quelles quantités de Kérosène et de Super à produire à partir de PL1 et PL2
pour maximiser le profit tout en satisfaisant aux contraintes du problème.

1. Identifier les variables du problème.

2. Montrer que les contraintes sur les taux d'octane sont linéaires.
3. Formuler le problème comme un programme linéaire.

EXERCICE N°5:

Un constructeur de postes de télévision possède 4 modèles à son catalogue : le portatif noir et blanc (T1), le
standard noir et blanc (T2), le standard couleur (T3) et le couleur de luxe (T4).
L'entreprise comporte deux ateliers : Montage et Tests. Les durées nécessaires pour le montage et le test des
différents modèles sont données dans le tableau suivant (en heures) :

Modèle T1 T2 T3 T4
Montage 8 10 12 15
Test 2 2 4 5

D'autre part, la force de travail de l'atelier de montage correspond à 6000 heures par mois, celle de l'atelier de
tests à 1500 heures par mois et les profits relatifs à la production des postes sont de 40D, 60D, 80D et 100D
respectivement pour T1, T2, T3 et T4. Enfin, l'entreprise dispose chaque mois de 450 transformateurs et de 300
tubes cathodiques couleurs. On a besoin d'un transformateur dans chaque poste (noir et blanc ou couleur). La
quantité de tubes cathodiques noir et blanc disponible n'est pas limitée.
Formuler le problème de maximisation du profit de cette firme sous la forme d'un programme linéaire (P). On
précisera très soigneusement quelles sont les variables et les contraintes de (P).
EXERCICE N°6:

Une petite usine de confection fabrique quatre types de vêtements : tee short(I), chemises(II), pantalons(III) et
vestes(IV). Cette entreprise comporte deux ateliers : Coupe et Couture. Les durées nécessaires pour la coupe et
la couture de ces vêtements sont donnés par le tableau suivant (en heures) :

Vêtement I II III IV
Coupe 1 3 5,5 5
Couture 4 6 7 10

La capacité de l'atelier de coupe est de 2000 heures de travail, celle de l'atelier de couture est de 3000 heures.
D'autre part, les vêtements I, II, III, IV ramènent un profit de 1,200 D ; 2D ; 3D et 4D respectivement.
Formuler ce problème comme un programme linéaire (P).

EXERCICE N°7 : (Partie d'Examen Sess. Juillet 93)

On désire déterminer la composition, à coût minimal, d'un aliment pour bétail qui est obtenu en mélangeant au
plus trois produits bruts : orge, arachide, sésame. L'aliment ainsi conditionné devra comporter au moins 22% de
protéine et 3,6% de graisses, pour se conformer aux exigences de la clientèle. On a indiqué ci-dessous les
pourcentages de protéines et de graisses contenues, respectivement, dans l'orge, les arachides et le sésame, ainsi
que le coût par tonne de chacun des produits bruts :

Produit Brut 1.Orge 2.Arachides 3.Sésame % Requis

% de Protéine 12 52 42 22
% de Graisse 2 2 10 3,6
Coût par tonne 25 41 37

On vous demande d'écrire le programme linéaire relatif à ce problème.

EXERCICE N°8 :

Montrer que le problème :

AX = b αj ≤ Xj ≤ β j j = 1,2, ... , n
CX = Z(Max)

est un programme linéaire. L'écrire sous forme standard.

EXERCICE N°9 :

Montrer que le problème :

AX + Uv = b X≥ 0
CX - ∑ |v| = Z(Max)

peut s'écrire sous la forme d'un programme linéaire. (U est la matrice unité mxm)

EXERCICE N°10 :

On considère les deux programmes linéaires :

AX ≤ b X ≥0 AX ≤ b Xj ≥ 0 j=2, 3, ... n
(P) (P')
CX = Z(Max) CX = Z(Max)

Montrer que si X est solution optimale de (P') avec X1 ≥ 0 alors X est solution optimale de (P).