Programming

Mathématique

Mr. El Kettani Moummou

1
1. General Introduction
Problems of Decision making
the company

Formulation of mathematical models

(Modeling)

Problem solving
Optimization

Interpretations
2
 Minimization
Maximization

The costs
Profit Execution deadlines (of
production)

3
 Charts Algorithmic

Inconvenient: Algorithm of
Valid on Sun 2 Computer science
SIMPLEX
only

Programming Software of
computer science the R.O.

CUTE.
Ms-Project
STORM
 Objectives:
• Effectively ensure the combination of
factors of production, which implies
an optimal use of these factors.
Decision making in a company.

5
 Applications:
Production Management.
Project Management
Inventory management
G. R. H.
Schedule management
Transport problems
• Etc...

6
 Chapter 1:

Modeling and Resolution

graph of problems
optimization

7
 1. Modeling
The act of translating (formulating) the
company problems by
mathematical relations is called 'The'
Modeling.
• Alors les relations mathématiques
obtained only constitutes
"Models" of the issues considered.
• Know an optimal solution of
models often allow for taking
appropriate decisions.
8
 Example no. 1: Problem of
restaurateur
A restaurateur has three types of fruit
from the sea: 30 sea urchins, 24 shrimp, and 18 oysters.
The restaurateur wants to prepare two types
of plates:
Plates at 8 Dhs consisting of 5 sea urchins, 2 shrimp
and 1 oyster.
Plates at 6 Dhs consisting of 3 sea urchins, 3 shrimp
and 3 oysters.
How many plates of each type does he need?
prepare to maximize his income?
9
 Model No. 1:
Actions Amplitudes
Plates at 8 Dhs to prepare x
Plates at 6 Dhs to prepare y

Economic function Constraints

8x + 6y (to maximize) 5x + 3y ≤ 30
2x + 3y ≤ 24
x + 3y ≤ 18
with x,y IN 10
 Model No. 1
So the model nº1 is:
max 8x + 6y
Subject to 5x + 3y ≤ 30
2x + 3y ≤ 24
x + 3y ≤ 18
x,y IN

11
 Example No. 2
A car manufacturer makes three models
of automobiles; each model goes through two workshops.
The first workshop (stamping, assembly) has
of a maximum of 350 hours and the second (painting,
definition) of a maximum of 400 hours.
The production of the first model takes 10 hours
in the first workshop and 14 hours in the second;
the fabrication of the 2nd model requires 12 hours in the
first workshop and 9 hours in the second and that of
The 3rd model requires 13 hours in the first.
workshop and 11 o'clock in the second.

12
The unit margins of the three models
manufactured are respectively 10000,
12000 and 15000 DH.
The builder wants to determine the
number of automobiles of each
modèle qu’il faudrait fabriquer pour
maximize your income.
Provide the mathematical model of this
problem in the form of a program
linear.

13
 Model No. 2:
Actions Amplitudes
Number of cars from 1hemodel x
Number of automobiles of 2thmodel y
Number of automobiles from 3thmodel z

Economic function
Max 10000x + 12000y + 15000z

14
 Constraints:

10x+12y+13z≤350
14x + 9y + 11z ≤ 400
x, y, z ≥ 0
So the sought model is:
Max 10000x + 12000y + 15000z
Subject to 10x + 12y + 13z ≤ 350
14x + 9y + 11z ≤ 400
x, y, z ≥ 0
15
 Example no. 3
A company is engaged in production of
tables and chairs. The production cost of
each table is 30DH and that of each
The chair is 20 DH. The sales market can
absorber une production d’au plus 3 tables et 4
chairs per day. Furthermore, the total number of
the number of tables and chairs sold cannot exceed 5
units per day. Once the assembly is
completed, each table requires 2 hours of
drying and each chair requires 1 hour of
drying to allow the glue to set.
16
The apartment where the drying takes place does not
can only contain one item at a time.
Furthermore, for economic reasons, we...
requires that the apartment be used at
less than 5 hours per day. Packaging
a table requires 2 operations and that
a chair requires 4 operations on a
machine. For economic reasons
for the adjustment of the machine, it is required
that the total number of operations
executed at least 8 per day.
17
The company wishes to determine the number
tables and chairs to be produced per day
to minimize the total cost.
• Formulate this problem in the form of a
linear programming problem.

