Statistics

Linear Programming

Read at your own pace. Use chapter practice to check your understanding.

Chapters and chapter contents
100%
Practise this chapter ↓

Last updated · By the Clerk2Officer editorial team · Report a correction

1. A decision under limited resources

Linear programming chooses values of decision variables to maximise or minimise a linear objective subject to linear restrictions. A bank might allocate processing capacity between products, assign a budget across activities or plan a simplified portfolio. The method makes tradeoffs explicit. It does not decide which business objective is ethically or commercially appropriate. That objective and the relevant constraints must be supplied by the decision maker and represented accurately in the model.

Consider two types of review work, retail and SME. Let x and y represent quantities of work in divisible capacity units. Each unit contributes three and five illustrative value points respectively. Retail capacity is limited to four units, SME capacity to six, and shared analyst capacity requires three hours per retail unit and two per SME unit with eighteen hours available. The model maximises Z = 3x + 5y subject to x ≤ 4, y ≤ 6, 3x + 2y ≤ 18 and x,y ≥ 0. These are invented classroom inputs. If actual files must be indivisible, an integer model or explicit integer feasibility check is needed before adopting the solution.

2. Translate words into a model

Define each variable with units and a time horizon. If x is weekly retail review units, every related capacity must refer to the same week. The objective coefficient three is value points per retail unit, so multiplying by x produces value points. The shared-capacity coefficient three has a different meaning: analyst hours per retail unit. Identical numerical coefficients do not imply identical units. Dimensional consistency catches many formulation errors before calculation begins.

Translate “at most” into a less-than-or-equal restriction, “at least” into greater-than-or-equal, and an exact requirement into equality. Add nonnegativity when negative activity is not meaningful. Distinguish a decision variable from a fixed input. Available staff hours are normally a parameter in this simple model, while the amount of work assigned is a decision. If overtime can be purchased, it may become another variable with a cost and upper limit. Include only restrictions relevant to the authorised decision, but do not omit real limits to make the objective look better. A mathematically optimal answer to an incomplete model can be operationally infeasible.

3. Assumptions behind linearity

Proportionality means resource use and contribution change in direct proportion to each activity level. Additivity means total use and value equal the sums of individual activity contributions. Divisibility permits fractional decision values in an ordinary linear program. Certainty treats coefficients as known for the calculation. Nonnegativity restricts activities where negative values have no physical meaning. These assumptions define the model's scope rather than asserting that all banking operations are literally linear.

For example, a fixed setup cost violates simple proportionality because starting an activity incurs a cost even at a tiny volume. A bulk discount changes the marginal contribution after a threshold. Interaction between two activities can violate additivity. Indivisible staff shifts violate divisibility. Uncertain processing times challenge the certainty assumption. Some such features can be handled with additional variables, integer restrictions or other optimisation approaches, but they should not be hidden inside an unsuitable basic model. In an examination case, solve the stated model and identify assumptions when asked. In an implementation, compare the model with the real process before treating the mathematical optimum as a ready-to-execute plan.

4. Draw the feasible region

With two decision variables, plot each constraint boundary on an x-y plane. The boundary x = 4 is vertical, y = 6 is horizontal, and 3x + 2y = 18 intersects the axes at x = 6 and y = 9. Test a point such as the origin to determine which side satisfies an inequality. Nonnegativity restricts attention to the first quadrant. The feasible region is the intersection of all allowed half-planes. Every point in that intersection satisfies every restriction simultaneously.

In the worked model, the feasible vertices are (0,0), (4,0), (4,3), (2,6) and (0,6). The point (4,6) satisfies the separate upper bounds but violates the shared resource limit because 3 × 4 + 2 × 6 = 24 exceeds eighteen. Checking only one or two constraints is insufficient. The diagonal boundary meets x = 4 at y = 3 and y = 6 at x = 2. These intersections explain the two upper-right corners. A sketch should label boundaries and feasible shading clearly, but numerical substitution remains the final check. A visually plausible point can still be infeasible if the axes or intercepts were drawn inaccurately.

