Network Models in Transportation Problems
Translated by
ScribdTranslationsNetwork Models in Transportation Problems
Translated by
ScribdTranslationsQuantitative methods
Teacher: Diana Carolina Ríos Echeverri
dianarios@[Link]
Module 2:
Distribution and network models
Amodel of networks that can be represented by a
a set of nodes, a set of arcs, and a set of
functions (costs, offers, demands) that are associated with the
arcs and/or to the nodes.
Transportation, allocation, and problems transshipment are
examples of network problems.
Each of the three presented models can be formulated
how to solve a linear program with its own algorithms
linear programming.
Content
Transportation problem
Transportation problem
It arises from the need to address the distribution of products and services.
from various supply sites to various demand sites.
…
Transport problem
Typical application:
A company has several plants where it manufactures a product.
determined that they need to send to their clients (or perhaps, to centers of
distribution). How much should each plant send to each customer for
minimize the total cost? Linear programming can provide the answer.
This type of linear programming problem is called a problem of
transporte.
Exercise 1
La Big M Company produce varias máquinas de trabajo pesado endos fábricas. Una de
These machines are a large lathe. Three customers have placed orders to buy.
some the following month.
The lathes will be shipped individually, the following table shows what will be
cost of shipping each one from each plant to each customer. This table also
show how many each customer has ordered and how many each factory will produce.
Now, the distribution manager of the company wants to determine how many machines
send from each factory to each customer to minimize the total shipping cost.
Exercise 1
Exercise 1
Node
Arch
This graph is a network
Transportation problem
Each origin and destination is represented by
every possible shipping route is identified
through an arc.
Exercise 1
1. Decision variables
SF1-C1 = number of lathes shipped from factory 1 to customer 1
SF1-C2 = number of toruses shipped from factory 1 to customer 2
SF1-C3 = number of lathes shipped from factory 1 to customer 3
SF2-C1 = número de tornos embarcados de la fábrica 2 al cliente 1
SF2-C2 = number of lathes shipped from factory 2 to customer 2
SF2-C3 = number of lathes shipped from factory 2 to customer 3
2. Objective function
Minimize total cost of sending the lathes
Costo = 700SF1-C1+ 900SF1-C2+ 800SF1-C3+ 800SF2-C1+
900SF2-C2+ 700SF2-C3
Exercise 1
2. Restrictions
Requerimiento 1: la fábrica 1 debe enviar 12 tornos.
Requerimiento 2: la fábrica 2 debe enviar 15 tornos.
Requirement 3: customer 1 must receive 10 lathes.
Requerimiento 4: el cliente 2 debe recibir 8 tornos.
Requirement 5: Client 3 must receive 9 lathes.
Fixed requirement constraints
Exercise 1
SF1-C1+SF1-C2+SF1-C3 12
SF2-C1+SF2-C2+SF2-C3 = 15
SF1-C1 + SF2-C1 = 10
SF1-C2 + SF2-C2 =8
SF1-C3 + SF2-C3 = 9
Transportation problem
We use double subscript decision variables.
In general, the decision variables for a transportation problem that
the origin and destinies are written as follows:
number of units sent from the original destination
where i = 1, 2, ..., j = 1, 2, ..., n
Exercise 2
How much production should
send from each plant to
each distribution center?
Exercise 2
Objective function
Transportation costs for units shipped from Cleveland
For i=1 3x11+ 2x12+ 7x13+ 6x14
Transportation costs for units sent from Bedford
For i=2 7x21+ 5x22+ 2x23+ 3x24
Transport costs for units sent from York
For i=3 2x31 + 5x32 + 4x33 + 5x34
Exercise 2
=
=
=
=
Solution in LINGO
Transportation problem
General formulation of the transportation problem
xij quantity of units sent from the original destination
unit shipping cost from the original destination
supply or capacity in units at the origin
demand in units at the destination
Transportation Problem
Seaxijthe amount sent from the original destination.
Min cijxij
s.a. xij<sI for all origins; i = 1, 2,…, m
j
xij=dj for every destination j; j= 1,2, …, n
i
xij0 for everything
Transportation problem
Special cases
Minimum transportation requirement from now on:
x
ijis ij
greater than L
Maximum capacity of the deiaj route:
xij < ijL
–Unacceptable route: