Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Chapter 18

Network Programming

Abstract

This chapter examines the evolution and advantages of applying network programming, as well as its importance for decision making. Problems in network programming are modeled through graph structures and are often particular cases of linear programming. We will present the modeling of various real problems with network programming, including the classic transportation problem and the transshipment problem, to name a few. The classic transportation problem will be solved through the transportation algorithm, which is a simplification of the Simplex method. All of the network programming problems presented will be solved by Excel Solver.

Keywords

Network programming; Classic transportation problem; Transportation algorithm; Transhipment problem; Job assignment problem; Shortest path problem; Maximum flow problem; Excel Solver

I understand reason to be, not the ability to ratiocinate, which may be well or poorly employed, but the sequencing of truths that can only produce truths, and one truth cannot be contrary to the other.

Gottfried Wilhelm von Leibniz

18.1 Introduction

A network programming problem is modeled through a graph structure or network that consists of various nodes, in which each node must be connected to one or more arcs.

Network models are increasingly utilized in various business areas, such as production, transportation, facility location, project management, finances, and others. Many of them may be formulated as linear programming problems (LP) and, therefore, may be solved by the Simplex method.

Network modeling facilitates visualization and understanding of system characteristics. Thus, simplified versions of the Simplex method may be used for solving LP problems in networks. Additionally, other more efficient algorithms and software are being proposed and utilized for solving models in networks.

Among the main problems in network programming are the classic transportation problem, the transshipment problem, the job assignment problem, the shortest path problem, and the maximum flow problem.

Each one of the problems listed here will be studied in this chapter. We will initially present the mathematical modeling of each problem, as well as its solution using Excel Solver. In the case of the classic transportation problem, we will also describe how to solve it by using the transportation algorithm, which is a simplification of the Simplex method.

18.2 Terminology of Graphs and Networks

A graph is defined as a set of nodes or vertices and a set of arcs or edges interconnecting these nodes. The nodes, drawn as circles or points, may represent facilities (such as factories, distribution centers, terminals, or seaports), or workstations, or intersections. The arcs, illustrated as line segments, make connections between pairs of nodes, and can represent paths, routes, wires, cables, channels, among others.

The notation for a graph is G = (N, A), in which N is a set of nodes and A is a set of arcs. Fig. 18.1 shows an example of a graph with five nodes and eight arcs.

Many times, the arcs of a graph that make connections between nodes are associated to a numerical variable called a flow that represents a measurable characteristic of that connection as a distance between nodes, transportation cost, time expended, dimensions of the wire, number of parts transported, and other factors. Analogously, the nodes of a graph may be associated with a numerical variable called capacity, and may represent the loading and unloading capacity, supplies, demand, between other.

A graph whose arcs and/or nodes are associated with the numerical flow variable and/or capacity is called a network. Fig. 18.2 shows an example of networks. The nodes represent the cities and the flows represent the distances (km) between them.

For simplicity’s sake, we will henceforth no longer make a distinction between the terms “graphs” and “networks,” and will employ only the term “network.”

The nodes of a network may be subdivided into three types: a) supply nodes or sources that represent entities that produce or distribute a given product; b) demand nodes that represent entities that consume the product; c) transshipment nodes that are the intermediate points between the supply nodes and demand and represent the waypoints for those products.

The arcs may have an arrow indicating the direction of the arc. When the flow between the respective nodes occurs in a single direction indicated by an arrow, we have a directed arc. When the flow occurs in both directions, it is called an undirected arc. In cases where there is a single connection between the nodes, but without an arrow indicating the direction of the arc, it is presumed that the arc is undirected. Each one of those cases may be visualized in Fig. 18.3.

Fig. 18.3 Differences between directed and undirected arc.

The arcs of Figs. 18.1 and 18.2 are also examples of undirected arcs. One may assume in these cases that the distances are symmetrical.

When all of the arcs of the network are directed, we have a directed network. Analogously, when all of the arcs are undirected, we say that the network is undirected. Fig. 18.2 is an example of an undirected network. As for Fig. 18.4, it refers to a directed network, whose nodes represent a set of physical activities with the respective durations (minutes) and the directed arcs represent the relations of precedence between the activities.

Fig. 18.4 Example of a directed network.

Other definitions of the graph theory, such as path, Hamiltonian path, cycle, tree, spanning tree and minimum spanning tree, will be presented.

Hillier and Lieberman (2005) define a path between two nodes as the sequence of different arcs connecting these nodes. For example, the sequence of arcs AB − BC − CE (A → B → C → E) of Fig. 18.1 is considered a path. In a directed network, one may have a directed or undirected path. A path that has a single direction is called a directed path. On the other hand, if at least one arc of the path has an opposite direction from the others, it is said that the path is undirected. For example, the path AC − CD − DE (A → C → D → E) of Fig. 18.4 is considered a directed path, given that all of the arcs follow the same direction. On the other hand, the path AB − BD − DC (A → B → D → C) of the same is considered an undirected path, given that the direction of arc DC is contrary to that of the other arcs.

A Hamiltonian path is one that visits each node a single time. For example, the path AB − BC − CE of Fig. 18.1 is also considered a Hamiltonian path. On the other hand, the path AB − BC − CE − ED − DC (A → B → C → E → D → C) of the same figure is not a Hamiltonian path.

A path that begins and ends at the same node forms a cycle. The path AB − BC − CE − EA (A → B → C → E → A) of Fig. 18.1 is an example of a cycle. In a directed network, one may have a directed or undirected cycle. When the path run in a cycle is directed we have a directed cycle. Analogously, an undirected path that begins and ends at the same node is called an undirected cycle. For example, the cycle AB − BD − DE − EA (A → B → D → E → A) of Fig. 18.4 is directed, whereas the cycle AB − BC − CA (A → B → C → A) of the same figure is an example of an undirected cycle.

An undirected network G = (N, A) is said to be related when there is a path between any pair of nodes. A network G has a tree structure if it is related and acyclic (without cycles). In addition, as part of the tree concept, it is affirmed that:

– A tree with n nodes contains n − 1 arcs.
– If an arc is added to a tree, a cycle is formed.
– If an arc is eliminated from the tree, the network ceases to be related (instead of a single related network there will be two related networks).

The network presented in Fig. 18.5 is an example of a tree based on the network presented in Fig. 18.1.

