运筹学03-excel求解.pdf

《运筹学03-excel求解.pdf》由会员分享，可在线阅读，更多相关《运筹学03-excel求解.pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第第 2 2 章章 线性规划的计算机求解及应用举例线性规划的计算机求解及应用举例1线性规划线性规划模型在电子表格电子表格中的布局线性规划模型在电子表格中布局的好坏关系到问题可读性和求解方便性的高低。 本节以第一章中的例 1（资源分配问题）为例来说明一下如何在电子表格中描述线性规划模型，让我们回顾一下第一章中例1 的数学模型：MaxZ 4x13x2x1 62x 82.（）2x 3x 1821x1,x2 0一般来说， 在与问题相关的表格的基础上稍加调整就可以在电子表格中形成一个十分清晰的模型描述。我们以表1-1 为基础在 Excel 电子表格中将上述问题描述如图2-1。图图 2-12-1 资源分配

2、问题的模型在资源分配问题的模型在 ExcelExcel 电子表格的布局及公式电子表格的布局及公式2 用 Excel 规划求解工具求解线性规划模型Excel 中有一个工具叫规划求解，可以方便地求解线性规划模型。“规划求解”加载宏是Excel 的一个可选加载模块， 在安装 Excel 时，只有在选择 “定制安装” 或完全安装时才可以选择装入这个模块。如果你现在的Excel 窗口菜单栏的“工具”菜单中没“规划求解”选项，可以通过“工具” 菜单的 “加载宏” 选项打开 “加载宏”对话框来添加“规划求解” （见图 2-2） 。在应用规划求解工具以前，要首先确认在Excel 电子表格中包括决策变量、目标函

3、数、约束函数三种信息的单元格或单元格区域。图 2-1中的电子表格中就已经有了这部分内容： 决策变图图 2-22-2 加载宏对话框加载宏对话框量在 C9 和 D9 单元格中；目标函数的系数在第8 行；约束函数在第5、6 和 7 行。因为我们不知道决策变量的值是多少，所以就在决策变量所在的单元格中填上初始值 “0” ，当然也可以什么都不填，系统会默认它为 0，在求解以后 Excel 会自动将它们替换成决策变量的最优解。下面我们接着上节的内容用Excel 规划求解将第一章例 1 的资源分配问题解一遍。首先将要求解模型的所有相关信息和公式像图 2-1 那样填入电子表格中后，再选取工具 | 规划求解命令

4、后，弹出图 2-3 所示的“规划求解参数”对话框。图图 2-32-3 规划求解参数对话框规划求解参数对话框“规划求解参数” 对话框的作用就是让计算机知道模型的每个组成部分放在电子表格的什么地方，我们可以通过键入单元格 （或单元格区域）的地址或用鼠标在电子表格相应的单元格（或单元格区域）点击或拖动的办法将有关信息加入到对话框相应的位置。 下面我们分别对其中的选项略作解释：1. 1.设置目标单元格设置目标单元格。 在此文本框中应指定目标函数所在单元格的引用位置， 此目标单元格， 经求解后获得某一特定数值、 最大值或最小值。 由此可见， 这个单元格必须包含公式。本例中由于目标函数在 E8 单元格，所

5、以输入“E8” 。输入后 Excel 会自动将其变为图 2-3 所示的美元符号来固定这个地址。2. 2.等于等于。在此指定是否需要对目标单元格求取最大值、 最小值或某一指定数值。 如果需要让目标函数为某一指定数值，则要在右侧编辑框中键入。本例是求目标函数最大化，所以选最大值。3. 3.可变单元格可变单元格。可变单元格指定决策变量所在的各单元格、 不含公式，可以有多个区域或单元格，求解时其中的数值不断调整，直到满足约束条件，并且“设置目标单元格”编辑框中指定的单元格达到目标值。 可变单元格必须直接或间接与目标单元格相联系。 本例的决策变量在 C9 和 D9 两个单元格中，所以在此键入“C9:D9

