Where the Optimal Lives, Explained with Examples

UPI Study › Courses › Quantitative Analysis › Free lessons › Lesson 9.4 Free with a free account

Where the Optimal Lives

Quantitative Analysis · Chapter 9: Linear and Integer ProgrammingSection 9.4 · lesson 43 of 5511 min · free with a free account

← Solving for the Best OutcomeNext lesson: Beyond the Printout →

Earn 3 college credits for Quantitative AnalysisRecommended for credit by NCCRS · Math 250 · self-paced · one payment, lifetime access
Enroll in Quantitative Analysis · $250 →Download the syllabus (PDF)

In this lesson

Why extreme points are central to linear programming solutions.

  • Explain why the feasible region of any LP is convex
  • Connect extreme points to basic feasible solutions
  • Distinguish unique, alternative, unbounded, infeasible and degenerate cases
  • Read an LP graph and identify which case applies

Transcript

Everything said in the video, section by section (1,689 words). Read along, or search it.

Linear Programming - Geometry of LP · Section 9.4

Where the Optimal Lives

Welcome to Chapter nine point four of Quantitative Analysis. Where the Optimal Lives. Every linear programme has a feasible set, and that set always has a special shape. That shape decides where the optimum is allowed to sit. It also decides how many optima there are, and whether one exists at all. By the end of this section you will know why the feasible region is always convex. You will connect the corners of that region to basic feasible solutions in the tableau. And you will be able to look at a graph, and name which of the five cases applies.

Convex By Construction

The Shape Every LP Shares

Start with the feasible set. It is the collection of every point that satisfies every constraint at once. In two dimensions that set is a convex polygon. In higher dimensions it is a convex polyhedron, but the idea is identical. Here is the test for convexity. Pick any two points inside the set, and join them with a straight line. If the whole segment stays inside, the set is convex. So why is a linear programme always like this? Because every constraint is linear, and a linear inequality carves out a half plane. The intersection of half planes is convex, always. Convexity is therefore not luck, and not a feature of tidy textbook examples. It follows directly from the linearity that defines linear programming.

Extreme Point Principle

The Optimum Lives at a Corner

Now put a linear objective on top of that convex region. Whenever an optimum exists, at least one optimal solution sits at an extreme point. An extreme point is simply a corner, a vertex of the region. Notice that condition, because it is doing real work: the region must be non empty, and the objective bounded on it. Given that, the interior never holds an isolated optimum. Move in any direction inside a convex set, and a linear function keeps improving. It only stops when it hits a boundary. So the best value has nowhere in the middle to hide. A level set of the objective is called the iso profit line. Slide it as far as it will go in the improving direction. It comes to rest on a corner. That is what makes linear programming solvable, because an infinite set of feasible points collapses to a finite list of corners.

Geometry Meets Algebra

Corners Are Basic Feasible Solutions

Corners are geometry, and the simplex method is algebra, but they describe one object. Every corner of the feasible region is a basic feasible solution in the tableau. At a corner of an n variable problem, exactly n constraints are binding. Binding means the constraint holds with equality, with no slack left over. The variables that remain are called non basic, and they are set to zero. You then solve the binding constraints for the values of the basic variables. An edge of the region is a move between two adjacent basic feasible solutions. That correspondence is exactly what makes the simplex method efficient. It never searches the infinite set of feasible points. It hops from corner to corner along edges, improving the objective at each step. And it stops when no neighbouring corner is any better.

5 Outcomes

Every LP Ends One of 5 Ways

Once you know the optimum lives at a corner, the question becomes which corner. And whether there is one of them, or many. A linear programme has exactly five geometric outcomes. The first two are the healthy cases. A unique optimum, or a whole family of alternative optima. The next two mean something is wrong with the model itself. Unbounded, and infeasible. The fifth is degeneracy, and it is a numerical subtlety rather than a modelling fault. Nothing is wrong with the problem, but the algorithm has to handle it carefully. Learn all five, and an LP graph stops being a picture and becomes a diagnosis.

