《运筹学》试题及答案大全(一)

《运筹学》试题及参考答案

一、填空题（每空2分，共10分）

1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为可行解.

2、在线性规划问题中，图解法适合用于处理工为两个的线性规划问题。

3、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点，化为供求平衡

的标准形式

4、在图论中，称无圈的连通图为树。

5、运输问题中求初始基本可行解的方法通常有最小费用法、西北角法两

种方法。

二、（每小题5分，共10分）用图解法求解下列线性规划问题：

1)maxz=6xi+4x2

2.x,+x2<10

$+x,<8

x2<7

Xpx220

解：此题在“侬筹约复习参考废科doc”中己有，不再重复。

2)minz=-3X1+2X2⑴

-2.Y1+4X2<22⑵

-^+4.^<10(3)

<2.v,-x2<7(4)

占一3%2«1(5)

.七户22°⑹、⑺

解:

可行解域为abcda,最优解为b点。

2X]+4X2=22

{$=0解出Xl=ll,X2=0

（\

，X*=xI=（11,0）T

kX2y

minz=—3x11+2X0=—33

三、（15分）某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，

每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储

备如下表所示：

ABC

甲94370

乙1610120

360200300

1）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）

2）用单纯形法求该问题的最优解。（10分）

解：1）建立线性规划数学模型：

设甲、乙产品的生产数量应为Xi、X2,则X】、X220,设z是产品售后的总利

润，则

maxz=70X1+120X2

s.t.

’9巧4-4X2<,360

4巧+6X24200

3.Vj4-10x24300

x2^0

2）用单纯形法求最优解:

加入松弛变量X3,X4,X5,得到等效的标准模型：

maxz=70X1+120x2+0X3+OX4+OX5

s.t.

9巧4-4X2+X3=360

4巧+6x2+x4=200

3巧+10x2+%=300

A?/20,y=1,2,…,5

列表计算如下：

四、（10分）用大M法或对偶单纯形法求解如下线性规划模型:

minz=5xi+2x2+4x3

3再4-,x2+2X3>4

<6工]+3.马+5.0210

石户2户320

解：用大M法，先化为等效的标准模型：

maxz/=—5xi—2x2—4x3

s.t.

3再+x,+2X3-x4=4

<6.X]+3x,+5X3-x5=10

>0,j=l,2,...,5

增加人工变量X6、X7,得到：

-

maxZ=—5xi—2x2—4x3—MX6Mx7

s.t

3再+吃+2.r3-x4+x6=4

<6玉+3X2+5玉-x5+x-j=10

>0,j=l,2,...,7

大M法单纯形表求解过程如下:

五、（15分）给定下列运输问题：（表中数据为产地Ai到销地Bj的单位运费）

BiB2B3B4Si

Ai123410

A2876580

A391011915

dj8221218

1）用最小费用法求初始运输方案，并写出相应的总运费；（5分）

2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分）

解：用“表上作业法”求解。

1）先用最小费用法（最小元素法）求此问题的初始基本可行解:

费\销

以

BiB2B3B4Si

1234

Ai10

82XX

8765

Ai20

XX218

910119

As30

X2010X

\60

dj8221218

6o\

•••初始方案:

BiB3

A2

B：B4

Z=1X8+2X2+6X2+5X18+10X20+11X10=424

2)①用闭回路法，求检验数:

费\销

7

BiB：B3B4Si

12304-2

Ai10

82XX

8-47-265

A20

XX218

90101191

As30

X2010X

\60

dj8221218

60\

其余%

Vff34=l>0,<0

选0作为入基变量迭代调整。

②用表上闭回路法进行迭代调整:

费\销

NBiB2B3B4Si

123-14-3

Ai10

82XX

8-37—165

A20

XX128

901011-19

A30

X20X10

\60

dj8221218

6C)\

调整后，从上表可看出，所有检验数％<0,已得最优解。

•••最优方案为:

Bi

B：

最小运费Z=1X8+2><2+6X12+5X8+10X20+9X10=414

