August 25, 2020
Linear programming is a technique to obtain the best result in the mathematical model. The essentials of the mathematical model are depicted by the linear relationships. In other words, it is a response to situations that require the maximization or minimization of certain functions which are subject to limitations. These limitations are called constraints.
Applications of Linear Programming
The applications of linear programming for optimization in certain fields are widespread. In manufacturing industry, it can be utilized to determine how to allocate labor and resources to maximize the profits, and minimize the cost of operations. It can also be used to determine which products should be sold in which specific quantity to maximize the earnings. In logistics, it tells us how to allocate the resources so that we can achieve more in less time. In operations research, we can express practical problems as linear programming problems. Linear programming was widely used in preliminary development of microeconomics.
Today, it is widely used in management science as the companies utilize it for managing the company's operations such as planning , production, technology, and transportation. The primary goal of the businesses are to maximize the profits, and minimize the costs. Hence, certain issues can be expressed as linear programming problems to reach a viable conclusion.
We know that the linear programming optimizes a system of linear constraints and a linear objective function. You may be wondering what is a linear objective function. Well, this function elucidate the quantity that needs optimization. The main objective of the linear programming is to fetch the values of variables that minimize or maximize the objective function. Hence, we can say that linear programming optimizes (maximize or minimize) an objective function (a linear function of several variables):
The objective function is subject to certain constraints, expressed by linear inequalities. These constraints are actually the limitations on the primary decision variables.
|a1x + b1y ≤ c1|
|a2x + b2y ≤c2|
|... ... ...|
|anx + bny ≤cn|
Each inequality constraint system determines a half-plane.
The feasibility region of the linear programming problem shows set of all feasible solutions. A feasible solution of the linear programming problem satisfies every constraint of the problem.
It is also included in the feasible region, however it represents the maximum objective value of the function for the problem which requires maximization and smallest objective value of the function that requires minimization.
There are many methods to solve linear programming problems. These methods include a simplex method, graphing method, northwest corner method, and least cost method. In this article, we will see how to solve these problems using the graphing method. You must know how to graph a system of linear inequalities and highlight their overlapping region to determine the solutions.
A furniture company produces office chairs and tables. The company projects the demand of at least 100 chairs and 50 tables daily. The company can produce no more than 120 chairs and 70 tables daily. The company must ship at most 150 units of chairs and tables daily to fulfill the shipping contract.
Each sold table results in the profit of $50 and each chair produces $15 profit.
a) How many units of chairs and tables should be made daily to maximize the profit?
b) Compute the maximum profit the company can earn in a day?
We will start to solve the above optimization problem by defining the variables first.
The number of chairs sold daily = x
The number of tables sold daily = y
The equation will be written as:
Now, the next step will be to define the constraints.
It is given in the problem that there is a projected demand for at least 100 chairs daily and the company cannot produce more than 150 chairs. Hence, we will write this constraint as an inequality like this:
The problem says that there is a projected demand for at least 50 tables daily and the company cannot produce more than 70 tables. Hence, we will write this constraint as an inequality like this:
To satisfy the shipping contract, the company must ship at most 15o units of both chairs and tables daily. We will write this constraint as:
We will graph the following inequalities in an xy plane:
We will graph these inequalities in an xy plane like this:
Example 1- Graph
You can see that at point (100,50), all the three lines of the graph are intersecting each other. There only one feasible solution which is also the optimal solution of the problem. The point (100,50) satisfies all the constraints of the problem. Hence, to optimize the profits, the company must make 100 chairs and 50 table daily.
The maximum profit can be computed by putting x = 100 and y = 50 in the following equation,
An airline must sell at least 25 business class and 90 economy class tickets to earn profit. It makes a profit of $320 by selling each business class ticket and a profit of $400 by selling an economy class ticket. No more than 180 passengers can board the plane at a time.
a) How many of economy and business class tickets should be sold by the airline to maximize the profit?
b) How much maximum profit the airline can earn?
First of all, we will define the variables.
x = number of business class tickets sold
y = number of economy class tickets sold
It is given that the airline earns a total profit of $320 for each business class ticket and a profit of $400 for each economy class ticket. This information can be written in the form of following equation:
The airline must sell at least 25 business class and 90 economy class tickets to be profitable:
Not more than 180 passengers can board the plane at a time. This information is represented by the following inequality:
We will graph the following inequalities to determine the feasibility region of this problem:
Example 2 - Graph
The highlighted green area of the graph is the feasibility region. We will see that how many of business and economy class tickets can be sold to maximize the profit, therefore we can use the highest point of the graph in this regard. This is known as optimal solution of the problem.
Example 2 - Optimal point
Hence, for optimizing the profits, the airline must sell 25 business class and 155 economy class tickets.
Now, we will put these values in the equation to get the maximum profit that can be earned by the airline:
P = 320 (25) + 400 (155)
P = 8000 + 62000 = $70000