Linear problems made visual
About this app
Understand and solve linear problems graphically — explore objective function, constraints and feasible region interactively.
The problem
A linear program looks for the maximum or minimum of a linear objective z = c₁x₁ + c₂x₂ subject to linear constraints such as a₁x₁ + a₂x₂ ≤ b and x₁, x₂ ≥ 0. With two variables it can be solved in the plane. Each constraint is a line that splits the plane into a feasible and an infeasible half. The intersection of all feasible halves is the feasible region, a convex polygon. Points with the same objective value lie on parallel lines. If an optimum exists, it is always attained at a vertex of the feasible region.
What the app shows
In the model panel you enter the objective with max or min and as many constraints as you like; “+ C” and “− C” add or remove them. Each constraint appears as a coloured line, the feasible region is shaded and the optimal vertex marked. The F-value moves the dashed objective line in parallel across the plane. The formula panel shows the model in mathematical notation. If the feasible region is empty, the app reports the problem as infeasible.
Try it yourself
Increase the F-value until the objective line just touches the feasible region: that is the optimum, and it is a vertex. Then change the objective coefficients and watch the optimum jump from vertex to vertex. When the objective becomes parallel to an edge, every point on that edge is optimal. Add a constraint that empties the region and see how the app responds.
Frequently asked questions
- How do you solve a linear programming problem graphically?
- Draw each constraint as a line and shade the feasible region. Then slide a line of the objective function in parallel until it just touches the region. The point of contact, usually a vertex, is the optimal solution.
- Why is the optimum of a linear program at a vertex?
- The objective is linear, so its level sets are parallel lines. Moving them towards better values, they leave the convex feasible region last at a vertex or along a whole edge. In both cases at least one vertex is optimal.
- What does it mean when a linear program is infeasible?
- No point satisfies all constraints at once; the feasible region is empty, so there is no solution. This differs from an unbounded problem, where the objective value can grow without limit.
- Can I enter my own problems in the app?
- Yes. You choose max or min for the objective and enter constraints with coefficients and right-hand side. Constraints can be added and removed, and the graph updates immediately.
Subject: Operations research
More from Operations research
- Big M: Nebenbedingungen an- und ausschalten
- Dijkstra's algorithm
- Ganzzahlig ist anders: LP gegen IP
- Konvexe Mengen, Hülle und Ecken
- Nebenbedingungen verschärfen (Tightening)
- Simplex in space
- Simplex algorithm
- Tabu search on a small TSP
A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps