四、某工厂在计划期内要安排生产I、Ⅱ两种产品。已知生产单位产品所需的设备台时及A、B两种原料的消耗如表所示： I Ⅱ 设备 1 2 8台时 原材料A 4 0 16kg 原材料B 0 4 12kg 该工厂每生产一件产品I可获利2百元，每生产一件产品Ⅱ可获利3百元。 (1)单纯形迭代的初始表及最终表分别如下表I、Ⅱ所示：

x1 x2 x3 x4 x5

xB 0 2 3 O 0 -Z 0 X3 8 1 2 1 O X4 16 0 X5 12 4 0 0 1 0 0 4 0 0 1 14 0 0 -3/2 -1/8 0 Xl 4 1 0 0 1/4 X5 4 0 X2 2 0 0 -2 1/2 1 0 1 1/2 -1/8 0 说明使工厂获利最多的产品混合生产方案。 (2)如该厂从别处抽出4台时的设备用于生产I、Ⅱ，求这时该厂生产产品I、Ⅱ的最优方案。 (3)确定原最优解不变条件下，产品Ⅱ的单位利润可变范围。 (4)该厂预备引进一种新产品Ⅲ，已知生产每件产品Ⅲ，需消耗原材料A、B分别为6kg，3kg使用设备2台时，可获利5百元，问该厂是否应生产该产品及生产多少?

(1)使工厂获利最多的产品混合生产方案：生产I产品4件，生产II产品2件，设备台时与原材料A全部用完，原材料B剩余4kg，此时，获利14百元。 (2)X*=(4，3,2，0，o)Tz*=17 (3)0≤C2≤4 (4)应生产产品Ⅲ，产量为2。

五、给出线性规划问题

用单纯形表求解得单纯形表如下，试分析下列各种条件变化下最优解(基)的变化：

xl x2 x3 x4 x5

-8 0 0 -3 -5 -1 xl 1 1 0 -1 4 x2 2 -1 0 1 2 -1 1 (1)分别确定目标函数中变量X1和X2的系数C1，c2在什么范围内变动时最优解不变； (2)目标函数中变量X3的系数变为6； (3)增添新的约束X1+2x2+x3≤4

-Z xB

解：(1)3/4≤C1≤3 2≤C2≤8 (2)X*=(2，0，1，0，0，T 0)Z*=10

(3)X*=(2，1，0，0，1，0)T Z*=7 (4)X*=(0，2，0，0，0，1/3)T Z*=25/3

第六章 物资调运规划运输问题

一、填空题

1．物资调运问题中，有m个供应地，Al，A2…，Am，Aj的供应量为ai(i=1，2…，m)，n个需求地B1，B2，…Bn，B的需求量为bj(j=1，2，…，n)，则供需平

衡条件为 ?ai=?bi

i?1mnj?12．物资调运方案的最优性判别准则是：当全部检验数非负时，当前的方案一定是最优方案。

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

4．若调运方案中的某一空格的检验数为1，则在该空格的闭回路上调整单位运置而使运费增加1。

5．调运方案的调整是要在检验数出现负值的点为顶点所对应的闭回路内进行运量的调整。

6．按照表上作业法给出的初始调运方案，从每一空格出发可以找到且仅能找到_1条闭回路

7．在运输问题中，单位运价为Cij位势分别用ui，Vj表示，则在基变量处有cij Cij=ui+Vj 。

nm8、供大于求的、供不应求的不平衡运输问题，分别是指_＞abi的运输问??imni?1j?1题、?ai_＜?bi的运输问题。 i?1j?110．在表上作业法所得到的调运方案中，从某空格出发的闭回路的转角点所对应的变量必为基变量。

11．在某运输问题的调运方案中，点(2，2)的检验数为负值，(调运方案为表所示)则相应的调整量应为300_。 I Ⅱ Ⅲ Ⅳ A 300 100 300 B 400 C 600 300 12.若某运输问题初始方案的检验数中只有一个负值：－2，则这个－2的含义是该检验数所在格单位调整量。

13.运输问题的初始方案中的基变量取值为正。 14表上作业法中，每一次调整1个“入基变量”。

15.在编制初始方案调运方案及调整中，如出现退化，则某一个或多个点处应填入数字0

16运输问题的模型中，含有的方程个数为n+M个。

17表上作业法中，每一次调整，“出基变量”的个数为1个。 18给出初始调运方案的方法共有三种。

19.运输问题中，每一行或列若有闭回路的顶点，则必有两个。

二、单选题

1、在运输问题中，可以作为表上作业法的初始基可行解的调运方案应满足的条件是D。

A．含有m+n—1个基变量B．基变量不构成闭回路 C．含有m+n一1个基变量且不构成闭回路D．含有m+n一1个非零的基变量且不构成闭回

2．若运输问题的单位运价表的某一行元素分别加上一个常数k，最优调运方案将B。

A．发生变化 B．不发生变化C．A、B都有可能

3．在表上作业法求解运输问题中，非基变量的检验数D。

A．大于0B．小于0C．等于0D．以上三种都可能