6、”单元格引用区域。4. 4.推测推测。单击此按钮，自动定位“设置目标单元格” 编辑框中公式引用的所有非公式单元格，并在“可变单元格”编辑框中输入其引用。5. 5.约束约束。在此列出了当前的所有约束条件。 到此为止，我们还未添加模型的任何约束条件，所以图 2-3 中没有显示。6. 6.添加添加。显示“添加约束”对话框（见图2-4） 。在添加约束对话框中有三个选项，其中单元格引用位置指定需要约束其中数据的单元格或单元格区域， 一般在此处添加约束函数不等式左侧的函数表达式的单元格或单元格区域。本例输入“E5:E7” 。约束值。在此指定对“单元格引用位置”编辑框中输入的内容的限制条件。即，对于单元格引

7、用及其约束条件， 选定相应的需要添加或修改的关系运算符 （=、 Int、 或 Bin） ，然后在右侧的编辑框中输入数字、 单元格或区域引用及公式等约束条件。 本例输入 “G5:G7” 。添加。单击此按钮可以在不返回 “规划求解参数”对话框的情况下继续添加其它约束条件。由于我们已经把所有的约束都一次添加上了，所以只需按“确定”键，回到“规划求解参数对话框（见图 2-5） ，我们发现“约束”一栏中已经显示了我们刚刚添加的约束。图图 2-42-4 添加约束对话框添加约束对话框图图 2-62-6 改变约束对话框改变约束对话框图图 2-52-5 添加了约束后的规划求解参数对话框添加了约束后的规划求解参数

8、对话框7. 7.更改更改。单击后显示“改变约束”对话框（见图2-6） 。从本质上说， “改变约束”对话框与“添加约束”对话框没有区别，它们的各个选项都是一样的。8. 8.删除删除。删除选定的约束条件。图图 2-72-7“规划求解选项”对话框“规划求解选项”对话框9. 9.选项选项。显示“规划求解选项”对话框（见图 2-7） 。在其中装入或保存规划求解模型， 并对求解运算的高级属性进行设定。 本例中的模型是线性的， 而且所有变量都是非负的，所以在选中“采用线性模型”和“假定非负”两个复选框，本对话框的其它选项采用默认值对于求解大多数线性规划问题就足够了，本例也不例外。设置完选项后，单击“确定”按

9、钮返回到图 2-5 的“规划求解参数”对话框。10.10. 关闭关闭。关闭对话框， 不进行规划求解。 但保留通过 “选项” 、 “添加” 、 “更改” 或“删除”按钮所做的修改。11.11. 全部重设全部重设。清除规划求解中的当前设置，将所有的设置恢复为初始值。12.12. 求解求解。对定义好的问题进行求解。单击“求解”键后，经过几秒钟的计算（小型问题） ，弹出“规划求解结果”对话框（图2-8） 。图图 2-82-8 “规划求解结果”对话框“规划求解结果”对话框本例中，像图2-8 告诉我们“规划求解”找到一个最优解，可以满足所有的约束及目标的最大化要求，选中“保存规划求解结果”单选框 ，然后单

10、击确定键，可以得到求解的结果（见图 2-9） 。图图 2-92-9 资源分配问题的资源分配问题的 ExcelExcel 求解结果求解结果我们看到图 2-10 中的 C6 和 D6 单元格中的“0”已经被图 2-9 中相应的单元格内的最优解“6”和“2”替代，根据这个最优解，E8 单元格中的最优值“30”也计算了出来。这些信息告诉我们，工厂应该安排生产甲产品6 件，乙产品 2 件，能够在有限的资源限制下获得最大的利润 30（百元） 。3 线性规划问题的建模与应用举例第一章和本章的前面部分围绕三个例子讲解了线性规划问题的图解法和计算机求解方法，为使读者进一步了解线性规划问题的建模与求解，我们举例如

