全国2012年4月高等教育自学考试运筹学基础试题
全国2012年4月高等教育自学考试运筹学基础试题课程代码：02375 一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．借助于某些正规的计量方法而做出的决策，称为( )A．定量决策B．定性决策C．混合性决策 D．满意决策2．利用直观材料，依靠个人经验的主观判断和分析能力，对未来的发展进行预测属于( )A．经济预测B．科技预测C．定性预测D．定量预测3．在接受咨询的专家之间组成一个小组，面对面地进行讨论与磋商，最后对需要预测的课题得出比较一致的意见，这种预测方法是( )A．指数平滑预测法B．回归模型预测法C．专家小组法 D．特尔斐法4．风险条件下的决策是( )A．存在一个以上的自然状态，但是决策者具有提供将概率值分配到每个可能状态的信息B．决策者知道所面对的部分自然状态C．决策者面对的只有一种自然状态，即关于未来的状态是完全确定的D．决策者所面对的是，存在一个以上的自然状态，而决策者不了解其它状态，甚至不完全了解如何把概率（可能性）分配给自然状态5．根据库存管理理论，约占全部存货单元数的30%，但它们的年度需用价值却只占该企业全部存货年度需用价值的20%，这类存货单元称为( )A．A类存货单元B．B类存货单元C．C类存货单元 D．经济存货单元6．在库存管理中，为了预防可能出现的缺货现象而保持的额外库存量，称为( )A．再订货点B．安全库存量C．经济订货量 D．缺货量7．在线性规划的图解法中，全部可行解所分布的区域称之为( )A．阴影区 B．可行解区C．最优解区D．基础可行解区8．用单纯形法求解线性规划问题时，若约束条件是等于或小于某确定数值，则应当在每个不等式中引入一个( )A．基变量 B．非基变量C．松驰变量D．剩余变量9．对于供求不平衡的运输问题，若需求量大于供应量，为了转化成供求平衡的运输问题，我们往往虚设一个( )A．供应点 B．需求点C．仓库 D．运输渠道10．对计划项目进行核算、评价，然后选定最优计划方案的技术，称为( )A．网络计划技术B．计划评核术C．关键路线法 D．单纯形法11．在网络计划技术中，总时差等于0的活动，称之为( )A．关键线路B．关键结点（事项）C．关键工序D．关键时差12．网络图中，正常条件下完成一项活动可能性最大的时间，称为( )A．作业时间B．最乐观时间C．最保守时间 D．最可能时间13．在图论中，根据问题的需要，我们可以在图的点旁或边旁标上数，这个数有时称之为( )A．树 B．杈C．枝叉树 D．最小枝叉树14．在一定时期内不随企业产量的增减而变化的费用，称之为( )A．固定成本B．可变成本C．预付成本D．计划成本15．如果一个随机变量允许在某个给定范围内具有有限个数的数值，则它就是一个( )A．随机数 B．随机数分布C．离散的随机变量D．连续的随机变量二、填空题(本大题共10小题，每小题1分，共10分)请在每小题的空格中填上正确***。错填、不填均无分。 16．对于管理领域，运筹学也是对管理决策工作进行决策的______方法。17．凡利用事物内部因素发展的因果关系来预测事物发展趋势的叫因果法，常用的有经济计量法、______、投入产出分析法等。18．《管理决策新科学》是美国著名管理学家、1978年诺贝尔经济学奖获得者______的名著。19．经济订货量（EOQ）是使总的______达到最低的为某个台套或某个存货单元确定的最佳的订货批量。20．初始单纯形表是由线性规划模型标准形式的______转变而成的，由于填入的是以原点为基础的可行解的系数，故称之为初始单纯形表。21．结点时差等于______的结点，称之为关键结点。22．在图论中我们往往用一条带箭头的线来表示研究对象之间的关系，这样的线条称之为______。23．对于概率矩阵P，若Pn矩阵中每一个行向量都相等，则Pn称作P的______。24．用“计划性能法”得到的盈亏平衡图，总成本成______变化。25．蒙特卡洛方法是应用______进行模拟试验的方法。三、名词解释题(本大题共5小题，每小题3分，共15分)26．一元线性回归27．订货费用28．单纯形法29．网络计划中的虚活动30．马尔柯夫分析四、计算题Ⅰ(本大题共3小题，每小题5分，共15分)写出下列每小题的计算过程，否则只给结果分。 31．某公司的销售额数据如题31表。试计算3个月的加权滑动平均预测值（直接填在题31表中相应空栏）。题31表 某公司的销售额数据月份实际销售额（万元）3个月加权滑动平均预测值120&224&326&432&538&646&32．某公司计划向市场推出一项新产品。拟定的价格有A1、A2、A3三个方案，预计进入市场后可能的销售状况（自然状态）也有三种，收益值表如题32表。试以最小最大遗憾值决策标准作出产品价格的决策选择。题32表 某公司新产品的收益值表销售状态价格方案销路较好销路一般销路较差较高价格出售A1300000180000120000中等价格出售A2240000240000150000较低价格出售A318000018000018000033．某公司以单价10元每年购买某种产品8000件。每次订货费用为30元，单位库存维护费按库存物资价值的30%计算。试求该公司最佳订货批量和全年最佳订货次数。五、计算题Ⅱ(本大题共3小题，每小题5分，共15分)写出下列每小题的计算过程，否则只给结果分。 34．某厂商拟对移动***新产品生产作出决策，经调研，现有二种备选方案：A1方案是建较大规模的厂，总投资2000万元；A2方案是建较小规模的厂，总投资1600万元。未来市场对该产品的需求有三种可能的自然状态N1、N2、N3，相应概率与收入矩阵如题34表，该厂商希望五年中所获净利润最大化。试画出该问题的决策树，并以决策树法作出最优生产决策。题34表 某厂商市场概率与收入矩阵表（单位：万元）自然状态行动方案N1（高需求）PN1=0.5N2（中需求）PN2=0.3N3（低需求）PN3=0.2A1(建大厂)1000600-200A2(建小厂)55045025035．某住宅区***供水管道如题35图。图中：方框表示供水管道的进水阀门，圆圈代表住宅，连线表示可以铺设的管道线路，线上数据表示距离（单位：米）。试以最小枝杈树方法画出最优管道线路方案，并计算管道的总长度。
![题35图 某住宅区***供水管道线路图36．某公司现有位于不同城市的两个工厂A、B和3个仓库U、V、W。考虑公司的发展，公司决定选择在X城新建一个工厂，各工厂生产能力、仓库需求及工厂到仓库的单位运费如题36表。试建立供需平衡的运输表，并以西北角法求其最初的运输方案。题36表 各工厂生产能力、仓库需求及工厂到仓库的单位运费表现有工厂和备选工厂生产能力（台/月）到各仓库单位运费（元/台）UVWA2800102436B2000201614X2400302212各仓库需求量（台/月）220014002600六、计算题Ⅲ(本大题共2小题，每小题7分，共14分)写出下列每小题的计算过程，否则只给结果分。 37．某公司产品生产需要A、B两种原料的总量至少为350吨，其中A原料至少购进125吨。加工每吨原料A需要2小时，加工每吨原料B需要1小时，而公司的加工能力总共只有600小时；每吨原料A价格为2万元，每吨原料B价格为3万元，试求在满足生产需要前提下，在公司加工能力范围内，如何购买两种原料可使总成本最低？试建立该问题的线性规划数学模型并用图解法求出最优解。38．将37题线性规划问题转换为标准形式，以原点为基础求出基础可行解，并建立初始单纯形表。七、计算题 Ⅳ(本大题共2小题，每小题8分，共16分)写出下列每小题的计算过程，否则只给结果分。 39．某企业设备***工程有10项活动，其各项活动的明细表如题39表。试绘制网络图。题39表 某企业***工程活动明细表工序名称ABCDEFGHIJ紧前工序-- -- A、BBACE、FD、FG、HI工序时间（天）234153276540．在你为题39所绘制的网络图上标出各结点的时间参数；指明A、B、C、D四项活动的最早开始时间和最迟开始时间。<br />
关于自考更多信息：<br />
2017年自考： <br />
自考365网络课程<br />
英语（一）<br />
英语（二）<br />
高等数学（一）<br />
大学语文<br />
线性代数（经管类）<br />
中国近现代史纲要<br />
思想道德修养与法律基础<br />
概率论与数理统计(经管类)<br />
国际贸易<br />
工商企业管理<br />
独立本科段<br />
汉语言文学<br />
本文标题: 本文地址:<br />
热搜 o 问答<br />
最新考试信息<br />
2017年9月考试热点<br />
教育桔(hijiaoyuju)<br />
版权所有 深圳市诺达教育股份有限公司 (C)<br />
All Rights Reserved 粤ICP备号-3君，已阅读到文档的结尾了呢~~<br />
精品：运筹学复习资料 运筹学复习题及*** 管理学基础复习资料 自考 运筹学基础 运筹学基础小抄 管理运筹学 运筹学基础 运筹学基础及应用 管理运筹学*** 管理运筹学课件<br />
扫扫二维码，随身浏览文档<br />
手机或平板扫扫即可继续访问<br />
管理运筹学基础复习资料<br />
举报该文档为侵权文档。<br />
举报该文档含有违规或不良信息。<br />
反馈该文档无法正常浏览。<br />
举报该文档为重复文档。<br />
推荐理由：<br />
将文档分享至：<br />
分享完整地址<br />
文档地址：<br />
粘贴到BBS或博客<br />
flash地址：<br />
支持嵌入FLASH地址的网站使用<br />
html代码：<br />
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&<br />
450px*300px480px*400px650px*490px<br />
支持嵌入HTML代码的网站使用<br />
您的内容已经提交成功<br />
您所提交的内容需要审核后才能发布，请您等待！<br />
3秒自动关闭窗口《运筹学》题库_甜梦文库<br />
《运筹学》题库<br />
运筹学习题库 数学建模题（5） 1、某厂生产甲、乙两种产品，这两种产品均需要 A、B、C 三种资源，每种产品的资源消耗 量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示： A 甲 乙 9 4 360 B 4 6 200 C 3 10 300 70 120试建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。 解：设甲、乙产品的生产数量应为 x1、x2，则 x1、x2≥0，设 z 是产品售后的总利润，则 max z =70x1+120x2 s.t.?9 x1 ? 4 x 2 ? 360 ? ?4 x1 ? 6 x 2 ? 200 ? ? 3 x1 ? 10x 2 ? 300 ? x1，x 2 ? 0 ?2、某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有关数据如下： 甲 原材料（吨/件） 工时（工时/件） 零件（套/件） 产品利润（元/件） 2 5 1 4 乙 2 2.5 3 可用量 3000 吨 4000 工时 500 套建立使利润最大的生产计划的数学模型，不求解。 解：设甲、乙两种产品的生产数量为 x1、x2， 设 z 为产品售后总利润，则 max z= 4x1+3x2 s.t.?2 x1 ? 2 x2 ? 3000 ?5 x ? 2.5 x ? 4000 ? 1 2 ? ? 500 ? x1 ? x1 , x2 ? 0 ?3、一家工厂制造甲、乙、丙三种产品，需要三种资源——技术服务、劳动力和行政管理。 每种产品的资源消耗量、 单位产品销售后所能获得的利润值以及这三种资源的储备量如下表 所示： 技术服务 甲 乙 1 1 劳动力 10 4 行政管理 2 2 单位利润 10 61 丙 资源储备量1 1005 6006 3004建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。 解：建立线性规划数学模型： 设甲、乙、丙三种产品的生产数量应为 x1、x2、x3，则 x1、x2、x3≥0，设 z 是产品售后的总 利润，则 max z =10x1+6x2+4x3 s.t.? x1 ? x2 ? x3 ? 100 ?10x ? 4 x ? 5 x ? 600 ? 1 2 3 ? ?2 x1 ? 2 x2 ? 6 x3 ? 300 ? x1，x2，x3 ? 0 ?4、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通 信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg, 试选择该队员所应携带的物品。 序号 物品 重量/Kg 重要性系数 1 食品 5 20 2 氧气 5 15 3 冰镐 2 18 4 绳索 6 14 5 帐篷 12 8 6 照相器材 2 4 7 通信设备 4 10试建立队员所能携带物品最大量的线性规划模型，不求解。 解：引入 0—1 变量 xi, xi=1 表示应携带物品 i，,xi=0 表示不应携带物品 Inaxz ? 20x1 ? 15x 2 ? 18x3 ? 14x 4 ? 8 x5 ? 4 x 6 ?10x7 ?5 x1 ? 5 x 2 ? 2 x3 ? 6 x 4 ? 12x5 ? 2 x 6 ? 4 x7 ? 25 ? ? xi ? 0或1, i ? 1,2,...,75、工厂每月生产 A、B、C 三种产品，单件产品的原材料消耗量、设备台时的消耗量、资源 限量及单件产品利润如下图所示：产 资 源 品ABC资源限量材料（kg） 设备（台时）1.5 31.2 1.6 144 1.2 12利润（元/件） 10根据市场需求， 预测三种产品最低月需求量分别是 150、 260、 120， 最高需求量是 250、 310、 130，试建立该问题数学模型，使每月利润最大，为求解。 解：设每月生产 A、B、C 数量为 x1 , x2 , x3 。MaxZ ? 10x1 ? 14x2 ? 12x3 1.5x1 ? 1.2x2 ? 4 x3 ? 25002 3x1 ? 1.6x2 ? 1.2x3 ? 1400150 ? x1 ? 250 260 ? x2 ? 310120 ? x3 ? 130x1 , x2 , x3 ? 06、A、B 两种产品，都需要经过前后两道工序，每一个单位产品 A 需要前道工序 1 小时和后 道工序 2 小时， 每单位产品 B 需要前道工序 2 小时和后道工序 3 小时。 可供利用的前道工序 有 11 小时，后道工序有 17 小时。 每加工一个单位产品 B 的同时，会产生两个单位的副产 品 C，且不需要任何费用，产品 C 一部分可出售盈利，其余只能加以销毁。 出售 A、B、C 的利润分别为 3、7、2 元，每单位产品 C 的销毁费用为 1 元。预测表明，产品 C 最多只能售 出 13 个单位。试建立总利润最大的生产计划数学模型，不求解。 解：设每月生产 A、B 数量为 x1 , x2 , 销毁的产品 C 为 x3 。MaxZ ? 3x1 ? 7 x2 ? 2(2x2 ? x3 ) ? x3x1 ? 2 x2 ? 11 2x1 ? 3x2 ? 172x2 ? x3 ? 13x1 , x2 , x3 ? 07、靠近某河流有两个化工厂（参见附图） ，流经第一化工厂的河流流量为每天 500 m ，在 两个工厂之间有一条流量为 200 万 m 的支流。第一化工厂每天排放有某种优化物质的工业 污水 2 万 m ，第二化工厂每天排放该污水 1.4 万 m 。从第一化工厂的出来的污水在流至 第二化工厂的过程中， 20%可自然净化。 有 根据环保要求， 河流中的污水含量不应大于 0.2%。 这两个工厂的都需要各自处理一部分工业污水。第一化工厂的处理成本是 1000 元/万 m ， 第二化工厂的为 800 元/万 m 。 现在要问满足环保的条件下， 每厂各应处理多少工业污水， 才能使两个工厂的总的污水处理费用最少？列出数学模型，不求解。 附图： ¤工厂 1 ¤工厂 23 3 3 3 333 500 万 m3200 万 m3解：设第一化工厂和第二化工厂的污水处理量分别为每天 x1 m 和 x2 万 m ，33min Z ? 1000x1 ? 800x2?1 ? x1 ? 2 ?0.8 x ? x ? 1.6 ? 1 2 st ? ? x 2 ? 1 .4 ? x1 , x 2 ? 0 ?8、消费者购买某一时期需要的营养物（如大米、猪肉、牛奶等） ，希望获得其中的营养成分 （如：蛋白质、脂肪、维生素等） 。设市面上现有这 3 种营养物，其分别含有各种营养成分 数量，以及各营养物价格和根据医生建议消费者这段时间至少需要的各种营养成分的数量 （单位都略去）见下表。营养物 营养成分甲 4 1 1 21 25乙 6 1 0 7 20丙 20 2 3 35 45至少需要的营养成分数量 80 65 70 450A B C D 价格问：消费者怎么购买营养物，才能既获得必要的营养成分，而花钱最少？只建立模型，不用 计算。 解：设购买甲、乙、丙三种营养物的数量分别为 x1、x2和x3 ， 则根据题意可得如下线性规 划模型：min z ? 25x1 ? 20x2 ? 45x3 ? 4 x1 ? 6 x2 ? 20x3 ? 80 ? x ? x ? 2 x ? 65 1 2 3 ? ? s.t.? x1 ? 3x3 ? 70 ?21x ? 7 x ? 35x ? 450 2 3 ? 1 ? x1 , x2 , x3 ? 0 ?9、某公司生产的产品 A，B，C 和 D 都要经过下列工序：刨、立铣、钻孔和装配。已知每 单位产品所需工时及本月四道工序可用生产时间如下表所示： 刨 A B C 0.5 1.0 1.0 立铣 2.0 1.0. 1.0 钻孔 0.5 0.5 1.0 装配 3.0 1.0. 2.04 D 可用生产时间 （小时）0.5 18001.0 28001.0 30003.0 6000又知四种产品对利润贡献及本月最少销售需要单位如下： 产品 A B C D 最少销售需要单位 100 600 500 400 元/单位 2 3 1 4问该公司该如何安排生产使利润收入为最大？（只需建立模型） 解：设生产四种产品分别 x1,x2,x3,x4 单位 则应满足的目标函数为：max z=2 x1+3 x2+x3+ x4 满足的约束条件为：?0.5 x1 ? x2 ? x3 ? 0.5 x4 ? 1800 ?2 x ? x ? x ? x ? 2800 ? 1 2 3 4 ?0.5 x1 ? 0.5 x2 ? x3 ? x4 ? 3000 ? ?3 x1 ? x2 ? 2 x3 ? 3x4 ? 6000 ? ? x1 ? 100 ? x2 ? 600 ? ? x3 ? 500 ? x ? 400 ? 410、某航空公司拥有 10 架大型客机、15 架中型客机和 2 架小型客机，现要安排从一机场 到 4 城市的航行计划，有关数据如表 1-5，要求每天到 D 城有 2 个航次（往返） ，到 A,B,C 城市各 4 个航次（往返） ，每架飞机每天只能完成一个航次，且飞行时间最多为 18 小时， 求利润最大的航班计划。客机类型 大型中型小型到达城市 A B C D A B C D A B C D飞行费用（元/次） 00<br />
---00 ----飞行收入（元/次） 000<br />
---00 ----飞行时间（h/d） 1 2 5 10 2 4 8 20 1 2 6 19解：设大型客机飞往 A 城的架次为 x1A，中型客机飞往 A 城的架次为 x2A，小型客机飞往 A 城的架次为 x3A，其余依此类推。 资源限制派出的大型客机架次不能超过 10 架，表示为5 x1A ? x1B ? x1C ? x1D ? 10同理x2 A ? x2 B ? x2C ? 15 x3 A ? x3 B ? x3C ? 2班次约束飞往各城的班次要满足x1 A ? x2 A ? x3 A ? 4 x1B ? x2 B ? x3 B ? 4 x1C ? x2C ? x3C ? 4 x1D ? x2 D ? x3 D ? 2非负性约束 xij ? 0 且为整数； （i=1,2,3;j=A,B,C,D）目标函数为max z ? － 1000 x1A ? 0 x1B ? 2000 x1C ? 8000x1D +2000 x2 A ? 2000 x2 B ? 2000 x2C ? 2000 x3 A ? 2000 x3B ? 2000 x3C11、 CRISP 公司制造四种类型的小型飞机：AR1 型（具有一个座位的飞机） 、AR2 型（具有 两个座位的飞机） 、AR4 型（具有四个座位的飞机）以及 AR6 型（具有六个座位的飞机） 。AR1 和 AR2 一般由私人飞行员购买，而 AR4 和 AR6 一般由公司购买，以便加强公司的飞行编队。 为了提高安全性，联邦航空局（F.A.A）对小型飞机的制造做出了许多规定。一般的联邦航 空局制造规章和检测是基于一个月进度表进行的， 因此小型飞机的制造是以月为单位进行的。 表说明了 CRISP 公司的有关飞机制造的重要信息。AR1 联邦航空局的最大产量（每月生产的飞机数目） 建造飞机所需要的时间（天） 每架飞机所需要的生产经理数目 每架飞机的盈利贡献（千美元） 8 4 1 62 AR2 17 7 1 84 AR4 11 9 2 103 AR6 15 11 2 125CRISP 公司下个月可以得到的生产经理的总数是 60 人。该公司的飞机制造设施可以同 时在任何给定的时间生产多达 9 架飞机。 因此， 下一个月可以得到的制造天数是 270 天 （9*30， 每月按 30 天计算） 。Jonathan Kuring 是该公司飞机制造管理的主任，他想要确定下个月的 生产计划安排，以便使盈利贡献最大化。 解：设 x1 表示下个月生产 AR1 型飞机的数目， x2 表示 AR2 型， x3 表示 AR4 型， x4 表示 AR6 型 目标函数： max z ? 62 x1 ? 84 x2 ? 103x3 ? 125x46 4 x1 ? 7 x2 ? 9 x3 ? 11x4 ? 270 x1 ? x2 ? 2 x3 ? 2 x4 ? 60 x1 ? 8约束条件： x2 ? 17x3 ? 11 x4 ? 15 x1 , x2 , x3 , x4 ? 0x1, x2 , x3 , x4 为整数12、永辉食品厂在第一车间用 1 单位原料 N 可加工 3 单位产品 A 及 2 单位产品 B，产品 A 可 以按单位售价 8 元出售，也可以在第二车间继续加工，单位生产费用要增加 6 元，加工后单 位售价增加 9 元。产品 B 可以按单位售价 7 元出售，也可以在第三车间继续加工，单位生产 费用要增加 4 元，加工后单位售价可增加 6 元。原料 N 的单位购入价为 2 元，上述生产费用 不包括工资在内。3 个车间每月最多有 20 万工时，每工时工资 0.5 元，每加工 1 单位 N 需 要 1.5 工时，若 A 继续加工，每单位需 3 工时，如 B 继续加工，每单位需 2 工时。原料 N 每月最多能得到 10 万单位。问如何安排生产，使工厂获利最大？ 解：设 x1 为产品 A 的售出量； x2 为 A 在第二车间加工后的售出量； x3 表示产品 B 的售出 量； x4 表示 B 在第三车间加工后的售出量； x5 为第一车间所用原材料的数量， 则目标函数为： max z ? 8x1 ? 9.5x2 ? 7 x3 ? 8x4 ? 2.75x5? x5 ?<br />
x ? 2 x ? 1.5 x ?<br />
5 ? 2 ? 约束条件： ? x1 ? x2 ? 3 x5 ? 0 ?x ? x ? 2x ? 0 5 ? 3 4 ? x1 , x2 , x3 , x4 , x5 ? 0 ?7 ? 化标准形式（5） 1、将下列线性规划模型化为标准形式 解：min z ? x1 ? 2 x2 ? 3 x3 ? x1 ? ? x ? ? 1 ? ?? 3 x1 ? ? x1 ? 0 ? x2 ? x2 ? x2 ? x3 ? x3 ? 2 x3 ? 7 2 ?5x2 ? 0 x3无约束max z ' ? ? x1 ? 2 x2 ? 3( x4 ? x5 ) ? 0 ? x6 ? 0 ? x7 ? x1 ? x2 ? ?x ? x ? ? 1 2 ? ?3 x1 ? x2 ? ? ? x4 ? x5 ? x6 ? 7 x4 ? x5 ? x7 ? 2 2 x3 ? x1?7 ? 0 52、将下列线性规划模型化为标准形式min z ? x1 ? 2 x2 ? 3x3 ?? 2 x1 ? ?? 3x ? ? 1 ? ? 4 x1 ? ? x1 ? 0 ?解：x2 ? x2 ? 2 x2 ?x3 ? 2 x3 ? 3x3 ?9 4 ?6x2 ? 0 x3无约束max z ' ? x1 '?2 x 2 ? 3x3 '?3x3 ' ' x3 '? x3 ' ' ? x 4 ? 9 ?2 x1 '? x 2 ? ?3x '? x ? 2 x ? 2 x ' ' ? x ? 4 ? 1 2 3 3 5 ? 3x3 '?3x3 ' ' ? 6 ?4 x1 '? 2 x 2 ? ? x1?5 ? 0 ?3、将下列线性规划变为最大值标准形。min z ? ?3x1 ? 4 x2 ? 2 x3 ? 5 x4 ?4 x1 ? x2 ? 2 x3 ? x4 ? ?2 ? x ? x ? 3x ? x ? 14 ? 1 2 3 4 st ? ??2 x1 ? 3x2 ? x3 ? 2 x4 ? 2 ? x1 , x2 , x3 ? 0, x4无约束 ?解：8 max z ' ? 3x1 ? 4 x2 ? 2 x3 ? 5 x4 ? 5 x4&'??4 x1 ? x2 ? 2 x3 ? x4 ' ? x4& ? 2 ? ' & ? x1 ? x2 ? 3x3 ? x4 ? x4 ? x5 ? 14 st ? ' & ??2 x1 ? 3x2 ? x3 ? 2 x4 ? 2 x4 ? x6 ? 2 ?x , x , x , x ', x &, x x ? 0 ? 1 2 3 4 4 5, 69 ? 图解法（5） 1、用图解法求解下面线性规划 min z =－3x1+2x2?2 x1 ? 4 x 2 ? 22 ?? x ? 4 x ? 10 2 ? 1 ? ? 2 x1 ? x2 ? 7 ? x ? 3x ? 1 2 ? 1 ? x1 , x 2 ? 0 ?解：可行解域为 abcda，最优解为 b 点。 由方程组 ?? 2 x1 ? 4 x2 ? 22 解出 x =11，x =0 x2 ? 0 ?1 2? x1 ? T ∴X = ? ? x ? =（11，0） ? ? 2?*∴min z =－3×11+2×0=－33 2、用图解法求解下面线性规划 min z =2x1+x2?? x1 ? 4 x2 ? 24 ?x ? x ? 8 ? 1 2 ? ? 5 ? x1 ? 10 ? x2 ? 0 ?解：10 从上图分析，可行解域为 abcde，最优解为 e 点。 由方程组? x1 ? x2 ? 8 ? ? x1 ? 5∴X = ? ?*解出 x1=5，x2=3? x1 ? ? =（5，3）T x2 ? ? ?*∴min z =Z = 2×5+3=13 3、已知线性规划问题如下： Max Z= x1 ? 3x25x1 ? 10x2 ? 50 x1 ? x2 ? 1 x2 ? 4 x1 , x2 ? 0用图解法求解，并写出解的情况 解： x2 6 Z’ 4 2 Z’ x1 0 2 4 6 8 10 5x1+10x2=50 x1+x2=1x2=411 由图可知：5x1 ? 10x2 ? 50 x2 ? 4 x2 ? 4解之得： x1 ? 2则 max Z=2+3*4=14 4、用图解法求解下面线性规划问题max z ? 2 x1 ? x2 ?5 x1 ? 15 ?6 x ? 2 x ? 24 ? 1 2 st. ? ? x2 ? x2 ? 5 ? x1 , x2 ? 0 ?解：12 5、用图解法求解下面线性规划问题max z ? 2 x1 ? 3 x2 ? x1 ? 2 x2 ? 8 ?4 x ? 16 ? 1 s.t. ? ?4 x2 ? 12 ? x j ? 0, j ? 1, 2 ?图解如下：可知，目标函数在 B(4, 2)处取得最大值，故原问题的最优解为 X 大值为 z**? (4,2)T ，目标函数最? 2*4 ? 3*2 ? 14 。二、单纯型法（15） 1、用单纯型法求解下面线性规划问题的解 max z= 3x1+3x2+4x3?3 x1 ? 4 x2 ? 5 x3 ? 40 ? 6 x ? 4 x2 ? 3 x3 ? 66 s.t. ? 1 ? x , x ，x ? 0 ? 1 2 3解：加入松弛变量 x4，x5，得到等效的标准模型： max z= 3x1+3x2+4x3+0 x4+0 x513 ?3x1 ? 4 x2 ? 5 x3 ? x4 ? 40 ? ? x5 ? 66 s.t. ?6 x1 ? 4 x2 ? 3 x3 ? x ? 0, j ? 1,2,...,5 ? j列表计算如下： CB 0 0 XB x4 x5 b 40 66 3 x1 3 6 0 3 4 0 x3 x5 8 42 3/5 （21/5） 12/5 3/5↑ 4 3 x3 x1 2 10 0 1 3 38 0* T3 x2 4 4 0 3 4/5 8/5 16/5 －1/5 4/7 8/21 24/7 －3/74 x3 （5） 3 0 4↑ 1 0 4 0 1 0 4 00 x4 1 0 0 0 1/5 －3/5 4/5 －4/5 2/7 －1/7 5/7 －5/70 x5 0 1 0 0 0 1 0 0 －1/7 5/21 1/7 －1/7θ L 8 2240/3 10∴X =（10，0，2，0，0） ∴max z =3×10+4×2 =38 2、用单纯型法求解下面线性规划问题的解 max z =70x1+120x2?9 x1 ? 4 x 2 ? 360 ? ?4 x1 ? 6 x 2 ? 200 s.t. ? 3 x ? 10 x ? 300 2 ? 1 ? x1，x 2 ? 0 ?解：加入松弛变量 x3，x4，x5，得到等效的标准模型： max z =70x1+120x2+0 x3+0 x4+0 x5 s.t.? 360 ? 9 x1 ? 4 x 2 ? x 3 ? ? x4 ? 200 ? 4 x1 ? 6 x 2 ? ? x 5 ? 300 ? 3 x1 ? 10x 2 ? x j ? 0, j ? 1,2,...,5 ?列表计算如下：14 CB 0 0 0XB x3 x4 x5b 360 200 30070 x1 9 4 3 0 70120 x2 4 6 （10） 0 120↑ 0 0 1 120 0 0 0 1 120 00 x3 1 0 0 0 0 1 0 0 0 0 1 0 0 0 00 x4 0 1 0 0 0 0 1 0 0 0 －39/11 5/11 - 3/22 170/11 -170/110 x5 0 0 1 0 0 - 2/5 - 3/5 1/10 12 －12 19/11 - 3/11 2/11 30/11 －30/11θ L 90 100/3 300 0 120x3 x4 x2240 20 3039/5 （11/5） 3/10 36 34↑400/13 100/11 1000 70 120x3 x1 x2/11 300/110 1 0 70 043000 11∴X =（*100 300 1860 T ， ， ，0，0） 11 11 11100 300 4× = 11 11 11∴max z =70×3、用单纯型法求解下面线性规划问题的解?2 x1 ? 2 x2 ? 3000 ?5 x ? 2.5 x ? 4000 ? 1 2 max z= 4x1+3x2s.t. ? ? 500 ? x1 ? x1 , x2 ? 0 ?解：加入松弛变量 x3，x4，x5，得到等效的标准形式：max z= 4x1+3x2+0 x3+0 x4+0?2 x1 ? 2 x2 ? x3 ? 3000 ?5 x ? 2.5 x ? x ? 4000 ? 1 2 4 x5s.t. ? ? x5 ? 500 ? x1 ? x j ? 0 , j ? 1,2,...,5 ?用表解形式的单纯形法求解，列表计算如下：15 4 CB XB b x1 2 5 （1） 0 4↑ 0 0 4 x3 x4 x1 0 0 0 1 4 0 0 3 4 x3 x2 x1 800 600 500 0 0 1 4 0 0 3 4 x5 x2 x1 400 0 0 0 1 43 x2 2 2.5 0 0 3 2 （2.5） 0 0 3↑ 0 1 0 3 0 0 1 0 30 x3 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0.5 1 -0.5 10 x4 0 1 0 0 0 0 1 0 0 0 -0.8 0.4 0 1.2 -1.2 -0.4 -0.4 0.4 0.40 x5 0 0 1 0 0 -2 -5 1 4 -4 （2） -2 1 -2 2↑ 1 0 0 0 800/2 =400 —— 500/1 =500 00<br />
=600 —— θL0 0 0x3 x4 x5000 0 500/1 =5000 0 -1 -0.4 0 T 据上表，X =（100，，400） max z =4×100+3×、用单纯型法求解下面线性规划问题的解 max z =10x1+6x2+4x3 s.t.*16 ? x1 ? x2 ? x3 ? 100 ?10x ? 4 x ? 5 x ? 600 ? 1 2 3 ? ?2 x1 ? 2 x2 ? 6 x3 ? 300 ? x1，x2，x3 ? 0 ?解：加入松弛变量 x4，x5，x6，得到等效的标准模型： max z =10x1+6x2+4x3+0 x4+0 x5+0 x6? 100 ? x1 ? x2 ? x3 ? x4 ?10x ? 4 x ? 5 x ? x ? 600 ? 1 2 3 5 s.t. ?2 x ? 2 x ? 6 x ? x6 ? 300 2 3 ? 1 ? x j ? 0, j ? 1,2,...,6 ?列表计算如下： CB 0 0 0 XB x4 x5 x6 b 100 600 300 10 x1 1 （10） 2 0 10↑ 0 10 0 x4 x1 x6 40 60 180 0 1 0 10 0 6 10 0 x2 x1 x6 200/3 100/3 100 0 1 0 10 0 6 x2 1 4 2 0 6 （3/5） 2/5 6/5 4 2↑ 1 0 0 6 0T4 x3 1 5 6 0 4 1/2 1/2 5 5 －1 5/6 1/6 4 20/30 x4 1 0 0 0 0 1 0 0 0 0 5/3 －2/3 －2 10/30 x5 0 1 0 0 0 －1/10 1/10 －1/5 1 －1 －1/6 1/6 0 2/3 －2/30 x6 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0θ L 100 60 150200/3 150 1502200 3∴X =（*－8/3 －10/3100 200 ， 3 3，0，0，0，100）∴max z =10×200 × = 3 3 35、用单纯型法求解下面线性规划问题的解17 Max Z? 4x1 - 2x2 ? 2x3 3x1 ? x2 ? x3 ? 60 x1 ? x2 ? 2x3 ? 10 2 x1 ? 2x2 ? 2x3 ? 40x1 , x2 , x3 ? 0用单纯形法求解，并指出问题的解属于哪一类。 解： 、将原问题划为标准形得： （1）MaxZ ? 4x1 ? 2x2 ? 2x3 ? 0x4 ? 0x5 ? 0x63x1 ? x2 ? x3 ? x4 =60x1 ? x2 ? 2 x3 ? x5 ? 10 2x1 ? 2x2 ? 2x3 ? x6 ? 40 x1 , x2 , x3 , x4 , x5 , x6 ? 0Cj4 b 60 10 40 -2 2 0 0 0CB0 0 0XBx13 [1] 2 4 4x21 -1 -2 -2 -2x31 2 2 2 2x41 0 0 0 0x50 1 0 0 0x60 0 1 0 0x4x5 x6?jCjCB0 4 0XBb 30 10 20x10 1 0x24 -1 [4]x3-5 2 -6x41 0 0x5-3 1 -2x60 0 1x4x1x618 ?jCj0 4 b 10 15 52 -2-6 20 0-4 00 0CB0 4 -2XBx10 1 0 0x20 0 1 0x31 1/2 -3/2 -3x41 0 0 0x5-1 1/2 -1/2 -3x6-1 1/4 1/4 -1/2x4x1x2?j所以 X=（15，5，0，10，0，0） Max Z=4*15-2*5=50 6、用单纯形法求解下述 LP 问题。T为唯一最优解max z ? 2.5 x1 ? x2 ?3x1 ? 5 x2 ? 15 ? s.t. ?5 x1 ? 2 x2 ? 10 ?x , x ? 0 ? 1 2解：引入松弛变量 x3 、 x4 ，化为标准形式：max z ? 2.5 x1 ? x2 ?3x1 ? 5 x2 ? x3 ? 15 ? s.t. ?5 x1 ? 2 x2 ? x4 ? 10 ?x , x , x , x ? 0 ? 1 2 3 4构造单纯形表，计算如下：cj2.5100?icB0 0XBb15 10x13 [5] 2.5x25 2 1 [19/5]x31 0 0 1x40 1 0 －3/5 45/19 5 2x3 x4?j0x39019 2.5x121 02/5 0 1 0 00 0 5/19 －2/19 01/5 －1/2 －3/19 5/19 －1/25?j1 2.5x2 x145/19 20/190 1 0(1)?j由单纯形表，可得两个最优解 X? (2,0,9,0)T 、 X (2) ? (20 /19,45 /19,0,0)T ，所以(1)两点之间的所有解都是最优解，即最优解集合为：? X 7、用单纯形法解线性规划问题? (1 ? ? ) X (2) ，其中 0 ? ? ? 1 。max z ? 2 x1 ? x2 5 x2 ? ? 6x ? 2x ? 1 2 ? x2 ? x1 ? ? x1 ? 0 ?解：化为标准型? 15 ? 24 ?5 x2 ? 0max z ? 2 x1 ? x2 ? 0 x3 ? 0 x4 ? 0 x5 5 x2 ? ?6 x ? 2 x ? 1 2 ? x2 ? x1 ? ? ?列出单纯形表 Cj CB 0 0 0 0 2 0 XB b 15 24 5 0 15 4 1 -8 2 1 0 0 0? x3 ? 15 ? x4 ? 24 ? x5 ? 5 x1?5 ? 0x10 [6] 1 2 0 1 0 0x25 2 1 1 5 1/3 [2/3] 1/3x31 0 0 0 1 0 0 0x40 1 0 0 0 1/6 -1/6 -1/3x50 0 1 0 0 0 1 020x3 x4 x5-Z4 5 3 12 3/2x3 x1 x5-Z 0 2 1x3 x1 x2 -Z15/2 7/2 3/2 -200 1 0 00 0 1 01 0 0 05/4 1/4 -1/4 -1/4-15/2 -1/2 3/2 -1/2Z*=17/2, X*=(7/2,3/2, 15/2,0,0)’ 8、用单纯型法求解下面线性规划问题的解max z ? x1 ? x2 2 x2 ? x1 ? ?? 2 x ? x ? 1 2 ? x2 ? ? x1 ? ? x1 ? 0 ?解： Cj CB 0 0 0 1 0 0 XB b 2 2 4 0 2 6 6 -2 1 1 0 0 0?2 ?2 ?4 x2 ? 0x1[1] -2 -1 1 1 0 0 0x212 1 1 1 -2 -3 -1 3x31 0 0 0 1 2 1 -1x40 1 0 0 0 1 0 0x50 0 1 0 0 0 1 0 2x3 x4 x5-Zx1 x4 x5-Z把表格还原为线性方程max z ? 3 x 2 ? x3 ? 2 ? x1 ? ? ? ? ? 2 x2 ? 3x2 ? x2 ? x3 ? 2 x3 ? x3? x3 ? 2 x3 ? x3?2 ? x4 ? x5 ?6 ?6? x1 ? 2 ? 2 x 2 ? ? x4 ? 6 ? 3x2 ?x ? 6 ? x 2 ? 5令 x 3=0? x1 ? 2 ? 2 x 2 ? ? x4 ? 6 ? 3x2 ?x ? 6 ? x 2 ? 5此时，若让x2进基，则会和基变量x1同时增加，使目标函数值无限增长，所以本题无界 9、用单纯型法求解下面线性规划问题的解21 max z ? 2 x1 ? 4 x2 ? x1 ? 2 x2 ? x ? 1 ? x2 ? ? x1 ? 0 ? ?8 ?4 ?3 x2 ? 0Cj CB 0 0 0 0 0 4 2 0 4 2 0 4 XB b 8 4 3 0 2 4 3 -12 2 2 3 -20 4 1 2 -2024000x11 1 0 2 [1] 1 0 2 1 0 0 0 1 0 0 0x22 0 [1] 4 0 0 1 0 0 0 1 0 0 0 1 0x31 0 0 0 1 0 0 0 1 -1 0 -2 0 -1/2 1/2 -2x40 1 0 0 0 1 0 0 0 1 0 0 1 1/2 -1/2 0x50 0 1 0 -2 0 1 -4 -2 2 1 0 0 1 0 0 2 4 4 3x3 x4 x5-Zx3 x4 x2-Zx1 x4 x2 -Z x1 x5 x2 -ZZ*=20, X*=(2,3,0,2,0)’Z*=20, X*=(4,2,0,0,1)’ 10、用单纯型法求解下面线性规划问题的解max z ? 3 x1 ? 5 x2 ? x1 ? 2 x2 ? ? ? 3 x1 ? 2 x2 ? x1 ? 0 ?解：列表如下 Cj CB 0 0 0 XB b 4 12 18 0 3 5 0 0 0?4 ? 12 ? 18 x2 ? 0x11 0 3 3x20 [2] 2 5x31 0 0 0x40 1 0 0x50 0 1 022x3 x4 x5-Z6 9 0 5 0 0 5 3x3 x2 x5-Z4 6 6 -30 6 2 2 -201 0 [3] 3 0 0 1 00 1 0 0 0 1 0 01 0 0 0 1 0 0 00 1/2 -1 -5/2 1/3 1/2 -1/3 -3/20 0 1 0 -1/3 0 1/3 -14 3x3 x2 x1 -ZX*=(2,6,6,0,0)’ Z*=36 11、用单纯型法求解下面线性规划问题的解max z ? 2 x1 ? x2 ?5 x1 ? 15 ?6 x ? 2 x ? 24 ? 1 2 st. ? ? x2 ? x2 ? 5 ? x1 , x2 ? 0 ?解：化为标准型max z ? 2 x1 ? x2 ?5 x1 ? x3 ? 15 ?6 x ? 2 x ? x ? 24 ? 1 2 4 st. ? x2 ? x2 ? x5 ? 5 ? ? x1 , x2 , x3 , x4 , x5 ? 0 ?单纯型表如下： Cj CB 0 0 0 0 2 0 0 2 1 XB x3 x4 x5 Z x3 x1 x5 Z x3 x1 x2 Z b 15 24 5 0 15 4 1 0 15/2 7/2 3/2 17/2 2 1 0 0 0x10 [6] 1 2 0 1 0 0 0 1 0 0x25 2 1 1 5 1/3 [2/3] 1/3 0 0 1 0x31 0 0 0 1 0 0 0 1 0 0 0x40 1 0 0 0 1/6 -1/6 -1/3 5/4 1/4 -1/4 -1/4x50 0 1 0 0 0 1 0 -15/2 -1/2 3/2 -1/2 3 12 3/2 – 4 5由些可得，问题的最优解为 x1=7/2，x2=3/2，最优值 max z=17/2 12、用大 M 法求解如下线性规划模型： minz =5x1＋2x2＋4x323 ?3 x1 ? x2 ? 2 x3 ? 4 ? ?6 x1 ? 3 x2 ? 5 x3 ? 10 ? x ,x ,x ? 0 ? 1 2 3解：用大 M 法，先化为等效的标准模型： / max z =－5x1－2x2－4x3 s.t.?3x1 ? x2 ? 2 x3 ? x4 ?4 ? ? x5 ? 10 ?6 x1 ? 3x2 ? 5 x3 ? y ? 0, j ? 1,2,...,5 ? j增加人工变量 x6、x7，得到： / max z =－5x1－2x2－4x3－Mx6－Mx7 s.t?3x1 ? x2 ? 2 x3 ? x4 ? x6 ?4 ? ? x5 ? x7 ? 10 ?6 x1 ? 3x2 ? 5 x3 ? x ? 0, j ? 1,2,...,7 ? jCB －M －M 大 M 法单纯形表求解过程如下： －5 －2 XB b x1 x2 x6 x7 4 10 （3） 6 －9M 9M－5↑ －5 －M x1 x7 4/3 2 1 0 －5 0 －5 0 x1 x4 5/3 1 1 0 －5 0 －5 －2 x1 x2 2/3 2 1 0 1 3 －4M 4M－2 1/3 1 -M－5/3 M－1/3 1/2 （1/2） －5/2 1/2↑ 0 1 －4 x3 2 5 －7M 7M－4 2/3 1 -M－10/3 M－2/3 5/6 1/2 －25/6 1/6 1/3 1 0 x4 －1 0 M －M －1/3 （2） -2M+5/3 2M－5/3↑ 0 1 0 0 －1 2 0 x5 0 －1 M －M 0 －1 M －M －1/6 －1/2 5/6 －5/6 1/3 －1 －M x6 1 0 －M 0 1/3 －2 2M－5/3 －3M+5/3 0 －1 0 －M 1 －2 －M x7 0 1 －M 0 0 1 -M 0 1/6 1/2 －5/6 －M+5/6 －1/3 1 10/3 2 —— 1 θ L 4/3 5/324 －－5 0－2 0－11/3 －1/31 －11/3 －1/3－1 －M+1－1/3 －M+1/322 3*∴x =（2 3，2，0，0，0）T最优目标函数值 min z =－max z =－（－/22 22 ）= 3 313、用大 M 法求解如下线性规划模型： minz =540x1＋450x2＋720x3?3x1 ? 5 x2 ? 9 x3 ? 70 ? ?9 x1 ? 5 x2 ? 3x3 ? 30 ? x ,x ,x ?0 ? 1 2 3解：用大 M 法，先化为等效的标准模型： / max z =－540x1－450x2－720x3 s.t.?3 x1 ? 5 x2 ? 9 x3 ? x4 ? 70 ? ? x5 ? 30 ?9 x1 ? 5 x2 ? 3 x3 ? y ? 0, j ? 1,2,...,5 ? j增加人工变量 x6、x7，得到： / max z =－540x1－450x2－720x3－Mx6－Mx7 s.t?3x1 ? 5 x2 ? 9 x3 ? x4 ? x6 ? 70 ? ? x5 ? ? x7 ? 30 ?9 x1 ? 5 x2 ? 3x3 ? x ? 0, j ? 1,2,...,5 ? jCB －M －M 大 M 法单纯形表求解过程如下： －540 －450 XB b x1 x2 x6 x7 70 30 3 （9） －12M 12M－540↑ －M x6 60 0 5 5 －10M 10M－450 10/3 －720 x3 9 3 －12M 12M－720 （8） 0 x4 －1 0 M －M －1 0 x5 0 －1 M －M 1/3 －M x6 1 0 －M 0 1 －M x7 0 1 －M 0 －1/325θ L 70/3 30/9=10/ 360/8=2.5 －540x110/315/9 -300+10/3M1/3 -8M－1800 －M M－1/9 －M/3+60 M/3－600 －M 01/9 M/3－60 －M/3+6010/3/1/3 =100-150+10/3M 8M-540↑－720x315/205/121－1/81/241/8－1/24－540x15/61 －540 0（5/12） －572 125↑ 0 1 －450 00 －720 0 1 0 －720 01/24－1/8－1/24 －135/2 135/2－M 1/6 －1/10 －75 75－M1/8 －75/2 75/2－M －1/6 3/10 －15 15－M15/2/5/1 2 =18 5/6/5/12 =2－135/2 475/12 135/2 －475/12 1/6 1/10 75 －75 1/6 －3/10 15 －15－720 －450x3 x220/3 2－1 12/5 －360－5700 －180∴该对偶问题的最优解是 x =（0，2， 最优目标函数值 min z =－（－5700）=5700 14、用单纯形法求解线性规划问题*20 3，0，0）Tmax z ? ?3 x1 ? x3 ? x1 ? ?? 2 x ? ? 1 ? ? ? x1 ? 0 ?化成标准形式有x2 ? x2 ? 3 x2 ?x3 ? x3 ? x3 ?4 1 9x2 ? 0 x3 ? 0max z ? ?3 x1 ? x3 ? 0 x4 ? 0 x5 x2 ? ? x1 ? ?? 2x ? x ? ? 1 2 ? 3 x2 ? ? ? x1?5 ? 0 ?加入人工变量则为x3 ? x3 x3x4 ? x5?4 ?1 ?926 max z ? ?3x1 ? x3 ? 0 x4 ? 0 x5 ? Mx6 ? Mx7 x2 ? ? x1 ? ? ? 2x ? x ? ? 1 2 ? 3 x2 ? ? ? x1?7 ? 0 ?列出单纯形表 Cj CB 0 -M -M 0 0 -M 0 0 -3 0 0 1 XB b 4 1 9 10M 3 1 6 6M 0 3 1 3 0 5/2 3/2 -3/2 －3 0 1 0 0 －M -Mx3 ? x3 x3x4 ? x5 ? x6?4 ?1 ? x7 ? 9x11 -2 0 -2M-3 3 -2 [6] 6M-3 0 0 1 0 0 -1/2 3/2 -9/2x21 [1] 3 4M 0 1 0 0 0 1 0 0 0 1 0 0x31 -1 1 1 2 -1 4 4M+1 0 1/3 [2/3] 3 0 0 1 0x41 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0x50 -1 0 -M 1 -1 3 3M -1/2 0 1/2 3/2 -1/2 -1/4 3/4 -3/4x60 1 0 0 -1 1 -3 -4M -1/2 0 -1/2 -M-3/2 1/2 1/4 -3/4 -M+3/4 0 0 1 0 0 1x7x4 x6 x7-Z0x4 x2 x7-Z0 1/2 1/3 1/6 -M+1/2 -1/2 1/4 1/4 -M-1/4x4 x2 x1 -Z x4 x2 x3 -Z人工变量已不在基变量中，X*=(0,5/2,3/2,0,0,0,0)’ 15、用单纯形法求解线性规划问题Z*=3/2max z ? ?3 x1 ? 2 x2 ? 2 x1 ? x2 ? 3x ? 4 x ? 1 2 ? ? ? x1 ? 0 ? ?2 ? 12 x2 ? 0解化为标准形式有27 max z ? ?3x1 ? 2 x2 ? 0 x3 ? 0 x4 ? Mx5 x2 ? x3 ?2 x1 ? ?3 x ? 4 x ? x ? x ? 1 2 4 5 ? ? ? x1?5 ? 0 ? ?2 ? 12列表计算 Cj CB 0 M -2 M XB b 2 12 -12M 2 4 4-4M －3 －2 0 0 Mx12 3 3M+3 2 -5 -5M-1x2[1] 4 4M+2 1 0 0x31 0 0 1 -4 -4M-2x40 -1 -M 0 -1 -Mx50 1 0 0 1 0 2 3x3 x5-Zx2 x5-ZX*=(0,2,0,0,4)’Z*=4M-4说明原问题无解? 写对偶问题（10） 1、 写出下列线性绘画问题的对偶问题max z ? 2x1 ? x2 ? 3x3 ? x4? x1 ? x 2 ? x3 ? x 4 ? 5 ?2 x ? x ? 3x ? ?4 ? 1 2 3 ? ? x3 ? x 4 ? 1 ? x1 ? x1 , x3 ? 0, x 2 , x 4 无约束 ?解：min? ? 5 y1 ? 4 y2 ? y3? y1 ? 2 y 2 ? y 3 ? 2 ? ?1 ? y1 ? y 2 ? ? y1 ? 3 y 2 ? y 3 ? 3 ?y ? y3 ? 1 ? 1 ? y1 ? 0, y 2 无约束, y 3 ? 0 ?2、写出下述线性规划的对偶问题28 max z ? x1 ? 4 x 2 ? 3 x3 5 x3 ? 2 ? 2 x1 ? 3 x 2 ? ? 3x ? x2 ? 6 x3 ? 1 ? 1 ? x2 ? x3 ? 4 ? x1 ? ? x1 ? 0 x 2 ? 0 x3 无约束 ?解min w ? 2 y1 ? y2 ? 4 y3 ? 2 y1 ? ? 3y ? ? 1 ? ?? 5 y1 ? ? y1 ? 0 ? 3 y2 ? y2 ? 6 y2 ? y2 ? 0 y3 ? y3 ? y3 ? y3无约束 1 4 33、写出下列线性规划的对偶问题min z ? 25 x1 ? 2 x2 ? 3 x3 x2 ? x3 ? 1 ? x1 ? ? x ? 2x ? x3 ? 1 ? 1 2 ? x3 ? 1 ? 2 x1 ? x2 ? ? x1 ? 0 x2 ? 0 x3无约束 ?解：max w ? y1 ? y2 ? y3 ?? y1 ? ? y ? ? 1 ? ?? y1 ? ? y1 ? 0 ? y2 ? 2 y2 ? y2 ? y2 ? 0 2 y3 ? y3 ? y3 ? y3无约束 25 2 34、写出下列线性规划的对偶问题max z ? 2 x1 ? x2 ? 4 x3 x3 ? 1 ? 2 x1 ? 3 x2 ? ? 3x ? x2 ? x3 ? 4 ? 1 ? ? x3 ? 3 ? x1 ? x1 ? 0 x2 ? 0 x3无约束 ?解29 min w ? y1 ? 4 y2 ? 3 y3 ? 2 y1 ? ? 3y ? ? 1 ? ? y1 ? ? y1 ? 0 ? 3 y2 ? y2 y2 ? y2 ? 0 y3 ? ? y3 ? y3无约束 2 1 430 ? 对偶性质 1、已知线性规划问题如下： Max Z= x1 ? 3x25x1 ? 10x2 ? 50 x1 ? x2 ? 1 x2 ? 4 x1 , x2 ? 0已知该问题的解为（2，4）利用对偶性质写出对偶问题的最优解。 解：该问题的对偶问题为：MinZ ? 50y1 ? y2 ? 4 y35 y1 ? y 2 ? 110y1 ? y2 ? y3 ? 3 y1 , y3 ? 0; y2 ? 0将 X=（2，4） 代入原问题可知： x1 ? x2 〉1 为严格不等式，所以 y 2 ? 0T由对偶问题性质可知：50y1 ? 4 y3 ? 1410y1 ? y3 ? 3 y 2 ? 0解之得：y1 ? 1 / 5y3 ? 1所以 Y=（1/5，0，1） 2、已知线性规划问题TMin Z=14min z ? 2x1 ? 3x2 ? 5x3 ? 6x4? x1 ? 2 x 2 ? 3x3 ? x 4 ? 2 ? ?? 2 x1 ? x 2 ? x3 ? 3x 4 ? ?3 ? x j ? 0 ( j ? 1,2,3,4) ?用图解法求对偶问题的解；利用(b)的结果及对偶性质求原问题解。 ***：(对偶问题的最优解为 Y*8 1 ? ( , )； 5 5(依据 z*=w*及互补松弛性，有 x4=0,且31 ?2 x1 ? 3 x 2 ? 5 x3 ? 19 / 5 ? ? x1 ? 2 x 2 ? 3 x3 ? 2 ?2 x ? x ? x ? 3 2 3 ? 1解得愿问题最优解 X*=(7/5,0,1/5,0)。 3、已知线性规划问题min ? ? 2x1 ? 3x2 ? 5x3 ? 2x4 ? 3x5 s.t.x1 ? x2 ? 2x3 ? x4 ? 3x5 ? 4 2x1 ? x2 ? 3x3 ? x4 ? x5 ? 3x j ? 0, j ? 1,2,?,5*已知其对偶问题的最优解为 y1 ? 的最优解。 解 先写出它的对偶问题4 * 3 , y 2 ? ，最优值为 z * ? 5 。试用对偶理论找出原问题 5 5max z ? 4 y1 ? 3 y2s.t. y1 ? 2 y2 ? 2 ①y1 ? y2 ? 3 ②2 y1 ? 3 y3 ? 5 ③y1 ? y2 ? 2 ④ 3 y1 ? y2 ? 3 ⑤ y1 , y2 ? 0将 y1 , y2 的 值 代 入 约 束 条 件 ， 得 ② ， ③ ， ④ 为 严 格 不 等 式 ； 设 原 问 题 的 最 优 解 为* * * * * * * x* ? ( x1 ,?, x5 ) ，由互补松弛性得 x2 ? x3 ? x4 ? 0 。因 y1 , y2 ? 0 ；原问题的两个约束 * *条件应取等式，故有* * 3x1 ? x5 ? 4 * * 2 x1 ? x5 ? 3 * * 求解后得到 x1 ? 1, x5 ? 1 ；故原问题的最优解为32 X * ? [1 0 0 0 1]' ；最优值为 w* ? 5 。4、已知下列问题的最优解为X*=(1/7,11/7),用互补松弛定理求其对偶问题的最优解。LP : max z ? x1 ? 2 x2 ?3 x1 ? x2 ? 2 ?? x ? 2 x ? 3 ? 1 2 ? ? x1 ? 3 x2 ? 1 ? x1, x 2 ? 0 ?解：第一步，写出对偶问题 第二步，将 LP，DP 都化为标准型DP : min w ? 2 y1 ? 3 y2 ? y3 ? 3 y1 ? ? y ? ? 1 ? ? ? y1 ? 0 ? y2 ? 2 y2 ? y2 ? 0 y3 ? 3 y3 ? y3 ? 0 1 2LP : max z ? x1 ? 2 x 2 ? x1S ?2 ?3 x1 ? x 2 ?? x ? 2 x ? x2 S ?3 ? 1 2 ? ? x3 S ? 1 ? x1 ? 3 x 2 ? x1, x 2 ? 0 x1S , 2 S , 3 S ? 0 ?DP : min w ? 2 y1 ? 3 y 2 ? y 3 ? 3 y1 ? ? y ? ? 1 ? ? ? y1 ? 0 ? y2 ? 2 y2 ? y2 ? 0 y3 3 y3 y3 ? 0 ? y1S ? 1 ? y2S ? 2 y1S , 2 S ? 0第三步：将最优解代入标准型中，确定松弛变量取值? 1 11 ? x1S ?2 ? ?3 ? 7 ? 7 ? x1S ? 0 ? ? 11 ? 1 ? x2 S ? 3 ? ? x2 S ? 0 ?? ? 2 ? 7 ? 7 ? 39 11 ?1 ? x3 S ? ? x3 S ? 1 7 ? ?7 ? 3? 7 ?第四步：利用互补松弛定理? X 1S ? ? ? Y * X S ? (Y1 *,Y2 *,Y3 *)? X 2 S ? ? Y1 * X 1S ? Y2 * X 2 S ? Y3 * X 3 S ? 0 ?X ? ? 3S ?∴Y3*=0? X1 * ? YS X * ? (Y1S , Y2 S )? ? X *? ? Y1S X 1 * ?Y2 S X 2 * ? 0 ? ? 2 ?∴Y1S=0Y2S=033 第五步：将 Y3*=0 则有 ?Y1S=0Y2S=0代入约束条件?3 y1 ? y 2 ? 1 4 ? ? ? y1 ? 7 ? y1 ? 2 y 2 ? 2 ?y2 ?5 7∴对偶问题的最优解为Y*=(4/7,5/7,0)’max z ? x1 ? x 25、已知线性规划问题： ?? ? x1 ?? 2 x1 ? x, ? 1? ? x2 ,x2 x2 x3? ? ?x3 x3 0? 2 ? 1，试用对偶理论证明上述线性规划问题无最优解。 证明：首先看到该问题存在可行解，例如 X ? ?00 0? ，而上述问题的对偶问题为：min w ? 2 y1 ? y 2 ?? y1 ? y ? 1 ? ? y1 ? y1 , ? ? ? ? y2 2 y2 y2 y2 ? ? 1 ? 1 ? 0 0由第一约束条件可知对偶问题无可行解，因而无最优解。由此，原问题也无最优解。 5、已知线性规划问题min z ? 2 x1 ? 3 x2 ? 5 x3 ? 6 x4 ? x1 ? 2 x2 ? 3 x3 ? x4 ? 2 ? s.t.?? 2 x1 ? x2 ? x3 ? 3 x4 ? ?3 ? x j ? 0? j ? 1,2,3,4 ? ?（1）写出其对偶问题； （2）用图解法求对偶问题的解； （3）利用（2）的结果及对偶性质求原问题解。 解： （1）原线性规划问题可化为：min z ? 2 x1 ? 3 x2 ? 5 x3 ? 6 x4 ? x1 ? 2 x2 ? 3 x3 ? x4 ? 2 ? s.t.? 2 x1 ? x2 ? x3 ? 3 x4 ? 3 ? x ? 0? j ? 1,2,3,4 ? ? j其对偶问题为：34 max w ? 2 y1 ? 3 y2 ? y1 ? 2 y2 ? 2 ?2 y ? y ? 3 2 ? 1 ? s.t.?3 y1 ? y2 ? 5 ? y ? 3y ? 6 2 ? 1 ? y1 , y2 ? 0 ?（2）用图解法解得 Y ? ( y1 , y2 ) ? ( , ) w ?* *8 1 5 519 5（3）由互补松弛性定理知道，? y1 ? 3 y2 ? 1 ? 6,? x4 ? 019 ? ?2x1 ? 3x2 ? 5 x3 ? 5 ? 又由 z * ? w* , 可得： x1 ? 2 x2 ? 3 x3 ? 2 ? ? 2x ? x ? x ? 3 1 2 3 ? ?解之，可得原问题最优解 X ? ( 7 ,0, 1 ,0)。*5535 ? 对偶单纯形法（15） 1、用对偶单纯形法解下列线性规划问题min w ? 15 x1 ? 24 x2 ? 5 x3 ? ? ?5 x1 ? ? ?解：先化为标准型6 x2 ? x3 ? 2 2 x2 ? x3 ? 1 x1?3 ? 0max z ? ?15 x1 ? 24 x 2 ? 5 x3 ? 0 ? x 4 ? 0 ? x5 ? ? ?5 x1 ? ? ?约束条件两边同乘(-1)6 x 2 ? x3 ? x 4 ? 2 2 x2 ? x3 ? x5 ? 1 x1?5 ? 0? ? ?? 5 x1 ? ?列单纯形表 Cj CB 0 0 XB b －2 －1? 6 x2 ? ? 2 x2 ?x3 ? x 4 ? ?2 x3 ? x5 ? ?1－15－24－500x10 －5 -15 ---x2[-6] -2 -24 4 1 0 0 1 0 0x3-1 -1 -5 5 1/6 [-2/3] -1 3/2 0 1 0x41 0 0 -1/6 -1/3 -4 12 -1/4 1/2 -7/2x50 1 0 0 1 0 1/4 -3/2 -3/2x4 x5-24 0x2 x51/3 -1/30 -5 -15 3-24 -5x2 x31/4 1/2-5/4 15/2 -15/2X*=(0,1/4,1/2)’Y*=(7/2,3/2)2、用对偶单纯形法解下列线性规划问题36 min z ? 4 x1 ? 12 x2 ? 18 x3 ? x1 ? ? ? ? ?解：改写为标准形式2 x2 ? x1?3 ? 03 x3 ? 3 2 x3 ? 5max z ' ? ?4 x1 ? 12x 2 ?18x3 ? 0 ? x 4 ? 0 ? x5 ?? x1 ? ? ? ? ? 3 x3 ? 2 x2 ? 2 x3 x1?5 ? 0 ? x4 ? x5 ? ?3 ? ?5列单纯形表如下： Cj CB 0 0 XB b －3 －5 －4 －12 －18 0 0x1－1 0 -4 ---x20 [-2] -12 6 0 1 0 0 1 0x3-3 -2 -18 9 [-3] 1 -6 2 1 0 0x41 0 0 1 0 0 12 -1/3 1/3 -2x50 1 0 0 -1/2 -6 --0 -1/2 -6x4 x50 -12x4 x2-3 5/2-1 0 -4 4-18 -12x3 x213/21/3 -1/3 -2X*=(0,3/2,1)’ Y*=(2,6) 3、用对偶单纯形法求解下面的问题：min z ? 12x1 ? 8 x 2 ? 16x3 ? 12x 4 ?2 x1 ? ?2 x1 ?x , ? 1?? ? x2 ,x2 2 x2 x3 ,? ? x44 x3 4 x4 ?? 2 ? 3 0解：令 z ? ? z ，则问题可以标准化为：max z ? ?12x1 ? 8 x2 ? 16x3 ? 12x4 ?? 2 x1 ? ?? 2 x1 ? x, ? 1 ? x2 ? 2 x2 x 2 , x3 , ? 4 x3 ? 4 x4 x 4 , x5 , ? ? x6 x5 x6 ? ? ?2 ? ?3 0?37 取 ?P5? x5 ? ? ? 2 ? ? 1 0? P6 ? ? ? ? ? ? 0 1 ? 为 初 始 基 ， 则 ? x ? ? ? ? 3 ?, 其余 x j ? 0 是 非 基 可 行 解 ， 但 ? ? 6? ? ? ? ?? 1 ? ?12,? 2 ? ?8,? 3 ? ?16,? 4 ? ?12 ，?Y ? CBB ?1 是对偶可行解，建立单纯形表（见表 4-1）计算结果如下：最优解 ?? x2 ? ? 3 / 2 ? ?, 其余x j ? 0，最优值z ? 14. 。 ?? x3 ? ? 1 / 8 ? ? ? ? ?或最优解 ?? x1 ? ?1 / 2 ? ?, 其余x j ? 0，最优值z ? 14. 。 ??? ? ? ? x2 ? ? 1 ?x8 ? ，本例如果用单纯形法计算， 确定初始基可行解时， 还需要引入两个人工变量 ?x7 计算量要多于对欧单纯形法。 表 3-1： C? 12 ? 8 ? 16 ? 12 0 0?备注CB0 0XBx5 x6B b?2 ?3?1x1x2x3x4x5x6?? 3/ 4L=2 K=4? 2 ?1 ? 4 0 1 0 ?2 ?2 0 ?4 0 1-4?0 ? 12? 12 ? 8 ? 16 ? 12 0 0-1x5 x4?2 3/ 4? 2 ?1 1/ 2 1/ 2?4 0 1 0 1 00 ? 1/ 42 3/ 2L=1 K=2??8 ? 12?62 ? 1/ 4?2? 16 0 04 0 ?1 ? 2 1 1/ 2?30 ? 1/ 4L=2 K=1 或 3x2 x42 1 ?-1/2 2 0 1/??8 ? 12?2 01 1/ 2?8 0?2?3x5 x10 1 ? 4 4 ? 3 ?1 1 0 4 ? 2 ? 1 1/ 2? 灵敏度分析 1、已知线性规划的标准形式为38 max z ? ? x1 ? 2 x 2 ? x3 ? 0 ? x 4 ? 0 ? x5 ? x1 ? ?2 x1 ? ? ? x2 ? x2 x1?5 ? 0 ? x3 ? x4 ? x5 ?6 ?4其最优单纯形表如下 Cj CB 2 0 XB b 6 10 -12 －1 2 1 0 0x11 3 -3x21 0 0x31 1 -1x41 1 -2x50 1 0x2 x5-Z问：(1)当 C1 由－1 变为 4 时，求新问题的最优解 (2)讨论 C2 在什么范围内变化时，原有的最优解仍是最优解 解：由表可知，C1 是非基变量的价值系数，因此 C1 的改变只影响σ1? 1 ' ? c1 '? z1 ' ? (c1 ? ?c1 ) ? CB B ?1 p1 ? (c1 ? CB B ?1 p1 ) ? ?c1 ? ? 1 ? ?c1 ? ?3 ? 5 ? 2 ? 0可见最优性准则已不满足，继续迭代 Cj CB 2 0 2 4 XB b 6 10 -12 8/3 10/3 -56/3 4 2 1 0 0x11 [3] 2 0 1 0x21 0 0 1 0 0x31 1 -1 2/3 1/3 -5/3x41 1 -2 2/3 1/3 -8/3x50 1 0 -1/3 1/3 -2/3 6 10/3x2 x5-Zx2 x1-Z(2)要使原最优解仍为最优解，只要在新的条件下满足σ ≤0 成立，因为 x2 是基变量，所以 所有的σ 值都将发生变化 σ ＝C-CBB A-1? (c1 , c 2 ' , c3 , c 4 , c5 ) ? C B B ?1 ( p1 , p 2 , p3 , p 4 , p5 ) ?1 0 ?? 1 1 1 1 0 ? ? (?1, c 2 ' ,1,0,0) ? (c 2 ' , c5 )? ?1 1 ?? 2 ? 1 0 0 1 ? ?? ? ? ?? ? ?1 1 1 1 0? ? (?1, c 2 ' ,1,0,0) ? (c 2 ' ,0)? ?3 0 1 1 1? ? ? ? ? (?1, c 2 ' ,1,0,0) ? (c 2 ' , c 2 ' , c 2 ' , c 2 ' ,0) ? (?1 ? c 2 ' ,0,1 ? c 2 ' ,?c 2 ' ,0) ? 039 ?? 1 ? c 2 ' ? 0 ? 即 ?1 ? c 2 ' ? 0 ?? c ' ? 0 ? 2则 c2’≥1 c2+△c2≥1 △c2≥-1所以当 x2 的系数△c2≥-1 时，原最优解仍能保持为最优解。 2．已知线性规划问题及其最优单纯形表max z ? ? x1 ? x2 ? 4 x3 x 2 ? 2 x3 ? 9 ? x1 ? ? x ? x 2 ? x3 ? 2 ? 1 ? ? ? x1 ? x2 ? x3 ? 4 ? x1?3 ? 0 ?Cj CB －1 0 4 XB b 1/3 6 13/3 -17 －1 －1 4 0 0 0x11 0 0 0x2-1/3 2 2/3 -4x30 0 1 0x41/3 0 1/3 -1x50 1 0 0x6-2/3 1 1/3 -2x1 x5 x3-Z?9 ? ?3 ? ?2? ? ?2? ，求新问题的最优解。 若右端列向量 b ? ? ? ? ? ? 4? ?3 ? ? ? ? ??1 0 2 ? ?3 ? ?1 / 3 0 ? 2 / 3? ?3 ? ?? 1? ? ? ? 2? ? ? 0 1 ?1 1 ? ?2? ? ?5 ? 解： X B ? B (b ? ?b) ? 1 1 ? 1 ? ? ? ? ? ?? ? ? ? ?0 0 1 ? ?3 ? ?1 / 3 0 1 / 3 ? ?3 ? ?2 ? ? ? ? ? ? ?? ? ? ?因为－1 小于 0，因此继续迭代 Cj CB －1 0 4 XB b －1 5 2 -9 3/2 －1 －1 4 0 0 0?1x11 0 0 0 -3/2x2-1/3 2 2/3 -4 12 1/2x30 0 1 0 0x41/3 0 1/3 -1 -1/2x50 1 0 0 0x6[-2/3] 1 1/3 -2 3 140x1 x5 x3-Z σ j/arj0x6 0 4x5 x3-Z7/2 3/2 -63/2 1/2 -33/2 1/2 -30 1 01/2 1/2 -2 Z*=61 0 00 0 0∴新问题的最优解为 X*=(0,0,3/2,0,7/2,3/2)’ 3、已知线性规划问题及其最优单纯形表max z ? 2 x1 ? 3x 2 ? x3 1 1 ?1 ? 3 x1 ? 3 x 2 ? 3 x3 ? x 4 ?1 4 7 ? ? x1 ? x 2 ? x3 3 3 ?3 x1?5 ? 0 ? ? ?最优单纯形表如下： Cj CB 2 3 XB b 1 2 -8 2 3 1 0 0?1 ? x5 ?3x11 0 0x20 1 0x3－1 2 -3x44 －1 -5x5－1 1 －1 6 10/3x1 x2-Z若 p3 由原来的 ??1 / 3 ? ?1 / 10? ??? ? ，最优解将如何改变？ ?7 / 3? ?1 / 3 ? ? 4 ? 1??1 / 10? ?1 / 15 ? ?? ??? ? ?? ? ? ? ? ? 1 1 ??1 / 3 ? ? 7 / 30?解：计算 p3 ' ? B ?1 p3 ' ? ? ?? ? ?2 3?? ? 7 / 30? ? 1 / 6 ? 0 ∴继续迭代 ? ? ?Cj CB 2 3 2 1 XB b 1 2 -8 3/7 60/7 -66/7 2 3 1 0 0?1 / 15 ?x11 0 0 1 0 0x20 1 0 -2/7 -30/7 -5/7x31/15 [7/30] 1/6 0 1 0x44 －1 -5 30/7 -30/7 -30/7x5－1 1 －1 －9/7 -30/7 －12/741x1 x2-Z15 60/7 15 60/7x1 x3-Z X*=(3/7,0,60/7,0,0) 例4 (仍以例2为例)Z*=66/7 已知线性规划问题及其最优单纯形表max z ? ? x1 ? x2 ? 4 x3 x 2 ? 2 x3 ? 9 ? x1 ? ? x ? x 2 ? x3 ? 2 ? 1 ? ? ? x1 ? x2 ? x3 ? 4 ? x1?3 ? 0 ?Cj CB －1 0 4 XB b 1/3 6 13/3 -17 －1 －1 4 0 0 0x11 0 0 0x2-1/3 2 2/3 -4x30 0 1 0x41/3 0 1/3 -1x50 1 0 0x6-2/3 1 1/3 -2x1 x5 x3-Z现增加一个新变量 x7，且 c7=3，p7=(3,1,-3)’，求新问题的最优解。?1解：由表知： B?1 / 3 0 ? 2 / 3 ? ? ? ?? 0 1 1 ? ?1 / 3 0 1 / 3 ? ? ??1 / 3 0 ? 2 / 3 ?? 3 ? ? 3 ? ? ?? ? ? ? 1 1 ??1 ? ? ? ? 2 ? ∴ p7 ' ? B p7 ? ? 0 ?1 / 3 0 1 / 3 ?? ? 3 ? ? 0 ? ? ?? ? ? ??1?3 ? ? ? ? 7 ? c7 ? C B B p 7 ? 3 ? (?1,0,4)? ? 2 ? ? 6 ? 0 ?0 ? ? ??1∴继续迭代 Cj CB －1 0 4 3 0 XB b 1/3 6 13/3 -17 1/9 56/9 －1 －1 4 0 0 0 3x11 0 0 0 1/3 2/3x2-1/3 2 2/3 -4 -1/9 16/9x30 0 1 0 0 0x41/3 0 1/3 -1 1/9 2/9x50 1 0 0 0 1x6-2/3 1 1/3 -2 -2/9 5/9x7[3] -2 0 6 1 042x1 x5 x3-Zx7 x5 4x3-Z13/3 -53/30 -22/3 -10/31 01/3 -5/3 Z*=53/30 01/3 -2/30 0∴X*=(0,0,13/3,0,56/9,0,1/9)’5．已知线性规划问题及其最优单纯形表 Cj CB －1 0 4 XB b 1/3 6 13/3 -17 －1 －1 4 0 0 0x11 0 0 0x2-1/3 2 2/3 -4x30 0 1 0x41/3 0 1/3 -1x50 1 0 0x6-2/3 1 1/3 -2x1 x5 x3-Z现增加新约束 ? 3x1 ? x2 ? 6 x3 ? 17，求新问题的最优解。 解：将原问题的最优解代入新增约束 ? 3 ?1 13 ? 0 ? 6 ? ? 25 ? 17 3 3不满足新增加的约束条件，因此引入松弛变量 x7 后，新增约束变为? 3x1 ? x2 ? 6x3 ? x7 ? 17 ，加进最优表得：Cj CB －1 0 4 0 －1 0 4 0 XB b 1/3 6 13/3 17 -17 1/3 6 13/3 -8 -17 －1 －1 4 0 0 0 0x11 0 0 -3 0 1 0 0 0 0x2-1/3 2 2/3 1 -4 -1/3 2 2/3 -4 -4 1x30 0 1 6 0 0 0 1 6 0x41/3 0 1/3 0 -1 1/3 0 1/3 -1 -1 1x50 1 0 0 0 0 1 0 0 0x6-2/3 1 1/3 0 -2 -2/3 1 1/3 [-4] -2 1/2x7[3] -2 0 1 0 0 0 0 1 0x1 x5 x3 x7-Zx1 x5 x3 x7-Z? j / arj '－1 0 4 0x1 x5 x3 x6-Z5/3 4 11/3 2 -131 0 0 0 01/3 1 1/3 1 -2 Z*=130 0 1 0 01/2 -1/4 1/4 1/4 -1/20 1 0 0 00 0 0 1 0-1/6 1/4 1/12 -1/4 -1/2∴ X*=(5/3,0,11/3,0,4,2,0)’ 5、线性规划问题43 max Z ? 2 x1 ? x 2 ? x3 ? x1 ? x 2 ? x3 ? 6 ? ? ? x1 ? 2 x 2 ? 4 ? x ,x ,x ? 0 ? 1 2 3用单纯形法求解得最终单纯形表如下表所示。x1 x1 X5cj-zj 6 10 1 0 0x21 3 -3x31 1 -1x41 1 -2x50 1 0试说明分别发生如下变化时，新的最优解是什么？ （1）目标函数变为 max Z ? 2 x1 ? 3x2 ? x3 ； （2）约束条件右端项由 ? ? 变为 ? ? ； （3）增添一个新的约束 ? x1 ? 2 x3 ? 2 。 解： （1） cj→ CB 2 0 2 3 xB b 6 10 8/3 10/3 2 3 1 0 0?6 ? ?4??3? ?4?x11 0 0 1 0 0x21 [3] 1 0 1 0*x31 1 -1 2/3 1/3 -4/3x41 1 -2 2/3 1/3 -7/3x50 1 0 -1/3 1/3 -1/3θ 2 0 2 0ix1 x5cj-zjx1 X2cj-zj因为所有的检验数均小于等于零。故最优解为 X ? (8 / 3,10/ 3,0,0,0) （2）因为 B?1?1 0? ?? 3? ?? 3? ?1 ?? ?, ?b ? ? 0 ? 。所以 B b ? ?? 3? ?1 1? ? ? ? ?2 b 3 7 -1 1 0 0cj→ CB 2 0 xBx11 0 0x21 3 -3*x31 1 -1x41 1 -2x50 1 0θix1 x5cj-zj因为所有的检验数均小于等于零，故最优解为 X ? (3,0,0,0,7) （3）由于 ? x1 ? 2 x3 ? ?6 ? 2 ? 0 ? ?6 ? 2 ， 所以原问题的最优解不是该问题的最优解。 在约束条件 ? x1 ? 2 x3 ? 2 左右两端同时乘以“-1” ，并加上松弛变量 x6 ，44 得到 x1 ? 2 x3 ? x6 ? ?2 cj→ CB 2 0 0 2 0 0 2 0 1 xB b 6 10 -2 6 10 -8 10/3 22/3 8/3 2 -1 1 0 0 0 θix11 0 1 0 1 0 0 0 1 0 0 0x21 3 0 -3 1 3 -1 -3 2/3 8/3 1/3 -8/3x31 1 -2 -1 1 1 [-3] -1 0 0 1 0x41 1 0 -2 1 1 -1 -2 2/3 2/3 1/3 -5/3x50 1 0 0 0 1 0 0 0 1 0 0x60 0 1 0 0 0 1 0 1/3 1/3 -1/3 -1/3x1 x5 x6cj-zjx1 x5 x6cj-zjx1 x5 x3cj-zj因为所有的检验数均小于等于零，故最优解为 X * ? (10 / 3,0,8 / 3,0,22 / 3)45 第三章 运输问题（15） 1、安排一个使总运费最低的运输计划，并求出最低运费。 运 产 地 产 价 1 2 3 需求量 销地 A1 6 10 12 30 A2 11 7 8 40 A3 10 6 8 50 A4 9 14 11 30 产量 50 70 30要求：先用最小元素法求出一个初始方案，再用闭回路法，求检验数。如果不是最优，改进 为最优。 解：1）先用最小费用法（最小元素法）求此问题的初始基本可行解： 费 销 A 1 6 1 30 10 2 × 12 3 × dj 30 40 20 50 × 10 150 30 150 8 20 8 50 11 30 × 7 × 6 × 14 70 20 11 A 2 10 A 3 9 50 A 4 Si用 产 地 地∴初始方案：Z=6×30+9×20+7×20+6×50+8×20+11×10=1070 2）用闭回路法，求检验数： 费 用 产 地 6 1 30 10 2 × 12 3 × 20 × 10 －4 8 20 8 50 －1 11 30 × －3 7 × 6 × 14 20 －4 70 11 －5 10 －5 9 50 销 地 A 1 A 2 A 3 A 4 Si46 150 dj 30 40 50 30 150 从上表可看出，所有检验数 ? j ≤0，已得最优解。 ∴该指派问题的最优方案就是上面用“最小费用法”求得的初始方案 求出最小费用 Z=6×30+9×20+7×20+6×50+8×20+11×10=1070 2、给定下列运输问题： （表中数据为产地 Ai 到销地 Bj 的单位运费） B1 B2 B3 B4 siA1 A2 A31 8 92 7 103 6 5 114 910 80 15dj82212181）用最小费用法求初始运输方案，并写出相应的总运费； 分） （5 2）用 1）得到的基本可行解，继续迭代求该问题的最优解。 （10 分） 解：用“表上作业法”求解。 1）先用最小费用法（最小元素法）求此问题的初始基本可行解： 费 用 产 地 1 A1 8 8 A2 × 9 A3 × dj ∴初始方案： 8 22 20 12 10 18 60 × 60 10 × 11 2 9 30 18 7 2 6 × 5 20 × 2 3 4 10 销 地 B1 B2 B3 B4 Si2 8B3 A3 B420B2B118 1047 3A2 Z=1×8+2×2+6×2+5×18+10×20+11×10=424 A12BB2 2）①用闭回路法，求检验数： 费 用 产 地 1 A1 8 8 A2 × 9 A3 × dj 8 ∵ ? 34 =1＞0，其余 ? j ≤0 ∴选 x34 作为入基变量迭代调整。 ②用表上闭回路法进行迭代调整： 费 用 产 地 1 A1 8 8 A2 × 9 A3 × dj 8 22 20 12 × 18 60 调整后，从上表可看出，所有检验数 ? j ≤0，已得最优解。 ∴最优方案为： 10 60 0 10 × 11 12 －1 9 30 8 －3 7 2 －1 6 × 5 20 × 2 3 －1 4 －3 10 销 地 B1 B2 B3 B4 Si 22 20 12 10 18 60 × 60 0 10 × 11 2 9 18 1 30 －4 7 2 －2 6 × 5 20 × 2 3 0 4 －2 10 销 地 B1 B2 B3 B4 Si8B148A1 12B3 A320B2A2最小运费 Z=1×8+2×2+6×12+5×8+10×20+9×10=414 8 B4 3、下列是将产品从三个产地运往四个销地的运输费用表。 运 产 产 地 1 2 3 需求量 9 7 6 40 12 3 5 40 9 7 9 60 销 价 地10B4产量A1A2A3A46 7 11 2050 60 50要求：?用最小费用法建立运输计划的初始方案； ?用位势法做最优解检验； ?求最优解和最优方案的运费。 解：?先用最小费用法（最小元素法）求此问题的初始基本可行解： 费 用 产 地 9 1 × 7 2 × 6 3 40 dj 40 40 × 60 10 20 160 ∴最小费用法初始方案： × 160 5 40 9 20 11 50 × 3 × 7 30 7 60 20 12 9 6 50 销 地 A 1 A 2 A 3 A 4 Si40 30A3 220A2 3 A340A11201049A4A3 初始方案总运费 Z=9×30+6×20+3×40+7×20+6×40+9×10=980 ?按题目要求用位势法，作最优解检验： 费 用 产 地 9 1 × 7 2 × 6 3 40 Vj 9 所有检验数如下： 12 × 16 10 × 5 40 0 9 20 11 × 0 －7 7 3 × 7 30 7 20 －2 －9 0 12 0 9 6 0 销 地 A1A2A3A4ui18? 11 ＝ c11 ? u1 ? v1 ＝9－0－9＝0 ，? 12 ＝ c12 ? u1 ? v2 ＝12－0－12＝0 ，? 21 ＝ c21 ? u2 ? v1 ＝7－（－9）－9＝7 ， ? 24 ＝ c24 ? u2 ? v4 ＝7－（－9）－18＝－2 ，? 32 ＝ c32 ? u3 ? v2 ＝5－（－7）－12＝0 ， ? 34 ＝ c34 ? u3 ? v4 ＝11－（－7）－18＝0。 ?再用闭回路法求最优解和最优方案的运费，先检验： 费 用 产 地 9 1 × 2 7 －3 3 × 7 30 7 20 －3 60 －3 12 －7 9 6 50 销 地 A 1 A 2 A 3 A 4 Si50 × 6 3 40 Dj 40 ∵所有检验数 ? ij ≤0， 40 540 0 × 60 920 11 10 20× －5 50 × 160 160∴该方案已是最优方案，不需要再调整。30A3 240A2 340A1120A420A310A3最优方案的运费 Z=9×30+6×20+3×40+7×20+6×40+9×10=980 4、给定下列运输问题： （表中数据为产地 Ai 到销地 Bj 的单位运费） B1 B2 B3 B4 siA1 A2 A320 5 18 711 9 48 10 2 165 10 15dj3312121）用最小费用法求初始运输方案，并写出相应的总运费； 分） （4 2）用 1）得到的基本可行解，继续迭代求该问题的最优解。 （10 分） 解：用“表上作业法”求解。 1）先用最小费用法（最小元素法）求此问题的初始基本可行解： 费 用 产 地 20 A1 3 A2 5 9 2 10 × 2 × 10 11 8 6 5 销 地 B1 B2 B3 B4 Si51 × 18 A3 × Dj ∴初始方案： 3 3 7× 4 1 12× 11015 12 12 30 2 301 3B1B21210A2 Z=20×3+11×2+2×10+7×1+4×12+1×2=159 A1 2）①用闭回路法，求检验数：费 用 产 地 20 A1 3 5 A2 × 18 A3 × Dj 3 ∵ ? 21 =12＞0，其余 ? j ≤0 ∴选 x21 作为入基变量迭代调整。 ②用表上闭回路法进行迭代调整： 费 用 产 地 20 A1 2 3 11 销 地 B1 B2 3 1 －2 7 × 12 9 2 －1 11 销 地B4A32B3 B4B3 B4Si2B1B2B280 ×6－1 5 ×10－5 ×2 10 10 1 154 12 122 30 12 30B3B4Si812 ×611 5 ×52 5 A2 1 18 A3 × Dj 3 －149－13 ×10－15 ×2 10 9 1 157－12 × 34 12 123 30 12 30再选 x13 作为入基变量迭代调整。 费 用 产 地 20 A1 × 5 A2 3 18 A3 × Dj 3 3 × 12 10 12 30 调整后，从上表可看出，所有检验数 ? j ≤0，已得最优解。 ∴最优方案为： 3 10 B3 最小运费 Z=11×3+8×2+5×3+2×7+4×10+1×5=123 B1 5、某百货公司去外地采购 A、B、C、D 四种规格的服装，数量分别为 A——1500 套，B—— 3 B2 A2 A3 2000 套，C——3000 套，D——3500 套，有三个城市可供应上述规格服装，供应数量为Ⅰ— —2500 套，Ⅱ——2500 套，Ⅲ——5000 套。由于这些城市的服装质量、运价情况不一，运 7 5 A1 B4 B4 输成本（元/套）也不一样，详见下表： 5 30 －14 7 × 0 4 × 1 15 7 9 3 －1 10 2 －5 2 10 × －12 11 8 6 －1 5 销 地 B1 B2 B3 B4 Si2B3A Ⅰ Ⅱ Ⅲ 10 8 9B 5 2 3C 6 7 4D 7 6 8请帮助该公司确定一个成本最小的采购方案。(用伏格尔法)（12 分） 解：用伏格尔法确定初始调运方案为： A B C D 供53 Ⅰ Ⅱ Ⅲ 销 00 00 350000 （5 分）? 11=2； ? 12=-2； ? 13=3； ? 21=1； ? 23=5； ? 32=-1 有 ? ij ? 0,所以需要调整为：A Ⅰ Ⅱ Ⅲ 销 00 500 00 3500 B C D<br />
供 00? 11=1； ? 12=2； ? 13=2； ? 21=0； ? 23=4； ? 34=1 因为 ? ij ? 0， 所以为最优方案。Min Z=0*2+0*9+500*3+00 由于 ? 21=0 所以在此闭回路上有无穷多最优解。 6 已知某运输问题如下（单位：百元/吨）（12 分） ： 单位运价 产地 A1 A2 A3 需求量（吨） 3 5 9 16 7 8 4 12 2 10 5 17 18 12 15 销地 B1 B2 B3 供应量（吨）（5 分） （2 分）求： 、使总运费最小的调运方案和最小运费。(用伏格尔法)（10 分） （1） （2） 、该问题是否有多个最优调运方案？若没有，说明为什么；若有，请再求出一 个最优调运方案来。 分） （2 解：1）用伏格尔法确定初始调运方案为： B1 A1 A2 A3 需 1 12 3 16 12 12 17 （4 分） B1 A1 A2 A3 需 16 4 12 12 12 3 17 （4 分） （2 分） B2 B3 14 供 18 12 15 B2 B3 17 供 18 12 15? 12=9； ? 22=0； ? 23=6； ? 33=-3 有 ? ij ? 0,所以需要调整为：? 12=6； ? 22=5； ? 23=6； ? 31=3 因为 ? ij ? 0， 所以为最优方案。Min Z=3*4+2*14+12*5+12*4+3*5=163 为唯一最优解。54 7 已知运输问题的产销平衡表与单位运价表如下表所示。 销地 A B C 销量 甲 3 7 2 60 乙 2 5 5 40 丙 7 2 4 20 丁 6 3 5 15 产量 50 60 25试用表上作业法求出最优解。 解：本问题是产销平衡问题。根据最小元素法，初始可行解为： 甲 A B C 销量 10 25 25 60 甲 A B C 销量 Vj 10（0） 25(0) 25(0) 60 3 40 乙 40（0） （-1） （4） 40 2 20 丙 （9） 20(0) （7） 20 -2 15 丁 （7） 15(0) （7） 15 -1 乙 40 20 15 丙 丁 产量 50 60 25 135 产量 50 60 25 135 Ui 0 4 -1采用位势法，可得检验数如下表所示（为了区别，检验数用“括号里的数字”表示）因为（B，乙）的检验数为-1，所以该初始可行解非最优解。 从空格（B，乙）出发的闭回路为（B，乙）——（B，甲）——（A，甲）——（A，乙） ——（B，乙） 。 该闭回路的偶数顶点位于格（B，甲）和（A，乙） ，由于 min(25,40) ? 25 所以可得如下可行解 甲 A B C 销量 Vj 35（0） (1) 25(0) 60 3 乙 15（0） 25（0） （4） 40 2 丙 （8） 20(0) （6） 20 -1 丁 （6） 15(0) （6） 15 0 产量 50 60 25 135 Ui 0 3 -1由于所有空格的检验数均大于零。所以得到唯一最优解。55 ? 匈牙利法（15） 1、求解指派问题，并求出最小费用。 Min z =?? ci ?1 j ?144ij ijx? ? ? （cij）4×4= ? ? ? ?10 17 24 178 12 22 24 18 16 21 2522 ? ? 20 ? 19 ? ? 19? ?解：用 “匈牙利法”求解。 效率矩阵表示为：? ? ? ? ? ? ?10 17 24 178 12 22 24 18 16 21 2522 ? ? ?? 20 ? ? 19 ? ? ?? 19? ? ??2 0 4 行约简 0 5 7 8 2 0 0 4 814 ? ? 3? 3? ? 2? ?列约简 标号? 2 ? ? (0) ?8 ? ? 0* ?(0) 5 2 44 7 (0) 8?0 ? ?1 至此已得最优解： ? 0 ? ?0 ?12 ? ? 1? 1? ? (0) ? ? 1 0 0 00 0 1 00? ? 0? 0? ? 1? ?∴最小费用 W=8+17+16+19=60 2、有甲、乙、丙、丁四个人，要分别指派他们完成 A、B、C、D 四项不同的工作，每人做各 项工作所消耗的时间如下表所示： A 甲 乙 丙 丁 2 15 13 4 B 10 4 14 15 C 9 14 16 13 D 7 8 11 9问：应该如何指派，才能使总的消耗时间为最少？ 解：用 “匈牙利法”求解。 效率矩阵表示为：? ? ? ? ? ? ?2 15 13 410 4 14 159 14 16 137 ? ? 8 ? 11? ? 9 ? ?? ? ? ? ? ? ?0 8 7 行约简 11 0 10 2 3 5 0 11 95? ? 4? 0? ? 5? ?√列约简 标号√ 56 ? (0) ? ? 11 ? 2 ? ? 0* ?8 (0) 3 12 ? ? ? ? ? ? ? 0* 13 4 ( 0)2 5 (0) 4 6 ( 0) 3 100 1 0 05 ? ? (0) ?? 4 ? ? 11 0* ? ? 2 ?? 5 ? ? 0* ?? ( 0) 5 0* 21 0 0 0 0? ? 0? 1? ? 0? ?8 (0) 3 12 3? ? 4 ? ? ( 0) ? 3 ? ?2 5 (0) 45 ? ? 4 ? 0* ? ? 5 ? ??0 ? ?0 至此已得最优解： ? 0 ? ?1 ?∴使总消耗时间为最少的分配任务方案为：甲→C，乙→B，丙→D，丁→A。此时总消耗时间 W=9+4+11+4=28 3、一个公司经理要分派 4 个推销员去 4 个地区推销某种商品。4 个推销员各有不同的经验 和能力，因而他们在每一地区能获得的利润不同，其估计值如下表所示： D1 甲 乙 丙 丁 35 28 35 24 D2 27 34 24 32 D3 28 29 32 25 D4 37 40 33 28问：公司经理应怎样分派 4 个推销员才使总利润最大？ 解：用求极大值的“匈牙利法”求解。 效率矩阵表示为：? 35 ? ? 28 ? 35 ? ? 24 ?27 34 24 3228 29 32 2537? ? 5 13 ? ? M－Cij 40? ?12 6 33 ? ? 5 16 ? ? M=40 ? ?16 28? ? 812 11 8 153? ? 0? 7? ? 12? ?行约简57 ? 2 ? ? 12 ? 0 ? ? 8 ?10 6 11 09 11 3 70? ? 列约简6 ? ?12 0? ? 2 ? ? (0)标号11 ? 4?? 8 (0) ???2106 8 0* 4(0) ? ? 0* ? ? ，未 2 ? 所画（）0 元素少于 n（n＝4） 4? ?得到最优解，需要继续变换矩阵（求能覆盖所有 0 元素的最少数直线集合） ：?2 ? ?12 ? ? (0) ?8 ?10 6 11 (0)6 8 0* 4√) ? √ (0? 0 ?√ ? 2? 4? ?*未被直线覆盖的最小元素为 cij=2,在未被直线覆盖处减去 2，在直线交叉处加上 2。? ? ? ? ? ? ?0 10 0 88 4 11 04 6 0 4 1 0 0 0 0 0 0 1? (0) 0 ? ? 标号 ? 10 0? ? ? * 4? ? 0 ? 6? ? 8 ??0 0 1 0 0? ? 1? 0? ? 0? ?8 4 11 （0）4 6 (0) 40* ? ? （0） ? ? 4 ? 6 ? ?? ? ? ∴得最优解： ? ? ? ?∴使总利润为最大的分配任务方案为：甲→D1，乙→D4，丙→D3，丁→D2。此时总利润 W=35+40+32+32=139 4、求解系数矩阵 C 的指派问题?12 7 9 7 9 ? ?8 9 6 6 6? ? ? C ? ? 7 17 12 14 12? ? ? ?15 14 6 6 10? ? 4 10 7 10 6 ? ? ?解：先作等价变换如下?7 ?6 ?7 ?6 ?40 ?12 7 9 7 9 ? ? 5 0* 2 ?8 9 6 6 6? ?2 3 0 0* ? ? ? 7 ? 7 17 12 14 12? ? ?0 * 10 5 ? ? ? 8 0* 0 ?15 14 6 6 10? ?9 ? 4 10 7 10 6 ? ?0 6 3 6 ? ? ? ?2? 0? ? 5? ? ? 4? 2? ? ?58 ?7 ?4 ? ?0 ? ?11 ?0 ?0 2 0 2? 3 0 0 0? ? 8 3 5 3? ? 8 0 0 4? 4 1 4 0? ?现在已可看出，最优指派为 ? ?? 1 2 3 4 5? ? ? ? 2 4 1 3 5?5、用匈牙利法求解下列的指派问题，已知效率矩阵如下： 。?3 8 ?8 7 ? ?6 4 ? ?8 4 ?9 10 ?2 10 2 2 2 6 9 7 3 93? 7? ? 5? ? 5? 10? ? 3 ? ?0 7 ? ?5 ? ? 5 ? ? ?3 ? ? 5 ? ?5 10? ?2 ? ? 4 0 7 0? 3 0 6 4? √ ? 0 0 4 2? ? 0 0 0 2? 2 0 2 3? √ ? ?0 ?3 ? → ?3 ? ?5 ?0 ? 4 2 7 0? 1 0 4 2? ? 0 2 4 2? ? 0 2 0 2? 0 0 0 1? ??3 8 ?8 7 ? 解： ?6 4 ? ?8 4 ?9 10 ? ?0 ?0 ? X * ? ?0 ? ?0 ?1 ?2 10 2 2 2 6 9 7 3 9√ 由于得到了 5 个独立零元素，故可得最优指派方案。本题的最优解为：0 0 0 1? 0 1 0 0? ? 1 0 0 0? 。这样可使目标函数最小，为 3+2+4+3+9=21。 ? 0 0 1 0? 0 0 0 0? ?6、某5×5指派问题效率矩阵如下，求解该指派问题。?12 7 9 7 9 ? ?8 9 6 6 6? ? ? C ? ? 7 17 12 14 9 ? ? ? ?15 14 6 6 10? ? 4 10 7 10 9 ? ? ?解：对 C 进行行、列变换，减去各行各列最小元素59 ?12 7 9 7 9 ? ?5 0 2 0 ?8 9 6 6 6? ?2 3 0 0 ? ? ? C ? ? 7 17 12 14 9 ?行变换?0 10 5 7 ? ? ? ?15 14 6 6 10? ?9 8 0 0 ? 4 10 7 10 9 ? ?0 6 3 6 ? ? ?用圈 0 法对 C1 进行行列检验，得到2? ?5 0 2 0 ? ?2 3 0 0 0? ? 2?列变换?0 10 5 7 ? ? 4? ?9 8 0 0 ?0 6 3 6 5? ? ?2? 0? ? 2?＝C1 ? 4? 5? ??5 0 2 0 ?2 3 0 0 ? ?0 10 5 7 ? ?9 8 0 0 ?0 6 3 6 ?2? 0? ? 2?＝C 2 ? 4? 5? ?(1) 对 C2 中所有不含圈 0 元素的行打√，如第 5 行 (2) 对打√的行中，所有 0 元素所在列打√，如第 1 列 (3) 对所有打√列中圈 0 元素所在行打√，如第 3 行 (4) 重复上述(2),(3)步，直到不能进一步打√为止 (5) 对未打√的每一行划一直线，如 1，2，4 行，对已打√的列划一纵线， 如第 1 列，即得到覆盖当前 0 元素的最少直线数。见 C3?5 0 2 0 ?2 3 0 0 ? C 2 ? ?0 10 5 7 ? ?9 8 0 0 ?0 6 3 6 ?2? ?5 0 2 0 ? ?2 3 0 0 0? ? 2? ? C 3 ? ?0 10 5 7 ? ? 4? ?9 8 0 0 ?0 6 3 6 5? ? ?2? 0? ? 2? ? 4? 5? ?第 5 步：对矩阵 C3 作进一步变换，增加 0 元素 在未被直线覆盖过的元素中找出最小元素， 将打√行的各元素减去这个最小元素， 将打√列 的各元素加上这个最小元素(以避免打√行中出现负元素)，这样就增加了 0 元素的个数。 对 C3 进行变换，最小元素为 2，对打√的第 3，5 行各元素都减去 2，对打√的第 1 列各元 素都加上 2，得到矩阵 C4?7 ?4 ? C4 ? ? 0 ? ?11 ?0 ?0 2 0 2? ?7 ? ?4 3 0 0 0? ? 8 3 5 0? C 4 ? ? 0 ? ? 8 0 0 4? ?11 ?0 4 1 4 3? ? ?0 2 0 2? 3 0 0 0? ? 8 3 5 0? ? C 5 ? 8 0 0 4? 4 1 4 3? ?令决策变量矩阵中 x12=x24=x35=x43=x51=1,其余 xij=060 ? 隐枚举法 1、用隐枚举法求解规模0－1规划问题min z ? 3 x1 ? 7 x2 ? x3 ? x4 x4 ? 1 ?2 x1 ? 2 x2 ? x3 ? ?x ? x2 ? 6 x3 ? 4 x4 ? 8 ? 1 ? x4 ? 5 ?5 x1 ? 3 x2 ? ? ? ? x1? 4 ? 0或1 ?解： 由于本题过滤条件不好选，所以开始不设过滤条件 点 (x2,x1,x4,x3) (0,0,0,0) (0,0,0,1) (0,0,1,0) (0,0,1,1) (0,1,0,0) (0,1,0,1) (0,1,1,0) (0,1,1,1) (1,0,0,0) (1,0,0,1) (1,0,1,0) (1,0,1,1) (1,1,0,0) (1,1,0,1) (1,1,1,0) (1,1,1,1) 此例的最优解 X*=(0,1,1,1)’ × × × × × × × × minz=3 过滤条件 约束 (4) (1) × √ × × √ √ √ √ × × × √ √ 3 × (2) (3) Z值61 ? 割平面法 1、用割平面法解整数规划问题 将原整数规划问题称为原问题 A0， 不考虑整数条件的伴随规划称为问题 B0， 用单纯形法求解max z ? x1 ? x2 ?? x1 ? x2 ? 1 ? ? 3 x1 ? x2 ? 4 ? x , x ? 0且为整数 ? 1 2B0，得最优单纯形表 Cj CB 1 1 XB 1 1 0 0b7/4 3/4 -5/2x10 1 0x21 0 0x33/4 -1/4 -1/2x41/4 1/4 -1/2x2 x1 -Z问：原问题的解是多少？ 解：x1=3/4,x2=7/4 均不满足整数条件，选 x1，则含 x1 的约束方程为：x1 ?1 1 3 x3 ? x 4 ? 4 4 47/4=1+3/4将所选的约束方程中非基变量的系数及常数项进行拆分处理。 -5/2=-3+1/2 1/4=0+1/4 求割平面方程?Cj CB 1 1 0 XB3 1 3 x3 ? x 4 ? ? 4 4 41 1 0 0 0将割平面方程加到伴随规划的最终单纯形表中，用对偶单纯形法继续求解b7/4 3/4 -3/4 -5/2 1 1 1 -2x10 1 0 0 0 1 0 0x21 0 0 0 1 0 0 0x33/4 -1/4 [-3/4] -1/2 2/3 0 0 1 0x41/4 1/4 -1/4 -1/2 2 0 1/3 1/3 -1/3x50 0 1 0 1 -1/3 -4/3 -2/3x2 x1 x5 -Z x2 x1 x3 -ZZ*=21 1 0 X*=(1,1)’ 2、62 ?图和网络分析1、求下图中从 v1 到 v3 短路。v11v2 3 37 3 v6 2 2v326v4解：令 P(v1)=0，k=v1；T(vj)=+∞。 当 k=v1 时， T(v2)=P(v1)+1=1, T(v4=P(v1)+2=2, λ (v2)=v1; λ (v4=v1;v5所有 T 标号中 T(v2)最小，故 P(v2)=T(v2)=1， k=v2。 当 k=v2 时， T(v3)=P(v2)+7=8, T(v6)=P(v2)+3=4, λ (v3)=v2; λ (v6)=v2;T(v4)&P(v2)+3，故 v4 的 T 标号不变; 所有 T 标号中 T(v4)最小，故 P(v4)=T(v4)=2， k=v4。 当 k=v4 时， T(v6)==P(v3)+2，可不变; T(v5)=P(v3)+2=4, λ (v5)=v4; 所有 T 标号中 T(v6)最小，故 P(v6)=T(v6)=4，k=v6。 当 k=v6 时， T(v3)=P(v6)+3=7, λ (v3)=v6 所有 T 标号中 T(v5)最小，故 P(v5)=T(v5)=4，k=v5。 当 k=v5 时， T(v3)&P(v5)+6，故 v3 的 T 标号不变;63 所有 T 标号中 T(v3)最小，故 P(v3)=T(v3)=7。 所有的点都具有 P 标号，算法结束。从 v1 至 v3 的最短路为：v1→v2→v6→v3。2、电信公司要在 15 个城市之间铺设光缆，这些城市的位置及相互之间的铺设光缆的费用如下图所示。试求出一个连接在 15 个城市的铺设方案，使得总费用最 小。1 2 v2 4 v3 1 v6 2 v4 4 v5 2 4 v9 1 3 v7 2 v8 3 2 v12 6 5 v10 1 v11 4 5 3 3v1v13 1 v14 3 v15解：费用最小的铺设方案对应于光缆图的最小支撑树。求得最小支撑树为：1 2 v2 2 v5 2 v3 1 v6 v9 1 v4 3 v7 2 v8 3 2 v12 v10 1 v11 4 3v1v13 1 v14 3 v15最小费用为 28。3、求出从 vs 到 vt 的最大流，弧旁的数字是弧的容量。64 v12 3 1 5 2vs43vtv2v3解：以零流作为初始流，计算增广链并调整流量，过程如下：v1 (vs, 2)(2, 0) (0, ∞) (3, 0) (v1, 2) (1, 0) (3, 0) (4, 0) (2, 0) (5, 0)vsvtv2(vs, 4)v3v1 (v2, 3)(2, 2) (0, ∞) (3, 2) (v3, 2) (1, 0) (3, 0) (4, 0) (2, 0) (5, 0)vsvtv2(vs, 4)v3(v2, 2)65 v1 (v2, 2)(2, 2) (0, ∞) (3, 2)vs(3, 0) (4, 2) (2, 2)(1, 0)vt(5, 2)(v1, 1)v2(vs, 2)v3v1 (v2, 1)(2, 2) (0, ∞) (3, 3)vs(3, 1) (4, 3) (2, 2)(1, 0)vt(5, 2)v2(vs, 1)v3可知， 最大流量为 5， 最小截集为 (V1,V1) ? {(v1, vt ), (v2 , v3 )} ， 其中 V1 ? {vs , v1, v2} ，V1 ? {v3, vt } 。66 ? 决策分析 1、设三个备选投资方案的决策益损如下表： 销售状态 收益值(万元) 可行方案 A B C销路好销路一般销路差销路极差50 70 3025 30 15–25 –40 –5–45 –80 –10问题： (1)试用最大最大决策标准选择方案； (2)当α 取何值时，用现实主义决策标准和用最大最大决策标准选择的方案相同? 解： 2、已知某企业有下表所示的情况，请选择所用策略。表中效益值的单位为万元。 效益 自然状态 Sj 及 值 aij 概率 P(Sj) 策略 di d1（按甲方案生产） d2（按乙方案生产） d3（按丙方案生产） S1（产品销路好） P(S1)=0.3 S（产品销路一般） S（产品销路差） 2 3 P(S2)=0.5 P(S3)=0.240 35 3026 30 2415 20 20请用决策树来进行决策。 解：来说明单级决策树的画法和最优期望益损值准则的决策方法。步骤如下： 销路好 P(S1)=0.3 d1=28 销路一般 P(S2)=0.5 △26 △40销路差 P(S3)=0.2 △15 29.5\\d2=29.5 销路好 P(S1)=0.3 △35 决 选乙方案 销路一般 P(S2)=0.5 △30 策 销路差 P(S3)=0.2 △20 \\ d3=25 销路好 P(S1)=0.3 △30 销路一般 P(S2)=0.5 △24 销路差 P(S3)=0.2 △20 3、公司有 50000 元多余资金，如用于某项投资，估计成功率为 96%，成功时可获利 12%，若 失败，将丧失全部资金。如果把资金存入银行，则可稳得利息 6%。为获取更多情报，该公 司可求助于咨询服务，咨询费用为 500 元，但咨询意见只能提供参考。该咨询公司过去类似 的 200 例咨询意见实施结果如下表所示。 实施结果 咨询意见 可以投资 不宜投资 合计 154 次 2次 192 次 2次 6次 8次 156 次 44 次 200 次 投资成功 投资失败 合计问：该公司是否值得求助于咨询服务？应如何安排多余资金？ 解：根据以上分析，可以完成决策树的全部内容。见下图：67 P（E1）= 0.96 3760 投资 3760 不咨询存银行 P（E1∣T1）= 0.987 5272P（E2∣T1）= 0.0136000 咨询 5272 投资 - T1 存银行 P（E1∣T2）= 0.0 投资 P（E2∣T2）= 0.136 -50000 T2 存银行 3000 图 9-3 6000 P（E2）= 0.04 -50000-500本题的结论是，该公司应求助于咨询服务。如果咨询意见是可以投资，则将资金用于投资； 如果咨询意见是不宜投资，则将资金存入银行。 4、某化工厂原料车间，欲对旧工艺进行革新，采用新工艺。取得新工艺有两种策略：一是 自行研究，成功的可能性为 0.6；二是买专利，估计谈判成功的可能性为 0.8。无论研究成 功或谈判成功，生产规模都考虑两种方案：一是产量不变；二是增加产量。如果研究或谈判 都失败，则仍采用旧工艺进行生产，并保持原产品产量不变。根据市场预测，估计今后几年 内这种产品价格下跌的概率是 0.1，价格中等的概率是 0.5，价格上升的概率 0.4。经过分 析计算，得到各个策略在不同价格的情况下的收益值，收益情况如下表： （单位:百万元） 收益 价格下跌 价格中等 价格上升 旧工艺 -100 0 100 买专利成功 产量不变 -200 50 150 增加产量 -300 50 250 自行研究成功 产量不变 -200 0 200 增加产量 -300 -150 600试用决策树方法寻找最优策略。68 解： （1）绘制决策树如图所示。价格下跌 0.160价格中等 0.5-200 0 200 -300 -150 600135 4 成功P=0.6产量不变8价格上升 0.4 价格下跌 0.1932 自行研究 失败P=0.4产量增加135 9价格中等 0.5 价格上升 0.4价格下跌 0.130 法5价格中等 0.5 价格上升 0.4-100 0 100价格下跌 0.1 价格中等 0.5 价格上升 0.41 65 购买专利 成功P=0.8 产量不变 95 6 产量增加 95 11价格下跌 0.1-200 50 150 -300 50 25030 10价格下跌 0.1 价格中等 0.5 价格上升 0.4823失败P=0.2-100 0 10030 7价格中等 0.5 价格上升 0.4（2）计算各结点的收益期望值 结点○：E8=（－200）×0.1＋0×0.5＋200×0.4＝60； 8 结点○：E9=（－300）×0.1＋(－150)×0.5＋600×0.4＝135； 9 结点10：E10=（－200）×0.1＋50×0.5＋150×0.4＝65； ○ 结点11：E11=（－300）×0.1＋50×0.5＋250×0.4＝95； ○ 结点⑤⑦：E5=E7=（－100）×0.1＋0×0.5＋100×0.4＝30。 因为结点④是决策点,通过以上计算可知，结点⑨的收益期望值大于结点⑧的收益期望值， 所以决策点○的收益期望值取 135，即采用增加产量的方案。同样，对决策点⑥，由于结点 4 11收益期望值大于结点⑩的收益期望值，所以决策点⑥的收益期望值取 95，即采用增加产 ○ 量的方案。 继续计算结点②③的收益期望值：结点②：E2=135×0.6＋30×0.4＝93， 结 点③：E3=95×0.8＋30×0.2＝8269 （3）选择策略通过比较后进行“剪枝” ，结点②的收益期望值大，所以应选取自行研究的方 案。 5、某企业要投产一件新产品，投资方案有甲、乙两种。同时，市场预测发现，产品甲销路 好的可能性为 0.6, 净收益总值为 100 万；销路差的可能性为 0.4, 净收益总值为-60 万。产 品乙销路好的可能性为 0.4, 净收益总值为 200 万； 销路差的可能性为 0.6, 净收益总值为-80 万。要求：用决策树法进行决策。 解： 1、绘制决策树100 36 甲 2 -60 不好 0.4 1 32 乙 3 好 0.4 好 0.6200不好 0.62、计算各节点的期望值 节点 2：100×0.6+-60×0.4=36（万元） 节点 3：200×0.4-80×0.6=32（万元） 决策点 1 的期望损益值为：max（36，32）=36（万元） 3、剪枝。 可以判断，选择产品甲。-802、某企业需要在是否引进新产品之间进行决策，即开始时有引进新产品和不引进新产品两 种方案。若引进新产品，又面临其它企业的竞争。估计有其他企业参与竞争的概率为 0.8， 没有企业参与竞争的概率为 0.2。在无竞争的情况下，企业有给产品确定高价、中价和低价 三种方案，其相应的收益分别为 500、300 和 100 万元。在有竞争情况下，企业也有给产品 确定高价、 中价和低价三种方案， 但此时各方案的收益大小要受到竞争企业的产品定价的影 响，有关数据如表。试用决策树法进行决策。 竞争企业定价方案 本企业 定价方 案 高价 中价 概率 收益（万元） 概率 收益（万元） 高价 0.3 150 0.1 250 中价 0.5 0 0.6 100 低价 0.2 -200 0.3 -5070 低价概率 收益（万元）0.1 1000.2 500.7 -100解：首先画出决策树如图 2 决策计算从右向左进行，具体如下： 节点 5：0.3×150+0.5×0+0.2×（－200）=5（万元） 节点 6：0.1×250+0.6×100+0.3×（－50）=70（万元） 节点 7：0.1×100+0.2×50+0.7×（－100）=－50（万元）对手高价(0.3)5 本企业高价 5150 0 -200对手中价(0.5) 对手低价(0.2) 对手高价(0.1)有竞争 （0.8）70 本企业中价370 6250 100 -50对手中价(0.6) 对手低价（0.3） 对手高价(0.1)引进产品156 2-50 本企业低价 7100 50 -100对手中价(0.2) 对手低价(0.7)156 1无竞争 （0.2） 500本企业高价 本企业中价500 3004本企业低价100不引进产品0节点 3（二级决策点） ：max{5，70，－50}=70（万元） 。即在有竞争的情况下，本企业给产 品制定中价为最优方案，期望收益为 70 万元。 节点 4（二级决策点） ：max{500，300，100}=500（万元） 。即在无竞争的情况下，本企 业给产品制定高价为最优方案，收益为 500 万元。 节点 2：0.8×70+0.2×500=156（万元） 节点 1（一级决策点） ：max{156，0}=156（万元） ，即企业应采取引进新产品的方案， 该方案相应的期望收益为 156 万元。71<br />
更多相关文档
</div>
<div id=]()
