LINEAR PROGRAMMING PROBLEM (LPP):

INTRODUCTION, SOLUTIONS, EXAMPLES, BASIC TERMINOLOGY

TABLE OF CONTENTS

INTRODUCTION ............................................................................................................... 2

SOLVING ANY LPP .......................................................................................................... 3

EXAMPLES OF LPP (FORMULATION AND THEIR SOLUTIONS) .......................................... 3

BASIC TERMINOLOGY ..................................................................................................... 5

1|Page
INTRODUCTION
The word 'linear' means that the relationships are represented by straight lines, i.e., the
relationships are of the form k = p + qx. In other words, it is used to describe the relationships
among two or more variables, which are directly proportional. The word 'programming' is
concerned with optimal allocation of limited resources.

In fact, every organization faces the problem of allocating limited resources to different activities.
Such type of problem arises when there are alternative ways of performing a number of
activities. For instance, consider a manufacturing firm where it is possible to manufacture a
variety of products. Each of the products has a certain margin of profit per unit. These products
use a common pool of resources whose availability is limited. Now the problem is to carefully
allocate these resources to different types of finished products in such a way so that the total
return will be maximum. In such a situation, the management's decision may be based on past
experience and intuition, but decision so made is subjective rather than objective.

Linear Programming (LP) is a versatile technique for assigning a fixed amount of resources among
competing factors, in such a way that some objective is optimized and other defined conditions
are also satisfied.

In other words, linear programming is a mathematical technique for determining the optimal
allocation of resources and obtaining a particular objective when there are alternate uses of the
resources. The objective can be a cost minimization or inversely profit maximization.

Linear programming has been successfully applied to a variety of problems of management, such
as production, advertising, transportation, refinery operation, investment analysis etc. Over the
years, linear programming has been found useful not only in business and industry but also in
non-profit organizations such as government, hospitals, libraries, education, etc. Actually, linear
programming improves the quality of decisions by amplifying the analytic abilities of a decision
maker. Please note that the result of the mathematical models that we will study cannot
substitute for decision maker's experience and intuition, but they provide the comprehensive
data needed to apply his knowledge effectively.

2|Page
SOLVING ANY LPP
The process of solving any LPP involves the following two steps:

I. Formulation of Linear Programming Problem (LPP):

Various steps of defining a Linear Programming problem include:

1. Identify the decision variables

2. Write the objective function
3. Mention the constraints
4. Explicitly state the non-negativity restriction

For a problem to be a linear programming problem, the decision variables, objective

function and constraints all have to be linear functions.

If all the three conditions are satisfied, it is called a Linear Programming Problem.

II. Solve Linear Programs by Graphical Method or Simplex Method

A linear program can be solved by multiple methods. In this section, we are going to look
at the Graphical method and simplex method for solving a linear program. Graphical
method is used to solve a two-variable linear programming problem i:e If we have only
two decision variables, we will use the graphical method to find the optimal solution.
However, in case the number of decision variables is more than two then simplex method
becomes the potential option

Let’s understand all of the above discussion with the help of few examples as given.

EXAMPLES OF LPP (FORMULATION AND THEIR SOLUTIONS)

Example 1: Consider a chocolate manufacturing company that produces two types of chocolates
namely – A and B. Both the chocolates require Milk and Choco only. To manufacture each unit of
A and B, the following quantities are required:

 Each unit of A requires 2 units of Milk and 3 units of Choco

 Each unit of B requires 4 units of Milk and 2 units of Choco

The company kitchen has a total of 20 units of Milk and 12 units of Choco. On each sale, the
company makes a profit of

 Rs 6 per unit A sold

 Rs 5 per unit B sold.

3|Page
 Now, the company wishes to maximize its profit. In order to get the maximum profit, how many
units of A and how many units of B the company must produce respectively?

Solution: The first thing we will do is to represent the problem in a tabular form for better
understanding which however is an optional step to follow.

Milk Choco Profit Per Unit

A 2 3 6

B 4 2 5

Total 20 12

I. Formulation of Linear Programming Problem (LPP):

Step 1: Identify the decision variables

Let the total number of units of chocolate type A to be produced by the company= X

Let the total number of units of chocolate type B to be produced by the company = Y

Step 2: Write the objective function

Now, the total profit is represented by Z

The total profit the company makes is given by the total number of units of A and B
produced multiplied by their per-unit profit of Rs 6 and Rs 5 respectively.

Profit: Maximize Z = 6X+5Y

which means we have to maximize Z.

So our objective function (given by Z) is, Max Z = 6X + 5Y

Step 3: Writing the constraints

The company will try to produce as many units of A and B to maximize the profit. But the
resources Milk and Choco are available in a limited amount.

Constraint 1: As per the above table, each unit of A and B requires 2 units and 4 units of
Milk respectively. The total amount of Milk available is 20 units. To represent this
mathematically,

2X + 4Y ≤ 20

Constraint 2: Also, each unit of A and B requires 3 units & 2 units of Choco respectively. The
total amount of Choco available is 12 units. To represent this mathematically,

3X + 2Y ≤ 12

4|Page
 Constraint 3 (The non-negativity restriction): Also, the values for units of A and B can only
be positive integers greater than zero.

So we have two more constraints, X ≥ 0 & Y ≥ 0

For the company to make maximum profit, the above inequalities have to be satisfied.

This is called formulating a real-world problem into a mathematical model.

So at the end of I (Step 1, Step 2, and step 3), following will be a more precise mathematical form
of the above LPP

Maximize Z = 6X + 5Y

Subject to:

2X + 4Y ≤ 20
3X + 2Y ≤ 12
X≥0, Y≥0

BASIC TERMINOLOGY
Below are various terms frequently employed in the description of Linear Programming models.

Linear Function: A linear function contains terms each of which is composed of only a single,
continuous variable raised to (and only to) power of 1.

Decision Variables: These are economic or physical quantities whose numerical values indicate
the solution of the linear programming problem. These variables are under the control of the
decision maker and does have an impact on the solution to the problem under consideration. The
relationships among these variables should be linear.

In other words, the decision variables are the variables that will decide an output. They represent
an ultimate solution. To solve any problem, decision variables are identified first. In above
example, the number of units of A and B denoted by X & Y respectively are decision variables.

Objective Function: It is a linear function of the decision variables expressing the objective of the
decision maker.The most typical forms of objective functions are: maximize f(x) or minimize f(x).

It is defined as the objective of making decisions. In the above example, the company wishes to
increase the total profit represented by Z. So,

Maximize Z = 6X + 5Y

in above example represents the objective function.

5|Page
Constraints: These are linear equations arising out of practical limitations. The mathematical
forms of the constraints are:
f(x) ≥ b or f(x) ≤ b or f(x) = b
The constraints are the restrictions or limitations on the decision variables. They usually limit the
value of the decision variables. In the above example, the limit on the availability of resources
Milk and Choco represent the constraints and in above example are given as:

2X + 4Y ≤ 20
3X + 2Y ≤ 12

Feasible Solution: Any non-negative solution which satisfies all the constraints is known as a
feasible solution. The region comprising all feasible solutions is referred to as feasible region.

Optimal Solution: The solution where the objective function is maximized or minimized is known
as optimal solution.

Non-negativity restriction: For all linear programs, the decision variables should always take non-
negative values. This means the values for decision variables should be greater than or equal to 0.
In above example,
X≥0, Y≥0
represent Non-negative restrictions and are also called as Non-negative stipulation constraints.

6|Page