《运筹学》课程教学资源（实验讲义）实验四 运输问题和指派问题

实验四运输问题和指派问题（一）实验目的：熟悉运用Exce1软件求解运输问题和指派问题，掌握其求解方法。（二）内容和要求：求解教材第4章习题的第1、2、6、7、11、15题（或其他例题、习题、案例等）（三）操作步骤：（1）建立电子表格模型；（2）使用Excel规划求解功能求解运输问题和指派问题；（3）结果分析；（4）在Excel或Word文档中书写实验报告，包括线性规划模型、电子表格模型和结果分析等。案例4某市的菜篮子工程某市是一个人口不到15万人的小城市，根据该市的蔬菜种植情况，分别在A、B和C设三个收购点，再由收购点分送到全市的8个菜市场。按常年情况，A、B、C三个收购点每天收购量分别为200、170和160（单位：100kg），各菜市场的每天需求量及发生供应短缺时带来的损失见表C--14.从收购点至各菜市场的距离见表C--15，设从收购点至各菜市场蔬菜调用费用为1元/（100kg100m)

实验四 运输问题和指派问题 （一）实验目的：熟悉运用 Excel 软件求解运输问题和指派问题，掌握其求解 方法。 （二）内容和要求：求解教材第 4 章习题的第 1、2、6、7、11、15 题（或其 他例题、习题、案例等） （三）操作步骤： （1）建立电子表格模型； （2）使用 Excel 规划求解功能求解运输问题和指派问题； （3）结果分析； （4）在 Excel 或 Word 文档中书写实验报告，包括线性规划模型、电子表格模 型和结果分析等。 案例 4 某市的菜篮子工程 某市是一个人口不到 15 万人的小城市，根据该市的蔬菜种植情况，分别在 A、B 和 C 设三个收购点，再由收购点分送到全市的 8 个菜市场。按常年情况， A、B、C 三个收购点每天收购量分别为 200、170 和 160（单位：100kg），各菜 市场的每天需求量及发生供应短缺时带来的损失见表 C-14.从收购点至各菜 市场的距离见表 C-15，设从收购点至各菜市场蔬菜调用费用为 1 元/(100kg• 100m)

表C-14各菜市场每天需求量及短缺损失菜市场每天需求量（100kg）短缺损失（元/100kg）75102608380547010510010655879058808表C-15收购点至各菜市场的距离距离菜市场（单位：100m）2134678收A488192211616购B14771617121623点C20195101114615（a）为该市设计一个从各收购点至菜市场的定点供应方案，使用于蔬菜调用的费用及预期的短缺损失为最小；（b）若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案；（c）为满足城市居民的蔬菜供应，该市的领导规划增加蔬菜种植面积，试问增产的蔬菜每天应分别向A、B、C三个收购点各供应多少最为经济合理。解（a）设xu为收购点i向菜市场j调运的蔬菜量（1000kg）（i=A,B,C:j=1,2，,8)，yi为菜市场j供应短缺量（100kg）（j=l,2，，8）。目标函数为：Minz=，其中c为调用费用，S,为短缺损失。约束条件：（由于三个收购点每天收购总量为200+170+160=530，小于菜市场每

（a）为该市设计一个从各收购点至菜市场的定点供应方案，使用于蔬菜调用 的费用及预期的短缺损失为最小； （b）若规定各菜市场短缺量一律不超过需求量的 20%，重新设计定点供应方 案； （c）为满足城市居民的蔬菜供应，该市的领导规划增加蔬菜种植面积，试问 增产的蔬菜每天应分别向 A、B、C 三个收购点各供应多少最为经济合理。 解 （a）设 xij为收购点 i 向菜市场 j 调运的蔬菜量（1000kg）(i=A,B,C;j=1,2,.,8)， yi为菜市场 j 供应短缺量（100kg）(j=1,2,.,8)。 目标函数为：Min z= ,其中 cij 为调用费用，sj 为短缺 损失。 约束条件：（由于三个收购点每天收购总量为 200+170+160=530，小于菜市场每

