2014考研西安建筑科技大学-《816运筹学》习题解析

书第１讲第一章　线性 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 （一）线性规划例１　试述线性规划问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 数学模型的组成部分及特征，判别下列数学模型是否是线性规划模型（模型中ａ，ｂ，ｃ为常数，θ为可取某一常数值的参变量，ｘ，ｙ为变量）．Ａ．ｍａｘＺ＝３ｘ１＋５ｘ２＋７ｘ３ｓｔｘ１＋２ｘ２－６ｘ３≥８５ｘ１＋ｘ２＋８ｘ３≤２０３ｘ１＋４ｘ２＝１２ｘ１，ｘ３≥０　　Ｂ．ｍｉｎＺ＝∏ｎｊ＝１ｃｊｘｊｓ．ｔ∑ｎｊ＝１ａｉｊｘｊ≤ｂｉ，（ｉ＝１，２，…，ｍ）ｘｊ≥０，（ｊ＝１，２，…，ｎ{）Ｃ．ｍｉｎＺ＝∑ｍｉ＝１ａ２ｉｘｉ＋∑ｎｊ＝１ｂ２ｊｙｊｓ．ｔｘｉ＋ｙｊ≤ｃ２ｉｊ（ｉ＝１，２，…，ｍ；ｊ＝１，２，…，ｎ{）Ｄ．ｍａｘＺ（θ）＝∑ｎｊ＝１ｃｊｘｊｓ．ｔ∑ｎｊ＝１ａｉｊｘｊ≤ｂｉ＋ａｉθｘｊ≥０，（ｊ＝１，２，…，ｎ{）例２　将下列线性规划问题化成 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 型：Ａ．ｍｉｎＺ＝－３ｘ１＋４ｘ２－２ｘ３＋５ｘ４ｓ．ｔ４ｘ１－ｘ２＋２ｘ３－ｘ４＝－２ｘ１＋ｘ２＋３ｘ３－ｘ４≤１４－２ｘ１＋３ｘ２－ｘ３＋２ｘ４≥２ｘ１，ｘ２，ｘ３≥０，ｘ４无约束Ｂ．ｍｉｎＺ＝２ｘ１－ｘ２＋２ｘ３ｓ．ｔ－ｘ１＋ｘ２＋ｘ３＝４－ｘ１＋ｘ２－ｘ３≤６ｘ１≤０，ｘ２≥０，ｘ３{无约束单纯形法例１　用单纯形法求解线性规划ｍｉｎＺ＝－３ｘ１＋２ｘ２－４ｘ３ｓｔｘ１＋ｘ２＋ｘ３≤１８２ｘ２＋ｘ３≤８２ｘ１－ｘ２＋２ｘ３≤２４ｘ１，ｘ２，ｘ３≥０ｍｉｎＺ＝－３ｘ１＋２ｘ２－４ｘ３ｓｔｘ１＋ｘ２＋ｘ３＝１８２ｘ２＋ｘ３＋ｘ５＝８２ｘ１－ｘ２＋２ｘ３＋ｘ６＝２４ｘ１，ｘ２，ｘ３≥０—１—西安建筑科技大学《８１６运筹学》习题解析ｃｊ－３２－４０００ＣＢＸＢｘ１ｘ２ｘ３ｘ４ｘ５ｘ６ｂθ０ｘ４１１１１００１８１８０ｘ５０２１０１０８８０ｘ６２－１２００１２４１２λ－３２－４００００ｃｊ－３２－４０００ＣＢＸＢｘ１ｘ２ｘ３ｘ４ｘ５ｘ６ｂθ０ｘ４０３／２０１０－１／２６－４ｘ３０２１０１０８－３ｘ１１－５／２００－１１／２４λ０５／２００１３／２－４４例２　用单纯形法求解线性规划ｍａｘＺ＝１０ｘ１＋１５ｘ２＋１２ｘ３ｓｔ５ｘ１＋３ｘ２＋ｘ３≤９－５ｘ１＋６ｘ２＋１５ｘ３≤１５２ｘ１＋ｘ２＋ｘ３≥５ｘ１，ｘ２，ｘ３≥０ｍａｘＺ＝１０ｘ１＋１５ｘ２＋１２ｘ３－Ｍｘ７ｓｔ５ｘ１＋３ｘ２＋ｘ３＋ｘ４＝９－５ｘ１＋６ｘ２＋１５ｘ３＋ｘ５＝１５２ｘ１＋ｘ２＋ｘ３－ｘ６＋ｘ７＝５ｘｊ≥０，ｊ＝１，…，７ｃｊ１０１５１２０００－ＭＣＢＸＢｘ１ｘ２ｘ３ｘ４ｘ５ｘ６ｘ７ｂθ０ｘ４５３１１０００９９／５０ｘ５－５６１５０１００１５－－Ｍｘ７２１１００－１１５５／２λ２Ｍ＋１０Ｍ＋１５Ｍ＋１２００－Ｍ０ｃｊ１０１５１２０００－ＭＣＢＸＢｘ１ｘ２ｘ３ｘ４ｘ５ｘ６ｘ７ｂθ１０ｘ１１３９／８００３／１６－１／８０００３／２１２ｘ３０９／１６１１／１６１／１６００３／２－Ｍｘ７０－４３／８００－７／１６－３／８０－１１１／２λ０－４３／８０Ｍ＋２７／８０－３５／８０Ｍ－２１／８－３／８０Ｍ－５／８－Ｍ０—２—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５第２讲第一章　线性规划（二）线性规划应用举例１．经营规划２．配料选取３．任务分配４．投资预算５．任务指派６．合理利用线材（补充）例１　用长８米的角钢切割钢窗用料．每付钢窗含长１．５米的２根，１．４５米的２根，１．３米的６根，０．３５米的１２根．若需钢窗用料１００付，问最少需切割８米长的角钢多少根？例２　某厂计划在下月内生产４种产品Ｂ１，Ｂ２，Ｂ３，Ｂ４。每种产品都可用三条流水线作业Ａ１，Ａ２，Ａ３中任何一条加工出来。每条流水线Ａｉ加工每件产品Ｂｊ所需的工时数（ｉ＝１，２，３；ｊ＝１，２，３）、每条流水线在下月内可供利用的工时数及各种产品的需求量均列于下 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 中。又Ａ１，Ａ２，Ａ３三条流水线的生产成本分别为每小时７，８，９元。问应如何安排各条流水线在下月的生产任务，才能使总的生产成本最少？每件产品　　　产品　耗时数　　　　　　流水线　　　　　　Ｂ１Ｂ２Ｂ３Ｂ４可用工时数Ａ１２１３２１５００Ａ２３２４４１８００Ａ３１２１２２０００需求量／件２００１５０２５０３００例３　某公司下月需要Ｂ１，Ｂ２，Ｂ３，Ｂ４四种型号的钢板分别为１０００吨、１２００吨、１５００吨和２０００吨。他准备向生产这些钢板的Ａ１，Ａ２，Ａ３三家工厂订货。该公司掌握了这三家工厂生产各种钢板的效率（吨／小时）及下月的生产能力（小时），如下表１所示，而他们生产各种型号钢板的成本也如下表２所示。该公司当然希望能以最少的代价得到自己所需的各种钢板。问他应该向各钢厂订购每种钢板各多少吨？—３—西安建筑科技大学《８１６运筹学》习题解析表１生产效率　　钢板型号（吨／小时）　　　　　　钢厂名称　　　　　Ｂ１Ｂ２Ｂ３Ｂ４下月生产能力／小时Ａ１１２１０１５８２００Ａ２９１１１３２３０Ａ３１４１２７２１０钢板需求量／吨１０００１２００１５００２０００表２单位成本　　钢板型号　（百元／吨）　　　　　　钢厂名称　　　　　　５１Ｂ２Ｂ３Ｂ４Ａ１３６５４５０４８Ａ２４０５２Ａ３６２４８５３例４　某造纸厂接到一份定货单， 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 供应三种规格的卷纸：０．７米宽的２００米，０．８米宽的３００米，０．９米宽的４００米。该厂只生产１．５米宽和２米宽两种标准宽度的卷纸，现需将他们按定单要求的大小切开。对标准纸的长度没有限制，因为可以按实际需要，把有限长度的卷纸连接起来，达到所需要的长度。现问应如何进行切割，才能既满足用户要求，又使切割损失最小？例５　中华家电公司最近生产了一种新型洗衣机。为了推销这种新产品，该公司销售部决定利用多种广告宣传形式来使顾客了解新洗衣机的优点。经过调查研究，销售部经理提出了五种可供选择的宣传方式。销售部门并收集了许多数据，如每项广告的费用，每种宣传方式在一个月内可利用的最高次数以及每种广告宣传方式每进行一次所期望得到的效果等。这种期望效果以一种特定的相对价值来度量，是根据长期的经验判断出来的。上述有关数据见下表。广告方式每次广告费用／元每月可用的最高次数期望的宣传效果／单位电视台Ａ／（白天，１分钟）５００１６５０电视台Ｂ／（晚上，３０秒种）１０００１０８０每日晨报／（半版）１００２４３０星期日报（半版）３００４４０广播电台／（１分钟）８０２５１５公司现拨了２万元给销售部作为第一个月的广告预算费，同时提出，月内至少得有８个电视商业节目，１５条报纸广告，且整个电视广告费不得超过１．２万元，电台广播至少隔日有一次。现问该公司—４—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５销售部应当采取怎样的广告宣传计划，才能取得最好的效果？例６　长城家电公司最近研制了一种新型电视机，准备在三种类型的商场即一家航空商场、一家铁路商场和一家水上商场进行销售。由于三家商场的类型不同，他们的批发价和推销费都不同，因而产品的利润也不同。此外，公司根据过去的经验，对这三家商场所需的广告费和推销人员的工时作了估计。这些数据列于下表中。由于这种电视机的性能良好，各家商场都纷纷争购；但公司的生产能力有限，每月只能生产１０００台，故公司规定了如下的销售方针：铁路商场至少经销３００台，水上商场至少经销２００台，航空商场至少经销１００台，至多２００台。公司计划在一个月内的广告预算费为８０００元，推销人员最高可用工时数为２５００小时，同时，公司只根据经销数进行生产，即生产台数＝销售台数。经销商场每销售一台的利润／元每销售一台的广告费／元每销售一台需推销工时／小时航空商场５０１２２铁路商场８０７３水上商场７０８４公司现在要确定下月的市场对策，具体说来，就是要对下面三个问题作出决策：１）应为各家商场生产多少台电视机？２）用于各家商场的广告费是多少？３）为各家商场各安排多少推销人员的工时？—５—西安建筑科技大学《８１６运筹学》习题解析第３讲第一章　线性规划（三）第二章　对偶规划（

一）线性规划应用举例例７　某厂现有资金１００万元，准备投资若干项目，据了解在今后五年内，已有下列四个项目欢迎该厂投资：１）第一年年初投资，到次年末可收回本金的７０％，第三年末除收回全部本金外，还可获利２５％；第三年初投资，第四年末可收回本利１１６％。项目投资额至少１０万元。２）第二年初投资，第四年末可收回本金８０％，第五年末，除收回全部本金外，还可获利润３５％；第四年年初投资，第五年末可收回本利１１８％。项目投资额至少２０万元，至多４０万元。３）第三年年初投资，第五年末可收回本利１３５％，但投资额不得超过３０万元，也不得少于１５万元。４）每年年初在银行进行定期储蓄，当年末取出，年利５％。该厂决定对上述四个投资项目都进行投资，但每年度对各项目的投资金额，完全可由该厂根据自己的情况确定。现问该厂应如何安排每年给各个项目的投资额，以便到第五年末能拥有最多的资金？例８　设有４名运动员Ａ１，Ａ２，Ａ３，Ａ４组成的一个游泳队准备参加４×１００米的混合接力赛（由爬泳、蝶泳、仰泳、蛙泳各１００米组成），这４名运动员的１００米爬泳、蝶泳、仰泳、蛙泳成绩如下表所示。现问应指派每个人各游什么姿势，才能使总的成绩最好？爬泳Ｂ１蝶泳Ｂ２仰泳Ｂ３蛙泳Ｂ４Ａ１５７″３６３″６４″７７″Ａ２５６″６０″２６２″６３″５Ａ３５６″４６１″６３″７１″Ａ４５８″６４″６５″６８″７对偶规划问题：怎样写出原问题的对偶问题？针对对称形式的对偶问题“上、下”交换，“左、右”换位，不等式变号，“极大”变“极小”针对非对称形式的对偶问题—６—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５把一个等式约束写成两个不等式约束，再根据对称形式的对偶关系定义写出；按照原始－对偶表直接写出；对称形式下对偶问题的一般形式项目原问题对偶问题ＡｂＣ目标函数约束条件决策变量约束系数矩阵约束条件的右端项向量目标函数中的价格系数向量ｍａｘＺ＝ＣＸＡＸ≤ｂＸ≥０其约束系数矩阵的转置目标函数中的价格系数向量约束条件的右端项向量ｍｉｎＷ＝Ｙ′ｂＡ′Ｙ≥Ｃ′Ｙ≥０例１　写出下面线性规划的对偶问题（对称形式）ｍａｘＺ＝２ｘ１＋ｘ２ｓ．ｔ．３ｘ１＋４ｘ２≤１５５ｘ１＋２ｘ２≤１０ｘ１，ｘ２≥{０ｍｉｎＷ＝１５ｙ１＋１０ｙ２ｓ．ｔ．３ｙ１＋５ｙ２≥２４ｙ１＋２ｙ２≥１ｙ１，ｙ２≥{０原始—对偶表原问题（或对偶问题）对偶问题（或原问题）目标函数ｍａｘＺ目标函数ｍｉｎＷ约束条件数：ｍ个第ｉ个约束条件类型为“≤”第ｉ个约束条件类型为“≥”第ｉ个约束条件类型为“＝”对偶变量数：ｍ个第ｉ个变量≥０第ｉ个变量≤０第ｉ个变量是自由变量决策变量数：ｎ个第ｊ个变量≥０第ｊ个变量≤０第ｊ个变量是自由变量约束条件数：ｎ第ｉ个约束条件类型为“≥”第ｉ个约束条件类型为“≤”第ｉ个约束条件类型为“＝”课堂练习：写出下面线性规划的对偶规划：ｍｉｎＺ＝４ｘ１＋２ｘ２＋３ｘ３ｓ．ｔ．４ｘ１＋５ｘ２－６ｘ３＝７８ｘ１－９ｘ２＋１０ｘ３≥１１１２ｘ１＋１３ｘ２≤１４ｘ１≤０，ｘ２符号不限，ｘ３≥０下面的答案哪一个是正确的？为什麽？—７—西安建筑科技大学《８１６运筹学》习题解析ｍａｘＷ＝７ｙ１＋１１ｙ２＋１４ｙ３ｓ．ｔ．４ｙ１＋８ｙ２＋１２ｙ３≥４５ｙ１－９ｙ２＋１３ｙ３＝２－６ｙ１＋１０ｙ２≤３ｙ１符号不限，ｙ２≥０，ｙ３≤０ｍａｘＷ＝７ｙ１＋１１ｙ２＋１４ｙ３ｓ．ｔ．４ｙ１＋８ｙ２＋１２ｙ３≤４５ｙ１－９ｙ２＋１３ｙ３＝２－６ｙ１＋１０ｙ２≥３ｙ１符号不限，ｙ２≤０，ｙ３≥０（原问题是极小化问题，因此应从原始对偶表的右边往左边查！）例　列出线性规划问题的对偶问题ｍｉｎｆ（ｘ）＝２ｘ１＋３ｘ２－５ｘ３＋ｘ４ｓ·ｔ４ｘ１＋ｘ２－３ｘ３＋２ｘ４≥５３ｘ１－２ｘ２＋７ｘ４≤４－２ｘ１＋３ｘ２＋４ｘ３＋ｘ４＝６ｘ１≤０，ｘ２，ｘ３≥０，ｘ４自由ｍａｘｇ（ｙ）＝１０ｙ１－５ｙ２－８ｙ３ｓ·ｔｙ１－ｙ２＋３ｙ３≥２－ｙ１＋４ｙ２＋２ｙ３≤４ｙ１－３ｙ２－５ｙ３＝－３ｙ１≥０，ｙ２自由，ｙ３≤０ｍａｘＺ＝－ｘ１＋２ｘ２＋３ｘ３ｓｔ２ｘ１＋ｘ２－３ｘ３＝１８３ｘ１－ｘ２＋２ｘ３≥－４ｘ１－ｘ２＋３ｘ３≤４ｘ１≤０，ｘ２≥０，ｘ３自由ｍｉｎＺ＝１８ｙ１－４ｙ２＋４ｙ３ｓｔ２ｙ１＋３ｙ２＋ｙ３≤－１ｙ１－ｙ２－ｙ３≥２－３ｙ１＋２ｙ２＋３ｙ３＝３ｙ１自由，ｙ２≥０，ｙ３≤０对偶问题的基本性质对称性———原始问题与对偶问题是两个互为对偶的问题。弱对偶性———两个问题的可行解对应的目标函数值互为上下界。最优性———两个问题最优解的目标函数值必相等。强对偶性———两个问题都有可行解时则两个问题必都有最优解。互补松弛性———两个问题最优解中，一个问题中某个变量取值非零，则该变量在对偶问题中对应的某个约束条件必为紧约束（严格等式）；反之，如果约束条件为松约束（严格不等式），则其对应的对偶变量一定取值为零。因此，该定理又称为松紧定理。原问题与对偶问题解的对应关系表问题与解的状态对偶问题有最优解无界解无可行解原问题有最优解一定不可能不可能无界解不可能不可能可能无可行解不可能可能可能—８—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５第４讲第二章　对偶规划（二）对偶单纯形法例　用对偶单纯形法求解ＬＰ：ｍｉｎＷ＝３ｙ１＋９ｙ２ｓ．ｔ．ｙ１＋ｙ２≥２ｙ１＋４ｙ２≥３ｙ１＋７ｙ２≥３ｙ１≥０，ｙ２≥０　其化为标准型为　ｍａｘＺ＝－３ｙ１－９ｙ２ｓ．ｔ．ｙ１＋ｙ２－ｙ３＝２ｙ１＋４ｙ２－ｙ４＝３ｙ１＋７ｙ２－ｙ５＝３ｙ１，…，ｙ５≥０灵敏度分析例　考虑以下线性规划问题ｍａｘＺ＝ｘ１－ｘ２＋２ｘ３ｓｔｘ１＋ｘ２＋３ｘ３≤１５２ｘ１－ｘ２＋ｘ３≤２－ｘ１＋ｘ２＋ｘ３≤４ｘ１，ｘ２，ｘ３≥０应用单纯形得到部分最优单纯形表如下：ＣＢＸＢｘ１ｘ２ｘ３ｘ４ｘ５ｘ６ｂｘ４１－１－２ｘ３０１／２１／２ｘ２０－１／２１／２－Ｚ（１）完成以上单纯形表。（２）当右端项ｂ变为（１２，４，２）Ｔ时，最优解如何变化？（３）当ｘ１的价值系数变为４时，最优解如何变化？（４）当ｘ１的价值系数为何值，原最优解仍是最优的，且为无穷多个最优解，并求出这些解。（５）若增加一个变量ｘ′，其价值系数为－２，相应的技术系数为（２，－３，３）Ｔ，最优解将如何变化？—９—西安建筑科技大学《８１６运筹学》习题解析（６）若增加一个约束３ｘ１＋２ｘ２＋ｘ３≤２，最优解如何变化？定义　如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题．一般形式：ｍｉｎ()ｆＸ　　　（１）其中ｓ．ｔ．ｇｉ()Ｘ≥０　ｉ＝１，２，…，ｍ；ｈｊ()Ｘ＝０　ｊ＝１，２，…，{ｌ．是定义在Ｅｎ上的实值函数。其它情况：求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式．证明定理：设ｆ（ｘ）为定义在凸集Ｒ上的凸函数，则对任一实数β，Ｓβ＝｛ｘ｜ｘ∈Ｒ，ｆ（ｘ）≤β｝集合是凸集。定理：有限个凸函数的非负线性组合仍为凸集。凹凸函数的定义及其证明方法例　证明()ｆＸ＝Ｘ１２＋Ｘ２２为凸函数。凸规划的一些性质：ｍｉｎｘ∈Ｒｆ（ｘ）Ｒ＝｛ｘ｜ｇｉ（ｘ）≥０，ｊ＝１，２，……，ｌ｝其中ｆ（ｘ）为凸函数，ｇｉ（ｘ）为凹函数，这样的非线性规划是凸规划。性质：１．凸规划的可行域为凸集，其局部最优解即为全局最优解，最优解的集合形成一个凸集。２．当凸规划的函数ｆ（ｘ）为严格凸时，其最优解必定唯一（假定最优解存在的情况下）。３．线性函数即可是凸函数，又可以凹函数。例　分析下面非线性规划是否是凸规划ｍｉｎｆ（ｘ）＝ｘ２１＋ｘ２２－４ｘ１＋４ｇ１（ｘ）＝ｘ１－ｘ２＋４≥０ｇ２（ｘ）＝－ｘ２１＋ｘ２＋２≥０ｘ１，ｘ２≥{０—０１—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５第５讲第三章　运输规划表上

作业法表上作业法的步骤：（１）→找出初始基可行解表上给出ｍ＋ｎ－１个数字格（２）→求各非基变量的检验数计算表中空格检验数（３）→判断是否最优解判断方法相同（４）确定换入变量和换出变量找出新的基可行解→。表上调整（闭回路调整）（５）重复（２）、（３）直至求出最优解→。（运输问题必有最优解）例　某部门有３个同类型的工厂（产地），生产的产品由４个销售点出售，各工厂的生产量、各销售点的销售量（假定单位为ｔ）以及各工厂到销售点的单位运价（元／ｔ）示于下表中，问如何调运才能使总运费最小？　　　销地产地　　　Ｂ１Ｂ２Ｂ３Ｂ４产量Ａ１ｘ１１４ｘ１２１２ｘ１３４ｘ１４１１１６Ａ２ｘ２１２ｘ２２１０ｘ２３３ｘ２４９１０Ａ３ｘ３１８ｘ３２５ｘ３３１１ｘ３４６２２销　量８１４１２１４４８具有上下界的运输问题例　求解下列运输问题。—１１—西安建筑科技大学《８１６运筹学》习题解析　　　　销地产地　　　　Ｂ１Ｂ２Ｂ３Ｂ４收量Ａ１１６１３２２１７５０Ａ２１４１３１９１５６０Ａ３１９２０２３—５０最低需求３０７００１０最高需求５０７０３０不限请大家关注：有转运的运输问题（关键是怎样求解）运输问题的应用例　某厂按合同规定须于当年每个季度末分别提供１０，１５，２５，２０台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表３－２９所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用０．１５万元。要求在完成合同的情况下，作出使该厂全年生产（包括储存、维护）费用最小的决策。季度生产能力（台）单位成本（元）Ⅰ２５１０．８Ⅱ３５１１．１Ⅲ３０１１．０Ⅳ１０１１．３例　腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产４５０台，广州分厂每月生产６００台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如下图，单位百元。应该如何调运可使总运输费用最低？（图见视频）—２１—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５第６讲第四章　整数规划割平面法１．令ｘｉ是相应线性规划最优解中为分数值的一个基变量，由单纯形表的最终表得到：ｘｉ＋∑ａｉｋｘｋ＝ｂｉ，其中ｉ∈Ｉ（Ｉ指构成基变量号码的集合），ｋ∈Ｋ（Ｋ指构成非基变量号码的集合）。２．将ｂｉ和ａｉｋ都分解成整数部分Ｎ与非负真分数ｆ之和，即ｂｉ＝Ｎｉ＋ｆｉ，其中０＜ｆｉ＜１ａｉｋ＝Ｎｉｋ＋ｆｉｋ，其中０≤ｆｉ＜１而Ｎ表示不超过ｂ的最大整数。代入Ⅰ中的方程得：ｘｉ＋∑Ｎｉｋｘｋ－Ｎｉ＝ｆｉ－∑ｆｉｋｘｋ３．提出变量为整数的条件（包括非负的条件），则由上式由左边看必须是整数，但由右边看，因为０＜ｆｉ＜１，所以不能为正，即ｆｉ－∑ｆｉｋｘｋ≤０即可得到一个切割方程。例　求解下列整数规划问题ｍａｘｆ（ｘ）＝ｘ１＋ｘ２ｓｔ－ｘ１＋ｘ２≤１３ｘ１＋ｘ２≤４ｘ１，ｘ２≥０，ｘ１，ｘ２{整数隐枚举法例　求解下列整数规划问题ｍａｘｆ（ｘ）＝３ｘ１－２ｘ２＋５ｘ３ｓｔｘ１＋２ｘ２!ｘ３≤２　　①ｘ１＋４ｘ２＋ｘ３≤４　　②ｘ１＋ｘ２≤３　　③４ｘ１＋ｘ３≤６　　④ｘ１，ｘ２，ｘ３＝０或１指派问题例　求下表所示效率矩阵的指派问题的最小解。—３１—西安建筑科技大学《８１６运筹学》习题解析　　　　任务人员　　　　ＡＢＣＤＥ甲１２７９７９乙８９６６６丙７１７１２１４９丁１５１４６６１０戊４１０７１０９非标准形式的指派问题在实际应用中，常会遇到各种非标准形式的制派问题。一般的处理方法是先将其转化为标准形式，然后再用匈牙利法求解。１．最大化指派问题设最大化指派问题系数矩阵Ｃ＝（ｃｉｊ）其中最大元素为ｍ。令矩阵Ｂ＝（ｂｉｊ）＝（ｍ－ｃｉｊ），则以Ｂ为系数矩阵的最小化指派问题和以Ｃ为系数矩阵的最大化指派问题有相同最优解。２．人数和事数不等的指派问题若人少事多，则添加一些虚拟的“人”，其费用系数取０，若人多事少，则添加一些虚拟的“事”，其费用系数取０。３．一个人可做几件事的指派问题若某个人可以做几件事，则将该人化作几个“人”来接受指派。这几个“人”做同一件事的费用系数当然都一样。４．某事一定不能由某人做的指派问题若某事一定不能由某人做，则可将相应的费用系数取为足够大的数Ｍ。怎样产生最少的直线１）找出矩阵Ｃ中含有０元素最少的一行（或一列），从该行（或该列）中圈一个０，再通过这个０作一竖线（或横线）划去此０所在之列（或行）；２）对Ｃ中余下的各行各列重复步骤１），已圈数的行和列不再圈数；如果划线数不等于ｎ，则应在那些未划直线的地方产生一些０元素：在所有未划去的数中找出最小的，设为ｄ；将所有未划去的各数都减去ｄ，而位于已画的两直线交点处的数则加上ｄ如果有ｍ个互相排斥的约束条件（≤型）：ａｉ１ｘ１＋ａｉ２ｘ２＋…＋ａｉｎｘｎ≤ｂｉ，ｉ＝１，２，…，ｍ为了保证这ｍ个约束条件只有一个起作用，我们引入ｍ个０－１变量ｙｉ（ｉ＝１，２，…，ｍ）和一个充分大的常数Ｍ，而下面这一组ｍ＋１个约束条件：ａｉ１ｘ１＋ａｉ２ｘ２＋…＋ａｉｎｘｎ≤ｂｉ＋ｙｉＭ，ｉ＝１，２，…，ｍ　　（４－１）ｙ１＋ｙ２＋…＋ｙｍ＝ｍ－１　　（４－２）—４１—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５就合于上述的要求。这是因为，由于（４－２）式，ｍ个ｙｉ中只有一个能取０值，设ｙｉ＝０，代入（４－１）式，就只有ｉ＝ｉ的约束条件起作用，而别的式子都是多余的。例　某厂拟用集装箱托运甲乙两种货物，运货有车运和船运两种方式。每箱的体积、重量、可获利润以及托运所受限制如下所示。问两种货物各托运多少箱，可使获得利润为最大？　　货运方式货物　　　　车运船运体积（ｍ３／箱）体积（１００ｋｇ／箱）体积（ｍ３／箱）体积（１００ｋｇ／箱）利润（１００元／箱）甲５２７２４２乙４５３５３３托运限制２４ｍ３１３００ｋｇ３５ｍ３１３００ｋｇ—５１—西安建筑科技大学《８１６运筹学》习题解析第７讲第六章　动态规划（一）动态规划建立动态规划的模型的十步曲：１．正确、明确地划分阶段ｋ，ｋ＝１，２，３，…，ｎ。依据决策过程的时间和空间的顺序关系。２．正确选择并确定状态变量Ｓｋ及状态集合Ｓｋ。状态变量的确定有时并非显而易见，要确定它，通常可对问题作如下分析而帮助确定状态变量ａ．什么关系将各个阶段联系在一起？ｂ．为了决定今后的最优（子）策略，需要事件现状的哪些信息？３．确定决策变量ｕｋ及决策集合Ｄｋ（Ｓｋ）。４．写出状态转移方程Ｓｋ＋１＝Ｔｋ（Ｓｋ，ｕｋ）。５．定义阶段指标值（函数）ｖｋ（Ｓｋ，ｕｋ）。６．定义第ｋ至ｎ阶段（后部子过程）的最优指标（目标）函数ｆｋ（Ｓｋ）。７．作出动态规划结构图：８．建立动态规划基本方程：（逆序递推方程）ｆｋ（Ｓｋ）＝ｏｐｔ［ｖｋ（Ｓｋ，ｕｋ）＋ｆｋ＋１（Ｓｋ＋１）］，ｋ＝ｎ－１，…，２，１ｕｋ∈Ｄｋ（Ｓｋ）或ｋ＝ｎ，ｎ－１，…，{１ｆｎ（Ｓｎ）＝ｏｐｔ［ｖｎ（Ｓｎ，ｕｎ）］ｕｎ∈Ｄｎ（Ｓｎ{）或ｆｎ＋１（Ｓｎ＋１）＝!（Ｓｎ＋１）———边界条件（!为已知函数）９．逆序递推求解动态规划基本方程。求出最优决策序列Ｕ：ｕｎ，ｕｎ－１，…，ｕ２，ｕ１１０．顺序确定最优策略。ｐ１ｎ＝｛ｕ１，ｕ２，…，ｕｎ｝逆推解法例　用逆推法求解下面问题。ｍａｘＺ＝ｘ１ｘ２２ｘ３ｘ１＋ｘ２＋ｘ３＝ｃｘ１，ｘ２，ｘ３≥０—６１—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５动态规划应用举例例　某工厂的１００台机器，拟分四个周期使用，在每一周期有两种生产任务。据经验，把机器ｘ１台投入第一种生产任务，则在生产周期中将有１／３ｘ１台机器作废；余下的机器全部投入第二种生产任务，则有１／１０台机器作废，如果于第一种生产任务每台机器可收益１０单位，于第二种生产任务每台机器可收益７单位。问怎样分配机器，使总的收益最大？例　给定一个线路网络，要从Ａ向Ｆ铺设一条输

油管，各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短？（图见视频）—７１—西安建筑科技大学《８１６运筹学》习题解析第８讲第六章　动态规划（二）动态规划应用举例例１　某工厂根据国家的需要其交货任务如下表：月份１２３４５６货物量（百件）１２５３２１表中数字为月底的交货量。该厂的生产能力为每月４００件，该厂仓库的存货量为３００件。已知每百件货物的生产费用为１万元。在进行生产的月份，工厂要支出经常费用４０００元，仓库保管费为每百件货物每月１０００元。假定开始时及六月底交货后无存货。试问应在每个月个生产多少件物品，才能既满足交货任务又使总费用最小？例２　某台新设备的年效益及年均维修费、更新净费用如表所示。试确定今后５年内的更新策略，使总收益最大。（"＝１）单位：万元　　　　役龄项目　　　　０１２３４５效益ｒｋ（ｔ）５４．５４３．７５３２．５维修费ｕｋ（ｔ）０．５１１．５２２．５３更新费ｃｋ（ｔ）０．５１．５２．２２．５３３．５例３　某部门欲在五周内采购一批原料，事先可估计出未来五周的每周内可能有三种价格，而每种价格的概率变化如下表所示．该部门由于生产需要，必须在这五周内采购此种原料．问该部门究竟应该在哪周、按什么价格采购，使得采购费用最小？价格４５０４７０５００概率０．２５０．３５０．４０例４　设有５个工件需在机床Ａ，Ｂ上加工，加工顺序是先Ａ后Ｂ，每个工件所需加工时间（单位：小时）如下表所示，问如何安排加工顺序，使机床连续加工完所有工件的加工总时间最少？并求出总加工时间。—８１—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５加工时间　　机床工件号码　　　　　ＡＢ１３６２７２３４７４５３５７４例５　某厂有１０００台完好机器，每台机器全年在高负荷下运行可创利８千元，在低负荷下运行可创利５千元。机器在高、低负荷下运行一年的折损率分别为０．７，０．９。试拟订一个五年计划使总利润最大？—９１—西安建筑科技大学《８１６运筹学》习题解析第９讲第八章　存储论存储问题存储问题中牵涉到的费用的相关概念：１．存储费（Ｃ１）：存储费用是由于对库存物资进行保管而引起的费用，货物占用资金的利息；为了库存物资安全而向保险机构缴纳的保险金；部分库存物资损坏、变质、短缺而造成的损失；库存物资占用仓库面积而引起的一系列费用。２．建立费（Ｃ３＋ＫＱ）：对于外购物资来说主要是订货费，它包括二项：一项是订货费用（固定费用），它与订购次数有关，与订购数量无关。另一项是货物的成本费用，它与订购数量有关（可变费用）。对于自行生产的物资来说主要是生产费，这时仍需要支出两项费用。一项是装配费用（固定费用），另一项是与生产产品的数量有关的费用（可变费用）。３．缺货损失费（Ｃ２）：当某种物资存储量不足，不能满足需求时所造成的损失，如工厂停工待料，失去销售机会以及不能履行合同而缴纳的罚款等。在不允许缺货的情况下，缺货费为无穷大。四种模型，四种公式的记忆规律（确定的存储模型）最佳生产间隔期最佳生产批量最大存储量例１　某厂每月需甲产品１００件，每月生产率为５００件，每批装配费用为５元，每月每件产品存贮费用为４元，求ＥＯＱ及最低费用。例２　某商店经售甲商品成本单价５００元，年存储费用为成本的２０％，年需求量３６５件，需求速度为常数。甲商品的定购费为２０元，提前期为１０天，求ＥＯＱ及最低费用。例３　某厂按合同每年需提供Ｄ个产品，不许缺货。假设每一周期工厂需装配费Ｃ３元。存贮费每年每单位产品为Ｃ１元，问全年应分几批供货才能使装配费、存贮费两者之和最少。例４　某商店拟在新年期间出售一批日历画片，每售出一千张可赢利７００元。如果在新年期间不能售出，必须削价处理，作为画片出售。由于削价，一定可以售完，此时每千张赔损４００元。根据以往的经验，市场需求的概率见表需求０１２３４５概率０．０５０．１０．２５０．３５０．１５０．１每年只能订货一次，问应订购日历画片几千张才能使获利的期望值最大？例５　设某公司利用塑料作原料制成产品出售，已知每箱塑料购价为Ｋ＝８００元，订购费Ｃ３＝６０—０２—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５元，存贮费每箱Ｃ１＝４０元，缺货费每箱Ｃ２＝１０１５元，原有存贮量Ｉ＝１０箱。已知对原料需求的概率Ｐ（ｒ＝３０箱）＝０．２０，Ｐ（ｒ＝４０箱）＝０．２０，Ｐ（ｒ＝５０箱）＝０．４０，Ｐ（ｒ＝６０箱）＝０．２０。求该公司订购原料的最佳订购量．例　已知某产品的需求量服从正态分布，已知μ＝１５０，σ＝２５，又知每件产品的进价为８元，售价为１５元，存储费为３元，问该产品的订货量应为多少件才能使预期的利润最大？—１２—西安建筑科技大学《８１６运筹学》习题解析第１０讲第九章　排队论排队问题排队系统可用如下符号表示：［Ａ／Ｂ／Ｃ］：［ｄ／ｅ／ｆ］其中：Ａ———表示相继到达间隔时间的分布；Ｂ———表示服务时间的分布；Ｃ———表示服务台的个数；ｄ———表示系统容量；ｅ———表示顾客源数；ｆ———表示服务规则；ｓ———系统中并联服务台的数目；μ———平均到达率；１／μ———平均到达间隔。#———平均服务率；１／#———平均服务时间。$———服务强度，即每个服务台单位时间内的平均服务时间；一般有$%&'(ｓ#)；Ｎ———稳态系统任一时刻的状态（即系统中的顾客数）；Ｕ———顾客在稳态系统中的逗留时间；Ｑ———顾客在稳态系统中的等待时间。Ｐｎ＝Ｐ｛Ｎ＝ｎ｝：稳态系统任一时刻状态为ｎ的概率；特别当ｎ＝０时，Ｐｎ即Ｐ０，为稳态系统所有服务台全部空闲的概率。描述排队系统的四个指标变量Ｌ或Ｌｓ———平均队长，稳态系统任一时刻的顾客数的期望值Ｌｑ———平均等待队长或队列长，稳态系统任一时刻等待服务的顾客数期望值Ｗ或Ｗｓ———平均逗留时间，在任意时刻进入稳态系统的顾客逗留时间期望值Ｗｑ———平均等待时间，在任意时刻进入稳态系统的顾客等待时间期望值。这四项主要性能指标（又称主要工作指标）的值越小，说明系统排队越少，等待时间越少，因而系统性能越好。显然，它们是顾客与服务系统的管理者都很关注的排队问题解题步骤：对于泊松输入—负指数分布服务的排队系统的一般决策过程：１）根据已知条件绘制状态转移速度图（转入率＝转出率）。—２２—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５２）依据状态转移速度图写出各稳态概率之间的关系。３）求出Ｐ０及Ｐｎ。４）计算各项数量运行指标。５）用系统运行指标构造目标函数，对系统进行优化。排队问题例１　某修理店只有一个工人，每小时平均有四个顾客来修理东西。工人平均每６分钟修好一个，若顾客到达是最简单流，服务时间是负指数分布，求这个服务系统的运行指标。例２　某单位理发店内有５把椅子接待人们排队等待理发，当５把椅子都坐满顾客时，后来的顾客就不进入理发店而离开。顾客平均到达率为３（人／小时），理发时间平均１５（分钟／人），设顾客到达是最简单流，服务时间服从负指数分布，求：（１）顾客一到达就能理发的概率；（２）系统中顾客的期望值Ｌ和排队等待的顾客的期望Ｌｑ；（３）顾客在理发店内逗留的全部时间的期望值Ｗ；（４）在可能到来的顾客中因客满而不等待就离开的概率；例３　一个机修工负责３台机器的维修工作。设每台机器在修理之后平均可运行１５天，而平均修理一台机器的时间为２天，试求稳态下的各状态概率和各运行指标。例４　一个大型露天矿山，考虑建设矿石卸位数，是建一个好，还是两个？估计矿车按普阿松流到达，平均每小时到达１５辆，卸载时间服从负指数分布，平均卸载时间是３分钟，每辆卡车的售价是８万元，建设第二个卸位的投资是１４万元。例５　某售票处共有三个窗口，顾客到达为普阿松流，平均速率为０．９（人／分钟），服务（售票）时间服从负指数分布，平均服务率为０．４（人／分钟）。（１）试求整个售票处空闲的概率；（２）顾客必须等待的概率及运行指标。（这里假设顾客到达后排成一队，依次向空闲的窗口购票）—３２—西安建筑科技大学《８１６运筹

学》习题解析第１１讲第七章　目标规划目标规划目标规划的解（１）若多目标规划问题的解能使所有的目标都达到，就称该解为多目标规划的最优解；（２）若解只能满足部分目标，就称该解为多目标规划的次优解；（３）若找不到满足任何一个目标的解，就称该问题为无解。（４）前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现，就称该解为多目标规划的满意解（具有层次意义的解）例１　用单纯形法求解下列目标规划问题ｍｉｎＺ＝Ｐ１ｄ１－＋Ｐ２（ｄ２－＋ｄ２＋）＋Ｐ３（３ｄ３－＋５ｄ４－）５ｘ１＋４ｘ２＋ｄ１－－ｄ１＋＝２０ｓｔ４ｘ１＋３ｘ２＋ｄ２－－ｄ２＋＝２４ｘ１＋ｄ３－－ｄ３＋＝３－ｘ１＋ｘ２＋ｄ４－－ｄ４＋＝２ｘ１，ｘ２，ｄｋ－，ｄｋ＋≥０例２　某种牌号的酒系由三种等级的酒兑制而成。已知各种等级酒的每天供应量和单位成本如下：等级日供应量成本／ｋｇⅠ１５００６Ⅱ２０００４．５Ⅲ１０００３商标兑制配比要求单位售价（元）红Ⅲ少于１０％Ⅰ多于５０％５．５黄Ⅲ少于７０％Ⅰ多于２０％５．０蓝Ⅲ少于５０％Ⅰ多于１０％４．８—４２—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５该种牌号的酒有三种商标（红、黄、蓝），各种商标的混合比及售价如上表所示。为保持声誉，确定经营目标为Ｐ１：兑制要求必须严格满足；Ｐ２：企业获取尽可能多的利润；Ｐ３：红色商标酒每天产量不低于２０００单位。试对此问题建立目标规划模型。例３　某彩色电视机组装工厂，生产Ａ，Ｂ，Ｃ三种规格电视机。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为６，８和１０ｈ。生产线每月正常工作时间为２００ｈ；三种规格电视机销售后，每台可获利分别为５００元，６５０元和８００元。每月销售量预计为１２台、１０台、６台。该厂经营目标如下：ｐ１：利润指定为每月１．６×１０４元；ｐ２：充分利用生产能力；ｐ３：加班时间不超过２４ｈ；ｐ４：产量以预计销售量为标准；为确定生产划，试建立该问题的目标规划模型。例４　友谊农场有３万亩农田欲种植玉米，大豆和小麦三种农作物。各种作物每亩需施化肥分别为０．１２，０．２０，０．１５ｔ．预计秋后玉米每亩可收获５００ｋｇ，售价为０．２４元／ｋｇ，大豆每亩可收获２００ｋｇ，售价为１．２元／ｋｇ，小麦每亩可收获３００ｋｇ，售价为０．７０元／ｋｇ．农场年初规划时考虑如下几个方面：ｐ１：年终收益不低于３５０万元；ｐ２：总产量不低于１．２５万ｔ；ｐ３：小麦产量以０．５万ｔ为宜；ｐ４：大豆产量不超为０．２万ｔ；ｐ５：玉米产量不超过０．６万ｔ；ｐ６：农场现能提供５０００ｔ化肥；若不够，可在市场高价购买，但希望高价采购量愈少愈好。试就该农场生产计划建立数学模型。例５　某公司下属三个小型煤矿厂Ａ１，Ａ２，Ａ３，每天煤炭的生产量分别为１２ｔ，１０ｔ，１０ｔ，供应Ｂ１，Ｂ２，Ｂ３，Ｂ４四个工厂，需求量分别为６ｔ，８ｔ，６ｔ，１０ｔ。公司调运时依次考虑的目标优先级为：ｐ１：Ａ１产地因库存限制，应尽量全部调出；ｐ２：因煤质要求，Ｂ４需求最好由Ａ２供应；ｐ３：满足各销地需求；ｐ４：调运总费用尽可能小；从煤矿至各厂调运的单位运价如下表：　　　　工厂煤矿　　　　Ｂ１Ｂ２Ｂ３Ｂ４Ａ１３６５２Ａ２２４４１Ａ３４３６３—５２—西安建筑科技大学《８１６运筹学》习题解析第１２讲第十章　对策问题对策问题局中人：参与竞争的各方．可以是一个人，也可以是一个集团；可以有两方，也可以有多方，局中人之间可以有结盟和不结盟之分．策略：指局中人用于对付其他局中人的行动方案．策略集合：一个局中人的策略全体．如只含有限个策略，则称之为有限对策，否则为无限对策．局势：在一局对策中，各局中人选定的策略构成一个策略组称为局势．收益函数：在竞争的局势中，当一个局势确定后，就决定了局中人的输赢，这个输赢的值是局势的函数，称作收益函数．矩阵对策的模型矩整对策（二人有限零和对策）：在这样的对策中，只有两个局中人，每个局中人的策略集合中只含有有限个策略，一个局势形成后，一个局中人的赢得值恰为另一个局中人输掉的值，即两个局中人的得失总和为零．由于局中人的收益函数可用矩阵表示，故简称矩阵对策。设有两个局中人，Ⅰ和Ⅱ，他们的策略集合分别为：Ｓ１＝｛α１，α２，…，αｍ｝，Ｓ２＝｛β１，β２，…βｎ｝其中αｉ，βｊ称为纯策略，Ｓ１，Ｓ２称为纯策略集合。如果局中人Ⅰ选取纯策略αｉ∈Ｓ１，局中人Ⅱ选取纯策略βｊ∈Ｓ２，就形成纯局势（αｉ，βｊ），这时，局中人Ⅰ得到收益ａｉｊ，而局中人Ⅱ得到收益为－ａｉｊ。考虑到各种可能出现的局势，局中人Ⅰ的所得收益矩阵（或赢得矩阵）为：ａ１１ａ１２…ａ１ｎａ２１ａ２２…ａ２ｎａｍ１ａｍ２…ａｍｎ矩阵对策模型可记为：Ｇ＝｛Ｓ１，Ｓ２；Ａ｝例　（纯策略）求解矩阵对策Ｇ＝｛Ｓ甲，Ｓ乙；Ａ｝，其中Ａ＝－７１－８３２４１６－１－３－３０５例（优超策略解决）设赢得矩阵为Ａ，求解这个矩阵对策—６２—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５Ａ＝３２０３０５０２５９７３９５９４６８７５．５６０８８３例　（单纯形法）“石头－剪刀－布”游戏．两名儿童甲、乙玩“石头－剪刀－布”游戏，他们的策略集合都是｛石头，剪刀，布｝．当双方选定自己的策略后，一个局势就形成了，我们规定，赢的一方得１分，输的一方得－１分，平局得０分，则在各种可能局势下，儿童甲的得分如下表所示．因为甲和乙在同一局势下的得分之和为零，故矩阵中各元素的相反数表示儿童乙在各种局势下的得分．在这个游戏中，双方都必须考虑对方的可能策略来决定自己的策略选择．对策问题Ａ＝２３１１[]７５２　　　　Ａ＝２７６６１１２当局中人Ⅰ采用混合策略，局中人Ⅱ分别采取纯策略β１，β２，…，βｎ时，局中人Ⅰ的期望赢得分别为∑ｍｉ＝１ａｉ１ｘｉ，∑ｍｉ＝１ａｉ２ｘｉ…∑ｍｉ＝１ａｉｍｘｉ，依据小中取大原则，局中人Ⅰ的最终期望赢得ｖ１：ｖ１＝ｍａｘＸ｛ｍｉｎ（∑ｍｉ＝１ａｉ１ｘｉ，∑ｍｉ＝１ａｉ２ｘｉ，…，∑ｍｉ＝１ａｉｎｘｉ）｝ｘ１＋ｘ２＋…＋ｘｍ{＝１　　（１２．７）若令ｖ′＝｛ｍｉｎｊ（∑ｍｉ＝１ａｉｊｘｉ）｝，则上式可写为：Ｌ：ｍａｘ｛ｖ′｝ｓ．ｔ∑ｍｉ＝１ａｉｊｘｉ≥ｖ′（ｊ＝１，２，…，ｎ）∑ｍｉ＝１ｘｉ＝１ｘｉ≥０　　（１２．８）上式中的每个约束均除以ｖ′，又ｍａｘ｛ｖ′｝ｍｉｎ｛１ｖ′｝，令ｘ′ｉ＝ｘｉｖ′（ｖ′＞０），则有Ｌ１：ｍｉｎ｛１ｖ′｝＝ｘ′１＋ｘ′２＋…＋ｘ′ｍｓ．ｔａ１１ｘ′１＋ａ１２ｘ′２＋…＋ａｍ１ｘ′ｍ≥１ａ１２ｘ′１＋ａ２２ｘ′２＋…＋ａｍ２ｘ′ｍ≥１……ａ１ｎｘ′１＋ａ２ｎｘ′２＋…＋ａｍｎｘ′ｍ≥１ｘ′ｉ≥０（ｉ＝１，２，…，ｍ）　　（１２．９）—７２—西安建筑科技大学《８１６运筹学》习题解析同理，当局中人Ⅱ采用混合策略，局中人Ⅰ分别采取纯策略α１，α２，…，αｍ时，局中人Ⅱ的期望损失分别为∑ｍｉ＝１ａ１ｊｘｊ，∑ｍｉ＝１ａ２ｊｘｊ…∑ｍｉ＝１ａｍｊｘｊ，依据大中取小原则，局中人Ⅱ的最终期望赢得ｖ２：ｖ２＝ｍｉｎＹ｛ｍａｘ（∑ｍｉ＝１ａ１ｊｘｊ，∑ｍｉ＝１ａ２ｊｘｊ，…，∑ｍｉ＝１ａｍｊｘｊ）｝ｙ１＋ｙ２＋…＋ｙｎ{＝１　　（１２．１０）若令ｖ″＝｛ｍａｘｉ（∑ｍｊ＝１ａｉｊｘｊ）｝，ｙ′ｊ＝ｙｊｖ″（ｖ″＞０）则上式可写为：Ｌ２：ｍａｘ｛１ｖ″｝＝ｙ′１＋ｙ′２＋…＋ｙ′ｎｓ．ｔａ１１ｙ′１＋ａ１２ｙ′２＋…＋ａ１ｎｙ′ｎ≤１ａ２１ｙ′１＋ａ２２ｙ′２＋…＋ａ２ｎｙ′ｎ≤１……ａｍ１ｙ′１＋ａｍ２ｙ′２＋…＋ａｍｎｙ′ｎ≥１ｙ′ｊ≥０（ｊ＝１，２，…，ｎ）　　（１２．１１）Ｌ１和Ｌ２互为对偶线性规划问题．注意：Ｌ１和Ｌ２模型中的ｖ′和ｖ″不允许为零，故当支付矩阵Ａ＝（ａｉｊ）ｍ×ｎ中元素有负值时，可将该矩阵

的每一个元素都加上一个常数ｋ变换为正值，得到矩阵Ａ－＝（ａｉｊ＋ｋ）ｍ×ｎ．可以证明矩阵对策Ｇ＝｛Ｓ１，Ｓ２；Ａ｝和Ｇ－＝｛Ｓ１，Ｓ２；Ａ－｝同解．且有：ＶＧ－＝ＶＧ＋ｋ．—８２—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５第１３讲考试试题形式判断题（在下列各题中，你认为体重描述的内容为正确者，在题尾括号内写“√”，错误者写“×”。）１．图解法提供了求解线性规划问题的通用方法。（　　）２．用单纯形法求解一般线性规划时，当目标函数求最小值时，若所有的检验数Ｃｊ－Ｚｊ≥０，则问题达到最优。（　　）３．在单纯形表中，基变量对应的系数矩阵往往为单位矩阵。（　　）４．满足线性规划问题所有约束条件的解称为基本可行解。（　　）５．在线性规划问题的求解过程中，基变量和非基变量的个数是固定的。（　　）６．对偶问题的目标函数总是与原问题目标函数相等。（　　）７．原问题与对偶问题是———对应的。（　　）８．运输问题的可行解中基变量的个数一定遵循ｍ＋ｎ－１的规则。（　　）９．这牌问题的解中基变量的个数为ｍ＋ｎ．（　　）１０．网络最短路径是指从网络起点至终点的一条权和最小的路线。（　　）１１．动态规划中运用图解法的顺推方法和网络最短路径的标号法伤是一致的。（　　）名词解释１．运筹学：２．线性规划：３．可行解：４最优解：５运输问题：６闭回路：问答题１．试述组成对策模型的三个基本及其含义。２．试述存储问题的费用分类及其含义。３．用符号Ｘ／Ｙ／Ｚ／Ａ／Ｂ／Ｃ表示一个排队模型时，符号中各个字母的含义。４．试述凸函数及其严格凸函数的定义。５．试述如何在单纯形表上判断规划具有唯一最优解，无穷多个最优解，无界解或者无可行解。６．试从经济上解释对偶问题及其对偶变量的含义。—９２—西安建筑科技大学《８１６运筹学》习题解析填空题１．线性规划问题如果没有最优解，则单纯形计算表的终点表中必然有．２．用分枝定界法求解纯整数规划问题的过程可以大概分为以下三步：第一步：用单纯形法求的解，如果有解且不满足纯整要求，转下步第二步：建立并加入线性规划问题，转下步。第三步：用方法定界，确定下一个问题，然后转第一步。３．对偶问题的性质有（至少答三个）：。４．线性规划问题求解的优点中有，缺点有。５．对偶价格是指。１．排队问题（天大考研）：（１０％）某购物中心设有一个能容纳１００辆轿车的停车场，设轿车的到达为一泊松流，顾客的购物时间服从负指数分布，当轿车到达停车场时，若停车场已满，则轿车将不再等待而离去。（１）此问题可看作何种类型的排队模型？（２）请解释本问题中的状态概率Ｐｎ，队长Ｌｓ，排队长Ｌｑ，逗留时间Ｗｓ和等待时间Ｗｑ的实际意义。（３）如果购物中心的经理希望知道是否需扩大停车场容量，你认为对此可怎样分析？２．存储问题（天大）：在确定性存贮问题中，记Ｃ１为订货费，Ｃ２为存贮费，Ｃ３为缺货费，Ｒ为需求率，设Ｃ１、Ｃ２和Ｒ均为常数，不需要提前订货，且一订货即可全部供货。（１）请分别写出不允许缺货和允许缺货（缺货要补）两种条件下最佳批量相应的总费用表达式，并说明允许缺货时的费用不会超过不允许缺货时的费用。（２）若Ｒ＝５０箱／月，Ｃ１＝６０元／次，Ｃ２＝４０元／月，允许缺货且缺货要补，Ｃ３＝４０元／箱·周。求最佳订货批量及订货间隔时间。—０３—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５第１４讲考试样题一、不定项选择题（每小题２分，共６分）１．线性规划的标准型有特点（　　）。Ａ．右端项非零；　　　　　　　　　　　　Ｂ．目标求最大；Ｃ．有等式或不等式约束；Ｄ．变量均非负。２．一个线性规划问题（Ｐ）与它的对偶问题（Ｄ）有关系（　　）。Ａ．（Ｐ）无可行解则（Ｄ）一定无可行解；Ｂ．（Ｐ）、（Ｄ）均有可行解则都有最优解；Ｃ．（Ｐ）的约束均为等式，则（Ｄ）的所有变量均无非负限制；Ｄ．若（Ｄ）是（Ｐ）的对偶问题，则（Ｐ）是（Ｄ）的对偶问题。３．关于动态规划问题的下列命题中（　　）是错误的。Ａ．动态规划阶段的顺序与求解过程无关；Ｂ．状态是由决策确定的；Ｃ．用逆序法求解动态规划问题的重要基础之一是最优性原理；Ｄ．列表法是求解某些离散变量动态规划问题的有效方法。二、判断题（每小题１分，共５分）１．若某种资源的影子价格等于ｋ，在其他条件不变的情况下，当该种资源增加５个单位时，相应的目标函数值将增大５ｋ个单位。（　　）２．如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数ｋ，最优调运方案将不会发生变化。（　　）３．运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解。（　　）４．用割平面法求解纯整数规划问题时，要求包括松弛变量在内的全部变量必须取整数值。（　　）三、考虑下列线性规划（２０分）ｍａｘｚ＝３ｘ１＋５ｘ２＋ｘ３４ｘ１＋２ｘ２＋ｘ３≤１４ｘ１＋ｘ２＋ｘ３≤４ｘｊ≥０，ｊ＝１，２，{３其最优单纯形表为：—１３—西安建筑科技大学《８１６运筹学》习题解析ＣＢＸＢｂ′Ｘ１Ｘ２Ｘ３Ｘ４Ｘ５０６２０－１１－２５４１１１０１－Ｚ－２０－２０－４０－５１．（１０分）写出此线性规划的最优解、最优值；２．（２分）求线性规划的对偶问题的最优解；３．（４分）试求在什么范围内，此线性规划的最优解不变；４．（４分）若变为９，最优解及最优值是什么？四、下述线性规划问题（１０分）ｍａｘｚ＝１０ｘ１＋２４ｘ２＋２０ｘ３＋２０ｘ４＋２５ｘ５ｘ１＋ｘ２＋２ｘ３＋３ｘ４＋５ｘ５≤１９２ｘ１＋４ｘ２＋３ｘ３＋２ｘ４＋ｘ５≤５７ｘｊ≥０，ｊ＝１，２，…，{５以ｙ１，ｙ２为对偶变量写出其对偶问题。五、某公司下属的２个分厂Ａ１、Ａ２生产质量相同的工艺品，要运输到Ｂ１、Ｂ２、Ｂ３，３个销售点，分厂产量、销售点销量、单位物品的运费数据如下表：（１４分）Ｂ１Ｂ２Ｂ３产量Ａ１２３１１２０２５Ａ２１８１６１７２５销量２０１０２０用伏格尔法给出近似最优解。六、已知目标规划模型为：（１０分）ｍｉｎｚ＝ｐ１ｄ＋１＋ｐ２（ｄ－２＋ｄ＋２）＋ｐ３ｄ－３２ｘ１＋ｘ２≤１０ｘ１－ｘ２＋ｄ－１－ｄ＋１＝０ｘ１＋２ｘ２＋ｄ－２－ｄ＋２＝１２－ｘ１＋ｘ２＋ｄ－３－ｄ＋３＝８ｘ１，ｘ２，ｄ－ｉ，ｄ＋ｉ≥０，ｉ＝１，２，３试用图解法求满意解。七、有甲、乙、丙、丁四个人，要分别指派他们完成Ａ、Ｂ、Ｃ、Ｄ不同的工作，每人做各项工作所消耗的时间如下表所示：（１５分）—２３—考试点（ｗｗｗｋａｏｓｈｉｄｉａｎｃｏｍ）名师精品课程电话：４００－６８８５－３６５ＡＢＣＤ甲７９１０１２乙１３１２１５１７丙１５１６１４１５丁１１１２１５１６问：应该如何指派，才能使总的消耗时间为最少？八、问答题（每题５分，共１０分）１．求线性规划最优解时，可能会出现什么结果？如何用单纯形表进行判断？２．解决动态规划问题时，需要哪些变量来描述一个动态规划？试用自己的语言描述Ｂａｌｍａｎ原则。—３３—西安建筑科技大学《８１６运筹学》习题解析第１５讲西建大考试样题一、判断正误，若判断为误，请作简要分析（８分）１．单纯形的迭代计算是从一个可行解迭代到目标函数增大的另一可行解。２．表上作业法对于任何类型的运输问题都可以直接应用。二、简答题（２０分）１．试述对策问题的三要素及二人有限零和对策概念上的含义，该种对策问题为什么又称矩阵对策？２．线性规划最优解存在有哪几种情况？简述单纯形法求解过程中表现？３．什么是平衡运输问题？该类问题数学模型有什么样的特征？４．简述存储问题的费用构成以及各种费用与其对用的物资量之间关系。三、建立下面问题的线性规划模型，不求解（１０分）某建筑工地要做８９套钢架，每套用长２．９米和１．５米的角钢各两根，２．１米的角钢一根。已知原料长７．４米，问应如何下料，可使原料的浪费量最少？四、求解下列线性规划问题（１５分）ｍａｘｆ（ｘ）＝－９ｘ１－６ｘ２－２ｘ３ｘ１＋ｘ２＋ｘ３≤８ｘ１－ｘ３≥４ｘ２－ｘ３≥３ｘ１，ｘ２，ｘ３≥０五