北京交通大学《运筹学》考试试卷及答案

北京交通大学《运筹学》考试试卷及答案考试时间：______分钟总分：______分姓名：______一、选择题（每小题2分，共10分。请将正确选项的字母填在题后的括号内）1.下列说法中，正确的是（）。A.可行解是满足所有约束条件的解。B.最优解是可行解中目标函数值最好的解。C.基本解一定是可行解。D.对偶问题的对偶就是原问题。2.在单纯形法迭代中，若某非基变量的检验数为负，则（）。A.当前解已是最优解。B.当前解不是最优解，且可以改进。C.当前解不可行。D.需要引入人工变量。3.用大M法求解线性规划问题时，人为引入的变量在最终最优解中（）。A.必须为正。B.必须为零。C.可以为正也可以为零。D.没有取值限制。4.某线性规划问题的对偶问题是求一组变量的最大值，则原问题（）。A.也是求一组变量的最大值。B.是求一组变量的最小值。C.是求一组变量的最小值或最大值，取决于具体问题。D.是一个整数规划问题。5.在运输问题的表上作业法中，若某次迭代后，在非最优空格处的检验数γij<0，则（）。A.当前解已是最优解。B.当前解不是最优解，需要调整方案。C.当前解不可行。D.需要增加一个约束条件。二、填空题（每小题2分，共10分。请将答案填在题中的横线上）6.线性规划模型的标准形式要求目标函数实现__________，约束条件均为__________。7.在单纯形表中，若某基变量的值为负数，则该解__________。8.若线性规划原问题的对偶问题有最优解，则原问题也一定有__________。9.在图论中，连接两个顶点的线段称为__________，无方向的有向线段称为__________。10.动态规划方法的核心思想是__________。三、计算题（共60分）11.（10分）用单纯形法求解以下线性规划问题：MaxZ=3x1+5x2s.t.x1+x2≤42x1+x2≤6x1,x2≥012.（10分）用两阶段法求解以下线性规划问题：MaxZ=x1+2x2s.t.x1+x2≥3x1+x2≤4x1-x2≤1x1,x2≥013.（10分）已知某物资从三个产地A1,A2,A3运往四个销地B1,B2,B3,B4。产地的产量分别为30吨，50吨，20吨；销地的需求量分别为40吨，30吨，20吨，10吨。单位运价（元/吨）如下表所示（表中未列出的运价为M，表示产销地之间不直接运输）：||B1|B2|B3|B4||:----|:-:|:-:|:-:|:-:||A1|3|11|3|10||A2|1|9|2|8||A3|7|4|10|5|试用表上作业法求该物资的最优运输方案（最小总运费）。14.（10分）用Dijkstra算法求图G中从顶点v1到其余各顶点的最短路径及其距离。（图G的顶点和边及其权值请自行设定，需包含至少6个顶点，边权值大于0且无负权值边）15.（20分）某工厂计划用三个月生产三种产品A,B,C。每种产品的生产都需要经过两道工序，每件产品在各道工序上的耗时（小时/件）及三个月内各道工序的总可用工时（小时）如下表所示：|产品|工序1耗时|工序2耗时||:---|:--------:|:--------:||A|1|2||B|1.5|1||C|2|1.5|三个月的总可用工时分别为：工序1，180小时；工序2，150小时。若产品A的售价为40元/件，产品B为30元/件，产品C为50元/件。假设产品只生产不存储，且生产数量必须为整数。问如何安排三个月的生产计划，才能使工厂的总收入最大？请建立该问题的整数规划模型，并写出目标函数和约束条件。---试卷答案一、选择题1.B2.B3.B4.B5.B二、填空题6.最大值；等式7.不可行8.最优解9.边；弧10.最优化原理（或贝尔曼最优性原则）三、计算题11.解：引入松弛变量x3,x4，化为标准型：MaxZ=3x1+5x2s.t.x1+x2+x3=42x1+x2+x4=6x1,x2,x3,x4≥0单纯形表：|基变量|Z|x1|x2|x3|x4|RHS||:-----|:-:|:-:|:-:|:-:|:-:|:-:||Z|1|-3|-5|0|0|0||x3|0|1|1|1|0|4||x4|0|2|1|0|1|6||--------|---|----|----|----|----|-----||Z|1|0|-2|3|0|12||x2|0|1|1|1|0|4||x4|0|1|0|-1|1|2|检验数已无负值，停止迭代。最优解：x1=0,x2=4最优值：Z=20解析思路：1.将原线性规划问题化为标准形式，引入松弛变量。2.建立初始单纯形表，选择Z行和RHS列确定进入基变量（选择系数最大的负检验数对应的变量，此处为x2）。3.在x2列中，计算RHS元素与对应正系数之比，选择最小比值确定离开基变量（此处x3列的比值为4/1=4，最小，离开基变量为x3）。4.进行旋转运算（以x2行和x4列交叉处的1为中心），将进入基变量x2的检验数变为0，并使离开基变量x3所在的检验数以及其所在行的其他系数变为0。5.检查新的单纯形表中所有检验数，若均非负，则得最优解；否则，回到步骤2继续迭代。6.从最终单纯形表中读出最优解（基变量取值为RHS列对应值，非基变量取值为0）和最优目标函数值。12.解：首先将不等式约束改为等式约束，引入剩余变量x3,x4,x5：MaxZ=x1+2x2s.t.x1+x2-x3=3x1+x2+x4=4x1-x2+x5=1x1,x2,x3,x4,x5≥0第一阶段：加入人工变量a1,a2,a3，求人工变量之和的最小值。MinW=a1+a2+a3s.t.x1+x2-x3+a1=3x1+x2+x4+a2=4x1-x2+x5+a3=1x1,x2,...,a3≥0单纯形表（第一阶段）：|基变量|W|x1|x2|x3|x4|x5|a1|a2|a3|RHS||:-----|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:||W|1|1|1|-1|0|0|1|1|1|8||a1|0|1|1|-1|0|0|1|0|0|3||a2|0|1|1|0|1|0|0|1|0|4||a3|0|1|-1|0|0|1|0|0|1|1||--------|---|----|----|----|----|----|----|----|----|-----||W|1|0|0|-1|-1|-1|1|1|1|3||x2|0|1|1|-1|0|0|1|0|0|3||a2|0|0|0|1|1|0|-1|1|0|1||a3|0|0|-2|0|0|1|-1|0|1|-2|检验数已无正数，第一阶段最优解W=3，且人工变量a2=1，a3=-2。由于存在负的人工变量，原问题无解。解析思路：1.将原问题的不等式约束转化为等式约束，引入剩余变量。2.检查约束条件是否为标准型（右端项非负）。若不是，需通过变量变换或调整基变量。3.在第一阶段目标函数中引入人工变量，目标是最小化人工变量之和。4.建立第一阶段单纯形表，进行迭代，使人工变量出基，同时使W的值非正。5.检查最终第一阶段单纯形表：若人工变量均为0，则转第二阶段；若存在正的人工变量，则原问题无解。6.*（本例中，由于a2和a3不能同时为0，故原问题无解）*13.解：（1）检查产销平衡：总产量=30+50+20=100吨，总需求=40+30+20+10=100吨，产销平衡。（2）用最小元素法确定初始基可行解：i=1,j=1:c11=3最小，x11=min(30,40)=30,dA1=30,dB1=10i=1,j=3:c13=3次小，x13=min(20,10)=10,dA3=10,dA1=0i=2,j=2:c22=9次小，x22=min(50,30)=30,dA2=20,dB2=0i=2,j=4:c24=8次小，x24=min(20,10)=10,dA2=10,dA4=0i=3,j=2:c32=4最小，x32=min(20,30)=20,dA3=0,dB2=0基可行解：x11=30,x13=10,x22=30,x24=10,x32=20。非基变量x12=0,x14=0。总运费=3*30+3*10+9*30+8*10+4*20=480元。（3）用闭回路法检验非基变量x12：可行调整量θ=min(30,10,20,10)=10。沿闭回路调整：x12←x12+θ=0+10=10x11←x11-θ=30-10=20x22←x22-θ=30-10=20x14←x14+θ=0+10=10新解：x11=20,x12=10,x13=10,x22=20,x24=10,x32=20。总运费=3*20+11*10+3*10+9*20+8*10+4*20=490元。闭回路中，负环上的检验数γ12=(c11-c12)+(c22-c14)=3-11+9-8=-7<0，需继续调整。（4）用闭回路法检验非基变量x14：当前解：x11=20,x12=10,x13=10,x22=20,x24=10,x32=20。x14的闭回路顶点：(x14,x24,x22,x12,x14)。对应变量为x14,x24,x22,x12。可行调整量θ=min(10,10,20,10)=10。沿闭回路调整：x14←x14+θ=0+10=10x24←x24-θ=10-10=0x22←x22-θ=20-10=10x12←x12-θ=10-10=0新解：x11=20,x12=0,x13=10,x22=10,x24=0,x32=20。总运费=3*20+3*10+9*20+8*0+4*20=490元。闭回路中，负环上的检验数γ14=(c14-c24)=-8<0，需继续调整。（5）用闭回路法检验非基变量x24：当前解：x11=20,x12=0,x13=10,x22=10,x24=0,x32=20。x24的闭回路顶点：(x24,x14,x12,x11,x22,x24)。对应变量为x24,x14,x12,x11,x22。可行调整量θ=min(10,10,20,20,10)=10。沿闭回路调整：x24←x24+θ=0+10=10x14←x14-θ=10-10=0x12←x12-θ=0-10=-10（不可行）x11←x11-θ=20-10=10x22←x22-θ=10-10=0检验发现调整量θ过大导致x12为负。需重新计算θ：θ=min(10,10,20,20)=10。沿闭回路调整：x24←x24+θ=0+10=10x14←x14-θ=10-10=0x12←x12-θ=0-10=0x11←x11-θ=20-10=10x22←x22-θ=10-10=0新解：x11=10,x12=0,x13=10,x22=0,x24=10,x32=20。总运费=3*10+3*10+9*0+8*10+4*20=490元。所有非基变量的检验数非负（或闭回路检验数非负），最优解已找到。最优运输方案：A1运B110吨，运B310吨；A2运B20吨，运B410吨；A3运B220吨。最小总运费为490元。解析思路：1.检查产销平衡，若不平衡需添加虚设产地或销地。2.采用最小元素法给出一个初始基可行解（初始调运方案）。3.计算各非基变量的检验数（闭回路法是常用方法）。4.若存在负检验数，则从未检验过的负检验数对应的变量开始，构造闭回路，计算可行调整量θ。5.沿闭回路进行调整：沿负环方向减去θ，沿正环方向加上θ。6.用新的调运方案重新计算所有未检验非基变量的检验数。7.重复步骤3-6，直到所有非基变量的检验数均非负（或闭回路检验数均非负），此时得到最优解。14.解：（示例图）设图G如下：顶点：v1,v2,v3,v4,v5,v6边及权值：v1-v2:5v1-v3:3v2-v3:4v2-v4:6v3-v4:2v3-v5:7v4-v5:1v4-v6:8v5-v6:9求v1到各顶点的最短路径及距离。Dijkstra算法步骤：初始化：S={v1},D={d(v2)=∞,d(v3)=∞,d(v4)=∞,d(v5)=∞,d(v6)=∞}d(v1)=0Π(vj)=NULL(j≠1)i=1:v1∈Sv2:d(v2)=5<∞,更新d(v2)=5,Π(v2)=v1v3:d(v3)=3<∞,更新d(v3)=3,Π(v3)=v1v4:d(v4)=6<∞,更新d(v4)=6,Π(v4)=v1v5,v6:d(v5)=∞,d(v6)=∞未更新点中最小d值是d(v3)=3,v3入S.S={v1,v3}i=2:v3∈Sv2:在v2∈S之前已更新d(v2)=5,不变v4:在v2∈S之前已更新d(v4)=6,v3-v4边权2<d(v4)=6,更新d(v4)=5,Π(v4)=v3v5:d(v5)=7>v3-v5边权7,不变v6:d(v6)=∞>v3-v5边权7(修正：应为v3-v6,权值假设为4),d(v6)=4,Π(v6)=v3未更新点中最小d值是d(v2)=5,v2入S.S={v1,v3,v2}i=3:v2∈Sv4:在v3∈S之后已更新d(v4)=5,不变v5:d(v5)=7>v2-v5边权1(修正：图中无v2-v5边),不变v6:在v3∈S之后已更新d(v6)=4,不变未更新点中最小d值是d(v4)=5,v4入S.S={v1,v3,v2,v4}i=4:v4∈Sv5:d(v5)=7>v4-v5边权1,更新d(v5)=6,Π(v5)=v4v6:在v4∈S之后已更新d(v6)=4,不变未更新点中最小d值是d(v5)=6,v5入S.S={v1,v3,v2,v4,v5}i=5:v5∈Sv6:d(v6)=4<v5-v6边权9(修正：图中无v5-v6边),不变所有顶点已加入S，算法结束。结果：v1到v2的最短路径：v1-v2，距离：5v1到v3的最短路径：v1-v3，距离：3v1到v4的最短路径：v1-v3-v4，距离：5v1到v5的最短路径：v1-v3-v4-v5，距离：6v1到v6的最短路径：v1-v3-v6，距离：4解析思路：1.初始化：选择起始点v1，S集合包含v1，其他顶点距离设为无穷大（除起点为0），路径predecessorΠ设为空。2.循环处理：对于当前集合S中的每个顶点vi，考察其邻接顶点vj（不在S中），计算通过vi到达vj的距离d(vj)=d(vi)+