1、5对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足 ( )。 A等式约束 B“”型约束 C“”约束 D非负约束6. 原问题的第个约束方程是“”型,则对偶问题的变量是()。多余变量自由变量松弛变量非负变量7.在运输方案中出现退化现象,是指数字格的数目( )。 A.等于m+n B.大于m+n-1 C.小于m+n-1 D.等于m+n-18. 树的任意两个顶点间恰好有一条()。边初等链欧拉圈回路9若G中不存在流f增流链,则f为G的 ( )。 A最小流 B最大流 C最小费用流 D无法确定10.对偶单纯型法与标准单纯型法的主要区别是每次迭代的基变量都满足最优检验但不完全满足
2、()等式约束“”型约束“”型约束非负约束二、多项选择题(每小题4分,共20分)1化一般规划模型为标准型时,可能引入的变量有 ( ) A松弛变量 B剩余变量 C非负变量 D非正变量 E自由变量2图解法求解线性规划问题的主要过程有 ( ) A画出可行域 B求出顶点坐标 C求最优目标值 D选基本解 E选最优解3表上作业法中确定换出变量的过程有 ( ) A判断检验数是否都非负 B选最大检验数 C确定换出变量 D选最小检验数 E确定换入变量4求解约束条件为“”型的线性规划、构造基本矩阵时,可用的变量有 ( )A人工变量 B松弛变量 C. 负变量 D剩余变量 E稳态变量5线性规划问题的主要特征有 ( )A
3、目标是线性的 B约束是线性的 C求目标最大值 D求目标最小值 E非线性三、 计算题(共60分)1. 下列线性规划问题化为标准型。(10分) 满足 2. 写出下列问题的对偶问题 (10分) 3. 用最小元素法求下列运输问题的一个初始基本可行解(10分) 4某公司有资金10万元,若投资用于项目问应如何分配投资数额才能使总收益最大?(15分)5 求图中所示网络中的最短路。参考答案一、 单选题1.C 2.B 3.D 4. A 5. D 6. B 7. C 8.B 9. B 10.D二、 多选题1. ABE 2. ABE 3. ACD 4. AD 5. AB三、计算题1、 max(-z)= 2、 写出对
4、偶问题maxW= 3、解: 4解:状态变量为第k阶段初拥有的可以分配给第k到底3个项目的资金额;决策变量为决定给第k个项目的资金额;状态转移方程为;最优指标函数表示第k阶段初始状态为时,从第k到第3个项目所获得的最大收益,即为所求的总收益。递推方程为:当k=3时有 当时,取得极大值2,即: 当k=2时有:令 用经典解析方法求其极值点。由 解得: 而 所以 是极小值点。极大值点可能在0,端点取得: , 当时,解得 当时,此时,当k=1时, 当 时,但此时 ,与矛盾,所以舍去。当时,令 而 所以 是极小值点。比较0,10两个端点 时, 时, 所以再由状态转移方程顺推: 因为 所以 ,因此 最优投资方案为全部资金用于第3个项目,可获得最大收益200万元。5. 解:用Dijkstra算法的步骤如下,P()0T()(2,37)第一步:因为,且,是T标号,则修改上个点的T标号分别为: =所有T标号中,T()最小,令P()2第二步:是刚得到的P标号,考察,且,是T标号 =所有T标号中,T()最小,令P()5第三步:= 所有T标号中,T()最小,令P()6第四步:所有T标号中,T(),T()同时标号,令P()=P()7第五步:同各标号点相邻的未标号只有至此:所有的T标号全部变为P标号,计算结束。故至的最短路为10。6