运筹学课后习题答案__林齐宁版本__北邮出版社

运筹学作业标准答案(教师用)1·No.1线性规划1、某织带厂生产A、B两种纱线和C、D两种纱带，纱带由专门纱线加工而成。这四种产品的产值、成本、加工工时等资料列表如下：产品项目ABCD单位产值(元)1681401050406单位成本(元)4228350140单位纺纱用时(h)32104单位织带用时(h)0020.5工厂有供纺纱的总工时7200h，织带的总工时1200h。(1)列出线性规划模型，以便确定产品的数量使总利润最大；(2)如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型的解是否有影响？解：(1)设A的产量为x1，B的产量为x2，C的产量为x3，D的产量为x4，则有线性规划模型如下：maxf(x)=(16842)x1+(14028)x2+(1050350)x3+(406140)x4=126x1+112x2+700x3+266x4s.t.4,3,2,1,012005.02720041023434321ixxxxxxxi(2)如果组织这次生产有一次性的投入20万元，由于与产品的生产量无关，故上述模型只需要在目标函数中减去一个常数20万，因此可知对模型的解没有影响。2、将下列线性规划化为极大化的标准形式解：将约束条件中的第一行的右端项变为正值，并添加松弛变量x4，在第二行添加人工变量x5，将第三行约束的绝对值号打开，变为两个不等式，分别添加松弛变量x6,x7，并令xxx333，则有max[f(x)]={2x13x25(xx33)+0x4Mx5+0x6+0x7}s.t.0,,,,,,,1355719135571916997657654332173321633215332143321xxxxxxxxxxxxxxxxxxxxxxxxxxxx不限321321321321321,0,13|5719|169765..532)(minxxxxxxxxxxxxtsxxxxf运筹学作业标准答案(教师用)23、用单纯形法解下面的线性规划,0,,4205.021253661023..352)(max321321321321321xxxxxxxxxxxxtsxxxxf解：在约束行1,2,3分别添加x4,x5,x6松弛变量，有初始基础可行解和单纯形法迭代步骤如下：Cj253000CBXBbx1x2x3x4x5x6bi/aij*0x4610321100610/20x51251(6)3010125/6*0x6420211/2001420/1OBJ=0zj000000cj-zj253000Cj253000CBXBbx1x2x3x4x5x6bi/aij*0x41705/3(10/3)0211/30170.55x2125/61/611/201/60－0x62395/611/60001/61－OBJ=625/6zj5/655/205/60cj-zj17/601/205/60Cj253000CBXBbx1x2x3x4x5x6bi/aij*2x1341/2103/53/101/100－5x5197/401(2/5)1/203/200125.1250x62847/40011/1011/207/201－OBJ=2349/4zj254/517/2011/200cj-zj0011/5011/200Cj253000CBXBbx1x2x3x4x5x6bi/aij*2x11955/813/203/81/803x3985/805/211/83/800x613555/16011/4011/161/161OBJ=6865/8zj221/239/811/80cj-zj011/209/811/80答：最优解为x1=244.375,x2=0,x3=123.125,剩余变量x6=847.1875；最优解的目标函数值为858.125。运筹学作业标准答案(教师用)3No.2两阶段法和大M法解：将原问题变为第一阶段的标准型0,,,,,753802..00)(max654321642153216521xxxxxxxxxxxxxxtsxxxxxf第一阶段单纯形表Cj000011CBXBbx1x2x3x4x5x6bi/aij*1x580121010801x675(3)1010175/3*OBJ=155zj431111cj-zj431100Cj000011CBXBbx1x2x3x4x5x6bi/aij*1x5550(5/3)11/311/3553/5*0x12511/301/301/3253OBJ=55zj05/311/311/3cj-zj05/311/304/3Cj000011CBXBbx1x2x3x4x5x6bi/aij*0x233013/51/53/51/50x114101/52/51/52/5OBJ=0zj000000cj-zj000011第二阶段Cj4600CBXBbx1x2x3x4bi/aij*6x233013/51/54x114101/52/5OBJ=254zj4614/52/5cj-zj0014/52/5答：最优解为x1=14，x2=33，目标函数值为254。1、用两阶段法解下面问题：0,753802..64)(min21212121xxxxxxtsxxxf运筹学作业标准答案(教师用)42、用大M法解下面问题，并讨论问题的解,0,,52151565935..121510)(max321321321321321xxxxxxxxxxxxtsxxxxf解：第1、2行约束条件添加x4,x5松弛变量，第3行添加x6剩余变量和x7人工变量，有如下初始单纯形表和迭代步骤：Cj101512000MCBXBbx1x2x3x4x5x6x70x49(5)3110000x51556150100Mx752110011OBJ=5Mzj2MMM00MMcj-zj10+2M15+M12+M00M0Cj101512000MCBXBbx1x2x3x4x5x6x710x19/513/51/51/50000x52409(16)1100Mx77/501/53/52/5011OBJ=187M/5zj106+M/523M/52+2M/50MMcj-zj09M/510+3M/522M/50M0Cj101512000MCBXBbx1x2x3x4x5x6x710x13/2139/8003/101/100012x33/209/1611/203/2000Mx71/2043/80011/207/2011OBJ=33M/2zj1093/8+43M/801221/8+7M/165/8+3M/80MMcj-zj027/843M/80021/87M/165/83M/80M0答：最后单纯形表中检验数都小于等于0，已满足最优解判定条件，但人工变量x7仍未迭代出去，可知原问题无可行解(无解)。运筹学作业标准答案(教师用)5No.3线性规划的对偶问题解：对偶问题为不限321313213121321,0,005322..645)(minyyyyyyyyyyyytsyyyyg0,0,12841426321332211xxxxxxxxx不限令改写后约束条件每行对应的对偶变量为y1,...,y6，则有对偶规划如下：0,,,0,,834..12841426)(max642531654321654321yyyyyyyyyyyytsyyyyyyyg1、写出下列线性规划问题的对偶问题：(1)不限4321432314321321,0,,06425..532)(maxxxxxxxxxxxxxxtsxxxxf(2)81214462..834)(min321321xxxtsxxxxf解：原问题的约束条件可改写为右式运筹学作业标准答案(教师用)62、写出下问题的对偶问题，解对偶问题，并证明原问题无可行解解：对偶问题为约束条件标准化为0,,324..)(min32132131321yyyyyyyytsyyyyg0,,,,3+24543215321431yyyyyyyyyyyy有对偶问题解的单纯形表如下：Cj11100CBYBby1y2y3y4y50y44101100y531(1)201OBJ=0zj00000zjcj11100Cj11100CBYBby1y2y3yy50y4410(1)101y2311201OBJ=3zj11201zjcj00101Cj11100CBYBby1y2y3y4y51y34101101y21131021OBJ=7zj21111zjcj10011入变量答：迭代到第三步，x1为入变量，但主列中技术系数全为负值，故对偶问题有可行解但解无界，由弱对偶定理推论可知，原问题无可行解。,0,1211..34)(max212122121xxxxxxxtsxxxf运筹学作业标准答案(教师用)73、用对偶单纯形法求下面问题0,753802..64)(min21212121xxxxxxtsxxxf解：Cj4600min{(zj-cj)/ai*j}CBXBbx1x2x3x4ai*j00x3801(2)10{4,3*}0x4753101OBJ=0zj0000zj-cj4600Cj4600CBXBbx1x2x3x46x2401/211/200x435(5/2)01/21{2/5*,6}OBJ=240zj3630zj-cj1030Cj4600CBXBbx1x2x3x46x233013/51/54x114101/52/5OBJ=254zj4614/52/5zj-cj0014/52/5答：最优解为x1=14，x2=33，目标函数值为254。No.4线性规划的灵敏度分析1、下表是一线性规划最优解的单纯形表Cj2194000CBXBbx1x2x3x4x5x621x14101/32/301/30x52002/34/311/39x223011/31/302/3zj219101101cjzj0061101原问题为max型，x4，x5为松驰变量，x6为剩余变量，回答下列问题：(1)资源1、2、3的边际值各是多少？(x4，x5是资源1、2的松驰变量，x6是资源3的剩余变量)(2)求C1,C2和C3的灵敏度范围；(3)求b1，b2的灵敏度范围。解：(1)q1=11,q2=0,q3=1。(2)x1,x2为基变量，故运筹学作业标准答案(教师用)8max/,/,/max,.,61311231131816533181111CCCCmax/min/,/..61311131231815105222CCC9x3为非基变量，故CC33610(3)5.163/123,3/42min3/24max11bb同理有22bNo.5运输问题1、