Before we define the concept of spanning tree, we will define the concept of subgraph. G^' = (N^', A^') is a subgraph of G = (N, A) if the set of nodes of G^' is a subset of the set of nodes of G (N^' ⊂ N), if the set of arcs of G^' is a subset of the set of arcs of G (A^' ⊂ A) and if G^' is a graph. Using the network G = (N, A), a spanning tree, also called a generating tree, is a subgraph of G that has a tree structure and contains all of the nodes of G. Fig. 18.6 is an example of a spanning tree using the network drawn in Fig. 18.1.

A minimum spanning tree of G is a spanning tree with a lower cost.

18.3 Classic Transportation Problem

The classic transportation problem has the objective of determining the quantities of products to be transported going from a set of suppliers to a set of consumers, so that the total transportation cost is minimized. Each supplier manufactures a fixed number of products, and each consumer has a known demand that will be met. The problem is modeled using two links in the supply chain; in other words, not considering intermediate facilities (distribution centers, terminal, seaport, or factory). The mathematical notation and the network representation of the classic transportation problem are presented as follows.

Consider a set of m suppliers that provide goods to a set of n consumers. The maximum amount to be transported from a given supplier i (i = 1, …, m) corresponds to its capacity of Cs_i units. On the other hand, the demand of each consumer j (j = 1, …, n) must be met and is represented by d_j. The unit cost for transportation for the supplier i to the consumer j is represented by c_ij. The objective is to determine the quantities to be transported from the supplier i to the consumer j (x_ij) in order to minimize the total transportation cost (z).

Fig. 18.7 presents the network representation of the classic transportation problem.

18.3.1 Mathematical Formulation of the Classic Transportation Problem

The model parameters, the decision variables, and the general mathematical formulation of the classic transportation problem are specified as follows.

Parameters of the model:

c_ij = unit cost for transportation from the supplier i (i = 1, …, m) to the consumer j (j = 1, …, n)

Cs_i = supply capacity of the supplier i (i = 1, …, m)

d_j = demand by the consumer j (j = 1, …, n)

Decision variables:

x_ij = quantities transported from the supplier i (i = 1, …, m) to the consumer j (j = 1, …, n)

General formulation:

$\begin{array}{l} min z = \sum_{i = 1}^{m} \sum_{j = 1}^{n} c_{ij} x_{ij} \\ s . t . \\ \sum_{j = 1}^{n} x_{ij} \leq {Cs}_{i}, i = 1, 2, \dots, m \\ \sum_{i = 1}^{m} x_{ij} \geq d_{j}, j = 1, 2, \dots, n \\ x_{ij} \geq 0, i = 1, 2, \dots, m, j = 1, 2, \dots, n \end{array}$

si1_e (18.1)

that correspond to a linear programming problem.

Thus, the problem could be solved by the Simplex method. However, the special structure of the network problem makes it possible to obtain more efficient solution algorithms, such as the transportation algorithm that will be described in Section 18.3.3.1.

In order for problem represented by Expression (18.1) to have the basic doable solution, the total supply capacity should be greater than or equal to the demand of consumers, so that, $\sum_{i = 1}^{m} {Cs}_{i} \geq \sum_{j = 1}^{n} d_{j}$ .

If total supply total capacity is exactly equal to the total demand consumed, meaning, $\sum_{i = 1}^{m} {Cs}_{i} = \sum_{j = 1}^{n} d_{j}$ (balancing equation), the problem is known as the balanced transportation problem, and may be rewritten as:

$\begin{array}{l} min z = \sum_{i = 1}^{m} \sum_{j = 1}^{n} c_{ij} x_{ij} \\ s . t . \\ \sum_{j = 1}^{n} x_{ij} = {Cs}_{i}, i = 1, 2, \dots, m \\ \sum_{i = 1}^{m} x_{ij} = d_{j}, j = 1, 2, \dots, n \\ x_{ij} \geq 0, i = 1, 2, \dots, m, j = 1, 2, \dots, n \end{array}$

si4_e (18.2)

We can have a third case in which the total supply capacity is less than the total demand consumed $(\sum_{i = 1}^{m} {Cs}_{i} < \sum_{j = 1}^{n} d_{j})$ , so that the total demand of some consumers will not be met. On the other hand, the suppliers will utilize its maximum capacity. That case may be mathematically formulated as:

$\begin{array}{l} min z = \sum_{i = 1}^{m} \sum_{j = 1}^{n} c_{ij} x_{ij} \\ s . t . \\ \sum_{j = 1}^{n} x_{ij} = {Cs}_{i}, i = 1, 2, \dots, m \\ \sum_{i = 1}^{m} x_{ij} \leq d_{j}, j = 1, 2, \dots, n \\ x_{ij} \geq 0, i = 1, 2, \dots, m, j = 1, 2, \dots, n \end{array}$

si6_e (18.3)

Example 18.1

Karpet Ltd. is an automotive parts manufacturer, whose units are located in the Brazilian cities of Osasco, Sorocaba, and Sao Sebastiao. Its clients are found in Sao Paulo, Rio de Janeiro, and Curitiba, as presented in Fig. 18.8. The unit transportation costs from each origin to each destination, as well as the capacity of each supplier and the demand of each consumer, are found in Table 18.E.1. The objective is to meet the demand of each final consumer, respecting the supply capacities, so as to minimize the total transportation cost. Model the transportation problem.

Fig. 18.8 Pool of Karpet Ltd. suppliers and consumers.

Table 18.E.1

Transportation Data of the Karpet Ltd. Company
		Transportation Unit Cost
		Consumer			Capacity
		Sao Paulo	Rio de Janeiro	Curitiba	Capacity
	Osasco	12	22	30	100
Supplier	Sorocaba	18	24	32	140
	Sao Sebastiao	22	15	34	160
Demand		120	130	150

Unlabelled Table

Solution

Since the total supply capacity is exactly equal to the total demand consumed, we have a balanced transportation problem.

First, the decision variables of the model are defined:

x_ij = number of parts transported from the supplier i to the consumer j, i = 1, 2, 3; j = 1, 2, 3.

Thus, we have:

x₁₁ = parts transported from the supplier in Osasco to the consumer in Sao Paulo.

x₁₂ = parts transported from the supplier in Osasco to the consumer in Rio de Janeiro.

x₁₃ = parts transported from the supplier in Osasco to the consumer in Curitiba.

⋮

x₃₁ = parts transported from the supplier in Sao Sebastiao to the consumer in Sao Paulo.

x₃₂ = parts transported from the supplier in Sao Sebastiao to the consumer in Rio de Janeiro.

x₃₃ = parts transported from the supplier in Sao Sebastiao to the consumer in Curitiba.

The objective function seeks to minimize the total transportation cost:

$min z = 12 x_{11} + 22 x_{12} + 30 x_{13} + 18 x_{21} + 24 x_{22} + 32 x_{23} + 22 x_{31} + 15 x_{32} + 34 x_{33}$

The constraints of the model are specified as follows:

1. The capacity of each supplier will be utilized to meet consumer demand:

$\begin{array}{l} x_{11} + x_{12} + x_{13} = 100 \\ x_{21} + x_{22} + x_{23} = 140 \\ x_{31} + x_{32} + x_{33} = 160 \end{array}$

si8_e

2. The demand of each consumer should be met:

$\begin{array}{l} x_{11} + x_{21} + x_{31} = 120 \\ x_{12} + x_{22} + x_{32} = 130 \\ x_{13} + x_{23} + x_{33} = 150 \end{array}$

si9_e

3. The decision variables of the model are non-negative:

$x_{ij} \geq 0, i = 1, 2, 3, j = 1, 2, 3$

The optimal solution, obtained by the transportation algorithm (see Section 18.3.3.1) or using Excel Solver (Section 18.3.3.2), is x₁₁ = 100, x₁₂ = 0, x₁₃ = 0, x₂₁ = 20, x₂₂ = 0, x₂₃ = 120, x₃₁ = 0, x₃₂ = 130, x₃₃ = 30 with z = 8,370.

18.3.2 Balancing the Transportation Problem When the Total Supply Capacity Is Not Equal to the Total Demand Consumed

In the next section, we will present several methods for solving the classic transportation problem. Most require that the transportation problem be balanced, so that a ghost supplier or customer (dummy) should be added when the total supply is not equal to the total demand. We will see each one of the cases.

Case 1: Total Supply Is Greater than Total Demand

Consider an unbalanced transportation problem whose total supply capacity is greater than the total demand consumed. To restore the balance, one must create a ghost customer (dummy) that will absorb the excess supplied. Thus, the demand of this new destination will correspond to the difference between the total supply and the total demand consumed, indicating the nonutilized supply capacity. The transportation unit cost for any supplier to the ghost customer created will be null, since the same is not real. We thus guarantee a feasible basic solution using the solution procedures presented in Sections 18.3.3.1 and 18.3.3.2, given that the total supply capacity has become exactly equal to the total demand.

Example 18.2

The Caramel Candy & Confetti company has been involved in the candy sector since 1990 and owns three stores located in the Greater Sao Paulo area. Its main clients are located in the Sao Paulo Capital, Baixada Santista, and Vale do Paraiba, as shown in Fig. 18.9. The production capacity of the stores, the consumer demand, and the costs per unit distributed by each store for each consumer are illustrated in Table 18.E.2. In order to minimize the total transportation cost, the company wants to determine how much to distribute from each store to the respective consumers, respecting the production capacity and ensuring that the demands will be met. Formulate the Caramel Candy & Confetti company transportation problem.

Fig. 18.9 Stores and clients of the Caramel Candy & Confetti company.

Table 18.E.2

Transportation Data of the Caramel Candy & Confetti Company
		Transportation Unit Cost
		Consumer			Capacity
		Sao Paulo	Baixada Santista	Vale do Paraiba	Capacity
	Store 1	8	12	10	50
Supplier	Store 2	4	10	6	100
	Store 3	6	15	12	40
Demand		60	70	30

Unlabelled Table

Solution

We can verify that the Caramel Candy & Confetti company transportation problem is unbalanced, given that the total supply capacity (190) is greater than the total demand consumed (160).

Solution (a)

One way to represent the mathematical model of the Caramel Candy & Confetti company is by an Expression (18.1) in which the constraints are written in an unequal form. In that model, one has the following decision variables:

x_ij = number of candies transported from store i to the consumer j, i = 1, 2, 3; j = 1, 2, 3.

Thus, we have:

x₁₁ = candies transported from store 1 to the consumer in Sao Paulo (SP).

x₁₂ = candies transported from store 1 to the consumer in Baixada Santista (BS).

x₁₃ = candies transported from store 1 to the consumer in Vale do Paraiba (VP).

⋮

x₃₁ = candies transported from store 3 to the consumer in Sao Paulo (SP).

x₃₂ = candies transported from store 3 to the consumer in Baixada Santista (BS).

x₃₃ = candies transported from store 3 to the consumer in Vale do Paraiba (VP).

The objective function seeks to minimize the total transportation cost:

$min z = 8 x_{11} + 12 x_{12} + 10 x_{13} + 4 x_{21} + 10 x_{22} + 6 x_{23} + 6 x_{31} + 15 x_{32} + 12 x_{33}$

The constraints of the model are specified as follows:

1. The production capacity of each store should be respected:

$\begin{array}{l} x_{11} + x_{12} + x_{13} \leq 50 \\ x_{21} + x_{22} + x_{23} \leq 100 \\ x_{31} + x_{32} + x_{33} \leq 40 \end{array}$

si12_e

2. The demand of each consumer should be met:

$\begin{array}{l} x_{11} + x_{21} + x_{31} \geq 60 \\ x_{12} + x_{22} + x_{32} \geq 70 \\ x_{13} + x_{23} + x_{33} \geq 30 \end{array}$

si13_e

3. The decision variables of the model are non-negative:

$x_{ij} \geq 0, i = 1, 2, 3, j = 1, 2, 3$

The optimal solution of this model, obtained using Excel Solver (see Section 18.3.3.2), is x₁₁ = 0, x₁₂ = 50, x₁₃ = 0, x₂₁ = 50, x₂₂ = 20, x₂₃ = 30, x₃₁ = 10, x₃₂ = 0, x₃₃ = 0 with z = 1,240.

One may see, from that result, that store 3 did not use its maximum capacity of 40 units, but only 10 units.

Solution (b)

In order for the transportation algorithm presented in Section 18.3.3.1 to be applied, we must have a balanced transportation problem, so that the total supply capacity is equal to the total demand. To restore the balance for the Caramel Candy & Confetti company problem, one must create a ghost customer (dummy) that will absorb the excess supply of 30 units. Network modeling of the balanced problem is illustrated in Fig. 18.10.

Fig. 18.10 Network modeling of the balanced problem for the Caramel Candy & Confetti company.

The mathematical formulation of the balanced Caramel Candy & Confetti company problem is described as follows. Since the new consumer was added, x_ij may be rewritten as:

x_ij = number of candies transported from store i to the consumer j, i = 1, 2, 3; j = 1, 2, 3, 4.

The new decision variables are:

x₁₄ = candies transported from store 1 to the new ghost customer (dummy).

x₂₄ = candies transported from store 2 to the new ghost customer (dummy).

x₃₄ = candies transported from store 3 to the new ghost customer (dummy).

Since the transportation unit cost for any supplier to the new consumer is null, the objective function is not changed:

$min z = 8 x_{11} + 12 x_{12} + 10 x_{13} + 4 x_{21} + 10 x_{22} + 6 x_{23} + 6 x_{31} + 15 x_{32} + 12 x_{33}$

The constraints on supply capacity and on demand consumed are changed:

1. Supply constraints by the stores:

$\begin{array}{l} x_{11} + x_{12} + x_{13} + x_{14} = 50 \\ x_{21} + x_{22} + x_{23} + x_{24} = 100 \\ x_{31} + x_{32} + x_{33} + x_{34} = 40 \end{array}$

si16_e

2. Demand constraints:

$\begin{array}{l} x_{11} + x_{21} + x_{31} = 60 \\ x_{12} + x_{22} + x_{32} = 70 \\ x_{13} + x_{23} + x_{33} = 30 \\ x_{14} + x_{24} + x_{34} = 30 \end{array}$

si17_e

3. Nonnegativity constraints:

$x_{ij} \geq 0, i = 1, 2, 3, j = 1, 2, 3, 4$

From solution (a), we already know that the nonutilized capacity of 30 units comes only from store 3. Since the new ghost consumer was created to absorb that surplus supply, we can affirm that x₃₄ = 30.

Therefore, the optimal solution of the balanced model is x₁₁ = 0, x₁₂ = 50, x₁₃ = 0, x₁₄ = 0, x₂₁ = 50, x₂₂ = 20, x₂₃ = 30, x₂₄ = 0, x₃₁ = 10, x₃₂ = 0, x₃₃ = 0, and x₃₄ = 30 with z = 1,240.

Case 2: Total Supply Capacity Is Lower than Total Demand Consumed

Consider an unbalanced transportation problem whose total supply capacity is less than the total demand consumed. To restore the balance, one must create a ghost supplier (dummy) that will meet the remaining demand. Thus, the amount offered by this new supplier will correspond to the difference between the total demand consumed and the total supply capacity, indicating the unmet demand. The transportation unit cost for the ghost supplier created for any consumer will be null, since the supplier is not real. Analogous to Case 1, the balancing equation between supply and demand guarantees that a feasible basic solution will be found.

Example 18.3

Consider Example 18.2 of the Caramel Candy & Confetti company, with, however, distinct production capacities of the stores and consumer demand, as shown in Table 18.E.3. Formulate the new Caramel Candy & Confetti company transportation problem.

Table 18.E.3

New Transportation Data of the Caramel Candy & Confetti Company
		Transportation Unit Cost
		Consumer			Capacity
		Sao Paulo	Baixada Santista	Vale do Paraiba	Capacity
	Store 1	8	12	10	60
Supplier	Store 2	4	10	6	40
	Store 3	6	15	12	50
Demand		50	120	80

Unlabelled Table

Solution

Once again, we are faced with an unbalanced transportation problem; however, this time, the total supply capacity (150) is less than the total demand consumed (250).

Solution (a)

One way to represent that model is through Expression (18.3), in which the suppliers utilize its maximum capacity; however, the total demand of some consumers is not met. The decision variables are not changed in relation to the unbalanced model presented in Example 18.2:

x_ij = number of candies transported from store i to the consumer j, i = 1, 2, 3; j = 1, 2, 3.

The same occurs in relation to the objective function:

$min z = 8 x_{11} + 12 x_{12} + 10 x_{13} + 4 x_{21} + 10 x_{22} + 6 x_{23} + 6 x_{31} + 15 x_{32} + 12 x_{33}$

The constraints on Example 18.3 are specified as follows.

1. The suppliers will utilize its maximum capacity:

$\begin{array}{l} x_{11} + x_{12} + x_{13} = 60 \\ x_{21} + x_{22} + x_{23} = 40 \\ x_{31} + x_{32} + x_{33} = 50 \end{array}$

si20_e

2. The total demand of each consumer may not be met:

$\begin{array}{l} x_{11} + x_{21} + x_{31} \leq 50 \\ x_{12} + x_{22} + x_{32} \leq 120 \\ x_{13} + x_{23} + x_{33} \leq 80 \end{array}$

si21_e

3. The decision variables of the model are nonnegative:

$x_{ij} \geq 0, i = 1, 2, 3, j = 1, 2, 3$

The optimal solution of this model, obtained using Excel Solver (see Section 18.3.3.2), is x₁₁ = 0, x₁₂ = 20, x₁₃ = 40, x₂₁ = 0, x₂₂ = 0, x₂₃ = 40, x₃₁ = 50, x₃₂ = 0, x₃₃ = 0 with z = 1,180.

One may see, from that result, that the total demand of 120 units from the consumer in Baixada Santista was not met, only part of it (20 units).

Solution (b)

Analogous to Example 18.2, in order for the transportation algorithm presented in Section 18.3.3.1 to be applied, we must have a balanced transportation problem before us. To restore the balance, one must create a ghost supplier (dummy) that will meet the unmet demand for 100 units. Network modeling of the new balanced problem is illustrated in Fig. 18.11.

Fig. 18.11 Network modeling of Example 18.3 balanced.

The mathematical formulation of Example 18.3 balanced is described as follows. Since the new supplier has been added, x_ij may be rewritten as:

x_ij = number of candies transported from store i to the consumer j, i = 1, 2, 3, 4; j = 1, 2, 3.

The new decision variables are:

x₄₁ = candies transported from the new ghost store (dummy) to consumer 1.

x₄₂ = candies transported from the new ghost store (dummy) to consumer 2.

x₄₃ = candies transported from the new ghost store (dummy) to consumer 3.

Since the transportation unit cost to the new supplier for any consumer is null, the objective function is not changed:

$min z = 8 x_{11} + 12 x_{12} + 10 x_{13} + 4 x_{21} + 10 x_{22} + 6 x_{23} + 6 x_{31} + 15 x_{32} + 12 x_{33}$

The balanced model of Example 18.3 presents the following constraints:

1. Supply constraints by the stores:

$\begin{array}{l} x_{11} + x_{12} + x_{13} = 60 \\ x_{21} + x_{22} + x_{23} = 40 \\ x_{31} + x_{32} + x_{33} = 50 \\ x_{41} + x_{42} + x_{43} = 100 \end{array}$

si24_e

2. Demand constraints:

$\begin{array}{l} x_{11} + x_{21} + x_{31} + x_{41} = 50 \\ x_{12} + x_{22} + x_{32} + x_{42} = 120 \\ x_{13} + x_{23} + x_{33} + x_{43} = 80 \end{array}$

si25_e

3. Nonnegativity constraints:

$x_{ij} \geq 0, i = 1, 2, 3, j = 1, 2, 3, 4$

From solution (a) of that same example, we already know that the unmet demand for 100 units comes from the consumer in Baixada Santista. Because the new ghost supplier was created to meet that remaining demand, we can affirm that x₄₂ = 100.

Therefore, the optimal solution of the model is x₁₁ = 0, x₁₂ = 20, x₁₃ = 40, x₂₁ = 0, x₂₂ = 0, x₂₃ = 40, x₃₁ = 50, x₃₂ = 0, x₃₃ = 0, x₄₁ = 0, x₄₂ = 100, x₄₃ = 0 with z = 1,180.

18.3.3 Solution of the Classic Transportation Problem

The classic transportation problem will be solved in two ways. First, we will use the transportation algorithm that is a simplification of the Simplex method presented in Chapter 17. And in Section 18.3.3.2, we will present a solution of the problem using the Excel Solver.

18.3.3.1 The Transportation Algorithm

In order to facilitate resolution of the classic transportation problem using the methods presented in this section, the problem should be represented in table form. Box 18.1 presents the tabular form of the general balanced transportation model expressed in Expression (18.2).

Box 18.1

General Tabular Form of the Balanced Transportation Problem

The transportation algorithm follows the same logic of the Simplex method presented in Chapter 17, with some simplifications in light of the peculiarities of the transportation problem. Fig. 18.12 presents each one of the steps of the transportation algorithm.

The elementary operations utilized in the Simplex method to recalculate the values of the new adjacent basic solution are not necessary, given that the new solution may be easily obtained using the table form of the transportation problem.

Each one of the steps of the transportation algorithm presented in Fig. 18.12 will be detailed and later applied to solve the transportation problem for the Karpet Ltd. company (Example 18.1).

Example 18.4

Represent the Karpet Ltd. company transportation problem (Example 18.1) in table form expressed in Box 18.1.

Solution

Using data from the balanced Karpet Ltd. company transportation problem presented in Table 18.E.1, one may easily obtain its tabular form, as shown in Table 18.E.4.

Step 1. Determining the Initial Feasible Basic Solution

Table 18.E.4

Representation of the Balanced Karpet Ltd. Company Transportation Problem in Table Form

The classic transportation problem considers a set of m suppliers and n consumers. Using Expression (18.2) it was found that the balanced transportation problem contains m + n equality constraints. Because in the balanced transportation problem the total inflow is equal to the total outflow, we can affirm that one of those constraints is redundant, so that the model contains m + n − 1 independent equations and, consequently, m + n − 1 basic variables.

For the Karpet Ltd. company transportation problem in which m = 3 and n = 3, we have, therefore, 5 basic variables.

We first see how to find an initial FBS using the northwest corner method, followed by the minimum cost method, as well as the Vogel approximation method.

Northwest Corner Method

The northwest corner method follows the following steps:

Initially: Represent the transportation problem in initial tabular form (see Box 18.1). In that method, the transportation costs need not be specified, given that they are not utilized in the algorithm.
Step 1: Select the cell located in the upper left corner (northwest), among the cells not yet allocated in Step 2 and the cells not yet blocked in Step 3. Therefore, x₁₁ will always be the first variable selected.
Step 2: Allocate the largest possible amount of product to that cell, so that the sum of the corresponding cells in the same row and in the same column does not exceed the total supply and total demand capacities, respectively.
Step 3: Using the cell selected in the previous step, block (marking with an x) the cells corresponding to the same row or column that reached the maximum limit of supply or demand, respectively, given that no other value different from zero may be attributed to those cells. If the researcher uses the maximum limit on both the row and the column, only one of them must be blocked. That condition guarantees that there will be basic variables with null values. The algorithm finalizes when all of the cells have been allocated or blocked. Otherwise, return to Step 1.

Example 18.5

Apply the northwest corner method to the Karpet Ltd. company problem to obtain an initial FBS.

Solution

The initial tabular form of the Karpet Ltd. company problem, for applying the northwest corner method, is represented in Table 18.E.5 and is similar to the Table 18.E.4, but without the unit transportation costs.

Table 18.E.5

Initial Tabular Form of the Karpet Ltd. Company Problem for the Northwest Corner Method

The three steps of the first round are described and represented in Table 18.E.6.

Step 1: Select the cell x₁₁, located upper left corner (northwest).
Step 2: One may see, from Table 18.E.5, that the total capacity from supplier 1 (Osasco) is 100. For its part, the demand from consumer 1 (Sao Paulo) is 120, so that the maximum value to be allocated in that cell is the minimum between those two values.
Step 3: The maximum capacity limit from supplier 1 has been reached, so that the cells corresponding to the same row (x₁₂ and x₁₃) should be blocked.

Table 18.E.6
The Three Steps of the First Round

The same logic is applied to the second round.

Step 1: Among the remaining cells, select the one located in the northwest corner (x₂₁).
Step 2: In setting column 1 relating to the Sao Paulo consumer, the maximum amount that may be allocated in the cell x₂₁ is 20, since the sum of the quantities allocated to the cells of that column may not exceed the demand for 120 units of that consumer. In setting row 2 one may allocate up to 140 units in that same cell. Therefore, x₂₁ = min {20, 140} = 20.
Step 3: the cell x₃₁ should be blocked, since the maximum demand limit of column 1 has been reached.

Table 18.E.7
Result of the Second Round

For the third round, one has the following steps:

Step 1: Among the remaining cells, select the one located in the northwest corner (x₂₂).
Step 2: In setting row 2 referring to the Sorocaba supplier, the maximum amount that may be allocated in x₂₂ is 120, given that the sum of the quantities allocated to all of the cells of that same row may not exceed the 140-unit capacity of that supplier. In setting column 2, one may allocate up to 130 units in that same cell. Therefore, x₂₂ = min {120, 130} = 120.
Step 3: the cell x₂₃ should be blocked, since the maximum capacity limit of row 2 has been reached.

Table 18.E.8
Result of the Third Round

In the last two rounds, Step 3 will not be applied, given that the other cells belonging to the row or column that reached the maximum capacity or demand, respectively, have already been blocked in previous rounds. In the case of the next-to-last round, one selects cell x₃₂ and allocates to it the maximum amount possible of 10 units. Finally, in the last round, one allocates the remaining amount of 150 units to cell x₃₃. The initial FBS of the northwest corner method is listed in Table 18.E.9.

Table 18.E.9

Final Result of the Northwest Corner Method

The basic solution is, therefore: x₁₁ = 100, x₂₁ = 20, x₂₂ = 120, x₃₂ = 10 and x₃₃ = 150 with z = 9,690.

Nonbasic variables: x₁₂ = 0, x₁₃ = 0, x₂₃ = 0 and x₃₁ = 0.

Minimum Cost Method

The minimum cost method is an adaptation of the northwest corner method, in which, instead of selecting the cell closest to the northwest corner, one selects the one with the lowest cost. The complete algorithm of the lowest cost is detailed as follows.

Initially: Represent the transportation problem in initial tabular form in Box 18.1.
Step 1: Select the cell with lowest possible cost, among the cells not yet allocated in Step 2 and the cells not yet blocked in Step 3.
Step 2: Allocate the largest possible amount of product to that cell, so that the sum of the corresponding cells in the same row and in the same column does not exceed the total supply and total demand capacities, respectively.
Step 3: Starting with the cell selected in the previous step, block (marking with an x) the cells corresponding to the same row or column that reached the maximum limit of supply or demand, respectively. Analogous to the northwest corner method, if the researcher uses the maximum limit on both the row and the column, only one of them must be blocked. The algorithm finalizes when all of the cells have been allocated or blocked. Otherwise, return to Step 1.

Example 18.6

Apply the minimum cost method to the Karpet Ltd. company problem to obtain an initial FBS.

Solution

Consider the balanced Karpet Ltd. company transportation problem in initial tabular form (Table 18.E.4). The three steps of the first round are described now and represented in Table 18.E.10.

Step 1: Select the cell x₁₁ that is the one with the lowest cost.
Step 2: Analogous to the northwest corner method, the largest possible amount to be allocated in that cell is 100 = min {100, 120}.
Step 3: The maximum capacity limit from supplier 1 has already been reached, so that the cells corresponding to the same row (x₁₂ and x₁₃) should be blocked.

Table 18.E.10
The Three Steps of the First Round

The same logic is applied to the second round and the result is presented in Table 18.E.11.

Step 1: Among the remaining cells, select the one with the lowest unit cost (x₃₂).
Step 2: the maximum amount that may be allocated in that cell is 130 = min {130, 160}.
Step 3: the cell x₂₂ should be blocked since the maximum demand limit of column 2 has been reached.

Table 18.E.11
Result of the Second Round

For the third round, one has the following steps:

Step 1: Among the remaining cells, select the one with the lowest cost (x₂₁).
Step 2: In setting row 2 referring to the Sorocaba supplier, one could allocate up to 140 units in x₂₁. However, setting column 1 relating to the Sao Paulo consumer, the maximum limit is 20 units, given that the sum of the quantities allocated to all of the cells of that column may not exceed the demand for 120 units of that consumer. Therefore, x₂₁ = min {20, 140} = 20.
Step 3: the cell x₃₁ should be blocked since the maximum limit of column 1 has been reached.

Table 18.E.12
Result of the Third Round

Analogous to the northwest corner method, in the last two rounds, Step 3 is not applied, given that the cells belonging to the row or column that reached the maximum capacity or demand, respectively, have already been blocked. In the next-to-last round, one selects cell x₂₃ and allocates to it a number of 120 units. Finally, in the last round, one allocates the remaining 30 units to cell x₃₃. The initial FBS of the minimum cost method is represented in Table 18.E.13.

Table 18.E.13

Result of the Minimum Cost Method

The basic solution is, therefore: x₁₁ = 100, x₂₁ = 20, x₂₃ = 120, x₃₂ = 130, and x₃₃ = 30 with z = 8,370.

Nonbasic variables: x₁₂ = 0, x₁₃ = 0, x₂₂ = 0, and x₃₁ = 0.

Vogel Approximation Method

According to Taha (2016), the Vogel approximation method is an improved version of the minimum cost method that generally leads to better initial solutions. The detailed steps of the algorithm are:

Initially: Represent the transportation problem in initial tabular form in Box 18.1.
Step 1: For each row (and column), calculate the penalty that corresponds to the difference between the two smallest unit transportation costs in the respective row (and column). The penalty for one row (column) is calculated as long as there are at least two cells not yet allocated and not blocked in the same row (column).
Step 2: Choose the row or column with the highest penalty. In case of a tie, randomly choose any one of them. In the row or column selected, choose the cell with lowest cost.
Step 3: Thus, as with the northwest corner and lowest cost methods, allocate the largest possible amount of product to this cell, so that the sum of the corresponding cells in the same row and in the same column does not exceed the total supply and total demand capacities, respectively.
Step 4: Analogous to the northwest corner method and that of the lowest cost, using the cell selected in the previous step, block (marking with an x) the cells corresponding to the same row or column that reached the maximum limit of supply or demand, respectively. If the researcher uses the maximum limit on both the row and the column, only one of them must be blocked. As long as there is more than one cell that is not allocated and not blocked, return to Step 1. Otherwise, go to Step 5.
Step 5: Allocate the capacity or remaining demand to this last cell.

Example 18.7

Apply the Vogel approximation method to the Karpet Ltd. company problem to obtain an initial FBS.

Solution

All of the steps of the first round are represented in Table 18.E.14. First, the penalties for each row and column were calculated. One may see that the largest penalty occurred in row 1. One selects cell x₁₁ that is the one with the lowest cost in row 1. The next step consists of allocating the largest possible amount of product to this cell, which is 100 = min {100, 120}. The other cells of row 1 are blocked, since the capacity limit of that supplier has been reached. The result of the first round is highlighted in gray.

Table 18.E.14

First Round of the Vogel Approximation Method

The same process is repeated for the second round (see Table 18.E.15). First, the new penalties for each column and for the lines 2 and 3 are calculated. The largest penalty this time is in column 2. Cell x₃₂ is selected as the one with the lowest cost in column 2 and allocated the largest possible amount of product, which is 130 = min {130, 160}. Cell x₂₂ is also blocked, given that the total demand from consumer 2 was met. The new cells allocated and blocked in the second round are highlighted in gray.

Table 18.15

Second Round of the Vogel Approximation Method

In the third round (see table 18.16), one first calculates the new penalties to lines 2 and 3 and to the columns 1 and 3. One may see that the largest penalty is in row 2. Among the remaining cells, the cell with lowest cost in row 2 is x₂₁. In setting column 1, the maximum amount that may be allocated in x₂₁ is 20, given that the sum of the quantities allocated to all of the cells of that same column may not exceed the demand for 120 units by that consumer. In setting row 2, one may allocate up to 140 units in that same cell. Therefore, x₂₁ = min {20, 140} = 20. Cell x₃₁ is blocked, given that the total demand from consumer 1 was met. The result of the third round is highlighted in gray.

Table 18.E.16

Third Round of the Vogel Approximation Method

There now only remains calculation of the penalty for column 3. One chooses the cell with lowest cost in that column; x₂₃ is chosen and allocated 120 units. Finally, one allocates 30 units to the last cell, x₃₃. The initial FBS of the Vogel approximation method is illustrated in Table 18.E.17.

Table 18.E.17

Initial Feasible Basic Solution Obtained by the Vogel Approximation Method

The basic solution is, therefore: x₁₁ = 100, x₂₁ = 20, x₂₃ = 120, x₃₂ = 130, and x₃₃ = 30 with z = 8,370. Note that this solution is the same as the one obtained by the minimum cost method.

Step 2. Optimality Test

To verify if the solution found is optimal, we employ the method of multipliers that is based on the duality theory. Thus, one associates to each row i and to each column j the multipliers u_i and v_j, respectively. The coefficients of the objective function (reduced costs) of variable x_ij ( ${\bar{c}}_{ij}$ ) are given by the following equation:

${\bar{c}}_{ij} = u_{i} + v_{j} - c_{ij}$

(18.4)

Since the reduced costs of the basic variables are null, Expression (18.4) states that:

$u_{i} + v_{j} = c_{ij}, for each basic variable x_{ij}$

(18.5)

Since the model contains m + n − 1 independent equations and, consequently, m + n − 1 basic variables for solving the system of equations represented by Expression (18.5) with m + n unknown, one must arbitrarily attribute a value of zero to one of the multipliers; for example, u₁ = 0.

After calculating the multipliers, one may determine the reduced costs of the nonbasic variables from Expression (18.4). For the transportation problem (minimization problem), the current solution is optimal if, and only if, the reduced costs of all the nonbasic variables are nonpositive:

$u_{i} + v_{j} - c_{ij} \leq 0, for each nonbasic variable x_{ij}$

(18.6)

As long as there is at least one nonbasic variable with reduced positive cost, there is a better adjacent feasible basic solution (FBS).

Iteration. Determine a better adjacent FBS

To find the new feasible basic solution, three steps should be taken:

1. Determine the nonbasic variable that will go into the base, using the method of multipliers. The nonbasic variable x_ij selected is the one with greatest reduced cost (greatest value of u_i + v_j − c_ij).
2. Choose the basic variable that will come from the base (see explanation later).
3. Recalculate the new basic solution. Unlike the Simplex method, this calculation may be done directly using the table form of the transportation problem.

The choice of variable that comes from the base and calculation of the new basic solution may be obtained by constructing a closed cycle that begins and ends in the nonbasic variable chosen to enter the base (Step 1). The cycle consists of a sequence of horizontal and vertical sequences connected to each other (diagonal movements are not permitted), in which each corner is associated with the basic variable, with the exception of the nonbasic variable selected. There is only one closed cycle that may be constructed under those conditions.

With the closed cycle constructed, the next step consists of determining the variable that will come from the base. Thus, among the corners next to the nonbasic variable x_ij (horizontally or vertically), one chooses the basic variable with lowest value, given that the capacity constraints from the supplier i and on demand from consumer j should be respected. In case of a tie, one chooses one of them, randomly.

Finally, one recalculates the new basic solution. First, the value corresponding to the basic variable chosen to leave the base for new basic variable x_ij is attributed. The variable that comes from the base thus assumes the value of zero. The new values of the basic variables of the closed cycle should also be recalculated, so that the required supply capacities and demands continue to be satisfied.

Example 18.8

Starting from the basic initial solution obtained by the northwest corner method for the Karpet Ltd. company problem (Example 18.5), determine the optimal solution using the transportation algorithm.

Solution

Each one of the steps of the transportation algorithm will be applied to determine the optimal solution of the problem studied. As the initial FBS, we will use the one obtained by the northwest corner method.

Step 1. Initial FBS Obtained by the Northwest Corner Method

The initial solution of the northwest corner method obtained in Example 18.5, including the unit transportation costs of each cell, is represented in Table 18.E.18.

Step 2. Optimality Test

Table 18.E.18

Initial FBS of the Northwest Corner Method, Including the Unit Transportation Costs

For each basic variable x_ij, describe the equation u_i + v_j = c_ij (Expression (18.5)):

For x₁₁: u₁ + v₁ = 12
For x₂₁: u₂ + v₁ = 18
For x₂₂: u₂ + v₂ = 24
For x₃₂: u₃ + v₂ = 15
For x₃₃: u₃ + v₃ = 34

Doing u₁ = 0, one obtains the following results:

v₁ = 12, u₂ = 6, v₂ = 18, u₃ = − 3 and v₃ = 37

Using those multipliers, one determines the reduced costs of the nonbasic variables from Expression (18.4):

${\bar{c}}_{12} = u_{1} + v_{2} - c_{12} = 0 + 18 - 22 = - 4$

${\bar{c}}_{13} = u_{1} + v_{3} - c_{13} = 0 + 37 - 30 = 7$

${\bar{c}}_{23} = u_{2} + v_{3} - c_{23} = 6 + 37 - 32 = 11$

${\bar{c}}_{31} = u_{3} + v_{1} - c_{31} = - 3 + 12 - 22 = - 13$

Since the reduced costs of the nonbasic variables x₁₃ and x₂₃ are positive, there is a better adjacent feasible basic solution (FBS). The nonbasic variable that will enter the base is x₂₃, because it has the greatest reduced cost.

Iteration. Determine a Better Adjacent FBS

The closed cycle should be constructed to determine the variable that will come from the base and to calculate the new basic solution. That closed cycle must satisfy the following conditions: (a) begin and end in x₂₃; (b) be formed by a sequence of horizontal and vertical segments connected to each other; and (c) each corner must be associated with the basic variable, with the exception of variable x₂₃. Table 18.E.19 presents the closed cycle that satisfies those conditions.

Table 18.E.19

Construction of the Closed Cycle in the First Iteration

With the closed cycle constructed, the next step consists of determining the variable that will come from the base. Thus, among the corners next to the nonbasic variable x₂₃ (horizontally or vertically), one chooses the basic variable x₂₂ that has the lowest value (120 < 150), given that the capacity constraint from the supplier 2 must be respected.

Finally, one recalculates the new basic solution. First, one attributes the value of 20 from the basic variable output x₂₂ to the new basic variable x₂₃. The variable x₂₂ that comes from the base assumes, therefore, the value of zero. To restore the balance of the closed cycle, one calculates the new values of the basic variables x₃₂ and x₃₃ (130 and 30, respectively). Table 18.E.20 illustrates the new Adjacent FBS.

Step 2. Optimality Test

Table 18.E.20

Adjacent Basic Solution Obtained in the First Iteration

For each basic variable x_ij, describe the equation u_i + v_j = c_ij (Expression (18.5):

For x₁₁: u₁ + v₁ = 12
For x₂₁: u₂ + v₁ = 18
For x₂₃: u₂ + v₃ = 32
For x₃₂: u₃ + v₂ = 15
For x₃₃: u₃ + v₃ = 34

Doing u₁ = 0, one obtains the following results:

v₁ = 12, u₂ = 6, v₃ = 26, u₃ = 8, and v₂ = 7

Using those multipliers, one determines the reduced costs of the nonbasic variables through Expression (18.4):

${\bar{c}}_{12} = u_{1} + v_{2} - c_{12} = 0 + 7 - 22 = - 15$

${\bar{c}}_{13} = u_{1} + v_{3} - c_{13} = 0 + 26 - 30 = - 4$

${\bar{c}}_{22} = u_{2} + v_{2} - c_{22} = 6 + 7 - 24 = - 11$

${\bar{c}}_{31} = u_{3} + v_{1} - c_{31} = 8 + 12 - 22 = - 2$

Since the reduced costs of all the nonbasic variables are nonpositive, the current solution is optimal. The optimal solution is, therefore:

Basic solution: x₁₁ = 100, x₂₁ = 20, x₂₃ = 120, x₃₂ = 130, and x₃₃ = 30 with z = 8,370.

Nonbasic variables: x₁₂ = 0, x₁₃ = 0, x₂₂ = 0, and x₃₁ = 0.

Note that this solution is similar to the initial solution obtained by the lowest cost and Vogel approximation methods.

18.3.3.2 Solution of the Transportation Problem Using Excel Solver

Examples 18.1, 18.2, and 18.3 referring to the classic transportation problem will be solved in this section using Excel Solver.

Solution of the Karpet Ltd. company problem (Example 18.1):

Fig. 18.13 illustrates the representation of the Karpet Ltd. company transportation problem in an Excel spreadsheet (see file Example18.1_Karpet.xls).

The equations utilized in Fig. 18.13 are specified in Box 18.2.

Box 18.2

Equations of Fig. 18.13

Cell	Equation
E16	= SUM(B16:D16)
E17	= SUM(B17:D17)
E18	= SUM(B18:D18)
B20	= SUM(B16:B18)
C20	= SUM(C16:C18)
D20	= SUM(D16:D18)
G22	= SUMPRODUCT(B7:D9,B16:D18)

Analogous to the examples from Chapter 17, names were attributed to the cells and intervals of cells of Fig. 18.13 that will be referred to in the Solver, in order to facilitate understanding of the model. Box 18.3 presents the names attributed to the respective cells.

Box 18.3

Names Attributed to the Cells of Fig. 18.13

Name	Cells
Quantities_transported	B16:D18
Quantities_supplied	E16:E18
Capacity	G16:G18
Quantities_delivered	B20:D20
Demand	B22:D22
Total_cost	G22

The representation of the Karpet Ltd. company problem in the Solver Parameters dialog box is illustrated in Fig. 18.14. Since names were attributed to the cells of the model, Fig. 18.14 will now be referred to by their respective names.

Note that the non-negativity constraints were activated by selecting the Make Unconstrained Variables Non-Negative check box, and the Simplex LP engine was selected in the Solving Method box. The Options command remained unaltered.

Finally, click on Solve and select the option Keep Solver Solution in the Solver Results dialog box. Fig. 18.15 presents the optimal solution of the Karpet Ltd. company transportation problem.

Solution of the Caramel Candy & Confetti company problem (Example 18.2):

The representation of the Caramel Candy & Confetti company transportation problem in an Excel spreadsheet is in Fig. 18.16 (see file Example18.2_Confetti.xls).

Analogous to the Karpet Ltd. company problem (Example 18.1), that problem also considers three suppliers and three consumers. Note that the transport unit cost, the quantities transported, supplied, and delivered, besides the capacity, demand, and total cost, are represented in the same cells of Fig. 18.13. Thus, the equations and the names attributed to the cells of Fig. 18.16 are similar to those of Fig. 18.13 from the previous example. Because we are not faced with a balanced problem (where the total supply capacity is greater than the total demand), the constraints may not be written in the equality form. The new constraints may be visualized in Fig. 18.16 and in the Solver Parameters dialog box, as shown in Fig. 18.17. Analogous to previous models, one assumes that the variables are non-negative and that the model is linear. The optimal solution of the Caramel Candy & Confetti company transportation problem (Example 18.2) is illustrated in Fig. 18.18.

Solution of the Modified Caramel Candy & Confetti company problem (Example 18.3):

Fig. 18.17 Solver Parameters dialog box for Caramel Candy & Confetti company problem (Example 18.2).

Fig. 18.18 Optimal solution of the Caramel Candy & Confetti company transportation problem (Example 18.2) using Excel Solver.

The Example 18.3 is an adaptation from the previous example of the Caramel Candy & Confetti company, in which the production capacities of the stores and client demand are changed, focusing on Case 2 in which the total supply capacity is less than the total demand consumed. Thus, the supply constraints are represented in the equality form, given that the entire capacity should be utilized and given the demand constraints in the form of inequality (the total demand of some consumers will not be met). That problem is represented in an Excel spreadsheet, as shown in Fig. 18.19 (see file Example18.3_Confetti.xls).

The new constraints may be visualized in Fig. 18.19 and in the Solver Parameters dialog box, as shown in Fig. 18.20. One again assumes that the decision variables are non-negative and that the model is linear.

The optimal solution of the adapted Caramel Candy & Confetti company transportation problem (Example 18.3) is illustrated in Fig. 18.21.

18.4 Transhipment Problem

The transhipment problem (TSP) is an extension of the classic transportation problem, in which, instead of transporting the products directly from several origins to several destinations, one considers intermediate transhipment points (facilities such as a distribution center, terminal, seaport, or factory) that may connect these paths, with the objective of reducing logistics costs. The transhipment problem is modeled based on three links in the supply chain, and the transportation process occurs in two stages: transportation from the supply points to the transhipment points and transportation from the transhipment points to the demand points. The objective of the transhipment problem is to determine the flow of goods to be transported from a set of origins to a set of destinations via intermediate facilities, in order to minimize the total transportation cost involved in the system. The mathematical notation and the network representation of the transhipment problem are presented as follows.

Consider a set of m suppliers that supply goods to the set of n consumers via intermediate facilities. The maximum amount to be transported from a given supplier i (i = 1, …, m) corresponds to its capacity of Cs_i units. On the other hand, the demand of each consumer j (j = 1, …, n) should be met, being represented by d_j. The transhipment points are represented by the index k (k = 1, …, K). The transportation unit cost from the supplier i to the consumer j via transhipment point k is represented by c_ij,k. The objective is to determine the quantities to be transported from the supplier i to the consumer j, going through a transhipment point k (x_ij,k), so as to minimize the total transportation cost (z). Fig. 18.22 illustrates the network representation of the transhipment problem.

We can see from Fig. 18.22, that the transportation unit cost from the supplier i to the consumer j via transhipment point k (c_{ij, k}) corresponds to the sum of the unit transportation costs from the supplier i to transhipment point k (c_ik) and from transhipment point k to the consumer j (c_kj):

$c_{ij, k} = c_{ik} + c_{kj}$

(18.7)

Analogously, the amount transported from the supplier i to the consumer j via transhipment point k (x_ij,k) corresponds to the sum of the quantities transported from the supplier i to transhipment point k (x_ik) and from transhipment point k to the consumer j (x_kj):

$x_{ij, k} = x_{ik} + x_{kj}$

(18.8)

18.4.1 Mathematical Formulation of the Transhipment Problem

The model parameters, the decision variables, and the overall mathematical formulation of the transhipment problem are specified here.

Parameters of the model:

c_ij,k = transport unit cost from the supplier i to the consumer j via transhipment point k, i = 1, …, m; j = 1, …, n; k = 1, …, K

Cs_i = supply capacity of the supplier i, i = 1, …, m

d_j = demand from consumer j, j = 1, …, n

Decision variables:

x_ij,k = quantity transported from the supplier i to the consumer j via transhipment point k, i = 1, …, m; j = 1, …, n; k = 1, …, K.

General formulation:

$\begin{array}{l} min z = \sum_{i = 1}^{m} \sum_{j = 1}^{n} c_{i j, k} x_{i j, k} \\ s . t . \\ \sum_{j = 1}^{n} x_{i j, k} \leq {C s}_{i}, i = 1, 2, \dots, m (1) \\ \sum_{i = 1}^{m} x_{i j, k} \geq d_{j}, j = 1, 2, \dots, n (2) \\ \sum_{i = 1}^{m} x_{i k} = \sum_{j = 1}^{n} x_{k j}, k = 1, 2, \dots, K (3) \\ x_{i j} \geq 0, i = 1, 2, \dots, m, j = 1, 2, \dots, n (4) \end{array}$

si41_e (18.9)

that correspond to a linear programming problem.

The objective is, therefore, to minimize the total transportation cost involved in the logistics network.

Constraint (1) of the problem represented by Expression (18.9) affirms that the total capacity of each supplier should be respected. Constraint (2) guarantees that the demand for all of the consumers will be satisfied. Constraint (3) is conservation of the input and output flows, that is, the entire amount that reaches transhipment point k leaves from the same point. Finally, the constraint (4) requires that the decision variables x_ij,k be non-negative.

Analogous to the classic transportation problem, in order for the problem represented by Expression (18.9) to have a basic solution, the total supply capacity should be greater than or equal to demand for all of the consumers, that is, $\sum_{i = 1}^{m} {Cs}_{i} \geq \sum_{j = 1}^{n} d_{j}$ . If the total supply capacity is exactly equal to the total demand consumed, that is, $\sum_{i = 1}^{m} {Cs}_{i} = \sum_{j = 1}^{n} d_{j}$ (balancing equation), we have a balanced transhipment problem, that may be rewritten as:

$\begin{array}{l} min z = \sum_{i = 1}^{m} \sum_{j = 1}^{n} c_{ij, k} x_{ij, k} \\ s . t . \\ \sum_{j = 1}^{n} x_{ij, k} = {Cs}_{i}, i = 1, 2, \dots, m (1) \\ \sum_{i = 1}^{m} x_{ij, k} = d_{j}, j = 1, 2, \dots, n (2) \\ \sum_{i = 1}^{m} x_{ik} = \sum_{j = 1}^{n} x_{kj}, k = 1, 2, \dots, K (3) \\ x_{ij} \geq 0, i = 1, 2, \dots, m, j = 1, 2, \dots, n (4) \end{array}$

si44_e (18.10)

If the parameter c_ij,k and the decision variable x_ij,k are rewritten according to Expressions (18.7), (18.8), the problem represented by Expression (18.10) is now formulated as:

$\begin{array}{l} min z = \sum_{i = 1}^{m} \sum_{k = 1}^{K} c_{ik} x_{ik} + \sum_{k = 1}^{K} \sum_{j = 1}^{n} c_{kj} x_{kj} \\ s . t . \\ \sum_{k = 1}^{K} x_{ik} = {Cs}_{i}, i = 1, 2, \dots, m (1) \\ \sum_{k = 1}^{K} x_{kj} = d_{j}, j = 1, 2, \dots, n (2) \\ \sum_{i = 1}^{m} x_{ik} = \sum_{j = 1}^{n} x_{kj}, k = 1, 2, \dots, K (3) \\ x_{ij} \geq 0, i = 1, 2, \dots, m, j = 1, 2, \dots, n (4) \end{array}$

si45_e (18.11)

Example 18.9

The PetrusNortel company operates in the petrochemical sector and has two factories. One of them is responsible for producing polymers and is located in Recife. The other is located in Manaus as is responsible for producing resin. In order to reduce logistics costs, the products go through a transshipment stage at one of the distribution centers, located in Sao Paulo and Rio de Janeiro. From the distribution centers, the products are transported to the final clients, located in Belo Horizonte, Joinville, and Porto Alegre, as shown in Fig. 18.23. The production capacity in the factories is 500 units in Manaus and 300 in Recife. The demand by consumers from Belo Horizonte, Joinville, and Porto Alegre is 200, 250, and 350, respectively. The unit transportation costs, from the factories to the transshipment points and from the transshipment points to the final customers, are represented in Tables 18.E.21 and 18.E.22, respectively. Formulate the transshipment problem.

Fig. 18.23 The transshipment problem of the PetrusNortel company.

Table 18.E.21

Unit Transportation Costs From the Factories to the Distribution Centers
	Sao Paulo	Rio de Janeiro
Manaus	8	10
Recife	7	6

Table 18.E.22

Unit Transportation Costs From the Distribution Centers to the Consumers
	Belo Horizonte	Joinville	Porto Alegre
Sao Paulo	2	3	4
Rio de Janeiro	1	4	5

Unlabelled Table

Solution

Since the total supply capacity is equal to the total demand from consumers, we are faced with a balanced transshipment problem.

The network representation of the transshipment problem for the PetrusNortel company may be visualized in Fig. 18.24.

One may verify from Fig. 18.24 that nodes 1 and 2 represent the factories in Manaus and Recife, respectively, nodes 3 and 4 represent the transshipment points or distribution centers (DCs) in Sao Paulo and Rio de Janeiro, respectively, and nodes 5, 6 and 7 represent the clients in Belo Horizonte, Joinville, and Porto Alegre, respectively.

We will use directly the mathematical formulation described in Expression (18.11). First, we define the decision variables of the model:

x_ik = quantity transported from factory i to transshipment point k, i = 1, 2; k = 3, 4.

x_kj = quantity transported from transshipment point k to the consumer j, k = 3, 4; j = 5, 6, 7.

Thus, we have:

x₁₃ = parts transported from the factory in Manaus to the DC in Sao Paulo.

x₁₄ = parts transported from the factory in Manaus to the DC in Rio de Janeiro.

x₂₃ = parts transported from the factory in Recife to the DC in Sao Paulo.

x₂₄ = parts transported from the factory in Recife to the DC in Rio de Janeiro.

x₃₅ = parts transported from the DC in Sao Paulo to the consumer in Belo Horizonte.

x₃₆ = parts transported from the DC in Sao Paulo to the consumer in Joinville.

x₃₇ = parts transported from the DC in Sao Paulo to the consumer in Porto Alegre.

x₄₅ = parts transported from the DC in Rio de Janeiro to the consumer in Belo Horizonte.

x₄₆ = parts transported from the DC in Rio de Janeiro to the consumer in Joinville.

x₄₇ = parts transported from the DC in Rio de Janeiro to the consumer in Porto Alegre.

The objective function seeks to minimize the total transportation cost:

$min z = 8 x_{13} + 10 x_{14} + 7 x_{23} + 6 x_{24} + 2 x_{35} + 3 x_{36} + 4 x_{37} + 1 x_{45} + 4 x_{46} + 5 x_{47}$

The constraints of the model are specified as follows:

1. The capacity of each factory will be utilized to meet consumer demand via transhipment points:

$\begin{array}{l} x_{13} + x_{14} = 500 (Factory in Manaus) \\ x_{23} + x_{24} = 300 (Factory in Recife) \end{array}$

si47_e

2. The demand of each consumer will be met from the transhipment points:

$\begin{array}{l} x_{35} + x_{45} = 200 (Consumer in Belo Horizonte) \\ x_{36} + x_{46} = 250 (Consumer in Joinville) \\ x_{37} + x_{47} = 350 (Consumer in Porto Alegre) \end{array}$

si48_e

3. Constraints on conservation of the input and output flows of each transhipment point:

$\begin{array}{l} x_{13} + x_{23} = x_{35} + x_{36} + x_{37} (DC in São Paulo) \\ x_{14} + x_{24} = x_{45} + x_{46} + x_{47} (DC in Rio de Janeiro) \end{array}$

si49_e

4. The decision variables of the model are nonnegative:

$x_{ij} \geq 0, i = 1, 2, 3, j = 1, 2, 3$

18.4.2 Solution of the Transhipment Problem Using Excel Solver

Example 18.9 referring to the transhipment problem of the PetrusNortel company will be solved in this section using Excel Solver.

The representation of the problem in an Excel spreadsheet is illustrated in Fig. 18.25 (see file Example18.9_PetrusNortel.xls). On the left side is represented all the movement from the factories to the transhipment points and on the right side all the movement from the transhipment points up to the final customers.

The equations utilized in Fig. 18.25 are specified in Box 18.4.

Box 18.4

Equations of Fig. 18.25

Cell	Equation
D15	= SUM(B15:C15)
D16	= SUM(B16:C16)
B18	= SUM(B15:B16)
C18	= SUM(C15:C16)
L15	= SUM(I15:K15)
L16	= SUM(I16:K16)
I18	= SUM(I15:I16)
J18	= SUM(J15:J16)
K18	= SUM(K15:K16)
F22	= SUMPRODUCT(B7:C8,B15:C16)+ SUMPRODUCT(I7:K8,I15:K16)

The names attributed to the cells and intervals of cells in Fig. 18.25 that will be referred to in the Solver are presented in Box 18.5.

Box 18.5

Names Attributed to the Cells of Fig. 18.25

Name	Cells
Transport_costs_Factory_Transhipment	B7:C8
Transport_costs_Transhipment_Consumer	I7:K8
Total_transported_Factory_Transhipment	B15:C16
Total_transported_Transhipment_Consumer	I15:K16
Total_supplied	D15:D16
Capacity	F15:F16
Total_delivered	I18:K18
Demand	I20:K20
Entry_DC	B18:C18
Exit_DC	L15:L16
Total_cost	F22

The representation of the problem of the PetrusNortel company in the Solver Parameters dialog box is illustrated in Fig. 18.26. Since names were attributed to the cells of the model, Fig. 18.26 begins to be referred to by the respective names.

Analogous to previous models, we selected the Make Unconstrained Variables Non-Negative check box and the Simplex LP engine in the Select a Solving Method box. The Options command remained unaltered.

Finally, click on Solve and OK to keep Solver solution. Fig. 18.27 presents the optimal solution of the transshipment problem of the PetrusNortel company.

The optimal solution is, therefore, x₁₃ = 500, x₁₄ = 0, x₂₃ = 100, x₂₄ = 200, x₃₅ = 0, x₃₆ = 250, x₃₇ = 350, x₄₅ = 200, x₄₆ = 0, x₄₇ = 0 with z = 8,250.

18.5 Job Assignment Problem

The job assignment problem, also known as the allocation or attribution problem, consists of assigning a set of jobs to a set of machines, so as to minimize the total cost of assignment. The job assignment problem may be modeled like a transportation problem, in which the suppliers correspond to the jobs, and the demands correspond to the machines. Since each job may be assigned to only one machine, and each machine can process only one job, if the assignment problem is modeled like a transportation problem, the capacity of each supplier and the demand of each client will correspond a 1. Additionally, the decision variables of the assignment problem will become binary. The mathematical notation and the network representation of the job assignment problem are presented as follows.

Consider a set of n jobs (j = 1, …, n) and a set of m machines (i = 1, …, m). The cost of assigning a job j to a machine i is c_ij. Each job j may be assigned to only one machine i, and each machine i can process only one job j. The problem consists of assigning the n jobs to the m machines, so as to minimize the total cost of assignment (z).

Fig. 18.28 presents the network representation of the job assignment problem.

18.5.1 Mathematical Formulation of the Job Assignment Problem

The model parameters, the decision variables, and the overall mathematical formulation of the job assignment problem are specified as follows.

Parameters of the model:

c_ij = cost of assigning a job j to a machine i, i = 1, …, m; j = 1, …, n

Decision variables:

$x_{ij} = \{\begin{cases} 1 if job j is assigned to machine i \\ 0 otherwise \end{cases}$

si51_e

General formulation:

$\begin{array}{l} min z = \sum_{i = 1}^{m} \sum_{j = 1}^{n} c_{ij} x_{ij} \\ s . t . \\ \sum_{i = 1}^{m} x_{ij} = 1, j = 1, 2, \dots, n (1) \\ \sum_{j = 1}^{n} x_{ij} = 1, i = 1, 2, \dots, m (2) \\ x_{ij} = 0 or 1, i = 1, 2, \dots, m, j = 1, 2, \dots, n (3) \end{array}$

si52_e (18.12)

that corresponds to a binary programming problem, given that all of the decision variables are binary.

The objective function z seeks to minimize the total cost of assignment of jobs j to the machines i. The first constraint on Expression (18.12) guarantees that each job j will be assigned to only one machine. The second constraint on Expression (18.12) guarantees that each machine i will process a single job. Finally, the constraint (3) affirms that the decision variables are binary.

Fortunately, in this problem, the constraint that the variables are binary may be relaxed or eliminated, given that the optimal solution of the relaxed problem will still satisfy that condition. Thus, the problem may be solved like a linear programming model (x_ij ≥ 0). Greater details on linear relaxation and binary programming may be found in the next chapter.

Example 18.10

A factory in the auto-parts sector has three machines (M1, M2, and M3) and three jobs that should be concluded in the process of manufacturing car seats (finishing, assembly, and painting). Each job may be assigned to only one machine and each machine can process only one job. The processing time of each job in each machine is illustrated in Table 18.E.23. Formulate the assignment problem that has the objective of minimizing the total processing time.

Table 18.E.23

Processing Time (Hours) of Each Job in Each Machine
	Machines
Jobs	M1	M2	M3
Finishing	8	10	12
Assembly	15	13	12
Painting	8	12	10

Unlabelled Table

Solution

The model parameters are:

c_ij = processing time of job j in machine i, i = 1, 2, 3; j = 1, 2, 3

in which the index j corresponds to:

j = 1 (finishing), j = 2 (assembly), and j = 3 (painting)

and the index i:

i = 1 (M1), i = 2 (M2) and i = 3 (M3)

The decision variables of the model are:

$x_{ij} = \{\begin{cases} 1 if job j is assigned to machine i \\ 0 otherwise \end{cases}$

si51_e

The objective function seeks to minimize the total processing time:

$min z = 8 x_{11} + 15 x_{12} + 8 x_{13} + 10 x_{21} + 13 x_{22} + 12 x_{23} + 12 x_{31} + 12 x_{32} + 10 x_{33}$

The constraints of the model are specified as follows:

1. Each job j may be assigned to only one machine i:

$\begin{array}{l} x_{11} + x_{21} + x_{31} = 1 (Finishing) \\ x_{12} + x_{22} + x_{32} = 1 (Assembly) \\ x_{13} + x_{23} + x_{33} = 1 (Painting) \end{array}$

si55_e

2. Each machine j can process only one job i:

$\begin{array}{l} x_{11} + x_{12} + x_{13} = 1 (Machine 1) \\ x_{21} + x_{22} + x_{23} = 1 (Machine 2) \\ x_{31} + x_{32} + x_{33} = 1 (Machine 3) \end{array}$

si56_e

3. The decision variables x_ij are binary:

$x_{ij} = 0 or 1, i = 1, 2, 3, j = 1, 2, 3$

As previously described, in the job assignment problem, the constraint that the decision variables be binary may be relaxed or eliminated, given that the optimal solution of the relaxed problem corresponds to the optimal solution of the original model. Thus, the problem may be solved like a linear programming model in which the decision variables x_ij are non-negative (x_ij ≥ 0).

18.5.2 Solution of the Job Assignment Problem Using Excel Solver

Example 18.10 referring to the job assignment problem will be solved in this section using Excel Solver.

The representation of the problem in an Excel spreadsheet is illustrated in Fig. 18.29 (see file Example18.10_Assignment.xls). Note that this representation is similar to the classic transportation problem, with the exception of cells G16:G18 and B22:D22 that are equal to 1.

The equations utilized in Fig. 18.29 are specified in Box 18.6 and are similar to the classic transportation problem.

Box 18.6

Equations Utilized in Fig. 18.29

Cell	Equation
E16	= SUM(B16:D16)
E17	= SUM(B17:D17)
E18	= SUM(B18:D18)
B20	= SUM(B16:B18)
C20	= SUM(C16:C18)
D20	= SUM(D16:D18)
G22	= SUMPRODUCT(B7:D9,B16:D18)

The names attributed to the cells and intervals of cells of Fig. 18.29 that will be referred to in the Solver are presented in Box 18.7.

Box 18.7

Names Attributed to the Cells of Fig. 18.29

Name	Cells
Processing_time	B7:D9
Assignment	B16:D18
Job_Machines	E16:E18
Machine_Jobs	B20:D20
Total_time	G22

The representation of the assignment problem (Example 18.10) in the Solver Parameters dialog box is illustrated in Fig. 18.30. Analogous to previous models, one assumes that the variables are non-negative and that the model is linear.

Fig. 18.31 presents the optimal solution of the assignment problem (Example 18.10).

The optimal solution is, therefore, x₁₁ = 0, x₁₂ = 0, x₁₃ = 1, x₂₁ = 1, x₂₂ = 0, x₂₃ = 0, x₃₁ = 0, x₃₂ = 1, and x₃₃ = 0 with z = 30.

18.6 Shortest Path Problem

The shortest path problem, also known as the minimum path problem, seeks to find the shortest path between two nodes of a network. Instead of minimizing the total distance traveled, one may also minimize the total cost or the total travel time.

The problem considers only one supply node that corresponds to the point of origin of the network and only one demand node that corresponds to the point of destination of the network. The supply capacity node and the demand of the destination node of the network correspond to one unit. All of the other intermediate or transhipment nodes will have supply and demand equal to zero. The mathematical notation is presented as follows.

Consider a given node i ∈ I. The nodes of origin for i are represented by the index k ∈ K and the destination nodes for i are represented by the index j ∈ J. The supply node of the network is represented by O and the demand node of the network is represented by T, with capacity and demand of a unit, respectively. If the node i analyzed corresponds to the supply node of the network, we have i = O. On the other hand, if the node i corresponds to the demand node of the network, we have i = T. The distance between the nodes i and j is represented by c_ij. In order to find the shortest path between the supply and demand nodes of the network, we seek to determine if the arc (i, j) is contained in that path.

18.6.1 Mathematical Formulation of the Shortest Path Problem

The model parameters, the decision variables, and the overall mathematical formulation of the shortest path problem are specified.

Parameters of the model:

c_ij = distance from node i to node j, ∀ i, j

Decision variables:

$x_{ij} = \{\begin{cases} 1 if the arc (i, j) is contained in the shortest path, \forall i, j \\ 0 otherwise \end{cases}$

si58_e

General formulation:

$\begin{array}{l} min z = \sum_{i} \sum_{j} c_{ij} x_{ij} \\ s . t . \\ \sum_{k} x_{ki} - \sum_{j} x_{ij} = \{\begin{cases} - 1 if i = O \\ 1 if i = T \\ 0 \forall i \neq O, T \end{cases} (1) \\ x_{ij} = 0 or 1, \forall i, j (2) \end{array}$

si59_e (18.13)

$\begin{array}{l} min z = \sum_{i} \sum_{j} c_{ij} x_{ij} \\ s . t . \\ \sum_{j} x_{ij} = 1, if i = O (1) \\ \sum_{k} x_{ki} = 1, if i = T (2) \\ \sum_{k} x_{ki} - \sum_{j} x_{ij} = 0, \forall i \neq O, T (3) \\ x_{ij} = 0 or 1, \forall i, j (4) \end{array}$

si60_e (18.14)

that corresponds to a binary programming problem.

The objective of the shortest path problem is, therefore, to determine the shortest path between the supply node and the demand node of the network, among the possible paths. The first three constraints of Expression (18.14) represent the input and output flows of each node i. If the node i analyzed is the supply node of the network (i = O), the constraint $\sum_{k} x_{ki} - \sum_{j} x_{ij} = - 1$ of Expression (18.13) is summarized as $\sum_{j} x_{ij} = 1$ , since the input flow of node O is zero and its supply capacity is that of a unit. If the node i analyzed is the demand node of the network (i = T), the constraint $\sum_{k} x_{ki} - \sum_{j} x_{ij} = 1$ of Expression (18.13) is summarized as $\sum_{k} x_{ki} = 1$ , since the output flow of node T is zero and its demand is that of a unit. For all of the other nodes, the input flow minus the output flow is equal to zero. Finally, constraint (4) requires that the decision variables be binary.

Analogous to the job assignment problem, in the shortest path problem, the constraint that the decision variables be binary may fortunately also be relaxed or eliminated, given that the optimal solution of the relaxed problem will still satisfy that condition. Thus, the problem may be solved like a linear programming model (x_ij ≥ 0).

Example 18.11

A food supplier located in Osasco delivers snacks and candies every day to a bakery located in the Vila Formosa area of Sao Paulo. To do that, the driver can take more than one route, going through several Sao Paulo neighborhoods. Fig. 18.32 presents the possible routes that the vehicle can cover, from the supply node (Osasco) to the demand node (Vila Formosa), besides the distances in kilometers between the nodes or neighborhoods. Formulate the problem for the shortest path studied.

Fig. 18.32 Network representation of Example 18.11.

Solution

First, we define the decision variables of the model:

$x_{ij} = \{\begin{cases} 1 if the route (i, j) is contained in the shortest path, \forall i, j \\ 0 otherwise \end{cases}$

si65_e

Thus, we have:

x₁₂ = 1 if the route (1, 2) is contained in the shortest path; 0 otherwise.

x₁₃ = 1 if the route (1, 3) is contained in the shortest path; 0 otherwise.

X₂₄ = 1 if the route (2, 4) is contained in the shortest path; 0 otherwise.

X₂₅ = 1 if the route (2, 5) is contained in the shortest path; 0 otherwise.

X₃₄ = 1 if the route (3, 4) is contained in the shortest path; 0 otherwise.

X₃₅ = 1 if the route (3, 5) is contained in the shortest path; 0 otherwise.

X₄₆ = 1 if the route (4, 6) is contained in the shortest path; 0 otherwise.

X₄₇ = 1 if the route (4, 7) is contained in the shortest path; 0 otherwise.

X₅₇ = 1 if the route (5, 7) is contained in the shortest path; 0 otherwise.

X₅₈ = 1 if the route (5, 8) is contained in the shortest path; 0 otherwise.

X₆₉ = 1 if the route (6, 9) is contained in the shortest path; 0 otherwise.

X₇₉ = 1 if the route (7, 9) is contained in the shortest path; 0 otherwise.

X₈₉ = 1 if the route (8, 9) is contained in the shortest path; 0 otherwise.

The objective function seeks the shortest path between the supply node and the demand node of the network:

$min z = 11 x_{12} + 9 x_{13} + 4 x_{24} + 8 x_{25} + 8 x_{34} + 6 x_{35} + 6 x_{46} + 5 x_{47} + 6 x_{57} + 4 x_{58} + 6 x_{69} + 4 x_{79} + 6 x_{89}$

The constraints of the model are specified as follows:

1. Supply node:

$x_{12} + x_{13} = 1 (node 1 - Osasco)$

2. Demand node:

$x_{69} + x_{79} + x_{89} = 1 (node 9 - Vila Formosa)$

3. Intermediate or transhipment nodes:

$\begin{array}{l} x_{12} - x_{24} - x_{25} = 0 (node 2 - Lapa) \\ x_{13} - x_{34} - x_{35} = 0 (node 3 - Alto de Pinheiros) \\ x_{24} + x_{34} - x_{46} - x_{47} = 0 (node 4 - Sta . Cecilia) \\ x_{25} + x_{35} - x_{57} - x_{58} = 0 (node 5 - Jd . Paulista) \\ x_{46} - x_{69} = 0 (node 6 - Belem) \\ x_{47} + x_{57} - x_{79} = 0 (node 7 - Mooca) \\ x_{58} - x_{89} = 0 (node 8 - Ipiranga) \end{array}$

si69_e

4. The decision variables are binary:

$x_{12}, x_{13}, x_{24}, x_{25}, x_{34}, x_{35}, x_{46}, x_{47}, x_{57}, x_{58}, x_{69}, x_{79}, x_{89} \in \{0, 1\}$

That problem may also be solved like a linear programming model by relaxing or eliminating the last constraint and adding the non-negativity constraint of the decision variables (x_ij ≥ 0).

18.6.2 Solution of the Shortest Path Problem Using Excel Solver

Example 18.11 referring to the shortest path problem will be solved in this section using Excel Solver. The representation of the problem in an Excel spreadsheet is illustrated in Fig. 18.33 (see file Example18.11_Bakery.xls).

The equations utilized in Fig. 18.33 are specified in Box 18.8.

Box 18.8

Equations Utilized in Fig. 18.33

Cell	Equation
L6	= G6 + G7
L7	= G6-G8-G9
L8	= G7-G10-G11
L9	= G8 + G10-G12-G13
L10	= G9 + G11-G14-G15
L11	= G12-G16
L12	= G13 + G14-G17
L13	= G15-G18
L14	= SUM(G16:G18)
G22	= SUMPRODUCT(F6:F18,G6:G18)

The names attributed to the cells and intervals of cells of Fig. 18.33 are presented in Box 18.9.

Box 18.9

Names Attributed to the Cells of Fig. 18.33

Name	Cells
Distance	F6:F18
Routes	G6:G18
Input_minus_output	L6:L14
Supply_or_demand	N6:N14
Total_distance	G22

The representation of the shortest path problem (Example 18.11) in the Solver Parameters dialog box is illustrated in Fig. 18.34. One again assumes that the decision variables are non-negative and that the model is linear.

Fig. 18.35 presents the optimal solution of the shortest path problem (Example 18.11).

The optimal FBS is, therefore, x₁₂ = 1, x₂₄ = 1, x₄₇ = 1, x₇₉ = 1 (Osasco → Lapa → Santa Cecilia → Mooca → Vila Formosa) with z = 24.

18.7 Maximum Flow Problem

The maximum flow problem seeks to maximize the flow (of goods, materials, energy, etc.) from a node of origin to a destination node in the network, respecting the minimum and maximum limits on flow in the arcs. The flow may be measured in two directions: maximum output flow from the node of origin or maximum input flow at the destination node. As examples of applications of the maximum flow problem, one has to: a) maximize the flow of goods in a distribution network; b) maximize the flow of oil, gas, or water through a system of pipelines, gas pipelines, or aqueducts, respectively; c) maximize the flow of vehicles in a transportation network. The mathematical notation is presented as follows.

Consider a given node i ∈ I. The nodes of origin for i are represented by the index k ∈ K and the destination nodes of i are represented by the index j ∈ J. The node of origin of the network is represented by O and the destination node of the network is represented by T. If the node i analyzed corresponds to the supply node of the network, we have i = O. On the other hand, if the node i corresponds to the demand node of the network, we have i = T. The flow from node i to node j is represented by x_ij. The objective of this transshipment problem is to determine the maximum output flow from the node of origin O ( $max \sum_{j} x_{Oj}$ ) or the maximum input flow at the destination node T ( $max \sum_{k} x_{kT}$ ), respecting the conservation constraints on the flows between the nodes of origin (O) and output (T), the constraint on conservation of the input and output flows for each one of the intermediate or transhipment nodes, besides the constraint on minimum and maximum limit in each arc.

18.7.1 Mathematical Formulation of the Maximum Flow Problem

The model parameters, the decision variables, and the overall mathematical formulation of the maximum flow problem are specified.

Parameters of the model:

l_ij = minimum limit for the flow in arc (i, j), ∀ i, j

u_ij = maximum limit for the flow in arc (i, j), ∀ i, j

Decision variables:

x_ij = flow in arc (i, j), ∀ i, j

General formulation:

$\begin{array}{l} max z = \sum_{j} x_{Oj} (or max z = \sum_{k} x_{kT}) \\ s . t . \\ \sum_{k} x_{kT} - \sum_{j} x_{Oj} = 0, i = O, T (1) \\ \sum_{k} x_{ki} - \sum_{j} x_{ij} = 0, \forall i \neq O, T (2) \\ l_{ij} \leq x_{ij} \leq u_{ij}, \forall i, j (3) \\ x_{ij} \geq 0, \forall i, j (4) \end{array}$

si73_e (18.15)

that correspond to a linear programming problem.

The objective function therefore seeks to maximize the total outflow from the node of origin of the network (O) to the destination nodes j, or the total input flow at the destination node of the network (T) starting from the nodes of origin k. The constraint (1) guarantees that the total input flow at the destination node of the network (T) is equal to the total outflow at the node of origin of the network (O). The constraint (2) is conservation of the input and output flows for each one of the intermediate or transhipment nodes. As for constraint (3), it guarantees a minimum and maximum flow in arc (i, j). Finally, one has the non-negativity constraints of the decision variables.

Example 18.12

The Petro Duct company transports oil, natural gas, renewable biofuels, and other products, through a solid network of 1,000 kilometers of pipelines. The company seeks to determine the maximum flow of oil (in m³/s) that may be transported over the network in Fig. 18.36, that has as the node of origin (O) the station in Minas and as the destination node (T) a final consumer located in Sao Paulo. The values in the arcs represent the maximum capacities in each arc (in m³/s).

Fig. 18.36 Network of pipelines of the Petro Duct company.

Solution

First, we define the decision variables of the model:

x_ij = oil flow (m³/s) in arc (i, j), ∀ i, j

Thus, we have:

x_OA = oil flow (m³/s) from the Minas station to station A.

x_OB = oil flow (m³/s) from the Minas station to station B.

x_AC = oil flow (m³/s) from station A to station C.

x_AD = oil flow (m³/s) from station A to station D.

x_BC = oil flow (m³/s) from station B to station C.

x_BD = oil flow (m³/s) from station B to station D.

x_CT = oil flow (m³/s) from station C to Sao Paulo.

x_DT = oil flow (m³/s) from station D to Sao Paulo.

The objective function seeks to maximize the total outflow from the Minas station (O):

$max x_{OA} + x_{OB}$

or maximize the total input flow in Sao Paulo (T):

$max x_{CT} + x_{DT}$

The constraints of the model are specified as follows:

1. Input flow in T is equal to the output flow in O:

$x_{CT} + x_{DT} - x_{OA} - x_{OB} = 0 (nodes O and T)$

2. Conservation of the input and output flows in each transhipment node:

$x_{OA} - x_{AC} - x_{AD} = 0 (node A)$

$x_{OB} - x_{BC} - x_{BD} = 0 (node B)$

$x_{AC} + x_{BC} - x_{CT} = 0 (node C)$

$x_{AD} + x_{BD} - x_{DT} = 0 (node D)$

3. Maximum capacity in each arc:

$x_{OA} \leq 50 (arc O, A)$

$x_{OB} \leq 60 (arc O, B)$

$x_{AC} \leq 40 (arc A, C)$

$x_{AD} \leq 60 (arc A, D)$

$x_{BC} \leq 80 (arc B, C)$

$x_{BD} \leq 60 (arc B, D)$

$x_{CT} \leq 50 (arc C, T)$

$x_{DT} \leq 70 (arc D, T)$

4. Nonnegativity constraints:

$x_{OA}, x_{OB}, x_{AC}, x_{AD}, x_{BC}, x_{BD}, x_{CT}, x_{DT} \geq 0$

18.7.2 Solution of the Maximum Flow Problem Using Excel Solver

Example 18.2 of the Petro Duct company referring to the maximum flow problem will be solved in this section using Excel Solver. The representation of the problem in an Excel spreadsheet is illustrated in Fig. 18.37 (see file Example18.12_Petro_duct.xls).

The equations utilized in Fig. 18.37 are specified in Box 18.10.

Box 18.10

Equations Utilized in Fig. 18.37

Cell	Equation
J5	= -D5-D6
K6	= D5-D7-D8
K7	= D6-D9-D10
K8	= D7 + D9-D11
K9	= D8 + D10-D12
I10	= D11 + D12
F16	= D5 + D6

The names attributed to the cells and intervals of cells of Fig. 18.37 are presented in Box 18.11.

Box 18.11

Names Attributed to the Cells of Fig. 18.37

Name	Cells
Flow	D5:D12
Capacity	F5:F12
Flow_outputO	J5
Flow_inputT	I10
Flow_i_o_transhipment	K6:K9
Supply_or_demand	M6:M9
Maximum_flow	F16

The representation of the maximum flow problem of the Petro Duct company (Example 18.12) in the Solver Parameters dialog box is illustrated in Fig. 18.38.

Fig. 18.38 Solver Parameters referring to the maximum flow problem (Example 18.12).

Note that the non-negativity constraints were activated by selecting the Make Unconstrained Variables Non-Negative check box, and the Simplex LP method was selected. The Options command remained unaltered.

Fig. 18.39 presents the optimal solution of the maximum flow problem of the Petro Duct company (Example 18.12).

The optimal FBS is, therefore, x_OA = 50, x_OB = 60, x_AC = 40, x_AD = 10, x_BC = 10, x_BD = 50, x_CT = 50, x_DT = 60 with z = 110.

18.8 Exercises

Ex.1. Consider the following network:

Determine:

a) The set of nodes of the network (N).
b) The set of arcs of the network (A).
c) If a network is directed or undirected.
d) A directed path.
e) An undirected path.
f) A Hamiltonian path.
g) A directed cycle.
h) An undirected cycle.

