 # Linear Programming – Covering Model using LibreOffice Calc Solver

🕋 Eid Mubarak, Selamat Hari Raya Haji ☪️

I have written about Linear Programming – Allocation model in my previous post Linear Programming and Linear Programming with LibreOffice Calc Solver. This post would talk about Linear Programming – Covering models.

First question would be – what’s the difference between Allocation model and Covering model. There is no difference in the optimization function. The difference exists in the constraints. All our constraints talk about maximum in allocation model. All those constraints had symbol. Covering models talk about minimization, usually cost.

### Example

I’ll use the data set given in https://paginas.fe.up.pt/~mac/ensino/docs/OR/otherDocs/PowellAllocationCoveringBlendingConstraints.pdf

Dahlby Outfitters wishes to introduce packaged trail mix as a new product. The ingredients for the trail mix are seeds, raisins, flakes, and two kinds of nuts. Each ingredient contains certain amounts of vitamins, minerals, protein, and calories.

The marketing department has specified that the product be designed so that a certain minimum nutritional profile is met. The decision problem is to determine the optimal product composition—that is, to minimize the product cost by choosing the amount for each of the ingredients in the mix. The data shown below summarize the parameters of the problem:

 Component Grams per pound Nutritional Requirement Seeds Raisins Flakes Pecans Walnuts Vitamins 10 20 10 30 20 20 Minerals 5 7 4 9 2 10 Protein 1 4 10 2 1 15 Calories 500 450 160 300 500 600 Cost/pound 4 5 3 7 6

Lets  denote the product names as S, R, F, P and W. Our objective function would be like this.

Total Cost = 4S+5R+3F+7P+6W

Rewriting the above statement as –

Zmin = 4S+5R+3F+7P+6W

subject to constraints –

 Vitamin content 10S + 20R + 10F + 30P + 20W greater than or eq 20 Mineral content 5S + 7R + 4F + 9P + 2W greater than or eq 10 Protein content 1S + 4R + 10F + 2P + 1W greater than or eq 15 Calorie content 500S + 450R + 160F + 300P + 500W greater than or eq 600

Rewriting the above constraints as linear equations as given below,

10S + 20R + 10F + 30P + 20W ≥ 20
5S + 7R + 4F + 9P + 2W ≥ 10
1S + 4R + 10F + 2P + 1W ≥ 15
500S + 450R + 160F + 300P + 500W ≥ 600

Prepare the data set. G9 is highlighted in yellow colour. This would be our minimizing figure. The data have given the cost of each product already. So, our aim is to find how much amount of each product shall be produced. This would be the decision variable. We need to find out. The cells of the decision variables are also highlighted in yellow colour. Let’s write the constraints now. Our aim is to find how much vitamin, mineral etc to be added in our product. Those cells are highlighted in yellow colour. Let’s open the Solver now. Following is my selection.

1. Target cell is where we find the minimum cost.
2. As we are talking about minimum, we choose ‘optimize result to’ as ‘Minimum’
3. By changing cells = Decision variable cells
4. Limiting Constraints are highlighted with => operator. Following is the result. The answer I get in Calc is not equal to what I see in the reference PDF. However, let’s take it as the decision at the moment –

We would take 24.6, 10, 15, 600 for vitamins, minerals, protein and calories.

Linear programming suggests us to avoid pecans and walnuts.

0.5 x seeds, 0.3 x Raisins and 1.3 x Flakes are sufficient.

With this, we would be able to provide 24.6 vitamins, 10 minerals, 15 protein and 600 calories.

With this I’m closing the statistics post. I’d be starting the next part of this series soon, which is R programming. # Linear Programming with LibreOffice Calc Solver

Hi,

I wrote about Linear Programming using a car factory example in my previous post Linear Programming. That was a manual graphical method computation. In this post, I’ll solve the same maximization problem using LibreOffice Calc.

Lets prepare the data – What we need to find out? We need to find out how many cars of both types can be produced. Let’s leave one blank cell for each SUV (highlighted in yellow colour). What’s out objective function? Maximum profit obtained using x number of SUV cars and y number of Sedan cars.

Let’s add another blank cell. The formula of this cell would be =SUMPRODUCT(B6:C6,B9:C9)

This is nothing but, number of SUV cars x SUV profit + number of Sedan cars x Sedan profit We have constraints on raw material, machine and man power, right? Let’s add the the first constraint as below.

Number of SUV cars x raw material required by SUV car (2) should be lesser than or equal to maximum raw material available (18 tonnes). This is represented using the following formula.

=SUMPRODUCT(B3:C3,B9:C9) Similarly we are adding another two constraints using the following formulas.

=SUMPRODUCT(B4:C4,B9:C9)

=SUMPRODUCT(B5:C5,B9:C9)

Finally out data set looks like this. Open Tools> Solver Let’s fill the solver window as below.

Target cell = Profit cell G9

We want maximization function, because we need to know the maximum count of cars can be produced.

Optimize results to = Maximum

