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

Spreadsheet method (LibreOffice Calc)

Prepare the data set. G9 is highlighted in yellow colour. This would be our minimizing figure.

Linear Programming covering model libreoffice calc solver 01

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.

Linear Programming covering model libreoffice calc solver 02

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.

Linear Programming covering model libreoffice calc solver 03

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.

Linear Programming covering model libreoffice calc solver 04

Following is the result.

Linear Programming covering model libreoffice calc solver 05

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.

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s