南京应用运筹学线性规划.ppt

南京大学周晶教授jzhou 运筹学 问题 什么是运筹学 为什么要学习运筹学 要学习哪些内容 什么是运筹学 运筹帷幄 决策千里作为一门学科诞生于20世纪30年代末期 运筹学一词在英国称为operationalresearch 在美国称为operationsresearch 缩写为O R 在 大英百科全书 中 运筹学是一门应用于管理有组织系统的科学 运筹学为掌握这类系统的人提供决策目标和数量分析的工具 朴素的运筹思想都江堰水利工程战国时期 大约公元前250年 川西太守李冰父子主持修建 其目标是 利用岷江上游的水资源灌溉川西平原 追求的效益还有防洪与航运 其总体构思是系统思想的杰出运用 丁谓的皇宫修复工程北宋年间 丁谓负责修复火毁的开封皇宫 他的施工方案是 先将工程皇宫前的一条大街挖成一条大沟 将大沟与汴水相通 使用挖出的土就地制砖 令与汴水相连形成的河道承担繁重的运输任务 修复工程完成后 实施大沟排水 并将原废墟物回填 修复成原来的大街 丁谓将取材 生产 运输及废墟物的处理用 一沟三用 巧妙地解决了 田忌赛马齐王要与大臣田忌赛马 双方各出上 中 下马各一匹 对局三次 每次胜负1000金 田忌在好友 著名的军事谋略家孙膑的指导下 以以下安排 齐王上中下田忌下上中最终净胜一局 赢得1000金 运筹学的三大来源 军事运筹帷幄 决策千里第二次世界大战经济莱昂惕夫的投入产出模型管理著名经济学家西蒙有一句名言 管理就是决策 鲍德西 Bawdsey 雷达站的研究 1935年 1935年 英国科学家R Watson Wart发明了雷达 丘吉尔命令在英国东海岸的Bawdsey建立了一个秘密雷达站 当时 德国已拥有一支强大的空军 起飞17分钟即到达英国本土 在如此短的时间内 如何预警和拦截成为一大难题 1939年由曼彻斯特大学物理学家 英国战斗机司令部顾问 战后获得诺贝尔奖金的P M S Blackett为首 组织了一个小组 代号 Blackett马戏团 这个小组包括三名心理学家 两名数学家 两名应用数学家 一名天文物理学家 一名普通物理学家 一名海军军官 一名陆军军官 一名测量员 研究的问题是 设计将雷达信息传送到指挥系统和武器系统的最佳方式 雷达与武器的最佳配置 对探测 信息传递 作战指挥 战斗机与武器的协调 作了系统的研究 并获得成功 Blackett马戏团 在秘密报告中使用了 OperationalResearch 即 运筹学 大西洋反潜战 1942年 1942年 美国大西洋舰队反潜战官员W D Baker舰长请求成立反潜战运筹组 麻省理工学院的物理学家P W Morse被请来担任计划与监督 Morse出色的工作之一 是协助英国打破了德国对英吉利海峡的封锁 1941 1942年 德国潜艇严密封锁了英吉利海峡 企图切断英国的 生命线 海军几次反封锁 均不成功 应英国要求 美国派Morse率领一个小组去协助 Morse经过多方实地考察 最后提出了两条重要建议 将反潜攻击由反潜潜艇投掷水雷 改为飞机投掷深水炸弹 起爆深度由100米左右改为25米左右 即当潜艇刚下潜时攻击效果最佳 提高效率4 7倍 运送物资的船队及护航舰队编队 由小规模多批次 改为加大规模 减少批次 这样 损失率将减少 25 下降到10 管理与运筹学 泰勒的科学管理方法对工人提出科学的操作方法 时间 动作研究 对工人进行科学的选择 培训和提高 能力与工作相适应 制定科学的工艺流程 并以文件的形式加以固定和推广 工作定额与标准化 使管理和劳动相分离 计划与执行分离 在工资制度上实行差别计件制 差别计件付酬制 各种管理科学学派 科学管理原理 社会技术系统学派 行为科学学派 人际关系行为学派 管理过程学派 社会合作系统学派 决策理论学派 沟通信息学派 管理科学学派 经验案例学派 数理学派 系统管理学派 经理角色学派 群体行为学派战略管理创新管理知识管理 决策制定 主体 管理者 管理者的多重角色 认可并奖励业绩 不断完善个人管理技能 给予指导建议 不断提出反馈 员工发展 构建有效团队 倾听 调解冲突 设定富于挑战但可以达到的业绩标准 提供及时精确的信息 控制质量 倡导变化 影响高层领导的决策 争取资源实现团队目标 实现经营目标 满足客户的需要 明确阐述目标 全盘考虑 计划资源的合理利用 灵活性 控制 公司外部的重点 公司内部的重点 教练员创新者 促导者经纪人 监理者生产者 协调员指挥者 激励适应 政策目标 决策制定 决策环境 不确定性程度 确定 风险 不确定可重复性程度 程序 非程序人员参与程度 个体 群体主体价值判断 最优 满意 合理 决策制定 决策过程 识别问题 方案执行 观察 方案选择 方案评价 备择方案 理解问题 设定目标 解决问题周期 反馈 典型的定量决策问题 装箱问题 已知 两种货物装葙每种货物装葙利润体积限制重量限制问题 两种货物各多少箱 可使获得利润最大 箱数不能为分数 OR航空公司的问题 该公司要在郊区商业中心内设一个订票服务处 旅客订票时可以用电话与服务处联系 OR公司想知道 为了满足订票业务的需要 应该安装多少条电话线路为宜 显然 电话机和雇员的费用随电话线路的增设而变化 该公司希望对若干条不同线路方案的服务水平加以对比 尤其是公司要设法确定所有线路被占用的时间百分比 以及占先的平均时间长度 经济的定货量问题 萨拇 塔龙是某闹市区的一家工装裤零售店的主人 他对于尺码短缺的裤子应该进多少货常常感到为难 他决定采用科学的方法来补充库存 以避免因存货短缺而脱销 先假定他出售某种特殊尺码裤子的销售量每周为M件 为简便起见 还假定这个销售是固定的 那么如果库存量为kM件 则库存恰好在k周内售完 又假设M在整个时期内是不变的 因而是补充定货可以定期进行 要决策的问题是确定最经济的定货量 A2 B7 C20 D12 1 2 3 4 0 2 2 9 2 22 9 21 0 2 3 10 10 22 2 22 网络计划 白色表示作业长度tij 红色表示最早TES和TEF 绿色表示最迟TLS和TLF 秘书问题 瓦特 威洛比是一家从事经济分析和预测的咨询公司 这家公司的总经理凯 塞拉女士想雇佣一位新的事务秘书 正大算请职业介绍所推荐适当的人选同他会面 根据过去的经验 她自信能凭面谈即可断定求职者在受雇后的表现是极好的 好的 还是一般的 她给三种人以相应的分数 极好的为3分 好的为2分 一般为1分 一往的经验还使她相信 会见极好的候选人的概率为0 2 会见好的候选人的概率为0 5 而会见一般的候选人的概率为0 3 定量分析的过程 定性分析定量分析的前奏应当是一个彻底的定性分析表达问题列出表达问题的基本要素 决策变量 不可控量 限制条件等 建立模型列出表达这些要素之间关系的数学方程式求解模型与分析运用算法求解所构建的模型得到最佳方案或满意方案对输入数据和模型结构作灵敏度分析执行决定或修改模型在实际应用过程中不断完善模型 定量分析的工具 模型 模型 把需要解决的决策问题 通过分析其外部影响因素和内部的条件变量 用一个逻辑的或数学的表达式 从整体上说明它们之间的结构关系 代表一种现实情况 经过简化只保留相关的部分 用模型的特性代表现实情况中的特性P N S C 利润 销售量 价格 单位成本 建立模型的重要性 建立模型是运筹学方法的精髓建立模型有助于我们把决策问题所遇到的复杂性和可能的不确定性 转变为适于综合分析的逻辑结构 模型是一种媒介 借以对现实世界作出正确的认识 模型是现实的近似表达 要能抓住决策问题的关键 在真实性和可用性之间取得适当的平衡 典型的定量分析模型 定量分析的特点 定量分析 管理问题的理性描述和最优解分析方法 数学的 概率的和统计的方法定量优势 可靠数据为依据保证结果客观定量局限 实际问题无法完全地理性描述方法改进 数据分析与经验判断有机结合 运筹学的定义 定义1 为决策机构在对其控制下业务活动进行决策时 提供以定量化为基础的科学方法 定义2 运筹学是一门应用科学 它广泛应用现有的科学技术知识和数学方法 解决实际中提出的专门问题 为决策者选择最优决策提供定量依据 定义3 运筹学是应用系统的 科学的 数学分析的方法 通过建模 检验和求解数学模型而获得最优决策的科学 运筹学的研究对象 机器 设备 网络 乃至系统的运用问题 即如何提高运作效率 拥挤现象 交通路口的车辆排队 服务热线 飞机着陆 船舶进港 网络 竞争现象 人与自然的对抗 人与人的对抗 运筹学的重要分支 运用分析理论数学规划 又包含线性规划 非线性规划 整数规划 目标规划 动态规划等 图与网络流随机服务系统理论排队论库存论竞争决策理论决策论 人与自然的较量对策论 博弈论 人与人的较量 运筹学的主要研究分支 线性规划 模型简单 是运筹学中应用最为广泛的一个分支 非线性规划 在各类工程的优化设计中应用广泛 动态规划 研究多阶段决策过程最优化的运筹学分支 图与网络流 利用图来表示研究对象及其联系 并用图论方法来研究网络结构和流量的优化分析 决策论 研究决策过程中关于方案目标选取和度量 效用值计算 选取最优方案和策略等的有关科学理论 对策论 博弈论 用于研究具有对抗局势的模型 存贮论 研究最优存贮策略的理论和方法 排队论 对排队系统的研究理论和方法 运筹学主要分支简介 数学规划MathematicalProgramming 一般数学描述目标函数或约束函数都是线性的 则是线性规划 LinearProgramming 若其中至少有一个是非线性的 为非线性规划 NonlinearProgramming 若其中至少有一个变量要求为整数 则为整数规划 IntegerProgramming 数学规划 动态规划 DynamicProgramming 解决多阶段决策过程最优化问题的一种方法可用于解决最优路径问题 生产计划与库存 投资决策等实际问题 图与网络流Graphtheory 决策论 decision 著名经济学家西蒙有一句名言 管理就是决策 决策 一词本身是一个广义的概念 后续课程将介绍在不确定或随机环境下的决策分析方法 应用背景 产品开发决策问题 风险投资决策问题 开设连锁店问题等等 博弈论 GameTheory 排队论 QueuingTheory 银行 医院 机场跑道 港口码头 理发店 通信设备 交通路口等等的排队现象 排队论又叫做随机服务系统理论 它的研究目的是要回答如何改进服务机构 或组织被服务的对象 使得某种指标达到最优的问题 比如一个港口应该有多少个码头 一个工厂应该有多少维修人员等 库存论 InventoryTheory 存储物品的现象是为了解决供应 生产 与需求 消费 之间的不协调的一种措施 由此带来一些需要决策的问题 库存量 进货量 如报童问题 补货的时间等等决策量 现在也是供应链管理研究中的热点问题 真实系统 系统分析问题描述 模型建立与修改 模型求解与检验 结果分析与实施 数据准备 运筹学分析的步骤 本课程的主要内容 线性规划整数规划 线性 图论决策论博弈论 第一章线性规划LinearProgramming 运筹学中应用最广泛的方法之一运筹学的最基本的方法之一 网络规划 整数规划 目标规划和多目标规划都是以线性规划为基础的解决稀缺资源最优分配的有效方法 使付出的费用最小或获得的收益最大 发展历程 原始的数学规划模型早在1759年和1874年就分别由经济学家Quesnay和Walras提出 康托洛维奇于1939年出版了 生产组织与计划中的数学方法 一书 对一个工厂的生产计划任务建立了线性规划模型 并提出 解乘数法 冯 诺伊曼 VonNeuman 和摩根斯坦 Morgenstern 1944年发表的 对策论与经济行为 涉及与线性规划等价的对策问题及线性规划对偶理论GBDantzig1947年研究美国空军资源的优化配置时提出了线性规划的通用解法 单纯型法 50年代初成功地用电子计算机求解线性规划问题 从1964年诺贝尔奖设经济学奖后 到1992年28年间的32名获奖者中有13人 40 从事过与线性规划有关的研究工作 其中著名的还有Simon Samullson Leontief Arrow Miller等 发展历程 1 1线性规划的数学模型 例1 生产计划问题 问产品A B各生产多少 可获最大利润 maxZ 40 x1 50 x2 解 设产品A B产量分别为变量x1 x2 例2 求 最低成本的原料混合方案 解 设每单位添加剂中原料i的用量为xi i 1 2 3 4 minZ 2x1 5x2 6x3 8x4 要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件 线性规划问题的特征 线性规划模型的要素 决策变量 向量 x1 xn T决策人要考虑和控制的因素非负约束条件 线性等式或不等式目标函数 Z x1 xn 线性式 求Z极大或极小 56 一般式 Max min Z c1x1 c2x2 cnxn 线性规划问题解的定义 定义1 满足所有约束条件 1 2 的解X X1 Xn T称为LP问题的可行解 全部可行解的集合称为可行域 定义2 使目标函数达到最优值的可行解称为LP问题的最优解 LP 1 3线性规划的图解法 maxz x1 3x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 可行域 目标函数等值线 最优解 6 4 8 6 0 x1 x2 例1 maxZ 40 x1 50 x2 解 1 确定可行域x1 0 x1 0 纵 x2 0 x2 0 横 x1 2x2 30 x1 2x2 30 0 15 30 0 3x1 2x2 60 0 30 20 0 2x2 24 2 求最优解 解 x 15 7 5 Zmax 975 0 最优解 BC线段B点C点x 1 6 12 x 2 15 7 5 x x 1 1 x 2 0 1 求解 X 1 无界无有限最优解 无解无可行解 0 a 可行域封闭 唯一最优解 a 可行域封闭 多个最优解 d 可行域开放 多个最优解 e 可行域开放 目标函数无界 f 可行域为空集 c 可行域开放 唯一最优解 总结 1 可行域为凸多边形 2 若有最优解 一定可在可行域的顶点达到 1 4线性规划解的几何特性 凸集及其性质 定义1 凸集 D是n维欧氏空间的一个集合X 1 X 2 D 若任一个满足X X 1 1 X 2 0 1 有X D凸集中任意两点的连线仍然属于该集合 凸集图例 a 凸集 b 凸集 c 凸集 a 非凸集 b 非凸集 c 非凸集 X 1 X 2 X k 是n维欧氏空间中的k个点 若有一组数 1 2 k满足0 i 1 i 1 k 定义2 有点X 1X 1 kX k 则称点X为X 1 X 2 X k 的凸组合 凸组合 凸集D 点X D 若找不到两个不同的点X 1 X 2 D使得X X 1 1 X 2 0 1 则称X为D的顶点 定义3 顶点 1 5LP问题的基本解 m n r A m 至少有一个m阶子式不为0 定义4 基 基阵 由A中一个子矩阵B是可逆矩阵 则方阵B称为LP问题的一个基 X x1 xmxm 1 xn T XBXN T基变量非基变量XBXN 基 基变量 非基变量 目标函数 约束条件 行列式 0基 右边常数 AX b的求解 A BN X XBXN TXBXN BN b BXB NXN bBXB b NXNXB B 1b B 1NXN 例 基变量x1 x2 x3 非基变量x4 x5 x6 基本解为 x1 x2 x3 x4 x5 x6 5 3 1 0 0 0 是基本可行解 表示可行域的一个极点 目标函数值为 z 20 基变量x1 x2 x4 非基变量x3 x5 x6 基本解为 x1 x2 x3 x4 x5 x6 27 5 12 5 0 2 5 0 0 是基本可行解 表示可行域的一个极点 目标函数值为 z 18 基变量x1 x2 x5 非基变量x3 x4 x6 基本解为 x1 x2 x3 x4 x5 x6 6 3 0 0 3 0 是基本解 但不是可行解 不是一个极点 基变量x1 x2 x6 非基变量x3 x4 x5 基本解为 x1 x2 x3 x4 x5 x6 3 4 0 0 0 4 是基本可行解 表示可行域的一个极点 目标函数值为 z 18 基变量x2 x3 x4 非基变量x1 x5 x6 基本解为 x1 x2 x3 x4 x5 x6 0 21 2 27 2 30 0 0 是基本解 但不是可行解 基变量x1 x2 x3 非基变量x4 x5 x6 基本解为 x1 x2 x3 x4 x5 x6 0 3 6 0 15 0 是基本可行解 表示可行域的一个极点 目标函数值为 z 15 基变量x1 x2 x3 非基变量x4 x5 x6 基本解为 x1 x2 x3 x4 x5 x6 0 11 2 3 2 0 0 10 是基本解但不是可行解 LP 问题的基本可行解可行域的顶点 若 LP 问题有最优解 必定可以在基本可行解 顶点 达到 LP问题解的性质 若 LP 问题有可行解 则可行解集 可行域 是凸集 可能有界 也可能无界 有有限个顶点 基本解 基本可行解与顶点 maxz x1 3x2Ds t x1 x2 x3 6B x1 2x2 x4 8x4 0Cx3 0 x1 x2 x3 x4 0 x1 0EOx2 0A 几何概念 代数概念 约束直线 满足一个等式约束的解 约束半平面 满足一个不等式约束的解 约束半平面的交集 凸多边形 满足一组不等式约束的解 约束直线的交点 基本解 可行域的极点 基本可行解 目标函数等值线 一组平行线 目标函数值等于一个常数的解 定理2 LP有最优解 必定可以在可行域 凸多面集 的顶点得到 定理1 LP问题的可行域一定是凸集 凸多面集 基本可行解个数有限 当约束条件为m个 n个变量时 基本可行解个数不超过 n 5m 3C53 10 n 50m 20C5020 4 70 1013 1000000个 秒1 309 104小时 545天 1 6单纯形法SimplexMethod 一 单纯形方法的基本思路 从一个初始的基本可行解出发 经过判断 如果是最优解 则结束 否则经过基变换得到另一个改善的基本可行解 如此一直进行下去 直到找到最优解 目标函数 约束条件 基矩阵 右边常数 进基变量 离基变量 基变换 基变量 进基变量 离基变量 目标函数 约束条件 右边常数 目标函数 约束条件 新的基矩阵 右边常数 进基变量 离基变量 目标函数 约束条件 基矩阵 目标函数 约束条件 新的基矩阵 右边常数 二 线性规划的典式 AX b的求解 A BN X XBXN TXBXN BN b BXB NXN bBXB b NXNXB B 1b B 1NXN 例 解 1 确定初始可行解 B P3P4P5 I 令x1 x2 0 X 1 0 0 30 60 24 TZ 1 0 2 判定解是否最优 Z 0 40 x1 50 x2当x1从0 或x2从0 Z从0 X 1 不是最优解 3 由一个基可行解 另一个基可行解 50 40选x2从0 x1 0 x2 min 30 2 60 2 24 2 12x2进基变量 x5出基变量 B2 P3P4P2 1 2 代入 式 令x1 x5 0X 2 0 12 6 36 0 TZ 2 600 2 判断 40 0 X 2 不是 3 选x1从0 x5 0 x1 min 6 1 36 3 1 6x1进基 x3出基 B3 P1P4P2 令x3 x5 0X 3 6 12 0 18 0 TZ 3 840 2 15 0 X 3 不是 3 选x5从0 x3 0 x5 min 18 2 12 1 2 9x5进基 x4出基 B4 P1P5P2 令x3 x4 0X 4 15 15 2 0 0 9 TZ 4 975 0 0 0 x2 x1 三 单纯形表 c1c2 cmcm 1 cm k cnCBXBB 1bx1x2 xmxm 1 xm k xnc1x1b110 0a1m 1 a1m k a1nc2x2b201 0a2m 1 a2m k a2ncrxrbr00 0arm 1 arm k arncmxmbm00 1amm 1 amm k ann Z000 0 m 1 m k n 例1 4050000CBXBbx1x2x3x4x5 0 x33012100150 x46032010300 x5240 2 00112040500000 x36 1 010 160 x4363001 11250 x21201001 260040000 2540 x161010 10 x41800 31 2 950 x21201001 224 84000 40015 40 x11510 1 21 200 x5900 3 21 2150 x215 2013 4 1 40 本问题的最优解X 15 15 2 0 0 9 TZ 975 4050000CBXBbx1x2x3x4x5 97500 35 2 15 20 例2maxZ x1 2x2 12000CBXBbx1x2x3x4x50 x34101000 x430 1 0100 x58120010120000 x34101002x23010100 x52 1 00 21 接下表 6100 20 12000CBXBbx1x2x3x4x50 x32001 2 12x23010101x12100 2180000 10 x41001 21 1 22x2201 1 201 21x1410100 80000 1 X 1 2 3 Z 1 8 X 2 4 2 Z 2 8 无穷多解 1 110 30CBXBbx1x2x3x4x5x61x36011 1201x15120 2000 x68020131110 403 501x3140310511x1211600620 x48020131350 1000 14 3 1012000XBbx1x2x3x4x5 i0 x363 4 1003 20 x42410102 10 x53320013 20101200012x23 23 411 40020 x41 213 40 1 4102 130 x50 3 2 0 1 20101810 30012x23 2011 20 1 20 x41 2005 61 13 610 x1010 1 302 3 1800 8 30 2 3 退化解 X 0 3 2 0 1 2 0 T Zmax 18 例5 41000CBXBbx1x2x3x4x50 x32 111000 x44 1 40100 x581 2001 041000 0 x360 31104x141 40100 x540 2 0 11160170 400 x312001 1 23 24x112100 121x22010 1 21 2 500009 2 17 2 本问题无界 四 初始基本可行解的求法 一 大M法 判定无解条件 当进行到最优表时 仍有人工变量在基中 且 0 则说明原问题无可行解 例1 64000 M MCBXBbX1X2X3X4X5X6X70X310023100000X41204201000 MX614 1 000010 MX7220100 101 36MM 6M 400 M000X37203100 200X46402010 406X1141000010 MX7220 1 00 101 84 22M0M 400 M6 M0 0 x360010 3 2 30 x42000012 4 26x11410000104x2220100 101172000046 M4 M0 x52001 301 2 3 10 x41600 2 310 8 306x11410000104x224011 300 2 3 2 18000 4 300 M 10 3 M CBXBbx1x2x3x4x5x6x7 64000 M M 1 7线性规划的对偶问题 Duality 一 对偶问题 例 某厂生产甲 乙两种产品 消耗A B两种原材料 生产一件甲产品可获利2元 生产乙产品获利3元 问在以下条件下如何安排生产 建立线性规划模型 目标函数 MAXZ 2X1 3X2约束条件 X1 2X2 84X1 164X2 12X1 X2 0 从另一角度考虑 如果该厂决定不生产甲 乙两种产品 而将其资源出租或出售 这时工厂的决策者就要考虑给每种资源如何定价的问题 设用Y1 Y2 Y3分别表示出租单位设备台时的租金和出让原材料A B的附加值 作如下比较 用一个单位设备台时和四个单位的原材料可以生产甲产品一件 获利2元 那么出租和出让的收益不应低于自己生产时的收益 因此有Y1 4Y2 2 同样地乙产品也有 2Y1 4Y3 3 一 对偶问题 全部出让或出租的总收入为W 8Y1 16Y2 12Y3从决策者来看 当然希望W值越大越好 但从接受者来讲 支付越少越好 为提高竞争力 因此工厂只能在满足 所有产品的利润条件 使其总收入具有竞争力的 因此 W需要求解最小值 因此有线性规划模型 目标函数 minW 8Y1 16Y2 12Y3s tY1 4Y2 22Y1 4Y3 3Y1 Y2 Y3 0 一 对偶问题 二 对偶关系 P D 二 对偶关系 原问题 primalproblem P1 maxz CTXAX bX 0对偶问题 dualproblem D1 minw bTYATY CY 0 二 对偶关系 例子 minz 3x1 2x2 x3s t 2x1 x2 3x3 23x1 5x2 5x1 x2 x3 1x1 0 x2自由 x3 0 二 对偶关系 其对偶问题 maxw 2y1 5y2 y3s t 2y1 3y2 y3 3y1 5y2 y3 23y1 y3 1y1 0 y2 0 y3自由 例 写对偶规划 MinZ 4x1 2x2 3x3 x1 2x2 62x1 3x3 9x1 5x2 2x3 4x2 x3 0 MaxW 6y1 9y2 4y3 y1 2y2 y3 42y1 5y3 23y2 2y3 3y1 0 y2 0 y3自由 MinZ 4x1 2x2 3x3 x1 2x2 62x1 3x3 9x1 5x2 2x3 4x2 x3 0 例 MaxW 6y1 9y2 4y3 y1 2y2 y3 4 2y1 5y3 23y2 2y3 3y1 y2 0 y3自由 三 对偶性质 对称性 P 和 D 相互对偶弱对偶性 CTX bTY最优性 当CTX bTY时 P D 皆最优对偶原理 如果一个问题有最优解 其对偶问题也有最优且等最优值 如一个问题无界 其对偶问题无可行解兼容性 标准形 原问题的检验数给出对偶问题的一个基本解互补松弛性 标准形 例1 写出下面问题的对偶规划 产品A B产量x1 x2 Z为利润 例1 X 8 24 TZ 184 5600XBbx1x2x3x40 x34831100 x41203 4 01056000 x318 9 4 01 1 46x2303 4101 41801 200 3 25x18104 9 1 96x22401 1 31 3 18400 2 9 13 9 4812000MMyBy1y2y3y4y5y6My5533 1010My66140 10111M48 4M120 7MMM00My51 29 40 13 41 3 4120y23 21 410 1 401 4180 1 2M18 9 4M0M30 3 4M0 30 7 4M48y12 910 4 91 34 9 1 3120y213 9011 9 1 3 1 91 3 y 2 9 13 9 Z 184 18400824M 8M 24 观察结论 一对互为对偶的线性规划问题都有最优解 且目标函数值相等 最优表中有两个问题的最优解 四 对偶解的经济意义 经济解释 bi 第i种资源的数量yi 对偶解bi增加bi 其它资源数量不变时 目标函数的增量 Z biyi yi 反映bi的边际效益 边际成本 例1中y1 2 9 当机器台时数增加1个单位时 工厂可增加利润2 9个单位 2 影子价格在模型中 yi表示资源bi增加1单位时 企业目标增加的净利润 由 1 的经济解释可知 yi的大小与系统内资源对目标的贡献有关 是资源的一种估价 称为影子价格 3 应用 情况 某资源对偶解 0 该资源有利可图 可增加此种资源量 某资源对偶解为0 则不增加此种资源量 情况 直接用影子价格与市场价格相比较 进行决策 是否买入该资源 生产计划问题项目投资问题配料配套问题合理下料问题人力资源问题运输调运问题任务指派问题 1 8线性规划模型的应用 例1 生产计划问题某企业拟生产A B两种产品 需利用一种原材料并经过车 铣两台机床加工 加工的工时定额 每天可用工时和原材料以及两种产品可能获得的利润如下表所示 要求 1 拟定一个获得利润最大的生产计划 2 若单价0 8元再购入少量原材料投入生产是否合算 为什么 例2 生产计划问题某车间在每个生产期5天所需要的每种刀具的统计资料如下 每一把刀具成本为0 6元 用过的刀具送到机修车间研磨 每把需花费0 2元 刀具用过后送去磨 只一次 两天后可以磨好送回 供当天 第三天 使用 第五天后应全部换新 每期开始时没有任何刀具 问这个车间需要多少刀具才能应付需要 而成本又最低 试建立线性规划模型 确定变量 问题是要确定每期需要新刀具的总数 它等价于要确定每天所需的新刀具 同时考虑到送去研磨的刀具第三天可使用 为此 设决策变量Xi i 1 2 3 4 5 为第i天使用的新刀具 Yj j 1 2 3 为第j天送去研磨的刀具数 确定目标函数 新刀具成本 研磨成本 为最小 即 minZ 0 6 X1 X2 X3 X4 X5 0 2 Y1 Y2 Y3 确定约束条件 由于研磨的刀具第三天才能使用 因此 X1 120 X2 85第三天开始 每天使用新的和研磨送回的刀具 X3 Y1 160 X4 Y2 145 X5 Y3 300在头三天送去研磨的刀具应满足 Y1 X1 Y2 X2 120 Y1 Y3 X3 120 Y1 85 Y2 每天使用的新刀具和送研磨的刀具数为非负整数 X1 X2 X3 X4 X5 Y1 Y2 Y3 0 且均为整数 完整的模型为 minZ 0 6 X1 X2 X3 X4 X5 0 2 Y1 Y2 Y3 s t X1 120X2 85X3 Y1 160X4 Y2 145X5 Y3 300Y1 X1Y2 X2 120 Y1 Y3 X3 120 Y1 85 Y2 X1 X2 X3 X4 X5 Y1 Y2 Y3 0 且均为整数 求解结果X1 120X2 85X3 160X4 0X5 80Y1 0Y2 145Y3 220 例3 营销策略一贸易公司专门经营某商品的批发业务 公司有库容5000单位的仓库 某年一月一日 公司有库存1000单位 并有资金20000元 估计第一季度该商品的价格如下表所示 如买进的商品当月到货 但需到下月才能卖出 且规定 货到付款 公司希望本季末库存为2000单位 问应采取什么样的买卖策略可使3个月总的获利最大 一月二月三月进货价 元 2 853 052 90出货价 元 3 103 252 95 考虑到资金周转 应该是先卖出再买进 而且最好是月初卖出月底买进 决策变量 每月买进Xi i 1 2 3 每月卖出Yi i 1 2 3 分析库存情况 库存卖出买入月末库存一月1000Y1X11000 Y1 X1二月1000 Y1 X1Y2X21000 Y1 X1 Y2 X2三月1000 Y1 X1 Y2 X2Y3X31000 Y1 X1 Y2 X2 Y3 X3存货限制 Y1 1000Y2 1000 Y1 X1Y3 1000 Y1 X1 Y2 X2库容限制 1000 Y1 X1 50001000 Y1 X1 Y2 X2 50001000 Y1 X1 Y2 X2 Y3 X3 2000 分析资金流动情况 月初资金卖出买入一月200003 10Y12 85X1二月20000 3 10Y1 2 85X13 25Y23 05X2三月20000 3 10Y1 2 85X1 3 25Y2 3 05X22 95Y32 90X3资金限制 2 85X1 20000 3 10Y13 05X2 20000 3 10Y1 2 85X1 3 25Y22 90X3 20000 3 10Y1 2 85X1 3 25Y2 3 05X2 2 95Y3目标函数 MAXZ 3 10Y1 3 25Y2 2 95Y3 2 85X1 3 05X2 2 90X3 目标函数 MAXZ 3 10Y1 3 25Y2 2 95Y3 2 85X1 3 05X2 2 90X3资金限制 2 85X1 20000 3 10Y13 05X2 20000 3 10Y1 2 85X1 3 25Y22 90X3 20000 3 10Y1 2 85X1 3 25Y2 3 05X2 2 95Y3存货限制 Y1 1000Y2 1000 Y1 X1Y3 1000 Y1 X1 Y2 X2库容限制 1000 Y1 X1 50001000 Y1 X1 Y2 X2 50001000 Y1 X1 Y2 X2 Y3 X3 2000 例4连续投资问题某部门在五年内考虑给下列项目投资 项目A 从第一年到第四年每年年初需要投资 并于次年末回收本利115 项目B 从第三年初需投资 到第五年末能回收本利125 但规定最大投资额不超过4万元 项目C 第二年初需要投资 到第五年末能回收本利140 但规定最大投资额不超过3万元 项目D 五年内每年初可购买公债于当年末归还并加利息6 该部门现有资金10万元 问应如何确定给这些项目每年的投资额 使到第五年末拥有的资金的本利总额为最大 确定变量 以XiA XiB XiC XiD i 1 2 3 4 5 分别表示第i年年初给项目A B C D的投资额 具体列于下表 确定约束条件 投资额应等于手中拥有的资金 不应有剩余 第一年 X1A X1D 100000第二年 年初资金仅为D项目第一年的本息 X2A X2C X2D X1D 1 6 第三年 年初资金为A第一次回收本利 D第二次本息X3A X3B X3D X1A 1 15 X2D 1 6 第四年 X4A X4D X2A 1 15 X3D 1 6 第五年 X5D X3A 1 15 X4D 1 6 B C投资额限制 X3B 40000 X2C 30000确定目标函数 第五年末资金最大MAXZ 1 15X4A 1 40X2C 1 25X3B 1 06X5D 完整的模型为 MAXZ 1 15X4A 1 40X2C 1 25X3B 1 06X5Ds t X1A X1D 100000 1 06X1D X2A X2C X2D 0 1 15X1A 1 06X2D X3A X3B X3D 0 1 15X2A 1 06X3D X4A X4D 0 1 15X3A 1 06X4D X4D 0X2C 30000X3B 40000XiA XiB XiC XiD i 1 2 3 4 5 0 求解结果 单位 元 第一年 X1A 34783 X1D 65217第二年 X2A 39130 X2C 30000 X2D 0第三年 X3A 0 X3B 40000 X3D 0第四年 X4A 45000 X4D 0第五年 X5D 0第五年末总资金 Z 143750 例5投资问题某部门现有资金200万元 今后五年内考虑给以下的项目投资 项目A 从第一年到第五年每年年初都可投资 当年末能收回本利110 项目B 从第一年到第四年每年年初都可投资 次年末能收回本利125 但规定每年最大投资额不能超过30万元 项目C 需在第三年年初投资 第五年末能收回本利140 但规定最大投资额不能超过80万元 项目D 需在第二年年初投资 第五年末能收回本利155 但规定最大投资额不能超过100万元 据测定每万元每次投资的风险指数如下表 问 a 应如何确定这些项目的每年投资额 使得第五年年末拥有资金的本利金额为最大 b 应如何确定这些项目的每年投资额 使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小 解 1 确定决策变量 连续投资问题设xij i 1 5 j 1 2 3 4 表示第i年初投资于A j 1 B j 2 C j 3 D j 4 项目的金额 这样我们建立如下的决策变量 Ax11x21x31x41x51Bx12x22x32x42Cx33Dx24 2 约束条件 第一年 A当年末可收回投资 故第一年年初应把全部资金投出去 于是x11 x12 200 第二年 B次年末才可收回投资 故第二年年初的资金为1 1x11 于是x21 x22 x24 1 1x11 第三年 年初的资金为1 1x21 1 25x12 于是x31 x32 x33 1 1x21 1 25x12 第四年 年初的资金为1 1x31 1 25x22 于是x41 x42 1 1x31 1 25x22 第五年 年初的资金为1 1x41 1 25x32 于是x51 1 1x41 1 25x32 B C D的投资限制 xi2 30 I 1 2 3 4 x33 80 x24 100 a 应如何确定这些项目的每年投资额 使得第五年年末拥有资金的本利金额为最大 目标函数及模型 Maxz 1 1x51 1 25x42 1 4x33 1 55x24s t x11 x12 200 x21 x22 x24 1 1x11x31 x32 x33 1 1x21 1 25x12x41 x42 1 1x31 1 25x22x51 1 1x41 1 25x32xi2 30 I 1 2 3 4 x33 80 x24 100 xij 0 i 1 2 3 4 5 j 1 2 3 4 b 应如何确定这些项目的每年投资额 使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小 Minf x11 x21 x31 x41 x51 3 x12 x22 x32 x42 4x33 5 5x24s t x11 x12 200 x21 x22 x24 1 1x11 x31 x32 x33 1 1x21 1 25x12 x41 x42 1 1x31 1 25x22 x51 1 1x41 1 25x32 xi2 30 I 1 2 3 4 x33 80 x24 1001 1x51 1 25x42 1 4x33 1 55x24 330 xij 0 i 1 2 3 4 5 j 1 2 3 4 例6配料问题 某工厂要用三种原料1 2 3混合调配出三种不同规格的产品甲 乙 丙 数据如下表 问 该厂应如何安排生产 使利润收入为最大 解 设xij表示第i种 甲 乙 丙 产品中原料j的含量 这样我们建立数学模型时 要考虑 对于甲 x11 x12 x13 对于乙 x21 x22