Scribd
Upload
22 views

Lec 4 - Transportation and Assignment Model

The document discusses transportation and assignment models. It provides basics on transportation models including representing supply and demand nodes and arcs between them. It also covers formulating transportation models as linear programs and solving them using the transportation simplex algorithm or method of multipliers. Additionally, it briefly introduces assignment models as a variant of transportation models.

Uploaded by

Ifeanyi Snyders
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
22 views

Lec 4 - Transportation and Assignment Model

The document discusses transportation and assignment models. It provides basics on transportation models including representing supply and demand nodes and arcs between them. It also covers formulating transportation models as linear programs and solving them using the transportation simplex algorithm or method of multipliers. Additionally, it briefly introduces assignment models as a variant of transportation models.

Uploaded by

Ifeanyi Snyders
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

Transportation and Assignment Models (chapter 5)

Dr. GJ Oyewole
School of Mechanical, Industrial and Aeronautical Engineering
University of the Witwatersrand

1
Transportation Model basics
 LP special case
 All constraints equality (classical)
 One basic commodity ( newer extensions)
 m sources to transport to n destinations -
represented by nodes
 Routes linking supply to demand = arcs
 Arc(𝑖𝑖, 𝑗𝑗) from source 𝑖𝑖 to destination 𝑗𝑗
 Transportation costs associated with arc = 𝑐𝑐𝑖𝑖𝑖𝑖
 Cost per unit (𝑐𝑐𝑖𝑖𝑖𝑖) x number of units (𝑥𝑥𝑖𝑖𝑖𝑖)

2
Transportation Model basics

• If demand = supply, problem is balanced, otherwise add a


dummy supply / destination with 0 cost to balance
• Transportation problems are a sub-type of the minimum cost
capacitated network model (Ch22.1)
• LP that can be formulated and solved with a simpler variant
of the simplex algorithm
• Number of basic variables must be = m (sources) +
n (destinations) -1 (even if some have a value of zero!)

3
Transportation Model Formulation and Representation

4
Transportation Model Tableau

Example transportation tableau


right top
corner cij

supply
per
source i
ai

current
value of
xij

demand per
destination j - bj

5
Solving the Classical Transportation Problem
( Transportation Algorithm)

6
Solving the Classical Transportation Problem

• After computing penalties allocate as much as


possible to least cost unit and break ties arbitrarily
• If row/column are satisfied arbitrarily select one and
assign zero to the other row/column

Stopping
Re-compute criteria 7
penalties
Improving the Starting solution by method of
multipliers

• 𝑢𝑢𝑖𝑖 + 𝑣𝑣𝑖𝑖 = 𝑐𝑐𝑖𝑖𝑗𝑗 • 𝑢𝑢𝑖𝑖 + 𝑣𝑣𝑖𝑖 ≥ 𝑜𝑜𝑜𝑜 ≤ 𝑐𝑐𝑖𝑖𝑗𝑗


• Rooted in
duality theory • Select highest positive : minimization 8
objective
Step 3. Determine the leaving variable
• Start with the new entering basic variable, assign xij = θ
• Find a closed loop through the basic variables, alternating row / col
moves
• Assigned values become alternating xij - θ ; xij + θ .
• Make sure all new values are xij - θ ≥ 0
• Calculate biggest allowable value for θ - the cell with the first limit is
the leaving variable – more than one, pick the one with the highest
cost

9
Assignment Model

• For each workers 𝑖𝑖 ( 𝑖𝑖 = 1 𝑡𝑡𝑡𝑡 𝑁𝑁), only


one job can be done.
• For each jobs 𝑗𝑗 ( 𝑗𝑗 = 1 𝑡𝑡𝑡𝑡 𝑛𝑛 ) only one
• Variant of transportation one worker can be chosen
model
• Source = worker
10
• Destination => jobs
Solving the Assignment Model

11
Tutorial questions
• See the Ulwazi Course page

12

You might also like