Mathematics · Ch 12 — Linear Programming
Introduction
Introduction
12.1 Introduction
From Equations to Optimisation
In earlier classes you solved systems of linear equations, and in Class XI you studied linear inequalities and systems of linear inequalities in two variables, solving them graphically. Many real situations involve exactly this kind of system of inequalities or equations. In this chapter we apply those tools to real-life problems of the type described below.
A Concrete Example
A furniture dealer deals in only two items — tables and chairs. He has ₹50,000 to invest and storage space for at most 60 pieces. A table costs ₹2,500 and a chair costs ₹500. He estimates a profit of ₹250 from the sale of one table and ₹75 from the sale of one chair. He wants to know how many tables and chairs he should buy from the available money so as to maximise his total profit, assuming that he can sell all the items he buys.
The dealer can invest his money in tables, in chairs, or in some combination of the two, and different choices earn him different profits. He needs a way to decide which combination is best.
What Is an Optimisation Problem?
Problems of this type — where we must choose the best strategy from many possibilities so as to maximise (or minimise) some outcome such as profit, cost, or use of resources — form a general class of problems called optimisation problems. An optimisation problem may involve finding a maximum profit, a minimum cost, or a minimum use of resources, among other goals.
"Optimisation" simply means finding the best (optimum) outcome — the largest possible value of a quantity like profit, or the smallest possible value of a quantity like cost — given the limitations of a situation.
Linear Programming: A Special Class of Optimisation Problems
A special, and very important, class of optimisation problems is the linear programming problem. The furniture dealer's problem above is itself an example of one. Linear programming problems are of much interest because of their wide applicability in industry, commerce, management science, and similar fields — anywhere a business or organisation must make the best use of limited resources.
The mathematician L. Kantorovich was among the pioneers who developed the theory behind linear programming, work for which he later shared the Nobel Memorial Prize in Economic Sciences. Today linear programming is a standard planning tool used by businesses, industries, and governments worldwide.
Scope of This Chapter
In this chapter we study linear programming problems and solve them by the graphical method only, even though several other methods (such as the simplex method, for problems with more than two variables) also exist for solving such problems.
The graphical method works because we can draw in only two dimensions — it is well suited to problems with exactly two decision variables. Problems with more variables need algebraic methods instead.
The furniture dealer's problem is the running example used throughout this chapter to build up, step by step, the formal ideas of linear programming — starting with its precise mathematical formulation in the next section.