DASE7034 Chap.2 Linear Programming Formulation and Geometry
Linear Programming Formulation and Geometry
Linear programming represents a linear objective over a feasible set defined by linear equalities or inequalities and variable domains. Graphical analysis separates feasibility from preference: constraints create accepted half-planes, their intersection is the feasible region and the objective ranks its corner points.
Binding constraints identify active limits, while slack identifies unused capacity.
Build the model from units
Begin by defining each decision variable in operational language and giving its measurement unit. Objective coefficients then express value or cost per unit of activity, while constraint coefficients express resource use, output or requirement per unit.
Multiplying a coefficient by its variable must produce the same unit as the corresponding right-hand side.
This dimensional check catches common formulation mistakes such as mixing hours with minutes, using total demand where demand per activity is required or reversing a capacity inequality.
Use geometry to separate feasibility and preference
For two variables, replace each inequality temporarily by equality to draw its boundary line, test a point to identify the accepted half-plane and retain the nonnegative region when required.
The intersection of all accepted regions is the feasible set. The objective does not decide feasibility; it ranks feasible points.
Candidate corner points come from axis intersections and pairs of binding boundaries, but every candidate must be substituted into every constraint because an intersection can lie outside the common region.
Read the optimum as an operational statement
In a bounded feasible linear program, an optimum occurs at a corner point, although an entire edge can be optimal when its slope matches the objective.
Evaluate the objective consistently and report both the chosen activities and the resulting value. Substitution reveals which constraints bind and the slack in the others.
Binding means no unused amount under the model; it does not automatically mean that purchasing more of the resource is valuable, because that conclusion requires sensitivity information and can change when another constraint becomes limiting.
Diagnose exceptional geometry
An empty intersection means the model is infeasible, so the constraints or data must be reconciled rather than forcing a numerical solution.
An open feasible region is not necessarily unbounded in the objective direction; inspect whether the objective can improve indefinitely along a feasible ray. Redundant constraints do not change the feasible region, but recognising them can clarify the structure.
If activity counts must be whole, the graphical LP optimum remains a relaxation benchmark and nearby integer points must be tested for feasibility rather than obtained by casual rounding.
What this chapter covers
- 01
Linearity assumptions
- 02
Feasible and infeasible solutions
- 03
Graphing half-planes
- 04
Corner-point optimality
- 05
Binding constraints and slack
Worked example · free
Verify a corner optimum
- 2List feasible corner points.
- 3Evaluate the objective at each point.
- 3Substitute the winner into every constraint.
Key terms
- Feasible Region
- The set of all variable values satisfying every constraint and domain rule.
- Corner Point
- A feasible extreme point formed where enough independent constraints bind.
- Slack
- The unused amount of a less-than-or-equal capacity constraint at a solution.
Linear Programming Formulation and Geometry FAQ
Why can an optimum be checked at corners?
For a linear objective over a polyhedral feasible region, any existing optimum has at least one corner-point representative. The objective cannot form an isolated interior peak because its level sets are parallel lines or hyperplanes.
Does every binding constraint have a positive value?
No. Binding means the constraint holds as an equality at the solution. Its marginal value can still be zero when relaxing it does not improve the objective, particularly with degeneracy or redundant active boundaries.
When does a graphical model become unbounded?
If the feasible region extends indefinitely in a direction that improves the objective, the objective line can move without a final point of contact. This usually indicates a missing real-world limit in the formulation.
Exam move
Draw one two-variable feasible region by hand. For each inequality, mark a test point and shade the accepted side. List corners, evaluate the objective and then read every binding constraint aloud. Repeat with one inequality reversed to see how a single direction word changes the decision space. Build a candidate table with one row per axis intercept or pairwise boundary intersection.
Keep exact fractions, substitute every coordinate into every constraint and compute the objective only after feasibility is established. Draw an objective contour and an arrow showing improvement, then compare its slope with each active boundary. This separates a calculated optimum from a point guessed from the sketch.
After solving, translate the geometry back into management information: state activity levels, objective value, binding limits and slack in original units. If an edge is optimal, identify at least two feasible points on it and name a practical secondary criterion that could select between them.
If counts must be whole, label the graphical LP solution as a relaxation and test nearby integer candidates instead of rounding without verification. Finish by changing one right-hand side and predicting how the feasible region moves before redrawing it.
Working through Linear Programming Formulation and Geometry in DASE7034? Sia is AskSia’s AI Mathematics tutor — ask any DASE7034 Linear Programming Formulation and Geometry question and get a clear, step-by-step explanation grounded in how DASE7034 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.