We want to get the best results by changing the value of the count of cars shall be produced.

By changing cells = number of SUV and Sedan cars = B9 and C9.

1. Constraints cells B12:B14 should be lesser than maximum available resources D12:D14
2. Number of cars should not be negative
3. I tested a third constraint, which is maximum number of cars shall not exceed 10 (You may ignore this).

Finally, my selection is given as below. Ok Siri, get me the results.  This solver suggests me not to produce any Sedan cars. It asks me to produce 2 SUV cars. This is same as that of the results I got in graphical analysis Linear Programming (point c in the below given graph). In addition LibreOffice Calc, suggests me maximum resources can be consumed!

See you in another interesting post. # Linear Programming

We talked about some of the interesting statistical computations in my earlier posts. Now, let’s get into Linear Programming.

Programming here, does not refer to computer programming. It refers to statistical operations.

Linear programming helps in planning to obtain optimum result that meets a specific goal after considering all the possible options. It is widely used to calculate the optimum allocation of scarce resources among competing demands. Formulation of linear programing is the representation of the problem situation in a mathematical form.

### Properties or prerequisites for linear programming model

1. Relationship among the decision variables must be linear.
2. A model must have an objective function
3. Constraints like resource constraints should exist.
4. None of the constraint should be a negative number

### Steps for the formulation of linear programming model

1. Identify the objective of the model
2. Identify the suitable variables and their appropriate unit to measure
3. Identify the required constraints and other parameters
4. Assign right algebraic symbols to the objective function (Z) and the variables (x1, x2 … xn)
5. Form the objective function z = c1x1 + c2x2 + .. .. .. + cnxn
6. Include all the constraints
ai1x1 + ai2x2 + .. .. .. +ainxn ≤ bi
0 ≤ xj
where i = 1 ~ m and j = 1 ~ n

### Simplex Algorithm

This is an algorithm for starting at some extreme feasible point and by using a sequence of exchanges, moving on to other such points until a final solution point is found.

### Example

Lets look at an example. A popular car maker in GST near Chennai has the following resources available per day.

• 18 tonnes of raw materials
• 9 hours of machine hours
• 8 hours of man power

This manufacturing plant of the company gets 5 lakhs and 2 lakh as profit from SUV and Sedan type cars respectively.  How many SUV and Sedan cars should be produced by the company to maximize total profit?

 Resources Requirement per unit Daily Availability SUV Sedan Raw material 2 1 18 tonnes Machine 2 3 9 hours Man Power 4 2 8 hours Profit 5 2 lakhs

Let’s perform the steps one by one.

#### Identify the key variables

Let x1 be the number of SUVs
Let x2 be the number of Sedans

#### Define the objective function

Based on the profit, company gets 3 Lakhs and 1 Lakh as benefit from x1 and x2. So,

Zmax = f(x,y) = 5x1+2x2

#### Include the constraints

Availability of the raw materials, machine hours and man power are our constraints.

Raw material 2 x1+1 x2≤18
machine hours 2 x1+3 x2≤9
Man Power 4 x1+2 x2≤8

Non-negative constraints:

The plant cannot produce -ve cars. So,

x1≥0
x2≥0

Hence our linear programming model for this case is given as:

Max Z = 5x1+2x2

Subject to constraints,

2 x1+1 x2≤18
2 x1+3 x2≤9
4 x1+2 x2≤8
x1≥0
x2≥0

#### Graphical method

Remove the inequalities to form equations

2x1+1x2=18  ————– Constraint 1
2x1+3x2=9  ————– Constraint 2
4x1+2x2=8  ————– Constraint 3
x1=0
x2=0

Substitute x1 = 0 in first equation.

2x1+1x2=18
0x1+1x2=18
x2=18

Now substitute x2 = 0

2x1+1x2=18
2×1+0x2=18
x1=9

So our data points for first constraint is given as below

 x1 0 9 x2 18 0

Similarly compute the data points for constraints 2 and 3.

Data points for constraint 2 is given below.

 x1 0 4.5 x2 3 0

Data points for constraint 2 is given below.

 x1 0 2 x2 4 0

Let’s plot the x-y or scatter graph now. All our constraints are ≤. So we need to find an area in the graph which is lesser than all three constraints. This is highlighted in the below given graph. So we have 4 data points a, b, c and d. Lets find those values from the graph.

 a b c d x1 0 0.8 2 0 x2 3 2.5 0 0

So we have got 4 sets of values, which is to be substituted in the objective function to find the maximization.

Max Z = 5x1+2x2

Substituting the values of data point a – (0, 3).

Max Z = 5(0)+2(3) = 6.

Substituting the values of data point b – (0.8, 2.5).

Max Z = 5(0.8)+2(2.5) = 9.

Substituting the values of data point c – (2, 0).

Max Z = 5(2)+2(0) = 10.

Substituting the values of data point d – (0, 0).

Max Z = 5(0)+2(0) = 0.

So, based on our finding, 2 SUV and 0 Sedan would give us best profit.

You may look at the following tutorial videos –