高等教育出版社：《数学建模与数学实验》课程教学资源（第3版）第4讲 线性规划

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

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

实验目的 1.了解线性规划的基本内容 2.掌握用数学软件包求解线性规划问题. 实验内容 1.两个引例 2.用数学软件包 MATLAB求解线性规划问题 3.用数学软件包LⅠNDO、 LINGO求解线性规划问题 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 91080 乙 0.5 1.2 1.3 11 12 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的数量分别为x、x2、x3, 在乙车床上加工工件1、2、3的数量分别为x4、x5、x6,可建立以 下线性规划模型: minz=13x1+9x2+10x3+11x4+12x5+8x6 X1+x=400 x,+x=600 x2+x=500 St 0.4x1+1.lx2+x3≤800 0.5x4+1.2x、+1.3x≤900 x1≥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×x1+8×3×x2=32x1+24x 因检验员错检而造成的损失为 (8×25×2%×x1+8×15×5%×x2)×2=8x1+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=(32x1+24x2)+(8x1+12x2)=40x1+36x2 约束条件为: 8×25×x,+8×15×x≥1800 8×25×x,<1800 8×15×x<1800 x,≥0.x≥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,+36x 2 5x,+3x2≥45 x,<9 S t x<15 ≥0.x12≥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 u=cr x=b,=12…,n,st Ax<h S t u)k=1 ≤x≤mhb x20.i=12…,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=(x1 的优化模型 st.8(x)≤0,i=1,2,…,m x是决策变量f(x)是目标函数gx)≤0是约束条件 数学规划 线性规划(LP)0-1整数规划纯整数规划PIP) 二次规划(QP) 般整数规划混合整数规划(MIP) 非线性规划(NLP) 连续规划 整数规划(IP

实际问题中 的优化模型 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.模型:minz=cX s.t.AX<b 命令:x=1 Inprog(c,a,b) 2.模型:minz=cX St.AX<b Aeg. X= beq 命令:x=1 Inprog(c,A,b,Aeq,beq 注意:若没有不等式: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=[ ]