1、Page:Page:Page:1 1 1QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学Page:Page:Page:2 2 2QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学经典运输问题经典运输问题销销售售商商供供应应商商Boston Chicago St. Louis Lexington生生产产能能力力(吨吨)Cleveland32765,000Bedford75236,000York25452,500需需求求量量(吨吨) 6,0004,0002,0001,500每吨
2、运输成本(/吨)Page:Page:Page:3 3 3QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学网络表示网络表示供应商供应商1Cleveland2Bedford3York2Chicago1Boston3St. Louis4Lexington销售商销售商5,0002,5006,0006,0001,5002,0004,000327627534255Page:Page:Page:4 4 4QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学线性规划模型线性规划模型MinZ=
3、3x11+2x12+7x13+6x14+7x21+5x22+2x23+3x24+2x31+5x32+4x33+5x34S. t.x11+x12+x13+x145000 x21+x22+x23+x246000 x31+x32+x33+x342500 x11+x21+x31= 6000 x11+x21+x31= 4000 x11+x21+x31= 2000 x11+x21+x31= 1500 xij 0 ,Page:Page:Page:5 5 5QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学运输问题线性规划的一般形式运输问题线性规划的
4、一般形式m1in1jijijc=zMin xm,1,2,=i sxn1jiijn ,1,2,=j dxm1ijijn,1,=jm;,1,2,=i 0,xijst. 供应供应：需求需求：Page:Page:Page:6 6 6QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学供求平衡问题的特征供求平衡问题的特征 d sn1jjm1ii 基变量的个数基变量的个数=m+n-1Page:Page:Page:7 7 7QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学初始基本可行解的构
5、造初始基本可行解的构造Page:Page:Page:8 8 8QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学西北角方法西北角方法供应量供应量327675232545需求量需求量BostonChicagoSt. Louis LexingtonCleveland5,000Bedford6,000York2,5006,0004,0002,0001,5005000100001000050004000010001000010001000015001500Page:Page:Page:9 9 9QSCQSCQSC华东理工大学华东理工大学华东理
6、工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学最小元素法最小元素法供应量供应量327675232545需求量需求量BostonChicagoSt. Louis LexingtonCleveland5,000Bedford6,000York2,5006,0004,0002,0001,5004000010002500200015003500002500250040000025001000Page:Page:Page:101010QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学运输问题的特殊解法运输问题的特殊解法闭回路方法
7、闭回路方法 检验数：非基变量增加一个单位引起的成本变化量检验数：非基变量增加一个单位引起的成本变化量Page:Page:Page:111111QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学闭回路方法闭回路方法-例例 供应量供应量327675232545需求量需求量BostonChicagoSt. Louis LexingtonCleveland5,000Bedford6,000York2,5006,0004,0002,0001,500Page:Page:Page:121212QSCQSCQSC华东理工大学华东理工大学华东理工大学
8、工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学初始基本可行解：初始基本可行解：供应量供应量10004000752325002000150025452500需求量需求量6,0004,0002,0001,500York6,000Bedford2,50065,00027Cleveland3BostonChicagoSt. Louis Lexington基本可行解基本可行解Page:Page:Page:131313QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学检验数的计算：检验数的计算： 供应量供应量10004000+175-12
9、325002000150025452500需求量需求量BostonChicagoSt. Louis LexingtonCleveland-132+1765,000York6,000Bedford2,5006,0004,0002,0001,5009闭回路闭回路检验数检验数Page:Page:Page:141414QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学初始基本可行解与检验数：初始基本可行解与检验数： 供应量供应量10004000752325002000150025452500需求量需求量BostonChicagoSt. Lou
10、is LexingtonCleveland32765,000York6,000Bedford2,5006,0004,0002,0001,50074-1977基本可行解基本可行解检验数检验数Page:Page:Page:151515QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学10004000-7+52325002000150025452500BostonChicagoSt. Louis LexingtonCleveland+3-627YorkBedford-135001500752325002000150025452500Bost
11、onChicagoSt. Louis LexingtonCleveland3627YorkBedford=2500基本可行解的调整：基本可行解的调整： Page:Page:Page:161616QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学检验数的重新计算：检验数的重新计算： 35001500752325002000150025452500YorkBedford627Cleveland3BostonChicagoSt. Louis Lexington866416检验数均大于检验数均大于0，得最优解：，得最优解：Page:Page:
12、Page:171717QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学运输问题的特殊解法运输问题的特殊解法位势方法位势方法 检验数：目标函数的系数减去对偶变量之和检验数：目标函数的系数减去对偶变量之和Page:Page:Page:181818QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学m1in1jijijc=zMin xm,1,2,=i sxn1jiijn ,1,2,=j dxm1ijijn,1,=jm;,1,2,=i 0,xijst. 供应供应：需求需求：对偶变量对
13、偶变量 ui对偶变量对偶变量 vjPage:Page:Page:191919QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学m1in1jjjiivdus=Max wn,1,2,j m;,1,2,=i cv uijjin,1,=j m;,1,2,=i v,uji无约束st. 对偶变量对偶变量 xijPage:Page:Page:202020QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学原问题检验数：原问题检验数： ij=cij-(ui+vj)i=1,2,m; j=1,2,
14、n特别对于特别对于m+n-1个基变量，有个基变量，有 ij=cij-(ui+vj)=0Page:Page:Page:212121QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学位势法位势法-例例供应量供应量327675232545需求量需求量BostonChicagoSt. Louis LexingtonCleveland5,000Bedford6,000York2,5006,0004,0002,0001,500Page:Page:Page:222222QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院
15、工商经济学院运筹学运筹学运筹学初始基本可行解：初始基本可行解：供应量供应量10004000752325002000150025452500需求量需求量BostonChicagoSt. Louis LexingtonCleveland32765,000York6,000Bedford2,5006,0004,0002,00015,000基本可行解基本可行解Page:Page:Page:232323QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学位势计算：位势计算：10004000752325002000150025452500u1u2u
16、3v1v2v3v4YorkBedford627Cleveland3BostonChicagoSt. Louis Lexington3vu2vu2vu7vu2vu3vu4232131221111v2;v1;u4;u2;v3;v0;u4332211Page:Page:Page:242424QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学10004000752325002000150025452500Lexingtonv2=2v3=-2v4=-1BostonChicagoSt. Louis3276Bedfordu1=0u2=4u3=-1v
17、1=3YorkCleveland-197477检验数的计算：检验数的计算： Page:Page:Page:252525QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学退化问题的处理退化问题的处理 保证基变量的个数为保证基变量的个数为m+n-1Page:Page:Page:262626QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学供应量供应量327675232545需求量需求量5,0004,0002,0002,500York2,500Bedford6,000Clevela
18、nd5,000BostonChicagoSt. Louis Lexington500000Page:Page:Page:272727QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学非平衡问题的处理非平衡问题的处理 -转换为平衡问题转换为平衡问题Page:Page:Page:282828QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学销销售售商商 供供应应商商 A B C D 生生产产能能力力 (吨吨) 甲甲 3 2 7 6 5,000 乙乙 7 5 2 3 6,000 丙
19、丙 2 5 4 5 4,500 需需求求量量(吨吨) 6,000 4,000 2,000 1,500 销售商销售商 供应商供应商 A B C D E 生产能力生产能力 (吨吨) 甲甲 3 2 7 6 0 5,000 乙乙 7 5 2 3 0 6,000 丙丙 2 5 4 5 0 4,500 需求量需求量(吨吨) 6,000 4,000 2,000 1,500 2000 供过于求的处理供过于求的处理Page:Page:Page:292929QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学销销售售商商 供供应应商商 A B C D 生生
20、产产能能力力 (吨吨) 甲甲 3 2 7 6 5,000 乙乙 7 5 2 3 6,000 丙丙 2 5 4 5 2,500 需需求求量量(吨吨) 6,000 4,000 2,000 3,500 销销售售商商 供供应应商商 A B C D 生生产产能能力力 (吨吨) 甲甲 3 2 7 6 5,000 乙乙 7 5 2 3 6,000 丙丙 2 5 4 5 2,500 丁丁 0 0 0 0 2000 需需求求量量(吨吨) 6,000 4,000 2,000 1,500 供不应求的处理供不应求的处理Page:Page:Page:303030QSCQSCQSC华东理工大学华东理工大学华东理工大学 工
21、商经济学院工商经济学院工商经济学院运筹学运筹学运筹学运输问题的推广运输问题的推广转运问题转运问题Page:Page:Page:313131QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学转运问题转运问题-例例生产厂1Denver2Atlanta6Miami5Detroit7Dallas8NewOrleans零售店6004002003003501503236431162543KansasCity4Louisville64批发部Page:Page:Page:323232QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院
22、工商经济学院工商经济学院运筹学运筹学运筹学MinZ=2x13+3x14+3x23+x24+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48+4x28+x78S. t.x13+x14600 x23+x24+x28400-x13-x23+x35+x36+x37+x38=0-x14-x24+x45+x46+x47+x48=0 x35+x45=200 x36+x46=150 x37+x47-x78=350 x38+x48+x28+x78=300 xij 0for all i, j供应供应转运转运需求需求线性规划模型线性规划模型Page:Page:Page:333333QS
23、CQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学转运问题分析与建模要点转运问题分析与建模要点 纯供应节点纯供应节点有供应量有供应量S Si i，无需求量，无转运功能，无需求量，无转运功能生产厂生产厂1Denver60032供应量供应量Out) (Arcs,ijiSxPage:Page:Page:343434QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学纯需求节点纯需求节点无供应量，有需求量无供应量，有需求量d dj j，无转运功能，无转运功能5Detroit零售店零售店20
24、0需求量需求量24In) (Arcs,jjidxPage:Page:Page:353535QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学供应节点供应节点有供应量，无需求量，具有转运功能有供应量，无需求量，具有转运功能生产厂生产厂1Denver60032供应量供应量4Out) (ArcsIn) (Arcs,ijijiSxxPage:Page:Page:363636QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学需求节点需求节点无供应量，有需求量无供应量，有需求量d dj
25、j，具有转运功能，具有转运功能7Dallas350163销售商销售商需求量需求量Out) (ArcsIn) (Arcs,jjijidxxPage:Page:Page:373737QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学纯转运节点纯转运节点无供应量，无需求量，仅具有转运功能无供应量，无需求量，仅具有转运功能236323KansasCity6批发部批发部Out) (ArcsIn) (Arcs,0jijixxPage:Page:Page:383838QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工
26、商经济学院运筹学运筹学运筹学一般转运节点一般转运节点有供应量有供应量S Si i，有需求量，有需求量d di i，又具有转运功，又具有转运功能能2633KansasCity56002001需求量需求量供应量供应量Out) (ArcsIn) (Arcs,iijijidSxxPage:Page:Page:393939QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学转运问题的应用转运问题的应用生产与库存计划生产与库存计划 季季 度度 生生 产产 能能 力力 需需 求求 量量 单单 位位 生生产产 成成 本本 单单 位位 库库存存 费费 用用 1 600 400 2 0.25 2 300 500 5 0.25 3 500 400 3 0.25 4 400 400 3 0.25 Page:Page:Page:404040QSCQSCQSC华东理工大学华东理工大学华东理工大学 工商经济学院工商经济学院工商经济学院运筹学运筹学运筹学生产第一季度第二季度600300235第四季度第三季度500400需求第一季度第二季度400500第四季度第三季度40040030.250.250.25生产能力生产需求量
