版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 1 Chapter 7 Transportation, Assignment and Transshipment Problems to accompany Introduction to Mathematical Programming: Operations Research, Volume 1 4th edition, by Wayne L. Winston and Munirpallam Venkataramanan Presentation: H. Sar
2、per, modified by MGS Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 2 Description A transportation problem basically deals with the problem, which aims to find the best way to fulfill the demand of n demand points using the capacities of m supply points. While trying to find the be
3、st way, generally a variable cost of shipping the product from one supply point to a demand point or a similar constraint should be taken into consideration. Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 3 7.1 Formulating Transportation Problems Example 1: Powerco has three electr
4、ic power plants that supply the electric needs of four cities. The associated supply of each plant and demand of each city is given in the table 1. The cost of sending 1 million kwh of electricity from a plant to a city depends on the distance the electricity must travel. Copyright 2003 Brooks/Cole,
5、 a division of Thomson Learning, Inc. 4 Transportation tableau A transportation problem is specified by the supply, the demand, and the shipping costs. So the relevant data can be summarized in a transportation tableau. The transportation tableau implicitly expresses the supply and demand constraint
6、s and the shipping cost between each demand and supply point. Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 5 Table 1. Shipping costs, Supply, and Demand for Powerco Example FromTo City 1City 2City 3City 4Supply (Million kwh) Plant 1$8$6$10$935 Plant 2$9$12$13$750 Plant 3$14$9$16$
7、540 Demand (Million kwh) 45203030 Transportation Tableau Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 6 Solution Decision Variable: Since we have to determine how much electricity is sent from each plant to each city, let Xij = Amount of electricity produced at plant i and sent t
8、o city j X14 = Amount of electricity produced at plant 1 and sent to city 4, for instance Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 7 2. Objective function Since we want to minimize the total cost of shipping from plants to cities; Minimize Z = 8X11+6X12+10X13+9X14 +9X21+12X22
9、+13X23+7X24 +14X31+9X32+16X33+5X34 Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 8 3. Supply Constraints Since each supply point has a limited production capacity; X11+X12+X13+X14 35 X21+X22+X23+X24 50 X31+X32+X33+X34 40 Copyright 2003 Brooks/Cole, a division of Thomson Learning,
10、Inc. 9 4. Demand Constraints Since each demand point has a minimum requirement: X11+X21+X31 45 X12+X22+X32 20 X13+X23+X33 30 X14+X24+X34 30 Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 10 5. Sign Constraints Since a negative amount of electricity can not be shipped all Xijs must
11、be nonnegative; Xij 0 (i= 1,2,3; j= 1,2,3,4) Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 11 LP Formulation of Powercos Problem Min Z = 8X11+6X12+10X13+9X14+9X21+12X22+13X23+7X24 +14X31+9X32+16X33+5X34 S.T.:X11+X12+X13+X14 35 (Supply Constraints) X21+X22+X23+X24 50 X31+X32+X33+X3
12、4 40 X11+X21+X31 45 (Demand Constraints) X12+X22+X32 20 X13+X23+X33 30 X14+X24+X34 30 Xij 0 (i= 1,2,3; j= 1,2,3,4) Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 12 General Description of a Transportation Problem A set of m supply points from which a good is shipped. Supply point i
13、 can supply at most si units. A set of n demand points to which the good is shipped. Demand point j must receive at least di units of the shipped good. Each unit produced at supply point i and shipped to demand point j incurs a variable cost of cij. Copyright 2003 Brooks/Cole, a division of Thomson
14、Learning, Inc. 13 Xij = number of units shipped from supply point i to demand point j ),.,2 , 1;,.,2 , 1(0 ),.,2 , 1( ),.,2 , 1(. . min 1 1 11 njmiX njdX misXts Xc ij mi i jij nj j iij mi i nj j ijij Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 14 Balanced Transportation Problem
15、If Total supply equals total demand, the problem is said to be a balanced transportation problem: nj j j mi i ids 11 Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 15 Balancing a TP if total supply exceeds total demand If total supply exceeds total demand, we can balance the proble
16、m by adding dummy demand point. Since shipments to the dummy demand point are not real, they are assigned a cost of zero. Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 16 Balancing a transportation problem if total supply is less than total demand If a transportation problem has a
17、 total supply that is strictly less than total demand the problem has no feasible solution. There is no doubt that in such a case one or more of the demand will be left unmet. Generally in such situations a penalty cost is often associated with unmet demand and as one can guess this time the total p
18、enalty cost is desired to be minimum Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 17 7.2 Finding Basic Feasible Solution for TP Unlike other Linear Programming problems, a balanced TP with m supply points and n demand points is easier to solve, although it has m + n equality cons
19、traints. The reason for that is, if a set of decision variables (xijs) satisfy all but one constraint, the values for xijs will satisfy that remaining constraint automatically. Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 18 Methods to find the bfs for a balanced TP There are thr
20、ee basic methods: Northwest Corner Method Minimum Cost Method 1.Vogels Method Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 19 1. Northwest Corner Method To find the bfs by the NWC method: Begin in the upper left (northwest) corner of the transportation tableau and set x11 as larg
21、e as possible (here the limitations for setting x11 to a larger number, will be the demand of demand point 1 and the supply of supply point 1. Your x11 value can not be greater than minimum of this 2 values). Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 20 According to the explan
22、ations in the previous slide we can set x11=3 (meaning demand of demand point 1 is satisfied by supply point 1). 5 6 2 3523 Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 21 After we check the east and south cells, we saw that we can go east (meaning supply point 1 still has capaci
23、ty to fulfill some demand). Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 22 After applying the same procedure, we saw that we can go south this time (meaning demand point 2 needs more supply by supply point 2). Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 23 F
24、inally, we will have the following bfs, which is: x11=3, x12=2, x22=3, x23=2, x24=1, x34=2 Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 24 2. Minimum Cost Method The Northwest Corner Method does not utilize shipping costs. It can yield an initial bfs easily but the total shipping
25、 cost may be very high. The minimum cost method uses shipping costs in order come up with a bfs that has a lower cost. To begin the minimum cost method, first we find the decision variable with the smallest shipping cost (Xij). Then assign Xij its largest possible value, which is the minimum of si a
26、nd dj Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 25 After that, as in the Northwest Corner Method we should cross out row i or column j and reduce the supply or demand of the noncrossed-out row or column by the value of Xij. Then we will choose the cell with the minimum cost of
27、 shipping from the cells that do not lie in a crossed-out row or column and we will repeat the procedure. Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 26 An example for Minimum Cost Method Step 1: Select the cell with minimum cost. 2356 2135 3846 5 10 15 12846 Copyright 2003 Broo
28、ks/Cole, a division of Thomson Learning, Inc. 27 Step 2: Cross-out column 2 2356 2135 8 3846 12X46 5 2 15 Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 28 Step 3: Find the new cell with minimum shipping cost and cross-out row 2 2356 2135 28 3846 5 X 15 10X46 Copyright 2003 Brooks/
29、Cole, a division of Thomson Learning, Inc. 29 Step 4: Find the new cell with minimum shipping cost and cross-out row 1 2356 5 2135 28 3846 X X 15 5X46 Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 30 Step 5: Find the new cell with minimum shipping cost and cross-out column 1 2356
30、5 2135 28 3846 5 X X 10 XX46 Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 31 Step 6: Find the new cell with minimum shipping cost and cross-out column 3 2356 5 2135 28 3846 54 X X 6 XXX6 Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 32 Step 7: Finally assign 6
31、to last cell. The bfs is found as: X11=5, X21=2, X22=8, X31=5, X33=4 and X34=6 2356 5 2135 28 3846 546 X X X XXXX Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 33 3. Vogels Method Begin with computing for each row and column a penalty. The penalty will be equal to the difference b
32、etween the two smallest shipping costs in the row or column. Identify the row or column with the largest penalty. Find the first basic variable which has the smallest shipping cost in that row or column. Then assign the highest possible value to that variable, and cross-out the row or column as in t
33、he previous methods. Compute new penalties and use the same procedure. Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 34 An example for Vogels Method Step 1: Compute the penalties. Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 35 Step 2: Identify the largest pena
34、lty and assign the highest possible value to the variable. SupplyRow Penalty 678 5 158078 Demand Column Penalty15-6=9_78-8=70 8-6=2 78-15=63 15X5 5 15 Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 36 Step 3: Identify the largest penalty and assign the highest possible value to the
35、 variable. SupplyRow Penalty 678 55 158078 Demand Column Penalty15-6=9_ _ _ 15XX 0 15 Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 37 Step 4: Identify the largest penalty and assign the highest possible value to the variable. SupplyRow Penalty 678 055 158078 Demand Column Penalty
36、_ _ _ 15XX X 15 Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 38 Step 5: Finally the bfs is found as X11=0, X12=5, X13=5, and X21=15 SupplyRow Penalty 678 055 158078 15 Demand Column Penalty_ _ _ XXX X X Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 39 7.3 The T
37、ransportation Simplex Method In this section we will explain how the simplex algorithm is used to solve a transportation problem. Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 40 How to Pivot a Transportation Problem Based on the transportation tableau, the following steps should
38、be performed. Step 1. Determine (by a criterion to be developed shortly, for example northwest corner method) the variable that should enter the basis. Step 2. Find the loop (it can be shown that there is only one loop) involving the entering variable and some of the basic variables. Step 3. Countin
39、g the cells in the loop, label them as even cells or odd cells. Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 41 Step 4. Find the odd cells whose variable assumes the smallest value. Call this value . The variable corresponding to this odd cell will leave the basis. To perform the
40、 pivot, decrease the value of each odd cell by and increase the value of each even cell by . The variables that are not in the loop remain unchanged. The pivot is now complete. If =0, the entering variable will equal 0, and an odd variable that has a current value of 0 will leave the basis. In this
41、case a degenerate bfs existed before and will result after the pivot. If more than one odd cell in the loop equals , you may arbitrarily choose one of these odd cells to leave the basis; again a degenerate bfs will result Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 42 Illustrati
42、on of pivoting procedure on the Powerco example. We want to find the bfs that would result if X14 were entered into the basis. Nothwest Corner bfs and loop for Powerco 3535 10202050 103040 45203030 EOEOEO (1, 4)(3, 4)(3, 3)(2, 3)(2, 1)(1, 1) 0 1 2 34 5 Copyright 2003 Brooks/Cole, a division of Thoms
43、on Learning, Inc. 43 New bfs after X14 is pivoted into basis. Since there is no loop involving the cells (1,1), (1,4), (2,1), (2,2), (3,3) and (3, 4) the new solution is a bfs. 35-200+2035 10+2020 20-20 (nonbasic) 50 10+2030-2040 45203030 After the pivot the new bfs is X11=15, X14=20, X21=30, X22=20
44、, X33=30 and X34=10. Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 44 Two important points! In the pivoting procedure: Since each row has as many +20s as 20s, the new solution will satisfy each supply and demand constraint. 1.By choosing the smallest odd variable (X23) to leave th
45、e basis, we ensured that all variables will remain nonnegative. Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 45 Pricing out nonbasic variables To complete the transportation simplex, now we will discuss how to row 0 for any bfs. For a bfs in which the set of basic variables is BV
46、, the coefficient of the variable Xij (call it ij) in the tableaus row 0 is given by “pricing out”, i.e., it is the cost cij of Xij minus the sum of the shadow prices ui and vj of the only two rows containing Xij , namely, the supply constraint of i and the demand constraint of j, where the coeffici
47、ent of Xij is 1: ij = cij ui vj Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 46 Since the example is a minimization problem, the current bfs will be optimal if all the ijs are nonnegative; otherwise, we enter into the basis Xij with the most negative ij. After determining all ui
48、and all vj we can easily determine ij. But can we? We know that one equation is redundant. If for instance we decide to drop the first constraint, there will be m+n-1 elements ui and vj : u2 u3um v1 v2vn, but to keep the problem symmetric, we can assume that u1=0. Copyright 2003 Brooks/Cole, a divis
49、ion of Thomson Learning, Inc. 47 To determine all other ui and all vj we use the fact that in any tableau, each basic variable Xij must have ij=0. Thus for each of the m + n 1 variables in BV, cij ui vj =0. For the Northwest corner bfs of the Powerco problem, BV=X11, X21, X22, X23, X33, X34. Applyin
50、g the equation above we obtain: 11= 8 v1=0 Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 48 21= 9 u2 v1 =0 22= 12 u2 v2=0 23= 13 u2 v3=0 33= 16 u3 v3=0 34= 5 u3 v4 =0 The equations we used above reduce to ui+vj=cij. Thus we must solve the following system of m+n equations: Copyrig
51、ht 2003 Brooks/Cole, a division of Thomson Learning, Inc. 49 u1=0 u1+v1=8 u2+v1=9 u2+v2=12 u2+v3=13 u3+v3=16 u3+v4=5 By solving this system, we obtain: v1=8, u2=1, v2=11,v3=12, u3=4, v4=1 Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 50 For each nonbasic variable, we now compute i
52、j = cij ui vj We obtain: 12 = 6 0 11 = 5 13 = 10 0 12 = 2 14 = 9 0 1 = 8 24 = 7 1 1 = 5 31 = 14 4 8 = 2 32 = 9 4 11 = 6 Since 32 is the greatest negative ij, we would next enter X32 into the basis. Each unit that is entered into the basis will decrease Powercos cost by $6. Copyright 2003 Brooks/Cole
53、, a division of Thomson Learning, Inc. 51 We have determined that X32 should enter the basis. As shown in the table below the loop involving X32 and some of the basic variables is (3,2), (3,3), (2,3), (2,2). The odd cells in the loop are (2,2) and (3,3). Since the smallest value of these two is 10 t
54、he pivot is 10. 3535 10202050 103040 45203030 Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 52 The resulting bfs will be: X11=35, X32=10, X21=10, X22=10, X23=30 and X34=30 The uis and vjs for the new bfs were obtained by solving u1=0 u2+v2=12 u3+v4=5 u1+v1=8 u2+v3=13 u2+v1=9 u3+v2
55、=9 Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 53 In computing ij = cij ui vj for each nonbasic variable, we find that 12 = 5, 13 = 2 and 24 = 1 are the only negative ijs. Thus we next enter X12 into the basis. By applying the same steps we will finally get a solution where all
56、ijs are greater than or equal to 0, so an optimal solution has been obtained. The optimal solution for Powerco is X11=10, X13=25, X21=45, X23=5, X32=10 and X34=30. As a result of this solution the objective function value becomes: Z=6(10)+10(25)+9(45)+13(5)+9(10)+5(30)=$1020 Copyright 2003 Brooks/Co
57、le, a division of Thomson Learning, Inc. 54 7.4 Sensitivity Analysis In this section we discuss the following three aspects of sensitivity analysis for the transportation problem: 1. Changing the objective function coefficient of a nonbasic variable. 2. Changing the objective function coefficient of
58、 a basic variable. 3. Increasing a single supply by and a single demand by . Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 55 1. Changing the objective function coefficient of a nonbasic variable. Changing the objective function coefficient of a nonbasic variable Xij will leave th
59、e right hand side of the optimal tableau unchanged. Thus the current basis will still be feasible. If we are not changing cBV, from which we computed the uis and vjs , these remain unchanged. In row 0 only the coefficient of Xij will change. Thus as long as the coefficient of Xij in the optimal row
60、0 is nonnegative, the current basis remains optimal. Copyright 2003 Brooks/Cole, a division of Thomson Learning, Inc. 56 Lets try to answer the following question about Powerco as an example: For what range of values of the cost of shipping 1 million kwh of electricity from plant 1 to city 1 will th
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026-2027学年许昌市魏都区一年级上册语文期末质量检测卷含答案
- 支气管胸膜瘘护理查房
- 肝脏肿瘤护理课件
- 骨折专科护理课件
- 陶瓷、玻璃文物修复师岗前面试考核试卷含答案
- 阳极炉工成果模拟考核试卷含答案
- 草坪管护工改进考核试卷含答案
- 炭素焙烧工安全防护知识考核试卷含答案
- 司泵工岗位实操水平考核试卷含答案
- 露天采矿吊斗铲司机诚信考核试卷含答案
- 人工智能赋能课堂教学设计方案
- QC/T 783-2026摩托车用车速传感器
- 动物疫病防治员考试题库及答案
- (2026年秋)语文人教版七年级上册知识点大全
- 2026年广西高考物理真题含答案
- 临床提高临床护理文书书写规范率品管圈
- 儿童木工教育工具安全标准与课程分级体系
- 2026年高考全国1卷语文高考真题含答案
- 支气管哮喘用药指导与注意事项
- 土建管理实施方案
- 中国联合网络通信集团有限公司招聘笔试题库2026
评论
0/150
提交评论