Lecture_2_Linear Programming : Introduction and Formulation

2.1 Introduction to Linear Programming
A linear form is meant a mathematical expression of the type a1x1 + a2x2 + …. + anxn, where a1,
a2, …, an are constants and x1, x2 … xn are variables. The term Programming refers to the process
of determining a particular program or plan of action. So Linear Programming (LP) is one of the
most important optimization (maximization / minimization) techniques developed in the field of
Operations Research (OR).
The methods applied for solving a linear programming problem are basically simple problems; a
solution can be obtained by a set of simultaneous equations. However a unique solution for a set
of simultaneous equations in n-variables (x1, x2 … xn), at least one of them is non-zero, can be
obtained if there are exactly n relations. When the number of relations is greater than or less than
n, a unique solution does not exist but a number of trial solutions can be found.
In various practical situations, the problems are seen in which the number of relations is not
equal to the number of the number of variables and many of the relations are in the form of
inequalities (? or ?) to maximize or minimize a linear function of the variables subject to such
conditions. Such problems are known as Linear Programming Problem (LPP).
Definition – The general LPP calls for optimizing (maximizing / minimizing) a linear function
of variables called the ‘Objective function’ subject to a set of linear equations and / or
inequalities called the ‘Constraints’ or ‘Restrictions’.




2.2 General form of LPP
We formulate a mathematical model for general problem of allocating resources to activities. In
particular, this model is to select the values for x1, x2 … xn so as to maximize or minimize
Z = c1x1 + c2x2 +………….+cnxn
subject to restrictions
a11x1 + a12x2 + …..........+a1nxn (? or ?) b1
a21x1 + a22x2 + ………..+a2nxn (? or ?) b2
.
.
.
am1x1 + am2x2 + ……….+amnxn (? or ?) bm
and
x1 ? 0, x2 ? 0,…, xn ? 0
Where
Z = value of overall measure of performance
xj = level of activity (for j = 1, 2, ..., n)
cj = increase in Z that would result from each unit increase in level of activity j
bi = amount of resource i that is available for allocation to activities (for i = 1,2, …, m)
aij = amount of resource i consumed by each unit of activity j