Linear Programming
1 Introduction:
Linear programming is a mathematical technique of finding the optimum solution( i.e. maximum profit, maximum production, maximum contribution, or minimum cost of production) to a linear desired objective using limited resources and satisfying certain given conditions or restrictions. The main objective of linear programming is to achieve maximum profit by utilizing the scarce resources or to make the minimum cost of any production process by utilizing the scarce resources.
2 Basis terms:
Some basic terms, which are essential to be familiar with the linear programming problems, are
a. Linearity: In linear programming problems, variables must be linearly related in each equation.
b. Decision variables: Decision variables are those non-negative independent variables that are to be determined in the solution of the linear programming. Decision variables are denoted by X1, X2, ………Xn. which are to be evaluated as per the nature of the objective functions and availability of limited resources.
c. Objective function: The objective function is a linear equation involving the decision variables which is either maximized or minimized (optimized) subjected to a given situation. It is usually expressed as
Z = C1X1 + C2X2 +………+ C n Xn
Where C1, C2 ………..Cn is the coefficients ( i.e. profit per unit of decision variables) X1, X2,………Xn.
Note
i) If Z is defined as production cost. It is minimized i.e.
Minimized Z = C1X1 + C2X2 (involving two decision variables)
ii) If Z is defined as profit. It is maximized i.e.
Maximized Z = C1X1 + C2X2 (involving two decision variables)
d. Constraints (limitations): constraints are the restriction imposed on the available resources. In linear programming problems, these constraints are always expressed as linear inequalities in terms of decision variables. All constraints of the linear programming problems should be satisfied while obtaining the solution i.e. optimum solution.
In linear programming problems, constraints are in the following forms
a11X1 + a12X2 ( =) b
e. Non-negative criteria: All the decision variables are assumed to be non-negative i.e.
x1 0, x2 0,……………
f. Feasible solutions: Feasible solution are all those possible solutions, which satisfies the given constraints in the linear programming problems (LP problem)
g. Optimum solution: The optimum solution is the best feasible solution. It means there could be several feasible solutions. Among these, a solution that maximizes or minimizes the objective function is called an optimum feasible solution.
h. Infeasibility: Infeasibility means there is no solution, which satisfies all constraints.
i. Unboundedness: Simply unbound ness means there is no bounded feasible area. In such a case, objective functions have infinitely large no. of the solution, which satisfies all given restrictions (constraints). In real life linear programming problem, Unboundedness occurs due to the wrong formulation of the problem.
j. Redundancy: A constraint that does not affect the feasible solution (feasible area) is called redundant constraints i.e. if inclusion and exclusion of any constraints do not affect the optimal solution then such type of constraints is called redundant.
k. Degeneracy: If the value of any basic variable is zero then the solution is said to be degenerate.
3 General mathematical form of linear programming problems
Before the formulation of the LP problems, read the problem description thoroughly to get a feel for what is involved in the problem i.e. at first identify the objective of the problem that is either maximized or minimized.
In general, suppose there are ‘n’ activities (variables or unknowns) represented by the decision variables X1,X2………, Xn and in resources b1,b2………, bm. then the general mathematical form of LP problem is
(Maximize or Minimize) Z = C1X1 + C2X2 +………+ C n Xn
Subject to constraints
a11X1 + a12X2+……….+ a1nXn ( =)b1
a21X1 + a22X2+……….+ a2nXn ( =)b2
………………………………………………
………………………………………………
am1X1 + am2X2+……….+ amnXn ( =)bm
Non negative constraints
X1, X2,………Xn. 0
At first, the given information in the linear programming problems is presented in the following form as far as possible. Then formulate the LP problem according to the nature of the problems as shown above.
| Resources | Resources uses per unit of activities | Amount of resources available
|
| X1 X2 Xn | ||
| 1
2 . . m |
a11 a12…………… … a1n
a21 a22………………..a2n …………………………… …………………………… am1 am2……. ………….amn
|
b1
b2 . . bm
|
| Contribution to Z per unit activities | C1 C2………………Cn |
The general guidelines for the use of the different types of sings = in formulating the constraints equations are presented in the following table
| Use ‘’ in the constraints equation if the constraints in LPP is relating to words | Use ‘’ in the constraints equation if the constraints in LPP is relating to words | Use ‘=’ in the constraints equation if the constraints in LPP is relating to words |
| i) maximum available
ii) at the most iii) not more than iv) not exceeding v) restricted to vi) up to vii) unwilling to viii) capacity to ix) limited to x) available |
i) Minimum required.
ii) At least. iii) Not less than. iv) Willing to at least. v) Minimum demand. vi) Exceeded by |
i) Must be.
ii) Exactly. iii) Standard size. iv) Net weight content. v) Neither less nor more. |
Note:
- Generally, in maximization problems, constraints sing is less or equal ( ) to type
- Generally, in minimization problems, constraints sing is greater than or equal () to type
Example of LP problem involving two decision variables
| (objective function)
Maximize Z = C1X1 + C2X2 Subject to constraints a11X1 + a12X2 b1 a21X1 + a22X2 b2 where x1 0 , x2 0
|
(objective function)
Minimize Z = C1X1 + C2X2 Subject to constraints a11X1 + a12X2 b1 a21X1 + a22X2 b2 where x1 0 , x2 0
|
You may also like: Method of Construction of Index Number