Solving for the Best Outcome, Explained with Examples

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

Solving for the Best Outcome

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

← Indivisible by DesignNext lesson: Where the Optimal Lives →

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

Putting linear programming to work on business constraints.

  • Solve a two-variable model graphically at its corner points
  • Tell binding from non-binding constraints, and read slack
  • Convert any model to standard form with slack and surplus
  • Run the simplex algorithm and read its stopping signals

Transcript

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

Linear Programming for Business Decisions · Section 9.3

Solving for the Best Outcome

Formulating a linear programming model is only half the job. At some point somebody has to actually solve it. There are two methods for that, and they are not rivals. The graphical method draws the problem on a flat plane. You can see the answer, which makes it a superb teaching tool. It stops working the moment you have three variables. The simplex method is algebraic, and it scales without limit. It is the engine inside virtually every commercial optimisation solver. By the end you will run both of them on real numbers.

Two Roads, One Answer

Why Linear Programming Needs Two Methods

Section nine point one taught you to build the model. An objective function, decision variables, and a set of linear constraints. Section nine point two examined its geometry, and this section solves it. The graphical method is intuitive and visual, but strictly limited to two decision variables. So it teaches beautifully, and is rarely used in industry. The simplex method was developed by George Dantzig in nineteen forty-seven. Because it is algebraic, the number of variables does not matter. Excel Solver, LINGO, CPLEX and Gurobi all run some form of it. Both methods lean on one deep result, the corner-point theorem. If an optimal solution exists, at least one of them sits at a vertex. Every technique here is an organised search across those corners.

Five Disciplined Steps

The Graphical Method

The graphical method is five steps, and the discipline matters. Step one, plot each constraint as a boundary line, treating every inequality as an equality. To decide which side to shade, test the origin in the original inequality. Step two, shade the feasible region. It is the intersection of every constraint half-plane with the non-negativity restrictions. Only points inside or on that polygon satisfy the whole model at once. Step three, identify the corner points where two boundary lines meet. Solve each pair of equations algebraically for exact coordinates. Step four, evaluate the objective function at every vertex. The largest value wins a maximisation, the smallest wins a minimisation. Step five, classify the constraints: a binding one passes through the optimal vertex as an equality. A non-binding one leaves capacity unused, and that spare amount is the slack.

Worked Example 9.3-A

Product Mix, Solved Graphically

Here is the product-mix problem, with real numbers attached. A manufacturer makes two products. Each unit of the first earns forty dollars of profit, each unit of the second thirty. The first product needs two machine hours and one labour hour. The second needs one machine hour and one labour hour. Daily capacity is forty machine hours and twenty-four labour hours. So we maximise forty x one plus thirty x two. Subject to two x one plus x two at most forty, the machine constraint. And x one plus x two at most twenty-four, the labour constraint. Plus non-negativity, because you cannot make a negative number of units. Plot both lines and the feasible region is a quadrilateral, with four corners.

Worked Example 9.3-A

Evaluate Every Corner Point

Now evaluate the objective function at each of the four corners. At the origin the profit is zero. At twenty and zero it is eight hundred. At sixteen and eight it is eight hundred and eighty. At zero and twenty-four it falls back to seven hundred and twenty. So the third corner wins, and neither single-product corner does. Now classify the constraints there. Two times sixteen plus eight is forty, so the machine constraint is binding. Sixteen plus eight is twenty-four, so the labour constraint is binding too. Both resources are fully exhausted, so the slack on each is zero. Make sixteen units of the first product and eight of the second, for eight hundred and eighty dollars a day. Because both constraints bind, more profit means buying more capacity, and shadow prices price that.

Preparing The Model

From Inequalities to Standard Form

Real business problems have hundreds or thousands of decision variables. An airline scheduling pilots across a network, a refinery blending crude oils. You cannot draw those on paper, and nobody tries. The simplex method walks algebraically from one corner to an adjacent, better one. But it works on equalities, not inequalities. So every constraint is converted by introducing a non-negative variable. A less-than-or-equal constraint gets a slack variable that absorbs unused resource. A greater-than-or-equal constraint has a surplus subtracted, plus an artificial variable to start the algorithm. An equality constraint takes an artificial variable only. That artificial variable has no physical meaning, and must equal zero in any feasible solution. It is driven out using the big M method, or the two-phase method. The slack variable is different: its final value is literally the unused capacity.

The Algorithm

Simplex in Five Steps

The simplex algorithm itself is five steps, repeated until it stops. Step one, set up the initial tableau from the converted equations. Every original decision variable starts at zero, and each slack equals its right-hand side. Geometrically you are standing at the origin, the simplest vertex there is. Step two is the optimality test: read the bottom row of reduced costs. For a maximisation in standard form, you are optimal when every reduced cost is zero or negative. Step three, pick the entering variable with the most positive reduced cost. That is the edge of the feasible region along which you will travel. Step four, the minimum-ratio test picks the leaving variable. Divide each right-hand side by the matching positive entry in the pivot column, and take the smallest ratio. This is the step that stops you at the first constraint you hit. Skip it, and you walk straight out of the feasible region. Step five, pivot with row operations, then go back to the optimality test.

