Transportation problem

A linear optimization problem that assigns shipments from sources to destinations while satisfying supply and demand constraints and minimizing total transportation cost.

Linear programming: A mathematical method for optimizing a linear objective subject to linear constraints. The transportation problem is a structured linear program with shipment quantities as decision variables.
Supply and demand: The quantities available from sources and required by destinations in an allocation system. These quantities define the row and column totals that shipments must satisfy.
Supply chain: A network of organizations and activities involved in producing and delivering goods or services. Transportation models optimize one recurring allocation task within supply-chain operations.
Shortest path problem: A network optimization problem that finds a minimum-cost path between specified nodes. It routes a single flow along connected arcs rather than allocating quantities across source-destination pairs.
Total unimodularity: A matrix property that ensures linear programs with integral right-hand sides have integral optimal extreme points. The transportation constraint matrix explains why integer supplies and demands can yield integer shipments without integer restrictions.
Transportation tableau: A tabular representation of a transportation problem’s costs, supplies, demands, and shipment allocations. It organizes the data used to find and update feasible shipment plans.
Cost matrix: A rectangular array whose entries give the cost of assigning units between source and destination pairs. Each entry supplies the per-unit coefficient in the objective function.
Facility location problem: An optimization problem that chooses facility locations and assigns demand to them while accounting for costs. It can extend shipment allocation by deciding which sources should operate.
Maximum flow problem: A network optimization problem that maximizes flow from a source to a sink subject to arc capacities. It maximizes throughput, whereas the transportation problem meets fixed demands at minimum cost.
Reduced cost: The change in objective value associated with introducing a variable into a current linear-programming basis. Reduced costs identify unused routes that could improve the current shipment plan.

Linked from 10 pages