六、（8分）有甲、乙、丙、丁四个人，要分别指派他们完成A、B、C、D四项不同的工作，每

人做各项工作所消耗的时间如下表所示：

ABCD

甲21097

乙154148

丙13141611

T415139

问：应该如何指派，才能使总的消耗时间为最少？

解：用“匈牙利法”求解。

效率矩阵表示为：

'210971'0875、列约简

154148””间110104

_____N.|=>

131416111---------，2350标号"

415139,1195,

4

r（o）825)[(()825]

it(0)54-41—-——

23(0)0,J——3—-40)-

5I

1。*V

1245J卜),124

6(0)3、

(0)54

30*(0)

1023>

"0010、

0100

至此已得最优解:

0001

000)

使总消耗时间为最少的分配任务方案为

甲~*C,乙一B,丙一D,T-*A

此时总消耗时间W=9+4+l1+4=28

七、（6分）计算下图所示的网络从A点到F点的最短路线及其长度。

此题在“《运筹学参考综合习题》（我站搜集信息自编）doc”中已有。

解：此为动态规划之''最短路问题”，可用逆向追踪“图上标号法”解决如下:

HHS

最佳策略为：A-*B2-*C】fD】fE?fF

此时的最短距离为5+4+1+2+2=14

《运筹学》试题及答案

19、简述线性规划模型主要参数（D11）

（1）、价值系数：目标函数中决策变量前的系数为价值系数

（2）,技术系数：约束条件中决策变量前的系数

（3）、约束条件右边常数项

15、简述线性规划解几种可能的结果（情形）（ppt第二章39或89页）

（1）.有唯一最优解（单纯形法中在求最大目标函数的问题时，对尸某个基本可行解，所

有8jWO）

（2）.无可行解，即可行域为空域，不存在满足约束条件的解，也就不存在最优解了。

（3）.无界解，即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小，一般来

说，这说明模型有错，忽略了一些必要的约束条件

（4）.无穷多个最优解，则线段上的所有点都代表了最优解

（5）退化问题，基变最有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个

或几个基变最等于零，用图解法无退化解

1、简述单纯形法的基本思路（p70）

从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是，则再找另一个使得其目标

函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，

就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。

17、简述线性规划中添加人I：变量的前提（p85）

在系数矩阵中直接找不到初始可行解，进而通过添加人工变量的方法来构造初始可行基，

得出初始基本可行解

10、简述线性规划对儡问题的居外性质（D122）

（1）对称性（2）弱对偶性（3）强对偶性（4）最优性（5）互补松弛型

原函数与对偶问题的关系

1）求目标函数最大值的线性规划问题中有n个变量m个约束条件，它的约束条件都是小于

等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，

其约束条件都为大于等于不等式。

2）原问题的目标函数中的价值系数为对偶问题中的约束条件的右边常数项，并且原问题的目

标函数中的第i个价值系数就等于对偶问题中的第i个约束条件的右边常数项。

3）原问题的约束条件的右边常数项为对偶问题的目标函数中价值系数。并且原问题的第i个约

束条件的右边常数项就等于零对偶问题的目标函数中的第i个变最的系数。

4）对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。

5、运输问题是特殊的线性规划问题，但为什么不用单纯形法求解

因为这类线性规划问题在结构上存在着特殊性,表上作业法根据运输问题的特点来设计的

特殊的单纯形法，可以更加形象直观简单的解决运输问题。

9、简述表上作业法的基本步骤

（1）用最小元素法找出初始基可行解，也就是初始调运方案。对于有m个产地n个销地的

产销平衡问题，则有m个关于产量的约束方程和n个关于销量的约束方程。由于产销平衡，其

模型最多只有m+n-1个独立的约束方程，即运输问题有m+n-1个基变量。在mXn的产销平衡表

上给出m+n-1个数字格，其相对应的调运量的值即为基变量的值。

（2）求各非基变量的检验数。

（3）用闭回路法来判别问题是否达到最优解。如己是最优解则停止计免，否则继续下一步。

