《建模教程线性规划》PPT课件.ppt

静态最优化问题 2020 2 9 线性规划模型与求解 线性规划LinearProgramming 运筹学中应用最广泛的方法之一运筹学的最基本的方法之一 网络规划 整数规划 目标规划和多目标规划都是以线性规划为基础的解决稀缺资源最优分配的有效方法 使付出的费用最小或获得的收益最大 研究对象 有一定的人力 财力 资源条件下 如何合理安排使用 效益最高某项任务确定后 如何安排人 财 物 使之最省 线性规划的数学模型 某家具厂木器车间生产木门与木窗两种产品 加工木门收入为56元 扇 加工木窗收入为30元 扇 生产一扇木门需要木工4小时 油漆工2小时 生产一扇木窗需要木工3小时 油漆工1小时 该车间每日可用木工总工时为120小时 油漆工总工时为50小时 问该车间应如何安排生产才能使每日收入最大 设该车间每日安排生产木门x1扇 木窗x2扇 Model Maxz 56x1 30 x2s t4x1 3x2 1202x1 x2 50 x1 x2 0解得 X 15 20 T z 1440 假若另有一个个体经营者 手中有一批木器家具生产订单 他想利用该木器车间的木工与油漆工来加工完成他的订单 他就要事先考虑付给该车间每个工时的价格 他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图从而愿意为他加工这批订单 又使自己所付的工时费用总数最少 设w1 w2分别为付给木工和油漆工每个工时的价格 则该个体经营者的目标函数为每日所付工时总费用最小 Minf 120w1 50w2该个体经营者所付的价格不能太低 至少不能低于该车间生产木门 木窗时所得到的收入 否则该车间觉得无利可图就不会替他加工这批订单 因此 需满足4w1 2w2 563w1 w2 30w1 w2 0解得 W 2 24 f 1440 Maxz 56x1 30 x2Minf 120w1 50w2s t4x1 3x2 120s t 4w1 2w2 562x1 x2 503w1 w2 30 x1 x2 0w1 w2 0上面两个线性规划模型称为一对对偶的线性规划模型 任一线性规划问题都有一对偶问题 线性规划模型特点 决策变量 向量 x1 xn T决策人要考虑和控制的因素 一般非负约束条件 线性等式或不等式目标函数 Z x1 xn 线性式 求Z极大或极小 11 一般式 max min Z C1X1 C2X2 CnXn 隐含的假设 比例性 决策变量变化引起目标的改变量与决策变量改变量成正比可加性 每个决策变量对目标和约束的影响独立于其它变量连续性 每个决策变量取连续值确定性 线性规划中的参数aij bi ci为确定值 线性规划模型 线性规划模型的结构目标函数 max min约束条件 变量符号 0 unr 0线性规划的标准形式目标函数 min约束条件 变量符号 0 线性规划的图解法 maxz x1 3x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 可行域 目标函数等值线 最优解 6 4 8 6 0 x1 x2 可行域线段组成的凸多边形目标函数等值线为直线最优解凸多边形的某个顶点 LP问题的特性 2维 n维 超平面组成的凸多面体等值线是超平面凸多面体的某个顶点 凸集 D是n维欧氏空间的一个集合X 1 X 2 D 若任一个满足X X 1 1 X 2 0 1 有X D 定义1 凸集及其顶点 X 1 X 2 X k 是n维欧氏空间中的k个点 若有一组数 1 2 k满足0 i 1 i 1 k 定义2 有点x 1X 1 kX k 则称点X为X 1 X 2 X k 的凸组合 凸组合 凸集D 点X D 若找不到两个不同的点X 1 X 2 D使得X X 1 1 X 2 0 1 则称X为D的顶点 定义3 顶点 定理2 LP有最优解 必定可以在可行域 凸多面集 的顶点得到 定理1 LP问题的可行域一定是凸集 凸多面集 LP问题的解的性质 凸集 凸集 不是凸集 LP问题解的性质 m n r A m 至少有一个m阶子式不为0 定义1 基 基阵 A中一个子矩阵B是可逆矩阵 则称方阵B为LP问题的一个基 AX b的求解 A BN X XBXN TXBXN BN b BXB NXN bBXB b NXNXB B 1b B 1NXN 两个重要公式 当LP的数学模型为一般型时 两个重要公式形如 B P1P2 Pm I 当Xj 0 j m 1 n 时 单纯形法原理 此时 B P1P2 Pm 对应的基本可行解为 定理1 对解X 1 若检验数 j j m 1 n 全部 0 则X 1 为最优解 定理2 对X 1 若有某个非基变量Xm k m k 0且相应的Pm k a1m k amm k T 0 则原问题无有限最优解 线性规划的求解软件 LINDOLINGO ExcelMatlabMathematicaSASCPLEX LinDo 输入模型求解点击求解按钮即可结果 输入模型 注释内容 可用中文 目标函数 最大 max 最小 min 大小写不分max3x1 5x2 4x3 约束 以subjectto开始subjectto2x1 3x2 15002x2 4x3 8003x1 2x2 5x3 2000end 注意事项 变量以字母开头 下标写在后面 系数与变量之间加空格不等号为 与 等同变量非负约束可省略结束时以end标示 结果 LPOPTIMUMFOUNDATSTEP3OBJECTIVEFUNCTIONVALUE1 2675 000VARIABLEVALUEREDUCEDCOSTX1375 0000000 000000X2250 0000000 000000X375 0000000 000000ROWSLACKORSURPLUSDUALPRICES2 0 0000001 0500003 0 0000000 6250004 0 0000000 300000 LinGo 输入模型LinDo模式LinGo模式求解点击求解按钮即可结果 LinGo输入模式 model MAX 3 x1 5 x2 4 x3 2 x1 3 x2 1500 2 x2 4 x3 800 3 x1 2 x2 5 x3 2000 end 注意与LinDo的区别 目标函数中加等号变量与系数之间用 Model end可省略 LinGo模式 Model Sets 定义集合EndsetsData 定义数据Enddata调用函数与计算end 集合部分 model 开始sets 定义集合ve 1 3 c x co 1 3 b ma co ve a endsets 注 集表达式 名称 成员 属性名称 初始集 属性 定义数据 data 定义数据c 354 ba 230024325 Enddata 注 数据的大小与集合定义中一致 分量中间用空格或逗号分开 数据结束后用分号 调用函数 max sum ve j c j x j for co i sum ve j a i j x j b i 主要函数 for set set index list condition expression sum set set index list condition expression min max set set index list condition expression 结果 Globaloptimalsolutionfoundatiteration 3Objectivevalue 2675 000VariableValueReducedCostC 1 3 0000000 000000C 2 5 0000000 000000C 3 4 0000000 000000X 1 375 00000 000000X 2 250 00000 000000X 3 75 000000 000000 B 1 1500 0000 000000B 2 800 00000 000000B 3 2000 0000 000000A 1 1 2 0000000 000000A 1 2 3 0000000 000000A 1 3 0 0000000 000000A 2 1 0 0000000 000000A 2 2 2 0000000 000000A 2 3 4 0000000 000000A 3 1 3 0000000 000000A 3 2 2 0000000 000000A 3 3 5 0000000 000000RowSlackorSurplusDualPrice12675 0001 00000020 0000001 05000030 0000000 625000040 0000000 3000000 用MATLAB优化工具箱解线性规划 命令 x linprog c A b 2 模型 minz cX 命令 x linprog c A b Aeq beq 注意 若没有不等式 存在 则令A b 命令 1 x linprog c A b Aeq beq VLB VUB 2 x linprog c A b Aeq beq VLB VUB X0 注意 1 若没有等式约束 则令Aeq beq 2 其中X0表示初始点 4 命令 x fval linprog 返回最优解 及 处的目标函数值fval 解编写M文件如下 c 0 4 0 28 0 32 0 72 0 64 0 6 A 0 010 010 010 030 030 03 0 02000 0500 00 02000 050 000 03000 08 b 850 700 100 900 Aeq beq vlb 0 0 0 0 0 0 vub x fval linprog c A b Aeq beq vlb vub 线性规划的应用 市场营销 广告预算和媒介选择 竞争性定价 新产品开发 制定销售计划 生产计划制定 合理下料 配料 生产计划 库存 劳力综合 库存管理 合理物资库存量 停车场大小 设备容量 运输问题财政 会计 预算 贷款 成本分析 投资 证券管理 人事 人员分配 人才评价 工资和奖金的确定 设备管理 维修计划 设备更新 城市管理 供水 污水管理 服务系统设计 运用 应用条件 要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件 某种产品由4个1号零件 3个2号零件组成 这些零件可由三个工厂生产 生产1号 2号零件需A B两种原料 现有300公斤原料A 500公斤原料B 问 如何安排生产使产品产量最大 合理下料问题某车间接到制作100套钢架的订单 每套钢架用长为2 9米 2 1米 1 5米的圆钢各一根 已知原料长7 4米 问应如何下料 使原材料最省 设按方案i i 下料的原材料根数为Xi 则可以列出下面模型 由计算得到的最优下料方案为 按方案I下料30根 按方案II下料10根 按方案IV下料50根 即需要90根原料可以制造100套钢架 考虑下列问题 可行的套裁方案是否完全 如何找出所有的套裁方案 如何比较和取舍套裁方案 是否可以使用其他的目标函数形式 其要求和意义有不同 如何决定约束是取 还是取 整数约束是否可以忽略 求解方法是否合适 有配套约束的资源优化问题 某公司计划用资金60万元来购买A B C三种运输汽车 已知A种汽车每辆为1万元 每班需一名司机 可完成2100t km B种汽车每辆为2万元 每班需两名司机 可完成3600t km C种汽车每辆为2 3万元 每班需两名司机 可完成3780t km 每辆汽车每天最多安排三班 每个司机每天最多安排一班 购买汽车数量不超过30辆 司机不超过145人 问 每种汽车应购买多少辆 可使该公司今后每天可完成的t km数最大 例 某炼油厂生产三种规格的汽油 70号 80号与85号 它们各有不同的辛烷值与含硫量的质量要求 这三种汽油由三种原料油调和而成 每种原料油每日可用量 质量指标及生产成本 每种汽油的质量要求和销售价格见下表 假定在调和中辛烷值与含硫量指标都符合线性可加性 问该炼油厂如何安排生产才能使利润最大 港口船只配备问题 某航运公司承担六个港口城市A B C D E F的四条固定航线的物资运输任务 已知各条航线的起点 终点城市及每天航班数 假定各条航线使用相同型号的船只 已知各城市间航程天数 又知每条船只每次装卸货的时间各需一天 问该公司至少应配备多少条船 才能满足所有航线运货要求 航运公司所需配备的船只分两部分 载货航程 包括装 卸货 需要的周转船只数 共91条 港口间调度所需船只数 即空船行驶部分 各港口每天船只余缺表 对某个港口 若到达的船只多于发出船只 多余的船只则调往其他港口 它相当于产地 若到达的船只少于发出船只 则需从其他港口调入船只 它相当于销地 以航程天数作为单位运价 这是一个供需平衡的运输问题 最优调度方案如下 共需周转船40条 所需配备船只总数为条 131 运输问题的数学模型 设有同一种货物从m个产地1 2 m运往n个销地1 2 n 第i个发地的供应量 Supply 为si si 0 第j个收地的需求量 Demand 为dj dj 0 每单位货物从发地i运到收地j的运价为cij 求一个使总运费最小的运输方案 我们假定从任一发地到任一收地都有道路通行 如果总供应量等于总需求量 这样的运输问题称为供求平衡的运输问题 运输问题线性规划模型 在运输问题线性规划模型中 令X x11 x12 x1n x21 x22 x2n xm1 xm2 xmn TC c11 c12 c1n c21 c22 c2n cm1 cm2 cmn Tb s1 s2 sm d1 d2 dn TA a11 a12 a1n a21 a22 a2n am1 am2 amn 则运输问题的线性规划可以写成 minz CTXs t AX bX 0其中A矩阵的列向量aij ei em j 运输问题网络图 供应地 运价 需求地 供应量 需求量 总供应量20吨 总需求量20吨 供求平衡的运输问题 运输问题线性规划模型 供应地约束 需求地约束 运输问题系数矩阵的秩为m n 1 即运输问题有m n 1个基变量 mn m n 1 个非基变量 例如以上问题m 3 n 4 基变量为3 4 1 6个 非基变量为12 6 6个 运输问题的表格表示 运输问题的网络图 线性规划模型以及运输表之间的关系 运输问题单纯形法 1 求得一个初始基础可行解 2 对非基变量xij计算检验数cij zij 根据各非基变量的检验数的值 确定最优性或选择进基变量 3 当进基变量xij进基时 根据基变量的变化 求出最先降为0的基变量确定为离基变量 4 进行基变换 获得新的基础可行解并转步骤2 98A题投资的收益和风险 试给该公司设计一种投资组合方案 即用给定的资金 有选择地购买若干种资产或存银行生息 使净收益尽可能大 而总体风险尽可能小 设变量xi表示存入银行和购买Si的金额yj 0表示不买Sj yj 1表示购买Sj 投资的收益和风险的数学模型为 这是一个双目标优化问题 可化为单目标规划问题 模型1固定风险水平 优化收益 模型2固定盈利水平 最小化风险 模型3确定投资者的风险 收益偏好参数 0 在上述三个模型中 选择k h的不同水平和 的不同取值进行求解就可揭示投资和风险间的相互依存关系 再根据投资者对风险的承受能力 确定投资方案 求解中的问题 上述模型虽已化成单目标规划 但交易成本函数是非凸和非连续的 无法用通常的方法求解 交易费函数的简化 考虑到投资总额M相当大 若某种资产被选中 其投资额一般都超过ui 从而交易费简化为 风险度量的选择也造成了模型3求解的困难 可以用引入新变量的方法 把模型化为线性规划模型 电站建设计划在今后的十五年 某省的用电需求将显著增加 该省水利发电站将负责投资兴建新电站以满足增加的电量需求 每年对电的需求通常由下面三个特性值确定 总电量 单位为106千瓦时 保证功率 单位为103千瓦 峰值功率 单位为103千瓦 下页表给出了以上特性值在以后的十五年应达的增加量 因为电不可贮存 所以不同类型的电站的三个特性值很不相同 例如 同是一百万千瓦发电 蒸气发电峰值功率为0 30 103KW 而核发电站的保证功率和峰值功率分别为0 20 103KW 和0 25 103KW 给出了在以后的十五年内欲意兴建的五座电站的功率特性值 投资量以及年总费用所有数据都是对年输出电量一百万千瓦时 106KWH 而言的 年总费用包括每年的建设费用和