Learn Maths from the best

Chapters

Introduction to Linear Programming
Features of Linear Programming
Parts of Linear Programming
Why we Need Linear Programming?
Steps to Solve a Linear Programming Problem
Example
Solution

Introduction to Linear Programming

It is an optimization method for a linear objective function and a system of linear inequalities or equations. The linear inequalities or equations are known as constraints. The quantity which needs to be maximized or minimized (optimized) is reflected by the objective function. The fundamental objective of the linear programming model is to look for the values of the variables that optimize (maximize or minimize) the objective function.

We know that in linear programming, we subject linear functions to multiple constraints. These constraints can be written in the form of linear inequality or linear equations. This method plays a fundamental role in finding optimal resource utilization. The word "linear" in linear programming depicts the relationship between different variables. It means that the variables have a linear relationship between them. The word "programming" in linear programming shows that the optimal solution is selected from different alternatives.

We assume the following things while solving the linear programming problems:

The constraints are expressed in the quantitative values
There is a linear relationship between the objective function and the constraints
The objective function which is also a linear function needs optimization

The best Maths tutors available

Features of Linear Programming

The linear programming problem has the following five features:

Constraints

These are the limitations set on the main objective function. These limitations must be represented in the mathematical form.

Objective function

This function is expressed as a linear function and it describes the quantity that needs optimization.

Linearity

There is a linear relationship between the variables of the function.

Non-negativity

The value of the variable should be zero or non-negative.

Parts of Linear Programming

The primary parts of a linear programming problem are given below:

Objective function
Decision variables
Data
Constraints

Why we Need Linear Programming?

The applications of linear programming are widespread in many areas. It is especially used in mathematics, telecommunication, logistics, economics, business, and manufacturing fields. The main benefits of using linear programming are given below:

It provides valuable insights to the business problems as it helps in finding the optimal solution for any situation.
In engineering, it resolves design and manufacturing issues and facilitates in achieving optimization of shapes.
In manufacturing, it helps to maximize profits.
In the energy sector, it facilitates optimizing the electrical power system
In the transportation and logistics industries, it helps in achieving time and cost efficiency.

In the next section, we will discuss the steps involved in solving linear programming problems.

Steps to Solve a Linear Programming Problem

We should follow the following steps while solving a linear programming problem graphically.

Step 1 - Identify the decision variables

The first step is to discern the decision variables which control the behavior of the objective function. Objective function is a function that requires optimization.

Step 2 - Write the objective function

The decision variables that you have just selected should be employed to jot down an algebraic expression that shows the quantity we are trying to optimize. In other words, we can say that the objective function is a linear equation that is comprised of decision variables.

Step 3 - Identify Set of Constraints

Constraints are the limitations in the form of equations or inequalities on the decision variables. Remember that all the decision variables are non-negative; i.e. they are either positive or zero.

Step 4 - Choose the method for solving the linear programming problem

Multiple techniques can be used to solve a linear programming problem. These techniques include:

Simplex method
Solving the problem using R
Solving the problem by employing the graphical method
Solving the problem using an open solver

In this article, we will specifically discuss how to solve linear programming problems using a graphical method.

Step 5 - Construct the graph

After you have selected the graphical method for solving the linear programming problem, you should construct the graph and plot the constraints lines.

Step 6 - Identify the feasible region

This region of the graph satisfies all the constraints in the problem. Selecting any point in the feasible region yields a valid solution for the objective function.

Step 7 - Find the optimum point

Any point in the feasible region that gives the maximum or minimum value of the objective function represents the optimal solution.

Now, that you know what are the steps involved in solving a linear programming problem, we will proceed to solve an example using the steps above.

Example

A bakery manufacturers two kinds of cookies, chocolate chip, and caramel. The bakery forecasts the demand for at least 80 caramel and 120 chocolate chip cookies daily. Due to the limited ingredients and employees, the bakery can manufacture at most 120 caramel cookies and 140 chocolate chip cookies daily. To be profitable the bakery must sell at least 240 cookies daily.

Each chocolate chip cookie sold results in a profit of $0.75 and each caramel cookie produces $0.88 profit.

a) How many chocolate chip and caramel cookies should be made daily to maximize the profit?

b) Compute the maximum revenue that can be generated in a day?

Solution

Part a

Follow the following steps to solve the above problem.

Step 1 - Identify the decision variables

Suppose:

Number of caramel cookies sold daily = x

Number of chocolate chip cookies sold daily = y

Step 2 - Write the Objective Function

Since each chocolate chip cookie yields the profit of $0.75 and each caramel cookie produces a profit of $0.88, therefore we will write the objective function as:

$P = 0.88 x + 0.75 y$ , where x and y are non negative

Step 3 - Identify Set of Constraints

It is mentioned in the problem that the demand forecast of caramel cookies is at least 80 and the bakery cannot produce more than 120 caramel cookies. Therefore, we will write this constraint as:

$80 \leq x \leq 120$

It is also mentioned that the expected demand for the chocolate chip cookies is at least 120 and the bakery can produce no more than 140 cookies. Therefore, the second constraint is:

