《运筹学》试题及答案大全

《运筹学》试题及参考答案一、填空题（每空2分，共10分）1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为可行解。2、在线性规划问题中，图解法适合用于处理变量为两个的线性规划问题。3、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点，化为供求平衡的标准形式。4、在图论中，称无圈的连通图为树。5、运输问题中求初始基本可行解的方法通常有最小费用法、西北角法两种方法。二、（每小题5分，共10分）用图解法求解下列线性规划问题：1）maxz=6x1+4x20781022122121xxxxxxx，解：此题在“《运筹学》复习参考资料.doc”中已有，不再重复。2）minz=－3x1+2x20,137210422422121212121xxxxxxxxxx解：可行解域为abcda，最优解为b点。⑴⑵⑶⑷⑸⑹、⑺由方程组02242221xxx解出x1=11，x2=0∴X*=21xx=（11，0）T∴minz=－3×11+2×0=－33三、（15分）某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：ABC甲94370乙46101203602003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）2）用单纯形法求该问题的最优解。（10分）解：1）建立线性规划数学模型：设甲、乙产品的生产数量应为x1、x2，则x1、x2≥0，设z是产品售后的总利润，则maxz=70x1+120x2s.t.0300103200643604921212121xxxxxxxx，2）用单纯形法求最优解：加入松弛变量x3，x4，x5，得到等效的标准模型：maxz=70x1+120x2+0x3+0x4+0x5s.t.5,...,2,1,03001032006436049521421321jxxxxxxxxxxj列表计算如下：四、（10分）用大M法或对偶单纯形法求解如下线性规划模型：minz=5x1＋2x2＋4x30,,10536423321321321xxxxxxxxx解：用大M法，先化为等效的标准模型：maxz/=－5x1－2x2－4x3s.t.5,...,2,1,01053642353214321jyxxxxxxxxj增加人工变量x6、x7，得到：maxz/=－5x1－2x2－4x3－Mx6－Mx7s.t7,...,2,1,0105364237532164321jxxxxxxxxxxxj大M法单纯形表求解过程如下：五、（15分）给定下列运输问题：（表中数据为产地Ai到销地Bj的单位运费）B1B2B3B4siA1A2A312348765910119108015dj82212181）用最小费用法求初始运输方案，并写出相应的总运费；（5分）2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分）解：用“表上作业法”求解。1）先用最小费用法（最小元素法）求此问题的初始基本可行解：B1B2B3B4SiA112341082××A2876520××218A391011930×2010×dj82212186060∴初始方案：218B3B4A22010B2B3A3销地费用产地82B1B2A1Z=1×8+2×2+6×2+5×18+10×20+11×10=4242）①用闭回路法，求检验数：B1B2B3B4SiA112304－21082××A28－47－26520××218A39010119130×2010×dj82212186060∵34=1＞0，其余j≤0∴选34x作为入基变量迭代调整。②用表上闭回路法进行迭代调整：B1B2B3B4SiA1123－14－31082××A28－37－16520××128A3901011－1930×20×10dj82212186060调整后，从上表可看出，所有检验数j≤0，已得最优解。销地费用产地销地费用产地∴最优方案为：最小运费Z=1×8+2×2+6×12+5×8+10×20+9×10=414六、（8分）有甲、乙、丙、丁四个人，要分别指派他们完成A、B、C、D四项不同的工作，每人做各项工作所消耗的时间如下表所示：ABCD甲21097乙154148丙13141611丁415139问：应该如何指派，才能使总的消耗时间为最少？解：用“匈牙利法”求解。效率矩阵表示为：91315411161413814415791025911005324100115780541200)0(3245)0(11528)0(**541200)0(3245)0(11528)0(**行约简128B3B4A22010B2B4A382B1B2A1标号列约简√√√3210)0()0(03445)0(133)0(60**至此已得最优解：0001100000100100∴使总消耗时间为最少的分配任务方案为：甲→C，乙→B，丙→D，丁→A此时总消耗时间W=9+4+11+4=28七、（6分）计算下图所示的网络从A点到F点的最短路线及其长度。此题在“《运筹学参考综合习题》（我站搜集信息自编）.doc”中已有。解：此为动态规划之“最短路问题”，可用逆向追踪“图上标号法”解决如下：43735191257962424468515454AB1B2B3C1C2C3D1D2D3E1E2F最佳策略为：A→B2→C1→D1→E2→F此时的最短距离为5+4+1+2+2=14《运筹学》试题及答案19、简述线性规划模型主要参数（p11）（1）、价值系数：目标函数中决策变量前的系数为价值系数（2）、技术系数：约束条件中决策变量前的系数（3）、约束条件右边常数项15、简述线性规划解几种可能的结果（情形）（ppt第二章39或89页）（1）.有唯一最优解(单纯形法中在求最大目标函数的问题时，对于某个基本可行解，所有δj≤0)（2）.无可行解，即可行域为空域，不存在满足约束条件的解，也就不存在最优解了。（3）.无界解，即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小，一般来说，这说明模型有错，忽略了一些必要的约束条件（4）.无穷多个最优解，则线段上的所有点都代表了最优解（5）退化问题，基变量有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个17343201257962424468515454AB1B2B3C1C2C3D1D2D3E1E2F59147711859121414或几个基变量等于零，用图解法无退化解1、简述单纯形法的基本思路（p70）从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。17、简述线性规划中添加人工变量的前提（p85）在系数矩阵中直接找不到初始可行解，进而通过添加人工变量的方法来构造初始可行基，得出初始基本可行解10、简述线性规划对偶问题的基本性质（p122）（1）对称性（2）弱对偶性（3）强对偶性（4）最优性（5）互补松弛型原函数与对偶问题的关系1）求目标函数最大值的线性规划问题中有n个变量m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。2）原问题的目标函数中的价值系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i个价值系数就等于对偶问题中的第i个约束条件的右边常数项。3）原问题的约束条件的右边常数项为对偶问题的目标函数中价值系数。并且原问题的第i个约束条件的右边常数项就等于零对偶问题的目标函数中的第i个变量的系数。4）对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。5、运输问题是特殊的线性规划问题，但为什么不用单纯形法求解因为这类线性规划问题在结构上存在着特殊性,表上作业法根据运输问题的特点来设计的特殊的单纯形法，可以更加形象直观简单的解决运输问题。9、简述表上作业法的基本步骤（1）用最小元素法找出初始基可行解,也就是初始调运方案。对于有m个产地n个销地的产销平衡问题，则有m个关于产量的约束方程和n个关于销量的约束方程。由于产销平衡，其模型最多只有m+n-1个独立的约束方程，即运输问题有m+n-1个基变量。在m×n的产销平衡表上给出m+n-1个数字格，其相对应的调运量的值即为基变量的值。（2）求各非基变量的检验数。（3）用闭回路法来判别问题是否达到最优解。如已是最优解则停止计算，否则继续下一步。（4）用闭回路法进行基变换，确定入基变量和出基变量，找出新的基本可行解。在表上用闭回路法调整。11、简述指派问题的标准形式及数学模型（ppt或书上p179）设n个人被分配去做n件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j件工作的效率（时间或费用）为Cij(i=1.2…n;j=1.2…n)并假设Cij≥0。问应如何分配才能使总效率（时间或费用）最高？12、简述分枝定界法的基本步骤分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。基本思路：1、先求出线性规划的解2、确定整数规划的最优目标函数值z*初始上界和下界z3、将一个线性规划问题分为两枝，并求解4、修改最优目标函数上、下界5、比较与剪枝：各分枝的目标函数值中，若有小于Z者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。6、如此反复进行，直到得到Z＝Z*为止，即得最优解X*。6、简述目标规划的目标函数主要类型及其数学表达式。目标规划的目标函数只能取极小形式，即minz=f(d+,d-)，共有如下三种形式：（1）,要求恰好等于目标值，即希望决策值超过和不足目标值的部分都尽可能小，因此由函数minz=f(d++d-)；（2），要求不超过目标值，允许达不到目标值，即希望决策值不超过目标值，也希望d+越小越好，因此有minz=f（d+）;(3)要求不低于目标值，允许超过目标值，即希望决策值不低于目标值，也希望d-越小越好，因此有minz=f(d-).2、简述运筹学中背包问题的一般提法（p225）对于N种具有不同重量和不同价值的物品，在携带物品总重量限制的情况下，决定这N种物品中每一种物品多少数量装入背包内，使得装入背包物品的总价值最大。4、建立动态规划模型时，应定义状态变量，请说明状态变量的特点第一,可知性,即各阶段的状态变量的取值能直接或间接的确定；第二,能够确切的描述过程的演变且满足无后效性.7、简述动态规划数学模型要点（ppt第十章18论述题增加阶段和阶段变量）（1）分析题意，识别问题的多阶段特性，按时间或空间的先后顺序适当划分为满足递推关系的若干阶段，对分时序的静态问题要认为赋予“时段”概念；（2）正确选择状态变量，状态变量应具备两个特征：第一，可知性，即各阶段的状态变量的取值能直接或间接的确定；第二，能够确切的描述过程的演变且满足无后效性；（3）根据状态变量和决策变量的含义，正确写出状态转移方程；（4）根据题意明确过程指标函数和最优指标函数以及第k阶段指标函数的含义，并正确列出基本方程。3、简述著名的哥尼斯堡七桥难题及答案河上有7座桥，将河中的两个岛和河岸连结，如图1所示。一个散步者能否一次走遍7座桥，而且每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，