运筹学第一章线性规划及单纯形法.ppt

胡运权 清华大学出版社 《 运 筹 学 教 程 》 (第三版） 参 考 书 目 《运筹学》 施泉生 中国电力出版社, 《运筹学习题集(第三版)》 胡运权,清华大学出版社, “运筹学” . Operations Research (美国) Operational Research (英国) 运 筹 学 定 义 在现有的条件下，如何科学地设 计和操作某复杂系统，使其在某 种意义上达到最优。 本 课 程 内 容 规划论：线性规划、非线性规划、整数规划、动态规划、网络规划、多目标规划、随机规划、…… 图与网络分析：关键路线、最短路、最大流、最小树、…… 各种模型与问题：运输问题、分派问题、存贮论、排队论、决策论、对策论、…… 软 件 Excel Matlab Lindo, Lingo …… 运筹学的历史和发展 名称由来： 二次大战 课程设置： 1948年麻省理工学院 学术团体： 1957年 英国牛津大学 第一届国际运筹学会议 1959年 “国际运筹学联合会” 学术刊物： 1950年 英国“运筹学季刊” 我国大陆译作 “运筹学”，是借用了 《史记-汉高祖本纪》 “运筹于帷幄之中，决胜于千里之外” 一语中“运筹”二字，既显示其军事的起 源，也表明它在我国已早有萌芽。 本课程的研究方法 从现实生活场合抽出本质的要素来构造数学模型，因而可寻求一个跟决策者的目标有关的解； 探索求解的结构并导出系统的求解过程； 从可行方案中寻求系统的最优解法。 本 课 程 的 特 点 被广泛用于工程建设、企业管理、军事部门、……，具有很强的实践性。 是一门优化技术，提供的是解决各类问题 的优化方法。 是数学模型竞赛中使用的主要工具。 运筹学解决问题的步骤 提出问题：用自然语言描述问题。 建立模型：用变量、函数、方程描述问题。 求解：用数学方法求出模型的最优解、次优解、满意解，复杂模型求解要用计算机。 解的检验：检查模型和求解步骤有无错误，检查解是否反映现实问题。 决策实施：决策者根据自己的经验和偏好，对方案进行选择和修改，作出实施的决定。 运筹学的应用 市场销售、生产计划、资本运营、 库存管理、运输问题、财政和会计、 人事管理、设备维修和更新、 项目评价和选择、工程优化设计、 计算机和信息系统、城市管理、发展战略、 ………… 本 课 程 要 求 熟练掌握各种模型及其求解方法。 掌握与基本模型有关的基本概念及基本原理。 领会原理、掌握方法、强化应用， 提高解决实际问题的能力。 中国： 都江堰水利工程 (公元前250年) 丁谓修开封皇宫 (北宋年间) 运 筹 学 案 例 齐王赛马 (齐王与田忌) 外国： 哥尼斯堡七桥问题 (1736) 欧拉 二战期间： 反潜艇问题 (英吉利海峡) 渡大西洋船队规模问题 德国“飞弹”袭击伦敦问题 线性规划：LP 求有线性约束的线性函数的最优解。 第一章 线性规划及单纯形法 线性规划是运筹学的重要内容。本章介绍 (1) 线性规划数学模型; (2) 线性规划的基本理论; (3) 求解线性规划的基本算法——单纯形法。 于1947年提出了求解线性规 划问题的单纯形法。 单纯形法至今还是求解线性规划最有效的方法。 例 生产计划问题（资源利用问题） 某家具厂生产桌子和椅子两种家具。 桌子售价50元/个，椅子销售价格30元/个。 需要木工和油漆工两种工种。 生产一个桌子需要木工4小时，油漆工2小时。 生产一个椅子需要木工3小时，油漆工1小时。 该厂每个月可用木工工时为120小时， 油漆工工时为50小时。 问如何组织生产才能使每月的销售收入最大？ 解：将这个问题化为线性规划模型: 1．确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量 2．确定目标函数：家具厂的目标是销售收入最大 max (50x1+30x2) 3．确定约束条件： 4x1+3x2  120（木工工时限制） 2x1+x2  50 （油漆工工时限制） 4．变量取值限制：决策变量只取正值（非负值） x1  0, x2  0 数学模型 max (50x1+30x2) . 4x1+3x2  120 2x1+ x2  50 x1, x2  0 线性规划数学模型三要素： 决策变量、约束条件、目标函数 每一个线性规划问题都有一组决策变量 (x1, x2, ……, xn) , 这组决策变量的值就代 表一个具体方案。 有使用各种资源的的约束条件。 有一个要达到的目标，是决策变量的线性函数。 一般形式 线性规划模型 矩阵形式 标准形式 将一般线性规划化成标准形 线性规划问题的一般形式： max(min) Z = c1x1+c2x2+…..+cnxn . a11x1+a12x2+….+a1nxn (=, )b1 a21x1+a22x2+….+a2nxn (=, )b2 …………………. am1x1+am2x2+….+amnxn (=, )bm x1, x2, …., xn  0 线性规划的矩阵形式： max Z = CTX . AX=b X  0 a11 a12 …. a1n b1 A = a21 a22 …. a2n b = b2 …………………………… ………. am1 am2 …. amn bm c1 x1 0 c2 x2 0 C = X = 0 = … … ... cn xn 0 线性规划问题的标准形式： max Z = c1x1+c2x2+…..+cnxn . a11x1+a12x2+….+a1nxn = b1 a21x1+a22x2+….+a2nxn = b2 …………………. am1x1+am2x2+….+amnxn = bm x1, x2, …., xn  0 其中：bi  0, i=1, 2,…., m. 四点要求: 将一般线性规划化成标准形 求max 等式约束 bi  0 xi  0 (1) 若目标函数是求最小值: min Z = CTX 令 Z’ = Z, 则化成 max Z’= CTX 注意: 因为 min Z =  max(Z ) 所以变换后的最优解不变，最优值变号。 (2) 若约束条件是不等式 若约束条件是“  ” 不等式， 则不等式左边 “加上” 非负的松驰变量； ii)若约束条件是“  ” 不等式， 则不等式左边 “减去” 非负的松驰变量。 (3) 若约束条件右面的某一常数项 bi<0, 这时只要在 bi 相对应的约束方程两边乘 1。 (4) 若变量 xj 无非负限制 引进两个非负变量 xj’ xj”  0 令 xj= xj’ xj’’（可正可负） 任何形式的线性规划总可以化成标准型 例 将下列问题化成标准型: min Z =  x1+ 2x2  3x3 . x1+ x2 + x3  7 x1  x2 + x3  2  3x1 + x2 + 2x3 = 5 x1 0, x2 0, x3 无限制 例 将下列问题化成标准型: max ( x1  2x2 + 3x3) . x1+ x2 + x3  7 x1  x2 + x3  2  3x1 + x2 + 2x3 = 5 x1 0, x2 0, x3 无限制 例 将下列问题化成标准型: max ( x1  2x2 + 3x3) . x1+ x2 + x3 + x4 = 7 x1  x2 + x3  2  3x1 + x2 + 2x3 = 5 x1 0, x2 0, x3 无限制 例 将下列问题化成标准型: max ( x1  2x2 + 3x3) . x1+ x2 + x3 + x4 = 7 x1  x2 + x3  x5 = 2  3x1 + x2 + 2x3 = 5 x1 0, x2 0, x3 无限制 max ( x1  2x2 + 3x3’  3x3’’) . x1+ x2 + x3’  x3’’ + x4 = 7 x1  x2 + x3’  x3’’  x5 = 2  3x1 + x2 + 2x3’  2x3’’ = 5 x1 0, x2 0, x3’0, x3’’0 令 x3 = x3’  x3’’ 变换举例 习 题 P43 ， 先画可行域(满足约束条件的X的全体) 两个变量LP问题的图解法 再画法线方向 求 max，沿法线方向推； 求 min，沿负法线方向推。 最后的交点为顶点。 例 max Z = 50x1+30x2 . 4x1+3x2  120 2x1+x2  50 x1, x2  0 x2 40 30 20 10 10 20 30 x1 由 4x1+3x2  120 x1  0, x2  0 围成的区域 50 由 2x1+x2  50 x1  0, x2  0 围成的区域 x2 40 30 20 10 10 20 30 x1 由 4x1+3x2  120 2x1+x2  50 x1  0, x2  0 围成的区域 (可行域) 50 可行域 x2 40 30 20 10 10 20 30 x1 该问题的可行域是由 Q1，Q2，Q3，Q4 作为顶点的凸多边形 50 可行域 Q1(0, 0) Q2(25, 0) Q4(0, 40) Q3(15, 20) x2 40 30 20 10 10 20 30 x1 目标函数 Z = 50x1+30x2 是一组平行线 50 可行域 x2 40 30 20 10 10 20 30 x1 此组平行线沿其 法线方向 (50, 30) 右上方 函数值 Z 增加 50 可行域 x2 40 30 20 10 10 20 30 x1 当该直线移到 Q3(15, 20)点时，Z 值达到最大： max Z=5015+3020=1350 此时最优解 X*=（15，20） 50 Q3(15, 20) 二个重要结论： 可行域是一个凸多边形。 最优解必定能在某一个顶点上取得。 习 题 P43 LP问题最优解的归类 可行解：满足约束条件（包括非负条件）的 一组变量值，称可行解。 可行域：可行解的全体。 最优解：使目标函数达到最大的可行解。 最优值：将最优解代入目标函数得到的值。 可行域为空集  无可行解 可行域非空，则有三种情况： i) 有唯一解 (顶点) ii) 有无穷多个解 (两个顶点间的连线) iii) 无最优解 (无界解) 无最优解  x2 40 30 20 10 10 20 30 x1 当目标函数由 max Z=50x1+30x2 变成 max Z=40x1+30x2 目标函数是同约束条件 4x1+3x2  120 平行的直线 Q2与Q3之间都是最优解 50 Q3(15, 20) Q2(25, 0) 无界解 ：若可行域无界， 且目标函数值可增加(减少)到正无穷(负无穷)， 称这种无最优解的情况为无界解。 注意： 可行域无界，不一定无最优解； 可行域非空有界，则必定有最优解。 定义 (凸集) LP问题解的性质 设 D  Rn 若任对 X1, X2 D， 对一切 0<<1, 有 X=  X1+(1 )X2  D 则称D为凸集。  (X1, X2 连线上的一切点仍在中) 凸集之例: 非凸集之例: 凸集性质: 二个凸集的交还是凸集. 二个凸集的并不一定是凸集 定义 (凸组合) LP问题解的性质 设 D  Rn, 若 X1, X2, …, , Xk D， 称 a1X1 + a2X2 +……+ akXk 为X1, X2, …, , Xk 的凸组合。 其中 a1 ≥0, a2 ≥0, ……, ak ≥0. 而且 a1 + a2 +……+ ak=1. 定义 (凸集中的顶点) LP问题解的性质 设 D为凸集, X0D， 若X0不可被表示成D中其它不同两点的凸组合, 则称X0为D的顶点. 问题: 如何描述D中的点不是顶点? 顶点之例: 多边形上的尖角点是顶点 圆周上的点都是顶点 线性规划的基本定理 线性规划的可行域 D 为凸集。 若有最优解，则最优解集 D* 为凸集。 最优解集 D* 为: 空集、单点集、无限集。 基可行解 (1) 基阵: 设 r(A) = m, 且B是A的m 阶非奇异的子矩阵（det(B)  0), 则称矩阵B为线性规划问题的一个基阵。 a11 … a1m a1m+1 … a1n a21 … a2m a2m+1 … a2n ………… …………… am1 … amm amm+1 … amn p1 … pm pm+1 … pn B N ( mn) r(A)=m，至少有一个m阶子式不为0。 A满行秩 基阵 = A的 m 阶可逆 子方阵 A的基阵最 多几个? (2) 基变量、非基变量: 设 A=( p1, p2, ……, pn ), 若B=( pi1, pi2, ……, pim )为 A的基阵, 则称 x1, x2, ……, xn 中的xi1, xi2, ……, xim 为对应于B的基变量，其余的称为非基变量。 A= ( p1 … pm pm+1 … pn ) = ( B, N ) 基向量 非基向量 X= ( x1 … xm xm+1 … xn )T = ( XB XN)T 基变量 非基变量 (3) 基解: 令非基变量取值为零, 则基变量的取值可从 AX=b 中唯一解得。 如此的一组解称为对应于B的一个基解。 例: 设 B 为A的一个基阵，且A=(B, N)，则 X 为： 令非基变量取值零，则基变量的取值可从 AX=b 中唯一解得： (4) 基可行解: 若X0是一个基解，而且又是一个可行解， 则称X0是一个基可行解。 基可行解对应于可行域的顶点。 问题: 基解是否为可行解? 基解满足：AX0 = b，但不一定有 X00. (5) 退化的基可行解: 问题: 在基可行解中,非基变量的取值必定为零, 基变量的取值是否必定大于零? 若X0是一个基可行解, 其基变量的取值全部大 于零，则称X0是非退化的; 否则称为退化的。 解的关系： 可行解 基解 基可行解 最优解 图例 1 1 8 7 6 5 4 3 2 2 x 1 8 7 6 5 4 3 O 10 9 x 2 A B C E D F G H 1 2 3 可行解、基解和基可行解举例 1 1 8 7 6 5 4 3 2 2 x 1 8 7 6 5 4 3 O 10 9 x 2 A B C E D F G H 1 2 3 f ( x )=36 K 习 题 P44 , 基可行解 = 顶点 代数描述 几何描述 X0 为基可行解  X0 的非零分量对应的A的列向量线性无关  X0 是D的顶点 线性规划的基本定理 可行域非空 ，则必存在基可行解（顶点） 可行域中顶点个数为有限个。 若有最优解，则必可在某个顶点上达到。 i) 先从一个基可行解(顶点)出发 单 纯 形 法 ii) 判断此基可行解是否为最优解 iii) 若不是最优解，则换一个基可行解 如此反复，直至找到最优解 先假定基阵B为单位阵(iii中达到此目的) 章 节 安 排 i) 最优解的判断 ii) 换基可行解的方法 iii) 初始基可行解的确定 单纯型法的基本思路 确定初始基可行解 得最优值 确定改进方向 求出新的基可行解 检查是否为 最优解？ 是 否 一、最优解判别定理： 不妨假设 A = (B, N) = (Im, N) 则由 AX=b，可得：XB=b-NXN 代入目标函数： f(X) = CB XB+ CN XN = CB (b-NXN )+ CN XN = CB b + (CN –CBN)XN 对应的基可行解为: X0=(b , 0) 对应的目标函数： f(X0)=CB b 若求Max，则当 CN- CB N  0 时， X0 = (b , 0) 为最优解， f(X0) = CB b 为最优值。 若求Min，则当 CN- CB N  0 时， X0 = (b , 0) 为最优解， f(X0) = CB b 为最优值。 称　 = CN- CB N 为检验数， 检 验 数 公 式 注意:　 (1) 对应于非基变量 xj 的检验数为：　 j = Cj- CB Pj (2) 对应于基变量 的检验数为零。　 单纯形解题判别步骤(max)： 若检验数全小于等于零，则基B所对应的 基可行解X就是最优解，终止。 若存在检验数大于零，但所对应的进基变 量XS的系数向量PS小于等于零， 则原问题无最优解，终止。 若存在检验数大于零，且对应的常数项 大于零，则需要换基迭代。 换基迭代 从检验数j > 0 中找最大者， j* = max{j ; j > 0 } 选中者对应的变量称为进基变量， xj* 　第 j* 列称为主列. 换基迭代 确定离基变量：如果有 则xi* 为离基变量．第 i* 行称为主行． 换基迭代 迭代过程 i* 行与 j*列相交的元素ai*j* 称为主元，也称主元为枢轴量; 迭代以枢轴量为中心进行线性变换；. 将主元 ai*j*变为1，主列上其它元素变为0. 例 求线性规划问题　 max ( x1-2x2 + x3) . 2x1+ +x3 = 2 x1 -4x2 +x4 = 5 x1 , x2 , x3 , x4 ≥ 0 习 题 P43 (1) 用单纯形法 i) 无法给出初始基可行解 大 M 法 ii) 添加人工变量 iii) 修改目标函数 习 题 P43 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *