数学13级运筹学自测试卷2

数学13级运筹学自测试卷2

一、单项选择题

1使用人工变量法求解极大化的线性规划问题时，当所有的检验数0j??,但在基变量中仍含有非零的人工变量，表明该线性规划问题 ( D )

A．有唯一的最优解 B．有无穷多最优解 C．为无界解 D．无可行解

2当线性规划的可行解集合非空时一定（ D ） A.包含原点 B.有界 C．无界 D.是凸集

3线性规划具有多重最优解是指（ B ） A.目标函数系数与某约束系数对应成比例。 B．最优表中存在非基变量的检验数为零。 C．可行解集合无界。 D．存在基变量等于零。

4使用人工变量法求解极大化线性规划问题时，当所有的检验数?j?0，在基变量中仍含有非零的人工变量，表明该线性规划问题（ C ）

A. 有唯一的最优解； B. 有无穷多个最优解；C. 无可行解；D. 为无界解

5在产销平衡运输问题中，设产地为m个，销地为n个，那么基可行解中非零变量的个数（ A ）

A. 不能大于(m+n-1)； B. 不能小于(m+n-1)； C. 等于(m+n-1)； D. 不确定。 6如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足（B ）

A. d??0 B. d??0 C. d??0 D. d??0,d??0 7下列说法正确的为（ D ）

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

C．在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数 D．如果线性规划问题原问题有无界解，那么其对偶问题必定无可行解 4.用最小元素法求初始调运方案是，运输表中数字格的个数为（D）个。 m*n B、m+n C、m*n-1 D、m+n-1

8对于第二类存储模型——进货能力有限，不允许缺货，下列哪项不属于起假设前提条件（ D ）

A 需求是连续，均匀的 B 进货是连续，均匀的

C 当存储降至零时，可以立即得到补充

D 每个周期的定货量需要一次性进入存储，一次性满足 9对于风险型决策问题，下列说法错误的是（ D ）

A 风险型决策问题是指决策者根据以往的经验及历史统计资料，可以判明各种自然 因素出现的可能性大小

B 风险型决策除了满足一般决策问题的四个条件外，还需要加一个条件：存在两个或两个以上的自然因素，并可估算所有自然因素出现的概率

C 期望值法就是决策者根据各个方案的期望值大小，来选择最优方案

D 确定型决策其实是风险型决策的一个特例，即自然因素出现的概率为0，而其他自然因素出现的概率为1的风险型决策问题

10下面哪些不是线性规划问题的标准形式所具备的（ C ）

A 所有的变量必须是非负的 B 所有的约束条件（变量的非负约束除外）必须是等式

C 添加新变量时，可以不考虑变量的正负性 D 求目标函数的最小值 11下面哪项不是求解“不确定型决策问题”的方法（ B ）

A 悲观法 B 期望值法 C 折衷法 D 最小遗憾法

12用单纯形法求解线性规划问题时引入的松弛变量在目标函数中的系数为（A）

A． 0 B.1 C.-1 D.2

13如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足（B）

??? A. d?0 B. d?0 C. d?0 D. d??0,d??0

14.在一个网络中，如果从一个起点出发到所有的点，找出一条或几条路线，以使在这样一些路线中所采用的全部支线的总长度最小，这种方法称之为( D ) A．点的问题 C.树的问题

B.线的问题 D.最小枝叉树问题

15．线性规划可行域的顶点一定是( )

A．基本可行解 B．非基本解 C．非可行解 D．最优解 16．X是线性规划的基本可行解则有( )

A．X中的基变量非零，非基变量为零 B．X不一定满足约束条件 C．X中的基变量非负，非基变量为零 D．X是最优解 17．要求不低于目标值，其目标函数是( ) A． C．

B． D．

二、填空题

1. 线性规划问题中，如果在约束条件中没有单位矩阵作为初始可行基，我们通常用增加 人工变量 的方法来产生初始可行基。

2. 当原问题可行，对偶问题不可行时，常用的求解线性规划问题的方法是 单纯形 法。

4对策行为的三个基本要素分别为局中人、策略集、赢得函数（支付函数） 5用大M法求目标函数为极大值的线性规划问题时，引入的人工变量在目标函数中的系数应为：－M

