ETF5248 Chap.1 Linear Programming Foundations
Linear Programming Foundations
Linear programming turns a decision into variables, an objective, linear constraints and domains. The formulation must preserve both the business meaning and the units of every quantity.
A two-variable graph then makes feasibility visible: each inequality defines a half-plane, their intersection is the feasible region, and a linear objective reaches an optimum at a corner when an optimum exists.
This chapter builds the complete workflow from words to algebra, checks inequality direction with test points, distinguishes binding constraints from slack ones, and interprets an optimiser as a business action rather than a bare coordinate.
It also explains how infeasibility, unboundedness and multiple optima should be diagnosed instead of hidden.
A reliable formulation is auditable before it is solved. Multiplying a variable's unit by its objective coefficient should produce the objective unit, and doing the same inside a constraint should match the right-hand side.
Non-negativity must be stated when negative activity is meaningless, while free or bounded variables need their real domains. A point found from two boundary equations is only a candidate until it satisfies every other row. If two objective contours are parallel to a feasible edge, more than one point can be optimal; if the improving direction never meets a boundary, the model may be unbounded.
Those outcomes are information about the formulation and business rules, not solver inconveniences. The chapter therefore pairs algebra with geometry and finishes every calculation with a feasibility table. That combination makes it easier to distinguish a wrong numerical answer from a correctly solved but incorrectly formulated model.
What this chapter covers
- 01
Decision variables with units and domains
- 02
Maximisation and minimisation objectives
- 03
Capacity, requirement and balance constraints
- 04
Feasible regions and corner points
- 05
Binding rows, slack and resource use
- 06
Infeasible, unbounded and alternative solutions
Worked example · free
Solve a two-product linear program by corners
- 1Let t and s be non-negative weekly quantities of tables and stools. Maximise Z = 70t + 40s.
- 1Carpentry gives 3t + s no more than 90. Finishing gives t + 2s no more than 60.
- 1The two boundaries intersect at t = 24 and s = 18, using all 90 carpentry hours and all 60 finishing hours.
- 1Axis corners are (30, 0), worth $2,100, and (0, 30), worth $1,200. The origin is worth zero.
- 1The intersection earns $2,400, so it is the best feasible corner under the continuous assumption.
Key terms
- Feasible region
- The set of all points satisfying every constraint and domain restriction.
- Corner point
- A vertex of the feasible region where constraint boundaries meet.
- Binding constraint
- A constraint with no slack at the reported solution.
- Unbounded model
- A model whose objective can improve indefinitely within its stated feasible set.
- Alternative optima
- Two or more distinct feasible solutions that share the same best objective value.
Linear Programming Foundations FAQ
What makes a model linear?
Every objective and constraint expression must be a linear combination of variables with constant coefficients. Products of decision variables, powers, ratios with a variable denominator and logical either-or rules are not linear in their raw form. Constant setup data and fixed right-hand sides are allowed.
How do I choose the inequality direction?
Read the complete row in words and test an obvious point. A resource use cannot exceed availability, so it normally uses a less-than-or-equal sign. A minimum service or nutrition requirement normally uses a greater-than-or-equal sign. Conservation is usually equality because both sides account for the same physical quantity.
Why check every corner in two dimensions?
A bounded linear program with a non-empty polygonal feasible region has an optimum at a corner, although an entire edge can also be optimal. Evaluating all feasible corners provides a transparent hand solution and catches a graph shaded on the wrong side of a boundary.
What should the final sentence contain?
State the decision variable values in their units, the optimal objective value, which constraints bind, and any assumption that affects implementation, such as continuous divisibility. A solver status alone is not a managerial recommendation and does not show that the returned numbers were independently checked.
Exam move
Start every practice problem with a variable dictionary and units. Build one row at a time, naming the resource or requirement before writing coefficients. For graphical questions, find intercepts, test the half-plane, label the feasible polygon and evaluate each corner in a small table. Then recompute the objective and all constraint left-hand sides at the chosen point.
Keep an error log separated into definition, coefficient, sign, domain, arithmetic and interpretation mistakes. This makes revision target the modelling step that actually failed instead of merely repeating the same calculation.
Working through Linear Programming Foundations in ETF5248? Sia is AskSia’s AI Mathematics tutor — ask any ETF5248 Linear Programming Foundations question and get a clear, step-by-step explanation grounded in how ETF5248 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
