Chapter01.线性规划及单纯形法.ppt

黑龙江大学数学科学学院 信息与计算数学系 All rights reserved,第1章 线性规划及单纯形法,姚明臣 2011年3月,2,2019/6/4,本次课程要求掌握的内容,会建立简单的线性规划问题的数学模型； 理解并记忆线性规划模型的各种形式； 分量形式 向量形式 矩阵形式 会将一般线性规划模型化成标准型； 有关线性规划问题解的若干重要概念 可行解、最优解、基、基(本)解、基可行解等。 熟练掌握含两个决策变量问题的图解法； 凸集的相关概念和单纯形法若干基本定理。,3,2019/6/4,1 线性问题的数学模型,问题的提出 例1. 用一块边长为a的正方形铁皮做一个容器，应如何裁剪，才能使做成容器的容积最大？,a,x,解：利用高等数学的知识 V=(a - 2x)2 x 求 V(x) 的最大值即可。 问题？,4,2019/6/4,线性规划的数学模型,问题的提出 例2 (生产计划安排，要求利润最大),解：设在计划期内生产产品I和产品II分别为x1和x2件(决策变量) 目标是要使 z = 2 x1 + 3 x2达到最大。(目标函数) 限制条件是： （约束条件） 2x1 + 2x2 12 和 2x1 16 以及 5x2 15 要求 x1, x2 0,5,2019/6/4,线性规划的数学模型,问题的提出 例子之三(合理下料问题) 现有一批10m长的贵重钢筋，需要截取3m和4m长的钢筋各50根，试问如何截取，才能使原料最省？ 问题分析： 先确定截取方案 建立数学规划模型,问题：模型是否有别的形式？,6,2019/6/4,线性规划问题数学模型的定义,线性规划模型组成的三要素： 决策变量 目标函数 约束条件 定义1 在线性规划数学模型中，如果决策变量为可控的连续变量，目标函数和约束条件都是线性的，称这类模型为线性规划问题的数学模型。 问题：例一中的问题是否为线性规划模型？,7,2019/6/4,线性规划问题数学模型的一般形式,关于幻灯片中的数学符号： 小写斜体字母表示实数，如a,b,c,x,x1,y,z等 小写黑体字母表示向量，如x,y,z等 大写黑体字母表示矩阵，如 A, B,C等 线性规划(LP)数学模型的一般形式,或,8,2019/6/4,线性规划数学模型向量和矩阵形式,(LP)向量形式 (LP)矩阵形式,9,2019/6/4,线性规划问题的标准形式,什么是(LP)问题的标准形式？ 满足如下条件： 目标函数是求极大值； 约束条件全为等式； bi和xj全为非负数。,10,2019/6/4,(LP)一般形式向标准形式的转化,(LP)一般形式向标准形转化的情况： 目标函数是求极小值； 约束条件为不等式“”的情形（松弛变量，例2）； 约束条件为不等式“” 的情形（剩余变量，例3）； 取值无约束的变量； 某个变量 xj 0 问题：某个变量有上下界限制，比如l xj u，如何处理？ 例3. 见书P12。,11,2019/6/4,线性规划问题解的若干重要概念,线性规划问题的任务 从满足约束条件（2）和非负条件（3）的方程组中，找到使目标函数（1）取得最大值的解。,可行解和可行域 满足约束和非负条件的解x。 最优解 基、基向量、基变量 设A=(aij)mn，r(A) = m，称A的一个m阶满秩子矩阵B称为(LP)问题的的一个基。 基解 由基矩阵B确定的m个基变量，并上非基变量取0的解。 基(本)可行解 同时是可行解的基解。 可行基,12,2019/6/4,利用初等变换求基可行解,例4. 教材14页，列出(LP)问题的全部基，基解、基可行解并指出最优解。 问题: I) 如何判断一个解是基可行解； II）表1-1中为何少了两行？ 利用p1,p2, p4 求基解的过程,13,2019/6/4,2 图解法求最优解,什么时候用图解法？ (LP)模型仅含两个决策变量。 求解方法和根据： 根据约束画出求解区域，一般为第一象限的凸多边形 (有界或无界)，标记出顶点坐标； 求目标函数的梯度：设目标函数是 z=c1x1+c2x2，则 n = grad z = (c1,c2) 为等值线c1x1+c2x2= h的法线方向，沿n的方向函数值增加的最快，沿-n方向函数值减少的最快。 移动等值线 c1x1+c2x2= h 在区域顶点或边界达到最大最小值。 书中的方法是把目标函数z当做参数处理。,14,2019/6/4,一般情况求解区域的确定,约束一般都可化成 ax1+bx2+c = 0 (a 0，b 0)的形式特殊情形？,15,2019/6/4,一个用图解法求极值的例子,用图解法求如下线性规划问题的极值。,最大值点 x* = (1,4), Zmax = 3；最小值点 x* = (4,1), Zmin = 3；,A(2,0),B(4,1),C(1,4),D(0,2),16,2019/6/4,图解法的其他情形 无穷多最优解,无穷多最优解(书，P16，见下图) 问题1：什么情况下发生？,问题2：这个最优解如何表示？,17,2019/6/4,图解法的其他情形 无界解(无最优解),求下面规划问题的最优解。,问题1：如果目标函数是求极大，是否有最优解？ 问题2：能否定量说明 z 是无下界的？,18,2019/6/4,图解法的其他情形 无可行解,求下面规划问题的最优解。,19,2019/6/4,3 单纯形基本原理 预备知识,凸集 定义1.1：如果集合C中任意两点x(1)，x(2)，其连线上的所有点也在集合C中，即对任何x(1)C， x(2)C，01，都有 x(1)+(1) x(2) C，则称C为凸集。,顶点 定义1.2：如果凸集C中不存在任何两个不同的点x(1)、x(2) ，使x成为x(1)和x(2)连线上的某个点，这样的x称为C的顶点。 （问题：书上的数学描述是否妥当？）,20,2019/6/4,单纯形法的基本定理,定理1.1 若(LP)问题有可行解，则问题的可行域为凸集。 利用凸集的定义，结合LP的矩阵形式P8证明。 引理1.1 (LP)问题可行解x为基可行解的充要条件是x的非零分量所对应的系数列向量是线性独立的。 利用基可行解的定义证明。 定理1.2 (LP)问题的可行解x是可行域(凸集)顶点的充要条件是x为一个基可行解。 利用分块矩阵的形式，结合引理1.1利用反证法 (较长,最后证)。,21,2019/6/4,引理1.1的证明,引理1.1 (LP)问题可行解x为基可行解的充要条件是x的非零分量所对应的系数列向量是线性独立的。 证明：充分性 设x为一可行解，不妨设其非零分量(正分量)为前k个，即x = (x1 , x2 , , xk , 0,0)T， xi 0 (1 i k), 若x是基可行解，则必有 k m(为什么？)，由可行基的定义，部分向量组 p1,p2, ,pk 必线性无关。 必要性 若x为可行解(同上假设)，其对应系数列向量 p1,p2, ,pk 线性独立(无关)，同样 k m (为什么？)。 (1)、若k = m, 则 p1,p2, ,pk 刚好构成一个基矩阵，而x = (x1 , x2 , , xk , 0,0)T为对应基可行解。 (2)、若k m ，则可以利用p1,p2, ,pk构造一个基，因为rank(A) = m, 从pk+1,p2, ,pn中必可以选出mk列，和p1,p2, ,pk共同组成一个基，这样一定可以办到(为什么？) ，其对应基解恰为x。这样的x称为退化的基可行解。,22,2019/6/4,单纯形法的基本定理 凸组合性质,凸组合 定义1.3 设x(1), x(2) , x(m)是En中的m个向量， 而1, 2, , m是满足1+ 2+ + m=1，i0的m个实数，称向量x = 1x(1)+ 2 x(2) + + m x(m)为x(1), x(2) , x(m)的凸组合。 问题：凸组合和普通线性组合有什么区别？ 引理1.2 En中的点集为凸集的充要条件是对任何正整数m, 中任意m个点x(1), x(2) , x(m)的凸组合x都在内。 充分性：利用定义证凸集；必要性：数学归纳法+凸集定义。,23,2019/6/4,单纯形法的基本定理 - 顶点表示定理,引理1.3 设(LP)问题的可行域C有界，则任何可行解xC都可以表示成C的顶点的凸组合。 (证明略，图解示意，考虑x的三种情况：顶点、边界点和内点),24,2019/6/4,一个顶点表示的例子,例 设x是三角形中任意一点， x(1), x(2) , x(3) 是三角形的三个顶点，试将x表示为x(1), x(2) 和x(3) 的凸组合。,解：连接x(1)和x交x(2) x(3) 于x，因三角形是凸集, x = x(1) + (1 ) x (1) x = x(2) + (1 ) x(3) (2) 0 , 1 (2)代入(1)得： x = x(1) + (1 ) x(2) + (1 ) (1 ) x(3) ， 验证组合系数之和为1即可。,25,2019/6/4,基可行解和最优解的关系,定理1.3 若(LP)问题有最优解，则一定存在一个基可行解是最优解。 定理的应用： 定理1.1 (可行域是凸集) 定理1.2 (凸集顶点对应基的可行解) 定理1.3 (某个基可行解是最优解) 证明思路： 设x* 是最优解，全部基可行解 x(1), x(2) , x(m)， 希望最优值在某个顶点x(k)达到，利用引理1.3建立x* 和x(1), x(2) , x(m)之间的关系，再利用最优解性质和不等式放缩证明即可。 问题：关于书上的证明?,26,2019/6/4,4单纯形法迭代求解的基本思想,27,2019/6/4,迭代法求解(续1),上述操作的实质是消元法 主元素的选取，进基和离基。,28,2019/6/4,迭代法求解(续2),问题：那个变量离基？,29,2019/6/4,迭代法求解(续3),迭代法小结： 先求得一个初始基可行解，一般要获得一个单位阵基； 判断获得的解是否是最优解，如判断目标函数中非基变量的系数； 如果不是最优解，按照消元法进行基可行解的转换； 重复和，直至求得最优解。,30,2019/6/4,第1次作业总结,首页写清专业+姓名+学号 （单页、草纸、背面！） 作业版本拷贝！ 基本概念不清晰 最优解和最优值。 如作业1.2（a）中，最优解 为 x(1)=(0,3,0,0,7/2,0)T, 和 x(2)=(0,0,3/2,0,8,0)T, 最优值为 z* = 3。 问题：参考图解法的(a)，利用x(1)和x(2)给出一个新最优解？,31,2019/6/4,一个求解所有基解的matlab程序(作业1.2),%BFS Bases Feasible solution by yaomingchen,2011.03.12 c = 3 1 2; % 目标函数系数 A = 12 3 6 3 0 0;8 1 -4 0 2 0;3 0 0 0 0 -1; % 约束矩阵 b = 9 10 0; % 右端项 m n= size(A);% 矩阵规模 MaxNumofBase = nchoosek(n,m); % 最大的基数量 comb = combntns(1:n,m); % 具体的列组合 for i = 1:MaxNumofBase % 对每个可能的基 x = zeros(1,n); % 解分量全赋0值 ploc = comb(i,:); % 基列的位置 B = A(:,ploc); % 取出A的作为基的各列 if rank(B)m-1 % 如果 r(B) = 3 Base = ; for j=1:m % 将B表示成（p1 p2 .pk）的形式 Base = Base,blanks(10), p,int2str(ploc(j); end disp(BASE = , Base); % 显示基是哪些列构成的 x(ploc)= Bb % 求 x_B 并放入基列位置 zvalue = c*x(1:m) % 计算最优值 end end,32,2019/6/4,初始基可行解的获得,设法构造一个初始单位阵基。 如果约束条件都是 “ ” 形式，化标准型直接获得； 如果约束条件是 “=” 或 “ ” 形式，采用人工变量法(稍后讲)。 不妨设(LP)标准形前m列是单位阵，即典型形式(典式)。,33,2019/6/4,最优解的判别 - 检验数,最优解的判别：用非基变量表示目标函数值。,34,2019/6/4,单纯形表的建立,B 基(变量)；CB - 基变量对应目标函数系数；b 右端项 检验数的计算： j= cj zj = cj (c1a1j+ c2a2j+ cmamj),35,2019/6/4,用单纯形表求解的例子(书p26.例5),化标准型,建立初始单纯形表，计算检验数；,确定进基变量，x2进基 (检验数最大);,确定离基变量，=min12/2,16/0,15/5 = 3，x5离基。 由主元a32确定。,36,2019/6/4,单纯形表上的迭代算法,0 1 0 0 1/5,3,3 x2,2 0 1 0 -2/5,6,2 0 0 0 -3/5,所有检验数非正，最优解 x*=(3,3,0,4,0)T，最优值 z*=15,第1次迭代：对主元所在行和列进行初等变换，并计算检验数。,第2次迭代：x1进基，x3离基，主元a12=2，消元并计算检验数。,2 x1,3,1 0 1/2 0 -1/5,0 x4,3 x2,4,0 0 -2 1 4/5,3,0 1 0 0 1/5,j=cj zj,0 0 -1 0 -1/5,37,2019/6/4,单纯形算法的一般形式,38,2019/6/4,单纯形算法的计算步骤,把(LP)化成标准形式，建立初始单纯形表； （一般能获得一个单位阵基作为初始可行基） 计算所有变量的检验数，若所有 j 0 (1 j n)，则当前解 x 即为最优解，迭代结束。否则转; 确定 k = maxj| j 0, 则xk待进基； 若所有aik 0, 则停止计算，(LP)无最优解，否则转； 计算 = minbi/aik | aik 0, 1 i m = bl /alk ,则xl离基； 以alk为主元,通过高斯消元法进行基可行解的转换，求得表中一新基可行解，转步骤。 (注：若在和中出现多个k或者l, 则按照自然顺序选择),39,2019/6/4,迭代一次之后的形式,40,2019/6/4,迭代前后解,函数值,检验数等的变化,41,2019/6/4,一个讲练的例子(大家参与),42,2019/6/4,最优性检验标准(),若所有 j 0 ( m+1 j n ),则x(k)为(LP)唯一的最优解。,设x(k)是最优解，有某个 r = 0 ( m+1 r n ),且存在air 0 (1 i m), 则 (LP)有无穷多最优解。,若有某个 j 0 ( m+1 j n ),但是 pj = (a1j, a2j, , amj) 0, 则(LP)无有限的最优解和最优值（无最优解）。,采用人工变量方法时(大M法和二阶段法)，满足最优条件时人工变量不为零，则原LP问题无可行解。,43,2019/6/4,5 人工变量法 问题的提出,如果原（LP）问题的约束全是“”号的形式，可以引入m个松弛变量xn+m，使得后m列自然形成初始单位阵基，再用单纯形法进行迭代求解。,如果原（LP）问题的约束是“”和“”号，或者三种符号（ 、 、 ）都有的的混合形式，且化成标准形式后约束矩阵不具备初始单位阵基，这时候怎么办？ 解决办法：自然的想法就是在标准形约束矩阵中，人工加入若干单位向量，(和已有的)形成初始单位阵基。,化标准型,44,2019/6/4,人工变量法 大M法,例6 求解如下线性规划问题(书P29),标准形中只有p4是单位向量？强行加入两列p6和p7 ，或者说在第2、3个约束上分别加入人工变量，即x6和x7。 人工变量的系数问题？目标函数中人工变量系数都取M (M 0 充分大)。,45,2019/6/4,用大M法求解 例6,检验数比较： 形式 aM+b 1. a 0, aM+b 0 2. a 0, aM+b 0 3. 若 0a1a2 则a1M+b1a2M+b2 此时可省略常数b,0 x2,0 x4,-M x7,3,3 0 2 1 1 -1 0,6,6 0 4 0 3 -3 1,6M 0 4M 0 3M -4M 0,46,2019/6/4,用大M法求解 例6（续）,x*=(0,5/2,3/2,0,0,0,0)T, z*=3/2 .,47,2019/6/4,大M法的理论分析,对标准形式的 (LP) 问题，设约束矩阵无单位阵基，令 xk=(xn+1, xn+2, xn+k)T, (k m), 则大M法是求解：,48,2019/6/4,大M法的理论分析,49,2019/6/4,一个无可行解的例子(P18, P42),单纯形表的迭代过程：,人工变量x5 = 1 0 ,由定理5.1,原问题无可行解。,50,2019/6/4,人工变量法 两阶段方法,大M方法的缺点：带有非数值符号M，不方便计算。 什么是两阶段方法？ 和大M方法一样，同样引入人工变量xT=(xn+1, xn+2, xn+k)T, (k m)，并设 e=(1,1,1) ,构造一新的线性规划问题（TP，Two-Phase Programming）,两阶段方法的计算步骤： 引入人工变量并构造新的(TP)问题：目标函数中原决策变量系数全取0，人工变量系数皆取1，且目标函数求极小)； 第一阶段，求(TP)问题的最优解(一般xT=0),同时得到原(LP)问题的基可行解(未必最优)； 第二阶段，删除(TP)最终单纯表中人工变量列，利用第一阶段的得到的基可行解，以及原(LP)的目标函数继续迭代求解。,51,2019/6/4,两阶段方法求解的例子(习题1.1a),约束化等式,构造TP问题,52,2019/6/4,第一阶段 :求解TP问题,x*=(3/4,1/2,0,0,0,0)T,2 3 0 0,53,2019/6/4,第二阶段：求原LP问题,因为c4z4 =3/2 0 但p4 =(-1/2,-3) 0 故原LP无最优解。 本幻灯片42页。,54,2019/6/4,原问题如果是求极小(无穷多最优解),因为求极小，所有检验数非负停止迭代； 继续迭代可得到另外一个最优解。,55,2019/6/4,两阶段方法的理论分析（情况1）,首先若(LP)有可行解，(TP)问题一定有最优解？ 这是因为 e = (1,.,1)T, 对任意xT 0, y = exT 0 有下界。 如 xT= 0 就是 (TP) 的一个最优解，但这个最优解未必能达到。,56,2019/6/4,两阶段方法的理论分析（情况2）,57,2019/6/4,情况2的例子,第一阶段的求解过程（注意求极小）：,58,2019/6/4,情况2的例子(续1),第一阶段的结果没有获得单位阵基，开始第二阶段：,0 0 -5 -2 1 2,0 1 0 1/2 0 1/2,-1 x1,0 0 -1 -1/2 0 1/2,x4,0 0 5/2 1 -1/2 -1,0 1 -5/4 0 1/4 1,1 0 -1 0 0 1,0 0 1/4 0 - -,59,2019/6/4,情况2的例子(续2),抛弃人工变量，继续迭代：,x*=(0,1,0)T, z*=1 .,60,2019/6/4,两阶段方法的理论分析（情况3）,61,2019/6/4,一个无可行解的例子(本幻灯片P49,和大M法关系),第一阶段的迭代过程：,人工变量x5 = 1 0 ,由情况3, 原问题无可行解。,62,2019/6/4,6 单纯形法的矩阵形式(),例 6.1 单纯形表迭代变化的实质（本幻灯片P44-46）,问题：B1对应最终单纯形表那些列，原来那些列是什么？,63,2019/6/4,矩阵形式的单纯形表,目标函数值： z = cBB1b 非基变量检验数： N= cN cBB1N 基变量检验数： B= cB cB = 0,记号： y = cBB1称为单纯形乘子。,I = B1B,B1N,B1b,B= 0,N= cN cBB1N,cBB1b,64,2019/6/4,例10. 确定B1,单纯形乘子y 和计算检验数（用矩阵形式）,确定B = ? B1 = ? 求B1b = ? 计算迭代后的p1和p3 确定单纯形乘子y = cBB1 计算x3和x5的检验数 计算目标函数值,65,2019/6/4,例11. 确定单纯形表中的未知量（大家参与）,如下表，给出了某线性规划问题计算过程中的一个单纯形表，目标函数为max z =28x4+x5+2x6, 约束条件全为 “ ”，表中x1, x2, x3为松弛变量，表中解的目标函数值为 z = 14。 （1）. 求 a g 的值； （2）. 求原约束矩阵的第五列p5。,66,2019/6/4,修正单纯形算法,为什么要引入修正单纯形算法？ 单纯形表每次迭代过程有m1列未发生变化 参见下2页； 单纯形表操作不适合大规模的LP问题计算。 迭代前后两个表中的基B和新基B的关系 问题1. 迭代前的基B是什么，B1是什么？ 问题2. 迭代后的新基B是什么？B1如何计算？ 两个基的逆之间的关系：(Bnew)1= (Blk) 1=ElkI=ElkB 1 推导两个逆矩阵之间的关系式 用原基的逆表示新基 表中其他量皆可以用B 1表示,67,2019/6/4,迭代之前,68,2019/6/4,迭代之后,69,2019/6/4,修正单纯形算法的计算步骤,对标准形式的LP问题，写出矩阵A, b 和 c; 确定初始单位阵基B (= I ),记录基向量下标集合 I 、非基变量集合 J和cB；计算xB=B1b. 计算单纯形乘子 y = cBB1, 并计算检验数N= cN yN ，若所有 j 0 (m+1 j n)，则当前解 x 即为最优解，迭代结束。否则转; 计算 k = maxj| j 0, 确定k, 并计算pk = B1pk； 若所有aik 0, 则停止计算，(LP)无最优解，否则转； 计算 = minbi/aik | aik 0, 1 i m = bl /alk , 修改集合I,J和cB； 形成Elk , 并计算 B1=ElkB 1, xB=Elk xB