运筹学期末考试题型

1、运筹学一、填空题（1分*10题）运筹学建模一般步骤：1.提出问题，明确目标2,构建模型3 .求解与检验4 .结果分析与实施确定型模型和概率模型包含哪些内容：确定型模型主要包括：线性规划、整数规划、目标规划、非线性规划、动态规则、图与网络；概率型模型主要包括：决策论、对策论、排队论、存储论、维修更新理论、搜索论、可靠性和质量管理等二、选择题（2分*5题）1,整数规划的常见解法：分枝定界法、割平面法（求解0-1规划的常用算法：完全枚举法、隐枚举法）（求解指派问题的常用算法：匈牙利法）5 .目标规划的基本概念:决策变量和偏差变量：决策变量又称控制变量,用xi表示.在目标规划中，引进正、负偏差变量，分

2、别用di+和di-表示.di+为正偏差变量,它表示实际决策值超过第i个目标值的数量；di-为负偏差变量,它表示实际决策值低于第i个目标值的数单。资源约束和目标约束：资源约束是指必须严格满足的等式或不等式约束,又称为硬约束.目标约束是目标规划特有的,它把要预定的目标值作为右端的常数项,在达到目标值时允许发生正或负的偏差量,因此，目标约束是软约束，具有一定的弹性.目标约束不会不满足,但可能偏差过大.优先因子与权系数：目标规划中,当决策者要求实现多个目标时，为使多个目标统一在单一目标中,且按主次或轻重缓急依次实现,故引进优先因子.凡要求第一位达到的目标赋予优先因子P1,次位的目标赋予优先因子P2,P

3、k+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 .阶段根据问题的特点和需要,将问题的

4、全过程恰当地划分为若干个相互联系的阶段，以便把问题分解成若干子问题逐个求解.本章用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 .决策与决策变量决策是指在某一阶段状态给定以后，从该状态演变至下一阶段某状态的选择.描述决策的

5、变量称为决策变量.用dk(sO表示第k阶段处丁状态sk时的决策变量.dk(sL)的可能值全体构成决策集合Dk(&).如例1中，D1(A)=4 .状态转移与状态转移方程系统由这一阶段的一个状态转变到下一阶段的另一个状态称为状态转移,状态转移既与状态有关，又与决策有关,描述状态转移关系的方程称为状态转移方程.若笫k阶段的状态变量必与该阶段的决策变量小确定后，第k+1阶段的状态变量必一也随之确定，则它们的关系式i=Tk(»,dO称为由状态盘转移到状态”一的状态转移方程.反之.若第k阶段的状态变量“与k1阶段的决策变量确定后，笫k-1阶段的状态变量隘也随之确定，则它们的关系式Sk-1

6、=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 .阶段指标阶段指标是对过程中

7、某一个阶段的决策效果衡量其优劣的一种数量指标，第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的最优值称为最

8、优指标函数.记为37.它表示从第k阶段的状态泣开始.选取最优策略(或增优后部子策略)后，得到的指标函数值.在例1中，f“A)表示从始点A到终点E的管线最短长度.从例)的计算过程可以看到,在求解的各个阶段，我们运用了如下递归关系：fi(si)=minVk(sk.di(si)+fi+(st+)disi)FDk(%)(k=4,3,2,1)f3(a)0.这种递归关系就是科动态规划函数方程，三、简答题(10分*2题)线性规划模型一般型、标准型、矩阵形式、线性规划模糊解的基本概念：动态规划方程、最优化原理：最优化原理即，“作为整个过程的最优策略具有这样的性质,即无论过去的状态和决策如何,对前面的决策所形成

9、的状态而言,余下的诸决策必须构成最优策略.”由动态规划最优化原理可以得到体现这一原理思想的函数基本方程：f1(Si)-upt(V1(i,dk(Sk)+ft*J(51*J)dn(sr)eDJaj(k=ntn*1.*】)(4.1)fm-lSn-fI)=0.这里ipt表示“最优二即代表“最大”(max)化或“最小中而黑)化四、建立运筹学模型（10分*1题）只需要建模就好，不求解。刘满凤教材运筹学教程2.4节（即对一些线性规划问题的实际应用案例建模，来解释线性规划问题建模的基本思路、方法和技巧）五、计算题（10分*5题）对偶理论:i,对背格式的对偶问题对标黯式的对偶向题川矩阵表示，若母问题是muxZ=

10、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

11、）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,14XbX、XlQC1,B-lN-CnCuB-1YiYY对偶单纯形方法：第一步：建立线性规划问题的初始单纯形表.设表中检验数行的值2厂©全部30,即是其对偶问题的一个可

12、行解一第二步：检行b列的数字，若均非负，则已得最优解，停止计算.若b列有负分量，则转第三步.第三步：换基迭代（1）确定换出变量按mini魏Bb）K0=，确定基变量Xr为换出变量.（2）确定换入变量杵单纯在发中检杳k闷一行的各系数a（J”.n）.若所有au三。,则上也门解.停止计算.否则，计算确定"为换入变量.(3)以a”为主元素，按原单纯形法在表中进行初等行变换，得到新基的单纯形表.返网第二步.例14用对偶单纯形法求解下列线性规划问题.minZ=12yi+8y?+16y3+12y2yi4-y2+4yj22s.t.2yi+2y2+4y3yi>0(i=1,2,3,4).解先将问题化

13、为maxZ1=-12yi-8y-16yL12y,+Oys+0”-2y1-ya-4y»+y5=-2s.t.-2yi-2y24y4+y6=-3y-y620用对偶单纯法进行计算，其过程见表2.15.表2.15-12-8-16-1200GXbby>户y>广ys*00y«V6-2-3-2-2-1-2-400-4100IZ，0128161200一g0-12ysJU-23/4-21/2-4Z9-96216003-g812丫22-1/42-1/2104-201-11/20-1/4Z，-13208023q-816V33/21/811/4100121/20

14、-1/4-1/21/8E-14000442一q至此，得原问题的最优解y=(yi,y2,yj,y4)r=(0,3/2,1/8,0)r.最优值为Z*=-Z'=14.灵敏度分析:F列线性规划问题:maxZ5x1xs.t.12x1x24x25x23x310x313x32090x1、x2、X3解：先将该线性规划化引入松弛变量乂4,乂5,得:maxZ5x15x2x1x23x3st.12x14x210x313x3x420x590x1、x2、x3、x4、x(1)求出该问题的最优解和最优值:C?-5513000CBXbbXix2x3x4x50x420-11310200x590124100122.5Z0-

15、5513005x220-113100x510160-2-41Z-10000-2-50T故，得其最优解为(x1,x2,x3,x4,x5)T=(0,20,0,0,10)最优值为maxZ=100.(2)目标函数中X3系数变为8,最优解是否改变？若改变，请求出由(1)得知，X3为非基变量，故其检验数为:'，-i一1一'63=(c3+c3)-CbBP33=8-508-15-7<0-2故，原最优方案不变。(3)第二个约束变为10x1+5x2+10x30100,最优解是否改变？若改变，请求出11X1系数列由1变成11210B1R=101411011411CBBP1=-5-50=0<

16、;0;14改系数列由4变成;加P2=1405C2-CBB-1B1=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显然不满足，说明约束条件起作

17、用。在以上约束条件中加入松弛变量x6后得2xi+3x2+5x3+x6=50列单纯形法解题，过程如下：C-5513000GXbbx1乂2乂3x4乂5x65x220-1131000x510160-2-4100x650235001Z-10000-2-500上表中，由于乂2,乂5是基变量，必须为单位向量，因此将乂2,乂5化为单位向量得：C-5513000QXbbx1乂2乂3x4乂5x65乂220-1131000乂510160-2-4100x6-1050-4-301Z-10000-2-500虽然检验数行全部都是小于等于0的数了，但b列出现-10,所以这张单纯形表已经不是最优表，用对偶单纯形法求解过程如下

18、：C-5513000CBXbbX1X2X3X4X5X65X220-1131000X510160-2-4100X6-1050-4-301Z-10000-2-5005X225/211/410-5/403/40X51527/200-5/21-1/213X35/2-5/4013/40-1/4Z-95-5/200-7/20-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=10

19、3030，其中有小于0的分量，故最优解改变。419030也因为有小于0的分量，所以需要用对偶单纯形法来求解，其过程如下:C-551300CBXbbx1x2x3x4Xs5x230-113100x5-30160-2-41Z-15000-2-505x2-152310-53/213x315-8012-1/2Z-120-1600-1-10x43-23/5-1/501-3/1013x396/52/5101/10Z-117-103/5-1/500-13/10此时，b列数字均大于0,检验数行也都小于等于0,故，此时为最优表。因此，最优解是(xi,x2,x3,x4,x5)t=(0,0,9,3,0)T最优值max

