Now let's take a look at some special network flow models. There are several reasons to introduce them. First, they are useful and they have all kinds of practical applications. The second, they are famous, especially if you're studying the field of information management and computer science or industrial engineering, typically you should have heard about those maximum flow, shortest paths, assignment problem, and so on. Let's take a look at what are them and how to solve them, how to deal with them from the OR perspective. Let's take a look at all these well-known problems. Transportation problem, assignment problem, transshipment problem, maximum flow problem, and the shortest paths problems. We will give an introduction to all of them and try to formulate them. Once we do that, we know if any of these problem may be formulated as an integer program, as an MCNF problem in this case, we are done in solving that. Because once we are able to formulate that as the integer program, our solver, our grow b, our branch and bound whatever will be able to solve it in the final solution. Because it is an MCNF, if it can be solved in a very fast way, in a very short time, then in that case, we actually don't need to worry about special algorithms. Our model is actually OR solution. I won't say that those special algorithms are not useful because in practice, if you really solve very large-scale transportation or very large-scale maximum flow problems, those specially defined, determined, developed algorithms are still helpful are still faster in general than the simplex method. That makes sense because the simplex method is not designed to solve these special problems. When you look at each special problem and if you look at its special property, your special algorithms should outperform the general simplex method. It's just that in many cases, when you are just looking at practical practice, you don't really need to decide algorithms by yourself, or you are unable to decide algorithms by yourselves. Then a model which gives you a solution quickly, actually still helps a lot. That's the reason for us to do this. If we want to introduce all these special algorithms, we need a one semester course to talk about all these network flow problems. But today, we will finish the introduction very quickly by just giving you those LP or IP formulations. Let's start with our transportation problem. Let's say there is a firm owning n factories and they supply one product to m markets. The capacity of factory i is called s_i, so that's the amount they can produce. For demand for market j is d_j and that's the amount of items they need at that market. Between factory i and market j, there is a route, there is a link, and there is a unit cost for shipping one unit along that route, along that link, that's c_ij. Our decision is to produce and ship products to fulfill all demands while minimizing the total cost. Obviously this is a special case of MCNF. Lets see why. Basically, we need to first assume that all the supply is equal to all the demand. Later we will see what will happen if this is not true. Suppose this is the case. We may say x_ij is the shipping quantity on arc i, j. Then this is MCNF. If we consider those supply nodes as factories, demand nodes as markets and the supply quantities are either s_i, the real supply capacity or negative d_j which is the demand quantity. The supply quantity at demand nodes are actually the negative demand qualities to fit the idea, to fit the formulation of MCNF. Compared to MCNF, in our transportation problem, there is no transshipment nodes. Each node is either a factory or of market. Arc weights are considered as unit transportation cost and then there is no capacity constraints. You may also say that those u_ij are all unlimited. This is a transportation problem considered as an MCNF. Obviously we need to take care of those variants. For example, it's possible that you are sum of s_i is greater than your d_j. That somehow means the total capacity is enough to satisfy all the demands and you still don't need to use all of them. In this case, you may still consider it as an MCNF because all you need to do is to create a virtual market where the demand size is the difference between the capacity and the true demand. If you need to ship anything to there, the cost would be set to zero. The sum shipping quantity simply means the capacity is unused. This somehow help us to again formulate a transportation problem as an MCNF problem with no difficulty. Even if in practice you have this, you still are able to deal with that by having a virtual node. It's also possible that your costs are not just on routes. You also have costs on factories or on retail sites or markets. In that case, all you need to do is to update your c_ij. For example, if Factory 1 has its capacity cost, then all you need to do is to carry that cost and put the cost to all those outgoing links from factory i, then you are done. In that case, this is nothing but some variants of transportation problems. But that allows us to formulate the transportation problems into an MCNF problem.