Ex.2. Same for the following network:

Ex.3. Using the following network, determine:

a) A tree.
b) A spanning tree.

Ex.4. Draw a network that presents the following sets of nodes and arcs:

$N = \{1, 2, 3, 4, 5, 6, 7, 8\}$

$A = \{(1, 3), (1, 4), (2, 1), (2, 4), (3, 4), (3, 5), (4, 6), (5, 7), (6, 3), (6, 5), (6, 8), (7, 6), (8, 7)\}$

Ex.5. Consider the following problem:

$\begin{array}{c} min z = 4 x_{11} + 8 x_{12} + 6 x_{13} + 4 x_{14} + 9 x_{21} + 8 x_{22} + 8 x_{23} + 5 x_{24} + 6 x_{31} + 7 x_{32} + 5 x_{33} + 9 x_{34} \\ s . t . \\ x_{11} + x_{12} + x_{13} + x_{14} = 70 \\ x_{21} + x_{22} + x_{23} + x_{24} = 80 \\ x_{31} + x_{32} + x_{33} + x_{34} = 50 \\ x_{11} + x_{21} + x_{31} = 40 \\ x_{12} + x_{22} + x_{32} = 60 \\ x_{13} + x_{23} + x_{33} = 50 \\ x_{14} + x_{24} + x_{34} = 50 \\ x_{ij} \geq 0, i = 1, 2, 3; j = 1, 2, 3, 4 \end{array}$

