运筹学期末考试题型.docx
《运筹学期末考试题型.docx》由会员分享，可在线阅读，更多相关《运筹学期末考试题型.docx（20页珍藏版）》请在冰点文库上搜索。
运筹学期末考试题型
运筹学
一、填空题（1分*10题）
运筹学建模一般步骤：
1.提出问题，明确目标
2,构建模型
3.求解与检验
4.结果分析与实施
确定型模型和概率模型包含哪些内容：
确定型模型主要包括：
线性规划、整数规划、目标规划、非线性
规划、动态规则、图与网络；
概率型模型主要包括：
决策论、对策论、排队论、存储论、维修更新理论、搜索论、可靠性和质量管理等
二、选择题（2分*5题）
1,整数规划的常见解法：
分枝定界法、割平面法
（求解0-1规划的常用算法：
完全枚举法、隐枚举法）
（求解指派问题的常用算法：
匈牙利法）
5.目标规划的基本概念:
①决策变量和偏差变量：
决策变量又称控制变量
用xi表示.
在目标规划中，引进正、负偏差变量，分别用
di+和di-表示.di+
为正偏差变量,它表示实际决策值超过第i
个目标值的数量；
di-为负偏差变量,它表示实际决策值低于第
i个目标值的数
单。
②资源约束和目标约束：
资源约束是指必须严格满足的等式或不等式约束,又称为硬约束.目标约束是目标规划特有的,它把要预定的目标值作为右端的常数项,在达到目标值时允许发生正
或负的偏差量,因此，目标约束是软约束，具有一定的弹性.目标约束不会不满足,但可能偏差过大.
③优先因子与权系数：
目标规划中,当决策者要求实现多个目标时，为使多个目标统一在单一目标中,且按主次或轻重缓急依次
实现,故引进优先因子.凡要求第一位达到的目标赋予优先因子P1,次位的目标赋予优先因子P2,…,Pk+1,并规定PkmPk+1,（k=
5.2,…丛）表示Pk比Pk+i有更大的优先权，不同的优先因子代表不同的优先等级.
④目标规划的目标函数：
目标规划的目标函数是由各目标约束的正、负偏差变量和相应的优先因子组成的.因决策者的愿望是尽可能缩小偏离目标值,故目标函数总是极小化.
对于目标约束fi（X）+di--di+=bi,相应目标函数的基本形
式有如下三种:
（1）若要求恰好达到预定目标值，则目标函数为min（di++di-）;
（2）若要求不超过预定目标值，则目标函数为min（di+）;
（3）若要求超过预定目标值,则目标函数为min（di-）.
6.动态规划的基本概念:
1.阶段
根据问题的特点和需要,将问题的全过程恰当地划分为若干个相互联系的阶段，以便把问题分解成若干子问题逐个求解.本章用k表示阶段（kWn,n为阶段总数）.如例l,n=4,k=1,2,3,4.
2.状态与状态变量
状态是系统在变化过程中某个阶段的初始形态表征.它通过系统在某个阶段的出发位置来描述.描述状态的变量称为状态变量.木章用Sk表示第k阶段的初始状态.如例1中用s.表示第一阶段的初始状态，即s产A.通常一个阶段包含若干个状态.第k阶段所有可能状态构成的集合称为该阶段的状态集，记为9.例1中第二阶段的状态集为S尸｛Bi,B2,Bj）.
3.决策与决策变量
决策是指在某一阶段状态给定以后，从该状态演变至下一阶段某状态的选择.描述决策的变量称为决策变量.用dk（sO表示第k阶段处丁•状态sk时的决策变量.dk（sL）的可能值全体构成决策集合Dk（&）.如例1中，D1（A）=
4.状态转移与状态转移方程
系统由这一阶段的一个状态转变到下一阶段的另一个状态称为状态转移,状态转移既与状态有关，又与决策有关,描述状态转移关系的方程称为状态转移方程.若笫k阶段的状态变量必与该阶段的决策变量小确定后，第k+1阶段的状态变量必一也随之确定，则它们的关系式
i=Tk（»,dO
称为由状态盘转移到状态”一的状态转移方程.反之.若第k阶段的状态变量“与k・1阶段的决策变量确定后，笫k-1阶段的状态变量隘」也随之确定，则它们的关系式
Sk-1=Tk-l（»,dkl）
称为由状态Sk转移到状态的状态转移方程.
5.策略与（后部）子策略
由过程的第一阶段开始到终点为止的每阶段的决策心（8k）（k=1,2,….n）所组成的决策序列称为全过程策略，简称策略，记为
p）n（si）=（dl（Sl）,dz（S2）,dn（s»））.
这里，状态间的转移符合其逻辑关系.全部策略构成策略集，记为PMsi）.
从第k阶段某一初始状态SK开始到终点的过程称为全过程的k后部子过程.其相应的决策序列
pkQ（Sk）=（ck（Sk）,dk+I）,…，d式Sn））称为k后部子策略，简称子策略.k后部子策略的全体记为Pkn（Sk）.
6.阶段指标
阶段指标是对过程中某一个阶段的决策效果衡量其优劣的一种数量指标，第k阶段初始状态为»且采取决策（Ma）时的阶段指标记为H%,dKsk））,
7.指标函数与最优指标函数
指标函数息用火为名阶段决策过程决策效臬衡后具优生的一钟教局指标.支是定义在全过程或所有后部子过程上的确定的数量函数，表示为
Vu（Sk）=Via（Sk,pkD（&））
=Vt*（sk.di,si+1,dk+i,■**,Si.du）.
由于常见的指标函数是取各阶段指标和的形式，故本章作此殿定，即
VLD（5k）=Si,£）■））.
I-h
其中V人“（hG））表示第i阶段的初始状态为由兄采取决策也（s.）时该阶段两指标值.
指标函数VMS的最优值称为最优指标函数.记为3{7.它表示从第k阶段的状态泣开始.选取最优策略（或增优后部子策略）后，得到的指标函数值.在例1中，f“A）表示从始点A到终点E的管线最短长度.
从例）的计算过程可以看到,在求解的各个阶段，我们运用了如下递归关系：
fi（si）=min^Vk（sk.di（si））+fi+।（st+।）}
di{si）FDk（%）（k=4,3,2,1）f3（a）—0.
这种递归关系就是•科动态规划函数方程，
三、简答题（10分*2题）
线性规划模型一般型、标准型、矩阵形式、线性规划模糊解的基
本概念：
动态规划方程、最优化原理：
最优化原理即，“作为整个过程的
最优策略具有这样的性质,即无论过去的状态和决策如何,对前
面的决策所形成的状态而言,余下的诸决策必须构成最优策略.”
由动态规划最优化原理可以得到体现这一原理思想的函数基本方程：
f1（Si）-upt（V1（i,dk（Sk））+ft*J（51*J）}
dn（sr）eDJaj（k=ntn*1.■•**】）（4.1）
fm-l{Sn-fI）=0.
这里ipt表示“最优二即代表“最大”（max）化或“最小中而黑）化
四、建立运筹学模型（10分*1题）只需要建模就好，不求解。
刘满凤教材《运筹学教程》2.4节（即对一些线性规划问
题的实际应用案例建模，来解释线性规划问题建模的基本思路、方法和技巧）
五、计算题（10分*5题）
对偶理论:
i,对背格式的对偶问题
对标黯式的对偶向题川矩阵表示，若母问题是muxZ=CX,
AXWb
则其对偶可迎为
minW=¥b.
原问题（或对偶问题）
对偶问题（或原问题）
目标函数maxZ
目标函数m）nW
变量H个
约束条件n个
变量20
约束条件2
变量W0
约束条件W
变量.无约束
约束条件=
约束条件m个
变量m个
约束条件后
变量
约束条件三
变量W0
为衷笑件=
奋&王的言
约束条件右端项
目标函数变量的系数
目标函数变量的系数
约束条件右端项
t,
X孑。
.
YACs.t.
0.
相关定理:
对称性定理对偶问题的对偶是原问题
弱对偶性定理若X（0）是原问题的可行解，Y（0）是对偶问题的可行解，则有CX（0）＜Y（o）b
最优性定理若X（o）是原问题的可行解，Y（o）是对偶问题的可行解，且有CX（0）=Y（o）b,则X（o）,Y（o）分别是原问题和对偶问题的最优解.对偶定理若两个互为对偶问题之一有最优解，则另一个必有最优解且目标函数值相等
互补松弛性定理若X*,Y*分别是原问题和对偶问题的可行解，则
X*,Y*为最优解的充分必要条件是Y*Xl=0和YsX*=0
解的对应定理
设原问题是maxZ=CX,AX+b,X,X!
对偶问题是minW=Y=C,Y.
则原问题单纯形表的检脸数行对应其对偈问题的一个基解，其对应关系见表2.14.
表2,14
Xb
X、
Xl
Q
C1,B-lN-Cn
CuB-1
Yi
Y
Y
对偶单纯形方法：
第一步：
建立线性规划问题的初始单纯形表.
设表中检验数行的值2厂©全部30,即是其对偶问题的一个可行解一
第二步：
检行b列的数字，若均非负，则已得最优解，停止计算.若b列有负分量，则转第三步.
第三步：
换基迭代
（1）确定换出变量
按min{i魏Bb）K0}=『，确定基变量Xr为换出变量.
（2）确定换入变量
杵单纯在发中检杳k闷一行的各系数a（J”….n）.若所有au三。
则上也门解.停止计算.否则，计算
确定"为换入变量.
（3）以a”为主元素，按原单纯形法在表中进行初等行变换，得到新基的单纯形表.返网第二步.
例14用对偶单纯形法求解下列线性规划问题.
minZ=12yi+8y?
+16y3+12y
2yi4-y2+4yj22
s.t.2yi+2y2+4y』》3
yi>0（i=1,2,3,4）.解先将问题化为
maxZ1=-12yi-8y-16yL12y,+Oys+0”-2y1-ya-4y»+y5=-2
s.t.-2yi-2y2・4y4+y6=-3y-y620•用对偶单纯法进行计算，其过程见表2.15.
表2.15
-12
-8
-16
-12
0
0
G
Xb
b
y>
户
y>
广
ys
*
0
0
y«
V6
-2
-3
-2
-2
-1
-2
-40
0
[-4]
1
0
0I
Z
，
0
12
8
16
12
0
0
一g
0
-12
ys
JU
-2
3/4
-2
1/2
[-I]
172
•40
0
1
1
0
0
・1/4
Z
9
-9
6
2
16
0
0
3
-g
•8
•12
丫2
2
-1/4
2
-1/2
1
0
4
[-2]
0
1
-1
1/2
0
-1/4
Z，
-13
2
0
8
0
2
3
「q
-8
•16
V3
3/2
1/8
1
1/4
1
0
0
1
2
•1/2
0
-1/4
-1/2
1/8
E
-14
0
0
0
4
4
2
一q
至此，得原问题的最优解y=（yi,y2,yj,y4）r=（0,3/2,1/8,0）r.
最优值为Z*=-Z'=14.
灵敏度分析:
F列线性规划问题:
maxZ
5x1
x
s.t.12x1
x2
4x2
5x2
3x3
10x3
13x3
20
90
x1、x2、
X3
解：
先将该线性规划化引入松弛变量
乂4,
乂5,得:
maxZ5x15x2
x1x23x3st.12x14x210x3
13x3
x4
20
x5
90
x1、x2、x3、x4、x
（1）求出该问题的最优解和最优值:
C?
-5
5
13
0
0
0
CB
Xb
b
Xi
x2
x3
x4
x5
0
x4
20
-1
[1]
3
1
0
20
0
x5
90
12
4
10
0
1
22.5
Z
0
-5
5
13
0
0
5
x2
20
-1
1
3
1
0
0
x5
10
16
0
-2
-4
1
Z
-100
0
0
-2
-5
0
T
故，得其最优解为（x1,x2,x3,x4,x5）T=（0,20,0,0,10）
最优值为maxZ=100.
（2）目标函数中X3系数变为8,最优解是否改变？
若改变，请求出
由
（1）得知，X3为非基变量，故其检验数为:
'，-i—一1一'
63=（c3+△c3）-CbBP3
3
=8-508-15-7<0
-2
故，原最优方案不变。
（3）第二个约束变为10x1+5x2+10x30100,最优解是否改变？
若改
变，请求出
11
CBBP1=-5-50=0<0;
14
1
=5-50=0<0;
1
第二个约束的右端由90变为100b%=：
02；；20”
中各分量均大于0。
综上所述，做该变化后原最优方案即最优解不变。
（4）x1系数列向量（-1,12）T变为（0,5）T,最优解是否改变？
若改
变，请求出。
x1为基变量，有C'CbB-1R'=-5-500-5<0,所以原
5
最优方案不变。
（5）增加一个约束条件2x1+3x2+5x3050,最优解是否改变？
若改
变，请求出。
将最优解（xi,X2,X3,x4,X5）T=（0,20,0,0,10）T代入得60<
50显然不满足，说明约束条件起作用。
在以上约束条件中加入松弛变量x6后得2xi+3x2+5x3+x6=50
列单纯形法解题，过程如下：
C
-5
5
13
0
0
0
G
Xb
b
x1
乂2
乂3
x4
乂5
x6
5
x2
20
-1
1
3
1
0
0
0
x5
10
16
0
-2
-4
1
0
0
x6
50
2
3
5
0
0
1
Z
-100
0
0
-2
-5
0
0
上表中，由于乂2,乂5是基变量，必须为单位向量，因此将乂2,乂5
化为单位向量得：
C
-5
5
13
0
0
0
Q
Xb
b
x1
乂2
乂3
x4
乂5
x6
5
乂2
20
-1
1
3
1
0
0
0
乂5
10
16
0
-2
-4
1
0
0
x6
-10
5
0
-4
-3
0
1
Z
-100
0
0
-2
-5
0
0
虽然检验数行全部都是小于等于0的数了，但b列出现-10,所
以这张单纯形表已经不是最优表，用对偶单纯形法求解过程如下：
C
-5
5
13
0
0
0
CB
Xb
b
X1
X2
X3
X4
X5
X6
5
X2
20
-1
1
3
1
0
0
0
X5
10
16
0
-2
-4
1
0
0
X6
-10
5
0
[-4]
-3
0
1
Z
-100
0
0
-2
-5
0
0
5
X2
25/2
11/4
1
0
-5/4
0
3/4
0
X5
15
27/2
0
0
-5/2
1
-1/2
13
X3
5/2
-5/4
0
1
3/4
0
-1/4
Z
-95
-5/2
0
0
-7/2
0
-1/2
此时，b列数字均大于0,检验数行也都小于等于0,故，此时为最优表。
因此，最优解是（Xi,X2,X3,X4,X5,X6）T=（0,25/2,5/2,0,15,0）T,最优值maXZ=95.
（6）第一个约束条件的右端常数由20变为30,最优解是否改变？
若改变，请求出。
B-1b=103030，其中有小于0的分量，故最优解改变。
419030
也因为有小于0的分量，所以需要用对偶单纯形法来求解，其过程如
下:
C
-5
5
13
0
0
CB
Xb
b
x1
x2
x3
x4
Xs
5
x2
30
-1
1
3
1
0
0
x5
-30
16
0
[-2]
-4
1
Z
-150
0
0
-2
-5
0
5
x2
-15
23
1
0
[-5]
3/2
13
x3
15
-8
0
1
2
-1/2
Z
-120
-16
0
0
-1
-1
0
x4
3
-23/5
-1/5
0
1
-3/10
13
x3
9
6/5
2/5
1
0
1/10
Z
-117
-103/5
-1/5
0
0
-13/10
此时，b列数字均大于0,检验数行也都小于等于0,故，此时为最优表。
因此，最优解是（xi,x2,x3,x4,x5）t=（0,0,9,3,0）T最优值maxZ=117.
（7）第二个约束条件的右端常数由90变为70,最优解是否改变？
若改变，请求出。
B-1b=102020，其中有小于0的分量，故最优解改变。
417010
也因为有小于0的分量，所以需要用对偶单纯形法来求解，其过程如下：
C1
1-5
5
13
0
0
G
Xb
b
xi
x2
x3
x4
乂5
5
x2
20
-1
1
3
1
0
0
乂5
-10
16
0
[-2]
-4
1
Z
-100
0
0
-2
-5
0
5
x2
5
23
1
0
-5
3/2
13
x3
5
-8
0
1
2
-1/2
Z
-90
-16
0
0
-1
-1
此时，b列数字均大于0,检验数行也都小于等于0,故，此时
为最优表。
因此，最优解是（Xi,x2,x3,x4,x5）t=（0,5,5,0,0）
最优值maxZ=90.
运输问题求解：
求解方法：
表上作业法：
步骤一：
确定初始调运方法（数格个数为m+n-1）
1.最小元素法：
按运价最小的优先调运原则确定初始方案。
2.伏格尔法：
①分别计算表中隔行和割裂中最小运费和次小运费的差额，弁
填入表中的最右列和最下行；
②从行和列的差额中选最大者，选择其所在的行或列中的最小
元素，按类似于最小元素法优先供应。
划去相应的行或列；
③对表中未划去的元素，重复①②，知道所有行和列划完。
步骤二：
最有调运方案的判别（如何计算空格的检验数）
1.闭回路法：
以空格出发形成的闭回路，故此空格的检验数为：
奇顶点运费之和一偶顶点运费之和
对目标函数要求极小化的运输问题，当所有检验数）0时，
才为最优方案。
2.位势法：
在运价表中增加Vj行和Ui列，任意取某个位任意为
确定值，而后在确定其他行和列的Vj、和Ui值。
再用公式
5=cij-（Ui+Vj）
算出检验数，当所有检验数）0时，才为最优方案。
步骤三：
用闭回路发调整方案（即出现）＜0时）
若有2及以上，选其中负数检验数最小的正检验数以及它对
应的格为调入格，做它的闭回路，。
=min｛闭回路中偶数拐点的运量｝,而后在奇数拐点（+1）增加8个单位，在偶数拐点（-1）减少e个单位。
而后重新用位势法计算空格检验数。
重复以上操作，直到所有的空格的检验数均为>0.
几点说明：
1.在最优方案中某空格检验数为0时，由线性规划的理论知，一定由多重最优解。
2.退化情况：
表上作业法求解运输问题出现退化情况时,须在相应格中填上一个0,以表示此格为数格。
有以下两种情况：
①确定初始方案时,若出现同时划去一行和一列,则需在填写数格的行或列上,再添一个“0”数格。
②闭回路调整时，若同时有r（r>1）个最小值格时，则需在要划去的这r个数格中改填（r-1）个“0”数格
整数规划求解：
一、一般整数规划的解法：
分枝定界法
先不考虑原整数规划问题中的整数性约束，去解其相应的松
弛问题。
订下界z=0,上界z=其松弛问题最优解。
在求解子问题时遵循：
1.松弛问题无可行解，则不再分枝。
2,松弛问题的解满足整数性约束，则不再分枝。
如果目标函数数值大于目前的下界值，则修改下界值。
3,松弛问题的解的目标函数值不大于目前下界值，则不再分枝。
二、0-1整数规划的解法
完全枚举法：
隐枚举法：
三、指派问题的解法：
匈牙利法
设有n个人去分派去作n项工作，要求每项工作需且仅需一个人去做。
每个人做且仅作一项工作，一直某人完成某工作的效率是Cij,问应该怎样指派，才能使总的工作效率最好。
步骤一：
变化指派问题的系数矩阵，使在各行各列中都出现0
元素。
若行（列）已经有0,则不用再剪；如没有，则：
①从系数矩阵的每行元素中减去该行的最小元素。
②再从所得系数矩阵的每列元素中减去该列的最小元素。
步骤二：
进行试指派，寻求最优解
①从只有一个0元素的行（列）开始，给这个0元素加圈，记作
◎。
划去◎所在行（列）的其他0元素，弁记作。
。
②若◎元素的数目m等于矩阵的阶数n,则指派问题的最优解得
出；若m步骤三：
确定独立0元素最多。
①对没有◎的行打，
②对已打，的行中所有含0元素的列打，
③再对打，的列中含◎元素的打，④重复②③知道打不出新的，。
⑤对没有打，的行画横线，对有打，的列画横线，得直线数k
⑥若k然后在打
，行各元素中都减去这个最小元素，而在打，列的各，元素都加
上这个最小元素。
若得到n个独立的0元素，则已得到最优解，否则返回第三步重新进行。
步骤四：
在没有被直线覆盖的部分中找出最小元素，然后在打，行的各元素中都减去这个最小元素，而在打，列的个元素都加上这个最小元素。
使每行每列都
有0元素
◎的数目m等于矩阵的阶数n,则为指派问题最优解。
◎的数目m小于矩阵的阶数n,则进行第三步打，，之后画直线
最大流最小截集：
一、求最小树：
（1）用破圈法求最小树的具体步骤是:
第一步：
先任取一个圈,从圈中去掉一条权最大的边,若在同一圈中有几条都是权最大边,则任选其中的一条边去掉.
第二步：
在余下的
升级会员 