第3章-线性规划-1.ppt

《第3章-线性规划-1.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章线性规划数学建模与数学实验教学目的教学内容2掌握线性规划模型建立的三个基本要素3理解单纯型算法1、了解线性规划的基本内容。2、线性规划的基本算法。1、两个引例。问题一：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？两个引例问什么?——问怎样分配车床的加工任务？设什

2、么？设各车床的具体加工任务，得决策变量：设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。基本过程：决策变量——〉目标函数——〉约束条件1、确定决策变量——问什么，则设什么。2、确定目标函数——看目标是什么？使加工费用最低！加工费用3、确定约束条件——各决策变量有何限制？3、确定约束条件——各决策变量有何限制？三种工件的数量分别为400、600和500，两台车床的可用台时数分别为800和900非负性要求解设在甲车床上加工工件1、2、3的数量分

3、别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：解答三种工件的数量分别为400、600和500，两台车床的可用台时数分别为800和900线性规划的组成要素：决策变量用符号来表示可控制的因素目标函数MaxF或MinF约束条件s.t.(subjectto)满足于建模步骤1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，…，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量

4、的等式或不等式表示解决问题过程中必须遵循的约束条件问题二：某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15小时/件，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？解设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：因检验员错检而造成的损失为：故目标函数为：故目标函数为：约束条件为

5、：线性规划模型：返回目标函数：约束条件：①②③线性规划数学模型的一般形式一般有两种方法图解法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量、但需将一般形式变成标准形式线性规划问题的求解方法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法。例1.目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)图解法（1）画出线性规划问题

6、的可行域，如图所示。x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图1Maxz=50x1+100x2s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)（2）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。得到最优解：x1=50，x2=250，最优目标值z=27500x1x2z=20000=50x1+

7、100x2图2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE1、解的概念⑴可行解：满足约束条件②、③的解为可行解。所有解的集合为可行解的集或可行域。⑵最优解：使目标函数达到最大值的可行解。线性规划问题的解目标函数：约束条件：①②③⑶基：B是矩阵A中m×n阶非奇异子矩阵（∣B∣≠0），则B是一个基。则称Pj(j=12……m)为基向量。∴Xj为基变量，否则为非基变量。目标函数：约束条件：①②③⑷基本解：满足条件②，但不满足条件③的所有解，最多为个。⑸

8、基本可行解：满足非负约束条件的基本解，简称基可行解。⑹可行基：对应于基可行解的基称为可行基。非可行解可行解基解基可行解2、解的基本定理⑴线性规划问题的可行域是凸集（凸多边形）。凸集凸集不是凸集顶点⑵最优解一定是在凸集的某一顶点实现（顶点数目不超过个）⑶先找一个基本可行解，与周围顶点比较，如不是最大，继续比较，直到找出最大为止。3、解的情况唯一解无穷解无界解无可行解有最优解无最优解（一）、基本思想将模