运筹学03-excel求解

1、第2章 线性规划的计算机求解及应用举例1线性规划模型在电子表格中的布局线性规划模型在电子表格中布局的好坏关系到问题可读性和求解方便性的高低。本节以第一章中的例1（资源分配问题）为例来说明一下如何在电子表格中描述线性规划模型，让我们回顾一下第一章中例1的数学模型： Max s.t. （2.1）一般来说，在与问题相关的表格的基础上稍加调整就可以在电子表格中形成一个十分清晰的模型描述。我们以表1-1为基础在Excel电子表格中将上述问题描述如图2-1。图2-1 资源分配问题的模型在Excel电子表格的布局及公式图2-2 加载宏对话框2用Excel规划求解工具求解线性规划模型Excel中有一个工具叫规

2、划求解，可以方便地求解线性规划模型。“规划求解”加载宏是Excel的一个可选加载模块，在安装Excel时，只有在选择“定制安装”或完全安装时才可以选择装入这个模块。如果你现在的Excel窗口菜单栏的“工具”菜单中没“规划求解”选项，可以通过“工具”菜单的“加载宏”选项打开“加载宏”对话框来添加“规划求解”（见图2-2）。在应用规划求解工具以前，要首先确认在Excel电子表格中包括决策变量、目标函数、约束函数三种信息的单元格或单元格区域。图2-1中的电子表格中就已经有了这部分内容：决策变量在C9和D9单元格中；目标函数的系数在第8行；约束函数在第5、6和7行。因为我们不知道决策变量的值是多少，所

3、以就在决策变量所在的单元格中填上初始值“0”，当然也可以什么都不填，系统会默认它为0，在求解以后Excel会自动将它们替换成决策变量的最优解。下面我们接着上节的内容用Excel规划求解将第一章例1的资源分配问题解一遍。首先将要求解模型的所有相关信息和公式像图2-1那样填入电子表格中后，再选取工具 | 规划求解命令后，弹出图2-3所示的“规划求解参数”对话框。图2-3 规划求解参数对话框“规划求解参数”对话框的作用就是让计算机知道模型的每个组成部分放在电子表格的什么地方，我们可以通过键入单元格（或单元格区域）的地址或用鼠标在电子表格相应的单元格（或单元格区域）点击或拖动的办法将有关信息加入到对话

4、框相应的位置。下面我们分别对其中的选项略作解释：1. 设置目标单元格。在此文本框中应指定目标函数所在单元格的引用位置，此目标单元格，经求解后获得某一特定数值、最大值或最小值。由此可见，这个单元格必须包含公式。本例中由于目标函数在E8单元格，所以输入“E8”。输入后Excel会自动将其变为图2-3所示的美元符号来固定这个地址。2. 等于。在此指定是否需要对目标单元格求取最大值、最小值或某一指定数值。如果需要让目标函数为某一指定数值，则要在右侧编辑框中键入。本例是求目标函数最大化，所以选最大值。3. 可变单元格。可变单元格指定决策变量所在的各单元格、不含公式，可以有多个区域或单元格，求解时其中的数

5、值不断调整，直到满足约束条件，并且“设置目标单元格”编辑框中指定的单元格达到目标值。可变单元格必须直接或间接与目标单元格相联系。本例的决策变量在C9和D9两个单元格中，所以在此键入“C9:D9”单元格引用区域。4. 推测。单击此按钮，自动定位“设置目标单元格”编辑框中公式引用的所有非公式单元格，并在“可变单元格”编辑框中输入其引用。5. 约束。在此列出了当前的所有约束条件。到此为止，我们还未添加模型的任何约束条件，所以图2-3中没有显示。6. 添加。显示“添加约束”对话框（见图2-4）。在添加约束对话框中有三个选项，其中 单元格引用位置指定需要约束其中数据的单元格或单元格区域，一般在此处添加约

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

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

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

9、6单元格中的“0”已经被图2-9中相应的单元格内的最优解“6”和“2”替代，根据这个最优解，E8单元格中的最优值“30”也计算了出来。这些信息告诉我们，工厂应该安排生产甲产品6件，乙产品2件，能够在有限的资源限制下获得最大的利润30（百元）。 3线性规划问题的建模与应用举例第一章和本章的前面部分围绕三个例子讲解了线性规划问题的图解法和计算机求解方法，为使读者进一步了解线性规划问题的建模与求解，我们举例如下：例1. 农场灌溉问题某公司有四个农场，每个农场的耕地作物需要用水灌溉，因灌溉条件限制，农场的最大水资源供应量有一定限制，各农场的总耕地面积与最大水资源供应量如表2-1所示。该地区适合种植的农

