运筹学课程设计指导书.doc

课程设计指导书【预备实验】一 LINDO的基本操作一实验目的1.熟悉LINDO软件的操作界面。2.掌握LINDO中的基本语法。二实验原理本实验使用LINDO 6.01进行操作。LINDO（Linear Interactive and Discrete Optimizer）是一种专门用于求解数学规划问题的软件包。由于LINDO执行速度很快、易于方便输入、求解和分析数学规划问题，因此在数学、科研和工业界得到广泛应用。LINDO主要用于解线性规划、非线性规划、二次规划和整数规划等问题。也可以用于一些非线性和线性方程组的求解以及代数方程求根等。LINDO中包含了一种建模语言和许多常用的数学函数（包括大量概论函数），可供使用者建立规划问题时调用。一般用LINDO解决线性规划（LPLinear Programming），整数规划（IPInteger Programming）问题。其中LINDO 6 .01 学生版至多可求解多达100个变量和50个约束的规划问题。其正式版（标准版）则可求解的变量和约束在104量级以上。要学好用这个软件最好的办法就是学习它自带的HELP文件。三实验设备与器件1.安装win98系统以上的计算机。2.LINDO 6.01或更高版本的软件。四实验预习要求1.在网上下载LINDO软件。2.自学LINDO软件help文档中的操作界面部分。五、实验内容及实验步骤1.安装LINDO软件到D:LINDO。2.LINDO的基本语法。与MATLAB等工具一样，LINDO对所求解问题的描述也有自身的一套规则。LINDO的基本程序架构如下：MAX 目标函数表达ST 变量约束1 变量约束2 变量约束3 END3.简单的示例假设现在一个计算机厂商要生产两种型号的PC：标准型(standard)和增强型(turbo)，由于生产线和劳动力工作时间的约束，使得标准型PC最多生产100台。增强型PC最多生产120台；一共耗时劳动力时间不能超过160小时。已知每台标准型PC可获利润$100，耗掉1小时劳动力工作时间；每台增强型PC可获利润$150，耗掉2小时劳动力工作时间。请问：该如何规划这两种计算机的生产量才能够使得最后获利最大？这个问题是标准的线性规划，目标函数是100*standard+150*turbo最大！lindo的程序如下：max 100 standard+150 turbost standard=100 turbo=120 standard+2 turbo=160end然后再按运算符键即可得结果。运行结果如下：LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 14500. VARIABLE VALUE REDUCED COST STANDARD 100.000000 0.000000 TURBO 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 25.000000 3) 90.000000 0.00000 4) 0.000000 75.000000 NO. ITERATIONS= 2注解：第一行告知线性优化步数为2，下面是目标函数值=14500，在standard=100/turbo=30时取到；下面是对偶值。六实验报告要求（可选）1.将实验中对例子求解的步骤详细写在报告里。二 线性规划问题一实验目的1. 掌握对线性规划问题的数学模型抽象。2. 掌握对线性规划问题的求解方法。3. 掌握用LINDO求解该问题的基本步骤。4. 学会分析LINDO的计算结果。二实验原理线性规划常见可以解决资源分配问题，成本效益平衡问题。在求解线性规划时，常用的方法有图解法和单纯形法。单纯形法基本思路是：先找出一个基本可行解,判断其是否为最优解,如果不是最优解，则转换到相邻的基本可行解,并使目标函数值不断增大,直到找出最优解或判断有无界解、无解为止。三实验预习要求1 复习解线性规划问题的步骤。2 了解线性规划问题的基本写法。四实验内容与实验步骤利用所学知识，利用LINDO求解下列两个问题：问题1 试验一中的实例。问题2 一个企业需要同一种原材料生产甲乙两种产品，他们的单位产品所需要的原材料的数量，以及所消耗的加工时间各不相同，从而所获得的利润也不相同，如下表所示。那么，该企业应如何安排生产计划，才能使获得的利润最大？表 2.1产品/资源甲乙可利用的资源原材料（t）23100加工时间（h）42120单位利润（100元）64求解步骤：1 抽象出数学表达式，照标准格式书写。2 将表达式按LINDO的语法规则输入到该软件中。3 进行求解。4 对实验数据进行分析。五实验报告要求（可选）1 写出问题2的常规数学表达式和在LINDO中的语法表达。2 将LINDO的求解结果写在实验报告里。三 灵敏度分析一实验目的1掌握灵敏度分析原理和方法，能够对目标函数系数和右边常数进行灵敏度分析。2掌握增加一个变量，增加一个约束后求新的最优解的方法。二实验原理灵敏度分析是要在求得最优解以后，解决以下几方面的问题：1 线性规划问题中的各系数在什么范围内变化，不会影响已获得的最优基。2 如果系数的变化超过以上范围，如何在原来最优解的基础上求得新的最优解3 当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。三实验内容本次实验将分别讨论下列数据或条件变化时对于最优基（最优解）的灵敏度分析：l 目标函数的变化；l 右端常数的变化；l 增加新变量或新的约束条件的变化；l 目标系数或右端项包含参数的变化。依次针对上面的四个条件对下面的几个例子进行灵敏度分析：例3.1 线性规划问题为minz=-2x1+x2-x3s.t.x1+x2+x36-x1+2x24x1,x2,x30求c2=1在什么范围内变化，原来的最优基保持不变；当c2=-3时，最优基是否变化，如果变化，求新的最优基和最优解。例3.2 在线性规划问题中，对c1=1进行灵敏度分析。minz=x1+x2-4x3s.t.x1+x2+2x39x1+x2-x32-x1+x2+x34x1,x2,x30例3.3 对以下线性规划问题中第一个约束右边常数b1=9进行灵敏度分析。minz=x1+x2-4x3s.t.x1+x2+2x39x1+x2-x32-x1+x2+x34x1,x2,x30例3.4 在例3.1minz=-2x1+x2-x3s.t.x1+x2+x36-x1+2x24x1,x2,x30中，增加一个新的变量x6，它在目标函数中的系数c6=1，在约束条件中的系数向量为，求新的最优基和最优解。例3.5 设线性规划问题为minz=-2x1+x2-x3s.t.x1+x2+x36-x1+2x24x1,x2,x30最优单纯形表为zx1x2x3x4x5RHSz10-3-1-20-12x10111106x500311110增加一个约束-x1+2x22，求新的最优基和最优解。四试验报告要求（可选）将上述问题的LINDO求解结果写在报告里。四 整数规划一实验目的1.掌握整数规划的基本数学模型。2.熟悉解的特点。3.能够用LINDO求解一般整数规划问题。4.培养对模型和解结果进行分析的能力。二实验原理整数规划简介：整数线性规划数学模型的一般形式为: 整数线性规划问题可以分为下列几种类型：1. 纯整数线性规划(Pure integer linear programming)：指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。2. 混合整数线性规划(Mixed integer linear programming）：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。3. 0-1型整数线性规划(Zero-one integer linear programming)：指决策变量只能了取值0或1的整数线性规划。三实验内容与步骤求解下面的整数规划问题：1.某服务部门各时段（每2小时为一时段）需要的服务人数见表4-2。按规定，服务员连续工作8小时（即四个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。表 4.1时 段12345678服务员最少数目108911138532.人力资源分配问题某个中型百货商场对售货人员（周工资200元）的需求经统计如下表:表 4.2星期一二三四五六七人数12151214161819为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？求解步骤：1.弄清楚所求解的问题。2.抽象出数学模型。3.输入到LINDO里求解。4.分析实验结果。四实验报告要求（可选）1.分别对所求的问题进行分析和建模，列出因素、方案、变量、约束条件、目标函数和计算模型2.用LINDO软件对该计算模型进行求解并分析其结果。【综合实验】（必做）一实验目的锻炼应用所学知识解决综合性问题的能力二实验内容任选一题，可4-5人组队解决。A. 线材切割问题 在很多工程领域，都有线材切割问题。这一问题可表述为:设能购买到的不同长度的原线材有m种，长度分别为L1,.,Lm，这些原线材只是长度不同，其它都相同。某工程中所要切割出的线材长度分别为li,i=1,2,.,n(这里 li 所有Li)，对应数量分别为Ni,i=1,2,.,n。设计优化计算方案，求出分别需要购买多少根不同长度的原线材,并能给出切割方案及线材利用率。现假设某装修工程中需要对铝合金线材进行切割，工程能购买到的同一规格的铝合金线材有二种长度，一种长度是8米，另一种是12米。现在假设要切割长度和数量如下所示的铝合金线材：表 5.1编号长度(单位:米)数量(单位:根)16.209023.6012032.8013641.8531050.7521560.55320应用所设计的计算方案，请问至少需要购买多少根8米和12米的线材，使浪费的线材比较少，并给出切割方案和计算线材利用率。B. 板材切割问题 设工程中能购买到的原板材的长、宽分别为X、Y；现要切割长度和宽度分别为xi,yi, i = 1,2,.,m 共m种大小的板材，每种板材的所需数量分别为N1,N2,.,Nm块给出一个切割算法，尽量使购买的板材数量少，并给出切割方案和计算板材利用率。利用所设计计算方案，对下列假设数据，计算需要购买多少块原板材，并给出切割方案和计算板材利用率。原板材长2.85米，宽1.55米。所需板材: 表 5.2编号长度(单位:米)宽度(单位:米)数量(单位:块)