Chapters

Introduction
Applications of Linear Programming
Objective Function
Constraints
Feasible Solution
Optimal Solution
Example 1
Example 2

Introduction

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.

The best Maths tutors available

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.

Objective Function

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):

$f(x,y) = ax + by$

Constraints

The objective function is subject to certain constraints, expressed by linear inequalities. These constraints are actually the limitations on the primary decision variables.

	a₁x + b₁y ≤ c₁
	a₂x + b₂y ≤c₂
	... ... ...
	a_nx + b_ny ≤c_n

Each inequality constraint system determines a half-plane.

Feasible Solution

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.

Optimal Solution

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.

Now, that you know what are linear programming models, we will now learn how to solve optimization problems through the following examples.

Example 1

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?

Solution

Part a

We will start to solve the above optimization problem by defining the variables first.

Suppose:

The number of chairs sold daily = x

The number of tables sold daily = y

The equation will be written as:

$P = 15x + 50y$

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:

$100 \leq x \leq 150$

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:

$50 \leq y \leq 70$

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:

$x + y \leq 150$

We will graph the following inequalities in an xy plane:

$x + y \leq 150$

$100 \leq x \leq 150$

$50 \leq y \leq 70$

We will graph these inequalities in an xy plane like this:

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.

Part b

The maximum profit can be computed by putting x = 100 and y = 50 in the following equation,

$P = 15x + 50y$

$P = 15(100) + 50 (50)$

$P = 1500 + 2500 = 4000$

$P = $4000$

Example 2

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?