线性规划最新版本ppt课件

第一章线性规划与单纯形方法,第一节线性规划问题及数学模型线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）,线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）,线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”,线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”,线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”,线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。,1线性规划发展史线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。,2线性规划基本概念生产计划问题如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。如何合理使用有限的人力，物力和资金，以达到最经济的方式，完成生产计划的要求。,例1生产计划问题（资源利用问题）某家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？,解：将此问题列成图表如下：,将一个实际问题转化为线性规划模型有以下几个步骤：,将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量x2=生产椅子的数量,解：将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量x2=生产椅子的数量2确定目标函数：家具厂的目标是销售收入最大maxz=50 x1+30 x2,解：将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量x2=生产椅子的数量2确定目标函数：家具厂的目标是销售收入最大maxz=50 x1+30 x23确定约束条件：4x1+3x2120（木工工时限制）2x1+x250（油漆工工时限制）,解：将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量x2=生产椅子的数量2确定目标函数：家具厂的目标是销售收入最大maxz=50 x1+30 x23确定约束条件：4x1+3x2120（木工工时限制）2x1+x250（油漆工工时限制）4变量取值限制：一般情况，决策变量只取正值（非负值）x10,x20,解：将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量x2=生产椅子的数量2确定目标函数：家具厂的目标是销售收入最大maxz=50 x1+30 x23确定约束条件：4x1+3x2120（木工工时限制）2x1+x250（油漆工工时限制）4变量取值限制：一般情况，决策变量只取正值（非负值）x10,x20,数学模型maxS=50 x1+30 x2s.t.4x1+3x21202x1+x250 x1,x20线性规划数学模型三要素：决策变量、约束条件、目标函数,一、问题的提出,解：,1.决策变量：设产品I、II的产量分别为x1、x2,2.目标函数：设总运费为z，则有：maxz=2x1+3x2,3.约束条件：,3线性规划问题的数学模型,例3营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？,各种食物的营养成分表,每天需要300055800,各种食物的营养成分表,每天需要300055800,X1X2x3x4,解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：minS=14x1+6x2+3x3+2x4s.t.1000 x1+800 x2+900 x3+200 x4300050 x1+60 x2+20 x3+10 x455400 x1+200 x2+300 x3+500 x4800 x1，x2，x3，x40,例4合理下料问题现做100套钢架，每套用长为2.9m,2.1m和1.5m的原钢各一根。已知原料长为7.4m，问应如何下料，使用的原料最省。解：最简单的方法是在每根原料上截取2.9m,2.1m,1.5m的元钢各一根组成一套，需100根，每根省下料头0.9m，就浪费了。若改为套裁，可以节约原料。几种套裁方案如下表：,设各种方案下料的根数为xi,i=1,2,3,4,5其数学模型为：minS=0.3x1+0 x2+0.1x3+0.8x4+0.2x5(orminS=x1+x2+x3+x4+x5)s.t.x1+2x2+2x3=1002x1+x4+2x5=1003x1+x3+3x4+2x5=100 x1，x2，x3，x4，x50,例5运输问题设有两砖厂A1、A2分别供应三个工地B1、B2、B3，运价表如下，问如何调运使总运费最省？列出数学模型。,解设Ai调运给Bj的调运量为xij,i=1,2;j=1,2,3其数学模型为：minS=50 x11+60 x12+70 x13+60 x21+110 x22+160 x23s.t.x11+x12+x13=23x21+x22+x23=27x11+x21=17x12+x22=18x13+x23=15xij0,i=1,2;j=1,2,3,其他典型问题：运输问题,其他典型问题：合理下料问题运输问题生产的组织与计划问题,其他典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题,其他典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题,其他典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题生产工艺优化问题,用于成功决策的实例：美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策,用于成功决策的实例：美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策美国国防部关于如何从现有的一些基地向海湾运送海湾战争所需要的人员和物资的决策,用于成功决策的实例：美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策美国国防部关于如何从现有的一些基地向海湾运送海湾战争所需要的人员和物资的决策Chessie道路系统关于购买和修理价值40亿美圆货运汽车决策,用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每天电力需求决策,用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策,用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策北美长途运输公司关于每周如何调度数千辆货车的决策,用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策北美长途运输公司关于每周如何调度数千辆货车的决策埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更改的决策,用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策北美长途运输公司关于每周如何调度数千辆货车的决策埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更改的决策,4线性规划问题的一般形式：Max(Min)S=c1x1+c2x2+.+cnxns.t.a11x1+a12x2+.+a1nxn(=,)b1a21x1+a22x2+.+a2nxn(=,)b2.am1x1+am2x2+.+amnxn(=,)bmx1,x2,.,xn0,线性规划问题的标准形式(1)：MaxS=c1x1+c2x2+.+cnxns.t.a11x1+a12x2+.+a1nxn=b1a21x1+a22x2+.+a2nxn=b2.am1x1+am2x2+.+amnxn=bmx1,x2,.,xn0其中：bi0(i=1,2,.m),线性规划问题的标准形式(2)：,向量形式(3),线性规划标准型的矩阵形式(3)：,x10 x20C=(c1,c2,cn)X=0=.xn0,a11a12.a1nb1A=a21a22.a2nb=b2.am1am2.amnbn,如何将一般问题化为标准型：若目标函数是求最小值MinS=CX令S=-S,则MaxS=-CX,如何将一般问题化为标准型：若目标函数是求最小值MinS=CX令S=-S,则MaxS=-CX若约束条件是不等式,如何将一般问题化为标准型：若目标函数是求最小值MinS=CX令S=-S,则MaxS=-CX若约束条件是不等式若约束条件是“”不等式naijxj+yi=bij=1yi0是非负的松驰变量,如何将一般问题化为标准型：若约束条件是“”不等式naijxj-zi=bij=1zi0是非负的松驰变量,如何将一般问题化为标准型：若约束条件右面的某一常数项bi0这时只要在bi相对应的约束方程两边乘上-1。,如何将一般问题化为标准型：若约束条件右面的某一常数项bi0这时只要在bi相对应的约束方程两边乘上-1。若变量xj无非负限制引进两个非负变量xjxj”0令xj=xj-xj”,如何将一般问题化为标准型：若约束条件右面的某一常数项bi=0令xj=xj-xj”（可正可负）任何形式的线性规划总可以化成标准型,例6将下列问题化成标准型:MinS=-x1+2x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1+x2+2x3=5x1,x20 x3无非负限制,MaxS=x1-2x2+3x3-3x3”s.t.x1+x2+x3-x3”+x4=7x1-x2+x3-x3”-x5=2-3x1+x2+2x3-2x3”=5x1,x2,x3,x3”,x4,x50,例6将下列问题化成标准型:MinS=-x1+2x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1+x2+2x3=5x1,x20 x3无非负限制,（二维）线性规划问题图解法：（1）满足约束条件的变量的值，称为可行解。,（二维）线性规划问题图解法：（1）满足约束条件的变量的值，称为可行解。（2）使目标函数取得最优值的可行解，称为最优解。,（二维）线性规划问题图解法：（1）满足约束条件的变量的值，称为可行解。（2）使目标函数取得最优值的可行解，称为最优解。例1的数学模型maxS=50 x1+30 x2s.t.4x1+3x21202x1+x250 x1,x20,x2,50,40,30,20,10,10,20,30,40,x1,4x1+3x2120,由4x1+3x2120 x10 x20围成的区域,x2,50,40,30,20,10,10,20,30,40,x1,2x1+x250,由2x1+x250 x10 x20围成的区域,x2,50,40,30,20,10,10,20,30,40,x1,2x1+x250,4x1+3x2120,可行域,同时满足：2x1+x2504x1+3x2120 x10 x20的区域可行域,x2,50,40,30,20,10,10,20,30,40,x1,可行域,O（0，0）,Q1（25，0）,Q2（15，20）,Q3（0，40）,可行域是由约束条件围成的区域，该区域内的每一点都是可行解，它的全体组成问题的解集合。该问题的可行域是由O，Q1，Q2，Q3作为顶点的凸多边形,x2,50,40,30,20,10,10,20,30,40,x1,可行域,目标函数是以S作为参数的一组平行线S=50 x1+30 x2x2=S/30-（5/3）x1-2-5/3-4/3,x2,50,40,30,20,10,10,20,30,40,x1,可行域,当S值不断增加时，该直线x2=S/30-（5/3）x1沿着其法线方向向右上方移动。,x2,50,40,30,20,10,10,20,30,40,x1,可行域,当该直线移到Q2点时，S（目标函数）值达到最大：MaxS=50*15+30*20=1350此时最优解=（15，20）,Q2（15，20）,二个重要结论：满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。,二个重要结论：满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。最优解必定能在凸多边形的某一个顶点上取得，这一事实也可以推广到更多变量的场合。,解的讨论：最优解是唯一解；,解的讨论：最优解是唯一解；无穷多组最优解：例1的目标函数由maxS=50 x1+30 x2变成：maxS=40 x1+30 x2s.t.4x1+3x21202x1+x250 x1,x20,例1maxS=50 x1+30 x2s.t.4x1+3x21202x1+x250 x1,x20,x2,50,40,30,20,10,10,20,30,40,x1,可行域,目标函数是同约束条件：4x1+3x2120平行的直线x2=S/30-（4/3）x1,x2,50,40,30,20,10,10,20,30,40,x1,可行域,当S的值增加时，目标函数同约束条件：4x1+3x2120重合，Q1与Q2之间都是最优解。,Q1（0，40）,Q2（15，20）,解的讨论：无界解：例：maxS=x1+x2s.t.-2x1+x240 x1-x220 x1,x20,x2,50,40,30,20,10,10,20,30,40,x1,该可行域无界，目标函数值可增加到无穷大，称这种情况为无界解或无最优解。,-2x1+x240,x1-x220,解的讨论：无可行解：例：maxS=2x1+3x2s.t.x1+2x28x14x23-2x1+x24x1,x20,该问题可行域为空集，即无可行解，也不存在最优解。,解的情况：有可行解有唯一最优解有无穷最优解无界解(无最优解）无可行解,线性规划问题解的概念线性规划标准型的矩阵形式：MaxS=CX（1-9）s.t.AX=b（1-10）X0（1-11）,a11a12.a1nb1A=a21a22.a2nb=b2am1am2.amnbn,c1x10c2x20C=X=0=xn0,.,线性规划问题的数学模型：一般式，标准型。线性规划问题的图解法（二维）,线性规划标准型的矩阵形式：MaxS=CXs.t.AX=bX0,线性规划问题的解解、可行解、最优解满足约束条件（1-10）的X，称为线性规划问题的解。,MaxS=CX（1-9）s.t.AX=b（1-10）X0（1-11）,解、可行解、最优解满足约束条件（1-10）的X，称为线性规划问题的解。满足约束条件（1-10）与（1-11）的X，称为线性规划的问题可行解。,解、可行解、最优解满足约束条件（1-10）的X，称为线性规划问题的解。满足约束条件（1-10）与（1-11）的X，称为线性规划的问题可行解。满足目标函数（1-9）的可行解X，称为线性规划的问题最优解。,基、基向量、基变量设r(A)=m,并且B是A的m阶非奇异的子矩阵（det(B)0),则称矩阵B为线性规划问题的一个基。,基、基向量、基变量设r(A)=m,并且B是A的m阶非奇异的子矩阵（det(B)0),则称矩阵B为线性规划问题的一个基。矩阵B=（P1，P2.Pm)，其列向量Pj称为对应基B的基向量。,基、基向量、基变量设r(A)=m,并且B是A的m阶非奇异的子矩阵（det(B)0),则称矩阵B为线性规划问题的一个基。矩阵B=（P1，P2.Pm)，其列向量Pj称为对应基B的基向量。与基向量Pj相对应的变量xj就称为基变量，其余的就称为非基变量。,基础解.基础可行解.可行基对于某一特定的基B，非基变量取0值的解，称为基础解(基解)。,基础解.基础可行解.可行基对于某一特定的基B，非基变量取0值的解，称为基础解。满足非负约束条件的基础解，称为基础可行解(基可行解)。,基础解.基础可行解.可行基对于某一特定的基B，非基变量取0值的解，称为基础解。满足非负约束条件的基础解，称为基础可行解。与基础可行解对应的基，称为可行基。,矩阵A=（P1，P2.,Pn),B=（P1，P2.Pm)，基的个数，基可行解的个数。,a11a12.a1mb1B=a21a22.a2mb=b2am1am2.ammbn,a11a12a1mb1a1m+1a1na21x1+a22x2+.+a2mxm=b2-a2m+1xm+1-.-a2nxnam1am2ammbnamm+1amn,或,令,XB是对应这个基的基变量XB=,为基解。,基解中非零分量的个数小于m个时，该基解是退化解。为了理解基础解.基础可行解.最优解的概念，用下列例子说明：,.,标准型为：,maxz=2x1+3x2+0 x3+0 x4+0 x5,例maxz=2x1+3x2,.,基,基为：,基变量为：x3，x4，x5，非基变量为x1，x2。,令非基变量x1=0，x2=0，基变量x3=8，x4=16，x5=12,X=(0,0,8,16,12)T为基解，且为基可行解,解的集合：,非可行解,可行解,解的集合：,基础解,解的集合：,可行解,基础解,基础可行解,解的集合：,可行解,基础解,基础最优解,基础可行解,第二节：线性规划解的性质（几何意义）凸集（Convexset）概念：设D是n维欧氏空间的一个点集，若D中的任意两点x(1),x(2)的连线上的一切点x仍在D中，则称D为凸集。即：若D中的任意两点x(1),x(2)D，存在01使得x=x(1)+(1-)x(2)D,则称D为凸集,.,例1.6（凸集）,.,例（非凸集）,例:X=X(1)+(1-)X(2),为什么？,X1,X2,X(1),X(2),X,图（1-7）,例,X1,X2,X(1),X(2),-X(2),X(1)-X(2),图（1-7）,X,例,X1,X2,X(1),X(2),X,X(1)-X(2),y=(X(1)-X(2)(01),X=X(2)+y=X(2)+(X(1)-X(2)=X(1)+(1-)X(2),图（1-7）,例,X1,X2,X(1),X(2),X,-X(2),X(1)-X(2),图（1-7）,X=X(2)+y=X(2)+(X(1)-X(2)=X(1)+(1-)X(2),y=(X(1)-X(2)(01),两个基本概念：凸组合(Convexcombination)：设x(1),x(2).x(k)是n维欧氏空间中的k个点，若存在数u1,u2,.uk且0ui1(i=1,2,k),ui=1,使得x=u1x(1)+u2x(2)+.+ukx(k)成立，则称x为x(1),x(2).x(k)的凸组合。,两个基本概念：顶点(Extremeopint)：设D是凸集,若D中的点x不能成为D中任何线段上的内点，则称x为凸集D的顶点。即：若D中的任意两点x(1),x(2)，不存在数（01）使得x=x(1)+(1-)x(2)成立，则称x为凸集D的一个顶点。,例：多边形上的点是顶点,圆周上的点都是顶点,线性规划的基本定理,定理1-1线性规划问题的可行解集是凸集。（即连接线性规划问题任意两个可行解的线段上的点仍然是可行解。),证明线性规划问题的可行解的集合为D=X|AX=b,X0。任意X1,X2D,有AX1=b,X10;AX2=b,X20。令X*=X1+(1-)X2,则AX*=AX1+(1-)X2=AX1+(1-)AX2=b+(1-)b=b,且X1+(1-)X20。故X*D,线性规划的基本定理,定理1-2线性规划问题的可行解x=（x1,x2,xn)T为基础可行解的充分必要条件是：x的非零分量所对应的系数矩阵A的列向量是线性