Constraints as Equations, Explained with Examples

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

Constraints as Equations

Quantitative Analysis · Chapter 9: Linear and Integer ProgrammingSection 9.1 · lesson 40 of 5512 min · free with a free account

← Across Cultures and BordersNext lesson: Indivisible by Design →

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

Constructing linear programming models from real business problems.

  • Identify variables, objective and constraints
  • Translate a verbal description into an LP model
  • Distinguish the four business LP problem types
  • Formulate a complete multi-resource LP model

Transcript

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

Linear and Integer Programming · Section 9.1

Constraints as Equations

Welcome to section nine point one, Constraints as Equations. Linear programming is the workhorse of quantitative optimisation in business. But before any solver can help you, somebody has to write the model down. That translation step is called formulation, and it is the whole subject of this section. We begin with the four components that every linear programming model contains. Then we look at the four families of problems that recur across industries. After that come four formulation tips that catch the most common errors. Finally, we build a complete model for a two product manufacturer. By the end, you should be able to turn a paragraph of business description into algebra. That skill transfers to every optimisation topic that follows.

The Workhorse

Why Formulation Comes First

Think about the decisions a manager actually faces each week. How many units of each product to produce. What mix of ingredients to use in a blend. How to allocate workers across shifts, or how to route shipments. Every one of those asks how much of several activities to undertake. And every one of them runs into limits, because resources are finite. Linear programming gives a structured, mathematical way to find the best possible plan. Notice the word possible. The plan has to satisfy the constraints, not just look attractive. Formulation is the bridge between the business situation and the algebra. On one side is the business situation, on the other, a structure that graphical, simplex or software methods can solve. Get the bridge wrong, and even the best solver returns a confident but useless answer.

Model Anatomy

The Four Components of an LP Model

Every linear programming model is built from four essential components. This is true regardless of the industry, and regardless of the size of the problem. First, the decision variables: the quantities the manager controls. In a two product plant, x one is units of product A and x two is units of product B. Second, the objective function, a linear function of those variables. It is maximised for profit or revenue, and minimised for cost or time. Third, the constraints, which are linear inequalities or equalities. They restrict the feasible set to plans the firm can actually carry out. Resource limits use less than or equal to, minimum requirements use greater than or equal to, and exact balances use an equals sign. Fourth, non-negativity. In standard linear programming every variable must be at least zero. That is not bookkeeping. It encodes the fact that you cannot produce a negative quantity.

Recognising The Form

Four Families of LP Problems

Linear programming is a general framework, but in practice it appears in four classic forms. Recognising the form helps you identify variables and constraints much more quickly. The first is product mix. The variables are units of each product. The objective maximises profit, and the constraints are machine hours, labour hours and materials. The second is blending. Here the variables are proportions of ingredients. The objective minimises cost, subject to nutritional or quality specifications. The third is scheduling, where the variables are workers assigned to each shift. The objective minimises labour cost, subject to coverage requirements in every time period. The fourth is transportation, with units shipped from each source to each destination. The objective minimises total shipping cost, subject to supply and demand at every node. Transportation has a special network structure and a specialised solution algorithm. For that reason it gets a chapter of its own, chapter twelve.

Avoiding Errors

Formulation Tips: Variables and Sides

Even experienced analysts can produce an invalid model if they skip the verification steps. These tips separate a model that solves cleanly from one that fails or returns nonsense. Tip one. Define one variable for each controllable quantity. That means a separate variable for each distinct product, ingredient, shift or route. Not one variable per category. If a firm makes standard and deluxe chairs, that is two variables, not one variable called chairs. Collapsing them assumes both chairs use resources identically and earn identical profit. The model will still solve. It will simply answer a different question than the one you asked. Tip two. Put the limiting resource on the right hand side of each constraint. Written that way, the constraint reads as machine A usage is at most machine A availability. That habit makes an error visible the moment you read the line back.

Units And Linearity

Formulation Tips: Units and Linearity

Tip three. Check your units on both sides of every constraint. If the left side is expressed in hours, the right side must also be in hours. Not days, not units of output, and certainly not dollars. Get that wrong and the model may still solve, but it answers a nonsense question. Tip four. Verify linearity, because linear programming requires every term to be linear. That rules out multiplying two decision variables together. It rules out powers, such as a variable squared, and it rules out absolute values and piecewise functions. If your formulation contains any of these, it is not a linear program. It is a non-linear program, and it needs entirely different techniques. Linearity and non-negativity are the standing assumptions behind every method in this course. Dropping either one quietly invalidates the solution you get back.

The Workflow

A Repeatable Five-Step Workflow

The same five moves will formulate any linear programming model. They work for a two product workshop and for a refinery with thousands of variables. Step one. Read the problem and note exactly what the manager controls. Step two. Identify the variables, one per controllable quantity, and state their units. Units matter here, because units per week and units per day give different models. Step three. Write the objective, either a maximisation or a minimisation. It must be linear in the decision variables you just defined. Step four. List the constraints, with the resource amount on the right hand side. Then add the non-negativity restrictions, which are easy to forget. Step five. Verify that units match and that no term contains a product or a power. That last step confirms units and linearity, and it costs almost nothing to run.