10、作物有棉花、玉米和高粱，三种农作物每种作物每单位种植面积的净收入和耗水量以及每种作物最大允许种植面积如表2-2所示。由于水资源短，公司统一调配水资源，为了保持公正，规定每个农场受灌溉面积占农场总耕地面积的比例相同，公司管理层面临的决策问题还是如何确定各农场种植各种作物的面积，使得在满足以上各种限制的条件下，公司总收入最大。表2-1 农场耕地面积（亩）最大水资源供应量（吨）123440006000500045006000900055005000表2-2 作物单位种植面积收入（元）单位面积耗水量（吨）最大允许种植面积（亩）棉花玉米高粱80060045021.51600055005000解：我们首先

11、建立此问题的线性规划模型。由于此问题是决定四个农场中每个农场种植三种农作物的面积，我们引入决策变量xij（i = 1，2，3，4；j = 1，2，3）表示第i个农场种植第j种作物的面积，目标是使总收入Z = 800( x11 + x21 + x31 + x41) + 600(x12 + x22 + x32 + x42 ) + 450(x13 + x23 + x33 + x43)最大化，且满足下列约束条件：1. 农场的耕地面积约束x11 + x12 + x13 4000 (农场1)x21 + x22 + x23 6000 (农场2)x31 + x32 + x33 5000 (农场3)x41 +

12、x42 + x43 4500 (农场4)2. 农场最大供水量约束2x11 + 1.5x12 + x13 6000 (农场1)2x21 + 1.5x22 + x23 9000 (农场2)2x31 + 1.5x32 + x33 5500 (农场3)2x41 + 1.5x42 + x43 5000 (农场4)3.农作物的种植面积约束x11 + x21 + x31 + x41 6000 （农作物1，棉花） x12 + x22 + x32 + x42 5500 （农作物2，玉米）x13 + x23 + x33 + x43 5000 （农作物3，高粱）即各农作物种植面积不超过最大允许种植面积。 4. 种植

13、作物面积占总耕地面积比例约束即各农场种植作物面积（灌溉面积）占总耕地面积的比例相同。5. 决策变量的非负约束xij 0， i = 1，2，3，4；j = 1，2，3。现在我们用Excel电子表格求解以上问题，具体过程如下：将表2-1和表2-2的数据录入到Excel 电子表格中（见图2-12），在D5：F8单元格区域放置决策变量，目标单元格是G13。应用“规划求解”后，我们得到一个最优解，由图中阴影部分的数据可知，农场1种植棉花1346.15亩、玉米2038.46亩，不种高粱；农场2种植棉花3923.08亩、高粱1153.85亩，不种玉米；农场3种植玉米2538.46亩、高粱1692.31亩，不

14、种棉花；农场4种植棉花730.769亩、玉米923.077亩、高粱2153.85亩。可获总收入1035万元。图2-12 农场灌溉问题的Excel规划求解例2. 证券投资问题一证券投资者将1000万元资金用于证券投资，已知各种证券（A、B、C、D、E、F）的评级、到期年限、每年税后收益如表2-3所示。表2-3 证券名称证券类型评级到期年限每年税后收益（%）ABCDEF地方债券基金国债国债地方债券基金22114591254344.34.43.23.03.24.5管理层对该投资者提出下列要求：1. 国债投资额不能少于300万元；2. 投资证券的平均评级不超过1.5；3. 投资证券的平均到期年限不超过

15、5年。问：每种证券投资多少可以使得税后收益最大？解：引入决策变量xA、xB、xC、xD、xE、xF分别表示证券A、B、C、D、E、F的投资金额（单位：万元），相应的目标函数（税后收益）为：Z = 90.043xA + 120.044xB + 50.032xC + 40.03xD + 30.032xE + 40.045xF约束条件为：1. 资金总额约束： xA + xB + xC + xD + xE + xF 10002. 国债投资额约束： xC + xD 3003. 证券平均评级约束： 这是一个非线性约束，很容易转化为以下线性约束： 0.5xA + 0.5xB 0.5xC 0.5xD + 2.

