《[数学]学习课件－线性规划》

《《[数学]学习课件－线性规划》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章线性规划线性规划的建模线性规划的模型线性规划的图解法线性规划的标准化线性规划的基本概念线性规划的求解1线性规划Linearprogramming21、线性规划的建模一例（例1）例1：在工厂计划期内要安排生产A、B两种产品，已知生产单位产品所需的设备台时及a、b两种原材料的消耗如下表。又该工厂每生产一件A产品可获利2元，每生产一件B产品可获例3元。问：如何安排计划使该工厂获利最大？产品A产品B资源总数设备128台时原材料a4016KG原材料b0412KG单位利润233解设A、B两种的产量分别为（决策变量），该问题的数学模型为：目标函数约束函数（Su

2、bjectTo：s.t.）产品A产品B资源总数设备128台时原材料a4016KG原材料b0412KG单位利润2342、线性规划模型5线性规划模型解析式标准形式6模型形式简记7线性规划模型矩阵标准形式线性规划模型的结构目标函数：max，min约束条件：≥,=,≤变量符号：：≥0,unr,≤0线性规划的标准形式目标函数：max约束条件：=变量符号：≥08线性规划模型练习1三种产品要经过三种不同的工序加工。各种产品每一件所需时间（分钟），每天各道工序的加工能力（每天多少分钟）和销售每一种产品的单位利润如下。试建立使总利润达到最大的线性规划模型。工序每件时间（

3、分钟）第1种产品第2种产品第3种产品工序加工能力（分钟/天）123121312141430460420利润/件（元）3259线性规划模型练习2某厂为进行生产需采购A、B两种原材料，单价分别为70元/公斤和50元/公斤。现要求购买资金不超过5000元，总购买量不少于80公斤，而A原材料不少于20公斤。问如何确定最好的采购方案（即花掉的资金最少并且购买的总量最大）？103、线性规划的图解解决只有两个决策变量的线性规划问题方法：在直角坐标系中画出所有约束方程的图象，从而得到可行域（满足所有约束方程的解的集合）；然后画出经过原点的目标函数图象的平行线——目标函

4、数等值线；寻找经过可行域的使Z达到最大的目标函数等值线，该直线与可行域的交集即为最优解集。11图解法例1maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥064-860x1x2目标函数等值线最优解可行域12图解法例2maxz=2x1+3x2s.t.x1+2x2≤84x1≤164x2≤12x1≥0,x2≥0x204843x1最优解（4，2）目标函数等值线可行域013四种可能的解的情况唯一最优解无穷多最优解无界解（无穷可行解，但无最优解）无解（无可行解）14唯一最优解maxz=2x1+3x2s.t.x1+2x2≤84x1≤164

5、x2≤12x1≥0,x2≥004843x1x2最优解（4，2）目标函数等值线可行域15线性规划的图解无穷多最优解在例2中，maxz=2x1+3x2s.t.x1+2x2≤84x1≤164x2≤12x1≥0,x2≥0目标函数改为：maxz=2x1+4x204843x1最优解（4，2）目标函数等值线可行域目标函数等值线与第一条约束直线平行，可以移至重合，与可行域交集为一线段。16无界解目标函数等值线17无解184、模型的标准化一般形式：标准形式：19模型的标准化20模型的标准化例题将标准化21例题答案标准化形式原型22模型的标准化练习将下列模型标准化23练习

6、答案原型标准化形式245、线性规划的基本概念25几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基解可行域的极点基可行解目标函数等值线：一组平行线目标函数值等于一个常数的解26可行解与最优解可行解：满足约束条件的解，记为XX=（x1，x2，…，xn）T最优解：使目标函数值达到最优的可行解。27基矩阵约束方程系数矩阵A的m×m子矩阵B，若B的行列式≠0，则称B为A的一个基（矩阵）。==目标函数约束条件行列式≠0基矩阵右边常数28基变量、基向量基B对应的m个变量为基变

7、量，其他n-m个变量为非基变量。假定29基阵非基阵基向量非基向量基变量非基变量30基解、基可行解基解：令所有非基变量为0，根据约束方程求得的解（不包括非负约束）为对应基的基解。表示为X=（x1，x2，…，xm，0，…，0）T基可行解：满足非负约束的基解。基的个数最多为，故基解的个数最多为。31总结几个概念基矩阵、非基矩阵基变量、非基变量基向量、非基向量基解、可行解、基可行解、最优解32几种解的关系33可行域的性质线性规划的可行域是凸集线性规划的最优解在极点上凸集凸集不是凸集极点34基解例135基变量x1、x2、x3，非基变量x4、x5、x6基解为（x1

8、，x2，x3，x4，x5，x6）T=（5，3，1，0，0，0）T是基可行解，表示可行域的一个极