si92_e

Represent the problem in networks and determine in what class of problems with network programming it fits, besides the optimal solution.

Ex.6. Same for this problem:

$\begin{array}{l} max z = x_{47} + x_{57} + x_{67} \\ s . t . \\ x_{47} + x_{57} + x_{67} - x_{12} - x_{13} - x_{14} = 0 \\ x_{12} - x_{24} - x_{25} = 0 \\ x_{13} - x_{34} - x_{36} = 0 \\ x_{14} + x_{24} + x_{34} - x_{45} - x_{46} - x_{47} = 0 \\ x_{25} + x_{45} - x_{57} = 0 \\ x_{36} + x_{46} - x_{67} = 0 \\ x_{12} \leq 6 \\ x_{13} \leq 5 \\ x_{14} \leq 7 \\ x_{24} \leq 6 \\ x_{25} \leq 8 \\ x_{34} \leq 6 \\ x_{36} \leq 7 \\ x_{45} \leq 3 \\ x_{46} \leq 4 \\ x_{47} \leq 6 \\ x_{57} \leq 6 \\ x_{67} \leq 3 \\ x_{12}, x_{13}, x_{14}, x_{24}, x_{25}, x_{34}, x_{36}, x_{45}, x_{46}, x_{47}, x_{57}, x_{67} \geq 0 \end{array}$