Feasible region and optimumShaded polygon satisfies x≤4, y≤6, 3x+2y≤18 and nonnegativity. The marked optimum (2,6) gives 3x+5y=36.Feasible region and optimum(2,6), Z=36(4,3)046xy
Shaded polygon satisfies x≤4, y≤6, 3x+2y≤18 and nonnegativity. The marked optimum (2,6) gives 3x+5y=36.

5. Evaluate corner points

For a nonempty bounded feasible region in this two-variable linear problem, at least one corner point attains the optimum. Evaluate the objective at each feasible vertex. At (0,0), Z is zero. At (4,0), it is twelve. At (4,3), it is twenty-seven. At (2,6), it is thirty-six. At (0,6), it is thirty. Therefore the maximum is thirty-six at x = 2 and y = 6. The calculation is transparent and can be checked against the graph.

The objective line 3x + 5y = Z has slope minus three fifths. Moving it in the improving direction until it last touches the feasible region reaches the same point. The corner method does not mean that every optimum must be a single isolated corner. If the objective is parallel to a feasible edge at the best level, every point along that edge can be optimal. Also, the usual corner argument needs the relevant feasibility and boundedness conditions. Do not evaluate arbitrary intersections outside the feasible region. A boundary intersection is only a candidate after all original inequalities and nonnegativity have been checked.

Compare every feasible vertexObjective 3x+5y has values 0, 12, 27, 36 and 30 at the five feasible vertices. The highest is 36.Compare every feasible vertexValue points0(0,0)12(4,0)27(4,3)36(2,6)30(0,6)
Objective 3x+5y has values 0, 12, 27, 36 and 30 at the five feasible vertices. The highest is 36.

6. Slack, binding constraints and interpretation

Slack for a less-than-or-equal constraint is available capacity minus used capacity. At the optimum (2,6), the retail upper bound has slack four minus two, or two units. The SME bound has zero slack, and the shared analyst constraint uses 3 × 2 + 2 × 6 = 18 hours, also leaving zero slack. Constraints with zero slack are binding at that solution. Different slacks have different units, so adding them together usually has no useful interpretation.

A nonbinding resource has spare capacity at the current optimum, but that does not mean the resource is permanently worthless. Its relevance can change if objective coefficients or other constraints change. A binding constraint need not always have a positive marginal value, particularly in degenerate or redundant situations. To interpret a capacity increase, examine the model's sensitivity within a range where the solution structure remains valid. In this example, one additional shared analyst hour with the SME bound unchanged permits x to rise by one third, increasing value by one point, while the same active constraints remain appropriate. This local result is not a promise for arbitrarily large capacity increases.

7. Standard form for simplex

The simplex method moves between basic feasible solutions while improving the objective. For this maximisation problem with less-than-or-equal constraints and nonnegative right-hand sides, add nonnegative slack variables to convert inequalities into equalities. The equations become x + s1 = 4, y + s2 = 6 and 3x + 2y + s3 = 18. Write the objective as Z−3x−5y = 0. Initially set x and y to zero, giving slack values four, six and eighteen.

The slack variables form an initial feasible basis because their columns identify one variable in each constraint and their values are nonnegative. In the chosen objective-row convention, a negative coefficient signals a potential improving entering variable. Other textbooks may use a different sign convention, so follow the stated tableau consistently. The underlying optimisation is unchanged by notation. A basic variable is solved from the current equations, while nonbasic variables are temporarily set to zero. A pivot exchanges one entering and one leaving variable. The ratio test controls how far the entering variable can increase without making a basic variable negative, preserving feasibility during the move.

8. First simplex pivot

The initial objective row has coefficients minus three for x and minus five for y. Choose y to enter using the most-negative-coefficient rule in this convention. Only rows with a positive y coefficient qualify for the ratio test. The y-bound row gives 6/1 = 6. The shared row gives 18/2 = 9. The x-bound row has zero y coefficient and does not limit this increase. The smallest eligible ratio is six, so s2 leaves and y becomes basic.