（4）用闭回路法进行基变换，确定入基变量和出基变量，找出新的基本可行解。在表上用

闭回路法调整。

11、简述指派问题的标准形式及数学模生（ppt或书上pl79）

设A个人被分配去做〃件工作，规定每个人只做一件工作，每件工作只有一个人去做。己

知第i个人去做第j件工作的效率（时间或费用）为GJ（f=L2…户L2…〃）并假设GJ20。

问应如何分配才能使总效率（时间或费用）最高？

12、简述分枝定界法的基木步骤

分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整

数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝）,

再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的

最优解。

基本思路：

1、先求出线性规划的解

2、确定整数规划的最优目标函数值z*初始上界和下界工

3、将一个线性规划问题分为两枝，并求解

4、修改最优目标函数上、下界

5、比较与剪枝：各分枝的目标函数值中，若有小于幺者，则剪掉此枝，表明此子问题已

经探清，不必再分枝了；否则继续分枝。

6、如此反复进行，直到得到Z=Z为止，即得最优解丫-

6、简述目标规划的目标函数主要类型及其数学表达式。

目标规划的目标函数只能取极小形式，即minz=f（d+,d-）,共有如下三种形式：（1）,要求

恰好等于目标值，即希望决策值超过和不足目标值的部分都尽可能小，因此由函数

minz=f（d++d-）：（2）,要求不超过目标值，允许达不到目标值，即希望决策值不超过目标值，

也希望d+越小越好，因此有minz=f（d+）;（3）要求不低于目标值，允许超过目标值，即希望决

策值不低于目标值，也希望d-越小越好，因此有minz=f（d-）.

2、简述运筹学中背包问题的一般提法（p225）

对于N种具有不同重量和不同价值的物品，在携带物品总重量限制的情况下，决定这N种

物品中每一种物品多少数量装入背包内，使得装入背包物品的总价值最大。

4、建立动态规划模型时，应定义状态变量，请说明状态变量的特点

第一,可知性,即各阶段的状态变量的取值能直接或间接的确定：第二能够确切的描述过程

的演变且满足无后效性.

7、简述动态规划数学模型要点（ppt第十章18论述题增加阶段和阶段变量）

（1）分析题意，识别问题的多阶段特性，按时间或空间的先后顺序适当划分为满足递推关

系的若干阶段，对分时序的静态问题要认为赋予“时段”概念;

（2）正确选择状态变量，状态变量应具备两个特征：第一，可知性，即各阶段的状态变量

的取值能直接或间接的确定：第二，能够确切的描述过程的演变且满足无后效性：

（3）根据状态变量和决策变量的含义，正确写出状态转移方程；

（4）根据题意明确过程指标函数和最优指标函数以及第k阶段指标函数的含义，并正确列

出基本方程。

3、简述著字的哥尼斯堡七桥难题及答案

河上有7座桥，将河中的两个岛和河岸连结，如图1所示。一个散步者能否一次走遍7座

桥，而且每座桥只许通过一次，最后仍回到起始地点。这就是七桥问题，一个著名的图论问题。

欧拉证明了这样的走法不存在。欧拉是这样解决问题的：既然陆地是桥梁的连接地点，不

妨把图中被河隔开的陆地看成A、B、C、D4个点，7座桥表示成7条连接这4个点的线，如图2

所示。

于是“七桥问题”就等价于图3中所画图形的一笔画问题了。每个点如果有进去的边就必

须有出来的边，从而每个点连接的边数必须有偶数个才能完成一笔画。图3的每个点都连接着

奇数条边，因此不可能一笔画出，这就说明不存在一次走遍7座桥，而每座桥只许通过一次的

走法。

8、简述树定义及性质

树:连通且不含圈的无向图称为树。

性质：（1）裙无圈，m=n-l.（2）相连通，m=n-l.（3）树无圈，但每加一条新边，则可得到

