线性规划（1）课件

线性规划（1）,线性规划概念及解的性质,1、线性规划概论,线性规划（Linear Programming)创始人： 1947年美国人G.B.丹齐克（Dantzing） 1951年提出单纯形算法（Simpler） 1963年Dantzing写成“Linear Programming and Extension” 线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。,1-1 线性规划基本概念,线形规划模型是对一个线形的目标函数在若干个线形约束条件下进行的最优化处理. 通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标； 或企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多 、利润最大）。,问题提出,胜利家具厂生产桌子和椅子两种家具。桌子科获得利润50元/个，椅子销售可获得利润30元/个，生产桌子和椅子要求需要木材和油漆两种资源。生产一个桌子需要木材4立方分米，油漆2公斤。生产一个椅子需要木材3立方分米，油漆工1公斤。该厂目前拥有木材120立方分米，油漆50公斤。问该厂如何组织生产才能获得最大利润？,解：将一个实际问题转化为线性规划模型有以下 几个步骤： 1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量 2确定目标函数：家具厂的目标是销售收入最大 max z=50x1+30x2 3确定约束条件： 4x1+3x2120（木工工时限制） 2x1+x2 50（油漆工工时限制） 4变量取值限制： 一般情况，决策变量只取正值（非负值） x1 0, x2 0,数学模型 max S=50x1+30x2 s.t. 4x1+3x2 120 2x1+ x2 50 x1,x2 0 线性规划数学模型三要素： 决策变量 约束条件 目标函数,线性规划数学模型的特征 1解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或 最小值； 2解决问题的约束条件是一组多个决策变量的线性不等式或等式。,1-2 几类典型的线性规划模型,生产计划问题 运输问题 合理下料问题 配料问题 人员安排问题 投资问题,例1：生产计划问题,某工厂计划生产甲、乙两种产品。所需的设备台时及A、B两种原材料消耗，详见下表,该工厂每生产一件甲产品可获利2元，每生产一件乙产品可获利3元，问如何安排生产计划，可使利润最大？,解： 设x1，x2分别为甲、乙产品的数量，则有 目标函数 max z=2x1+3x2 约束条件 x1 + 2x28 4x1 16 4x212 x10，x20 称x1，x2为决策变量,例2：运输问题,现有A、B两个产地；1、2、3三个销地，各个产地的产量、各个销售地的销量以及各个产地到销售的运价如下 表，问如何安排调运，运费最小？,注：表中（ ）中数字表示运价,解：设 xij为从产地运往销地的物资数量 (i=1,2；j=1,2,3), 则有 目标函数： min z=2 x11+x12+3 x13+2x21+ 2x22+4x23 约束条件: x11+x12+ x13 = 50 x21+ x22+x23 = 30 x11+ x21 =40 x12+ x22 =15 x13+ x23 =25 xij0 i=1,2；j=1,2,3,现要做100套钢架，每套用长为2.9m，2.1m和1.5m的元钢各一根。已知原料长7.4m，问应如何下料，使用的原材料最省。,例3：合理利用线材问题,解：最简单做法是，在每一根原材料上截取 2.9m，2.1和1.5m的元钢各一根组成一套，每根原材料省下料头0.9m，为了做100套钢架，需用原材料100根，有90m料头。 若改为用套裁，这可以节约原材料，下面有几种套裁方案，都可以考虑采用。 见表111。,为了得到100套钢架，需要混合使用各种下料方案。 设按I方案下料的材料根数为x1，II方安为x2，III方案为x3，IV方案为x4，V方案为x5。根据表111的方案，可列出以下数学模型：,例4：营养配餐问题,假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？,各种食物的营养成分表,解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为： Min S=14x1+6x2 +3x3+2x4 s.t. 1000x1+800x2 +900x3+200x4 3000 50x1+ 60x2 + 20x3+ 10x4 55 400x1+200x2 +300x3+500x4 800 x1，x2 ， x3 ， x4 0,例5：人员安排问题,某商场决定：营业员每周连续工作5天后连续休息2天，轮流休息。根据统计，商场每天需要的营业员下表所示。商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。,【解】 设xj(j=1，2，7)为休息2天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为,例6：投资问题,某投资公司拟将5000万元的资金用于国债、地方国债及基金三种类型证券投资，每类各有两种。每种证券的评级、到期年限及每年税后收益率下表决策者希望：国债投资额不少于1000万，平均到期年限不超过5年，平均评级不超过2。问每种证券各投资多少使总收益最大。,解 ：设xj(j=1,2,，6)为第j种证券的投资额，目标函数是税后总 收益为,资金约束：,国债投资额约束：,平均评级约束：,平均到期年限约束：,整理后得到线性规划模型,1.2 线性规划的标准形式,规定线性规划的标准形式 把各种形式的线性规划写成标准形式。,线性规划问题的一般形式： Max(Min)S=c1x1+c2x2+cnxn s.t. a11x1+a12x2+.+a1nxn (=, )b1 a21x1+a22x2+.+a2nxn (=, )b2 . am1x1+am2x2+.+amnxn (=, )bm x1,x2.xn 0,线性规划问题的标准形式(1)： Max S=c1x1+c2x2+cnxn s.t. a11x1+a12x2+.+a1nxn=b1 a21x1+a22x2+.+a2nxn=b2 . am1x1+am2x2+.+amnxn=bm x1,x2.xn 0 其中：bi 0(i=1,2,.m),线性规划问题的标准形式(2)： Max S = s.t. xj 0 (j=1,2,.n),线性规划标准型的矩阵形式(3)： Max S = CX s.t. AX=b X 0,a11 a12 . a1n b1 A= a21 a22 . a2n b = b2 . am1 am2 . amn bn,c1 x1 0 c2 x2 0 CT= X= 0 = cn xn 0,如何将一般问题化为标准型： 1、若目标函数是求最小值 Min S = CX 令 S= - S, 则 Max S=- CX 2、若约束条件是不等式 若约束条件是“”不等式,yi 0是非负的松驰变量 如2x1+ 3x26 可写成2x1+ 3x2 + x3=6,3、若约束条件是“”不等式,zi 0是非负的剩余变量 如 2x1+ 3x26 可写成2x1+ 3x2 - x3=6,4、若约束条件右面的某一常数项 bi0 这时只要在bi相对应的约束方程两边乘 上-1。 5、若变量 xj自由变量 引进两个非负变量xj xj 0 令xj= xj- xj（可正可负）,6、决策变量xj有上下界限制。 引进新的变量，使其等于原变量减去下限值，则下限为零。 如axkb,用 xl=xka, 则有0 xlb-a。 用新的变量xl替换目标函数和约束条件中所有的原变量xk，再将上限约束列为新的约束条件并化为等式。,例1：将下列问题化成标准型: Min S = -x1+2x2-3x3 s.t. x1+x2+x3 7 x1-x2+x3 2 -3x1+x2+2x3 = 5 x1,x2 0 x3 无非负限制,Max S = x1-2x2+3x3 -3x3 s.t. x1+x2+x3 -x3 +x4 =7 x1-x2+ x3 -x3 -x5=2 -3x1+x2+2x3 -2x3 =5 x1, x2 , x3 ，x3 , x4，x5 0,例如：将下列线性规划问题化成标准型 max Z= x1+ 2 x2 + 4 x3 2x1+x2+3x3=20 s.t 3x1+x2+4x3=25 x1, x20, 2x36,解：以x4=x3-2代入，问题化为 max Z= x1+ 2 x2 + 4 x4 + 8 2x1+x2+3x4=14 s.t 3x1+x2+4x4=17 x4 4 x1, x2 , x4 0 再把约束x4 4化为等式即可得到标准形式。,标准形式为 max Z= x1+ 2 x2 + 4 x4 + 8 2x1+x2+3x4 =14 s.t 3x1+x2+4x4 =17 x4+x5 =4 x1, x2 , x4 ，x5 0,1-3 线性规划解的概念,（1）满足约束条件的变量值，称为 可行解。 （2）使目标函数取得最优值的可行 解，称为最优解。,1、线性规划问题图解法,1、图解法的步骤： （1）约束区域的确定 （2）目标函数等值线 （3）平移目标函数等值线求最优值 2、图解法的作用： 图解法不是解线性规划的主要方法,只是用于说明线性规划解的性质和特点。只能解两个变量问题。（用图解法求解,线性规划不需要化成标准型）,例1：用图解法解线性规划,max S =50x1+30x2 s.t. 4x1+3x2 120 2x1+x2 50 x1 , x2 0,x2,50,40,30,20,10,10,20,30,40,x1,4x1+3x2 120,由 4x1+3x2 120 x1 0 x2 0 围成的区域,x2,50,40,30,20,10,10,20,30,40,x1,2x1+x2 50,由 2x1+x2 50 x1 0 x2 0 围成的区域,x2,50,40,30,20,10,10,20,30,40,x1,2x1+x2 50,4x1+3x2 120,可行域,同时满足： 2x1+x2 50 4x1+3x2 120 x1 0 x2 0 的区域可行域,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作为参数的一组平行线 x2 = S/30-（5/3）x1,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（目标函数）值达到最大： Max S=5015+30 20=1350 此时最优解=（15，20）,Q2（15，20）,二个重要结论： 满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。 最优解必定能在凸多边形的某一个顶点上取得，这一事实也可以推广到更多变量的场合。,解的讨论： 1、最优解是唯一解； 2、无穷多组最优解： 若例1的目标函数由 max S=50x1+30x2 变成： max S=40x1+30x2 s.t. 4x1+3x2 120 2x1+ x2 50 x1,x2 0,x2,50,40,30,20,10,10,20,30,40,x1,可行域,目标函数是同约束条件：4x1+3x2 120平行的直线 x2 = S/30-（4/3）x1,x2,50,40,30,20,10,10,20,30,40,x1,可行域,当S的值增加时，目标函数同约束条件：4x1+3x2 120 重合，Q1与Q2之间都是最优解。,Q1（25，0）,Q2（15，20）,3、无界解： 例： max S=x1+x2 s.t. -2x1+x2 40 x1 - x2 20 x1,x2 0,x2,50,40,30,20,10,10,20,30,40,x1,该可行域无界，目标函数值可增加到无穷大，称这种情况为无界解或无最优解。,约束条件围不成区域 (又称矛盾方程),4、无可行解,例4：,解的情况： 1、有可行解 （1）有唯一最优解 （2）有无穷最优解 （3）无界解 2、无可行解,1.4 线性规划问题解的概念,设线性规划的标准型 max Z=CX （1.1） AX=b （1.2） X 0 （1.3） 式中A 是mn矩阵，mn并且r（A）=m，显然A中至少有一个mm子矩阵B，使得,线性规划解的几个基本概念,基 基向量、非基向量 基变量、非基变量 基解 基可行解 可行基、非可行基 基最优解 最优基,基：A是约束方程组的系数矩阵（mn维），若B是A中的一个mm子矩阵，并且B的行列式不为零（|B|0），则称B是线性规划的一个基（或基矩阵basis matrix ）。当子矩阵B的行列式等式为零,即|B|=0时,该子矩阵就不是基。 当m=n时，基矩阵唯一，当mn时，基矩阵就可能有多个，但数目不超过,例1 :线性规划,求所有基矩阵。,【解】约束方程的系数矩阵为24矩阵,容易看出r(A)=2，2阶子矩阵有C42=6个,由计算可知，该六个子矩阵的行列式的值均不为零，因此该线性规划有六个基（或六个基矩阵）。,基向量、非基向量：当确定某一子矩阵为基矩阵时，则该基矩阵对应的列向量称为基向量，其余列向量称为非基向量 。,基变量、非基变量：基向量对应的变量称为基变量；非基向量对应的变量称为非基变量 。,例如:B3的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基变量，x2、x3是非基变量。,B1的基向量是A中的第一列和第二列，其余列向量是非基向量，x1、x2是基变量，x3、x4是非基变量。基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。,基解: 对某一确定的基B，令非基变量等于零，则可以用联立方程解出基变量，则这组解称为基的基解。 解得 基解1 解得 基解2 解得 基解3 解得 基解4 解得 基解5 解得 基解6,基可行解: 若基解中各个变量均大于0，则称为基可行解。 上述6个基解中 为基可行解。 为可行基. 为非基可行解。 为非可行基,基最优解: 使目标函数达到最优值的基可行解,称为 基最优解。对应的基矩阵为最优基矩阵. 上述4个基可行解对应的目标函数值为: Z=1350 Z=1250 Z=1200 Z=0 可见 为基最优解. 为最优基.,注意: 当最优解唯一时，最优解亦是基最优解，当最优解不唯一时，则最优解不一定是基最优解。例如右图中线段 的点为最优解时，Q1点及Q2点是基最优解,线段 的内点是最优解而不是基最优解。,例1 max S =50x1 + 30x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1,x2 0,基解的图形表示,x2,80,60,40,20,20,40,60,80,x1,O,-20,-20,-40,-40,-60,-60,2x1+x2=50,4x1 + 3x2=120,A,Q1,Q2,Q3,Q4,B,Q5,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,80,60,40,20,20,40,60,80,x1,O,-20,-20,-40,-40,-60,-60,2x1+x2=50,4x1 + 3x2=120,A,Q1,Q2,Q3,Q4,B,Q5,x2,80,60,40,20,20,40,60,80,x1,O,-20,-20,-40,-40,-60,-60,2x1+x2=50,4x1 + 3x2=120,A,Q1,Q2,Q3,Q4,B,Q5,约束条件： 4x1+3x2 =120 2x1+x2 =50 与坐标系 x1,x2 交点Q1，Q2，Q3，Q4 坐标原点为o, 两直线交点为Q5都是代表基础解 坐标分别为: Q1(25,0) Q2(0,40) Q3(30,0) Q4(0,50) O (0,0) Q5(15,20) 注意：Q3(40,0),Q4(0,25)不满足约束条件,故不是可 行解.,本问题解的情况： 基础解：点（O，Q1，Q2，Q3，Q4， Q5 ） 可行解：由点（O，Q1，Q2，Q5）围成的区域 基础可行解：点（O，Q1，Q2，Q5） 最优解：Q5,解的集合：,非可行解,可行解,解的集合：,可行解,基础解,基础最优解,基础可行解,1.4 线性规划解的性质（几何意义）,凸集概念： 设D是n维线性空间Rn的一个点集，若D中的任意两点x(1),x(2)的连线上的一切点x仍在D中，则称D为凸集。 即：若D中的任意两点x(1),x(2) D，存在01 使得 x= x(1)+(1- )x(2) D,则称D为凸集,两点间任一点的向量表述形式,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) ) (0 1),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) ) (0 1),两点间任一点的向量表述形式,例1（凸集）,例2：非凸集,例3：（凸集性质） 二个凸集的交还是凸集,二个凸集的并不一定是凸集,两个基本概念： 1、凸组合： 设x(1),x(2) x(k)是n维线性空间Rn中的k个点，若存在数u1,u2,.uk 且0 ui 1 (i=1,2,k), ui =1, 使得 x= u1x(1)+ u2x(2) + ukx(k) 成立，则称x为x(1),x(2) x(k)的凸组合。,2、顶点 设D是凸集, 若D中点x 不能成为D中任何线段上的内点，则称x为凸集D的顶点。 即：若D中的任意两点x(1),x(2) ，不存在数 （0 1） 使得 x= x(1)+(1- )x(2) 成立，则称x为凸集D的一个顶点。,例4：多边形上的点是顶点,圆周上的点都是顶点,1.5 线性规划的基本定理,定理1：线性规划问题的可行解集是凸集。（即连接线性规划问题任意两个可行解的线段上的点仍然是可行解。),设x(1)x(2)为D内任取两点，则Ax(1)=b,Ax(2)=b,x(1) 0, x(2) 0,令x为线段x(1) ,x(2)上任一点,既有 x=x(1)+(1-)x(2) (01) 则 Ax=Ax(1) + (1-) x(2) (01) =Ax(1)+Ax(2)-Ax(2) =b+bb=b 又因为 x(1) 0, x(2) 0, 01 所以 x 0 即 xD 证毕,证明：线性规划 max z =CX s.t AX=b X0,定理2： X是线性规划问题的基可行解的充要条件是它对应于可行域D的顶点。,证明：不失一般性，假设基可行解X的前m个分量为正。故 (1)充分性(用反证法）： 若X不是基可行解，则它一定不是可行域D的顶点 由引理1，若X不是基可行解，则其正分量所对应的系数列向量P1,P2,Pk线性相关,即存在一组不全为零的数i,i=1,2,m,（1）,令X(1)=(x1-1),(x2-2), ,(xm-m),0, ,0 X(2)=(x1+1),(x2+2), ,(xm+m),0, ,0 由X(1), X(2) 可以得到 X= ,即X是X(1),X(2)连线的中心. 另一方面,当充分小时,可保证xii0 i=1,2, ,m,即X(1), X(2)是可行解,所以X不是可行域D的顶点.,使得1P1+ 2P2+ +mPm=0 （2） 用一个0的数乘（2）式在分别与（1）相加和相减，这样得到 (x1-1)P1+(x2-2)P2+(xm-m)Pm=b (x1+1)P1+(x2+2)P2+(xm+m)Pm=b,必要性（用反证法）： 若X不是可行域D的顶点，则它一定不是基可行解。 X不是可行域的顶点,故可在可行域内找到两个不同的点x(1),x(2)，使得 x=x(1)+(1-)x(2), 01 由于x(1),x(2)是可行域的两点，应满足：Pjxj(1)=b Pjxj(2)=b 将这两式相减,即得 Pj(xj(1)-xj(2)=0 因X(1)x(2),所以上式系数(xj(1)-x