Starting Simple and Improving, Explained with Examples

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

Starting Simple and Improving

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

← Edge Cases and ExceptionsNext lesson: The Assignment Problem →

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

Solving transportation problems from initial feasible solution to optimal plan.

  • Build an initial feasible solution three different ways
  • Trace a stepping-stone loop and read its improvement index
  • Use MODI duals to index every empty cell algebraically
  • Solve a 3 by 4 problem from staircase start to verified optimum

Transcript

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

Transportation Models - Solution Procedures · Section 12.3

Starting Simple and Improving

Transportation problems have a shape that general purpose methods cannot exploit. Supply nodes, demand nodes, and a per unit cost on every single route. That structure is worth so much that specialised algorithms beat the simplex method outright. The standard routine runs in two phases. Phase one builds any allocation that respects supply and demand. Phase two improves it, one shift at a time, until nothing cheaper exists. In this section we compare three ways to start, and two ways to improve. Then we solve a three by four problem end to end, from staircase start to verified optimum.

Two Phase Routine

Why Transportation Gets Its Own Algorithm

Start with why transportation gets its own algorithm at all. Every transportation problem is a linear program, so the simplex method would solve it. But the constraint matrix has a very particular pattern. Each shipment appears in exactly one supply row and one demand column. Exploiting that pattern is what makes the specialised methods faster. The procedure splits cleanly into two phases. Phase one is construction, and any feasible allocation will do. Phase two is testing and improvement, cell by cell. Here is the part learners often get backwards. A poor starting cost is not a mistake. It just means phase two has more iterations to run.

Feasible To Start

What an Initial Feasible Solution Must Satisfy

An initial feasible solution is a modest thing. It is any set of shipments, none of them negative, that clears every supply. The row sums must equal the supplies, and the column sums must equal the demands. Cost does not enter the definition at all. There is one further requirement, and it is easy to overlook. In a balanced problem, the solution occupies exactly m plus n minus one cells. For a three by four problem, that means six occupied cells. The number is not arbitrary. It matches the rank of the simplex basis. With fewer cells the solution is degenerate, and the dual equations no longer pin down every value. The remedy is a tiny epsilon, a zero allocation, placed in an empty cell to restore the count.

Three Constructions

Three Ways to Build the Start

Three classical methods build that starting allocation. The Northwest Corner method is the simplest to describe. Begin at the top left cell and allocate the smaller of the supply and the demand. If demand was satisfied, move right. If supply ran out, move down. Repeat until you reach the bottom right corner. Notice what is missing there. Costs play no part whatsoever. The Minimum Cost method fixes exactly that. At every step it allocates as much as it can to the cheapest cell still available. Vogel's Approximation goes further, and asks a sharper question. For every row and column it computes a penalty: the second lowest cost minus the lowest. That penalty is the price of getting the line wrong, so Vogel serves the largest penalty first.

Speed Against Quality

What Each Method Buys You

So which method should you actually use? Northwest Corner is very fast to set up, and its starting solution is usually poor. Minimum Cost takes a little more effort and lands much closer to the optimum. It is greedy, though, and greed has a failure mode. A cheap cell taken early can lock you into expensive moves later on. Vogel's is the most work per step, and routinely gives the best start. On small problems it often lands on the optimum straight away. Now here is the reassuring part. If you run the improvement phase afterwards, all three converge to the same answer. The choice changes only how many iterations you grind through. For hand work, pick Northwest Corner for speed of setup, and Vogel for fewer iterations.

Trace The Loop

The Stepping-Stone Method

Phase two begins with a single question, asked of every empty cell. Would shipping units through this route reduce the total bill? The classical answer is the stepping stone method. Picture the occupied cells as stones you are allowed to step on. From an empty cell, move along its row until you land on an occupied cell. Turn ninety degrees, move along that column to another occupied cell, and keep alternating. Eventually the path closes back on where it started. Now label the corners of that loop, alternately plus and minus. Add up the signed costs, and you have the improvement index. It is the net cost of pushing one single unit into that empty cell. For a minimization problem, a negative index means the shift saves money, and the most negative cell enters. The shift size is the smallest allocation on a minus corner, because that cell empties first.

Duals Do It Faster

The MODI (u-v) Method

Stepping stone works, but it does not scale. Every empty cell needs its own loop, traced by hand. On a large table that is a great deal of careful pencil work. The MODI method, also called the u v method, gets the same numbers algebraically. Give every row a dual value, and every column a dual value. For each occupied cell, the two duals must sum to that cell's unit cost. Set the first row dual to zero to anchor the system, then propagate outwards. Once the duals are known, the index of an empty cell is its cost minus both duals. No loop tracing at all. You simply read the indices off. State the optimality condition carefully, because it depends on direction. For a minimization problem, you are optimal when every empty cell index is non negative. For a maximization problem, such as maximizing profit, the condition flips to non positive. One loop is still traced, but only for the cell that enters, to size the shift.

Worked Example

A 3 by 4 Problem: Costs, Supplies, Demands

