Network models

From Supply Chain Management Encyclopedia

Revision as of 13:08, 24 August 2011 by Zyatchin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

The Main Definitions

Let $\, N=\{x \}$ is a finite set called a set of nodes. The rule $\, f$ , which associates each element $\, x \ in N$ with an element $\, f (x) \ in N$ , is called single-valued transformation $\, N$ in $\, N$ . A multi-valued transformation $\, F$ of the set $\, N$ in $\, N$ is a rule that for each element $\, x \ in N$ defines a subset $\, F_ {x} \ in N$ (in this case it is allowed $\, F_ {x} = \emptyset$ ) . A couple $\, \Gamma = (N, F)$ is called a graph if $\, N$ is a finite set, a $\, F$ is a transformation of $\, N$ in $\, N$ . As an example, consider a supply chain in which suppliers, manufacturers and consumers of all levels are the nodes of the graph, and transformation $\, F$ describes all possible routes for the movement of materials (goods).

Further elements of $\, N$ will be represented by points on the plane, and a pair of points $\, x$ and $\, y$ , for which $\, y \in F_ {x}$ , will be joined by continuous line with an arrow pointing from $\, x$ to $\, y$ . Each element of $\, N$ is called a vertex or node of the graph, and a pair of elements $\, (x, y)$ , where $\, y \in F_ {x}$ is the arc of the graph. The set of arcs in the graph is denoted by $\, P$ .

The set of arcs in the graph $\, \Gamma = (N, F)$ defines the mapping $\, F$ and vice versa, mapping $\, F$ defines the many $\, P$ . Therefore, the graph can be written in the form of $\, \Gamma = (N, F)$ , and as $\, \Gamma = (N, P)$ .

An edge of the graph $\, \Gamma = (N, P)$ is the set of two elements $\, x$ , $\, y \in F_ {x }$ , for which the following conditions takes place: $\, (x, y) \in P$ , or $\, (y, x) \in P$ . An edge has no an orientation . Edges are denoted by the letters $\, p$ , $\, q$ , the set of edges - $\, G$ .

A chain is a sequence of edges $\, (p_ {1}, p_ {2}, \ldots)$ , in which each edge $\, p_ {k}$ has the boundary vertex for $\, p_ {k-1}$ , the other vertex is the boundary for $\, p_ {k +1}$ .

A cycle is the chain starting at some vertex and ending at the same vertex. A graph is called connected graph if any two vertices can be connected by a chain.

Network is a graph whose edge set is given by a numerical function.

Each network is associated a particular stream (e.g. gas flow in pipelines, the flow of information in computer networks). Assume that the flow in the network is limited by bandwidth of its edges, which can be both finite and infinite.

The Transportation Problem

In this section, a special class of linear programming problems - transportation models – is considered. The classical problem of transportation is the following: some goods are to be delivered from several points of origin (production, warehouses) to several destinations (customers, stores). In other words, there are two types of nodes:

1) sources (departure)

2) sinks (destinations)

In the transportation problem supply and demand are known, the cost of transportation on any route directly proportional to the volume of cargo. The problem is to find a transportation plan, in which the total transportation costs are minimal and all products are exported from the points of departure and demand at the all destination points is satisfied.

It should be noted that on the one hand the mathematical solution of transport models, is applicable to a variety of real-world problems, in which nothing will be transported (the problem of optimal assignment of employees, production planning for months, etc.). On the other hand, not all the problems of logistics of transportation are in the class of linear programming problems (traveling salesman problem, the problem of the shortest path).

2.1 Statements of the transportation problem

In this section three ways to specify the transportation problem are considered: analytical, network and a table.

Analytical method

Consider the transportation problem in the classical statement. Let there are $\, m$ points of production and $\, n$ points of consumption. Define a table of transportation costs, consisting of elements $\, c_ {ij}$ - the transportation cost per unit from $\, i$ -th producer to $\, j$ th customer:

