运筹学问题的Excel建模和求解.doc

第十三章 运筹学问题的Excel建模及求解学习运筹学的目的在于学会用运筹学的方法解决实践中的管理问题.注重学以致用.很多实际问题利用人工计算要经过长时间的艰苦工作才能完成甚至根本无法求解.但若使用运筹学软件则瞬间就能解决.因此在学习过程中不仅要掌握运筹学的基本理论和计算方法.还要充分利用现代化的手段和技术.微软的电子表格软件〔Microsoft Excel为展示和分析许多运筹学问题提供了一个功能强大而直观的工具.它现在已经被应用于管理实践中.本章将重点介绍如何建立和求解规划问题的电子表格模型.对于解决大量的中、小规模的实际规划问题.电子表格软件是远远优于传统的代数算法的.第一节 Excel中的规划求解工具本节中.我们将举例说明如何使用微软Excel以电子表格的形式建立线性规划模型.并利用Excel中的规划求解工具对模型求解.一、在Excel中加载规划求解工具图 13-1要使用Excel应首先安装Microsoft Office.然后从屏幕左下角的[开始]—[程序]中找到Microsoft Excel并启动.在Excel的主菜单中点击[工具]—[加载宏].选择"规划求解".如图13-1所示.点击[确定]后.在工具菜单中将增加[规划求解]选项.二、在Excel中建立线性规划模型我们以例2-1为例说明如何在电子表格中建立该问题的线性规划模型.建立电子表格模型时既可以直接利用问题中所给的数据和信息.也可以利用已建立的代数模型.本例的代数模型为：目标函数 图 13-3图 13-2图13-2显示了将该例的数据转送到电子表格中后所建立的电子表格数学模型〔本例是一个线性规划模型.其中显示数据的单元格称为数据单元格.包括生产每单位药品Ⅰ和Ⅱ所需要的4种设备的台时数〔单元格C5：D8.药品Ⅰ和Ⅱ的单位利润〔单元格C9：D9.4种设备可用的台时数〔单元格G5：G8.我们要做的决策是两种药品各生产多少；对这一决策的约束条件是生产两种药品所需的4种设备台时的限制；判断这些决策的优劣程度的指标是生产这两种药品所获得的总利润〔决策目标.如图13-3所示.将决策变量〔药品Ⅰ、Ⅱ的产量分别放入单元格C10和D10.正好在两种药品所在列的数据单元格的下面.由于不知道这些产量会是多少.故在图13-3中均设为零〔空白的单元格默认取值为零.实际上.除负值外的任何一个试验解都可以.以后在寻找产量最佳组合时这些数值会被改变.因此.含有需要做出决策的单元格称为可变单元格.两种药品所需的4种设备台时总数分别放入单元格E5至E8.正好在对应数据单元格的右边.由于所需的各种设备台时总数取决两种药品的实际产量.如：E5=C5×C10+D5×D10〔可直接将公式写入E5.也可利用SUMPRODUCT函数.E5=SUMPRODUCT〔C5：D5.C10：D10.此函数可以计算若干维数相同的数组的彼此对应元素乘积之和.因此当产量为零时所需各种设备台时的总数也为零.由于E5至E8单元格每个都给出了依赖于可变单元格〔C10和D10的输出结果.它们因此被称为输出单元格.作为输出单元格的结果.4种设备台时数的总需求量不应超过其可用台时数的限制.所以用F列中的来表示.两种药品的总利润作为决策目标进入单元格E9.正好位于用来帮助计算总利润的数据单元格的右边.类似于E列的其他输出单元格.E9=C9×C10+D9×D10或E9= SUMPRODUCT〔C9：D9.C10：D10.由于它是在对产量做出决策时目标值定为尽可能大的特殊单元格.所以被称为目标单元格.根据对上述建模过程的总结.在电子表格中建立线性规划模型的步骤可归纳如下：1．收集问题的数据.并将数据输入电子表格的数据单元格；2．确定需要做出的决策.并且指定可变单元格显示这些决策；3．确定对这些决策的限制〔约束条件.并将以数据和决策表示的被限制的结果放入输出单元格；4．选择要输入目标单元格的以数据和决策表示的决策目标.三、应用电子表格求解线性规划模型上例的求解过程可通过在Excel的工具菜单中选择"规划求解"开始."规划求解"对话框如图13-4所示.图 13-4"规划求解"开始前.可通过键入单元格地址或选中单元格的方式确定模型的每个组成部分设置在电子表格的何处〔单击暂时隐藏对话框.再从工作表中选定单元格.然后再次单击.如目标单元格地址为E9.可变单元格地址范围为C10：D10.并选中最大值〔M表示要最大化目标单元格.图 13-5约束条件的设定可通过点击对话框中的"添加"按钮.弹出图13-5所示的添加约束对话框.由于各种设备台时的总需求量均不应超过可用台时数的限制.故单元格E5到E8必须小于或等于对应的单元格G5到G8.即在添加约束对话框的左端输入范围E5：E8〔可用选中单元格的方式.中间选择<=〔点开下拉列表进行选择.右端输入范围G5：G8.如果模型中还包含其他类型的函数约束.则可点击"添加"按钮以弹出一个新的添加约束对话框.根据输出单元格与约束值之间的关系在对话框中间的下拉列表中选择适当的约束类型.以增加新的约束.但本例中已无其他约束了.所以只要点击"确定"按钮返回"规划求解"对话框.如果需要修改或删除已添加的约束.可选中该约束后点击"更改"或"删除" 按钮.到现在为止"规划求解"对话框已根据图13-3的电子表格描述了整个模型〔见图13-4.但在求解模型前还需要进行最后一个程序.点击"选项"按钮弹出图13-6所示的选项对话框.这个对话框中是一些关于如何求解问题的细节的选项.对于决策变量取值非负的线性规划模型.最主要的选项是"采用线性模型"和"假定非负"选项.〔见图13-6.关于其他选项.对小型问题来说接受图中所示的默认值通常比较合适.点击"确定"按钮返回"规划求图 13-6解"对话框.图 13-7现在可以点击"规划求解"对话框中的"求解"按钮了.它会在后台开始对问题进行求解.对于一个小型问题.几秒钟之后"规划求解"就会显示运行结果.如图13-7所示.它会显示已经找到了一个最优解.如果模型没有可行解或没有最优解.对话框会显示"规划求解找不到可行解"或"设定的单元格值不能集中".对话框还显示了产生各种报告的选项.后面将会介绍.选择"保存规划求解结果" 并点击"确定" 按钮.返回电子表格模型.图 13-8求解模型之后.如图13-8所示."规划求解"用最优解和最优值代替了可变单元格和目标单元格中的初始值.因此.最优解是生产4公斤药品Ⅰ和2公斤药品Ⅱ.最优值为1400元.与图解法的结果一致.图13-9显示的是例2-2的电子表格模型及求解过程.图 13-9这个问题的电子表格模型建立与求解过程与例2-1描述的基本相同.数据单元格〔C5：E8、〔C9：E9和〔H5：H8分别存放三种原料B1、B2、B3每斤所含四种营养成分的数量、每斤原料的单价以及食品所要求的最低营养成分的含量限制.可变单元格〔C10：E10存放三种原料配比情况〔图13-9的左上部分.输出单元格〔F5：F8给出了食品中实际的营养成分含量.目标单元格〔F9显示了该种食品的总成本〔图13-9的左下部分.图13-9的右下角显示了"规划求解"对话框的主要部分.包括为目标单元格和可变单元格设定的地址.约束条件F5H5.F6H6.F7H7和F8H8通过"添加约束"对话框显示在"规划求解" 对话框中.由于目标是最小化总成本.所以选择了"最小值〔N".图13-9的右上角显示了点击"规划求解" 对话框的"选项"按钮后所选择的选项."采用线性模型"先期定义了这个模型是线性规划模型."假定非负"选项定义了可变单元格必须是非负约束.因为食品的配比不可能出现负值.点击"规划求解" 对话框的求解按钮后.得到了图13-9中电子表格的可变单元格中显示的最优解.即该食品配比为原料B1是1.94斤.原料B3是2.36斤.成本为109.72元.与单纯形法人工求解不同.如果输出单元格、可变单元格或目标单元格结果不是整数.电子表格是以小数而非分数形式显示的.本例结果以四舍五入的方式保留了两位小数.第二节 线性规划的应用问题一、合理用料问题这是第二章第五节的第一个问题.由于原料胶管的长度为15分米.而输液管、止血带和听诊器胶管分别长5.7、4.2和3.1分米.所以每根原料胶管最多可截三种材料依次为2根、3根和4根.即总的截法不超过3×4×5=60〔种.又由于每种截法的料头不能超过2分米.所以可先通过电子表格进行试算以选择其中可行的几种截法.再利用线性规划的方法找出用料根数最少的方案.如图13-10的左上部分所示.单元格C4至E4显示三种胶管的长度；C5至E5输入不同的方法截出每种胶管的根数；F4为对应C5至E5的不同截法所剩料头的长度. F5通过判断剩余料头的长度是否在0到2之间显示出该种解法是否可行.单元格F4和F5的公式见图13-10的左下部分.图 13-10不断变换C5至E5的可能取值并选择其中可行的截法〔共6种.在电子表格中建立该问题的线性规划模型.数据单元格为C9：H11、C12：H12和K9：K12.分别显示每种截法截一根原料胶管时得到三种不同材料的数量、每种截法截取一次所用胶管的数量和三种材料的需要量；可变单元格C13：H13显示采用每种截法所截的胶管原料数；输出单元格I9：I12列出了某一截取方案实际获得的三种材料数量.每种材料的数量等于各种截法截得该材料数与对应截法所截原料数的乘积之和.如输液管的数量I9=SUMPRODUCT；目标单元格I12为总用料数.应等于各种截法所截原料数之和,即I12=SUM.图13-10的右半部分显示了"规划求解"对话框及"选项"对话框的内容.该问题的目标是所用的胶管原料的总根数最少.因此设置目标单元格为I12等于最小值.由于实际获得的材料数量必须满足需求量的要求.考虑到最优方案〔各种截法的某一组合不一定能使截出的三种材料数量恰好等于需要的数量.而某种材料超过需求量是允许的.故在添加约束时可设置实际截得的数量大于等于需求量.即I9：I12>=K9：K12〔本题中.该约束取">="和"="的结果是相同的；又由于截出的各种材料数量均为整数.因此约束中应包括决策变量取整数的限制.即C13:H13=整数.图13-10的左上部分显示了该问题的最优方案为：分别用第二种、第四种和第五种截法截取原料40、60和10根.共用原料110根.与第二章中用大法求解的结果一致.二、放射科的业务安排图 13-11图13-11显示了第二章问题二的电子表格模型及求解过程.该问题的数据包括：进行三种检查的单位时间〔C5：E5.三种检查设备每月的可用时间〔C9：E9.三项业务每月最多提供量〔H6以及每项业务的单位利润〔C10：E10.可变单元格为C6至E6.给出三项业务每月的实际发生数量.输出单元格为C7至E7和F6.分别表示根据各项业务的实际发生数量产生的设备使用时间及实际的总业务量.目标单元格F10显示由每项业务的单位利润及每月实际发生数量计算的总利润.图13-11的左下部分给出了输出单元格及目标单元格的公式.图13-11右下部分的"规划求解"对话框显示了求解时应注意的问题：求目标单元格的最大值〔利润最大；约束为设备的实际使用时间小于等于设备的可用时间及实际总业务量小于等于总业务提供量的限制.打开"选项"对话框.仍选择"采用线性模型"和"假定非负".回到"规划求解"并按"求解"按钮.得到问题的最优方案为：每月X线及CT检查的业务量分别为1320人次和480人次.磁共振业务量为0.即不必购买该设备；按最优方案安排业务每月可获利55200元.在电子表格上建立线性规划或其它问题模型的方式是非常灵活的.不必拘泥于一种固定的模式.本书仅提供了一种建立模型的思路.读者可根据不同问题的特点以及个人的习惯或喜好建立不同风格的电子表格模。