运筹学软件的使用.ppt

《运筹学软件的使用.ppt》由会员分享，可在线阅读，更多相关《运筹学软件的使用.ppt（123页珍藏版）》请在装配图网上搜索。

1、运筹学软件的使用,运筹学软件,Lindo的使用（Linear, Interactive, and Discrete Optimizer） Lingo的使用 WinQSB的使用 Scilab的使用,Lindo软件,简介 使用方法 实例,Lindo 简介,LINDO由Linus Schrage 于1986年开发的优化计算软件包, 可以用来求解线性规划 (LP-Linear Programming), 整数规划 (IP-Integer Programming) 和二次规划 (QP-Quadratic Programming) 问题. 由于LINDO执行速度很快、易于方便输入、求解和分析数学规划问题。

2、因此在数学、科研和工业界得到广泛应用。 具体事务包括：产品分销、成分混合、生产与个人事务安排、存货管理,一般用LINDO（Linear Interactive and Discrete Optimizer）解决线性规划(LP-Linear Programming)。整数规划（IP-Integer Programming）问题。其中LINDO 6 .1 学生版至多可求解多达300个变量和150个约束的规划问题。其正式版（标准版）则可求解的变量和约束在1量级以上。,使用方法,窗口界面 基本操作 模型输入 求解 结果分析 求解整数线性规划,模型输入,变量：以字母开头字母和数字组成，系数在前变量在后，

3、 变量默认为非负变量 目标函数: max(min) 函数 max 4 x1+2 x2 约束不等式: 以Subject To 开始，以end结束 1）=或-大于等于号 2）= 或-小于等于号 3）不区分大小写,求解,求解按钮 求解菜单,是否进行灵敏度分析,对各项数据/控制按钮的说明,据项/控制 说明 Status 给出当前解决方案的状态，可能的值包括：Optimal（最优的）, Feasible（可行的）, Infeasible（不可行的）,Unbounded（未定的） Iterations solver的重复次数 Infeasibility 多余或错误约束条件数量 Objective 目标函数

4、的当前值 Best IP 标示得到最优整数解决方案值，该项只出现在IP（整数规划）模型。 IP Bound IP模型中目标的理论范围 Branches 由LINDO IP solver分生出来的整型变量个数 Elapsed Time solver启动后所经过时间 Update Interval 状态窗口更新周期（秒）。你可以把这个值设成任何一个非负数，如果把它设成零的话很可能会增加求解时间。 Interrupt Solver 按下该按钮，solver将立刻停止并返回当前得到的最优解。 Close 按下该按钮关闭状态窗口，solver继续运行。状态窗口可以通过选取相应命令重新打开。,对偶价格,检

5、验数行,迭代次数,1次迭代或旋转后得到最优解,要判断表达式输入是否有错误时，也可以使用菜单“Reports“的”Picture“选项,若想获得灵敏度分析，可用“Reports“的”Rang“选项,若需显示单纯形表，可执行“Reports“的”Tab lean“选项,注意事项：,） 目标函数及各约束条件之间一定要有“Subject to (ST) ”分开。 ） 变量名不能超过个字符。 ） 变量与其系数间可以有空格，单不能有任何运算符号（如乘号“”等）。,注意事项：,） 要输入=约束，相应以代替即可。 ） 一般LINDO中不能接受括号“（）“和逗号“，“，例：400(X1+X2) 需写成400X1

6、+400X2；10,000需写成10000。 ） 表达式应当经过简化。不能出现 2 X1+3 X2-4 X1，而应写成-X1+3 X2。,整数线性规划,整数变量的设置 一般整数变量 GIN 0-1整数变量 INT 放在end之后 Int 3 前3个为整数0-1 变量 Int x1 x1 为整数0-1 变量 实例,整数规划,max x1+4x2 st 3x1+5x2=8 4x1+6x2=10 end gin 2 -表示有两个变量,整数规划,OBJECTIVE FUNCTION VALUE 1) 5.000000 VARIABLE VALUE REDUCED COST X1 1.000000 -1

7、.000000 X2 1.000000 -4.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 0.000000,整数线性规划,有四个工人，要分别指派他们完成四项不同的工作，每个人做各项工作所消耗的时间如表。问应该如何指派，才能使总的消耗时间为最小？,整数线性规划,工作,整数线性规划,这是一道典型的整数规则问题。 我们记派第I去做工作记为Xij 注意到每人只能做一项工作。每项工作一人做。我们得到目标函数为约束条件：,运行后我们可得到最优目标值为70,在用LINDO解整数规划（IP）问题时，只要在EN