si93_e

Ex.7. Same for the following problem:

$\begin{array}{l} min z = 3 x_{12} + 2 x_{13} + 5 x_{14} + 4 x_{24} + 4 x_{34} + 4 x_{35} + 6 x_{36} + 5 x_{46} + 4 x_{56} + 4 x_{57} + 5 x_{67} + 3 x_{68} + 3 x_{78} \\ s . t . \\ x_{12} + x_{13} + x_{14} = 1 \\ x_{68} + x_{78} = 1 \\ x_{12} - x_{24} = 0 \\ x_{13} - x_{34} - x_{35} - x_{36} = 0 \\ x_{14} + x_{24} + x_{34} - x_{46} = 0 \\ x_{35} - x_{56} - x_{57} = 0 \\ x_{36} + x_{46} + x_{56} - x_{67} - x_{68} = 0 \\ x_{57} + x_{67} - x_{78} = 0 \\ x_{12}, x_{13}, x_{14}, x_{24}, x_{34}, x_{35}, x_{36}, x_{46}, x_{56}, x_{57}, x_{67}, x_{68}, x_{78} \in \{0, 1\} \end{array}$

si94_e

Ex.8. For a transportation problem with 3 suppliers with capacities for 50, 30, and 20 units, respectively, and 3 consumers with demand for 50, 10, and 40 units, respectively, determine the initial FBS using the northwest corner method.