11、下：例例 1. 1. 农场灌溉问题农场灌溉问题某公司有四个农场，每个农场的耕地作物需要用水灌溉， 因灌溉条件限制， 农场的最大水资源供应量有一定限制，各农场的总耕地面积与最大水资源供应量如表2-1 所示。该地区适合种植的农作物有棉花、 玉米和高粱， 三种农作物每种作物每单位种植面积的净收入和耗水量以及每种作物最大允许种植面积如表2-2 所示。由于水资源短，公司统一调配水资源，为了保持公正， 规定每个农场受灌溉面积占农场总耕地面积的比例相同， 公司管理层面临的决策问题还是如何确定各农场种植各种作物的面积， 使得在满足以上各种限制的条件下， 公司总收入最大。表表 2-12-1农场1234表表 2-

12、22-2耕地面积（亩）4000600050004500最大水资源供应量（吨）6000900055005000作物棉花玉米高粱单位种植面积收入 （元） 单位面积耗水量（吨） 最大允许种植面积（亩）80026000600550045015000解： 我们首先建立此问题的线性规划模型。 由于此问题是决定四个农场中每个农场种植三种农作物的面积，我们引入决策变量xij（i = 1，2，3，4；j = 1，2，3）表示第 i 个农场种植第 j 种作物的面积，目标是使总收入Z = 800( x11+ x21 + x31 + x41) + 600(x12+ x22 + x32 + x42 ) + 450(x1

13、3+ x23 + x33 + x43)最大化，且满足下列约束条件：1. 农场的耕地面积约束x11+ x12+ x134000(农场 1)x21 + x22 + x236000(农场 2)x31 + x32 + x335000(农场 3)x41+ x42 + x434500(农场 4)2. 农场最大供水量约束2x11+ x136000(农场 1)2x21 + x239000(农场 2)2x31 + x335500(农场 3)2x41+ x435000(农场 4)3.农作物的种植面积约束x11+ x21 + x31 + x416000（农作物 1，棉花）x12+ x22 + x32 + x4255

14、00（农作物 2，玉米）x13+ x23 + x33 + x435000（农作物 3，高粱）即各农作物种植面积不超过最大允许种植面积。4. 种植作物面积占总耕地面积比例约束x11 x12 x13x21 x22 x2340006000 x21 x22 x23x31 x32 x3360005000 x31 x32 x33x41 x42 x4350004500即各农场种植作物面积（灌溉面积）占总耕地面积的比例相同。5. 决策变量的非负约束xij 0， i = 1，2，3，4；j = 1，2，3。现在我们用 Excel 电子表格求解以上问题，具体过程如下：将表 2-1 和表 2-2 的数据录入到 Ex

15、cel 电子表格中（见图2-12） ，在 D5：F8 单元格区域放置决策变量，目标单元格是G13。应用“规划求解”后，我们得到一个最优解，由图中阴影部分的数据可知，农场1 种植棉花亩、玉米亩，不种高粱；农场2 种植棉花亩、高粱亩，不种玉米；农场 3 种植玉米亩、高粱亩，不种棉花；农场4 种植棉花亩、玉米亩、高粱亩。可获总收入 1035 万元。图图 2-122-12 农场灌溉问题的农场灌溉问题的 ExcelExcel 规划求解规划求解例例 2. 2. 证券投资问题证券投资问题一证券投资者将 1000 万元资金用于证券投资，已知各种证券（A、B、C、D、E、F）的评级、到期年限、每年税后收益如表2

16、-3 所示。表表 2-32-3证券名称ABCDEF证券类型地方债券基金国债国债地方债券基金评级221145到期年限9125434每年税后收益（%）管理层对该投资者提出下列要求：1.国债投资额不能少于 300 万元；2.投资证券的平均评级不超过；3.投资证券的平均到期年限不超过5 年。问：每种证券投资多少可以使得税后收益最大解：引入决策变量xA、xB、xC、xD、xE、xF分别表示证券 A、B、C、D、E、F 的投资金额（单位：万元） ，相应的目标函数（税后收益）为：Z = 9 + 12 + 5 + 4 + 3 + 4约束条件为：1.资金总额约束：xA + xB + xC + xD + xE +

