Chapter 12 — Linear Programming

What is Linear Programming?
Linear Programming (LP) is a method to achieve the best outcome (maximum profit, minimum cost, etc.) in a mathematical model whose requirements are represented by linear relationships. An LP problem consists of a linear objective function to be maximized or minimized subject to a set of linear constraints (inequalities or equations) and non-negativity conditions on the variables.

Key components

• Decision variables: unknowns to be determined (e.g., x and y).
• Objective function: a linear function of decision variables to maximize or minimize, e.g. Z = c1 x + c2 y.
• Constraints: linear inequalities/equations limiting the variables, e.g. a1 x + b1 y ≤ b.
• Feasible region: set of all points satisfying the constraints and non-negativity — usually a convex polygon (or unbounded region) in 2D.
• Optimal solution: a point in the feasible region where the objective function reaches its best value. For LP with linear constraints, an optimum (if exists and is finite) occurs at a vertex (corner point) of the feasible region.

Graphical method (for two variables)

1. Introduce decision variables x and y (both ≥ 0 unless otherwise stated).
2. Write the objective function (e.g. Maximize Z = p x + q y).
3. Plot each linear constraint as a straight line and shade the half-plane satisfying the inequality.
4. The feasible region is the intersection of all shaded half-planes (and axes for non-negativity).
5. Find the vertices (corner points) of the feasible region by solving pairs of boundary equations.
6. Evaluate the objective function at each vertex; the best value gives the optimal solution.

Special cases

• No feasible solution: constraints are inconsistent (feasible region empty).
• Unbounded solution: feasible region is unbounded and objective can increase/decrease without bound.
• Multiple optima: whole edge (segment) of the feasible region gives the same optimal value.

Practical tips: Always check non-negativity conditions, draw constraint lines accurately (use intercepts), label intersection points, and use the corner-point principle to compute objective values only at vertices.

What is a Linear Programming Problem (LPP)?
A linear programming problem is a mathematical procedure to find the best (maximum or minimum) value of a linear objective function subject to a set of linear constraints (equalities or inequalities) and non-negativity conditions. It models optimization problems where relationships are linear.

Key components

• Decision variables: unknowns to be determined (x1, x2, ...).
• Objective function: the linear function to maximize or minimize, e.g., Maximize Z = c1 x1 + c2 x2 + ...
• Constraints: linear inequalities or equations representing resource limits, e.g., a11 x1 + a12 x2 + ... ≤ b1.
• Non-negativity conditions: xj ≥ 0 unless negative values are allowed.

Steps to formulate an LPP

1. Understand the problem: read context, identify what to optimize (profit, cost, time, etc.).
2. Define decision variables: assign variables to quantities you can control, with units.
3. Write the objective function: express the quantity to maximize/minimize in terms of the decision variables.
4. Write constraints: translate resource limits, requirements and logical conditions into linear inequalities or equations.
5. Set non-negativity conditions: state xj ≥ 0 if negative values are not meaningful.
6. Convert to standard form if needed: for algorithmic solution (simplex), convert inequalities to equalities using slack/surplus (and possibly artificial) variables.

Common translations

• 'At most' or 'not more than' → use ≤
• 'At least' or 'not less than' → use ≥
• 'Total available' or 'limited by' usually give ≤ constraints
• 'Needs to be exactly' → use =

Properties
For problems with two variables, the feasible region (set of points satisfying all constraints) is a convex polygon (possibly unbounded). If an optimal solution exists for a linear objective, at least one optimal solution occurs at a corner (extreme) point of the feasible region (corner-point principle).

Converting inequalities for simplex
To convert ≤ constraints to equalities, add slack variables s ≥ 0: a11 x1 + a12 x2 + ... + s = b. For ≥ constraints, subtract a surplus variable and possibly add an artificial variable when using simplex.

What is a Linear Programming Problem (LPP)?
An LPP is the process of optimizing (maximizing or minimizing) a linear objective function subject to a set of linear constraints (inequalities or equalities). In Class 12 problems the variables are usually two: x and y.

Standard form (two variables)
Objective: Z = ax + by (to be maximized or minimized)
Subject to: linear constraints of the form c1x + d1y (≤, ≥, =) e1, etc., and usually x ≥ 0, y ≥ 0.

