What is Linear Programming?
Linear programming is used to optimize a linear objective function and a system of linear inequalities or equations. The limitations set on the objective function are called as constraints. The objective function represents the quantity which needs to be minimized or maximized. Linear programming's main objective is to optimize the objective function.
The assumptions for a linear programming problem are given below:
- The limitations on the objective function known as constraints are written in the form of quantitative values.
- The objective function must be a linear function.
- The relationship between the objective function and the constraints must be linear.
Linear programming problems can be solved using multiple methods. The most common methods are simplex method, solving the problems using R or open solver, and graphical method. In this article, we will solve the linear programming problems using the graphucal method.
Example 1
A store has requested a manufacturer to produce pants and sports jackets.
For materials, the manufacturer has $750 m ^2$ of cotton textile and $1000 m^2$ of polyester. Every pair of pants (1 unit) needs $1 m^2$ of cotton and $2 m ^2$ of polyester. Every jacket needs $1.5 m ^2$ of cotton and $1 m^2$ of polyester. The price of the pants is fixed at $50 and the jacket, $40. What is the number of pants and jackets that the manufacturer must give to the stores so that these items obtain a maximum sale?
Solution
Step 1 - Identify the Decision Variables
Choose the unknowns.
x = number of pants
y = number of jackets
Step 2 - Write the objective function.
$f(x,y)= 50x + 40y$
Step 3 - Identify the set of Constraints
To write the constraints, use a table:
| pants | jackets | available | |
|---|---|---|---|
| cotton | 1 | 1,5 | 750 |
| polyester | 2 | 1 | 1,000 |
$x + 1.5y leq 750$
$ 2x+3y leq 1500$
$2x + y leq 1000$
As the number of pants and jackets are natural numbers, there are two more constraints:
x ≥ 0
y ≥ 0
Step 4 - Choose the method for solving the problem
There are many methods to solve a linear programming method. In this problem, we will find the solution of the problem graphically.
Step 5 - Construct the graph
Represent the constraints graphically.
As x ≥ 0 and y ≥ 0, work in the first quadrant.
Represent the straight lines from their points of intersection with the axes.
Solve the inequality graphically: $2x +3y leq 1500$, and take a point on the plane, for example (0,0).
$2 cdot 0 + 3 cdot 0 leq 1500$
Since $0 leq 1500$ then the point (0,0) is in the half plane where the inequality is satisfied.
Similarly, solve $2x + y leq 1000$.
$2 cdot 0 + 0 leq 1000$
Step 6 - Identify the feasible region
The area of intersection of the solutions of the inequalities would be the solution to the system of inequalities, which is the set of feasible solutions.
Step 7 - Find the optimum point
Calculate the coordinates of the vertices from the compound of feasible solutions.
The optimal solution, if unique, is in a vertex. These are the solutions to the systems:
$2x + 3y = 1500 ; x = 0 (0, 500)$
$2x + y = 1000; y = 0 (500, 0)$
$2x + 3y =1500$; $2x + y = 1000 (375, 250)$
Now, we will calculate the value of the objective function at each of the vertices to determine which of them has the maximum or minimum values. It must be taken into account the possible non-existence of a solution if the compound is not bounded.
In the objective function, place each of the vertices that were determined in the previous step.
$f(x, y) = 50x + 40y$
$f(0, 500) = 50 cdot 0 + 40cdot 500 = $20000$
$f(500, 0) = 50 cdot 500 + 40 cdot 0 = $25000$
$f(375, 250) = 50 cdot 375 + 40 cdot 250 = $28750$ Maximum
The optimum solution is to make 375 pants and 250 jackets to obtain a benefit of $28,750.
The solution is not always unique, so we can also find other solutions.
Example 2
Maria has an online shop where she sells hand made paintings and cards. She sells the painting for $50 and the card for $20. It takes her 2 hours to complete 1 painting and 45 minutes to make a single card. She also has a day job and makes paintings and cards in her free time. She cannot spend more than 15 hours a week to make paintings and cards. Additionally, she should make not more than 10 paintings and cards per week.
She makes a profit of $25 on painting and $15 on each card. How many paintings and cards should she make each week to maximize her profit.
Solution
Follow these steps to solve the above problem.
Step 1 - Identify the decision variables
x = number of paintings
y = number of cards
Step 2 - Write the objective function
Since she makes $25 profit in each sold painting and $15 on each sold card, therefore the objective function is:
$P = 25x + 15y$
Step 3 - Identify the set of constraints
It takes her 2 hours to complete a painting and 45 minutes to make a card. She cannot spend more than 15 hours a week in making cards and painting.
$2x + 0.75y leq 15$
She should make at most 10 paintings and cards a week.
$x + y leq 10$
We also have two other constraints:
$x geq 0$ and $y geq 0$
Step 4 - Choose the method for solving the problem
We will use the graphical method to solve this problem.
Step 5 - Construct the graph
Step 6 - Identify the feasible region
The green highlighted area is the feasibility region of the graph
Step 7 - Find the optimum point
Use the coordinates of the vertices and substitute them in the objective function to yield the maximum point.
$(7, 0) P = 25(7) + 15(0) = 175$
$(6, 4) P = 25(6) + 15(4) = 210$ Maximum
$ (0,11) P = 25(0) + 15 (11) = 155$
The above calculations show that Maria can make the maximum profit of $210 a week by making 6 paintings and 4 cards.
Did you like this article? Rate it!
Loading...
An agricultural Research institute suggested to a farmer to spread out at least 4800kg of a special phosphate fertilizer and not less than 7200kg of a special nitrogen fertilizer to raise productivity of crops in his fields. There are two sources for obtaining these: Mixture A and B, both of these are available in bags weighting 100 kg each and they cost sh 40 and sh24 respectively. Mixture A contains phosphate and nitrogen equivalent of 20 kg and 80 kg respectively, while mixture B contains these ingredients equivalent of 50 kg each.
Required: Write this as a linear programming problem and determine how many bags of each type the farmer should buy in order to obtain the required fertilizer at a minimum cost
Very good
Please help to do under this question
A company produces two types of TVs, one of which is black and white, the
other colour. The company has the resources to make at most 200 sets a week. Creating a black
and white set includes Birr 2700 and Birr 3600 to create a colored set. The business should
spend no more than Birr 648,000 a week producing TV sets. If it benefits from Birr 525 per set
of black and white and Birr 675 per set of colours.
Construct the linear programing model.
How many sets of black/white and colored sets it should produce in order to get
maximum profit using
Graphical Method and Simplex Method
A company manufacture two types of product A1 and A2. Each product using milling and drilling machine. The process time per unit of A1 on the milling is 10 hours and the drilling is 8 hours, the process time per unit of A2 on the milling is 15 minute and on the drilling is 10 hours, the maximum number of hours available per week on the drilling and milling machine are 80 hours and 60 hours respectively also the profit per selling of A1 and A2 are 25 naira and 35 naira respectively. Formulate a LP model to determine the production volume of each of the product such that the total profit is maximized
so this equestion of linear programming what have a solution
A linear programming problem
Please help to do this qutions,
Ethio Manufacturing, a renowned company in Ethiopia, specializes in
producing two types of products: Product A and Product B, with the primary
objective of maximizing its total profit. Each unit of Product A yields a profit
of 5 Birr, and each unit of Product B yields a profit of 4 Birr.
The company is
constrained by limited resources in two vital departments: Department A, with 60 hours of available production time, where producing one unit of
Product A consumes 3 hours and one unit of Product B consumes 2 hours;
and Department B, with 72 hours of available production time, where
producing one unit of Product A takes 4 hours and one unit of Product B
takes 3 hours. Questions
1. Formulate the Linear Programming Problem (LPP):
2.Graphically analyze the LPP to determine the optimal production quantities
of Product A and Product B that maximize Ethio Manufacturing’s profit. Identify the coordinates of the optimal solution point.
3. Apply the simplex method to find the optimal solution for Ethio
Manufacturing’s LPP. Present the initial tableau, pivot steps, and the final
solution. Explain each step in the simplex method.
4. Determine the dual problem for Ethio Manufacturing’s LPP and present
the dual problem’s objective function and constraints.
5a. Discuss the changes in objective-function coefficients (cj) of the optimal basic feasible solution
5b. Discuss the effect of discrete change in the avaliabilty of resources from
[60, 72 ]T to [70, 50]T
Hi pls hw d u obtain d constraints in for truck type B in exercise 1