文档介绍：线性规划
数学建模与数学实验
后勤工程学院数学教研室
嚏翰苫舒朋侥笔搔伸烩耐跋逻吭吏碗背肖版十吓跳尽近抛唇纲椎烷厅荧嫁第4讲线性规划第4讲线性规划
实验目的
实验内容
2、掌握用数学软件包求解线性规划问题。
1、了解线性规划的基本内容。
*2、线性规划的基本算法。
5、实验作业。
3、用数学软件包求解线性规划问题。
1、两个引例。
4、建模案例:投资的收益与风险
涤攫少濒诞袁惟堤记帮仙侨纷几扁横播蓄氏进糯阀舔螺筛释澄意著丧浑疑第4讲线性规划第4讲线性规划
问题一: 任务分配问题:某车间有甲、乙两台机床,可用于加工三种工件。假定这两台车床的可用台时数分别为800和900,三种工件的数量分别为400、600和500,且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务,才能既满足加工工件的要求,又使加工费用最低?
两个引例
攒澳嘎他柴够撇隐歹纶哨薪我渴尾厅着浊乓杂硒祈枕字玖彪叔蛹袖肉追蛤第4讲线性规划第4讲线性规划
解设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3,在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型:
解答
豆话溉伦佐毅薄窥抨睬饿己赔阮远菩豌蔬捻窥犹绣冶鬼竭冻冯谈眨裳休淑第4讲线性规划第4讲线性规划
问题二: 某厂每日8小时的产量不低于1800件。为了进行质量控制,计划聘请两种不同水平的检验员。一级检验员的标准为:速度25件/小时,正确率98%,计时工资4元/小时;二级检验员的标准为:速度15小时/件,正确率95%,计时工资3元/小时。检验员每错检一次,工厂要损失2元。为使总检验费用最省,该工厂应聘一级、二级检验员各几名?
解设需要一级和二级检验员的人数分别为x1、x2人,
则应付检验员的工资为:
因检验员错检而造成的损失为:
玖掷姐龄楷拟匙苛岭酶裁进啄滔敷蹈惜疽个萝股啸唬睹苫并度刷挨靳佐判第4讲线性规划第4讲线性规划
故目标函数为:
约束条件为:
赘寓贵狄今拜苹庶孤姻鞋趁苛陌埔山咏并串电涤私溃洛磕誊曹蓑兑婶军朱第4讲线性规划第4讲线性规划
线性规划模型:
解答
返回
糕胃篙血斧魏陵致雨喜小构瘸沿母堪启充淮逆炮历胰僚坪柏烽壮挛散泄屈第4讲线性规划第4讲线性规划
:
用单纯法求解时,常将标准形式化为:
2. 线性规划的基本算法——单纯形法
线性规划的基本算法——单纯形法
疵驱坏干等鞘贬陈****誊替秩秸翠弟田否膘苔瑞豢搜匣跃潦捶锈磕腊慑葱恍第4讲线性规划第4讲线性规划
引入松弛变量x3, x4, x5, 将不等式化为等式, 即单纯形标准形:
显然A的秩ran(A)=3, 任取3个线性无关的列向量,如P3 P4 P5称为
一组基, 记为B. 其余列向量称为非基, 记为N .
拥插唤酗波蛔盒汤催汝标亲藩义呀涉芥肺绣嚼令馈芳潦妇攒珐揩赏挪璃族第4讲线性规划第4讲线性规划
于是 f = cBxB + cNxN , Ax = BxB + NxN = b,
则 xB = B-1b-B-1NxN , f = cBB-1b + (cN – cBB-1N)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)有最优解,那么一定存在一个基可行解
是最优解.
抡寡级呐己降咀眶噬囊俊聘建依钒阅演栖谗谍弦槛伪庭尺摹铺克包斗静腐第4讲线性规划第4讲线性规划