$\,C=\left(\begin{array}{cccc} {c_{11} } & {c_{12} } & {\ldots } & {c_{1n} } \\{c_{21} } & {c_{22} } & {\ldots } & {c_{2n} } \\{\ldots } & {\ldots } & {\ldots } & {\ldots } \\{c_{m1} } & {c_{m2} } & {\ldots } & {c_{mn} } \end{array}\right)$ All the elements of the transport table $\, C$ are known.

Consider a transportation table, consisting of variables $\, x_ {ij}$ - the number of transported goods from $\, i$ -th producer to $\, j$ - th customer:

$\,X=\left(\begin{array}{cccc} {x_{11} } & {x_{12} } & {\ldots } & {x_{1n} } \\{x_{21} } & {x_{22} } & {\ldots } & {x_{2n} } \\{\ldots } & {\ldots } & {\ldots } & {\ldots } \\{x_{m1} } & {x_{m2} } & {\ldots } & {x_{mn} } \end{array}\right)$

The elements of the table $\, X$ are unknown. There are variables whose values are to be determined.

Production and consumption denote respectively as follows: $\, a_ {1}, \ldots, a_ {m}$ and $\, b_ {1}, \ldots, b_ {n}$ .

Network method

The figure shows an overview of the transport problem as a network with two types of nodes, corresponding to $\, m$ points of origin and $\, n$ destinations. Arcs, connecting the nodes, correspond to routes between the origin and destination. Each arc $\, (i, j)$ is defined by the costs $\, c_ {ij}$ and the amount of cargo $\, x_ {ij}$ :

Table method

Rows of Table 2 correspond to the points of origin and the columns correspond to the points of destinations. Cells $\, (i, j)$ correspond to the parameters $\, c_ {ij}$ and variables $\, x_ {ij}$ . The consumption is set in the cell lines $\, m +1$ , the volume of production - in a column $\, n +1$ :

Table 2.

2.2 Mathematical model of the transportation problem

To optimize the transportation problem we are to minimize transportation costs. Marginal costs are presented in the transportation table $\, C$ , the variables form a table $\, X$ . To create an objective function we may multiply elements of a tables $\, C$ and $\, X$ and then summarize the resulting products. The total costs are:

$\,\min z=\min (c_{11} x_{11} +c_{12} x_{12} +\ldots +c_{mn} x_{mn} )=\min \sum \limits _{i=1}^{m}\sum \limits _{j=1}^{n}c_{ij} x_{ij}$

under constraints on departure points:

$\,\sum \limits _{j=1}^{n}x_{ij} =a_{i}$ , где $\,i=1,2,\ldots m$

and constraints on destination points:

$\,\sum \limits _{i=1}^{m}x_{ij} =b_{j}$ , где $\,j=1,2,\cdots n$

Consider also non-negativity and integer variables:

$\,x_{ij} \ge 0$ , $\,x_{ij}$ - integer.

2.3 Example

A company "Comfort" has two stores. Earlier this week, it received orders from three customers for 6, 7 and 11 cabinets. In the first warehouse there are 15, in the second warehouse - 9 cabinets. Replenishment is not expected. The cost of transportation of one cabinet from the first warehouse to consumers 1, 2, 3 is respectively 600, 100, 400 rubles. From the second warehouse - 1200, 200, 800 rubles respectively.

Find a transportation plan that minimizes total transportation costs.

To solve a problem consider a network:

The problem is balanced, since the total inventory in the warehouses $\, 15 9 = 24$ equal to the volume of demand: $\, 6 +7 = 24 11$ . The mathematical formulation is the following:

$\,\min z=\min (600x_{11} +100x_{12} +400x_{13} +1200x_{21} +200x_{22} +800x_{23} )$