The pivot row is y + s2 = 6. Subtract twice this row from the shared equation to obtain 3x−2s2+s3 = 6. Add five times the pivot row to the objective equation to obtain Z−3x+5s2 = 30. The x-bound equation remains x+s1 = 4. With nonbasic x and s2 set to zero, the basic solution is x = 0, y = 6, s1 = 4 and s3 = 6, with objective thirty. This matches a feasible graph vertex. The remaining negative objective coefficient for x indicates that further improvement is possible. Stop only when the appropriate optimality condition is satisfied, not after the first improvement.

9. Second simplex pivot and verification

Let x enter next. The positive x coefficients give ratios 4/1 = 4 in the first row and 6/3 = 2 in the transformed shared row. The smaller ratio is two, so s3 leaves. Divide the shared row by three to obtain x−(2/3)s2+(1/3)s3 = 2. Eliminate x from the other rows. The objective becomes Z+3s2+s3 = 36. The first constraint becomes s1+(2/3)s2−(1/3)s3 = 2, while y+s2 = 6 remains.

All nonbasic objective coefficients are now nonnegative in this convention. Setting s2 and s3 to zero gives x = 2, y = 6, s1 = 2 and Z = 36. This agrees with the graphical result. Always verify against the original model rather than only the final tableau. The activities satisfy both upper bounds and use exactly eighteen shared hours. The objective recomputation is 3 × 2 + 5 × 6 = 36. A common arithmetic error is carrying an incorrect coefficient of s2 into the final objective row. Reperforming the elimination shows that five minus two equals three, which provides a simple independent check of the final expression.

10. Special cases

An infeasible model has no point satisfying all constraints. For example, x ≥ 5 together with x ≤ 4 is contradictory. An unbounded objective can improve indefinitely while remaining feasible. An unbounded feasible region alone does not prove an unbounded objective. Minimising x over x ≥ 0 has an unbounded region but a finite minimum at zero. Distinguish the geometry of the region from the direction of objective improvement.

Alternate optima occur when different feasible points share the best objective value. A zero reduced cost for a suitable nonbasic variable at an optimum can signal an alternative optimal move, though feasibility and degeneracy must be checked. Degeneracy means a basic feasible solution has a basic variable equal to zero. A zero ratio can produce a pivot without objective improvement, and special pivot rules prevent cycling in implementations. If an improving entering column has no positive constraint coefficients under the stated primal simplex setup, no leaving variable limits the increase and the objective is unbounded. These cases are diagnoses of the mathematical model. They may reveal contradictory requirements, missing restrictions or genuine flexibility in the business problem.

11. Greater-than constraints and artificial variables

A greater-than-or-equal constraint can be converted to equality by subtracting a nonnegative surplus variable. Unlike a simple slack variable, this does not necessarily provide a convenient feasible starting basis. Equality constraints can present the same difficulty. Artificial variables may be introduced to construct a starting basis for an auxiliary problem. They are computational devices and have no direct operational meaning in the final business plan.

In a two-phase approach, Phase One minimises the sum of artificial variables to search for feasibility. If the minimum remains positive beyond numerical tolerance, the original model is infeasible. If it reaches zero, remove artificial variables appropriately and proceed to the original objective in Phase Two. A Big-M approach penalises artificial variables in a combined objective, but selecting an excessively large numerical penalty can create computational difficulties. For this chapter's worked model, artificial variables are unnecessary because the nonnegative slack basis is already feasible. Recognising when a simple starting basis exists saves effort. Do not add artificial variables mechanically to every constraint. First inspect inequality directions, right-hand-side signs and whether the proposed initial basic solution satisfies nonnegativity.

12. Sensitivity and business interpretation

Sensitivity analysis asks how the solution changes when objective coefficients or resource limits change. A shadow price describes a local marginal change in optimal objective per unit increase in a constraint's right-hand side, within its valid range and under the model's assumptions. It is not necessarily a market price or an amount the bank should always pay. It should be compared with the actual incremental cost and the permitted range of change.

