一章线规划与单纯形法.ppt
《一章线规划与单纯形法.ppt》由会员分享,可在线阅读,更多相关《一章线规划与单纯形法.ppt(61页珍藏版)》请在三一文库上搜索。
1、第一章 线性规划与单纯形法,第一节 线性规划的基本概念 第二节 线性规划的标准形式和解的性质 第三节 单纯形法 第四节 人工变量法 第五节 线性规划应用举例,本章学习目的和要求,通过本章的学习,要求学生掌握线性规划的图解法,深刻理解单纯形法的解题思路,熟练掌握其运算步骤,并能在实际问题中加以运用。,主要研究目的,1已有一定数量的人力、物力、财力资源,研究如何充分合理地使用才能使完成的任务量最大。(如:利润、产值等最大。 maximum) 2当一项任务量确定以后,研究如何统筹安排,才能使完成任务耗费的资源量为最小。(如:成本最小。minimum),第一节 线性规划的基本概念,一、线性规划的数学模
2、型 【例1-1】 某厂生产P、Q两种产品,主要消耗A、B、C三种原料,已知单位产品的原料消耗数量等资料如表1-1所示。,表11,要求确定P、Q的产量,使产值最大。,解:设P、Q的产量分别为x1,x2,则问题的模型为,【例1-2】 某公司打算利用甲、乙、丙3种原料配置一种新型保健饮料,已知每千克原料中两种主要保健成分A,B的含量及原料单价如表1-2所示。,产品质量标准规定每千克饮料中,营养成分A,B的含量不低于10个与8个单位。如何制定饮料配方,既满足质量标准又使成本最低?,解:设每千克饮料中原料甲,乙,丙的投入量分为x1,x2,x3千克,则问题的模型为:,【例1-3】 A1,A2是两个粮库,每
3、月分别可调出粮食30吨与40吨,三个粮店B1,B2,B3每月的需求量分别为20吨,25吨与18吨。粮库与粮店之间每吨粮食的运费如下表1-3所示(单位:元/吨)。,粮店,运费,粮库,要求安排粮食调运方案,在满足需求的前提下,使总运费最低。,解:设从粮库Ai到粮店Bj的调运量为xij,i=1,2,j=1,2,3,则问题的模型为:,上述三个问题属于同一类型的决策优化问题,它们具有下列共同特点: (1)每个行动方案可用一组变量(x1,xn)的值表示,这些变量一般取非负值; (2)变量的变化要受某些限制,这些限制条件用一些线性等式或不等式表示; (3)有一个需要优化的目标,它也是变量的线性函数。 具备以
4、上三个特点的数学模型称为线性规划(Linear Programming,简记为LP)。,实际问题中线性的含义,一是严格的比例性,如生产某产品对资源的消耗量和可获取的利润,同其生产数量严格成比例。 二是可叠加性,如生产多种产品时对某项资源的消耗量应等于各产品对该项资源的消耗量之和。,线性规划的一般形式为:,变量x1,x2,xn称为决策变量,目标函数中变量系数cj,称为价值系数,bi称为右端常数,约束条件(1-3)称为非负约束,(1-2)称为技术约束,系数aij称为技术系数。满足全部约束条件的变量值(x1,xn)称为可行解,可行解的集合称为可行域,记为R;使目标函数取得最大(最小)值的可行解(x1
5、,xn)称为最优解。,(1-3),(1-2),(1-1),采用求和符号,线性规划的一般形式可以简写为:,用向量形式可表示为:,用矩阵和向量形式表示为:,式中:X=(x1,x2,xn)T C=(c1,c2,cn) b=(b1,b2,bm)T A=(aij)mn Pj=(a1j,a2j,amj)T,二、图解法,当决策变量个数n=2时,LP问题可以通过在平面上作图的方法求解,称为图解法。 图解法求解的目的: 1.判别线性规划问题的求解结局。 2.在存在最优解的条件下,把问题的最优解找出来。,【例1-4】 求下列问题的最优解。,(1)确定问题的可行域R。,可行域R是凸多角形OQ1Q2Q3Q4,(2)分
6、析目标函数Z的等值线平行移动与Z值的关系,确定最优解的位置。,当z取定值时,方程z=2x1+5x2或x2=2/5x1+z/5表示一条斜率为2/5的直线 l , 称为z的等值线,它在x2轴上的截距为z/5。当l向右上方平行移动且保持与R有共同部分时,z值不断上升,由于l的斜率为2/5,因此当l向右上方平移的过程中,与R最后的公共点是Q3,z在Q3达到最大值。,(3)计算最优解。,点Q3是直线l1与l3的交点,它的坐标由方程组,决定,从中解得x1=2,x2=3。这就是问题的最优解,相应的目标函数值z=2253=19。最优产量计划是P,Q分别生产2个与3个单位,最大产值为19万元。这时原料A与C用完
7、,B剩余4吨。,线性规划问题求解的几种可能结局:,1.唯一最优解:如上例。 2.无穷多最优解:如Z换成maxZ=2X1+4X2,,此时最优解在线段Q2Q3 上达到,有无穷多最优解。 已求得Q3的坐标为(2,3);Q2坐标由方程组,决定,从中解得x1=3,x2=5/2。 设 , ,线段Q2Q3上的点可用 X1+(1)X2(01)表示。因此,X1+(1)X2(01)是问题的全部最优解。,3.无界解,如约束条件只保留第3个,即4X212,这时可行域无界,Z值可无限上升,无最优解,简称无界解,即有可行解,但目标函数值无解。 产生原因:是由于在建立实际问题的数学模型中遗漏了某些必要的资源约束条件。,4.
8、无解或无可行解,O,x2,D,A,2,4,x1,B,C,l1,l2,l,可行域是空集,问题无可行解,当然更无最优解。 注意:考试中如出现3、4两种情况,一定自己搞错了,必须重新解。,图解法得到的启示,1.求解线性规划问题时,解的情况有:唯一最优解、无穷多最优解、无界解和无可行解。 2.若线性规划问题的可行域存在,则可行域是一凸集。 3.若线性规划问题的最优解存在,则最优解一定在某个顶点可达到。 4.解题思路是:先找出凸集的任一顶点,计算Z值,比较相邻顶点Z值,如大,转到相邻顶点,一直到找出使Z值最大的顶点为止。,第二节 线性规划的标准形式和解的性质,一、 LP的标准形式,称为线性规划问题的标准
9、形式(其中右端常数b1,b2,bm0)。,线性规划标准形式的特点: 1. 技术约束条件全部是等式约束 2. 目标函数限定求最大值,变换一般LP为标准形式的方法: (1)如果原问题目标函数求极小值:,令z1=z,转化为求 。 (2)若某个右端常数bi0,则以1乘该约束两端。 (3)若某约束为“”型的不等式约束,则在左端加上一个非负变量,称为松弛变量,使不等式化为等式;若某约束为“”型,则在左端减去一个非负变量,称为剩余变量,或者仍然称为松弛变量,使不等式转化为等式。(目标函数不变) (4)若某个xj的符号约束为xj0;那么令xj=xj,则xj0;若某个xj无符号限制,令xj=xjxj,其中xj0
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线规 单纯
链接地址:https://www.31doc.com/p-3247734.html