最全的运筹学复习题及答案

1717.求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。5、线性规划数学模型具备哪几个要素答：（1）.求一组决策变量Xi或xu的值（i5、线性规划数学模型具备哪几个要素mj=1,2…n）使目标函数达到极大或极小； （2）.表示约束条件的数学式都是线性等式或不等式；（3）.表示问题最优化指标的目标函数都是决策变量的线性函数第二章 线性规划的基本概念一、填空题.线性规划问题是求一个线性目标函数 在一组线性约束条件下的极值问题。.图解法适用于含有两个变量的线性规划问题。.线性规划问题的可行解是指满足所有约束条件的解。.在线性规划问题的基本解中，所有的非基变量等于零。_.在线性规划问题中，基可行解的非零分量所对应的列向量线性无关.若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。.线性规划问题有可行解，则必有基可行解。.如果线性规划问题存在目标函数为有限值的最优解， 求解时只需在其基可行解 的集合中进行搜索即可得到最优解。.满足非负条件的基本解称为基本可行解。.在将线性规划问题的一般形式转化为标准形式时， 引入的松驰数量在目标函数中的系数为基.将线性规划模型化成标准形式时， “w”的约束条件要在不等式左_端加入松弛变量。.线性规划模型包括决策（可控）变量，约束条件，目标函数三个要素。.线性规划问题可分为目标函数求极大值和极小值两类。.线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。.线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解.在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则这段边界上的一切点都是最优解。.如果某个约束条件是y情形，若化为标准形式，需要引入一松弛变量。.如果某个变量X为自由变量，则应引进两个非负变量 X,X,同时令X=X‘一X。.表达线性规划的简式中目标函数为 max(min)Z=汇5xu。P5)) 线性规划一般表达式中， au表示该元素位置在i行j列。.、单选题.如果一个线性规划问题有 n个变量，m个约束方程(m<n),系数矩阵的数为m,则基可行解的个数最为_C_。A.m个 B.n个C .Gm D.Cn个TOC\o"1-5"\h\z.下列图形中阴影部分构成的集合是凸集的是 A<B>co<r>>.线性规划模型不包括下列D要素。A.目标函数 B .约束条件 C.决策变量 D.状态变量.线性规划模型中增加一个约束条件，可行域的范围一般将 _B_。A.增大 B.缩小C.不变D.不定.若针对实际问题建立的线性规划模型的解是无界的，不可能的原因是 B__。A.出现矛盾的条件 B.缺乏必要的条件 C.有多余的条件D.有相同的条件.在下列线性规划问题的基本解中，属于基可行解的是 _DA.(—1,0,O)TB.(1,0,3,0)TC.(一4,0,0,3)TD.(0,—1,0,5)T.关于线性规划模型的可行域，下面 _B_的叙述正确。A.可行域内必有无穷多个点 B.可行域必有界C.可行域内必然包括原点 D.可行域必是凸的.下列关于可行解，基本解，基可行解的说法错误的是 _D__.A.可行解中包含基可行解 B .可行解与基本解之间无交集行解C.线性规划问题有可行解必有基可行解D.满足非负约束条件的基本解为基可.线性规划问题有可行解，则AA行解C.线性规划问题有可行解必有基可行解D.满足非负约束条件的基本解为基可.线性规划问题有可行解，则AA必有基可行解 B 必有唯一最优解 C 无基可行解D无唯一最优解.线性规划问题有可行解且凸多边形无界，这时 工A没有无界解B 没有可行解 C有无界解 D 有有限最优解.若目标函数为求max,一个基可行解比另一个基可行解更好的标志是AA使A使Z更大B使Z更小绝对值更大 DZ 绝对值更小.如果线性规划问题有可行解，那么该解必须满足 DA所有约束条件B变量取值非负 C所有等式要求D 所有不等式要求.如果线性规划问题存在目标函数为有限值的最优解，求解时只需在 D集合中进行搜索即可得到最优解。A基B 基本解C基可行解D可行域.线性规划问题是针对D求极值问题.A约束B 决策变量 C秩 D 目标函数15如果第K个约束条件是y情形，若化为标准形式，需要BA左边增加一个变量 B右边增加一个变量 C左边减去一个变量D右边减去一个变量.若某个bk<0,化为标准形式日立原不等式D—A不变B 左端乘负1C右端乘负1D 两边乘负1.为化为标准形式而引入的松弛变量在目标函数中的系数应为 AA0 B1C2D3.若线性规划问题没有可行解，可行解集是空集，则此问题BA没有无穷多最优解 B 没有最优解C有无界解D 有无界解三、多选题.在线性规划问题的标准形式中，不可能存在的变量是 D.A可控变量B.松驰变量c.剩余变量D.人工变量.下列选项中符合线性规划模型标准形式要求的有 BCD6.6.下列模型中，属于线性规划问题的标准形式的是 ACDA.目标函数求极小值B.右端常数非负C.变量非负D.约束条件为等式E.约束条件为“W的不等式.某线性规划问题，n个变量，m个约束方程，系数矩阵的秩为 m(m<n)则下列说法正确的是ABDEA.基可行解的非零分量的个数不大于mB基本解的个数不会超过Cn个C.该问题不会出现退化现象D.基可行解的个数不超过基本解的个数E.该问题的基是一个mKm阶方阵4.若线性规划问题的可行域是无界的，则该问题可能 ABCDA.无有限最优解B.有有限最优解C.有唯一最优解D.有无穷多个最优解E.有有限多个最优解.判断下列数学模型，哪些为线性规划模型 (模型中a.b.c为常数；。为可取某一常数值的参变量，x,Y为变量)ACDEC.minZ=£a,x,J+Sb：y-:S・t.《&・¥.为自由变量.….….m.)D*maxZ=jt弋,大这卜+虫8(i=1,2,…m)E.maKZ=ZK/CltZkmlh・l,x,t>O(i=1.2,…=1.2…，m)A.maxZ=X|+4r2%一%42B.maxZ=5xLA.maxZ=X|+4r2%一%42B.maxZ=5xL+2x2s.t.Ui+x，2C.minZ=5瓦+&Jxl-I(I^=20Wr+vTD,rnaxZ=6%+机M『x：»2瓦打产Is.t?3xi+4x2-L5工鸣邦.下列说法错误的有_ABD、A.基本解是大于零的解 B.极点与基解一一对应C.线性规划问题的最优解是唯一的 D.满足约束条件的解就是线性规划的可行解.在线性规划的一般表达式中，变量 xu为ABEA大于等于0B小于等于0C大于0D小于0E等于0TOC\o"1-5"\h\z.在线性规划的一般表达式中，线性约束的表现有 CDEAvB>C£D>E=.若某线性规划问题有无界解，应满足的条件有 ADAPk<0B非基变量检验数为零C基变量中没有人工变量 DSj>OE所有8jW0.在线性规划问题中a23表不'AEAi=2Bi=3Ci=5Dj=2Ej=343.线性规划问题若有最优解，则最优解 ADA定在其可行域顶点达到 B 只有一个C会有无穷多个D唯一或无穷多个E其值为042.线性规划模型包括的要素有 CDEA.目标函数 B.约束条件C.决策变量 D 状态变量 E 环境变量四、名词1基：在线性规划问题中，约束方程组的系数矩阵 A的任意一个mxm阶的非奇异子方阵B,称为线性规划问题的一个基。2、线性规划问题：就是求一个线性目标函数在一组线性约束条件下的极值问题。3.可行解：在线性规划问题中，凡满足所有约束条件的解称为线性规划问题可行解4、行域：线性规划问题的可行解集合。5、本解：在线性约束方程组中，对于选定的基 B令所有的非基变量等于零，得到的解，称为线性规划问题的一个基本解。可以用在平面上作图的方法来求解， 这种6.、图解法：对于只有两个变量的线性规划问题，可以用在平面上作图的方法来求解， 这种方法称为图解法。7、本可行解：在线性规划问题中，满足非负约束条件的基本解称为基本可行解。8、模型是一件实际事物或实际情况的代表或抽象，它根据因果显示出行动与反映的关系和客观事物的内在联系。四、把下列线性规划问题化成标准形式：minZ-55—2啊%+jXj<42处事3X],总>0/科:mojtn'=-5/十X1+3工工+工3=4人"Wj *4A22x2+m,工31巧>0(>-1,2,3.4.5)2、minZ=2xi-x2+2x3=X]+#+X3不4t.J一的+X?-x3<6Ixj<0,x2>0fx3无约束2.令工I=-工/*4=工J-工3”・化为标准型为majcZ=ZmJ+x：- +2M3”'xj+x2+hJ—mJ=45.八：工I'+工工-工3,+胃3”+孙=6〔工l *JTJ1工*>。3-maxZ=2x：+ +3x3+x*产l+川+/+网工7上“如-8看i2x,+2%・引，电/0,取EO,也无约束

五、按各题要求。建立线性规划数学模型1、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示:单位、产品一心X资源ABC资源限最原材料1.01.54.02000机械台时2.01,21.01000单位利润101412根据客户订货，三种产品的最低月需要量分别为 200,250和100件，最大月销售量分别为250,280和120件。月销售分别为250,280和120件。 问如何安排生产计划，使总利润最大五J设4分别收枭三种产品的产■，划线性旗则稳型为wiiZ=1g+14科+12zjfx.+l.5rJ+4x)<20002工1+l-2ri+工i《1C002W<Jt<2503超250W为《280；100<xj<120txji>J)子。2、某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋90根，长度为4米的钢筋60根，问怎样下料，才能使所使用的原材料最省33.对于目标函数极大值型的线性规划问题，用单纯型法求解 时，当基变量检验数8j_S2.将10米长的钢筋裁为3米长和4米隹.共有以下几种下料方式t「n103米0234米2Li-i0设为，壬r科分别表乐采用I.11.111种下料方式的堀筋数।则旋性规则模整可写成；minZ=工.+xz+Xj)2工工+3xa>W+Xj60工].H1.工,善0.某运输公司在春运期间需要24小时昼夜加班工作，需要的人员数量如下表所示:起运时间服务员数2 66 1010一1414 1818 2222 248107124每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数最少3.设在第1时风上班的人数为&=1内.…,则St件双期模型为,D*minZ工12工，j-iJT]+Hq4工144*E+JTa二10*▼上.J 37■T*+H,>12+工修>4.工,》口(>=1第三章线性规划的基本方法一、填空题.线性规划的代数解法主要利用了代数消去法的原理， 实现基可行解的转换, 寻找最优解。.标准形线性规划典式的目标函数的矩阵形式是maxZ=CBB1b+(CN—酒卜沁。_0时，当前解为最优解。.用大M法求目标函数为极大值的线性规划问题时，引入的人工变量在目标函数中的系数应为二.在单纯形迭代中，可以根据最终 表中人工变量不为零判断线性规划问题无解。.在线性规划典式中，所有基变量的目标系数为 0。.当线性规划问题的系数矩阵中不存在现成的可行基时，一般可以加入人工变量构造可行基。.在单纯形迭代中，选出基变量时应遵循最小比值。法则。.线性规划典式的特点是基为单位矩阵，基变量的目标函数系数为 0。.对于目标函数求极大值线性规划问题在非基变量的检验数全部8 jWQ问题无界时，问题无解时情况下,单纯形迭代应停止。.在单纯形迭代过程中，若有某个8 k>0对应的非基变量Xk的系数列向量P_三_0_时，则此问题是无界的。.在线性规划问题的典式中，基变量的系数列向量为单位列向量.对于求极小值而言，人工变量在目标函数中的系数应取 -1.(单纯形法解基的形成来源共有三种.在大M法中，M表示充分大正数。二、单选题.线性规划问题C3272片才丁餐・稀埼肿KM靛疗触价糖1的惧叮门⑺球M_-A,r=(rrBrxry nr与关.在单纯形迭代中，出基变量在紧接着的下一次迭代中 B立即进入基底。A.会 B.不会C.有可能D.不一定.在单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中 BoA.不影响解的可行性B.至少有一个基变量的值为负 C.找不到出基变量D.找不到进基变量.用单纯形法求解极大化线性规划问题中，若某非基变量检验数为零，而其他非基变量检

验数全部<0,则说明本问题B。A.有惟一最优解 B.有多重最优解 C.无界D.无解.线性规划问题maxZ=CXAX=b,X>0中，选定基B,变量X的系数列向量为Pk,则在关于基B的典式中，X的系数列向量为__DT - —1A.BR B.BP< C.P<B D.BR.下列说法错误的是BA.图解法与单纯形法从几何理解上是一致的 B.在单纯形迭代中，进基变量可以任选C.在单纯形迭代中，出基变量必须按最小比值法则选取 D.人工变量离开基底后，不会再进基.单纯形法当中，入基变量的确定应选择检验数 C—A绝对值最大 B绝对值最小C 正值最大 D 负值最小.在单纯形表的终表中，若若非基变量的检验数有 0,那么最优解&A不存在B 唯一C 无穷多D 无穷大.若在单纯形法迭代中， 有两个Q值相等，当分别取这两个不同的变量为入基变量时， 获得的结果将是CA先优后劣 B先劣后优C相同D 会随目标函数而改变TOC\o"1-5"\h\z.若某个约束方程中含有系数列向量为单位向量的变量，则该约束方程不必再引入 CA松弛变量 B 剩余变量 C 人工变量 D自由变量.在线性规划问题的典式中，基变量的系数列向量为 DA单位阵B 非单位阵 C单位行向量D 单位列向量.在约束方程中引入人工变量的目的是 DA体现变量的多样性 B 变不等式为等式 C 使目标函数为最优D 形成一个单位阵.出基变量的含义是DA该变量取值不变 B该变量取值增大 C由0值上升为某值D由某值下降为0.在我们所使用的教材中对单纯形目标函数的讨论都是针对 B情况而言的。AminBmaxCmin+maxDmin,max任选AminBmaxCmin+maxDmin,max任选.求目标函数为极大的线性规划问题时， 若全部非基变量的检验数wQ且基变量中有人工变量时该问题有BA无界解B无可行解C 唯一最优解D无穷多最优解三、多选题1.对取值无约束的变量Xj。通常令Xj=Xj'-x"j,其中Xj'>0,Xj”>0,在用单纯形法求得的最优解中，可能出现的是 ABC8,1（>0,1*=01片。0。DEQQ.线性规划问题maXZ=X+CX'事储知后8其中4<c<6,一1<a<3,10<b<12,则当BC时,该问题的最优目标函数值分别达到上界或下界。A.c=6a=-1b=10B.c=6a=-1b=12C.c=4a=3b=12D.c=4a=3b=12E.c=6a=3b=12.设X（1）,X⑵是用单纯形法求得的某一线性规划问题的最优解，则说明ACDEA.此问题有无穷多最优解 B.该问题是退化问题C.此问题的全部最优解可表示为入X（1）+（1一入）X⑵，其中0W入W1D.X\X⑵是两个基可行解E.X⑴，乂2）的基变量个数相同.某线性规划问题，含有n个变量，m个约束方程，（m<n）,系数矩阵的秩为m,则ABD。A.该问题的典式不超过GM个B.基可行解中的基变量的个数为 m个C.该问题一定存在可行解D.该问题的基至多有CNM=1个E.该问题有111个基可行解.单纯形法中，在进行换基运算时，应ACDEA.先选取进基变量，再选取出基变量 B.先选出基变量，再选进基变量 C.进基变量的系数列向量应化为单位向量 D.旋转变换时采用的矩阵的初等行变换E.出基变量的选取是根据最小比值法则.从一张单纯形表中可以看出的内容有 ABCEA.一个基可行解B.当前解是否为最优解C.线性规划问题是否出现退化 D.线性规划问题的最优解E.线性规划问题是否无界.单纯形表迭代停止的条件为（AB）A所有6j均小于等于0B所有6j均小于等于0且有aikw0C所有ak>0D

所有biw0.下列解中可能成为最优解的有（ ABCDE）A基可行解B 迭代一次的改进解 C迭代两次的改进解D迭代三次的改进解E所有检验数均小于等于0且解中无人工变量9、若某线性规划问题有无穷多最优解，应满足的条件有（ BCE）APkVPkOB非基变量检验数为零C基变量中没有人工变量 DSjVOE所有8j&010.下列解中可能成为最优解的有（ ABCDE）A基可行解 B 迭代一次的改进解 C 迭代两次的改进解D迭代三次的改进解E所有检验数均小于等于0且解中无人工变量四、名词、简答1、人造初始可行基：当我们无法从一个标准的线性规划问题中找到一个 m阶单位矩阵时，通常在约束方程中引入人工变量， 而在系数矩阵中凑成一个m阶单位矩阵，进而形成的一个初始可行基称为人造初始可行基。2、单纯形法解题的基本思路 可行域的一个基本可行解开始，转移到另一个基本可行解，并且使目标函数值逐步得到改善，直到最后球场最优解或判定原问题无解。五、分别用图解法和单纯形法求解下列线性规划问题. 并对照指出单纯形迭代的每一步相当于图解法可行域中的哪一个顶点。2. =2x3+x2'5修<156x|(+22. =2x3+x2'5修<156x|(+2向京24s.t,\ -| +x3IX］，为r।半任**仁4k冉hr）札百■1-'六、用单纯形法求解下列线性规划问题:・曰力・曰力2^<[2I%，3k；1；1名L.*三41Kiii2~2iihrLU3si+X；+工.<6。X）电十九/1。*'Ld+&_事…也，为a。■f片5.。七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类*2x3+2处+为石4»|才七一,J=5*2x3+2处+为石4»|才七一,J=5Xi+2jes+3xs"IS2^*\*Hi—20吗*2玛+K>+Wm=10乔.J 於正术者#:1ft>*1臼 iiHFK.fAh*"Ky…〜IM「♦TOC\o"1-5"\h\z《Kf夫axx+K.-ar~》广 一“？|X1 +1XjA*i^C■»-5—Nrj一八«+k*+XLJ,-J尸一尸r. .J/*□^―/&r-◎，〜ut7*>KMK-*r%K;,一f1心由Mu//<pa木卡*r-Vi-ir■eiQG¥O—A>(%/fJFoe»E3»*上声14M4HHe-J«-八；0c>&-M/4&一狂</.)/j0与Xf-L^^r-/公Gr30g—A-1Mt_1,4-/OQ一Q7JfEjQ—Jrofit,尸、L。fK//A.O-5^*/,*OKrd/t^L.O3o2-*tV|/<rIof-G*/1-sAliL/£• b■,L-L-J_Le>-I**Q，・Xfd—f-aIcN喷 KTWdJ^hL.英1金二连4一斫狂;，木w*r-3-TOC\o"1-5"\h\z.,2..潮、+t为我一袤书外苞X.*■talrMj■>SAj A-<#上-J/■ (K■+ 4+3K与 f^SjF 352M『fKjl十步K■鼻 +X*Ix.+q^x4+j(去t-?s- =，*"X^ao《j0*，--0&)一木m/-—*7asLXi.R上XjXW.^J-%-H—勺—/Xc*Xi▽i3f-<>idf二)金夕/oD/Jo0a*OJ一£54E■*1与M+2号F30G一,■»dXLJC/Kd营/JF.牙0Joof,^<1F",—/¥d公j<?OCFJ口G々j更〜1o±7：上■-1^4/xrXpogf>■J-看iQ&d 0O,—金一名c- D3A17-—-2 Q —73 Xy 学〜%i5Zxd CZ1-0 0 * .、. ，口 G*c口 柒一抬一# # 0 , >-1.一后...._1一々 J。 A £> 一JN7-jM1J- fr1 tF***q**).N、/maxZ=5x+3x2maxZ=5x+3x2,约束形式为y,X%为松驰变量.表中解代入目标函数后得z=ioXX2X3X4一10b-1fg

X32CO11/5Xade01(1)求表中a〜g的值(2) 表中给出的解是否为最优解(2)表中给出的解为最优解(1)(2)表中给出的解为最优解第四章线性规划的对偶理论第四章线性规划的对偶理论一、填空题1,线性规划问题具有对偶性，即对于任何一个求最大值的线性规划问题，都有一个求最小值 /极小值白勺线性规划问题与之对应，反之亦然。2,在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的目标函数系数。TOC\o"1-5"\h\z3,如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为等式 。4.对偶问题的对偶问题是原问题 。5,若原问题可行，但目标函数无界，则对偶问题不可彳工.若某种资源的影子价格等于k。在其他条件不变的情况下(假设原问题的最佳基不变)，当该种资源增加3个单位时。相应的目标函数值将增加 3k0.线性规划问题的最优基为B,基变量的目标系数为Cb,则其对偶问题的最优解Y*=CbB1。.若X*和Y*分别是线性规划的原问题和对偶问题的最优解，则有 CX*=Ybo.若X、Y分别是线性规划的原问题和对偶问题的可行解，则有 CX£Ybo.若X*和Y*分别是线性规划的原问题和对偶问题的最优解，则有CX=Y*bo.设线性规划的原问题为maxZ=CXAx<b,X>0,则其对偶问题为min=YbYA>cY)0_。.影子价格实际上是与原问题各约束条件相联系的对偶变量的数量表现。.线性规划的原问题的约束条件系数矩阵为 A,则其对偶问题的约束条件系数矩阵为 A^o.在对偶单纯形法迭代中，若某 b<0,且所有的aj>0(j=1,2,…n),则原问题_无解。二、单选题.线性规划原问题的目标函数为求极小值型， 若其某个变量小于等于0,则其对偶问题约束条件为A形式CA.〜B.yC,">"D.“=”TOC\o"1-5"\h\z.设X、Y分别是标准形式的原问题与对偶问题的可行解 ，则C。A.CX^yb BnCX=ybC.CXEyb D.Cb.对偶单纯形法的迭代是从_A开始的。A.正则解 B.最优解C.可行解D.基本解.如果zo是某标准型线性规划问题的最优目标函数值，则其对偶问题的最优目标函数值 w*3A.WW=Z B.W，Z*C,W<Z* D.W>Z*.如果某种资源的影子价格大于其市场价格，则说明_BA.该资源过剩B.该资源稀缺C.企业应尽快处理该资源D.企业应充分利用该资源，开僻新的生产途径

三、多选题.在一对对偶问题中，可能存在的情况是 ABCA.一个问题有可行解，另一个问题无可行解 B.两个问题都有可行解C.两个问题都无可行解 D .一个问题无界，另一个问题可行.下列说法错误的是BoA.任何线性规划问题都有一个与之对应的对偶问题 B.对偶问题无可行解时，其原问题的目标函数无界。C.若原问题为maxZ=CXAXb,X>0,则对偶问题为minW=YbYA>C,Y>0。D.若原问题有可行解,但目标函数无界，其对偶问题无可行解。.如线性规划的原问题为求极大值型，则下列关于原问题与对偶问题的关系中正确的是 BCDEA原问题的约束条件，对应的对偶变量“奥0”B原问题的约束条件为“="，对应的对偶变量为自由变量C.原问题的变量“奥0”，对应的对偶约束“)”D.原问题的变量“W。，对应的对偶约束ye.原问题的变量无符号限制，对应的对偶约束“=”TOC\o"1-5"\h\z.一对互为对偶的问题存在最优解，则在其最优点处有 BDA.若某个变量取值为0,则对应的对偶约束为严格的不等式 B.若某个变量取值为正，则相应的对偶约束必为等式C.若某个约束为等式，则相应的对偶变取值为正 D.若某个约束为严格的不等式，则相应的对偶变量取值为0E.若某个约束为等式，则相应的对偶变量取值为 0.下列有关对偶单纯形法的说法正确的是 ABCDA.在迭代过程中应先选出基变量，再选进基变量 B.当迭代中得到的解满足原始可行性条件时，即得到最优解C.初始单纯形表中填列的是一个正则解 D.初始解不需要满足可行性E.初始解必须是可行的。.根据对偶理论，在求解线性规划的原问题时，可以得到以下结论 ACDA.对偶问题的解B.市场上的稀缺情况 C.影子价格D.资源的购销决策E.资源的市场价格.在下列线性规划问题中，CE采用求其对偶问题的方法，单纯形迭代的步骤一般会减少tiihjlZ■-tiihjlZ■-4XjXj+Qk,+Jx；+x*We2：^i+*达6i.yX：+X,+%用胃=I二3,4)maxZ=羽+1-Xj+出一 -2冷+JCj-与(1Xi.x；,xQO四、名词、简答题1、对偶可行基：凡满足条件1、对偶可行基：凡满足条件S=C-CbB1A<0的基B称为对偶可行基。2、.对称的对偶问题：设原始线性规划问题为 maxZ=CXAXJ<b>0称线性规划问题minW=YbYA{>CY >0 为其对偶问题。又称它们为一对对称的对偶问题。3、影子价格：对偶变量Y表示与原问题的第i个约束条件相对应的资源的影子价格， 在数量上表现为，当该约束条件的右端常数增加一个单位时（假设原问题的最优解不变） ，原问题目标函数最优值增加的数量。.影子价格在经济管理中的作用。 （1）指出企业内部挖潜的方向；（2）为资源的购销决策提供依据； （3）分析现有产品价格变动时资源紧缺情况的影响； （4）分析资源节约所带来的收益；（5）决定某项新产品是否应投产。.线性规划对偶问题可以采用哪些方法求解（ 1）用单纯形法解对偶问题；（2）由原问题的最优单纯形表得到；（3）由原问题的最优解利用互补松弛定理求得； （4）由Y*=CbB-1求得，其中B为原问题的最优基6、一对对偶问题可能出现的情形：1.原问题和对偶问题都有最优解，且二者相等；2.一个问题具有无界解,则另一个问题具有无可行解；3.原问题和对偶问题都无可行解五、写出下列线性规划问题的对偶问题minZ=2xi+2xz+4x3.田*建=?1.田*建=?1-+Jxi+ej*$*5』二二=5Tn,+Kj-311*--JA1)L:'!(„+?!+却占1,与无为号限制.minZ-ti*lUjl■a,(i-1.2^--Tm)j-isE=bj(j・1,2n)J*…*J.加。，净切JJ.加。，净切J珈2”十打「次名工以7J W2-/4”2+白此宅1朴我鹏砌露索%+也=-1■a7叫一加¥$为7TlH1风力讥.st府写母岑口3,mojW出£口陷+£4匕

i»| I%♦匕4Q力——匕无符号四桌（J-1口产-lt1，htN）六、已知线性规划问题tnaxZ-4Xi+7Kl+'M+2町+曲<10sL2xj+ +3〜410应用对偶理论证明该问题最优解的目标函数值不大于 25阳tk2p应用对偶理论证明该问题最优解的目标函数值不大于 25证明上m同m对以同mi为:tninW=3»i*ija善+士门上A7iCi*.+通叁2，*a**口蜉屏族E现时叫同她的一EKj琳V-Cljih刊曲时H麻需8方W=四附殖JS雎而刑尸‘印”《百一汇

七、已知线性规划问题maxZ=2x1+X2+5X3+6X4/曰+.#0<8s,d+2^+Mj+2%鬲12外；耻产12,3,4)其对偶问题的最优解为Y*=4,丫2*=1,试应用对偶问题的性质求原问题的最优解。八*「”又*了■*，工学今日*-露r£*.◎熊&y「型'巧切为沟片徜或青卡格X'Skv5法f注25岳M加内心-tt皿七、用对偶单纯形法求解下列线性规划问题:minZ-3m.干2Ms+/叫*小十JK|-1.1^4以1,一曲XJ-都：^±■1 Ji/.-_■1>/r必fK.,-r: ♦一.1丫#a.XfK.A**[1**'！1*16弋曰/—一》_*.T：遇一. 息]・十•？！■■+4%--」4篁1)、f胃1 AU一为 ♦』1"Aj -#i%5f、飞8b -•E：-M *&_金JzL-j--JF0七J血bWiKb>i.flo J”&X揩;b4*_* Xj V1 9r * j 卡。-i—} i "■Fb:w ' B・।■■■/■7c ・ 」 口<?7T5 #_&_ AAh(*®.『 ・ 心 日’Sj.r/-J己J? 1：.-r. --：-Z一/nB©于，h*- F口3T「a7rp-rnT €<丐,占胃 ;Lr，■—_-广一>. Q>・%一？ _“k翼t〜p为T中G；■孑；告0 -I。 wf C"J ,a t7 2q -4 营T用折!1口"S痼 口yT0t*Jr『T4第!_^A_源 「&*।口 -r 『T『立「£i£* 0-务a-*/ 三.。平中1—J0 0 -/*11 g—— J-Lr•即1°口»7Q■鼻，上■।,丁丁二F 3打7».把装吊册八、已知线性规划问题muZ=2x|* *Mj,+K.F43x±+x.CS上国।十%豆6军ra应十K|,a匕AEi十：十町W9马；川7.33⑷(1)写出其对偶问题(2)已知原问题最优解为X*=(2,2,4,0)T,试根据对偶理论，直接求出对偶问题的最优解W*=16第五章线性规划的灵敏度分析一、填空题1、灵敏度分析研究的是线性规划模型的原始、最优解数据变化对产生的影响。2、在线性规划的灵敏度分析中，我们主要用到的性质是 _可行性，正则性。.在灵敏度分析中，某个非基变量的目标系数的改变，将引起该非基变量自身的检验数的变化。.如果某基变量的目标系数的变化范围超过其灵敏度分析容许的变化范围，则此基变量应出基。.约束常数b;的变化，不会引起解的正则性的变化。.在某线性规划问题中，已知某资源的影子价格为 Y1,相应的约束常数bi,在灵敏度容许变动范围内发生△bi的变化，则新的最优解对应的最优目标函数值是 Z*+y（b（设原最优目标函数值为Z*）.若某约束常数b的变化超过其容许变动范围，为求得新的最优解，需在原最优单纯形表的基础上运用对—偶单纯形法求解。.已知线性规划问题，最优基为B,目标系数为Cb,若新增变量xt,目标系数为Ct,系数列向量为Pt,则当CaGB-Pt时，xt不能进入基底。.如果线性规划的原问题增加一个约束条件，相当于其对偶问题增加一个变量。10、若某线性规划问题增加一个新的约束条件，在其最优单纯形表中将表现为增加一行，一列。.线性规划灵敏度分析应在最优单纯形表的基础上,分析系数变化对最优解产生的影响.在某生产规划问题的线性规划模型中，变量X的目标系数C代表该变量所对应的产品的利润，则当某一非基变量的目标系数发生增大变化时,其有可能进入基底。二、单选题.若线性规划问题最优基中某个基变量的目标系数发生变化，则CoA.该基变量的检］^数发生变化 B.其他基变量的检验数发生变化 C.所有非基变量的检验数发生变化D.所有变量的检验数都发生变化.线性规划灵敏度分析的主要功能是分析线性规划参数变化对 D的影响。A.正则性B.可行性C.可彳f解D.最优解.在线性规划的各项敏感性分析中，一定会引起最优目标函数值发生变化的是 BoA.目标系数G的变化B.约束常数项b变化C.增加新的变量D.增加新约束.在线性规划问题的各种灵敏度分析中， b_的变化不能引起最优解的正则性变化。A.目标系数B.约束常数C.技术系数D.增加新的变量E.增加新的约束条件.对于标准型的线性规划问题，下列说法错误的是 CA.在新增变量的灵敏度分析中，若新变量可以进入基底，则目标函数将会得到进一步改善。 B.在增加新约束条件的灵敏度分析中，新的最优目标函数值不可能增加。C.当某个名束常数bk增加时，目标函数值一定增加。D.某基变量的目标系数增大，目标函数值将得到改善.灵敏度分析研究的是线性规划模型中最优解和 C之间的变化和影响。A基B 松弛变量 C原始数据D 条件系数三、多选题.如果线性规划中的G、bi同时发生变化，可能对原最优解产生的影响是 _ABCD.A.正则性不满足，可行性满足 B.正则性满足，可行性不满足 C.正则性与可行性都满足D.正则性与可行性都不满足E.可行性和正则性中只可能有一个受影响.在灵敏度分析中，我们可以直接从最优单纯形表中获得的有效信息有 ABCEA.最优基B的逆B1B.最优解与最优目标函数值C.各变量的检验数D.对偶问题的解E.各列向量.线性规划问题的各项系数发生变化，下列不能引起最优解的可行性变化的是 AB（_oA.非基变量的目标系数变化B.基变量的目标系数变化C.增加新的变量D,增加新的约束条件.下列说法错误的是ACDA.若最优解的可行性满足B1b>0,则最优解不发生变化B.目标系数G发生变化时，解的正则性将受

到影响C.某个变量Xj的目标系数c发生变化，只会影响到该变量的检验数的变化 D.某个变量x的目标系数Cj发生变化，会影响到所有变量的检验数发生变化。四、名词、简答题.灵敏度分析：研究线性规划模型的原始数据变化对最优解产生的影响.线性规划问题灵敏度分析的意义。 （1）预先确定保持现有生产规划条件下，单位产品利润的可变范围；（2）当资源限制量发生变化时，确定新的生产方案； （3）确定某种新产品的投产在经济上是否有利； （4）考察建模时忽略的约束对问题的影响程度； （5）当产品的设计工艺改变时，原最优方案是否需要调整。四、某工厂在计划期内要安排生产 I、口两种产品。已知生产单位产品所需的设备台时及 A、B两种原料的消耗如表所示：In设备128台时原材料A4016kg原材料B0412kg3百元该工厂每生产一件产品I可获利23百元（1） 单纯形迭代的初始表及最终表分别如下表 I、口所示:

Xi x2x3x4xx^^'--.^02 3O0 0X381 2 1O0X4164 0 0 1 0X5120 4 0 0 11400-3/2-1/8 0Xl410 0 1/4 0X5400 -21/2 1X201 1/2-1/8 0说明使工厂获利最多的产品混合生产方案。 （2）如该厂从别处抽出4台时的设备用于生产I、口，求这时该厂生产产品I、口的最优方案。（3）确定原最优解不变条件下，产品口的单位利润可变范围。 （4）AB分别为6kg,3kg使用设备2台时,AB分别为6kg,3kg使用设备2台时,（1）使工厂获利最多的产品混合生产方案：生产I产品4件，生产II产品2件，设备台时与原材料A（1）使工厂获利最多的产品混合生产方案：生产用完，原材料B剩余4kg,此时，获利14百元(2)X*=(4,3,2,0,o)Tz*=17 用完，原材料B剩余4kg,此时，获利14百元(2)X*=(4,3,2,0,o)Tz*=17 (3)0<C2<4(4)应生产产品W,产量为2小¥尸拇叩岫日s科情.科五、给出线性规划问题用单纯形表求解得单纯形表如下，试分析下列各种条件变化下最优解 （基）的变化:xix2x3x4x5^>^z-800-3-5-1x1110-14-1x22012-11(1) 分别确定目标函数中变量 X和X2的系数c,C2在什么范围内变动时最优解不变； (2)目标函数中变量X3的系数变为6;(3)增添新的约束Xi+2X2+X3<43押加一个新的亶・》用=()心一解：变量X3的系数变为6;(3)增添新的约束Xi+2X2+X3<43押加一个新的亶・》用=()心一解：(1)3/4<C<3 2 <C2<8 (2)X*=(2(3)X*=(2,1,0,0,1,0)TZ*=7 (4)X*=(0第六章 物资调运规划运输问题,0,1,0,0,0)TZ*=10,2,0,0,0,1/3)TZ*=25/3、填空题1.物资调运问题中，有m个供应地，A,A…，Arn,A的供应量为a(i=1,2…，m),n个需求地B,Bz,…BB的需求量为bj(j=1,2,…，n),则供需平衡条件为bij1.物资调运方案的最优性判别准则是：当全部检验数非负时，当前的方案一定是最优方案。.可以作为表上作业法的初始调运方案的填有数字的方格数应为 m+n-1个(设问题中含有m个供应地和n个需求地).若调运方案中的某一空格的检验数为 1,则在该空格的闭回路上调整单位运置而使运费增加.调运方案的调整是要在检验数出现负值的点为顶点所对应的闭回路内进行运量的调整。.按照表上作业法给出的初始调运方案，从每一空格出发可以找到且仅能找到 _1条闭回路.在运输问题中，单位运价为C位势分别用u,V表示，则在基变量处有CjCj=u+V。、供大于求的、供不应求的不平衡运输问题，分别是指 mai _三n bi的运输问题、mai _< nbi的运输i1 j1 i1 j1问题。.在表上作业法所得到的调运方案中，从某空格出发的闭回路的转角点所对应的变量必为基变量。.在某运输问题的调运方案中，点 (2,2)的检验数为负值，(调运方案为表所示)则相应的调整量应为300。InmIVA300100300B400C600300.若某运输问题初始方案的检验数中只有一个负值：- 2,则这个-2的含义是该检验数所在格单位调整.运输问题的初始方案中的基变量取值为正。14表上作业法中，每一次调整1个“入基变量”。15.在编制初始方案调运方案及调整中，如出现退化，则某一个或多个点处应填入数字16运输问题的模型中，含有的方程个数为 n+M个。17表上作业法中，每一次调整，“出基变量”的个数为1个。18给出初始调运方案的方法共有三种。19.运输问题中，每一行或列若有闭回路的顶点，则必有两个。二、单选题1、在运输问题中，可以作为表上作业法的初始基可行解的调运方案应满足的条件是 DoA.含有m+n-1个基变量B.基变量不构成闭回路C.含有m+n—1个基变量且不构成闭回路D.含有m+n—1个非零的基变量且不构成闭回k,最优调运方案将Rk,最优调运方案将RA.发生变化B.不发生变化C.A、B都有可能.在表上作业法求解运输问题中，非基变量的检验数 DoA.大于0B.小于0C.等于0D.以上三种都可能.运输问题的初始方案中，没有分配运量的格所对应的变量为 BA基变量A基变量B 非基变量 C 松弛变量 D剩余变量.表上作业法的基本思想和步骤与单纯形法类似，那么基变量所在格为 C无分配数格A有单位运费格 B无单位运费格C 有分配数格 D无分配数格.表上作业法中初始方案均为工D最优解D 水平或垂直A可行解B D最优解D 水平或垂直.闭回路是一条封闭折线，每一条边都是DA水平B垂直C水平十垂直TOC\o"1-5"\h\z8当供应量大于需求量，欲化为平衡问题，可虚设一需求点，并令其相应运价为 DA0B 所有运价中最小值C所有运价中最大值D最大与最小运量之差.运输问题中分配运量的格所对应的变量为 AA基变量B 非基变量 C松弛变量D 剩余变量.所有物资调运问题，应用表上作业法最后均能找到一个 DA可行解B 非可行解 C待改进解D最优解.一般讲，在给出的初始调运方案中，最接近最优解的是乙A西北角法 B最小元素法C差值法D位势法.在运输问题中，调整对象的确定应选择 CA检验数为负B检验数为正C检验数为负且绝对值最大 D检验数为负且绝对值最小.运输问题中，调运方案的调整应在检验数为 金负值的点所在的闭回路内进行。A任意值B最大值C 绝对值最大 D 绝对值最小.表上作业法的基本思想和步骤与单纯形法类似，因而初始调运方案的给出就相当于找到一个 CA基B 可行解C 初始基本可行解D最优解15平衡运输问题即是指m个供应地的总供应量Dn个需求地的总需求量。A大于B 大于等于 C小于D等于三、多选题.运输问题的求解结果中可能出现的是 ABC_。A、惟一最优解 B.无穷多最优解 C.退化解D.无可行解.下列说法正确的是ABDA.表上作业法也是从寻找初始基可行解开始的B.当一个调运方案的检验数全部为正值时，当前方案一定是最佳方案C.最小元素法所求得的运输的运量是最小的D.表上作业法中一张供需平衡表对应一个基可行解.对于供过于求的不平衡运输问题，下列说法正确的是 ABCA.仍然可以应用表上作业法求解 B.在应用表上作业法之前，应将其转化为平衡的运输问题 C.可以虚设一个需求地点，令其需求量为供应量与需求量之差。 D.令虚设的需求地点与各供应地之间运价为 M（M为极大的正数）4.下列关于运输问题模型特点的说法正确的是 ABDA.约束方程矩阵具有稀疏结构 B.基变量的个数是m+n-1个C.基变量中不能有零 D.基变量不构成闭回路.对于供过于求的不平衡运输问题，下列说法正确的是 ABCA.仍然可以应用表上作业法求解 B.在应用表上作业法之前，应将其转化为平衡的运输问题C.可以虚设一个需求地点，令其需求量为供应量与需求量之差。D.令虚设的需求地点与各供应地之间运价为 M（M为极大的正数）E.可以虚设一个库存，令其库存量为 0三、判断表（a）（b）（c）中给出的调运方案能否作为表上作业法求解时的初始解，为什么(a)BB2B3B4BsBe产量A201030A2302050A3101050575A42020销量204030105025(b) (c)BB2BB4BsR产量B B B3 B4 产量A3030A 6 5 11A203050A2 5 4 2 11A31030102575A 5 3 8A2020销量 5 9 9 7

销量204030105025(a)可作为初始方案；(b)中填有数字的方格数少于 9(产地数+销地数—1),不能作为初始方案；(c)中存在以非零元素为顶点的闭回路，不能作为初始方案四、已知某运输问题的产销平衡表。单位运价表及给出的一个调运方案分别见表 (a)和(b),判断给出的调运方案是否为最优如是说明理由；如否。也说明理由表(a)产销平衡表及某一调运方案 单位运价表产地BiB2B3B4B5B6产量l302050A301040A10401060A201131销量305020403011五、给出如下运输问题运价\肖产B1B2B3B4产量Ai5310490A2169640A320105770销量30508040200(1)应用最小元素法求其初始方案； (2)应用位势法求初始方案的检验数，并检验该方案是否为最优方案

才k冉三,也■>:上才k冉三,也■>:上小a卜;：就六、用表上作业法求给出的运输问题的最优解甲乙丙丁产量11067124216059935410104销量5246甲乙丙丁产量112142369344销量5246在最优调运方案下的运输费用最小为 118七、名词1、平衡运输问题：m个供应地的供应量等于n个需求地的总需求量，这样的运输问题称平衡运输问题。2、不平衡运输问题：m个供应地的供应量不等于n个需求地的总需求量，这样的运输问题称不平衡运输问题。第七章 整数规划一、填空题.用分枝定界法求极大化的整数规划问题时， 任何一个可行解的目标函数值是该问题目标函数值的下界。—.在分枝定界法中，若选X=4/3进行分支，则构造的约束条件应为X1&1,XB2o.已知整数规划问题R,其相应的松驰问题记为R，,若问题P。’无可行解，则问题Po无可行解。.在0-1整数规划中变量的取值可能是_0或1o.对于一个有n项任务需要有n个人去完成的分配问题，其解中取值为1的变量数为n个。.分枝定界法和割平面法的基础都是用 线性规划方法求解整数规划。%所在行得X+1/7x%所在行得X+1/7x3+277x5=13/7,则以X行为源行的割平面方程为_6—1X3—2X5<0_o7~717 .在用割平面法求解整数规划问题时，要求全部变量必须都为整数。.用割平面法求解整数规划问题时，若某个约束条件中有不为整数的系数，则需在该约束两端扩大适当倍数，将全部系数化为整数。TOC\o"1-5"\h\z.求解纯整数规划的方法是割平面法。求解混合整数规划的方法是分枝定界法 一.求解0—1整数规划的方法是隐枚举法。求解分配问题的专门方法是匈牙利法。.在应用匈牙利法求解分配问题时，最终求得的分配元应是独立零元素 一.分枝定界法一般每次分枝数量为 2±.二、单选题.整数规划问题中，变量的取值可能是 9A.整数B.0或1C.大于零的非整数D.以上三种都可能.在下列整数规划问题中，分枝定界法和割平面法都可以采用的是 A。A.纯整数规划B.混合整数规划C.01规划D.线性规划.下列方法中用于求解分配问题的是 D_oA.单纯形表B.分枝定界法C.表上彳^业法D.匈牙利法三、多项选择1.下列说明不正确的是ABCA.求解整数规划可以采用求解其相应的松驰问题， 然后对其非整数值的解四舍五人的方法得到整数解。B.用分枝定界法求解一个极大化的整数规划问题， 当得到多于一个可行解时，通常任取其中一个作为下界。C.用割平面法求解整数规划时，构造的割平面可能割去一些不属于最优解的整数解。 D.用割平面法求解整数规划问题时，必须首先将原问题的非整数的约束系数及右端常数化为整数。.在求解整数规划问题时，可能出现的是ABCA.唯一最优解B.无可行解C.多重最佳解D.无穷多个最优解.关于分配问题的下列说法正确的是_ABDoA.分配问题是一个高度退化的运输问题 B.可以用表上作业法求解分配问题 C.从分配问题的效益矩阵中逐行取其最小元素，可得到最优分配方案 D.匈牙利法所能求解的分配问题，要求规定一个人只能完成一件工作，同时一件工作也只给一个人做。.整数规划类型包括（CDE）A线性规划B非线性规划C纯整数规划D混合整数规划E0 1规划.对于某一整数规划可能涉及到的解题内容为（ ABCDE）A求其松弛问题B 在其松弛问题中增加一个约束方程 C应用单形或图解法D割去部分非整数解E多次切割三、名词1、纯整数规划：如果要求所有的决策变量都取整数，这样的问题成为纯整数规划问题

0或1,这样的问题称为0—0或1,这样的问题称为0—1规划。3、混合整数规划：在线性规划问题中，如果要求部分决策变量取整数，则称该问题为混合整数规划四、用分枝定界法求解下列整数规划问题： （提示：可采用图解法）maxZ=40x1+90X2'fl*,他五、用割平面法求解majtZ五、用割平面法求解majtZ==X]+血2x1.十与＜6,号”且为整数出彳叱再,苑"-胃上^一三/|冉 XL二奏乙1a卢出彳叱再,苑"-胃上^一三/|冉 XL二奏乙1a卢A* r F* 人寻。智"苣*；/评ET，二』"J六、下列整数规划问题maxZ-20衣|#10x2+10xaI2箕1■+20算正+4工31153.464<20x?+4%1-20X1.Kt.Xj含。且为物畋说明能否用先求解相应的线性规划问题然后四舍五人的办法来求得该整数规划的一个可行解。答：不考虑整数约束，求解相应线性规划得最优解为 x1=10/3,X2=X3=0,用四舍五人法时，令xi=3,X2=X3=0,其中第2个约束无法满足，故不可行。七、若某钻井队要从以下10个可供选择的井位中确定5个钻井探油。使总的钻探费用为最小。若10个井位的代号为&,S2.…，S10相应的钻探费用为 C,C2,…C10,并且井位选择要满足下列限制条件：（1）在S1,S2, S4中至多只能选择两个；（2）在S5, S6中至少选择一个；（3）在S3, S6, S7, S8中至少选择两个； 试建立这个问题的整数规划模型03。-f,一小》。聒4帆书军」■中4旧产怎・箕=j-ia 尸"F¥产-百* j*jj+1立3二]4'j）+君.+E于+K*A2祥站黑跳电再收f"is>aww八、有四项工作要甲、乙、丙、丁四个人去完成.每项工作只允许一人去完成。每个人只完成其中一项工作，已知每个人完成各项工作的时间如下表。问应指派每个人完成哪项工作，使总的消耗时间最少、蜕或弓力廿*.、蜕或弓力廿*.占4[图与网络分析人InmIV甲15182l24乙19232218丙671619丁19212317、填空题.图的最基本要素是点、点与点之间构成的边.在图论中，通常用点表示，用边或有向边表示研究对象，以及研究对象之间具有特定关系。.在图论中，通常用点H示研究对象，用边或有向边表示研究对象之间具有某种特定的关系。.在图论中，图是反映研究对象 之间特定关系的一种工具。.任一树中的辿婺必定是它的点鳌懑 1。.最小树问题就是在网络图中，找出若干条边，连接所有结点，而且连接的总长度最小。.最小树的算法关键是把最近的未也_结点连接到那些已接结点上去。.求最短路问题的计算方法是从 00fj&Cj开始逐步推算的，在推算过程中需要不断标记平衡和最短路线。二、单选题1、关于图论中图的概念，以下叙述虑）正确。A图中的有向边表示研究对象，结点表示衔接关系。 B图中的点表示研究对象，边表示点与点之间的关系。C图中任意两点之间必有边。 D图的边数必定等于点数减1。.关于树的概念，以下叙述（B）正确。A树中的点数等于边数减1B连通无圈的图必定是树 C含n个点的树是唯一的 D任一树中，去掉一条边仍为树。.一个连通图中的最小树（B）,其权（A）oA是唯一确定的 B可能不唯一C可能不存在D一定有多个。.关于最大流量问题，以下叙述（D）正确。A一个容量网络的最大流是唯一确定的 B达到最大流的方案是唯一的C当用标号法求最大流时，可能得到不同的最大流方案D当最大流方案不唯一时，得到的最大流量亦可能不相同。.图论中的图，以下叙述（C）不正确。A.图论中点表示研究对象，边或有向边表示研究对象之间的特定关系。 B.图论中的图，用点与点的相互位置，边的长短曲直来表示研究对象的相互关系。 C.图论中的边表示研究对象，点表示研究对象之间的特定关系。 D.图论中的图，可以改变点与点的相互位置。只要不改变点与点的连接关系。.关于最小树，以下叙述（B）正确。A.最小树是一个网络中连通所有点而边数最少的图 B.最小树是一个网络中连通所有的点，而权数最少的图C.一个网络中的最大权边必不包含在其最小树内 D.一个网络的最小树一般是不唯一的。.关于可行流，以下叙述（A）不正确。A.可行流的流量大于零而小于容量限制条件 B.在网络的任一中间点，可行流满足流人量=流出量。C.各条有向边上的流量均为零的流是一个可行流 D.可行流的流量小于容量限制条件而大于或等于零。三、多选题,关于图论中图的本吃念，以下叙述（123）正确。（1）图中的边可以是有向边，也可以是无向边 （2）图中的各条边上可以标注权。 （3）结点数等于边数的连通图必含圈（4）结点数等于边数的图必连通。2,关于树的概念，以下叙述（123）正确。1）树中的边数等于点数减 1（2）树中再添一条边后必含圈。（3）树中删去一条边后必不连通 （4）树中两点之间的通路可能不唯一。3,从连通图中生成树，以下叙述（134）正确。（1）任一连通图必有支撑树（2）任一连通图生成的支撑树必唯一（3）在支撑树中再增加一条边后必含圈（4）任一连通图生成的各个支撑树其边数必相同4.在下图中，（abcd）不是根据（a）生成的支撑树。,Q七七日［Wle）WJ5,从赋权连通图中生成最小树，以下叙述 （124）不正确。（1）任一连通图生成的各个最小树， 其总长度必相等（2）任一连通图生成的各个最小树， 其边数必相等。（3）任一连通图中具有最小权的边必包含在生成的最小树上。 （4）最小树中可能包括连通图中的最大权边。6,从起点到终点的最短路线，以下叙述 （123）不正确。1）从起点出发的最小权有向边必含在最短路线中。 （2）整个图中权最小的有向边必包含在最短路线中。（3）整个图中权最大的有向边可能含在最短路线中 （4）从起点到终点的最短路线是唯一的。.关于带收发点的容量网络中从发点到收点的一条增广路，以下叙述 （123）不正确。（1）增广路上的有向边的方向必须是从发点指向收点的 （2）增广路上的有向边，必须都是不饱和边（3）增广路上不能有零流边（4）增广路上与发点到收点方向一致的有向边不能是饱和边， 相反方向的有向边不能是零流边.关于树，以下叙述（ABCE）正确。A.树是连通、无圈的图B.任一树，添加一条边便含圈C.任一树的边数等于点数减1。D.任一树的点数等于边数减1E.任一树，去掉条边便不连通。.关于最短路，以下叙述（ACDE河正确。A从起点出发到终点的最短路是唯一的。 B.从起点出发到终点的最短路不一定是唯一的，但其最短路线的长度是确定的。C.从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上 D.从起点出发的有向边中的最大权边，一定不包含在起点到终点的最短路上。 E.整个网络的最大权边的一定不包含在从起点到终点的最短路线上。10.关于增广路，以下叙述（BC）正确。A.增广路是一条从发点到收点的有向路，这条路上各条边的方向必一致。 B.增广路是一条从发点到收点的有向路，这条路上各条边的方向可不一致。C.增广路上与发点到收点方向一致的边必须是非饱和边，方向相反的边必须是流量大于零的边。 D.增广路上与发点到收点方向一致的边必须是流量小于容量的边，方向相反的边必须是流量等于零的边。 E.增广路上与发点到收点方向一致的边必须是流量为零的边，方向相反的边必须是流量大于零的边。四、名词解释1、树：在图论中，具有连通和不含圈特点的图称为树。

.权：在图中，边旁标注的数字称为权。.网络：在图论中，给边或有向边赋了权的图称为网络.最大流问题：最大流问题是指在网络图中，在单位时间内，从发点到收点的最大流量.最大流问题中流量：最大流问题中流量是指单位时间的发点的流出量或收点的流入量。.容量：最大流问题中，每条有向边单位时间的最大通过能力称为容量.饱合边：容量与流量相等的有向边称为饱合边。8零流边：流量为零的有向边称为零流边9.生成树：若树T是无向图G的生成树，则称T是G的生成树。.o10根：有向图G中可以到达图中任一顶点的顶点 u称为G的根。11枝：树中的边称为枝。12.平行边：具有相同端点的边叫平行边。13根树：若有向图G有根u,且它的基本图是一棵树，则称G为以u为根的根树。四、计算题.下图是6个城市的交通图，为将部分道路改造成高速公路，使各个城市均能通达，又要使高速公路的总长度最小，应如何做最小的总长度是多少2.对下面的两个连通图，试分别求出最小树2.对下面的两个连通图，试分别求出最小树3、第1题中的交通图，求城市A到D沿公路走的最短路的路长及路径4.对下面两图，试分别求出从起点到终点的最短路线。

米逢:落Jif 看i；66.下面网络中，点①，②是油井，点⑥是原油脱水处理厂，点③、④、⑤是泵站，各管道的每小时最6.下面网络中，点①，②是油井，点⑥是原油脱水处理厂，点③、④、⑤是泵站，各管道的每小时最大通过能力（吨/小时）如有向边上的标注。求从油井①、②每小时能输送到脱水处理厂的最大流量。（提示：虚设一个发点S,令有向边（S,1）,（S,2）的容量为8）性;'％?出，心十崂巾尸产3・优”，皤｝力5J，!”！月M力.外＞b袅 ,内，净，＞.叱A：4*了一名词十一章需求：需求就是库存的输出。存贮费：一般是指每存贮单位物资单位时间所需花费的费用。缺货损失费：一般指由于中断供应影响生产造成的损失赔偿费。4、订货批量Q:存贮系统根据需求，为补充某种物资的库存而向供货厂商一次订货或采购的数量。5、订货间隔期T:两次订货的时间间隔可订货合同中规定的两次进货之间的时间间隔。6、记账间隔期R:指库存记账制度中的间隔记账制所规定的时间。十二章预测：是决策的基础，它借助于经济学、概率论与数理统计、现代管理科学、系统论和计算机科学等所提供的理论及方法，通过适当的模型技术，分析和预测研究对象的发展趋势。十三章决策：凡是根据预定目标而采取某种行动方案所作出的选择或决定就称为决策。单纯选优决策：是指根据已掌握的数据，不需再加工计算，或仅进行方案指标值的简单计算，通过比较便可以直接选出最优方案的决策方法。模型选优决策：是在决策对象的客观状态完全确定的条件下，建立一定的符合实际经济状况的数学模型，进而通过对模型的求解来选择最优方案的方法。非确定型决策：是一种在决策分析过程中，对决策方案付诸实施后可能遇到的客观状态，虽然能够进行估计，但却无法确定每一种客观状态出现的概率的决策。风险型决策：是一种在分析过程中，对方案付诸实施后可能遇到的客观状态，不仅在决策分析时能够加以估计，而且对每一种状态出现的概率大小也有所掌握。决策树：就是对一个决策问题画一张图，用更容易了解的形式来表示有关信息。十四章排队论：排队论所讨论的是一个系统对一群体提供某种服务时该群体占用此服务系统时所呈现的状态。排队规则：是描述顾客来到服务系统时，服务机构是否充许，顾客是否愿意排队，在排队等待情形下服务的顺序。M/G/1排队系统：是单服务台系统，其顾客到达服从参数为人的泊松分布，服务时间属一般分布。随机排队模型：称服务员个数为随机变量的排队系统为随机排队服务系统，相应的模型为随机排队模型。一、（10分）某咨询公司，受厂商委托，对新上市的一种新产品进行消费者反映的调查。该公司采用了挨户调查的方法，委托他们调查的厂商以及该公司的市场研究专家对该调查提出下列几点要求：1）必须调查 2000户人家；(2)在晚上调查的户数和白天调查的户数相等;(3)至少应调查700户有孩子的家庭；(4)至少应调查450户无孩子的家庭。每会见一户家庭，进行调查所需费用为家庭白天会见晚上会见有孩子25元30元无孩子20元24元问为使总调查费用最少，应调查各类家庭的户数是多少(只建立模型)二、(10分)某公司受委托，准备把120万元投资两种基金A和B,其中A基金的每单位投资额为50元，年回报率为10%B基金的每单位投资额为100元，年回报率为4%委托人要求在每年的年回报金额至少达到6万元的基础上要求投资风险最小。 据测定每单位A基金的投资风险指数为8,每单位B基金的投资风险指数为3,投资风险指数越大表明投资风险越大。委托人要求在B基金中的投资额不少于30万元。为了使总的投资风险最小，该公司应该在基金A和基金B中各投资多少单位这时每年的回报金额是多少为求该解问题，设可以建立下面的线性规划模型使用《管理运筹学》软件，求得计算机解如下图所示，最优解目标函数值=相差值x1x23约束 松驰/剩余变量 对偶价格123目标系数范围变量 下限 当前值上限x1 无上限x2 无下限常数项范围变量 下限 当前值 上限12无下限根据图回答问题:a.最优解是什么，最小风险是多少b.投资的年收入是多少c.每个约束条件的对偶价格是多少d.当每单位基金A的风险指数从8降为6,而每单位基金B的风险指数从3上升为5时,用百分之一百法则能否断定，其最优解变或不变为什么e.对图中的右边值范围的上、下限给予具体解释，并阐述如何使用这些信息。三、（10分）某造船厂根据合同从当年起连续三年末各提供五条规格型号相同的大型客货轮。 已知该厂这三年内生产大型客货轮的能力及每艘客货轮的成本如下表所示。已知加班生产时，每艘客货轮成本比正常高出 10%又知造出来的客货轮如当年不交货，每艘每积压一年所造成的积压损失为 60万元。在签合同时，该厂已积压了两艘未交货的客货轮，而该厂希望在第三年末完成合同后还能储存一艘备用。 问该厂应如何安排每年客货轮生产量，使在满足上述各项要求的情况下，总的生产费用为最少建立上述运输问题模型。年度正常生产时间内可完成的客货轮数加班生产时间内可完成的客货轮数正常生产时每艘成本（万元）133600242700323650四、（10分）某畜产品公司计划在市区的东、 西、南、北四区建立销售门市部，拟议中有10个位置Ai（i=1,2,3,…，10）可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区由Ai,A>,A三个点中至少选择两个；在西区由A4,A5两个点中至少选一个；在南区由A6,A7两个点中至少选一个；在北区由A8,A9,Ao三个点中至多选两个。A各点的设备投资及每年可获利润由于地点不同都是不一样的， 预测情况见下表（单位：万元）所示。AA2A3AAAAA8A9A10投资额110130160908010090150170190利润31354517152520435356但投资总额不能超过820万元，问应选择哪几个销售点，可使年利润为最大建立上述问题的整数规划模型。五、（10分）某公司拟将某种设备4台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如下表所示，设备台数甲厂炉乙厂十.丙厂炉gg6+*SIB7讣学IIP4』问这4台设备应如何分配给这3个工厂，使得所创造的总利润为最大用动态规划求解。六、（10分）请确定a、b、c、d各题的存储模型，确定各输入数据，不需计算：a、某公司生产一种电子设备，该设备所需的一个部件由自己的分厂提供，分厂对这种部件的生产能力为6000/件，分厂每次的生产准备费为250元。公司的这种电子设备的年需求为2000台/年。装配允许滞后，滞后的费用为每台成本的40%该部件每件成本为500元,年存贮为成本的20%求：公司生产关于这种部件费用最小的生产批量。b、某单位每年需要一种备件5000个，这种备件可以从市场直接购买到。设该备件的单价为16元/个，年存贮费为单价的25%一个备件缺货一年的缺货费为单价的10%若每组织采购一次的费用为120元。试确定一个使采购存贮费用之和为最小的采购批量。c、一条生产线如果全部用于某型号产品时， 其年生产能力为600000台。据预测对该型号产品的年需求量为250000台，并在全年内需求基本保持平衡，因此该生产线将用于多品种的轮番生产。已知在生产线上更换一种产品时，需准备结束费 1350元。该产品每台成本为45元，年存贮费用为产品成本的 24%不允许发生供应短缺。求使费用最小的该产品的生产批量。d、某企业