Reading The Ending

Three Ways the Algorithm Stops

The loop can only end in three ways, and you should know all three. The first is optimality. Every reduced cost is zero or negative, and the current tableau holds the answer. The second is unboundedness: every entry in your chosen pivot column is zero or negative. That means the objective can be improved without any limit at all. In practice that almost always means a constraint is missing from the formulation. Real businesses do not have infinite profit, so suspect the model, not your luck. The third is infeasibility. An artificial variable is still positive when the algorithm terminates, so the constraints contradict one another. Everything in between is just one vertex hop to a better neighbour.

Worked Example 9.3-B

Three Variables, One Tableau

Now a three-variable problem, where drawing is no longer an option. A workshop makes three items on a single machine, against a fixed assembly budget. Unit profits are three, five and four dollars. So we maximise three x one plus five x two plus four x three. The first constraint is two x one plus three x two, at most eight. The second is two x two plus five x three, at most ten. The third is three x one plus two x two plus four x three, at most fifteen. Add three slack variables, and the inequalities become equalities. The basic variables are the three slacks, holding eight, ten and fifteen. All the original variables are zero, so the starting profit is zero. The bottom row holds reduced costs of three, five and four, so x two enters.

Worked Example 9.3-B

Pivot One: A Variable Enters the Basis

The entering variable is x two, with a reduced cost of five. Now the minimum-ratio test decides what leaves. Divide each right-hand side by the positive entry in the x two column. Eight divided by three is about two point six seven. Ten divided by two is five, and fifteen divided by two is seven point five. The smallest ratio belongs to the first row, so the first slack leaves. The pivot element is the three sitting where that row and column cross. Divide the whole row by three, then clear the column above and below it. The new solution has x two at eight thirds, the second slack at fourteen thirds. The third slack sits at twenty-nine thirds. Profit climbs from zero to forty thirds, roughly thirteen point three three. But the reduced cost of x three is still four, so the algorithm is not finished.

Worked Example 9.3-B

Pivot Two, and Why We Are Not Done

Pivot two runs the same machinery on the x three column. The first row has a zero there, so its ratio is undefined and we skip it. Fourteen thirds divided by five is fourteen fifteenths, about nought point nine three. Twenty-nine thirds divided by four is twenty-nine twelfths, about two point four two. The smallest positive ratio is in row two, so the second slack leaves. Divide that row by five, and eliminate x three everywhere else. Now x two is eight thirds and x three is fourteen fifteenths. The remaining slack sits at eighty-nine fifteenths. Profit is two hundred and fifty-six fifteenths, about seventeen point zero seven. Two pivots have carried us from zero to just over seventeen. But the reduced cost of x one is eleven fifteenths, still positive, so another pivot would help. Each row says how much of one basic variable is in the solution, and the bottom row says whether a swap is worth it.

Key Takeaways

Choosing the Right Method in Practice

So when should you reach for each method? The graphical method handles exactly two variables, and nothing more. The simplex method handles any size at all. One uses a coordinate plane, the other an algebraic tableau. One is for teaching, the other runs inside industrial solvers. Both find the optimum at a vertex, one visually and one algebraically. Both detect an unbounded problem, but they show it differently. Graphically it is a feasible region that never closes; in the tableau, a pivot column with no positive entries. Infeasibility looks like constraints that never overlap on the plane. In the tableau it is an artificial variable that refuses to leave the basis. Both rest on the same fact: the optimum lives at a corner of the feasible region.

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 Solving for the Best Outcome

How do you solve a linear programming problem graphically?
Plot each constraint as a line by treating it as an equality, and use a test point such as the origin to decide which side to shade. The feasible region is where all shaded half-planes overlap with the non-negativity restrictions. Find each corner point by solving pairs of boundary equations, evaluate the objective at every corner, and pick the best. The method works only for two decision variables.
What is the difference between binding and non-binding constraints?
A binding constraint holds as an equality at the optimal solution, so the resource is fully used and has zero slack. A non-binding constraint has unused capacity, and that spare amount is its slack. For example, maximizing 40x_1 + 30x_2 subject to 2x_1 + x_2 \le 40 and x_1 + x_2 \le 24 gives the optimum (16, 8) with a profit of $880, where both constraints bind.
What are slack, surplus and artificial variables in the simplex method?
The simplex method works with equalities, so each inequality is converted. A less-than-or-equal constraint gets a slack variable equal to the unused resource. A greater-than-or-equal constraint has a surplus variable subtracted and an artificial variable added to start the algorithm. An equality constraint gets only an artificial variable. Artificial variables have no physical meaning and must reach zero, driven out by the big M or two-phase method.
How do you know when the simplex method has finished?
For a maximization in standard form, the tableau is optimal when every reduced cost in the bottom row is zero or negative. If the entering variable's column has no positive entries, the problem is unbounded, which usually signals a missing constraint. If an artificial variable is still positive at the end, the problem is infeasible because the constraints contradict each other. Otherwise the algorithm keeps pivoting, using the minimum-ratio test.

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 →