Ex.9. Obtain the initial basic solution using the minimum cost method for the transportation problem of the Solutions & Ideas company that may be represented in a table form as:

Ex.10. Same using the Vogel approximation method.

Ex.11. For each transportation problem represented here in table form, solve it analytically using the transportation algorithm.

Ex.12. (Source: Adapted from Brito Júnior, 2004). A supply company with head offices in the United States and Europe supplies a production line located in Harbin (northern China). The various materials may be sent from the suppliers directly to the production line in Harbin or undergo a consolidation stage (transhipment) in Brazil (Sao Jose dos Campos), East and West Coasts of the United States (Miami and Los Angeles) or in France (Paris). In this problem, each client may be served by more than one facility. The consolidation points have constraints on maximum capacity.

The objective is to determine the amount of each product that will go directly from the suppliers to the production line in Harbin, and the amount of each product that undergoes the transshipment stage, in order to minimize total logistics costs in the network analyzed, subject to the following conditions:

1. The demand for all of the products should be satisfied;
2. Each consolidation point has a maximum storage capacity;
3. The supply capacity may not be exceeded for each product.

Model the transshipment problem of the company analyzed.

Ex.13. The WLV Ltd. company performs 4 different jobs on 4 distinct machines. The processing times for each job in each machine (in minutes) are listed in the table below. The objective is to designate a set of jobs to a set of machines, so as to minimize the total time spent. Model the problem and solve it using Excel Solver, for each one of the following cases:

a) Each job may only be performed in a single machine.
b) Each machine may perform more than one job at a time.

	Machine
Job	M1	M2	M3	M4
J1	18	12	10	12
J2	10	11	7	8
J3	12	15	8	14
J4	9	10	16	13

Unlabelled Table

Ex.14. An American transportation company makes daily deliveries in the city of New York from the point of origin 1 (Queens) to the point of destination 6 (Manhattan), and may follow several routes, as shown in following figure. The flow in the arcs represents the cost of transporting the necessary demand between the respective boroughs. Describe the mathematical formulation of the problem and determine the best route using Excel Solver.

Ex.15. A company in the petroleum sector is analyzing the movement of its products in a logistics network that has node A as its point of origin and node E as its point of destination, going through intermediate nodes B, C and D. The flow in the arcs represents the time of movement between the respective nodes, in seconds. Determine the fastest path to be traveled, using Excel Solver.

Ex.16. The WT Logistics & Solutions company wishes to determine the maximum amount of product that may be transported from the port of Suape (1) to the port of Santos (6). The other nodes represent the intermediate ports to be visited in the logistics network. The flow in the arcs represents the maximum amount that may be transported (in millions of tons) between the respective ports.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for Chapter 18: Network Programming

Create new playlist

Sign In

Sign Up

