江苏大学运筹学样卷3

江苏大学《运筹学》期末考试任课老师:张怀胜考试日期:2012-06-06；班级:工业09；学号:3090804031；姓名:徐峰；上机IP:202.195.169.154；上机总得分:71题目填空题判断题选择题计算题1计算题2计算题3计算题4计算题5计算题6计算题7计算题8应用题总分题分510108988888810100得分25389848878171一、填空题（每题1分,共5分；徐峰得分:2分）1、已知线性规划maxZ=3x1+4x2+x3,x1+2x2+x3≤10,2x1+2x2+x3≤16,x1,x2,x3≥0的最优基为约束条件系数矩阵的第一、第二两列，则最优解(x1,x2)=(6,2)。√+1分2、若一个线性规划为无界解，则其对偶问题一定无可行解。√+1分3、用0-1变量x1、x2、x3分别表示A1、A2、A3的选与不选，值为1表示选中，否则为不选，则A1，A2，A3中必须选两个的表达式为x1+x2+x3≥2。×!参考答案:x1+x2+x3=24、一个可行流为最大流的充要条件是存在一个截集使其截量大于网络流的流量。×!参考答案:=5、报童模型中的损失h增加，会使得最优进货量Q0减小。×!参考答案:减少或不变-------------------------------------------------------------------------------------------------------------------------二、判断题（每题1分,共10分；徐峰得分:5分）1、在基本可行解中非基变量一定为零。(正确)√+1分2、若线性规划的原问题有无穷多最优解，则其对偶问题也一定有无穷多最优解。(错误)√+1分3、变量取0或1的规划是整数规划(正确)√+1分4、运输问题的检验数就是对偶问题的松驰变量的值。(错误)×5、最大流问题是找一条从发点到收点的路，使得通过这条路的流量最大。(正确)×6、m+n－1个变量构成基变量组的充要条件是它们不包含闭回路。(正确)√+1分7、单位存储费和订购费同时增加i%，则总成本也增加i%(错误)√+1分8、LP问题的基本可行解对应可行域的顶点。(错误)×9、定义状态时应保证各个阶段中所做的决策相互独立(错误)×10、在其他费用不变的条件下，随着单位缺货费用的增加，最优订货批量将相应增加(正确)×-------------------------------------------------------------------------------------------------------------------------三、单项选择题（每题1分,共10分；徐峰得分:3分）1、设X是一个线性规划问题的基本可行解，如果其中一个分量xj0，则：1)、只有解不退化时，xj才是一个基变量选择×2)、只有解退化时，xj才是一个基变量3)、xj是非基变量正确4)、无论解是否退化，xj一定是一个基变量2、设一目标为极大化的线性规划有最优解，其对偶解的某一个分量大于零，则该分量对应的原问题的约束条件：1)、可能是紧约束，也可能是松约束正确2)、不可能是松约束，且当右边项增加时，其目标函数值上升选择×3)、只能是紧约束，且当右边项增加时，其目标函数值下降4)、只能是松约束，且当右边项发生变化时目标函数值不会变化3、对一个求目标函数最大的混合整数规划问题，以下命题中不正确的是：选择×1)、任一可行解的目标函数值不可能大于其松弛问题的目标函数最优值正确2)、该问题可行解的个数是有限的3)、该问题可行解中可能存在不取整数值的变量4)、其松弛问题的最优解可能是该整数规划问题的最优解4、求总销量小于总产量的运输问题不需要做的是1)、虚设一个销地2)、令产地到虚设的销地的单位运费为0选择正确3)、删去一个产地√+1分4)、取虚设的销地的需求量为恰当值5、设P是图G从vs到vt的最短路，则有正确1)、P的长度等于P的每条边的长度之和2)、P的最短路长等于vs到vt的最大流量选择×3)、P的长度等于G的每条边的长度之和4)、P有n个点n-1条边6、下列关于运输问题的说法正确的是选择×1)、运输问题的对偶问题不一定存在最优解2)、平衡运输问题的对偶问题的变量非负3)、若变量组B包含有闭回路，则B中的变量对应的列向量线性无关正确4)、第i行的位势Ui是第i个对偶变量7、某商店经销某种饮料，据统计，饮料日需求量(单位：箱)的概率分布为：P(100)=0.1,P(120)=0.25,P(150)=0.35,P(180)=0.2,P(200)=0.1。每天进货一次，进价为6元/箱，零售价是9元/箱。若当天不能售完，则第二天可以4元/箱售完。为获得最大利润，商店每天应进饮料1)、120箱2)、180箱选择正确3)、150箱√+1分4)、200箱8、下例错误的说法是选择×1)、标准型的目标函数是求最小值2)、标准型的目标函数是求最大值3)、标准型的变量一定要非负正确4)、标准型的常数项非正9、在生产与存储问题中选择正确1)、状态变量为存储量，决策变量是生产量√+1分2)、状态变量为生产量，决策变量是存储量3)、阶段指标函数是从第k阶段到第n阶段的总成本4)、过程指标函数是从第k阶段到下一阶段的总成本10、已知某一求极大值的线性规划的最优目标函数值，如果加入一个新约束，则：1)、无论加入什么样的约束，最优目标函数值不会下降选择×2)、只有新约束是小于等于约束时，最优目标函数值会下降正确3)、无论加入什么样的约束，最优目标函数值不会上升4)、只有新约束是大于等于约束时，最优目标函数值会下降-------------------------------------------------------------------------------------------------------------------------四、计算题题目1:用图解法求解下列线性规划问题(题分:8，徐峰得分:8)maxz=x1+9x24x1+3x2≤123x1+2x2≤6x1-x2≥-1x1,x2≥0做题记录(见图1)：可行域见图1中灰色区域；目标函数初始线见图1中的A1B1线；结论：此LP有唯一最优解:x1=4/5,x2=9/5；目标函数最优值为maxz=17；图1:徐峰所作的图答案(见图2)：可行域见图2的灰色区域，图2中直线A1B1为目标函数等值线；此LP有唯一最优解：x1=4/5,x2=9/5,目标函数最优值为maxz=17。1图2:答案图题目2:用单纯形法求解下列线性规划问题(题分:9，徐峰得分:9)Maxz=-9x1+x2-M-5x1+6x2-+=302x1-x2+=2x1+=5做题记录(已通过标准化):列单纯形表计算如下:cj0-91000-MCBXBbx1x2x3x4x5x6-Mx630-56-10010x422-101000x55100010检验数30M-5M-96M+1-M0001x25-5/61-1/6001/60x477/60-1/6101/60x55100010检验数-5-49/601/600-1/6-M此LP为无界解参考答案,列单纯形表迭代如下：cj0-91000-MCBXBbx1x2x3x4x5x6-Mx630-56-10010x422-101000x55100010检验数-5M-96M+1-M0001x25-5/61-1/6001/60x477/60-1/6101/60x55100010检验数-49/601/600-M-1/6此LP为无界解题目3:用对偶单纯形法求解下列线性规划问题(题分:8，徐峰得分:8)Maxz=-6x1-6x2-4x1+5x2+=-20-x1+x2+=-1-4x1-x2+=-4做题记录(已通过标准化):列单纯形表计算如下:cj0-6-6000CBXBbx1x2x3x4x50x3-20-451000x4-1-110100x5-4-4-1001检验数0-6-6000-6x151-5/4-1/4000x440-1/4-1/4100x5160-6-101检验数300-27/2-3/200此LP的最优解为:X=(5,0,0,4,16),minz=30参考答案,列单纯形表迭代如下：cj0-6-6000CBXBbx1x2x3x4x50x3-20-451000x4-1-110100x5-4-4-1001检验数-6-6000-6x151-5/4-1/4000x440-1/4-1/4100x5160-6-101检验数0-27/2-3/200此LP的最优解为:X=(5,0,0,4,16)';minz=30题目4:求解下列运输问题,使总运费最小(题分:8，徐峰得分:4)单位运费与产量销量表运费B1B2B3B4产量A15714910A210157645A315919105销量8201616做题过程(加括号的为检验数,其余为运输量):第1次运输方案与检验:表1B1B2B3B4产量A182(15)(11)10A2(-3)13161645A3(8)5(18)(10)5销量8201616第2次运输方案与检验:表2B1B2B3B4产量A1()710A285161645A355销量8201616表2所示运输方案为最优,最小总运费为:457×,总运费计算错误!×,调整后的运输方案不是基本可行解!答案：.第1次运输方案与检验(加括号的数字为检验数,其余的数字为运输量或产量和销量):表1B1B2B3B4产量A182(15)(11)10A2(-3)13161645A3(8)5(18)(10)5销量8201616第2次运输方案与检验:表2B1B2B3B4产量A4(3)10(15)(11)10A585161645A6(11)5(18)(10)5销量8201616第2次检验数无负数，故第2次运输方案为最优，最小总运费为478题目5:用匈牙利法求解下列指派问题(题分:8，徐峰得分:8)完成任务所需时间表人\任务任务1任务2任务3任务4第1人810717第2人111239第3人771316第4人7667做题记录：最优指派方案为：1→1，2→3，3→2，4→4，目标函数最小值为25答案：最优指派方案为：1→1，2→3，3→2，4→4，目标函数最小值为25题目7:求下图中v1至其它各点的最短路(题分:8，徐峰得分:8)做题过程：以P表示最短路标号，T表示一般路程标号，标号过程如下：P(vs)=0，T(v3)=5，T(v4)=6，T(v2)=13，P(v3)=5，P(v3)来自于点v1;T(v5)=10，P(v4)=6，P(v4)来自于点v1;T(v7)=14，T(v6)=21，P(v5)=10，P(v5)来自于点v3;T(v6)=20，T(v8)=13，P(v2)=13，P(v2)来自于点v1;P(v8)=13，P(v8)来自于点v5;P(v7)=14，P(v7)来自于点v4;T(v6)=18，P(v6)=18，P(v6)来自于点v7;点v1到其它各点的最短路见下图:答案：标号过程如下：P(v1)=0，T(v2)=13，T(v3)=5，T(v4)=6，P(v3)=5，P(v3)来自于点v1T(v2)=13，T(v4)=6，T(v5)=10，P(v4)=6，P(v4)来自于点v1T(v2)=13，T(v5)=10，T(v6)=21，T(v7)=14，P(v5)=10，P(v5)来自于点v3T(v2)=13，T(v6)=20，T(v7)=14，T(v8)=13，P(v2)=13，P(v2)来自于点v1T(v6)=20，T(v7)=14，T(v8)=13，P(v8)=13，P(v8)来自于点v5T(v6)=20，T(v7)=14，P(v7)=14，P(v7)来自于点v4T(v6)=18，P(v6)=18，P(v6)来自于点v7点v1到其它各点的最短路见下图:题目8:求下图所示网络中v1至v8的最大流，并找出一个最小截集(题分:8，徐峰得分:7)做题记录:第1次标号:s(0,+∞),2(s,3),6(2,1),t(6,