数学建模讲义 →优化模型
数学建模讲义 →优化模型
1、线性规划 2、线性整数规划 3、运输问题 4、无约束规划 5、多目标规划 6、非线性规划 7、动态规划 ■■
1、线性规划 5、多目标规划 6、非线性规划 7、动态规划 ……… 2、线性整数规划 4、无约束规划 3、运输问题
1.线性规划 线性规划建模一 引例 线性规划模型 线性规划的图解 线性规划的性质 线性规划重要算法 用MATLAB解线性规划
1. 线性规划 线性规划建模——引例 线性规划模型 线性规划的图解 线性规划的性质 线性规划重要算法 用MATLAB解线性规划
例1：一某厂每日8小时的产量不低于1800件。为了进行质 量控制，计划聘请两种不同水平的检验员。一级检验员的标准 为：速度25件/小时，正确率98%，计时工资4元/小时；二级检 验员的标准为：速度15小时/件，正确率95%，计时工资3元/小 时。检验员每错检一次，工厂要损失2元。为使总检验费用最 省，该工厂应聘一级、二级检验员各几名？ 解 设需要一级和二级检验员的人数分别为x1、X2人，则应付 检验员的工资为： 8×4×x1+8×3×X2=32x1+24x2 因检验员可能错检而造成的损失为： (8×25×2%×x1+8×15×5%×x2)×2=8x1+12x2 故目标函数为： min Z=40x +36x2 约束条件为： s.t.5x1+3x2≥45 x1≤9，x2≤15 x1≥0，X2≥0
引例1： 某厂每日8小时的产量不低于1800件。为了进行质 量控制，计划聘请两种不同水平的检验员。一级检验员的标准 为：速度25件/小时，正确率98%，计时工资4元/小时；二级检 验员的标准为：速度15小时/件，正确率95%，计时工资3元/小 时。检验员每错检一次，工厂要损失2元。为使总检验费用最 省，该工厂应聘一级、二级检验员各几名？ 解 设需要一级和二级检验员的人数分别为x1、x2人, 则应付 检验员的工资为： 84x1 + 83x2 = 32x1 + 24x2 因检验员可能错检而造成的损失为： 1 2 2 8x1 12x2 (8252%x + 8155%x ) = + 故目标函数为： 40x1 36x2 min z = + 约束条件为： x 0, x 0 x 9, x 15 s.t. 5x 3x 45 1 2 1 2 1 2 +
引例2任务分配问题： 求解 某车间有甲、乙两台机床，可用于加工三种工件。假定这两台 车床的可用台时数分别为800和00，三种工件的数量分别为 400、600和500，且已知用三种不同车床加工单位数量不同工 件所需的台时数和加工费用如下表。问怎样分配车床的加工任 务，才能既满足加工工件的要求，又使加工费用最低？ 车床 单位工件所需加工台时数 单位工件的加工费用 可用台 类型 工件1 工件2 工件3 时数 工件1 工件2 工件3 甲 0.4 1.1 1.0 800 13 9 10 0.5 1.2 1.3 900 11 12 8 设在甲车床上加工工件1、2、3的数量分别为x1,X2,X3, 在乙车床上加工工件1、2、3的数量分别为x4,X5,6
某车间有甲、乙两台机床，可用于加工三种工件。假定这两台 车床的可用台时数分别为800和900，三种工件的数量分别为 400、600和500，且已知用三种不同车床加工单位数量不同工 件所需的台时数和加工费用如下表。问怎样分配车床的加工任 务，才能既满足加工工件的要求，又使加工费用最低？ 引例2 任务分配问题： 车床 类 型 单位工件所需加工台时数 可用台 时数 单位工件的加工费用 工件1 工件2 工件3 工件1 工件2 工件3 甲 0.4 1.1 1.0 800 13 9 10 乙 0.5 1.2 1.3 900 11 12 8 设在甲车床上加工工件1、2、3的数量分别为x1 , x2 , x3 , 在乙车床上加工工件1、2、3的数量分别为x4 , x5 , x6 . 求解
引例2任务分配问题： 求解 单位工件所需加工台时数 单位工件的加工费用 车床 可用台 类型 工件1 工件2 工件3 时数 工件1 工件2 工件3 甲 0.4 1.1 1.0 800 13 9 10 乙 0.5 1.2 1.3 900 11 12 8 z=13x1+9x2+10x3+11x4+12x5+8x6→min 要 X1+X4=400 0.4x1+1.1x2+x3≤800 求 X2+X5=600 0.5x4+1.2x5+1.3x6≤900 X3+X6=500 X≥0，i=1,2,…,6
引例2 任务分配问题： 车床 类 型 单位工件所需加工台时数 可用台 时数 单位工件的加工费用 工件1 工件2 工件3 工件1 工件2 工件3 甲 0.4 1.1 1.0 800 13 9 10 乙 0.5 1.2 1.3 900 11 12 8 z = 13x1 + 9x2 +10x3 +11x4 +12x5 + 8x6 → min x3 + x6 = 500 x2 + x5 = 600 要 x1 + x4 = 400 求 0.4x1 +1.1x2 + x3 800 0.5x4 +1.2x5 +1.3x6 900 xi 0,i = 1,2, ,6 求解
解设在甲车床上加工工件1、2、3的数量分别为x1、2X, 在乙车床上加工工件1、2、3的数量分别为x4x5、X6·可建立 以下线性规划模型： minz=13x1+9x2+10x3+11x4+12x5+8x6 X1+X4=400 X2+x5=600 X3+X6=500 线性规对 0.4x1+1.1x2+x3≤800 0.5x4+1.2x5+1.3x6≤900 X1≥0，i=1,2,…,6
解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3， 在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立 以下线性规划模型： 13x1 9x2 10x3 11x4 12x5 8x6 min z = + + + + + x3 + x6 = 500 x2 + x5 = 600 x1 + x4 = 400 0.4x1 +1.1x2 + x3 800 0.5x4 +1.2x5 +1.3x6 900 xi 0,i = 1,2, ,6 线性规划
引例3下料问题： 制造某种机床，需要A,B,C 类型 规格：长度(m) 件数/台机床 三种轴件其规格如右表所示， A 3.1 1 这些轴件都用5.5m长的圆钢 下料.若计划生产100台机床， B 2.1 2 怎样下料最省？ C 1.2 分析：需要列出可行 的下料方式 截法 根圆钢所截的件数 轴承需 设采用1,2,3,4,5截 类型 2 3 4 5 要量 法的圆钢数量分别为 A 0 0 100 X1)X23X3,X4)X5. B 0 200 min =c'x C 0 2 2 4 400 s.t.Ax=b 余料 0.3 0.1 1 0.7 x≥0 结果：采用1,2,3,4,5截法的圆钢数量分别 为(0,100,100,0,25)，余料27.5m
制造某种机床，需要A, B, C 三种轴件其规格如右表所示, 这些轴件都用5.5m长的圆钢 下料. 若计划生产100台机床, 怎样下料最省? 引例3 下料问题： 类 型 规格:长度(m) 件数/台机床 A 3.1 1 B 2.1 2 C 1.2 4 设采用1, 2, 3, 4, 5截 法的圆钢数量分别为 x1 , x2 , x3 , x4 , x5 . 分析：需要列出可行 的下料方式 截法 类 型 一根圆钢所截的件数 轴承需 1 2 3 4 5 要量 A 1 1 0 0 0 100 B 1 0 2 1 0 200 C 0 2 1 2 4 400 余料 0.3 0 0.1 1 0.7 0 . . min = = x s t Ax b z c x c A b 结果：采用1, 2, 3, 4, 5截法的圆钢数量分别 为(0, 100, 100, 0, 25)，余料27.5m
线性规划模型 线性规划模型的结构 目标函数： max,min max(min)z=CTX 约束条件：≥，=，≤ s.t. AX≥(=，≤)b X≥（≤）0，或无限制 变量符号：≥0，≤0或无限制 线性规划的标准形式 目标函数：min min Z=CTX 约束条件：= s.t.AX=b 变量符号：≥0 X≥0
线性规划模型 线性规划模型的结构 目标函数 ：max，min 约束条件：≥, =, ≤ 变量符号：≥0, ≤0或无限制 线性规划的标准形式 目标函数：min 约束条件：= 变量符号：≥0 X ( )0,或无限制 s.t. AX ( , )b max(min) z C X T = = X 0 s.t. AX b min z C X T = =
线性规刘的图解 ☒ max Z=X1+3X2 x2 s.t. X1+X2≤6 最优解 -X1+2X2≤8 X1≥0，X220 可行域 -8 6 目标函数等值线
线性规划的图解 max z=x1+3x2 s.t. x1+ x2≤6 -x1+2x2≤8 x1 ≥0, x2≥0 可行域 目标函数等值线 最优解 6 4 -8 6 0 x1 x2