天需求总量75+60+80+70+100+55+90+80=610，为销大于产的运输问题）。①三个收购点每天收购量：②8个菜市场每天需求量：7560T80705十十1000559080③8个菜市场每天短缺量：=75-（=60（十）-80-）70（）100-（十十，=55（十）=90-（A十X十C），Y8=80-（18十1十10）④非负：Xij，yi≥0(i=A,B,C;j-l,2,",8)建立电子表格模型，求解结果如表C--16所示。表C-16索例4的结果（a)供应方案菜市场123450070收购点A750055收购点B0608030001030收购点C00009040短缺04000040调运总费用3890短缺总损失720总费用4610（b）在（a）的基础上，增加约束“各菜市场短缺量一律不超过需求量的20%”即可。yl≤75×20%，y2≤60×20%，y≤80×20%，y4≤70×20%Ys≤100×20%，y≤55×20%，y≤90×20%，y：≤80×20%求解结果如表C--17所示

天需求总量 75+60+80+70+100+55+90+80=610，为销大于产的运输问题）。 ①三个收购点每天收购量： ②8 个菜市场每天需求量： ③8 个菜市场每天短缺量： ④非负：xij，yi≥0 (i=A,B,C;j=1,2,.,8) 建立电子表格模型，求解结果如表 C-16 所示。 （b）在（a）的基础上，增加约束“各菜市场短缺量一律不超过需求量的 20%” 即可。 y1≤75×20%， y2≤60×20%， y3≤80×20%， y4≤70×20% Y5≤100×20%，y6≤55×20% ，y7≤90×20% ，y8≤80×20% 求解结果如表 C-17 所示

表C-17案例4的结果（b）供应方案菜市场1235618收购点A750106005500收购点B06054560O00收购点C00002407264短缺1600141601816调运总费用4208短缺总损失598总费用4806（c）比（b），（a）简单，只需设xu为收购点i向菜市场j调运的蔬菜数量（100kg）(i=A,B,C;j=1,2，,8)，增产的蔬菜每天应分别向A、B、C三个采购点个供应ya，yb,ye(100kg)。由于是要满足8个菜市场每天的需求量，所以数学模型为：CMin2=2g8H8门口IN=200+YA.2=170+2Xcy=160+yc-lXA十十=75十+=60S.++=80++=70工十十2=100，6十十=551A7十1C=90TA8十十TC=80.y≥0=ABC=12..8)建立电子表格模型，求解结果如表C--18所示

（c）比（b），（a）简单，只需设 xij为收购点 i 向菜市场 j 调运的蔬菜数量（100kg） (i=A,B,C;j=1,2,.,8),增产的蔬菜每天应分别向 A、B、C 三个采购点个供应 ya， yb，yc（100kg）。 由于是要满足 8 个菜市场每天的需求量，所以数学模型为： 建立电子表格模型，求解结果如表 C-18 所示

表C-18案例4的结果(c)供应方案菜市场123576增产4875收购点A0403055000006070收购点B40000000709080收购点C0000804.770调运总费用也就是说，增产蔬菜（80）每天都向C这个收购点供应量最经济合理。案例5人员指派方案研究某设计院是国家甲级工程勘察设计单位，经常要对较大型设计项目的“设计人员指派问题”进行分析研究，作为设计项目管理现代化的开端。现在要进行一个较大型矿井设计项目，牵涉到采矿、电气、机制、设备、土建、总运技经，共7个专业，每个专业有需要若干设计人员分别担任设计和检审工作，各专业现有人员中可抽调人员数和需要人员数见表C--19。由于专业技术的限制，各专业之间专业设计人员不能流动。表C-19各专业可用人数和需要人员数专业采矿电气机制设备土建总运技经10可用人数514736需设计人数322542需检审人数2

也就是说，增产蔬菜（80）每天都向 C 这个收购点供应量最经济合理。 案例 5 人员指派方案研究 某设计院是国家甲级工程勘察设计单位，经常要对较大型设计项目的“设计人员 指派问题”进行分析研究，作为设计项目管理现代化的开端。现在要进行一个较 大型矿井设计项目，牵涉到采矿、电气、机制、设备、土建、总运技经，共 7 个专业，每个专业有需要若干设计人员分别担任设计和检审工作，各专业现有人 员中可抽调人员数和需要人员数见表 C-19。由于专业技术的限制，各专业之间 专业设计人员不能流动