The Healthy Cases

Unique and Alternative Optima

Case one is the unique optimal solution. The iso profit line, pushed as far as it will go, touches the region at a single vertex. One corner, one answer, no ambiguity. Case two is more interesting. Suppose the objective function happens to run parallel to a binding constraint. Now the iso profit line does not touch a point, it lies along an entire edge. Every point on that edge is optimal, and there are infinitely many of them. The simplex method will hand you one of the two endpoint corners. Do not mistake that for the only answer. Any feasible mix along the edge earns exactly the same profit. That is free flexibility, and a good manager spends it. Smooth the labour schedule, favour a preferred supplier, or choose the most robust point.

When The Model Is Wrong

Unbounded and Infeasible

The next two outcomes are the model telling you that it is broken. An unbounded solution means the region runs on forever in the improving direction. No finite maximum exists, because nothing stops the objective from growing. In the tableau, simplex spots this as a pivot column with all non positive entries. There is no ratio to limit how far the entering variable can rise. In practice, this is almost always a formulation error. A resource constraint, a demand ceiling, or a capacity limit was left out. No real business has infinite profit, so the fault is in the model, not the world. An infeasible linear programme is the opposite failure. The constraints contradict each other, so no point satisfies all of them. Common causes are data entry errors, double counted resources, or minimum demand above maximum supply. To find it, check each constraint on its own, or relax them one at a time. You can also read the artificial variables in phase one of the simplex method.

Degeneracy

When Too Many Constraints Meet

The fifth case is degeneracy, and it is the subtle one. A basic feasible solution is degenerate when too many constraints meet at one vertex. More constraints bind there than are needed to pin that corner down. In two dimensions, two constraints are enough to identify a corner. If a third passes through the same point, that extra one is redundant. In the simplex tableau, degeneracy shows up as a basic variable equal to zero. The danger it creates is cycling. The method swaps one basis for another without improving the objective at all. Left unchecked, it can loop without ever terminating. Bland's rule is the standard fix. Always choose the lowest indexed eligible entering variable, and the lowest indexed leaving variable. That single tie breaking rule prevents cycling and guarantees the method finishes.

Quick Diagnostic

Naming the Case From the Graph

Here is the whole diagnostic, in one pass over the graph. If the iso profit line touches exactly one corner, you have a unique optimum. Take that corner and report it. If the line lies parallel to a binding edge, you have alternative optima. Spend the freedom on a second criterion that the model does not capture. If the region runs on without limit in the improving direction, it is unbounded. Go and find the constraint you forgot to write down. If the constraints contradict each other, the problem is infeasible, so check the data. And if an extra constraint binds at the optimal vertex, you are in the degenerate case. Apply Bland's rule and let the method finish. Two of these readings end the analysis. Three of them send you back.

Exercise

3 Slopes on 1 Feasible Region

Now do the experiment yourself, because this geometry only lands when you draw it. Take the feasible region from section nine point three, or the five corner region A to E from this chapter's figure. Hold that region completely fixed, and draw three different objective functions over it. First, maximise x one plus two x two, with iso profit lines at four, eight and twelve. The optimum lands on the upper left corner, D. Second, maximise two x one plus x two, with lines at four, eight and fourteen. This time the optimum jumps across to corner C. Be careful with the word slope here, because it is easy to invert. The line for x one plus two x two has a gradient of minus one half. The line for two x one plus x two has a gradient of minus two. So the flatter line is the one weighting x two more heavily, and it pulls the optimum up and to the left. Third, maximise x one plus x two. That line has a gradient of minus one, so test it against every edge. In the section nine point three region, edge C to D matches, so every point along C to D is optimal. Finally, at each optimum, list the constraints that bind. Exactly two should bind in two dimensions, and that is the basic feasible solution condition.

Reflection

What Rotating the Line Proves

