运筹学软件的使用.ppt

运筹学软件的使用 运筹学软件 Lindo的使用 Linear Interactive andDiscreteOptimizer Lingo的使用WinQSB的使用Scilab的使用 Lindo软件 简介使用方法实例 Lindo简介 LINDO由LinusSchrage于1986年开发的优化计算软件包 可以用来求解线性规划 LP LinearProgramming 整数规划 IP IntegerProgramming 和二次规划 QP QuadraticProgramming 问题 由于LINDO执行速度很快 易于方便输入 求解和分析数学规划问题 因此在数学 科研和工业界得到广泛应用 具体事务包括 产品分销 成分混合 生产与个人事务安排 存货管理 一般用LINDO LinearInteractiveandDiscreteOptimizer 解决线性规划 LP LinearProgramming 整数规划 IP IntegerProgramming 问题 其中LINDO6 1学生版至多可求解多达300个变量和150个约束的规划问题 其正式版 标准版 则可求解的变量和约束在1量级以上 使用方法 窗口界面基本操作模型输入求解结果分析求解整数线性规划 模型输入 变量 以字母开头字母和数字组成 系数在前变量在后 变量默认为非负变量目标函数 max min 函数max4x1 2x2约束不等式 以SubjectTo开始 以end结束1 或 大于等于号2 或 小于等于号3 不区分大小写 求解 求解按钮求解菜单 是否进行灵敏度分析 对各项数据 控制按钮的说明 据项 控制说明Status给出当前解决方案的状态 可能的值包括 Optimal 最优的 Feasible 可行的 Infeasible 不可行的 Unbounded 未定的 Iterationssolver的重复次数Infeasibility多余或错误约束条件数量Objective目标函数的当前值BestIP标示得到最优整数解决方案值 该项只出现在IP 整数规划 模型 IPBoundIP模型中目标的理论范围Branches由LINDOIPsolver分生出来的整型变量个数ElapsedTimesolver启动后所经过时间UpdateInterval状态窗口更新周期 秒 你可以把这个值设成任何一个非负数 如果把它设成零的话很可能会增加求解时间 InterruptSolver按下该按钮 solver将立刻停止并返回当前得到的最优解 Close按下该按钮关闭状态窗口 solver继续运行 状态窗口可以通过选取相应命令重新打开 对偶价格 检验数行 迭代次数 1次迭代或旋转后得到最优解 要判断表达式输入是否有错误时 也可以使用菜单 Reports 的 Picture 选项 若想获得灵敏度分析 可用 Reports 的 Rang 选项 若需显示单纯形表 可执行 Reports 的 Tablean 选项 注意事项 目标函数及各约束条件之间一定要有 Subjectto ST 分开 变量名不能超过 个字符 变量与其系数间可以有空格 单不能有任何运算符号 如乘号 等 注意事项 要输入 约束 相应以代替即可 一般LINDO中不能接受括号 和逗号 例 400 X1 X2 需写成400X1 400X2 10 000需写成10000 表达式应当经过简化 不能出现2X1 3X2 4X1 而应写成 X1 3X2 整数线性规划 整数变量的设置一般整数变量GIN0 1整数变量INT放在end之后Int3前3个为整数0 1变量Intx1x1为整数0 1变量实例 整数规划 maxx1 4x2st3x1 5x2 84x1 6x2 10endgin2 表示有两个变量 整数规划 OBJECTIVEFUNCTIONVALUE1 5 000000VARIABLEVALUEREDUCEDCOSTX11 000000 1 000000X21 000000 4 000000ROWSLACKORSURPLUSDUALPRICES2 0 0000000 0000003 0 0000000 000000 整数线性规划 有四个工人 要分别指派他们完成四项不同的工作 每个人做各项工作所消耗的时间如表 问应该如何指派 才能使总的消耗时间为最小 整数线性规划 工作 整数线性规划 这是一道典型的整数规则问题 我们记派第I去做工作记为Xij注意到每人只能做一项工作 每项工作一人做 我们得到目标函数为约束条件 运行后我们可得到最优目标值为70 在用LINDO解整数规划 IP 问题时 只要在END后加上标识即可 INTname或INTn n指前n个变量标识为0 1型 解混合型整数规划则用GIN来标识 整数线性规划 自由变量 定义 取值可正可负的变量 一般可以通过写成两个非负变量的差转化成非负变量在end之后freename LinGo软件 简介使用方法实例 LinGo简介 用于求解非线性规划 NLP NON LINEARPROGRAMMING 和二次规则 QP QUARATICPROGRAMING 其中LINGO 0学生版最多可版最多达300个变量和150个约束的规则问题 其标准版的求解能力亦再10 4量级以上 虽然LINDO和LINGO不能直接求解目标规划问题 但用序贯式算法可分解成一个个LINDO和LINGO能解决的规划问题 使用方法 窗口界面基本操作模型输入求解结果分析求解整数线性规划 窗口界面 模型输入 直接输入模式 与Lindo类似 不同之处有 1 以model 开始以end结束2 目标函数加等号max 3 系数与变量之间加 3 x14 每一个不等式结束后加 5 在END之前定义整数变量6 可以出现 二次规划 minz x1 1 2 x2 2 2x2 x1 1x1 x2 0 x2 0 二次规划 model min x1 1 2 x2 2 2 x2 1 1 x1 x2 2 End 二次规划 Localoptimalsolutionfoundatiteration 3Objectivevalue 1 000000VariableValueReducedCostX10 0000000 000000X22 0000000 000000RowSlackorSurplusDualPrice11 000000 1 00000020 000000 2 00024430 0000002 000000 参数输入模式 Model Sets 定义集合EndsetsData 定义数据Enddata调用函数与计算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 vendors j volume i j capacity 下面是数据 Data Capacity 749 Demand 3656 Cost 311310192874105 Enddata 例3 1运输问题 例3 1运输问题 例3 1运输问题 模型的集部分 定义原始集 语法 setname member list attribute list 用 表示该部分内容可选注意 集的名字 可选 集的成员可选 集成员的属性 模型的集部分 Member list是集成员列表 如果集成员放在集定义中 那么对它们可采取显式罗列和隐式罗列两种方式 当显式罗列成员时 必须为每个成员输入一个不同的名字 中间用空格或逗号搁开 允许混合使用 当隐式罗列成员时 不必罗列出每个集成员 可采用如下语法 setname member1 memberN attribute list 在attribute list可以指定一个或多个集成员的属性 属性之间必须用逗号隔开 模型的数据部分和初始部分 数据部分入门数据部分以关键字 data 开始 以关键字 enddata 结束 语法 object list value list 对象列 object list 包含要指定值的属性名 要设置集成员的集名 用逗号或空格隔开 数值列 value list 包含要分配给对象列中的对象的值 用逗号或空格隔开 注意属性值的个数必须等于集成员的个数 LINGO有9种类型的函数 1 基本运算符 包括算术运算符 逻辑运算符和关系运算符2 数学函数 三角函数和常规的数学函数3 金融函数 LINGO提供的两种金融函数4 概率函数 LINGO提供了大量概率相关的函数5 变量界定函数 这类函数用来定义变量的取值范围6 集操作函数 这类函数为对集的操作提供帮助7 集循环函数 遍历集的元素 执行一定的操作的函数8 数据输入输出函数 这类函数允许模型和外部数据源相联系 进行数据的输入输出9 辅助函数 各种杂类函数 界定函数定义变量 变量界定函数实现对变量取值范围的附加限制 共4种 0 1整数变量 bin bin x 限制x为0或1 界定函数定义变量 BND 下界 变量 上界 定义有界变量 bnd L x U 限制L x U FREE 变量 定义自由变量 free x 取消对变量x的默认下界为0的限制 即x可以取任意实数 界定函数定义变量 一般整数变量 gin gin x 限制x为整数放在end之前单个定义 案例 某钢筋车间 现用的原材料是长度10米的钢筋 直径相同 需要制作一批长度为3米的钢筋90根 长度为4米的钢筋60根 问怎样下料既满足需要 又使原材料最少 解 根据题意 有如下三种下料方式 1 截成3米的3根 2 截成3米的2根 4米的1根 3 截成4米的2根 设三种下料方式B1 B2 B3分别用原材料 10米 x1 x2 x3根 列成表1 7 下料方式表 可转化成求下面的线性规划问题 minf x1 x2 x3 下料方式 x1 x2 x3 案例 配料问题案例 问题问题分析模型求解 配料问题 某化工厂要用三中原料混合配置三种不同规格的产品各产品的规格单价如表1 问如何安排生产使得生产利润最大 原料的单价与每天最大供应量如表2 问题分析 变量约束条件目标函数 变量 生产计划就是要确定每天生产三种产品的数量以及非中产品中三中原料的数量 而由于每种产品的数量等于三种原料数量之和 所以只要确定每天生产三种产品分别含有的原料数量即可 所以变量就是每天生产三种产品所用的 约束条件 规格约束等价于 资源约束 目标函数 总产值总成本总利润 总产值 总成本 目标函数 模型 求解 集循环函数 语法 function setname set index list conditional qualifier expression list 1 for该函数用来产生对集成员的约束 基于建模语言的标量需要显式输入每个约束 不过 for函数允许只输入一个约束 然后LINGO自动产生每个集成员的约束 for set set index list condition expression 集循环函数 2 sum该函数返回遍历指定的集成员的一个表达式的和 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 辅助函数 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 1ifX 0 Otherwise itreturns 1 数学函数 SIN X SMAX X1 X2 XN SMIN X1 X2 XN TAN X 数学函数 WinQSB软件 QSB是QuantitativeSystemsforBusiness的缩写 WinQSB是一种教学软件 对于非大型的问题一般都能计算 较小的问题还能演示中间的计算过程 该软件可用于管理科学 决策科学 运筹学及生产运作管理等领域的求解问题 WinQSB软件 2 WinQSB软件用法安装WinQSB软件后 在系统程序中自动生成WinQSB应用程序 用户根据不同的问题选择子程序 进入某个子序后 第一项工作就是建立新问题或打开已有的数据文件 观察数据输入格式 系统能够解决哪些问题 结果的输出格式等内容 WinQSB软件 QSB的基本内容1 抽样分析AcceptanceSamplingAnalysis ASA 2 综合计划编制AggregatePlanning AP 3 决策分析DecisionAnalysis DA 4 动态规划DynamicProgramming DP 5 设备场地布局FacilityLocationandLayout FLL WinQSB软件 6 预测与线性回归ForecastingandLinearRegression FC 7 目标规划与整数线性目标规划GoalProgrammingandIntegerLineargoalProgramming GP IGP 8 库存论与存储控制系统InventoryTheoryandSystems ITS 9 作业调度JobScheduling JOB WinQSB软件 10 线性规划和整数规划LinearProgrammingandIntegerLinearProgramming LP ILP 11 马尔可夫过程MarKovProcess MKP 12 物料需求计划MaterialRequirementsPlanning MRP 13 网络模型NetworkModeling Net 14 非线性规划NonLinearProgramming NLP 15 网络计划Projectscheduling PERT CPM WinQSB软件 16 二次规划QuadraticProgramming QP 17 排队分析QueuingAnalysis QA 18 排队系统模拟QueuingSystemSimulation QSS 19 质量管理控制图QualityControlCharts QCC 本章所有计算都调用子程序NetworkModeling 1 用WinQSB求解最小树例求解下图的最小树 启动程序 依次点击开始 程序 WinQSB NetworkModeling WinQSB软件示例 建立新问题 在右图中选择MinimalspanningTree 输入标题与顶点数 点击确定后 出现下表 输入数据在右表中输入数据 两点间的权数只输入一次 求解点击菜单栏SolveandAnalyze 输出表最小树结果 最小树长为15 点击菜单栏Results GraphicSolution 显示最小树树形 2 用WinQSB求解最短路进入图6 6 2所示界面 选择ShortestPathProblem 如果是有向图就按弧的方向输入数据 如果是无向图每条边必须输入两次 无向边变为两条方向相反的弧 例如求图6 6 6的最短路 输入数据 见表6 6 7 点击菜单栏SolveandAnalyze后系统提示用户选择图的起点和终点 系统默认从第一个点到最后一个点 用户选择后系统不仅输出v1到v5的路径和路长 还显示了v1到各点的最短路长 见表6 6 8 点击菜单栏Results GraphicSolution 显示了v1到各点的最短路线图 图6 6 9 3 用WinQSB求解最大流选择MaximalFlowProblem 输入节点数 输入数据 求解与最短路同 点击菜单栏Results GraphicSolution 输出最大流网络图 略 4 用WinQSB求解最小费用流系统没有直接求最小费用流的程序 只要利用第四节中 式得到赋权图 就可以用最短路程序寻找最小费用增广链 解决了主要的计算过程 Scilab软件 软件简介基本操作求解线性规划 简介 Scilab是由法国INRIA实验室开发的一个开放源代码的自由软件 它最初是为系统控制和信号处理而开发的 与传统的开放源代码数学软件相比 Scilab的特点在于它具有友好的用户界面和较完善的图形功能 Scilab软件由三个部分组成 语言解释器 Scilab例程的函数库 Fortran和C例程库 特点 免费 开放源代码简单易学强大的网络优化功能兼容性强与matlab Fortra