11/12/2020
Contents
• Transportation Problems
• Assignment Problems
Chapter 3
Transportation and Assignment Problems
Yabibal A. Yabibal A.
Mathematical Model
3.1 Transportation Problems • Xij = number of units shipped from supply point i to demand point
j.
• A transportation problem basically deals with the problem,
i m jn
which aims to find the best way to fulfill the demand of n
demand points using the capacities of m supply points. min
i 1 j 1
c ij X ij
• A transportation problem is specified by the supply, the jn
demand, and the shipping costs. So the relevant data can be s .t . X ij s i ( i 1 , 2 ,..., m )
summarized in a transportation tableau. j 1
• The transportation tableau implicitly expresses the supply and i m
demand constraints and the shipping cost between each
demand and supply point.
i 1
X ij d j ( j 1 , 2 ,..., n )
X ij 0 ( i 1 , 2 ,..., m ; j 1 , 2 ,..., n )
Yabibal A. Yabibal A.
11/12/2020
Balanced Transportation Problem 3.1 Transportation Problems
• If total supply equals to total demand, the problem is said to be • Example 1: Powerco has three electric power plants that supply
a balanced transportation problem: (feasibility assumption) the electric needs of four cities. The associated supply of each
plant and demand of each city is given in the table 1. The cost of
i m j n sending 1 million kwh of electricity from a plant to a city
s d
i 1
i
j 1
j depends on the distance the electricity must travel.
• Determine how much electricity is sent from each plant to each
city to minimize the total cost of shipping from plants to cities.
Yabibal A. Yabibal A.
3.1 Transportation Problems 3.1 Transportation Problems
• Table 1. Shipping costs, Supply, and Demand for Powerco Decision Variable:
Example
• Since we have to determine how much electricity is sent from
From To
each plant to each city;
City 1 City 2 City 3 City 4 Supply (Million
kwh) Xij = Amount of electricity produced at plant i and sent to city j
Plant 1 $8 $6 $10 $9 35
Plant 2 $9 $12 $13 $7 50 X14 = Amount of electricity produced at plant 1 and sent to city 4
Plant 3 $14 $9 $16 $5 40
Demand (Million 45 20 30 30
kwh)
Yabibal A. Yabibal A.
11/12/2020
3.1 Transportation Problems
3.1 Transportation Problems Supply Constraints:
Since each supply point has a limited production capacity;
Objective function:
X11+X12+X13+X14 = 35
Since we want to minimize the total cost of shipping from plants to X21+X22+X23+X24 = 50
X31+X32+X33+X34 = 40
cities;
Demand Constraints:
Minimize Z = Since each demand point receives sufficient power to meet its peak demand;
8X11+6X12+10X13+9X14
X11+X21+X31 = 45
+9X21+12X22+13X23+7X24
X12+X22+X32 = 20
+14X31+9X32+16X33+5X34 X13+X23+X33 = 30
X14+X24+X34 = 30
Yabibal A. Yabibal A.
3.1 Transportation Problems The transportation tableau
Full LP Form:
• The following steps are involved in transportation method
Min Z = 8X11+6X12+10X13+9X14+9X21+12X22+13X23+7X24
+14X31+9X32+16X33+5X34 Step1: Formulate the problem as a model and set up in a matrix
S.T.: X11+X12+X13+X14 = 35 (Supply Constraints) form
X21+X22+X23+X24 = 50
X31+X32+X33+X34 = 40 Step2: Obtain an initial feasible solution by using one of the
X11+X21+X31 = 45 (Demand Constraints)
X12+X22+X32 = 20 following methods
X13+X23+X33 = 30
The North – west Corner method
X14+X24+X34 = 30
Xij >= 0 (i= 1,2,3; j= 1,2,3,4) (Non-negativity cosnstraint) Least cost method/ intuitive method
VOGEL’s Approximation Method(VAM)
Yabibal A. Yabibal A.
11/12/2020
The transportation tableau The transportation tableau
• The following steps are involved in transportation method A Company has three production facilities S1, S2 and S3 with production
capacity of 7, 9 and 18 (in 000’s) units per week of a product respectively.
Step1: Formulate the problem as a model and set up in a matrix The units are to be shipped to four warehouses D1, D2, D3 and D4 with
form demand quantity of 5,8,7 and 14 (in 000’s) units per week respectively.
Step2: Obtain an initial feasible solution by using one of the The transportation costs per unit between factories to warehouses are given
following methods below.
The North – west Corner method T0 Capacity
D1 D2 D3 D4
Least cost method/ intuitive method From (supply)
VOGEL’s Approximation Method(VAM) S1 19 30 50 10 7
Step 3: Test for optimality S2 70 30 40 60 9
S3 40 8 70 20 18
Step 4: Update the solution
Demand 5 8 7 14 34
Yabibal A. Yabibal A.
The transportation tableau The transportation tableau
• Initial feasible solution using the north western method
The Least Cost Method/The Intuitive Approach
To Capacity
From D1 D2 D3 D4 (supply) Number of
occupied cells
19 5 30 2 50 10
must be m+n-1
S1 7
70 30 6 40 3 60 7-1 = 6
S2 9
40 8 70 4 20 14
S3 18
Demand 5 8 7 14 34
The total transportation costs can be calculated as follows
5x19 + 2x30 + 6x30 + 3x40 + 4x70 + 14x20 = 1,015 or
Yabibal A. Yabibal A.
11/12/2020
The transportation tableau The transportation tableau
• Step1: For occupied cells calculate Ui and Vj values by using
Let V4 = 0 then; • Step 2: for unoccupied cell
Ui + Vj = Cij ; U1 + V1 = C11 U1 + V1 = 19 U1 = 10
calculate the opportunity cost
through
U1 + V4 = C14 U1 + V4 = 10 U2 = 60
dij = Cij – (Ui +Vj) d21 = C21 – (U2 +V1)
U2 + V3 = C23 U2 + V3 = 40 U3 =20
U2 + V4 = C24 U2 + V4 = 60 V1 = 9 = 70 – (60 + 9)
d12 = C12 –(U1 = V2) = 70- 69 =1
U3 + V2 = C32 U3 + V2 = 8 V2= -12
= 30 – (10+(-12)) d22 = C22 – (U2+V2)
U3 + V4 = C34 U3 + V4 = 20 V3 = -20
= 30 + 2 =32 =30- (60+(-12))
= 30 -48= -18
d13 = C13 – (U1 + V3) d33 = C33- (U3+V3)
= 50 – (10 – 20) = 70- (20+(-20) = 70
= 50 –(-10 ) = 60
Yabibal A. Yabibal A.
The transportation tableau The transportation tableau
• Step 3: Check if dij < 0 • Step5: in order to maintain feasibility, examine the occupied cell
d22 = -18 in the cell (S2, D2) is indicating that the total with minus signs at the corners of closed loop and select the
transportation cost can be reduced in the multiple of 18 by smallest allocation i .e, 2 the values of this allocation is then
shifting the allocation to this cell. added to the cell (S2, D2) and (S3, D4) which carry a plus sign,
the same value is subtracted from cell (S2, D4) and (S3, D2) which
carry minus sign.
• Step 4: a closed loop is traced along S2 to an occupied cell (S3, D2). A plus
sign is placed in the selected cell (S2, D2) and minus sign in the cell (S3, D2). • Step 6: obtain the improved solution+
Now take the right angle and locate an occupied in the column D4. An
occupied cell (S3, D4) exists on the row S3 and plus sign is placed on it and
back to the starting cell.
Yabibal A. Yabibal A.
11/12/2020
The transportation tableau Special Issues
1. Alternate Optimal Solutions
• Sometimes transportation problems have multiple optimal
solutions giving management alternative options.
2. Degeneracy
• A transportation problem is degenerate when there are two few
occupied cells to enable all the empty cells to be evaluated
making it impossible to determine all of the row and column
index numbers.
• Total Transportation Cost = (5 x19) + (2x10) + (2x30) + (7x40) + (6x8) +
(12x20) = $743
Yabibal A. Yabibal A.
Special Issues Special Issues
3. Unacceptable Routs 5. Maximization
• In some cases, certain origin-destination combinations may be • Some transportation type problems concern profits or revenues
unacceptable. rather than costs. In such cases, the objective is to maximize
rather than to minimize.
4. Unequal Supply and Demand • Such problems can be handled by adding one additional step at
• When such a situation is encountered, it is necessary to modify the start: identify the cell with the largest profit and subtract all
the original problem so that supply and demand are equal. This the other cell profits from that value. Then replace the cell
is accomplished by adding either a dummy column or a profits with the resulting values.
dummy row • These values reflect the opportunity costs that would be
incurred by using routes with unit profits that are less than the
largest unit profit.
Yabibal A. Yabibal A.
11/12/2020
3.2 Assignment Problems 3.2 Assignment Problems
• Assigning problems are a special case of linear programming • Example: Machineco has four jobs to be completed. Each
problems. machine must be assigned to complete one job. The time
• Such problems are characterized by a need to pair items in one required to setup each machine for completing each job is
group with items in another group in a one-for-one matching. shown in the table below. Machineco wants to minimize the
total setup time needed to complete the four jobs.
• Typically, the time or cost required to complete a job or a project
will differ, depending on the machine used for the job or the
staff member doing the project.
• The manager’s goal in such cases is to develop a set of
assignments that will minimize the total time or cost of doing
the work.
Yabibal A. Yabibal A.
3.2 Assignment Problems 3.2 Assignment Problems
• Setup times (Also called the cost matrix) • According to the setup table Machineco’s problem can be formulated as
follows (for i,j=1,2,3,4): Minimize Z 14 X 11 5 X 12 8 X 13 7 X 14 2 X 21 12 X 22 6 X 23 5 X 24
Time (Hours) 7 X 31 8 X 32 3 X 33 9 X 34 2 X 41 4 X 42 6 X 43 10 X 44
s.t. X 11 X 12 X 13 X 14 1
Job1 Job2 Job3 Job4 X 21 X 22 X 23 X 24 1
Machine 1 14 5 8 7 X 31 X 32 X 33 X 34 1
X 41 X 42 X 43 X 44 1
Machine 2 2 12 6 5
X 11 X 21 X 31 X 41 1
Machine 3 7 8 3 9 X 12 X 22 X 32 X 42 1
X 13 X 23 cX 33 X 43 1
Machine 4 2 4 6 10
X 14 X 24 X 34 X 44 1
Xij 0 or Xij 1
Yabibal A. Yabibal A.
11/12/2020
Steps involved in the assignment problem Steps involved in the assignment problem
• Step 1: Formulate the problem in a table form • Step 3:
• Step 2: A. Examine rows successively, until a row with exactly one unmarked
zero obtained and make an assignment to this single zero.
A. locate the smallest element in each row of the given costs table and
then subtract it from each element in each row. B. For each zero value that becomes assigned, eliminate all other zeros in
the same row or column
B. In the reduced matrix obtained from step 2 A, locate the smallest
element in each column and then subtract it from each element of each C. Repeat step 3A and 3B for each column also with exactly single zero
column. values that has not been assigned.
D. if a row or column has two or more unmarked zeros and one cannot
• Step 3: … select by inspection, choose the assigned cell arbitrarily
• Step 4: if the number of assigned cell is equals to the number of
rows or columns then, it is the optimal solution
Yabibal A. Yabibal A.
Example
• Solve the machineco assignment problem manually
Thank you!
Questions?
Yabibal A. Yabibal A.