$\,\left\{\begin{array}{l} {x_{11} +x_{12} +x_{13} =15} \\{x_{21} +x_{22} +x_{23} =9} \\{x_{11} +x_{21} =6} \\{x_{12} +x_{22} =7} \\{x_{13} +x_{23} =11} \\{x_{ij} \ge 0,\, \, x_{ij} -\, F5;.,\, \, i=1,2;\, j=1,2,3} \end{array}\right.$

2.4 Balance condition of the transport model.

Balance condition

The transportation problem is balanced, if the condition of balance - the total output is equal to the total volume of consumption:

$\,\sum \limits _{i=1}^{m}a_{i} =\sum \limits _{j=1}^{n}b_{j}$

In this case, the problem has an optimal solution. Balance condition is not fulfilled in two cases: over-supply and deficit.

Over-supply

$\,\sum \limits _{i=1}^{m}a_{i} >\sum \limits _{j=1}^{n}b_{j}$

The solution in over-supply case depends on fines for incomplete removal of goods from the warehouse:

1) No fines. Therefore, the objective function (total cost) is not changed, part of the goods remains in storage. In the math formulation replace the equal sign in the restrictions on production with the inequality:

$\,\min z=\min (c_{11} x_{11} +c_{12} x_{12} +\ldots +c_{mn} x_{mn} )=\min \sum \limits _{i=1}^{m}\sum \limits _{j=1}^{n}c_{ij} x_{ij}$

$\,\sum \limits _{j=1}^{n}x_{ij} \le a_{i}$ , где $\,i=1,2,\ldots m$

$\,\sum \limits _{i=1}^{m}x_{ij} =b_{j}$ , где $\,j=1,2,\cdots n$

$\,x_{ij} \ge 0$ , $\,x_{ij}$ - целые.

2) There are penalties for possession of the remaining goods in at least one point of departure. The size of the penalty is proportional to the number of items. In this case, the objective function includes the emerging costs. Balance the model by adding a fictitious user. We assume that the consumer has a demand $\, b_ {n +1} = \sum \limits _ {i = 1} ^ {m} a_ {i} - \sum \limits _ {j = 1 } ^ {n} b_ {j}$ . The penalty for the remainder of departure at number $\, i$ denote $\, c_ {in +1}$ . Thus, the transportation table has an additional column of traffic with the number $\, n +1$ . As a result, we have a new problem, for which the condition of balanced.

Example.

The next problem is the overproduction of four units:

The penalty for the remainder on the first warehouse is zero, for the second – is equal to 2, for the third - 1. We introduce a fictitious consumer demand with volume 4:

Deficit

$\,\sum \limits _{i=1}^{m}a_{i} <\sum \limits _{j=1}^{n}b_{j}$

Solution of the transportation problem subject to deficit depends on the existence of penalties for unmet demand:

1) No penalties. Therefore, the objective function (total cost) is not changed, part of the goods are not delivered to customers. In the math formulation replace the equal sign in the restrictions on the volume of demand with inequality:

$\,\min z=\min (c_{11} x_{11}+c_{12} x_{12} +\ldots +c_{mn} x_{mn} )=\min \sum \limits _{i=1}^{m}\sum \limits _{j=1}^{n}c_{ij} x_{ij}$

$\,\sum \limits _{j=1}^{n}x_{ij} =a_{i}$ , where $\,i=1,2,\ldots m$

$\,\sum \limits _{i=1}^{m}x_{ij} \le b_{j}$ , where $\,j=1,2,\cdots n$

$\,x_{ij} \ge 0$ , $\,x_{ij}$ - integer.

2) There are penalties for unsatisfied demand, at least for one consumer. The size of the penalty is proportional to the number of units not delivered the goods. In this case, the objective function includes the emerging costs. Balance the problem by adding a fictitious manufacturer. Assume that the manufacturer has the missing amount $\, a_ {m +1} = \sum \limits _ {j = 1} ^ {n} b_ {j} - \sum \limits _ {i = 1} ^ {m} a_ {i}$ . The penalty for each unit of product, which was not delivered to the consumer $\, j$ , denote $\, c_ {m +1 j}$ . Thus, the transportation table has the additional line $\, m +1$ . As a result, we have a new task, for which the condition of balance is hold.

Example.

In the next example deficit is equal to 7 units:

The penalty for unsatisfied demand of the first and the fourth user is zero. For the second manufacturer fee is equal to 3, for the third manufacturer - 1. Consider a fictitious manufacturer with inventory of 7 items:

2.5 Initial solution

For the correct solution of transportation problems by using an add-on for MS Excel "Solver" it is necessary to indicate an initial solution that is feasible. In this section two methods to find a feasible solution are considered. They are: method northwest element and method of a minimal element.

Method northwest element

Algorithm:

1) For a variable in the top left table cell the maximum value allowed by the constraints on supply and demand is assigned.

2) A row (or column) with satisfied offer (or demand) is eliminated. Offer (or demand) in the corresponding row (or column) is being corrected.

3) If the table consists of only one row or only one column, its cells are filled according to the available offer and demand. Otherwise, proceed to the first stage.

Define the initial solution by the northwest elements in the transportation problem of "Comfort" company:

Minimum element method

Algotithm:

1) In the transportation table the cell with minimal costs is determined. For a variable in this cell the maximum value allowed by the constraints on supply and demand is assigned

2) A row (or column) with satisfied offer (or demand) is eliminated. Offer (or demand) in the corresponding row (or column) is being corrected.

3) If the table consists of only one row or only one column, its cells are filled according to the available offer and demand. Otherwise, proceed to the first stage.

Define the initial solution by the minimum element method in the transportation problem of "Comfort" company:

2.6 Transportation problem solving in MS Excel

Open a sheet "feasible solution". Determine the optimal transportation plan, according to incoming orders for the company "Comfort" from the example at paragraph 2.3.

Cells containing parameters of the problem, we will be mark by blue frame. Cells containing the variables, we will mark by the red frames.

Parameters

In cells C6: E7 indicate the cost of transportation from each warehouse to each customer

In cells C12: E13 we specify the initial values of traffic volume, determined by the method of minimum element.

Cells H12: H13 indicate the existing product inventories in warehouses

In cells C16: E16 we set the value of customers' 1, 2 and 3 order volumes

Restrictions

In cell F12 calculate the total amount of goods exported from the first store using the formula:

=SUM(C12:E12).

In cell F13 indicate the total quantity of goods exported from the second warehouse.

Similarly, we define the number of goods delivered to each customer. In a cell C14 count the total number of goods delivered to the first client using the formula:

=SUM(C12:C13).

To determine the number of products received the second and third clients, copy the formula in cell D14: E14. Note that in this case we use relative addressing.

Objective function

In cell C20 we calculate the total cost of transportation problem using the formula:

=SUMPRODUCT(C6:E7;C12:E13).

Solver

Open a sheet "optimal solution" and open the add-in "Solver".

Set Target Cell. Specify the cell C20 - the total cost

Variable cell. Select the array $C$12:$E$13 as changing cells.

Restrictions. Add restrictions on the available inventory: $F$12:$F$13 = $H$12:$H$13 on demand: $C$14:$E$14 = $C$16: $E$16, and the integrality and nonnegativity of the variables: $C$12:$E$13 = integer, $C$12:$E$13.

Click the Options button and set the flag in the linear model. We return to the Solver Parameters dialog box and click Run.

The total cost of transportation is 10200 rub. This result was unexpected for the delivery of the company "Comfort".

Recall that the initial decision obtained by a minimum element method consists in exporting of goods by the cheapest route.

Of course, in the first step it was supposed to take out the maximum number of goods from the first warehouse to the second client, because shipping is only $100. But at the same time the total transportation costs were significantly different from the optimum value and accounted for 13 500 rubles.

In addition, according to the optimal plan we not carry anything from the first warehouse to the second consumer! How can we explain that the "Solver" "ignored" in the optimal solution of the lowest cost?

It is easy to see that in the solution obtained by the method of the minimal element, the goods are carried by the cheapest route (from the first warehouse of second client), and the goods are carried by the most expensive route (from the second warehouse the first client). In this case the cost of transportation of one cabinet by the last route is 1,200 rubles, and in the solution proposed we carry 6 cabinets by this route. Now consider the optimal transportation plan. Yes, by the cheapest route we are taking nothing, but we also do not use the most expensive route.