惟一一个圈.（4）相连通，但任舍一条边，图就不连通.（5）秘中任意两点之间有惟一一条链相

连.

16、简述求最小生成树的方法

（1）避圈法：将图中的边按权由小到大排序：按排序由小到大选定n—l条边为止，选择

时每选一条边应避免和已选的边构成圈，且所选边是未选边中的最小权边。

（2）破圈法：在给定的赋权的连通图上任选一个圈：在所找的圈中去掉一个权数最大的

边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）：如果所余下的图己

不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。

18、简述决策按环境分类（分为哪几种）（D389）

确定型决策：在决策环境完全确定的条件下,进行

不确定型决策：在决策环境不确定的条件下进行，决策者对个自然状态发生的概率一无所

知

风险型决策问题：在决策环境不确定的条件下进行，决策者对各自然状态发生的概率可以

预先估计或计算出来［非程序化决策：］

13、简述不确定型决策的决策方法（决策准则）5389）

（1）最大最小准则（悲观准则），决策者从最不利的角度去考虑问题：

（2）最大最大准则（乐观准则），决策者从最有利的角度去考虑问题：

（3）等可能性准则，决策者把各自然状态发生的机会看成是等可能的；

（4）乐观系数准则（折衷准则），决策者取乐观准则和悲观准则的折衷：

（5）后悔值准则（沙万奇准则），决策者从后悔的角度去考虑问题

14、简述层次分析法的基本步骤（ppt第16章31）

1.明确问题，提出总目标2.绘制层次结构图3.标度及两两比较矩阵4.求各因素权重的过

程5.两两比较矩阵一致性检验6.利用权数或特征向量求出各方案的优劣次序.EVPI=EV.PI

-EV^PI

1、结合我国企业发展中面临的一实际问题，简要论述运筹学在我国企业管理优化中的重要应用

及作用。

答：运筹学在企业管理优化领域的主要应用有：

①生产计划。如一家重型制造厂用线性规划及整数规划安排生产计划，节约了10%的生产费

用。

②市场营销。在广告预算和广告媒介的选择、竞争性定价、新产品开发、销售计划、市场

竞争策略的制定等方面，运筹学也大展身手。美国杜邦公司在五十年代起就非常重视将运筹学

用于研究如何做好广告工作、产品定价，通用公司也运用运筹学方法进行市场模拟研究。

③库存管理。运筹学中的存贮论可以应用于物资库存量的管理，以确定仓库的合理容量，

以及确定适当的库存方式和库存量。

④运输问题。运用运筹学，可以确定最小成本的运输路线、物资的调拨、运输I：具的调度，

以及新建厂址的选择等等。

⑤人事管理。对人员的需求和招聘情况的预测；人力资源的开发，如对人才的教育和培训I，

人才评价体系、薪酬体系的确定等，都可以运用运筹学方法。

⑥财务会计。运筹学解决企业如何最有效的利用资金资源的问题。其涉及到投资决策分析、

成本核算分析、证券管理等。在投资决策分析中，企业如何利用剩余资金，如何投资往往有多

种方案。而运筹学的作用就是要要对这些不同的投资方案进行决策，以确定最优的方案，使得

企业的收益最大。通常是利用线性规划模型、决策论来进行判断。

满足乘客需求前提下.以最低成本进行订票及安排600万

联合航空公司1-2/1986

机场工作班次

控制成品库存（制定最优再订购点和订购量，确保

标准品牌公司12/1981380万

安全库存）

进行上千个国内航线的飞机优化配置来,大化制

Delta航空公司1-2/19941亿

润

京新设计北美生产和分箱系统以降低成本并加快

宝清公司1-2/19972亿

了市场进入速度

2、根据您所学的《运筹学》及其它学科知识，谈谈您对“运筹帷幄，决胜r里”的理解：

语出〈史记高祖本纪》，意思是说，张良坐在军帐中运用计谋，就能决定千里之外战斗的胜

利，这说明张良心计多，善用脑，善用兵，后来人们就用“运筹帷线”表示善于策划用兵。