Graphical method — idea
When there are two variables, each linear constraint corresponds to a straight line on the xy-plane. The set of points satisfying all constraints is the feasible region (a polygon or unbounded region). The optimal value of Z occurs at one (or more) corner (vertex) of the feasible region (Corner-Point Theorem).

Step-by-step procedure

1. Write the objective function and all constraints (including x ≥ 0, y ≥ 0 if given).
2. Convert each constraint into an equality to draw its boundary line: cix + diy = ei.
3. Plot each boundary line on a graph. Use intercepts (set x=0 to get y-intercept, set y=0 to get x-intercept) or two convenient points to draw the line.
4. Determine which side of each boundary line satisfies the inequality (test a point, often (0,0) if not on the line).
5. Shade the common region that satisfies all constraints — this is the feasible region. If no common region exists, the LPP is infeasible.
6. Identify all corner points (vertices) of the feasible region — intersections of boundary lines and/or axes.
7. Evaluate the objective function Z = ax + by at each corner point. The largest value (for maximization) or smallest (for minimization) among these is the optimal solution.
8. Special-case checks: if feasible region is unbounded, check whether objective can increase/decrease without bound; if an objective line coincides with an edge, there are infinitely many optimal solutions.

Iso-profit / Iso-cost line method (alternate visualization)
Write ax + by = Z and regard Z as a parameter. This is a straight line with slope -a/b. For maximization, slide the line parallelly away from the origin until it last touches the feasible region; that touching point is the optimum. For minimization slide toward the origin until first touch.

Corner-Point Theorem
If the feasible region is non-empty and bounded, the maximum or minimum value of a linear objective function occurs at a vertex (corner point) of the feasible region.

Special cases to watch

• Infeasible: no common feasible region.
• Unbounded: feasible region extends to infinity; objective may be unbounded (no finite optimum) or may have finite optimum depending on its direction.
• Multiple optimal solutions: objective line is parallel to a side of feasible region and the entire side yields the same optimal value.
• Redundant constraint: constraint that does not affect feasible region.

Notes
Graphical method applies only when there are two decision variables. If variables must be integers, graphical method gives fractional solution which may need integer programming techniques.

Overview

Linear Programming (LP) is the study of optimizing a linear objective function subject to a set of linear constraints (equalities or inequalities). In Class 12, the focus is on two-variable problems solved by the graphical method and on fundamental theorems that guarantee where optima occur.

Key components of an LPP

• Decision variables: unknowns to be chosen (usually x and y).
• Objective function: a linear function to be maximized or minimized, e.g. Z = c1 x + c2 y.
• Constraints: linear inequalities (or equalities) like a11 x + a12 y ≤ b1, together with non‑negativity conditions x ≥ 0, y ≥ 0.
• Feasible region: set of all points (x,y) satisfying all constraints. For linear constraints this is a convex polygon (possibly unbounded) in the plane.

Why convexity matters

The feasible region formed by linear inequalities is convex: any line segment joining two feasible points lies entirely in the region. This convexity is critical for optimization because it ensures that a global optimum occurs at an extreme point (vertex) of the feasible region.

Fundamental theorem (Corner‑point or Extreme‑point theorem)

If a linear programming problem has an optimal solution and the feasible region is nonempty and bounded, then at least one optimal solution occurs at a vertex (corner point) of the feasible region. Consequently, for two‑variable problems solved graphically, one needs only evaluate the objective function at the vertices to find the optimum.

Special cases

• No feasible solution: constraints are inconsistent and feasible region is empty.
• Unbounded solution: feasible region is unbounded and the objective can increase (or decrease) without bound.
• Multiple (infinitely many) optimal solutions: objective function is parallel to a constraint line and attains the same maximum/minimum along an edge segment of the feasible polygon.

Graphical method summary (2 variables)