20、Z=117.(7)第二个约束条件的右端常数由90变为70,最优解是否改变？若改变，请求出。B-1b=102020，其中有小于0的分量，故最优解改变。417010也因为有小于0的分量，所以需要用对偶单纯形法来求解，其过程如下：C11-551300GXbbxix2x3x4乂55x220-113100乂5-10160-2-41Z-10000-2-505x252310-53/213x35-8012-1/2Z-90-1600-1-1此时，b列数字均大于0,检验数行也都小于等于0,故，此时为最优表。因此，最优解是(Xi,x2,x3,x4,x5)t=(0,5,5,0,0)最优值maxZ=90.运输问题求解：

21、求解方法：表上作业法：步骤一：确定初始调运方法（数格个数为m+n-1）1 .最小元素法：按运价最小的优先调运原则确定初始方案。2 .伏格尔法：分别计算表中隔行和割裂中最小运费和次小运费的差额，弁填入表中的最右列和最下行；从行和列的差额中选最大者，选择其所在的行或列中的最小元素，按类似于最小元素法优先供应。划去相应的行或列；对表中未划去的元素，重复，知道所有行和列划完。步骤二：最有调运方案的判别（如何计算空格的检验数）1 .闭回路法：以空格出发形成的闭回路，故此空格的检验数为：奇顶点运费之和一偶顶点运费之和对目标函数要求极小化的运输问题，当所有检验数）0时，才为最优方案。2 .位势法：在运价表中

22、增加Vj行和Ui列，任意取某个位任意为确定值，而后在确定其他行和列的Vj、和Ui值。再用公式5=cij-（Ui+Vj）算出检验数，当所有检验数）0时，才为最优方案。步骤三：用闭回路发调整方案（即出现）0时）若有2及以上，选其中负数检验数最小的正检验数以及它对应的格为调入格，做它的闭回路，。=min闭回路中偶数拐点的运量,而后在奇数拐点(+1)增加8个单位，在偶数拐点(-1)减少e个单位。而后重新用位势法计算空格检验数。重复以上操作，直到所有的空格的检验数均为>0.几点说明：1 .在最优方案中某空格检验数为0时，由线性规划的理论知，一定由多重最优解。2 .退化情况：表上作业法求解运输问题出

23、现退化情况时,须在相应格中填上一个0,以表示此格为数格。有以下两种情况：确定初始方案时,若出现同时划去一行和一列,则需在填写数格的行或列上,再添一个“0”数格。闭回路调整时，若同时有r(r>1)个最小值格时，则需在要划去的这r个数格中改填(r-1)个“0”数格整数规划求解：一、一般整数规划的解法：分枝定界法先不考虑原整数规划问题中的整数性约束，去解其相应的松弛问题。订下界z=0,上界z=其松弛问题最优解。在求解子问题时遵循：1.松弛问题无可行解，则不再分枝。2,松弛问题的解满足整数性约束，则不再分枝。如果目标函数数值大于目前的下界值，则修改下界值。3,松弛问题的解的目标函数值不大于目前下

24、界值，则不再分枝。二、0-1整数规划的解法完全枚举法：隐枚举法：三、指派问题的解法：匈牙利法设有n个人去分派去作n项工作，要求每项工作需且仅需一个人去做。每个人做且仅作一项工作，一直某人完成某工作的效率是Cij,问应该怎样指派，才能使总的工作效率最好。步骤一：变化指派问题的系数矩阵，使在各行各列中都出现0元素。若行（列）已经有0,则不用再剪；如没有，则：从系数矩阵的每行元素中减去该行的最小元素。再从所得系数矩阵的每列元素中减去该列的最小元素。步骤二：进行试指派，寻求最优解从只有一个0元素的行（列）开始，给这个0元素加圈，记作。划去所在行（列）的其他0元素，弁记作。若元素的数目m等于矩阵的阶数n,则指派问题的最优解得出；若m<n,则进行步骤三。步骤三：确定独立0元素最多。对没有的行打，对已打，的行中所有含0元素的列打，再对打，的列中含元素的打，重复知道打不出新的，。对没有打，的行画横线，对有打，的列画横线，得直线数k若k<n,从没有被直线覆盖的部分中找出最小元素。然后在打，行各元素中都减去这个最小元素，而在打，列的各，元素都加上这个最小元素。若得到n个独立的0元素，则已得到最优解，否则返回第三步重新