第一章 线性规划与单纯形方法

1、第一章线性规划与单纯形方法,第一节线性规划问题及数学模型线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）,线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）,线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”,线性规划（概论）线

2、性规划（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年印度的

3、Karmarkar提出“投影梯度法”,线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。,1线性规划发展史线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dan

4、tzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。,2线性规划基本概念生产计划问题如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。如何合理使用有限的人力，物力和资金，以达到最经济的方式，完成生产计划的要求。,例1生产计划问题（资源利用问题）某家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅

5、子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？,解：将此问题列成图表如下：,将一个实际问题转化为线性规划模型有以下几个步骤：,将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量x2=生产椅子的数量,解：将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量x2=生产椅子的数量2确定目标函数：家具厂的目标是销售收入最大maxz=5

6、0 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变量取值限制：一般情况，决策变量只取正

7、值（非负值）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.目标函

8、数：设总运费为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 x

9、3+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.

10、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=15

11、xij0,i=1,2;j=1,2,3,其他典型问题：运输问题,其他典型问题：合理下料问题运输问题生产的组织与计划问题,其他典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题,其他典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题,其他典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题生产工艺优化问题,用于成功决策的实例：美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策,用于成功决策的实例：美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策美国国防部关于如何从现有的一些基地向海湾运送海湾

12、战争所需要的人员和物资的决策,用于成功决策的实例：美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策美国国防部关于如何从现有的一些基地向海湾运送海湾战争所需要的人员和物资的决策Chessie道路系统关于购买和修理价值40亿美圆货运汽车决策,用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每天电力需求决策,用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策,用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系

13、统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策北美长途运输公司关于每周如何调度数千辆货车的决策,用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策北美长途运输公司关于每周如何调度数千辆货车的决策埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更改的决策,用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计6

14、0亿美圆）来维持发展决策北美长途运输公司关于每周如何调度数千辆货车的决策埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更改的决策,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+.+

15、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若约束条件是不

16、等式若约束条件是“”不等式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将下列问题

17、化成标准型: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）

18、满足约束条件的变量的值，称为可行解。（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

19、,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/3

20、0-（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）,二个重要结论：满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。,二个重要结论：满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。最优解必定能

21、在凸多边形的某一个顶点上取得，这一事实也可以推广到更多变量的场合。,解的讨论：最优解是唯一解；,解的讨论：最优解是唯一解；无穷多组最优解：例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,x

22、1,可行域,当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,该问题可行域为空集，即无可行解，也不存在最优解。,解的情况：有可行解有唯一

23、最优解有无穷最优解无界解(无最优解）无可行解,线性规划问题解的概念线性规划标准型的矩阵形式：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）,解、可行解、最优解满足约束

24、条件（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称

25、为对应基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值的解，称为基础解。满足非负约束条件的基础解，称为

26、基础可行解。与基础可行解对应的基，称为可行基。,矩阵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,

27、例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)+