1. Let x ≥ 0, y ≥ 0 (if given) and write all constraints.
2. Convert each inequality into the boundary line (replace ≤ or ≥ by =).
3. Plot the boundary lines (use intercepts to draw them quickly) and determine the half‑planes to shade; intersection of all half‑planes is the feasible region.
4. Identify corner points (vertices) of the feasible region — intersections of pairs of boundary lines or intersections with axes.
5. Compute the objective value Z at each vertex; choose the vertex giving the largest (or smallest) Z.
6. Check special cases: if objective lines are parallel to an edge containing vertices with same Z, there are infinitely many optima; if region is unbounded and objective improves indefinitely in an allowed direction, there is no finite optimum.

Practical notion of slack and surplus

For a ≤ constraint, slack = b − (ax + by) ≥ 0. For a ≥ constraint, surplus = (ax + by) − b ≥ 0. These measure unused or excess amounts and are used in algebraic/LP tableau methods.

What is being solved: In linear programming (graphical method) we maximize or minimize a linear objective function Z = ax + by subject to linear inequalities (constraints) and x, y usually ≥ 0. The feasible region is the set of all points (x,y) that satisfy the constraints. The nature of the feasible region and how the objective lines meet it determine the type of solution.

Corner-point (vertex) principle: For a linear objective and a convex polygonal feasible region, an optimal value (maximum or minimum) if it exists occurs at a vertex (corner point) of the feasible region. Thus the graphical method: draw constraints, find vertices (intersections of boundary lines), evaluate Z at each vertex and choose the best value.

Main types of solutions and special cases

• Unique (single) optimal solution: The objective line touches the feasible region at exactly one vertex. Evaluate Z at all vertices; one vertex gives the best value.
• Multiple (infinitely many) optimal solutions: The objective line is parallel to a boundary of the feasible region and coincides with it at the optimum. Every point on that edge (line segment) gives the same optimal value — infinitely many optima.
• Unbounded solution (objective unbounded): The feasible region is unbounded in a direction in which the objective function increases (for maximization) or decreases (for minimization). Then the objective can go to +∞ or −∞ and no finite optimal value exists.
• No feasible solution (infeasible LP): The constraints have no common point; feasible region is empty. There is no solution that satisfies all constraints simultaneously.
• Feasible region is a single point or a line segment: If constraints reduce to equalities or force a single intersection, the feasible set may be a single point (one feasible solution) or a line segment (every point on it feasible). If objective is constant on that set, every point is optimal; otherwise pick that point.
• Redundant constraint: A constraint that does not affect the feasible region (it is implied by others). Removing it does not change the feasible set or optimum.
• Degeneracy (graphical view): More than two boundary lines meet at a single vertex (e.g., an intersection where three or more constraints are active). Degeneracy can lead to ties in objective values at adjacent vertices or multiple bases representing same vertex.

How to identify these cases (graphical checklist):

• Plot all constraint lines and shade the feasible side; locate the feasible region (if none, LP is infeasible).
• Check if the feasible region is bounded (closed polygon) or unbounded (opens to infinity).
• Draw objective lines ax + by = c and slide them in the direction of increasing (or decreasing) c until the last contact with the feasible region. If the last contact is a vertex — unique optimum; if it coincides with an entire edge — infinitely many optima; if the line can move to infinity without leaving feasible region — unbounded objective.
• Check constraint redundancy visually: a constraint inside the feasible polygon is redundant.

Typical solution procedure (graphical): 1) Convert inequalities to boundary lines. 2) Draw lines, find intersection points (vertices). 3) List only vertices inside the feasible region. 4) Compute Z = ax + by at each vertex. 5) Select the vertex(ices) giving maximum/minimum. Use the behaviour of objective lines to detect special cases.

In linear programming (Class 12), constraints are linear equations or inequalities that define the feasible region for the decision variables. Handling different types of constraints correctly is essential to get the correct feasible region and optimum solution. Common constraint types are:

• ‘≤’ (less-than-or-equal-to) : represents an upper bound. Convert to an equality by adding a slack variable (nonnegative).
• ‘≥’ (greater-than-or-equal-to) : represents a lower bound. Convert to an equality by subtracting a surplus variable (nonnegative). In algebraic methods you may also need an artificial variable for simplex methods.
• ‘=’ (equality) : the feasible region is restricted to the line itself (or intersection of lines).
• Non-negativity constraints (x, y ≥ 0) : restrict variables to the first quadrant. If variables are free (can be negative), replace each free variable by difference of two nonnegative variables.