学习中，我们应当努力学习运筹学的理论知识，并将理论知识付诸实践，在学习其他学科

时，运用运筹学的知识，比如在写毕业论文时，运用运筹学的知识，丰富论文内容，为论文增

加支撑理论。

生活中，我们面对任何问题都要仔细思考，运用运筹学的知识，更好地解决问题，而现在

网络及通讯工具的不断发展，让我们远在厂里之外也可以解决问题，如：越来越多的跨国公司，

不仅仅是局限于面对面的交谈，很多网络会议或电话会议，让解决问题更加方便迅速。

在企业管理中，生产计划、市场营销、库存管理、人事资源、运输问题等。

3、请论述如何把你所学的运筹学的知识应用到今后的管理实践中去：

答：（1）对运筹学的知识体系了若指掌。（2）处理管理实践的问题时，有意识的使用运筹

学的知识体系和方法来解决。（3）需要有很强的归纳总结能力，把在实践中遇到的问题，转化

为运筹学书上的问题来解决，如：背包问题、七桥问题。以上三者缺一不可，遇到问题，首先

想到解决该问题需要哪些资源，从哪里可以获得这些资源：其次考虑再获得资源后，如何使这

些资源得到最合理的利用，使其产生最大效益。另外，强化管理，不断进行管理刨新已成为企

业在竞争中制胜的根本保证。作为企业的管理者，把握并运用好运筹学的理念定会取得“运筹

帷幄之中，决胜千里之外”之功效。

,1、请简要列举（至少3）我国古代朴素的运筹学思想,并论述其间的运筹学原理。（I个）

答：（1）孙子兵法与运筹学思想。《孙子兵法》在表达军事思想的同时，也蕴藏着丰富的运

筹学思想-----军事运筹学。孙武在《孙子兵法》中灵活运用整体性原则研究军事问题，采用

定量分析方法谋划战争，运用优化原则进行科学决策。

（2）田忌赛马。战国时期的“田忌赛马”是运筹思想的一次完美应用。整个赛马过程中,

孙膑巧妙地运用了一种科学合理的方法——博弈论。博弈论是运筹学的一个分支，是指二人在

平等的对局中各自利用对方的策略变换自己的对抗策略，达到取胜的目的。通过博弈论的思想，

孙膑指出用本方的下马对齐王的上马，用本方的上马对齐王的中马，用本方的中马对齐王的下

马。最终以一负两胜取胜。孙膑成功地将本方劣势转为优势，赢得了比赛。

（3）南魏救赵。魏国攻打赵国，赵国求救于齐。孙膑指出应趁魏国国内兵力空虚之际，发

兵直取魏都大梁，迫使伪军弃赵回救。最终这一战略取得了胜利。其中的战略思想，妙在善尸

调动第二年。调动敌人的要诀，在于“攻其所必救:这充分体现了如何策划兵力，选择最佳时

间、地点，趋利避害，集中优势兵力以弱克强的运筹思想。

（4）沈括运军粮：沈括曾经从行军中各类人员可以背负粮食的基本数据出发，分析计

算了后勤人员与作战兵士在不同行军天数中的不同比例关系，同时也分析计算了用

各种牲畜运粮与人力运粮之间的利弊，最后做出了从敌国就地征粮，保障前方供

应的重要决策，从而减少了后勤人员的比例，增强了前方作战的兵力。这种军事后勤

问题的分析计算是具有现代意义的运筹思想的范例。

（5）晋国公重建皇城的施工方案，体现了运筹学的朴素斯思想。要使重建工程的各个

工序，在时间、空间上彼此协调，环环相扣，就需要运用行列式的相关知识，进行精确计

算。

1.影子价格:当约束条件中的常数项增加一个单位时，最优目标函数值增加的数量。（影增）

2.对偶价格:当约束条件中的常数项增加一个单位时，最优目标函数值改进的数量。

3.灵敏度分析:对系统或事物因周围条件变化显示出来的敏感程度分析。

