University of Science and Technology Houari Boumediene
Faculty of Mechanical Engineering & Process Engineering
Department of Mechanical Construction & Production
TP : Optimization
Master 1 FMP + CM
Pr. F. BOUMEDIENE
Mr .WALID LAROUI
Mr . SAMIR HARITI
Emails:
[email protected]
[email protected]
[email protected]
1
TP°N 2 : Linear programming
Introduction
La programmation linéaire est une méthode d'optimisation mathématique visant à
atteindre le résultat optimal dans un modèle donné, tout en respectant des contraintes
spécifiques. Cette approche cherche à maximiser ou minimiser une fonction objectif
linéairement définie.
Linprog
Linprog est une fonction MATLAB utilisée pour résoudre des problèmes de programmation linéaire.
Son rôle est de trouver une solution optimale qui minimise ou maximise une fonction linéaire tout en
respectant des contraintes linéaires.
La forme générale d'un problème de programmation
linéaire peut être exprimée comme suit :
Vecteur de coefficients de la fonction objective à
minimiser
La matrice de coefficients des contraintes d’inégalité
Le vecteur des contraintes d’inégalité
La matrice des contraintes d’égalité
Le vecteur des contraintes d’égalité
La borne supérieure de x
La borne inférieure de x
Example: Find the solution of the following linear programming problem, using the simplex
method (linprog function of Matlab):
Min f = −x1 − 2x2 − x3
Subject to 2x1 + x2 − x3 ≤ 2
2x1 − x2 + 5x3 ≤ 6
4x1 + x2 + x3 ≤ 6
xi ≥ 0; i = 1, 2, 3
clc
clear all
C=[-1;-2;-1]; % Linear objective function vector f
A=[2 1 -1; % Matrix for linear inequality constraints
2 -1 5;
4 1 1];
b=[2;6;6]; % Vector for linear inequality constraints
lb=zeros(3,1); % lb Vector of lower bounds
Aeq=[]; % Matrix for linear equality constraints
beq=[]; % beq Vector for linear equality constraints
[x,fval] = linprog(C,A,b,Aeq,beq,lb)
Applications: Solve graphically, and using the “linprog” function, the following linear programming problems:
Min z = 3x1 + 4x2
Subject to x1 + 2x2 ≥ 8
3x1 + 3x2 ≥ 15
and x1, x2 ≥ 0
Max z = 2x1 + 3x2
Subject to x1 + 3x2 ≤ 6
2x1 + x2 ≤ 4
and x1, x2 ≥ 0
x =[ 1.2000 ; 1.6000]
fval = 7.2000 (maximum)
Example A manufacturing firm produces two machine parts using lathes, milling
machines, and grinding machines. The different machining times required for each
part, the machining times available on different machines, and the profit on each
machine part are given in the following table.
Determine the number of parts I and II to be manufactured per week to maximize
the profit.
11
SOLUTION :
X: number of machine parts I manufactured per week
y: number of machine parts II manufactured per week
The constraints due to the maximum time limitations on the various machines are given by
10x + 5y ≤ 2500
4x + 10y ≤ 2000
x + 1.5y ≤ 450
Since the variables x and y cannot take negative values, we have
x≥0
The total profit is given by f (x, y) = 50x + 100y y≥0
Max f (x, y) = 50x + 100y
Subject to 10x + 5y ≤ 2500
4x + 10y ≤ 2000
x + 1.5y ≤ 450 12
The optimum solution
corresponds to a value of
x∗ = 187.5, y∗ = 125.0
and a profit of $21,875.00.
QUADRATIC PROGRAMMING
PROBLEMS
the quadratic part of the
objective function
D a symmetric
positive-definite
matrix
Resolution using Matlab : Find the solution of the following quadratic programming
problem using MATLAB:
Expressing a quadratic form with a matrix
19
20
Examples:
22
