2024--2025运筹学期末考试试题及答案

楚大2024-2025上学期经济信息管理及计算机应用系运筹学期末考试试题及答案 班级： 学号 一、单项选择题：1、在下面的数学模型中，属于线性规划模型的为（ A ）。 2、线性规划问题若有最优解，则肯定可以在可行域的 （ A ）上达到。A顶点 B内点 C外点 D几何点3、在线性规划模型中，没有非负约束的变量称为 （ C ）A多余变量 B松弛变量 C.自由变量 D人工变量4、若线性规划问题的最优解同时在可行解域的两个顶点处达到，那么该线性规划问题最优解为（ C ）。A.两个 B.零个 C.无穷多个 D.有限多个5、线性规划具有唯一最优解是指（ B ）A最优表中存在常数项为零B最优表中非基变量检验数全部非零C最优表中存在非基变量的检验数为零D可行解集合有界6、设线性规划的约束条件为 则基本可行解为（ C ）。A(0, 0, 4, 3) B (3, 4, 0, 0)C(2, 0, 1, 0) D (3, 0, 4, 0)7、若运输问题已求得最优解，此时所求出的检验数肯定是全部（ D ） A、小于或等于零 B大于零 C小于零 D大于或等于零8、对于m个发点、n个收点的运输问题，叙述错误的是( D )A该问题的系数矩阵有mn列B该问题的系数矩阵有m+n行C该问题的系数矩阵的秩必为m+n-1D该问题的最优解必唯一9、关于动态规划问题的下列命题中错误的是（ A ）A、动态规划分阶段依次不同，则结果不同B、状态对决策有影响 C、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性D、动态规划的求解过程都可以用列表形式实现10、若P为网络G的一条流量增广链，则P中全部正向弧都为G的（ D ） A对边 B饱和边 C邻边 D不饱和边 一、 推断题。1、图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一样的。（ T ） 2、单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解。（ F ）3、一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。（ T ） 4、若线性规划问题中的值同时发生变更，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行基的状况。（ F ） 5、若线性规划的原问题有无穷多最优解，则其对偶问题也肯定具有无穷多最优解。（ T ） 6、运输问题的表上作业法实质上就是求解运输问题的单纯形法。（ T ） 7、对于动态规划问题，应用顺推或逆推解法可能会得出不同的最优解。（ F ） 8、动态规划的基本方程是将一个多阶段的决策问题转化为一系列具有递推关系的单阶段的决策问题。（T ） 9、图论中的图不仅反映了探讨对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格留意。（F ） 10、网络最短路途问题和最短树问题实质上是一个问题。（F ）二、 填空题。1、线性规划中，满意非负条件的基本解称为_基本可行解_，对应的基称为_可行基_。2、线性规划的目标函数的系数是其对偶问题的_右端常数_；而若线性规划为最大化问题，则对偶问题为_最小化问题_。3、在运输问题模型中，个变量构成基变量的充要条件是_不含闭回路_。4、动态规划方法的步骤可以总结为：逆序求解_最优目标函数_，依次求_最优策略_、_最优路途_和_最优目标函数值_。5、工程路途问题也称为最短路问题，依据问题的不同分为定步数问题和不定步数问题；对不定步数问题，用迭代法求解，有_函数_迭代法和_策略_迭代法两种方法。6、在图论方法中，通常用_点_表示人们探讨的对象，用_边_表示对象之间的联系。7、线性规划的最优解是(0，6),它的第1、2个约束中松驰变量（）= （ (0,2) ）8、运输问题的检验数ij的经济含义是（ xij增加一个单位总运费增加ij ）四、计算题。1、考虑线性规划问题：（a）、写出其对偶问题；（b）、用单纯形方法求解原问题；（c）、用对偶单纯形方法求解其对偶问题；（d）、比较（b）（c）计算结果。1：解 a）、其对偶问题为 b）、用单纯形方法求解原问题时每步迭代结果：原问题解第一步其次步第三步（0，0，0，60，40，80）（0，15，0，0，25，35）（0，20/3，50/3，0，0，80/3） c）、用对偶单纯形方法求解对偶问题时每步迭代结果：对偶问题问题解第一步其次步第三步（0，0，0，-2，-4，-3）（1，0，0，1，0，-1）（5/6，2/3，0，11/6，0，0） d）、对偶问题的实质是将单纯形法应用于对偶问题的求解，又对偶问题的对偶即原问题，因此（b）、（c）的计算结果完全相同。 五、证明题：1、对问题minf（x1,x2）=x12+25x22中的变量x=(x1,x2)T作线性变换：y1=x1,y2=5x2,则原来的无约束优化问题变为： minF(y1,y2)=y12+y22证明：从随意初始点y0动身，用最速下降法问题（* *）迭代一轮即可求得最优化解，从中你可以得到什么启示？证：从随意初始点为y0=（y10,y20）T，令P0=-f(y0),则代入f(y)=(1+2t)2(y10)2+(y20)2,令df/dt=0得t0=-1/2,故y1=y0+tp0=(0,0)T为原问题的最优解，可知，若（UMP）具有 Minf(x)= Xi2形式，用最速下降法迭代一次即可求得最优解。