运筹学与系统分析复习题a

运筹学与系统分析复习题A

一、单项选择题（在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括 号内。错选、多选或未选均无分）。

i线性规划无可行解是指（ ）

A•第一阶段最优目标函数值等于零

C.用大M法求解时，最优解中还有非零的人工变量 A . b列元素都不小于零 C.检验数都不小于零 3下列说法正确的为（

）

B •入基列系数非正 D .有两个相同的最小比值

）

2在用对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（

B. b列元素都不大于零 D .检验数都不大于零

A .如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解 B .如果线性规划的对偶问题无可行解，则原问题也一定无可行解

C.在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值都 —定不超过其

对偶问题可行解的目标函数

D •如果线性规划问题原问题有无界解，那么其对偶问题必定无可行解 4有5个产地4个销地的平衡运输问题（ A .有9个变量 B .有9个基变量 5下列说法错误的是（

）

）

C .有20个约束 D .有8个基变量

A .将指派问题的效率矩阵每行分别乘以一个非零数后最优解不变 B .将指派问题的效率矩阵每行分别加上一个数后最优解不变 C .将指派问题的效率矩阵每个元素同时乘以一个非零数后最优解不变 D .指派问题的数学模型是整数规划模型

二、填空题

6为求解需要量大于供应量的运输问题，可虚设一个供应点，该点的供应量等于 7线形规划问题的标准形式是：目标函授是求

约束条件右侧常数项全为 ___________________ 。

____________________ 。

，约束条件全为 ______________________

8若线性规划为最大化问题，则对偶问题为 ___________________ 问题。 9动态规划模型的构成要素有

和 __________________ 。

、

、 ________________ 、 ________________

三、判断题（在正确的后面打上“V” ，在错误的后面打上“X” 。）

10图解法提供了求解线性规划问题的通用方法。

11用单纯形法求解一般线性规划时，当目标函数求最大值时，若所有的检验数都小于等于零，

最优。

（） 则问题达到 （） （） （） （）

12在单纯形表中，基变量对应的系数矩阵往往为单位矩阵。 13任何线性规划问题存在并具有惟一的对偶问题。 14对偶问题的对偶问题不一定是原问题。

15当所有产地产量和销地的销量均为整数值时，运输问题的最优解也为整数值。

16运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有惟一最优解，有

无穷多最优解，无界解，无可行解。

（）

（）

（） （） （ ） 四、

17运输问题的可行解中基变量的个数一定遵循 m + n — 1的规则。 18指派问题的解中基变量的个数为 m+ n。

19表上作业法实质上就是求解运输问题的单纯形法。

计算题

20写出下列线形规划问题的对偶问题

Min Z=2X1+2X2+4X3 s.t 2X1+ 3X2+ 5X3 > 2

3X1+ X2 + 7X3 < 3 X1+ 4X2 + 6X3 = 5 X1, X2 , X3 > 0

21有四项工作要甲，乙，丙，丁四个人去完成，每一项工作只许一个人去完成，四项工作要四个不同的人 去完成；

问：应指派每个人完成哪一项工作，使得总的消耗时间为最短？用匈牙利法求解。

工作1 工作2 工作3 工作4 消耗时间 甲 乙 丙 15 21 26 23 18 23 17 21 21 22 16 19 24 18 19 17 丁 22已知：运输问题的单价表。

（1） 用最小元素法找出初始可行解； （2） 用位势法求出初始可行解相应的检验数; （3） 求最优方案。

单位：万元 单价 甲 乙 丙 供给量 A B C 3 7 3 5 5 4 2 25 8 6 9 10 20 10 需求量 5 23某公司有资金3万元，可以向A.B.C三个项目投资，已知各项目不同投资额的相应效益值如表所示, 用动态规划方

法求解，如何分配资金可使总效益最大？

单位：万元 投资额 效益值 0 0 0 0 1 41 42 64 2 48 50 68 3 60 60 78 A B C