$120 \leq y \leq 140$

To be profitable the company must sell at least 240 cookies daily. Therefore, the third constraint is:

$x + y \geq 240$

Step 4 - Choose the method for solving the linear programming problem

We will find the solution of the above problem graphically.

Step 5 - Construct the graph

$P = 0.88 x + 0.75 y$

is subjected to the following constraints:

$80 \leq x \leq 120$

$120 \leq y \leq 140$

$x + y \geq 240$

Step 6 - Identify the feasible region

The green area of the graph is the feasibility region.

Step 7 - Find the Optimum point

Now, we will test the vertices of the feasibility region to determine the optimal solution. The vertices are:

(120, 120) , (100, 140), (120, 140)

(120, 120) P = 0.88 (120) + 0.75 (120) = $ 195.6

(100, 140) P = 0.88 (100) + 0.75 (140) = $ 193

(120, 140) P = 0.88 (120) + 0.75 (140) = $ 210.6

Hence, the bakery should manufacture 120 caramel cookies and 140 chocolate cookies daily to maximize the profit.

Now, we will proceed to solve the part b of the problem.

Part b

The answer to the part b is given in the previous section. The maximum profit that can be generated in a day is $210.6.

The platform that connects tutors and students

Did you like this article? Rate it!

4.00 (6 rating(s))

Emma

I am passionate about travelling and currently live and work in Paris. I like to spend my time reading, gardening, running, learning languages and exploring new places.

Leave us a comment

Cancel reply

Sandstone

February 2022

Anyone to help me solve this question -A brick manufacturing plants makes two types of blocks. Each Type 1 Block sells for $27, uses$ 10 of raw materials and takes $14 of labor & overhead costs. Each Type 2 Block sells for$ 21, uses $9 of raw materials, and takes$ 10 of overhead costs. Each Type 1 Block needs 2 hours molding and 1 hour drying; each Type 2 Block needs 1 hour molding and 1 hour drying. Raw materials are unlimited, but only 100 hours of molding and 80 hours of drying are available each week. Demand for Type 1 is unlimited; but at most 40 Type 2 can be sold each week.
i. Formulate this as a linear programming problem [5 Marks]
ii. How many of each type should be made to obtain a maximum profit? (Use the simplex method)

Enikanselu Iyanu

March 2022

in 2016, Nigeria economy was claimed to be recession due to crash in the price of crude oil. several calls were made by both and international women’s individuals/groups to invest in agriculture for the purpose of economic diversification. chief Adeoye is a successful oil magnate in Nigeria oil and gas sector. he was seriously affected by the global crash in the price of crude oil, hence, he decided to put a trial to investigate in the agricultural sector of the economy. After much deliberation he remembers the 120 acres of land in the village that was allocated to him as part of his own inheritance from his parents properties, he then decided to practice mixed cropping by sowing three crops, yan, maize and soya beans on the land. because of the naira dollars exchange rate, he wants to use is domiciliary dollars account to invest in the business. The cost of the seed for the crops are $40,$ 30 and $30 per acre respectively.chief adeoye plan to invest a maximum of$ 3400 in the seeds.the crops required 1,2and 1 working days per acre respectively to be planted and because of change in weather conditions,all crops must be planted within 170 days.futhermore,a market feasibility study shows that a profit of $300 per acre can be achieved with maize ,$ 200 per acre with soya beans and $100 per acre with yam.(a) formuate the above as a linear programming problem. (b) determine the number of acres of land the chief cultivate for each of the crop to maximize his profit.

Abidoye Oluwasunmisola

December 2021

This is awesome and simple to digest. It indeed is user friendly 😊🙇🏽‍♀️

gryyyy

October 2021

The company can make a total of 80 celphones per day and it has 240 work hours available per day. It takes 2 work hours to make celphone X and 6 work hours to make celphone Y. The profit on celphone X is $80 and the profit on celphone Y is$ 120.

How many of each should be made to maximize profit?

Shanice

October 2021

Can you kindly help me solve this question. ….A company proposes to invest in two divisible projects which are expected to generate the following cash flows.

Cash flows

Year

Project A

Project B

10,000

60,000

30,000

Additional information

1. The cost of capital applicable to both projects is 12%

2. Project A requires sh. 20,000 and Project B 10,000 initial investment.

3. The funds available are restricted as follows;

Years

Cash available

1,000,000

800,000

4. Funds not utilized one year will not be available in the subsequent years.

Required;

i. Formulate a linear programming model to solve the above problem.

ii. Solve the problem graphically and comment on the proportion of investing on the two projects.

Erko Sufa

July 2021

please help me

A farmer has 500acres of land kept for grazing by some animals.The estimate that one cow requires five acres and one goat requires 4 acres.The farmer has the facilities for 40 cows and 100 goats.if the farmer makes 300 per cow and100 per goat.How many cow and goat should be varse for maximum profit.(linear programming)

Erko Sufa

July 2021

have you got the answer for this problem sir

Steps to Solve a Linear Programming Problem

Introduction to Linear Programming

Features of Linear Programming

Parts of Linear Programming

Why we Need Linear Programming?