运筹学

运筹学试卷(1)一、回答下面问题(每小题3分)1.在单纯形法计算中,如果不按最小比值规则确定换基变量,则在下一个解中一定会出现。2.原问题无界时，其对偶问题，反之，当对偶问题无可行解时，原问题。3．已知y0为线性规划的对偶问题的最优解，若y00，说明在最优生产计划中对应的资源。4．已知y0为线性规划的对偶问题的最优解，若y0=0，说明在最优生产计划中对应的资源。5．已知线形规划问题的原问题有无穷多最优解，则其对偶问题的最优解一定是。6．m个产地n个销地的产销平衡运输问题的模型其决策变量的个数是个；基变量的个数是个；决策变量的系数列向量的特点是。7．用位势法求解运输问题，位势的含义是；行位势与列位势中有一个的取值是任意的，这是因为。8.用割平面法求解整数规划，割平面割去了；但未割去。9．按教材中的符号写出最大流问题的数学模型。10．什么是截集，何谓最小截集？二、（10分）下表是用单纯形法计算到某一步的表格，已知该线性规划的目标函数值为z=14表1cjx1x2x3x4x3x12acd0e101/51σjb-1fg（1）求a—g的值；（8分）（2）表中给出的解是否为最优解。（2分）三、（每小题6分共12分）车间为全厂生产一种零件，其生产准备费是100元，存贮费是0.05元／天·个，需求量为每天30个，而且要保证供应。（1）设车间生产所需零件的时间很短（即看成瞬时供应）；（2）设车间生产零件的生产率是50个／天。要求在（1）（2）条件下的最优生产批量Q*，生产间隔期t*和每天的总费用C*。四、（18分）某公司下属甲、乙两个厂，有A原料360斤，B原料640斤。甲厂用A、B两种原料生产x1,x2两种产品，乙厂也用A、B两种原料生产x3,x4两种产品。每种单位产品所消耗各种原料的数量及产值、分配等如下工厂甲分配原料乙分配原料产品x1x2x3x4原料AB8461016033058104200310产值（百元）43341．求各厂最优生产计划；（12分）2．问公司能否制定新的资源分配方案使产值更高？（6分）五、（10分）已知有六个村庄，相互间道路的距离如图所示，已知各村庄的小学生数为：A村50人，B村40人，C村40人，D村60人，E村50人，F村90人。现六村决定合建一所小学，问小学应建在哪村，才能使学生上学所走的总路程最短？六、（8分）A、B、C、D、E、F分别代表陆地和岛屿，1、2、3……14表示桥梁及其编号。若河两岸分别敌对的双方部队占领，问至少应切几座桥梁（具体指出编号）才能达到阻止对方部队过河的目的，试用图论方法进行分析。（提示：以陆地为点，桥梁为弧，两点之间的桥梁数为弧的容量。）七、（12分）设有三个化肥厂供应四个地区的农用化肥。各化肥的年产量，各地区的需求量，化肥的运价如下表所示，请写出产销平衡运输表。B1B2B3B4产量A11613221650ABCDEF2746381163A21214181560A3192123…50最低要求3070010最高要求457030不限运筹学试卷（2）一、一、填空（15×2分）1、在线性规划问题的约束方程AX=b,X≥0中，对于选定的基B，令非基变量XN=0，得到的解X=；若，则称此基本解为基本可行解；若，则称此基本可行解为退化的解；若，则此基可行解为最优解。2、用对偶单纯形法求解线性规划问题时，根据br确定xr为出基变量；根据最小比值法则θ=，确定xk为进基变量。3、在单纯形法的相邻两次迭代中，迭代前的可行基B和迭代后的可行基B的逆矩阵存在关系：B-1=ErkB-1其中Erk=。4、已知y*为某线形规划问题的对偶问题的最优解，若y*0，说明在最优化生产计划中对应的资源。5、平衡运输问题（m个产地，n个销地）的基可行解中基变量共有个；其中决策变量xij所对应的列向量pij=.。6、对于Max型整数规划问题，若其松弛问题的最优单纯形表中有一行数据为：XBbx1x2x3x4x23/4017/4-11/4则对应的割平面方程为。7、用匈牙利法解分配问题时，当则找到了分配问题的最优解；称此时独立零元素对应的效益矩阵为。8、将网络D=（V，A，C）的顶点集合V分割成两个非空集合V1和V1，使VS∈V1，Vt∈V1，则弧集成为分割VS和Vt的截集；称为截集的容量。二、二、问答题（2×5分）1．材写出目标规划的一般模型；2．试叙动态规划的最优性原理。三、三、已知某线性规划问题的目标函数为max=5x1+3x2,约束形式为“≤”。设x3,x4为松弛变量，用单纯形法计算是某一步的表格如下所示：（15分）Cj5300CBXBbx1x2x3x40x3c011/55x1de01-Z-10b-1fg（1）（1）求a~g的值；（2）（2）表中给出的解是否为最优解，并求出最优解。四、四、已知某线性规划问题，其初始及最优单纯形表如下：（15分）Cj12000CBXBbX1x2x3x4x50x312221000x49300110x5802001σj12000最优解表Cj12000CBXBBx1x2x3x4x51x12101/20-1/20x4300-3/213/22x2401001/2σj00-1/20-1/2(1)求出对偶问题的最优解;(2)求C1的变化范围,使最优基不变;(3)如果b1由12变为16,求最优解.五、种机器可以在高低两种不同的负荷下生产,高负荷生产时,产品的年产量g与投资的机器数量x的关系为:g(x)=8x,这时机器的年完好率a=0.7;在低负荷下生产时产品的年产量h和投入的机器数量y的关系为:h(x)=5y,这时机器的年完好率b=0.7。假定开始生产时的完好机器数量s1=1000台，试制定一个5年计划，确定每年投入高、低两种负荷下生产的完好机器数量，使5年内产品的总产品量最大，并且5年末完好的机器数量是500台。（1）（1）写出阶段变量、状态变量、决策变量；（6分）（2）（2）写出第k阶段的决策集合与状态转移方程；（9分）（3）（3）写出递推方程，并规范化求解。（选作10分）五、五、如图所示是某地区交通运输示意图，s是起点t终点，弧旁数字为cij(fij)。（15分）（1）写出此交通运输规划的线性规划数学模型；（2）用标号法求出从s到t最大流及其流量；（3）写出该网络的最小割集。运筹学试卷(3)一、一、填空(11×3分)1、在线性规划问题的约束方程AX=b,X≥0中，对于选定的基B，令非基变量XN=0，得到的解X=；若，则称此基本解为基本可行解；若，则称此基本可行解为退化的解。2、用单纯形法求解线性规划问题的迭代步骤中，根据σK=确定xk为进基变量；根据最小比值法则=，确定xr为出基变量。3、平衡运输问题（m个产地，n个销地）的基可行解中基变量共有个。4、对于Max型整数规划问题，若其松弛问题的最优单纯形表中有一行数据为：XBbx1xxxx23/4017/4-11/4则对应的割平面方程为。5、用匈牙利法解分配问题时，当则找到了分配问题的最优解；称此时独立零元素对应的效益矩阵为。6、将网络D=(V,A,C)的顶点集合V分割成两个非空集合V1和1V，使VS∈V1,Vt∈1V，则弧集成为分割VS和Vt的截集；称为截集的容量。二、二、单项选择题（3×5分）1、含有两个变量的线性规划问题若有可行解，则可行域是（）（A）全平面（B）多平面（C）凸多平面（D）凹多平面2、在目标线性规划问题中，叙述正确的选项为（）（A）（A）正偏差变量取正值，负偏差变量取负值；（B）（B）目标规划模型中，若模型有解，则一定有最优解；（C）（C）目标函数中的优先级P1，P2，P3，……之间表明数量上的重要型差别，如：P1比P2级重要10倍或20倍等；（D）（D）描写可以含系统约束（刚性约束），也可以不含。3、下列叙述中，有关树G（V，E）性质不正确的选项为（）（A）（A）无圈且不连通；（B）（B）n个顶点的树必有n-1条边；（C）（C）树中任意两点，恰有一条初等链；（D）（D）树无回路，但不相邻顶点连一条边，恰得一回路。三、已知某线性规划问题的目标函数为maxZ=5x1+3x2,约束形式为“≤”。设x3,x4为松弛变量，用单纯形法计算是某一步的表如下所示：（15分）Cj5300CBXBBx1x2x3x40x32c011/55x1ade01Z-10b-1fg（1）求a~g的值；（2）表中给出的解是否为最优解，并求出最优解。四、已知某线性规划问题，其初始及最优单纯形表如下：（15分）Cj12345CBXBbx1x2x3x4x50x312221000x49300100x5802001σj12000最优解表Cj12000CBXBbx1x2x3x4x51x12101/20-1/20x4300-3/213/22x2401001/2σj00-1/20-1/2（1）求对偶问题的最优解；（2）求C1的变化范围，使最优基不变；（3）如果b1由12变为16，求最优解。五、如图所示是某地区交通运输示意图。VS是起点，Vt是终点。（12分）（1）求出从VS到Vt的最短距径；（2）用双箭头在图上标明。六、某物资每月需供应50箱，每次订货费为60元，每月每箱的存贮费为40元。（10分）（1）若不允许缺货，且一订货就可以提货，试问每隔多少时间订购一次，每次应订购多少箱？（2）若一个周期中缺一箱的缺货损失费为40元，缺货不补，问每隔多少时间订购一次，每次应订购多少箱？运筹学习题(4)一、一、知线性规划问题（本题14分）minz=-5x1-6x2-7x3无约束，，3213213213210052010651535xxxxxxxxxxxx要求：（1）化为标准形式（7分）（2）列出用两阶段法求解时第一阶段的初始单纯形表（7分）。二、已知下表是某极大化线性规划问题的初始单纯形表和迭代计算中某一步的单纯形表，试求出表中未知数a~l的值（每个1.5分，共18分）。x1x2x3x4x5x6X5205-413(b)10X68(j)-1(k)(c)01cj-zj16-7(a)00┇┇x3(d)-1/701-3/7(5)4/7X2(e)(l)10-3/7-5/7(g)cj-zj72/70011/7(k)(i)三、已知某一运输问题的产销平衡表、单位运价表如下表所示，且表中给出一个最优调运方案（16分）。问：（1）从A2→B2的单位运价c22在什么范围内变化时，上述最优调运方案不变（8分）。（2）A2→B4的单位运价c24变为何值时，该运输问题有无穷多最优调运方案。（4分）除表中给出的方案外，至少再给出另两个不同的最优的方案。（4分）四、有十名研究生参加六门课程考试，由于每人研究方向不同，所选课程也不一样，已知每名研究生要参加考试的课程如下表所示（表中打√的为参加考试的课程）（16分）。考试安排在1月18~20日连续三天，上、下午各考一门。每名研究生都要提出希望自己每天最多只参加一门课程考试。已知要求C课程安排在19日上午，D课程必须安排在下午考，F课的考试必须安排在B、E考试之后。要求排出一张满足上述所有要求的考试日程表。上午下午1月18日1月19日1月20日五、见以下有向图，图中数字为两点间距离（16分）。要求：（1）用动态规划的方法求出A→D的最短路（8分）（2）若f2(B1)为从B1出发至D点的最短距离，写出f2(B1)的动态规划递推方程的一般表达式，并具体说明递推方程中每个符号的意义（8分）。六、选择填充题（每题4分，共20分）（1）（1）线性规划问题minz=3x1+5x23212211210,18231224yxxyxxyxx对偶变量已知其最优解为x1=2,x2=6,z*=36,则其对偶问题的最优解为.。.（①y1=3,y2=2,y3=0;②y1=0,y2=3/2,y3=1;③y1=0,y2=1,y3=4/3;④y1=3,y2=1,y3=2/3）（2）已知某个含10个节点的树图，其中9个节点的次（线度）为，1，1，3，1，1，1，3，1，3，则另一节点的次为。（①1；②4；③3；④2）（3）用