Standard graphical method steps when constraints involve two variables:

1. Write each constraint in the form ax + by ≤ c or ax + by ≥ c (or = c).
2. Draw the boundary line ax + by = c for each constraint. Use intercepts or solve two points to plot the line.
3. Determine the half-plane that satisfies the inequality by testing a point (usually origin if not on the line).
4. The feasible region is the intersection of all half-planes and non-negativity conditions. It will be a polygon (possibly unbounded), a line segment, a single point, empty (infeasible), or unbounded.
5. Use the corner-point (vertex) method: compute all corner (intersection) points of the feasible polygon and evaluate the objective function Z = ax + by at each vertex. The maximum or minimum occurs at one (or more) vertices.

Special cases to recognize:

• Redundant constraint : does not change the feasible region (lies outside or inside polygon).
• Infeasible system : no point satisfies all constraints.
• Unbounded solution : feasible region is unbounded and objective function can increase/decrease indefinitely (no finite optimum).
• Multiple optimal solutions : objective function is parallel to a constraint edge; every point on that edge gives the same optimal value.
• Binding vs non-binding : at optimum, a constraint is binding if it holds as equality at the optimum vertex; otherwise, it is non-binding.

Algebraic conversions often used:

• For ax + by ≤ c: add slack s ≥ 0 so ax + by + s = c.
• For ax + by ≥ c: subtract surplus s ≥ 0 so ax + by - s = c (and possibly add artificial variable if using simplex).
• For a variable free in sign: x = x' - x'' with x', x'' ≥ 0.

Handling these conversions carefully ensures correct plotting, correct vertex calculation, and correct identification of optimal values.

What it is: In Linear Programming (graphical method for two variables) you form an objective function (to maximize or minimize) and linear constraints. The solution strategy finds the feasible region (set of all points satisfying the constraints) and uses the Corner‑Point (Extreme Point) principle: the optimum value of the objective occurs at one (or more) vertices of the feasible region.

Step‑by‑step solution strategy:

• 1. Define variables: assign x and y to measurable quantities (non‑negative if stated).
• 2. Form the objective function: Z = ax + by (either maximize or minimize).
• 3. Write constraints as linear inequalities (include x ≥ 0, y ≥ 0 if required).
• 4. Convert inequalities to equalities to draw boundary lines: ax + by = c.
• 5. Plot boundary lines on the xy‑plane (use intercepts for quick sketch).
• 6. Determine feasible region by testing a convenient point (e.g., (0,0)) or using the direction of inequalities; shade it.
• 7. Find corner (vertex) points — intersections of pairs of boundary lines and intersections with axes.
• 8. Evaluate objective Z at each vertex. The maximum/minimum among these is the required optimum.
• 9. Check feasibility/special cases: no feasible region (infeasible), unbounded region (may have no finite optimum), or infinitely many optima (objective parallel to a constraint along an edge).

Common shortcuts and tips:

• Plot lines fast using intercepts: for ax + by = c, x‑intercept = c/a (set y=0), y‑intercept = c/b (set x=0).
• To find intersection of two lines, solve the 2×2 linear system. Use substitution, elimination, or Cramer’s rule if you prefer.
• Test (0,0) to quickly determine which side of a line to shade when 0 satisfies all nonstrict inequalities.
• Use the slope of objective line (-a/b) to compare with constraint slopes: if objective is parallel to a bounding edge and you can move the objective line along that direction inside the feasible region, you may have infinitely many optimal solutions along that edge.
• If feasible region is unbounded, compare objective slope with feasible directions. For maximization, if you can move objective line indefinitely in increasing direction without leaving feasible region, no finite maximum exists (similarly for minimization).
• Eliminate redundant constraints (those that do not affect the feasible region) to simplify graphing.
• Compute slack for a constraint: slack = RHS − (ax + by). If slack = 0 at optimum, the constraint is binding.

Special cases (recognize quickly):

• No feasible region → no solution (constraints inconsistent).
• Unbounded feasible region with objective improving without bound → no finite optimum.
• Objective line parallel to a constraint edge that forms a face of the feasible region → infinitely many optima along that edge.