6可以作为表上作业法的初始调运方案的填有数字的方格数应为：m+n－1个(设问题中含有m个供应地和n个需求地)

8 求解运输问题时，常用的判断运输方案是否最优的方法，一个是闭合回路，另一个是位势法

11因为决策值不可能既超过目标值同时又未达到目标值，所以对于正、负偏差

d??d??0） 变量恒有（

三、判断题

判断题（共计10分，每小题1分，对的打√，错的打X） 1. 无孤立点的图一定是连通图。（ X ）

2．用单纯形法求解标准形式（求最小值）的线性规划问题时，与对应的变量都可以被选作换入变量。（ √ ） 3度为0的点称为悬挂点。 （ X ）

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

5一个图G 是树的充分必要条件是边数最少的无孤立点的图。（ X ）

6如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（ 对 ）

7单纯形法计算中，如不按最小比列原则选取换出变量，则在下一个解中至少有一个基变量的值为负。 (对 ） 8若线性规划的原问题有无穷多最优解，则其最偶问题也一定具有无穷多最优解。（ 对 ）

9运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解。 （ 错 ） 10如果运输问题的单位运价表的某一行（或某一列）元素再乘上那个一个常数k，最有调运方案将不会发生变化。 （错 ）

11目标规划模型中，应同时包含绝对约束与目标约束。 （ 错 ） 12线性规划问题是目标规划问题的一种特殊形式。 （ 错 ） 14在线性规划的图解法中，基可行解一定可以在顶点得到。（ √ ）

15运输问题解的情况有四种：无可行解；无界解；唯一最优解；无穷多最优解。（ × ）

16如果单纯形表中，某一检验数大于0，而且对应变量所在列中没有正数，则线性规划问题无最优解（√） 18线性规划问题标准型中，使目标函数达到最小值的可行解称为最优解。（ × ）

四、计算题

1. 用单纯形法解下列线性规划问题

maxZ?2x1?x2?x3 s. t. 3 x1 + x2 + x3 ? 60

x 1- x 2 +2 x 3 ? 10 x 1+ x 2- x 3 ? 20 x 1, x 2 , x 3 ?0 解：引入松弛变量x4、 x5、 x6，标准化得，

maxZ?2x1?x2?x3

s. t. 3 x1 + x2 + x3+ x4 = 60 x 1- x 2 +2 x 3 + x5 = 10 x 1+ x 2- x 3 + x6 = 0 x 1, x 2 , x 3， x4、 x5、 x6，≥0 建初始单纯形表，进行迭代运算：

CB 0 0 0 ?1 0 2 0 ?2 0 2 -1 ?3 x4 x1 x2 x4 x1 x6 Xb x4 x5 x6 b’ 60 10 20 0 30 10 10 20 10 15 5 25 2 x1 3 [1] 1 2* 0 1 0 0 0 1 0 0 -1 x2 1 -1 1 -1 4 -1 [2] 1* 0 0 1 0 1 x3 1 2 -1 1 -5 2 -3 -3 1 0.5 -1.5 -1.5 0 x4 1 0 0 0 1 0 0 0 1 0 0 0 0 x5 0 1 0 0 -3 1 -1 -2 -1 0.5 -0.5 0 x6 0 0 1 0 0 0 1 0 -2 0.5 0.5 θ 20 10* 20 7.5 --- 5* -1.5 -0.5 由最优单纯形表可知，原线性规划的最优解为： ( 15 , 5 , 0 )T

最优值为： z*=25。

2. 求解下面运输问题。

某公司从三个产地A1、A2、A3 将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示： 问：应如何调运，可使得总运输费最小?

销 地 B1 产 地 A1 A2 B2 B3 B4 产 量 25 25 50 100 A3 销 量 10 8 9 15 5 2 3 20 6 7 4 30 7 6 8 35 解： （1）最小元素法：

设xij为由Ai运往Bj的运量（i=1,2,3; j=1,2,3,4）, 列表如下：

销 地 B1 B2 B3 B4 产 量 产 地 1 25 25 2 20 5 25 3 15 30 5 50 15 20 30 35 100 销 量 所以，基本的初始可行解为：x14 =25； x22=20 ； x24 =5 ；

X31 =15； x33 =30； x34=5

其余的xij=0。

（2）求最优调运方案：

会求检验数，检验解的最优性：?11=2；?12=2；?13=3；

?21=1；?23=5；?32= - 1

会求调整量进行调整：=5 销 地 B1 B2 B3 B4 产 量 产 地 1 25 25 2 15 10 25 3 15 5 30 50 15 20 30 35 100 销 量 再次检验

能够写出正确结论

解为：x14=25 ； x22 =15 ； x24 =10 x31 =15， x32 =5 x33=30

其余的xij=0。

最少运费为： 535

3. 某种子商店希望订购一批种子。据已往经验，种子的销售量可能为500，1000，1500或2000公斤。假定每公斤种子的订购价为6元，销售价为9元，剩余种子的处理价为每公斤3元。 要求：

（1）建立损益矩阵；

（2）用悲观法决定该商店应订购的种子数。

（3）建立后悔矩阵，并用后悔值法决定商店应订购的种子数。 （1）益损矩阵如下表所示：

S1 S2 S3 S4 销 售 500 1000 1500 2000 订 购 A1 500 1500 1500 1500 1500 A2 1000 0 3000 3000 3000 A3 1500 4500 4500 －1500 1500 A4 2000 3000 6000 －3000 0 （2）悲观法：A1 ，订购500公斤。 （3）后悔矩阵如下表所示： S1 S2 S3 S4 最大后悔值 A1 0 1500 3000 4500 4500 A2 1500 0 1500 3000 3000 A3 3000 1500 0 1500 3000 A4 4500 3000 1500 0 4500 按后悔值法商店应取决策为A2或A3 ，即订购1000公斤或1500公斤。

4（15分）用表上作业法求下表中给出的运输问题的最优解。

销地 甲 乙 丙 丁 产量 产地 Ⅰ Ⅱ Ⅲ 销量 3 7 2 60 2 5 5 40 7 2 4 20 6 3 5 15 50 60 25 解：

因为销量：3+5+6+4+3=21；产量：9+4+8=21；为产销平衡的运输问题。 （1分） 由最小元素法求初始解：

销地 产地 甲 乙 丙 丁 戊 产量 4 5 9 Ⅰ 4 4 Ⅱ 3 1 1 3 8 Ⅲ 3 5 4 6 3 销量 （5分） 用位势法检验得： 销地 产地 Ⅰ Ⅱ Ⅲ 甲 10 ○11 ○3 乙 1 ○4 1 丙 4 12 ○1 ○丁 5 30 ○1 戊 7 ○12 ○3 U 0 -9 1 V 0 19 5 9 3 （7分） 所有非基变量的检验数都大于零，所以上述即为最优解且该问题有唯一最优解。 此时的总运费：minz?4?5?5?9?4?10?3?1?1?20?1?10?3?4?150。（2分）

5求下表所示效率矩阵的指派问题的最小解， 工作 A B C D E 工人 甲 乙 丙 丁 戊 12 8 7 15 14 7 9 17 14 10 9 6 12 6 7 7 6 14 6 10 9 6 9 10 9 解：

系数矩阵为：

?127979??89666????71712149? ??15146610????4107109??（3分）

?5020?2300?从系数矩阵的每行元素减去该行的最小元素，得： ?01057??9800??06362?0??2? ?4?5??

?70202??43000???经变换之后最后得到矩阵：?08350?

??118004????04143???0?0?相应的解矩阵：?0??0??10?0??1? （13分） ?0?0??由解矩阵得最有指派方案：甲—B，乙—D,丙—E，丁—C，戊—A 或者甲—B,乙—C,丙—E，丁—D，戊—A （2分） 所需总时间为：Minz=32 （2分）

6某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？ 解： 共可设计下列5 种下料方案，见下表

100000001001000

2.9 m 2.1 m 1.5 m 合计 剩余料头 方案1 1 0 3 7.4 0 方案2 2 0 1 7.3 0.1 方案3 0 2 2 7.2 0.2 方案4 1 2 0 7.1 0.3 方案5 0 1 3 6.6 0.8 设 x1,x2,x3,x4,x5 分别为上面 5 种方案下料的原材料根数。这样我们建立如下的数学模型。

目标函数： Min x1 + x2 + x3 + x4 + x5 约束条件： s.t. x1 + 2x2 + x4 ≥ 100 2x3 + 2x4 + x5 ≥ 100

3x1 + x2 + 2x3 + 3x5 ≥ 100 x1,x2,x3,x4,x5 ≥ 0

7运用单纯形法求解下面线性规划问题。

maxz?3x1?x2?3x1?5x2?15 ?

s.t?6x1?2x2?24?x,x?0?12解

（1）加入松弛变量x3,x4，上述模型可转化为

maxz?3x1?x2?3x1?5x2?x3?15 ?s.t?6x1?2x2?x4?24?x,x?0?12

cj CB 0 0 z 0 3 z x3 x1 XB x3 x4 b 15 24 0 3 4 12 3 x1 3 [6] 3 0 1 0 1 x2 5 2 1 4 1/3 0 3 x3 1 0 0 1 0 0 0 x4 0 1 0 -0.5 1/6 -0.5 θ 5 4 1.2 - 最优解x*?(4,0,0,0)T，最优值Z*?12

8已知运输问题的产销平衡表与单位运价表如下表所示

销地 产地 A1 A2 A3 销量 B1 10 16 5 5 B2 6 10 4 2 B3 7 5 10 4 B4 12 9 10 6 产量 4 9 4 试用运用伏格尔法求出初始运输方案。 解、

（1）用最小元素法求得初始可行基如下

销地 B1 B2 B3 B4 产量 产地 A1 10 3 6 × 7 × 12 1 A2 9 5 16 × 10 × 5 4 A3 5 2 4 2 10 × 10 ×

5 10 2 9 4 8 6 12 销量

（2）位势方程组为 u1+v1=10 u1+v4=12 u2+v3=5 u2+v4=9 u3+v1=5 u3+v2=4

令u1＝0，解得v1=10 v2=9 v3=8 v4=12 u2 =-3 u3 =-5 各非基变量检验数为

Δ12＝6－（0＋9）＝-3 Δ13＝7－（0＋8）＝-1 Δ21＝16－（10－3）＝9 Δ22＝10－（9－3）＝4 Δ33＝10－（8－5）＝7 Δ34＝10－（12－5）＝3

存在非基变量检验数为负，没有达到最优解

4 0 9 -3 4 -5

9 已知某运输问题的产量、销量及运输单价如表。又知B地区需要的115单位必须满足

要求：（1）列出该运输问题的产销平衡及单位运价表； （2）用最小元素法求出此运输问题的初始解。 解：（1）据题意，需大于供，需要增加一个假想的产地丁，列出产销平衡及单位运价表如下：

（2）用最小元素法求得初始解（因计算过程中最小元素有多个，可任选其一计算，计算的初始解不唯一）如下：

10求解指派问题，并求出最小费用。（15

分）

Min z =??cijxij

i?1j?144??（cij）4×4=?????1017241781222241816212522??20? ?19?19??解：用 “匈牙利法”求解。 效率矩阵表示为：

?? ?????1017241781222241816212522????行约简 20?? ?19?????19??20800524470814?列约简 ?3? 3?标号 ?2??

?2??(0)?8??0*?(0)52447(0)812??1? 1??(0)??

?0?1至此已得最优解：??0??0?100000100??0? 0??1??∴最小费用W=8+17+16+19=60

11 某厂每月需甲产品1000件，每月生产率为5000件，每批装配费为500元，每月每件产品储存费为20元，求E.O.Q及最低费用。 解：

已知C3?500,C1?20,P?5000,R?1000,将各值代入式子得：

2C3RP?E.O.Q=

C1?P?R?2?500?1000?5000?250(件)；

20??5000?1000?C0?2C1C3R?P?R?2?20?500?1000??5000?1000???16000000?4000

P5000(元)

答：每次生产批量为250件，每次生产所需装配费及储存费最低为4000元。

12、将下列线性规划问题标准化

maxZ?3x1?4x2?5x3?x1?2x2?x3?10??2x1?x2?3x3?5?x?0，j?1,2,3?j

答案：

maxZ?3x1?4x2?5x3?x1?2x2?x3?x4?10??2x1?x2?3x3?x5?5?x?0，j?1,2,?,5?j

13、求解下列线性规划

答案：

满意解X是AB线段上任意点。

15、（计算）将下述线性规划问题化为标准型

minz??x1?2x2?3x3?x1?x2?x3?7?x?x?x?3?123? ??3x1?x2?x3?5?x1,x2?0;x3为无约束?解：步骤:

(1) 用x4?x5替换x3，其中x4,x5≥0；

(2) 在第一个约束不等式≤号的左端加入松弛变量x6； (3) 在第二个约束不等式≥号的左端减去剩余变量x7； (4) 令z′= -z，把求min z 改为求max z′，即可得到该问题的标准型:

maxz?x1?2x2?3(x4?x5)?0x6?0x7?7?x1?x2?(x4?x5)?x6?x?x?(x?x)?x7?3?1245??5??3x1?x2?2(x4?x)??x1,x2,x4,x5,x6,x7?0'

16、某厂每月需甲产品1000件，每月生产率为5000件，每批装配费为500元，每月每件产品储存费为20元，求E.O.Q及最低费用。 解：

已知C3?500,C1?20,P?5000,R?1000,将各值代入式子得：

E.O.Q=

2C3RP2?500?1000?5000??250(件)；

C1?P?R?20??5000?1000?C0?2C1C3R?P?R?2?20?500?1000??5000?1000???16000000?4000

P5000(元)

答：每次生产批量为250件，每次生产所需装配费及储存费最低为4000元。

17 用单纯形求解线性规划问题，完成下表。

cj CB 2 b 8 16 12 3 0 0 0 ?i XB x1 1 4 0 x2 2 0 4 x3 1 0 0 x4 0 1 0 x5 0 0 1 ?j 解： cj 2 3 0 0 0 CB 0 0 0 XB b x1 1 4 0 2 x2 2 0 4 3 0 x3 1 0 0 0 1 x4 0 1 0 0 0 x5 0 0 1 0 ?i 4 - 3 2 x3 x4 x5 8 16 12 ?j0 2 1 x3 1? 20 3 x4 x5 16 3 4 0 0 1 0 0 1 0 0 4 - 1 4Ci?Zj

2 0 0 0 3? 4 18 将下面的线性规划化为标准型

min z??3x1?4x2?2x3?5x4

?4x1?x2?2x3?x4??2??x1?x2?3x3?x4?14??2x?3x2?x3?2x4?2 ?1

x1?0,x2?0,x3?0,x4无非负限制 解 max z???z?3x1?4x9?2x3?5x7?5x8

??4x1?x9?2x3?x7?x8?2??x1?x9?3x3?x7?x8?x5?14???2x1?3x9?x3?2x7?2x8?x6?2

x1,x3,x5,x6,x7,x8,x9?0.

19.设k1,k2是凸集，证明k1?k2是凸集

证明：?x1,x2?k1?k2,

?x1?(1??)x2?k1 ?x1?(1??)x2?k2?x1?(1??)x2?k1?k2

?k1?k2是凸集

0 3 x4 x5 16 3 4 0 0 1 0 0 1 0 0 4 - 1 4Ci?Zj

2 0 0 0 3? 4 18 将下面的线性规划化为标准型

min z??3x1?4x2?2x3?5x4

?4x1?x2?2x3?x4??2??x1?x2?3x3?x4?14??2x?3x2?x3?2x4?2 ?1

x1?0,x2?0,x3?0,x4无非负限制 解 max z???z?3x1?4x9?2x3?5x7?5x8

??4x1?x9?2x3?x7?x8?2??x1?x9?3x3?x7?x8?x5?14???2x1?3x9?x3?2x7?2x8?x6?2

x1,x3,x5,x6,x7,x8,x9?0.

19.设k1,k2是凸集，证明k1?k2是凸集

证明：?x1,x2?k1?k2,

?x1?(1??)x2?k1 ?x1?(1??)x2?k2?x1?(1??)x2?k1?k2

?k1?k2是凸集

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数学13级运筹学自测试卷2在线全文阅读。