Worked Example

The Two-Machine Manufacturer

Now let us formulate a complete model from a verbal description. A manufacturer produces two products using two machines. Machine A is available forty hours per week, and machine B is available thirty hours per week. Product one requires two hours on machine A and one hour on machine B. Product two requires one hour on machine A and three hours on machine B. Profit is five dollars per unit of product one, and four dollars per unit of product two. The task is to formulate the linear programming model completely. Step one is simply to organise the data into a table. That is not decoration. Each resource row of the table becomes a constraint. Each product column becomes a decision variable, and the profit row becomes the objective function. Once the table is laid out, the algebra almost writes itself.

Steps Two And Three

Decision Variables and Objective

Step two. Define the decision variables. The manager controls the production quantity of each product, so there is one variable per product. Let x one be the number of units of product one produced per week. Let x two be the number of units of product two produced per week. Notice that each definition carries a unit and a time period. Per week is part of the definition, not an afterthought. Step three. Write the objective function. Total weekly profit is profit per unit multiplied by units produced, summed across products. So the objective is five x one plus four x two. Because profit should be as high as possible, we maximise that expression. Check the shape of it. A single linear function, no products of variables and no powers. That confirms the objective is admissible for linear programming.

Steps Four And Five

Constraints and the Complete Model

Step four. Express the constraints, because each machine has limited weekly hours available. The hours used by both products on a given machine cannot exceed the hours available. On machine A, product one uses two hours per unit and product two uses one hour. So two x one plus x two must be less than or equal to forty. On machine B, product one uses one hour per unit and product two uses three hours. So x one plus three x two must be less than or equal to thirty. Then add non-negativity, because production cannot be negative. Both x one and x two must be greater than or equal to zero. Step five collects all of it into the complete model, and that is the deliverable. Now read the units back on the first constraint. Two hours per unit times x one units gives hours, and forty is also hours. That check takes seconds, and a mismatch there means the constraint is simply wrong.

Step Six

The Feasible Region and Its Corners

Step six. Visualise the feasible region. Plotting both constraints on a graph shows every valid production plan at once. Every point inside the shaded region satisfies both machine limits and non-negativity. Here is the result that makes two variable problems easy. The optimal solution always lies at a corner point, where constraints intersect. So you only need to evaluate the objective at the four corners of this region. At the origin, producing nothing, profit is zero. At twenty units of product one and none of product two, profit is one hundred dollars. At none of product one and ten of product two, profit is only forty dollars. At eighteen units of product one and four of product two, profit is one hundred and six dollars. That is the maximum, and corner C is where the two machine constraints intersect. At that point both machines run at full capacity, with no idle hours on either.

Section Summary

What to Carry Forward

Let us gather what to carry forward from this section. Define one decision variable for each distinct controllable quantity, with clear notation. Write a single linear objective function, either maximised or minimised. Use less than or equal to for limits, greater than or equal to for requirements. Use an equals sign for exact balances. Standard linear programming requires every decision variable to be at least zero. Run the linearity check: no product of variables, no powers, no absolute values. The feasible region is the set of values that satisfy every constraint at once. A corner point is where two or more constraints meet, and the optimum sits at one of them. With two variables you can solve graphically; at any size, simplex or software will do it. Notice that the answer of eighteen and four followed directly from steps two to four. Careful, correct formulation is the most important step in any optimisation project.

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 Constraints as Equations

What are the components of a linear programming model?
Every linear programming model has four parts. Decision variables are the quantities the manager controls, such as units of each product. The objective function is a linear expression to maximize, like profit, or minimize, like cost. Constraints are linear inequalities or equalities describing resource limits, minimum requirements or exact balances. Non-negativity requires every variable to be zero or more, since negative production is impossible.
How do you formulate a linear programming problem from a word problem?
Read the problem and note what the manager controls. Define one decision variable per controllable quantity, with units and a time period. Write a linear objective to maximize or minimize. List each constraint with the resource amount on the right-hand side, then add non-negativity. Finally, check that units match on both sides and that no term multiplies variables together or raises one to a power.
What is an example of a product mix linear program?
A firm makes two products: product 1 uses 2 hours on machine A and 1 on machine B, and product 2 uses 1 and 3 hours. Machines A and B have 40 and 30 hours a week, and profits are $5 and $4 per unit. Maximize 5x_1 + 4x_2 subject to 2x_1 + x_2 \le 40, x_1 + 3x_2 \le 30 and x_1, x_2 \ge 0. The best plan, x_1 = 18 and x_2 = 4, earns $106.
What are common mistakes when formulating a linear program?
A frequent error is collapsing distinct items into one variable, such as a single chairs variable for standard and deluxe chairs that use different resources and earn different profits. Others are mismatched units, such as hours on one side and days on the other, forgetting non-negativity, and including nonlinear terms like products of variables, squares or absolute values. A flawed model may still solve, but it answers a different question.

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 →