第4讲 线性规划.ppt

文档介绍：线性规划
数学建模与数学实验
汤绍春
实验目的
实验内容
2、掌握用数学软件包求解线性规划问题。
1、了解线性规划的基本内容。
*2、线性规划的基本算法。
5、实验作业。
3、用数学软件包求解线性规划问题。
1、两个引例。
4、建模案例:投资的收益与风险
问题一: 任务分配问题:某车间有甲、乙两台机床,可用于加工三种工件。假定这两台车床的可用台时数分别为800和900,三种工件的数量分别为400、600和500,且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务,才能既满足加工工件的要求,又使加工费用最低?
两个引例
解设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3,在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型:
解答
问题二: 某厂每日8小时的产量不低于1800件。为了进行质量控制,计划聘请两种不同水平的检验员。一级检验员的标准为:速度25件/小时,正确率98%,计时工资4元/小时;二级检验员的标准为:速度15小时/件,正确率95%,计时工资3元/小时。检验员每错检一次,工厂要损失2元。为使总检验费用最省,该工厂应聘一级、二级检验员各几名?
解设需要一级和二级检验员的人数分别为x1、x2人,
则应付检验员的工资为:
因检验员错检而造成的损失为:
故目标函数为:
约束条件为:
线性规划模型:
解答
返回
:
用单纯法求解时,常将标准形式化为:
2. 线性规划的基本算法——单纯形法
线性规划的基本算法——单纯形法
引入松弛变量x3, x4, x5, 将不等式化为等式, 即单纯形标准形:
显然A的秩ran(A)=3, 任取3个线性无关的列向量,如P3 P4 P5称为
一组基, 记为B. 其余列向量称为非基, 记为N .
于是 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)有最优解,那么一定存在一个基可行解
是最优解.