运筹学

简答题

1对形如max：{CX|AX≤b,X≥0}线性规划，写出其对偶解与检验数（递减成本）的表达式，并解释它们的经济含义

2写出min{f(x)|g(x)≥0,x≥0}的K—T最优条件 3写出线性规划的对偶问题： max CX

S.T.{a≤AX≤b l≤X≤u}

4.简述求解无约束非线性规划的梯度法与共轭梯度法的异同。

5.比较求解线性规划的单纯性法和内点法的优缺点

解答题

1.考虑资源最优分配的线性规划问题（P）可以写成以下形式： max: cx s.t． Ax≤b

0≤x≤u

式中，c是产品的单位价格，b为可以使用资源的数量，u是市场对产品需求的上限，A矩阵是生产各种单位产品需要消耗各种资源数量的消耗矩阵，x是决定生产数量的决策变量。如果我们假定使用的资源还没有买入（b也为决策变量），令p＞0为各种资源的市场价格，问题p可以变为：

max: cx-pb s.t. Ax-b≤0 0≤x≤u, b≥0

（1）证明新问题总有最优解；

（2）令y*(b)代表p的对偶最优解，这里已经显性地表示出对偶最优解的值取决于b的取值，证明b的最优解值b*满足y*(b*)=p

2.考虑下面的线性规划问题： max: cx s.t． Ax≤b

x≥0

令y*(b)为该问题的最优解，假定y*(b)小于正无穷大，证明y*(b)是一个凹函数

3.某企业使用四种化工原料生产六种化工产品，生产每种产品的投入产出系数见下表： 原料1 原料2 原料3 原料4 产品A 0.5 0.1 0.2 0.4 产品B 0.6 0.1 0.3 43 40 100 产品C 0.2 0.2 0.5 45 30 150 产品D 0.4 0.4 0.6 65 30 200 产品E 0.1 0.5 0.6 56 50 120 产品F 0.6 0.2 0.1 0.2 48 40 70 原料成本 22 18 32 25 可用数量 160 140 150 150 销售价格 55 最小需求 50 最大需求 140

（表中的成本和价格的单位为万元/吨，最大、最小需求数量和原料可用数量的单位为吨） 每种产品的投入产出系数列在表中，例如生产一吨A产品需要0.5吨原料1，0.1吨原料2，0.2吨原料3，0.4吨原料4，其他产品需要的原料数可依此类推。原料的成本和可使用数量列在表的最后两列；产品的销售价格在表的最后一行。产品的产量应该大于最小需求量，同时也要小于最大需求量。构造的求销售利润最大的线性规划模型用EXCEL求解后的敏感性分析报告如下表：

可变单元格： 名字 产品A产量 产品B产量 产品C产量 产品D产量 产品E产量 产品F产量

约束： 名字 终值 影子价格 21.8 22.0 0.0 27.7 约束限制值 160 140 150 150 允许的增量 1.71 12 1E+30 5.43 允许的减量 15.43 4.47 35.03 6 原料1使用量 160 原料2使用量 140 原料3使用量 115 原料4使用量 150 终值 140 52.7 150 30 78 67 递减成本 1.6 0.0 12.3 -0.1 0.0 0.0 目标式系数 25.8 21.5 21 34 29.8 23 允许的增量 1E+30 0.4 1E+30 0.13 2.03 2.32 允许的减量 1.63 2.22 12.3 1E+30 0.13 0.27 （1）该问题的最优解中应该有几个基变量（提示：应包括松弛变量中的基变量），根据敏感性分析表中提供的信息，判断那些变量是基变量？

（2）从表中可知：产品D的单位利润最高（34万元/吨），但它对目标池数的边际贡献却最小（递减成本为-0.1万元/吨）；产品C的单位利润最低（21万元/吨），但它对目标函数的边际贡献却最大（递减成本为12.3万元/吨），为什么会有这样矛盾的现象，请解释其中的原因？

（3）四种原料中哪种原料的影子价格最高，如果企业还可以从市场上获得这种原料，企业可以出的最高价格是多少？

（4）在保持最优基不变的前提下，你建议该企业应继续采购哪种原材料，采购多少可以使

企业获得最大的收益？

（5）该企业正考虑生产一种新产品E，该产品计划售价为60万元/吨，需要0.7吨原料1，0.1吨原料2，0.2吨原料3和0.3吨原料4，是否应该生产这种新产品？