18
 Model No. 3:
Actions Amplitudes
Number of chairs to produce/day x
Number of tables to produce/day y

Economic function

MinZ=20x+30y

19
Constraints:

x≤4
y≤3
x+y≤5
x + 2y ≥ 5
4x + 2y ≥ 8
x, y ≥ 0

20
 So the linear model sought
est:
MinZ=20x+30y
Subject to x+y≤5

x + 2y ≥ 5
4x + 2y ≥ 8
0≤x≤4
0≤y≤3

21
 3. Graphical resolution
•Feasible solution: is a solution that
satisfies all the constraints of the problem.
Optimal solution: is a feasible solution
qui donne l’optimum.
The feasible domain: is the set of
viable solutions and it can be bounded or not.
Extreme point: It is the intersection of two
any lines that define the domain
achievable.

22
 Graphic resolution
This method is based on the curves of
level of the objective function.
It consists of determining the points
feasible from the set of solutions
(achievable domains)
located on the lower contour line and
superior that lead to the minimum and
at most respectively of the
objective function
23
 Graphical resolution
Steps to follow
1. Check if the objective function is linear
2. Represent the feasible domain 'D'
3. Calculate and graphically represent the gradient of the
objective function ’’, f f
4. Represent the contour line '' f=z=0 ’’
5. The contour line passes through the domain 'D'
6. The gradient indicates the direction of increase of the
objective function ’’ f
The last point of 'D' that touches the curve f' is the
optimal solution sought

24
Graphical resolution of the example
number 1:
The problem of the restorer is:
Max 8x + 6y
Subject to 5x + 3y ≤ 30
2x + 3y ≤ 24
x + 3y ≤ 18
x,y IN

25
2x + 3y = 24

x + 3y = 18

B (3,5)
A

D
C
O
8x+6y=54

5x + 3y = 30
26
 Conclusion:
D is the realizable domain
O, A, B and C are the extreme points
(3,5) is the optimal solution.
So the optimal value is 54:
Z=8x3+6x5=24+30=54

27
 Graphical resolution of the model
number 2:
The model number 2 is:
Max 10000x + 12000y + 15000z
Subject to 10x+12y+13z≤350
14x+9y+11z≤400
x, y, z ≥ 0

28
 Graphic resolution
Observation
As this model involves three
variables (more than two variables), we do not
cannot apply the graphical method
pour résoudre ce problème puisque la
graphical method is only applicable
in the case of two variables.

29
 Graphic resolution of the model
number 3:
The model number 3 is:
MinZ=20x+30y
Subject to x + y ≤ 5

x + 2y ≥ 5
4x+2y≥8
0≤x≤4
0≤y≤3

30
 x=4

3 B C y=3

∆
A

D
E
4
x + 2y = 5

x+y=5
4x + 2y = 8
31
 Conclusion
The minimum is Z=80 reached at A(1,2)

Economic interpretation:
We need to make a chair and two tables
per day to minimize the total cost up to
that it reaches 80DH.

32
 Exercises

From page 16 of the book:

Management of
Operations
33
A problem well stated is a problem half solved...

Charles Franklin Kettering

USA 1876--1958

34
Chapter 2:

Method of
Simplex:
35
 1. Introduction:
The simplex algorithm has been used since
1949(*), to the resolution of numerous models
relative linear to management problems,
transport, assignment...
• Today, thanks to the power of the
modern computers and improvement
the calculation processes used by this
algorithm, we can solve models that
contain thousands of constraints and
tens of thousands of variables.
36
2. Resolution of example number 1:
The problem of the restaurateur is:
MaxZ=8x+6y
Subject to 5x + 3y ≤ 30
2x + 3y ≤ 24
x + 3y ≤ 18
x, y ≥ 0

