Linear ProgrammingLinear Programming Problem and its Mathematical Formulation
A furniture dealer deals in only two items, tables and chairs. He has ₹50,000 to invest and space to store at most 60 pieces. A table costs him ₹2500 and a chair ₹500. He expects a profit of ₹250 on each table and ₹75 on each chair, and he can sell everything he buys. How many tables and how many chairs should he buy, with the money he has, to make his total profit as large as possible?
Two things stand out. First, he can invest his money in many different ways — only tables, only chairs, or a mix — and each way earns a different profit. Second, there are overriding conditions, called constraints, that limit his choice: his investment can be at most ₹50,000, and his storeroom holds at most 60 pieces.
Before any algebra, play shopkeeper. Which of these plans can the dealer actually carry out?
Ten tables and fifty chairs use exactly ₹50,000 and exactly 60 places. Here are three plans worth comparing.
| Plan | Cost | Pieces | Profit |
|---|---|---|---|
| tables only: 50000 ÷ 2500 = 20 tables | ₹50,000 | 20 | 20 × 250 = ₹5000 |
| chairs only: he can afford 100, but can store only 60 | ₹30,000 | 60 | 60 × 75 = ₹4500 |
| 10 tables and 50 chairs | ₹50,000 | 60 | 10 × 250 + 50 × 75 = ₹6250 |
There are many other plans, each with its own profit. So the real question is: how should he invest his money to get the maximum profit? To answer it, we first write the problem in the language of mathematics.
Mathematical formulation of the problem
Let the dealer buy tables and chairs.
Nobody can buy a negative number of tables or chairs, so
Money. A table costs ₹2500 and a chair ₹500, so the plan costs
Space. The storeroom holds at most 60 pieces, so the storage constraint is
Profit. The dealer earns ₹250 per table and ₹75 per chair, so his profit is Z =
Every line of the story became one line of mathematics: each limit an inequality, the goal a single linear expression to be made as large as possible. The graph shows the two limits as the blue line and the green line — we will use it in a moment.
The dealer's problem, written mathematically
Maximise
subject to the constraints
The Words of Linear Programming
So we have to maximise a linear function Z, subject to conditions given by linear inequalities whose variables are non-negative. Other problems ask us to minimise a linear function under such conditions. All of these are called linear programming problems. The word linear says that every relation in the problem is linear; programming refers to finding a programme, a plan of action.
- A linear programming problem (LPP) asks for the optimal value — the maximum or the minimum — of a linear function of several variables, called the objective function, subject to the conditions that the variables are non-negative and satisfy a set of linear inequalities, called the linear constraints.
- Objective function. A linear function (, constants) that is to be maximised or minimised. For the dealer it is , and the variables and are the decision variables.
- Constraints. The linear inequalities or equations, that is, the restrictions, on the variables of an LPP. The conditions , are the non-negative restrictions. For the dealer, (1) to (4) are the constraints.
- Optimisation problem. A problem that seeks to maximise or minimise a linear function subject to constraints given by linear inequalities. Linear programming problems are a special type of optimisation problem.
Which of these could be the objective function of a linear programming problem?
has the form with , . The coefficients may be negative — a cost, or a loss — but the variables appear only to the first power, multiplied by constants and added.
Graphical method of solving linear programming problems
The dealer can choose from infinitely many plans. To see them all at once, we draw them. Take the investment constraint . The line cuts the plane into two half-planes: at every point on one side, is less than 100, and at every point on the other side it is more. So one test point decides a whole side.
Tip
The origin test. At , is true, so the half-plane of is the side of the line that contains O. If a line passes through the origin, test any other point, such as or .
Fig 12.1 is live. Tap the side of the blue line where holds, then the side of the green line where holds. The constraints and already keep us in the first quadrant.
Each point of the purple region OABC satisfies all four constraints (1) to (4), so it stands for a feasible choice open to the dealer.
- Feasible region. The common region determined by all the constraints, including the non-negative constraints , , of a linear programming problem is called its feasible region (or solution region). For the dealer it is the region OABC. The region other than the feasible region is called the infeasible region.
- Feasible solutions. The points within and on the boundary of the feasible region are feasible solutions of the constraints: for example , and .
- Infeasible solutions. Any point outside the feasible region is an infeasible solution.
Check the plan of 25 tables and 40 chairs:
Hunting the Corners
Every point of the region OABC is a feasible plan, and there are infinitely many of them. We cannot try them all. So where should we look for the plan that makes as large as possible? Gupta-ji's sweet shop gave us a clue: at a corner.
Drag the amber dot to each corner of the feasible region, or tap near a corner. The table records Z = 250x + 75y at every corner you visit. Then tap the row with the largest profit.
The largest value is ₹6250, at B(10, 50): the dealer should buy 10 tables and 50 chairs. A point of the feasible region that gives the optimal value (maximum or minimum) of the objective function is called an optimal (feasible) solution. But why should the best point be a corner, and not somewhere in the middle of the region? The answer is a pair of theorems that are fundamental to the whole subject. Their proofs are beyond the scope of the book, but the next step shows why they are true.
Theorem 1 Let R be the feasible region (a convex polygon) of a linear programming problem, and let be the objective function. If Z has an optimal value (maximum or minimum), where the variables , are subject to constraints described by linear inequalities, then this optimal value must occur at a corner point (vertex) of the feasible region.
Theorem 2 Let R be the feasible region of a linear programming problem, and let be the objective function. If R is bounded, then Z has both a maximum and a minimum value on R, and each of them occurs at a corner point (vertex) of R.
Note
A corner point of a feasible region is a point of the region where two boundary lines meet. A feasible region is bounded if some circle can enclose it; otherwise it is unbounded, which means that it extends without end in some direction.
Remark: if R is unbounded, a maximum or a minimum value of the objective function may not exist. But if it does exist, it must occur at a corner point of R (by Theorem 1).
Why the Corners Win
All the plans that earn exactly ₹2000 lie on one straight line, . Change the target to ₹3000 and you get : a line with the same slope, simply moved further from O. Raising the profit target slides this iso-profit line across the plane without turning it.
Slide the profit target. The amber line is every plan that earns exactly that much, and its thick part is the plans the dealer can actually carry out. Push the target as high as it can go while the line still touches the region.
Profit target: Z = ₹
As the target rises, the thick part of the line shrinks, until at ₹6250 only one point is left: the corner B. Any higher, and no feasible plan earns that much. A straight line sliding across a polygon always leaves it at a corner — or along a whole edge, if the line runs parallel to that edge. That is the idea behind Theorem 1.
The Corner Point Method
What you have just done has a name: the Corner Point Method. Before reading its steps, put the moves you made into order.
The corner point method
- Find the feasible region of the linear programming problem and its corner points (vertices) — either by inspection, or by solving the equations of the two lines that meet at that point.
- Evaluate the objective function at each corner point. Let M and m be the largest and the smallest of these values.
- If the feasible region is bounded, M and m are the maximum and the minimum values of Z.
- If the feasible region is unbounded: (a) M is the maximum value of Z if the open half-plane has no point in common with the feasible region; otherwise Z has no maximum value. (b) Similarly, m is the minimum value of Z if the open half-plane has no point in common with the feasible region; otherwise Z has no minimum value.
Let us see these steps at work in five examples. Each one has its own lab: the lab is the figure from the book, made live.
Example 1: Two Limits, One Maximum
Example 1 : Solve the following linear programming problem graphically:
Maximise … (1)
subject to the constraints:
… (2)
… (3)
… (4)
Fig 12.2 is live. Shade both constraints, visit every corner, then pick the maximum.
Now write the same solution the way you would in an exam.
Solution : The shaded region in Fig 12.2 is the feasible region determined by the constraints (2) to (4). It is the region OABC, and it is
The corner B is where meets . Subtracting the first equation from the second, , so
So the corner points O, A, B and C are , , and . Evaluating Z at each of them:
| Corner point | Z = 4x + y |
|---|---|
| O(0, 0) | 0 |
| A(30, 0) | 120 |
| B(20, 30) | 110 |
| C(0, 50) | 50 |
Hence the maximum value of Z is
Example 2: Shading Away from the Origin
Example 2 : Solve the following linear programming problem graphically:
Minimise … (1)
subject to the constraints:
… (2)
… (3)
… (4)
This time constraint (2) is a "≥". The origin test gives , which is false, so its half-plane is the side away from O.
Fig 12.3 is live. Shade both constraints, visit every corner, then pick the minimum.
Solution : The shaded region in Fig 12.3 is the feasible region ABC determined by the constraints (2) to (4). It is bounded.
The corner B is where meets . Doubling the first gives ; subtracting it from the second,
So the corner points A, B and C are , and . Evaluating there gives
Hence the minimum value of Z is 2300, attained at the point .
Example 3: A Tie at the Top
Example 3 : Solve the following problem graphically:
Minimise and Maximise … (1)
subject to the constraints:
… (2)
… (3)
… (4)
… (5)
Tip
The line of constraint (4) passes through O, so the origin test cannot decide its side. Test instead: is true, so the half-plane of is the side above the line, containing the y-axis.
Fig 12.4 is live. Shade all three constraints, visit the corners, then pick the minimum and the maximum.
Solution : First, graph the feasible region of the inequalities (2) to (5). It is the region ABCD in Fig 12.4, and it is bounded.
A is where meets the y-axis: . B is where meets : , so B =
| Corner point | Z = 3x + 9y |
|---|---|
| A(0, 10) | 90 |
| B(5, 5) | 60 |
| C(15, 15) | 180 |
| D(0, 20) | 180 |
From the table, the minimum value of Z is
Remark
This problem has multiple optimal solutions: the corner points C and D give the same maximum value, 180. In such a case every point of the line segment CD joining them also gives the maximum value. The same is true when two corner points give the same minimum value.
Why a Whole Edge Can Win
Why should every point between C and D give 180? Write . The objective function is a multiple of the left-hand side of constraint (2), so its iso-lines are parallel to the edge CD.
Slide Z up. Find the largest value at which the amber line still touches the region, and watch what it touches.
Z =
At Z = 180 the line does not leave the region at a single corner: it lies along the whole edge CD, and every point of that edge — , , and all the rest — gives Z = 180. Notice too that at Z = 60 the line touches the region only at B: the minimum is unique.
Example 4: An Unbounded Region
Example 4 : Determine graphically the minimum value of the objective function
… (1)
subject to the constraints:
… (2)
… (3)
… (4)
… (5)
The feasible region of these constraints is shaded in Fig 12.5. It is unbounded: it runs off towards the top right without end. So Theorem 2 does not apply, and the smallest corner value may not be the minimum.
Fig 12.5 is live. Visit the four corners and pick the smallest value of Z. Then use step 4 of the corner point method: test the open half-plane.
Solution : The feasible region (Fig 12.5) is unbounded. Evaluating Z at its corner points:
| Corner point | Z = −50x + 20y |
|---|---|
| A(1, 0) | −50 |
| B(0, 3) | 60 |
| C(0, 5) | 100 |
| D(6, 0) | −300 |
From this table, −300 is the smallest value of Z, at the corner point . Can we say that the minimum value of Z is −300? If the region were bounded, yes, by Theorem 2. But the region is unbounded, so −300 may or may not be the minimum. To decide, we graph the inequality
, i.e.
and check whether this open half-plane has points in common with the feasible region. If it does, −300 is not the minimum value of Z; if it does not, −300 is the minimum.
As the lab shows, it does: the point is feasible and gives
Can Z have a maximum here? The largest corner value is 100, at . Check the open half-plane , i.e. . Every feasible point satisfies constraint (2), , so . The half-plane has no point in common with the region, so Z
Example 5: No Feasible Region
Example 5 : Minimise
subject to the constraints:
… (1)
… (2)
… (3)
Fig 12.6 is live. Shade both constraints and see what is left. Is there any feasible region?
Solution : From Fig 12.6 you can see that there is no point satisfying all the constraints simultaneously. The problem has no feasible region, and hence no feasible solution. (Look at the numbers: on the line the largest value of is 5, at , nowhere near 8.)
Remarks
From the examples so far, we notice some general features of linear programming problems:
(i) The feasible region is always a convex region: the line segment joining any two of its points lies completely inside it.
(ii) The maximum (or minimum) of the objective function occurs at a vertex (corner) of the feasible region. If two corner points give the same maximum (or minimum) value of the objective function, then every point on the line segment joining them gives the same maximum (or minimum) value.
Speed Round: Read the Region
Shade it in your head. The lines are drawn for you; decide whether the feasible region is bounded, unbounded, or not there at all. After each answer, the region fills in.
Get five right to move on.
Speed Round: Does the Optimum Exist?
Work out Z at each corner in your head. If the region is bounded, the answer is in your list. If it is unbounded, ask one more question first: can Z keep growing (or falling) along the open side?
Get five right to move on.