Mathematical Formulation of Linear Programming Problems

Mathematical Formulation of Linear
Programming Problems
There are mainly four steps in the mathematical formulation of linear programming problem
as a mathematical model. We will discuss formulation of those problems which involve only
two variables.
 Identify the decision variables and assign symbols x and y to them. These decision
variables are those quantities whose values we wish to determine.
 Identify the set of constraints and express them as linear equations/inequations in

terms of the decision variables. These constraints are the given conditions.
 Identify the objective function and express it as a linear function of decision variables.
It might take the form of maximizing profit or production or minimizing cost.
 Add the non-negativity restrictions on the decision variables, as in the physical

problems, negative values of decision variables have no valid interpretation.
There are many real life situations where an LPP may be formulated. The following examples
will help to explain the mathematical formulation of an LPP.
01. A diet is to contain at least 4000 units of carbohydrates, 500 units of fat and 300 units of
protein. Two foods A and B are available. Food A costs 2 dollars per unit and food B costs 4
dollars per unit. A unit of food A contains 10 units of carbohydrates, 20 units of fat and 15
units of protein. A unit of food B contains 25 units of carbohydrates, 10 units of fat and 20
units of protein. Formulate the problem as an LPP so as to find the minimum cost for a diet
that consists of a mixture of these two foods and also meets the minimum requirements.
Sub Topics
 Suggested answer:
 Suggested answer:
 Mathematical Formulation
Suggested answer:
Back to Top
The above information can be represented as

Let the diet contain x units of A and y units of B.
\ Total cost = 2x + 4y
The LPP formulated for the given diet problem is
Minimize Z = 2x + 4y
subject to the constraints
02. In the production of 2 types of toys, a factory uses 3 machines A, B and C. The time
required to produce the first type of toy is 6 hours, 8 hours and 12 hours in machines A, B
and C respectively. The time required to make the second type of toy is 8 hours, 4 hours and
4 hours in machines A, B and C respectively. The maximum available time (in hours) for the
machines A, B, C are 380, 300 and 404 respectively. The profit on the first type of toy is 5
dollars while that on the second type of toy is 3 dollars. Find the number of toys of each type
that should be produced to get maximum profit.
Suggested answer:
Back to Top
Mathematical Formulation
Back to Top
The data given in the problem can be represented in a table as follows.
Let x = number of toys of type-I to be produced
y = number of toys of the type - II to be produced
\ Total profit = 5x + 3y
The LPP formulated for the given problem is:
Maximise Z = 5x + 3y subject to the constraints
Linear Programming
Operations management often presents complex problems that can be modeled by linear
functions. The mathematical technique of linear programming is instrumental in solving a
wide range of operations management problems.
Linear Program Structure
Linear programming models consist of an objective function and the constraints on that
function. A linear programming model takes the following form:
Objective function:
Z = a1X1 + a2X2 + a3X3 + . . . + anXn
Constraints:
b11X1 + b12X2 + b13X3 + . . . + b1nXn < c1
b21X1 + b22X2 + b23X3 + . . . + b2nXn < c2

.
.
.
bm1X1 + bm2X2 + bm3X3 + . . . + bmnXn < cm
In this system of linear equations, Z is the objective function value that is being optimized, Xi
are the decision variables whose optimal values are to be found, and ai, bij, and ci are
constants derived from the specifics of the problem.
Linear Programming Assumptions
Linear programming requires linearity in the equations as shown in the above structure. In a
linear equation, each decision variable is multiplied by a constant coefficient with no
multiplying between decision variables and no nonlinear functions such as logarithms.
Linearity requires the following assumptions:
 Proportionality - a change in a variable results in a proportionate change in that

variable's contribution to the value of the function.
 Additivity - the function value is the sum of the contributions of each term.
 Divisibility - the decision variables can be divided into non-integer values, taking on
fractional values. Integer programming techniques can be used if the divisibility
assumption does not hold.
In addition to these linearity assumptions, linear programming assumes certainty; that is, that
the coefficients are known and constant.
Problem Formulation
With computers able to solve linear programming problems with ease, the challenge is in
problem formulation - translating the problem statement into a system of linear equations to
be solved by computer. The information required to write the objective function is derived
from the problem statement. The problem is formulated from the problem statement as
follows:
1. Identify the objective of the problem; that is, which quantity is to be optimized. For
example, one may seek to maximize profit.
2. Identify the decision variables and the constraints on them. For example, production
quantities and production limits may serve as decision variables and constraints.
3. Write the objective function and constraints in terms of the decision variables, using
information from the problem statement to determine the proper coefficient for each
term. Discard any unnecessary information.
4. Add any implicit constraints, such as non-negative restrictions.
5. Arrange the system of equations in a consistent form suitable for solving by computer.
For example, place all variables on the left side of their equations and list them in the
order of their subscripts.
The following guidelines help to reduce the risk of errors in problem formulation:
 Be sure to consider any initial conditions.
 Make sure that each variable in the objective function appears at least once in the
constraints.
 Consider constraints that might not be specified explicitly. For example, if there are
physical quantities that must be non-negative, then these constraints must be included
in the formulation.
The Effect of Constraints
Constraints exist because certain limitations restrict the range of a variable's possible values.
A constraint is considered to be binding if changing it also changes the optimal solution. Less
severe constraints that do not affect the optimal solution are non-binding.
Tightening a binding constraint can only worsen the objective function value, and loosening a
binding constraint can only improve the objective function value. As such, once an optimal
solution is found, managers can seek to improve that solution by finding ways to relax
binding constraints.
Shadow Price
The shadow price for a constraint is the amount that the objective function value changes per
unit change in the constraint. Since constraints often are determined by resources, a
comparison of the shadow prices of each constraint provides valuable insight into the most
effective place to apply additional resources in order to achieve the best improvement in the
objective function value.
The reported shadow price is valid up to the allowable increase or allowable decrease in the
constraint.
Applications of Linear Programming
Linear programming is used to solve problems in many aspects of business administration

including:
 product mix planning

 distribution networks
 truck routing
 staff scheduling
 financial portfolios
 corporate restructuring

Mathematical Formulation of Linear Programming Problems

Uploaded by

Copyright:

Available Formats

Mathematical Formulation of Linear Programming Problems

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Mathematical Formulation of Linear Programming Problems

Uploaded by

Copyright:

Available Formats

Mathematical Formulation of Linear

 Identify the set of constraints and express them as linear equations/inequations in

 Add the non-negativity restrictions on the decision variables, as in the physical

The above information can be represented as

The LPP formulated for the given diet problem is

subject to the constraints

The data given in the problem can be represented in a table as follows.

Let x = number of toys of type-I to be produced

y = number of toys of the type - II to be produced

Maximise Z = 5x + 3y subject to the constraints

Linear Program Structure

Z = a1X1 + a2X2 + a3X3 + . . . + anXn

b11X1 + b12X2 + b13X3 + . . . + b1nXn < c1

b21X1 + b22X2 + b23X3 + . . . + b2nXn < c2

Linear Programming Assumptions

 Proportionality - a change in a variable results in a proportionate change in that

4. Add any implicit constraints, such as non-negative restrictions.

 Be sure to consider any initial conditions.

The Effect of Constraints

Applications of Linear Programming

Linear programming is used to solve problems in many aspects of business administration

 product mix planning

You might also like