Now the worked example, carried right through to the optimum. Three supply nodes ship to four demand nodes. Supply one holds eighty units, supply two holds sixty, supply three holds seventy. The four demands are forty, fifty, sixty and sixty. Both sides total two hundred and ten units. That matters. The problem is balanced, so no dummy row or dummy column is needed. The costs vary sharply from route to route. Supply three reaches demand four for two per unit, its cheapest route by a wide margin. That same supply three reaches demand three for nine, the dearest cell in the table. With three rows and four columns, a non degenerate solution occupies six cells.

Northwest Start

Step 1: The Staircase Allocation

Start with Northwest Corner, precisely because it ignores costs. It gives us the worst realistic start, and so the most to demonstrate. Begin at the top left. Supply is eighty, demand is forty, so allocate forty. Demand one is satisfied, so step right. Forty units remain at supply one, and demand two wants fifty, so allocate forty. Supply one is now exhausted, so step down. The staircase continues: ten units, then fifty, then ten, then sixty. Six cells are occupied, matching m plus n minus one, so the solution is non degenerate. Multiply each allocation by its unit cost and add them together. The starting total comes to nine hundred and twenty dollars. Look at the second term. Three hundred and twenty dollars on a route costing eight per unit. That is the price of ignoring cost, and it is exactly what phase two goes after.

Iteration One

MODI Finds the First Saving

Now run MODI on that staircase. Set the dual for row one to zero. The cell in row one, column one is occupied and costs four, so column one gets four. The cell in row one, column two costs eight, so column two gets eight. Row two is occupied in column two at a cost of three, so its row dual is minus five. Continuing that way, the row duals are zero, minus five and zero. The column duals come out as four, eight, nine and two. Now index every empty cell: cost minus the row dual minus the column dual. Row one, column three costs six, against duals of zero and nine, so its index is minus three. Row three, column two also comes out negative, at minus one. Any negative index means we are not optimal, and we take the most negative first. So row one, column three enters, and its stepping stone loop touches four cells. The minus corners hold forty and fifty units, so forty units are free to shift. Forty units, saving three dollars each, brings nine hundred and twenty down to eight hundred.

Iteration Two

A Second Pivot Reaches 780

Repeat the whole procedure on the improved plan. The occupied cells have changed, so the duals change with them. Anchor row one at zero once more and propagate. The row duals are zero, minus two and three. The column duals are four, five, six and minus one. Duals can be negative. That is perfectly normal and carries no meaning on its own. Index the six empty cells again. Two are still negative. Row three, column one at minus two, and row three, column two at minus one. The most negative enters, so row three, column one comes in. Its loop runs through row three column three, then row one column three, back to row one column one. The minus corners hold ten and forty units, so only ten units can shift. Ten units, at two dollars each, takes eight hundred down to seven hundred and eighty.

Optimality Reached

Iteration 3: Nothing Left to Gain

One more MODI pass tells us whether to stop. Recompute the duals across the six newly occupied cells. The row duals are zero, minus two and one. The column duals are four, five, six and one. Every empty cell index now comes out positive. Plus three, plus four, plus four, plus eight, plus one, and plus two. For a minimization problem, that satisfies the optimality condition exactly. No shift anywhere can lower the bill, so we stop here. The optimal plan ships thirty units from supply one to demand one, and fifty to demand three. Supply two sends fifty to demand two and ten to demand three. Supply three sends ten to demand one and sixty to demand four. The minimum total cost is seven hundred and eighty dollars. Nine hundred and twenty was eighteen per cent above that optimum, and two iterations closed the gap. A Minimum Cost start would have begun at eight hundred, and a Vogel start at seven hundred and eighty. Time spent on a better start, in phase one, is time you do not spend iterating in phase two.

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 Starting Simple and Improving

What is the difference between the Northwest Corner, Minimum Cost and Vogel's methods?
All three build an initial feasible solution for a transportation problem. Northwest Corner starts at the top-left cell and works toward the bottom-right, ignoring costs, so it is fast but usually poor. Minimum Cost repeatedly fills the cheapest available cell. Vogel's Approximation computes a penalty for each row and column, the gap between its two lowest costs, and serves the largest penalty first, typically giving the best start.
How does the stepping-stone method work?
For each empty cell, trace a closed loop that moves along rows and columns, turning only at occupied cells, and returns to the start. Label the corners alternately plus and minus, starting with plus at the empty cell, and sum the signed costs to get the improvement index, the net cost of shipping one unit through that cell. In a minimization, the most negative index enters, and the shift equals the smallest allocation on a minus corner.
How does the MODI method calculate improvement indices?
MODI, or the u-v method, assigns a dual value u_i to each row and v_j to each column so that u_i + v_j = c_{ij} for every occupied cell, starting by setting u_1 = 0. Each empty cell's index is then c_{ij} - u_i - v_j, with no loop tracing. A minimization solution is optimal when every index is non-negative; a loop is traced only for the entering cell, to size the shift.
Does the starting method change the final transportation solution?
It does not change the minimum total cost, only how many improvement iterations are needed, because running the improvement phase to optimality reaches the same optimum from any feasible start. In one 3 by 4 problem, a Northwest Corner start cost $920 and needed two improvement iterations to reach $780, while a Minimum Cost start began at $800 and a Vogel start landed on $780 directly. With tied optima, different starts can end on different plans of equal 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 →