Getting Goods Where They Need to Go, Explained with Examples

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

Getting Goods Where They Need to Go

Quantitative Analysis · Chapter 12: Transportation ModelsSection 12.1 · lesson 51 of 5511 min · free with a free account

← Balancing Risk and ReturnNext lesson: Edge Cases and Exceptions →

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

A special-structure linear program for moving goods from many sources to many destinations at minimum total cost.

  • Identify the supply, demand and cost data of a transportation problem
  • Formulate the full LP: variables, objective, constraints
  • Tell balanced from unbalanced, and restore balance with a dummy
  • Recognise the maximisation, assignment and transhipment variants

Transcript

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

Transportation Problems · Chapter 12.1

Getting Goods Where They Need to Go

Every distributor faces the same puzzle every week. Goods sit in several warehouses, and customers are waiting in several places. Shipping between any given pair costs a different amount per unit. So how much should travel along each route? This section builds the model that answers that question. It is called the transportation problem, and it is a linear program with a very particular shape. You will learn to spot its supply, demand, and cost data inside a word problem. Then write the objective, the constraints, and the non-negativity restrictions. You will also meet its three variants, and formulate a full warehouse-to-store example.

The Core Question

From Many Sources to Many Destinations

Start with the situation rather than the algebra. A business has multiple sources of supply: factories, warehouses, distribution centres. It also has multiple points of demand: stores, customers, project sites. The unit cost of moving goods varies by route, and that is what makes the problem interesting. The question is how much to ship from each source to each destination. Total shipping cost should be as low as possible. Every demand must be satisfied, and no source may ship more than it actually has. That is the classical transportation problem, and it is a linear program in disguise. But its structure is so regular that specialised methods beat the ordinary simplex method. The stepping-stone method, MODI, and the network simplex all exploit that structure. In practice the software hides them, whether that is Excel Solver, Python PuLP, CPLEX, or Gurobi.

Given Data

Five Ingredients, and the Formulation Writes Itself

A transportation problem has five clearly-defined ingredients. Once you can name each one in a word problem, the formulation writes itself. First, m supply origins, each with a capacity written s i. Warehouses, factories, plants: anywhere goods start their journey. Second, n demand destinations, each requiring at least d j units. Stores, customers, project sites: anywhere goods are needed. Third, a unit shipping cost c i j for every origin and destination pair. Watch the subscripts, because the order carries meaning. The first is always the origin, the second always the destination. Fourth, the decision variable x i j, the units actually shipped on that route. With m origins and n destinations there are m times n routes, and one variable for each. The objective function and the constraints complete the structure, and we build both next.

Objective Function

Minimise the Cost of Every Route at Once

The objective is the easy part, once the variables are defined. Take one route, and multiply its units by its unit cost. Now do that for every route in the network, and add the results. Minimise Z equals the double sum, over i and j, of c i j times x i j. The double sum simply means loop over origins, loop over destinations, and miss nothing. Look closely at the shape of each individual term. A constant cost, multiplied by a variable quantity. That is exactly what makes the objective linear. The model assumes the cost per unit on a route is fixed. It does not fall when you ship more, and it does not rise. If your real freight rates had volume discounts, the cost curve would bend, and this model would not fit.

The Constraints

Supply, Demand, and Non-negativity

There are three families of constraints, and their directions are not the same. Supply constraints look across a row of the cost matrix. The sum over j of x i j is at most s i. In plain words, origin i cannot ship more than its capacity. Demand constraints look down a column instead. The sum over i of x i j is at least d j. Then non-negativity: every x i j is greater than or equal to zero. You cannot ship a negative number of units. That sounds obvious, but leave it out and a solver will happily invent negative flows. The classic slip is writing both inequalities the same way round. Rows are capped from above, and columns are floored from below.

Balanced Problems

When Supply Exactly Equals Demand

Now a distinction that changes how the problem gets solved. A problem is balanced when total supply exactly equals total demand. Add up every s i, add up every d j, and compare the two totals. If they match, something useful follows immediately. Every unit produced will be shipped, and every unit demanded will be received. So no supply can be left over, and no demand can be overshot. Each at-most constraint and each at-least constraint collapses into a plain equality. Equalities give the specialised algorithms a known feasible structure to work from. That is why balanced problems are the easier case. And it is why the very first thing you do is compare the totals.

Restoring Balance

Unbalanced? Add a Dummy Row or Column

Real data is rarely balanced, and that is not a problem. The fix is a fictitious row or column carrying zero shipping cost. Suppose supply exceeds demand. Add a dummy destination whose demand equals the surplus. Goods shipped there are never actually moved; they represent unsold inventory. Now suppose demand exceeds supply instead. Add a dummy origin whose supply equals the shortfall. Units shipped from it represent demand you simply cannot meet. Try one. Total supply five hundred units, total demand four hundred and twenty. Not balanced. The surplus is eighty units. So add a dummy destination with a demand of eighty, at zero unit cost. The zero cost matters, because a fictitious route must not distort the objective.

Two Variants

Maximisation and Assignment

