北京科技大学861应用运筹学历年考研真题及详解.pdf

目录2011年北京科技大学数理学院810运筹学考研真题2011年北京科技大学数理学院810运筹学考研真题及详解2010年北京科技大学数理学院810运筹学考研真题2010年北京科技大学数理学院810运筹学考研真题及详解2008年北京科技大学应用科学学院810运筹学考研真题及答案2007年北京科技大学应用科学学院410运筹学考研真题2007年北京科技大学应用科学学院410运筹学考研真题及详解2011年北京科技大学数理学院810运筹学考研真题2011年北京科技大学数理学院810运筹学考研真题及详解北京科技大学2011年硕士学位研究生入学考试试题试题编号：810 试题名称：运筹学适用专业：系统工程说明：所有答案必须写在答题纸上，做在试题或草稿纸上无效。一、填空题（20分，每空2分）1若对偶问题为无界解，则原问题_。无可行解【答案】【解析】任一对偶问题的可行解都是原问题的上界，而原问题的任意可行解都是对偶问题的下界。若对偶问题为无界解，则原问题的目标函数，则z无解，即没有可行解。2.0.618法在2，6区间上取的初始点是_。3.528【答案】0.618法在2，6区间上取的初始点为：0.382（62）23.528。【解析】3最速下降法的搜索方向_。牛顿法的搜索方向为_。拟牛顿法的搜索方向为_。；【答案】最速下降法：【解析】可以得出，当时，下降最快。牛顿法：正定二次函数若X*是最优点，则，即搜索方向是。拟牛顿法：，4若是在处的下降方向，则需满足_。【答案】【解析】将目标函数在点处作一阶泰勒展开，可知满足条件的方向必为点的下降方向。5在一维搜索中，当为非正定二次函数时，最优步长满足_，当为正定二次函数时，最优步长_。前舱中舱后舱最大允许载重量（吨）容积（m3）200040003000540015001500【答案】【解析】6两阶段法中，若第一阶段目标函数最优值不为0，则原问题_。无可行解【答案】第一阶段目标函数值不是0，则说明最优解的基变量中含有非零的人工变量，表明原先性规划问题五可行解。【解析】7在拟牛顿算法中要求对称正定是为了保证搜索方向_。为下降方向【答案】【解析】保证搜索方向为下降方向，这就可以保证每次迭代均能使目标函数值有所改善。二、（10分）试建立下面问题的线性规划数学模型（不需要求解）有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量见表1。现有三种货物待运，已知有关数据见表2：表1表2商品数量（件）每件体积（m3/件）每件重量（吨/件）运价（元/件）A BC600 100080010 5 78 6 51000 700600问该货轮应装载三种货物各多少件，运费收入为最大？（三种商品在货舱的前、中、后舱均可装载）答：设xij表示i舱装载j获取xij件，i1，2，3分别表示前中后舱，j1，2，3分别表示A、B、C三种货物。则得下列模型三、（18分）对于线性规划问题：cj10500CBXBbx1x2x3x40 x3934100 x485201105000 x321/5014/513/510 x18/512/501/501025x23/2015/143/1410 x11101/72/7005/1425/14（1）用单纯形法求解最优解，最优值；（2）写出最优基，最优基的逆阵；（3）写出对偶规划；对偶规划的最优解。答：（1）加入松弛变量后，用单纯形表计算如下：得最优解X*1，1.5T，maxz17.5。（2）最优基是：逆阵是：销地 产地产量10163215142240922243416销量12820 销地 产地产量10（3）16632（12）1514（9）2244049221024（8）34（8）16销量12820（3）对偶规划模型为：，由最终单纯形表可知Y*5/14，25/14，maxw17.5。四、（12分）用表上作业法求解下面运输问题的最优调运方案和最小总运费：答：此问题属于运输平衡问题，则由沃格尔法得初始方案（）内数据），并检验（内数据）存在空格检验数为负，调整其所在回路，调整量min（8，12）销地 产地产量10（3）16（8）32（4）1514（9）2224049221024634（16）16销量12820 销地 产地产量384159 9 1616销量12820 产品 单位消耗 资源 资源限制劳动力 原料（单位）（单位）单位利润 8，得新的方案，并检验之所有检验数均为正。故得到最优方案。最小运费为：3109148164321634956。五、（25分）某工厂生产A，B，C三种产品，需消耗劳动力和原料两种资源，相关数据如下：设分别为A，B，C三种产品的产量，为制定最优生产计划建立如下模型：其最优单纯形表为（其中为松弛变量）：试分别就以下情况进行分析：（1）当产品A、C的单位利润在什么范围变化时，最优生产计划不变？（2）求劳动力减少的范围是多少时，原最优生产计划不变？（3）如果需增加电力的限制条件：，那么原最优生产计划是否改变？若改变，试求新的最优生产计划。答：（1）产品A单位利润变化时，时，最优生产计划不变，计算得。产品C单位利润发生变化时，解得。（2）设劳动力变化，在最优单纯形表中最优基的逆阵是：cj215000CBXBbx1x2x3x4x5x60 x4456351000 x5303450100 x6102130012150000 x485/38/310/30105/30 x540/35/37/30015/35x310/32/31/31001/34/32/30003/535/2005/1425/14则得出在最优单纯形表中，。求得，只要满足产品C的需求即可，所以劳动力减少的范围是0，15。（3）显然x36不满足新增加的约束方程，则增加一个松弛变量x6，重新利用单纯形表继续计算如下：得新的最优解，X*0，0，10/3T。六、（14分）已知线性整数规划：相应伴随规划的最优解为：，及最优单纯形表为：3/2015/143/141101/72/7（1）对进行分枝，写出相应的分枝规划（不要求求解）；（2）由最优单纯形表的第二个方程推导出割平面方程。答：（1）对进行分枝，1）将原问题分成B1，B2，其中B1中，定x21，再根据约束条件得出x1的值，并计算目标函数值z1；B1中，定x22，同样根据约束条件得出x1的值，计算z2；2）比较二者大小，选择较优者，若满足整数条件则停止分支；否则再继续对x1进行分支。（2）第二个方程是：，化为最终得割平面方程。七、（14分）用共轭梯度法求解问题：，取初始点。答：（1）；。（2），则继续计算。（3），则停止计算。得最优解。八、（13分）给定非线性规划问题：求满足KT条件的点。答：模型化成以下形式：目标函数及约束函数的梯度：，对约束条件引入乘子，则得KT条件是：为解该方程组，现考虑以下几种情形：（1），则，是KT点。（2），则，是KT点。（3），无解。（4），则，是KT点。结束。九、（12分）试用外点法求解非线性规划问题：（北京科技大学2011年研）答：构造罚函数：令得min P（X，M）的就解为。，M2/3因此得。十、（12分）试用乘子法求解非线性规划问题（取）：解：设定义拉格朗日函数于是得到解得，。2010年北京科技大学数理学院810运筹学考研真题2010年北京科技大学数理学院810运筹学考研真题及详解北京科技大学2010年硕士学位研究生入学考试试题试题编号：810 试题名称：运筹学适用专业：系统工程说明：所有答案必须写在答题纸上，做在试题或者草稿纸上无效一、选择与填空题（27分，每题3分）1若p（k）是f（X）在X（k）处的下降方向，则满足_。，【答案】【解析】若存在实数，使对于任意的均有下式成立：，就称方向点的一个下降方向。2两阶段法中，若第一个阶段目标函数最优值不为0，则原问题_。无可行解【答案】第一个阶段目标函数最优值不为0，则说明人工变量不为零，则原问题无解。【解析】3最速下降法的搜索方向_。负梯度方向【答案】【解析】若存在实数，使对于任意的均有下式成立：，就称方向点的一个下降方向。而最速下降方向即使函数值下降最快的方向，显然，负梯度方向是该方向。4在拟牛顿算法中要求H（k）对称正定是为了保证搜索方向p（k）H（k）g（k）_。下降方向【答案】尺度矩阵H（k）是正定阵是确定搜索方向的先行条件。【解析】5.Fibonacci法在2，6区间上取的初始点是_。，【答案】由Fibonacci的计算方法可知。【解析】6根据对偶解的经济含义，若天然气是资源是我国的一种稀缺能源资源，其影子价格必然是（）（A）不能确定 （B）0 （C）0 （D）0D【答案】影子价格是对系统内部资源稀缺程度的一种客观评价，某【解析】种资源的影子价格越高，说明该资源在系统内越稀缺，增加该资源的供应量对系统目标函数值贡献也越大。天然气是资源是一种稀缺能源资源，其影子价格必然大于0。7设线性规划有可行解，则此线性规划一定有（）（A）基本可行解 （B）基本可行最优解 （C）最优解（D）基本解A【答案】可行解包括基可行解与非基可行解。【解析】8设H为对称正定阵，方向P1，P2关于H共轭，则P1，P2应满足（）（A）p1Hp20 （B）p1Hp20 （C）p1Hp20 （D）p1p20C【答案】设H为对称正定阵，若p1Hp20，则方向P1，P2关于H共轭。【解析】9无约束最优化问题则问题的（）。Cj25000 CBXBb 041010006010106018320019CjZj25000 04101004560101006300212CjZj20050 020012/31/3 5601010（A）全局最优解 （B）局部最优解 （C）极点 （D）KT点B【答案】局部最优解即在x*的某邻域，满足，则称x*是函数的局部最优解。【解析】二、（20分）对于下列线性规划问题：（1）用单纯形法求解最优解，最优值；（2）写出最优基，最优基的逆阵；（3）写出对偶规划：对偶规划的最优解。答：（1）用单纯形法进行求解221002/31/3 CjZj00011/32/3 所以最优解，最优值30434。（2）最优基为最优基的逆矩阵即在最终单纯表中x3，x4，x5对应列的矩阵，即。（3）对偶规划为由互补松弛条件YXs0，XYs0。由于，所以，即对偶问题中的约束条件为严格的等式，可得，最优值为34。三、（21分）已知下列线性规划及其最优单纯形表：maxZ6x12x212x3Cj6200CBb84/31/311/300625011CjZj64/321/301/30答：（1）若，又因为，所以为使最优基不变，则，所以。（2）将c3的变化反应的最优单纯形表中，则为使最优解不变，则检验数满足，所以。（3）若增加一个新的约束条件，则新问题为Cj6212000CBb1284/31/311/30006250110012122001CjZj102040 1284/31/311/30006250110045/34/302/301CjZj102040 1224/507/511/504/5054/5017/501/516/5612/514/502/503/5CjZj0100008原问题的最优解为，代入新的约束条件，001612，故不满足新的约束条件，因此引入松弛变量x6后，新增加的约束条件变为，将此式代入最优单纯形表中。所以，此时的最优解，最优值为四、（12分）用表上作业法求解下面运输问题的最优调运方案和最小总运费：销地 产地B1B2B3B4产量A13（15）514（15）9230A2734（10）5（20）8030A398762（10）5（40）50销量15104540 销地 产地B1B2B3B4产量A115 15 30A2 1020 30A3 104050销量1510 答：此问题属于产销平衡问题，由沃格尔法计算初始可行方案如下：其中（）内为运量，内为检验数。检验数均为非负，故已得最优方案。五、（16分）已知线性整数规划：maxZ3x16x2其相应伴随规划的最优解为：（1）对x2进行分枝，写出相应的分枝规划（不要求求解）：（2）由最优单纯形表的第二个方程推导出割平面方程。答：（1）对x2进行分枝，则得问题B1和B2。规划B1_ 规划B2（2）得：；化成，最终得割平面方程。六、（14分）用牛顿法求解：minf（X）2x122x1x2x22x1x2取初始点x（1）（0，0）T。答：，为对称正定矩阵。；即极小点为。七、（14分）给定非线性规划问题求满足KT条件的点。答：求各函数梯度则得以下方程：（1）则无解（2）则，不是KT点（3）则，是KT点（4）则，不是KT点。八、（14分）使用内点法求解下列问题：解：先将该线性规划问题写成如下形式：构造障碍函数；联立解上述两个方程，得；于是得到最优解：。九、（12分）设f（x）是正定二次函数试证：若分别是在两条平行于方向p的直线上的极小点，则方向p与方向证明：与 分别是在两条平行于方向p的直线上的极小点；则有（）T，；从而（）T；又由于；则有。即方向p与方向2008年北京科技大学应用科学学院810运筹学考研真题及答案参考答案一、答：该问题的对偶规划为：二、答：图解法：单纯形法：加入松弛变量，将原问题改为标准形式为：210000301100-0123101040511001521000 21000030110032411/301/30120102/30-1/313/201/30-2/30 2100003/20011/2-3/2 27/21001/2-1/2 13/2010-1/23/2 000-1/2-1/2 用单纯形法解得：对应原点（4，0）对应图解法中的D点。得到最优解为：，对应图解法中的C点。620084/31/311/30 06-250-11 6-4/32-1/30-1/30 62120001284/31/311/300 06-250-110 012322001 三、答：（1）设代入题中给出的最优单纯形表，得若使最优解不变，则需满足：（2）最优解不变。（3）将原问题的最优解代入新增加的约束条件中，因为不满足约束条件，故原问题的最优解已不是本题的最优解。在新增约束条件中加入松弛变量得以为基变量，加入到原问题的最优单纯形表中得将上述表进行初等变换得：62120001284/31/311/300 06-250-110 0-41/34/30-2/301-10-20-400 62120001263/211001/2 012-5/23001-3/2 06-1/2-2010-3/2-12-10000-6 用对偶单纯形法迭代计算得：得到最优解为。四、答：取初始点五、答：先不考虑整数约束，解该规划问题，得最优解为：。可见它不符合整数条件，这时是问题A的最优目标函数值的上界，记作。而时，显然是问题A的一个整数可行解，这时z=0，是的一个下界，记作，即。原问题的最优解中x1是一个非整数变量的解，于是对原问题增加两个约束条件可将原问题分解为两个子问题，得到最优解为：问题问题=23/3=8=1=2=7/3=1 B1B2B3B4B5产量A11510 5 30A2 302050A3 4515 60销量1510455020140 B1B2B3B4B5uiA1 6 8-27 12-100A25100708 11 0-1A31012610 5 830-4vj689121 B1B2B3B4B5产量A115105 30因，故将 改为8，而且问题已得到整数解，那么必然存在最优整数解（2，1）。六、答：因该运输问题不是平衡问题，故加入一个虚拟销地，销量为20第一步，用沃格尔法算出初始方案为：第二步，用位势法计算非基变量的检验数第三步，因为上述初始方案中的非基变量的检验数有负数，故不是最优解，用闭合回路法对上述初始方案进行改进，得：A2 302050A3 4020 60销量1510455020140 B1B2B3B4B5uiA1 6 8 7212100A2310-2708 11 01A3812410 5 830-2vj68710-1 B1B2B3B4B5产量A115 15 30A2 10 202050A3 3030 60销量1510455020140 B1B2B3B4B5uiA1 628 7212100A2310 708 11 01A3812610 5 830-2vj66710-1 第四步，用位势法对上述改进解计算检验数，得：第五步，因为上述初始方案中的非基变量的检验数有负数，故不是最优解，用闭合回路法对上述初始方案进行改进，得：第六步，用位势法对上述改进解计算检验数，得：从上表可得出该改进解的非基变量的检验数均不为负数，故得到最优方案：A1-B1:15，-B3:15A2-B2:10，-B4:20A3-B3:30，-B4:30七、答：上述非线性规划问题等价于：设K-T点为，则K-T条件如下：为解上述方程组，考虑以下几种情形：（1）令；（2）令；（3）令；（4）令，无解。八、答：构造障碍函数九、答：设为分配给A县的救护车数，为分配给B县的救护车数量。2007年北京科技大学应用科学学院410运筹学考研真题2007年北京科技大学应用科学学院410运筹学考研真题及详解北京科技大学2007年硕士学位研究生入学考试试题试题编号：410 试题名称：运筹学 适用专业：系统工程说明：所有答案必须写在答题纸上，做在试题或草稿纸上无效。一、（13分）写出以下线性规划的对偶规划：max S=x1+x2答：二、（15分）某一线性规划问题，其目标函数为min S=-2x1-5x2-8x3，用单纯形法求解时得到某一步的单纯形表如下（其中a，b是常数，部分数据有缺失）：x1x2x3x4x5x6 14-ab020-8-1/2b0 x620003001x2ba1-62/b01/20 x48-20-1110（1）在所有的空格中填上数（其中可含常数a，b）；（2）判断以下几种情况何时成立（上表中不含人工变量）：现行解不是可行解；现行解是可行解，但无有限最优解；现行解是可行解，下一步迭代是x1进基、x2出基。答：（1）（2）情况情况情况三、（25分）某工厂生产A，B，C三种产品，需消耗劳动力和原料两种资源，相关数据如下：设x1，x2，x3分别为A，B，C三种产品的产量，为制定最优生产计划建立如下模型：其最优单纯形表为（其中x4，x5为松弛变量）：试分别就以下情况进行分析：cj215000CBXBbx1x2x3x4x5x60 x4456351000 x530345010（1）当产品A、C的单位利润在什么范围变化时，最优生产计划不变?（2）求劳动力减少的范围是多少时，原最优生产计划不变?（3）如果需增加电力的限制条件：2x1+x2+3x310，那么原最优生产计划是否改变?若改变，试求新的最优生产计划。答：（1）产品A单位利润变化时，时，最优生产计划不变，计算得产品C单位利润发生变化时，解得（2）设劳动力变化，在最优单纯形表中最优基的逆阵是,则得出在最有单纯形表中，求得，只要满足产品C的需求即可，所以劳动力减少的范围是0，15。（3）显然x3=6不满足新增加的这个约束方程，则增加一个松弛变量x6，重新利用单纯形表继续计算如下：0 x6102130012150000 x485/38/310/3010-5/30 x540/35/37/3001-5/35x310/32/31/31001/3-4/3-2/3000-3/5得新的最优解，X*=0,0,10/3T。四、（16分）试用最速下降法求解：答：，；，；，；,；。五、（16分）试用分枝定界法求解：cj3200CBXBbx1x2x3x42x25/2011/2-1/23x113/410-1/43/400-1/4-2maxZ=3x1+2x2答：先用单纯形法计算出其对应线性规划的最优解因而最优解为。因为。将原问题分解为两个子问题：B1：求得的最优解，。B2：求得的最优解，。于是。无需在分支，将B1分解为两个子问题：销地 产地B1B2B3B4产量A1-13003B3：求得的最优解，。（小于下界，舍去该枝）B4：求得的最优解，。（小于下界，舍去该枝）所以，最优解为：，。六、（15分）用表上作业法求解以下运输问题的最优调运方案和最小总运费：答：属于运输平衡问题，用沃格尔法得初始方案如下，且检验之得检验数内所示：A243246A340236销量434415销地 产地B1B2B3B4产量A103113A242246A34-1236销量434415销地 产地B1B2B3B4产量A131113A243246A313236销量434415有空格检验数为-1，则调整其所在回路继续求解得：有空格检验数为-1，则调整其所在回路继续求解得：所有空格元素都是正数，则得最优方案。七、（20分）用KT条件求下列问题的最优解：min f（X）=（x1-3）2+（x2-2）2答：将上述非线性规划化成以下形式：写出其目标函数和约束函数的梯度：,引入乘子得K-T条件如下：1）。2）。3）无解。4）；。八、（20分）用乘子法求解下列问题答：引入朗格朗日乘子，得求偏导数如下：求解得得minz=85/16。九、（10分）某农场有3万亩农田。打算种植玉米，大豆和小麦三种作物。预计秋后玉米每亩可收获500千克，售价为O24元千克；大豆每亩可收获200千克，售价为l20元千克；小麦每亩可收获300千克，售价为O70元千克。农场年初计划时考虑如下目标：P1：年终收益不低于350万元；P2：总产量不低于125万吨；P3：小麦产量以05万吨为宜；P4：大豆产量不超过02万吨；试建立该农场生产计划的数学规划模型（只建立模型，不用求解）。答：设玉米、大豆和小麦各种植x1,x2,x3亩。则按照决策者的意愿可建立模型如下：