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

第1章 线性规划及单纯形法 姚明臣 2011年3月 中国科技网到中国电信网络线路使用分析报告 All rights reserved 本次课程要求掌握的内容 n会建立简单的线性规划问题的数学模型； n理解并记忆线性规划模型的各种形式； 分量形式 向量形式 矩阵形式 n会将一般线性规划模型化成标准型； n有关线性规划问题解的若干重要概念 可行解、最优解、基、基(本)解、基可行解等。 n熟练掌握含两个决策变量问题的图解法； n凸集的相关概念和单纯形法若干基本定理。 Date 2 1 线性问题的数学模型 n问题的提出 例1. 用一块边长为a的正方 形铁皮做一个容器，应如 何裁剪，才能使做成容器 的容积最大？ a x 解：利用高等数学的知识 V=(a - 2x)2 x 求 V(x) 的最大值即可。 问题？ Date 3 线性规划的数学模型 n问题的提出 例2 (生产计划安排，要求利润最大) n解：设在计划期 内生产产品I和产 品II分别为x1和x2 件(决策变量) n目标是要使 z = 2 x1 + 3 x2达到 最大。(目标函数) n限制条件是： （约束条件） 2x1 + 2x2 12 和 2x1 16 以 及 5x2 15 要求 x1, x2 0 加工设 备 ABC 单件利润 产品 I2402元 产品 II2053元 设备时 限 12h 16h 15 h Date 4 线性规划的数学模型 n问题的提出 例子之三(合理下 料问题) 现有一批10m长的贵重钢筋， 需要截取3m和4m长的钢筋各50 根，试问如何截取，才能使原 料最省？ n问题分析： 先确定截取方案 建立数学规划模型 n问题：模型是否有别的形式？ 截取方 案 IIIIII 3m钢筋230 4m钢筋102 废料长0m1m 2m Date 5 线性规划问题数学模型的定义 n线性规划模型组成的三要素： 决策变量 目标函数 约束条件 n定义1 在线性规划数学模型中，如果决策变量为可控的 连续变量，目标函数和约束条件都是线性的，称这类模 型为线性规划问题的数学模型。 n问题：例一中的问题是否为线性规划模型？ Date 6 线性规划问题数学模型的一般形式 n关于幻灯片中的数学符号： 小写斜体字母表示实数，如a,b,c,x,x1,y,z等 小写黑体字母表示向量，如x,y,z等 大写黑体字母表示矩阵，如 A, B,C等 n线性规划(LP)数学模型的一般形式 或 Date 7 线性规划数学模型向量和矩阵形式 n(LP)向量形式 n(LP)矩阵形式 Date 8 线性规划问题的标准形式 n什么是(LP)问题的标准形式 ？ 满足如下条件： 目标函数是求极大值； 约束条件全为等式； bi和xj全为非负数。 Date 9 (LP)一般形式向标准形式的转化 n(LP)一般形式向标准形转化的情况： 目标函数是求极小值； 约束条件为不等式“”的情形（松弛变量，例2）； 约束条件为不等式“” 的情形（剩余变量，例3）； 取值无约束的变量； 某个变量 xj 0 问题：某个变量有上下界限制，比如l xj u，如何处理？ n例3. 见书P12。 Date 10 线性规划问题解的若干重要概念 n线性规划问题的任务 从满足约束条件（2）和非负条件 （3）的方程组中，找到使目标函 数（1）取得最大值的解。 n可行解和可行域 满足约束和非负条件的解x。 n最优解 n基、基向量、基变量 设A=(aij)mn，r(A) = m，称A的 一个m阶满秩子矩阵B称为(LP) 问题的的一个基。 n基解 由基矩阵B确定的m个基变量， 并上非基变量取0的解。 n基(本)可行解 同时是可行解的基解。 n可行基 Date 11 利用初等变换求基可行解 n例4. 教材14页，列出(LP)问题的全部基，基解、基可行解并指 出最优解。 n问题: I) 如何判断一个解是基可行解； II）表1-1中为何少了两行？ n利用p1,p2, p4 求基解的过程 Date 12 2 图解法求最优解 n什么时候用图解法？ (LP)模型仅含两个决策变量。 n求解方法和根据： 根据约束画出求解区域，一般为第一象限的凸多边形 (有界或无界)，标记出顶点坐标； 求目标函数的梯度：设目标函数是 z=c1x1+c2x2，则 n = grad z = (c1,c2) 为等值线c1x1+c2x2= h的法线方向，沿n的方向 函数值增加的最快，沿-n方向函数值减少的最快。 移动等值线 c1x1+c2x2= h 在区域顶点或边界达到最大最小值。 n书中的方法是把目标函数z当做参数处理。 Date 13 一般情况求解区域的确定 n约束一般都可化成 ax1+bx2+c = 0 (a 0，b 0)的形式特殊情形？ Date 14 一个用图解法求极值的例子 n用图解法求如下线性规划问题的极值。 最大值点 x* = (1,4), Zmax = 3；最小值点 x* = (4,1), Zmin = 3； A(2,0) B(4,1) C(1,4) D(0,2) Date 15 图解法的其他情形 无穷多最优解 n无穷多最优解(书，P16，见下图) 问题1：什么情况下发生？ n问题2：这个最优解如何表示？ Date 16 图解法的其他情形 无界解(无最优解) n求下面规划问题的最优解。 问题1：如果目标函数是求极大，是否有最优解？ 问题2：能否定量说明 z 是无下界的？ Date 17 图解法的其他情形 无可行解 n求下面规划问题的最优解。 Date 18 3 单纯形基本原理 预备知识 n凸集 定义1.1：如果集合C中任意两点x(1)，x(2)，其连线上的所 有点也在集合C中，即对任何x(1)C， x(2)C，0 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-1 % 如果 r(B) = 3 n Base = ; n for j=1:m n % 将B表示成（p1 p2 .pk）的形式 n Base = Base,blanks(10), p,int2str(ploc(j); n end n disp(BASE = , Base); % 显示基是哪些列构成的 n x(ploc)= Bb % 求 x_B 并放入基列位置 n zvalue = c*x(1:m) % 计算最优值 n end nend Date 31 初始基可行解的获得 n设法构造一个初始单位阵基。 如果约束条件都是 “ ” 形式，化标准型直接获得； 如果约束条件是 “=” 或 “ ” 形式，采用人工变量法(稍后讲)。 n不妨设(LP)标准形前m列是单位阵，即典型形式(典式)。 Date 32 最优解的判别 - 检验数 n最优解的判别：用非基变量表示目标函数值。 Date 33 单纯形表的建立 cjc1c2 c m cm+1cj cn CBBbx1x2 x m xm+1xj xn c1x1b11a1m+ 1 a1j a1n c2x2b21a2m+ 1 a2j a2n cmxmbm1 amm +1 amj am n j=cj-zj00 0 nB 基(变量)；CB - 基变量对应目标函数系数；b 右端 项 检验数的计算： j= cj zj = cj (c1a1j+ c2a2j+ cmamj) Date 34 用单纯形表求解的例子(书p26.例5) cj23000 CBBb x1x2x3x4x5 0x312 22100 0x416 40010 0x515 05001 j=cj zj 23000 化标准型 建立初始单纯形 表，计算检验数； 确定进基变量 ，x2进基 (检验数最大); 确定离基变量， =min12/2,16/0,15/5 = 3，x5离基。 由主元a32确定 。 Date 35 单纯形表上的迭代算法 cj23000 CBBb x1x2x3x4x5 0x3 12 22100 0x4 16 40010 0x515 05001 j=cj zj 23000 0 1 0 0 1/53 3 x2 2 0 1 0 -2/56 2 0 0 0 -3/5 所有检验数非正，最优解 x*=(3,3,0,4,0)T，最优值 z*=15 第1次迭代：对主元 所在行和列进行初 等变换，并计算检 验数。 第2次迭代：x1进基 ，x3离基，主元 a12=2，消元并计算 检验数。 2 x13 1 0 1/2 0 -1/5 0 x4 3 x2 40 0 -2 1 4/5 30 1 0 0 1/5 j=cj zj0 0 -1 0 -1/5 Date 36 单纯形算法的一般形式 cjc1clcmckcj CBBbx1xlxmxkxj c1x1b11a1ka1j cixibiaikaij clxlbl1alkalj cmxmbm1amkam j j=cj-zj0 0 0kj Date 37 单纯形算法的计算步骤 n把(LP)化成标准形式，建立初始单纯形表； （一般能获得一个单位阵基作为初始可行基） n计算所有变量的检验数，若所有 j 0 (1 j n)，则当 前解 x 即为最优解，迭代结束。否则转; n确定 k = maxj| j 0, 则xk待进基； n若所有aik 0, 则停止计算，(LP)无最优解，否则转； n计算 = minbi/aik | aik 0, 1 i m = bl /alk ,则xl离基； n以alk为主元,通过高斯消元法进行基可行解的转换，求得 表中一新基可行解，转步骤。 (注：若在和中出现多个k或者l, 则按照自然顺序选择 ) Date 38 迭代一次之后的形式 cjc1clcmckcj C B Bbx1xlxm xk xj c1x1 1 0 cixi 0 ckxk1 c m x m 1 0 j=cj-zj000 Date 39 迭代前后解,函数值,检验数等的变化 Date 40 一个讲练的例子(大家参与) Date 41 最优性检验标准() 若所有 j 0 (1 i m), 则 (LP)有无穷多最优解。 若有某个 j 0 ( m+1 j n ),但是 pj = (a1j, a2j, , amj) 0, 则(LP)无有限的 最优解和最优值（无最优解）。 采用人工变量方法时(大M法和二阶 段法)，满足最优条件时人工变量不为 零，则原LP问题无可行解。 Date 42 5 人工变量法 问题的提出 n如果原（LP）问题的约束全是“”号的形式，可以引入m个松 弛变量xn+m，使得后m列自然形成初始单位阵基，再用单纯形法 进行迭代求解。 n如果原（LP）问题的约束是“”和“”号，或者三种符号（ 、 、 ）都有的的混合形式，且化成标准形式后约束矩阵不 具备初始单位阵基，这时候怎么办？ n解决办法：自然的想法就是在标准形约束矩阵中，人工加入若 干单位向量，(和已有的)形成初始单位阵基。 化标准型 Date 43 人工变量法 大M法 n例6 求解如下线性规划问题(书P29) n标准形中只有p4是单位向量 ？强行加入两列p6和p7 ，或 者说在第2、3个约束上分别 加入人工变量，即x6和x7。 n人工变量的系数问题？目标 函数中人工变量系数都取M (M 0 充分大)。 Date 44 用大M法求解 例6 cj-30100 -M-M CBBb x1x2x3x4x5x6x7 0x441111000 -M x61-21 -10-110 -M x790310001 cj zj-2M-34M 10 -M 00 检验数比较： 形式 aM+b 1. a 0, aM+b 0 2. a 0 但p4 =(-1/2,-3) 0, 确定k, 并计算pk = B1pk； n若所有aik 0, 则停止计算，(LP)无最优解，否则转； n计算 = minbi/aik | aik 0, 1 i m = bl /alk , 修改集合I,J和cB； n形成Elk , 并计算 B1=ElkB 1, xB=Elk xB, 转步骤。 (注：若在和中出现多个k或者l, 则按照自然顺序选择) Date 69 单纯形表vs.修正单纯形算法（板书计算） cj-1300 CBBb x1x2x3x4 0x36-1210 0x451101 cj zj-1300 3x23- 1/ 2 1 1/ 2 0 0 x4 23/ 2 0 -1/2 1 cj zj 1/ 2 0 -3/2 0 3x2 11/3 01 1/31/3 -1 x1 4/ 3 10 -1/32/3 cj zj 00 -4/3-1/3 Date 70 应用举例 投资项目的组合问题 n例14 .（书P45）兴安公司有一笔30万元的自己，考虑今后三年内 用于下列项目的投资： 三年内每年年初均可投资，每年获利为投资额的20%，其本利可一起 用于下一年的投资； 允许第一年初投入，于第二年末收回，本利合计为投资额的150%，但 是此类投资限额不超过15万元； 允许于第二年初投资，于第三年末收回，本利合计为投资额的160%， 但限额投资20万元； 允许于第三年初投入，年末收回，可获利40%，但限额为10万元。 试为该公司制定一个使第三年末本利和最大的投资组合方案。 n求解注意的问题： 如何设定决策变量？ 约束的控制 求解的过程 Date 71 综合问题. 解的性质判别（大家参与） n下表给出某极大化问题的单纯形表，问表中a1, a2, c1, c2, d为何值时 ，以及表中变量属那种类型时(3)，有 (1). 表中解为唯一解？无穷多最优解之一？无界解？退化的可行解 ？ (2). 下一步迭代将以x1替换基变量x5? (3). 该线性规划问题无可行解？ x1x2x3x4x5 x3 d 4a1100 x4 2 -1-5010 x53 a2-3001 cj zj c1c2000 Dat