《关于运输问题与指派问题的建模及其求解》由会员分享，可在线阅读，更多相关《关于运输问题与指派问题的建模及其求解（7页珍藏版）》请在金锄头文库上搜索。
1、运筹学试卷 2011 级营升本 2 班 第 2 组关于运输问题与指派问题的建模及其求解考生名单：石琦、程培培、曾凯、桑佳丽、王菁、 薛苗苗、郝园、付长宇、孙丽媛、杜晓宇问题：某公司决定使用三个有生产余力的工厂进行四种新产品的生产。下面表中给出了每种产品在不同工厂中的单位成本，以及各工厂每天生产的每种产品的数量，每种产品每天的需求量。每家工厂都可以制造这些产品，除了工厂 2不能生产产品 3 以外。现在需要决定的是在哪个工厂生产哪种产品，可使总成本最小。产品生产的有关数据单位成本（元）产品 1 产品 2 产品 3 产品 4生产能力工厂 1 41 27 28 24 78工厂 2 40 29 23 7
2、0工厂 3 38 30 27 22 40需求量 25 35 30 40（1）如果允许产品的生产分解，请建模并求解。（2）如果不允许产品的生产分解，请建模并求解。分析：（1）如果允许产品的生产分解，可以将生产产品问题看作运输问题来求解。三个工厂 1、2、3 的总产量为 78+70+40=188；四种产品 1、2、3、4 的总需求量为：25+35+30+40=115.由于总产量大于总需求量，所以该问题是一个供大于求的运输问题。 决策变量运筹学试卷 2011 级营升本 2 班 第 2 组设 为工厂 生产产品 的数量（ 1,2,3; 1,2,3,4） 。 = = 目标函数本问题的目标函数是使得总成本最
3、小。即Min 41 +27 +28 +24 +z= 1112131440 +29 +23 +2122 2438 +30 +27 +2231323334 约束条件根据上表可以写出此问题的约束条件各厂产量（生产能力）限制工厂 1： + + + 7811121314工厂 2： + + + 7021222324工厂 3： + + + 4031323334各种产品需求量的约束产品 1： + + 25112131=产品 2： + + 35122232=产品 3： + + 30132333=产品 4： + + 40142434=由于工厂 2 不能生产产品 3，所以 023=非负： 0；（ 1,2,3; 1,
4、2,3,4） 。 = =所以该供大于求的运输问题的线性规划模型如下：Min =41 +27 +28 +24 + 40 +z 11121314 2129 +23 +38 +30 +27 +2222 2431323334s.t.11+12+13+1478 21+22+23+2470 31+32+33+3440 11+21+31=25 12+22+32=35 13+23+33=30 14+24+34=40 23=0 0；（ =1,2,3; =1,2,3,4）运筹学试卷 2011 级营升本 2 班 第 2 组（2）如果不允许产品的生产分解，可以将该问题视为指派工厂生产产品问题，工厂可以看作指派问题中的
5、人，产品则可以看作需要完成的工作（任务） 。由于有四种产品和三个工厂，所以就有两个工厂各只能生产一种新产品，第三个工厂生产两种新产品。只有工厂 1 和工厂 2 有生产两种产品的能力。这里涉及如何把运输问题转换为指派问题，关键所在是数据转换。 单位指派成本：原来的单位成本转换成整批成本（=单位成本需求量） ，即单位指派成本为每个工厂生产每种产品的成本。 供应量和需求量的转换问题：三个工厂生产四种产品，但一种产品只能在一个工厂生产，根据生产能力，工厂 3 只能生产一种产品（供应量为 1） ，而工厂 1 和工厂 2 可以生产两种产品（供应量为 2） ，而产品的需求量为1。还有“总供应（2+2+1=5
6、）总需求（1+1+1+1=4） ”，为人多事少的指派问题。 决策变量设 为指派工厂 生产产品 的数量（ =1,2,3; =1,2,3,4） 。 目标函数本问题的目标函数是使得总成本最小。即Min 4125 +2735 +2830 +2440z= 11 12 13 14+4025 +2935 + 234021 22 24+3825 +3035 +2730 +224031 32 33 34 约束条件由上面分析表明工厂 1 和工厂 2 最多只能生产两种产品，工厂 3 只能生产一种产品。即工厂 1： 211+12+13+14工厂 2： 221+22+23+24工厂 3： 131+32+33+34=由于
7、一种产品只能由一个工厂生产，所以产品 1： + + 1（ 、 中只有一个发生为 1，其余为 0）112131= 1121、 31运筹学试卷 2011 级营升本 2 班 第 2 组产品 2： + + 1（ 、 、 ）122232= 122232中只有一个发生为 1，其余为 0产品 3： + + 1（ 、 、 ）132333= 132333中只有一个发生为 1，其余为 0产品 4： + + 1（ 、 、 ）142434= 142434中只有一个发生为 1，其余为 0由于工厂 2 不能生产产品 3，所以 023=非负： 0；（ 1,2,3; 1,2,3,4） 。 = =所以该指派问题的线性规划模型如
8、下：Min 4125 +2735 +2830 +2440z= 11 12 13 14+4025 +2935 + 234021 22 24+3825 +3035 +2730 +224031 32 33 34s.t.11+12+13+142 21+22+23+242 31+32+33+34=1 11+21+31=1 12+22+32=1 13+23+33=1 14+24+34=1 23=0 0；（ =1,2,3; =1,2,3,4）求解：目标单元格I运筹学试卷 2011 级营升本 2 班 第 2 组13 总成本14 =SUMPRODUCT(C4:F6,C9:F11)数据单元格G8 实际产量9 =S
9、UM(C9:F9)10 =SUM(C10:F10)11 =SUM(C11:F11)B C D E F12 实际销量 =SUM(C9:C11) =SUM(D9:D11) =SUM(E9:E11) =SUM(F9:F11)运筹学试卷 2011 级营升本 2 班 第 2 组目标单元格I20 总成本21 =SUMPRODUCT(C11:F13,C16:F18)数据单元格10 日成品 产品 1 产品 2 产品 3 产品 411 工厂 1 =C4*$C$8 =D4*$D$8 =E4*$E$8 =F4*$F$812 工厂 2 =C5*$C$8 =D5*$D$8 - =F5*$F$813 工厂 3 =C6*$C$8 =D6*$D$8 =E6*$E$8 =F6*$F$8运筹学试卷 2011 级营升本 2 班 第 2 组G15 实际指派16 =SUM(C16:F16)17 =SUM(C17:F17)18 =SUM(C18:F18)B C D E F19 实际分配 =SUM(C16:C18) =SUM(D16:D18) =SUM(E16:E18) =SUM(F16:F18)
