distinguish between transportation problem and assignment problem

Difference between transportation and assignment problems?

Engineeringbro
February 11, 2023
March 10, 2024
3 mins read

Post author: Engineeringbro
Post published: February 11, 2023
Post category: Blog
Post comments: 0 Comments

lets understand the Difference between transportation and assignment problems?

Transportation problems and assignment problems are two types of linear programming problems that arise in different applications.

The main difference between transportation and assignment problems is in the nature of the decision variables and the constraints.

If you’re unable to see the whole table kindly convert the mobile view to the desktop view


Assignment Problem	Minimization or maximization of the cost of transporting goods from one source to another	Maximization of the total profit or minimization of the total cost in assigning tasks to individuals
Nature of problem	Involves transporting goods from sources to destinations	Involves assigning tasks to individuals
Number of sources and destinations	Multiple sources and destinations	An equal number of sources and destinations
Availability and demand	Each source and destination have a supply or demand value	Each task has only one individual who can perform it
Decision variables	Amount of goods transported from each source to each destination	Binary variables indicate whether an individual is assigned a task or not
Constraints	Capacity constraints on sources and demand constraints on destinations	Each individual can only perform one task
Solution method	Transportation simplex method, northwest corner rule, Vogel’s approximation method	Hungarian algorithm, brute force method
Example	Transporting goods from factories to warehouses	Assigning tasks to employees or jobs to machines

Difference between transportation and assignment problems

Additional Different between Transportation and Assignment Problems are as follows :

Decision Variables:

In a transportation problem, the decision variables represent the flow of goods from sources to destinations. Each variable represents the quantity of goods transported from a source to a destination.

In contrast, in an assignment problem, the decision variables represent the assignment of agents to tasks. Each variable represents whether an agent is assigned to a particular task or not.

Constraints:

In a transportation problem, the constraints ensure that the supply from each source matches the demand at each destination and that the total flow of goods does not exceed the capacity of each source and destination.

In contrast, in an assignment problem, the constraints ensure that each task is assigned to exactly one agent and that each agent is assigned to at most one task.

Objective function:

The objective function in a transportation problem typically involves minimizing the total cost of transportation or maximizing the total profit of transportation.

In an assignment problem, the objective function typically involves minimizing the total cost or maximizing the total benefit of assigning agents to tasks.

In summary,

The transportation problem is concerned with finding the optimal way to transport goods from sources to destinations,

while the assignment problem is concerned with finding the optimal way to assign agents to tasks.

Both problems are important in operations research and have numerous practical applications.

Checkout Home page for more informative content and Follow us on facebook for more

Please Share This Share this content

Opens in a new window

Cutting speed: Formula, Calculation, Importance (Examples)

SpaceX’s Historic Polaris Dawn Mission Set for August 26: What to Expect?

What is Traction motor its characteristics

A guide to transportation problems ¶

Classic formulation ¶.

Let $\mathcal{G}$ be a complete bipartite directed graph , with disjoint sets of vertices $\mathcal{S}=\{s_i\}_{i=1}^{m}$ and $\mathcal{D}=\{d_j\}_{j=1}^{n}$ interpreted respectively as supply nodes and demand nodes .

For all $i=1,\dots,m,\;j=1,\dots,n$ let:

$c_{ij}$ represent the (unitary) transportation cost between $s_i$ and $d_j$ and $C=\left(c_{ij}\right)$ the corresponding $m\times n$ matrix
$x_{ij}\geq 0$ represent the amount of product transported between $s_i$ and $d_j$
$S_i$ amount of available product ( supply ) at node $s_i$
$D_j$ amount of required product ( demand ) at node $d_j$

We then define the transportation problem as the linear programming problem of minimize the total transportation cost subject to supply and demand constraints i.e.,

$\min\limits_{x}\sum\limits_{i=1}^m\sum\limits_{j=1}^n c_{ij}x_{ij}$ s.t.

supply constraint : $\sum\limits_{j=1}^n x_{ij}\leq S_i \;\;\forall i=1,\dots,m$
demand constraint : $\sum\limits_{i=1}^m x_{ij}\geq D_j \;\;\forall j=1,\dots,n$

Balancing ¶

We define two quantities that play a crucial role within transportation problem framework: total supply and total demand in the network, respectively expressed as $S^*=\sum_{i=1}^m S_i$ and analogously $D^*=\sum_{j=1}^n D_j$ . The problem is said to be balanced if $S^* = D^*$ and unbalanced otherwise. In case of an unbalanced transportation problem, is convenient to distinguish two cases:

if $D^* > S^*$ the problem is infeasible because there is not enough supply to satisfy the given demand
if $S^* > D^*$ the problem is in turn feasible thanks to the excess supply which makes no harm to any of the constraints

Since in the former case is possible to state a priori that the problem will result in an infeasible one, is convenient to propose a general balancing method for a transportation problem:

if $D^* > S^*$ , we can add a dummy supply which is accountable for unmet demand i.e., a node $s_{m+1}$ such that $S_{m+1}=D^* - S^*$ . In this case, we are expanding costs matrix $C$ by adding a new row. Each of its elements $c_{m+1,j}$ will represent the cost penalty associated with unmet demand for demand node $d_j$ . In a proper supply chain framework, this penalty can be thought as the financial loss for the unmet demand, as well as the buying-in cost for satisfying the (otherwise unmet) demand. In a costs minimization perspective, the higher is $c_{m+1,j}$ the lower will be $x_{m+1,j}$ : this means that we have a first way to influence the shape of the solution according to our (business) needs.
if $S^* > D^*$ , even if the problem would be feasible, is convenient to mirror the above technique by adding a dummy demand accountable for unexploited supply i.e., a node $d_{n+1}$ such that $D_{n+1}=S^* - D^*$ . Again, we are implicitly expanding costs matrix by adding a new column in which each element $c_{i, n+1}$ will represent cost associated with unexploited supply. In a supply chain framework, this can be interpreted as storage cost for excess supply, and all the considerations made above about the relationship with $x_{i,n+1}$ still hold.

In the following we will consider only balanced transportation problems, in which the balancing has might been restored with one of the above procedures. In particular, we will therefore consider both the constraints as equalities. For such a problem the following holds:

Theorem 1 ¶

Given a balanced transportation problem assigned over a complete bipartite directed graph $\mathcal{G}$ , the problem admits at least one feasible solution.

Transportation tableau ¶

distinguish between transportation problem and assignment problem

Transportation problem data are often summarized and visualized on a table called transportation tableau (see picture above). It basically consists in the costs matrix $C$ , with the addition of a bottom row containing the demands and a right column containing the supplies. Moreover, it’s useful also to hold the decision variables $x_{ij}$ as well as the total supply $S^*$ and the total demand $D^*$ .

Heuristics ¶

Based on the transportation tableau, several heuristics have been studied in order to find an initial basic feasible solution to the transportation problem. The most used are:

North West Corner method
Least Cost method
Vogel’s Approximation method

They basically consist in algorithm than can be performed (also) by a human in order to match the problem constraints while distributing product amount amongst each $x_{ij}$ (in a “Sudoku-like” approach) see here . Given an initial basic feasible solution, several techniques can be used to improve it in order to lower the corresponding objective function value (e.g. simplex method, evolutionary algorithms, Hungarian method).

We have seen that a classic transportation problem can be solved through several heuristics, even if possibly not in an optimal way. It’s anyway convenient, whenever possible, to approach it in a LP perspective, mostly to take advantages of all the linear programming techniques and libraries available.

The transportation problem can be approach as:

a classic LP problem with continuous decision variables i.e., $x_{ij}\in\mathbb{R}_{\geq 0}$ ;
an ILP/MIP problem if $x_{ij}\in\mathbb{N}$ i.e., if it’s more convenient to express the decision variables in terms of (integer) number of transports needed to satisfy the constraints. In this case, we must assume that the transportation costs do not depend on the amount of product transported along each route - to preserve linearity - and we also have to properly adjust objective function and constraints formulation to behave accordingly with the change in measurement units.

LP advantages ¶

Sensitivity analysis ¶.

LP formulation and implementation can guarantee several advantages in approaching a transportation problem.

One of them is the sensitivity analysis : defined $x^*$ as the optimal solution (or the set of optimal solutions) and $f$ the problem objective function, the sensitivity analysis leds to study changes in $x^*$ and $f(x^*)$ as functions of problem data.

For example, in the transportation problem framework, one of the sensitivity analysis goal is to answer to questions such as:

how much and how costs decrease when supply increases of 1 unit?
how much and how costs increase when demand increases of 1 unit?

Slack variables ¶

Another advantage of a LP approach is represented by slack variables , which enable the elastic relaxation of a given problem.

For example, we can consider the supply constraint $\sum_{j=1}^n x_{ij}\leq S_i$ for a given supply node $s_i$ . This constraint requires that the amount of product going out from $s_i$ is at most equal to the node capacity i.e., $S_i$ . Another way to monitor such a request is to keep track of the difference $\nu_i:= \sum_{j=1}^n x_{ij} - S_i$ . If $\nu_i\leq 0$ , the constraint has been observed, if $\nu_i>0$ the constraint has been violated.

Having observed so, we can then relax the supply constraint by restating it as follows:

$\sum\limits_{j=1}^n x_{ij}-\nu_i\leq S_i$

where $\nu_i$ is a decision variable taking values in $[0, U_i]$ - called slack variable - which objective is to soften the constraint possibly allowing to excess the given supply $S_i$ .

The main purpose of slack variables is to locate infeasibility causes: if the resolution of the problem seems impossible, we can add one slack variable for each constraint, taking care of adding it also to the objective function multiplying it by a (big) penalty factor. After the successful resolution procedure, whenever a slack variable hits a nonzero value it means that, despite its penalty factor in the objective function, its usage has been crucial to the resolution itself i.e., in making the problem actually feasible.

