**The Transportation Problem**Suppose you own a manufacturing company and its your job to ship your product from warehouse locations all across the United States to a number of customers. Each customer has ordered a certain quantity of the item, and each warehouse can supply up to a certain amount. Then we define the following variables: m = the number of warehouses n = the number of customers a

_{i}= the total amount of item available at warehouse i b

_{j}the total requirement of customer j x

_{i, j}= the amount of item shipped from warehouse i to customer j. In order for things to work properly, we need that the total amount in supply is equal to the the total amount ordered. If we assumed that we have 3 customers and 2 warehouses, then the following constraints help formulate this problem. x

_{1, 1}+ x

_{1, 2}+ x

_{1, 3}= a

_{1}x

_{2, 1}+ x

_{2, 2}+ x

_{2, 3}= a

_{2}x

_{1, 1}+ x

_{2, 1}= b

_{1}x

_{1, 2}+ x

_{2, 2}= b

_{2}x

_{1, 3}+ x

_{2, 3}= b

_{3}You also know the cost of shipping one unit of the item from warehouse i to customer j and label it c

_{i, j}. Then the objective function which we seek to minimze is c

_{1, 1}x

_{1, 1}+ c

_{1, 2}x

_{1, 2}+ c

_{1, 3}x

_{1, 3}+ c

_{2, 1}x

_{2, 1}+ c

_{2, 2}x

_{2, 2}+ c

_{2, 3}x

_{2, 3}. And we also have that x

_{i, j}is nonnegative since we are shipping (and not receiving) goods. Because we can state this problem as a linear programming problem, we can solve it using the simplex method. Although this problem was very simple to formulate, the ability to formulate a problem as a linear programming problem is seen as a great accomplishment because there exists so much literature on linear programming problems, and a method on how to solve them, (i.e. the Simplex method). For this reason, much work is often dedicated to finding good linear programming representations of problems. Another set of problems of interest are integer programming problems. These problems add the additional requirement to linear programming problems that some or all of these variables can only take on a discrete set of values instead of a continuous realm. Integer programming problems are generally thought to be more difficult to solve than linear programming problems. What makes integer programming problems special is the fact that many problems that are known to be just as difficult as integer programming problems can be formulated as integer programming problems. Although the Simplex Method does not promise to always solve these problems to optimality, it offers a way to approach integer programming problems, and thus every problems that is known to be just as hard these problems which is at least a starting point.