线性规划习题(10)

l

单位运价表

Bl 30

B2 20 30

B3

B4

B5

B6

产量 50

A2 A3 A4 销量 30

10 10 40 10 20 11 11

40 60 31

50

20

40

30

五、给出如下运输问题 运价 产 Al A2 A3 销量 5 1 20 30 3 6 10 50 10 9 5 80 4 6 7 40 90 40 70 200

销

B1

B2

B3

B4

产量

(1)应用最小元素法求其初始方案；(2)应用位势法求初始方案的检验数，并检验该方案是否为最优方案

六、用表上作业法求给出的运输问题的最优解 甲 1 2 3 销量 10 16 5 5 乙 6 0 4 2 丙 7 5 10 4 丁 12 9 10 6 产量 4 9 4

甲 1 2 3 销量 4 5 1

乙 2

丙 1 3

丁

产量 4

6

9 4

2

4

6

在最优调运方案下的运输费用最小为 118。 七、名词 1、 平衡运输问题：m 个供应地的供应量等于 n 个需求地的总需求量，这样的运输问题称平衡运输问题。

2、不平衡运输问题：m 个供应地的供应量不等于 n 个需求地的总需求量，这样的运输问题称不平衡运输 问题。 第七章 整数规划 一、填空题 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 6 1 2 ／7x5=13／7，则以 X1 行为源行的割平面方程为_ － X3－ X5≤0_。 7 7 7 8．在用割平面法求解整数规划问题时，要求全部变量必须都为整数。 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．用割平面法求解 整数规划问题时，必须首先将原问题的非整数的约束系数及右端常数化为整数。