运筹学实验6整数规划.docx

实验六、用 EXCEL 求解整数规划用单纯形法求解线性规划问题，最优解可能是整数，也可能不是整数，但在很多实际问 题中，要求全部或部分变量的取值必须是整数，如所求的解是安排上班的人数，按某个方案 裁剪钢材的根数，生产设备的台数等等对于整数解的线性规划问题，不是用四舍五入或去 尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决，如分枝 定界法和割平面算法这些算法比单纯形法更为复杂，因此，一般的学习者要想掌握整数规 划的数学算法有一定的困难然而事实上，由于Exce l的［工具］［规划求解］可以求解整数规 划问题，所以，对于一个真正有志于运用运筹学方法解决生产经营中问题的管理者来说，算 法将不是障碍因素一、 实验目的1、 掌握如何建立整数线性规划模型，特别是0〜1逻辑变量在模型中的应用2、 掌握用Excel求解整数线性规划模型的方法3、 掌握如何借助于Excel对整数线性规划模型进行灵敏度分析，以判断各种可能 的变化对最优方案产生的影响4、 读懂Excel求解整数线性规划问题输出的运算结果报告和敏感性报告二、 实验内容1、 整数规划问题模型该问题来自于《运筹学基础及应用》（第四版）胡运权主编P126习题4.13，题目如下： 需生产2000件某种产品，该种产品可利用A、B、C、D设备中的任意一种加工，已知每种 设备的生产准备结束费用、生产该产品时的单件成本以及每种设备限定的最大加工数量（件） 如表1所示，问企业应该如何安排设备生产该产品才能使得总的生产成本最少，试建立该问 题的数学模型并求解。

设备准备结束费（元）生产成本（元/件）生产能力（件）A100020900B980241000C800161200D700281600问题建模分析：该产品可以利用四种不同的设备加工，由于采用不同的设备加工需要支付不同的准备结 束费用，而如果不采用某种设备加工，是不需要支付使用该设备的准备结束费用的，所以必 须借助于逻辑变量来鉴定准备结束费用的支付设Xj为利用第j种设备加工的产品数量j 二 1,2,3,4;再设1,若使用第 j种设备生产（即 X > 0）j0，若不使用第 j种设备生产（即 X = 0 ）则问题的整数规划模型为：minz = 1000y + 980 y + 800 y + 700123y + 20 X + 24 X + 16 X + 28 X4 1 2 3 4x1xs .t 2 2x3x4x=1,2,3,4x + x + x + x = 20001234< 900 y1< 1000 y2< 1200 y3< 1600 y4> 0, y = 0或 1，j2、 ［工具］［规划求解］命令求解下面我们用Exce l中的［工具］［规划求解］对该问题进行求解由于［工具］［规划求解］命 令我们在求解线性规划和目标规划问题时已经用过，本实验的重点在于逻辑变量的应用。

另 外，为了使得结果看上去更加直观，我们将会运用f函数来表达逻辑变量的真实涵义第一，表格设置与公式说明根据本问题的规模和条件，拟设置如表1中A1 : K8所示形式：表1变量名称约束条件右边常量目标函数202416-1600700一,“ 02000目标函数中的系数，K2 : K6为约束条件右边常数项B8 : 18为各决策变更的初始值，我们全 部令其为0⑵输入公式：在J2 : J6输入约束条件左边的公式，输入方式为：调用SUMPRODUCT函数， 首先在单元格J2中输入“ =SUMPRODUCT(B2:I2,B$8:I$8)”，单元格J3 : J6的公式只要用填充 柄进行自动填充即可在单元格J7中输入目标函数公式，即“ =SUMPRODUCT(B7:I7,B$8:I$8) ”, 输入方式也是用填充柄自动填充第二，求解选择菜单［工具］［规划求解］，出现［规划求解参数］对话框，在对话框中输入如图1所示 的内容，在这里应该注意的是，在“约束(U)”对话框中输入了 “$F$8:$I$8=二进制”， 这是因为$F$8:$I$8代表决策变量y , y , y , y，而y , y , y , y为逻辑变量，即这四个变1 2 3 4 1 2 3 4量的值只能取0或1。

点击该对话框中的［选项(O)］，选择［采用线性模型］,然后按［确定］, 重新回到［规划求解参数］对话框，点击该对话框中的［求解(S)］，最后的计算结果如表2 所示图1x = 800 , x = 0, x = 1200 , x = 0, y = 1, y = 0, y = 1, y = 0.1 2 3 4 1 2 3 4目标函数：Z=37000表2备C加工的数量为1200件；与此对应的是y = 1, y = 0, y = 1, y = 0意思是：未用设备B1 2 3 4和D加工产品，因此用这两种设备生产产品的准备结束费就不用投入了第四，用if函数来表达逻辑变量取0和1的涵义为了更直观地判断输出结果的意思，我们还可以调用EXCEL中的辻函数来表达逻辑变量取 0和1的涵义方法如下：在表1中再加上一行，即第9行，在单元格F9中输入“ =IF（F8=1,〃 使用〃,〃不使用〃）”，然后用填充柄填充单元格G9:I9这样在第9行的单元格F9:I9,将显示逻辑变量 y = 1, y = 0, y = 1, y = 0的涵义，结果如表3所示1 2 3 4表3ABCDEFGHIJK1变量名称si k2x3yly2y3y4左边公式右边常量2约束条件111100002000200031000-900000-1000401000-100000005001000-12000060001000-1600007目标函数202416281000980800700370008决策变量80001200010109逻辑变量的涵义|使用不使用使用不使用!■三、 课外练习1、利用Excel对教材中的例题进行求解，并与教材中用图解法或分枝定界法求得的结果相比较，以判断计算是否正确。

2、 试着对教材中的习题进行建模，并利用Excel求解，然后阐述计算结果的经济涵义3、 练习使用if函数四、 实验要求1 、 课前预习，写出实验提纲；2、 能建立常见的整数规划模型（纯整数规划、混合整数规划和0-1整数规划），并用Excel进行求解；3、 能读懂Excel输出的结果报告，了解结果的经济学含义，以将计算结果用于指导企业经营实践；4、 根据实验目的和实验内容写出实验报告。