17、 xF 10002.国债投资额约束：xC + xD 3003.证券平均评级约束：2xA2xB xC xD4xE5xF1.5xA xB xC xD xE xF这是一个非线性约束，很容易转化为以下线性约束：+ 04.证券平均到期年限约束：9xA12xB5xC4xD3xE4xF 5xA xB xC xD xE xF它等价于线性约束：4xA + 7xB xD 2xE xF 05.非负约束：xA0，xB0， xC0， xD0， xE0， xF0用 Excel 电子表格求解以上问题过程如下：将表 2-3 中的数据录入电子表格中 （见图 2-13） ， 在 D5： D10 单元格区域放置决策变量，目标单元格

18、是 G11。应用“规划求解”后，我们得到一个最优解，由图中阴影部分的数据可知，xA= 200、xB= 0、xC = 0、xD = 725、xE = 0、xF = 75，也就是说该投资者只选择A、D 和 F证券进行投资，投资额分别是200、725 和 75 万元，可获得最大的税后收益万元。因为有两个非线性约束变为线性约束， 使得在电子表格中相关的数据不够直观， 请仔细体会电子表格中公式和约束的意义，想想它们与上文总结的各约束之间的关系。图图 2-132-13 证券投资问题的证券投资问题的 ExcelExcel 规划求解规划求解例例 3. 3. 话务员排班问题话务员排班问题某寻呼公司雇用了多名话务

19、员工作， 他们每天工作 3 节，每节 3 小时，每节开始时间为午夜、凌晨 3 点钟、凌晨 6 点钟，上午 9 点、中午 12 点、下午 3 点、6 点、9 点，为方便话务员上下班，管理层安排每位话务员每天边连续工作3 节，根据调查，对于不同的时间，由于业务量不同，需要的话务员的人数也不相同，公司付的薪水也不相同，有关数据见表24 。表表 2-42-4工作时间03 点最低需求8人数 （人）26薪水 （元）36 点63069 点1528912 点20221215 点1518 点1821 点210 点2520232018221024问：如何安排话务员才能保证服务人数，又使总成本最低解： 这个问题实际

20、上是一个成本效益平衡问题。 管理层在向客户提供满意服务水平的同时要控制成本，因此必须寻找成本与效益的平衡。 由于每节工作时间为 3 小时，一天被分为8 班，每人连续工作3 节，各班时间安排如下（见表2-5） ：表表 2-52-5时段0-33-66-99-1212-1515-1818-2121-0成本184280370班次456262666772880最低需求人数86152025231810为了建立数学模型， 对应于一般成本效益平衡问题， 我们首先必须明确包含的活动数目，活动一个单位是对应于分派一个话务员到该班次收， 效益的水平对应于时段。 收益水平就是该时段里上下班的话务员数目， 各活动的单位

21、效益贡献就是在该时间内增加的在岗位话务员数目。我们给出下列成本效益平衡问题参数表（见表2-6） ：表表 2-62-6时段0-33-66-99-1212-1515-1818-2121-0成本111100000842011100008030011100070班次4500011100620000111062600000111667100000117281100000180最低需求人数86152025231810决策变量xi表示分派到第i班的话务员人数（i= 1，2，3，4，5，6，7，8） ，约束条件为：0-3 时间段：x1 x7 x88（最低可接受水平）3-6 时间段：x1 x2 x8 66-9

