运筹学习题集(第五章)

判 断 题判断正误，如果错误请更正第五章 运输与指派问题1. 运输问题中用位势法求得的检验数不唯一。2. 产地数为3，销地数围的平衡运输中，变量组X11，X13，X22，X33，X34可作为一组基变量。3. 不平衡运输问题不一定有最优解。4. m+n-1个变量构成基变量组的充要条件是它们不包含闭合回路。5. 运输问题中的位势就是其对偶变量。6. 含有孤立点的变量组不包含有闭回路。7. 不包含任何闭回路的变量组必有孤立点。8. 产地个数为m销地个数为 n的平衡运输问题的对偶问题有m+n个约束。9. 运输问题的检验数就是对偶问题的松弛变量的值。10. 产地个数为m销地个数为 n的平衡运输问题的系数矩阵为A，则有r(A)=m+n-1。11. 用一个常数k加到运价C的某列的所有元素上，则最优解不变。12. 令虚设的产地或销地对应的运价为一任意大于0的常数C（C0），则最优解不变。13. 若运输问题中的产量或销量为整数则其最优解也一定为整数。14. 运输问题中的单位运价表的每一行都分别乘以一个非0常数，则最优解不变。15. 按最小元素法求得运输问题的初始方案，从任一非基格出发都存在唯一一个闭回路。16. 在指派问题的效率表的某行乘以一个大于零的数最优解不变。选择题在下列各题中，从4个备选答案中选出一个或从5个备选答案中选出25个正确答案。第五章 运输与指派问题1. 下列变量组是一个闭回路的有 Ax21,x11,x12,x32,x33,x23 B x11,x12,x23,x34,x41,x13 C x21,x13,x34,x41,x12 Dx12,x32,x33,x23,x21,x11 Dx12,x22,x32,x33,x23,x212. 具有M个产地N个销地的平衡运输问题模型具有特征 A有MN个变量M+N个约束 B 有M+N个变量MN个约束 C 有MN个变量M+N-1个约束 D 有M+N-1个基变量MN-M-N+1个非基变量 E 系数矩阵的秩等于M+N-13. 下列说法正确的有 A 运输问题的运价表第r行的每个cij 同时加上一个非0常数k，其最优调运方案不变。 B 运输问题的运价表的所有cij同时乘以一个非0常数k，其最优调运方案不变。 C运输问题的运价表第p列的每个cij同时乘以一个非0常数k，其最优调运方案不变。 D 输问题的运价表的所有cij同时乘以一个非0常数k，其最优调运方案变化。 E 不平衡运输问题不一定存在最优解。4. 下列结论正确的有 A 任意一个运输问题不一定存在最优解。 B 任何运输问题都存在可行解。 C 产量和销量均为整数的运输问题必存在整数最优解。 D m+n-1个变量组构成基变量的充要条件是它不包括任何闭回路。 E 运输单纯形法（表上作业法）的条件是产量等于销量的平衡问题。5. 下列说法错误的是 A 若变量B组包含有闭回路，则B中的变量对应的列向量线性无关。 B 运输问题的对偶问题不一定存在最优解。 C 平衡运输问题的对偶问题的变量非负。 D 运输问题的对偶问题的约束条件为大于等于约束。E 第i行的位势ui是第i个对偶变量。6. 有6个产地7个销地的饿平衡运输问题模型的对偶模型具有特征 A 有42个变量 B有42个约束 C 有13个约束 D 是线性规划模型 E 有13个变量7. 运输问题的数学模型属于 A 线性规划模型 B 整数规划模型 C 0-1整数规划模型 D 网络模型 E 不 属于以上任何一个模型 计算题5.1 求解下表所示的供需平衡的运输问题运价（元/吨）B1B2B3B4供应量（吨）A1912108240A214761180A35131520180需求量（吨）90120130160 1、求出使总的运费最小的最优运输方案以及最小运输费用； 2、从A1到B1的运价C11=9 在什么范围内变化，以上最优解保持不变？ 3、从A2到B3的运价C23=6 在什么范围内变化，以上最优解保持不变？解答：1、求出使总的运费最小的最优运输方案以及最小运输费用；运价（元/吨）B13B211B310B48供应量（吨）A10 -69 -112 8010 1608240A2-4 -1514 307 506 -71180A32 905 9013 -315 -1020180需求量（吨）90120130160 最优解为： X13=80 X14=160 X22=30 X23=50 X31=90 X32=90 minz=42102、从A1到B1的运价C11 3范围内变化，以上最优解保持不变；3、从A2到B3的运价5 C23 9范围内变化，以上最优解保持不变。5.2 某运输问题的供需平衡表与单位运价表如下表所示运价（元/吨）B1B2B3B4供应量（吨）A112910735A26118925A37861040需求量（吨）15203530 1、求出使总的运费最小的最优运输方案以及最小运输费用； 2、从A2到B4的运价C24=9 在什么范围内变化，以上最优解保持不变？解答：1、求出使总的运费最小的最优运输方案以及最小运输费用：运价（元/吨）B15B29B37B47供应量（吨）A10 -712 59 -310 30735A21 156 -111 108 -1925A3-1 -37 158 256 -41040需求量（吨）15203530最优运输方案为A1 至B2为5吨、A1至 B4为30吨、A2至 B1为15吨、A2至 B3为10吨、A3至 B2为15吨、A3至 B3为25吨。最小运费为695元。 2、从A2到B4的运价C24=9 在什么范围内变化，以上最优解保持不变？解：设C24* = C24+q,相应的检验数为-1-q 0,则有C24*8时，以上最优解保持不变。5.3求解下表所示的供需不平衡表的运输问题运价（元/吨）B1B2B3B4供应量（吨）A1211347A2103595A378127需求量（吨）2346 1、求出使总的运费最小的最优运输方案以及最小运输费用； 2、从A1到B1的运价C11=2 在什么范围内变化，以上最优解保持不变？解答: 1、第一种解（写出一种即可）；运价（元/吨）B12B23B33B44B50供应量（吨）A10 22 11 3 34207A20 10 33 5 9205A3-2 7 8 41 3207需求量（吨）23464 minz=35