《数学建模与数学实验》教学教学资源（PPT课件）第4讲 线性规划

数学建模与数学实验 tw 线性规划

线性规划 数学建模与数学实验

实验目的 1.了解线性规划的基本内容 2.掌握用数学软件包求解线性规划问题 实验内容 1.两个引例 2.用数学软件包MATLAB:求解线性规划问题. 3.用数学软件包LINDO、LNGO求解线性规划问题. 4.建模案例：投资的收益与风险. 5.实验作业

实验目的 实验内容 2. 掌握用数学软件包求解线性规划问题. 1. 了解线性规划的基本内容. 2. 用数学软件包MATLAB求解线性规划问题. 5. 实验作业. 3. 用数学软件包LINDO、LINGO求解线性规划问题. 1. 两个引例. 4. 建模案例：投资的收益与风险

两个引例 问题一：任务分配问题：某车间有甲、乙两台机床，可用 于加工三种工件.假定这两台车床的可用台时数分别为800和 900,三种工件的数量分别为400、600和500，且已知用三种 不同车床加工单位数量不同工件所需的台时数和加工费用如 下表问怎样分配车床的加工任务，才能既满足加工工件的要 求，又使加工费用最低？ 车床 单位工件所需加工台时数 单位工件的加工费用 可用台 类型 工件1 工件2 工件3 工件1 工件2 工件3 时数 甲 0.4 1.1 1.0 13 9 10 800 乙 0.5 1.2 1.3 11 12 8 900

问题一 ： 任务分配问题：某车间有甲、乙两台机床，可用 于加工三种工件.假定这两台车床的可用台时数分别为800和 900，三种工件的数量分别为400、600和500，且已知用三种 不同车床加工单位数量不同工件所需的台时数和加工费用如 下表.问怎样分配车床的加工任务，才能既满足加工工件的要 求，又使加工费用最低？ 车床 单位工件所需加工台时数 单位工件的加工费用 类 型 工件1 工件2 工件3 工件1 工件2 工件3 可用台 时数 甲 0.4 1.1 1.0 13 9 10 800 乙 0.5 1.2 1.3 11 12 8 900 两个引例

解设在甲车床上加工工件1、2、3的数量分别为x1、2、x, 在乙车床上加工工件1、2、3的数量分别为x4、x5、x6,可建立以 下线性规划模型： minz=13x1+9x2+10x3+11x4+12x5+8x6 X1+x4=400 x2+x=600 x3+x.=500 S.t. 0.4x+1.1x2+x3≤800 0.5x4+1.2x+1.3x6≤900 x,≥0，i=1,2,.,6 解签

解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3， 在乙车床上加工工件1、2、3的数量分别为x4、x5、x6 ,可建立以 下线性规划模型： 解答

问题二：某厂每日8小时的产量不低于1800件.为了进行质量 控制，计划聘请两种不同水平的检验员.一级检验员的标准为： 速度25件/小时，正确率98%，计时工资4元/小时：二级检验员 的标准为：速度15件/小时，正确率95%，计时工资3元/小时.检 验员每错检一次，工厂要损失2元.为使总检验费用最省，该工 厂应聘一级、二级检验员各几名？ 解设需要一级和二级检验员的人数分别为x1、x2人， 则应付检验员的工资为： 8×4×x+8×3×x2=32x,+24x2 因检验员错检而造成的损失为： (8×25×2%×x+8×15×5%×x2)×2=8x,+12x2

问题二： 某厂每日8小时的产量不低于1800件.为了进行质量 控制，计划聘请两种不同水平的检验员.一级检验员的标准为： 速度25件/小时，正确率98%，计时工资4元/小时；二级检验员 的标准为：速度15件/小时，正确率95%，计时工资3元/小时.检 验员每错检一次，工厂要损失2元.为使总检验费用最省，该工 厂应聘一级、二级检验员各几名？ 解 设需要一级和二级检验员的人数分别为x1、x2人, 则应付检验员的工资为： 1 2 1 2 8 4 x  8 3 x  32x  24x 因检验员错检而造成的损失为： 1 2 2 8 1 12 2 (8 25 2% x  8155% x )  x  x

故目标函数为： minz=(32x+24x2)+(8.x+12x2)=40x+36x2 约束条件为： 8×25×x,+8×15×x2≥1800 8×25×x≤1800 8×15×x2≤1800 x≥0，x2≥0

故目标函数为： 1 2 1 2 1 2 min z  (32x  24x )  (8x 12x )  40x  36x 约束条件为：                    0, 0 8 15 1800 8 25 1800 8 25 8 15 1800 1 2 2 1 1 2 x x x x x x

线性规划模型：minz=40x,+36x2 5x1+3x2≥45 ￥1≤9 S.t. x2≤15 x1≥0，x2≥0 返回 解答

线性规划模型： 1 2 min z  40x  36x 1 2 1 2 1 2 5 3 45 9 s.t. 15 0, 0 x x x x x x            解答 返 回

线性规划模型的一般形式 目标函数和所有的约束条件都是设计变量 的线性函数. minu=-∑cx 矩阵形式： min 儿=Cx di-bi-1.2 st/Ar s.t. k=1 b≤x≤ub x≥0，i=1,2,n

线性规划模型的一般形式 1 1 min , 1,2,., . s.t. 0, 1,2,., . n i i i n ik k i k i u c x a x b i n x i n               目标函数和所有的约束条件都是设计变量 的线性函数.  min .     s.t u cx Ax b vlb x vub 矩阵形式：

优化模型的分类 实际问题中 min(或max)z=f(x),x=(x,.,xn) 的优化模型 s.t.8,(x)≤0，i=1,2,.,m x是决策变量 fx)是目标函数gc)s0是约束条件 数学规划 线性规划LP) 0-1整数规划 纯整数规划(PIP) 二次规划(QP) 般整数规划 混合整数规划(MIP) 非线性规划NLP) 连续规划 整数规划(P)

实际问题中 的优化模型 T m 1 in( max) ( ), ( , , ) s.t. ( ) 0, 1, 2, , n i z f x x x x g x i m       或 x是决策变量 f(x)是目标函数 gi(x)0是约束条件 数学规划 线性规划(LP) 二次规划(QP) 非线性规划(NLP) 纯整数规划(PIP) 混合整数规划(MIP) 整数规划(IP) 0-1整数规划 一般整数规划 连续规划 优化模型的分类

用MATLAB优化工具箱解线性规划 1.模型： min z=cX s.t. AX≤b 命令：x=1 inprog（c,A,b) 2.模型：minz=cX st.AX≤b Aeq·X=beq 命令：x=1 inprog(c,A,b,Aeg,beg) 注意：若没有不等式：AX≤b存在，则令A=[],b=[]

用MATLAB优化工具箱解线性规划 min z=cX s.t. AX  b 1. 模型： 命令：x=linprog（c, A, b） 2. 模型：min z=cX s.t. AX  b Aeq  X  beq 命令：x=linprog（c，A，b，Aeq,beq） 注意：若没有不等式：AX  b 存在，则令A=[ ]，b=[ ]