管理运筹学全套课件-文档资料.ppt

管理运筹学 数学的魅力与实质 数学的本质是处理抽象对象 是比语言更精炼 更严谨的符号系统 是人类理性的集中体现 数学的方法是建立一个牢不可破的公理体系 并以演绎推理的方法去构建和扩展整个学科体系 应用 演绎方法 公理体系 数学大厦 数学的魅力与实质 数学方法在自然科学体系中无处不在 并取得了光辉的成就 19世纪以后 数学被广泛深入地应用于社会科学领域 经济学 管理学领域的许多大师具有高超的数学技能 数学的魅力与实质 本门课程不仅要学习一门课程 一套方法 更重要的是要学会理性分析问题的方法 培养逻辑思维能力和抽象思维能力 数学在发展的过程中遇到过许多问题 而且也并非确切无疑 大家要敢于质疑 敢于提问题 数学的魅力与实质 一个例子 S 1 1 1 1 1 请问S等于多少 数学的魅力与实质 至少有三种解法 1 S 1 1 1 1 1 1 2 S 1 1 1 1 1 3 1 S 1 1 1 1 1 1 1 1 1 1 1 S得到2S 1 从而S 1 2 数学的魅力与实质 事实上 这是一个争论未定的题目 反映了人类对自然认识的不足 无穷的概念存在许多不足之处 而且并非绝对精确 不同的学派对无穷有着不同的认识 考核方法 平时成绩占20 每位同学的初始成绩都是60分 按100分为满分计算 每次作业交上加1分 不交不加不减 拷贝别人作业一次扣2分 上课主动回答问题每次加2分 提出有价值问题或发现老师错误每次加5分 运筹学的体系和发展历史 定义运筹学是一门应用于管理有组织系统的科学它为掌管这类系统的人提供决策目标和数量分析的工具运筹学应用分析 实验 量化的方法 对经济管理系统中人 财 物等有限资源进行统筹安排 为决策者提供有依据的最优方案 以实现最有效的管理正式起源与二次世界大战 被称为Operationsresearch 日本人翻译为运做学 台湾人翻译为作业研究 运筹学的体系和发展历史 田忌赛马萌芽在20世纪初 Lanchester战斗方程 丹麦工程师爱尔朗研究电话通讯系统时提出了一些排队论的公式 30年代 数学家列温逊运用运筹思想分析商业广告 顾客心理 运筹学的体系和发展历史 二次世界大战中 英美科学家研究如何有效运用雷达 研究船队遇到袭击如何减少损失 以及如何使用深水炸弹等紧迫问题 应用 德国潜艇被摧毁数增加到400 船只中弹数由47 减少到29 结果 打赢了空战和海战 保证了二次世界大战的最终胜利 运筹学在现实生活中的例子 企业安排生产计划库存管理公交系统优化食堂窗口设置电脑游戏 帝国时代 魔兽争霸等 运筹学的学科体系 规划论 包括线性规划 非线性规划 整数规划等 1947年 Danzig提出单纯形法 随后规划方法得到了广泛的应用 图论与网络分析 图是研究离散事物之间关系的一种分析模型 例 有甲 乙 丙 丁 戊 己6名同学参加ABCDEF六个项目的比赛 下表是各运动员报名参赛的项目 问6个项目顺序如何安排 作到每名运动员不连续参加两项比赛 运筹学的学科体系 运筹学的学科体系 排队论 研究公共服务系统的运行与优化的数学理论方法 决策论 研究不确定情况以及风险情况下的决策 存储论 研究企业的库存计划 进货周期等 博弈论 研究竞争环境下决策者行为的数学方法 运筹学的工作步骤 提出和形成问题 弄清问题的目标 可能的约束 问题的可控变量 相关参数等 建立模型 把问题中的可控变量 参数 目标 约束之间的关系用一定的模型表示出来 求解 用计算或实验方法求出问题的解 解的检验 检查求解过程 检查解能否反映现实问题 解的实施 将解运用到实际问题中 第一章线性规划 本章内容 线性规划模型线性规划问题的图解法单纯形法非标准形线性规划的解法 线性规划模型 规划问题 就是否合理利用有限资源的问题 线性规划 线性的规划问题 两个意思 1 目标函数是线性的2 约束条件是线性的 线性规划模型 生产决策问题某汽车工厂生产大轿车和载重汽车两种型号的汽车 已知每辆汽车所用的钢材都是2吨 辆 该工厂每年供应的钢材为1600吨 工厂的生产能力是每2 5小时可生产一辆载重汽车 每5小时可生产一辆大轿车 工厂全年的有效工时为2500小时 已知供应给该厂大轿车用的座椅每年可装配400辆 据市场调查 出售一辆大轿车可获利4000元 出售一辆载重汽车可获利3000元 如何安排生产才能使工厂获利最大 线性规划模型 建模型如下 设大轿车数量为x1 载重汽车数量为x2 s t 是subjectto的简写 表示受限制于 线性规划模型 某工厂在计划期间内生产 两种产品 已知生产单位产品所需的设备台时及A B两种原材料的消耗 如下表所示 已知 两种产品每单位分别可以获利50元 100元 问工厂应该如何安排生产才能使工厂获利最多 线性规划模型 设置变量 生产 产品x1个 产品x2个目标函数是利润最大化 资源是有限的 第一个限制是设备台时的限制 线性规划模型 第二个限制是原材料A的限制 第三个限制是原材料B的限制 显然 产量不可能为负数 线性规划模型 建模型如下 设生产 产品x1件 产品x2件 线性规划模型 1 2 分别被称为目标函数和约束条件 目标函数中变量的系数被称为价值系数 约束条件不等号右端称为资源向量或限定系数 约束条件左端变量的系数被称为技术系数 目标函数和约束条件都是一次幂函数 或称线性函数 因此这类规划问题被称为线性规划问题 线性规划模型 例3 生产卷烟的主要原材料包括烟叶和烟梗 国家规定每千克焦油含量不超过15mg 烟气烟碱含量不超过1 4mg 现在知道每千克烟叶含焦油12mg 烟气烟碱1 5mg 烟梗含焦油18mg 烟气烟碱0 3mg 烟叶每千克50元 烟梗每千克20元 问如何搭配使生产成本最小 线性规划模型 设每千克卷烟用烟叶x1千克 烟梗x2千克 模型如下 这是目标函数一个求最小化的问题 线性规划的标准形 为求解方便 一般线性规划都可以转化成如下标准形式 要求 线性规划的标准形 目标函数为求最小化时 等式两端同乘以 1 变为求最大化 约束条件为 时 减一个剩余变量 资源变量为负数时 等式两端同乘以 1 变量为 0时 令变量无约束时 令 线性规划的图解法 以例1为例 线性规划的图解法 x2 800 400 400 800 x1 线性规划的图解法 从图中可以得到 x1 200 x2 600 z 2600最优解为 生产200辆大轿车 生产600辆载重汽车 可获利润2600千元 钢材和工时全部用完 座椅剩余200套 几个概念 凸集 设k是n维欧氏空间中的一个点集 在集合中任意取两点x1 x2 k 如果这两点连线上的一切点都落在k中 则称k为凸集 角顶 设k为凸集 x k 如果不能用不同的两点x1 x2 k线性表出x 则称x为k的一个角顶 角顶可行解和角顶不可行解 既是角顶解又是可行解的解称为角顶可行解 是角顶解而不是可行解的解称为角顶不可行解 图解法的几点启示 线性规划的可行域必定为凸集 线性规划的最优解必定在顶点取得 如果有多个最优解 那么至少有两个相邻的角顶可行解是最优解 角顶可行解的数目是有限的 如果一个角顶可行解的目标函数值比相邻的所有角顶解好 它就是最优解 解决线性规划问题的思路 基本思路是在满足约束条件的前提下 从一个初始顶点开始 不断寻找改进目标函数的顶点 直到无法改进为止 步骤1 从一个角顶可行解出发 判断相邻的角顶可行解是否比目前的点更好 如果相邻的角顶可行解都劣与这个顶点 则说明这个点已经是最优解 算法结束 步骤2 如果相邻的角顶可行解更好 就向这个点移动 重复步骤1 线性规划问题解的基本概念 可行解 满足约束条件解称为可行解 对应图解法的阴影部分 基 约束条件中任意一个m阶非奇异子矩阵确定一个线性规划问题的基 对应图解法中的顶点 基可行解 既是可行解又是基解称为基可行解 最优解 满足目标函数和约束条件的解称为最优解 单纯形法 求解单纯形法的步骤单纯形表法单纯形表法中的一些特殊情况 求解单纯形法的步骤 步骤1 将模型转化为标准形 步骤2 找到一个初始可行基 列出初始单纯形表 步骤3 判断初始可行基是否最优 如果是最优解则结束 否则转步骤4 步骤4 如果不是最优 则通过一定的规则将一个变量换出 另一个变量换入 构成一个新的基解 转步骤3 求解单纯形法的步骤 x2 800 400 400 800 x1 求解单纯形法的步骤 图形解法只能解决2维的线性规划问题 仅有两个变量 对超过3维的情况 既无法在平面上画出图形 也无法进行直观的想象 根据图形解法的启示 提出单纯形法解决线性规划问题的基本思路 单纯形表法 以例一为例 单纯形表法 步骤1 首先转化为标准形式 添加松弛变量 单纯形表法 步骤2 找到一个初始可行基 即寻找一个m阶的非奇异子矩阵 从标准形的线性规划问题中可以看出 x3 x4 x5构成了一个3阶的单位矩阵 把这三个变量作为初始可行基 列出初始单纯形表 单纯形表法 列出初始单纯形表 单纯形表法 步骤3 确定换入换出变量 方法 先确定换入变量 计算检验数zj cj 计算方法 cj为对应xj的系数 以最负的检验数对应的系数列作为主列元素 随后确定换出变量 计算检验数 计算方法 选择 值最小的行对应的主列元素作为换出变量 单纯形表法 确定换入换出变量 单纯形表法 步骤4 以主元素为中心 进行迭代运算 单纯形表法 检验数仍然有负数 继续确定换出换入变量 单纯形表法 迭代运算 单纯形表法 继续迭代 单纯形表法 从表中可以看出 检验数全部为正数或零 说明已达到最优 求得最优解为 x1 200 x2 600 x3 0 x4 0 x5 200 Z 2600 生产方案为 生产大轿车200辆 生产载重汽车600辆 剩余座椅200套 利润为2600千元 单纯形表法 思考题1 用单纯形法求解线性规划问题时为什么要首先转化为标准形 2 为什么要选择松弛变量作为初始可行基 能不能任意选择几个变量作为初始可行基 作业 求解线性规划问题 作业 某工厂在计划期内要生产A B两种产品 已知生产单位产品所需的设备台时及甲 乙两种原材料的消耗如下表所示 作业 该工厂每生产一件产品A可以获利2元 每生产一件产品B可以获利3元 问应该如何安排计划使该工厂获利最多 要求 建立线性规划模型并用单纯形法求解 单纯形表法 例2 用单纯形表法求解线性规划问题 单纯形表法 步骤1 首先转化为标准形式 添加松弛变量 单纯形表法 步骤2 找到一个初始可行基 从标准形的线性规划问题中可以看出 x3 x4 x5构成了一个3阶的单位矩阵 把这三个变量作为初始可行基 列出初始单纯形表 单纯形表法 列出初始单纯形表 x1x2x3x4x5 xCj zj zj cj 50100000 111002101001001 b 单纯形表法 步骤3 确定换入换出变量 确定换入变量 计算检验数zj cj 计算方法 cj为对应xj的系数 以最负的检验数对应的系数列作为主列元素 随后确定换出变量 计算检验数 计算方法 选择 值最小的行对应的主列元素作为换出变量 单纯形表法 确定换入换出变量 单纯形表法 步骤4 以主元素为中心 进行迭代运算 单纯形表法 检验数仍然有负数 继续确定换出换入变量 x1x2x3x4x5 xCj zj 500000 zj cj 0100000 50100000 1 010 12001 101001 b 25000 单纯形表法 迭代运算 x1x2x3x4x5 xCj zj 0050050 zj cj 5010050050 50100000 1010 100 21101001 b 27500 单纯形表法 检验数全部大于等于0 已经求得最优解 最优解为 x1 50 x2 250 x3 0 x4 50 x5 0 Z 27500 单纯形表法 例3 某工厂在计划期内要生产A B两种产品 已知生产单位产品所需的设备台时及甲 乙两种原材料的消耗如下表所示 单纯形表法 该工厂每生产一件产品A可以获利2元 每生产一件产品B可以获利3元 问应该如何安排计划使该工厂获利最多 要求 建立线性规划模型并用单纯形法求解 单纯形表法 A产品的产量设为x1 B产品的产量设为x2 建立模型如下 单纯形表法 最终单纯形表为 单纯形表法中一些问题 如果两个 相同 有可能产生退化现象 死循环 可以用摄动法求解 就是选下标最小的变量作为换出变量 有一个以上的非基变量为0时 说明有无穷多解 这时换入换出变量做完之后Z值不变 这时两个点连线上的任何一点都是最优解 主列元素全部为负数或0时 这时 值无法计算 也无法确定换出变量 则此时说明有无界解 此时检查你的计算过程看前面计算是否出现错误 或检查建模是否有错误 思考题 当变量无约束时 需要做变换 请问 会同时出现在最终单纯形表中吗 为什么 单纯形法的进一步讨论 目标函数求最小化时 有两种解决方法 1 目标函数左右同乘以 1 变成求最大化的问题 2 直接用单纯形法计算 但是检验规则改变 以正的检验数对应的变量作为换入变量 当全部检验数为负数时迭代结束 单纯形法的进一步讨论 当约束条件出现等号约束时 无法通过增加松弛变量的方法产生初始可行解 这时要使用增加人工变量的方法来产生初始可行基 由于人工变量在最终解中必须为0 否则无法满足约束条件 如何使人工变量在最优解中为0 用大M法 大M法 当目标函数是求极大值时 令人工变量在目标函数中的系数为 M 其中M是一个非常大的正数 这样 如果人工变量不为0 则目标函数就无法取到最优 当目标函数是求最小时 令人工变量在目标函数中的系数为M 为什么 大M法 例4 大M法 化为标准形 约束条件变为 大M法 系数行列式为 这时无法直接在系数矩阵中找到一个初始可行解 把第三个约束条件添加一个人工变量 大M法 约束条件 变为 由这两个式子可以看出x5必定等于0 大M法 系数行列式变为 出现了一个三维的单位矩阵 可以用单纯形法求解了 但还要保证x5 0 所以目标函数变形为 大M法 列出初始单纯形表 大M法 迭代计算 大M法 迭代运算 x1x2x3x4x5 xCj zj 00 4 502 5 M zj cj 35 4 502 5 3500 M 101000031 101 1 500 5 b 27 大M法 迭代计算 x1x2x3x4x5 xCj zj 0001 5M 1 zj cj 3501 51 3500 M 100 1 31 30011 3 1 30101 20 b 36 大M法 大于等于约束条件当出现大于等于约束条件时 首先添加一个剩余变量 使约束条件变为等式约束 然后再添加一个人工变量 用大M法求解 常数项为负数时 先在等式两边同乘 1 使资源变量变为正数 然后再根据相应情况进行处理 趣味数学 这是基诺未能想出来的又一个悖论 一条蠕虫在橡皮绳的一端 橡皮绳长一公里 蠕虫以每秒1厘米的稳定速度沿橡皮绳爬行 在1秒钟之后 橡皮绳就像橡皮筋一样拉长为2公里 再过一秒钟后 它又拉长为3公里 如此下去 蠕虫最后究竟会不会达到终点呢 作业 将本问题转化为标准形 并列出初始单纯形表 作业 求解线性规划问题 第二章对偶理论和灵敏度分析 本章内容 对偶问题的提出原问题与对偶问题原问题与对偶问题的转化影子价格对偶问题的求解灵敏度分析 对偶问题的提出 对偶现象无论是从理论还是实践 对偶问题是线性规划最重要和最有趣的概念和理论刻划四边形面积与周长之间的关系周长一定的四边形中 面积为最大面积一定的四边形中 周长为最小一种现象的两种提法线性规划问题原问题 求目标最大对偶问题 求目标最小 对偶问题的提出 例1美佳公司计划制造 两种家电产品的生产 已知生产单位产品所需的设备A B C台时如下 该公司每生产一单位产品 可获利50元 100元 问 如何达到利润最大 对偶问题的提出 例1的决策问题 生产多少个 产品和 产品才能使利润达到最大设决策变量x1为生产 产品的数量 x2为生产 产品的数量最大利润 maxz 50 x1 100 x2约束条件 x1 x2 3002x1 x2 400 x2 250 x1 x2 0 对偶问题的提出 生产产品 创造最大利润 出赁设备 确定合理租金 出赁设备总租金不应低于原利润 全部设备的总租金越低越好 对偶问题的提出 设决策变量y1 y2 y3为设备A B C每台时的租金最小租金 minf 300y1 400y2 250y3 原问题与对偶问题 原问题某企业有m种资源 生产n种产品各种资源的拥有量为bi xj为产量 aij为生产第j种产品所消耗第i种资源的数量 cj为产值 原问题与对偶问题 对偶问题出让资源 获取回报 付出代价条件 同等数量资源出让的代价应不低于组织生产的产值yi出让第i种资源付出的代价 原问题与对偶问题 两者的关系 原问题与对偶问题的转化 例2 写出下列问题的对偶问题及对偶的对偶问题 原问题与对偶问题的转化 对偶问题 对偶的对偶问题 原问题与对偶问题的转化 目标函数求最小等式约束xj 0 xj取值无约束 原问题与对偶问题的转化 例3写出下述线性规划的对偶问题 原问题与对偶问题的转化 对偶问题 影子价格 原问题与对偶问题的重要性质Yi对一个第i种资源的估价 不是资源的市场价格是企业根据资源在生产中作出的贡献的估价影子价格 对资源在生产中作出的贡献的估价对偶变量Yi单位资源在最优利用条件下所产生的经济效果特征影子价格依赖于资源利用情况 是未知量 随生产任务 产品结构情况变化 影子价格 一种边际价格 yi的值相当于在给定的生产条件下 bi每增加一个单位时 目标函数z的增加量一种机会成本当市场价格低于影子价格时 购进资源 增加生产 提高利润当市场价格高于影子价格时 出售资源 提高利润随着影子价格的买进和卖出 影子价格随之变动 直到影子价格与市场价格保持同等水平 才处于平衡 影子价格 线性规划的原问题是确定资源的最优分配方案 而对偶问题是确定对资源的恰当评估大公司借助资源的影子价格确定一些内部结算价格 以控制资源的使用和考核下属企业的经营状况在社会资源的有效配置中 可借助影子价格规定使用最紧缺资源一个单位必须上缴的利润额 以控制一些效益低的企业自觉节约使用紧缺资源 对偶问题的求解 利用原问题单纯形法 确定初始基可行解 转换为新基可行解 建立最优解判断准则 例4 求对偶问题的解 对偶问题的求解 对偶问题的求解 用单纯形法解 添加两个剩余变量 两个人工变量 用大M法求解 非常麻烦 运算量比较大 当约束条件个数很多时 计算量成倍增加 对偶问题的性质 弱对偶性 如果X Y分别是原问题和对偶问题的可行解 则存在 CX YB对偶定理 若原问题有最优解 则对偶问题也有最优解 且目标函数值相等 解的互补松弛性 原问题的基变量对应于对偶问题的松弛变量的检验数 原问题的松弛变量对应于对偶问题的基变量的检验数 对偶单纯形法基本思想 在保持对偶问题为可行解的基础上 逐步迭代 减小目标值 当原问题也达到可行解时 得到了目标函数的最小值 对偶问题的求解 对偶问题的求解 步骤1 根据线性规划问题 列出初始单纯形表 检查b列数字 若都为非负 检验数也均为非负 则已经得到最优解 否则转步骤2 步骤2 确定换出变量 选择最负的基变量为换出变量 步骤3 确定换入变量 如果换出变量对应的行系数全部非负 则无可行解 否则 用换出变量那一行具有负值的系数分别去除同列的检验数 取绝对值最小者对应的变量为换入变量 对偶问题的求解 步骤4 以换入变量对应的行和换出变量对应的列交点对应的元素做为主元素 进行迭代运算 得到新的单纯形表 步骤5 最优性检验 如果b列元素和检验数全部为非负 则已得到最优解 否则转步骤2 对偶单纯形法 步骤1 转换并列出初始单纯形表 对偶单纯形法 初始单纯形表 b b列系数为负 检验数为正 说明原问题为可行解 而对偶问题为不可行解 转步骤2 对偶单纯形法 确定换入换出变量 选b列系数最负的值为换出变量 用换出变量那一行具有负值的系数分别去除同列的检验数 取绝对值最小者对应的变量为换入变量 转步骤4 b 对偶单纯形法 迭代运算 y1y2y3y4y5 以换入变量对应的行和换出变量对应的列交点对应的元素做为主元素 进行迭代运算 得到新的单纯形表 b列系数仍存在负数 转步骤2 b 对偶单纯形法 确定换入换出变量 以换入变量对应的行和换出变量对应的列交点对应的元素做为主元素 进行迭代运算 得到新的单纯形表 b列系数仍存在负数 转步骤2 b 对偶单纯形法 迭代运算 以第一行和第一列交点对应的元素做为主元素 进行迭代运算 得到新的单纯形表 b列系数全部非负 检验数也全部非负 已求得最优解 b 对偶单纯形法 解的说明 Y 50 0 50 0 0 f 27500即f 27500 与原问题比较可以看到 y1 y3恰好是原问题第一 第三个约束条件的松弛变量 检验数恰好是原问题的解 这就是所谓的互补松弛性 原问题与对偶问题的最优解相同 对偶单纯形法 例5 求对偶问题的解 对偶单纯形法 例5的最终单纯形表如下 y1y2y3y4y5 YCj zj 001 81 60 2 zj cj 2 3 2 21 60 2 5 6 2 3 400 01 0 2 0 40 2101 4 0 2 0 4 b 对偶单纯形法 初始解可以是非可行解 当检验数都为负数时 就可以进行基的变换 这时不需要加入人工变量 可以简化计算 当变量多于约束条件时 用对偶单纯形法可以减少计算工作量 因此对变量较少 而约束条件很多的线性规划问题 可先转化为对偶问题 然后用对偶单纯形法求解 在灵敏度分析中 有时需要用对偶单纯形法 这样可以使问题简化 对偶单纯形法 作业 1 什么是资源的影子价格 同相应的市场价格之间有何区别 研究影子价格的意义何在 2 试述对偶单纯形法的计算步骤 它的优点及应用上的局限性 3 写出线性规划问题的对偶问题 对偶单纯形法 作业 用对偶单纯形法求解以下问题 灵敏度分析 由于市场条件 工艺条件以及企业规模的变化 价值系数 资源向量 技术系数等都会发生变化 提出两个问题 一 当这些系数有一个或几个发生变化时 最优解会发生变化 二 这些系数在什么范围内变化时 线性规划问题的最优解不变 如果每有参数发生变化就重新构建模型计算 太麻烦 也没有必要 可以把发生变化的个别系数 经过一定计算后直接填入最终计算表中 进行分析 灵敏度分析 价值系数的灵敏度分析资源向量的灵敏度分析约束方程系数矩阵的灵敏度分析决策变量增减的灵敏度分析约束条件增减的灵敏度分析 价值系数的灵敏度分析 某工厂在计划期间内生产1 2 3三种产品 已知生产单位产品所需的设备台时及A B两种原材料的消耗 如下表所示 1 2 3每单位产品分别可以获利2元 3元 a元 求如何安排生产可以使工厂利润最大 价值系数的灵敏度分析 线性规划问题 问 当a 1 2 3 5时 最优解分别为多少 最优基分别为那些变量 价值系数的灵敏度分析 当a 1时 最终单纯形表如下 价值系数的灵敏度分析 当a 2时 最终单纯形表如下 价值系数的灵敏度分析 当a 3时 最终单纯形表如下 价值系数的灵敏度分析 当a 5时 最终单纯形表如下 x1x2x3x4x5x6 xCj zj 0 5001 50 250 zj cj 2 5351 50 250 235000 0100 5 0 12500 50100 1250000 20 51 b 16 价值系数的灵敏度分析 当a 1 2 3时 zj cj 0 最终单纯形表基本没有改变 最优解没有改变 仅有x3的检验数有所不同 当a 5时 zj cj 0 最优基改变 最终单纯形表也发生改变 当最优基发生变化时 事实上我们不必重新进行全部计算 只需要在原来最终单纯形表的基础上继续迭代就可以得到最优解 价值系数的灵敏度分析 当a由3变为5时 价值系数的灵敏度分析 从上图中看到 检验数仍存在负数 继续迭代 x1x2x3x4x5x6 xCj zj 0 5001 50 250 zj cj 2 5351 50 250 235000 0 50100 1250000 20 510100 5 0 1250 b 16 价值系数的灵敏度分析 非基变量价值系数变化价值系数不在基变量中 zj保持不变 所以检验数zj cj变化 cj 为正数 要保持最优解不变 只要 cj zj cj 基变量价值系数变化基变量价值系数发生变化时 只需将新的价值系数代入最终单纯形表中 检查检验数 如果检验数仍保持为正 则最优基不变 但最优解的值会发生变化 如果检验数出现负数 则以原最终单纯形表为基础 继续进行迭代运算 资源向量的灵敏度分析 单纯形法的实质是找到一个能得到最优解的基xB 在约束条件中用其系数矩阵左乘一个B 1 令非基变量为0 得到最优解向量xB B 1b 事实上迭代过程也是用矩阵初等变换求B的逆矩阵B 1的过程 最终单纯形表中的b列其实就是B 1b 当第k个资源向量bk变为bk bk时 也就是原来单纯形表中的b向量变成了b 向量 资源向量的灵敏度分析 令 b 0 0 bk 0 T 则有b b b 这样最终单纯形表中基变量xB的解就变成了xB B 1 b b B 1b B 1 b 要使xB仍然为最优解 只要B 1b B 1 b 0即可 如果bk的变化使得B 1b B 1 b 0 这时最优解的基就要发生变化 这种情况下用对偶单纯形法继续求出新的最优解 资源向量的灵敏度分析 例 课本P6例1 1中 如果钢材的供应数量发生变化 请问1 钢材供应量在什么范围内变化时 最优基不会发生改变 2 当钢材的供应量增加到2200吨时 应当如何安排生产计划 资源向量的灵敏度分析 如果例1 1中的钢材供应数量变为1600 b1 最终解将变为 xB B 1b B 1 b b 资源向量的灵敏度分析 要保证最优基不改变 要求b 中所有向量大于等于0 即 从 1 式中可得 b1 400 从 2 式中可得 b1 600 从 3 式中可得 b1 400 得到 400 b1 400 也就是说 钢材供应量在1200到2000之间时 最优基不发生变化 资源向量的灵敏度分析 资源向量在一定范围内变化时 最优基虽然不会发生变化 但最优解则会发生变化 最优基不变时 可以直接将发生变化的资源向量代入B 1b 中 得到新的最优解的值 例如 当钢材供应量变为2000时 新的最优解的求解如下 资源向量的灵敏度分析 资源向量的灵敏度分析 当钢材的供应量增加到2200吨时 资源向量出现负数 不再是可行解 需要继续迭代 用对偶单纯形法 资源向量的灵敏度分析 最终单纯形表变为 资源向量的灵敏度分析 以主元素为中心进行迭代运算 趣味数学 一个富有的律师拥有11辆古董汽车 每辆值5000美元 律师死时留下了一个奇怪的遗嘱 他说他的11辆古董汽车分给他的三个儿子 把其中的一半分给长子 1 4分给次子 1 6分给小儿子 同时规定不能把车卖掉 律师去世后 儿子为了这个遗嘱争论不休 这时一个数学家开了一辆汽车来悼念老朋友 三个儿子把他们的难题告诉了数学家 数学家沉思片刻后说 我有办法了 请问 他该怎么分配这些汽车 约束方程系数矩阵的灵敏度分析 从前边的分析中 我们知道 单纯形法的实质是找到一个能得到最优解的基xB 在约束条件中用其系数矩阵左乘一个B 1 同时令非基变量为0 得到最优解向量xB B 1b 从而我们可以得到如下结论 最终单纯形表中xi的系数列向量pi 事实上就是其初始系数列向量pi左乘以B 1 既pi B 1pi 根据以上分析 我们可以得到约束方程技术系数变化时灵敏度分析的方法 约束方程系数矩阵的灵敏度分析 例如 在例1 1中 列向量x4的系数列向量 用p4表示 在最终单纯形表中为 用p4 表示 约束方程系数矩阵的灵敏度分析 根据以上分析我们可以得到系数矩阵灵敏度分析的思路 当基变量系数列向量改变时 用初始系数列向量左乘以B 1后代入原最终单纯形表 在新的单纯形表中继续进行运算 得到最优解 当新加入决策变量时 意味着约束方程组中增加了列向量 将这个列向量左乘以B 1后添加到原最终单纯形表中 继续运算得到最优解 约束方程系数矩阵的灵敏度分析 在例1 1 为了增加安全性 当每辆大轿车使用钢材由2吨变为3吨时 求最优解有什么变化 工厂具备了生产旅行车的技术 每辆旅行车用钢材1 5吨 工时1 25小时 座椅0 25套 利润为每辆3千元 问该不该投产 如果投产有利可图 应该如何安排新的生产计划 约束方程系数矩阵的灵敏度分析 当大轿车使用钢材变为3吨时 x1在最终单纯形表中的系数列向量变为 约束方程系数矩阵的灵敏度分析 最终单纯形表变为 约束方程系数矩阵的灵敏度分析 由于x1对应的列向量尚未化为单位向量 先进行迭代运算 1800 约束方程系数矩阵的灵敏度分析 检验数仍然有负数 继续迭代 约束方程系数矩阵的灵敏度分析 第二问 新增加一种产品 模型中增加了一个新列 设新产品产量为x6 增加的系数列向量在最终单纯形表中变为 约束方程系数矩阵的灵敏度分析 最终单纯形表变为 约束方程系数矩阵的灵敏度分析 检验数中存在负数 继续迭代 约束方程系数矩阵的灵敏度分析 仍不是最优解 继续运算 x1x2x3x4x5x6 xCj zj 012000 zj cj 430003 0210 2102 501 501 0 5 0 2501 50 b 442003 3200 约束方程系数矩阵的灵敏度分析 求得最优解为 x1 200 x2 0 x3 0 x4 500 x5 0 x6 800 Z 3200 可见 生产旅行车是有利可图的 新的生产方案为 生产大轿车200辆 生产旅行车800辆 剩余工时500小时 利润为3200千元 灵敏度分析小结 价值系数发生变化时 1 如果是非基变量的系数发生变化 则只要该变量对应的检验数zj cj在cj变化后仍然大于等于0 则最优解不发生任何变化 2 如果是基变量的价值系数发生变化 则需要重新计算所有检验数 如果所有检验数仍然保持大于等于0 则最优基不变 但最优解一般会发生变化 如果有检验数变为负数 则在原最终单纯形表中继续迭代 求出最优解 灵敏度分析小结 当资源向量发生改变时 用公式xB B 1b B 1 b xB B 1 b 其中 b 0 0 bk 0 T 计算新的b列的值 如果新的b列的值仍然全部大于等于0 则最优基不变 但最优解的值一般会发生变化 如果计算出来的新的b列的值出现负数 则说明该解是不可行解 用对偶单纯形法继续进行迭代运算 求出新的最优解 灵敏度分析小结 当基变量技术系数发生变化时 求出用公式pi B 1pi求出发生变化的系数所在列的数值 代替最终单纯形表中原来的列 然后用高斯消元法将该列化为单位向量 计算新的检验数 1 如果检验数不为负数 则最优基不变 2 如果新的检验数变为负数 则最优基将发生变化 用单纯形法继续迭代 求出新的最优解 趣味数学 你作为幸运观众参加了一个节目 节目中你面对三个门 其中一个门后一辆汽车 另外两个门后各有一只羊 主持人请你选择一扇门 门后的物品将做为你的奖品 当你选择后 主持人先不打开门 而是打开一扇门后有羊的门 然后问你改变不改变你的选择 请问 你该不该改变你的选择 作业 某公司制作三种产品A B C 需要劳动力和原材料两种资源 要求制订生产计划使总利润最大化 三种产品所需的资源和产生的利润如下表所示 作业 1 请建立模型 解决最优生产计划问题 2 求出使得最优解不变的产品A的单位利润变动范围 问A产品的利润变为2时最优解变不变 3 假定原材料的市场价格是10元每单位 可以购买15个单位 问以10元的价格采购15单位原材料是否合算 4 请问原材料的供应在什么范围内变化时 不必改变生产计划 作业 5 厂家研制出了一种新产品D 生产一单位D需要劳动力4单位 原材料3单位 而每单位的新产品D的利润为3元 请问 生产计划是否需要修改 为什么 该如何修改 第三章运输问题 主要内容 运输问题的背景运输问题的模型运输问题的表上作业法运输问题的应用 运输问题的背景 在经济建设中 经常碰到大宗物资调运问题 如煤炭 钢铁 粮食等等 主产区和主销区往往不同 需要大规模的调运 将物资从产地供应到销地 大型企业有多个生产基地 销售遍及全国乃至全世界 如何分配供应计划使经济效益最好 运输问题模型 运输问题解决把某种产品从若干个产地调运到若干个销地 在每个产地的供应量与每个销地的需求量已知 且各地运输单价已知的前提下 如何确定一个使总的运输费用最小的方案 运输问题模型 例1 某公司从两个产地A1 A2 将货物运往三个销地B1 B2 B3 各产地的产量 各销地的销量和各产地运往各销地的每件货物的运费如下表 问题 应如何调运 才能使得总运输费用最小 运输问题模型 这是一个产销平衡的运输问题把A1 A2的产量全部分配给B1 B2 B3 单位运价表 运输问题模型 设决策变量xij 产地Ai调运到Bj的运输量 i 1 2 j 1 2 3 产销平衡表 运输问题模型 线性规划模型 运输问题模型 一般线性规划模型Ai表示某种物资的第i个产地Bj表示某种物资的第j个销地si表示产地Ai的产量dj表示销地Bj的销量cij表示把物资从产地Ai运到销地Bj的单位运价决策变量xij表示产地Ai调运到销地Bj的运输量 运输问题模型 xj 0 i 1 2 m j 1 2 n 运输问题模型 其他的运输问题模型产销平衡的运输问题 当时求目标函数最大的运输问题考虑利润最大 营业额最大具有能力限制的运输问题运输线路的能力限制产销不平衡的运输问题产大于销 假设销地销大于产 假设产地 运输问题模型 从模型中看 运输问题属于线性规划问题的一种 其特殊之处在于 约束条件系数矩阵全部为0 1元素 而且结构比较松散 系数矩阵中对应xij的系数向量 其分量中除第i个和第m j个为1以外 其余的都为0 以例1的模型为例 考察其约束条件系数矩阵 运输问题模型 表上作业法 表上作业法 表上作业法解决运输问题的单纯形法针对运输问题变量多 结构独特的特点 简化了运算假设问题为产销平衡的运输问题求解步骤1 找出初始的基可行解运输问题有m n 1个基变量在 m n 产销平衡表上给出m n 1个数字格其相应的调运量就是基变量 格子中填写的值为基变量的值 表上作业法 2 求各非基变量的检验数在表上计算除了m n 1个数字格以外的空格的检验数判别是否达到最优解如已是最优解 则停止计算 否则转下步3 确定进基变量和出基变量找出新的基可行解在表上用闭回路法调整4 重复第2 3步骤 直至得到最优解 表上作业法 产销平衡表 B1B2BjBn产量限制 表上作业法 确定初始基可行解西北角法最小元素法西北角法从左上角的变量x11开始分配运输量 并使x11的取值尽可能大依次类推 直至给出全部方案为止例2 喜庆食品公司有三个生产面包的分厂A1 A2 A3 有四个销售公司B1 B2 B3 B4 其各分厂每日的产量 各销售公司每日的销量以及各分厂到各 表上作业法 销售公司的单位运价如下表 产量与销量的单位为吨 运价的单位为百元 吨 问该公司应如何调运产品在满足各销点需求量的前提下 使总运费最少 表上作业法 可行方案为 x11 3 x12 4 x22 2 x23 2 x33 3 x34 6 minf 135 3 0 4 4 0 2 2 0 2 2 3 0 3 0 6 6 0 0 表上作业法 最小元素法西北角法是对西北角的变量分配运输量最小元素法是就近供应 对单位运价最小的变量分配运输量用最小元素法求的初始基可行解比西北角法的总运费要小通常迭代的次数可能会少 表上作业法 可行方案为 x13 4 x14 3 x21 3 x23 1 x32 6 x34 3 minf 86 3 0 1 1 4 0 4 0 6 3 0 3 3 0 3 3 0 0 表上作业法 注意当取定xij的值之后 会出现Ai的产量与Bj的销量都为零的情况 只能划去Ai行或Bj列 不能同时划去用最小元素法时 可能会出现只剩一行或一列的所有格均未填数或未划掉的情况 此时在这一行或这一列中除去已填上的数外均填上零 不能将空格划掉这样可保证填过数或行的格为m n 1个 即基变量的个数为m n 1个 表上作业法 最优解的判定检验已得到的运输方案是否为最优方案闭回路法位势法闭回路法闭回路的构成在已给出的调运方案的运输表上 从代表非基变量的一个空格出发沿水平或垂直方向前进 只有碰到代表基变量的有数字的格才能向左或右转直到回到出发的空格 表上作业法 1 x11为非基变量的闭回路 表上作业法 检验数的计算 从 A1 B1 出发 增加一单位调运量 从A1运到B1 为保持产销平衡 依次做调整 在 A1 B3 处减少1吨 A2 B3 处增加1吨 A2 B1 处减少1吨 调整方案使运费增加 1 3 1 3 1 2 1 1 1 可见这样调整将每单位增加运费1 将1填入 A1 B1 所有非基变量的闭回路及检验数 表上作业法 空格 闭回路 检验数 x11 x11 x13 x23 x21 x11 x12 x14 x34 x32 x12 x12 x22 x24 x31 x33 x22 x23 x13 x14 x34 x32 x22 x24 x23 x33 x14 x24 x31 x34 x14 x13 x23 x21 x31 x33 x34 x14 x13 x33 1 2 1 1 10 12 表上作业法 闭回路法在以空格为始点和终点 其他顶点均为数字点的闭回路上将该空格的运输量调整为1 则其他顶点在保持供销平衡的基础上 运输量增加或减少1计算出该回路的总费用的变化值该变化值作为该非基变量的检验数若所有检验数都大于零 则原基可行解为最优解否则进一步迭代找出最优解用闭回路法求检验数要对每一个空格找一条闭回路当产销点多时 较繁杂 表上作业法 位势法将运输表上的每一行赋予值ui 每一列赋予值vjxij为基变量 则满足cij ui vj 0令u1 0 可先计算出ui和vj的值xij为非基变量 则利用ui和vj的值 计算出其检验数 ij cij ui vj若所有检验数 ij均大于零 则原基可行解为最优解否则进一步迭代找出最优解 表上作业法 例1中检验数的计算 令u1 0 将基变量的检验数列出 由基变量x14 有c14 u1 v4 0由基变量x13 有c13 u1 v3 0由基变量x21 有c21 u2 v1 0由基变量x23 有c23 u2 v3 0由基变量x32 有c32 u3 v2 0由基变量x34 有c34 u3 v4 0 表上作业法 即 8 u1 v4 0 5 u1 v3 01 u2 v1 0 4 u2 v3 03 u3 v2 0 10 u3 v4 0又知u1 0 所以得到 u1 0 u2 1 u3 5 v1 2 v2 9 v3 3 v4 10 因非基变量的检验数 ij cij ui vj 已知所有ui vj的值 可以在表格中计算所有非基变量的检验数 表上作业法 表上作业法 改进运输方案的方法 闭回路调整法选最小的负检验数 以它对应的非基变量为进基变量找出以该非基变量空格xij为出发点的闭回路尽量增加xij的运输量将该回路中的偶数顶点调运量的最小值取为xij的运输量将所有回路中的偶数顶点的调运量减去该值 而奇数顶点加上该值 得到新的调运方案 表上作业法 表上作业法 销地 产地 A14 1 3 1 7 A231 1 1 4 销量3656 B1B2B3B4产量 A3639 表上作业法 调整后的运输方案如下 表上作业法 用位势法再计算出检验数如下表 所有检验数都大于零 最小费用为85元 表上作业法 如何找多个最优方案识别是否有最优方案的方法与单纯形法一样只需检查最优方案中是否存在非基变量的检验数为零将检验数为零的非基变量进入基 对运输方案进行调整 就可得到另一个最优方案见下例 表上作业法 由前面的表中可知 x11的检验数 11 0令x11进入基 调整的运输方案为另一个最优方案 表上作业法 此时的最小运费仍为85 销地 产地 A1257 A2134 B1B2B3B4产量 A3639 销量3656 产销不平衡的运输问题 对于产大于销的运输问题 可以用增加一个虚拟销地的方法转化为产销平衡的运输问题 任何一个产地运往虚拟销地的运费均设为0 对于销大于产的运输问题 可以用增加一个虚拟产地的方法转化为产销平衡的运输问题 虚拟产地运往任何一个销地的运费均设为0 产销不平衡的运输问题 例2 某产品的供求表如下 请给出最佳调运方案 产销不平衡的运输问题 首先转化为产销平衡的运输问题 产销不平衡的运输问题 用最小元素法求出初始可行解 产销不平衡的运输问题 用位势法求出非基变量的检验数得 产销不平衡的运输问题 检验数存在负数 用闭回路法调整 产销不平衡的运输问题 调整后的运输方案为 产销不平衡的运输问题 运输费用为 80最优方案为 x13 4 x15 3 x21 3 x23 1 x24 3 x32 6 x34 3 产销不平衡的运输问题 思考题 产销不平衡的运输问题转化为产销平衡的运输问题后 虚拟产地运出的产品或运往虚拟销地的产品的单位运输费用均设为0 为什么 如果设为M行不行 设为任意数值行不行 为什么 运输问题作业 1 求解运输问题 B1B2B3产量 吨 销地 运费单价 产地 A1201624300 A210108500 销量 吨 200400300 900 900 A3801810100 运输问题作业 1 求解运输问题 B1B2B3产量 销地 运费单价 产地 A110163215 A21422407 销量12820 A322243416 第四章整数规划 主要内容 整数规划的特点整数规划的图解法整数规划的计算机解法整数规划的分枝定界法整数规划的应用 整数规划的特点 问题的提出在一般的线性规划中 最优解往往是分数或小数在许多实际问题中 要求全部或部分变量的取值必须是整数安排上班的人数裁剪钢材的根数生产机器的台数分类纯整数规划 所有变量为非负整数0 1规划 所有变量取值为0 1混合整数规划 部分变量为非负整数 整数规划的特点 求解方法四舍五入法或凑整法变量取值很大时 此方法得到的解与最优解差别不大但当问题规模较大时 计算工作量很大如 最优解为 4 6 5 5 10个变量要比较次 最优解不一定在这些组合中 整数规划的特点 比较 4 3 4 2 3 3 不是可行解 3 2 是可行解 不是最优解z 13最优解 4 1 z 14 1 2 3 x1 1 2 3 0 2x1 3x2 14 x2 4 x1 0 5x2 4 5 4 5 6 7 5 6 7 8 9 3 25 2 5 整数规划的特点 常用方法二变量的图解法分枝定界方法割平面法分配问题的匈牙利方法0 1型整数规划的隐枚举法 整数规划的特点 例1 有一份说明书 要分别翻译成英 日 德 俄四种文字 交甲 乙 丙 丁四个人去完成 因各个的专长不同 所需时间如表所示 问应如何分配 使这四个人分别完成这四项任务总的时间最小 人 工作 英文 日文 德文 俄文 甲乙丙丁 21097 154148 13141611 415139 整数规划的特点 引入0 1逻辑变量 整数规划的图解法 基本思想在可行域中寻找使目标值达到最大的整数解不使用四舍五入或截尾取整法例2 某公司拟用集装箱托运甲 乙两种货物 每件货物的体积 重量 利润及托运限制如下表 体积 立方英尺 利润 百元 甲 乙 托运限制 195 273 1365 立方英尺 4 40 140 百千克 2 3 货物 重量 百千克 整数规划的图解法 甲种货物至多托运4件 问两种货物各托运多少件可使获利最大 这是一个整数规划问题模型为maxz 2x1 3x2195x1 273x2 13654x1 40 x2 140 x1 4x1 x2 0 且为整数 整数规划的图解法 用图解法解该整数规划问题 2x1 3x2 14 1 2 3 x1 1 2 3 x2 4 4 2x1 3x2 6 2x1 3x2 14 66 该问题的线性规划的最优解为x1 2 44 x2 3 26 目标函数的最优值为14 66该解不是整数规划的可行解平移目标函数等直线 相交于整数规划的可行点x1 2 x2 4 目标函数的最优值为14 整数规划的图解法 用四舍五入或截尾法得到的线性规划的整数解不是整数规划的最优解或可行解如 x1 2 x2 3 目标函数值为13 不是最优解x1 3 x2 3 或x1 2 x2 4 x1 3 x2 4 都不是整数规划的可行解性质整数规划的最大目标值不会超过线性规划的最大目标值即整数规划的最小目标值不会小于线性规划的最小目标值 分枝定界法 意义和作用求解整数线性规划的有效方法既能解决纯整数规划 又能解决混合整数规划大多数软件都是基于该方法实施思路先求出相应线性规划的最优解定界 若该解不符合整数条件 求出整数规划的上下界分枝 把线性规划的可行域分成子区域 再求解这些子区域上的线性规划问题不断缩小整数规划上下界的距离 最后求出最优解 分枝定界法 分枝定界过程不断缩小最优目标函数值的上界和下界的距离通过分枝使得上界越来越小 而下界越来越大最优解的存在性当时 整数规划的最优解已求出即 最优解为其目标值取此下界的对应的线性规划的整数可行解 分枝定界法 例3 用分枝定界方法求解例2 的整数规划 maxz 2x1 3x2195x1 273x2 13654x1 40 x2 140 x1 4x1 x2 0 且为整数 分枝定界法 先求出相应的线性规划1的解线性规划1 maxz 2x1 3x2195x1 273x2 13654x1 40 x2 140 x1 4x1 x2 0 分枝定界法 最优解为x1 2 44 x2 3 26目标函数的最优值为z1 14 66x1 2 44 x2 3 26不是整数规划的最优解确定整数规划最优目标值的初始上界和下界由性质1 知 用观察法求出该整数规划的一个可行解 将其目标值作为用截尾法对线性规划的最优解进行处理得到x1 2 x2 3是整数规划的可行解令其目标值为 即 分枝定界法 分枝 将线性规划1分为两枝任取x1 2 44 x2 3 26中的一个或选取最远离整数的那一个 如 x1 2 44如x1取整数 则可在x1 2或x1 3中取值将线性规划1分成两枝 线性规划2和线性规划3 maxz 2x1 3x2195x1 273x2 13654x1 40 x2 140 x1 4x1 2x1 x2 0 maxz 2x1 3x2195x1 273x2 13654x1 40 x2 140 x1 4x1 3x1 x2 0 分枝定界法 求解线性规划2最优解为x1 2 x2 3 30目标函数的最优值为z2 13 90 maxz 2x1 3x2195x1 273x2 13654x1 40 x2 140 x1 4x1 2x1 x2 0 分枝定界法 求解线性规划3最优解为x1 3 x2 2 86目标函数的最优值为z3 14 58 maxz 2x1 3x2195x1 273x2 13654x1 40 x2 140 x1 4x1 3x1 x2 0 分枝定界法 修改整数规划最优目标值的上界和下界将 修改为定下界 用截尾法分别求出线性规划2和3的整数规划的可行解x1 2 x2 3 和x1 3 x2 2其目标值分别为13和12令在线性规划2和3中 选择上界最大的线性规划3进行分枝线性规划3的最优解为x1 3 x2 2 86将x2 2 86分成x2 2和x2 3两种情况将线性规划3分成两枝 线性规划4和线性规划5 分枝定界法 求解线性规划4最优解为x1 4 x2 2目标函数的最优值为z4 14 maxz 2x1 3x2195x1 273x2 13654x1 40 x2 140 x1 4x1 3x2 2x1 x2 0 分枝定界法 求解线性规划5无可行解 maxz 2x1 3x2195x1 273x2 13654x1 40 x2 140 x1 4x1 3x2 3x1 x2 0 分枝定界法 进一步修改整数规划最优目标值的上界和下界将的值修改为线性规划2的整数可行解为x1 2 x2 3 目标值为13线性规划4的整数可行解为 目标值为14令此时 且线性规划4的目标值为14 最优解为x1 4 x2 2 分枝定界法 线性规划1z1 14 66x1 2 44 x2 3 26 线性规划2z2 13 90 x1 2x2 3 30 x1 2 线性规划3z3 14 58x1 3x2 2 86 x1 3 线性规划4