运筹学习题集答案

第一套一、解：设代表第i种原料混入第j种产品中的数量，其中i=1，2，3；j=1，2，3；则3,2,1,3,2,1,02.08.05.12.08.05.12.08.05.185907862809078627090786250010002000140090060015001200900max313332313312322212311312111313332313312322212311312111313312311313312313113312311jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZijiiiiiiiiiiiijjjjjjjjjjijjiiiii二、解：原问题可化为：52,1,0945252max53243232121ixxxxxxxxxxxxZi210001x2x3x4x5x1b21x04x05x11100021100-4-60155-9jr0-1-200ijjar/-1/41/3--21x04x05x101/201/400-211/2013/20-1/4jr00-1/20-1/4-31/4431)49,411(),(*21*ZxxXTT三、解：将原问题改成产销平衡问题，并用沃格尔法给出初始解得：销产1B2B3B4B5B产jv1A10515502020205403550-152A2010401015603030301010003A30535654020552025651305'A015MM-10050-100520-20销25115603070300iu2030153020此方案还不是最优，需要调整销产1B2B3B4B5B产jv1A1015155020302015403550-252A20254001560301530010003A30153565403055302565130-5'A010MM-100150150520-30销25115603070300iu2040153030此时检验数均大于或等于0，为最优解650025*6515*3015*6035*6550*1520*25*Z四、解：1051520M831012M5079M-32105150080700807031514130~113950~113950~1527M01302M-801302M-809415807210007210004068M-3090710138401201M-90731001此时，费用最小，218553*Z其中，丙一，甲二，乙三，戌四五、解：1v2v3v4v5v6v7v0*119*101110*2011*21202121*21*2825*21vv11：21vv31vv9：31vv41vv10：41vv51vv21：541vvv61vv20：631vvv71vv25：7541vvvv六、解：阶段：以向某一项目投资作为一个阶段，如此可划分为三个阶段。状态变量：以可以提供的投资额作为状态变量is，其范围为0，1，2，3，4百万决策变量：以给某项目投资的金额作为决策变量ix，则iisx状态转移方程：iiidss140,33sk3s3x01234)(33sf3x*01234384148606638414860660123440,22sk2s2x01234)(22sf2x*0123440+3840+4142+3840+4842+4150+3840+6042+4850+4160+3840+6642+6050+4860+4166+38788188100106000，2004,11sk1s1x01234)(11sf1x*438+10664+10068+8878+8176+781641总效益最大值为164，其中3,0,1321xxx。七、解：1、无可行解：最终表人工变量不为零；或右侧常数0ib，对应的0ija；2、有多重解：0jr（非基变量）且至少有一个为零。3、有无界解：非基变量的检验数0jr，且对应的系数列向量0ija。第二套一、解：设ix代表第i月正常生产的柴油机数量，iy代表第i月加班生产的柴油机数量，iz代表第i月末的库存量，则iz=44,3,2,1,0,,500035004500300020065005000min44333222111414141izyxyxzyxzyxzyxzyxZiiiiiiiii二、解：1、对偶模型无约束2121212121,0431225225minyyyyyyyyyyW2、由单纯形表可看出，5295291)(*y由于0,00,0,0;021212211ssssyyxxxyxy而则对偶问题的第一、二个约束是紧的，可解出522y将21,yy代入第三个约束，满足约束条件，则51415252921*),,(),(*wyyyT3、5和24、1B5/25/15/15/25、如果原问题增加一个变量，则对偶问题就增加一个约束条件，它的可行域要么减少，要么不变，绝对不会变大。三、解：此题可看作指派问题求解：561012501400381012~467~023~01244500000010019*0,1,1,1331221Zxxx，其余为最优解四、解：将最大化问题化为极小化问题，并将系数转为正，即令'1iixx，整理得)5,2,1(1032212236224532631075min''5'4'3'2'5'4'3'2'1'5'4'3'2'1'5'4'3'2'1'''jxxxxxxxxxxxxxxxxxxxxZj或综上，该0-1规划无可行解五、解：按三个变量划分为三个阶段，状态转移方程第三阶段：233333*,max)(sxsxsf330sx第二阶段：2241'22'23'222)(max)(max)(sxsxsxsf2'20sx2'20sx其中221'2*sx)1(2'2xx第一阶段：2782214112241111)2(maxmax)(xxsxsf201x201x其中321*x2783233132'22321**,1*1*,*Zxxxx最优解六、解：依题意，首先给出一个可行流在初始流上增流到不能再增，得到如下结果：此时已不能再增流，流量105f，不能满足市场的需求量。应修改仓库3到市场3和4的容量，分别增流10和5即能满足需求。七、解：3、5正确。第三套一、解：将原问题化为标准形得5,2,1,0824424max52142132121ixxxxxxxxxxxxZi41000ibikiab/1x2x3x4x5x03x-111002-04x1-40104405x1-200188jr4100003x0-31106-41x1-40104-05x020-1142jr0170-4003x001-1/23/21241x100-121212x010-1/21/22jr0009/2-17/2由于04r而对应的04ia此线性规划问题无界二、解（1）X2的价值系数由-7变为3。01310232r最优解发生变化，继续迭代。231001x2x3x4x5xibikiab/21x05x1111003111610610/3jr01-1-2021x32x102/32/3-1/3011/31/31/38/310/3jr00-4/3-2-1/3-46/3此时最优解为346)310,38(),(*21*ZxxXTT（2）11011B0835311011'bBb此时不影响解的最优性，只改变解的值及目标函数值6*)8,3(),(*51ZxxXTT（3）最优解不满足新增加的约束条件2231xx最优解要发生改变将约束条件改写为22631xxx加入最优表中继续迭代。2-710001x2x3x4x5x6xib21x05x06x1111000311100-1-3-101610-8jr0-9-1-200ikjar/-91/32--21x05x13x12/302/301/308/302/314/301/311/30-1/310/322/38/3jr0-26/30-5/30-1/3-28/3新的最优解为328*),()3,1(*38310ZxxXTT三、解：建立运输问题模型并给出初始方案得：销产12345产iu110300131716200192000470001’1511818211241020020042M1070013-716-70070042’M1517180212000220023MM1570018005700-13’MM200232000020044MMM15-8070070044’MMM20-302002004销30070090060011003600jv10-41619-4检验数有负，重复调整，得如下解：销产12345产iu11030013016200194020070001’155185215249020020002M1070013016403700-32’M152182216020020003MM1570018401700-13’MM204238020020004MMM15600010070004’MMM20502002000销30070090060011003600jv101316150此时检验数全0jir，为最优解)(327001560015700162001070010300*元Z分配计划如下：第一个月正常生产500件，分别给1月300件，3月200件。第二个月正常生产700件，供给第二个月第三个月正常生产700件，供给第三个月第四个月正常生产600件，供给第六个月四、解：设号码的人入选，第号码的人不入选，第iiyi1010111113)185180186187191193(max989795548598755498765431或iyyyyyyyyyyyyyyyyyyyyyyyZ五、解：利用匈牙利法求解，增加一行元素000003030203020102030304020302030401030604050~000010100101020203001010200205030400000~1001010100000201030000201050204000000此时方案最优，最少人数人7010202020*Z方案为周一上美术课，周三上艺术课，周四上音乐课，周五上文学课。六、解七、解：1、（1）2321xxx（2）024242xxxx或2、运费还可以减少，此方案不是最优方案3、在多阶段决策过程中，最优决策序列具有这种性质，即不管该序列上某状态以前的状态和决策如何，余下的决策序列必构成该状态的最优决策序列。第四套一、解：（1）首先将解代入约束条件，满足，说明是可行解041200841A0A线性相关，此解不是基可行解（2）选取431,,xxx作为基变量，1001220081A036A线性无关。令07652xxxx，解出0,01,09431xxx得出一个基可