Note 23 Oct 2024 PDF

# Special Types of Linear Programming Problems ## Chapter 5: Special Types of Linear Programming Problems ## N THIS CHAPTER we study a number of special types of linear programming problems - These problems arise in transportation systems, in communication systems, in pipeline systems, in electri...

# Special Types of Linear Programming Problems ## Chapter 5: Special Types of Linear Programming Problems ## N THIS CHAPTER we study a number of special types of linear programming problems - These problems arise in transportation systems, in communication systems, in pipeline systems, in electrical networks, in the planning and scheduling of projects, and in many other applications. - Each of these problems can be formulated and solved as a linear programming problem. - However, because of their special structure these problems can be more effectively solved by other methods that have been specifically developed to handle them. ## 5.1 The Transportation Problem - We have previously considered two examples of the transportation problem-Example 3 in Section 1.1 and Example 1 in Section 4.1. - We present another example here that will be used to indicate the ways in which the simplex method can be adapted to the special structure of this problem. - Our eventual goal is the transportation algorithm. ## Example 1 - The plastic manufacturing company described in Example 3 of Section 1.1 has decided to build a combination plant-warehouse in San Antonio. This expansion will give it three plants and four warehouses. - The following shipping costs have been determined for the new plant and warehouse: - From Salt Lake City to Los Angeles is $6. - From Salt Lake City to Chicago is $5. - From Salt Lake City to New York City is $140. - From Salt Lake City to San Antonio is $1. - From Denver to Los Angeles is $7. - From Denver to Chicago is $6. - From Denver to New York City is $8. - From Denver to San Antonio is $0. - From San Antonio to Los Angeles is $100. - From San Antonio to Chicago is $60. - From San Antonio to New York City is $80. - From San Antonio to San Antonio is $120. - The San Antonio plant can supply 100 tons per week, and the warehouse needs 120 tons per week to meet its demand. - We want to determine how many tons of sheet polyethylene should be shipped from each plant to each warehouse to minimize the transportation cost. ## Mathematical Model The cost matrix is given by $C = \begin{bmatrix} 5 & 7 & 9 & 6 \\ 6 & 7 & 10 & 5 \\ 7 & 6 & 8 & 1 \end{bmatrix}$ where we have labeled the rows with the points of origin and the columns with the destinations. The supply vector is $s = \begin{bmatrix} 120 \\ 140 \\ 100 \end{bmatrix}$ and the demand vector is $d = \begin{bmatrix} 100 \\ 60 \\ 80 \\ 120 \end{bmatrix}$ We let $x_{ij}$ denote the amount shipped from the ith plant to the jth warehouse, where the plants and warehouses are numbered as in Equation (1). Our model is to minimize $z = \sum_{i=1}^{4}\sum_{j=1}^{3} c_{ij}x_{ij}$ subject to $\sum_{j=1}^{4} x_{ij} \le s_i, i = 1,2,3$ $\sum_{i=1}^{3} x_{ij} \ge d_j, j = 1,2,3,4$ $x_{ij} \ge 0, Integers.$ Clearly the company must be able to provide a supply of polyethylene at least equal to the demand. In our example, we have $\sum_{i=1}^{3} s_i = 360 = \sum_{j=1}^{4} d_j.$ Later, we will indicate what to do if supply exceeds demand. We will say that the model is infeasible if demand exceeds supply. The student may show that, when demand equals supply, each of the constraints in (2) is an equality. We will now develop an algorithm for solving the general transportation problem Minimize $z = \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}x_{ij}$ subject to $\sum_{j=1}^{n} x_{ij} = s_i, i = 1,2,.., m$ $\sum_{i=1}^{m} x_{ij} = d_j, j = 1,2,..,n$ $\sum_{i=1}^{m} s_i = \sum_{j=1}^{n} d_j$ $x_{ij} \ge 0, Integers.$ This form of the transportation problem has the following properties: 1. The problem always has a feasible solution (Exercise 17). 2. The set of feasible solutions is bounded (Exercise 18). 3. Because of (4), one of the m+n constraints in (3) is redundant. 4. We may substitute the values for the coefficients in our model and write it as Minimize $z = 5x_{11} + 7x_{12} + 9x_{13} + 6x_{14} + 6x_{21} + 7x_{22} + 10{x_{23}} + 5x_{24} + 7x_{31} + 6x_{32} +8x_{33} + x_{34}$ subject to $x_{11} + x_{12} + x_{13} + x_{14}=120$ $x_{21} + x_{22} + x_{23} + x_{24}=140$ $x_{31} + x_{32} + x_{33} + x_{34}=100$ $x_{11} + x_{21} + x_{31}=100$ $x_{12} + x_{22} + x_{32}=60$ $x_{13} +x_{23} + x_{33} = 80$ $x_{14} + x_{24} + x_{34} = 120$ $x_{ij} \ge 0, Integers, i = 1,2,3, j = 1,2,3,4.$ Note that each variable appears in exactly two constraints. Since there are seven constraints in the problem, we expect that there will be seven nonzero variables in a basic feasible solution. Actually, there will be only six nonzero variables in any basic feasible solution, because one constraint is redundant. This redundancy occurs because the supply is equal to the demand. - The model can be solved by the simplex algorithm, and its solutions will always be an integer vector, since the constraint matrix contains only 0's and 1's. - However, there is a much more efficient algorithm that uses a 3×4 tableau instead of the 6×12 tableau for the simplex algorithm. - We construct the transportation tableau by writing a 3×4 matrix to hold the values of xij. The supply vector is placed to the right of this matrix, the transpose of the demand vector is written below the matrix, and the unit costs are written in the insets. ## For our problem, we obtain Tableau 5.1 | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | | | | | | 120 | | 6| | | | | 140 | | 7 | | | | | 100 | | | 100 | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply Demand There are several ways of systematically filling in the tableau with values for $x_{ij}$ . For now, we start by allocating as much of the supply in row 1 (from plant 1) as possible to the cheapest route. This means $x_{11}=100$, which satisfies the demand in the first column and leaves 20 units to be allocated to the next cheapest route in the first row. We set $x_{14} = 20$, which exhausts the supply from the first plant. Consequently, x12 = x13 = 0. - Moving to the second row, we follow the same procedure of allocating as much as possible to the cheapest route. - We set $x_{24} = 100$, since 20 units have already been provided in row 1. - The 40 remaining units from plant 2 are shipped to warehouse 2, since that route is the cheapest remaining one. - The rest of the tableau is filled in using the same reasoning. - Observe that the solution represented by Tableau 5.2 is a basic feasible solution. There are six nonzero variables. - Later, we will develop a technique to show that the columns of the simplex tableau corresponding to these variables are linearly independent. | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | 5 | 100 | 0 | 0 | 20 | 120 | | 6| 0 | 40 | 0 | 100 | 140 | | 7 | 0 | 0 | 80 | 0 | 100 | | | | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply BV - Non Zero cells $x_{11}, x_{14}, x_{22}, x_{32}, x_{33}, x_{24}$ NON BV - $x_{12}, x_{13}, x{21}, x_{23}, x_{31}, x_{34}$ Demand Have we found the minimum cost solution? - Our scheme for distributing the polyethylene represents $2160 in transportation costs. - It is most likely not the minimum, since no goods made in San Antonio are shipped to San Antonio. We now look for a way of systematically modifying our initial solution to arrive at the minimum cost distribution scheme in a small number of steps. - For each of the unused routes, routes along which no goods were shipped, we calculate the change in the total shipping cost due to shipping one unit of goods along that route subject to the restriction that the corresponding changes must be made in the used routes. - For example, shipping one unit from plant 1 to warehouse 2 ($x_{12}=1$) leads to the modifications of Tableau 5.2 as shown in Tableau 5.3. | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | 5 | 100 | 1 | 0 | 19 | 120 | | 6| 0 | 39 | 0 | 101 | 140 | | 7 | 0 | 0 | 80 | 0 | 100 | | | | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply Demand The change in the total shipping cost due to this one modification is 7- 6 - 7 + 5 = -1. - That is, the total shipping cost for the modified tableau (Tableau 5.4) is $2159. - Thus, the cost has decreased and we have improved our solution by $1. <start_of_image> Table 5.4 | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | 5 | 100 | 0 | 20 | 0 | 120 | | 6| 0 | 40 | 0 | 100 | 140 | | 7 | 0 | 20 | 80 | 0 | 100 | | | | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply Demand We now compute the possible improvements for each of the unused routes. - There are six unused routes shown in Tableau 5.2, namely, (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), and (3, 4). - In doing these computations remember that all changes that are forced by the initial change must be assigned to a route that is being used. - Thus, in computing the possible improvement for route (3,4), for example, we have two choices for decreasing by 1 the amount shipped along a route in use. We may choose either (1, 4), or (2, 4). - However, only the choice of (2, 4) works, since choosing (1, 4) leads to a change in an unused route that cannot be balanced with a corresponding change in a route that is being used. - These two cases are illustrated in Tableaux 5.5 and 5.6. | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | 5 | 100 | 0 | 20 | 0 | 120 | | 6| 1 | 39 | 0 | 100 | 140 | | 7 | 0 | 21 | 79 | 0 | 100 | | | | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply Demand This case works | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | 5 | 101 | 0 | 19 | 0 | 120 | | 6| 0 | 39 | 0 | 101 | 140 | | 7 | 1 | 20 | 79 | 0 | 100 | | | | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply Demand Cannot balance this increase We show in Tableaux 5.7a-5.7f (displayed in abbreviated form) the modifications that would have to be made to the amounts shipped as shown in Tableau 5.2 if each of the unused routes were brought into the solution. - The corresponding change in cost is noted below each tableau. - We see that the shipping cost would be substantially reduced if we allocated more to routes (2, 2) and (3, 4) and then modified routes (3, 2) and (2, 4) accordingly. | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | 5 | 100 | 0 | 21 | 0 | 120 | | 6| 0 | 39 | 0 | 101 | 140 | | 7 | 1 | 20 | 79 | 0 | 100 | | | | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply Demand Cost decreases by 1 | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | 5 | 100 | 1 | 19 | 0 | 120 | | 6| 0 | 38 | 0 | 102 | 140 | | 7 | 0 | 21 | 79 | 0 | 100 | | | | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply Demand Cost decreases by 1 | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | 5 | 99 | 1 | 20 | 0 | 120 | | 6| 1 | 39 | 0 | 99 | 140 | | 7 | 0 | 20 | 80 | 0 | 100 | | | | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply Demand Cost increases by 2 | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | 5 | 100 | 0 | 20 | -1 | 120 | | 6| 0 | 40 | 1 | 99 | 140 | | 7 | 1 | 19 | 79 | 0 | 100 | | | | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply Demand Cost increases by 1 | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | 5 | 99 | 0 | 21 | 0 | 120 | | 6| 1 | 40 | 9 | 99 | 140 | | 7 | 0 | 19 | 79 | 0 | 100 | | | | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply Demand Cost increases by 4 | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | 5 | 100 | 0 | 20 | -1 | 120 | | 6| 0 | 40 | 0 | 101 | 140 | | 7 | 0 | 20 | 80 | 1 | 100 | | | | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply Demand Cost decreases by 3 If we set $x_{34} = 20$ [the largest amount by which we can decrease route (3, 2)] and increase $x_{22}$ by 20, then we get Tableau 5.8, which represents a tableau whose total shipping cost is $2100. Consequently, Tableau 5.2 did not represent an optimal solution. | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | 5 | 100 | 0 | 20 | 0 | 120 | | 6| 0 | 60 | 0 | 80 | 140 | | 7 | 0 | 0 | 60 | 40 | 100 | | | | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply Demand By developing a way to easily compute the possible improvements, we shall see how to reallocate shipments and how to determine when an optimal solution has been reached. - We first formulate the dual problem to the transportation problem. - Let $u_1, u_2$ , and $u_3$ be the dual variables corresponding to the supply constraints, and let $w_1, w_2, w_3$, and $w_4$ be the dual variables corresponding to the demand constraints. - Then the dual problem to the transportation problem (5) is Maximize $z' = \sum_{i=1}^{3} s_iu_i + \sum_{j=1}^{4} d_jw_j$ subject to $u_i + w_j \le c_{ij}, i = 1,2,3, j = 1,2,3,4$ $u_i, w_j unrestricted.$ Tableau 5.2 represents the initial basic feasible solution to the transportation problem with basic variables $x_{11}, x_{14}, x_{22}, x_{24}, x_{32}$, and $x_{33}$. - Since the variables $x_{ij}$ of the transportation problem are doubly indexed, so are the imputed values $z_{ij}$, and from the properties of the simplex algorithm, $z_{ij} = c_{ij}$ when $x_{ij}$ is a basic variable. - It follows from the discussion of complementary slackness in Section 3.2 that there are values for the dual variables for which the left-hand side of the dual constraint $u_i + w_j \le c_{ij}$ is equal to $z_{ij}$ , for all i and j. This gives six equations in seven unknowns. The values of the dual variables can be found from (6) by giving one of the unknowns—say, the one that appears most often—an arbitrary value—say, 0—and then solving for the remaining unknowns. Our system is $x_{11}: u_1 + w_1 = 5$ $x_{14}: u_1 + w_4 = 6$ $x_{22}: u_2 + w_2= 7$ $x_{24}: u_2 + w_4 = 5$ $x_{32}: u_3 + w_2 = 6$ $x_{33}: u_3 + w_3 = 8.$ Setting $u_i = 0$, we have $u_2 = -1, u_3 = -2, w_1 = 5, w_2 = 8, w_3 = 10$, and $w_4 = 6.$ Now the entries in the objective row of the simplex tableau corresponding to the solution in Tableau 5.2 can be determined. The only nonzero entries will be those for the nonbasic variables. - Each entry will be of the form $z_{ij} - c_{ij} = u_i + w_j - c_{ij}$ since $z_{ij}$ is the left-hand side of the (i, j) constraint of the dual problem. The entries are $x_{12}: u_1 + w_2 - c_{12}= 0 + 8 -7 = 1$ $x_{13}: u_1 + w_3 - c_{13} = 0 + 10 -9 = 1$ $x_{21}: u_2 + w_1 - c_{21}= -1 + 5 - 6=-2$ $x_{23}: u_2 + w_3 - c_{23}= -1 + 10 - 10 = -1$ $x_{31}: u_3 + w_1 - c_{31} = -2 + 5 -7 = -4$ $x_{34}: u_3 + w_4 - c_{34} = -2 + 6 - 1 = 3$ Since we are dealing with a minimization problem, the largest positive value determines the entering variable. In this case, it is x34. - To determine the departing variable, examine route (3,4). - If we try to send one unit along unused route (3, 4) and make the corresponding modification in the routes that are being used (basic variables), we have Tableau 5.9. - The total shipping cost is changed by 7-5-6+1 = -3 (Note: ($u_3+ w_4 -c_{34} = 3)$ | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | 5 | 100 | 0 | 20 | 0 | 120 | | 6| 0 | 40 | 1 | 99 | 140 | | 7 | 0 | 21 | 79 | 0 | 100 | | | | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply Demand so that it has been reduced by $3. We can send as many as 20 units along route (3, 4), so that if $x_{34}=20$, we drive $x_{32}$ to zero. - Thus, $x_{32}$ becomes the departing variable. - Modifying Tableau 5.2, we obtain Tableau 5.8, as we did before. - Since each unit sent along route (3,4) reduced the total shipping cost by $3, when 20 units are sent the cost should be reduced by $60. Indeed, the cost represented by Tableau 5.8 is $2100. We now give the calculations necessary to determine the next tableau. - The system of equations relating the dual variables is $x_{11}: u_1 + w_1 = 5$ $x_{14}: u_1 + w_4 = 6$ $x_{22}: u_2 + w_2 = 7$ $x_{24}: u_2 + w_4 = 5$ $x_{33}: u_3 + w_3 = 8$ $x_{34}: u_3 + w_4 = 1.$ To obtain a solution to this system of six equations in seven unknowns, we arbitrarily set $w_1 = 0$, obtaining $u_1 = 6, u_2 = 5, u_3 = 1, w_1 = -1, w_2 = 2$, and $w_3 = 7$ Consequently, the values of $z_{ij} - c_{ij}$ for the nonbasic variables are $x_{12}: u_1+w_2 -c_{12} = 6 + 2 - 7 = 1$ $x_{13}: u_1 + w_3 - c_{13} = 6 + 7 - 9 = 4$ $x_{21}: u_2 + w_1 - c_{21}= 5 - 1 - 6 = -2$ $x_{23}: u_2 + w_3 - c_{23} = 5 + 7 - 10 = 2$ $x_{31}: u_3 + w_1 - c_{31} = 1 - 1 - 7 = -7$ $x_{32}: u_3 + w_2 - c_{32} = 1 +2 - 6 = -3.$ The entering variable is $x_{13}$ . If we send one unit along the unused route (1,3) and make the modifications in the routes being used (basic variables), we have Tableau 5.10. - The total shipping cost is changed by $9 - 6 - 8 + 1 = -4$ (Note: ($u_1 + w_3 - c_{13} = 4$ | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | 5 | 100 | 0 | 20 | 0 | 120 | | 6| 0 | 60 | 0 | 80 | 140 | | 7 | 0 | 0 | 60 | 40 | 100 | | | | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply Demand so that it has been reduced by $4. We can send as many as 20 units along route (1,3) so that, if $x_{13} = 20$, we drive $x_{14}$ to 0. - Thus, $x_{14}$ becomes the departing variable. - Modifying Tableau 5.8, we obtain Tableau 5.11. - Since each unit sent along route (1,3) reduced the total shipping cost by $4, when 20 units are sent the cost should be reduced by $80. - Indeed, the cost represented by Tableau 5.11 is $2020. | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | 5 | 100 | 0 | 20 | 0 | 120 | | 6| 0 | 60 | 0 | 80 | 140 | | 7 | 0 | 0 | 60 | 40 | 100 | | | | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply Demand Performing these steps several more times, we come to the point at which no entering variable can be chosen (all $z_{ij} - c_{ij}$ are negative because this is a minimization problem), and the procedure stops. - An optimal solution has been obtained; it is given in Tableau 5.12. - The cost of this solution is $1900. - Note that it chooses the plant in San Antonio to supply all the demand of the San Antonio warehouse. | | 5 | 7 | 9 | 6 | | | --- | --- | --- | --- | --- | --- | | 5 | 100 | 0 | 20 | 0 | 120 | | 6| 0 | 60 | 0 | 80 | 140 | | 7 | 0 | 0 | 60 | 40 | 100 | | | | | | | | | | | 60 | | | | | | | | 80 | | | | | | | | 120 | | | | | | | | | Supply Demand We formalize the procedure used in this example as "the transportation algorithm". - Given the transportation problem $Minimize z = \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}x_{ij}$ subject to $\sum_{j=1}^{n} x_{ij} = s_i, i = 1,2,..., m$ $\sum_{i=1}^{m} x_{ij} = d_j, j = 1,2,..., n$ $\sum_{i=1}^{m} s_i = \sum_{j=1}^{n} d_j$ $x_{ij} \ge 0, Integers$ - We choose an initial basic feasible solution using the minimum cost rule. - For each row $i = 1,2,..., m$