Linear Programming Problems (LPP) are optimisation problems in two (or more) variables where you maximise or minimise a linear objective function subject to linear inequality constraints. The Chapter's "Examples and Practice Problems" develop skill in modelling real situations as LPP, drawing the feasible region, and using the graphical (corner-point) method to find the optimum.

Standard procedure (graphical method for two variables):

• Step 1 — Define variables: choose x, y to represent decision quantities clearly.
• Step 2 — Form the objective function: Z = px + qy (to be maximised or minimised).
• Step 3 — Write constraints as linear inequalities (including non-negativity x ≥ 0, y ≥ 0).
• Step 4 — Graph each constraint as a straight line; determine which side satisfies the inequality and shade it. The intersection of all shaded half-planes is the feasible region.
• Step 5 — Identify corner (extreme) points of the feasible region — these are intersection points of pairs of boundary lines (or intercepts with axes).
• Step 6 — Evaluate Z at each corner point. For a bounded feasible region, the maximum or minimum occurs at one of the corner points (corner-point theorem).
• Step 7 — Interpret the result in the original problem context and check feasibility (including integer requirements if any).

Important observations:

• If the feasible region is empty → LPP is infeasible.
• If the feasible region is unbounded and the objective function increases without bound along that region → objective is unbounded (no finite optimum).
• Sometimes constraints are redundant (do not affect the feasible region); identify them by graphing or algebraically.
• To find optimum quickly on graph, use isoprofit/isocost lines: draw the line px + qy = constant and slide it parallelly until the last point it touches the feasible region.

What to interpret from a linear programming (LP) solution

After solving an LP (graphically or by simplex), you must interpret the solution in terms of the original application. Key points to read from the solution are:

• Feasibility: Is there any point that satisfies all constraints? If not, the problem is infeasible — no practical solution meets the requirements.
• Optimality: If feasible, is there a point that maximizes/minimizes the objective? For a bounded feasible region, an optimal value exists and occurs at one (or more) corner(s) of the feasible region.
• Uniqueness vs. Multiplicity: The solution may be unique (one corner) or multiple (all points on an edge give the same objective value). Multiple optima happen when the objective line is parallel to a constraint boundary that forms the active edge.
• Unboundedness: If the objective can increase (or decrease) indefinitely while remaining feasible, the problem is unbounded — no finite optimum.
• Slack and Surplus: For ≤ constraints, slack = (RHS − LHS) at the solution; it measures unused resource. For ≥ constraints, surplus = (LHS − RHS) measures excess above the minimum requirement.

How to read the numeric solution

1. Identify the feasible region (intersection of all constraints including non-negativity if present).
2. List corner points (vertices) of the region and compute the objective function value at each corner.
3. The corner with the largest (for maximization) or smallest (for minimization) objective value is optimal (if region is bounded).
4. Compute slack/surplus for each constraint at the optimal point to see which resources are binding (zero slack) and which are not.

Practical considerations (modelling and real-world use)

• LP assumes linear relationships and continuous variables. If variables must be integers (e.g., number of machines, people), use integer programming or round carefully — naive rounding can violate constraints.
• Data uncertainty: coefficients and RHS values (profits, costs, capacities) may change. Check sensitivity: small changes in coefficients may change which corner is optimal.
• Multiple optima give flexibility: choose the solution that best fits secondary criteria (e.g., ease of implementation) while keeping the same objective value.
• Unbounded solutions usually indicate a missing realistic constraint (e.g., market limit, capacity limit). Re-examine model assumptions and add constraints as needed.
• Rounding: when presenting final values, round in a way that keeps feasibility and re-check constraints, or reformulate as integer LP if necessary.
• Scalability: Graphical methods apply only to two-variable LPs. For larger problems use algebraic simplex or solver software and then interpret results similarly (binding constraints, slack, shadow prices).

Summary checklist when you interpret results

• Confirm feasibility.
• Identify whether optimal solution is unique, multiple, unbounded, or infeasible.
• Report optimal variable values and objective value.
• Report slack/surplus for each constraint and note binding constraints.
• Consider real-world limits, integer needs, and sensitivity to data changes before acting on the numerical solution.