In general:

for a $\leq$ constraint we should subtract the slack variable from the left side of the constraint i.e., where decision variables are located;
for a $\geq$ constraint we should add the slack variable to the left side of the constraint;
for a $=$ constraint we should split the slack variable in its positive and negative part and respectively add and subtract these components to the left side of the constraint;
the slack variable must be added (if the goal is to minimize) / subtracted (if the goal is to maximize) from the objective function by multiplying it with a (big) penalty factor - to ensure its usage “only if needed”.

If any slack variable has been introduced and has been used in problem resolution, we must refactor the objective function value to restore its meaning with respect to the underlying business framework and units of measurements.

Multi-objective programming ¶

LP framework enables also to address multi-objective problems, in which for example we are interested in chase both $\min f_1$ and $\min f_2$ - we can consider both as minimization objectives thanks to the equivalence $\max(f) = -\min(-f)$ . A more rigorous definition of chasing more objectives can be stated in a Pareto perspective: we could be interested in finding $x^*$ such that, if there exists another $x'$ such that $f_1(x')<f_1(x^*)$ , then $f_2(x')>f_2(x^*)$ . In other words our aim could be find a $x^*$ which is Pareto-optimal i.e., a preferred solution such that any other candidate solution which significantly improves one of the objectives ends up worsening the other see here .

In such cases we can exploit one of the following techniques:

relaxed formulation : address one of the two objectives as the “real” objective of our LP problem, by adding the relaxed version of the other within the problem constraints. For example $\min f_1$ subject to $f_2\leq \varepsilon$ where $\varepsilon$ is an upper bound on $f_2$ known a priori;
elastic formulation : mix the objectives with a convex combination of parameters to encapsulate them into a single objective. For example $\min\lambda f_1 + (1-\lambda)f_2$ where $\lambda\in[0,1]$ controls the weight given to each of the original objectives;
sequential formulation : solve a single objective problem with one of the two objectives, for example $\min f_1$ finding $x^*$ as optimal solution, and then approaching a second single objective problem, for example $\min f_2$ , by adding a constraint to preserve the former optimality i.e., $f_1(x)\leq f_1(x^*)$ .

Problem variations ¶

Transshipment nodes ¶.

The classic formulation can be extended to a more general case where the product goes from the supply nodes to the demand ones through one (resp. $k$ ) layer of intermediary nodes, which is implicitly equivalent to change the underlying graph structure to the union of two (resp. $k+1$ ) complete bipartite graphs which share one set of nodes. In such a case, we refer to the shared layer of nodes with $\mathcal{T}=\{t_k\}_{k=1}^p$ and the problem objective will change as follows

$\min\limits_{x}\sum\limits_{i=1}^m\sum\limits_{k=1}^p c_{ik}x_{ik} + \sum\limits_{k=1}^p\sum\limits_{j=1}^n c_{kj}x_{kj}$

Both the supply and demand constraints must be changed accordingly (since no longer exists a direct connection between $\mathcal{S}$ and $\mathcal{D}$ ), and the transshipment constraint must be added in the following form

$\sum\limits_{i=1}^m x_{ik}=\sum\limits_{j=1}^n x_{kj}\;,\;\;\forall k=1,\dots,p$

assuming no storage is allowed within transshipment nodes.

Sortation centers ¶

The intermediaries of the middle layer can be interpreted also as sortation centers. In this case, a mixture between transportation problem and assignment problem better fits our needs: the classic transportation problem can be applied to the transportation of products between supply nodes and sortation centers, and then an assignment problem can be used to optimize the accountability of sortation centers with respect to final customer demands (this strategy is a simple yet good model of Amazon logistics).

In this case, the problem formulation can be changed as follows

$\min\limits_{x,y}\sum\limits_{i=1}^m\sum\limits_{k=1}^p c_{ik}x_{ik} + \sum\limits_{k=1}^p\sum\limits_{j=1}^n c_{kj}y_{kj}$

where the introduced new decision variables $y_{kj}\in\{0,1\}$ are binary variables which represent the assignment of sortation between $t_k$ and $d_j$ , with corresponding sortation cost $c_{kj}$ . The constraint of such a model are the following:

supply constraint : $\sum\limits_{k=1}^p x_{ik}\leq S_i \;\;\forall i=1,\dots,m$
sortation decoupling : $\sum\limits_{k=1}^p y_{kj} = 1\;\;\forall j=1,\dots,n$
demand constraint : $\sum\limits_{i=1}^m x_{ik} = \sum\limits_{j=1}^n y_{kj}\cdot D_j \;\;\forall k=1,\dots,p$

Multi-commodity transportation ¶

In the case of a transportation problem which involves the transportation of more than one product, the “product” variable can be taken into account in the LP framework switching to a three-dimension tensor of decision variables $x_{ijh}$ , each representing the amount of product $p_h$ transported from $s_i$ to $d_j$ .

Duality ¶

For reference see this article .

An example ¶

Let us consider the following maximization problem $\max 2x_1 + 3x_2$ s.t.

$4x_1 + 8x_2 \leq 12\;\;(1)$
$2x_1 + x_2 \leq 3\;\;(2)$
$3x_1 + 2x_2 \leq 4\;\;(3)$
$x_1, x_2 \geq 0\;\;(4)$

Thanks to nonnegativity constraint (4), we can observe for example that the objective function has an upper bound given by the left side of (1): this ensures that the objective function is bounded by 12. Similarly, the same holds dividing the left side of (1) by 2: we have then a better upper bound on the objective function i.e., 6: this is the inspiration for the following discussion.

Given $f$ the objective function of our LP problem, is then possible to write $f$ as a linear combination of variables $x_j$ i.e., $f(x_1,\dots,x_n)=\sum_{j=1}^nc_jx_j$ , and the same holds for the left side of each constraint, which can be represented by a function $g_i$ such that $g_i(x_1,\dots,x_n)=\sum_{j=1}^na_{ij}x_j\leq b_i$ . As in the above example, we are then interested in finding a linear combination of the given constraints which constitutes an upper bound on $f$ i.e., $f\leq\sum_{j=1}^nd_jx_j\leq M$ where $d_j\geq c_j$ for all $j=1,\dots, n$ . In the example, we are looking for a combination

$d_1x_1 + d_2x_2\leq M$

where $d_1\geq 2$ and $d_2\geq 3$ .

For doing so, we can consider a linear combination $\sum_{j=1}^nd_j(y_1,\dots,y_p)x_j=\sum_{i=1}^py_ig_i(x_1,\dots,x_n)\leq\sum_{i=1}^pb_iy_i=M$ where $y_i\geq 0$ are brand new variables linked with the original constraints. In the example, the linear combination is

$y_1\left(4x_1 + 8x_2\right) + y_2\left(2x_1 + x_2\right) + y_3\left(3x_1 + 2x_2\right) \leq 12y_1 + 3y_2 + 4y_3$

which correspondes to

$\left(4y_1+2y_2+3y_3\right)x_1 + \left(8y_1+y_2+2y_3\right)x_2\leq 12y_1 + 3y_2 + 4y_3$

As per the intro of this section, our goal is to find the best possible upper bound on $f$ i.e., to lower as much as we can the upper bound $M$ which controls $f$ from above while respecting the constraints $d_j\geq c_j$ for all $j=1,\dots,n$ . We have then implicitly defined a new LP problem, corresponding to the original one, i.e. $\min 12y_1 + 3y_2 + 4y_3$ s.t.

$4y_1+2y_2+3y_3 \geq 2\;\;(1)$
$8y_1+y_2+2y_3 \geq 3\;\;(2)$
$y_1, y_2, y_3 \geq 0\;\;(3)$

Dual problem ¶

We have just figured out that a minimization problem corresponds in a “natural way” to a maximization one, and viceversa. In general we have that to a minimization problem $\min b^Ty$ s.t.

$A^Ty\geq c$
$y\geq 0$

corresponds a maximization problem $\max c^Tx$ s.t.

$Ax\leq b$
$x\geq 0$

Given the privileged perspective of the transportation problem framework (minimization), we will call the former primal problem $\mathfrak{P}$ and the latter its dual problem $\mathfrak{D}$ .

Theorem 2 ¶

Any feasible solution of $\mathfrak{D}$ is a lower bound on the objective function of $\mathfrak{P}$ .

Theorem 3 ¶

One of the following holds:

both $\mathfrak{P}$ and $\mathfrak{D}$ are infeasible;
$\mathfrak{P}$ is unbounded and $\mathfrak{D}$ is infeasible;
$\mathfrak{P}$ is infeasible and $\mathfrak{D}$ is unbounded;
both $\mathfrak{P}$ and $\mathfrak{D}$ are feasible. Furthermore, for any $y^*$ solution of $\mathfrak{P}$ and $x^*$ solution of $\mathfrak{D}$ , the equation $b^Ty^*=c^Tx^*$ holds, which means that $\min\mathfrak{P}=\max\mathfrak{D}$ .

Transportation dual problem ¶

A possible formulation of the dual problem of the (primal) classic transportation problem defined above, with equalities constraints, is the following $\max\sum\limits_{j=1}^nD_jv_j-\sum\limits_{i=1}^mS_iu_i$ s.t. $v_j-u_i\leq c_{ij}$

To understand and interpret this dual problem, let us refer to this notes .

Consider the need of transportation expressed by the business stakeholders and modeled with the primal problem.

Imagine now that the business wants to outsource the transportation and finds an external company which offers such a service in a particular way: it offers to buy product at price $u_i$ at each supply nodes, transport it and resell the same amount at demand nodes at price $v_j$ . Since the original transportation cost from $s_i$ to $d_j$ was $c_{ij}$ , from a cost perspective the business should only ensure that $v_j - u_i$ is lower than $c_{ij}$ : the dual constraint represents this condition. From the external company point of view, it represents a condition to be matched to make the proposal appealing for the customer (our business).

The dual objective function represents the net revenue of the external company in managing transportation along the network while satisfying customer constraints in terms of supply and demand.

Extensions to other graph structures ¶

This section goal is to discuss the following question: what happens to Theorem 1 if $\mathcal{G}$ is not a complete bipartite graph anymore? Or, in other words, which are minimal balancing actions needed to ensure problem feasibility at the change of the underlying graph structure?

This is crucial because in a given business framework not all routes between $\mathcal{S}$ and $\mathcal{D}$ might be admissible. In such a case, graph connectivity can be “reduced” and therefore the problem could reveals to be infeasible subject to the given constraint.

Theorem 4 ¶

Consider a feasible transportation problem assigned over a bipartite directed graph $\mathcal{G}$ . For each demand node $d_j$ let $\mathcal{S}^j$ be the set of indices of supply nodes adjacent to $d_j$ . Then we have

$\sum\limits_{i\in\mathcal{S}^j} S_i\geq D_j$

This theorem provides a necessary condition to be checked in order to ensure feasibility for a transportation problem assigned over a generic bipartite graph: the sum of supplies of supply nodes adjacent to a given demand node must be at least equal to the demand of that node. This is a necessary condition which partially overcomes the possibly “insufficient” graph connectivity.

Unfortunately, since Theorem 1 does not hold if $\mathcal{G}$ isn’t complete and Theorem 4 gives only a necessary condition, we are still without a set of sufficient conditions for feasibility of a transportation problem assigned over a generic bipartite directed graph. Given the relationship between graph structure and supply-demand constraints, any useful condition must take into account the flow of product that can be assigned over the network ( max-flow connectivity , min-cut connectivity , etc.).

A custom heuristics ¶

In order to solve a transportation problem over a “generic” graph and to overcome the lack of a proper Theorem to ensure feasibility, a custom heuristics to “balance” the given problem before submitting it to the actual solver is below.

In particular, we search for $\mathcal{D}^i$ (defined similarly to $\mathcal{S}^j$ ) sets for each $s_i$ and define the maximal set of suppliers adjacent to nodes in $\mathcal{D}^i$ , denoting this set as $\mathcal{S}(\mathcal{D}^i)$ . Then we refer to supplier nodes in $\mathcal{S}(\mathcal{D}^i)$ as critical suppliers in the following cases:

if $\left|\mathcal{D}^i\right|=1$ ;
if $\left|\mathcal{D}^i\right|=2$ and $\left|\mathcal{S}(\mathcal{D}^i)\right|=1$ .

We then sum up the supply of all the critical suppliers and create a dummy supply node, adjacent to all demand nodes , accountable for this quantity: this helps preventing the unattainability of the critical suppliers, which might affect problem feasibility.

Resources ¶

TP in Scipbook
Min cost flow problem by OR-tools
TP heuristics
OR for programmers

Transportation, Transshipment, and Assignment Problems

Learning Objectives

After completing this chapter, you should be able to:

To learn more about the book this website supports, please visit its .

and .
is one of the many fine businesses of .

You must be a registered user to view the in this website. If you already have a username and password, enter it below. If your textbook came with a card and this is your first visit to this site, you can to register.
Username:
Password:

'); document.write(''); } // -->

( )
.'); } else{ document.write('This form changes settings for this website only.'); } //-->
		Send mail as:
		'); } else { document.write(' '); } } else { document.write(' '); } // -->
	'); } else { document.write(' '); } } else { document.write(' '); } document.write('
TA email:		'); } else { document.write(' '); } } else { document.write(' '); } // -->
Other email:		'); } else { document.write(' '); } } else { document.write(' '); } // -->

"Floating" navigation?	'); } else if (floatNav == 2) { document.write(' '); } else { document.write(' '); } // -->
Drawer speed:	'; theseOptions += (glideSpeed == 1) ? ' ' : ' ' ; theseOptions += (glideSpeed == 2) ? ' ' : ' ' ; theseOptions += (glideSpeed == 3) ? ' ' : ' ' ; theseOptions += (glideSpeed == 4) ? ' ' : ' ' ; theseOptions += (glideSpeed == 5) ? ' ' : ' ' ; theseOptions += (glideSpeed == 6) ? ' ' : ' ' ; document.write(theseOptions); // -->




1.	(optional) Enter a note here:
2.	(optional) Select some text on the page (or do this before you open the "Notes" drawer).
3.	Highlighter Color:
4.

Search for:
Search in:


Course-wide Content

	Quizzes

	More Resources


Instructor Resources


	Course-wide Content

	Instructor Resources

Operations Research/Transportation and Assignment Problem

The Transportation and Assignment problems deal with assigning sources and jobs to destinations and machines. We will discuss the transportation problem first.

Suppose a company has m factories where it manufactures its product and n outlets from where the product is sold. Transporting the product from a factory to an outlet costs some money which depends on several factors and varies for each choice of factory and outlet. The total amount of the product a particular factory makes is fixed and so is the total amount a particular outlet can store. The problem is to decide how much of the product should be supplied from each factory to each outlet so that the total cost is minimum.

Let us consider an example.

Suppose an auto company has three plants in cities A, B and C and two major distribution centers in D and E. The capacities of the three plants during the next quarter are 1000, 1500 and 1200 cars. The quarterly demands of the two distribution centers are 2300 and 1400 cars. The transportation costs (which depend on the mileage, transport company etc) between the plants and the distribution centers is as follows:

Cost Table	Dist Center D	Dist Center E
Plant A	80	215
Plant B	100	108
Plant C	102	68

Which plant should supply how many cars to which outlet so that the total cost is minimum?

The problem can be formulated as a LP model:

$x_{ij}$

The whole model is:

subject to,

$x_{11}+x_{12}=1000$

The problem can now be solved using the simplex method. A convenient procedure is discussed in the next section.

Book:Operations Research

This chapter begins with an introduction to transportation problem network analysis, which shows how different basic feasible solution methods can be used to solve transportation problems. We have demonstrated three methods to obtain basic feasible solution methods through examples. Next, two methods to obtain the optimum solutions for basic feasible solution methods are discussed through examples. Special cases for transportation problems are also presented. In the second part of this chapter, an assignment problem is discussed, which involves assigning people to tasks. The Hungarian method for solving assignment problems is presented. Various formulations for the problems are provided along with their solutions. All learning outcomes, solved examples, and questions are mapped with Bloom’s Taxonomy levels (BT levels 1–6).

Privacy Policy
Terms & Conditions
Cookie Policy
Taylor & Francis Online
Taylor & Francis Group
Students/Researchers
Librarians/Institutions

Connect with us

Transportation and Assignment Problems

Cite this chapter.

James K. Strayer 2

Part of the book series: Undergraduate Texts in Mathematics ((UTM))

1319 Accesses

Transportation and assignment problems are traditional examples of linear programming problems. Although these problems are solvable by using the techniques of Chapters 2–4 directly, the solution procedure is cumbersome; hence, we develop much more efficient algorithms for handling these problems. In the case of transportation problems, the algorithm is essentially a disguised form of the dual simplex algorithm of 4§2. Assignment problems, which are special cases of transportation problems, pose difficulties for the transportation algorithm and require the development of an algorithm which takes advantage of the simpler nature of these problems.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save.

Get 10 units per month
Download Article/Chapter or eBook
1 Unit = 1 Article or 1 Chapter
Cancel anytime
Available as PDF
Read on any device
Instant download
Own it forever
Compact, lightweight edition
Dispatched in 3 to 5 business days
Free shipping worldwide - see info
Durable hardcover edition

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Unable to display preview. Download preview PDF.

Author information

Authors and affiliations.

Department of Mathematics, Lock Haven University, Lock Haven, PA, 17745, USA

James K. Strayer

You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

Copyright information

About this chapter

Strayer, J.K. (1989). Transportation and Assignment Problems. In: Linear Programming and Its Applications. Undergraduate Texts in Mathematics. Springer, New York, NY. https://doi.org/10.1007/978-1-4612-1009-2_7

Download citation

DOI : https://doi.org/10.1007/978-1-4612-1009-2_7

Publisher Name : Springer, New York, NY

Print ISBN : 978-1-4612-6982-3

Online ISBN : 978-1-4612-1009-2

eBook Packages : Springer Book Archive

Share this chapter

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

Publish with us

Policies and ethics

Find a journal
Track your research

Practice Mathematical Algorithm
Mathematical Algorithms
Pythagorean Triplet
Fibonacci Number
Euclidean Algorithm
LCM of Array
GCD of Array
Binomial Coefficient
Catalan Numbers
Sieve of Eratosthenes
Euler Totient Function
Modular Exponentiation
Modular Multiplicative Inverse
Stein's Algorithm
Juggler Sequence
Chinese Remainder Theorem
Quiz on Fibonacci Numbers

Transportation Problem | Set 1 (Introduction)

Transportation problem is a special kind of Linear Programming Problem (LPP) in which goods are transported from a set of sources to a set of destinations subject to the supply and demand of the sources and destination respectively such that the total cost of transportation is minimized. It is also sometimes called as Hitchcock problem.

Types of Transportation problems: Balanced: When both supplies and demands are equal then the problem is said to be a balanced transportation problem.

Unbalanced: When the supply and demand are not equal then it is said to be an unbalanced transportation problem. In this type of problem, either a dummy row or a dummy column is added according to the requirement to make it a balanced problem. Then it can be solved similar to the balanced problem.

Methods to Solve: To find the initial basic feasible solution there are three methods:

NorthWest Corner Cell Method.
Least Cost Method.
Vogel’s Approximation Method (VAM).

Please Login to comment...

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

LIVE Course for free

Ask a Question

What is the difference between Assignment Problem and Transportation Problem?

operations research

Please log in or register to add a comment.


It is used to optimize the transportation cost.	It is about assigning finite source to finite destination (one source is alloted to one destination).
Number of Source and demand may or may not be equal.	Number of source and number of destination must be equal.
If demand and supply are not equal, then transportation problem is known as Unbalanced Transportation Problem.	If number of rows and number of columns are not equal, then the assignment problem is known as Unbalanced Assignment Problem.
It requires to step to solve: Find Initial Solution using North West, Least Cost or Vogel Approximation Find Optimal Solution using MODI method.	It requires only one step to solve. Hungarian Method is sufficient to find the optimal solutions.

The assignment problem is a special case of the transportation problem. The differences are given below.


1. This is about reducing cost of transportation merchandise	1. This is about assigning finite sources to finite destinations where only one destination is allotted for one source with minimum cost
2. Number of sources and number of demand need not be equal	2. Number of sources and the number of destinations must be equal
3. If total demand and total supply are not equal then the problem is said to be unbalanced.	3. If the number of rows are not equal to the number of columns then problems are unbalanced.
4. It requires 2 stages to solve Getting initial basic feasible solution, by NWC, LCM, VAM and optimal solution by MODI method	4. It has only one stage. Hungarian method is sufficient for obtaining an optimal solution

Find MCQs & Mock Test

JEE Main 2025 Test Series
NEET Test Series
Class 12 Chapterwise MCQ Test
Class 11 Chapterwise Practice Test
Class 10 Chapterwise MCQ Test
Class 9 Chapterwise MCQ Test
Class 8 Chapterwise MCQ Test
Class 7 Chapterwise MCQ Test

Related questions

Welcome to Sarthaks eConnect: A unique platform where students can interact with teachers/experts/students to get solutions to their queries. Students (upto class 10+2) preparing for All Government Exams, CBSE Board Exam , ICSE Board Exam , State Board Exam, JEE (Mains+Advance) and NEET can ask questions from any subject and get quick answers by subject teachers/ experts/mentors/students.

All categories
JEE (36.8k)
NEET (9.4k)
Science (789k)
Mathematics (256k)
Statistics (3.0k)
Environmental Science (5.4k)
Biotechnology (744)
Social Science (127k)
Commerce (75.2k)
Electronics (3.9k)
Computer (22.1k)
Artificial Intelligence (AI) (3.3k)
Information Technology (21.9k)
Programming (13.1k)
Political Science (10.6k)
Home Science (8.2k)
Psychology (4.4k)
Sociology (7.1k)
English (68.3k)
Hindi (30.8k)
Aptitude (23.7k)
Reasoning (14.8k)
Olympiad (535)
Skill Tips (91)
RBSE (49.1k)
General (74.5k)
MSBSHSE (1.8k)
Mathematics (1.5k)
Physics (1.9k)
Chemistry (4.3k)
Bio Botany (1.3k)
Bio Zoology (1.4k)
English (867)
Commerce (1.0k)
Economics (1.5k)
Accountancy (812)
Computer Science (1.2k)
Computer Applications (1.7k)
Applications of Matrices and Determinants (89)
Integral Calculus I (146)
Integral Calculus II (94)
Differential Equations (104)
Numerical Methods (61)
Random Variable and Mathematical Expectation (88)
Probability Distributions (104)
Sampling Techniques and Statistical Inference (81)
Applied Statistics (126)
Operations Research (72)
Class 11 (18.6k)
Class 10 (6.1k)
Class 9 (3.7k)
Class 8 (4.4k)
Class 7 (4.2k)
Class 6 (3.8k)
Kerala Board (24.5k)
Send feedback
Privacy Policy
Terms of Use
Refund Policy

COMMENTS

Difference Between Transportation Problem and Assignment Problem
The transportation problem is commonly approached through simplex methods, and the assignment problem is addressed using specific algorithms like the Hungarian method. In this article, we will learn the difference between transportation problems and assignment problems with the help of examples.
Difference between transportation and assignment problems?
The transportation problem is concerned with finding the optimal way to transport goods from sources to destinations, while the assignment problem is concerned with finding the optimal way to assign agents to tasks. Both problems are important in operations research and have numerous practical applications.
PDF CHAPTER 15 TRANSPORTATION AND ASSIGNMENT PROBLEMS
7. Identify the relationship between assignment problems and transportation problems. 8. Formulate a spreadsheet model for an assignment problem from a description of the problem. 9. Do the same for some variants of assignment problems. 10. Give the name of an algorithm that can solve huge assignment problems that are well
PDF Module 4: Transportation Problem and Assignment problem
Module 4: Transportation Problem and Assignment problem. Transportation problem is a special kind of Linear Programming Problem (LPP) in which goods are transported from a set of sources to a set of destinations subject to the supply and demand of the sources and destination respectively such that the total cost of transportation is minimized.
PDF Unit 4: ASSIGNMENT PROBLEM
The assignment model can be solved directly as a regular transportation model. The fact that all the supply and demand amounts equal 1 has led to the development of a simple solution algorithm called the Hungarian method. Difference between transportation and Assignment problems Sl. No. Transportation Assignment
Assignment Problem: Difference between Transportation Problem ...
In this video, we discuss the introduction of an Assignment problem and the mathematical representation of the Assignment problem.Link For Complete Playlist ...
PDF 9 Transportation and Assignment Problems
44 9 · Transportation and Assignment Problems m ij i,j i P k:(i,k)∈Em ik −b i j P k:(j,k)∈Em jk −b j 0 c ij Figure 9.1: Representation of ﬂow conservation constraints by a transportation problem We now construct a transportation problem as follows. For every vertex i ∈ V, we add a sink vertex with demand P km ik−b i. For every ...
Transportation and Assignment Problems
Describe the characteristics of assignment problems. Identify the relationship between assignment problems and transportation problems. Formulate a spreadsheet model for an assignment problem from a description of the problem. Do the same for some variants of assignment problems. Give the name of an algorithm that can solve huge assignment ...
A guide to transportation problems
In this case, a mixture between transportation problem and assignment problem better fits our needs: the classic transportation problem can be applied to the transportation of products between supply nodes and sortation centers, and then an assignment problem can be used to optimize the accountability of sortation centers with respect to final ...
Transportation, Transshipment, and Assignment Problems
After completing this chapter, you should be able to: Describe the nature of transportation transshipment and assignment problems. Formulate a transportation problem as a linear programming model. Use the transportation method to solve problems with Excel. Solve maximization transportation problems, unbalanced problems, and problems with ...
Operations Research/Transportation and Assignment Problem
The Transportation and Assignment problems deal with assigning sources and jobs to destinations and machines. We will discuss the transportation problem first. Suppose a company has m factories where it manufactures its product and n outlets from where the product is sold. Transporting the product from a factory to an outlet costs some money ...
PDF Transportation and Assignment Problems
Introduction. Transportation and assignment problems are traditional examples of linear programming problems. Although these problems are solvable by using the techniques of Chapters 2-4 directly, the solution procedure is cumbersome; hence, we develop much more efficient algorithms for handling these problems.
Transportation Problems and Assignment Problem
The Hungarian method for solving assignment problems is presented. Various formulations for the problems are provided along with their solutions. All learning outcomes, solved examples, and questions are mapped with Bloom's Taxonomy levels (BT levels 1-6). This chapter begins with an introduction to transportation problem network analysis ...
PDF Chapter5 Thetransportationproblemandthe assignmentproblem
Chapter5 Thetransportationproblemandthe assignmentproblem. r 5The transportation problem and the assignment problemIn this chapter we introduce the algorithms used to solve two specific linear prob-le. nd the assignment problem.5.1 The transportation problemIn the application of linear programming techniques, the transportation problem w.
Transportation and Related Problems
Transportation and Related Problems. In this section, we will discuss several special types of linear programs. These are the transportation problems, the assignment problems, and the transshipment problems. The standard scenario where a transportation problem arises is that of sending units of a product across a network of highways that ...
The Transportation and Assignment Problems
Definition of the Transportation Problem. Properties of the A Matrix. Representation of a Nonbasic Vector in Terms of the Basic Vectors. The Simplex Method for Transportation Problems. Illustrative Examples and a Note on Degeneracy. The Simplex Tableau Associated with a Transportation Tableau. The Assignment Problem: (Kuhn's) Hungarian Algorithm
PDF Transportation, and Assignment Problems
Transportation Problem •To solve the transportation problem by its special purpose algorithm, it is required that the sum of the supplies at the sources equal the sum of the demands at the destinations. If the total supply is greater than the total demand, a dummy destination is added with demand equal to the excess supply, and shipping costs
Transportation and Assignment Problems
Abstract. Transportation and assignment problems are traditional examples of linear programming problems. Although these problems are solvable by using the techniques of Chapters 2-4 directly, the solution procedure is cumbersome; hence, we develop much more efficient algorithms for handling these problems.
Transportation Problem: Definition, Formulation, and Types
Must Check: Difference Between Transporation Problem and Assignment Problem Conclusion. Transportation Problem in operational research is a special kind of linear programming problem, having an objective to find the minimum cost of transportation of goods from m source to n destination.
Transportation Problem
Transportation problem is a special kind of Linear Programming Problem (LPP) in which goods are transported from a set of sources to a set of destinations subject to the supply and demand of the sources and destination respectively such that the total cost of transportation is minimized. It is also sometimes called as Hitchcock problem. Types of Transportation problems:
Difference between Transportation Problem vs Assignment ...
hey everyone,this is sachin here. welcome to my youtube channel - sachin education hub. all commerce notes are provided here. online classes also available :...
Difference Between Transportation Problem and Assignment ...
Difference Between Transportation Problem and Assignment Problems, Easy Explanation, Operations Research
What is the difference between Assignment Problem and Transportation
Transportation Problem: Assignment Problem: 1. This is about reducing cost of transportation merchandise: 1. This is about assigning finite sources to finite destinations where only one destination is allotted for one source with minimum cost