16、5xE + 3.5xF 04. 证券平均到期年限约束： 它等价于线性约束： 4xA + 7xB xD 2xE xF 05. 非负约束： xA 0， xB 0， xC 0， xD 0， xE 0， xF 0用Excel电子表格求解以上问题过程如下：将表2-3中的数据录入电子表格中（见图2-13），在D5：D10单元格区域放置决策变量，目标单元格是G11。应用“规划求解”后，我们得到一个最优解，由图中阴影部分的数据可知，xA = 200、xB = 0、xC = 0、xD = 725、xE = 0、xF = 75，也就是说该投资者只选择A、D和F证券进行投资，投资额分别是200、725和75万元，可

17、获得最大的税后收益177.9万元。因为有两个非线性约束变为线性约束，使得在电子表格中相关的数据不够直观，请仔细体会电子表格中公式和约束的意义，想想它们与上文总结的各约束之间的关系。图2-13证券投资问题的Excel规划求解例3. 话务员排班问题某寻呼公司雇用了多名话务员工作，他们每天工作3节，每节3小时，每节开始时间为午夜、凌晨3点钟、凌晨6点钟，上午9点、中午12点、下午3点、6点、9点，为方便话务员上下班，管理层安排每位话务员每天边连续工作3节，根据调查，对于不同的时间，由于业务量不同，需要的话务员的人数也不相同，公司付的薪水也不相同，有关数据见表2-4。表2-4 工作时间0-3点3-6点

18、6-9点9-12点12-15点15-18点18-21点21-0点最低需求人数（人）86152025231810薪水（元）2630282220202224问：如何安排话务员才能保证服务人数，又使总成本最低？解：这个问题实际上是一个成本效益平衡问题。管理层在向客户提供满意服务水平的同时要控制成本，因此必须寻找成本与效益的平衡。由于每节工作时间为3小时，一天被分为8班，每人连续工作3节，各班时间安排如下（见表2-5）：表2-5 时段班 次最低需求人数123456780-33-66-99-1212-1515-1818-2121-086152025231810成本8480706262667280为了建立

19、数学模型，对应于一般成本效益平衡问题，我们首先必须明确包含的活动数目，活动一个单位是对应于分派一个话务员到该班次收，效益的水平对应于时段。收益水平就是该时段里上下班的话务员数目，各活动的单位效益贡献就是在该时间内增加的在岗位话务员数目。我们给出下列成本效益平衡问题参数表（见表2-6）：表2-6 时段班 次最低需求人数123456780-33-66-99-1212-1515-1818-2121-0111000000111000000111000000111000000111000000111100000111100000186152025231810成本8480706262667280决策变量表

20、示分派到第班的话务员人数（= 1，2，3，4，5，6，7，8），约束条件为：0-3时间段： （最低可接受水平）3-6时间段： 6-9时间段： 9-12时间段： 12-15时间段： 15-18时间段： 18-21时间段： 21-0时间段： 非负约束： = 1，2，3，4，5，6，7，8目标函数为最小化成本：图2-14 话务员排班问题的Excel规划求解根据以上模型，建立相应的Excel电子表格线性规划模型，并用“规划求解”得到一个最优解（见图2-14），第一班安排4人上班，第二班安排2人上班，第三、四、五、六、七班分别安排9、9、8、6、4人，第八班不安排人，在满足各时段的最低人数需求的同时花费

21、最少的薪金支出（2864元）。例4.多阶段生产安排问题南方机电制造公司为全国各地生产一种大型机电设备，按照公司的订单合同，不久要交付使用一定数量的机电设备，所以有必要制定为期6个月的设备生产计划。根据合同，公司必须在未来6个月中每个月底交付一定数量的机电设备，由于原料价格、生产条件、保修和维修工作等安排不同，每月的生产能力和生产成本也不同，当然，可以在成本较低的月份多生产一些设备，但在供给客户之前必须存放，需要付一定的存贮费用。管理层需要制定出一个逐月生产计划，使生产和存贮的总成本达到最小。管理科学小组通过调查收集到每单位生产成本、每月单位存贮费、每月需求量、最大生产能力等数据（见表2-7）。表2-7 月份（）月底需求量（台）最大生产能力（台）单位生产成本（千元）单位存贮成本（千元）最大存贮量（台）1234561016201425232030262830302.12.02.32.42.12.60.20.250.230.240.20.210