最全的运筹学复习题及答案 - 图文 下载本文

八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x1+3x2,约束形式为“≤”,X3,X4为松驰变量.表中解代入目标函数后得Z=10

X3 Xl —10 2 a Xl b C d X2 -1 O e X3 f 1 0 X4 g 1/5 1 (1)求表中a~g的值 (2)表中给出的解是否为最优解?

(1)a=2 b=0 c=0 d=1 e=4/5 f=0 g=-5 (2) 表中给出的解为最优解

第四章 线性规划的对偶理论

五、写出下列线性规划问题的对偶问题

1.minZ=2x1+2x2+4x3

六、已知线性规划问题

应用对偶理论证明该问题最优解的目标函数值不大于25

七、已知线性规划问题 maxZ=2x1+x2+5x3+6x4

其对偶问题的最优解为Y=4,Y2=1,试应用对偶问题的性质求原问题的最优解。

﹡l

七、用对偶单纯形法求解下列线性规划问题:

八、已知线性规划问题

T

(1) 写出其对偶问题 (2)已知原问题最优解为X﹡=(2,2,4,0),试根据对偶理论,直接求出对偶问题

的最优解。

W* = 16

第七章 整数规划

一、填空题 1.用分枝定界法求极大化的整数规划问题时,任何一个可行解的目标函数值是该问题目标函数值的下界。 2.在分枝定界法中,若选Xr=4/3进行分支,则构造的约束条件应为X1≤1,X1≥2。

3.已知整数规划问题P0,其相应的松驰问题记为P0’,若问题P0’无可行解,则问题P。无可行解。 4.在0 - 1整数规划中变量的取值可能是_0或1。

5.对于一个有n项任务需要有n个人去完成的分配问题,其 解中取值为1的变量数为n个。 6.分枝定界法和割平面法的基础都是用_线性规划方法求解整数规划。

7.若在对某整数规划问题的松驰问题进行求解时,得到最优单纯形表中,由X。所在行得X1+1/7x3+2

612/7x5=13/7,则以X1行为源行的割平面方程为_-X3-X5≤0_。

7778.在用割平面法求解整数规划问题时,要求全部变量必须都为整数。

9.用割平面法求解整数规划问题时,若某个约束条件中有不为整数的系数,则需在该约束两端扩大适当倍数,将全部系数化为整数。

10.求解纯整数规划的方法是割平面法。求解混合整数规划的方法是分枝定界法_。 11.求解0—1整数规划的方法是隐枚举法。求解分配问题的专门方法是匈牙利法。 12.在应用匈牙利法求解分配问题时,最终求得的分配元应是独立零元素_。

13.分枝定界法一般每次分枝数量为2个. 二、单选题

1.整数规划问题中,变量的取值可能是D。

A.整数B.0或1C.大于零的非整数D.以上三种都可能

2.在下列整数规划问题中,分枝定界法和割平面法都可以采用的是A 。

A.纯整数规划B.混合整数规划C.0—1规划D.线性规划 3.下列方法中用于求解分配问题的是D_。

A.单纯形表B.分枝定界法C.表上作业法D.匈牙利法 三、多项选择

1.下列说明不正确的是ABC。

A.求解整数规划可以采用求解其相应的松驰问题,然后对其非整数值的解四舍五入的方法得到整数解。B.用分枝定界法求解一个极大化的整数规划问题,当得到多于一个可行解时,通常任取其中一个作为下界。C.用割平面法求解整数规划时,构造的割平面可能割去一些不属于最优解的整数解。D.用割平面法求解整数规划问题时,必须首先将原问题的非整数的约束系数及右端常数化为整数。 2.在求解整数规划问题时,可能出现的是ABC。

A.唯一最优解B.无可行解 C.多重最佳解D.无穷多个最优解 3.关于分配问题的下列说法正确的是_ ABD。

A.分配问题是一个高度退化的运输问题B.可以用表上作业法求解分配问题 C.从分配问题的效益矩阵中逐行取其最小元素,可得到最优分配方案D.匈牙利法所能求解的分配问题,要求规定一个人只能完成一件工作,同时一件工作也只给一个人做。 4.整数规划类型包括( CDE )

A 线性规划 B 非线性规划 C 纯整数规划 D 混合整数规划 E 0—1规划 5.对于某一整数规划可能涉及到的解题内容为( ABCDE )

A 求其松弛问题 B 在其松弛问题中增加一个约束方程 C 应用单形或图解法D 割去部分非整数解 E多次切割 三、名词

1、纯整数规划:如果要求所有的决策变量都取整数,这样的问题成为纯整数规划问题。

2、0—1规划问题:在线性规划问题中,如果要求所有的决策变量只能取0或1,这样的问题称为0—1规划。

3、混合整数规划:在线性规划问题中,如果要求部分决策变量取整数,则称该问题为混合整数规划。 四、用分枝定界法求解下列整数规划问题:(提示:可采用图解法) maxZ=40x1+90x2