How a Carpenter Decides How Many Chairs and Tables to Build

A small workshop has limited wood and working hours but wants the largest profit. Each product uses resources and earns money at a steady rate, so every limit is a straight line on a graph — and the best plan always sits at a corner of the allowed region.

This part covers the terminology, formulating a problem, feasible regions, and finding the optimal solution.

**A linear programming problem asks for the maximum or minimum of a linear objective function $Z=ax+by$ subject to linear inequalities called constraints, including $x,y\ge 0$; points satisfying every constraint are feasible solutions, and the best of them is the optimal solution.

Terminology:

- Objective function** — the linear function to optimise, $Z=ax+by$
- Constraints — linear inequalities the variables must satisfy
- Feasible solution — a point satisfying every constraint; any other point is infeasible
- Optimal solution — a feasible point giving the maximum or minimum value of $Z$

Worked example — identify the parts. Maximise $Z=4x+y$ subject to $x+y\le 50$, $3x+y\le 90$, $x\ge 0$, $y\ge 0$.

- The point $(10,20)$ is feasible, since $30\le 50$ and $50\le 90$
- The point $(40,20)$ is infeasible, since $3(40)+20=140>90$

An everyday example. A student splitting a fixed number of free hours between two subjects is setting up constraints and an objective without calling it linear programming.

The substance. Every expression must be linear — a term like $xy$ or $x^2$ takes the problem outside linear programming.

Define variables for the quantities to be decided, write the objective function for profit or cost, turn every resource limit into a linear inequality, and add the non-negative constraints.

Worked example — the workshop. A carpenter makes chairs and tables. A chair needs $2$ hours of work and $1$ unit of wood; a table needs $3$ hours and $2$ units. At most $24$ hours and $14$ units of wood are available each week. The profit is ₹300 on a chair and ₹500 on a table.

Let $x$ chairs and $y$ tables be made.

$$\text{Maximise }Z=300x+500y$$

subject to

$$2x+3y\le 24\text{(hours)},x+2y\le 14\text{(wood)},x\ge 0,y\ge 0$$

An everyday example. A dietitian choosing amounts of two foods to meet minimum protein and calcium needs at the lowest cost is formulating a minimisation problem with $\ge$ constraints.

The substance. **Leaving out $x\ge 0$ and $y\ge 0$ can give nonsense answers**, such as building a negative number of tables.

Draw each constraint's boundary line, keep the side that satisfies the inequality, and take the region common to all constraints; it is bounded if it can be enclosed in a circle and unbounded if it extends indefinitely.

Worked example — the workshop. For $2x+3y\le 24$ and $x+2y\le 14$:

- $2x+3y=24$ meets the axes at $(12,0)$ and $(0,8)$
- $x+2y=14$ meets the axes at $(14,0)$ and $(0,7)$
- Solving $2x+3y=24$ with $2x+4y=28$ gives $y=4$ and $x=6$

The feasible region has corners $(0,0)$, $(12,0)$, $(6,4)$ and $(0,7)$, and it is bounded.

An unbounded region. The constraints $x+y\ge 4$, $x\ge 0$, $y\ge 0$ allow points as far out as you like, so their region is unbounded.

An everyday example. Marking every place on a map reachable within both a fuel limit and a time limit gives a bounded region.

The substance. If no point satisfies all the constraints, the region is empty and the problem has no feasible solution.

**If an optimal value exists, it occurs at a corner point: for a bounded region compare $Z$ at every corner, and for an unbounded region confirm that the half-plane beyond the best corner value contains no feasible point, or else no optimum exists.

Worked example — the workshop.** Evaluating $Z=300x+500y$:

- $(0,0)$: $Z=0$
- $(12,0)$: $Z=3600$
- $(6,4)$: $Z=300(6)+500(4)=3800$
- $(0,7)$: $Z=3500$

The maximum profit is ₹3800, from $6$ chairs and $4$ tables.

Worked example — an unbounded region. For $x+y\ge 4$, $x\ge 0$, $y\ge 0$, the corners are $(4,0)$ and $(0,4)$, where $Z=2x+3y$ takes the values $8$ and $12$.

- Minimum: the half-plane $2x+3y<8$ contains no feasible point, so the minimum is $8$ at $(4,0)$
- Maximum: $Z$ grows without limit as $x$ or $y$ increases, so there is no maximum

An everyday example. A shop owner comparing the profit from each extreme mix of products is checking corner points — the in-between mixes can never beat the best corner.

The substance. Two corners can tie — then every point on the edge joining them is also optimal.