4.一软件公司需要在自主开发一种微机上使用的会计软件和接受其他公司的委托进行办公自动化软件开发之间进行抉择。如果选择自主开发，根据过去的开发经验，开发一个会计软件需要投资20万元。如果软件开发得很成功（功能好于市场上已经存在的任何类似的产品，概率为20%），他们开发的软件产品可能以100万元的价格买给一个大的软件公司；如果比较成功（好于部分市场产品，概率为60%），价格将降为50万元；如果不成功（概率为20%），则无法卖出该产品。公司若决策接受其他公司的委托开发办公自动化软件，则可从客户支付的软件开发费中获得20万元利润。该软件公司还可以出2万元聘请一个咨询公司就该产品的开发问题进行咨询。根据以往的统计，该咨询公司咨询准确性的概率（P（咨询意见|成功状态））如下表： 咨询意见 很成功 可以开发 不可开发 0.9 0.1 成功状态 成功 0.5 0.5 不成功 0.1 0.9

（1）画出完整的决策树，并根据最大期望值方法找出最优决策路线。 （2）是否请咨询公司进行咨询，其咨询意见的样本信息期望值是多少？ （3）本问题的完全信息期望值是多少？

（4）总结和比较有咨询和无咨询时该公司的最优决策的风险特征。

5.一计算机芯片厂生产的某种芯片是以10个芯片为一个批次通过两道主要工序生产出来的。大量统计表明，一个批次的芯片经过生产的第一道工序的一次加工后会有80%的批次的产品合格率为90%，有20%的批次的产品合格率为50%，合格率为90%的批次下一道工序的加工成本为1000元，而合格率为50%的批次的下一道工序的加工费将高达4000元。为避免质量差的批次进入下一道工序，工厂还可以选择以1000元的成本将芯片重新在第一个工序中再加工一次。经两次加工后的产品的合格率将稳定在90%。芯片厂还有另外一种选择，即从每批中抽检一个产品，根据抽检结果决定该批次是直接进入下一道工序，还是在第一道工序中再加工一次。抽检一个产品的检查成本为100元。

（1）芯片厂希望每个批次的加工成本最小应如何决策，画出该问题的决策树； （2）计算与抽检相关的样本信息期望值； （3）计算该问题的完全信息期望值； （4）列出该问题最优决策的风险特征表。

6.超级市场上班的员工数量如果能随商城客流量大小而调整，则可在满足一定服务质量的前提下，减少人力资源的投入，从而可以降低运作成本。某超市根据统

计，在一个典型工作日，每个时间段需要的值班员工数量如下： 9：00-11：00 30人 11：00-13：00 50人 13：00-15：00 40人 15：00-17：00 45人 17：00-19：00 60人 19：00-21：00 40人 超市员工可以选择上全时班（连续工作8小时）或上半时班（连续工作4小时），但上半时班的员工人数不能超过每一时段使用员工总数的50%。超市按工作小时付给员工工资，上全时班和上半时班的小时工资率相同，请为该超市构造一个数学模型，使每天使用的员工费用最小。

7.机器每天坏三台，维修服务效率（时间倒数）机修与机修工人数满足miu(K)=1+0.5K，机修工人200元/天，每台机器每天损失4800元。

（1） 求最优工人数使得费用最小

（2） 求最小损失费用（包括停工损失和机修费用）

8.s.t. AX≤b

L≤X≤U (1)写出对偶问题

(2)如果目标系数C变为KC,对偶解将发生什么变化

(3)如果第i个约束乘以K(大于1的数) ，对偶解是否变化，发生怎样的变化 (4)如果变量约束U乘以K，原问题将发生什么变化，怎么样的趋势 (5)如果b乘以k,对偶问题是否变化，怎样变化

9.一个制造企业使用一种原材料制造两种产品A和B，一个单位的原材料的采购成本为C元，可以制造出k1单位的产品A和k2单位的产品B，如果企业生产出x1单位的产品A，可以在市场上以P1(x1)的价格将其售出；如果企业生产出x2单位的产品B，可以在市场上以P2(x2)的价格将其售出。企业最多能够从供应商处得到的原材料的数量Z单位。企业希望能构造一个非线性规划使企业获得的利润最大化。 1、写出该问题的数学模型；

2、写出该问题的最优条件（K-T条件）

3、请解释本问题的拉格朗日乘子（对偶解）的经济含义。

10.一房地产开发商面临一个五年开发规划问题：他目前已经得到三个房地产开发项目的许可，然而由于资金和建设力量的限制，必须确定一个最优的开发计划。三个房地产开发项目的数据如下：