Distribution Problem

As already noted, in a network method of defining such problems, there are two types of nodes: sources and sinks. Distribution problem is the most general statement of the network problem. It differs from the transportation model by the presence nodes of three types in a network:

1) Sources

2) Sinks

3) Intermediate nodes

As in the transportation models, each source is characterized by offer, stock – by demand. Intermediate nodes have zero demand and supply. Consequently, the distribution problem includes, as a special case, a transportation model.

3.1 Mathematical formulation of the distribution problem

Introduce the following notation:

$\, N$ - the set of nodes;

$\, n$ - the number of nodes,

$\, G$ - the set of arcs,

$\, x_{ij}$ - flow passing through the arc $\,(i,j)$ ,

$\,c_{ij}$ - costs of unit of flow from $\,i$ to $\,j$ ,

$\,l_{ij}$ - lower bound of flow from $\,i$ to $\,j$ ,

$\,u_{ij}$ - upper bound of flow from $\,i$ to $\,j$ ,

$\,b_{j}$ - capacity in the node $\,j$ ,

$\, \left(i,j\right)$ - arc.

Consider the level of demand in the sink as a performance with a minus sign. This allows writing the condition of the balance model in the form:

$\,\sum \limits _{j\in N}b_{j} =0$

Objective function

Consider the problem of finding a flow of minimal value in a network. The objective function becomes:

$\,\min \sum \limits _{(i,j)\in G}c_{ij} x_{ij}$

Restrictions

1) Restrictions defined by bandwidth of edges

Each variable $\, x_ {ij}$ defines the flow flowing along the edge $\, (i, j)$ , therefore, it must satisfy the constraints on the bandwidth of the edge:

$\,l_{ij} \le x_{ij} \le u_{ij} ,\; (i,j)\in G,$

For each node it must be satisfied the basic relation for the flow

2) The basic relation for the flow

For each network node it must hold:

The effluent - Inflowing flow = Node capacity

Or in the notation:

$\,\sum \limits _{(j,i)\in G}x_{ji} -\sum \limits _{(i,j)\in G}x_{ij} =b_{j}$ , $\,j =1,2,...,n$

In addition, it should be satisfied non-negativity and integrality conditions:

$\,x_{ij} \ge 0$

$\, x_{ij}$ - integer.

Finally, mathematical statement has the following form:

$\,\min \sum \limits _{(i,j)\in G}c_{ij} x_{ij}$

$\,l_{ij} \le x_{ij} \le u_{ij} ,\; (i,j)\in G,$

$\,\sum \limits _{j\in N}b_{j} =0,$

$\,\sum \limits _{(j,i)\in G}x_{ji} -\sum \limits _{(i,j)\in G}x_{ij} =b_{j}$ , $\,j=1,2,...,n$

$\,x_{ij} \ge 0$

$\,x_{ij}$ - integer.

3.1. The problem of minimal route

The problem of minimal route is the problem of determination the shortest path between two nodes of the transport network. Many real tasks such as routing, equipment replacement schedule, the load problem can be formalized by this model.

Example.

A "Comfort" company has received from non-resident client order for production and delivery of exclusive table. The department of logistics of the company has a map of roads with distances between towns:

A company "Comfort" is located in the city 1, the destination is the city 7. The table was made in time, the company needs to find a route of minimum length.

Solution.

Let's start by checking the balance of the model. The firm has received an order for a table. Recall that demand is treated as a negative performance; therefore, the balance condition is satisfied:

$\,1+(-1)=0$

Let $\, x_ {ij}$ is a flow from the city $\, i$ to the city $\, j$ . The cost are the distances between cities, then the objective function becomes:

$\,\min z=\min (10x_{12} +40x_{13} +30x_{14} +55x_{25} +15x_{24} +12x_{34} +18x_{36} +$

$\,+40x_{45} +60x_{47} +33x_{46} +15x_{57} +20x_{67} )$

Restrictions on the bandwidth problem are not defined, that is, all the roads can carry any amount of cargo.

