第4讲matlab线性规划研讨.ppt

线性规划数学建模与数学实验实验目的实验内容 2、掌握用数学软件包求解线性规划问题。 1、了解线性规划的基本内容。*2、线性规划的基本算法。 5、实验作业。 3、用数学软件包求解线性规划问题。 1、两个引例。 4、建模案例:投资的收益与风险问题一: 任务分配问题:某车间有甲、乙两台机床,可用于加工三种工件。假定这两台车床的可用台时数分别为 800 和 900 ,三种工件的数量分别为 400 、600 和500 ,且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务,才能既满足加工工件的要求,又使加工费用最低? 单位工件所需加工台时数单位工件的加工费用车床类型工件1 工件2 工件3 工件1 工件2 工件3 可用台时数甲 13 9 10 800 乙 11 12 8 900两个引例解设在甲车床上加工工件 1、2、3的数量分别为 x 1、x 2、x 3, 在乙车床上加工工件 1、2、3的数量分别为 x 4、x 5、x 6。可建立以下线性规划模型: 654321812 11 10 913 minxxxxxxz???????????????????????????????6,,2,1,0 900 800 500 600 400 x.. 654 321 63 52 41? ix xxx xxx xx xx xts i解答问题二: 某厂每日 8小时的产量不低于 1800 件。为了进行质量控制,计划聘请两种不同水平的检验员。一级检验员的标准为:速度 25件/小时,正确率 98% ,计时工资 4元/小时;二级检验员的标准为:速度 15小时/件,正确率 95% ,计时工资 3元/小时。检验员每错检一次,工厂要损失 2元。为使总检验费用最省,该工厂应聘一级、二级检验员各几名? 解设需要一级和二级检验员的人数分别为 x 1、x 2人, 则应付检验员的工资为: 212 1 24 32 3848xxxx???????因检验员错检而造成的损失为: 21 2 1 12 82)%5 15 8%2 25 8(xxxx??????????故目标函数为: 212121 36 40 ) 12 8() 24 32 ( minxxxxxxz??????约束条件为: ?????????????????????0,0 1800 15 8 1800 25 8 1800 15 825 8 21 2 1 2 1xx x x xx 线性规划模型: 2 1 36 40 minxxz???????????????0,0 15 9 45 35.. 21 2 1 21xx x x xxts解答返回 : x min z =)(xf..ts )(xg i? 0 (),,2,1mi??其中目标函数)(xf 和约束条件中)(xg i 都是线性函数 min f = cx . Ax = b (1)x ? 0 这里A = ( ija ) m,n , x = ?? T21nxxx? b = ?? T21nbbb?, c = ??? 21用单纯法求解时,常将标准形式化为: 2. 线性规划的基本算法——单纯形法线性规划的基本算法——单纯形法例 min z = 10x 1 + 9x 2 1 + 5x 2≤ 60 10x 1 + 20x 2≥ 150 x 1≤ 8 x 1, x 2≥ 0引入松弛变量 x 3, x 4, x 5, 将不等式化为等式, 即单纯形标准形: min z = 10x 1 + 9x 2 1 + 5x 2 + x 3 = 60 10x 1 + 20x 2 - x 4 = 150 x 1 + x 5 = 8 x i≥ 0 (i = 1,2,3,4,5) 系数矩阵为: 6 5 1 0 0 A = 10 20 0 -1 0 = (P 1 P 2 P 3 P 4 P 5) 1 0 0 0 1 b = (60, 150, 8 ) T显然 A的秩 ran(A)=3, 任取 3个线性无关的列向量,如P 3 P 4 P 5称为一组基,记为 B. 其余列向量称为非基, 记为 N . 于是 f = c Bx B + c Nx N , Ax = Bx B +