22、时间段：x1 x2 x3159-12 时间段：x2 x3 x4 2012-15 时间段：x3 x4 x5 2515-18 时间段：x4 x5 x6 2318-21 时间段：x5 x6 x71821-0 时间段：x6 x7 x8 10非负约束：xi 0i= 1，2，3，4，5，6，7，8目标函数为最小化成本：Z 84x180 x270 x362x462x566x672x780 x8根据以上模型，建立相应的 Excel 电子表格线性规划模型，并用“规划求解”得到一个最优解（见图 2-14） ，第一班安排 4 人上班，第二班安排2 人上班，第三、四、五、六、七班分别安排 9、9、8、6、4 人，第八

23、班不安排人，在满足各时段的最低人数需求的同时花费最少的薪金支出（2864 元） 。图图 2-142-14 话务员排班问题的话务员排班问题的 ExcelExcel 规划求解规划求解例例 4. 4.多阶段生产安排问题多阶段生产安排问题南方机电制造公司为全国各地生产一种大型机电设备， 按照公司的订单合同， 不久要交付使用一定数量的机电设备， 所以有必要制定为期6 个月的设备生产计划。 根据合同，公司必须在未来 6 个月中每个月底交付一定数量的机电设备， 由于原料价格、生产条件、保修和维修工作等安排不同，每月的生产能力和生产成本也不同， 当然，可以在成本较低的月份多生产一些设备，但在供给客户之前必须存

24、放， 需要付一定的存贮费用。 管理层需要制定出一个逐月生产计划， 使生产和存贮的总成本达到最小。 管理科学小组通过调查收集到每单位生产成本、每月单位存贮费、每月需求量、最大生产能力等数据（见表2-7） 。表表 2-72-7月份（i）123456月底需求量di（台）101620142523最大生产能力单位生产成本单位存贮成本ci（千元）hi（千元）li（台）203026283030最大存贮量fi（台）101261080解：管理层需要作出的决策是每个月生产多少台设备，因此我们引入决策变量xi表示第i个月生产机电设备的台数（i= 1，2，3，4，5，6） 。为了建立此问题的一般数学模型，我们用di表

25、示第i月的需求量； 用li表示第i月的最大生产能力； 用ci表示第i月的单位生产成本；用hi表示第i月的单位存贮成本；用fi表示第i月的最大存贮量。由最大生产能力限制，我们容易得到约束：xilii= 1，2，3，4，5，6用Ii表示第i月底的库存量（i= 1，2，3，4，5，6） ，由最大存贮量约束，我们有：Iifii= 1，2，3，4，5，6各个月份之间生产量、需求量和存贮量之间的关系可由下图（图2-15）表示：x1x2x3x4x5x6II1I2I3I4I5I60123456d1d2d3d4d5d6图 2-15 各个月份之间生产量、需求量和存贮量之间的关系容易得到下列约束：Ii1 xidi

26、Iii= 1，2，3，4，5，6I0 0（公司开始无存货）即第i个月初的库存量Ii1（上月底的库存量）+ 第i月的生产量 第i月的需求量等于第i月的存贮量。另外有非负约束：xi 0，Ii 0i= 1，2，3，4，5，6目标为总成本Z c x hIiii1i166ii最小化为此，我们建立了 Excel 电子表格线性规划模型（见图 2-16） ，注意电子表格中的约束与线性规划模型中约束及目标函数之间对应的关系。另外，由于Ii不是变量， “规划求解选项” 对话框中的 “假定非负” 选项并不能使它们为非负， 所以一定要在添加约束时将 “Ii 0”添加进去。也可以在表中再加一列，令其等于Ii，并将其设为变量（ “规划求解”时把这一区域设为可变单元格） ，就不需要在“添加约束”对话框去中添加了。从计算结果来看，公司按照1-6 月份分别生产 10、28、8、14、30、18 台设备的计划生产（G5：G10 单元格区域）将会使总成本最低，为千元（G11 单元格） 。图图 216216 多阶段生产安排问题的多阶段生产安排问题的 ExcelExcel 规划求解规划求解