Consider the basic relations for a flow. The first node is the source from which it is possible to get into the city 2, 3 and 4. Order quantity is one unit, then the performance of the source is 1. Influent flow is absent, thus:

$\, x_{12} +x_{13} +x_{14} =1$ (узел 1)

Consider the basic relation for the intermediate network nodes. It is known that their performance is equal to zero. From the city 2 is possible to get only city 4 and 5. Get into the city 2 it is possible only from the city of 1. It means that the basic relation of the node 2 has the form:

$\, (x_{24} +x_{25} )-x_{12} =0$ (node 2)

For the rest nodes we get:

$\, (x_{34} +x_{36} )-x_{13} =0$ (node 3)

$\, (x_{45} +x_{46} +x_{47} )-(x_{14} +x_{24} +x_{34} )=0$ (node 4)

$\, x_{57} -(x_{25} +x_{45} )=0$ (node 5)

$\, x_{67} -(x_{46} +x_{36} )=0$ (node 6)

A node 7 can be reached from nodes 4, 5 and 6. The effluent from the node 7 is missing. Considering the negative performance of demand, we have:

$\, -(x_{47} +x_{57} +x_{67} )=-1$ (node 7).

Take into account non-negativity and integrality of the flow:

$\,x_{ij} \ge 0$ , $\,x_{ij}$ - integer.

3.2. The realization of the problem of minimal route in MS Excel

Open a sheet "feasible solution". We define the shortest path, according to the pattern of roads in the example of paragraph 3.1.

As before, cells containing the parameters of the problem will be marked by blue frame. Cells that contain variables, mark by the red frames.

{\bf Parameters}

In cells B8: M8 specify the distance between cities

In cells B9: M15 indicate the coefficients corresponding to the effluent and influent stream in each node. It is sufficient to specify only the values 1 and -1. The contents of the empty cells are interpreted as 0.

Cells P9: P15 indicate the performance of nodes

In cells B6: M6 specify any feasible path between the source and sink, for example, 1> 2> 5> 7. To realize this it is necessary to set the value of a variable $\, x_ {12}$ , $\, x_ {25}$ , $\, x_ {57}$ . Other variables set to zero.

Restrictions

The cell N9 indicates the total flow flowing from node 1:

=SUMPRODUCT($B$6:$M$6;B9:M9).

Here we use absolute addressing for the array of cells containing the variables of the problem: $B$6:$M$6, and relative addressing for the coefficients: B9:M9. This allows to copy the formula into the cell corresponding to the remaining nodes: N10: N15.

Objective function

In cell A19 calculate the total path length using the formula:

= SUMPRODUCT (C6:E7;C12:E13).

The path length 1> 2> 5> 7 equals 80.

Solver

On the sheet "optimal solution", open the add-in "Solver".

Set Target Cell. Specify the cell A19 - the path length

Variable cell. Select the array $B$6:$M$6 as the changing cells.

Restrictions. Add restrictions on the value flowing and inflowing streams for each of the seven nodes: $N$9:$N$15 = $P$9:$P$15, and the integrality and nonnegativity of the variables: $B$6:$M$6 = integer, $B$6:$M$6.

Click the Options button and set the flag in the linear model. Return to the Solver Parameters dialog box and click Run.

As a result of optimizing the unit values have been assigned to the following variables: $\, x_ {13} = 1$ , $\, x_ {36} = 1$ , $\, x_ {67} = 1$ . The remaining variables are zero. This corresponds to path 1> 3> 6> 7. The length of this path is specified in the target cell and is equal to 68.

Network interpretation of the solution:

Note that in the problem of "Comfort" company was to bring the customer one exclusive table. Of course, the optimization problem solution (finding the shortest path) does not depend on order volume. Therefore, the general formulation of the problem of the shortest path is always assumed that the performance of the source (or sink) is equal to 1 (minus 1).

Network models

From Supply Chain Management Encyclopedia

The Main Definitions

The Transportation Problem

Distribution Problem

Views

Personal tools

Navigation

Search

Toolbox

Print/export

Our Partners