运筹学复习题目加答案

1、一、单选题1目标函数取极小（minZ）的线性规划问题可以转化为目标函数取极大的线性规划问题求解，原问题的目标函数值等于（ ）。A. maxZ B. max(-Z) C. max(-Z) D.-maxZ2 下列说法中正确的是（）。A 基本解一定是可行解 B基本可行解的每个分量一定非负C若B是基，则B一定是可逆D非基变量的系数列向量一定是线性相关的3在线性规划模型中，没有非负约束的变量称为 （ ）A.多余变量 B松弛变量 C人工变量 D自由变量4. 当满足最优解，且检验数为零的变量的个数大于基变量的个数时，可求得（）。A多重解B无解C正则解D退化解5对偶单纯型法与标准单纯型法的主要区别是每次迭代的

2、基变量都满足最优检验但不完全满足 （ ）。A等式约束 B“”型约束 C“”约束 D非负约束6. 原问题的第个约束方程是“”型，则对偶问题的变量是（）。A多余变量B自由变量C松弛变量D非负变量7.在运输方案中出现退化现象，是指数字格的数目( )。A.等于m+n B.大于m+n-1 C.小于m+n-1 D.等于m+n-1二、判断题1线性规划问题的一般模型中不能有等式约束。 2对偶问题的对偶一定是原问题。 3产地数与销地数相等的运输问题是产销平衡运输问题。 4对于一个动态规划问题，应用顺推或逆解法可能会得出不同的最优解。 5线性规划问题的每一个基本可行解对应可行域上的一个顶点。 6线性规划问题的基本

3、解就是基本可行解。 三、填空题1如果某一整数规划：MaxZ=X1+X2X1+9/14X251/14-2X1+X21/3X1,X20且均为整数所对应的线性规划（松弛问题）的最优解为X1=3/2，X2=10/3，MaxZ=6/29，我们现在要对X1进行分枝，应该分为 和 。2如希望I的2 倍产量2恰好等于II的产量，用目标规划约束可表为：3. 线性规划解的情形有 4. 求解指派问题的方法是 。5美国的R.Bellman根据动态规划的原理提出了求解动态规划的最优化原理为 6. 在用逆向解法求动态规划时，fk(sk)的含义是：7. 知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均

4、为“”型不等式）其中X4,X5,X6为松驰变量。XBbX1X2X3X4X5X6X12110201X32/3001104X510-20116Cj-Zj000-40-9问：(1)对偶问题的最优解： （2）写出B-1=四、计算题1. 下列线性规划问题化为标准型。 满足 2. 写出下列问题的对偶问题 满足 3. 用最小元素法求下列运输问题的一个初始基本可行解 4某集团公司拟将6千万资金用于改造扩建所属的A、B、C三个企业。每个企业的利润增长额与所分配到的投资额有关，各企业在获得不同的投资额时所能增加的利润如下表所示。集团公司考虑要给各企业都投资。问应如何分配这些资金可使公司总的利润增长额最大？ 5.已

5、知运输问题的产销平衡表，最优调运方案及单位运价表分别如下表所示： 产销平衡表及最优方案 单位运价表销地产地产量51015010152555销量5151510销地产地10120111279202141618 销地产地产量51015010152555销量5151510试分析：(1) 从在什么范围变化时，上述最优调运方案不变； (2) 从从变为何值时，将有无限多最优调运方案。参考答案一、单选题1.C 2.B 3.D 4. A 5. D 6. B 7. C 二、判断题1.× 2. 3.× 4. 5 6×三、填空题1、X11 ， X12 2、3、可行解、无可行解、无界解、无

6、穷多解4、匈牙利法5、作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对先前的决策所形成的状态而言，余下的诸决策必构成最优策略。6、 从第k个阶段到第n个阶段的最优解 7、： Y(4,0,9,0,0,0)T 四、计算题1、 max(-z)= 2、 写出对偶问题maxW= 3、解： 4. 解：第一步：构造求对三个企业的最有投资分配，使总利润额最大的动态规划模型。（1）阶段k：按ABC的顺序，每投资一个企业作为一个阶段，k1，2，3，4（2）状态变量：投资第k个企业前的资金数。（3）决策变量：对第k个企业的投资。（4）决策允许集合：。（5）状态转移方程：。（6）阶段指标：见表中所示

7、。（7）动态规划基本方程： （终端条件） 第二步：解动态规划基本方程，求最有值。 k=4, k=3, 计算结果（一）11044044121044+04722077+0731244+04932177073099+094134404144227707319909401414014k=2, , 计算结果（二）21133+477131233+71010121554941333+9121432255+71231310+41451433+1417171，3，42355+914321010+717411313+417k=1, , 计算结果（三）615221420331111+1021421515+722第三步：回溯求得最优策略最有解即最优策略巍：，；，；，；返回原问题的解，即企业A投资4千万元，企业B投资1千万元，企业C投资1千万元，最大效益为22千万元。5.解：假定未知，用位势法求各空格的检验数，如下表： 销地产地10120110-3010+012920-100010-2141618-11024-1718-13-110-11欲使所有非基变量的检验数非负，则有解之得所以从的单位运价在3与10之间变化