数学建模与数学实验 线性规划 后勤工程学院数学教研室
线性规划 数学建模与数学实验 后勤工程学院数学教研室
实验目的 1、了解线性规划的基本内容。 2、掌握用数学软件包求解线性规划问题 实验内容 1、两个引例。 2、线性规划的基本算法。 3、用数学软件包求解线性规划问题。 4、建模案例:投资的收益与风险 5、实验作业
实验目的 实验内容 2、掌握用数学软件包求解线性规划问题。 1、了解线性规划的基本内容。 *2、线性规划的基本算法。 5、实验作业。 3、用数学软件包求解线性规划问题。 1、两个引例。 4、建模案例：投资的收益与风险
两个引例 问题一:任务分配问题:某车间有甲、乙两台机床,可用 于加工三种工件。假定这两台车床的可用台时数分别为800和 900,三种工件的数量分别为400、600和500,且已知用三种 不同车床加工单位数量不同工件所需的台时数和加工费用如 下表。问怎样分配车床的加工任务,才能既满足加工工件的 要求,又使加工费用最低? 车床单位工件所需加工台时数单位工件的加工费用可用台 类型「工件1工件2工件3工件1工件2|工件3时数 甲 0.4 1.0 10 800 0.5 1.2 1.3 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的数量分别为、x2、x, 在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立 以下线性规划模型: minz=13x1+9x2+10x3+11x4+12x5+8x6 x1+x4=400 x2+x=600 x3+x6=500 st 0.4x1+1.1x2+x2≤800 0.5x4+1.2x+1.3x≤900 x.≥0.i=1.2..6 解答
解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3， 在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立 以下线性规划模型： min 13 1 9 2 10 3 11 4 12 5 8 6 z = x + x + x + x + x + x = + + + + + = + = + = 0, 1,2, ,6 0.5 1.2 1.3 900 0.4 1.1 800 500 600 x 400 . . 4 5 6 1 2 3 3 6 2 5 1 4 x i x x x x x x x x x x x st i 解答
问题二:某厂每日8小时的产量不低于1800件。为了进行质 量控制,计划聘请两种不同水平的检验员。一级检验员的标准 为:速度25件/小时,正确率98%,计时工资4元/小时;二级检 验员的标准为:速度15小时/件,正确率95%,计时工资3元/小 时。检验员每错检一次,工厂要损失2元。为使总检验费用最 省,该工厂应聘一级、二级检验员各几名? 解设需要一级和二级检验员的人数分别为x1、x2人, 则应付检验员的工资为: 8×4×x1+8×3×x2 =32x1+24x2 因检验员错检而造成的损失为: (8×25×2%×x+8×15×5%×x2)×2=8x1+12x2
问题二： 某厂每日8小时的产量不低于1800件。为了进行质 量控制，计划聘请两种不同水平的检验员。一级检验员的标准 为：速度25件/小时，正确率98%，计时工资4元/小时；二级检 验员的标准为：速度15小时/件，正确率95%，计时工资3元/小 时。检验员每错检一次，工厂要损失2元。为使总检验费用最 省，该工厂应聘一级、二级检验员各几名？ 解 设需要一级和二级检验员的人数分别为x1、x2人, 则应付检验员的工资为： 8 4 1 8 3 2 32 1 24 2 x + x = x + x 因检验员错检而造成的损失为： 1 2 2 8 1 12 2 (8 25 2% x + 8155% x ) = x + x
故目标函数为: minz=(32x1+24x2)+(8x+12x2)=40x1+36x2 约束条件为: 8×25×x,+8×15×x≥1800 8×25×x,<1800 8×15×x<1800 x≥0,x2≥0
故目标函数为： 1 2 1 2 40 1 36 2 min z = (32x + 24x ) + (8x +12x ) = x + x 约束条件为： + 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=40x1+36x 5x.+3x>45 x,<9 x<15 XI ≥0 x≥0 解答
线性规划模型： min 40 1 36 2 z = x + x + 0, 0 15 9 5 3 45 . . 1 2 2 1 1 2 x x x x x x st 解答 返 回
线性规划的基本算法单纯形法 1.线性规划的标准形式: mn z=f(x) s.g;(x)≤0(i=1,2,,m) 其中目标函数f(x)和约束条件中g;(x)都是线性函数 2.线性规划的基本算法单纯形法 用单纯法求解时,常将标准形式化为 min S.t。Ax=b (1) 0 这里A=(an)n,x=(1x2…x) bn)
1.线性规划的标准形式： x min z = f (x) s.t. g (x) i 0 （ i = 1,2,,m) 其中目标函数 f (x) 和约束条件中 g (x) i 都是线性函数 min f = c x s.t. Ax = b （1） x 0 这里 A = (ai j )m,n , x = ( ) T 1 2 n x x x b = ( ) T b1 b2 bn , c = ( ) n c c c 1 2 用单纯法求解时，常将标准形式化为： 2. 线性规划的基本算法——单纯形法 线性规划的基本算法——单纯形法
例minz=10x1+9x2 s.t.6x1+5x2≤60 10x1+20X,≥150 X1≤8 0 引入松弛变量x3,x4,x3,将不等式化为等式,即单纯形标准形 min z=10x,+9x s.t.6X1+5X2+x3=60 10X1+20X =150 XI+xs= 8 X≥0(i=1,2,3,4,5) 系数矩阵为 65100 A=|10200-10=(P1P2P3P4P) 000 b=(60,150,8) 显然A的秩ran(A)=3,任取3个线性无关的列向量如P3P4P称为 组基,记为B.其余列向量称为非基,记为N
例 min z = 10x1 + 9x2 s．t．6x1 + 5x2 ≤ 60 10x1 + 20x2 ≥ 150 x1 ≤ 8 x1 , x2 ≥ 0 引入松弛变量x3 , x4 , x5 , 将不等式化为等式, 即单纯形标准形: min z = 10x1 + 9x2 s．t．6x1 + 5x2 + x3 = 60 10x1 + 20x2 - x4 = 150 x1 + x5 = 8 xi≥ 0 (i = 1,2,3,4,5) 系数矩阵为: 6 5 1 0 0 A = 10 20 0 -1 0 = (P1 P2 P3 P4 P5 ) 1 0 0 0 1 b = (60, 150, 8 ) T 显然A的秩ran(A)=3, 任取3个线性无关的列向量,如P3 P4 P5称为 一组基, 记为B. 其余列向量称为非基, 记为N
将A的列向量重排次序成A=(B,N),相应x=(x,x),c=(cB,cN) 基对应的变量x称为基变量,非基对应的变量x称为非基变量 于是f=cBxB+cNxN,Ax=BxB+Nxy=b AU XB=B-b-B- NXN, f=CBB- b+(CN-CBB-NXN 令非基变量x=0,解得基变量xB=Bb,称(xB,x)为基解 基解的所有变量的值都非负,则称为基可行解,此时的基称为可行基 若可行基进一步满足:c-cBB-N≥0,即:cBB-N-cN≤0 则对一切可行解x,必有(x)≥cB1b,此时称基可行解x=(Bb,0)T 为最优解 3.最优解的存在性定理 定理1如果线性规划(1)有可行解,那么一定有基可行解. 定理2如果线性规划(1)有最优解,那么一定存在一个基可行解 是最优解
于是 f = cBxB + cNxN , Ax = BxB + NxN = b, 则 xB = B-1b-B-1NxN , f = cBB-1b + (cN – cBB-1N)xN 令非基变量 xN = 0, 解得基变量 xB = B−1 b, 称(xB, xN)为基解. 基解的所有变量的值都非负，则称为基可行解，此时的基称为可行基. 若可行基进一步满足: cN – cBB-1N≥0, 即: cBB-1N - cN≤0 则对一切可行解x, 必有f(x) ≥ cBB-1b, 此时称基可行解x = (B-1b, 0) T 为最优解. 3. 最优解的存在性定理 将A的列向量重排次序成A = (B, N), 相应x = (xB, xN) T , c = (cB, cN) 基对应的变量xB称为基变量, 非基对应的变量xN称为非基变量. 定理1 如果线性规划(1)有可行解，那么一定有基可行解. 定理2 如果线性规划(1)有最优解，那么一定存在一个基可行解 是最优解