The transportation problem in combinatorial optimization is to minimize the cost of transporting goods from m origins to n destinations along chosen direct routes from origin to destination. The setting is of given demand at each destination. Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory. ...

If the sum of the supplies at the m sources equals the sum of the demands at the destinations, then the problem is called balanced and the algorithm proceeds as described below. If the problem is not balanced to begin with, it can be balanced by adding a fictitious supply node (when supplies are short) or a fictitions demand node (when excess supplies are available) to balance the problem before applying the algorithm.

Origins are customarily listed along the left side of the table with supply amounts listed along the right side of the table, and Demands are customarily listed along the top of the table with demand amounts listed along the bottom side of the table. Per unit transportation costs are given in small boxes at the top of each cell in the rectangular matrix, where a zero unit cost is used for an unshipped units column (excess supply), and either a zero unit cost or a penalty unit cost is used for a shortage row (deficient supplies). For the square matrix section, see square matrix. ...

Like the more general simplex algorithm, the procedure works in two phases. The first Phase I algorithm allocates supplies to demands using a greedy minimal unit cost approach to generate a feasible solution, which however is not necessarily optimal. Then an optimizing Phase II procedure follows which checks for optimality conditions, and makes cost reducing improvements to the solution in case optimality conditions are violated. The Phase II iterations stop when the optimality conditions are finally met, at which time no further cost reductions are possible. In mathematical optimization theory, the simplex algorithm of George Dantzig is the fundamental technique for numerical solution of the linear programming problem. ... Look up greed in Wiktionary, the free dictionary Greed is a desire to obtain more money or material possessions or bodily satisfaction than one is considered to need. ... In optimization (a branch of mathematics), a candidate solution is a member of a set of possible solutions to a given problem. ... In mathematics, optimization is the discipline which is concerned with finding the maxima and minima of functions, possibly subject to constraints. ...

In the phase II discussion, we refer to Basic cells and Non-basic cells to distinguish between cells which may have positive flow and those which are currently set to zero flow. The transportation problem theorem tells us that the basic cells will always lie in cells which correspond to a spanning tree in the network model for the problem, so there will always be exactly m+n-1 Basic cells. Details of these two phases follow. A theorem is a proposition that has been or is to be proved on the basis of explicit assumptions. ...

Initialization

Step 0: Balance the problem by adding an "unshipped supply" column if supply exceeds demand, or by adding an "shortage" row if demand exceeds supply. Place zero unit costs in an unshipped supply column, and either zero or penalty costs in a shortage row.

PHASE I: Initial Feasible Solution

Step 1: Find the least cost cell with (residual) supply and (residual) demand still positive, and allocate flow to that cell up to the minimum of the residuals for that cell.

Step 2: Decrease residual supply and demand for the allocation in step 1. If all demand is met, go to Phase II. Otherwise, return to step 1.

PHASE II: Reduce costs until optimality conditions are met

Check Optimality Conditions.

Step 3: Compute the dual values for the rows (Ui) and columns (Vj) in the problem by setting the first dual value U1 to zero, and then solving the triangular dual equations one at a time. The dual equations are for the basic cells only, and read

Ui + Vj = Cij

Here Cij is the given unit cost for the cell, and either Ui (the dual value for row i) or Vj (the dual value for column j) is assumed to be already known. Then the other dual value is obtained by a simple subtraction. The spanning tree association for the basic cells guarantees that all row and column prices can be obtained when the first is set to zero, and the dual equations for the basic cells are used in an appropriate order.

Step 4. Optimality conditions are stated in terms of the Reduced Costs for each Non-basic cell, which are defined as follows:

RCij = Cij - (Ui + Vj)

The reduced cost for a non-basic cell represents the net unit cost change which results from bringing cell ij into the solution and making adjustments around the cycle thus created in the basic cells for the current solution (see Step 5). Hence if a RCij is positive, using this cell will cause the total transportation to increase, whereas if a RCij is negative, using this cell will cause the total transportation to decrease. If all of the RCij are nonnegative, in which case optimality conditions are met, then no further cost reductions are possible, so the algorithm terminates. If one or some of the RCij are negative, then further costs reductions may be possible, i.e. optimality conditions are violated, so the algorithm continues with Step 5.

Cost Reducing Solution Adjustment

Step 5. Choose the flow for cell 'ij' having the most negative reduced cost value as the entering variable to the solution. Identify it by placing a (+) sign in that cell. Now, in order to maintain equality in the demand and supply constraints, it is necessary to find basic cells in row i and column j to compensate for the flow increase at cell 'ij'. Place a (-) sign in those cells and continue the process until a complete cycle of (+) and (-) adjustments has been identified. Again, the spanning tree association with the basic set guarantees that there will only be one such cycle, so if you encounter any 'dead ends' during this process (i.e. a row or column without any basic cell to hold a compensating (+) or (-) sign), just back up and try one of the other alternatives. There will be a cycle which has balancing adjustments all around, so just use trial and error until you find it.

Step 6. Once the basic cells in the adjustment cycle have been determined, the amount of adjustment to make is obtained as the smallest flow in the basic cells containing negative (-) signs, call it 'aa' (for adjustment amount). Then add 'aa' to all flows with a (+) sign, and subtract 'aa' from all cells with a (-), and drop the cell going to zero from the basis. If more than one cell goes to zero as a result of this adjustment, only drop one of them from the basis (the one with the highest Cij value) since it is necessary to maintain m+n-1 basic cells in the basis in order to carry out the computation of the dual values. The cost reduction associated with this change in solution is given as the product of the reduced cost RCij for the incoming cell times the amount of flow previously held by the outgoing cell. With the new and improved solution in hand, go back to Step 3 to recheck the optimality conditions.