运筹学基础教程(第二版)教学课件+-+南京大学《大学物理学》课程.ppt

1 运筹学基础教程 第二版 制作人 黄桐城 上海交通大学安泰经济与管理学院 版权所有侵权必究 2 概述 运筹学 OperationsResearch 是用数学方法研究各种系统的最优化问题 运筹学强调发挥现有系统的效能 应用数学模型求得合理利用各种资源的最佳方案 为决策者提供科学决策的依据 运筹学的内容有数学规划 运输问题 图与网络分析 排队论 存储论 决策论和对策论等 其中数学规划又包括线性规划 整数规划 非线性规划 目标规划和动态规划等 虽然运筹学包括的内容较多 但是它们有两个共同的特点 一是以全局最优作为问题的基本出发点 二是通过建立数学模型 运用优化技术求得系统最合理的运营方案 由于各种系统的运营机制和性能不尽相同 它们的数学模型也各不相同 从而形成了运筹学的不同分支 3 所以可对运筹学做如下概括 运筹学的研究对象是各种系统 运筹学的研究目的是实现系统的最优化 求得合理利用各种资源的最优方案 运筹学的研究方法是运用数学语言来描述实际系统 通过建立数学模型和优化技术求得系统运营的最优解 运筹学的研究动机是为决策者提供科学决策的依据 运筹学在工业 农业 商业 物流 经济计划 人力资源 军事等行业都有着非常广泛的应用 有人曾对世界上500家著名的企业集团或跨国公司进行过调查 发现其中95 曾使用过线性规划 75 使用过运输模型 90 使用过网络计划技术 90 使用过存储模型 43 使用过动态规划 由此可见运筹学是一门应用性很强的学科 特别是随着计算机技术的不断发展 计算机成为运筹学最强有力的运算工具 运筹学越来越显示出其广泛的使用价值 4 运筹学这一名词最早出现于1938年 当时英 美等国盟军在与德国的战争中遇到了许多错综复杂的战略和战术问题难以解决 比如 防空雷达的布置问题 英美等国为了对付德国的空袭配备了先进的雷达作为防空系统的一部分 但是由于雷达系统的布置不甚合理 通过防空演习发现实际效果并不理想 护航舰队的编队问题 英美等国需要对本国的商船队配备护航舰队 以防止德国潜艇的攻击 这里有一个如何合理编队才能使商船队一旦遭受德国潜艇攻击时损失最少的问题 为了应付上述各种复杂问题 英美等国逐批召集不同专业背景的科学家 在三军组织了各种研究小组 研究的问题都是军事性质的 在英国称为 OperationalResearch 其他英语国家称为 OperationsResearch 意思是军事行动研究 这些研究小组运用系统优化的思想 应用数学技术分析军事问题 取得了非常理想的效果 5 二战以后 在军事运筹小组中工作过的一部分科学家开始转入民用部门 他们把对军事系统最优化的研究成果拓展到各种民用系统的研究上 1947年美国数学家G B Dantzig在研究美国空军资源配置时 提出了求解线性规划的有效方法 单纯形法 20世纪50年代初 应用计算机求解线性规划获得成功 至50年代末 一些工业先进国家的大型企业已经较普遍地使用运筹学方法解决在生产经营管理中遇到的实际问题 并取得了良好的效果 至60年代中期 运筹学开始应用于一些服务性行业和公用事业 同时很多国家成立了运筹学研究学会 一些大学的相关专业也陆续设置了运筹学的有关课程 专门发表运筹学研究论文的刊物开始出版 运筹学的理论研究日趋成熟 在实际应用上则日趋广泛 6 我国运筹学的研究始于20世纪50年代中期 当时由钱学森教授将运筹学从西方国家引入我国 以华罗庚教授为代表的一大批科学家在有关企事业单位积极推广和普及运筹学方法 在建筑 纺织 交通运输 水利建设和邮电等行业都有不少应用 关于邮递员投递的最佳路线问题就是由我国年轻的数学家管梅谷于1962年首先提出的 在国际上统称为中国邮递员问题 我国运筹学的理论和应用研究在较短时间内赶上了世界水平 如今对运筹学的研究大致在三个领域发展 运筹学应用 运筹科学和运筹数学 一般的共识是 运筹学的研究不能忘记其原有的应用性强的特色 必须强调多学科的交叉联系和解决实际问题的研究 我们面临的很多系统通常涉及到大量的经济 技术 社会 政治和心理等综合因素 这些综合因素受到人的影响和干预 存在非结构性的复杂问题 仅用数学模型是很难加以描述和解决的 总之随着社会的不断发展和进步 实践将对运筹学提出更新更多的研究课题 运筹学正处于不断发展 不断进步的时期 7 目录 第1章线性规划的基本概念第2章单纯形法第3章对偶规划与灵敏度分析第4章运输问题第5章图与网络分析第6章排队论第7章存贮论第8章决策分析 8 第1章线性规划的基本概念 线性规划问题及其数学模型线性规划的图解法线性规划的标准形式标准型线性规划的解的概念线性规划的基本理论 9 问题的提出 在生产管理的经营活动中 通常需要对 有限的资源 寻求 最佳 的利用或分配方式 有限资源 劳动力 原材料 设备或资金等最佳 有一个标准或目标 使利润达到最大或成本达到最小 有限资源的合理配置有两类问题 如何合理的使用有限的资源 使生产经营的效益达到最大 在生产或经营的任务确定的条件下 合理的组织生产 安排经营活动 使所消耗的资源数最少 线性规划问题及其数学模型 10 与规划问题有关的数学模型总有两部分组成 约束条件 反映了有限资源对生产经营活动的种种约束 或者生产经营必须完成的任务 目标函数 反映生产经营者在有限资源条件下希望达到的生产或经营的目标 11 例 某制药厂生产甲 乙两种药品 生产这两种药品要消耗某种维生素 生产每吨药品所需要的维生素量 所占用的设备时间 以及该厂每周可提供的资源总量如下表所示 已知该厂生产每吨甲 乙药品的利润分别为5万元和2万元 但根据市场需求调查的结果 甲药品每周的产量不应超过4吨 问该厂应如何安排两种药品的产量才能使每周获得的利润最大 12 定义x1为生产甲种药品的计划产量数 x2为生产乙种药品的计划产量数 目标 使总利润Z 5x1 2x2极大化约束 每周资源总量的限制 30 x1 20 x2 1605x1 x2 15甲种药品每周产量不应超过4吨的限制x1 4计划生产数不可能是负数 x1 0 x2 0 13 数学模型为s t subjectto suchthat 这是一个如何合理的使用有限的资源 使生产经营的效益达到最大的数学规划问题 在满足一组约束条件的限制下 寻求决策变量x1 x2的决策值 使目标函数达到最大值 14 例 某化工厂根据一项合同要求为用户生产一种用甲 乙两种原料混合配制而成的特种产品 已知甲 乙两种原料都含有A B C三种化学成分 两种原料分别所含三种化学成分的百分比含量 以及按合同规定的产品中三种化学成分的最低含量如下表所示 已知甲 乙两种原料的成本分别是每公斤3元和2元 厂方希望总成本达到最小 问如何配置该产品 化学成分 15 定义x1 x2分别为每公斤产品中甲 乙两种原料的数量 目标 使总成本Z 3x1 2x2极小化约束 配料平衡条件 x1 x2 1产品中A B C三种化学成分的最低含量12x1 3x2 42x1 3x2 23x1 15x2 5非负性条件x1 0 x2 0 化学成分 16 数学模型 s t 这是一个原料配制问题 是在生产任务确定的条件下 合理的组织生产 使所消耗的资源数最少的数学规划问题 满足一组约束条件的同时 寻求变量x1和x2的值使目标函数取得最小值 化学成分 17 例 某铁器加工厂要制作100套钢架 每套要用长为2 9米 2 1米和1 5米的圆钢各一根 已知原料长为7 4米 问应如何下料 可使材料最省 分析 在长度确定的原料上截取三种不同规格的圆钢 可以归纳出8种不同的下料方案 问题归纳为如何混合使用这8种不同的下料方案 来制造100套钢架 且要使剩余的料头总长为最短 18 设xj表示用第j种下料方案下料的原料根数 j 1 2 8 目标 使料头总长度Z 0 1x2 0 2x3 0 3x4 0 8x5 0 9x6 1 1x7 1 4x8极小化约束 三种规格圆钢根数x1 2x2 x4 x6 1002x3 2x4 x5 x6 3x7 1003x1 x2 2x3 3x5 x6 4x8 100非负取整条件xj 0 j 1 2 8 且取整数 19 数学模型s t 这是一个下料问题 是在生产任务确定的条件下 合理的组织生产 使所消耗的资源数最少的数学规划问题 满足一组约束条件的同时 寻求变量x1至x8的值 使目标函数取得最小值 且为整数 20 线性规划的一般数学模型线性规划模型的特征 1 用一组决策变量x1 x2 xn表示某一方案 且在一般情况下 变量的取值是非负的 2 有一个目标函数 这个目标函数可表示为这组变量的线性函数 3 存在若干个约束条件 约束条件用决策变量的线性等式或线性不等式来表达 4 要求目标函数实现极大化 max 或极小化 min 满足上述4个特征的规划问题称为线性规划问题 21 线性规划的模型的一般形式 目标函数满足约束条件通常称为决策变量 为价值系数 为消耗系数 为资源限制系数 22 线性规划的图解法 适用于求解两个变量的线性规划问题图解法的基本步骤例4利用例1说明图解法的主要步骤 例1的数学模型为s t 23 O 5 10 15 x1 x1 4 x2 5 10 1 A B 2 5 C Z 5x1 x2 15 30 x1 20 x2 160 5x1 2x2 5 24 线性规划图解法的基本步骤 1 建立以x1 x2为坐标轴的直角坐标系 画出线性规划问题的可行域 2 求目标函数Z C1x1 C2x2的梯度 Z c1 c2 3 任取等值线C1x1 C2x2 Z0 沿梯度 Z正方向平移 若是极小化问题 则沿负梯度方向 Z平移 求等直线将离未离可行域时与可行域的交点 4 若交点存在 则该点坐标就是最优解 25 图解法的几种可能结果 1 有唯一最优解 如例1 2 有无穷多最优解如例1中的目标函数设为maxZ 10 x1 2x2则目标函数等值线10 x1 2x2 Z与第二约束5x1 x2 15的边界线平行 将等值线沿梯度 Z 10 2 正方向平移至B点时与可行域OABC的整条边界线AB重合 这表明线段AB上的每一点都使目标函数取得同样的最大值 因而都是最优解 26 O 5 10 15 x1 x1 4 x2 5 10 1 A B 2 5 C Z 5x1 x2 15 30 x1 20 x2 160 10 x1 2x2 5 27 例5试用图解法求解下列线性规划问题st 3 无界解 或称无最优解 无界解是指线性规划问题的最优解无界 若是极大化问题 则可使目标函数值Z 极小化问题则可使目标函数值Z 有无界解的线性规划问题的可行域通常是无界区域 但反之则不必然 28 1O 2 4 x1 x2 2 4 Z 3 2 2x1 x2 2 x1 3x2 3 1O 3 3 29 4 无可行解某些线性规划问题的可行域是空集 即不存在满足所有约束条件的点 这时问题无可行解 当然更谈不上最优解了 在实际中出现这种情况可以认为资源条件无法满足人们的要求 即不存在可行方案 30 标准线性规划模型线性规划问题的标准形式 s t其中式 1 1 为目标函数 式 1 2 为约束条件 式 1 3 为非负条件 为称呼方便 有时也将式 1 3 称为约束条件 1 2 1 3 线性规划的标准形式 1 1 31 紧凑格式 s t 向量格式 s t 其中称为价值向量 为决策变量向量 为决策变量xj所对应的消耗系数向量 为资源向量 32 矩阵格式 其中为m n阶矩阵为价值向量 为决策变量向量 为资源向量 33 非标准形式线性规划问题的标准化 1 极大化与极小化 若 令 则有原目标函数 2 线性不等式与线性等式 其中为非负松弛变量 其中为非负剩余变量 34 3 非负变量与符号不受限制的变量 若xi的符号不受限制 则可引进非负变量xi1 xi2 令xi xi1 xi2 这样就可以使线性规划里所有的变量都转化为有非负限制的变量 例6将下述线性规划问题化为标准型 解 令 可将目标函数化为max型 令 其中 符号不受限制 35 考虑一个标准的线性规划问题 s t其中 为n维行向量 是n维列向量 是m维列向量 是m n阶矩阵 假定满足m n 且 m 标准型线性规划的解的概念 36 线性规划问题解的概念 1 可行解 满足约束条件 1 5 1 6 的解称为线性规划问题的可行解 可行解集称为线性规划问题的可行域 2 最优解 使目标函数 1 4 达到最优值的的可行解称为最优解 最优解常用表示 3 基 若 是 中m m阶非奇异矩阵 即 0 则称 是线性规划问题的一个基 37 若 是线性规划问题的一个基 那么 一定是由m个线性无关的列向量组成 不失一般性 可设称为基向量 与基向量相对应的变量称为基变量 一个线性规划的基通常不是唯一的 但是基的个数也不会超过个 一旦线性规划的基确定了 那么相应的基向量 基变量和非基变量也就确定了 38 4 基本解 设B是线性规划的一个基 若令n m个非基变量等于0 则所得的方程组 b的解称为线性规划问题的一个基本解 简称基解 有一个基就可以求得一个基本解 由基的有限性可知 基本解的个数也不会超过个 由于基本解中的非零分量可能是负数 所以基本解不一定是可行的 5 基本可行解 满足非负条件的基本解称为基本可行解 简称基可行解 与基本可行解对应的基成为可行基 基本可行解的非零向量的个数小于等于m 并且都是非负的 由于基本可行解的数目一般少于基本解的数目 因此可行基的数目也要少于基的数目 当基本可行解中有一个或多个基变量是取零值时 称此解为退化的基本可行解 39 线性规划问题各种解的关系可用文氏图表示 基本可行解 40 例7求下列约束方程所对应的线性规划的所有基本解 基本可行解 s t解 化为标准形式为2 4阶矩阵 且R A 2 所以该线性规划基的个数 6个取 为基变量 若令非基变量 约束方程组为可得对应的基本解是一个基本可行解 41 按相同步骤 可求得线性规划其他4个基 对应基本解是一个基本可行解 对应基本解是一个基本可行解 对应基本解不是一个基本可行解 对应基本解是一个基本可行解 42 若利用图解法画出线性规划的可行域 如图 C D O B A 4 4 8 43 线性规划的基本理论 由图解法的步骤 可以从几何的角度得出以下两个结论 1 线性规划问题的可行域是一个有界或无界的凸多边形 其顶点个数是有限个 2 若线性规划问题有最优解 那么最优解一定可在可行域的某个顶点上找到 44 几个基本概念 1 凸集 设k是n维欧式空间的一个点集 若任意两点X 1 k X 2 k的连线上的一切点 X 1 1 X 2 k 0 1 则称k为凸集 连接几何形体中任意两点的线段仍完全在该几何形体之中 有限个凸集的交集仍然是凸集 45 2 凸组合 设X 1 X 2 X k 是n维欧式空间中的k个点 若存在 1 2 k满足0 i 1 i 1 2 k 使X 1X 1 2X 2 kX k 则称X为X 1 X 2 X k 的凸组合 凸集k中任意两点X 1 X 2 连线上的任一点X都是X 1 与X 2 的一个凸组合 3 顶点 设k为凸集 X k 若X不能用X 1 k X 2 k两点的一个凸组合表示为X X 1 1 X 2 其中0 1 则称X为k的一个顶点 46 定理1若线性规划问题存在可行域 则其可行域是一个凸集 证明 为了证明满足 0的所有点 可行解 组成的几何体是凸集 只要证明 中任意两点任意两点连线上的一切点均满足线性约束条件既可 任取 满足则对任意的有 线性规划的基本定理 又因为均 0 所以由此可知 即 是凸集 47 证明 必要性 因为 是基本解 由基本解的定义 的非零分量所对应的系数列向量线性无关 又因为 是可行解 由基本可行解的定义 非零分量均是正的 所以 的正分量所对应的系数列向量线性无关 充分性 设 是线性规划问题的可行解 且正分量所对应的列向量也线性无关 则必有k m 若k m 则刚好构成一个基 为相应的基本可行解 若k m 则由线性代数知识 一定可以从其余的n k个系数列向量中取出m k个与构成最大线性无关向量组 其对应的基本可行解恰好为 不过此时的 是一个退化的基本可行解 引理1线性规划问题的可行解是基本可行解的充要条件是 的正分量所对应的系数列向量线性无关 48 定理2设线性规划问题的可行域 则 是 的一个顶点的充分必要条件是 为线性规划问题的基本可行解 证明思路 必要性 由引理1 若X是D的一个顶点 要证明X是线性规划的一个基本可行解 只要证明 的正分量所对应的系数列向量线性无关 用反证法 倘若 的正分量所对应的系数列向量线性相关 则可以在 中找到两点 使 与 是 的顶点矛盾 充分性 若 是线性规划的一个基本可行解 要证明 是可行域 的一个顶点 仍用反证法 倘若 不是可行域 的顶点 可以证明 的基变量所对应的系数列向量线性相关 与X是基本可行解矛盾 49 例8已知线性规划问题的约束条件为 试讨论可行域顶点和基本可行解之间的对应关系 解 可行域为四维凸多面体 可以推得在四维空间中有3个顶点 0 0 10 10 0 10 0 10 10 0 0 0 这3个顶点与线性规划的5个基本可行解的对应关系如下 顶点 对应以x3 x4为基变量的基本可行解 顶点 对应以x2 x4为基变量的基本可行解 顶点 对应x1 x2 x1 x3和x1 x4为基变量的退化基本可行解 50 一个线性规划问题 如果它的所有基本可行解都是非退化的 那么称这个线性规划是非退化的 只有在这种情况下 顶点和基本可行解之间才是一一对应的 定理3若可行域D非空有界 那么线性规划问题的目标函数一定可以在可行域D的顶点上达到最优值 本定理称为线性规划的基本定理 证明的思路是 因为可行域非空有界 所以线性规划一定有最优解 倘若不是点 且目标函数在该点处取到最优值 则必能找到可行域的一个顶点 使目标函数在的值也等于 定理3并不排除在一个非顶点上有一个最优解的可能性 但是在一个给定的线性规划问题的所有最优解中 至少有一个是顶点 如果可行域无界 则线性规划问题可能无最优解 如果目标函数同时在两个顶点上达到最优解 那么不难证明在这两个点的凸组合上也达到最优解 这时线性规划问题有无穷多最优解 51 第2章单纯形法 单纯形法的一般原理表格单纯形法借助人工变量求初始的基本可行解单纯形表与线性规划问题的讨论改进单纯形法 52 考虑到如下线性规划问题其中 一个m n矩阵 且秩为m 总可以被调整为一个m维非负列向量 为n维行向量 为n维列向量 根据线性规划基本定理 如果可行域 n 0 非空有界 则 上的最优目标函数值 一定可以在 的一个顶点上达到 这个重要的定理启发了Dantzig的单纯形法 即将寻优的目标集中在D的各个顶点上 单纯形法的一般原理 53 Dantzig的单纯形法把寻优的目标集中在所有基本可行解 即可行域顶点 中 其基本思路是从一个初始的基本可行解出发 寻找一条达到最优基本可行解的最佳途径 单纯形法的一般步骤如下 1 寻找一个初始的基本可行解 2 检查现行的基本可行解是否最优 如果为最优 则停止迭代 已找到最优解 否则转一步 3 移至目标函数值有所改善的另一个基本可行解 然后转到步骤 2 54 确定初始的基本可行解 确定初始的基本可行解等价于确定初始的可行基 一旦初始的可行基确定了 那么对应的初始基本可行解也就唯一确定为了讨论方便 不妨假设在标准型线性规划中 系数矩阵 中前m个系数列向量恰好构成一个可行基 即 其中 1 2 m 为基变量x1 x2 xm的系数列向量构成的可行基 m 1 Pm 2 Pn 为非基变量xm 1 xm 2 xn的系数列向量构成的矩阵 55 所以约束方程就可以表示为 用可行基 的逆阵 1左乘等式两端 再通过移项可推得 若令所有非基变量 则基变量由此可得初始的基本可行解 56 问题 要判断m个系数列向量是否恰好构成一个基并不是一件容易的事 基由系数矩阵 中m个线性无关的系数列向量构成 但是要判断m个系数列向量是否线性无关并非易事 即使系数矩阵 中找到了一个基B 也不能保证该基恰好是可行基 因为不能保证基变量 B 1b 0 为了求得基本可行解 必须求基 的逆阵 1 但是求逆阵 1也是一件麻烦的事 结论 在线性规划标准化过程中应设法得到一个m阶单位矩阵I作为初始可行基 57 若在化标准形式前 约束方程中有 不等式 那么在化标准型时除了在方程式左端减去剩余变量使不等式变成等式以外 还必须在左端再加上一个非负新变量 称为人工变量 若在化标准形式前 约束方程中有等式方程 那么可以直接在等式左端添加人工变量 为了设法得到一个m阶单位矩阵I作为初始可行基 可在性规划标准化过程中作如下处理 若在化标准型前 m个约束方程都是 的形式 那么在化标准型时只需在一个约束不等式左端都加上一个松弛变量xn i i 1 2 m 58 判断现行的基本可行解是否最优 假如已求得一个基本可行解 将这一基本可行解代入目标函数 可求得相应的目标函数值 其中分别表示基变量和非基变量所对应的价值系数子向量 59 要判定是否已经达到最大值 只需将代入目标函数 使目标函数用非基变量表示 即 其中称为非基变量 N的检验向量 它的各个分量称为检验数 若 N的每一个检验数均小于等于0 即 N 0 那么现在的基本可行解就是最优解 60 定理1最优解判别定理对于线性规划问题若某个基本可行解所对应的检验向量 则这个基本可行解就是最优解 定理2无穷多最优解判别定理若是一个基本可行解 所对应的检验向量 其中存在一个检验数 m k 0 则线性规划问题有无穷多最优解 61 基本可行解的改进 如果现行的基本可行解 不是最优解 即在检验向量中存在正的检验数 则需在原基本可行解 的基础上寻找一个新的基本可行解 并使目标函数值有所改善 具体做法是 先从检验数为正的非基变量中确定一个换入变量 使它从非基变量变成基变量 将它的值从零增至正值 再从原来的基变量中确定一个换出变量 使它从基变量变成非基变量 将它的值从正值减至零 由此可得一个新的基本可行解 由可知 这样的变换一定能使目标函数值有所增加 62 换入变量和换出变量的确定 换入变量的确定 最大增加原则 假设检验向量 若其中有两个以上的检验数为正 那么为了使目标函数值增加得快些 通常要用 最大增加原则 即选取最大正检验数所对应的非基变量为换入变量 即若则选取对应的为换入变量 由于且为最大 因此当由零增至正值 可使目标函数值最大限度的增加 63 换出变量的确定 最小比值原则如果确定为换入变量 方程其中为 中与对应的系数列向量 现在需在中确定一个基变量为换出变量 当由零慢慢增加到某个值时 的非负性可能被打破 为保持解的可行性 可以按最小比值原则确定换出变量 若 则选取对应的基变量为换出变量 64 定理3无最优解判别定理若是一个基本可行解 有一个检验数 但是 则该线性规划问题无最优解 证 令 则得新的可行解将上式代入因为 故当 时 Z 65 用初等变换求改进了的基本可行解 假设 是线性规划的可行基 则令非基变量 则基变量 可得基本可行解 用逆阵左乘约束方程组的两端 等价于对方程组施以一系列的初等 行变换 变换的结果是将系数矩阵 中的可行基 变换成单位矩阵I 把非基变量系数列向量构成的矩阵 变换成 把资源向量b变换成 66 且改进了的基本可行解只是在 的基变量的基础上用一个换入变量替代其中一个换出变量 其他的基变量仍然保持不变 这些基变量的系数列向量是单位矩阵I中的单位向量 为了求得改进的基本可行解 只需对增广矩阵施行初等行变换 将换入变量的系数列向量变换成换出变量所对应的单位向量即可 由于行初等变换后的方程组与原约束方程组或同解 67 例1 解 确定初始的基本可行解 基变量 非基变量 68 2 检验是否最优 检验向量因为 1 3 3 4均大于零 所以不是最优解 69 3 基本可行解的改进 选取换入变量因为max 3 4 4 取x3为换入变量 选取换出变量且 选取x4为换出变量 70 4 求改进了的基本可行解对约束方程组的增广矩阵施以初等行变换 使换入变量x3所对应的系数列向量变换成换出变量x4所对应的单位向量 注意保持基变量x5的系数列向量为单位向量不变 第一行除以 第二行减去第一行 71 可得改进的基本可行解 基变量 非基变量 基本可行解目标函数值易见目标函数值比原来的Z 1增加了 再转向步骤 2 72 2 检验是否最优 检验向量因为 所以仍不是最优解 73 3 基本可行解的改进 选取换入变量因为 取为换入变量 选取换出变量且 选取为换出变量 74 4 求改进了的基本可行解对约束方程组的增广矩阵施以初等行变换 使换入变量所对应的系数列向量变换成换出变量所对应的单位向量 第二行乘以 第一行减以第二行的 倍 75 可得改进的基本可行解 基变量 非基变量基本可行解目标函数值比Z 15增加了 再转向步骤 2 76 2 检验是否最优 检验向量因为所有检验数均小于零 所以是最优解 77 表格单纯形法 通过例 我们发现 在单纯形法的求解过程中 有下列重要指标 每一个基本可行解的检验向量根据检验向量可以确定所求得的基本可行解是否为最优解 如果不是最优又可以通过检验向量确定合适的换入变量 每一个基本可行解所对应的目标函数值通过目标函数值可以观察单纯形法的每次迭代是否能使目标函数值有效地增加 直至求得最优目标函数为止 在单纯形法求解过程中 每一个基本可行解 都以某个经过初等行变换的约束方程组中的单位矩阵 为可行基 当 时 1 易知 78 可将这些重要结论的计算设计成如下一个简单的表格 即单纯形表来完成 79 例2试利用单纯形表求例1中的最优解解 得初始的单纯形表 初始基本可行解 Z 1 12210 8 x4 1 30400 1 Z 34101 7 x5 1 x1x2x3x4x5 b XB CB 523 11 C 80 换入变量 换出变量 为主元进行旋转变换 基本可行解 Z 15 1 2111 20 4 x3 3 1 40 20 15 Z 5 230 1 21 3 x5 1 x1x2x3x4x5 b XB CB 523 11 C 12210 8 x4 1 30400 1 Z 34101 7 x5 1 x1x2x3x4x5 b XB CB 523 11 C 8 2 7 1 81 最优解最优值 换入变量 换出变量 为主元进行旋转变换 4 1 2 1 2111 20 4 x3 3 1 40 20 15 Z 3 5 2 5 230 1 21 3 x5 1 x1x2x3x4x5 b XB CB 523 11 C 02 513 5 1 5 17 5 x3 3 0 26 50 9 5 2 5 81 5 Z 16 50 1 52 5 6 5 x1 5 x1x2x3x4x5 b XB CB 523 11 C 82 例3用单纯形方法求解线性规划问题解 本题的目标函数是求极小化的线性函数 可以令则这两个线性规划问题具有相同的可行域和最优解 只是目标函数相差一个符号而已 83 01010 3 x2 2 0012 1 2 x3 0 01010 3 x2 2 4 1 10100 4 x3 0 3 1 01010 3 x4 0 10100 4 x3 0 0000 1 8 Z 100 21 2 x1 1 100 20 6 Z 2 1 100 21 2 x5 0 12000 0 Z 8 2 12001 8 x5 0 x1x2x3x4x5 b XB CB 12000 C 最优解最优值 2 2 3 1 84 因为非基变量x4的检验数 4 0 由无穷多最优解判别定理 本例的线性规划问题存在无穷多最优解 事实上若以x4为换入变量 以x3为换出变量 再进行一次迭代 可得以下单纯形表 最优解最优值最优解的一般表示式 85 对于极小化的线性规划问题的处理 先化为标准型 即将极小化问题变换为极大化问题 然后利用单纯形方法求解 直接利用单纯形方法求解 但是检验是否最优的准则有所不同 即 若某个基本可行解的所有非基变量对应的检验数 而不是 则基本可行解为最优解 否则采用最大减少原则 而非最大增加原则 来确定换入变量 即 若则选取对应的非基变量xm k为换入变量 确定了换入变量以后 换出变量仍采用最小比值原则来确定 86 借助人工变量求初始的基本可行解 若约束方程组含有 不等式 那么在化标准形时除了在方程式左端减去剩余变量 还必须在左端加上一个非负的人工变量 因为人工变量是在约束方程已为等式的基础上 人为的加上去的一个新变量 因此加入人工变量后的约束方程组与原约束方程组是不等价的 加上人工变量以后 线性规划的基本可行解不一定是原线性规划的问题的基本可行解 只有当基本可行解中所有人工变量都为取零值的非基变量时 该基本可行解对原线性规划才有意义 因为此时只需去掉基本可行解中的人工变量部分 剩余部分即为原线性规划的一个基本可行解 而这正是我们引入人工变量的主要目的 87 考虑线性规划问题 为了在约束方程组的系数矩阵中得到一个m阶单位矩阵作为初始可行基 在每个约束方程组的左端加上一个人工变量可得到 88 添加了m个人工变量以后 在系数矩阵中得到一个m阶单位矩阵 以该单位矩阵对应的人工变量为基变量 即可得到一个初始的基本可行解这样的基本可行解对原线性规划没有意义的 但是我们可以从X 0 出发进行迭代 一旦所有的人工变量都从基变量迭代出来 变成只能取零值的非基变量 那么我们实际上已经求得了原线性规划问题的一个初始的基本可行解 此时可以把所有人工变量剔除 开始正式进入求原线性规划最优解的过程 89 大M法 大M法首先将线性规划问题化为标准型 如果约束方程组中包含有一个单位矩阵I 那么已经得到了一个初始可行基 否则在约束方程组的左边加上若干个非负的人工变量 使人工变量对应的系数列向量与其他变量的系数列向量共同构成一个单位矩阵 以单位矩阵为初始基 即可求得一个初始的基本可行解 为了求得原问题的初始基本可行解 必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量 为此可以在目标函数中赋予人工变量一个绝对值很大的负系数 这样只要基变量中还存在人工变量 目标函数就不可能实现极大化 以后的计算与单纯形表解法相同 只需认定是一个很大的正数即可 假如在单纯形最优表的基变量中还包含人工变量 则说明原问题无可行解 否则最优解中剔除人工变量的剩余部分即为原问题的初始基本可行解 90 例4用大M法求解下面的线性规划问题 解 首先将原问题化为标准型添加人工变量 并在目标函数中分别赋予 91 01 1 2 1 201 21 2 3 2 X2 2 10 1 21 201 2 1 2 1 2 X1 1 110 1001 1 X2 2 1 2 20 1101 1 1 X6 M 1 1 110 1001 1 X7 M 2 1 11 10010 2 X6 M 001 23 20 1 2 M 3 2 M 5 2 Z 001 21 21 1 2 1 2 3 2 X5 0 1 2M0 M2 M00 2 2M 2 M Z 2 1 100110 1 2 X5 0 12 2M M M000 3M Z 3 1 0100100 3 X5 0 X1X2X3X4X5X6X7 b XB CB 12000 M M C 92 0100100 3 X2 2 100110 1 2 X4 0 11 10010 2 X2 2 20 1101 1 1 X4 0 01 1 2 1 201 21 2 3 2 X2 2 1 2 1 2 10 1 21 201 2 1 2 1 2 X1 1 1000 2 M M 6 Z 10101 10 1 X3 0 30200 2 M M 4 Z 10101 10 1 X5 0 001 23 20 1 2 M 3 2 M 5 2 Z 3 2 1 2 001 21 21 1 2 1 2 3 2 X5 0 X1X2X3X4X5X6X7 b XB CB 12000 M M C 最优解最优值 93 两阶段法 两阶段法引入人工变量的目的和原则与大M法相同 所不同的是处理人工变量的方法 两阶段法的步骤 求解一个辅助线性规划 目标函数取所有人工变量之和 并取极小化 约束条件为原问题中引入人工变量后包含一个单位矩阵的标准型的约束条件 如果辅助线性规划存在一个基本可行解 使目标函数的最小值等于零 则所有人工变量都已经 离基 表明原问题已经得了一个初始的基本可行解 可转入第二阶段继续计算 否则说明原问题没有可行解 可停止计算 求原问题的最优解 在第一阶段已求得原问题的一个初始基本可行解的基础上 继续用单纯形法求原问题的最优解 94 例5用两阶段法求解例4中的线性规划问题 解 首先将问题化为标准型添加人工变量x6 x7 并建立辅助线性规划如下 由于辅助线性规划的目标函数是极小化 因此最优解的判别准则应为 95 01 1 2 1 201 21 2 3 2 X2 0 10 1 21 201 2 1 2 1 2 X1 0 110 1001 1 X2 0 1 2 20 1101 1 1 X6 1 1 1 110 1001 1 X7 1 2 1 11 10010 2 X6 1 0000011 0 W 001 21 21 1 2 1 2 3 2 X5 0 201 1002 1 W 2 1 100110 1 2 X5 0 0 211000 3 W 3 1 0100100 3 X5 0 X1X2X3X4X5X6X7 b XB CB 0000011 C 辅助规划所有检验数 原问题已得一个初始基本可行解 96 由上表可知 通过若干次旋转变换 原问题的约束方程组已变换成包含一个单位矩阵的约束方程组该约束方程组可作为第二阶段初始约束方程组 将目标函数则还原成原问题的目标函数 可继续利用单纯形表求解 97 1000 2 6 Z 1001101001 10101 231 X4X2X3 020 30200 4 Z 20 11011 100 10101 121 X4X2X5 020 001 23 20 5 2 Z 1 2 1 2 3 2 1 2 10 1 21 2001 1 2 1 20001 21 21 1 23 23 2 X1X2X5 120 X1X2X3X4X5 b XB CB 12000 C 可得最优解 目标函数值maxZ 6 与用大M法的结果完全相同 98 单纯形表与线性规划问题的讨论 无可行解 通过大 法或两阶段法求初始的基本可行解 但是如果在大 法的最优单纯形表的基变量中仍含有人工变量 或者两阶段法的辅助线性规划的目标函数的极小值大于零 那么该线性规划就不存在可行解 人工变量的值不能取零 说明了原线性规划的数学模型的约束条件出现了相互矛盾的约束方程 此时线性规划问题的可行域为空集 99 例6求解下列线性规划问题解 首先将问题化为标准型令 则 故引入人工变量 并利用大M法求解 100 C 3 2 1000 M M CB XB b X1X2X3X4X5X6X7X8 0 M M X4X7X8 643 1111000010 10 101001 100 101 6 1 3 1 Z 7M 6 4M 15 M 3 M 2 M 1 2M0 M M00 0 M 2 X4X7x2 343 1021010 110 10 101001 100 101 3 14 1 Z Z 3 M0 3 M0 M 202 M 3 M 2 X1X7X2 313 1021010 100 3 1 1 11101 100 101 003 3M3 M M1 M0 1 在以上最优单纯形表中 所有非基变量检验数都小于零 但在该表中人工变量x7 1为基变量 所以原线性规划不存在可行解 101 无最优解 无最优解与无可行解时两个不同的概念 无可行解是指原规划不存在可行解 从几何的角度解释是指线性规划问题的可行域为空集 无最优解则是指线性规划问题存在可行解 但是可行解的目标函数达不到最优值 即目标函数在可行域内可以趋于无穷大 或者无穷小 无最优解也称为有限最优解 或无界解 判别方法 无最优解判别定理在求解极大化的线性规划问题过程中 若某单纯形表的检验行存在某个大于零的检验数 但是该检验数所对应的非基变量的系数列向量的全部系数都为负数或零 则该线性规划问题无最优解 可以 可以 102 例7试用单纯形法求解下列线性规划问题 解 引入松弛变量x3 x4化为标准型 因但所以原问题无最优解 103 退化解 当线性规划问题的基本可行解中有一个或多个基变量取零值时 称此基本可行解为退化解 产生的原因 在单纯形法计算中用最小比值原则确定换出变量时 有时存在两个或两个以上相同的最小比值 那么在下次迭代中就会出现一个甚至多个基变量等于零 遇到的问题 当某个基变量为零 且下次迭代以该基变量作为换出变量时 目标函数并不能因此得到任何改变 由旋转变换性质可知 任何一个换入变量只能仍取零值 其他基变量的取值保持不变 通过基变换以后的前后两个退化的基本可行解的坐标形式完全相同 从几何角度来解释 这两个退化的基本可行解对应线性规划可行域的同一个顶点 解决的办法 最小比值原则计算时存在两个及其以上相同的最小比值时 选取下标最大的基变量为换出变量 按此方法进行迭代一定能避免循环现象的产生 摄动法原理 104 例8求解下述线性规划问题 解 引入松弛变量化标准型 105 0 0 0 24 2 80 3 0 Z 5 6 0 42 0 8 0 5 Z 1 0 0 0 1 0 0 1 x3 2 1 2 0 6 0 24 1 1 x1 3 3 2 1 30 0 8 0 3 x5 0 0 3 0 42 5 8 0 0 Z 1 1 0 0 1 0 0 1 x7 0 0 1 0 6 1 24 1 0 x1 3 0 1 1 30 3 8 0 0 x5 0 1 1 0 0 1 0 0 1 x7 0 0 0 1 0 6 1 24 1 0 x6 0 0 0 0 1 36 4 32 1 0 x5 0 x7 x6 x5 x4 x3 x2 x1 b XB CB 0 0 0 24 2 80 3 C 第一次迭代中使用了摄动法原理 选择下标为6的基变量x6离基 可得最优解 目标函数值maxZ 106 无穷多最优解判别原理 若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零 但其中存在一个检验数等于零 那么该线性规划问题有无穷多最优解 例最优表 非基变量检验数 所以有无穷多最优解 最优解集为可行域两个顶点的凸组合 无穷多最优解 107 改进单纯形法的特点利用单纯形表求解线性规划时 每一次迭代都把整个单纯形表计算一遍 事实上我们关心的只是以下一些数据 基本可行解 其相应的目标函数值 非基变量检验数 及其换入变量 设主元列元素 及其换出变量 设利用它们可得到一组新的基变量以及新的可行基 1 改进单纯形法 为基变量下标 为非基变量下标 108 对任一基本可行解 只要知道 上述关键数据都可以从线性规划问题的初始数据直接计算出来 因此如何计算基本可行解 对应的可行基 的逆阵成为改进单纯形法的关键 改进单纯形法推导出从可行基 变换到 1时 到的变换公式 当初始可行基为单位矩阵 时 变换公式将更具有优越性 因为这样可以避免矩阵求逆的麻烦以下推导从到的变换公式 109 假设当前基 基变换中用非基变量取代基变量可得新基前后二个基相比仅相差一列 且比较以上二式 可得 其中表示第个元素为1 其他元素均为零的单位列向量 为主元列元素 110 假设 则 第列 换出变量对应列 第行 所以由 主元素 111 改进单纯形法的步骤 1 根据给出的线性规划问题的标准型 确定初始基变量和初始可行基 求初始可行基B的逆阵 1 得初始基本可行解 2 计算单纯形乘子 得目标函数当前值 3 计算非基变量检验数 若 N 0 则当前解已是最优解 停止计算 否则转下一步 4 根据 确定非基变量为换入变量 计算 若 0 则问题没有有限最优解 停止计算 否则转下一步 112 5 根据 确定基变量为换出变量 6 用替代得新基 1 由变换公式计算新基的逆阵 1 1 求出新的基本可行解其中为变换矩阵 构造方法是 从一个单位矩阵出发 把换出变量在基B中的对应列的单位向量 替换成换入变量对应的系数列向量 并做如下变形 主元素 应在主对角线上 取倒数 其他元素除以主元素并取相反数 重复 2 6 直至求得最优解 113 换入 无界解 换出 最优解 初始基 新基 114 例9试用改进单纯形法求解解 观察法确定 为基变量为非基变量 115 2 计算单纯行乘子目标函数当前值 3 非基变量检验数 4 选择换入变量故为换入变量 计算 116 确定换出变量确定为换出变量 主元素 6 用代替得新可行基为基变量 为非基变量 重复以上步骤 进入第二循环 117 1 2 3 118 4 选择换入变量 5 选择换出变量 主元素 6 用代替得新可行基为基变量 为非基变量 进入第三循环 119 1 2 3 非基变量对应的检验数全部非正 故当前解即为最优解 相应的目标函数最优值 120 第3章对偶规划与灵敏度分析 对偶线性规划对偶定理对偶最优解的经济解释 影子价格对偶单纯形法灵敏度分析 121 对偶理论是线性规划的重要内容之一 随着线性规划问题研究的深入 人们发现对应于每个线性规划问题都伴生一个相应的线性规划问题 前者是由矩阵 右端向量 和价值向量 定义的 称之为原问题 后者也是由相同的数据集合 和 构成的 称之为原问题的对偶问题 一对原问题和对偶问题是紧密关联的 它们不但有相同的数据集合 相同的最优目标函数值 而且在求得一个线性规划的最优解的同时 也同步得到对偶线性规划的最优解 对偶理论深刻地指示了原问题和对偶问题的内在联系 由对偶问题引伸出来的对偶解还有着重要的经济意义 是研究经济学的重要概念和工具之一 122 对偶问题的提出例1某工厂生产甲 乙两种产品 这两种产品需要在A B C三种不同设备上加工 每种甲 乙产品在不同设备上加工所需的台时 它们销售后所能获得的利润 以及这三种设备在计划期内能提供的有限台时数均列于表 试问如何安排生产计划 即甲 乙两种产品各生产多少吨 可使该厂所获得利润达到最大 对偶线性规划 123 假设计划期内甲乙两种产品各生产吨 用图解法或单纯形法可求得最优解 元 即在计划期内甲产品生产吨 乙产品生产8吨 可以使总利润达到最大 为元 124 现在从另一个角度来考虑该工厂的生产问题 假设该厂的决策者打算不再自己生产甲 乙产品 而是把各种设备的有限台时数租让给其他工厂使用 这时工厂的决策者应该如何确定各种设备的租价 设分别为设备A B C每台时的租价 约束条件 把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润目标函数 所获租金总额尽量少 125 由此可得两个对称的线性规划 矩阵形式 126 对偶线性规划考虑如下具有 不等式约束的线性规划问题加入松弛变量XS xn 1 xn 2 xn m T以后可得标准型若B是系数矩阵 A I 中的一个可行基 并假设 A I 可表示为 B N 则线性规划问题可改写为可得基本可行解 目标函数值 若非基变量检验数则为最优解 127 因为基变量检验数 最优解判别准则又可表述为 上述表达式又可写成即 其中称为单纯形乘子 所以当为最优解 且单纯形乘子用符号 示时 可以推得 且由 所以只存在最小值 由此可以得到另一个线性规划 称之为原线性规划问题的对偶问题 128 线性规划问题标准型的对偶问题考虑一个标准形式的线性规划问题由于任何一个等式约束都可以用两个不等式约束等价地表示 所以标准形线性规划问题