Step back and ask what actually changed during that exercise. You changed the objective coefficients, and that rotated the iso profit line. Rotating the line is all a change of coefficients can ever do. The feasible region never moved, and it stayed convex throughout. So the optimum still landed on a corner, just on a different one. And when the rotation happened to match a constraint, the optimum smeared along an edge. There is a clean division of labour hiding in that result. The constraints decide which corners exist. The objective decides which of those corners wins. Keep those two jobs separate in your head, and LP geometry stops feeling mysterious.

Carry Forward

Corners, Cases and What Comes Next

Let us gather up what to carry forward. The feasible region of any linear programme is convex, in two dimensions or in many. A linear objective over a convex set always has an extreme point optimum. Corners are basic feasible solutions, with n constraints binding for n variables. A unique optimum means the iso profit line touched exactly one vertex. Alternative optima mean the objective ran parallel to a binding constraint. An unbounded answer almost always means a constraint is missing from your model. An infeasible answer means the constraints contradict, so check the data and the formulation. Degeneracy can make the simplex method cycle, and Bland's rule stops it. Section nine point five reads every one of these conditions off the final tableau, with no plotting at all. Section nine point six then asks how the optimal corner shifts when the numbers change. That is sensitivity analysis, and the corner intuition you built here is what makes it feel inevitable.

About Quantitative Analysis at UPI Study

Quantitative Analysis (Math 250) is a self-paced online course of 55 video lessons in 13 chapters, from decision analysis and simulation to inventory and queuing models, project scheduling, linear programming and transportation models. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Math courses Every course with PRO →

Compare: Statistics vs Quantitative Analysis

Why take it here

Why students take Quantitative Analysis with UPI Study

Decide with numbersQuantitative Analysis teaches the models managers use to decide under uncertainty: decision trees, simulation, inventory and queuing models, project scheduling and linear programming. It is part of many business, management, operations and supply-chain programs.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Quantitative Analysis carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Where the Optimal Lives

Why is the feasible region of a linear program convex?
Each linear constraint defines a half-plane, or a half-space in higher dimensions, and any intersection of half-spaces is convex. Convex means the straight segment joining any two feasible points stays entirely inside the region. So a linear program's feasible set is a convex polygon or polyhedron, a direct consequence of linearity rather than a lucky feature of tidy textbook examples.
Why is the optimal solution of a linear program at a corner point?
If the feasible region is non-empty and the objective is bounded, a linear objective over a convex region reaches its optimum at an extreme point, or vertex. Sliding the iso-profit line in the improving direction, it last touches the region at a corner or along an edge between corners. Each corner is a basic feasible solution, where n constraints bind for n variables, which is why simplex moves from corner to adjacent corner.
What does it mean when a linear program has alternative optimal solutions?
Alternative optima occur when the objective function is parallel to a binding constraint, so the iso-profit line lies along a whole edge of the feasible region. Every point on that edge, including both endpoint corners, gives the same optimal value. The simplex method reports one corner, but managers can use the freedom to pursue goals the model ignores, such as smoother staffing or a preferred supplier.
What is degeneracy in linear programming?
A solution is degenerate when more constraints pass through a vertex than are needed to define it, such as three lines meeting at one corner in two dimensions. In the simplex tableau, it appears as a basic variable equal to zero. Degeneracy can cause cycling, where the method switches bases without improving the objective. Bland's rule, choosing the lowest-indexed eligible entering and leaving variables, prevents cycling.

About the Quantitative Analysis course

How many college credits is Quantitative Analysis?
Quantitative Analysis (Math 250) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Quantitative Analysis cost and what is included?
$250, paid once, with lifetime access: all 55 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Quantitative Analysis take?
It is self-paced with no deadlines. The 55 lessons total about 11 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Quantitative Analysis.

55 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Quantitative Analysis →Download the syllabusEvery course with PRO →
Quantitative Analysis
3 credits · NCCRSEnroll →