8、D后加上标识即可,INT name 或 INT n (n 指前n 个变量标识为0/1型) 解混合型整数规划则用GIN来标识。,整数线性规划,自由变量,定义：取值可正可负的变量，一般可以通过写成两个非负变量的差转化成非负变量 在end之后 free name,LinGo软件,简介 使用方法 实例,LinGo简介,用于求解非线性规划（NLPNONLINEAR PROGRAMMING）和二次规则（QPQUARATIC PROGRAMING）其中LINGO .0学生版最多可版最多达300个变量和150个约束的规则问题，其标准版的求解能力亦再104量级以上。虽然LINDO和LINGO不能直接求解目标规划

9、问题，但用序贯式算法可分解成一个个LINDO和LINGO能解决的规划问题。 ,使用方法,窗口界面 基本操作 模型输入 求解 结果分析 求解整数线性规划,窗口界面,模型输入,直接输入模式与Lindo类似，不同之处有： 1）以model:开始 以end结束 2)目标函数加等号 max= 3）系数与变量之间加* 3*x1 4）每一个不等式结束后加； 5）在END之前定义整数变量 6）可以出现“（）”,二次规划,min z=(x1-1)2+(x2-2)2 x2-x1=1 x1+x2=0,x2=0,二次规划,model: min=(x1-1)2+(x2-2)2; x2-1=1; x1+x2=2; End

10、,二次规划,Local optimal solution found at iteration: 3 Objective value: 1.000000 Variable Value Reduced Cost X1 0.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price 1 1.000000 -1.000000 2 0.000000 -2.000244 3 0.000000 2.000000,参数输入模式,Model: Sets: !定义集合 Endsets Data: ！定义数据 Enddata 调用函数与

