《运筹学》课程教学资源（实验讲义）实验五 网络最优化问题

实验五网络最优化问题一)实验目的：熟悉运用Exce1软件求解各种网络最优化问题，掌握其求解方法。(二)内容和要求：用Excel软件求解最小费用流问题、最大流问题、最短路问题、中国邮路问题等，题目自选。(三)操作步骤：(1)建立电子表格模型：(2)使用Excel规划求求解功能求解网络最优化问题(3)结果分析；(4)在Excel或Word文档中书写实验报告，包括数学模型、电子表格模型和结果分析等。案例6人员配备模型研究某计量所现有15个投资项目需要配备人员，但职工必须具备相应项目的检定证书才能从事相应项目的检定工作，而且，他们的检定工作效率也各不相同，这就产生了人员配备模型。根据某专业技术委员会评定、打分，具有相应项目的鉴定证书的职工（21人）从事相应项目（15个）的检定工作的工作效率如表C-22所示。职工从事项目检定工作的工作效率121表C-221314115109XA5120.70.80.20.90.220.20.930.50.250.70.960.90.90.50.880.50.8070.990.5100.9110.9120.5130.80.414150.9160.40.50.50.90.7170.20.80.90.7180.90.5190.8090.8200.60.70.70.6210.70.807(a)根据法律法规，每个项目至少应该有两名具有相应项目的检定证书的职工进行检定，同时，该计量所又规定，每个职工最多从事两个项目的检定工作。这样，就可以建立一个0-1整数规划的人员配备模型。请写出相应的0-1整数规划人员配备模型，并用Excel求解结果，看每位职工都检定哪些项目、每个项目都又哪些

实验五 网络最优化问题 （一） 实验目的：熟悉运用 Excel 软件求解各种网络最优化问题，掌握其求 解方法。 （二） 内容和要求：用 Excel 软件求解最小费用流问题、最大流问题、最短 路问题、中国邮路问题等，题目自选。 （三） 操作步骤： （1） 建立电子表格模型； （2） 使用 Excel 规划求求解功能求解网络最优化问题； （3） 结果分析； （4） 在 Excel 或 Word 文档中书写实验报告，包括数学模型、电子表格模型 和结果分析等。 案例 6 人员配备模型研究 某计量所现有 15 个投资项目需要配备人员，但职工必须具备相应项目的检 定证书才能从事相应项目的检定工作，而且，他们的检定工作效率也各不相同， 这就产生了人员配备模型。根据某专业技术委员会评定、打分，具有相应项目的 鉴定证书的职工（21 人）从事相应项目（15 个）的检定工作的工作效率如表 C-22 所示。 （a） 根据法律法规，每个项目至少应该有两名具有相应项目的检定证 书的职工进行检定，同时，该计量所又规定，每个职工最多从事 两个项目的检定工作。这样，就可以建立一个 0-1 整数规划的人 员配备模型。请写出相应的 0-1 整数规划人员配备模型，并用 Excel 求解结果，看每位职工都检定哪些项目、每个项目都又哪些

职工来检定？（提示：如果采用指派问题方法求解，会提示“可变单位格过多”，所以可采用网络最优化问题方法求解。）(b)由于只要持有检定证书的职工，就能参与某些项目的检定工作，造成工作的情性，竞争性不强。为了提高工作效率，可以通过提高职工间的竞争性来达到目的。这样，每个项目只充许两个检定人员检定。请问，哪些职工由于在其持有检定证书的项目上工作效率较低，没有竞争力，而无项目参与，只能下岗。解对于第（a）问：(1)决策变量这是一个指派问题（稀疏指派问题），假设x，表示职工i是否从事项目j的检定工作（1一是，0一否），需要说明的是：只是表C-22中有工作效率的才有相应的决策变量。(2)目标函数Maxz=Ecejahj所有项目检定工作的总工作效率最高，即：其中C.,为表C-22中职工i从事项目j检定工作工作的工作效率。(3)约束条件①每个项目至少应该有两名具有相应项目的检定证书的职工进行检定：

职工来检定？ （提示：如果采用指派问题方法求解，会提示“可变单位格过多”， 所以可采用网络最优化问题方法求解。） （b） 由于只要持有检定证书的职工，就能参与某些项目的检定工作， 造成工作的惰性，竞争性不强。为了提高工作效率，可以通过提 高职工间的竞争性来达到目的。这样，每个项目只允许两个检定 人员检定。请问，哪些职工由于在其持有检定证书的项目上工作 效率较低，没有竞争力，而无项目参与，只能下岗。 解 对于第（a）问： （1） 决策变量 这是一个指派问题（稀疏指派问题），假设 i j x 表示职工 i 是否从事项目 j 的 检定工作（1—是，0—否），需要说明的是：只是表 C-22 中有工作效率的才 有相应的决策变量。 （2） 目标函数 所有项目检定工作的总工作效率最高，即： 其中 Ci j 为表 C-22 中职工 i 从事项目 j 检定工作工作的工作效率。 （3） 约束条件 ① 每个项目至少应该有两名具有相应项目的检定证书的职工进行检定：