4.0-1规划:所有决策变量只能取0或1两个整数的整数线性规划。

5.分支定界法:分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，

则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称

为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整

数规划的最优解。

6.生成子图:给定一个无向图6=（V.E）,保留G的所有点，而删掉部分G的边或者说保留一部分

G的边，所获得图G,称之为G的生成子图。

7.松弛问题:不考虑整数约束条件，由余下的目标函数和约束条件构成的规划问题。

8.欧拉回路:图G的一个回路，若它恰通过G中每条边一次,则称该回路为欧拉回路。

9.样本信息:研究中实际观测或调查的一部分个体的信息。

10.最小生成树:在一个赋权的连通的无向图G找出一个生成树，并使得这个生成树的所有边的

权数之和最小。

11.目标约束:在引入了目标值和正、负偏差变量后，可以将原目标函数加上负偏差变量，减去

正偏差变量，并且等于目标值，这样形成一个新的函数方程，把它作为一个新的约束条件，加

入到原问题中去，称这种新的约束条件为目标约束。

12.偏差变■:指目标规划中实现值与目标值之间的差异。其中实现值超过目标值的部分记为d+.

实现值未达到目标值的部分记为d-od+,d-这样的变量称为偏差变量。

13.状态变■:描述各阶段状态的变量称为状态变量。

14.基本可行解：满足非负条件的基本解叫基本可行解。

15.后验概率：利用样本情报对先验概率修正后得到的概率。

16.定性分析：借助决策者的知识,经验,分析和判断能力等进行决策的方法。

17.定・分析：量化决策问题并建立数学模型进行决策的方法。（基于事物的数据和数量关系,建

模'计算找出解决方案）

18.状态与状态变置:状态是指每个阶段开始所处的自然状况或客观条件，而描述过程状态的变

量就是状态变量。能够完全描述动态系统时域行为的所含变量个数最少的变量组称为系统的状

态变量。

《运筹学》试题及答案（A卷）

一、单项选择题（从下列各题四个备选答案中选出个正确答案，答案选错或未选者,该题不得分.每小题1分，

共10分）

1.线性规划具有唯一最优解是指

A.最优表中存在常数项为零

B.最优表中非基变量检验数全部非零

C.最优表中存在非基变量的检验数为零

D.可行解集合有界

2.设线性规划的约束条件为

=

Kj+五？+Xj3

2々+2X2+&二4

々，…，人＞0

则基本可行解为

A.(0,0,4,3)B.(3.4,0,0)

C.(2.0.1,0)D.(3.0,4,0)

的之°,则

3minZ=3^+4X2,XJ+>4,2XJ+2,XP

A.无可行解B.有唯一最优解medn

C.有多重最优解D.有无界解

4,互为对偶的两个线性规划m"Z=及min“=丫瓦%

对任意可行解X和

K存在关系

A.Z>WB.Z=W

C.Z>WD.Z<i

5.有6个产地4个销地的平衡运输问题模型具有特征

A.有10个变量24个约束

B,有21个变量10个约束

C.有24个变量9个约束

D.有9个基变量10个非基变量

6.下例错误的说法是

A.标准型的目标函数是求最大值

B.标准型的目标函数是求最小值

C.标准型的常数项非正

D.标准型的变量一定要非负

7.m+n—1个变量构成一组基变量的充要条件是

A.m+n-l个变量恰好构成一个闭回路

B.m-n—l个变量不包含任何闭回路

C.m-n-1个变量中部分变量构成一个闭回路

D.m+n-l个变量对应的系数列向量线性相关

8.互为对偶的两个线性规划问题的解存在关系

A.原问题无可行解，对偶问题也无可行解

B.时偶问题行可行解，原问题可能无可行解

C.若最优解存在，则最优解相同

D.一个问题无可行解，则另一个问题具有无界解

9.有m个产地n个销地的平衡运输问题模型具有特征

A.有mn个变量m+n个约束-m+n-1个基变量

B.有m+n个变量mn个约束