11、计算 end,集合部分,返回,定义数据,返回,求解,求解按钮 求解菜单,结果,例 3.1运输问题,!3发点4收点; Model: Sets: Warehouses/A1.A3/:Capacity; Vendors/B1.B4/:Demand; Links(warehouses,vendors):cost,volume; Endsets !目标函数; Min=sum(links:cost*volume); !需求约束; For(vendors(j): Sum(warehouses(i):volume(i,j)=demand); !产量约束; For(warehouses(i): Sum(vend

12、ors(j):volume(i,j)=capacity); !下面是数据; Data: Capacity=7 4 9; Demand=3 6 5 6; Cost=3 11 3 10 1 9 2 8 7 4 10 5; Enddata,例 3.1运输问题,例 3.1运输问题,例 3.1运输问题,模型的集部分,定义原始集： 语法： setname/member_list/:attribute_list; 用“”表示该部分内容可选 注意： 集的名字可选，集的成员可选，集成员的属性,模型的集部分,Member_list是集成员列表。如果集成员放在集定义中，那么对它们可采取显式罗列和隐式罗列两种方式。

13、当显式罗列成员时，必须为每个成员输入一个不同的名字，中间用空格或逗号搁开，允许混合使用。 当隐式罗列成员时，不必罗列出每个集成员。可采用如下语法： setname/member1.memberN/: attribute_list; 在attribute_ list可以指定一个或多个集成员的属性，属性之间必须用逗号隔开。,模型的数据部分和初始部分,数据部分入门 数据部分以关键字“data:”开始，以关键字“enddata”结束。 语法： object_list = value_list; 对象列（object_list）包含要指定值的属性名、要设置集成员的集名，用逗号或空格隔开。 数值列（val

14、ue_list）包含要分配给对象列中的对象的值，用逗号或空格隔开。注意属性值的个数必须等于集成员的个数。,LINGO有9种类型的函数,1 基本运算符：包括算术运算符、逻辑运算符和关系运算符 2 数学函数：三角函数和常规的数学函数 3 金融函数：LINGO提供的两种金融函数 4 概率函数：LINGO提供了大量概率相关的函数 5 变量界定函数：这类函数用来定义变量的取值范围 6 集操作函数：这类函数为对集的操作提供帮助 7 集循环函数：遍历集的元素，执行一定的操作的函数 8 数据输入输出函数：这类函数允许模型和外部数据源相联系，进行数据的输入输出 9 辅助函数：各种杂类函数,界定函数 定义变量,变

15、量界定函数实现对变量取值范围的附加限制，共4种： 0-1整数变量 bin() bin(x) 限制x为0或1,界定函数 定义变量,BND( 下界, 变量, 上界) 定义有界变量 bnd(L,x,U) 限制LxU FREE( 变量) 定义自由变量 free(x) 取消对变量x的默认下界为0的限制，即x可以取任意实数,界定函数 定义变量,一般整数变量 gin() gin(x) 限制x为整数 放在end之前单个定义,案例,某钢筋车间，现用的原材料是长度10米的钢筋（直径相同），需要制作一批长度为3米的钢筋90根，长度为4米的钢筋60根，问怎样下料既满足需要，又使原材料最少？ 解：根据题意：有如下三种下

16、料方式： 1）截成3米的3根。 2）截成3米的2根， 4米的1根。 3）截成4米的2根。 设三种下料方式B1,B2,B3分别用原材料（10米） x1,x2,x3根，列成表1-7：,下料方式表,可转化成求下面的线性规划问题： min f= x1+x2+x3,下料方式,x1,x2,x3,案例,配料问题案例,问题 问题分析 模型 求解,配料问题,某化工厂要用三中原料混合配置三种不同规格的产品各产品的规格单价如表1，,问如何安排生产使得生产利润最大？,原料的单价与每天最大供应量如表2,问题分析,变量 约束条件 目标函数,变 量,生产计划就是要确定每天生产三种产品的数量以及非中产品中三中原料的数量。而由

17、于每种产品的数量等于三种原料数量之和，所以只要确定每天生产三种产品分别含有的原料数量即可。所以变量就是每天生产三种产品所用的,约束条件,规格约束 等价于,资源约束,目标函数,总产值 总成本 总利润=总产值-总成本,目标函数,模型,求解,集循环函数,语法： function(setname(set_index_list)|conditional_qualifier: expression_list); 1for 该函数用来产生对集成员的约束。基于建模语言的标量需要显式输入每个约束，不过for函数允许只输入一个约束，然后LINGO自动产生每个集成员的约束。 for(set(set_index_li

18、st)|condition:expression),集循环函数,2sum 该函数返回遍历指定的集成员的一个表达式的和。 sum(set(set_index_list)|condition:expression) 例如： For(vendors(j): Sum(warehouses(i):volume(i,j)=demand);,集循环函数,min和max 返回指定的集成员的一个表达式的最小值或最大值。 max(set(set_index_list)|condition:expression) min(set(set_index_list)|condition:expression),辅助函数,

19、if(logical_condition,true_result,false_result) if函数将评价一个逻辑表达式logical_condition，如果为真，返回true_ result，否则返回false_result。 IF( logical_condition, true_result, false_result),ABS( X) COS( X) EXP( X) FLOOR( X) LGM( X) ln (X - 1)! LOG( X) SIGN( X) -1 if X 0. Otherwise, it returns +1.,数学函数,SIN( X) SMAX( X1, X2

20、,., XN) SMIN( X1, X2,., XN) TAN( X),数学函数,WinQSB软件,QSB是Quantitative Systems for Business的缩写，WinQSB是一种教学软件，对于非大型的问题一般都能计算，较小的问题还能演示中间的计算过程。该软件可用于管理科学、决策科学、运筹学及生产运作管理等领域的求解问题。,WinQSB软件,（2） WinQSB软件用法 安装WinQSB软件后，在系统程序中自动生成WinQSB应用程序，用户根据不同的问题选择子程序。进入某个子序后，第一项工作就是建立新问题或打开已有的数据文件，观察数据输入格式，系统能够解决哪些问题，结果的输

21、出格式等内容。,WinQSB软件,QSB的基本内容 1、抽样分析Acceptance Sampling Analysis(ASA) 2、综合计划编制Aggregate Planning(AP) 3、决策分析Decision Analysis(DA) 4、动态规划 Dynamic Programming(DP) 5、设备场地布局Facility Location and Layout(FLL),WinQSB软件,6、预测与线性回归Forecasting and Linear Regression(FC) 7、目标规划与整数线性目标规划Goal Programming and Integer Li

22、near goal Programming (GP-IGP) 8、库存论与存储控制系统 Inventory Theory and Systems (ITS) 9、作业调度Job Scheduling(JOB),WinQSB软件,10、线性规划和整数规划 Linear Programming and Integer Linear Programming (LP- ILP) 11、马尔可夫过程MarKov Process(MKP) 12、物料需求计划Material Requirements Planning（MRP） 13、网络模型 Network Modeling (Net) 14、非线性规划

23、NonLinear Programming(NLP) 15、网络计划Project scheduling(PERT-CPM),WinQSB软件,16、二次规划 Quadratic Programming (QP) 17、排队分析 Queuing Analysis (QA) 18、排队系统模拟 Queuing System Simulation (QSS) 19、质量管理控制图Quality Control Charts(QCC),本章所有计算都调用子程序Network Modeling。 1.用WinQSB求解最小树 例 求解下图的最小树。 启动程序。依次点击开始，程序，WinQSB，Netw

24、ork Modeling。,WinQSB软件示例, 建立新问题。 在右图中选择Minimal spanning Tree，输入标题与顶点数。点击确定后，出现下表。 输入数据 在右表中输入数据，两点间的权数只输入一次。,求解 点击菜单栏Solve and Analyze，输出表最小树结果，最小树长为15。点击菜单栏Results-Graphic Solution,显示最小树树形。,2. 用WinQSB求解最短路 进入图6-6-2所示界面，选择Shortest Path Problem，如果是有向图就按弧的方向输入数据，如果是无向图每条边必须输入两次，无向边变为两条方向相反的弧。 例如求图6-6-

25、6的最短路。输入数据，见表6-6-7。,点击菜单栏Solve and Analyze后系统提示用户选择图的起点和终点，系统默认从第一个点到最后一个点，用户选择后系统不仅输出v1到v5的路径和路长，还显示了v1到各点的最短路长，见表6-6-8。点击菜单栏Results-Graphic Solution, 显示了v1到各点的最短路线图（图6-6-9）。,3. 用WinQSB求解最大流 选择Maximal Flow Problem，输入节点数，输入数据，求解与最短路同，点击菜单栏Results-Graphic Solution, 输出最大流网络图。（略） 4. 用WinQSB求解最小费用流 系统没有

26、直接求最小费用流的程序，只要利用第四节中（*）式得到赋权图，就可以用最短路程序寻找最小费用增广链，解决了主要的计算过程。,Scilab软件,软件简介 基本操作 求解线性规划,简介,Scilab是由法国INRIA实验室开发的一个开放源代码的自由软件，它最初是为系统控制和信号处理而开发的。与传统的开放源代码数学软件相比，Scilab的特点在于它具有友好的用户界面和较完善的图形功能。Scilab软件由三个部分组成：语言解释器，Scilab例程的函数库，Fortran和C例程库。,特点,免费、开放源代码 简单易学 强大的网络优化功能 兼容性强与matlab、 Fortran和C兼容,http:/www

27、.scilab.org/,基本操作,窗口界面 数据类型 矩阵运算,窗体界面,数据类型,数字 向量 矩阵 字符 列表,矩阵定义与运算,矩阵定义与运算,Scilab函数,命令1：x,lagr,f=linpro(p,C,b ,x0) 命令2：x,lagr,f=linpro(p,C,b,ci,cs ,x0) 命令3：x,lagr,f=linpro(p,C,b,ci,cs,me ,x0) 命令4：x,lagr,f=linpro(p,C,b,ci,cs,me,x0 ,imp) 命令5： x1,crit=karmarkar(a,b,c,x0) 注意事项,命令1,问题形式 min p*x s.t. C*x =

28、 b 实例,x,lagr,f=linpro(p,C,b ,x0）,实例,Max 3x1+5x2+4x3 2x1+3x2=1500 s.t. 2x2+4x3=800 3x1+2x2+5x3=2000,命令2,x,lagr,f=linpro(p,C,b,ci,cs ,x0) 问题形式 min p*x s.t. C*x = b ci = x = cs 实例,实例,命令3,x,lagr,f=linpro(p,C,b,ci,cs,me ,x0) 问题 min p*x s.t. C(j,:) x = b(j), j=1,.,me C(j,:) x = b(j), j=me+1,.,me+md ci = x

29、 = cs 实例,实例,命令4：,x,lagr,f=linpro(p,C,b,ci,cs,me,x0 ,imp) 问题形式 min p*x s.t. C(j,:) x = b(j), j=1,.,me C(j,:) x = b(j), j=me+1,.,me+md ci = x = cs 指定初始可行解x0,命令5,x1,crit=karmarkar(a,b,c,x0) 问题形式 min c*x s.t. a*x = b x=0 X0必须为内点可行解x0 0 a*x0=b 实例,实例,注意事项,命令2和3中x0可省略，但命令4和5中不可省略 向量都是列向量，参数的顺序不可换 命令3中等式约束必须在前面,