运筹学 试卷 答案 题目 测试
A
2008 ——2009 学年第 一 学期 课程名称： 运筹学 考试时间 120分钟 专业 年级 班 学号 姓名 题号 一 二 三 四 总得分 得分
评卷人签字 复核人签字
得分 一、填空题（每空2分，共16分）
1、若原问题(对偶问题)为无界解,则其对偶问题(原问题) 无可行解 。 2、产销平衡的运输问题，当某个非基变量（即空格）的检验数为0时，该问题有 无穷多最优 解。
3、目标规划中,min()zfd,的含义是 不允许出现负偏差，可以有正偏差 。 4、构造动态规划模型中，状态变量必须满足 无后效性 条件，它降低了动态规划的通用性。 5、存储论中常用的策略主要包括 t-循环策略 、 （s,S）策略 、 0
（t,s,S）策略 。
6、线性规划中的影子价格就是对偶问题的 检验数 。 得分 二、判断题（每小题2分，共14分）（对打?，错打×） 1、线性规划问题的基本解对应可行域的顶点。 （×）
2、若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多 最优解。 （?）
3、正偏差变量应取正值，负偏差变量应取负值。 （×）
4、动态规划中，问题的阶段数等于问题中的子问题的数目。 （?） 5、表上作业法实质就是求解运输问题的单纯形法。 （?）
6、对偶问题的对偶问题是原问题。 （?）
7、订货费为每订一次货发生的费用，它与每次订货的数量无关。 （?） 第1页（共7页）
得分 三、简答题（每题5分，共10分） 1、目标规划的目标函数及其三种形式。
答：目标规划的目标函数是按各目标约束的正、负偏差变量和赋予相应的优先因子及权系数构
造的。当每一目标确定后，决策者的要求是尽可能缩小目标值。因此目标规划的目标函数只能
是,，min(,)zfdd,。?2分 有三种基本形式：
（1）要求恰好达到目标值，即正、负偏差变量都要尽可能小，这时 ,，min()zfdd,， ???1分
（2）要求超过目标值，超过的量不限，即负偏差变量都要尽可能小，这时 ,min()zfd, ???1分
（3）要求不超过目标值，即正偏差变量都要尽可能小，这时 ，min()zfd, ???1分
2、动态规划的指标函数和最优值函数
答：动态规划的指标函数是用来衡量所实现过程的优劣的一种数量指标，它是定义在全过程和
后部子过程上的数量函数。动态规划的指标函数应具有可分离性、和递推 性。 ???3分
动态规划的最优值函数是指标函数的最优值。它表示从第k阶段的状态开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数。
???2分
得分 三、计算题（本题60分，每题12分）
1、设线性规划的目标函数是maxZ，在用标准的单纯形法求解的过程中，得下表（其中a，d
是常数，部分数据有缺失）： 第2页（共7页） c, 2 5 8 0 0 0 j XCxxxxxx b BB123456 x 0 20 0 0 3 0 0 1 6 a x 5 d 1 2 0 1/2 0 2 x 0 8 -2 0 -1 1 1 0 4 cz, a2-5 0 -2 0 -5/2 0 jj
（1）在所有的空格中填上适当的数（此数可含参数a，d）???6分 （2）当a，d在什么范围取值时，此解为最优解。
2,250,,aa,,, 解：，即；解为最优解。 ???2分 5,,d,0,,d,0, （3）若不是最优解，下一步迭代时的主元素为哪个？ 2解：若不是最优解，下一步迭代时的主元素为a（0,,a） 5 ???2分 （4）c,8在什么范围变化时，最优解不变？ 3 (8)100,2，,,,,,cc即。 ???2分 33
2、已知线性规划问题：min23zxxxxx=2+3+5，， 12453 xxxxx，，，，,234,12345,2xxxxx,，，，,233 s.t12345, ,12345xxxxx,,,,0,,
43,,其对偶问题的最优解为yyz,,,,=5，试用对偶问题的性质，求原问题的最优解。 1255
解：原问题的对偶问题为 第3页（共7页） max43,,，yy12
yy，,221,12，，,yy,,23(2)12,
,235(3)yy，,12, ???6分 ,12yy，,2(4), ,1233(5)yy，,,12yy,0,,,
43,,将代入约束条件，可知（2）（3）（4）式为严格不等式，由互补松弛性得 yyz,,,,=51255
,,,xxx,,,0 ???2分 234
,,因yy,0,，由互补松弛性，原问题的两个约束条件应取为等式，即 12 *xx，,34,x,1,151 ???2分 ,,,*24xx，,x,1,15,5
T**原问题最优解为X,,1,0,0,0,1,5目标函数最优值,。 ??2分 ，， 3、已知运输问题的运价表和发量和收量如下表2所示，请用伏格尔法求出运输问题的一组可行
解。
B B B 1234 BA 2 9 12 7 9 1 A 1 3 5 2 4 2 A 10 4 2 6 5 3 3 5 4 6 18
2912753A,,,,1解：,,,, ???2分 13521,A2,,,,,,,,104262A,,,,3 1 1 3 4
0912723A,,,,1,,,, ???2分 035214,A2,,,,,,,,04262A,,,,3 第4页（共7页） 1 3 4
0912723A,,,,1,,,, ???2分 000004,A2,,,,,,,,042624A,,,,3
5 10 1
090723A,,,,1,,,, ???2分 000004,A2,,,,,,,,0406214A,,,,3 5 1
090723342AA,,,,,,11,,,,,,
0000044,,AA22,,,,,,,,,,,,000001414AA,,,,,,33
???2分
运输问题的一个可行解为 B B B B 产量 1234 A 3 4 2 9 1 A 4 4 2 A 1 4 5 3 销量 3 5 4 6 18
???2分 4、下图为动态规划的一个图示模型，边上的数字为两点间的距离，请用逆推法，求出S、A至1
F点的最短路径及最短路长。
B 1 10 7 A 11C10 11 10 5 B8 12 2 S F 14 5 6 13 7 6 A C2210 9 B 3 第5页（共7页） 解： 1
10 7 BA 11C10 11 10 5 B9 2 12 S F14 5 （6 13 7 6 A） C22 10 9 B 3???8分
从S至F点的最短路径是SABCF,,,, ???1分 222 从S至F点的最短路长是31（单位） ???1分 从S至ABCF,,,A点的最短路径是 ???1分 1111
从S至A点的最短路长是27（单位） ???1分 1
5、某厂每月需甲产品100件，每批装配费5元，每月每件产品存储费0.4元,（1）求EOQ及最
低费用。若每月生产500件，（2）求EOQ及最低费用和最高存储数量。 解：（1）用“不允许缺货，生产时间很短”的模型求解
已知CRC,,,5,100,0.4，故 31
2CR25100，，3 最佳生产量 件 ????3分 Q,,,500C0.41
CQCR50100103最小费用 CQ,，,，，，,0.4520元 ??3分 ，，02250Q0 （2）用“不允许缺货，生产需要一定时间”模型求解 已知CRCP,,,,5,100,0.4,500 31 最佳生产量
2CRP3件 ???3分 Q,,,3125560CPR(),1 最小费用
第6页（共7页）
2()CCRPR,20.45100(500100)，，，，,13CQ,,，，0 P500 ,17.89元 ???3分
第7页（共7页）
运筹学 试卷 答案 题目 测试
