线性规划概念及图解法.pptx

《线性规划概念及图解法.pptx》由会员分享，可在线阅读，更多相关《线性规划概念及图解法.pptx（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、解 设工厂生产x1盒当归丸与x2瓶当归膏，可建立以下数学模型：第1页/共24页目标函数为：约束条件为：决策变量为：x1,x2第2页/共24页 例2 2 某公司由于生产需要，共需要A A，B B两种原料至少350350吨（A A，B B两种材料有一定替代性），其中A A原料至少购进125125吨。但由于A A，B B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A A原料需要2 2个小时，加工每吨B B原料需要1 1小时，而公司总共有600600个加工小时。又知道每吨A A原料的价格为2 2万元，每吨B B原料的价格为3 3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如

2、何购买A A，B B两种原料，使得购进成本最低？第3页/共24页解：解：设购买A种原料为x1，B种原料为x2，可建立以下数学模型：目标函数：目标函数：Min S=2xMin S=2x1 1+3 x+3 x2 2约束条件约束条件：s.t.xs.t.x1 1+x+x2 2 350 350 x x1 1 125 125 2 x 2 x1 1+x+x2 2 600 600 x x1 1 ,x ,x2 2 0 0 s.t.是subject to的缩写。意思为“满足于，受约束于”决策变量为：x1,x2第4页/共24页数学规划模型数学规划模型 实际问题中的优化模型x决策变量f(x)目标函数gi(x)0约束条

3、件数学规划线性规划非线性规划整数规划第5页/共24页线性规划问题（LP）：一组线性不等式约束下求线性目标函数的极大值或极小值问题。决策变量的一组取值便构成了线性规划问题的一个决策变量的一组取值便构成了线性规划问题的一个解解；满足约束条件的解称为满足约束条件的解称为可行解可行解；所有可行解构成的集合称为所有可行解构成的集合称为可行解集可行解集；使目标函数达到所追求极值的可行解称为使目标函数达到所追求极值的可行解称为最优解最优解；最优解所对应的目标函数值称为最优解所对应的目标函数值称为最优值最优值。相关定义：第6页/共24页二、线性规划的表现形式二、线性规划的表现形式一般形式：目标函数和所有的约束

4、条件都是设计变量的线性函数.目标函数：Max(Min）z=c1 x1+c2 x2+cn xn 约束条件：s.t.a11 x1+a12 x2+a1n xn （=,）b1 a21 x1+a22 x2+a2n xn （=,）b2 am1 x1+am2 x2+amn xn （=,）bm x1，x2，xn 0 第7页/共24页基本线性规划形式目标函数：Max（Min)S =c1 x1+c2 x2+cn xn 约束条件：s.t.a11 x1+a12 x2+a1n xn b1 a21 x1+a22 x2+a2n xn b2 am1 x1+am2 x2+amn xn bm x1，x2，xn 0，bi 0第8页

5、/共24页建模过程1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件第9页/共24页三、线性规划问题的数学模型生产安排原料搭配问题条件下料问题物资运输问题第10页/共24页 某家具厂需要长某家具厂需要长80cm80cm的角钢与长的角钢与长60cm60cm的角钢，它们皆从长的角钢，它们皆从长210cm210cm的的角钢截得。现在对长角钢截得。现在对长80cm80cm角钢的需要量为角钢的需要量为150150根，对

6、长根，对长60cm60cm角钢的需角钢的需要量为要量为330330根。问工厂应如何下料，才能使得用料最省？写出数学模型。根。问工厂应如何下料，才能使得用料最省？写出数学模型。条件下料问题1第11页/共24页 分析：共有三种下料方式，共有三种下料方式，第一种第一种是将是将1 1根根长长210210的角钢截得的角钢截得2 2根长根长80cm80cm的角钢；的角钢；第二第二种是将种是将1 1根长根长210210的角钢截得的角钢截得1 1根长根长80cm80cm和和2 2根根60cm60cm的角钢；的角钢；第三种第三种是将是将210cm210cm的角钢的角钢截得截得3 3根长根长60cm60cm的角钢

7、。现这三种下料方的角钢。现这三种下料方式应该混合使用。式应该混合使用。第12页/共24页 解：设设第一种第一种下料方式用掉下料方式用掉x x1 1根角钢；根角钢；第二种第二种下料方式用掉下料方式用掉x x2 2根角钢；根角钢；第三种第三种下料方式用掉下料方式用掉x x3 3根角钢；变量根角钢；变量x x1 1 x x2 2 x x3 3即为决策变量。即为决策变量。第13页/共24页数学模型为：数学模型为：第14页/共24页 某车间有一批长度为某车间有一批长度为7.4m7.4m的同型钢管，因生产需要，需将其截成长的同型钢管，因生产需要，需将其截成长2.9m2.9m、2.1m2.1m、1.5m1.

8、5m三种不同长度的管料。若三种管料各需三种不同长度的管料。若三种管料各需100100根，问根，问应如何下料，才能使得用料最省？写出数学模型。应如何下料，才能使得用料最省？写出数学模型。条件下料问题2第15页/共24页 分析：第16页/共24页 解：设设第一种第一种下料方式用掉下料方式用掉x x1 1根管料；根管料；第二种第二种下料方式用掉下料方式用掉x x2 2根管料；根管料；第三种第三种下料方式用掉下料方式用掉x x3 3根管料；根管料；第四种第四种下料方式用掉下料方式用掉x x4 4根管根管料；料；第五种第五种下料方式用掉下料方式用掉x x5 5根管料；变量根管料；变量x x1 1 x x

9、2 2 x x3 3 x x4 4 x x5 5即为决策变量。即为决策变量。第17页/共24页数学模型为：数学模型为：第18页/共24页例1.目标函数：Max S=50 x1+100 x2 约束条件：s.t.x1+x2 300 2 x1+x2 400 x 2 250 x1 0 x2 0四图四图 解解 法法 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。第19页/共24页四图四图 解解 法法 (1)(1)分别取决策变量X X1 1,X,X2 2 为坐标向量建立直角坐标系。取各约束条件的公共部分x1x2x2=0 x1=0 x2=250 x1+x2

10、=3002x1+x2=400图2-1第20页/共24页（2）目标函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE第21页/共24页重要结论1：当线性规划问题的可行域非空时，它是有界或无界的凸多边形（凸集）;如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；无穷多个最优解。若将例1中的目标函数变为max z=50 x1+50 x2，则线段BC上的所有点都代表了最优解；第22页/共24页重要结论2：无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x21200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。第23页/共24页感谢您的观看！第24页/共24页