Three variants keep the network structure but change the objective or the topology. The first is the maximisation transportation problem. Sometimes the coefficients represent profit or revenue per unit shipped, not cost. Then you want the largest total, not the smallest. To reuse the minimisation-based algorithms, convert the matrix first. Replace every coefficient with c max minus c i j. Here c max is the largest profit value anywhere in the matrix. Solving that modified minimisation gives the same optimal shipment plan as the original. The second variant is the assignment problem. It appears when m equals n, and every supply and every demand equals one. Each origin is matched to exactly one destination, and each destination to one origin. Think workers to tasks, machines to jobs, or salespeople to territories. The Hungarian algorithm solves it in polynomial time, and Chapter thirteen covers it fully.

Transhipment

Goods That Pass Through Intermediate Nodes

The third variant is transhipment, and it is the most realistic of the three. Goods rarely travel straight from factory to store. They pass through one or more intermediate nodes on the way. Regional distribution centres, ports, or cross-docks. Each of those nodes gets a constraint of its own, called flow conservation. Total units flowing into the node must equal total units flowing out. A hub stores nothing and creates nothing; it only redirects. Decision variables are now defined on every arc of the network. That includes the arcs entering the hubs and the arcs leaving them. The network grows, but the objective is unchanged. You are still minimising total shipping cost.

Worked Example

Three Warehouses, Four Stores

Time to turn a word problem into a formulation. A regional distributor runs three warehouses, W one, W two, and W three. Weekly supply capacities are one hundred and twenty, eighty, and one hundred units. Four retail stores, S one to S four, need seventy, ninety, eighty, and sixty units a week. The cost matrix gives a unit shipping cost for every one of the twelve routes. From warehouse one it is eight, six, ten, and nine dollars a unit. From warehouse two, nine, twelve, thirteen, and seven dollars. From warehouse three, fourteen, nine, sixteen, and five dollars. Step one is always the balance check, and it comes before anything else. Total supply is one hundred and twenty plus eighty plus one hundred, which is three hundred. Total demand is seventy plus ninety plus eighty plus sixty, also three hundred. The problem is balanced, so every supply and demand constraint becomes an equality.

Variables And Objective

Steps 2 and 3 - Twelve Variables, One Objective

Step two, define the decision variables precisely. Let x i j be the units shipped from warehouse i to store j. Here i runs from one to three, and j runs from one to four. Three times four is twelve, so the model has twelve decision variables. One per route, no more and no fewer. Step three, write the objective function out in full. Minimise Z equals eight x one one, plus six x one two, plus ten x one three, plus nine x one four. Then nine x two one, twelve x two two, thirteen x two three, and seven x two four. And finally fourteen x three one, nine x three two, sixteen x three three, and five x three four. Every coefficient comes straight from the cost matrix, read row by row. There is no arithmetic here yet. Formulation is bookkeeping, and it must be exact.

Constraints And Count

Step 4 - Constraints, and What the Count Tells You

Step four is the constraints, and here the balance check pays off. Each warehouse row sums to its capacity, as an equality. The four variables leaving warehouse one add up to one hundred and twenty. Warehouse two's four sum to eighty, and warehouse three's sum to one hundred. Each store column sums to its demand, again as an equality. The three shipments arriving at store one add up to seventy. Store two receives ninety, store three eighty, and store four sixty. Add non-negativity for all twelve variables, and the model is complete. Now count what you have built. Twelve decision variables, three supply equalities, and four demand equalities. But those seven equalities are not independent of one another. Because the totals already match, one of them follows from the other six. That leaves six independent constraints, which is m plus n minus one. And that number tells you how many basic variables an optimal transportation tableau holds.

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 Getting Goods Where They Need to Go

What is the transportation problem in linear programming?
The transportation problem finds how many units to ship from each of several sources, such as warehouses, to each of several destinations, such as stores, at minimum total cost. Each source has a supply capacity, each destination a demand, and each route a fixed cost per unit. It is a linear program with a regular structure that specialized methods, such as stepping-stone, MODI and network simplex, exploit.
How do you write the objective and constraints of a transportation problem?
With x_{ij} as units shipped from origin i to destination j, minimize \sum_i \sum_j c_{ij} x_{ij}. Each supply constraint caps a row, \sum_j x_{ij} \le s_i, and each demand constraint floors a column, \sum_i x_{ij} \ge d_j, with every x_{ij} \ge 0. A common slip is writing both inequalities in the same direction. With 3 warehouses and 4 stores, there are 12 decision variables.
How do you balance an unbalanced transportation problem?
First compare total supply with total demand. If they are equal, every supply and demand constraint becomes an equality. If supply exceeds demand, add a dummy destination with zero unit costs whose demand equals the surplus; shipments to it represent unsold inventory. If demand exceeds supply, add a dummy origin whose supply equals the shortfall, representing unmet demand. For example, 500 units of supply against 420 of demand needs a dummy demand of 80.
What is a transshipment problem?
A transshipment problem is a transportation model in which goods can pass through intermediate nodes, such as regional distribution centers, ports or cross-docks, instead of traveling straight from source to destination. Decision variables are defined on every arc, including those into and out of the hubs. Each hub gets a flow-conservation constraint requiring total inflow to equal total outflow, and the objective is still to minimize total shipping cost.

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 →