第一章 线性规划及单纯形法 习题.doc

运筹学习题选解第一章 线性规划及单纯形法1、 （生产计划问题） 某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表 1-12. 若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费0.2万元. 现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低. 试建立线性规划模型.表1-12季度生产能力（吨）生产成本（万元/吨）需求量（吨）13015020240140203201533041014810解: 现在我们对本问题定义三种不同形式的决策变量，从而从不同的途径来构建模型.（1）设工厂第季度生产产品吨首先，考虑约束条件：第一季度末工厂需交货20吨，故应有；第一季度末交货后积余（）吨；第二季度末工厂需交货20吨，故应有；类似地，应有；第四季度末供货后工厂不能积压产品，故应有；又考虑到工厂每个季度的生产能力，故应有. 其次，考虑目标函数：第一季度工厂的生产费用为15.0，第二季度工厂生产的费用包括生产费用14及积压产品的存贮费；类似地，第三季度费用为，第四季度费用为. 工厂一年的费用即为这四个季度费用之和. 整理后，得下列线性规划模型： min s.t. ，.（2）设第季度工厂生产的产品为吨，第季度初存贮的产品为吨（显然，）.因为每季度初的存贮量为上季度存贮量、生产量之和与上季度的需求量之差，又考虑到第四季度末存贮量为零，故有：， ， ；同时，每季度的生产量不能超过生产能力：；而工厂四个季度的总费用由每季的生产费用与存贮费用组成，于是得线性规划：min s.t. ， 2，3，4.（3） 设第季度生产而用于第季度末交货的产品数量为吨.根据合同要求，必须有： ， ， ， .又每季度生产而用于当季和以后各季交货的产品数不可能超过该季工厂的生产能力，故应有： ， ， ， .第季度生产的用于第季度交货的每吨产品的费用，于是，有线性规划模型：min z = s.t. 1，4；1，4，.2、（合理下料问题）某工厂要制作100套专用钢架，每套钢架需要用长为2.9m、2.1m和1.5m的圆钢各一根。已知原料每根长7.4m，现考虑应如何下料，可使所用原料最省？ 解: 分析：利用7.4m长的圆钢截成2.9m、2.1m、1.5m的圆钢共有如表1-13所示的8种下料方案.表1-13 下料方案表 方案毛坯/m方案1方案2方案3方案4方案5方案6方案7方案8292111000021021032101510130234合计7371657463726660剩余料头0103090011020814 一般情况下，我们可以设分别为上面8种方案下料的原材料根数.根据目标的要求，可以建立两种形式的目标函数： 材料根数最少：min z = (1.27) 剩余料头最少：min z = （1.28）约束是要满足各种方案剪裁得到的2.9m、2.1m、1.5m三种圆钢各自不少于100个，即 2.9m : 2.1m : 1.5m : 非负条件 ， ， ， 这样我们用目标函数（1.27）可建立如下数学模型： min s.t. ， ， ， 利用线性规划单纯形法求解可得：=（10，50，0，30，0，0，0，0）T，最少使用的材料为90（根），各种圆钢数均正好100个. 如果用目标函数（1.28），可建立如下数学模型：min s.t. ， ， ， 利用线性规划单纯形法求解可得：=（0，0，0，100，0，50，0，0）T，最少的剩余料头为10m. 这时2.9m和2.1m的圆钢数正好100个，而1.5m的圆钢数多300个. 显然，这不是最优解，为什么会出现误差呢？仔细观察一下会发现，原因出现在方案4的剩余料头为零，求解过程中目标函数最小对它失去了作用. 由此提示我们，在实际使用线性规划解决问题时，隐含的逻辑错误往往很难发现，必须进行解的分析才能够找出问题.3 、（多阶段投资问题）某企业现有资金200万元，计划在今后5年内给A，B，C，D ，4个项目投资。根据有关情况的分析得知：项目A：从第一年到第五年每年年初都可进行投资，当年末就能收回本利110%；项目B：从第一年到第四年每年年初都可进行投资，当年末能收回本利125%，但是要求每年最大投资额不能超过30万元；项目C：若投资则必须在第三年年初投资，到第五年末能收回本利140%，但是限制最大投资额不能超过80万元；项目D：若投资则需在第二年年初投资，到第五年末能收回本利155%，但是规定最大投资额不能超过100万元； 根据测定每万元每次投资的风险指数为：项目A为1，项目B为3，项目C为4，项目D为5.5. 问题：（1） 应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？（2） 应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上保证其投资的总风险系数最小？解: 首先考虑问题（1）：1）确定决策变量. 本题是一个连续投资的问题，由于需要考虑每年年初对不同项目的投资数，为了便于理解，建立双下标决策变量.设（1，2，3，4，5；1，2，3，4）表示第i年初投资于项目A（）、项目B（）、项目C（）、项目D（）的金额. 根据题意，我们建立如下决策变量：第一年年初 第二年年初 第三年年初 第四年年初 第五年年初项目A 项目B 项目C 项目D 2）考虑约束条件. 由于项目A的投资当年末就可以收回本息，因此在每一年的年初必然把所有的资金都投入到各项目中，否则一定不是最优的. 下面我们分年来考虑：第一年年初：由于只有项目A和项目B可以投资，又应把全部200万元资金投出去，于是有 第二年年初：由于项目B要次年末才可收回投资，故第二年年初的资金只有第一年年初对项目A投资后，在年末收回的本利110%，而投资项目为A，B和D，于是有：整理后得：第三年年初：年初的资金为第二年年初对项目A投资后，在年末收回的本利110%以及第一年年初对项目B投资后，在年末收回的本利125%. 可投资项目有A，B和C，于是有： 整理后得： 第四年年初：年初的资金为第三年年初对项目A投资后，在年末收回的本利110%以及第二年年初对项目B投资后，在年末收回的本利125%. 可投资项目只有A和B，于是有： 整理后得： 第五年年初：年初的资金为第四年年初对项目A投资后，在年末收回的本利110%以及第三年年初对项目B投资后，在年末收回的本利125%. 可投资项目只有A，于是有：整理后得： 其他的还有项目B，C，D的投资限制以及各决策变量的非负约束：项目B的投资限制： （1，2，3，4）项目C的投资限制： 项目D的投资限制： 各决策变量的非负约束：，（1，2，3，4，5；1，2，3，4）3）建立目标函数. 问题要求在第五年末公司这200万元用于4个项目投资的运作获得本利最大，而第五年末的本利获得有4项：第五年年初对项目A投资后，在年末收回的本利110%；第四年年初对项目B投资后，在年末收回的本利125%；第三年年初对项目C投资后，在年末收回的本利140%；第二年年初对项目D投资后，在年末收回的本利155%. 于是得到目标函数为： 根据上面的分析得到线性规划模型：max s.t. (1，2，3，4) ， （1，2，3，4，5;1，2，3，4）考虑问题（2）：据题意，问题（2）的决策变量设置与问题（1）的设置1）完全相同；而问题（2）的约束设置除与问题（1）的设置2）完全相同外，还增加一约束，就是考虑要使第五年末拥有资金的本利在330万元上，即 问题（2）的主要区别在于目标不同，是要使得第五年年末拥有资金的本利在330万元的基础上保证其投资的总风险系数为最小. 因此，目标函数为各年各项目的风险系数之和，而风险系数等于投资数乘以相应风险指数. 于是得到下列目标函数：综合以上分析，问题（2）的线性规划模型为：min s.t. (1，2，3，4)， （1，2，3，4，5;1，2，3，4）此例属于动态规划问题，它既可以建立上述模型用线性规划求解，也可以用动态规划的方法求解. 很多运筹学问题是可以用多种方法求解的，不同方法求解在理论上得到的结果应是一致的，但是由于方法本身的特征，不同算法可以得到不同的附带信息. 例如利用线性规划求解除了可得到最优解和最优植之外，还可通过分析得到下面将要介绍的影子价格（对偶价格）、灵敏度分析结果等. 另外，不同方法求解同一个问题时，计算量、复杂性、精确度等都会有差异.因此，读者在学习中了解掌握多种建摸思路，学会多种求解方法，对于提高解决实际问题的能力和水平是十分重要的. 4、（场地租借问题）某厂在今后四个月内需租用仓库堆存货物. 已知各个月所需的仓库面积数如表1-14. 又知，当租借合同期限越长时，场地租借费用享受的折扣优待越大，有关数据如表1-15.表1-14月份1 2 3 4所场地面积（百米2）15 10 20 12表1-15合同租借期限1个月 2个月 3个月 4个月 租借费用（元/百米2）2800 4500 6000 7300租借仓库的合同每月都可办理，每份合同应具体说明租借的场地面积和租借期限. 工厂在任何一个月初办理签约时，可签一份，也可同时签若干份租借场地面积数和租借期限不同的合同. 为使所付的场地总租借费用最小，试建立一个线性规划模型.解： 设为第i个月初签订的租借期限为j个月的合同租借面积（单位：百米2）.于是，有下列决策变量：一月签订： 二月签订： 三月签订： 四月签订： 各个月生效的合同的租借面积为：第一个月：+第二个月：+第三个月：+第四个月：+从而，我们得如下线性规划摸型：min z =s.t. +， +10， +20， +12 1，4 ， 1，2，3 ， .5、（分配问题）甲方战略轰炸机队指挥官得到了摧毁乙方坦克生产能力的命令. 根据情报，乙方有三个生产坦克部件的工厂，位于不同的地点. 只要破坏其中任一个工厂的生产设施就可以有效地停止乙方坦克的生产.该轰炸机队现有重型和中型两种轰炸机，其数量和燃油耗量如表1-16.表1-16编号i飞机类型每公里耗油量（加仑）飞机架数1重型1/2402中型1/328根据情报分析，空军基地与各工厂的距离和各类型飞机命中目标的概率如1-17表.表1-17 工厂#距离（公里）摧毁目标概率重型（1）中型（2）14500.100.0824800.200.1635700.150.12甲方为完成此项任务至多能提供48000加仑汽油. 而对于任何类型飞机，不论去轰炸那一个工厂，都必须有足够往返的燃料和100加仑备用燃料.试问指挥官为执行任务应向三个工厂派遣每种类型的飞机个多少架，才能使成功的概率最大？ 解 设为#型飞机被派遣去#工厂执行任务的架数.甲方的目标是希望事件“至少摧毁一个工厂”的概率最大. 这相当于希望事件“不摧毁任何工厂”的概率最小. 我们有：它不是线性的，为此将上式改写为 于是，模型的目标函数为 关于燃料的约束条件为： 经过整理，即为 .飞机数量约束： ，综上所述，本问题的线性规划模型为： max z = s.t. ， 1，2；1，2，3.6、（选址问题）设有A、A和A三个原料产地，其原料要在工厂加工，制成成品后再在销地销售，A与A两地又是销地. 设4吨原料可以加工成1吨成品，A与A间距离为150公里，A 与A间距离为200公里，A与A间距离为100公里. 原料运费每万吨公里为3千元，成品运费每万吨公里为2.5千元。现考虑在这三个地点建厂：若在A建厂，生产规模为每年生产的成品不能超过5万吨，而在A或A建厂，生产规模不受限制. 有关数据由表1-18给出.表1-18地点原料产量（万吨/年）成品销售量（万吨/年）成品加工费（千元/万吨）3075526134243试问在那几个地点建厂，生产规模如何，才能使生产成本最小？（这里为简化问题，仅考虑原料费用、成品运费和成品加工费，其它如原料单价、建厂投资费等未加考虑.）解: 在建立模型以前，让我们先来分析一下问题中所给数据是否产销平衡？A、A和A每年原料的生产量总和为80万吨，A和A每年对成品的销售量总和为20万吨，由于每4吨原料可加工为1吨成品，所以产销平衡.设为每年由产地运往建厂地的原料数量（万吨）（1，2，3）；为每年由建厂地运往销地的成品数量（万吨）（1，2，3；1，2）.第一组约束条件为：若在地建厂，则其所具有的原料数量（本地生产的原料数量与其它两地运来的原料数量之和）应等于该地设厂生产的成品数量的4倍. 例如对A来说，应有上式中既出现又出现，初看起来是矛盾的. 但是在研究建厂规划时，事先并不能知道哪一个方向是合理的，只好把两种可能的方向都考虑进去. 由于目标函数是要求生产成本最小，因此在最优解中不可能产生对流运输. 类似地，有 第二组约束条件为：各地工厂运到销地的成品数应恰为销地的需求量： 第三组约束条件为产地设厂的生产规模约束： 目标函数为 因此，本问题的线性规划模型为： s.t. ， 1，2，3， ， 1，2，3； 1，2. 用单纯形法对此模型求解，若得最优解（1，2，3；），（1，2，3；1，2），则地设厂的生产规模为，地设厂的生产规模为，地设厂的规模为. 若求得的生产规模为零，则在地不设厂.7、某饲养场饲养动物出售，设每头动物每天至少需700克蛋白质、30克矿物质、100毫克维生素. 现有五种饲料可供选用，各种饲料每公斤营养成分含量及单价如表1-19所示：表1-19饲 料蛋白质（g）矿物质（g）维生素（mg）价格（元/kg）1234532161810.50.220.50.51.00.220.80.20.70.40.30.8要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案. 建立这个问题的线性规划模型.解：用Xj（j=1.25）分别代表5中饲料的采购数，线性规划模型： 表1-20班次工作时间所需护士数（人）1234566:0010:0010:0014:0014:0018:0018:0022:0022:002:002:006:006070605020308、某医院护士值班班次、每班工作时间及各班所需护士数如表1-20所示. 每班护士值班开始时向病房报到，并连续工作8小时。试决定该医院最少需多少名护士，以满足轮班需要，建立线性规划模型.解：设x表示在第i个时期初开始工作的护士人数，z表示所需的总人数，则表1-21 前舱中舱后舱最大允许载重量（t）容积（m3）200040003000540015001500表1-22商品数量（件）每件体积（m3/件）每件重量（t/件）运价（元/件）ABC6001000800105786510007006009、一艘货轮分前、中、后三个舱位，它们的容积与最大允许载重量如表1-21所示. 现有三种货物待运，书籍有关数据列于表1-22.又为了船运安全，前、中、后舱的实际载重量上大体保持各舱最大允许载重量的比例关系. 具体要求：前、后舱分别与中舱之间载重量比例上偏差不超过15%，前、后舱之间不超过10%. 问该货轮应装载A,B,C各多少件运费收入才最大？试建立这个问题的线性规划模型.解：设用i=1，2，3分别表示商品A，B，C，j=1，2，3分别代表前，中，后舱，Xij表示装于j舱的i种商品的数量，Z表示总运费收入则：10、用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解.14（1） s.t. 解： Z = 4 （2） s.t. 解：如图：由图可得：即该问题具有唯一最优解（3） s.t. 无可行解（4） s.t. 解：如图由图知，该问题具有无界解。11、将下述线性规划问题化成标准形式（1）s.t. , 无约束解：（2）s.t. 无约束解：12、对下述线性规划问题找出所有基本解，指出哪些是基本可行解，并确定最优解（1）St 解：系数矩阵A： （B，b）= y1=（0，16/3，-7/6，0，0，0）T同理y2=（0，10，0，-7，0，0）T y3=（0， 3，0，0，7/2，0）T y4=（7/4，-4，0，0，0，21/4）T y5=（0，0，-5/2，8，0，0）T y6=（0，0，3/2，0，8，0）T y7=（1，0，-1/2，0，0，3）T y8=（0，0，0，3，5，0）T y9=（5/4，0，0，-2，0，15/4）T y10=（0， 3，-7/6，0，0，0）T y11=（0，0，-5/2，8，0，0）T y12=（0，0，-5/2，3，5，0）T y13=（4/3，0，0，0，2，3/4）T y14=（0，10，0，-7，0，0）T y15=（0， 3，0，0，7/3，0）T y16=（0，0，3/2，0，8，0）T 基可行解：（每个x值都大于0），（y3，y6，y8，y12，y13，y15，y16） 最优解：（y3，y6， y15，y16） Zmax=3p2 p3 p4，p2 p3 p5，p3 p4 p5，p2 p4 p5为奇异，只有16个基。（2） 解：该线性问题最多有个基本解。基本解 Z基本可行解最优解X1X2X3X4-411/2002/5011/50-1/30011/601/2200-1/202001113、设某线性规划问题的约束系数矩阵A和右端常数向量b分别为 ，.试问所对应的列向量能否构成基？若能，写出B,N，并求出B所对应的基本解.解：基的定义 X1 X2 X3所对应的列向量可以构成基 B 由 X1 X2 X3 列向量构成 = N 由 非基变量对应的向量构成 = （B，b）= B对应的基解：（-13/5，37/5，0，0，3/5）14、分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基本可行解对应图解法中可行域的哪一顶点.（1） s.t. 解：（1）由图知： 单纯形法：化为标准形如下：C10500bCBXBX1X2X3XR0X3341090XR52018检验数1050000X3014/51-3/521/510X112/50-1/58/5检验数010-2-165X2015/14-3/143/210X110-1/73/70检验数00-5/14-25/14-35/2所以：其中： （2） s.t. 解： A点最大 Z= 8 化为标准形：C2-100bCBXBX1X2X3X40X33510150X4620124检验数2-1000X3041-1/23X111/301/64检验数0-10-1/3-8 0点（0，0，15，24） A点（4，0，3，0） Zmax=815、上题（1）中，若目标函数变为，讨论c,d的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优.解1）要使A（0，0）成为最优解则需C0且d0； 2）要使B（8/5，0）成为最优解则 C0且d=0或C0且d0； 3）要使C（1，3/2）成为最优解则 -5/2-C/d-3/4且Cd0；即5/2C/d3/4且Cd0；4）要使D（0，9/4）成为最优解则C0或C=0，d016、用单纯形法求解下列线性规划问题（1）s.t. 解：化为标准型： C2-11000bCBXBX1X2X3X4X5X60X4311100600X51-12010100X611-100120检验数2-1100000X404-51-30302X11-12010100X602-30-1110检验数01-30-20-200X40011-1-2102X1101/201/21/215-1X201-3/20-1/21/25检验数00-3/20-3/2-1/2-25（2）s.t. 解：C2350000bCBXBX1X2X3X4X5X6X70X42231000120X5122010080X64060010160X7043000112检验数235000000X402010-1/2040X5-1/32001-1/303/85X32/301001/603/80X7-24000-1/214检验数-4/33000-5/60-40/30X410010-1/4-1/220X52/30001-1/12-1/22/35X32/301001/608/33X2-1/21000-1/81/41检验数1/60000-11/24-3/4-49/30X40001-2/3-1/81/412X110002/3-1/8-3/415X30010-11/41/223X201003/4-3/16-1/83/2检验数0000-1/4-7/16-5/8-33/2（3）s.t. 解：标准型：C35000bCBXBX1X2X3X4X50X31010040X402010120X53200118检验数350000X3101004X20101/206X5300-116检验数300-5/20-30X30011/3-1/32X20101/206X1100-1/31/32检验数000-3/2-1-36（4） s.t. 解：标准型C-11-1-11-11-11-M-M-M0bCBXBX1X2X3X4X4“X5X5“X6X6“X7X8X9X10-MX71001-1001-110009-MX831-400002-201002-MX91.200-112-2001060X10043000000000112检验数5M-1M+1-1-2MM-11-MM+11+M5M-11-5M000017M-MX70-1/34/31-1001/3-1/31-1/30028/3-1X111/3-4/300002/3-2/301/3002/3-MX90-1/310/300-114/3-4/30-1/31016/30X10043000000000112检验数04/3-2/3M14/5M-7/3M-11-MM-1M+15/3M-1/3-5/3M+1/30-5/3M+1/300-41/3M-2/3-MX70-1/501-12/5-2/5-1/51/51-1/5-2/5031/5-1X111/5000-2/52/56/5-6/501/52/5014/5-1X30-1/10100-3/103/102/5-2/50-1/103/1008/50X10043/100009/10-9/10-6/56/503/10-9/10136/5检验数0-1/5M+11/100M-11-M2/5M-17/10-2/5M+17/103/5-1/5M1/5M-3/50-6/5M-7/5M0-31M/5-22/5（5） s.t. 解：标准化：C62108000bCBXBX1X2X3X4X5X6X70X556-4-4100200X63-328010250X74-21300110检验数6210800000X521-208114600X6-510200-2510X34-21300110检验数-34220-2200-10-1000X5110012120702X2-510201-2510X3-601702-320检验数7600-660-2234-210由表可得， 因此问题的解无界。（6）s.t. 解：化为:标准形：Z=-Z（I）C-x-1-1000bCBXBX1X2X3X4X5X6-XX1100-40-25-1X20102-313-1X30012-565检验数0004-4x-87-2x5x+8 如图：1. X7/2 时，检验数0 ，最优解：（5，3，5，0，0）T2. 1X7/2时，4-4X0由（I）得：C-x-1-1000bCBXBX1X2X3X4X5X6-XX1101/3-10/3-5/3020/3-1X201-1/65/3-13/6013/60X6001/61/3-5/615/6检验数00X/3-7/6-10X/3+5/3-5X/3-13/6020X/3+13/63. X -2X+70 C-x-1-1000bCBXBX1X2X3X4X5X6-XX11200-6011-1X201/201-3/21/23/2-1X30-110-252检验数02x-200-6X-2511X+2检验数0，列系数0，所以解无界。4.-3/2X4-4X0C-x-1-1000bCBXBX1X2X3X4X5X6-XX1100-10/3-5/3020/3-1X20105/3-13/6013/6-1X60011/3-5/615/6检验数X/3-7/6-10X/3+5/3-5X/3-13/620X/3+13/6判断检验数的符号：1)1/2X 1 ，所有检验数 0（1/2X2）-1.3X1/2时表（A）C-x-1-1000bCBXBX1X2X3X4X5X6-XX11200-600110X403/5-1/101-13/100013/100X60-1/51/50-2/5112/5检验数02X-1-10-6X011X对-6X讨论，令-6X=0 X=0 0X1/2时， 检验数0 （0X1/2）-1.3X0 又 X5列的系数 0 ，所以解无界3） -1.5X0 ，又 X5的列的系数0，所以解无界（7）s.t. 解：化为标准形：C164000000-M-M-MbCBXBX1X2X3X4X5X6X7X8X9X10X11X120X4-122100000000130X54-41010000000200X612100110000017-MX101000000001001-MX110100000-100102-MX1200100000-10013检验数