37
a. Standard form of the problem:
We transform the problem by adding the
variables for each of the constraints that we
call "the deviation variables" in a way
à réécrire les inégalités (≤)sous la forme
of inequalities.
So we transform the problem of
maximization in a problem of
minimization.

38
It is said, then, that a problem is under the
standard form if it is a problem of
minimization whose variables are not
negatives and constraints are
equality.
The standard form of example no. 1:
Min Z=-8x-6y
Subject to 5x + 3y + u = 30
2x + 3y + p = 24
x+3y+h=18
x, y, u, p, h ≥ 0

39
 b. The Simplex tables:
• After putting the problem in the form
Standard, we begin to draw up the
simplex tableau by the initial tableau.
As an example of application, we
consider example number 1 presented in form
standard previously and we draw up
initial simplex tableau:

40
Variables xy up h -zTermes
base de
right
3 10 00 30

p 23 01 00 24

h 13 00 10 18

-Z -8 -6 00 01 0

41
The goal is to seek xety (that is to say
the optimal solution) that minimizes Z(which
give the optimum).
Among the coefficients of the function
economic, we are looking for who corresponds
le coefficient le plus faible.
It is observed that for this initial table, it
corresponds to x; then x is said to be variable
entry to the base.

42
Who is the variable that will exit the database?
So, we divide the constant terms of
right by 5; 2 and 1 respectively.
We find 30/5=6; 24/2=12 and 18/1=18.
The smallest positive value is
30/5=6 and she is in front of you, so where
the output variable of the database.
We have therefore determined what is called the
pivot; here the pivot is 5

43
 Simplex Table
On the 2ndththe
simplex tableau is obtained by
trying to make 1 appear instead of
pivot 5 and cancel all the terms of the
colonne du pivot, ceci par combinaison
linear between each line and the line of
pivot.

44
Variables x h -z Terms
based of
right
x 1 3/5 1/5 00 06

p 0 9/5 - 2/5 10 0 12

1 0 12

-Z 0 -6/5 8/5 0 0 1 48

45
In this 2thtableau, the highest coefficient
the weakness of the economic function is -6/5, it
corresponds to, hence the variable
of entry.
We then divide the right-hand terms by
3/5; 9/5 et 12/5 respectivement,
we find 10; 6.66 and 5;
So the smallest positive number is 5, it
is in front of; where the variable is from
output.

46
 Simplex Table
The pivot is therefore 12/5; then the 3rd
table is obtained by trying to make
appear 1 instead of the pivot 12/5 and
d’annuler tous les termes de la colonne du
pivot, this by linear combination between
each line is the pivot line.

47
Variables x why you p h -Terms
basic of
right
x 10 1/4 0 -1/4 03

p 00 -1/4 1 -3/4 03

y 01 -1/12 0 5/12 05

-Z 00 3/2 0 1/2 1 54

48
We notice that all the coefficients of
the economic function (last line of
the table) are positive or zero; then we say
that the optimum is reached and we stop,
sinon on recommence à déterminer un
nouveau pivot et un nouveau tableau.
So the minimum of Zest -54 and there
optimal solution is x=3; y=5; p=3 and theta
we are nothing.

49
 c. Analysis of the optimal solution:
•u=0 eth=0 it is said that the first and
the 3èmeconstraints are 'saturated' by the
solution found. Inequalities in the sense
large sont devenues des égalités pourx=3
ety=5.
•p=3 means that the 2thconstraint is not
Not "saturated" the inequality remains for x=3
ety=5.

50
 Exercise:
Determine a solution to the problem
next, using the algorithm of
simplex
MaxZ=x1+x2+x3
Subject to x1-x2+2x3<=2

-x1+2x2+x3<=1
x1, x2, x3≥0

51
 Solution:
The standard form of the problem is:
Min Z=-x1-x2-x3
Subject to x1-x2+2x3+x4=2

