运筹学试卷和答案1.docVIP

试 题 填空（每题4分，共20分） 1. 线性规划问题MaxZ=CX；AX=b，X≥0（A为kxl的矩阵，且lk）的基的最多个数为___，基的可行解的最多个数为_____. 2.指派问题的最优解的性质________________________________ ___________________________________________________________________________. 3.线性规划问题的所有可行解构成的集合是__________,它们有有限个______________________,线性规划问题的每个基可行解对应可行域的___________,若线性规划问题有最优解，必在______________得到。 4影子价格的经济含义______.在完全市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应_____该资源，而当某种资源的市场价格高于影子价格时，则企业应___该资源，可见影子价格对市场有____作用。 5. 运输问题的产销平衡表中有m个产地n个销地，其决策变量的个数有____个，其数值格有____个 计算（共60分） 1． 对下列线性规划问题 Max z=2x1+x2+3x3 x1+ x2+2x3 ≤5 s.t. 2x1+3x2+4x3＝12 x1, x2, x3≥0 写出其对偶问题；（5分） 已知（3，2，0）T是上述问题的最优解，根据互补松弛理论求出对偶问题的最优解；（10分） 2. （15分）运用单纯形法求解下面线性规划问题。 3． （15分）已知运输问题的产销平衡表与单位运价表如下表所示 销地 产地 B1 B2 B3 B4 产量 A1 10 6 7 12 4 A2 16 10 5 9 9 A3 5 4 10 10 4 销量 5 2 4 6 试用运用伏格尔法求出初始运输方案。 4． （15分）用匈牙利法求解下列分配问题，已知效益矩阵为 7 9 8 5 6 12 7 4 8 7 9 6 6 7 8 10 建模（第1题10分，第2题10分，共20分） 1． 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员? （15分） 某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？（15分） 试卷答案 填空（每空2分，共20分） 1:Clk , Clk 2设指派问题的效率矩阵为C= ，若将该矩阵的某一行（或某一列）的各个元素都减去统一常数，得到新的效率矩阵为效率矩阵的新的指派问题与原指派问题的最优解相同。 3 凸集，顶点，顶点，顶点 4其它条件不变的情况下，单位第i种资源变化所引起目标函数值的变化量。买进，卖出。 5 ， 计算（每题15分，共60分） 1. 解 （1）（5分）写出其对偶问题； Minw=5y1+12y2 s.t. y1+2y2≥2 y1+3y2≥1 2y1+4y2≥3 y1≥0， y2 无约束 （10分）已知（3，2，0）T是上述问题的最优解，根据互补松弛理论求出对偶问题的最优解； 由于原问题x1和x2为正，根据互补松弛理论，有对偶问题取最优解时 （1）、（2）取严格等式，即为 y1+2y2＝2 y1+3y2＝1 解得y2＝-1 y1＝4 故对偶问题最优解为Y*＝（4，－1），w*=8 2. 解 （1）（3分） 加入松弛变量，上述模型可转化为 （10分） cj 3 1 3 0 θ CB XB b x1 x2 x3 x4 0 x3 15 3 5 1 0 5 0 x4 24 [6] 2 0 1 4 z 0 3 1 0 0 0 x3 3 0 4 1 -0.5 1.2 3 x1 4 1 1/3 0 1/6 - z 12 0 0 0 -0.5 （2分）最优解，最优值 3. （1） （7分）用最小元素法求得初始可行基如下 销地 产地 B1 B2 B3 B4 产量 A1 10 3 6 × 7