第一章线性规划及单纯形法LP的数学模型图解法单纯形法单纯形法的进一步讨论-人工变量法LP模型的应用主要内容:线性规划问题的数学模型1.规划问题生产和经营管理中经常提出如何合理安排,使人力、物力等各种资源得到充分利用,获得最大的效益,这就是规划问题。线性规划通常解决下列两类问题:(1)当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源(如资金、设备、原标材料、人工、时间等)去完成确定的任务或目标(2)在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品量最多、利润最大.)线性规划问题的数学模型例1.1如图所示,如何截取x使铁皮所围成的容积最大?xaxxav220dxdv0)2()2()2(22xaxxa6ax线性规划问题的数学模型例1.2某厂生产两种产品,下表给出了单位产品所需资源及单位产品利润项目ⅠⅡ每天可用能力设备A(h)0515设备B(h)6224调试工序(h)115利润(元)21问:应如何安排生产计划,才能使总利润最大?解:1.决策变量:设产品I、II的产量分别为x1、x22.目标函数:设总利润为z,则有:maxz=2x1+x23.约束条件:5x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0线性规划问题的数学模型例1.3已知资料如下表所示,问如何安排生产才能使利润最大?或如何考虑利润大,产品好销。设备产品ABCD利润(元)Ⅰ21402Ⅱ22043有效台时1281612解:1.决策变量:设产品I、II的产量分别为x1、x22.目标函数:设总利润为z,则有:maxz=2x1+x23.约束条件:x1≥0,x2≥02x1+2x2≤12x1+2x2≤84x1≤164x2≤12线性规划问题的数学模型例1.4某厂生产三种药物,这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量解:要求:生产A种药物至少160单位;B种药物恰好200单位,C种药物不超过180单位,且使原料总成本最小。1.决策变量:设四种原料的使用量分别为:x1、x2、x3、x42.目标函数:设总成本为zminz=5x1+6x2+7x3+8x43.约束条件:x1+2x2+x3+x4≥1602x1+4x3+2x4=2003x1+x2+x3+2x4≤180x1、x2、x3、x4≥0例1.5某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示:航线号船队类型编队形式货运成本(千元/队)货运量(千吨)拖轮A型驳船B型驳船1112—362521—4362023224724041—42720船只种类船只数拖轮30A型驳船34B型驳船52航线号合同货运量12002400问:应如何编队,才能既完成合同任务,又使总货运成本为最小?线性规划问题的数学模型解:设:xj为第j号类型船队的队数(j=1,2,3,4),z为总货运成本则:minz=36x1+36x2+72x3+27x4x1+x2+2x3+x4≤302x1+2x3≤344x2+4x3+4x4≤5225x1+20x2=20040x3+20x4=400xj≥0(j=1,2,3,4)线性规划问题的数学模型线性规划问题的数学模型2.线性规划的数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints其特征是:(1)问题的目标函数是多个决策变量的线性函数,通常是求最大值或最小值;(2)问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型?线性规划问题的数学模型3.建模条件(1)优化条件:问题所要达到的目标能用线型函数描述,且能够用极值(max或min)来表示;(2)限定条件:达到目标受到一定的限制,且这些限制能够用决策变量的线性等式或线性不等式表示;(3)选择条件:有多种可选择的方案供决策者选择,以便找出最优方案。线性规划问题的数学模型4.建模步骤(1)确定决策变量:即需要我们作出决策或选择的量。一般情况下,题目问什么就设什么为决策变量;(2)找出所有限定条件:即决策变量受到的所有的约束;(3)写出目标函数:即问题所要达到的目标,并明确是max还是min。线性规划问题的数学模型00)()((min)max12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz目标函数:约束条件:5.线性规划数学模型的一般形式)21(j0)21(i)(Z(min)max11nxmbxaxcjnjijijnjjj简写为:线性规划问题的数学模型矩阵形式:mnmnaaaaA11110)((min)maxXBAXCXZ其中:)(21ncccCnxxX1mbbB1线性规划问题的数学模型向量形式:)(21ncccCnxxX1mjjjaaP1mbbB11max(min)()0njjjzCXpxBX其中:线性规划问题的数学模型6.线性规划问题的标准形式minjxbxatsxcZjnjijijnjjj,,2,1,,2,1,0.max11特点:(1)目标函数求最大值(有时求最小值)(2)约束条件都为等式方程,且右端常数项bi都大于或等于零(3)决策变量xj为非负。线性规划问题的数学模型(2)如何化标准形式目标函数的转换如果是求极小值即,则可将目标函数乘以(-1),可化为求极大值问题。jjxczmin也就是:令,可得到上式。zzjjxczzmax即若存在取值无约束的变量,可令其中:jxjjjxxx0,jjxx变量的变换线性规划问题的数学模型约束方程的转换:由不等式转换为等式。ijijbxa0iniinjijxbxxa称为松弛变量ijijbxa0iniinjijxbxxa称为剩余变量常量bi<0的变换:约束方程两边乘以(-1)线性规划问题的数学模型例1.6将下列线性规划问题化为标准形式,0,523247532min321321321321321无约束xxxxxxxxxxxxxxxZ用替换,且解:(1)因为x3无符号要求,即x3取正值也可取负值,标准型中要求变量非负,所以33xx3x0,33xx线性规划问题的数学模型(2)第一个约束条件是“≤”号,在“≤”左端加入松驰变量x4,x4≥0,化为等式;(3)第二个约束条件是“≥”号,在“≥”左端减去剩余变量x5,x5≥0;(4)第3个约束方程右端常数项为-5,方程两边同乘以(-1),将右端常数项化为正数;(5)目标函数是最小值,为了化为求最大值,令z′=-z,得到maxz′=-z,即当z达到最小值时z′达到最大值,反之亦然;线性规划问题的数学模型12334512334123351233123345max23()005()7()232()5,,,,,0Zxxxxxxxxxxxxxxxxxxxxxxxxxx标准形式如下:例1.7将下列线性规划问题化为标准形式,0,523247532min321321321321321xxxxxxxxxxxxxxxZ为无约束(无非负限制)线性规划问题的数学模型解:用替换,且,54xx3x0,54xx将第3个约束方程两边乘以(-1)将极小值问题反号,变为求极大值标准形式如下:12456712456124571245124567max23()005()7()232()5,,,,,0Zxxxxxxxxxxxxxxxxxxxxxxxxxx76,xx引入变量线性规划问题的数学模型无约束2121212,0435832xxxxxxx-xminZ10x,x,x,x,xx)x(xxx)x(xx)x(xxZaxm1111654364354343435832例1.8将线性规划问题化为标准型解:线性规划问题的数学模型例1.9将线性规划问题化为标准型解:Minf=-3x1+5x2+8x3-7x4s.t.2x1-3x2+5x3+6x4≤284x1+2x2+3x3-9x4≥396x2+2x3+3x4≤-58x1,x3,x4≥0;x2无约束Maxz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7=58x1,x2’,x2”,x3,x4,x5,x6,x7≥0线性规划问题的数学模型线性规划问题的数学模型7.线性规划问题的解)3(,,2,1,0)2(),,2,1(.)1(max11njxmibxatsxcZjnjijijnjjj线性规划问题求解线性规划问题,就是从满足约束条件(2)、(3)的方程组中找出一个解,使目标函数(1)达到最大值。线性规划问题的数学模型可行解:满足约束条件②、③的解为可行解。所有可行解的集合为可行域。最优解:使目标函数达到最大值的可行解。基:设A为约束条件②的m×n阶系数矩阵(mn),其秩为m,B是矩阵A中m阶满秩子矩阵(∣B∣≠0),称B是规划问题的一个基。设:)(11111mmmmmppaaaaB称B中每个列向量Pj(j=12……m)为基向量。与基向量Pj对应的变量xj为基变量。除基变量以外的变量为非基变量。线性规划问题的数学模型基解:某一确定的基B,令非基变量等于零,由约束条件方程②解出基变量,称这组解为基解。在基解中变量取非0值的个数不大于方程数m,基解的总数不超过基可行解:满足变量非负约束条件的基本解,简称基可行解。可行基:对应于基可行解的基称为可行基。mnC非可行解可行解基解基可行解标准LPmax..,0TzcxstAxbx(),,0ijmnAaDxAxbx系数矩阵行满秩可行域(,),BNxABNxx设相应Axb分块BNBxNxb左乘B-111BNxBNxBb11BNxBbBNx即令xN=010BNxBbxx线性规划问题的数学模型约束矩阵A的一个m阶满秩子方阵B称为一个基矩阵,xB称为基变量,xN称为非基变量;称为基矩阵B对应的基本解,的基本解称为线性规划的基本可行解,相应的基矩阵B称为可行基。的基本可行解称为是非退化的,所有基本可行解都非退化,则称线性规划问题是非退化的。说明.基本解或基本可行解中至少有n-m个零分量。10BNxBbxx10Bb10Bb线性规划问题的数学模型线性规划问题的数学模型例1.10求线性规划问题的所有基矩阵。5,,1,0226103524max53214321321jxxxxxxxxxxxxZj解:约束方程的系数矩阵为2×5矩阵10261001115Ar(A)=2,2阶子矩阵有10个,其中基矩阵只有9个,即100116010211120101015061111005261161015987654321BBBBBBBBB12123124125mi