由于每个设计人员的素质不同，因而他们从事设计或检审工作的效率和质量也各不相同。为了简化问题，由该院专业技术委员会对每个设计人员从事设计和检审的工作效率和质量进行综合评估，以百分制来衡量。个设计人员从事设计或检审工作的综合素质评分见表C--20。表C-20设计人员质量效率综合索质评分表人员T2345采矿专业（5人）设计89.5472.378.565.982.3检审70.2590.0282.3586.878.78电气专业（7人）设计77.2193.568.7585.6473.5682.7880.1688.15检审72.3182.5687.8578.2669.7673.15机制专业（4人）设计873478.3374.9881.23检审77.1567.2284.8771.54设备专业7人设计87.4279.6883.152375.6734检审76.4584.8785.7478.91826472.65人土建专业92.7489.8690.5668.7676.84设计72.7679.7587.7488.2578.3281.9382.65检审80.05H总运84.2678.3设计83.15检审88.1685.2780.81技经专业（5人设计82.1680.9872.8176.5679.35检审70.6981.678.2168.9877.57注：表中空表表示无此人。该问题的目标是根据各设计人员从事设计和检审工作的综合素质评分，选取各专业合适的人员进行设计工作或检审工作，以使参加项目的人员的综合素质总分最高，从而从人员选配方面保证整个设计项目达到效率和质量综合效果最好。提示：每个专业都是一个人员指派问题，因而可以分成7个指派问题。对某专业的每个设计人员分别就设计工作、检审工作引用两个0---1变量。解（1）对于采矿专业，可抽调人员有5人，需要设计人员3人，需要检审人员1人，因此是一个“人多事少的指派问题”。采矿专业的每个设计人员分别就设计工作、检审工作引用两个0--1变量：Xi-I1、Xi-2分别表示采矿人员i是否从事设计工作、检审工作（1---是，0---否）（i=1,2,3，4,5）则指派问题数学模型为

由于每个设计人员的素质不同，因而他们从事设计或检审工作的效率和质量也 各不相同。为了简化问题，由该院专业技术委员会对每个设计人员从事设计和检 审的工作效率和质量进行综合评估，以百分制来衡量。个设计人员从事设计或检 审工作的综合素质评分见表 C-20。 注：表中空表表示无此人。 该问题的目标是根据各设计人员从事设计和检审工作的综合素质评分，选取 各专业合适的人员进行设计工作或检审工作，以使参加项目的人员的综合素质总 分最高，从而从人员选配方面保证整个设计项目达到效率和质量综合效果最好。 提示：每个专业都是一个人员指派问题，因而可以分成 7 个指派问题。对某 专业的每个设计人员分别就设计工作、检审工作引用两个 0-1 变量。 解 （1）对于采矿专业，可抽调人员有 5 人，需要设计人员 3 人，需要检审人 员 1 人，因此是一个“人多事少的指派问题”。采矿专业的每个设计人员分别就 设计工作、检审工作引用两个 0-1 变量：xi-1、xi-2分别表示采矿人员 i 是否从 事设计工作、检审工作（1-是，0-否）（i=1,2,3,4,5）则指派问题数学模型 为

Max2=(89.541-1+72.312-1+78.523-1+65.9-+82.3zs-1)+（70.251-2+90.0212-2+82.35元3-2+86.82-2+78.785-2)21-1+2-1+23-1十34-1十35-1-311-2+12-2十1-2十-2十25-2-111-1+11-212-1+2-2≤1s. t.13-1+13-2≤11-1+1-2<115-+5-211-1,3-2=0,1i=1,2,3,4,5)（2）对于其余专业，求解过程与采矿专业类似，结果如表C--21所示。表C-21某设计项目各专业人员工作安排表人员1235610采矿专业平均：85.09综合素质评分合计量大值：340.36设计89.5478.582.3检审90.02电气专业综合素质评分合计最大值：267.29平均：89.10设计93.585.64检审88.15机制专业综合素质评分合计最大值：253.44平均：84.48设计87.3481.23检审84.87设备专业综合素质评分合计最大值：515.04平均：85.84设计83.1587.4290.7585.34检审85.7482.64土建专业综合素质评分合计最大值：616.42平均：88.06设计92.7489.8690.5685.5383.35检审82.6591.73续前表人员12314510总运专业综合素质评分合计最大值：250.72平均：83.57设计84.2678.3检审88.16技经专业综合素质评分合计最大值：320.06平均：80.02设计79.3582.1680.98检审77.57表C--21中空白表示无此人或者不安排该工作，有数字格子表示此人安排该工作，其数字就是此人从事该工作的综合素质评分。全体30名参加项目的人员综合素质总分为2563.33分，平均为85.44分

（2）对于其余专业，求解过程与采矿专业类似，结果如表 C-21 所示。 表 C-21 中空白表示无此人或者不安排该工作，有数字格子表示此人安排 该工作，其数字就是此人从事该工作的综合素质评分。全体 30 名参加项目的 人员综合素质总分为 2563.33 分，平均为 85.44 分