28、(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

29、=(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的一个顶点。,例：多边形上的点是顶点,圆周上的

30、点都是顶点,线性规划的基本定理,定理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的列向量是线性无关。,证明：必要性由基础解的定义可知：非零分量所对应的系数

31、列向量为基向量，故系数矩阵A的列向量是线性无关。（86）充分性若向量P1,P2,Pk线性无关，则必有km;当k=m时，恰构成一个基，从而X为基可行解，当km时，则一定可以从其余的列向量中取出m-k个与P1,P2,Pk构成极大无关组，对应的解恰为X，有定义它是基础可行解。,线性规划的基本定理,定理1-3线性规划问题的可行解集D中的点x是顶点的充分必要条件是：x是基础可行解。顶点与基可行解相对应,线性规划的基本定理,定理1-3线性规划问题的可行解集D中的点x是顶点的充分必要条件是：x是基础可行解。推论1：可行解集D中的顶点个数是有限的。,线性规划的基本定理,定理1-3线性规划问题的可行解集D中的点

32、x是顶点的充分必要条件是：x是基础可行解。推论：可行解集D中的顶点个数是有限的。推论2：若可行解集D是有界的凸集，则D中任意一点x，都可表示成D的顶点的凸组合。,例：,x1,x2,X(1),X(2),X(3),x,x1,x2,X(1),X(2),X(3),x,X,X=X(1)+(1-)X(3)(01),x1,x2,X(1),X(2),X(3),X,X,X=X+(1-)X(2)(01),因为x是X(1)，X(3)连线上的一点，故x=X(1)+(1-)X(3)(01)又因为x是X，X(2)连线上的一点，故X=X+(1-)X(2)(01)X=（X(1)+(1-)X(3)）+(1-)X(2)=X(1)

33、+(1-)X(2)+(1-)X(3)=u1X(1)+u2X(2)+u3X(3)其中(0ui1)且u1+u2+u3=+(1-)+(1-)=1,x1,x2,X(1),X(2),X(3),X,X=u1X(1)+u2X(2)+u3X(3),线性规划的基本定理,定理1-4若可行域D有界，则线性规划问题的最优解，必定在D的顶点上达到。证明反证法：若X*不为顶点且是LP的最优解，由推论2，因此，令则由此得到即目标函数在顶点处也达到最优值。,说明1：若可行解集D无界，则线性规划问题可能有最优解，也可能无最优解。若有最优解，也必在顶点上达到。说明2：有时目标函数也可能在多个顶点上达到最优值。这些顶点的凸组合也是

34、最优值。（有无穷多最优解）事实上，若是目标函数达到最大值的顶点，于是，,练习题已知线性规划问题：求其所有基解，基可行解及最优解。,MaxS=CXs.t.AX=bX0,基，基解，基可行解，可行基。线性规划问题的可行域D是凸集。顶点与基可行解相对应线性规划问题的最优解，必定在D的顶点上达到。目标函数在多个顶点上达到最优值。这些顶点的凸组合也是最优值。（有无穷多最优解）。,第三节线性规划-单纯形方法单纯形方法基本思路：从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。,线性规划（2）-单纯形方法单纯形方法基本思路：从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。如可能，

35、从可行域中求出具有更优目标函数值的另一个基础可行解（另一个顶点），以改进初始解。,线性规划（2）-单纯形方法单纯形方法基本思路：从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。如可能，从可行域中求出具有更优目标函数值的另一个基础可行解（另一个顶点），以改进初始解。继续寻找更优的基础可行解，进一步改进目标函数值。当某一个基础可行解不能再改善时，该解就是最优解。,第三节线性规划-单纯形方法单纯形方法基本思路：1.从可行域中某个基础可行解（一个顶点）开始（称为初始基础可行解）。,2.如可能，从可行域中求出具有更优目标函数值的另一个基础可行解（另一个顶点），以改进,3.继续寻找更优的基

36、础可行解，进一步改进目标函数值。当某一个基础可行解不能再改善时，该解就是最优解。,初始解。,一、消去法例1-18：一个企业需要同一两种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？,解：数学模型maxS=2x1+3x2s.t.x1+2x284x1164x212x1,x20,解：引进松弛变量x3,x4,x5=0数学模型标准形式：maxS=2x1+3x2s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x50,约束条件的增广矩阵

37、为：121008（Ab)=40010160400112显然r(A)=r(Ab)=35,该问题有无穷多组解。,令A=（P1，P2，P3，P4，P5）=121004001004001X=（x1,x2,x3,x4,x5),A=（P1，P2，P3，P4，P5）=121004001004001X=（x1,x2,x3,x4,x5)TB=(P3，P4，P5）=100010001x3,x4,x5是基变量，x1,x2,是非基变量。,用非基变量表示的方程：x3=8-x1-2x2x4=16-4x1(I)x5=12-4x2S=0+2x1+3x2称(I)为消去系统，,令非基变量（x1,x2）T=（0，0）T得基础可行解

38、：x(1)=(0,0,8,16,12)TS1=0经济含义：不生产产品甲乙，利润为零。分析：S=0+2x1+3x2（分别增加单位产品甲、乙，目标函数分别增加2、3，即利润分别增加2百元、3百元。）增加单位产品对目标函数的贡献，这就是检验数的概念。,增加单位产品乙（x2）比甲对目标函数的贡献大（检验数最大），把非基变量x2换成基变量，称x2为换入基变量，而把基变量x5换成非基变量，称x5为换出基变量。（在选择出基变量时，一定保证消去系统为正消去系统）（最小比值原则）,增加单位产品甲（x2）比乙对目标函数的贡献大（检验数最大），把非基变量x2换成基变量，称x2为换入基变量，而把基变量x5换成非基变量

39、，称x5为换出基变量。（在选择出基变量时，一定保证消去系统为正消去系统）（最小比值原则）事实上，当x1=0，有x3=8-2x20 x4=160（）x5=12-4x20min(8/2,-12/4)=3,当x2=0时，x5=0。x5换出基变量。,确定了换入变量x2，换出变量x5以后，得到新的消去系统：x3+2x2=8-x1（1）x3=2-x1+（1/2）x5x4=16-4x1（2）()即：x4=16-4x14x2=12-x5（3）x2=3-（1/4）x5其中（1）1/2（3）S=92x1-（3/4）x5令新的非基变量（x1，x5）=（0，0）T得到新的基础可行解：x(2)=(0,3,2,16,0)

40、TS2=9经济含义：生产乙产品3个，获得利润9百元。,这个方案比前方案好，但是否是最优？,这个方案比前方案好，但是否是最优？分析：S=92x1-（3/4）x5非基变量x1系数仍为正数，确定x1为换入变量。在保证正消去系统的情况下，确定x3为换出变量。得到新的消去系统：,这个方案比前方案，但是否是最优？分析：S=-180-x2+（3/2）x4非基变量x2系数仍为负数，确定x2为换入变量。在保证常数项非负的情况下，x1换入，x5=0。有x3=2-x10 x4=16-4x10()x2=30min2,4,-=2确定x3为换出变量。得到新的消去系统：,x1=2-x3+（1/2)x5x1=2-x3+（1/