C.有mn个变量m+n-1约束

D.有m+n—1个基变量，mn—m—n—1个非基变量

10.要求不超过第•目标值、恰好完成第二L1标值，目标函数是

_minZ=PM：+p?（d[+d；）

B,1而2=夕3：+。式吗一球）

cminZ=pxd~+p2（d；-dt）

DminZ=pM++d；）

二、判断题（你认为卜列命题是否正确，对正确的打“力；错误的打“X”。每小题1分，共15分）

11.若线性规划无最优解则其可行域无界X基本解为空x

12.凡基本解一定是可行解X同19x

13.线性规划的最优解一定是基本最优解X可能为负x

14.可行解集非空时，则在极点上至少有一点达到最优值X可能无穷x

15.互为对偶问题,或者同时都有最优解，或者同时都无最优解J

16.运输问题效率表中某一行元素分别乘以一个常数,则最优解不变X

17.要求不超过目标值的目标函数是mmZ=d*

18.求最小值问题的目标函数值是各分枝函数值的下界

19.基本解对应的基是可行基XII包时为星本可行解,对应的居叫叫】拈

20.对偈问题有可行解,则原问题也有可行解X

21.原问题具有无界解,则对偶问题不可行

22.m+n-l个变量构成基变量组的充要条件是它们不包含闭回路

23.目标约束含有偏差变量

24.整数规划的最优解是先求相应的线性规划的最优解然去取整得到X

25.匈牙利法是对指派问题求最小值的一种求解方法

三、填空题（每小题1分，共10分）

26.有5个产地5个销地的平衡运输问题，则它的基变量有（9）个

27.已知最优基

「12一

B=

L37'C,=（3,6）,则对偶问题的最优解是（）

28.已知线性规划求极小值，用对偶单纯形法求解时，初始表中应满足条件（对偶问题可行）

29.非基变量的系数c,变化后，最优表中（）发生变化

30.设运输问题求最大值，则当所有检验数（）时得到最优解。

31.线性规划maxZ=一丸+入2,246,4IL+x2三8"1，七之0的最优解是（0,6）,它的

第1、2个约束中松驰变量（£,$）=（）

32.在资源优化的线性规划问题中，某资源有剩余，则该资源影子价格等于（）

33.将目标函数2=与一$勺转化为求极小值是（）

34.来源行*+6X3~6V4=1的高莫雷方程是（）

35.运输问题的检验数入〃的经济含义是（）

四、求解下列各题（共50分）

36.已知线性规划（15分）

maxZ=3Xj+4x2+5x3

Xj+20-x3<10

<2x,一$+3A3<5

弓NO,y=1,2,3

（1）求原问题和对偶问题的最优解：（2）求最优解不变时0的变化范围

37.求下列指派问题（min）的最优解（10分）

5685

12152018

91097

9656

38.求解下列目标规划（15分）

niinz=W+d：)+gdj+舄dj

Xj+x2+d；-d：=40

$+x2+dJ-dj=60

<xx+dy~=30

x2+d；-d；=20

演，W，d「，d：>004)

39.求解下列运输问题（min）（10分）

85440

C=14181390

9210110

8010060

五、应用题（15分）

40.某公司要将一批货从三个产地运到四个销地,有关数据如下表所示。

供

销地B：B：B,B,

应

产地量

56

A,7379

0

40

A;26511

0

75

As6425

0

32244838

需求量

0000

现要求制定调运计划，且依次满足：

（1）B,的供应量不低于需要量：

（2）其余销地的供应量不低于85%：

（3）&给B,的供应量不低于200：

（4）A：尽可能少给瓦：

（5）销地昆、B,的供应量尽可能保持平衡。

（6）使总运费最小。

试建立该问题的目标规划数学模型.

运筹学（B卷）

一、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分•每小题1分,

共10分）

1.线性规划最优解不唯一是指（）

A.可行解集合无界B.存在某个检验数心〉0且％^中=L…普）

C.可行解集合是空集D.最优表中存在是变次的检验数卜孝

