最全的运筹学复习题及答案78213

四、把下列线性规划问题化成标准形式：

2、minZ=2x1-x2+2x3

五、按各题要求。建立线性规划数学模型

1、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示：

根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销售量分别为250，280和120件。月销售分别为

250，280和120件。问如何安排生产计划，使总利润最大。

2、某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋

90根，长度为4米的钢

筋60根，问怎样下料，才能使所使用的原材料最省?

1．某运输公司在春运期间需要24小时昼夜加班工作，需要的人员数量如下表所示：起运时间服务员数

2—6 6—10 10一14 14—18 18—22 22—2 4 8 10 7 12 4

每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数最少?

五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相当

于图解法可行域中的哪一个顶点。

六、用单纯形法求解下列线性规划问题：

七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。

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

X l X2X3X4

—10 b -1 f g

X3 2 C O 1 1／5

X l a d e 0 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 l﹡=4，Y2﹡=1，试应用对偶问题的性质求原问题的最优解。

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

八、已知线性规划问题

(1) 写出其对偶问题 (2)已知原问题最优解为X ﹡=(2，2，4，0)T

，试根据对偶理论，直接求出对偶问题

的最优解。

W* = 16

第七章 整数规划

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

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

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

7．若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中，由X 。所在行得X 1+1／7x 3+2

／7x 5=13／7，则以X 1行为源行的割平面方程为_76－71X 3－72

X 5≤0_。

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

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

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