Introduction

Linear programming is a mathematical technique used for optimizing (maximizing/minimizing ) the useful output of a process for a given input.

Terminology used :

Decision Varibles: These are controllable varibles that influence the performance of a system.

Objective Function : this is the function which is to be optimized.

Constraints: These contraints are limitations on our decision variables. These constraints can be linear equalities or inequalities.

Non Negativity Restrictions: For linear programming all decision varibles should always take non negative value which means they should be grater than or equal to zero.

Problem Defining :

To define the problem four steps are involved:

Identify the decision variables
Write the objective function
Define the constraints
Explicitly state non negative restrictions

Solution:

Linear Optimization can be solved in many ways using graphical method, using R, using Open Solver in Microsoft Excel or Simplex method.

In its simplest form linear programming can be solved Graphically if we have two decision varibles . We plot all constraints in X - Y plane . the inersecting region gives us a feasible solution. this region tells us all the values our model can take. To evaluate the optimum solution we evaluate objective function at all vertices of polygon formed.

In R we use Lpsolve package .

Problem

Below there is a diet chart which gives me calories, protien, carbohydrate and fat content for 4 food items. Sara wants a diet with minimum cost. The diet chart is as follows:

data<- data.frame("Nutrition" = c("Calories", "Protien (in grams)", "Carbohydrates ( in grams)", "Fat (in grams)", "Cost(in $)"), "Food1" = c( 400, 3, 2, 2, 0.50), "Food2" = c(200, 2, 2, 4, 0.20), "Food3" = c(150, 0, 4, 1, 0.30), "Food4" = c(500, 0, 4, 5, 0.80))

data

##                   Nutrition Food1 Food2 Food3 Food4
## 1                  Calories 400.0 200.0 150.0 500.0
## 2        Protien (in grams)   3.0   2.0   0.0   0.0
## 3 Carbohydrates ( in grams)   2.0   2.0   4.0   4.0
## 4            Fat (in grams)   2.0   4.0   1.0   5.0
## 5                Cost(in $)   0.5   0.2   0.3   0.8

The chart gives the nutrient content as well as the per-unit cost of each food item. The diet has to be planned in such a way that it should contain at least 500 calories, 6 grams of protien, 10 grams of carbohydrates and 8 grams of fat.

to solve the problem :

Identify Decision Varibles : food items are the decision variables in this example. let :
```
Food1 = a

Food2 = b

Food3 = c

Food4 = d
```
Write the Objective Function: As we want to keep the cost of diet minimum

Z(min) = 0.5a + 0.2b + 0.3c + 0.8d

Define the Constraints:

400a + 200b + 150c + 500d >= 500

3a + 2b + 0c + 0d >= 6

2a + 2b + 4c + 4d >= 10

2a + 4b + 1c + 5d >= 8

Non negative Restrictions: a >= 0 , b >= 0 , c >= 0 , d >= 0

Now as it has more than two decision variables we can’t use graphical method , so we are using R to solve the problem.

#set decision variables
objective.in <- c(0.5, 0.2, 0.3, 0.8)

# constraint matrix

const.mat<- matrix(c(400, 200, 150, 500, 3, 2, 0, 0, 2, 2, 4, 4, 2, 4, 1, 5), nrow = 4, byrow = TRUE)

# defining constraints

const_cal<-  500 
const_prot<- 6  # in grams
const_carb<- 10 # in grams
const_fat<-  8  # in grams

# RHS for constraints
const.rhs<- c(const_cal, const_prot, const_carb, const_fat)

#Direction for constraints
const.dir<- c(">=", ">=", ">=", ">=")

#Finding Optimum Solution
opt<- lp(direction = "min", objective.in , const.mat, const.dir, const.rhs)

summary(opt)

##                  Length Class  Mode     
## direction         1     -none- numeric  
## x.count           1     -none- numeric  
## objective         4     -none- numeric  
## const.count       1     -none- numeric  
## constraints      24     -none- numeric  
## int.count         1     -none- numeric  
## int.vec           1     -none- numeric  
## bin.count         1     -none- numeric  
## binary.vec        1     -none- numeric  
## num.bin.solns     1     -none- numeric  
## objval            1     -none- numeric  
## solution          4     -none- numeric  
## presolve          1     -none- numeric  
## compute.sens      1     -none- numeric  
## sens.coef.from    1     -none- numeric  
## sens.coef.to      1     -none- numeric  
## duals             1     -none- numeric  
## duals.from        1     -none- numeric  
## duals.to          1     -none- numeric  
## scale             1     -none- numeric  
## use.dense         1     -none- numeric  
## dense.col         1     -none- numeric  
## dense.val         1     -none- numeric  
## dense.const.nrow  1     -none- numeric  
## dense.ctr         1     -none- numeric  
## use.rw            1     -none- numeric  
## tmp               1     -none- character
## status            1     -none- numeric

# Objective values of a, b, c, d
opt$solution

## [1] 0 3 1 0

# Value of objective function at optimal point
opt$objval

## [1] 0.9

Conclusion:

As we see for our optimum solution means diet with minimum cost Sara should have 0 units of Food1, 3 units of Food2, 1 unit of Food3 and 0 units of Food4. the cost of diet will be $0.90 and this diet will provide her at least 500 calories, 6 grams of protien, 10 grams of carbohydrates and 8 grams of fat.

Linear Optimization