.maxZ=4.+孙，4毛+3勺匕24町之1°，如々2。，则（）

A.无可行解B.有唯一最优解C.有无界解D.有多重解

3.原问题有5个变量3个约束，其对偶问题（）

A.仃3个女用3个约束B.有5个变量3个约束

C.有5个变量5个约束D.有3个变量3个约束

4.有3个产地4个销地的平衡运输问题模型具有特征（）

A.有7个变量B.有12个约束

C.有6约束D.仃6个暴变显

5.线性规划可行域的顶点一定是（）

A.居本可行解B.非基本解C.非可行解D.最优解

6.X是线性规划的基本可行解则有（）

A.X中的基变量非零，非基变量为零B.X•不一定满足约束条件

C.X中的基变量非负，非堪变质为零D.1是最优解

7.互为对偶的两个问题存在关系（）

A.原问题无可行解，对偶问题也无可行解

B.对偶问题有可行解，原问题也有可行解

C.原问题有最优解解，对偶问题可能没有最优解

D.原问题无界解.对偶问题无可行解

8.线性规划的约束条件为

=

2尤］+不3+无35

，2演+2勺+々=6

j卜…NO

则基本解为()

A.(0,2,3,2)B.(3,0,1,0)

C.(0,0,6,5)D.(2,0,1,2)

9.要求不低于目标值.其口标函数是()

maxZ=d~mmZ-d~

C.maxZ=&'D.tninZ=d'

10.H是关于可行流f的一条增广链，则在H上有（）

A,对任意度有4'%B,对任意,力€“，有玲，%

C.对任意也力w-苟X%D..对任意—，，前

二、判断题（你认为下列命题是否正确.对正确的打“寸'；错误的打“x”.每小题1分,共15分）

11.线性规划的最优解是基本解x

12.可行解是基本解“

13.运输问题不一定存在最优解乂

14.一对正负偏差变量至少一个等于零X

15.人工变量出基后还可能再进基x

16.将指派问题效率表中的每一元素同时减去一个数后最优解不变

17.求极大值的目标值是各分校的上界

18.若原问题具有m个约束，则它的对偶问题具有m个变量

19.原问题求最大值，第i个约束是2“约束，则第2.个对偶变量匕4

20.要求不低于目标值的目标函数是加11Z=<T

21.原问题无最优解，则对偶问题无可行解*

22.正偏差变量大于等于零，负偏差变量小于等于零x

23.要求不超过目标值的目标函数是minZ=d+

24.可行流的流量等于发点流出的合流

25.割集中弧的容量之和称为割量.

三、填空题（每小题1分，共10分）

26.将目标函数皿12=3-5.丫2+8/转化为求极大值是（）

110

A=

27.在约束为⑷瓦°的线性规划中，设L20”,它的全部基是（）

28.运输问题中m+n-l个变量构成基变量的充要条件是（）

29.对偶变量的最优解就是（）价格

30.来源行“2一亍均二1"的高莫雷方程是（）

31.约束条件的常数项瓦变化后，最优表中（）发生变化

32.运输问题的检验数入〃与对偶变量u,、丫,之间存在关系（）

33.线性规划口】初2=_玉+/,2»+.马<6,4A1+X248,.片/220的最优解是（O,6）,它的

对偶问题的最优解是（）

34.已知线性规划求极大值，用对偶单纯形法求解时，初始表中应满足条件（）

35.Dijkstra算法中的点标号b（力的含义是（）

四、解答下列各题（共50分）

36.用对偶单纯形法求解下列线性规划（15分）

minZ=3X[+4必+5为

Xj+2勺+3X3>8

<2/+2与+x3>10

,勺,称修>0

37.求解下列目标规划（15分）

minZ=+d?j）+p2（d?j+d；）

为+为+d1一d：=1

2々+2X2+d]-d；=4

2入]一电+d：-d；=2

㈤知行,d：20,”1,2,3

38.求解F列指派问题（min）（10分）

39237