-x1+2x2+x3+x5=1
x1, x2, x3, x4, x5greater than or equal to 0

52
The initial simplex tableau is:

V
b..x1 x3x4x5-ZT. d.
x 41 -1 2 1 0 02

-121 0 1 01

-Z -1 -1 -1 00 10

53
To determine the pivot column, one
can choose one or the other of the three
columns, for example, x2is the variable
Upon entry, we choose the one that gives the most
small positive value by dividing the
terms of the right by those of the column of
x1,x2etx3this isx2(if there is a tie, we
choose one at random
By dividing the terms on the right by -1 and 2
respectively, we have ½ the smallest positive
between -2 and ½ and it is in front of them5
So x5output variable.
The pivot is therefore 2.
54
 V
b.. x2x3x4x5-ZT. d.

5/2

x2-1/2 1 1/2 0 1/2 0 1/2

-Z -3/2 0 -1/2 0 1/2 1 1/2

We pivot around 1/2

55
 V
b..x1x2x3x4x5-ZT. d.

x11 0 5 2 1 05

x 20 1 3 1 1 03
-Z 00 7 3 2 18

All the coefficients of the last row are

positive or zero
The optimum is reached
The maximum of Z is 8
an optimal solution is (5, 3, 0, 0, 0)
56
 Example:
Let's try to apply the algorithm of
simplex to the following problem:
MinZ=-10 x4
Subject to x1-2x4=8
x2-3x4=6
x3-8x4=24
x1, x2, x3, x4>=0

57
The problem is in its standard form because it is
a minimization problem and the constraints
are equalities.
The initial simplex table will be:
V
b..x1x2x3 -ZT. d.
x 11 00 -2 0 8

X2 0 10 -3 0 6

x 30 0 1 -8 0 24
-Z 0 0 0 -10 1 0

58
•x4is the input variable because it is the one that
the lowest coefficient in the
economic function Z.
But to determine the output variable
and by dividing the terms of the lines by -2,
-3 et -8 respectivement, on obtient des
all negative reports.
Therefore, the problem is not bounded.
inferiorly.

59
 Example:
Solve using the simplex algorithm the
next problem:
MinZ=3x1+x2+x3+ x4
Subject to 2x1+2x2+x3=4

3x1+4x2+x4=6
x1, x2, x3, x4greater than or equal to 0

60
We will bring out the variables of
base and this by replacing x3etx4by
their values given by the constraints
in the equation of Z,
so x3=4-2x1-2x2
etx4=6-3x1-4x2

So Z=x1-x2-3x1-4x2+10
Z = -2x1-5x2+10

61
The problem becomes
MinZ=-2x1-5x2+10
Subject to 2x1+2x2+x3=4

3x1+4x2+x46
x1, x2, x3, x4greater than or equal to 0
And we have (to minimize) -2x1-5x2-Z=-10
So the initial simplex tableau will be:

62
V
b..x1 x3x4-ZT. d.
x32 21 00 4

340 10 6

-Z -2 -5 0 01 -10

63
The input variable is: x2
The output variable is: x4because by dividing
4/2=2 ; 6/4=1,5
The pivot is: 4
So the second tableau of the simplex
est

64
 V
b..x1x2x3x4-ZT. d.
x31/2 01 -1/2 0 1

x23/4 10 1/4 0 3/2

-Z 7/4 0 0 5/4 1 -5/2

So the optimal value is 5/2 and a solution

optimal estx2=3/2;x3=1 etx1, x4are null.
65
 Case where more than one variable can
leave the base
(Degeneration)
Example:
MaxZ=1000 x1+1200 x2
Sujet à 10 x1+5x2≤200
2x1+3x2≤60
x1≤34
x2≤20
x1, x2greater than or equal to 0
66
The standard problem is:
MinZ= -1000 x1- 1200 x2
10 x1+5x2+ x3= 200
Subject to 2x1+3x2+x4= 60

x1+x5= 34
x2+x620
x1, x2, x3, x4, x5, x6greater than or equal to 0
The initial simplex table is:

67
V
b..x1 x3x4x5x6-ZT. d.

x310 51 00 00 200

x 42 30 10 00 60

X5 1 00 01 00 34

010 00 10 20
-Z -1000 -1200 00 0 01 0

68
The input variable is x2(that of the marginal cost
minimal)
• Let's find the output variable:
200/5=40; 60/3=20;34/0=∞(limite)et 20/1=20
two baseX variables4etx6
corresponding to the smallest positive value: we
choose, randomly or based on any other criteria
considered relevant, either of these two
variables as output variable.
Let's agree that6is the output variable.
The pivot is1

69
V
b.. x2x3x4x5x6-T. d.
Z
x310 01 00 -5 0 100

1 0 -3 0 0

X5 1 00 01 00 34

x20 10 00 10 20

-Z -1000 0 00 0 1200 1 24000

70
In this last table we have: a solution
from base null4=0.
We then talk about a base solution
degenerated.
This phenomenon of degeneration
occurs when, in the table
previous, more than one basic variable
corresponding to the smallest limit: in the
table obtained after pivoting, only one
one of them exits the database and the others remain in it
remain and necessarily take the value 0.

71
The input variable is x1
• Let's find the output variable:
100/10=10; 0; 34; 20/0=∞ (a limit)
The base variable that corresponds to the
smallest positive value is x4.
So x4is an output variable.
The pivot is 2.
The third tableau of the simplex is:

72
V
b..x1x2x3x4x5 -ZT. d.

0 01 -5 0100 100

x11 00 0.5 0 -1.5 0 0

X5 0 00 -0.5 1 1.5 0 34

x20 10 00 10 20

-Z 00 0 500 0 -300 1 24000

73
• In the last two tables, the
the terms of lines are identical, but the
equations, although equivalent, differ
and the marginal costs as well.
The next input variable is x6.
Let's look for the output variable:
["100/10=10","0/(-1,5)","34/1,5=22,6","20"]
so the output variable is x3and not
x1car -1.5<0.
The pivot is 10.
74
V
b..x1x2x3x4x5x6-ZT. d.

x 60 0 0,1 -0.5 01 0 10

x 11 0 0.15 -0.25 0 0 0 15

X5 0 0 -0.15 0.25 1 00 19

x 20 1 -0.10 0.50 0 00 10

-Z 00 30 350 00 1 27000

75
The optimum is reached because all the numbers
The last line is positive or zero.
The maximum of Zest 27000 and a
solution estx1=15;x2= 10;x3=0;x4=0;
x5=19 etx6=10.
The degeneration of a linear model has
so the potential to engage the algorithm of
simplex in an endless cycle, good
that this problem could have been avoided in this
example.

76
In fact, the phenomenon of cycling is little
frequent and seems to meet especially
in very large models
degenerates.
To avoid cycling, we proceed with the
manière suivante: A chaque itération du
simplex, among all the variables
susceptible to entering or leaving the database.
we choose the one that has the smallest
index.

77
 The surplus or excess variables
surplus
The simplex algorithm allows
to optimize continuous linear models
where the variables are non-negative and
where the constraints are written under
form of equations.
Many practical problems,
nevertheless, are modeled in such a way that
several constraints are written under
form of inequalities.

78
In order to use the algorithm of
simplex to solve these problems,
we have transformed the models
behavior of constraints of sign "≤"
by adding new variables not
negatives, into 'equivalent' models
except for all the constraints, except those of
non-negativities, of sign '='
These variables have been called variables
gap.
79
Let's now suppose that in a
problem, there are also constraints of
sign “≥”.
So, we transform them into equations of
sign “=” by subtracting anew
non-negative variables that we call
surplus or excess variables.

80
 Exercises
Do the exercises on pages 40, 41, and 42
of the book:
Management of
Operations

81
Graphic vs simplex

82
Graphic vs Simplex

83
Graphic vs Simplex

84
Graphic vs Simplex

85
Graphic vs simplex

86
Algorithm

87