Introduction

So far, we have studied the problem of linear programming in general. In this section, we will examine specific types of linear programming problems. In this section, we first examined the general model of minimum cost flow, and then we will examine the specific model of flow in the network, here the transportation problem.

Minumum cost flow problem

In the problem of minimum cost flow, we are looking for homogeneous product distribution from the factory (origin) to the sales market (destination). Suppose the number of products manufactored in each factory and the number of required products are known. Also, it is not necessary to send the products directly to the destinations, but it is possible to send it to the distribution centers through an intermediate point. In addition, transportation lines are limited in terms of line capacity. The goal in this issue is to minimize the cost of transporting products.

Consider a numerical example of the minimum cost flow problem in the figure below. Nodes are represented by numbered circles and arcs by arrows. Arcs are directional. For example, materials can be sent from node 1 to node 2, but this is not possible from node 2 to node 1. We denote the arc from node i to node j as i-j.

In the above figure, each arc is given a capacity and cost per unit of transportation, which is given next to each arc. For example, in arc (2-4), the flow can be from 0 to 4 units, and the cost of each unit passing through this arc is $2. The symbol ∞ means unlimited capacity. Finally, the numbers in parentheses next to the nodes show the amount of supply and demand. In this figure, node 1 is the origin and the amount of supply is equal to 20 units, and nodes 4 and 5 are the destinations that need 5 and 15 units, and it is the demand that is indicated by the sign -.

In the minimum cost flow problem, the goal is to find the flow pattern with minimum cost. To transform the problem into linear programming, suppose:

x_ij: is the number of units transported from node i to node j using arc i-j.

The linear programming model of minimum cost flow is presented as follows.

Equations 1 to 5 are the flow balance equations in the network. For example, the balance flow equation at node 1 is as follows.

The above equation states that the output flow from node 1 (x₁₂+x₁₃) should be equal to the supply of node 1 (20).

The balance equation in node 2 states that the input flow to node 2 (x₁₂ ) is equal to the output flow from node 2 (x₂₃+x₂₄+x₂₅ ).

The minimum cost flow model in the network has a special structure that is used to provide the solution order. Flow variables x_ij in balance equations only get 0, +1 and -1 coefficients. In addition, they appear exactly in two balance equations: once with a coefficient of +1 corresponding to the node from which they originate and -1 corresponding to the node to which they enter. According to the above, the general form of the Minumum Cost Flow is expressed as follows.

The above model is the general model of minimum cost flow. The above model can be converted into simpler forms, which we will describe below.

Minimum spanning tree

In this problem, it is considered to connect different nodes of a network to each other so that the minimum distance is established. Arcs connecting nodes (points) are undirected. Some examples of the application of this problem are:

1- A company in the construction of its central building wants to use the least amount of electric cable for the supply of electricity to various points in that building.

2- The Ministry of Roads is looking for a way to connect the villages of the same region based on which the length of the connecting roads is minimal.

3- The Water and Sewerage Department intends to use the shortest length of pipe to create a water supply network in a town under construction.

Minimum spanning tree algorithm

Assuming that there are n number of points (nodes) numbered from 1 to n in the given problem, the steps of the algorithm are as follows:

Step 1: Form an n*n square matrix of distances between points 1 to n.

Step 2: Start from an arbitrary point and find the shortest distance between that point and other points. For this purpose, the row corresponding to the selected point should be taken out of the main matrix and form a 1*n matrix and choose the smallest number in this matrix. In this case, the selected number is the shortest distance of the selected point. Consider the latter point as the second point.

Step 3: In this step, form the 2*n matrix related to the two indicated points and select the smallest number inside the matrix to get the third point as well. Continue like this until all points are selected.

Step 4: The order of obtaining these points indicates the order of optimal movement in the tree, and the sum of the distances in this tree will be the minimum possible distance to connect the points.

Note: If there are two or more equal numbers in the matrix at a stage, there will be two or more solutions to the problem.

Example:

In a building, electrical wiring must be done between six points with the distances listed in the matrix below. The symbol d for the distance between two points in the matrix indicates the impossibility of wiring between them. Using the minimum spanning tree algorithm, determine the minimum wiring tree and obtain the minimum amount of wires used.

Solution:

In stage 1 (k=1), a point should be chosen arbitrarily. Here point 1 is selected (any other point could also be selected). The corresponding 1*6 matrix is formed as follows:

In this matrix, the smallest number is equal to 1, which is marked with a square sign around it. This number corresponds to the distance between point 1 and point 2, and as a result, the shortest distance to point 2 was obtained.

In stage 2 (k=2), point 2, which is the shortest distance to it determined in the previous step, is added to the 1*6 matrix and the following 2*6 matrix is created.

Note that since points 1 and 2 have been assigned, in the matrix above, a mark “–“ is inserted in columns 1 and 2, which means that it is not necessary to check these points. In this matrix, the smallest number is equal to 3 and corresponds to the distance between point 2 and point 5, and therefore the shortest distance to point 5 was also obtained.

In stage 3 (k=3) by increasing row 5, 3*6 matrix is created:

In stage 4, the smallest number in this matrix is equal to 4 and corresponds to the distance between point 2 and point 4, and therefore the shortest distance to point 4 is obtained. In the same way, the next steps are also performed, whose matrices are:

The matrix of stage 5 (k=5) is as follows:

In stage 5 (k=5), it can be seen that there are three numbers equal to 6 as the smallest number in this matrix, so the problem has three solutions. That is, for wiring electricity to point 3, you can proceed from any of points 1, 2 or 4. Because the shortest distance to all points was obtained, and the algorithm ends. Three solutions to the problem (minimum spanning tree) are given in the figure below.