运筹学A-第1章线性规划.ppt

第1章线性规划与单纯形法,2019/12/9,2,第1章线性规划,内容提要,第一节线性规划问题的数学模型第二节两个变量LP问题的图解法第三节LP问题数学模型的标准型第四节线性规划问题解的性质第五节单纯形法原理及求解步骤,2019/12/9,3,第一节线性规划问题的数学模型,线性规划(LinearProgramming，LP)是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。,线性规划通常研究资源的最优利用、设备最佳运行以及费用最低等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大）。,2019/12/9,4,一、问题的提出（线性规划问题举例）3.26,例1-1(生产计划问题)某厂在计划期内安排、生产两种产品，已知生产单位产品所需要的设备台数、A和B两种原材料的消耗量以及利润如表1-1所示，问如何安排生产使利润最大？（假设产品全部售出）,x1,x1,x1,x2,x2,x2,2019/12/9,5,(1)决策变量：设x1为甲产品的产量，x2为乙产品的产量。(2)约束条件：生产受资源制约，不能突破有限供给量。设备约束条件的数学表达为：x1+2x28原材料A约束条件数学表达为：4x116原材料B约束条件数学表达为：4x212(3)目标函数：目标函数反映企业利润最大化maxZ=2x1+3x2(4)非负约束：两产品的产量为非负x10，x20,LP模型：,s.t.(subjectto)使满足，使服从,例1-2见教材第5页,2019/12/9,6,例1-3.某工地租赁甲、乙两种机械安装A、B、C三种构件，这两种机械每天的安装能力、租赁费用以及工程任务如下表所示，问如何租赁甲、乙两机械才能使总的租赁费用最低？,2019/12/9,7,【解】设租赁机械甲x1天、机械乙x2天，则该线性规划问题的数学模型为：,例1-4见教材第6页，例【1.2】人员分配问题,2019/12/9,8,某一机床需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是2.9、2.1和1.5m，这些轴需要用同一种圆钢切割而成，圆钢长度为7.4m。现在要制造100台机床，问：最少要用多少圆钢来生产这些轴？(切割损失不计),解：1、设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1,y2,y3,则切割方式可用不等式2.9y1+2.1y2+1.5y37.4表示，求这个不等式关于y1，y2，y3的非负整数解。例如：y1=2，y2=0，则y3只能为1，余料为0.1。像这样的非负整数解共有8组，也就是有8种下料方式，如表1.4所示。,2、建立线性规划数学模型。设xj(j=1,2,8)为第j种下料方案所用圆钢的根数。,思考题：（下料问题）,2019/12/9,9,minZ=x1+x2+x3+x4+x5+x6+x7+x8,(x1=10,x2=50,x4=30,16m),2019/12/9,10,思考题：某糖果厂用原料A，B，C加工成三种不同牌号糖果甲、乙、丙。已知各种糖果的中A，B，C的含量，原料成本，各种原料每月的限制用量，三种牌号糖果的单位加工费及售价如下表所示。,问该厂每月生产这三种牌号糖果各多少kg，利润最大？,2019/12/9,11,解：设xij为生产第j种糖果使用的第i种原料的公斤数，i=1,2,3；j=1,2,3，则该问题的数学模型可归结为：,最优解：,即该厂每月应生产甲种牌号糖果906.67kg，乙种牌号糖果4793.33kg。,2019/12/9,12,思考题：（投资问题）,某投资公司在第一年初有100万元资金，每年都有如下的投资方案：假使第一年初投入一笔资金，第二年初又继续投入此资金的50%，那么到第三年初就可回收第一年初投入资金的两倍。问：该投资公司如何确定投资策略使第六年初所拥有的资金最多？,解：设x1为第一年的投资，x2为第一年的保留资金，则：,x1+x2=100,第二年：设x3为第二年新的投资，x4为第二年的保留资金，则：,2019/12/9,13,第三年：设x5为新的投资，x6为第三年的保留资金；,第四年：设新的投资x7，第四年的保留资金x8；,第五年：设x9为第五年的保留资金。根据题意，第五年初不再进行新的投资，因为这笔投资要到第七年初才能收回。,约束条件每年应满足如下的关系：追加投资金额+新投资金额+保留资金=可利用的资金总额,2019/12/9,14,X*(22.64,72.36,58.54,0,26.02,0,104.06,0,0)T，Z*208.12。,到第六年初，实有资金总额为x9+2x7，整理后得到下列线性规划模型：,maxZ=2x7+x9,第一年投资22.64元;第二年新投资58.54元;第三年新投资26.02元;第四年新投资104.06元;第六年初拥有资金208.12万元。,2019/12/9,15,思考题：某人有30万元资金，在今后的三年内有以下投资项目可供参考：(1)三年内的每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年的投资；(2)只允许第一年年初投入，第二年末可收回，本利合计为投资额的150%，但此类投资额不超过15万元；(3)第二年初允许投资，可于第三年末收回，本利合计为投资额的160%，这类投资限额20万元；(4)第三年初允许投资，一年回收，可获利40%，投资限额为10万元。试为该人确定一个使第三年末本利和为最大的投资计划？（假设有钱就用于投资）,设xij为第i年初投入到j项目的资金额,2019/12/9,16,对于约束条件：,第1年，可用于项目1和2投资：x11+x12=300000,第2年，可用于项目1和3投资，投资额为x11的本利和：x21+x23=1.2x11,第3年，可用于项目1和4投资，投资额x21和x12有关：x31+x34=1.2x21+1.5x12,投资限额：x12150000;x23200000;x34100000,非负约束：xij0(i=1,2,3;j=1,2,3,4),对于目标函数，只需考虑第3年末的收益：,项目1：x311.2x31(本利和)；,项目2：x220；,项目3：x231.6x23(本利和)；,项目4：x341.4x34(本利和)；,maxZ=1.2x31+1.6x23+1.4x34,2019/12/9,17,解：设xij为第i年初投入到j项目的资金额，其数学模型为：,maxZ=1.2x31+1.6x23+1.4x34,注意本题条件：有钱就会用于投资，即：可利用的资金=投资金额，据此建立约束等式。,x11+x12=300000 x21+x23=1.2x11x31+x34=1.2x21+1.5x12x12150000 x23200000 x34100000 xij0(i=1,2,3;j=1,2,3,4),2019/12/9,18,二、线性规划问题的数学模型3.30,线性规划问题的数学模型包括三大要素：（1）一组决策变量（x1,x2,xn），是模型中需要首确定的未知量。（2）一组约束条件，是模型中决策变量受到的约束限制，包括两个部分：不等式或等式；非负取值（实际问题）。（3）一个目标函数，是关于决策变量的最优函数，max或min。,2019/12/9,19,思考：为什么称以上问题为线性规划问题呢？,其主要特征是：1.解决的问题是规划问题；2解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；3解决问题的约束条件是多个决策变量的线性不等式或等式。,2019/12/9,20,线性规划问题模型的一般形式可总结为：,线性规划问题模型的一般形式,用一组非负决策变量表示的一个决策问题；存在一组等式或不等式的线性约束条件；有一个希望达到的目标，可表示成决策变量的极值线性函数。,为了书写方便，上式也可简写：,2019/12/9,21,一般地，xj0，但有时xj0或xj无符号限制。,2019/12/9,22,其中：cj为价值系数，C=(c1,c2,cn)为价值向量；aij为技术系数，A=(P1,P2,Pn)为技术矩阵，如：P1=(a11,a21,am1)T，P2=(a12,a22,am2)T，Pn=(a1n,a2n,amn)T；bi为限制系数，b=(b1,b2,bm)T。,2019/12/9,23,线性规划模型矩阵形式，,其中：X=(x1,x2,xn)T；C=(c1,c2,cn)；b=(b1,b2,bm)T。,技术系数矩阵：,2019/12/9,24,第二节用于两个变量线性规划问题的图解法,1、概念：利用几何图形求解两个变量线性规划问题的方法。,3、求解步骤：,第一步：建立平面直角坐标系；,第三步：在可行域内平移目标函数等值线，确定最优解及最优目标函数值。,2、特点：简单、直观，但只适用于两个变量的LP问题。,第二步：根据约束条件画出可行域；,2019/12/9,25,可行解：满足约束条件的解；可行域：所有可行解的集合；最优解：使目标函数达到最优的可行解。可行域：满足所有约束条件的解的集合，即所有约束条件共同围城的区域。,maxZ=3x1+5x22x1162x2103x1+4x232x10,x20,s.t.,2019/12/9,26,目标函数等值线,目标函数Z=3x1+5x2代表以Z为参数的一族平行线。,(4,5),2019/12/9,27,例：用图解法求解线性规划问题？,坐标系：横坐标x1，纵坐标x2,(2,6),先将约束不等式变为等式，画出各等式对应的直线，然后再根据不等式符号确定可行域,*线性规划问题解的可能,结论：该问题具有唯一最优解，X*=(2,6)T，Z*=360,向上平移目标函数等值线x2=-3x1/5+Z/50，确定最优解。,2019/12/9,28,x1,x2,O,10,20,30,40,10,20,30,40,(15,10),最优解X*=(15,10)T,最优值Z*=85,2019/12/9,29,2,4,6,x1,x2,2,4,6,最优解X*=(3,1)T最优值Z*=5,(3,1),minZ=x1+2x2,2019/12/9,30,例：用图解法进行求解线性规划问题？,如果线性规划问题有两个最优解，则它一定有无穷多最优解（多重最优解）。,2019/12/9,31,例用图解法求线性规划问题？,2019/12/9,32,该线性规划问题具有无界解。可行域无上界，目标值可以无限增大(缺乏必要约束),2019/12/9,33,例,2019/12/9,34,该线性规划问题无可行解，原因：线性规划问题的可行域是空集(约束条件相互矛盾),2019/12/9,35,x2,x1,O,10,20,30,40,10,20,30,40,50,50,无可行解即无最优解,maxZ=10 x1+4x2,2019/12/9,36,图解法的解题思路和几何上的直观表示，对求解线性规划问题的求解具有重要启示：（1）LP问题的解一般有唯一解、无穷多最优解、无界解和无可行解四种情况。（2）LP问题的可行域一般为无界或有界凸多边形。（3）若LP问题的最优解存在，即有唯一最优解或无穷多最优解，则必在可行域的某个项点上找到最优解。（4）若LP问题有两个最优解，则在它们的连线上的任意一点都是最优解。,作业：教材第37页，1.3：(1)、(2)、(3)；1.4,2019/12/9,37,一、线性规划数学模型的标准型,第三节线性规划问题数学模型的标准形式,1、标准型表达方式,(1)代数式：,(2)向量式：,(3)矩阵式：,A：技术系数矩阵，简称系数矩阵；B：可用的资源量，称资源向量；C：决策变量对目标的贡献，称价值向量；X：决策向量。,2019/12/9,38,通常X记为：，其中，为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况mn，且r()m。,其中:,2019/12/9,39,2、一般型标准型的转换方法,(1)“决策变量非负”。若某决策变量xk为“取值无约束”(无符号限制)，令：xk=xkx”k，(xk0,x”k0)。(2)“目标函数求最大值”。如果极小化原问题minZ=CX，则令Z=Z，转为求maxZ=CX。注意：求解后还原。(3)“约束条件为等式”。对于“”型约束，则在“”左端加上一个非负松弛变量(slackvariable)，使其为等式。对于“”型约束，则在“”左端减去一个非负剩余变量(Surplusvariable)，使其为等式。(4)“资源限量非负”。若某个bi0(x20)。,说明x2可以无限增大，所以目标函数值可以无限增大。,2019/12/9,87,图解法求解结果：,判定定理3：,在单纯形表中，若某个检验数k大于零，且xk对应列向量的元素均为非正，导致出基变量无法确定，则线性规划问题具有无界解。,2019/12/9,88,练习求解下列线性规划问题,解：引进松驰变量x3,x4，化为标准形式：,从标准形中可看出存在可行基B=(P3，P4)=I，基变量为X3，X4；非基变量为X1，X2。建立初始单纯形表得：,2019/12/9,89,由于x1，x2的检验数均为非负，且x1的检验数绝对值最大，选取x1为进基变量；再按最小比值=min（24/2，26/3）=26/3，选取x4为出基变量，进行换基迭代。,2019/12/9,90,表中最后一行的所有检验数均为非正，表明目标函数已达到最大值，上表为最优单纯形表。从表中可得到最优解为：X*=(x1,x2,x3,x4)T=(6,4,0,0)T，最优值为：Z*=36。,作业：教材39页，1.8第(1),(4)题,在最终单纯形表中，所有非基变量检验数均为负数，说明该线性规划问题具有唯一最优解：X=(6,4,0,0)T，Z*=36。,2019/12/9,91,练习：已知某线性规划用单纯形法求得的某两步迭代表如下，请将表中空白处填上适当的数字。,2019/12/9,92,讨论：用单纯形法求解某极大化问题的单纯形表如下，问表中参数a1,a2,a3,d,1,2为何取值范围时，下列结论成立。,(1)表中解为唯一最优解：(2)表中解为无穷多最优解：(3)该问题具有无界解：(4)表中解为退化的基解：(5)表中解为不可行解：(6)x1入基，x6出基：,10,20,12=0,d0,10,d0,d/43/a3,2019/12/9,93,思考题：已知线性规划问题：,其中b1,b2是常数，且已知此问题的最终单纯形表如下。试确定表中所有的参数及b1和b2的值？,e=0,d=5,b=5,c=10,a=23,b1=30,b2=40,2019/12/9,94,思考题：已知线性规划问题的最优单纯形表如下，求初始单纯形表中参数C,A,b以及最优基B？,2019/12/9,95,解法(一)：矩阵初等行变换,增广矩阵：,求A和b：,2019/12/9,96,求cj：,最优基？,2019/12/9,97,解法(二)：用B-1求解,2019/12/9,98,求C和b：,2019/12/9,99,求解结果：,2019/12/9,100,大M法（大M单纯形法）,通过添加人工变量构成单位基，进而求解线性规划问题的方法。,2019/12/9,101,例求解下列线性规划问题,解：引进松驰变量x4,x5，化为标准形式：,2019/12/9,102,加入变量x6,x7，加入参数M，M为任意大的正数,2019/12/9,103,x3,-1,10,3,-2,0,1,0,0,-1,1,0,1,0,0,-1,1,-2,1,-1+M,0,0,-M,0,1-3M,2019/12/9,104,x2,-1,12,3,0,0,1,-2,2,-5,1,-2,0,1,0,0,0,1,1,0,0,0,-1,1-M,-1-M,2019/12/9,105,x1,3,4,1,0,0,1/3,-2/3,2/3,-5/3,9,0,0,1,2/3,-4/3,4/3,-7/3,0,0,0,-1/3,-1/3,1/3-M,2/3-M,2,X*=(4,1,9,0,0,0,0)T,Z*=2,2019/12/9,106,大M法求解的可能结果：,(1)基变量中不含人工变量；,(2)基变量中含人工变量，但人工变量取值为零；,(3)基变量中含人工变量，但人工变量取值不为零；,只在前两种情况下，线性规划问题有最优解，对于第三种情况，线性规划问题无可行解。,2019/12/9,107,例,2019/12/9,108,x1,30,2,0,0,-1,-1,0,0,1,6,0,2,-3,0,0,1,0,2019/12/9,109,x2,50,3,0,0,3/2,0,1,-1/2,0,3,0,1,-3/2,0,0,1/2,0,因基变量中含人工变量，且取值不为零(2)，所以该问题无可行解。,2019/12/9,110,课堂练习用大M法求解下列线性规划问题,解：引入松驰变量x4，化为标准形式：,2019/12/9,111,加入变量x5,x6，加入参数M，M为任意大的正数,2019/12/9,112,x1,1,2,0,-4,2,1,-1,1,0,-10-4M,4+2M,1+M,-1-2M,0,x3,3,1,0,-2,1,1/2,-1/2,1/2,3,1,0,0,-1/2,1/2,1/2,0,-2,0,-1,1-M,-2-M,6,2019/12/9,113,基变量中不含人工变量，且所有非基变量的检验数均为非正，所以该问题具有唯一最优解。,X*=(3,0,1,0,0,0)T,Z*=6,作业：教材39页，1.9第(1)题,2019/12/9,114,两阶段法,两阶段法是处理人工变量的另一种方法，是将加入人工变量后的线性规划问题分成两个阶段求解。,第一阶段：加入人工变量后构造辅助的线性规划问题：目标函数求最小值，人工变量系数均为-1，原变量系数均为0。若minW=0，则得到原问题的初始基可行解，可进入第二阶段。若minW0，表明原问题不可行。,第二阶段：首先在第一阶段最终