41、2)x54x1+x4=16（）即x4=8+4x3-2x5x2=3-(1/4)x5x2=3-(1/4)x5S=13-2x3+（1/4）x5令新的非基变量（x3，x5）=（0，0）T得到新的基础可行解：x(3)=(2,3,0,16,0)TS3=13经济含义：生产甲产品2个，乙产品3个，获得利润1300元。,分析：S=13-2x3+（1/4）x5x5系数仍为正数，确定x5为换入变量。在保证常数项非负的情况下，x5换入，x3=0。有x1=2+（1/2）x50 x4=8-2x50()x2=3-（1/4）x50min-,4,12=4确定x4为换出变量。有x1-（1/2）x5=2-x32x5=8+4x3-x

42、4x2+（1/4）x5=3,即：x1=4-（1/4）x4x5=4+2x3-（1/2）x4（）x2=2-（1/2）x3+（1/8）x4S=14-（3/2）x3-（1/8）x4得到新的消去系统目标函数中的非基变量的系数无正数，S4=14是最优值，x(4)=(4,2,0,0，4)T是最优解。该企业分别生产甲产品4个，乙产品2个可获得利润1400元。,x2,50,40,30,20,10,x1,maxS=2x1+3x2s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x50,Q1,Q2X4,X2Q4,X1O,X3Q3,4x2=12,4x1=16,x1+2x2=8,

43、X1（0，0），X2（0，3）X3（2，3），X4（4，2）,二、已知初始可行基求最优解线性规划标准型的矩阵形式(3)：MAXS=CX(1-17)s.t.AX=b(1-18)X=0(1-19),a11a12.a1nb1A=a21a22.a2nb=b2am1am2.amnbn,c1x10c2x20Ct=X=0=xn0并且r(A)=mn.,1.最优解判别定理：不妨假设A=（B,N）（B为一个基）相应地有XT=(XB,XN)C=(CB,CN)由（1-17）（1-18）Z=(CB,CN)(XB,XN)T=CBXB+CNXNAX=（B,N）(XB,XN)T=BXB+NXN=b,因为B为一个基,|B|0有

44、XB=B-1b-B-1NXNZ=CBXB+CNXN=CBB-1b+(CN-CBB-1N)XN令非基变量XN=0则X=(XB,XN)T=（B-1b,0）T为基础解，其目标函数值为S=CBB-1b只要XB=B-1b=0,X=（B-1b,0)T=0X为基础可行解,B就是可行基。,另外，若满足CN-CBB-1N0或CBB-1N-CN0则对任意的x=0有S=CXCBB-1b即对应可行基B的可行解x为最优解。,定理（最优解判别准则）对于可行基B,若C-CBB-1A0则对应于基B的基础可行解x就是基础最优解，此时的可行基就是最优基。=C-CBB-1A为检验数。基变量的检验数：CB-CBB-1B=0C-CBB

45、-1A=（0，CN-CBB-1N）,换入基变量中，得到基可行解,定理：若检验数全小于等于零，且某一个非基变量的检验数为0，则线性规划问题有无穷多最优解。（无穷多最优解情况）证明：某个非基变量,为最优解。故线性规划问题有无穷多最优解。,为一基可行解，有一个变量Xm+k对应,因,为可行解。,定理：若存在检验数大于零，但所对应的换入变量Xm+k的系数向量Pm+k0,则原问题无最优解。（无界解的情况）证明：,构造一个新的解，分量为,定理：若非基变量检验数严格小于零，则线性规划问题有唯一最优解。,定理：若检验数全小于等于零，且某一个非基变量的检验数为0，则线性规划问题有无穷多最优解。,定理：若某一个非基