At the worked optimum, increasing the SME upper bound slightly while keeping shared hours fixed requires reducing x. Since 3x+2y remains eighteen, one extra y reduces x by two thirds. The objective change is five minus three times two thirds, or three value points per extra SME unit, while the same structure remains feasible. Increasing the retail upper bound alone has no immediate value because x is already below that bound. These conclusions are local. Large changes can switch the binding constraints and invalidate the marginal calculation. Report units and the change being considered. A sensitivity statement without a range or model context can be more misleading than simply recomputing the optimisation for the proposed scenario.

13. Integer decisions and practical validation

Ordinary linear programming allows fractional solutions. If the variables represent whole employees, machines or indivisible files, the mathematical optimum may require an integer restriction. Rounding each variable independently can violate constraints or lose substantial value. For example, rounding a resource-intensive activity upward may exceed available capacity. A feasible rounded point is not automatically the best integer solution. Small examples can be checked by enumerating feasible integer combinations, while larger ones need an appropriate integer optimisation method.

The worked optimum happens to be integral, but that coincidence does not remove the need to define variable meaning. Review the proposed plan with operational owners. Are processing coefficients stable, are minimum service obligations represented, and can resources be shared as assumed? If the model excludes an essential quality requirement, adding more high-value activity may degrade actual service. Verify inputs, solve, substitute the answer into every original restriction and interpret unused resources. Then test plausible scenarios. Optimisation identifies the best solution within a specified model. Model validation establishes whether that model is useful for the real decision. These are complementary tasks, and success in one does not automatically establish success in the other.

14. A disciplined solution sequence

For a graphical problem, define variables, write the objective and constraints, draw boundaries, identify the feasible side of each, calculate feasible vertices and evaluate the objective. For a simplex problem, state the tableau convention, establish a feasible basis, choose an entering variable, perform the eligible ratio test and pivot carefully. At each step, preserve equality and nonnegativity. When the stopping condition is reached, translate the variables and slacks back into business units and recompute the objective directly.

Use the interactive laboratory to vary the two objective coefficients while keeping the five feasible vertices fixed. Notice that the best vertex can change even though the resource region does not. If the coefficients become three and two, the shared-resource boundary has constant objective eighteen, creating multiple optima along its feasible segment. If both coefficients are positive, the origin will not be optimal in this example, but that observation is specific to the feasible opportunities. Do not memorise the answer thirty-six without the model. The skill is constructing, solving and interpreting a constrained decision, with enough checks that an attractive numerical result does not conceal an infeasible or misunderstood plan.

Guided exercise: a minimum requirement

Add a requirement to the worked model that at least three retail units must be processed, so x ≥ 3. The earlier optimum at x = 2 is no longer feasible. Because y has positive value, the best y for a given feasible x lies at its available upper limit. At x = 3, the shared constraint allows y = 4.5. The objective is nine plus 22.5, or 31.5. Along the shared boundary, substituting y = 9−1.5x gives Z = 45−4.5x, which decreases as x increases. The continuous optimum under the new requirement is therefore (3,4.5), with value 31.5.

If x and y must be whole units, examine feasible integer choices. At x = 3, y can be at most four, giving value twenty-nine. At x = 4, y can be at most three, giving twenty-seven. The best integer choice is therefore (3,4) with value twenty-nine. Rounding the continuous y upward to five would use nineteen shared hours and violate the eighteen-hour limit. Rounding down happens to give the best integer answer here, but that is established by checking alternatives, not by a universal rounding rule. The exercise demonstrates how one business requirement changes both the feasible set and the optimum. Reuse the old answer only after verifying that it still satisfies every revised restriction and remains best among the revised feasible choices.

Precision check

When checking a proposed allocation, retain full precision until feasibility is established. Rounding intermediate intersections can move a point across a binding boundary. Report rounded values only with enough detail to preserve the intended resource interpretation.

Open the interactive chapter laboratory and offline practice

LEARN THROUGH EXPLANATIONS

Chapter practice

This practice is separate from timed mock tests. Answers and explanations appear after you choose an option.

Your reading progress

Sign in to save your progress across devices.

Browse published timed tests for this paper