Last Updated on: 19th January 2024, 12:22 pm

Linear Programming

Linear Programming

Earlier, we have studied Linear Equations and Linear Inequalities.  These properties are applied to solve real life problems through Linear Programming. It is used to solve  optimisation problems (like maximizing Profit, Minimising Cost, minimization of resources use,  etc).

In Mathematical terms, Linear programming is an optimization technique for a system of linear constraints and a linear objective function. An objective function defines the quantity to be optimized. linear programming finds the optimized values of the variables in the objective function.

Linear Programming solution Methods

There are several methods for Linear Programming solution. We describe some of them.

A person manufactures Pens and Pencils. It costs Rs 2 (selling at Rs 6) and takes 3 minutes to produce a Pen. It costs Rs 4 (selling at 7) and takes 4 minutes to produce a Pencil. The person has Rs.220 to spend and work upto 150 minutes in the day to produce these products. If each Pen Box sells for Rs.300 and each Pencil Box sells for 400. The factory has only Rs 2200 to spend. How many of each product should be manufactured to maximize profit by working maximum 150 hours in the week.

The constraints can be mathematically expressed as (assuming that x box of Pencil and y box of Pen production would maximise profit).

2x+4y≤2200 — (1) (Constraint of Money), 3x+4y ≤150 —(2), (constraint of time). We plot these two constraints in a graph (Fig-1). Then the area above the shaded polygon is the feasible solution. Now we see that profit from each Pen is 4 per unit and (=6-2) Pencil is 3 (=7-4) per unit. So, the Profit (P) can be defined as P= 4x+3y — (3). Here the inequalities (1) and (2) are called constraints and (3) is called the objective function to be optimized within the constraints. Any point in the feasible region that gives the optimal value (maximum / minimum) of the objective function is called the Optimal Solution.

P= 4x+3y. So, y=- x + , which represents a straight line. All points in the feasible region passing through this line is the optimal solution. The y-intercept of this line is . Since PP is maximized, this y-intercept should be maximized as well. The figure F-2 shows several lines with slope of .

Constraints Graph  in Linear Programming

Optimisation in Linear Programming

The line maximizing the y-intercept passes through the vertex at the intersection of the first two constraints (20,45). All other higher lines do not pass through the feasible region. All other lower lines pass through more than one point in the feasible region, and do not maximize the y-intercept of the line. Therefore, the factory should produce 20 Pens and 45 Pencils giving a profit of 4×20 + 3×45= Rs 215.