46、变量的检验数大于0，其系数列向量Pm+k0,则原问题无最优解。（无界解的情况）,线性规划为求最大化的标准型：,线性规划为求最小化的标准型时，相应的结果？,单纯形表：T（B）=B-1bB-1ACBB-1bC-CBB-1A=B-1bIB-1NCBB-1b0CN-CBB-1N注意：A=（B，N）,检验数=C-CBB-1A=（0，CN-CBB-1N）非基变量检验数=CN-CBB-1N,时,达到最优。,单纯形表格：,单纯形解题步骤：（已知初始可行基）求最大化时一、作对应B的单纯形表：T（B）=B-1bB-1ACBB-1bC-CBB-1A=B-1bIB-1NCBB-1b0CN-CBB-1N,单纯形解题步骤

47、：二、判别若检验数全小于等于零，则基B所对应的基础可行解X就是最优解，终止。若存在检验数大于零，但所对应的换入变量Xk的系数向量Pk0,则原问题无最优解，终止。若存在检验数大于零，且对应的系数列有大于零的分量，则需要换基迭代。,三、换基迭代确定换入变量Xk，其中max(j0)=k,xk为换入变量j=1,2,m确定换出基变量Xr,根据最小比值原则min(bi/aik,aik0,1im)=bl/blkalk为主元素,Xl为换出基变量。,对单纯形表T（B）进行初等行变换（主元运算）得到新的单纯形表。经过上述有限次的换基迭代，就可得到原问题的最优解，或判定无最优解。,例1-19求线性规划问题：maxS

48、=2x1+3x2s.t.x1+2x2=0,解：对目标函数标准化maxS=2x1+3x2s.t.x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3,x4,x5=012100A=4001004001（x1x2x3x4x5）=（NB）,解：100B=010=Ib=(8,16,12)T001x3x4,x5为基变量，CB=（0，0,0）x1,x2为非基变量。有B-1=I,B-1b=b,B-1A=A,单纯性表如下：,初始单纯性表TAB(1)为：,x2换入,x5换出；得TAB(2)为：,x1换入,x3换出；得TAB(3)为：,x5换入,x4换出；得TAB(4)为：,此时所有的检验数小

49、于等于零，此时的基础可行解X=（4，2，0，0,4）T就是最优解，对应的目标函数值：S=14就是最优值，对应的B4就是最优基。,求最大化LP问题单纯形表解题步骤：一.LP问题化成标准型,列初始单纯形表,二.判别1.若检验数全小于等于零，则基B所对应的基础可行解X就是最优解，终止。2.若存在检验数大于零，但所对应的换入变量Xk的系数向量Pk0,则原问题无最优解，终止。3.若存在检验数大于零，且对应的系数列有大于零的分量，则需要换基迭代。,三.换基迭代1.确定换入变量Xk，其中max(j0)=k,xk为换入变量j=1,2,m2.确定换出基变量Xr,根据最小比值原则min(bi/aik,aik0,1

50、im)=bl/blkalk为主元素,Xl为换出基变量。,对单纯形表T（B）进行初等行变换（主元运算）得到新的单纯形表。经过上述有限次的换基迭代，就可得到原问题的最优解，或判定无最优解。,定理（求最小化的最优解判别准则）（1）若=C-CBB-1A0，则对应于基B的基础可行解x就是基础最优解，此时的可行基就是最优基。（2）若检验数全大于等于零，且某一个非基变量的检验数为0，则线性规划问题有无穷多最优解。（无穷多最优解情况）（3）若存在检验数小于零，但所对应的换入变量Xm+k的系数向量Pm+k0,则原问题无最优解。（无界解的情况）确定换入变量时，找小于0中的最小者。,例8线性规划问题,一.大M法,当原问题求最大化时，假定人工变量在目标函数中的系数为（-M）（M为任意大正数），目标函数求最大化，必须把人工变量从基变量换出，否则，不可能实现最大化。,当原问题求最小化时，假定人工变量在目标函数中的系数为M（M为任意大正数），目标函数求最小化，必须把人工变量从基变量换出，否则，不可