Section 12.2 · Furniture dealer: Furniture dealer: maximise $Z = 250x + 75y$

Basics you need

Solution

1. Name the unknowns

   Let $x$ be the number of tables and $y$ the number of chairs that the dealer buys. Neither can be negative:

   $$x \ge 0, \qquad y \ge 0.$$
   Every plan the dealer could follow is described completely by the two numbers $x$ and $y$⁠, so these are the unknowns (the book calls them decision variables). The conditions $x \ge 0$⁠, $y \ge 0$ are not written in the story, but a negative number of chairs makes no sense; the book calls them the non-negative constraints and always includes them.
   Lesson: variables, constraints, objective

2. The money (investment) constraint

   $x$ tables cost $2500x$ rupees and $y$ chairs cost $500y$ rupees. Together they cannot exceed Rs 50,000:

   $$2500x + 500y \le 50000.$$

   Dividing every term by 500:

   $$5x + y \le 100.$$
   "He has Rs 50,000 to invest" sets an upper limit on what he spends, so the total cost is at most 50000, which is "$\le$". Dividing both sides of an inequality by a positive number keeps its direction, and the smaller numbers are easier to graph: $2500 \div 500 = 5$⁠, $500 \div 500 = 1$⁠, $50000 \div 500 = 100$⁠.
   Basics: "at most" means $\le$

3. The space (storage) constraint

   Each table and each chair takes one storage place, and there are at most 60 places:

   $$x + y \le 60.$$
   The number of pieces bought is $x + y$⁠, and "storage space of at most 60 pieces" means this is at most 60. Note that money alone would allow 100 chairs ($50000 \div 500$⁠), but space allows only 60, so both limits matter.
   Basics: "at most" means $\le$

4. The profit (objective function) and the whole problem

   Each table earns Rs 250 and each chair Rs 75, so the total profit is

   $$Z = 250x + 75y.$$

   The dealer's problem is therefore the linear programming problem

   $$\begin{aligned} &\text{Maximise } Z = 250x + 75y \\ &\text{subject to } 5x + y \le 100, \\ &\qquad x + y \le 60,\ x \ge 0,\ y \ge 0. \end{aligned}$$
   The quantity to make as large as possible is the profit, and it depends on $x$ and $y$ only through $250x + 75y$⁠: a linear objective function. Together with the linear constraints from Steps 1 to 3, this is exactly the form the book calls a linear programming problem (Section 12.2.1).
   Lesson: formulating the problem

5. Draw the line $5x + y = 100$ and choose its side

   Put $y = 0$⁠: $5x = 100$⁠, so $x = 20$⁠. Put $x = 0$⁠: $y = 100$⁠. The line passes through $(20, 0)$ and $(0, 100)$⁠.

   Test $(0, 0)$ in $5x + y \le 100$⁠: $0 \le 100$ is true. So we keep the side of the line that contains the origin.

   A linear inequality is satisfied on one whole side of its boundary line (together with the line itself, because of the "$=$" in "$\le$"). One test point decides which side; the origin is the easiest because every term becomes 0.
   Basics: where a line meets the axes · Basics: which side

6. Draw the line $x + y = 60$ and choose its side

   Put $y = 0$⁠: $x = 60$⁠. Put $x = 0$⁠: $y = 60$⁠. The line passes through $(60, 0)$ and $(0, 60)$⁠.

   Test $(0, 0)$ in $x + y \le 60$⁠: $0 \le 60$ is true. Again we keep the origin's side.

   Same method. For any "$\le$" constraint with a positive number on the right, the origin's side is the one kept.
   Basics: one side of a line

7. Shade the feasible region

   The constraints $x \ge 0$ and $y \ge 0$ keep only the first quadrant. The part of the first quadrant on the origin's side of both lines is the quadrilateral OABC in the graph.

   For example, $(10, 50)$ is feasible, while $(25, 40)$ is not: $5(25) + 40 = 165 > 100$⁠, so it needs more money than he has. OABC is bounded: it fits inside a circle about O of radius 61, since every corner is at most 60 from O.

   The feasible region is the set of points obeying all four constraints at once, so it is the overlap of the four kept sides. Every point of it is a possible plan; every point outside breaks at least one limit. Knowing that it is bounded matters for the last step.
   Basics: where the shadings overlap · Basics: bounded or not

8. Find the corner points

   O $(0, 0)$⁠: where the two axes meet.

   A $(20, 0)$⁠: where $5x + y = 100$ meets the $x$-axis. (The other line meets the $x$-axis at $(60, 0)$⁠, but there $5(60) + 0 = 300 > 100$⁠, so that point is not in the region.)

   C $(0, 60)$⁠: where $x + y = 60$ meets the $y$-axis. ($(0, 100)$ is not in the region: $0 + 100 = 100 > 60$⁠.)

   B: where the two lines cross. Subtract the equations:

   $$\begin{aligned} (5x + y) - (x + y) &= 100 - 60 \\ 4x &= 40 \\ x &= 10, \end{aligned}$$

   and then $y = 60 - 10 = 50$⁠. So B is $(10, 50)$⁠. It obeys every constraint: $5(10) + 50 = 100 \le 100$⁠, $10 + 50 = 60 \le 60$⁠, and $10, 50 \ge 0$⁠.

   A corner is a point of the region where two boundary lines meet. Four lines (two constraint lines and two axes) give six crossing points, but only four of them lie in the region; $(60, 0)$ and $(0, 100)$ break the other constraint, so they are not corners. B is not easy to read accurately off a graph, so we solve the equations.
   Basics: a corner solves two equations

9. Work out $Z$ at each corner

   Corner point	$Z = 250x + 75y$ (in Rs)
   O $(0, 0)$	$0 + 0 = 0$
   A $(20, 0)$	$5000 + 0 = 5000$
   B $(10, 50)$	$2500 + 3750 = 6250$ ← largest
   C $(0, 60)$	$0 + 4500 = 4500$

   These are the only candidates: by Theorem 1, if $Z$ has a largest value on the region, it occurs at a corner point. The book calls the largest value in this table $M$ and the smallest $m$⁠.
   Lesson: the corner point method

10. Conclude

    The region OABC is bounded, so by Theorem 2 the largest value in the table is the maximum of $Z$ on the whole region: $Z = 6250$ at B$(10, 50)$⁠.

    So the dealer should buy 10 tables and 50 chairs; his profit is then Rs 6250, the most possible. The numbers are whole numbers, as they must be, and the plan uses all the money and all the space: $2500(10) + 500(50) = 50000$ and $10 + 50 = 60$⁠.

    The book's first guesses fit the table: tables only gives 20 tables and Rs 5000 (corner A), chairs only gives 60 chairs and Rs 4500 (corner C). Mixing at B beats both. Steps 5 to 10 are the book's Corner Point Method: (1) find the region and its corners, (2) evaluate $Z$ at each, (3)(i) for a bounded region take the largest and smallest values. For an unbounded region, step 3(ii), the book adds an open half-plane test. It prints the test as items 4(a) and 4(b), directly after step 3(ii), and Example 4 refers to it as "Step 3(ii)". It is not needed here, because OABC is bounded.
    Lesson: the furniture dealer, step by step

Every fact used, and where it comes from