1-1+22-1+33-1+24-1+25-1≥21-2十12-2十42≥2X2-3+X3-3≥2X6-4+9-4+16-4≥27-+2g-5+16-5≥2-68-9-6+10-616-6≥218-7+29-1≥211-8+±13-8+214-8+217-8≥2Z15-9十116-9+217-9+19-9+20-9≥2X12-10+Z14-10≥218-11+120-11+121-11≥217-12+20-12+21-12≥218-13+20-13+21-13≥216-14+19-11≥217-15+19-15≥2②每个职工最多从事两个项目的检定工作：1-1+1-222-2-2+2-23-1+3-324-1+4-22X5-1<2C6-4≤2-5+-28-6+8-29-4+x9-5+±9-6X9-2X10-62X11-8<2

② 每个职工最多从事两个项目的检定工作：

412-10<2313-8<2Z14-8+114-10≤2Z15-9≤216-416-516-6+16-916-142317-8+17-9+17-12+17-152T18-+18-13≤2T19-9+19-14+119-15≤220-920-11+20-12+20-13≤2221-11+221-12+21-13≤2③0—1变量：x=0,1建立电子表格模型并求解，Exce1的求解结果如表C-23和C-24所示。也就是说，每个职工都参与1至2个项目的检定工作。而每个项目有2至4名职工进行检定，这样15个项目就用了35人次的职工。此时所有项目检定工作的总工作效率最高，为23.9。表C-23每个职工参与的项目（a)职工1参与项目1、2职工2参与项目2、3职工3参与项目1、3职工4参与项目1、2职工5参与项目1职工6参与项目4职工7参与项目5、6职工8参与项目6、7职工9参与项目5、7职工10参与项目6职工11参与项目8职工12参与项目10职工13参与项目8职工14参与项目8、10职工15参与项目9职工16参与项目4、14职工17参与项目9、15职工18参与项目11、13职工19参与项目14、15职工20参与项目11、12职工21参与项目12、13每个项目参与的职工数表C-24项目2参与的职工数3人项目1参与的职工数4人项目4参与的职工数2人项目3参与的职工数2人项目6参与的职工数3人项目5参与的职工数2人项目8参与的职工数3人项目7参与的职工数2人项目10参与的职工数2人项目9参与的职工数2人项目12参与的职工数2人项目11参与的职工数2人项目14参与的职工数2人项目13参与的职工数2人项目15参与的职工数2人

③ 0—1 变量： i j x =0,1 建立电子表格模型并求解，Excel 的求解结果如表 C-23 和 C-24 所示。也就 是说，每个职工都参与 1 至 2 个项目的检定工作。而每个项目有 2 至 4 名职 工进行检定，这样 15 个项目就用了 35 人次的职工。此时所有项目检定工作 的总工作效率最高，为 23.9

对于（b）问，只需在第（a）问的基础上，将约束条件中的“每个项目至少应该有两名具有相应项目的检定证书的职工进行检定，≥2”改为“每个项目只允许两名检定人员检定，=2”即可。Exce1的求解结果如图C-25所以。此时所有项目检定工作的总工作最高，为22。也就是说，有三位职工（职工4、10、13）由于在其持有检定证书的项目上工作效率较低，没有竞争力，而无项目参与，只能下岗。上岗的办法是提高所在项目的工作效率，或取得其他项目的检定证书并有较高的工作效率。表C-25每个职工参与的项目（b)职工1参与项目1、2职工2参与项目2、3职工3参与项目3职工4无参与项目职工6参与项目4职工5参与项目1职工8参与项目6、7职工7参与项目5、6职工10无参与项目职工9参与项目5、7职工12参与项目10职工11参与项目8职工14参与项目8、10职工13无参与项目职工16参与项目4、14职工15参与项目9职工18参与项目11、13职工17参与项目9、15职工20参与项目11、12职工19参与项目14、15职工21参与项目12、13

对于（b）问，只需在第（a）问的基础上，将约束条件中的“每个项目至少 应该有两名具有相应项目的检定证书的职工进行检定，≥2”改为“每个项 目只允许两名检定人员检定，=2”即可。 Excel 的求解结果如图 C-25 所以。此时所有项目检定工作的总工作最高， 为 22。也就是说，有三位职工（职工 4、10、13）由于在其持有检定证书的 项目上工作效率较低，没有竞争力，而无项目参与，只能下岗。上岗的办法 是提高所在项目的工作效率，或取得其他项目的检定证书并有较高的工作效 率