系统工程复习资料.docx
一、填空1、线性规划的数学模型中,决策者对于实现目标的限制因素称为一约束条件O2、在可行解区中,通过各极点作与目标函数直线斜率相同的平行直线,这些平行直线称之为_等值线O3、线性规划数学模型中,实际系统或决策问题中有待确定的未知因素,称之为_变量.4、对于供求平衡的运输问题,表上作业法是在平衡表的基础上首先求出一个初始调运方案_。5、图解法中,可行解区域内满意目标函数的解称之为一可行解一o6、通过一种数学的迭代过程,逐步求得线性规划多变量模型最优解的方法,称之为单纯形法一O7、用单纯形法求解线性规划问题时,若约束条件是等于或小于某确定数值,则应在每个不等式中引入一个松驰变量O8、线性规划的图解法适用于只含有23个变量的线性规划问题o9、若B是原规划的最优可行基,则最优单纯形乘子Y*=QBi是其对偶规划的最优解_。10、在线性规划模型中,没有非负约束的变量称为自由变量。11、在图论中,表示对象之间的某种特定的关系,通常用边或弧表示o12、原问题的第i个约束方程是“=”型,则对偶问题的变量Yi是自由变量o13、在线性规划中,凡满意约束条件的解均称之_可行解o14、单纯形法求解线性规划问题时,若要求得基础解,应令非基变量全为0o15、使用线性规划单纯形法时,为了将模型转换成标准形式,我们可以在每个不等式中引入一个新的变量,这个新变量称松驰变量O16、在线性规划的图解法中,全部可行解所分布的区域称之为可行解区。17、在线性规划中,设约束方程的个数为m,变量个数为n,mVn时,我们可以把变量分为基变量和非基变量两部分,基变量的个数为_m个o18、使目标值达到最优的可行解叫做最优解。19、假如实际运输问题的产销不平衡,为了转化为平衡的运输问题,我们可以虚设一个产地或销地_。20、在产销平衡运输问题中,设产地为m个,销地为n个,那么基可行解中非零变量的个数(不能大于(m+n-l)-o21、在一个网络中,假如图形是连通且不含圈的,则这种图形称之为一树o22、关于线性规划问题,叙述正确的为其最优解若存在,在可行解中必有最优解一o23、使用人工变量法求解极大化线性规划问题时,当全部的检验数%O,在基变量中仍含有非零的人工变量,表明该线性规划问题无可行解。24、运输问题的解是指满意要求的各供应点到各需求点的运量。25、在运输问题中假如总需求量小于总供应量,则求解时应虚设一个需求点.26、在线性规划中,设约束方程的个数为m,变量个数为n,m<n时,可以把变量分为基变量和非基变量两部分,基变量的个数为m个,非基变量的个数为一n-m个27、某配电站要向由其供电的五个小区铺设电缆,此时应采纳的方法是最短路线法28、树T的任意两个顶点间恰好有一条初等链。29、在方案项目的各项错综简单的工作中,抓住其中的关键活动进行方案支配的方法,称之为关键路线法O30、从网络的始点开头,顺着箭线的方向,到达网络终点的一条通路,称之为_线路O31、网络方案技术是解决哪类管理问题的科学方法?组织生产和进行方案管理O32、分支定界法主要是用来解决哪类问题的方法?整数规划问题o33、争论竞争或斗争现象的数学理论和方法,称为对策论。X1+X2+¾=234、线性规划的约束条件为2玉+2+%4=4,则基可行解是_(0,0,2,4)_ox1,x2,x3,x4035、在网络方案技术中,以箭线表示工作,在箭线的两端画上圆圈,称之为大事36、在接受询问的专家之间组成一个小组,面对面地进行争论与磋商,最终对需要猜测的课题得出比较全都的意见,这种猜测方法是一专家小组法O37、在求最大值的线性规划问题中,松弛变量在目标函数中的系数为O。38、在采用单纯性法求目标函数最大值时推断最优解的方法是_检验数都小于或等于39、线性规划数学模型三要素:决策变量、约束条件、目标函数40、每一线性规划问题,都伴随另一线性规划问题,二者有亲密关系,互为对偶。41、争论竞争或斗争现象的数学理论和方法,称为一对策论o42、线性规划的解有唯一最优解、无穷多最优解、无界解和无可行解四种。43、若图的某顶点与某条边连接,则称它们彼此关联、44、假如一个图中既没有多重边,也没有环,这样的图称为简洁图o45、无向图是由顶点和弧构成的。46、线性规划的约束条件个数与其对偶问题的变量_个数相等。47、有向图是由顶点和弧构成的。48、用图解法求解两个变量的最大值线性规划问题时,应先依据约束条件画出可行解区,再依据目标函数画出等值线线,才可求出该问题的最优解。49、对于供求不平衡的运输问题,若需求量大于供应量,为了转化成供求平衡的运输问题,我们往往虚设一个_供应点O50、在运输方案中消失退化现象,是指数字格的数目小于m+nT。51、关于运输问题的说法中错误的是_运输方案的任何调整必会引起总运费的下降o52、在图论中,假如全部的点都可通过相互间的连线而连通,则这种图形称之为连通图53、综合运用方案评核术和关键路线法的一种先进的方案管理方法称为网络方案技术54、虚活动不占用时间,也不消耗资源o55、盼望在“专家群”中通过匿名方式取得比较全都的意见而实行的定性猜测方法属于专家小组法56、使目标函数值达到最优值的可行解,称为最优解o57、在图论方法中,通常用顶点表示人们争论的对象,用边表示对象之间的某种联系。58、假如树T的顶点数为n,那么它的边数=n-1。59、若去掉某整数规划中的整数约束,就得到原整数规划问题的松弛问题。60、起点和终点为同一个顶点的链称为圈:二、推断改错1、在线性规划问题的求解过程中,基变量和非基变量的个数是固定的。()2、图解法供应了求解线性规划问题的一般方法。(X)改正:单纯性法供应了求解线性规划问题的一般方法。3、产地数与销地数相等的运输问题是产销平衡运输问题。(X)改正:总产量与总销量相等的运输问题是产销平衡运输问题。4、线性规划问题的每一个基本可行解对应可行域上的一个顶点。()5、线性规划问题的一般模型中不能有等式约束。(X)改正:线性规划问题的一般模型中可以有等式约束及不等式约束,6、在任一图G中,当点集V确定后,树图是G中边数最少的连通图。()7、同一问题的线性规划数学模型是唯一的。(X)改正:同一问题的线性规划模型不是唯一的。8、若在网络图中不存在关于可行流f的增流链时,f即为最大流。()9、假如线性规划的原问题存在可行解,则其对偶问题肯定存在可行解。(X)改正:假如线性规划的原问题存在可行解,且其目标函数值有界,则其对偶问题肯定存在可行解10、分派问题(有时也称指派问题)属于整数规划问题。(J)11、无圈且连通简洁图G是树图。()12、线性规划问题的基本解就是基本可行解。(X)改正:线性规划问题的基本解中,解的重量假如都满意非负条件,则该基本解就是基本可行解。13、对偶问题的对偶肯定是原问题。()14、分支定界法是较胜利的求解一般线性规划问题的一种方法。(X)改正:分支定界法是较胜利的求解整数规划问题的一种方法。15、表上作业法是用来求解运输问题的一种方法。()16、若原规划和对偶规划都有可行解,则它们都有有限最优解,而且其最优目标函数值相等。()17、满意线性规划问题全部约束条件的解称为基本可行解。(X)改正:满意线性规划问题全部约束条件的解称为可行解,不肯定是基本可行解。18、网络最短路径是指从网络起点至终点的一条权和最小的路线。()三、简答1、什么是整数规划?整数规划分为哪几类?答:整数规划是数学规划的一个分枝,争论的是一类要求其部分或全部变量取整数的最优化问题。主要分为全整数规划、混合整数规划以及0-1规划问题。2、简述运筹学主要分支。答:线性规划、整数规划、动态规划、图与网络分析、网络方案、对策论、决策论、存储伦、排队论、多目标规划、非线性规划等。3、简述分支定界法的一般计算步骤。答:主要分为以下4步:1、任找一整数可行解,算出其目标函数值,以这个值为目标函数最优值现时的下界;2、将整数规划问题分解为子问题,即分支;3、求解子问题;得出非整数最优解,若其目标函数值小于原来问题最优目标函数值现时的下界,进行剪枝,若其目标函数值大于现时的下界,返回步骤2连续进行分支;4、当求出的目标函数值的上界等于下界时,就求得最优解。4、简述用运筹学解决实际问题时的主要步骤。答:1、明确问题2、建立模型3、设计算法4、求解模型5、解的检验6、评价结果。5、简述求解整数规划问题的一般框架。答:求解一个整数规划问题的一般框架是:1、逐次生成一个原问题的衍生问题,对每个衍生问题又伴随一个比它更简洁求解的松弛问题(该衍生问题称为其松弛问题的原问题);2、通过松弛问题的解来确定它的原问题的归宿,即其原问题已被解决(包括已得整数解或被舍弃)呢,还是要再生成一个或多个它的衍生问题来替代它;3、然后再选择一个至此尚未被舍弃或得解的原问题的衍生问题4、重复以上步骤直至不再剩有未解决的衍生问题为止。6、什么是支撑生成子图?答:有图G1=(V1,EI)和G2=(V2,E2),若VI=V2和ElGE2,则Gl是G2的生成子图。7、什么是子图?答:有图G=(VLEl)和G2=(V2,E2),若VGV2#E1£E2,就称G是G2的子图。8、什么是关键线路?答:一般来说,不同线路所需时间是不同的,整个工程所需要的时间,是由耗时最多的那条线路打算的,因而称时间最长的线路为关键线路。9、什么是连通图?答:1、在一个无向图G中,若从顶点Vi到顶点Vj有路径相连(当然从Vj到Vi也肯定有路径),则称Vi和Vi是连通的:2、假如G是有向图,那么连接Vj和Vi的路径中全部的边都必需同向3、假如图中任意两点都是连通的,那么图被称作连通图。四、计算题1、求解下列矩阵对策。解:每行的min值为:(1,3,1),元素中最大值为3;每列的max值为(3,4,6),元素中最小的为3,于是maxminaij=minmaxaji=q一=3,i*=2,=1,故(ai,)是对策的解,ijJjtJiJ鞍点值=3。2、建立下面生产方案问题的数学模型。某工厂拥有A、B、C三种类型的设施,生产甲、乙两种产品,每件产品在生产中需要使用的机时数,每件产品可以获得的利润,以及三种设施可采用的机时数见下表。如何支配生产,利润最大?产品甲产品乙设施力量/h设施A3265设施B2140设施C0375利润/(元元牛)15002500解:MarZ=I500±+2500x23x1+2x2<65s.t.<2x1+x2403x275x1,x203、建立下面生产方案问题的数学模型。某厂I、II、III三种产品分别经过A、B、C三种设施加工。已知生产单位各种产品所需的设施台时,设施的现有加工力量及每件产品的预期利润见下表。建立线性规划模型,求获利最大的产品生产方案。IIIIII设施力量(台.h)A111IOOB1045600C226300单位产品利润(元)1064解:建立线性规划模型为:Maxz=IOx1+6x2+4x3x1+x2+x3100s.t.<IOx1+4x2÷5x36002x1+3x2+6x3300xl,x2,x304、将下面的线型规划问题写成标准型。Minz=-X1÷2x23X3+X2÷x37S.t.X'X2十%32【一3M÷X2÷2x3=7jv1,jv20,三无约束解:MaXZ=X-2x2+3(x4-x5)+Ox6+Ox7X1+X2÷(4-)÷x6=7Xl_X)+(x4-x5)-X1=2s.t.'-3x1+x2+2(x4-x5)=75、用避圈法(加边)法,对下图求最小生成树。解:最小树的权为:236、用乐观法进行选择。某企业生产三种产品Ai、A2、A3o每种产品在销售时可能消失销路好(Si),销路一般(Sz)和销路差(S3)三种状态,每种产品在不同销售状态的获利状况(效益值)如下表所示,请按乐观法则进行决策,选取生产哪种产品最为合适。状态产甫:SiS2S3Ai3010-6A220129A3151312解:首先找出每个方案的最大效益:30,20,15,再找出其中最大的元素30,它所对应的策略就是所选策略,即选方案Al7、已知一个线性规划原问题如下,请写出对应的对偶模型。Maxz=5x+3%2+2为+4-5x+Xz+无+8x48s.t<2x+4%2+3x3+2%4=10X,X10,%3,%4无约束解:minw=8yi+IOy25y+2y0y+4>23s.t.y+3»=28y+2»=4yO,y2无约束8、已知运输问题的运价表和发量和收量如下所示,请用最小元素法求出运输问题的初始方案,并求出初始方案所对应的目标函数值。.销地产地BlB2B3产量Al51612A224014A33674销量91011解:2103114初始成本为389、用避圈法(加边)法,对下图求最小生成树,并写出最小树的权。VlO最小数的权为:19V9