xSkill: notes, lectures and practice for CBSE and CSE

1.1 What a linear programming problem is A linear programming problem asks for the largest or smallest value of a linear function of two or more variables, with the variables restricted by linear inequalities and by non-negativity. The function to be optimised is the objective function, the variables are the decision variables, and the inequalities are the constraints. The chapter solves two-variable problems with the graphical method. 1.2 The standard form Every problem in this chapter can be written in one of two shapes. The objective is a linear expression, and the constraints are linear inequalities together with non-negative variables.

Maximise or minimise Z = a x + b y

The objective function; a and b are constants and x, y are the decision variables

subject to a_{1} x + b_{1} y \leq c_{1}, a_{2} x + b_{2} y \leq c_{2}, x \geq 0, y \geq 0

The constraints; some may use greater-than or equal signs, and non-negativity is always included

1.3 The feasible region The graph of the constraints gives a set of points common to all the half planes. That set is the feasible region, every point of it is a feasible solution, and a feasible point where the objective is optimal is an optimal solution. A feasible region is convex, so it is a polygon, possibly unbounded. Points outside it are infeasible and play no part in the solution. 1.4 The corner point method

Z (P_{1}), Z (P_{2}), \dots, Z (P_{n})

Evaluate the objective at every corner point of the feasible region; the list contains the answer

The method has three steps. First draw the feasible region and list its corner points, finding each by solving the two boundary lines that meet there. Second evaluate the objective function at every corner point. Third apply the theorem: for a bounded region, the largest and smallest of these values are the maximum and minimum of the problem.

bounded region ⟹ maximum and minimum both occur at corner points

Theorem 2, for a feasible region that can be enclosed in a circle

max Z exists only if a x + b y > M misses the feasible region

Unbounded case: if the open half plane beyond the largest corner value still cuts the region, no maximum exists

min Z exists only if a x + b y < m misses the feasible region

Unbounded case for a minimum, using the smallest corner value m

1.5 Multiple optimal solutions and no solution If two corner points give the same optimal value, every point on the segment joining them gives that value as well, so the problem has infinitely many optimal solutions. If the half planes have no point in common, the feasible region is empty and the problem has no feasible solution. Both cases are tested in the exercises and in board papers. Question asks Step to take Write the LPP from a word problem name the variables, write the objective, then each constraint Solve graphically shade the region, then list its corner points Bounded region corner point values settle maximum and minimum Unbounded region test whether the corner value can be beaten inside the region Two corners give the same value say every point on that edge is optimal No common point feasible region empty, so no solution 1.6 Common mistakes to avoid A strict inequality such as less than or greater than is drawn like the non-strict version for the feasible region, because the region is closed and the boundary points are included in the corner list. Non-negativity is not optional: a corner with a negative coordinate is not feasible even if it satisfies the other constraints. When the region is unbounded, the corner values are candidates, not answers, and the half-plane test must be written. In word problems, the objective is the quantity named in the question, not the constraint expression, and every constraint should be checked against the units used.

Question asks	Step to take
Write the LPP from a word problem	name the variables, write the objective, then each constraint
Solve graphically	shade the region, then list its corner points
Bounded region	corner point values settle maximum and minimum
Unbounded region	test whether the corner value can be beaten inside the region
Two corners give the same value	say every point on that edge is optimal
No common point	feasible region empty, so no solution