运筹学 第3版 课件 00 运筹学上机实验指导书

利用excel求解运筹问题经济管理学院运筹学教学组主要内容一、求解准备（加载宏）二、线性规划模型三、灵敏度分析四、运输问题五、整数规划六、目标规划七、最大流问题八、最短路问题九、网络计划问题一、求解准备加载excel自带的“规划求解”

简单易学

中文界面

变量有限制下载opensolver并加载

英文界面

变量无数量限制可以使用规划求解编辑模型，使用opensolver求解1、加载excel自带的“规划求解”2003版本office依次点选：工具加载宏规划求解

确定2007以上版本office依次点选：文件→选项→加载项→（在“管理：excel加载项”处）转到→规划求解→确定WPS不需要安装错误提示及解决方法如果提示错误，说明你的电脑缺少“规划求解”这个加载项。三种方式可以加载成功（1）将office安装盘放入光驱，重新加载；（2）重新安装office并选择完全安装。（3）在其他的电脑中，找到目录C:\ProgramFiles\MicrosoftOffice\Office16\Library，把solver目录整个拷贝到自己的电脑中相应的位置。(根据装载系统的不同，上述目录会有差别）2、下载opensolver并加载下载opensovler在“/installing-opensolver/”中下载opensovler可以下载OpenSolver2.9.0_LinearWin.zip也可以下载OpenSolver2.9.3_Beta_AdvancedWin.zip安装opensolver将opensolver解压缩，放到你想放置的任意位置。加载opensolver依次点选：文件→选项→加载项→（在“管理：excel加载项”处）转到→规划求解→浏览→将opensolver文件夹放到当前打开的文件夹中→点开opensolver文件夹→选择“OpenSolver.xlam”

→确定二、线性规划模型线性规划求解名称管理Opensolver求解线性规划示例1、求解线性规划模型说明：◆所有文字均直接输入 ◆蓝色框内数值直接填入模型各类型系数◆绿色阴影单元格内均写公式◆黄色框内的单元格不需填入任何数据，决策变量的求解结果将会返回到该单元格内。（1）输入模型基本信息（2）输入模型的公式(1/2)实际使用量单元格D4的公式=B4*B9+C4*C9可使用下面函数简化

=sumproduct(B4:C4,B9:C9)单元格D5的公式=sumproduct(B5:C5,B9:C9)单元格D6的公式=sumproduct(B6:C6,B9:C9)目标函数单元格F9

=sumproduct(B7:C7,B9:C9)Sumproduct(区域1：区域2）的含义将区域1和区域2内相应位置的单元格相乘，求和。输入公式的部位，系统默认显示为0（2）输入模型的公式(1/2)通过“公式”→“显示公式”可以在表格中直接显示出公式约束条件（3）设置参数目标函数约束条件决策变量Office中，依次点选“数据→规划求解”；WPS中，依次点选“数据—模拟分析（下拉）—规划求解”①点击参数设置框中的“求解”，得到下图②点击左图中的确定，excel表格中返回求解结果

（4）求解及其结果2、名称管理（1）在Office2016中，使用“定义名称”菜单选定有需要命名的区域点选“公式”

“定义名称”系统一般默认选定区域旁边的文字为区域名称

（2）在Office2016中，直接在单元格名字处命名选中欲命名的单元格。下图中选中“单元格B9和C9”（绿圈区域）在红圈处直接输入该单元格的名字“决策变量”回车即可下图中命名紫色字分别为其下面或右面对应的单元格的名称（3）利用“名称管理器”编辑“名称”点选“公式”

“名称管理器”进入右图页面后，“新建”、“编辑”、“删除”或“筛选”名称同一个工作簿中名称不能重复2、名称管理图中红框显示文字说明因为线性规划模型的约束条件均为“≤”约束，所以可以同时选中“实际使用量”部分三个单元格让其≤“可提供量”部分的三个单元格，使输入更方便，可读性更好。2、名称管理“命名”提高了模型的可读性3、利用opensolver求解利用“规划求解”建立模型之后，直接退出，依次点击“数据→model”进入右图界面。也可以直接在该界面输入模型，基本过程同“规划求解”。保存模型后，点击“solve”求解，直接将求解结果返回excel。三、灵敏度分析（1/2）在“规划求解结果”对话框中点选“敏感性报告”，则在生成求解结果的同时，会生成该线性规划问题的灵敏度分析报告。三、灵敏度分析（2/2）△c的变化范围最优解c1c2影子价格右端常数b1b2b3－1≤△c1

－4

≤△c2≤

2－4

≤△b1≤2－8≤△b2≤16－4

≤△b3

2≤

c1

0≤

c2≤64≤b1≤108≤b2≤328≤b3

c的变化范围△b的变化范围b的变化范围最优解不变，价值系数cj的变化范围影子价格不变，右端常数bi的变化范围价值系数参数范围参数范围销地产地用户1用户2用户3用户4产量工厂A71581660工厂B51471325工厂C119151050销量60402015解：设表示工厂i运到用户j的运量产地约束：

销地约束：

非负约束：

四、运输问题—产销平衡（1/4）【例】三个工厂生产糖，产量见表最后一列，四个用户的需求量见表最后一行，产地到销地的单位运价见，绿色区域。问如何安排运输方案运费最省。目标函数约束条件约束条件左端建立产销平衡运输问题模型，同时用紫色字为相应区域命名四、运输问题—产销平衡（2/4）求解运输问题四、运输问题—产销平衡（3/4）产销不平衡运输问题求解（产量大于销量）“产>销”的问题，不需要加入假想销地，仅需保持销地约束为等式的同时，设定产地约束为“≤”约束“销>产”的问题，不需要加入假想产地，仅需保持产地约束为等式的同时，设定销地约束为“≤”约束四、运输问题—产销不平衡（4/4）五、整数规划（1/3）对于一般线性整数规划来说，只需要将有整数要求的决策变量设置为整数，或者0-1变量即可例

有一份说明书，需要译成英、日、德、俄四种文字，由甲乙丙丁四人译成不同文字所需时间不同（见右表），应如何指派所需时间最少（效率最高）？

任务人员EJGR甲215134乙1041415丙9141613丁78119解：设变量

其中，cij为上表中数据五、整数规划—指派问题（2/3）五、整数规划—指派问题（3/3）指派问题与运输问题的主要区别是约束条件的右端常数，指派问题的右端常数为1，运输问题的右端常数可以为任意数值。【例】第一步：建立模型输入基础数据输入必要的公式定义名称六、目标规划（1/4）第二步：求解P1级目标设置规划求解的参数得到规划求解结果P1级目标等于0，在求解后续目标的时候，不能影响该目标。六、目标规划（2/4）第三步：求解P2级目标令单元格D11等于0，即P1级目标=0，加入约束条件，求解P2级目标设置规划求解的参数得到规划求解结果P1级目标等于0，P2级目标等于12，在求解后续目标的时候，不能影响该目标。六、目标规划（3/4）第四步：求解P3级目标令单元格D12等于12，即P2级目标=12，加入约束条件，求解P3级目标设置规划求解的参数得到规划求解结果

六、目标规划（4/4）六、目标规划—每步结果汇总七、最大流问题（1/9）【最大流问题】在给定的网络的可行流中，寻找流量最大的流。（1）容量条件：对于每一个弧有

（2）平衡条件：

对于发点

对于收点

对于中间点(i≠s,t)，有可行流要满足容量条件和平衡条件目标函数：f*=max(v(f))容量条件和中间节点的平衡条件构成最大流问题的约束条件【例】求解下面网络从vs到v5的最大流，弧上的数字是容量cij七、最大流问题（2/9）（3）（5）（1）（1）（2）（3）（2）（5）（4）【数学模型】解：设各个弧上的流量为xij，i=s,1,2,3,4；j=1,2,3,4,51、在excel表中建立模型七、最大流问题（3/9）将网络图转换到excel表中：例如将弧（vs，v1）写成上图中绿色圈中的形式，容量写到“容量1”这一列。定义名称：紫色楷体字是相应位置数据的名称输入已知数据：蓝色框中文字和数据输入公式：黑色框中输入公式七、最大流问题（4/9）——SUMIF函数说明条件区域求和区域求和条件SUMIF（条件区域，求和条件，求和区域）SUMIF(从1,I6,流量1)表示：在B4:B14的节点中，将值等于I6单元格的节点，其对应的流量相加SUMIF(从1,I6,流量1)－SUMIF(至1,I6,流量1)表示“从v2发出的弧的流量之和”－“流入v2弧的流量之和”七、最大流问题（5/9）【约束条件】（1）中间节点流量之差等于0（2）流量≤容量（3）流量非负【目标函数】发点流量之差等于最大流2、设置参数七、最大流问题（6/9）（3,3）（5,2）（1,0）（1,0）（2,2）（3,0）（2,2）（5,3）（4,3）【答案】本例最大流问题的流量为5，最大流见下图七、最大流问题（7/9）—多源点多收点【例】某汽车零件公司需要将柏林和斯图加特的零件运往西雅图和洛杉矶，各个运输路线上的最大运量如右图所示，问如何安排运输方案，能使该公司运出的零件数最多。七、最大流问题（8/9）—多源点多收点七、最大流问题（9/9）—多源点多收点说明：方案不唯一八、最短路问题（1/4）4.7S4.63.53.23.43.63.63.43.83.33.43.54.2213456L【例】Stagecoach运输公司用卡车把橘子从S市运到L市，卡车通过每条路线以小时计算的时间都显示在图中。运输公司希望用最短的时间将橘子运到目的地。八、最短路问题（2/4）【数学模型】解：设各个弧上的决策变量为xij。xij=1，最短路经过该弧；xij=0，最短路未经过该弧i

=S,1,2,3,4；j=1,2,3,4,5模型中，cij为各弧上的距离八、最短路问题（3/4）定义名称：紫色楷体字是相应位置数据的名称；输入已知数据：蓝色框中文字和数据输入公式：黑色框中输入公式-1=八、最短路问题（4/4）答：从S市到L市的运输时间最短的路线为S→3→5→L，总时间为11.3Stagecoach运输方案九、网络计划问题（1/4）23456ABCDEFG718910HIJK