Linear modelling

Let us remind the bases of modeling within the framework of linear problem. The steps to follow are:

  1. What are the variables? their type can be integer, floating point or binary.
  2. What are the constraints? since we are in linear modeling, the variables are isolated (ie only a coefficient can modify the variables, first order operations such as addition and subtraction relate the variables).
  3. What is the objective function? it can be a minimization or a maximization; since we are in linear modeling, the variables are isolated.
  4. The problem of complexity and resolution method will not be discussed in this chapter.

Example 1

An businessman has three manufactures and two products. Each batch of product earns him an amount of money, and he knows the number of hours for the manufacture of each type of batch in his factories.

decision1

The businessman wants to maximize his profit, so we must find the best possible production.

Let us set decision variables:

  • x1 = the number of batch of product 1
  • x2 = the number of batch of product 2

Let us set the objective function:

  • z = the total profit (in thousands of euros)
  • z = 3 x1 + 5 x2 (from the last raw of the table)
  • max z, we are looking for the maximum value that z

Let us set the constraints:

  • x1 ≤ 4 (second raw of the table)
  • 2 x2 ≤ 12 (third raw of the table)
  • 3 x1 + 2 x_2 ≤ 18 (fourth raw of the table)
  • x1 ≥ 0 and x2 ≥ 0 (the number of batches is positive or null)

Which gives the following mathematical model:

decision2

What can be represented from a graphical point of view (the choice space is in gray):

decision3

Example 2

Now that the businessman knows how to optimize his profit, he tries to minimize his expenses. These are composed to employee wages and working hours. The manufacturer estimates the minimum number of employees (MinEmp) to be assigned during each period of the day. Each employee must work shifts in order to maximize his or her time of attendance, one day has four quarter (Quart), and these quarters require a remuneration. The data set is described in the following table:

decision4

Let us set decision variables:

  • x1= the number of employees on the first quarter
  • x2= the number of employees on the second quarter
  • x3= the number of employees on the third quarter
  • x4= the number of employees on the fourth quarter
  • x5= the number of employees on the fifth quarter

Let us put the objective function:

  • Z = the total cost
  • Z = 170 x+ 160 x+ 175 x3+ 180 x4+ 195 x(from the last raw of the table)
  • min Z, we are looking for the minimum value Z can take

Let’s set the constraints:

  • x≥ 48 (from the second raw of the table)
  • xx79 (from the third raw  of the table)
  • etc.

Which gives the following mathematical model:

decision5