18.1 Introduction

18.2 Terminology of Graphs and Networks

18.3 Classic Transportation Problem

18.3.1 Mathematical Formulation of the Classic Transportation Problem

18.3.2 Balancing the Transportation Problem When the Total Supply Capacity Is Not Equal to the Total Demand Consumed

Case 1: Total Supply Is Greater than Total Demand

Case 2: Total Supply Capacity Is Lower than Total Demand Consumed

18.3.3 Solution of the Classic Transportation Problem

18.3.3.1 The Transportation Algorithm

18.3.3.2 Solution of the Transportation Problem Using Excel Solver

18.4 Transhipment Problem

18.4.1 Mathematical Formulation of the Transhipment Problem

18.4.2 Solution of the Transhipment Problem Using Excel Solver

18.5 Job Assignment Problem

18.5.1 Mathematical Formulation of the Job Assignment Problem

18.5.2 Solution of the Job Assignment Problem Using Excel Solver

18.6 Shortest Path Problem

18.6.1 Mathematical Formulation of the Shortest Path Problem

18.6.2 Solution of the Shortest Path Problem Using Excel Solver

18.7 Maximum Flow Problem

18.7.1 Mathematical Formulation of the Maximum Flow Problem

18.7.2 Solution of the Maximum Flow Problem Using Excel Solver

18.8 Exercises

Table of Contents for
Chapter 18: Network Programming