远程运筹学模拟考试题C答案

《运筹学》模拟试卷C一、填空题（每空3分3×10=30总30分）1、线性规划问题如果没有最优解，则单纯形计算表的终点表中必然有_存在一个大于零的检验数，并且该列的系数向量的每个元素都小于或等于零________；2、用分枝定界法求解纯整数规划问题的过程可以大概分为以下三步：第一步：用单纯形法求相应的线性规划问题_的解,如果有解且不满足纯整要求,转下步第二步:建立整数规划的上、下界_增加约束条件（分支）_并加入线性规划问题,转下步第三步:用_缩小上下界的距离方法定界,确定下一个问题,然后转第一步。3、对偶问题的性质有(至少答三个)：1.对称性（即对偶问题的对偶是原问题）_2.弱对偶性__3_最优性4。强对偶性。5互补松驰性4.线性规划问题求解的优点中有_收敛快；步骤机械化，易于使用计算机操作_，缺点有_当有无穷多最优解时，通常只得到其中的一个解。所见模型变量不多，但约束却很多。常需要灵敏度分析。5.对偶价格是指_在某种资源增加一个单位而使最优目标函数值得到改善的数量_。二．用图解法求解线性规划问题（15分）X235A121212125235155210..,0MaxZxxxxxxstxx解：在平面上画出基础可行域如图所示。在可行域内移动目标函数取值线，可看出最优解在图中AB线上处取得（无穷多解）。其中一个最优解是0,221xx，最优值是5Z。三、用单纯形法求解线性规划问题的解：(20分)121212125235155210..,0MaxZxxxxxxstxx解：引入松驰变量化成标准形，初始单纯形表为及单纯形迭代如下：迭代次数基变量CB1x2x3x4xb比值ijjab2510003x035101553154x0（5）201102510j25100Z=013x0051915391x251520512j000-2Z=5得到最优解是：0,221xx，最优值Z=5。由于非基变量2x的检验数为零，故最优解有无穷多个。四已知线性规划问题：(20分)12121211222227..3,0MaxZxxxxxxstxxx的最终单纯形表为：CB基1x2x3x4x5xb22x11x03x0101212510001300112323σ000-1-2(1)写出其对偶规划(6分)(2)若右端项变为2122b,其最优基是否变化?(6分)求出变化后的最优解及其最优目标值.(8分)解：（1）对偶规划是0,,2212..72min3212132121yyyyyyyytsyyZ（2）当2122372bb变为时，最优解会变化，因原最优解5,321xx约束条件,2,311xx变成了用单纯法求变化后的线性规划问题基变量CB1x2x3x4x5xb比值12000ijjab3x0-2（1）10022124x0-120101262125x0100012j12000Z=02x2-2110024x030-2108385x0（1）00012212j50-200Z=42x20110264x000-21-321x1100012j00-20-5Z=14故最优解为6,221xx，最优值为Z=14五.用表上作业法求解下列运输问题的解（15分）单位运价产地甲乙丙丁产量137644销地224322343854销量3322解：用最小元素法得到初始基可行解为：1B2B3B4B供应量1A317614242A2243223A4338154需求量3322即；1,3,2,2,1,1333221141311xxxxxx，总运费38由位势法求检验数：,2,4,6,312413111vuvuvuvu8,33323vuvu；令,01u得2,1,4,6,1,3324321uuvvvv从而求得检验数为：1,1,1,2,4,6343124232212由于检验数中有负值，故此解不是最优解。选取23x为入基变量，由闭回路法13x为出基变量，得到另一个解为：1B2B3B4B供应量1A32764242A21431223A4338154需求量33221,3,1,2,1,2333221142311xxxxxx，总运费36，再求检验数：,2,4,3,312413211vuvuvuvu8,33323vuvu令,01u得4,1,4,4,1,3324321uuvvvv从而检验数为2,3,1,2,6,3343124132212由于检验数中有负值，故此解不是最优解。选取31x为入基变量，由闭回路法33x为出基变量，得到另一个解为：1B2B3B4B供应量1A32764242A20432223A4133854需求量33220,3,1,2,2,2213231142311xxxxxx，总运费33，再求检验数：2,3,4,3,4,3122313324111vuvuvuvuvuvu令,01u得：1,1,4,4,2,3324321uuvvvv从而检验数为0,,3,0,2,3,5343324132212，从而得最优解。