UPI Study › Courses › Quantitative Analysis › Free lessons › Lesson 12.2 Free with a free account
Edge Cases and Exceptions
Quantitative Analysis · Chapter 12: Transportation ModelsSection 12.2 · lesson 52 of 5511 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Quantitative Analysis.
Lesson complete
Earn the 3 college credits for Quantitative Analysis
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Starting Simple and Improving →← Getting Goods Where They Need to GoNext lesson: Starting Simple and Improving →
In this lesson
Tackling non-standard scenarios in transportation problem-solving.
- Balance unbalanced problems with a dummy origin or destination
- Block prohibited routes with the Big-M cost method
- Convert maximisation to minimisation using opportunity losses
- Diagnose degeneracy and read multiple optimal solutions
Transcript
Everything said in the video, section by section (1,601 words). Read along, or search it.
Transportation and Assignment Models · Section 12.2
Edge Cases and Exceptions
Welcome to Section twelve point two of Quantitative Analysis. Edge Cases and Exceptions. Chapter twelve has given you a very tidy transportation model so far. Total supply equals total demand. Every route is open. The objective is cost. Real problems break all three of those conditions, routinely. So this section takes each break in turn, and gives you the standard repair. You will balance an unbalanced problem with a dummy row or column. You will block a forbidden route with a very large cost, written capital M. You will flip a profit-maximising problem into a cost-minimising one. And you will diagnose degeneracy, and read the meaning of a tie at the optimum.
One Logic, Four Fixes
The Textbook Model Is Rarely Enough
Start with what the classical transportation model quietly assumes. It assumes total supply exactly equals total demand. It assumes every origin can ship to every destination. It assumes the objective is to minimise cost, never to maximise profit. And it assumes a solution always has the right number of occupied cells. In practice, almost none of that holds. A factory may produce more than the market currently wants. A regulator may block one shipping lane outright. A manager may care about margin, not about freight cost. Here is the pattern worth memorising. Every fix turns the odd problem into an ordinary one. Then the usual algorithm runs unchanged, and never knows anything unusual happened.
Balance First
Unbalanced Problems and the Dummy Node
A transportation problem is balanced when total supply equals total demand. Northwest Corner, Least Cost, Vogel's Approximation and MODI all assume that. So when the totals differ, you restore balance before you solve anything. Case one is excess supply, where total supply exceeds total demand. You add a dummy destination whose demand is exactly the surplus. Every shipping cost into that dummy column is zero. That zero is not a modelling convenience. It is economically honest. Unsold inventory has no transport cost, because it simply stays where it is. Case two is excess demand, and it mirrors the first exactly. You add a dummy origin whose supply is exactly the shortage quantity.
Zero Or Penalty
The Dummy Row Is a Report, Not Waste
The dummy row or column is not waste. It is a report. After you solve, it tells you exactly where the imbalance landed. For a dummy origin, use zero cost if you do not mind which customer goes short. Use a large penalty cost, capital M, if you do mind. And you can vary that penalty across the dummy row, cell by cell. Charge a high penalty in a key customer's column, and the algorithm serves that customer first. That is a real managerial lever, hiding inside an artificial row. Take a quick example. Three plants supply thirty, twenty-five and thirty-five units. That is ninety units of capacity, against market demand of only seventy. So a dummy destination absorbs the twenty-unit surplus, at zero cost from every plant.
Prohibited Routes
Blocking a Lane with Big-M
Now the second edge case. A route that simply cannot be used. The reason may be physical, like no rail siding at the warehouse. It may be regulatory, such as hazardous goods rules or export restrictions. Or it may be commercial, where a contract excludes a particular customer. Your instinct is to delete the cell from the tableau. Resist it. The algorithm needs every cell in play, in case an iteration must route through it. So instead of deleting the cell, you make it unattractive. Assign it a deliberately huge shipping cost, written capital M. Because the algorithm minimises, it will then avoid that cell on its own. How large should M be? Large enough to dominate every real cost in the tableau. A safe default is ten times the largest real cost in the problem.
Maximisation
Flipping Profit into Opportunity Loss
Third edge case. The objective points the wrong way. Every standard transportation algorithm minimises. None of them maximise. So when you want to maximise profit or contribution margin, you convert first. Find the largest profit anywhere in the matrix, and call it capital M. Then replace every cell by that largest profit minus the cell's own profit. The result is an opportunity-loss matrix, and you minimise it instead. The most profitable cell now carries a loss of zero, making it the cheapest cell. Minimising total opportunity loss is mathematically equivalent to maximising total profit. Here is a small conversion. Row one is fifteen, twenty, eighteen. Row two is twenty-two, seventeen, twenty-five. Row three is nineteen, twenty-three, sixteen. The largest profit anywhere is twenty-five, so subtract every entry from twenty-five. Row one becomes ten, five, seven. Row two becomes three, eight, zero. One warning. The minimised total is not your answer. Substitute the allocations back into the original profit matrix.
Degeneracy
Too Few Occupied Cells
Fourth edge case, and the one students most often miss. A basic feasible solution needs exactly m plus n minus one occupied cells. That number is not arbitrary. It is the rank of the constraint matrix. One equation is always dependent, because total supply equals total demand. So a three by four tableau needs three plus four minus one, which is six. A three by three tableau needs five. A three by five tableau needs seven. Fewer than that, and the solution is degenerate. Stepping-stone and MODI then stall, unable to compute the improvement indices. The reason is that the dual values are under-determined. The repair is small, and slightly sneaky. Pick an empty cell with a low cost. It must sit in an independent position, closing no loop with the occupied cells. Put a vanishingly small quantity there, called epsilon, and treat it as a real allocation. In the final answer you read it as zero. Nothing actually ships.
Multiple Optima
When a Zero Index Is a Free Lever
When the algorithm stops, you compute one number for every empty cell. It is called the improvement index, or the opportunity-cost coefficient. If every index is strictly positive, your optimum is unique. If any index is exactly zero, something more interesting has happened. A second allocation pattern exists with exactly the same total cost. To produce it, run one more stepping-stone iteration on that zero-index cell. The tableau you land on is the alternative optimum, and any blend of the two is optimal too. Students often treat a tie like this as an inconvenience. It is the opposite. Alternative optima hand the manager flexibility that costs absolutely nothing. Perhaps the second plan uses a preferred supplier, frees critical equipment, or balances driver workload. A zero index is a lever for every preference the cost matrix never captured.
Worked Case
A 3 x 4 Problem with Two Wrinkles
Now put all of it together on a single problem. This is the three by four case from Section twelve point one, with two wrinkles. Warehouse one holds thirty-five units, warehouse two fifty, and warehouse three forty. That is one hundred and twenty-five units of supply in total. The four stores demand thirty, twenty-five, twenty and forty units. That totals one hundred and fifteen, so supply exceeds demand by ten units. That is the first wrinkle. The problem is unbalanced, with excess supply. The second wrinkle is a blocked lane. The route from warehouse two to store three is prohibited. It is a regulatory restriction on hazardous goods crossing a state line.
Balance And Block
Two Transformations, One Standard Tableau
The first move is to balance the problem. Supply of one hundred and twenty-five exceeds demand of one hundred and fifteen. The gap is ten units, so add a dummy destination with demand ten. Its shipping cost is zero from every warehouse. The second move is to block the prohibited route. Replace the warehouse two to store three cost with capital M. The cell stays in the tableau. Only its cost changes. Look at what those two small moves have produced. The tableau is three rows by five columns, and supply now equals demand. Every cell carries a cost, and no route has been deleted. It is an ordinary balanced problem. Start it with Vogel's method, then iterate.
Solve And Verify
The Optimal Plan, Checked Twice
Here is the optimal allocation for the modified tableau. Warehouse one ships fifteen units to store two, and twenty to store three. Warehouse two ships thirty to store one, ten to store four, and holds ten in the dummy column. Warehouse three ships ten to store two, and thirty to store four. Now check it twice. First the cell count: seven cells are occupied. A three by five tableau needs three plus five minus one, which is seven. So the solution is not degenerate, and the dual values are well defined. Second, the prohibited cell is empty, exactly as Big M intended. The total cost comes to eight hundred and seventy. One honest note about the allocation table printed in the source. Its numbers add up to nine hundred and seventy, not eight hundred and seventy. A MODI check also gives one empty cell an index of minus seven. That is this section's own lesson. Always verify the count and the indices.
Decision Flow
Four Checks Before You Solve
Read the answer back as a manager, not as an algorithm. The plan ships one hundred and fifteen units and meets every real demand. Ten units stay put at warehouse two, held as ending inventory. That is what the dummy column actually means out in the warehouse. If holding them is expensive, put a holding cost in the dummy column and solve again. So here is the whole section as a checklist, in order. First, compare total supply with total demand, and add a dummy if they differ. Second, look for blocked routes, and load any blocked cell with capital M. Third, check the direction of the objective, and convert profits into opportunity losses. Fourth, count the occupied cells, and insert an epsilon if you are short. After those four checks, the problem is in standard form. Then every classical method runs unchanged, and produces a plan you can actually use.
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
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 UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks 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 Edge Cases and Exceptions
How do you handle a prohibited route in a transportation problem?
How do you convert a maximization transportation problem to minimization?
What is degeneracy in a transportation problem, and how do you fix it?
What does a zero improvement index mean in a transportation solution?
About the Quantitative Analysis course
How many college credits is Quantitative Analysis?
How much does Quantitative Analysis cost and what is included?
Which universities accept UPI Study credits?
How long does Quantitative Analysis take?
How are the exams done?
How do my credits reach my college?
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.
3 credits · NCCRSEnroll →