建设所需全部投资（万元） 3000 5000 9000 建设所需时间（年） 1 2 3 建成后每年租金收益（万元） 150 320 500 项目 A B C 每年所需建筑工人 150 250 200

项目收益应在项目建成之后获得，即：若在第一年建设项目A，项目一年建成，则收益在第二年开始获得。建设时间超过一年的项目，其建设投资平均分滩在建设周期内，开发商面临的其他限制为：

（1）每年用于建设的资金不能超过6000万元； （2）每年可以使用的建筑工人总数最多为500人；

（3）由于项目管理上的原因，每年只能允许1个项目开工，同时施工建设的项目不能超2项。

请为该开发商构造一个满足上述约束限制，并使五年内租金收益最大的整数规划模型。

11.万佳公司主要生产和销售复印机，影响复印机销售量的主要因素之一是公司能否提供快捷的维修服务。根据历年统计表明，如果维修服务机构的距离在200公里之内，销售量将会明显的提高，下表是华北地区四个主要城市在不同服务条件下一年销售复印机数量的预测。

服务机构在200公里之内 服务机构不在200公里之内 北京 1000 700 天津 800 600 石家庄 600 400 太原 500 300

每台复印机的销售利润为1万元，在每个城市设立一个服务机构每年的平均费用为80万元，各个城市之间的距离如下表所示：

北京 天津 石家庄 太原 北京 0 130 200 350 天津 130 0 330 480 石家庄 200 330 0 150 太原 350 480 150 0

请根据造能使该公司年利润最大的整数规划问题。（只写模型，不必求解）

12.一架货机有三个货舱；前舱，中舱和后舱，每个货舱货运能力的限制如下表： J 前舱 中舱 后舱 货机需要运送下列四种货物： i A B C D 重量（吨）ci 20 16 25 13 体积（立方米/吨）vi 5 7 6 4 运费（元/吨）pi 5000 7000 6000 4000 可载货重量（吨）Cj 12 18 10 舱内容积（立方米）Vj 70 90 50

为保持飞机平衡，各个货舱装货重量与能力的比例必须相同（例如，如果前舱装6吨货，占实际装货能力的50%，则中舱必须装9吨，后舱必须装5吨，也要占能力的50%）。根据运输规定，每个货仓最多只能装载两种货物，各个货舱可以按任何比例混装两种货物，请构造一个混合整数规划模型，使一架飞机在满足装载限制的前提下获得的运费最大化。

13.某连锁商业公司主要从事大型家用电器的分销业务，在一个城市设有4个零售商场，每个商场每月平均销售家用电器的数量见下表： 每月平均销售电器数量（台） 商场1 160 商场2 240 商场3 350 商场4 310 各个商场销售的电器需要由分销中心配送，因此该公司需要决策在什么地方建立分销中心。备选的地点有3个，在每个地点设立分销中心的固定成本见下表：

每月的固定成本(万元) 分销能力（台/月） 地点A 1.4 700 地点B 2.3 1200 地点C 1.1 400

从各个备选地点供应各个商场的变动分销成本（元/每台）见下表：

地点A 地点B 地点C 商场1 15 12 21 商场2 20 22 14 商场3 17 23 13 商场4 25 16 31

该公司希望设计一个使分销成本（固定成本+变动成本）最小的建设方案，并考虑以下限制条件：

（1）最多设立两个分销中心；

（2）在地点A和地点B不能同时设分销中心； 请写一个满足上述要求的整数规划模型。

14.某省政府计划在所辖地区内新建粮食仓库，从投资预算限制角度出发，考虑最多新建m个粮食仓库。这m个粮食仓库将为n个城市供应粮食，n个城市对粮食的需求分别为D1,D2……Dn。各城市都提出建设粮食仓库的申请，若在第i个城市建仓库，其存储能力上限为Si（允许建设粮食仓库的规模小于Si），建设的固定投资费用为Fi，建设单位存储能力的变动投资为Vi（变动投资与建设规模成正比）此外在i处建设需改造它与其它城市间的运输设施。改造i城市到j城市的运输设施的投资费用为Fij，改造前从第i个城市到第j个城市的最大运输能力为uij，而改造后为Uij。设在这些粮食仓库的整个使用寿命期间内，各城市的单位运价为Cij。问m个粮食仓库建设在何处才能既满足各个城市的粮食供应需求，有可以使总投资和运输费用最省？

百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库运筹学在线全文阅读。