4.运输问题的初始方案中，没有分配运量的格所对应的变量为 B A基变量 B 非基变量 C 松弛变量 D 剩余变量

5.表上作业法的基本思想和步骤与单纯形法类似，那么基变量所在格为 C A 有单位运费格 B 无单位运费格 C 有分配数格 D 无分配数格

6.表上作业法中初始方案均为 A A 可行解 B 非可行解 C 待改进解 D 最优解

7.闭回路是一条封闭折线，每一条边都是 D A 水平 B 垂直 C水平＋垂直 D水平或垂直

8当供应量大于需求量，欲化为平衡问题，可虚设一需求点，并令其相应运价为 D

A 0 B 所有运价中最小值 C所有运价中最大值 D最大与最小运量之差

9.运输问题中分配运量的格所对应的变量为 A A基变量 B 非基变量 C 松弛变量 D 剩余变量 10.所有物资调运问题，应用表上作业法最后均能找到一个 D A 可行解 B 非可行解 C 待改进解 D 最优解 11.一般讲，在给出的初始调运方案中，最接近最优解的是 C A 西北角法 B 最小元素法 C 差值法 D 位势法

12.在运输问题中，调整对象的确定应选择 C A 检验数为负 B检验数为正 C检验数为负且绝对值最大 D检验数为负且绝对值最小

13.运输问题中，调运方案的调整应在检验数为 C 负值的点所在的闭回路内进行。

A 任意值 B最大值 C绝对值最大 D绝对值最小

14.表上作业法的基本思想和步骤与单纯形法类似，因而初始调运方案的给出就相当于找到一个 C

A 基 B 可行解 C 初始基本可行解 D最优解

15平衡运输问题即是指m个供应地的总供应量 D n个需求地的总需求量。 A 大于 B 大于等于 C小于 D 等于 三、多选题

1．运输问题的求解结果中可能出现的是ABC _。

A、惟一最优解 B．无穷多最优解 C．退化解 D．无可行解 2．下列说法正确的是ABD。

A．表上作业法也是从寻找初始基可行解开始的 B．当一个调运方案的检验数全部为正值时，当前方案一定是最佳方案C．最小元素法所求得的运输的运量是最小的 D．表上作业法中一张供需平衡表对应一个基可行解 3．对于供过于求的不平衡运输问题，下列说法正确的是ABC。

A．仍然可以应用表上作业法求解B．在应用表上作业法之前，应将其转化为平衡的运输问题C．可以虚设一个需求地点，令其需求量为供应量与需求量之差。D．令虚设的需求地点与各供应地之间运价为M(M为极大的正数)

4．下列关于运输问题模型特点的说法正确的是 ABD A．约束方程矩阵具有稀疏结构 B．基变量的个数是m+n-1个 C．基变量中不能有零 D．基变量不构成闭回路

5.对于供过于求的不平衡运输问题，下列说法正确的是 ABC A．仍然可以应用表上作业法求解 B．在应用表上作业法之前，应将其转化为平衡的运输问题

C．可以虚设一个需求地点，令其需求量为供应量与需求量之差。

D．令虚设的需求地点与各供应地之间运价为M(M为极大的正数) E. 可以虚设一个库存，令其库存量为0

三、判断表(a)(b)(c)中给出的调运方案能否作为表上作业法求解时的初始解，为什么?

(a) Bl B2 B3 B4 B5 B6 产量 30 Al 20 10 50 A2 30 20 75 A3 10 10 50 5 A4 20 20 销量 20 40 30 10 50 25 (b) (c) Bl B2 B3 B4 B5 B6 产量 Bl B2 B3 B4 产量 Al 30 30 Al 6 5 11 A2 20 30 50 A2 5 4 2 11 A3 10 30 10 25 75 A3 5 3 8 A4 20 20 销量 5 9 9 7 销量 20 40 30 10 50 25 (a)可作为初始方案； (b)中填有数字的方格数少于9(产地数+销地数－1)，不能作为初始方案；

(c)中存在以非零元素为顶点的闭回路，不能作为初始方案 四、已知某运输问题的产销平衡表。单位运价表及给出的一个调运方案分别见表(a)和(b)，判断给出的调运方案是否为最优?如是说明理由；如否。也说明理由。

表(a)产销平衡表及某一调运方案 单位运价表 销 地 B l B2 B3 B4 B5 B6 产量 产地 30 20 50 l A2 A3 A4 30 10 40 60 10 40 10 20 11 31 销量 30 50 20 40 30 11

五、给出如下运输问题

运价 销 B1 B2 B3 B4 产量 产 Al A2 A3 销量 5 3 10 4 90 1 6 9 6 40 20 10 5 7 70 30 50 80 40 200 (1)应用最小元素法求其初始方案；(2)应用位势法求初始方案的检验数，并检验该方案是否为最优方案

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

甲 乙 丙 丁 产量 1 1 2 1 4 2 3 6 9 3 4 4 销量 5 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．若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中，由61X。所在行得X则以X－X31+1／7x3+2／7x5=13／7，1行为源行的割平面方程为_277－X5≤0_。

7